Abstract Pattern Matching Techniques
Abstract pattern matching involves stepping back from the image itself and working at a higher level, grouping features in an abstract way to infer the presence of objects. Graph matching has long been a conventional method for performing this task, but in the right circumstances a suitable adaptation of the generalized Hough transform can actually outperform it. This chapter discusses inference procedures and considers relational descriptions of scenes and the various types of searches that can be used with image data.
• the match graph approach for identifying objects from their point features.
• how the need for robustness against noise, clutter, and occlusion translates into the requirement for subgraph-subgraph isomorphism.
• the maximal clique paradigm.
• how symmetry can be used to simplify the matching task.
• how the generalized Hough transform can be used for point pattern matching.
• how order calculations can be used to compare the speeds of matching algorithms.
• how relational descriptors may be used for logical analysis of scenes.
• the different types of search algorithms that may be used in scene analysis.
This chapter completes the work of Part 2 by showing how the presence of objects can be inferred from point features as an alternative to edge features. Even with point features it is found that the Hough transform may sometimes be used with advantage. However, all inference techniques need to be analyzed for computational complexity and suitable optimizations made. The need for complexity analysis carries on with even more force in subsequent work—not least the more complex algorithms used for processing 3-D images in Part 3 of this volume.