Im Zusammenhang mit der größeren Verbreitung erschwinglicher Laserscanner (Lidars), die 3D-Punktwolken ( 3dOT ) empfangen können, und der breiteren Anwendung dieser Technologie in verschiedenen Bereichen (vom Maschinenbau bis zur Sicherheit, von der Ölindustrie bis zur Architektur) hat das Interesse an Verarbeitungsalgorithmen wieder zugenommen Wolken von Punkten.
Eine der beliebtesten Anwendungen von 3d in der Industrie ist die Erstellung von Konstruktionsdokumentationen nur für konstruierte, alte oder umgebaute Geräte, die normalerweise aus Rohrleitungen und anderen Strukturen mit zylindrischer Geometrie bestehen.
Um geometrische Grundelemente in 3dOT zu erkennen , werden normalerweise spezielle 3D-Bibliotheken verwendet, z. B. Microsoft PCL. Der Ansatz mit der Verwendung von vorgefertigten Bibliotheken hat neben den Vorteilen auch Nachteile. Zum Beispiel ist es schwierig, sie in bestehende Kadov-Verarbeitungsschemata zu integrieren, die normalerweise eine 2D-Dimension haben.
Betrachten wir, wie es möglich wäre, 3dOT , beispielsweise eine Pumpstation, zu verarbeiten, beginnend mit 2D-Schnitten und unter Verwendung des gesamten Arsenals der 2D-Verarbeitung, das in zuverlässigen und optimierten Bildverarbeitungsbibliotheken, beispielsweise OpenCV, verfügbar ist .
Abbildung 1. 3D-OT-Modell einer Pumpstation
Das Hauptelement der Abschnitte, die durch Scannen verschiedener Rohrstrukturen erhalten werden, sind elliptische Bögen .
Abbildung 2. Horizontaler Querschnitt eines 3D-Modells einer Pumpstation auf durchschnittlicher Ebene.
In diesem Artikel beschränken wir uns auf einen Schlüsselalgorithmus, mit dem wir beliebige elliptische Bögen erkennen können. Dies ist ein iterativer Algorithmus für das Wachstum von Bogensegmenten und die Regionsbindung ( Regionswachstum und Kantenverknüpfung ).
Wachstumsalgorithmen sind die offensichtlichsten und am einfachsten zu überprüfenden, wenn auch zeitaufwändigen Algorithmen im Vergleich zu statistischen Algorithmen, die besser für den Fall geeignet sind, dass die Szene lose gekoppelte, entfernte Objekte enthält, die zu einer Ellipse gehören. Diese Algorithmen werden in zukünftigen Artikeln diskutiert.
Der Einfachheit halber lassen wir das Verfahren zum Abrufen eines Abschnitts aus der 3dOT-Quelldatei , zum Vorverarbeiten eines Abschnitts, zum Clustering zum Isolieren geometrischer Grundelemente sowie zum anschließenden Binden, Korrigieren und anderen photogrammetrischen Operationen, die zum Abrufen von Modellparametern erforderlich sind , weg . Wir werden die Parametrisierung heuristischer Suchalgorithmen nicht auf die gleiche Weise diskutieren. Beschreiben wir alle grundlegenden Operationen, aus denen der Algorithmus aufgebaut ist.Wir gehen davon aus, dass wir in diesem Bild, das aus dem horizontalen Abschnitt der Punktwolke ausgeschnitten ist, einen elliptischen Bogen erkennen (erkennen, klassifizieren) müssen (dh die Parameter der Ellipse sowie den Anfangs- und Endwinkel des elliptischen Bogens berechnen).
Abbildung 3. Einer der elliptischen Bögen des Querschnitts des 3D-Modells (nach dem Glätten)Um die Arbeit mit dem Raster blind zu minimieren, führen wir alle Operationen mit dem Raster durch Gliederung durch .Die OpenCV findContours Verfahren findet auf der Matte raster alle externen (ohne interne Formen) Konturen in Form eines Vektors von ganzzahligen Punktvektoren (in Rasterkoordinaten): Mat mat(size);
vector<vector<Point>> contours;
findContours(mat, contours, RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
Dies ist unsere Schlüsseloperation, die in einigen einfachen Fällen die Aufgabe vollständig löst . Da jedoch nicht immer entartete Fälle gefunden werden, betrachten wir die Verarbeitungstechnologie durch Konturierung genauer.Die umgekehrte Operation, bei der mithilfe der OpenCV- Funktion ein Raster gemäß dem vorhandenen externen Schaltkreis generiert wird , sieht ebenfalls einfach aus: drawContours(mat, contours, -1, Scalar(255), -1);
Es wird auch sehr oft verwendet, um Konturen zu maskieren, zu zeichnen oder die Fläche zu berechnen.Daher haben wir im Anfangsstadium eine Reihe von Flecken (Teile einer bestimmten Kurve), die zu einem elliptischen Bogen verbunden werden müssen, um Teile anderer Komponenten der Struktur (z. B. Befestigungselemente) oder optisches Rauschen zu eliminieren, das durch Abschatten während des Scannens und andere verursacht wird Gründe dafür.Erstellen wir eine Diskriminanzfunktion , die den Konturtyp (Ellipse, lineares Segment, Schraffur oder etwas anderes) sowie die Endpunkte der Kontur und ihres gedrehten Umrissrechtecks zurückgibt: contourTypeSearch(
const vector<Point> &contour, Vec4i &def, RotatedRect &rc);
Das Verhältnis von Länge und Breite des Rechtecks hilft dabei, Konturen in der Nähe von linearen Segmenten sowie kleine Rauschkonturen schnell zu unterscheiden .Das gedrehte Rechteck in OpenCV hat ein komplexes Koordinatensystem. Wenn nicht der Winkel selbst erforderlich ist, sondern seine trigonometrischen Funktionen , ist dies aus dem Kontext umso weniger ersichtlich. Wenn der Absolutwert des Winkels verwendet wird , muss berücksichtigt werden, dass der Winkel von der Horizontalen bis zur ersten Kante des Rechtecks gegen den Uhrzeigersinn gezählt wird und einen negativen Wert hat .Die Endpunkte der elliptischen Konturen werden mit unserem Verfahren ermittelt, das das Mat- Raster erhältmit einem diskriminierten Umriss, der durch Maskieren aus dem Originalbild extrahiert wird und den maximalen Fehler zurückgibt : contourConvFeature(mat, &def, … );
Der Hauptcode für diese Funktion besteht darin, zwei OpenCV- Prozeduren aufzurufen : vector<int> *hull = new vector<int>();
convexHull(contour, *hull);
vector<Vec4i> *defs = new vector<Vec4i>();
convexityDefects(contour, *hull, *defs);
Das erste Verfahren findet ein konvexes Polygon für die untersuchte Kontur, das zweite - berechnet alle Konvexitätsfehler .Wir nehmen nur den größten Defekt in Bezug auf die Konvexität, wenn man bedenkt, dass er die Endpunkte der Kontur bestimmt. Dies ist möglicherweise nicht der Fall, wenn die äußeren oder inneren Grenzen der Kontur Merkmale aufweisen . Um sie zu glätten , wenden wir eine zusätzliche Glättung auf die zu untersuchende Kontur an (und nicht auf das gesamte Bild, um die Landenschen zwischen den Konturen nicht zu „verwischen“ und die ursprüngliche Topologie nicht zu verletzen).
Abbildung 4. Berechnung des Ausbuchtungsdefekts.Option (a) definiert fälschlicherweise den roten Endpunkt. Option (b)Endpunkte werden korrekt definiert. Option (c) definiert die Endpunkte in der ursprünglichen Form neu.Da in der Technologie , die wir angenommen, wird die Schaltung regeneriert jedes Mal , haben wir Neusuche für die Punkte der Übereinstimmung (oder besser gesagt, deren Indizes) durch die erschöpfende Suche Verfahren : nearestContourPtIdx(const vector<Point> &contour, const Point& pt);
Für Fälle, in denen es nicht möglich ist, die Merkmale vollständig zu entfernen, wurde auch ein zusätzlicher Modus der Lichtbogentrennung implementiert (separat mit dem internen / externen Lichtbogen arbeiten). Dies ist beispielsweise in Fällen wichtig, in denen der äußere Bogen der Kontur mit anderen Objekten in Kontakt steht oder verrauscht ist . In diesem Fall können Sie mit dem internen Lichtbogen arbeiten. In diesem Fall ist es nicht erforderlich, die externen und internen Lichtbögen getrennt zu verarbeiten.Gemäß der bekannten Formel für das Verhältnis der Konvexität des Bogens wird der Radius des Kreises ungefähr geschätzt und zu große Ellipsen werden verworfen:R = bulge / 2 + SQR(hypot) / (8 * bulge);
Somit wurde für alle Konturen ihre Konvexitätsdefektmetrik gefunden (oder sie werden als linear oder klein klassifiziert und aus dem Verfahren entfernt). In der letzten Phase werden der ursprünglichen Metrik zusätzliche Parameter hinzugefügt, z. B. der gedrehte Bemaßungsparameter usw., und der gesamte Satz der untersuchten Metriken wird nach Größe sortiert . typedef tuple<int ,
RotatedRect,
Vec4i,
int>
RectDefMetric;
Algorithmus zum Verknüpfen von Bogensegmenten an Endpunkten
Der Wachstumsalgorithmus ist klar und offensichtlich: Wir nehmen die größte Kontur als Keim und versuchen, sie zu züchten, dh die nächstgelegenen Flecken zu finden und an ihren Endpunkten anzubringen, die die Wachstumsbedingungen erfüllen. In der gewachsenen Figur geben wir den gewünschten elliptischen Bogen ein . Maskieren und subtrahieren Sie die Figur vom Originalsatz. Wir wiederholen den Wachstumsvorgang, bis der anfängliche Satz abgelaufen ist .Das grundlegende Verfahren des Wachstumsalgorithmus sieht folgendermaßen aus: vector<Point> *patch =
growingContours(contour, def, tmp, hull);
Dabei ist Kontur die untersuchte Kontur, Def ist der Konvexitätsfehler, Rumpf ist das konvexe Polygon der gesamten Region, tmp ist die Hilfspuffermatrix. Am Ausgang erhalten wir eine vektorgewachsene Kontur.Das Verfahren besteht aus einem Zyklus von Versuchen, das Wachstum zu säen, der entweder durch Erschöpfung der verfügbaren Patches für das Wachstum endet oder durch den Parameter der maximalen Anzahl von Iterationen begrenzt wird .
Abbildung 5. Viele Flecken für das Wachstum ohne Samen DieHauptschwierigkeit besteht darin, die Flecken auszuwählen, die den Endpunkten der Kontur am nächsten liegen , sodass die Figur nur nach vorne wächst . Für tangentiale RichtungWir nehmen die gemittelte Linie, die zum Bogen in der Nähe des Endpunkts gehört. In Abbildung 6 werden die Kandidaten für die Verbindung mit dem Startwert bei einer bestimmten Iteration angezeigt.
Abbildung 6. Samen, umgeben von mehreren Wachstumskandidaten-Patches.Für jedes Kandidaten-Patch wird die folgende Metrik berechnet:typedef tuple<
double,
bool, bool,
int,
Vec4i>
DistMetric;
Es werden nur Flecken berücksichtigt, die in den Tangentialkegel fallen . Dann wird der Patch mit dem geringsten Abstand gewählt wird , und durch Aufdrucken der Verbindungsabschnitt in das Raster, verbindet mit dem entsprechenden Ende des Samens. Für das andere Ende des Seeds wird ein Patch gesucht, der den Parametern entspricht, und wenn es gefunden wird, wird es auch mit dem Seed verbunden. Dann wird der Samen maskiert und von den vielen Flecken abgezogen . Der Vorgang wird von Anfang an wiederholt.Am Ende des Wachstumsvorgangs haben wir einen elliptischen Bogen erhalten , der noch überprüft werden muss.Verwenden Sie zunächst das Standard- OpenCVDie Prozedur, die unser Patch empfängt (in Form eines Pfads erinnern wir uns, dass der Pfad und das Raster mit uns austauschbar sind) und gibt die gedrehte Dimension zurück , dh eine vollständige Ellipse. RotatedRect box = fitEllipse(patch);
Dann lehnen wir zu große und zu kleine Ellipsen ab und wenden dann unser ursprüngliches Verfahren zum Vergleichen der Bereiche des resultierenden elliptischen Bogens und des anfänglichen Wachstumsfelds in Rasterform an . Diese Prozedur enthält einige getarnte Tricks, daher werden wir ihre Beschreibung vorerst weglassen.Und schließlich finden wir die verbleibenden Parameter der erkannten Ellipse - den Start- und Endwinkel (die Halbachsen kennen wir bereits aus fitEllipse ).Um den Start- und Endwinkel zu bestimmen, gehen wir wie folgt vor: Wir transformieren unsere vollständige Ellipse zurück zum Polygon und finden durch direkte Aufzählung die Punkte, die unseren Enden am nächsten liegen. Ihre Winkelkoordinaten(in der Tat Indizes) und sind die Start- und Endwinkel eines elliptischen Bogens. Im Code sieht es so aus (etwas vereinfacht): pair<int, int>
ellipseAngles(const RotatedRect &box,
vector<Point> &ell, const Point &ps,
const Point &pe, const Point &pm)
{
vector<Point> ell0;
ellipse2Poly(Point(box.center.x, box.center.y),
Size(box.size.width / 2, box.size.height / 2),
box.angle, 0, 355, 5, ell0);
int i0 = nearestContourPtIdx(ell0, ps);
int i1 = nearestContourPtIdx(ell0, pe);
cutSides(ell0, i0, i1, i2, ell, nullptr);
return pair<int, int>(i0, i1);
}
Unser cutSides- Verfahren berücksichtigt die Topologie der elliptischen Bogenquerung . Insgesamt sollten acht mögliche Fälle der Umgehung der Indizes i0, i1, i2 berücksichtigt werden . Gehen wir entlang der äußeren oder der inneren Kontur, und welcher der Indizes ist größer, anfänglich oder endgültig?Einfacher zu erkennender Code: void cutSides(
const vector<Point> &ell0, int i0, int i1, int i2,
vector<Point> *ell_in, vector<Point> *ell_out)
{
if (i0 < i1) {
if (i2 > i0 && i2 < i1) {
if (ell_in) {...}
if (ell_out) {...}
} else {
if (ell_in) {...}
if (ell_out) {...}
}}
else {
if (i2 > i1 && i2 < i0) {
if (ell_in) {...}
if (ell_out) {...}
} else {
if (ell_in) {...}
if (ell_out) {...}
}}}
Einige Ergebnisse der Erkennung von Ellipsen in komplexen Fällen sind in Abbildung 7 dargestellt .
In den folgenden Artikeln werden statistische Nachweismethoden betrachtet.