Finden Sie die Ecken eines verformten Rechtecks ​​

Question

Ich versuche, ein Programm zu machen, das automatisch die Perspektive eines Rechtecks ​​korrigiert. Ich habe es geschafft, die Silhouette des Rechtecks ​​zu bekommen, und habe den Code, um die Perspektive zu korrigieren, aber ich kann die Ecken nicht finden. Das größte Problem ist, dass, weil es verformt wurde, habe ich nicht den folgenden „Code“ verwenden kann:

c1 = min(x), min(y) 
    c2 = max(x), min(y) 
    c3 = min(x), max(y) 
    c4 = max(x), max(y) 

Dies würde nicht mit dieser Situation arbeiten (X steht für eine Ecke):

X0000000000X 
.00000000000 
..X000000000 
.....0000000 
........0000 
...........X 

Weiß jemand, wie man das macht?

Answer 1

Am weitesten vom Zentrum entfernt gibt es eine Ecke. Der weiteste Punkt von der ersten Ecke wird Ihnen eine andere Ecke geben, die entweder benachbart oder gegenüber der ersten sein kann. Der weiteste Punkt von der Linie zwischen diesen beiden Ecken (ein bisschen mehr Mathe intensiv) wird Ihnen eine dritte Ecke geben. Ich würde die Entfernung von der Mitte als Tiebreaker benutzen. Um die 4. Ecke zu finden, ist es der Punkt außerhalb des Dreiecks, das von den ersten 3 Ecken gebildet wird, die am weitesten von der nächsten Linie zwischen diesen Ecken entfernt sind.

Dies ist ein sehr zeitaufwendiger Weg, und ich habe es noch nie versucht, aber es sollte funktionieren.

Answer 2

Sie könnten versuchen, einen Scanline-Algorithmus zu verwenden - Für jede Linie des Polygons (also y = min (y) .. max (y)), erhalten Sie l = min (x) und r = max (x). Berechnen Sie die linke/rechte Steigung (deltax) und vergleichen Sie sie mit der Steigung der Linie davor. Wenn es sich geändert hat (verwenden Sie hier eine Toleranz), befinden Sie sich in einer Ecke des Rechtecks ​​(oder in der Nähe davon). Das wird nicht in allen Fällen funktionieren, da die Steigung wegen der geringen Auflösung nicht genau sein kann, aber für große Rechtecke und nicht zu ähnliche Neigungen sollte dies funktionieren.

Zumindest funktioniert es gut für Ihr Beispiel:

X0000000000X l = 0, r = 11 
.00000000000 l = 1, r = 11, deltaxl = 1, deltaxr = 0 
..X000000000 l = 2, r = 11, deltaxl = 1, deltaxr = 0 
.....0000000 l = 5, r = 11, deltaxl = 3, deltaxr = 0 
........0000 l = 8, r = 11, deltaxl = 3, deltaxr = 0 
...........X l = 11, r = 11, deltaxl = 3, deltaxr = 0 

Sie beginnen mit der Spitze des Rechtecks ​​in dem Sie zwei verschiedene Werte für l und r erhalten, so dass Sie bereits zwei der Ecken aufweisen. Auf der linken Seite erhalten Sie für die ersten drei Zeilen deltax = 1, aber danach erhalten Sie deltax = 3, also gibt es eine Ecke bei (3, 3). Auf der rechten Seite ändert sich nichts, deltax = 0, so dass Sie nur den Punkt am Ende erhalten.

Beachten Sie, dass Sie Ecken hier "sammeln", also, wenn Sie nicht 4 Ecken am Ende haben, waren die Neigungen zu ähnlich (oder Sie haben ein Bild von einem Dreieck) und Sie können zu einem anderen wechseln (genauer) Algorithmus oder geben Sie einfach einen Fehler. Dasselbe gilt, wenn Sie mehr als 4 Ecken oder andere seltsame Dinge wie Löcher im Rechteck haben. Es scheint, dass irgendeine Art von Bilderkennung beteiligt ist, so dass diese Fälle auftreten können, oder?

Es gibt Fälle, in denen eine einfache deltax = (x - lastx) nicht gut arbeiten, dieses Beispiel für die linke Seite eines Rechtecks ​​sehen:

xxxxxx 
xxxxx deltax = 1 dy/dx = 1/1 = 1 
xxxxx deltax = 0 dy/dx = 2/1 = 2 
    xxxx deltax = 1 dy/dx = 3/2 = 1.5 
    xxxx deltax = 0 dy/dx = 4/2 = 2 
    xxx deltax = 1 dy/dx = 5/3 = 1.66 

Manchmal deltax 0, manchmal 1 Es ist besser, die Steigung der Linie vom tatsächlichen Punkt zum oberen linken/rechten Punkt (deltay/deltax) zu verwenden. Wenn Sie es verwenden, müssen Sie immer noch mit einer Toleranz bleiben, aber Ihre Werte werden mit jeder neuen Zeile genauer.

Answer 3

Dies sieht wie ein Problem mit der konvexen Hülle aus.

http://en.wikipedia.org/wiki/Convex_hull

Ihr Problem ist einfacher, aber die gleiche Lösung sollte funktionieren.

Answer 4

Sie könnten eine Hough-Transformation verwenden, um die 4 markantesten Linien im maskierten Bild zu finden. Diese Linien werden die Seiten des Vierecks sein. Die Linien werden sich in bis zu 6 Punkten schneiden, das sind die 4 Ecken und die 2 perspektivischen Fluchtpunkte.

Diese sind leicht zu unterscheiden: Wählen Sie einen beliebigen Punkt innerhalb des Vierecks und prüfen Sie, ob die Linie von diesem Punkt zu jedem der 6 Schnittpunkte eine der Linien schneidet. Wenn nicht, dann ist dieser Schnittpunkt eine Ecke.

Dies hat den Vorteil, dass es auch für verrauschte oder teilweise blockierte Bilder funktioniert oder wenn Ihre Segmentierung nicht exakt ist.

en.wikipedia.org/wiki/Hough_transform

Example CImg Code

würde ich in den Ergebnissen sehr interessiert. Ich habe darüber nachgedacht, so etwas selbst zu schreiben, um Fotos von schräg geschnittenen Papierbögen zu korrigieren. Ich bin gerade dabei, einen Weg zu finden, um die Perspektive zu korrigieren, wenn die 4 Punkte bekannt sind

p.s.

Überprüfen Sie auch Zhengyou Zhang, Li-Wei He, „Whiteboard-Scannen und Bildverbesserung“ http://research.microsoft.com/en-us/um/people/zhang/papers/tr03-39.pdf für eine erweiterte Lösung für Vierecks Erkennung

ich eine ähnliche Frage gestellt haben, die die zu lösen versucht, Perspektive Umwandlung: proportions of a perspective-deformed rectangle