Graph theoretical concepts for computer vision

Graphs are widely used in Computer Vision to represent the relational structure that exists in digital images as well as in the scenes shown by these images. This contribution starts with a collection of basic graph theoretical definitions including duality. These definitions are then used for an explicit representation of regions and boundaries in two dimensional digital images by pairs of dual graphs. Voronoi diagrams and Delaunay graphs are dual structures widely used to represent three and higher dimensional digital images. The contribution contains their definitions as well as some of their applications in the field of cellular biology and medicine. Two concluding sections of the contribution are dedicated to basic definitions of matching techniques and graph grammars. These techniques are frequently used to relate the content of an image to some pre-defined and application-specific knowledge of the world, or to the content of another image.