# Graphs in Image Analysis

## Graphs in Image Analysis

Graph based representations are mainly used in image analysis to represent irregular structures. Graphs were used in segmentation, shape matching, video action description, technical drawings, fingerprint recognition, etc.

In the following subsections examples of graph based representations and their properties are given, followed by operations and some applications.

### Representing Topological Structures

Attributed neighbourhood graphs represent an image as a graph. Attributes are derived from the colours of the pixels. Neighbourhood relations are represented by edges.Standard and extended region adjacency graphs (RAG, RAG+) represent the adjacency relations of image regions in, for example, a segmentation. In addition to RAGs, which are simple graphs, RAG+'s keep some self loops and parallel edges to encode inclusion relations (e.g. non-empty self-loops and parallel edges bounding non empty-faces).

Adjacency, and more general, structure, also plays an important role in dynamic scenes i.e. processing of videos. In the TWIST project (Tracking with Structure in Computer Vision) we study the importance of structure for tracking. Structure is represented e.g. in a graph or more generally graph pyramid representation of the segmented image and correspondence can be found by graph matching (see Figure 1).

(a) | (b) |

Sometimes it is not necessary to keep a whole RAG, a spanning tree is enough. From all the spanning trees of a graph, the Minimum Spanning Tree [HK04] has the minimum sum of edge weights and characterizes the discrepancy of the represented image. Integral features capture important properties of regions. The integral tree [KHP04] is a representation labeling each vertex of a tree with the integral feature(s) of the subtree.

Functional Graphical Models [MK03c] (FGM) describe dependence between variables by means of implicit equations. Explicit modeling of functional dependencies by a hypergraph, creates a structure well-adapted to information retrieval and processing.

The eccentricity transform [KIHF06] represents an image by assigning to each point the longest of the shortest paths to any other point of the image. It is robust against Salt & Pepper noise and articulated motion.

### Data Structures

To represent the topology of a partition of the 2D plane, a pair of dual RAG+ can be used. Every edge in the primal graph is associated to an edge in the dual graph, and every vertex in the primal is associated to a face in the dual and vice versa.Combinatorial maps represent objects subdivided into cells of many dimensions. They use permutations (alpha, sigma) to encode relations between atomic elements called darts (half edges). In 2D, they act as planar graphs explicitly encoding the orientation of edges around vertices (see Figure 2). Like combinatorial maps, generalized maps are defined in any dimension, and use only involutions.

Homology groups extend the Euler characteristic to a topological invariant that characterizes an object X by its "holes" in any dimension p=0..dim(X), (denoted p-holes). These holes can be seen as connected components in dimension 0, tunnels in dimension 1, voids in dimension 2,... .

### Operations on graphs

To reduce a graph or a map (e.g. when building a pyramid) contraction and removal operations are used. In 2D edge contraction removes the edge and identifies its end vertices. Edge contraction preserves the topology of the surviving elements. When building irregular pyramids, every contraction is followed by a simplification step, which removes redundant self loops and parallel edges i.e. empty self-loops and parallel edges bounding empty faces. Edges contracted in parallel form subtrees of the graph called contraction kernels [BK03a].### Where are Graphs Used?

Applications of graph based representations range from representations for cognitive vision [IHK05] inspired from human descriptions of videos [IHKH06], to graph-based fingerprint representation [OK04] encoding topology, to human problem solving and the Traveling Salesman Problem [PSS+06], to extraction of primitives (e.g. junction points, line segments) from graphs of digital points that are typically obtained from skeletonization [MK03b], to homotopic transformation for both combinatorial maps and weighted combinatorial maps [MKH03], and to efficient processing of huge amounts of structured sensory data for vision [Kro03].## Image Pyramids

An image pyramid is a stack of successively smaller descriptions of an image. Data structures for describing an image range fromarrays to graphs, dual graphs, combinatorial maps, and generalized maps. They can be divided in fixed (arrays) and variable structure (graphs, maps), and, depending on this and the reduction method, image pyramids can be regular (predefined, regular structure) and irregular (adaptable, irregular structure).

### Construction of Irregular Pyramids

Irregular pyramids are constructed sequentially in a bottom-up manner using only local operations. These operations create vertical relations between the levels of the pyramid. The receptive field [BK02b, BK03b] of any vertex is the connected set of bottom level vertices that can be reached from it using the vertical relations. The higher in the pyramid, the larger the receptive field of the vertices, and thus the higher the areas on which the operations apply. This results in a gradual shift from local to global processing. Regions [BK02a] have been formally defined to associate vertices from higher levels to connected sets of vertices in the bottom level.Bottom-up construction of irregular pyramids has been studied on dual graphs and on combinatorial maps:

Dual-graphs were used to create hierarchies relating topology and geometry [KHL06,KH04c], and study abstraction on discrete representations [Kro02]. Their structure is adapted to the processed data and they correctly encode the topology in 2D.

Combinatorial maps have been used to create combinatorial pyramids [BK03a]. We have studied the properties of their construction [BK03b], and created efficient ways of representing them (e.g. implicit encoding [BK03c]). Contraction kernels have been fitted to the combinatorial map structure and rooted kernels have been defined [MBK04]. The notion of receptive fields has been extended to combinatorial pyramids [BK03b] and the reduction of 3D complexes has been studied [IIHK06a, IIHK06b].

#### Properties of Pyramids

The height of a pyramid influences the length of the paths traversed along the vertical relations, and should be as short as possible - preferably logarithmic with respect to the number of vertices in the base level [HGS+02a, KS02c]. Methods like MIES and MIDES [HGS+02b, HK03b] guarantee the desired height/reduction relation. They break big contraction kernels into many small ones which can be contracted in parallel.Height characteristics of irregular pyramids have also increased their acceptance as a model for the human visual system and as a representation suited for algorithms mimicking human performance. A study of irregular pyramids in this context has been presented in [KHPL05]. It shows the advantages of models based on irregular pyramids over the ones based on regular pyramids.

Contains and Inside Relationships within Combinatorial Pyramids [BK05, BK06] help discriminate between configurations where a simple analysis of the adjacency relations would not be enough. Orientation explicitly encoded by combinatorial maps is used to determine inside and outside of loops with only local computations.

#### Segmentation with Pyramids

Graphs, maps and irregular pyramids are very well suited for representing image and object segmentation. Concepts like the redundancy pyramid, applied to images [HMK04] (Figure 3) or videos [MKH04], rely on these structures.Together with the concepts of internal and external contrast, and an algorithm for finding the Minimum Spanning Tree, a new method for image segmentation was introduced. The method was defined and studied in the framework of dual-graph pyramids [HK03d, HK04, KH04a, HK03c] and (dual-) combinatorial map pyramids [IHKB05, HIKB05] (see Figure 4). A theoretical study of its properties has been made [IKH06] which shows in a transformed space its similarity with the watershed transform. Different decimation strategies have been tried [HIK06c], and benchmarking with respect to human segmentation [HIK06a], the normalized cut [HIK06b] and other minimum spanning tree based methods [HIKI05] has been done.

Segmentation is bound to connected regions. There are many cases where broken (non-connected) elements 'belong together', e.g. dotted or dashed lines. Grouping such elements in the irregular pyramid has also been used to 'bridge the representational gap between image and model features' [KH05, KH04b].

0 (160 000) | 21 (2387) | 27 (321) | 37 (41) | 42 (9) |

#### Matching with Pyramids

A very important step in a classical image processing system, matching, has evolved from one-to-one, to one-to-many, and finally to many-to-many. Many-to-many matching of segmentation hierarchies has been approached in [GPK02, GPK04] and applied to the matching of panoramic images [GPK03]. It is more robust than one-to-one and one-to-many but also more computationally expensive.An efficient representation for eigenimage representations based on pyramids is shown in [LBK02].

Associated Projects: CogVis, Twist

### More on representing image by graphs can be found here.

## References

[BK02a] | L. Brun and W. G. Kropatsch. Defining regions within the combinatorial pyramid framework. In Computer Vision - CVWW’02, Computer Vision Winter Workshop, pages 198 – 207, Bad Aussee, Österreich, 2002. |

[BK02b] | L. Brun and W. G. Kropatsch. Receptive fields within the combinatorial pyramid framework. In Discrete Geometry for Computer Imagery, 10th DGCI, pages 92 – 101, Bordeaux, Frankreich, 2002. |

[BK03a] | L. Brun and W. G. Kropatsch. Contraction kernels and combinatorial maps. Pattern Recognition Letters, 24(8):1051 – 1057, 2003. |

[BK03b] | L. Brun and W. G. Kropatsch. Construction of combinatorial pyramids. In 4th IAPR-TC15Workshop on Graph-based Representation in Pattern Recognition, pages 1 – 12, 2003. |

[BK03c] | L. Brun and W. G. Kropatsch. Implicite encoding of combinatorial pyramids. In Computer Vision Winter Workshop 2003, page 6, 2003. |

[BK05] | L. Brun and W. G. Kropatsch. Inside and outside within combinatorial pyramids. In M. vento L. Brun, editor, 5th IAPR-TC15 Workshop on Graph-based Representation in Pattern Recognition, pages 122 – 131, 2005. |

[BK06] | L. Brun and W. G. Kropatsch. Contains and inside relationships within combinatorial pyramids. Pattern Recognition, 39(4):515 – 526, 2006. |

[GPK02] | R. Glantz, M. Pelillo, and W. G. Kropatsch. Matching hierarchies of segmentations. In Computer Vision - CVWW’02, Computer Vision Winter Workshop, pages 149 – 158, Bad Aussee, ¨ Osterreich, 2002. |

[GPK03] | R. Glantz, M. Pelillo, and W. G. Kropatsch. Hierarchical matching of panoramic images. In 12th International Conference on Image Analysis and Processing, pages 328–333, 2003. |

[GPK04] | R. Glantz, M. Pellilo, and W. G. Kropatsch. Matching segmentation hierarchies. International Journal of Pattern Recognition and Artificial Intelligence, 18, 2004. |

[HGS+02a] | Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. G. Kropatsch. Logarithmic tapering graph pyramid. In Proceedings of 24th DAGM Symposium, pages 117 – 124, Zürich, Schweiz, 2002. |

[HGS+02b] | Y. Haxhimusa, R. Glantz, M. Saib, G. Langs, and W. G. Kropatsch. Reduction factors of image pyramid on undirected and directed graph. In Proceedings of the 7th. Computer Vision Winter Workshop, pages 29 – 38, Bad Aussee, 2002. |

[HIK06a] | Y. Haxhimusa, A. Ion, and W. G. Kropatsch. Comparing hierarchies of segmentations: Humans, normalized cut, and minimum spanning tree. In Digital Imaging and Pattern Recognition, pages 95 – 103, Obergurgl, 2006. |

[HIK06b] | Y. Haxhimusa, A. Ion, and W. G. Kropatsch. Evaluating hierarchical graphbased segmentation. In The 18th International Conference on Pattern Recognition, pages 195 – 198, Hong Kong, 2006. |

[HIK06c] | Y. Haxhimusa, A. Ion, and W. G. Kropatsch. Irregular pyramid segmentations with stochastic graph decimation strategies. In Progress in Pattern Recognition, Image Analysis and Applications, pages 277 – 286, Cancun, Mexico, 2006. |

[HIKB05] | Y. Haxhimusa, A. Ion, W. G. Kropatsch, and L. Brun. Hierarchical image partitioning using combinatorial maps. In D. Chetverikov, L. Czuni, and M. Vincze, editors, Hierarchical Image Partitioning using Combinatorial Maps, pages 179 – 186, 2005. |

[HIKI05] | Y. Haxhimusa, A. Ion, W. G. Kropatsch, and T. Illetschko. Evaluating minimum spanning tree based segmentation algorithms. In A. Gagalowicz and W. Philips, editors, Computer Analysis of Images and Patterns: 11th International Conference, CAIP 2005, pages 579 – 586, 2005. |

[HK03b] | Y. Haxhimusa and W. G. Kropatsch. Constructing stochastic pyramids by mides - maximal independent directed set. In 4th IAPR-TC 15 Workshop on Graph based Representation in Pattern Recognition, page 11, 2003. |

[HK03c] | Y. Haxhimusa and W. G. Kropatsch. Hierarchical image partitioning with graph pyramids. In Proceedings of the 25th DAGM Symposium, page 8, 2003. |

[HK03d] | Y. Haxhimusa and W. G. Kropatsch. Image partitioning with graph pyramids. In Proceedings of 25th AGM Workshop, page 7, 2003. |

[HK04] | Y. Haxhimusa and W. G. Kropatsch. Segmentation graph hierarchies. In Proceedings of Joint International Workshops on Structural, Syntactic, and Statistical Pattern Recognition S+SSPR 2004, pages 343 – 351, 2004. |

[HMK04] | A. Hanbury, J. Marchadier, and W. G. Kropatsch. The redundancy pyramid and its application to image segmentation. In Digital Imaging in Media and Education, Proc. of the 28th Workshop of the Austrian Association for Pattern Recognition (OAGM/AAPR), pages 157 – 164, 2004. |

[IHK05] | A. Ion, Y. Haxhimusa, and W. G. Kropatsch. A graph-based concept for spatiotemporal information in cognitive vision. In M. vento L. Brun, editor, 5th IAPR-TC15 Workshop on Graph-based Representation in Pattern Recognition, pages 223 – 232, 2005. |

[IHKB05] | A. Ion, Y. Haxhimusa, W. G. Kropatsch, and L. Brun. Hierarchical image partitioning using combinatorial maps. In H. Bischof A. Hanbury, editor, 10th Computer Vision Winter Workshop - CVWW 2005, pages 43 – 52, 2005. |

[IHKH06] | A. Ion, H. Hausegger, W. G. Kropatsch, and Y. Haxhimusa. How humans describe short videos. In Proceedings of the Second International Cognitive Vision Workshop, 2006. |

[IIHK06a] | T. Illetschko, A. Ion, Y. Haxhimusa, and W. G. Kropatsch. Collapsing 3d combinatorial maps. In Digital Imaging and Pattern Recognition, pages 85 – 93, Obergurgl, 2006. |

[IIHK06b] | T. Illetschko, A. Ion, Y. Haxhimusa, and W. G. Kropatsch. Distinguishing the 3 primitive 3d-topological configurations: Simplex, hole, tunnel. In Proceedings of the 11th Computer Vision Winter Workshop, pages 22 – 27, Telc, Czech Republik, 2006. |

[IKH06] | A. Ion, W. G. Kropatsch, and Y. Haxhimusa. Considerations regarding the minimum spanning tree pyramid segmentation method. In Structural, Syntactic, and Statistical Pattern Recognition, pages 182 – 190, Hong Kong, 2006. |

[KH04a] | W. G. Kropatsch and Y. Haxhimusa. Grouping and segmentation in a hierarchy. In Computational Imaging II, pages 193 – 204, 2004. |

[KH04b] | W. G. Kropatsch and Y. Haxhimusa. Hierarchical grouping of non-connected structures. In Digital Imaging in Media and Education, Proc. of the 28th Workshop of the Austrian Association for Pattern Recognition (OAGM/AAPR), pages 165 – 172, 2004. |

[KH04c] | W. G. Kropatsch and Y. Haxhimusa. Hierarchies relating topology and geometry. In Cognitive Vision Systems, 2004. |

[KH05] | W. G. Kropatsch and Y. Haxhimusa. Grouping of non-connected structures by an irregular graph pyramid. In P. Pina J. Marques, N. de la Blanca, editor, Pattern Recognition and Image Analysis: Second Iberian Conference, IbPRIA 2005, pages 107 – 114, 2005. |

[KHL06] | W. G. Kropatsch, Y. Haxhimusa, and P. Lienhardt. Cognitive Vision Systems: Sampling the Spectrum of Approaches, chapter 13. Hiearchies relating Topology and Geometry, pages 199 – 220. Springer LNCS, Berlin - Heidelberg - New York, 2006. |

[KHP04] | W. G. Kropatsch, Y. Haxhimusa, and Z. Pizlo. Integral trees: Subtree depth and diameter. In Proceedings of the IWCIA 2004, pages 77 – 87, 2004. |

[KHPL05] | W. G. Kropatsch, Y. Haxhimusa, Z. Pizlo, and G. Langs. Vision pyramids that do not grow too high. Pattern Recognition Letters, 26(3):319 – 337, 2005. |

[KIHF06] | W. G. Kropatsch, A. Ion, Y. Haxhimusa, and T. Flanitzer. The eccentricity transform (of a digital shape). In Discrete Geometry for Computer Imagery, pages 437 – 448, Szeged, Ungarn, 2006. |

[Kro02] | W. G. Kropatsch. Abstraction pyramids on discrete representations. In Discrete Geometry for Computer Imagery, 10th DGCI, pages 1 – 21, Bordeaux, Frankreich, 2002. |

[Kro03] | W. G. Kropatsch. Benchmarking graph matching algorithm. Pattern Recognition Letters, 24(8):1051 – 1059, 2003. |

[KS02c] | W. G. Kropatsch and M. Saib. The optimal height of a graph pyramid. In Vision with Non-Traditional Sensors 26th ¨ OAGM Workshop, pages 87 – 94, Graz, Österreich, 2002. |

[LBK02] | G. Langs, H. Bischof, and W. G. Kropatsch. Hierarchical top-down enhancement of robust pca. In Proceedings of IAPR Int. Workshop on Syntactical and Structural Pattern Recognition (SSPR 2002), LNCS 2396, pages 131 – 136, Windsor, Kanada, 2002. |

[MBK04] | J. Marchadier, L. Brun, and W. G. Kropatsch. Rooted kernels and labeled combinatorial pyramids. In Computer Vision Winter Workshop - CVWW’04, pages 59 – 68, 2004. |

[MK03b] | J. Marchadier and W. G. Kropatsch. Extraction of curve segments and junctions by graph based optimization. In Vision in a Dynamic World 27th ÖAGM Workshop, 2003. |

[MKH03] | J. Marchadier, W. G. Kropatsch, and A. Hanbury. Homotopic transformation of combinatorial maps. In Discrete Geometry for Computer Imagery, pages 134 – 143, Neapel, Italy, 2003. |

[MKH04] | J. Marchadier, W. G. Kropatsch, and A. Hanbury. The redundancy pyramid and its application to segmentation on an image sequence. In DAGM Symposium 2004, pages 432 – 439, 2004. |

[MK03c] | J. Marchadier and W. G. Kropatsch. Functional modeling of structures images. In 4th IAPR-TC15 Workshop on Graph-Based Representation in Pattern Recognition, page 12, 2003. |

[OK04] | W. Ölz and W. G. Kropatsch. Graph representation of fingerprint topology. In Computer Vision Winter Workshop- CVWW’04, pages 51 – 58, 2004. |

[PSS+06] | Z. Pizlo, E. Stefanov, J. Saalweachter, Y. Haxhimusa, and W. G. Kropatsch. Traveling salesman problem: A foveating pyramid model. The Journal of Problem Solving, 1(1):83 – 101, 2006. |