Berechnung der Länge von Objekten im Binärbild - Algorithmus

Ich denke, das Problem ist einfach, wenn die Grenze eines Objekts konvex ist und keine drei Ecken auf einer Linie liegen (dh kein Eckpunkt kann entfernt werden, ohne das Polygon zu ändern): Dann können Sie einfach zwei Punkte zufällig auswählen und a verwenden Einfache Suche nach Gradienten-Abstieg, um die längste Linie zu finden:

Ich würde also vorschlagen, die konvexe Hülle für jeden Seed-Blob zu finden, alle "überflüssigen" Scheitelpunkte zu entfernen (um die Konvergenz sicherzustellen) und den obigen Algorithmus auszuführen.

Das Konstruieren einer konvexen Hülle ist eine O (n log n) -Operation IIRC, wobei n die Anzahl der Grenzpixel ist. Sollte für kleine Objekte wie diese ziemlich effizient sein. BEARBEITEN : Ich habe mich gerade daran erinnert, dass der O (n log n) für den konvexen Hüllenalgorithmus benötigt wurde, um die Punkte zu sortieren . Wenn die Grenzpunkte das Ergebnis einer verbundenen Komponentenanalyse sind, sind sie bereits sortiert. Daher sollte der gesamte Algorithmus in der O (n) Zeit laufen, wobei n die Anzahl der Grenzpunkte ist. (Es ist jedoch eine Menge Arbeit, weil Sie vielleicht Ihren eigenen Algorithmus für die konvexe Hülle schreiben oder einen ändern müssen, um die Sortierung zu überspringen.)

Hinzufügen: Antwort auf Kommentar

Wenn Sie keine 100% ige Genauigkeit benötigen, können Sie einfach eine Ellipse an jeden Blob anpassen und die Länge der Hauptachse berechnen: Dies kann aus zentrale Momente (IIRC ist es einfach die Quadratwurzel, wenn der größte Eigenwert der Kovarianzmatrix), also ist es eine O (n) Operation und kann effizient in einem einzigen Durchlauf über die berechnet werden Bild. Es hat den zusätzlichen Vorteil, dass es alle Pixel eines Blobs berücksichtigt, nicht nur zwei extreme Punkte, d. H. Es ist weit weniger von Rauschen betroffen.

Finden Sie die Hauptachsenlänge der Ellipse, die dieselben normalisierten zweiten zentralen Momente wie die Region aufweist. In MATLAB können Sie regionprops verwenden.

Ein sehr primitiver Ansatz wäre es, zuerst alle Kantenpixel (jedes schwarze Pixel im Objekt neben einem nicht schwarzen Pixel) zu identifizieren und die Abstände zwischen allen möglichen Paaren von Kantenpixeln zu berechnen. Die längste dieser Entfernungen gibt Ihnen die Länge des Objekts.

Wenn die Objekte immer wie die in Ihrer Probe aussehen, können Sie dies beschleunigen, indem Sie nur die Pixel mit den höchsten und niedrigsten x- und y-Werten innerhalb des Objekts auswerten.

Ich würde vorschlagen, eine "umgekehrte" Entfernungstransformation zu versuchen. In der magischen Welt der mathematischen Morphologie (Entschuldigung konnte der Alliteration nicht widerstehen) gibt die Abstandstransformation den kleinsten Abstand jedes Pixels zum nächsten Grenzpixel. In Ihrem Fall interessieren Sie sich für die entfernteste Entfernung zu einem Grenzpixel, daher habe ich geschickt einen "umgekehrten" Präfix angewendet.

Informationen zur Entfernung finden Sie hier und hier . Ich glaube, dass Matlab die Distanztransformation nach hier implementiert . Das würde mich zu der Annahme verleiten, dass man eine Open-Source-Implementierung der Distanztransformation in Oktave finden kann. Darüber hinaus würde es mich nicht im geringsten überraschen, wenn opencv es implementiert hätte.

Ich habe nicht viel darüber nachgedacht, aber es ist für mich intuitiv, dass Sie in der Lage sein sollten, die Distanztransformation umzukehren und sie ungefähr in der gleichen Zeit wie die ursprüngliche Distanztransformation zu berechnen.

Ich denke, Sie könnten einen Algorithmus für die erste Suche nach der Breite in Erwägung ziehen.

Die Grundidee ist, dass Sie jede Zeile und Spalte im Bild durchlaufen, und wenn Sie den Knoten noch nicht besucht haben (ein Knoten ist eine Zeile und Spalte mit einem farbigen Pixel), dann würden Sie zuerst die Breite ausführen Suche. Sie würden jeden möglichen Knoten besuchen und die maximalen und minimalen Punkte für das Objekt verfolgen.

Hier ist ein C ++ - Beispielcode (ungetestet):