臺灣博碩士論文加值系統

本論文由兩部分組成，在第一部分中，我們研究了圖信號(Graph Signals)下採樣方法，圖信號處理是一個新興的信號處理領域讓我們可以處理分析結構不規則信號，時至今日變得越來越重要。而這些圖形信號的操作也成為了最近的許多研究的主題，尤其是對於諸如移動，調變和採樣的基本信號的操作。然而，在應用中的圖的尺寸可以非常大，所以導致儲存或分析這些資料成為了一個重大的技術挑戰。要在圖表更有效地壓縮這些數據，我們提出了一個預過濾分類器(Pre-filtering Classifer)，其會考慮信號在圖上的分佈，可以有選擇性地進行信號的採樣。相比於其它方法，如著色法(Color-based)和基於拓撲方法(Topology-based)，我們提出的方法可以得到較高的信噪比。而且我們的方法可以很有效率的在短時間之內得到一定的壓縮效果。

本論文的第二部分會談到有關如何使用快速局部卷積神經網路(Fast R-CNN)開發一些物體偵測的應用，從運算環境的設置包括GPU的建置和可平行運算的快速局部卷積神經網路的平台的建置，到如何進行該演算法的學習以及測試。近年來通過使用基於局部卷積神經網絡，物體檢測的正確性有著大幅的進展，而快速局部卷積神經網路演算法可幫助我們即時的得到成果縱使是使用非常深層的網絡架構時。為了更加理解這種高效能方法，我們提出了它的一些應用。另外類似的機器學習技術也可以用在圖信號處理中。

This thesis consists of two sections. In the first section, we study the downsampling methods for graph signals. Graph Signal Processing is an emerging field of signal processing for us to analysis irregular structure signals and becomes more and more significant in these days. The operations on these datasets as graph signals have been subjects to many recent studies, especially for basic signal operations such as shifting, modulating, and down-sampling. However, the sizes of the graphs in the applications can be very large and lead a lot of computational and technical challenges for the purpose of storage or analysis. To compress these datasets on graphs more effectively, we propose a pre-filtering classifier can selectively downsample signals and also consider the distribution of the signals on graphs. As compared to the other methods, such as color-based methods and topology-based methods, our proposed method can achieve better performance in terms of higher SNR. Moreover, our method can be processed efficiently and efficacy in terms of shorter computing-time and fewer vertices in use during compression.

The second section of this thesis talks about how to use Fast Regions with Convolutional Neural Network (Fast R-CNN) to develop some object detection applications from the building of the environment including the setup of GPU and the platform of parallel computing to the process of training and testing in fast R-CNN algorithm. By using region-based convolutional neural networks, the correctness of object detection has a large progress in recent years, and fast R-CNN algorithm helps us to achieve near real-time rates when using very deep networks. To realize this efficient and powerful method more, some applications based on it are also proposed. Further, a machine learning technique is also applied to graph signal processing.

致謝……………………………………………………………………………………i
中文摘要………………………………………………………………………………ii
ABSTRACT…………………………………………………………………………..iii
CONTENTS…………………………………………………………………………...v
LIST OF FIGURES……………………………………………………………….......ix
LIST OF TABLES…………………………………………………………………...xiii
Chapter 1 Introduction…………………………………………………………………1
1.1 Introduction for Graph Signal Processing…………………………………….1
1.1.1 Background……………………………………………………………1
1.1.2 Graph Definition………………………………………………………3
1.1.3 Graph Laplacian matrix……………………………………………….5
1.2 Introduction for Object Detection by Fast R-CNN………………………….10
Chapter 2 Technique in Graph Signal Processing…………………………………….11
2.1 Bipartite Graph Downsampling and Graph Signal Filterbanks……………..11
2.1.1 Graph Fourier Transform…………………………………………….12
2.1.2 Spectral Folding Phenomenon of Bipartite Graphs…………………..13
2.1.3 Perfect Reconstruction Filterbanks on Graphs……………………….16
2.2 Perfect Reconstruction Condition of Oversampled Graph Filterbanks……...18
2.2.1 Four Channel Case…………………………………………………...19
2.2.2 General M-Channel Case…………………………………………….21
2.3 Oversampled Graph Signals…………………………………………………23
2.3.1 Oversampled Graph Laplacian Matrix……………………………….23
2.3.2 Effective Graph Expansion Methods………………………………...26
2.4 Coarsening Graph Signals with Spectral Invarience………………………...30
2.4.1 Dimensionality Reduction with Spectral Invariance…………………30
2.4.2 Problem Formulation and Optimal Algorithm……………………….32
2.5 Sampling Theorem for Discrete Signal Processing on Graphs………………37
2.5.1 Sampling on Graph…………………………………………………..37
2.5.2 Construction Downsampled Graphs for Signals……………………..39
2.5.3 Optimal Sampling Operator……………………………………….....40
2.5.4 Graph Filter Banks…………………………………………………...41
2.5.5 Example……………………………………………………………...42
Chapter 3 Graph Filter Design Methods………………………………………………45
3.1 Graph Quadrature Mirror Filter (Graph-QMF) Design……………………..45
3.2 NonzeroDC Graphbior Filter Design………………………………..………49
3.3 ZeroDC Graphbior Filter Design……………………………………………54
3.4 Polyphase Representation Biorthogonal Graph Filter…..…………………...57
3.4.1 Polyphase Represention……………………………………………...57
3.4.2 Ladder Structure……………………………………………………..60
3.4.3 Some Filterbanks Examples………………………………………….63
Chapter 4 Graph Signal Compression………………………………………………...70
4.1 Color-Based Method………………………………………………………...70
4.2 MST-Based Method…………………………………………………………72
4.3 Proposed Method Using Pre-filtering Classifier…………………………….75
4.3.1 Pre-Filtering…………………………...……………………………..76
4.3.2 Greedy Algorithm……………………………………………………79
4.3.3 Isolated Vertices Keeping…………………………………………….79
4.4 Experimental Results………………………………………………………..84
4.4.1 Compression with Previous and Proposed Methods……………….....84
4.4.2 Improvement by Polyphase Biorthgonal Filters……………………...96
Chapter 5 Object Detection Application Using Fast R-CNN…………………………99
5.1 Region Proposed Networks.............................................................................99
5.1.1 Anchors……………………………………………………………..100
5.1.2 Training RPNs ………………………………………………...........101
5.2 Sharing Features for RPN and Fast R-CNN………………………………..101
5.3 Implement Techniques of Fast R-CNN………………………………..…...102
5.3.1 CUDA………………………………………………………………103
5.3.2 Caffe………………………………………………………………..103
5.3.3 ImageNet…………………………………………………………...104
5.4 Object Detection Experiment………………………………………………104
Chapter 6 Active Semi-Supervised Learning for Graph Signals…………………….108
6.1 Sampling Theorem for Graph Signals……………………………………...108
6.1.1 Problem 1: Cutoff Frequency…………………………………...…..110
6.1.2 Problem 2: Sampling Set……………………………………………111
6.1.3 Problem 3: Reconstruction………………………………………….112
6.2 Graph Sampling Based on Semi-Supervised Learning…………………......113
6.3 Handwritten Classification Experiments…………………………………..116
Chapter 7 Conclusions………………………………………………………………117
References …………………………………………………………………………..118

[1]M. Crovella and E. Kolaczyk, “Graph wavelets for spatial traffic analysis,” in Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), vol. 3, pp. 1848–1857, 2003.
[2]G. Shen and A. Ortega, “Optimized distributed 2D transforms for irregularly sampled sensor network grids using wavelet lifting,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 2513–2516, 2008.
[3]D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains,” IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 83–98, 2013.
[4]M. Tsitsvero and S. Barbarossa. “On the degrees of freedom of signals on graphs.” in Proceedings of the Signal Processing Conference (EUSIPCO), pp. 1531-1535, 2015.
[5]B. Girault. “Stationary graph signals using an isometric graph translation.” in Proceedings of the Signal Processing Conference (EUSIPCO), pp. 1521-1525, 2015.
[6]G. Shen and A. Ortega, “Transform-based distributed data gathering,” IEEE Transactions on Signal Processing, vol. 58, no. 7, pp. 3802–3815, 2010.
[7]C. Zhang and D. Florêncio, “Analyzing the optimality of predictive transform coding using graph-based models,” IEEE Signal Processing Letters, vol. 20, no. 1, pp. 106–109, 2012.
[8]X. Wang, P. Liu, and Y. Gu, “Local-set-based graph signal reconstruction,” IEEE Transactions on Signal Processing, vol. 63, no. 9, pp.2432-2444, 2015.
[9]V. Ekambaram, G. Fanti, B. Ayazifar, and K. Ramchandran, “Spline-like wavelet filterbanks for multiresolution analysis of graph-structured data,” IEEE Transactions on Signal and Information Processing Over Networks, vol. 1, no. 4, pp. 268-278, 2015.
[10]S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, “Discrete signal processing on graphs: sampling theory”, IEEE Transactions on Signal Processing, vol. 63, no. 24, 2015.
[11]S. K. Narang and A. Ortega, “Downsampling graphs using spectral theory,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 4208-4211, 2011.
[12]S. K. Narang and A. Ortega, “Perfect reconstruction two-channel wavelet filter banks for graph structured data,” IEEE Transactions on Signal Processing, vol. 60, no. 6, pp. 2786–2799, 2012.
[13]S. K. Narang and A. Ortega, “Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs,” IEEE Transactions on Signal Processing, vol. 61, no. 19, pp. 4673–4685, 2013.
[14]Y. Tanaka and A. Sakiyama. “M-channel oversampled perfect reconstruction filter banks for graph signals,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 1604-1608. 2014.
[15]Y. Tanaka and A. Sakiyama. “M-channel oversampled graph filter banks,” IEEE Transactions on Signal Processing, vol. 62, no. 14, pp. 3578–3590, 2014.
[16]A. Sakiyama and Y. Tanaka. “Oversampled bipartite graphs with controlled redundancy,” in Proceedings of the Signal Processing Conference (EUSIPCO), pp. 1526-1530, 2015.
[17]S. K. Narang and A. Ortega, “Local two-channel critically sampled filter-banks on graphs,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 333–336, 2010.
[18]H. Q. Nguyen and M. N. Do, “Downsampling of signals on graphs via maximum spanning trees,” IEEE Transactions on Signal Processing, vol. 63, no. 1, pp. 182-191, 2015.
[19]Fan R. K. Chung, “Spectral graph theory,” CBMS Regional Conference Series in Math., No. 92, American Mathematical Society, February 1997.
[20]U. Luxburg, “A tutorial on spectral clustering,” Statistics and Computing, vol. 17, no. 4, pp. 395–416, 2007.
[21]David K. Hammond, Pierre Vandergheynst, and R´emi Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129–150, 2011.
[22]S. Lafon and A. B. Lee, “Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 9, pp. 1393-1403, 2006.
[23]D. Ron, I. Safro, and A. Brandt, “Relaxation-based coarsening and multiscale graph organization,” Multiscale Modeling&Simulation, vol. 9, no. 1, pp. 407-423, 2011.
[24]G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 359-392, 1998.
[25]I. S. Dhillon, Y. Guan, and B. Kulis, “Weighted graph cuts without eigenvectors a multilevel approach,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 11, pp. 1944-1957, 2007.
[26]D. Gfeller and P. De Los Rios, “Spectral coarse graining of complex networks,” Physical Review Letters, vol. 99, no. 3, pp. 038701, 2007.
[27]Liu, Pengfei, Xiaohan Wang, and Yuantao Gu. “Coarsening graph signal with spectral invariance.” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 1070-1074, 2014.
[28]Sandryhaila, Aliaksei, and José MF Moura. “Discrete signal processing on graphs,” IEEE Transactions on Signal Processing vol. 61, no. 7, pp. 1644-1656, 2013
[29]S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovaˇcevi´c, “Sampling theory for graph signals,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3392-3396, 2015.
[30]R. A. Horn and C. R. Johnson, “Matrix analysis,” Cambridge University Press, Cambridge, 1985.
[31]M. Vetterli, J. Kovaˇcevi´c, and V. K. Goyal, “Foundations of signal processing,” Cambridge University Press, 2014, http://www.fourierandwavelets.org/.
[32]M. Vetterli, “A theory of multirate filter banks,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), vol. 35, no. 3, pp. 356–372, 1987.
[33]A. Cohen, I. Daubechies, and J.-C. Feauveau, “Biorthogonal bases of compactly supported wavelets,” Communications on Pure and Applied Mathematics, vol. 45, no. 5, pp. 485–560, 1992.
[34]M. Vetterli and J. Kovaˇcevic, “Wavelets and subband coding,” Prentice-Hall Inc., NJ, USA, 1995.
[35]David BH Tay, and Jingxin Zhang. “Techniques for constructing biorthogonal bipartite graph filter banks.” IEEE Transactions on Signal Processing, vol. 63, no. 21, pp. 5772-5783, 2015.
[36]H. Caglar and A. N. Akansu, “A generalized parametric PR-QMF design technique based on Bernstein polynomial approximation,” IEEE Transactions on Signal Processing, vol. 41, no. 7, pp. 2314–2321, 1993.
[37]David S. Johnson, “The NP-completeness column: an ongoing guide,” Journal of Algorithms, vol 6, no.3, pp.434-451, 1985.
[38]R. C. Prim, “Shortest connection networks and some generalizations,” Bell system technical journal, vol. 36, no. 6, pp. 1389–1401, 1957.
[39]J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” in Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956.
[40]J. Long, E. Shelhamer, and T. Darrell, “Fully convolutional networks for semantic segmentation,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),pp.3431-3440, 2015.
[41]M. D. Zeiler and R. Fergus, “Visualizing and understanding convolutional neural networks,” in Proceedings of the European Conference on Computer Vision (ECCV), pp.818-833, 2014.
[42]K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” in Proceedings of the International Conference on Learning Representations (ICLR), pp.1409-1556, 2015.
[43]R. Girshick, “Fast R-CNN,” in Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 1440-1448, 2015.
[44]V. Nair and G. E. Hinton, “Rectified linear units improve restricted boltzmann machines,” in Proceedings of the International Conference on Machine Learning (ICML), pp.807-814, 2010.
[45]Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel, “Backpropagation applied to handwritten zip code recognition,” Neural computation, vol. 1, no. 4, 541-551, 1989.
[46]Nvidia Geforce Titan-X Official Website, http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-titan-x
[47]Nvidia CUDA Official Website, http://www.geforce.com/hardware/technology/cuda
[48]Jia, Yangqing, et al. “Caffe: convolutional architecture for fast feature embedding.” in Proceedings of the ACM International Conference on Multimedia. ACM, pp.675-678, 2014.
[49]ImageNet Official Website, http://image-net.org/index
[50]Ren, Shaoqing, et al. “Faster R-CNN: towards real-time object detection with region proposal networks.” Advances in Neural Information Processing Systems, pp. 91-99, 2015.
[51]Gadde, Akshay, Aamir Anis, and Antonio Ortega. “Active semi-supervised learning using sampling theory for graph signals.” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 91-99, 2014.
[52]I. Pesenson, “Sampling in Paley-Wiener spaces on combinatorial graphs,” Transactions of the American Mathematical Society, vol. 360, no. 10, 5603-5627, 2008.
[53]A. Anis, A. Gadde, and A. Ortega, “Towards a sampling theorem for signals on arbitrary graphs,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3862-3868, 2014.
[54]K. Sauer and J. Allebach, “Iterative reconstruction of bandlimited images from nonuniformly spaced samples,” IEEE Transactions on Circuits and Systems, vol. 34, no. 12, pp. 1497-1506, 1987.
[55]S. K. Narang, A. Gadde, E. Sanou, and A. Ortega, “Localized iterative methods for interpolation in graph structured data,” in Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 491-494, 2013.