Automatisches Zuschneiden beliebiger Formen

Ich habe eine beliebige Form, die durch eine Binärmaske definiert ist (grau = Form, schwarz = Hintergrund).

Ich möchte ein größtmögliches Rechteck finden, das nur graue Pixel enthält (ein solches Rechteck ist gelb dargestellt):

Die Form ist immer "einteilig", aber nicht unbedingt konvex (nicht alle Punktpaare an der Formgrenze können durch eine gerade Linie verbunden werden, die durch die Form verläuft).

Manchmal existieren viele solcher "maximalen Rechtecke" und dann können weitere Einschränkungen eingeführt werden, wie zum Beispiel:

• Das Rechteck so nehmen, dass sein Mittelpunkt dem Massenmittelpunkt (oder dem Bildmittelpunkt) der Form am nächsten liegt
• Ein Rechteck mit einem Seitenverhältnis nehmen, das einem vordefinierten Verhältnis (dh 4: 3) am nächsten kommt

Mein erster Gedanke an den Algorithmus ist folgender:

1. Berechnen Sie die Entfernungstransformation der Form und finden Sie den Schwerpunkt
2. Vergrößern Sie den quadratischen Bereich, während er nur die Pixel der Form enthält
3. Vergrößern Sie das Rechteck (ursprünglich ein Quadrat) in der Breite oder Höhe, während es nur die Pixel der Form enthält.

Ich denke jedoch, ein solcher Algorithmus wäre langsam und würde nicht zu einer optimalen Lösung führen.

Irgendwelche Vorschläge?

Auf Matlab Fileexchange befindet sich ein Code, der für Ihr Problem relevant ist: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle/content/html/Inscribed_Rectangle_demo.html

Aktualisieren

Ich habe diesen Tutorial-Artikel über die Berechnung der größten eingeschriebenen Rechtecke auf der Grundlage des obigen Links von Atul Ingle geschrieben.

Der Algorithmus sucht zuerst nach den größten Quadraten auf einer Binärmaske. Dies geschieht mit einem einfachen dynamischen Programmieralgorithmus. Jedes neue Pixel wird mit den drei bereits bekannten Nachbarn aktualisiert:

squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1

Die Beispielbinärmaske und die berechnete Karte sehen folgendermaßen aus:

Wenn Sie das Maximum in der Karte nehmen, sehen Sie das größte eingeschriebene Quadrat:

Der Suchalgorithmus für Rechtecke durchsucht die Maske dann zweimal nach zwei Klassen von Rechtecken:

• Breite größer als das Quadrat (und Höhe möglicherweise kleiner)
• Höhe größer als das Quadrat (und Breite möglicherweise kleiner)

Beide Klassen sind durch die größten Quadrate begrenzt, da kein Rechteck an einem bestimmten Punkt beide Dimensionen größer als das eingeschriebene Quadrat haben kann (obwohl eine Dimension größer sein kann).

Man muss eine Metrik für Rechteckgrößen wählen, wie Fläche, Umfang oder gewichtete Summe der Dimensionen.

Hier ist die resultierende Karte für Rechtecke:

Es ist praktisch, Position und Größe des besten bisher gefundenen Rechtecks ​​in einer Variablen zu speichern, anstatt Karten zu erstellen und dann nach Maxima zu suchen.

Die praktische Anwendung dieses Algorithmus ist das Beschneiden von nicht rechteckigen Bildern. Ich habe diesen Algorithmus in meiner Bildbibliothek SharpStitch verwendet :