Original paper

Finding Poly-Curves of Straight Line and Ellipse Segments in Images

Wenzel, Susanne; Förstner, Wolfgang

Abstract

Simplification of given polygons has attracted many researchers. Especially, finding circular and elliptical structures in images is relevant in many applications. Given pixel chains from edge detection, this paper proposes a method to segment them into straight line and ellipse segments. We propose an adaption of Douglas-Peucker's polygon simplification algorithm using circle segments instead of straight line segments and partition the sequence of points instead the sequence of edges. It is robust and decreases the complexity of given polygons better than the original algorithm. In a second step, we further simplify the poly-curve by merging neighbouring segments to straight line and ellipse segments. Merging is based on the evaluation of variation of entropy for proposed geometric models, which turns out as a combination of hypothesis testing and model selection. We demonstrate the results of circle Peucker as well as merging on several images of scenes with significant circular structures and compare them with the method of Patraucean et al. (2012).

Kurzfassung

Die Detektion runder und elliptischer Strukturen ist relevant für viele Anwendungen. Die Reduktion der Komplexität gegebener Polygone ist für sich ein interessantes Forschungsthema. Diese Arbeit stellt ein Verfahren zur Segmentierung von Pixelketten einer Kantendetektion in Geraden- und Ellipsensegmente vor. Der erste Schritt besteht in einer Adaption des Douglas-Peucker Algorithmus, in der Kreise anstelle von Geraden zur Partitionierung verwendet werden und die Punktstatt der Kantensequenz partitioniert wird. Das Verfahren ist robust und reduziert die Komplexität der gegebenen Polygone stärker als der originale Algorithmus. In einem zweiten Schritt vereinfachen wir diese Vorsegmentierung durch das Verschmelzen benachbarter Segmente zu Geraden- und Ellipsensegmenten und stützen uns dabei auf die Entropieänderung. Wir zeigen die Ergebnisse der Vorsegmentierung als auch der folgenden Vereinfachung anhand verschiedener Bilder von Szenen, die signifikante kreisförmige Strukturen aufweisen und vergleichen sie mit dem Algorithmus von Patraucean et al. (2012).

Keywords

polygon simplificationcircle and ellipse detectiongroupingmodel selection