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:
- Oblicz transformację odległościową kształtu i znajdź jego środek masy
- Rozwijaj kwadratowy obszar, gdy zawiera on tylko piksele kształtu
- 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?
image-processing
image
geometry
Libor
źródło
źródło
Odpowiedzi:
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:
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:
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 :
źródło