Laden...

Ecken eines gedrehten/verzerrten Rechtecks vor weißem Hintergrund erkennen

Erstellt von blutiger_anfänger vor 12 Jahren Letzter Beitrag vor 12 Jahren 4.954 Views
B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren
Ecken eines gedrehten/verzerrten Rechtecks vor weißem Hintergrund erkennen

Hallo,

ich habe schon die ein oder andere Googlesuche hinter mir, komme aber nicht weiter.
Gibt es einen schnellen Algorhitmus zur Erkennung der vier Ecken eines Rechtecks?

Es handelt sich um Grafiken, wie jene im Anhang. Die Grafiken können um ihre eigene Achse ge-/verdreht sein. Ich möchte lediglich die vier Ecken bestimmen.

Ich hatte auch schon den MoravecCornersDetector der AForge Library in den Fingern, dieser ist aber eher ungeeignet in meinem Fall, da er alle Ecken sucht. Also auch zwischen jedem kleinen Quadrat, was ihn relativ Langsam macht.
Ansonten bin ich bei der Suche immer wieder auf diverse Corner/Edge Detector Algorhitmen gestoßen. Diese berechnen jedoch auch alle wesentlich mehr, als die vier äußeren Ecken der gekachelten Fläche.

Ich hoffe ihr könnt mir helfen.

Viele Grüße,
Raffi

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo anfänger,

welches Rechteck willst du denn erkennen? Mit ist nicht mal klar, ob dein Bild der Input oder das Ergebnisrechteck ist.

herbivore

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

Ich bekomme die Bilder so, wie sie auch hier angehängt sind rein. (inklusive dem weißen Rand drumherum.)

Erkennen will ich die Koordinaten der folgenden Ecken. (Siehe Anhang).

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

2.207 Beiträge seit 2011
vor 12 Jahren

Hallo blutiger_anfänger,

dann fehlen uns Informationen. Auf was sind die Bilder denn platziert? Auf einem anderen Bild? In einem Word File? Die Koordinaten müssen sich ja auf etwas beziehen (Stichwort: Nullpunkt).

Gruss

Coffeebean

EDIT:

Falls die Bilder so kommen, sind die Koordinaten durch Länge/Breite des Bildes zu errechnen.

L
416 Beiträge seit 2008
vor 12 Jahren

Wenn du einen weißen Hintegrund hast ist es doch kein Problem das oberste/unterste, am weitesten rechte/linke nicht weiße Pixel zu finden?

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

Die Bilder bekomme ich aus Bilddateien. Die angehängte Datei wäre so ein Fall.

@Coffeebean:
Richtig, die Koordinaten beziehen sich auf die Bilddatei.
Ich will später weitere inhaltliche Auswertungen durchführen. Dafür brauche ich aber die Koordinaten dern vier Eckpunkte. Um die relativen Positionen einzelner, bestimmter Teilblöcke ermitteln zu können.

@Lennart:
Ich schrieb Eingangs, die Bilder können auch verzerrt/gedreht kommen. Dann klappt dein Ansatz leider nicht mehr so leicht.
Als Beispiel habe ich mal so einen Fall angehängt.

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

2.207 Beiträge seit 2011
vor 12 Jahren

Hallo blutiger_anfänger,

Richtig, die Koordinaten beziehen sich auf die Bilddatei.

Das klärt meine Frage nicht ganz 😉 Hast du eine Bilddatei, so wie abgebildet, die im Hintergrund weiss ist und darauf ist das Pixelbild gelegt? Oder worauf basiert denn das Pixelbild? Irgendwo muss doch der Nullpunkt sein. Ist der Nullpunkt die obere linke Ecke des Pixelbildes? Oder ist der Nullpunkt die obere linke Ecke des zu Grunde liegenden Bildes?

Das ist der erste Teil, der zweite Teil dreht sich um das Drehen deines Bildes.

Ist es eventuell ausreichend, um das verdrehte Bild einen "Rahmen" zu spannen und diesen dann auszuschneiden? Hintergrund könntest du, je nach Verwendung, auch transparent machen dann.

Grüsse

Coffeebean

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

Hast du eine Bilddatei, so wie abgebildet, die im Hintergrund weiss ist und darauf ist das Pixelbild gelegt?

Ja.

Oder ist der Nullpunkt die obere linke Ecke des zu Grunde liegenden Bildes?

Korrekt.

Ich hab noch mal ein Bild angehängt. Vielleicht macht es das ja noch mal besser deutlich, was ich meine.
_
edit:// Die Scala ist natürlich fiktiv und die Punkte sind nur geschätzt. Es geht nur darum zu verdeutlichen was ich von wo an berechnen/erkennen will._

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

2.207 Beiträge seit 2011
vor 12 Jahren

Hallo blutiger_anfänger,

dann könntest du, wie schon von Lennart beschrieben, durch die weissen Pixel laufen, bis du auf ein andernFarbiges Pixel stösst. (von oben, links, rechts und unten)

So erhälst du einen Wert der jeweiligen Punktkoordinate. Die andere Koordinate könntest du mittels des Abstands berechnen. Das wird ein wenig Rechnerei, aber ich schiesse jetzt mal ins Blaue und sage, dass es so gehen müsste.

Viele Grüsse

Coffeebean

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

Ich merke schon, wo du drauf hinaus willst, aber ich kann mir nciht vorstellen wie das zum Beispiel für das zweite Bild was ich gepostet hab, gehen sollte. (Das, was verzerrt aber nicht gedreht ist. Der Post von 11:41uhr.)
Ich wüsste nicht, wie ich da die rechte untere Ecke bekommen sollte. Egal in welche Richtugn ich die Pixel durchlaufe. Ich stoße entweder ersten rechts oben, oder links unten an. Nciht aber rechts unten. Und berechnen kann man die Ecke aus den anderen 3 Ecken heraus ja auch nicht so einfach, da das ja kein Parallelogramm, sondern unregelmäßig ist.

Verstehst du was ich meine? Oder habe ich vielleicht einfach nur ein Brett vorm Kopf?

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

S
269 Beiträge seit 2010
vor 12 Jahren

Was noch bestimmt möglich wäre, auch wenns recht subtil aus meiner Sicht ist:
Du suchst dir (wie auch immer) einen Randpunkt deines (nicht Rechtecks sondern) beliebigen Vierecks und folgst dann seinem Rand einmal außenrum (bis du wieder beim ersten Pixel bist). Bei jedem "Richtungswechsel" muss zwangsläufig ja ein Eckpunkt sein.

2.207 Beiträge seit 2011
vor 12 Jahren

Hallo blutiger_anfänger,

auch, wenn es sehr "teuer" ist: Du kannst jedes (!) Pixel durchlaufen und auf die Farbe überprüfen. Anhand seiner Nachbarn (Eckpunkte hätten nur in 3 Pixeln einen nicht-weissen-Nachbarn) kannst du die Eckpunkte rausfiltern.

Je nachde wie Zeitaufwendig deine Anwendung sein soll/muss.

Gruss

Coffeebean

S
269 Beiträge seit 2010
vor 12 Jahren

@Coffeebean ich glaube nicht, dass das so geht. Deine Theorie mit den 3 Pixeln trifft auf rechte Winkel zu, aber wenn die Ecken spitzer oder flacher sind, können auch mehr oder weniger benachbarte Pixel non-white sein.

2.207 Beiträge seit 2011
vor 12 Jahren

Hallo Karill Endusa,

das stimmt, das habe ich nicht bedacht. Trotzdem könnte man festlegen, dass ein "Eckpunkt" mehr weisse als nicht-weisse Pixel haben muss. Bei Gleichheit wäre es eine Kante.

Gruss

Coffeebean

S
269 Beiträge seit 2010
vor 12 Jahren

Bei Gleichheit wäre es eine Kante. Stimmt, und weniger weiße als nicht-weiße Pixel sollte allein schon aus der Logik heraus nicht möglich sein.
Damit ließe sich was anfangen.

D
91 Beiträge seit 2005
vor 12 Jahren

Hallo Karill!

Schau dir einmal diesen Artikel zum Thema Kantenerkennung an.

VG, Florian

L
416 Beiträge seit 2008
vor 12 Jahren

Du könntest mit einem Kantendetektionsfilter (zb Prewitt) über das Bild gehen. So müssten sich die Punkte der Kanten finden lassen. Wenn du nun daraus 4 Geradengleichungen erstellst kannst du die Eckpunkte ausrechnen (Schnittpunkte).

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

Ok, habe jetzt mal den Sobel-Operator implementiert. Kommt aber nicht wirklich das gewünschte Ergebnis raus.
Mit dem Ergebnis lassen sich Geradengleichungen wohl eher schwer aufstellen...

Wenn ich nicht hier bin, findest du mich auf code-bude.net.

L
416 Beiträge seit 2008
vor 12 Jahren

Das sieht doch gut aus 😉
Der nächste Schritt wäre jetzt mittels Hough-Transformation die Kanten zu finden. Müsste irgendwo noch ne Implementierung davon aus Studienzeiten rumfliegen haben ... schreib ne PM wenn ich mal suchen soll.

Edit: Hab ma gesucht und gefunden hier was mit deinem Bild rauskommt:

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo blutiger_anfänger,

berechne für jedes nicht weiße Pixel s1 = x + y und s2 = x - y.

Das Pixel, für das s1 minimal wird, ist die linke obere Ecke.
Das Pixel, für das s1 maximal wird, ist die rechte untere Ecke.
Das Pixel, für das s2 minimal wird, ist die rechte obere Ecke.
Das Pixel, für das s2 maximal wird, ist die linke untere Ecke.

Das sollte immer gelten, außer für Kanten, die exakt im 45° Winkel verlaufen. Diesen Fall muss man noch gesondert behandeln. Das sollte auch relativ einfach sein, man muss ja nur aus der Menge der Pixel mit dem gleichen (minimalen bzw. maximalen) s1 bzw. s2, die mit dem minimalen und maximalen x (oder y) Wert suchen.

herbivore

5.657 Beiträge seit 2006
vor 12 Jahren

Hi blutiger_anfänger,

also mir gefällt der Algorithmus von herbivore bisher am besten. Allerdings hat der den Nachteil, daß die Laufzeit von der Anzahl der nicht-weißen Pixel abhängig ist. Ich würde einen Algorithmus bevorzugen, der von der Anzahl der weißen Pixeln abhängig ist, weil man davon ausgehen kann, daß das gesuchte Bild den größten Bereich einnimmt, und nicht der Rand.

Ich würde daher vorschlagen, eine "Axis-Aligned BoundingBox" des gesuchten Bildes zu berechnen. Die gesuchten Eckpunkte liegen nämlich auf den Rändern der BoundingBox. Dazu würde ich wie folgt vorgehen:

(1) Für jede Bildzeile vom oberen Rand:
       Für jeden Pixel in der Bildzeile:
          Wenn (PixelFarbe != Weiß)
             1. Eckpunkt gefunden.
(2) Schritt (1) für die drei anderen Bildränder durchführen

Als Randbedingung muß man dann nur beachten, daß auch zwei Eckpunkte auf einer Seite der BoundingBox liegen können, wenn eine oder mehrere Seiten des Bildes entlang der X- oder Y-Achse ausgerichtet sind. In diesem Fall muß man nur überprüfen, ob sich in der jeweiligen Bildzeile (oder -spalte) noch weitere nicht-weiße Pixel befinden. Der letzte nicht-weiße Pixel ist dann der zweite Eckpunkt. Dafür sollte man natürlich irgendeinen Schwellwert festlegen, ab welcher Anzahl Pixel eine Bildseite auch erkannt wird.

Aus den vier gefundenen Eckpunkten kann man dann sehr einfach eine Transformations-Matrix berechnen, um das gefundene Bild zu entzerren.

Schöne Grüße,
Christian

// Edit: Formatierung

Weeks of programming can save you hours of planning

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo MrSparkle,

sicher zeigt mein Algorithmus nur die grobe Idee und enthält noch einiges an Optimierungspotenzial. Natürlich muss man wesentlich weniger als alle Pixel betrachten.

So könnte man mit dem mittleren Pixel des Bildes anfangen und sich - unter der Annahme, dass dieses Pixel nicht weiß ist, sonst muss man ein solches erst suchen, z.B. spiralförmig - von da in Richtung der Ecken des Bildes diagonal vorarbeiten. So spannt man zunächst quasi eine innere "Axis-Aligned BoundingBox" auf, ohne alle Pixel eine Zeile oder Spalte prüfen zu müssen. Alle Pixel die darin liegen muss man nicht mehr prüfen, weil sie weder s1 noch s2 weder weiter erhöhen noch weiter vermindern können.

Kommt man einer Kante des Rechtecks an, geht man - wenn es diagonal nicht mehr weitergeht - stattdessen einen Schritt nur horizontal oder nur vertikal weiter, je nachdem was geht. Wenn das nicht geht, biegt man von der ursprünglichen Richtung um 90° nach rechts oder links am, je nachdem was geht (bei 45°-Kanten ist auch beides gleichzeitig möglich, muss man wieder separat behandeln). Von aus probiert man erstmal wieder diagonal in die ursprüngliche Richtung und spielt diesen Absatz erneut durch, bis es gar nicht mehr weiter geht, sprich bis man in einer Ecke angekommen ist.

Je nachdem wie breit der weiße Rand ist, muss man sogar noch deutlich weniger Pixel testen als bei deinem Vorschlag.

Vor allem aber findet dein Vorschlag nur Ecken, die auf der BoundingBox liegen. Das ist aber nicht immer der Fall, wie z.B. das Bild in Lennarts Beitrag und auch Beispiele weiter oben zeigen.

herbivore

B
blutiger_anfänger Themenstarter:in
293 Beiträge seit 2008
vor 12 Jahren

So, dann melde ich mich noch mal zu Wort. Ohne den Beitrag von MrSparkle vorher gesehen zu haben, habe ich es auch so gelöst, wie er es gemacht hätte.

Ich durch laufe alle Zeilen und alle Spalten und nähere mich jeweils von rechts/links und oben/unten an, bis ich den ersten nicht-weißten Pixel finde.

Die Ecken bestimme ich aus der Menge der gefundenen Punkte mittels herbivores Gleichungen.

Das Ergebnis sieht dann wie folgt aus. (Siehe Anhang. Der magenta-farbene Rand sind die einzelnen gefundenen Pixel. Ich hatte diese zur Veranschaulichung eingefärbt.)

Den Weg mit dem Sobel Operator habe ich nicht weiter verfolgt, da allein die Anwendung des Sobel Operator (ohen weitere Kantenerkennungen, Ecken finden) schon knapp über 6 Sekunden gedauert hat.
Die jetzige Lösung/umsetzung ist da wesentlich schneller.

Viele Grüße,
Raffi

Wenn ich nicht hier bin, findest du mich auf code-bude.net.