Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Ecken eines gedrehten/verzerrten Rechtecks vor weißem Hintergrund erkennen
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

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

beantworten | zitieren | melden

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
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo anfänger,

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

herbivore
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

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).
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
Coffeebean
myCSharp.de - Team

Avatar #avatar-3295.gif


Dabei seit:
Beiträge: 2461
Herkunft: Deutschland/Schweiz

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Coffeebean am .
private Nachricht | Beiträge des Benutzers
Lennart
myCSharp.de - Member



Dabei seit:
Beiträge: 429
Herkunft: Bawü

beantworten | zitieren | melden

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?
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

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.
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

Dritter Fall:
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
Coffeebean
myCSharp.de - Team

Avatar #avatar-3295.gif


Dabei seit:
Beiträge: 2461
Herkunft: Deutschland/Schweiz

beantworten | zitieren | melden

Hallo blutiger_anfänger,
Zitat
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
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

Zitat
Hast du eine Bilddatei, so wie abgebildet, die im Hintergrund weiss ist und darauf ist das Pixelbild gelegt?
Ja.
Zitat
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.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von blutiger_anfänger am .
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
Coffeebean
myCSharp.de - Team

Avatar #avatar-3295.gif


Dabei seit:
Beiträge: 2461
Herkunft: Deutschland/Schweiz

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

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?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von blutiger_anfänger am .
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
Somakia
myCSharp.de - Member



Dabei seit:
Beiträge: 288
Herkunft: Hessen

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Coffeebean
myCSharp.de - Team

Avatar #avatar-3295.gif


Dabei seit:
Beiträge: 2461
Herkunft: Deutschland/Schweiz

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Somakia
myCSharp.de - Member



Dabei seit:
Beiträge: 288
Herkunft: Hessen

beantworten | zitieren | melden

@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.
private Nachricht | Beiträge des Benutzers
Coffeebean
myCSharp.de - Team

Avatar #avatar-3295.gif


Dabei seit:
Beiträge: 2461
Herkunft: Deutschland/Schweiz

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Somakia
myCSharp.de - Member



Dabei seit:
Beiträge: 288
Herkunft: Hessen

beantworten | zitieren | melden

Zitat von Coffeebean
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.
private Nachricht | Beiträge des Benutzers
deerhunter
myCSharp.de - Member



Dabei seit:
Beiträge: 92

beantworten | zitieren | melden

Hallo Karill!

Schau dir einmal diesen Artikel zum Thema Kantenerkennung an.

VG, Florian
private Nachricht | Beiträge des Benutzers
Lennart
myCSharp.de - Member



Dabei seit:
Beiträge: 429
Herkunft: Bawü

beantworten | zitieren | melden

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).
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

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...
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers
Lennart
myCSharp.de - Member



Dabei seit:
Beiträge: 429
Herkunft: Bawü

beantworten | zitieren | melden

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:
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Lennart am .
Attachments
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
MrSparkle
myCSharp.de - Team

Avatar #avatar-2159.gif


Dabei seit:
Beiträge: 5985
Herkunft: Leipzig

beantworten | zitieren | melden

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
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von MrSparkle am .
Weeks of programming can save you hours of planning
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
blutiger_anfänger
myCSharp.de - Member



Dabei seit:
Beiträge: 312
Herkunft: Meerbusch, NRW

Themenstarter:

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von blutiger_anfänger am .
Attachments
Wenn ich nicht hier bin, findest du mich auf code-bude.net.
private Nachricht | Beiträge des Benutzers