Balls hierarchy: Image segmentation by graph spanner

We propose a novel approach for solving the image segmentation and grouping problem. Our approach focuses on color and regional proximity relations in the image data. We treat image pixels as nodes in the graph so that proximity relations among both pixel´s color and position are kept in geometric spanners. Geometric spanners for both color and position are created in hierarchical data structure so-called balls hierarchy. Balls hierarchy creates a multiresolution hierarchical subgraph that reflects a great deal about the original graph while maintaining all the existing proximity information in the image. We show that balls hierarchy can be used for image segmentation and grouping problems. We have applied our novel approach to several exemplary images such as histopathologic images and found results encouraging.