Precise, automatic and fast method for vanishing point detection

A new automated approach for vanishing point detection in images of urban scenes is described. This method is based on the theorem of Thales. The main contribution of this paper is the automatic and simultaneous detection of all vanishing points of the image, achieved by converting this problem into the detection of circles in a complex cloud of points, in which each point corresponds to a segment and is associated with an uncertainty. This extraction of circles uses a RANSAC method, modified to improve its speed by using accumulation techniques (Hough transform or otherwise). This robust estimation is then refined by least squares error propagation using the individual variances of each segment. The algorithm is robust, its accuracy is optimised and it is entirely automatic. Its successful operation has been tested on a large number of images of varied urban scenes. Resume Un algorithme entierement automatique de detection de points de fuite dans des images de scenes urbaines est presente. Cette approche s’appuie sur un theoreme classique (theoreme de Thales), qui permet de transformer le probleme de detection des points de fuite a partir de segments et leur incertitude en un probleme de detection de cercles dans un nuage de points (chaque point correspond a un segment, et a chaque point on associe une incertitude). L’extraction de cercles utilise une methode robuste de type RANSAC, modifiee pour etre tres rapide par rapport a des techniques accumulatives (de type Hough ou autres). Cette estimation robuste est ensuite raffinee par une propagation d’incertitude par moindres carres exploitant les variances individuelles de chaque segment. L’algorithme developpe est robuste, sa precision est la meilleure au sens des moindres carres compte tenu des incertitudes associees aux segments detectes, et en outre il est entierement automatique. Son bon fonctionnement a ete teste sur un grand nombre d’images representant des paysages urbains varies. Zusammenfassung Es wird ein neuer, automatisierter Ansatz zur Bestimmung von Fluchtpunkten in Bildern urbaner Szenen vorgestellt. Die Methode basiert auf dem Satz des Thales. Der wesentliche Beitrag ist die automatische und simultane Detektion aller Fluchtpunkte eines Bildes durch Invertierung dieses Problems in die Aufgabe der Bestimmung von Kreisen in komplexen Punktwolken, in denen jeder Punkt zu einem Segment gehort und mit einer Unsicherheit behaftet ist. Die Extraktion von Kreisen nutzt die RANSAC Methode, die zur Geschwindigkeitssteigerung modifiziert wurde, und sich auf Akkumulationstechniken, wie z.B. die Hough Transformation stutzt. Diese robuste Schatzung wird abschliesend durch Fehlerfortpflanzung nach der Methode der Kleinsten Quadrate unter Ausnutzung der individuellen Varianzen jedes Segments verfeinert. Der Algorithmus arbeitet vollautomatisch, ist robust und die Genauigkeit ist optimiert. Die erfolgreiche Anwendung wurde an einer grosen Anzahl Bildern verschiedenster Stadtszenen getestet. Resumen Este articulo describe un procedimiento completamente automatico para la deteccion de puntos de fuga en imagenes de escenas urbanas. El principio se apoya en un teorema clasico (el teorema de Tales) que permite transformar el problema de la deteccion de los puntos de fuga a partir de segmentos y de su incertidumbre, en un problema de deteccion de circulos dentro de una nube de puntos en la que cada punto corresponde a un segmento y a cada punto se le asocia una incertidumbre. La extraccion de circulos utiliza un metodo robusto tipo RANSAC modificado para mejorar su velocidad comparado con tecnicas de acumulacion del tipo transformada de Hough u otras. Esta estimacion robusta se refina posteriormente mediante propagacion del error por minimos cuadrados utilizando las varianzas individuales de cada segmento. El algoritmo desarrollado es robusto, su precision es la mejor en el sentido de minimos cuadrados teniendo en cuenta las incertidumbres asociadas a los segmentos detectados y, ademas, es completamente automatico. Su buen funcionamiento se ha evaluado procesando muchas imagenes de escenas urbanas variadas.