Similarity Analysis from Limiting Quantum Walks

详细信息    查看全文

• 关键词：Edge detection ; Spectral clustering schrödinger operator ; Quantum walks
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9370
• 期：1
• 页码：38-53
• 全文大小：833 KB
• 参考文献：1.Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8(6), 679–698 (1986)CrossRef
  2.Martin, D.R., Fowlkes, C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE Trans. Pattern Anal. Mach. Intell. 26(5), 530–549 (2004)CrossRef
  3.Dollar, P., Tu, Z., Belongie, S.: Supervised learning of edges and object boundaries. In: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2006, vol. 2, pp. 1964–1971. IEEE Computer Society, Washington, DC (2006)
  4.Lim, J.J., Zitnick, C.L., Dollár, P.: Sketch tokens: a learned mid-level representation for contour and object detection. In: 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23–28, pp. 3158–3165 (2013)
  5. Isola, P., Zoran, D., Krishnan, D., Adelson, E.H.: Crisp boundary detection using pointwise mutual information. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds.) ECCV 2014, Part III. LNCS, vol. 8691, pp. 799–814. Springer, Heidelberg (2014)
  6.Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 33(5), 898–916 (2011)CrossRef
  7.Zhou, X., Belkin, M., Srebro, N.: An iterated graph laplacian approach for ranking on manifolds. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21–24, pp. 877–885 (2011)
  8.Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000)CrossRef
  9.Qiu, H., Hancock, E.R.: Clustering and embedding using commute times. IEEE Trans. Pattern Anal. Mach. Intell. 29(11), 1873–1890 (2007)CrossRef
  10.Grady, L.: Random walks for image segmentation. TPAMI 28(11), 1768–1783 (2006)CrossRef
  11.Bai, L., Rossi, L., Torsello, A., Hancock, E.R.: A quantum jensen-shannon graph kernel for unattributed graphs. Pattern Recogn. 48(2), 344–355 (2015)CrossRef
  12.Rossi, L., Torsello, A., Hancock, E.R., Wilson, R.C.: Characterizing graph symmetries through quantum jensen-shannon divergence. Phys. Rev. E 88, 032806 (2013)CrossRef
  13.Mülken, O., Blumen, A.: Continuous-time quantum walks: models for coherent transport on complex networks. Phys. Rep. 502(2–3), 37–87 (2011)MathSciNet CrossRef
  14.Stone, M.: On one-parameter unitary groups in hilbert space. Ann. Math. 33(3), 643–648 (1932)CrossRef
  15.Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915–928 (1998)MathSciNet CrossRef
  16.Szemerédi, E.: Regular partitions of graphs. In: Colloques Internationaux CNRS 260-Problèmes Combinatoires et Théorie des Graphes, Orsay, pp. 399–401 (1976)
  17.Nourbakhsh, F., Bulò, S.R., Pelillo, M.: A matrix factorization approach to graph compression. In: 22nd International Conference on Pattern Recognition, ICPR 2014, Stockholm, Sweden, August 24–28, pp. 76–81. IEEE (2014)
  18. Sperotto, A., Pelillo, M.: Szemerédi’s regularity lemma and its applications to pairwise clustering and segmentation. In: Yuille, A.L., Zhu, S.-C., Cremers, D., Wang, Y. (eds.) EMMCVPR 2007. LNCS, vol. 4679, pp. 13–27. Springer, Heidelberg (2007) CrossRef
  19.Alon, N., Duke, R.A., Lefmann, H., Rödl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. J. Algorithms 16(1), 80–109 (1994)MATH MathSciNet CrossRef
  20.Nourbakhsh, F.: Algorithms for graph compression: theory and experiments. Ph.D. thesis, Dipartamento di Scienze Ambientali, Infomatica e Statisitica, Universitá Ca’Foscari, Venice, IT (2015)
  
• 作者单位：Manuel Curado (16) (17) (18)
  Francisco Escolano (16) (17) (18)
  Edwin R. Hancock (16) (17) (18)
  Farshad Nourbakhsh (16) (17) (18)
  Marcello Pelillo (16) (17) (18)
  
  16. Department of Computer Science and AI, University of Alicante, Alicante, Spain
  17. Department of Computer Science, University of York, York, UK
  18. DAIS - Unversità Ca’ Foscari Venezia, Venezia, Italy
  
• 丛书名：Similarity-Based Pattern Recognition
• ISBN：978-3-319-24261-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Similarity compression is a critical step to improve the efficiency of edge detection. In this paper, we compare two approaches for compressing/decompressing similarity matrices, being edge detection our application domain. In this regard, state-of-the-art contour detectors rely on spectral clustering where pixel or patch similarity is encoded in a symmetric weight matrix and the eigenvectors of the normalized Laplacian derived from this matrix are clustered in order to find contours (normalized cuts and its variants). Despite significant interest in learning the similarity measure for providing well localized boundaries, the underlying spectral analysis has played a subsidiary role, and has mostly been based on classical random walks and the heat kernel. However, recent findings based on continuous-time quantum walks suggest that under the complex wave equation there are long-range interactions not present in the classical case. In the case of the edge map this opens up a means of controlling texture in the edge map by a simple thresholding. In this paper, we use the long-time averages of quantum walks for edge detection, and show that texture is a consequence of short-rangedness of these interactions. This is due to the local-to-global property of limiting quantum walks. In addition, when analyzing the role of limiting quantum walks as intermediate/indirect similarity decompression, we find that quantum walks are able of recovering the original edge structure when a factorization compressor is used, whereas this is not the case when compression relies on the Szemeéredi Regularity Lemma, despite this latter method is by far more efficient.