Automatyczne kadrowanie dowolnych kształtów

Mam dowolny kształt zdefiniowany przez maskę binarną (szary = kształt, czarny = tło).

Chciałbym znaleźć największy możliwy prostokąt zawierający tylko szare piksele (taki prostokąt jest przedstawiony na żółto):

Kształt jest zawsze „jednoczęściowy”, ale niekoniecznie jest wypukły (nie wszystkie pary punktów na granicy kształtu można połączyć prostą linią przechodzącą przez kształt).

Czasami istnieje wiele takich „maksymalnych prostokątów”, a następnie można wprowadzić dodatkowe ograniczenia, takie jak:

• Przyjmowanie prostokąta o środku najbliższym środkowi masy kształtu (lub środkowi obrazu)
• Przyjmowanie prostokąta o współczynniku kształtu najbliższym predefiniowanemu współczynnikowi (tj. 4: 3)

Moja pierwsza myśl o algorytmie jest następująca:

1. Oblicz transformację odległościową kształtu i znajdź jego środek masy
2. Rozwijaj kwadratowy obszar, gdy zawiera on tylko piksele kształtu
3. Rozwiń prostokąt (pierwotnie kwadrat) na szerokość lub wysokość, gdy zawiera on tylko piksele kształtu.

Myślę jednak, że taki algorytm byłby powolny i nie doprowadziłby do optymalnego rozwiązania.

Jakieś sugestie?

W programie Matlab Fileexchange znajduje się kod, który jest odpowiedni dla twojego problemu: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscriberectangle/content/html/Inscribe_Rectangle_demo.html

Aktualizacja

Napisałem ten samouczek na temat obliczania największych prostokątów wpisanych na podstawie powyższego linku z Atul Ingle.

Algorytm najpierw wyszukuje największe kwadraty na masce binarnej. Odbywa się to za pomocą prostego algorytmu programowania dynamicznego. Każdy nowy piksel jest aktualizowany przy użyciu trzech znanych już sąsiadów:

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

Przykładowa maska ​​binarna i obliczona mapa wyglądają następująco:

Wykorzystanie maksimum na mapie ujawnia największy wpisany kwadrat:

Algorytm wyszukiwania prostokąta skanuje maskę jeszcze dwa razy, szukając dwóch klas prostokątów:

• szerokość większa niż rozmiar kwadratu (i ewentualnie mniejsza wysokość)
• wysokość większa niż rozmiar kwadratu (i ewentualnie mniejsza szerokość)

Obie klasy są ograniczone największymi kwadratami, ponieważ żaden prostokąt w danym punkcie nie może mieć obu wymiarów większych niż kwadrat wpisany (chociaż jeden wymiar może być większy).

Trzeba wybrać metrykę dla rozmiarów prostokąta, taką jak powierzchnia, obwód lub ważona suma wymiarów.

Oto wynikowa mapa prostokątów:

Wygodnie jest przechowywać pozycję i rozmiar najlepszego prostokąta znalezionego do tej pory w zmiennej zamiast budować mapy, a następnie szukać maksimów.

Praktycznym zastosowaniem tego algorytmu jest kadrowanie obrazów nieprostokątnych. Użyłem tego algorytmu w mojej bibliotece zszywania obrazów SharpStitch :