Share Email Print

Proceedings Paper

Structural graph-matching approach to image understanding
Author(s): Gary P. Ford; Jun Zhang
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Image understanding is a broad field of image processing where the goal is to classify the elements of a scene. In this paper we describe an approach to image understanding based on the matching of structure graphs. The structure graph of the input image is composed of `nodes' (primitives extracted from the image, e.g., regions, line segments) and `edges' (relationships between primitives in the image). The goal of our algorithm is to find the best match between this graph and a prototype graph, representing the knowledge about the expected scene. We formulate the graph matching problem as a consistent labeling problem, where the nodes of the prototype graph are considered labels. We then search for a labeling of the input structure graph that is optimal in the sense that the nodes and edges of the input graph are consistent with the labels and relationships represented in the prototype graph. A `quality of fit' measurement is derived for the matching, and a genetic algorithm is used to find the optimal solution. The advantages of this method of inexact (or fuzzy) matching include its graceful degradation (robustness) in the presence of noise and image deformation, its parallelism, and its adaptability to a variety of domains. We complete this work with the discussion of experimental results.

Paper Details

Date Published: 1 February 1992
PDF: 11 pages
Proc. SPIE 1607, Intelligent Robots and Computer Vision X: Algorithms and Techniques, (1 February 1992); doi: 10.1117/12.57092
Show Author Affiliations
Gary P. Ford, Allen-Bradley Co. (United States)
Jun Zhang, Univ. of Wisconsin/Milwaukee (United States)

Published in SPIE Proceedings Vol. 1607:
Intelligent Robots and Computer Vision X: Algorithms and Techniques
David P. Casasent, Editor(s)

© SPIE. Terms of Use
Back to Top