ABSTRACT
This chapter explores the value of graphs in computer vision from the perspective of representing both structural quantum variations as well as metric changes, as applied to the matching and categorization problems. It briefly overviews an approach in using shock graph in matching and recognition, and proximity graphs in categorization. The key concept is that graphs can be viewed as capturing a notion of discrete topology, whether it is related to the shape space or to the category space. The technology for shape matching uses shock graphs, a form of the medial axis, while the technology for categorization uses proximity graphs. Exact metric search methods have focused their attention on the triangle inequality, which is weak in a high-dimensional space for partitioning space for access. Graphs are ideal structures to capture the local topology among points in a space. The chapter shows the comparison of proximity graphs to the kNN graphs.
