DE102017201169A1 - Rechnergestütztes Bildverarbeitungsverfahren - Google Patents

Abstract

Die Erfindung betrifft ein rechnergestütztes Bildverarbeitungsverfahren zum Ermitteln von zueinander orthogonalen Ebenen (W, W) aus einer orientierten Punktwolke, die eine Anzahl N von mit einem Normalvektor (n, n) assoziierten Punkten (p, p) enthält, durch Auswählen eines Punktes (p) aus der Punktwolke mit assoziiertem Normalvektor (n) als ein mit einem Referenznormalvektor (n) assoziierten Referenzpunkt (p), Bestimmen einer Punktpaar-Relation (F(p,p)), die eine Mehrzahl von Punktpaar-Merkmalen enthält, für den Referenzpunkt (p) mit den weiteren Punkten (p) der Punktwolke, wobei die Punktpaar-Merkmale sich jeweils auf unterschiedliche geometrische Parameter des Referenzpunktes (p) und des jeweiligen weiteren Punktes (p) und/oder des Referenznormalvektors (n) und des jeweiligen weiteren Normalvektors (n) beziehen, Bestimmen einer durch den Referenzpunkt (p) und den Referenznormalvektor (n) definierten Referenzebene (W), wenn die Punktpaar-Relation (F(p,p)) eine vorgegebene Bedingung erfüllt, und Bestimmen einer zu der Referenzebene (W) orthogonalen Ebene (W) aus denjenigen weiteren Punkten (p) , deren Punktpaar-Relation (F(p,p)) ebenfalls die vorgegebene Bedingung erfüllt.

Description

• Die Erfindung betrifft ein Rechnergestütztes Bildverarbeitungsverfahren zum Ermitteln von zueinander orthogonalen Ebenen aus einer orientierten Punktwolke.
• Das Gebiet der Ermittlung von Ebenen in der Bildverarbeitung ist gut untersucht. Es wird unter anderem auf folgende Dokumente verwiesen:
1. [1] Borrmann et al., „The 3d hough transform for plane detection in point clouds: A review and a new accumulator design," 3D Research, vol. 2, no. 2, pp. 1-13, 2011
2. [2] Yang und Förstner, „Plane detection in point cloud data," 2010
3. [3] Deschaud und Goulette, „A fast and accurate plane detection algorithm for large noisy point clouds using filtered normals and voxel growing," Proceedings of 3D Processing, Visualization and Transmission Conference, 2010
4. [4] B. Drost und S. Ilic, „Local hough transform for 3d primitive detection," in 3D Vision (3DV), 2015 International Conference on, pp. 398-406
5. [5] Li et al., „Globfit: consistently fitting primitives by discovering global relations," in ACM Transactions on Graphics (TOG). ACM, 2011, vol. 30, p. 52
6. [6] Wang und Xu, „Shape detection from raw lidar data with subspace modeling," IEEE Transactions on Visualization and Computer Graphics, vol. PP, no. 99, pp. 1-1, 2016.
7. [7] Oehler et al., „Efficient multiresolution plane segmentation of 3d point clouds," in International Conference on Intelligent Robotics and Applications. Springer, 2011, pp. 145-156
8. [8] Oßwald et al., „From 3d point clouds to climbing stairs: A comparison of plane segmentation approaches for humanoids," in Humanoid Robots (Humanoids), 2011 11th IEEE-RAS International Conference on. IEEE, 2011, pp. 93-98
9. [9] Holz et al., „Real-time plane segmentation using rgb-d cameras," in Robot Soccer World Cup. Springer, 2011, pp. 306-317
10. [10] Xiao et al., „Threedimensional point cloud plane segmentation in both structured and unstructured environments," Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1641-1652, 2013
11. [11] Micusik et al., „Detection and matching of rectilinear structures," in Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on. IEEE, 2008, pp. 1-7
12. [12] Fond et al., „Généeration d'hypothèeses de façades utilisant des critèeres contextuels et structurels," in Reconnaissance des Formes et Intelligence Artificielle, 2016
13. [13] Herout und Dubskä, „Real projective plane mapping for detection of orthogonal vanishing points," in Proceedings of the British Machine Vision Conference, 2013, BMVA Press
14. [14] Singhal et al., „Top down approach to detect multiple planes from pair of images," in Proceedings of the 2014 Indian Conference on Computer Vision Graphics and Image Processing, New York, NY, USA, 2014, ICVGIP '14, pp. 53:1-53:8, ACM
15. [15] Micusk et al. „Towards detection of orthogonal planes in monocular images of indoor environments," in Robotics and Automation, 2008. ICRA2008. IEEE International Conference on. IEEE, 2008, pp. 999-1004
16. [16] Lee et al., „Mav visual slam with plane constraint," in Robotics and Automation (ICRA), 2011 IEEE International Conference on, May 2011, pp. 3139-3144
17. [17] Trevor et al., „Planar surface slam with 3d and 2d sensors," in Robotics and Automation (ICRA), 2012 IEEE International Conference on, IEEE, 2012, pp. 3041-3048
18. [18] Kohlhepp et al., „Using orthogonal surface directions for autonomous 3d-exploration of indoor environments," in 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2006, pp. 3086-3092
19. [19] Pathak et al., „Online three-dimensional slam by registration of large planar surface segments and closed-form pose-graph relaxation," Journal of Field Robotics, vol. 27, no. 1, pp. 52-84, 2010.
20. [20] Harati und Siegwart, „Orthogonal 3d-slam for indoor environments using right angle corners,"
21. [21] Nguyen et al., „A lightweight slam algorithm using orthogonal planes for indoor mobile robotics," in 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2007, pp. 658-663.
22. [22] Garcia, „Fitting primitive shapes to point clouds for robotic grasping," Master of Science Thesis. School of Computer Science and Communication, Royal Institute of Technology, Stockholm, Sweden, 2009.
23. [23] Jiang und Xiao, „A linear approach to matching cuboids in rgbd images," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 2171-2178.
24. [24] Birdal und Ilic, „Point pair features based object detection and pose estimation revisited," in 3D Vision (3DV), 2015 International Conference on. IEEE, 2015, pp. 527-535.
25. [25] Duda und Hart, „Use of the hough transformation to detect lines and curves in pictures," Communications of the ACM, vol. 15, no. 1, pp. 11-15, 1972.
26. [26] Besl und McKay, „Method for registration of 3-d shapes," in Robotics-DL tentative. International Society for Optics and Photonics, 1992, pp. 586-606.
27. [27] Hoaglin et al., Understanding robust and exploratory data analysis, vol. 3, Wiley New York, 1983.
• Ebenenerfassung ist in der Bildverarbeitung ein gut untersuchtes Gebiet. Borrmann et. al. verwenden einen verbesserten Hough Akkumulator, um 3D-Ebenen zu ermitteln [1]. Yang und Forstner [2] schlagen ein RANSAC basiertes Schema vor, das häufig in unterschiedlichen Anwendungen verwendet wird. Sie verwenden eine minimale Beschreibungslänge (engl. minimum description lengh, MDL) um sich mit unterschiedlichen wettstreitenden Hypothesen auseinander zu setzen. Schnabel et. al. verallgemeinern den RANSAC basierten Ansatz, um unterschiedliche Primitive in Punktwolken zu ermitteln, einschließlich Ebenen. Deschaud et. al. verwenden gefilterte Normalen und Voxel Growing (ein 3D Analogon zu Region-Growing) für eine schnelle und zuverlässige Ermittlung. Schließlich verwenden Drost und Ilic [4] ein lokales Hough Voting Schema um effizient mehrere Ebenen zu ermitteln. Hierzu werden Punktpaar-Merkmale (engl. point pair features, PPF) verwendet. Das Verfahren befasst sich ebenso mit dem Entdecken anderer Primitive, wie etwa Kugeln oder Zylinder. Die Verwendung von Ebenen zusammen mit anderen Primitiven wurde zwar schon teilweise angegangen, vgl. [5, 4, 6]. Jedoch benötigt die Verwendung einzelner Ebenen in einer Pipeline zum Ermitteln orthogonaler Ebenen weitere aufwendige Schritte.
• Weitere Arbeiten befassen sich mit dem sogenannten Clustering Approach, um eine vernünftige Näherung der Umgebung zu erhalten [7, 8, 9, 10]. Jedoch befasst sich keiner dieser Ansätze mit orthogonalen Ebenen. Ebenso kann keine Orthogonalität der ermittelten Ebenen garantiert werden.
• Orthogonalität von Ebenen ist in menschengemachten Umgebungen allgegenwärtig, wie etwa bei Gebäudefassaden und auch in Innenräumen. Hierfür wurden zahlreiche Anwendungen ersonnen. In 2D wird Orthogonalität zum wiederherstellen recti-linearer Strukturen [11], schätzen von Fluchtpunkten und -linien [12, 13] oder zum Ermitteln von Ebenen aus einem Bilderpaar verwendet [14].
• Micusk et. al. [15, 11] geben Verfahren für die Erfassung von orthogonalen Ebenen in 2D Bildern an. Wegen fehlender 3D Information basieren die Verfahren auf Fluchtpunkten.
• Eine direkte und viel akzeptierte Anwendung der Orthogonalität auf 3D-Daten ist SLAM (engl. simultaneous localization and mapping). Viele Arbeiten betrachten hauptsächlich orthogonale Ebenen als Randbedingung, um SLAM durchführen zu können [16, 17, 18, 19, 20, 21]. Dies hilft etwa bei der Navigation von Robotern. Der gewöhnliche Ansatz ist hier jedoch, die Orthogonalität per Design in SLAM einzubauen und nicht aus den Daten zu ermitteln.
• Garcia et. al. [22] entwickelten ein Verfahren zur Box-Erkennung. Sie verwenden jedoch Punkttripletts um eine Ebene zu definieren. Die ist jedoch rechenzeitaufwendig aufgrund der sogenannten kombinatorischen Explosion der Daten.
• Drost und Ilic [4] verwenden Punktpaar-Merkmale zur Erfassung von Primitiven. Jedoch ist eine Ermittlung Orthogonaler Ebenen daraus nicht bekannt.
• Jiang und Xiao [23] erfassen Quader in Bildern, die auf RGBD-Daten basieren, also eine Tiefeninformation beinhalten.
• Auch in der Patentliteratur wurden unterschiedliche Ideen vorgestellt.
• US 8 908 913 B2 offenbart eine Voting-basierte Schätzung für 3D-Sensoren.
• US 7 843 448 B2 befasst sich mit verdeckten Kantenregionen in 3D-Punktdaten.
• US 9 208 609 B2 stellt ein Verfahren zum Fitten von primitiven Formen an 3D-Punktdaten mittels Entfernungsfeldern vor.
• US 2011 0 304 619 A1 offenbart die Extraktion einer primitiven Quadrik-Fläche aus unorganisierten Punktwolkendaten.
• US 9 412 040 B2 offenbart ein Verfahren zum Extrahieren von Ebenen aus 3D-Punktwolkendaten eines Sensors.
• US 5 978 504 A beschreibt ein schnelles planares Segmentierungsverfahren für Reichweitendaten mobiler Roboter.
• Die bekannten Verfahren verlassen sich auf RANSAC basiertes Sampling oder Ansätze nach Art von Region-Growing. Diese sind entweder (rechen-)zeitaufwendig oder benötigen eine Bildsegmentierung.
• Es ist die Aufgabe der Erfindung ein verbessertes Bildverarbeitungsverfahren zu schaffen, das insbesondere eine höhere Rauschresistenz, gesteigerte Effizienz und Robustheit aufweist.
• Die Aufgabe wird durch den Gegenstand des unabhängigen Anspruchs gelöst. Bevorzugte Ausgestaltungen der Erfindung sind Gegenstand der Unteransprüche.
• Es wird darauf hingewiesen, dass die Abfolge der Verfahrensschritte keine Reihenfolge impliziert. Die Schritte sind lediglich zur besseren Referenzierbarkeit mit Buchstaben versehen. Die Schritte können folglich auch in beliebigen anderen ausführbaren Kombinationen durchgeführt werden, so lange das gewünschte Ergebnis erreicht wird.
• Die Erfindung schafft ein rechnergestütztes Bildverarbeitungsverfahren zum Ermitteln von zueinander orthogonalen Ebenen aus einer orientierten Punktwolke, die eine Anzahl N von mit einem Normalvektor assoziierten Punkten enthält, durch Auswählen eines Punktes aus der Punktwolke mit assoziiertem Normalvektor als ein mit einem Referenznormalvektor assoziierten Referenzpunkt, Bestimmen einer Punktpaar-Relation, die eine Mehrzahl von Punktpaar-Merkmalen enthält, für den Referenzpunkt mit den weiteren Punkten der Punktwolke, wobei die Punktpaar-Merkmale sich jeweils auf unterschiedliche geometrische Parameter des Referenzpunktes und des jeweiligen weiteren Punktes und/oder des Referenznormalvektors und des jeweiligen weiteren Normalvektors beziehen, Bestimmen einer durch den Referenzpunkt und den Referenznormalvektor definierten Referenzebene, wenn die Punktpaar-Relation eine vorgegebene Bedingung erfüllt, und Bestimmen einer zu der Referenzebene orthogonalen Ebene aus denjenigen weiteren Punkten, deren Punktpaar-Relation ebenfalls die vorgegebene Bedingung erfüllt.
• Es ist bevorzugt, dass die Punktpaar-Merkmale wenigstens einen der folgenden geometrischen Parameter enthalten:
• - einen Normalwinkel zwischen dem Referenznormalvektor und dem weiteren Normalvektor; und/oder
• - einen Referenzverbindungswinkel zwischen dem Referenznormalvektor und einem Verbindungsvektor, der den Referenzpunkt mit dem jeweiligen weiteren Punkt verbindet; und/oder
• - einen Normalverbindungswinkel zwischen dem jeweiligen weiteren Normalvektor und einem Verbindungsvektor, der den Referenzpunkt mit dem jeweiligen weiteren Punkt verbindet; und/oder
• - eine Verbindungslänge eines Verbindungsvektors, der den Referenzpunkt mit dem jeweiligen weiteren Punkt verbindet.
• Es ist bevorzugt, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn eine Gruppe der Punktpaar-Merkmale innerhalb eines jeweiligen durch einen vorgegebenen Genauigkeitswert und einen Zielwert definierten Bereichs liegen. Es ist bevorzugt, dass der Bereich sich von einem um den Genauigkeitswert verringerten Zielwert bis zu einem um den Genauigkeitswert erhöhten Zielwert erstreckt.
• Es ist bevorzugt, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn der Normalwinkel um höchstens einen vorgegebenen Normal-Genauigkeitswert von einem rechten Winkel abweicht. Es ist bevorzugt, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn der Referenzverbindungswinkel und/oder der Normalverbindungswinkel kleiner sind als ein um einen vorgegebenen Verbindungs-Genauigkeitswert erhöhter rechter Winkel.
• Es ist bevorzugt, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn der Normalwinkel um höchstens einen vorgegebenen Normal-Genauigkeitswert von einem rechten Winkel abweicht. Es ist bevorzugt, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn der Referenzverbindungswinkel und/oder der Normalverbindungswinkel größer sind als ein um einen vorgegebenen Verbindungs-Genauigkeitswert erniedrigter rechter Winkel.
• Es ist bevorzugt, dass in Schritt c) die Paarpunkt-Relation die Bedingung erfüllt, wenn zusätzlich die Verbindungslänge weniger als eine vorgegebene Maximal-Verbindungslänge beträgt.
• Es ist bevorzugt, dass in Schritt d) die zu der Referenzebene orthogonale Ebene mittels eines Voting-Verfahrens, insbesondere mittels einer Hough-Transformation, bestimmt wird, wobei vorzugsweise der Referenzpunkt den Ursprung der Hough-Transformation bildet.
• Es ist bevorzugt, dass in Schritt d) wenigstens eine Schnittgerade zwischen der Referenzebene und der wenigstens einen durch den weiteren Punkt und die assoziierte Normale definierten Ebene ermittelt wird, wobei vorzugsweise die wenigstens eine Schnittgerade Hough transformiert wird.
• Vorzugsweise umfasst das Verfahren den Schritt:
• e) Wiederholen der Schritte b) bis d) für jeden weiteren Punkt der Punktwolke als Referenzpunkt.
• Vorzugsweise umfasst das Verfahren den Schritt:
• f) Vereinigen der orthogonalen Ebenen, die mit unterschiedlichen Referenzpunkten assoziiert sind, vorzugsweise durch ein Clusteranalyse-Verfahren, insbesondere ein agglomeratives Clusteranalyse-Verfahren.
• Vorzugsweise umfasst das Verfahren den Schritt:
• g) Optimieren der zuvor ermittelten orthogonalen Ebenen
• Mit den erfindungsgemäßen Merkmalen können unter anderem nachfolgend erläuterte Vorteile erreicht werden. Es sollte beachtet werden, dass nicht alle Vorteile gleichzeitig vorhanden sein müssen.
• Im Unterschied zu bekannten Verfahren mit dem hierin beschriebenen Verfahren orthogonale Ebenen simultan und direkt aus einer 3D Punktwolke ohne vorherige Bearbeitung der Daten extrahiert werden. Zudem kann gleichzeitig die Ausrichtung der Ebenen ermittelt werden. Die Eingangsdaten sind bevorzugt eine unstrukturierte 3D-Punktwolke ohne Farbinformation. Als Ausgabe werden die Ebenengleichungen aller Ebenen gewünscht, die orthogonal zueinander sind. Zudem kann durch Clustern orthogonaler Ebenen in einer Gruppe die volle Information über die Ausrichtung (6DOF, engl. 6 degrees of freedom) erhalten werden. Mittels einer Kombination aus Ermitteln und Optimieren können die Ergebnisse zusätzlich verbessert werden.
• Dies ist die erste Arbeit, die Punktpaar-Merkmale zusammen mit einer lokalen Hough-Transformation verwendet. Dabei wird ein Punktepaar, das auf zueinander orthogonalen Ebenen gefunden wird verwendet um die geometrische Konfiguration zu beschreiben.
• Die lokale Parametrisierung ist lediglich 2D, reicht jedoch aus um die gesamte 5D Konfiguration der orthogonalen Ebenen anzugeben. Somit ist das Verfahren weniger rechenaufwendig und kann auch in Echtzeitanwendungen verwendet werden. Insbesondere sind keine Region-Growing oder RANSAC-artigen Heuristiken mehr erforderlich. Dies kann insbesondere durch den lokalen Voting-Space erreicht werden.
• Es wird angemerkt, dass das Erzeugen eines lokalen Voting-Space den Aufwand für RANSAC deutlich reduziert, nämlich vom Auswählen zweier Punkte auf einen einzigen. Somit ist das Verfahren exponentiell effizienter als RANSAC. Durch das Verfahren können auch Diskretisierungsfehler vermieden werden, wobei Geschwindigkeit und Genauigkeit erhalten bleiben. Mittels des Verfahrens können somit mehrere orthogonale Ebenen ermittelt und geclustert werden, um insbesondere die volle 3D Geometrie der Umgebung zu beschreiben. Das Verfahren erfordert zudem keine Tiefeninformation und kann gegebenenfalls auch auf dünnbesetzten Punktmengen ohne weitere Vorverarbeitung verwendet werden.
• Das Verfahren kann auch unendlich ausgedehnte orthogonale Ebenen ermitteln, da insbesondere aufgrund des Paaransatzes sowohl lokaler als auch globaler Kontext, sogenannte Semi-Lokalität, gegeben sind. Wird eine Längenbeschränkung verwendet, kann ein Nutzer zudem nach Belieben die Größe der ermittelten Ebene einstellen.
• Durch die Nachoptimierung können die aus der 3D Punktwolke ermittelten genäherten orthogonalen Konfigurationen bis zur Maschinengenauigkeit des Rechners und zum Sensorrauschen verbessert werden. So kann eine äußerst präzise Anpassung erfolgen.
• Ausführungsbeispiele der Erfindung werden anhand der beigefügten schematischen Zeichnungen näher erläutert. Darin zeigt:
• 1 ein Ausführungsbeispiel des Verfahrens;
• 2 eine Darstellung orthogonaler Ebenen;
• 3 eine weitere Darstellung orthogonaler Ebenen;
• 4 eine 3D-Darstellung einer Referenzebene und einer weiteren Ebene; und
• 5 eine 2D-Darstellung einer Referenzebene und Schnittgerade.
• 1 zeigt ein Ausführungsbeispiel eines rechnergestützten Bildverarbeitungsverfahrens zum Ermitteln zueinander orthogonaler Ebenen aus einer Punktwolke. Die Punktwolke enthält insgesamt eine Anzahl N an Punkten. Das Verfahren beginnt in Schritt S1 mit dem auswählen eines Referenzpunktes p_i aus einer, vorzugsweise dreidimensionalen, orientierten Punktwolke. Orientiert bedeutet dabei, dass jedem Punkt p_j der Punktwolke ein zugehöriger Normalvektor n_j zugeordnet ist. Im Falle des Referenzpunktes p_i wird der zugehörige Normalvektor als Referenznormalvektor n_i bezeichnet.
• 2 und 3 zeigen zwei mögliche Konfigurationen orthogonaler Ebenen. Eine Referenzebene W_i ist durch den Referenzpunkt p_i und den Referenznormalvektor n_i definiert, während die andere Ebene W_j durch den Punkt p_j und den zugehörigen Normalvektor n_j definiert ist. Die in 2 dargestellte Variante wird als konkave Konfiguration bezeichnet, während die in 3 dargestellt Variante als konvex bezeichnet wird. Ein Verbindungsvektor d verbindet den Referenzpunkt p_i und den Punkt p_j.
• Für den Referenzpunkt p_i werden in Schritt S2 insgesamt N-1 Punktpaar-Relationen F(p_i, p_j) ermittelt; mit anderen Worten für jedes Paar Punkte (p_i, p_j) , wobei i ungleich j ist wird eine Punktpaar-Relation F(p_i, p_j) ermittelt. Die Punktpaar-Relation F(p_i, p_j) enthält eine Mehrzahl von Punktpaar-Merkmalen von denen sich jedes auf unterschiedliche geometrische Parameter des Referenzpunktes p_i und des Punktes p_j bezieht.
• Als Punktpaar-Merkmale werden der Normalwinkel <(n_i,n_j) zwischen dem Referenznormalvektor n_i und dem Normalvektor n_j, der Referenzverbindungswinkel <(n_i, d) zwischen dem Referenznormalvektor n_i und dem Verbindungsvektor d, der Normalverbindungswinkel <(n_j, d) zwischen dem Normalvektor n_j und dem Verbindungsvektor d sowie die Verbindungslänge | |d| | des Verbindungsvektors d ermittelt.
• Die Winkel werden bevorzugt anhand der folgenden Formel ermittelt, die an sich bekannt ist: $$<\left(v_1,v_2\right)={\text{tan}}^{-1}\left(\frac{\Vert v_1\times v_2\Vert }{v_1\cdot v_2}\right)$$

  
• In Schritt S3 werden die Punktpaar-Merkmale mit vorgegebenen Beziehungen verglichen. Für eine Einordnung der Punktpaar-Relation F(p_i, p_j) als Kandidat für eine konkave Konfiguration (2) müssen die Punktpaar-Merkmale die folgenden Relationen erfüllen: $$\mathrm{\pi }\text{/2}-{\mathrm{\epsilon }}_{\text{n}}<<\left({\text{n}}_{\text{i}}{\text{,n}}_{\text{j}}\right)<\mathrm{\pi }\text{/2}+{\mathrm{\epsilon }}_{\text{n}}$$

  

  $$\left|<\left({\text{n}}_{\text{i}}\text{, d}\right)\right|>\mathrm{\pi }\text{/}2-{\mathrm{\epsilon }}_{\text{d}}$$

  

  $$\left|<\left({\text{n}}_{\text{j}}\text{, d}\right)\right|>\mathrm{\pi }\text{/}2-{\mathrm{\epsilon }}_{\text{d}}$$

  
• Für eine Einordnung der Punktpaar-Relation F(p_i, p_j) als Kandidat für eine konvexe Konfiguration (3) müssen die Punktpaar-Merkmale die folgenden Relationen erfüllen: $$\mathrm{\pi }\text{/}2-{\mathrm{\epsilon }}_{\text{n}}<<\left({\text{n}}_{\text{i}}{\text{,n}}_{\text{j}}\right)<\mathrm{\pi }\text{/}2+{\mathrm{\epsilon }}_{\text{n}}$$

  

  $$\left|<\left({\text{n}}_{\text{i}\text{,}}\text{ d}\right)\right|<\mathrm{\pi }\text{/}2+{\mathrm{\epsilon }}_{\text{d}}$$

  

  $$\left|<\left({\text{n}}_{\text{j}\text{,}}\text{ d}\right)\right|<\mathrm{\pi }\text{/}2+{\mathrm{\epsilon }}_{\text{d}}$$

  
• Dabei bezeichnet |x| den Betrag von x, ε_n den Normal-Genauigkeitswert und ε_d den Verbindungs-Genauigkeitswert. Die Genauigkeitswerte geben die maximal zulässige Abweichung der Punktpaar-Merkmale vom Zielwert, hier: n/2, an.
• Zusätzlich kann verlangt sein, dass die Verbindungslänge | |d| | kleiner als ein Schwellwert τ_d ist. Somit werden nur Ebenen als Kandidaten in Betracht gezogen, die einen Abstand kleiner τ_d von dem Referenzpunkt p_i haben. τ_d wird auch als maximale Verbindungslänge bezeichnet.
• Erfüllen die Punktpaar-Merkmale alle der jeweiligen Relationen, so erfüllt die Punktpaar-Relation F(p_i, p_j) die Bedingung zum Fortsetzen des Verfahrens. Mit anderen Worten liegen die Punkte p_i, p_j des Punktpaares auf zueinander orthogonalen Ebenen innerhalb der betrachteten Genauigkeiten ε_n und ε_d.
• In Schritt S4 wird nun die zu der Referenzebene W_i orthogonale Ebene W_j ermittelt. Die Orthogonalitätsbedingung ist durch die Punktpaar-Relationen F(p_i,p_j) näherungsweise erfüllt, jedoch nicht eineindeutig. Die Kandidaten für die orthogonale Ebene W_j können um den Referenznormalvektor n_i rotiert und/oder in der Referenzebene W_i relativ zu dem Referenzpunkt p_i verschoben sein. Diese beiden Freiheitsgrade müssen noch bestimmt werden. Hierzu wird eine Konfiguration erzeugt, wie sie in 4 und 5 dargestellt ist. Der Kandidat für die orthogonale Ebene W_j wird demnach in einem Polarkoordinatensystem mit den Parametern (Θ, ϱ) dargestellt, wobei Θ den Drehwinkel um den Referenznormalvektor n_i, also den Winkel zwischen der Schnittgeraden l der x-Achse des Koordinatensystems, und ϱ den Abstand von einer Schnittgeraden l der Referenzebene W_i und dem Kandidaten für die orthogonale Ebene W_j zu dem Referenzpunkt p_i bezeichnet. Es sollte beachtet werden, dass zu diesem Zeitpunkt lediglich ein zweidimensionales Problem gelöst werden muss und nicht mehr alle grundsätzlichen 6 Freiheitsgrade ermittelt werden müssen.
• Zu dem Referenzpunkt p_i werden durch ein an sich bekanntes Voting-Verfahren, beispielsweise eine Hough-Transformation, die Parameter (Θ, ϱ) bestimmt, welche die zu der Referenzebene W_i orthogonale Ebene W_j beschreiben. Dabei wird zum Lösten des zweidimensionalen Problems der Referenzpunkt p_i als Ursprung des Koordinatensystems verwendet und der Referenznormalvektor n_i als y-Achse des Koordinatensystems.
• Die zuvor beschriebenen Schritte S1 bis S4 werden für einen weiteren Punkt der Punktwolke als Referenzpunkt p_i wiederholt, solange bis jeder Punkt der Punktwolke wenigstens einmal der Referenzpunkt p_i gewesen ist.
• In Schritt S5 werden die zu unterschiedlichen Referenzpunkten p_i gehörigen Referenzebenen W_i und die zugehörigen orthogonalen Ebenen W_j mittels eines, insbesondere agglomerativen, Clusteranalyse-Verfahrens vereinigt, das als solches bekannt ist. Demnach werden insbesondere anhand eines Ähnlichkeitsmaßes Gruppen von zueinander ähnlichen Paaren von Referenzebene W_i und orthogonaler Ebene W_j gebildet. Nach dem Gruppieren/Clustern wird diejenige Konfiguration ausgewählt, welche höchste Stimmanzahl erhalten hat. Die Stimmanzahl kann beispielsweise auf der Anzahl der zu einer Gruppe gehörenden Ebenen basieren.
• In Schritt S6 werden die zuvor ermittelten zueinander orthogonalen Ebenen W_i, W_j möglichst ohne Beeinträchtigung ihrer Orthogonalität optimiert. Unter optimieren wird hier verstanden, dass Diskretisierungsfehler, Rauschen und Artefakte, die bis zu diesem Zeitpunkt aufgetreten sind möglichst vollständig und ohne Beeinträchtigung der Orthogonalität der Ebenen zueinander entfernt werden.
• Es wird eine Variante des Iterative-Closest-Point-Verfahrens (ICP-Verfahren) vorgeschlagen. Die zu minimierende Zielfunktion lautet: $$E\left(P,\left\{W_1,W_2\right\}\right)={\displaystyle \sum _{i=1}^M\text{min}}\left(Q\left(p_i,W_1\right),Q\left(p_i,W_2\right)\right)$$

  
• Dabei bezeichnen W1 und W2 die zueinander orthogonalen Ebenen, P die gesamte Punktwolke, Q(p, W) der Punkt-Ebenen-Abstant (wie auch aus dem ICP-Verfahren bekannt) und p bezeichnet jeden Punkt der Punktwolke P. Um jedoch die Orthogonalität zu wahren müssen die Folgenden Zwangsbedingungen erfüllt sein: $$\begin{array}{c}{W}_1^n\cdot W_2^n=0\\ \begin{array}{ccc}\Vert W_1^n\Vert =1& \begin{array}{ccc}& & \end{array}& \Vert W_2^n\Vert =1\end{array}\end{array}$$

  
• Dabei bezeichnet Wⁿ _i die Normalvektorkoeffizienten der Ebene i. Die Zielfunktion kann daher umgeschrieben werden zu: $$\left\{W_1^{\ast },W_2^{\ast }\right\}=ar{g}_{W\mathrm{1,}W2}^{min}E\left(P,\left\{W_1,W_2\right\}\right)+\lambda \left(W_1^n\cdot W_2^n\right)+\mathrm{\gamma }\left(\Vert {\widehat{W}}_1^n\Vert -1\right)+\xi \left(\Vert {\widehat{W}}_2^n\Vert -1\right)$$

  
• Der Parameter λ steuert die Strenge der Orthogonalitätsbedingung. Da die Orthogonalität der Ebenen jedoch nicht ohne Weiteres sichergestellt ist, wird bevorzugt bei jedem Iterationsschritt der Minimierung die Lösung zurück auf den Orthogonalen Unterraum projiziert. Mit anderen Worten wird derjenige orthogonale Vektor V₂ ermittelt, der dem Vektor W₂ am nächsten liegt und dennoch orthogonal zu W₁ ist. Die Projektion lässt sich effizient berechnen, so dass insgesamt wiederum Rechenzeit eingespart werden kann. Die Minimierung der Zielfunktion erfolgt beispielsweise mittels Levenberg-Marquart-Iteration.
• Um die Konvergenz zu verbessern und bessere Ergebnisse auch bei stark rauschbehaftete Punktwolken, wie sie etwa durch RGBD-Sensoren erzeugt werden, zu erhalten wird als robuste Zielfunktion vorgeschlagen: $$E_{robust}\left(P,\left\{W_1,W_2\right\}\right)=\Phi \left(E\left(P,\left\{W_1,W_2\right\}\right)\right)$$

  
• Dabei ist Φ ein M-Schätzer, der an sich bekannt ist: $$\mathrm{\Phi }\left({\widehat{r}}_i\right)=\{\begin{array}{ll}{\widehat{r}}_i{\left(1-{\left(\frac{{\widehat{r}}_i}{c}\right)}^2\right)}^2\hfill & if\left|{\widehat{r}}_i\right|\le 0\hfill \\ 0\hfill & andernfalls\hfill \end{array}$$

  
• Dabei gilt $${\widehat{r}}_i=\frac{r_i}{\widehat{s}}$$

  
• Mit r_i dem momentanen Residuum und c einer Konstanten, etwa c = 4.685 und $$\widehat{s}=\frac{mad\left(r_i\right)}{0.6745}$$

  

  mit mad(r_i) dem Median der absoluten Abweichungen.
• Voriger Ansatz erfüllt zwar nicht direkt die Zwangsbedingungen. Sobald jedoch die Ebenen W₁ und W₂ gemeinsam als einzelner Parametervektor beschrieben sind, kann auf die Regularisierungsterme beim Minimieren verzichtet werden. Die zueinander orthogonalen Ebenen W_i, W_j sind durch {p_i, n_i, Θ, ϱ} parametrisiert. Obwohl dies immer noch Überbestimmt ist, können doch die Parameter individuell geändert werden, wobei die Orthogonalität der Ebenen W_i, W_j jedoch erhalten bleibt. Weiter vorteilhaft bleibt auch die Verbindung zwischen Ebene W_i und Referenzpunkt p_i erhalten. Es sollte beachtet werden, dass die Funktion f: (x) -> {W_i, W_j} unkompliziert ist, da stets die Schnittgerade l aus dem zweidimensionalen Geradenort (Θ, ϱ) rekonstruiert werden kann und umgekehrt. Überdies kann die orthogonale Ebene W_j durch projezieren des Referenzpunktes p_i auf die dreidimensionale Linie und berechnen des Kreuzproduktes der dreidimensionalen Linie und der Normale n_i des Referenzpunktes p_i gewonnen werden, sobald der Referenzpunkt n_i und die dreidimensionale Linie einmal bekannt sind.
• Weiter wird zum Optimieren noch ein Verfahren mit Lagrange-Multiplikatoren vorgeschlagen, wodurch die Zwangsbedingungen in der Zielfunktion direkt berücksichtigt werden können: $$L\left(W_1,W_2,\lambda ,\gamma ,\xi \right)=E\left(P,\left\{W_1,W_2\right\}\right)+\lambda \left(W_1^n\cdot W_2^n\right)+\gamma \left(\Vert {\widehat{W}}_1^n\Vert -1\right)+\xi \left(\Vert {\widehat{W}}_2^n\Vert -1\right)$$

  
• Die Parameter und Multiplikatoren können dann auf an sich bekannte Weise durch Lösen der Gleichung $${\nabla }_{W_1,W_2,\lambda ,\gamma ,\xi }L=0$$

  

  bestimmt werden.
• Da hier ausgedient Ebenenschnitte ermittelt werden müssen, wird auch hierfür ein besserer Ansatz vorgestellt. Während das Schnittproblem zwischen Ebenen gut untersucht ist ist für die hier vorgestellten Zwecke ein anderer Ansatz zielführender. Bei der bekannten Vorgehensweise wird ein beliebiger Punkt ausgewählt, ohne die Geometrie zu berücksichtigen. Bevorzugt jedoch soll dieser Punkt nahe an den Punkten p_i, p_j, den Ebenen W_i, W_j, oder der Schnittgeraden l sein. Gewöhnlich wird der Richtungsvektor der Schnittgeraden l als das Kreuzprodukt der Normalvektoren n_i, n_j der beiden orthogonalen Ebenen W_i, W_j berechnet. Üblicherweise würde dann ein beliebiger Punkt p₀ ausgewählt, beispielsweise der Ursprung oder der Mittelpunkt. Gewünscht ist jedoch, dass der gewählte Punkt p möglichst nahe an den Punkten p_i, p_j der Ebenen W_i, W_j liegt. Hierfür wird die Zielfunktion vorgeschlagen: $$J=\Vert p-p_0\Vert +\lambda {\left(p-p_1\right)}^2+\mu {\left(p-p_2\right)}^2$$

  
• Der gewählte Punkt p kann dann mit dem üblichen Lagrange-Formalismus ermittelt werden.
• Mit dem hierin beschriebenen Verfahren, können orthogonale Ebenen direkt aus 3 die Punktwolken generiert werden. Ferner kann die Ausrichtung der Gesamten orthogonalen Ebenenkonfiguration, die fünfdimensional ist, aus lediglich zwei Dimensionen ermittelt werden. Das Verfahren kann somit mit weniger Ressourcen durch einen Rechner ausgeführt werden, so dass grundsätzlich ein Einsatz bei zeitkritischen Anwendungen möglich ist.
• ZITATE ENTHALTEN IN DER BESCHREIBUNG
• Diese Liste der vom Anmelder aufgeführten Dokumente wurde automatisiert erzeugt und ist ausschließlich zur besseren Information des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt keinerlei Haftung für etwaige Fehler oder Auslassungen.
• Zitierte Patentliteratur
• US 8908913 B2 [0012]
• US 7843448 B2 [0013]
• US 9208609 B2 [0014]
• US 20110304619 A1 [0015]
• US 9412040 B2 [0016]
• US 5978504 A [0017]
• Zitierte Nicht-Patentliteratur
• Borrmann et al., „The 3d hough transform for plane detection in point clouds: A review and a new accumulator design,“ 3D Research, vol. 2, no. 2, pp. 1-13, 2011 [0002]
• Yang und Förstner, „Plane detection in point cloud data,“ 2010 [0002]
• Deschaud und Goulette, „A fast and accurate plane detection algorithm for large noisy point clouds using filtered normals and voxel growing,“ Proceedings of 3D Processing, Visualization and Transmission Conference, 2010 [0002]
• B. Drost und S. Ilic, „Local hough transform for 3d primitive detection,“ in 3D Vision (3DV), 2015 International Conference on, pp. 398-406 [0002]
• Li et al., „Globfit: consistently fitting primitives by discovering global relations,“ in ACM Transactions on Graphics (TOG). ACM, 2011, vol. 30, p. 52 [0002]
• Wang und Xu, „Shape detection from raw lidar data with subspace modeling,“ IEEE Transactions on Visualization and Computer Graphics, vol. PP, no. 99, pp. 1-1, 2016 [0002]
• Oehler et al., „Efficient multiresolution plane segmentation of 3d point clouds,“ in International Conference on Intelligent Robotics and Applications. Springer, 2011, pp. 145-156 [0002]
• Oßwald et al., „From 3d point clouds to climbing stairs: A comparison of plane segmentation approaches for humanoids,“ in Humanoid Robots (Humanoids), 2011 11th IEEE-RAS International Conference on. IEEE, 2011, pp. 93-98 [0002]
• Holz et al., „Real-time plane segmentation using rgb-d cameras,“ in Robot Soccer World Cup. Springer, 2011, pp. 306-317 [0002]
• Xiao et al., „Threedimensional point cloud plane segmentation in both structured and unstructured environments,“ Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1641-1652, 2013 [0002]
• Micusik et al., „Detection and matching of rectilinear structures,“ in Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on. IEEE, 2008, pp. 1-7 [0002]
• Fond et al., „Généeration d'hypothèeses de façades utilisant des critèeres contextuels et structurels,“ in Reconnaissance des Formes et Intelligence Artificielle, 2016 [0002]
• Herout und Dubskä, „Real projective plane mapping for detection of orthogonal vanishing points,“ in Proceedings of the British Machine Vision Conference, 2013, BMVA Press [0002]
• Singhal et al., „Top down approach to detect multiple planes from pair of images,“ in Proceedings of the 2014 Indian Conference on Computer Vision Graphics and Image Processing, New York, NY, USA, 2014, ICVGIP '14, pp. 53:1-53:8, ACM [0002]
• Micusk et al. „Towards detection of orthogonal planes in monocular images of indoor environments,“ in Robotics and Automation, 2008. ICRA2008. IEEE International Conference on. IEEE, 2008, pp. 999-1004 [0002]
• Lee et al., „Mav visual slam with plane constraint,“ in Robotics and Automation (ICRA), 2011 IEEE International Conference on, May 2011, pp. 3139-3144 [0002]
• Trevor et al., „Planar surface slam with 3d and 2d sensors,“ in Robotics and Automation (ICRA), 2012 IEEE International Conference on, IEEE, 2012, pp. 3041-3048 [0002]
• Kohlhepp et al., „Using orthogonal surface directions for autonomous 3d-exploration of indoor environments,“ in 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2006, pp. 3086-3092 [0002]
• Pathak et al., „Online three-dimensional slam by registration of large planar surface segments and closed-form pose-graph relaxation,“ Journal of Field Robotics, vol. 27, no. 1, pp. 52-84, 2010 [0002]
• Harati und Siegwart, „Orthogonal 3d-slam for indoor environments using right angle corners,“ [0002]
• Nguyen et al., „A lightweight slam algorithm using orthogonal planes for indoor mobile robotics,“ in 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2007, pp. 658-663 [0002]
• Garcia, „Fitting primitive shapes to point clouds for robotic grasping,“ Master of Science Thesis. School of Computer Science and Communication, Royal Institute of Technology, Stockholm, Sweden, 2009 [0002]
• Jiang und Xiao, „A linear approach to matching cuboids in rgbd images,“ in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013, pp. 2171-2178 [0002]
• Birdal und Ilic, „Point pair features based object detection and pose estimation revisited,“ in 3D Vision (3DV), 2015 International Conference on. IEEE, 2015, pp. 527-535 [0002]
• Duda und Hart, „Use of the hough transformation to detect lines and curves in pictures,“ Communications of the ACM, vol. 15, no. 1, pp. 11-15, 1972 [0002]
• Besl und McKay, „Method for registration of 3-d shapes,“ in Robotics-DL tentative. International Society for Optics and Photonics, 1992, pp. 586-606 [0002]
• Hoaglin et al., Understanding robust and exploratory data analysis, vol. 3, Wiley New York, 1983 [0002]

Claims (11)

1. Rechnergestütztes Bildverarbeitungsverfahren zum Ermitteln von zueinander orthogonalen Ebenen (W_i, W_j) aus einer orientierten Punktwolke, die eine Anzahl N von mit einem Normalvektor (n_i, n_j) assoziierten Punkten (p_i, p_j) enthält, durch a) Auswählen eines Punktes (p_i) aus der Punktwolke mit assoziiertem Normalvektor (n_i) als ein mit einem Referenznormalvektor (n_i) assoziierten Referenzpunkt (p_i); b) Bestimmen einer Punktpaar-Relation (F(p_i,p_j)), die eine Mehrzahl von Punktpaar-Merkmalen enthält, für den Referenzpunkt (p_i) mit den weiteren Punkten (p_j) der Punktwolke, wobei die Punktpaar-Merkmale sich jeweils auf unterschiedliche geometrische Parameter des Referenzpunktes (p_i) und des jeweiligen weiteren Punktes (p_j) und/oder des Referenznormalvektors (n_i) und des jeweiligen weiteren Normalvektors (n_j) beziehen; c) Bestimmen einer durch den Referenzpunkt (p_i) und den Referenznormalvektor (n_i) definierten Referenzebene (W_i), wenn die Punktpaar-Relation (F(p_i,p_j)) eine vorgegebene Bedingung erfüllt; und d) Bestimmen einer zu der Referenzebene (W_i) orthogonalen Ebene (W_j) aus denjenigen weiteren Punkten (p_j), deren Punktpaar-Relation (F(p_i,p_j)) ebenfalls die vorgegebene Bedingung erfüllt.
2. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die Punktpaar-Merkmale wenigstens einen der folgenden geometrischen Parameter enthalten: - einen Normalwinkel zwischen dem Referenznormalvektor und dem weiteren Normalvektor; und/oder - einen Referenzverbindungswinkel zwischen dem Referenznormalvektor und einem Verbindungsvektor, der den Referenzpunkt mit dem jeweiligen weiteren Punkt verbindet; und/oder - einen Normalverbindungswinkel zwischen dem jeweiligen weiteren Normalvektor und einem Verbindungsvektor, der den Referenzpunkt mit dem jeweiligen weiteren Punkt verbindet; und/oder - eine Verbindungslänge eines Verbindungsvektors, der den Referenzpunkt mit dem jeweiligen weiteren Punkt verbindet.
3. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn eine Gruppe der Punktpaar-Merkmale innerhalb eines jeweiligen durch einen vorgegebenen Genauigkeitswert und einen Zielwert definierten Bereichs liegen, wobei vorzugsweise der Bereich sich von einem um den Genauigkeitswert verringerten Zielwert bis zu einem um den Genauigkeitswert erhöhten Zielwert erstreckt.
4. Verfahren nach einem der Ansprüche 2 bis 3, dadurch gekennzeichnet, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn der Normalwinkel um höchstens einen vorgegebenen Normal-Genauigkeitswert von einem rechten Winkel abweicht und/oder wenn der Referenzverbindungswinkel und/oder der Normalverbindungswinkel kleiner sind als ein um einen vorgegebenen Verbindungs-Genauigkeitswert erhöhter rechter Winkel.
5. Verfahren nach einem der Ansprüche 2 bis 4, dadurch gekennzeichnet, dass in Schritt c) die Punktpaar-Relation die Bedingung erfüllt, wenn der Normalwinkel um höchstens einen vorgegebenen Normal-Genauigkeitswert von einem rechten Winkel abweicht und/oder wenn der Referenzverbindungswinkel und/oder der Normalverbindungswinkel größer sind als ein um einen vorgegebenen Verbindungs-Genauigkeitswert erniedrigter rechter Winkel.
6. Verfahren nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, dass in Schritt c) die Paarpunkt-Relation die Bedingung erfüllt, wenn zusätzlich die Verbindungslänge weniger als eine vorgegebene Maximal-Verbindungslänge beträgt.
7. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass in Schritt d) die zu der Referenzebene orthogonale Ebene mittels eines Voting-Verfahrens, insbesondere mittels einer Hough-Transformation, bestimmt wird, wobei vorzugsweise der Referenzpunkt den Ursprung der Hough-Transformation bildet.
8. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass in Schritt d) wenigstens eine Schnittgerade zwischen der Referenzebene und der wenigstens einen durch den weiteren Punkt und die assoziierte Normale definierten Ebene ermittelt wird, wobei vorzugsweise die wenigstens eine Schnittgerade Hough transformiert wird.
9. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch den Schritt: e) Wiederholen der Schritte b) bis d) für jeden weiteren Punkt der Punktwolke als Referenzpunkt.
10. Verfahren nach Anspruch 9, gekennzeichnet durch den Schritt: f) Vereinigen ähnlicher orthogonalen Ebenen, die mit unterschiedlichen Referenzpunkten assoziiert sind, vorzugsweise durch ein Clusteranalyse-Verfahren, insbesondere ein agglomeratives Clusteranalyse-Verfahren.
11. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch den Schritt: g) Optimieren der zuvor ermittelten orthogonalen Ebenen ohne Beeinträchtigung der Orthogonalität.

Images