XPMaps and Topological Segmentation - A Unified Approach to Finite Topologies in the Plane

Ullrich KötheDGCI 2002 · OpenReview

Abstract

Finite topological spaces are now widely recognized as a valuable tool of image analysis. However, their practical application is complicated because there are so many different approaches. We show that there are close relationships between those approaches which motivate the introduction of XPMaps as a concept that subsumes the important characteristics of the other approaches. The notion of topological segmentations then extends this concept to a particular class of labelings of XPMaps. We show that the new notions lead to significant simplifications from both a theoretical and practical viewpoint.

Introduction

In computer vision, understanding the topology of an image—how pixels form neighborhoods, boundaries, and connected regions—is fundamental for robust image segmentation. Over the years, researchers have proposed numerous ways to represent these finite 2D topologies, including abstract cellular complexes, combinatorial maps, and Khalimsky grids.

However, because these methods originate from different mathematical sub-fields (like graph theory vs. product topologies) and are often presented in isolation, it is difficult for researchers to compare them or build reusable, general-purpose software tools. This paper addresses this fragmentation by establishing formal relationships between these disparate models and introducing "XPMaps" (Extended Planar Maps) as a generalized data structure that captures the best properties of all of them.

Theoretical Framework: XPMaps

The paper establishes that any finite topology induced by a division of the plane can be represented by a planar cell complex. While standard combinatorial maps represent topologies using permutations of half-edges (darts) to define nodes, edges, and faces, they often struggle with disconnected graphs or regions with holes (non-simply connected regions).

A planar cell complex showing nodes (N), faces (F), and their connectivity.

To overcome these limitations, the author introduces the XPMap. An XPMap groups multiple combinatorial maps and links them using explicit exterior and contains relations. This allows the framework to handle complex, real-world image topologies, such as a "donut" shape where one region is contained within the hole of another.

Euler Operators and Reduction

A core component of the framework is a complete set of elementary Euler operators. These operations, such as node splitting, edge merging, and face splitting, allow for the modification of an XPMap's topology while strictly preserving its planarity according to Euler's formula.

An example of an Euler operator: edge contraction merging two nodes while preserving topology.

The concept of "topological segmentation" is then introduced. Instead of relying on strict geometric rules, a segment is defined by its ability to be mathematically "reduced" to a single point, line, or face using these Euler operators. This approach elegantly bypasses the "simply connected" limitation of traditional methods, allowing regions to have holes as long as they remain logically reducible.

Key Results and Theorems

The primary contribution of this work is the mathematical proof of interoperability between previously isolated models:

  • Equivalence: Theorems 1 and 2 prove that any finite topology from a plane division can be represented by a planar cell complex and, if connected, by a planar combinatorial map.
  • Grid Integration: Theorem 4 establishes that a Khalimsky grid, when modified with an "infinite point" for the outer boundary, perfectly defines a corresponding XPMap.
  • Completeness: Theorem 5 demonstrates that any connected open set in an XPMap can be reduced to a single face using the proposed Euler operators, proving the framework's utility for image reduction and analysis.

Conclusion and Future Directions

The introduction of XPMaps and topological segmentations provides a unified theoretical and practical foundation for 2D image analysis. While transforming a 2-complex back into an XPMap remains challenging due to potential ambiguities in edge ordering without geometric data, the framework opens new avenues for research. Future work includes extending these concepts to 3D spaces and applying XPMaps to the construction of "irregular pyramids" for hierarchical, multi-scale image analysis.

Summary updated

Abstract

Finite topological spaces are now widely recognized as a valuable tool of image analysis. However, their practical application is complicated because there are so many different approaches. We show that there are close relationships between those approaches which motivate the introduction of XPMaps as a concept that subsumes the important characteristics of the other approaches. The notion of topological segmentations then extends this concept to a particular class of labelings of XPMaps. We show that the new notions lead to significant simplifications from both a theoretical and practical viewpoint.
BibTeX
@inproceedings{kothe2002xpmaps,
  author = {Ullrich Köthe},
  title = {{XPMaps and Topological Segmentation - A Unified Approach to Finite Topologies in the Plane}},
  booktitle = {DGCI},
  year = {2002},
  url = {https://openreview.net/forum?id=awyTGuaW3P},
}
Figure