Automatyczne kadrowanie dowolnych kształtów

14

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):

wprowadź opis zdjęcia tutaj

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)

wprowadź opis zdjęcia tutaj

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?

Libor
źródło
2
Czy to jest pomocne? mathworks.com/matlabcentral/fileexchange/…
Atul Ingle
@AtulIngle Extactly! Dzięki. Czy możesz dodać odpowiedź, aby ją zaakceptować? Spróbuję następnie edytować odpowiedź, aby rozwinąć więcej szczegółów na temat algorytmu - ale nie chcę po prostu odpowiadać na moje własne pytanie, korzystając z linku, który podałeś ...
Libor
Świetny! Nie mogę się doczekać, aby przeczytać twoją szczegółową odpowiedź, ponieważ nie przeczytałem kodu.
Atul Ingle
@AtulIngle OK, dodałem dyskusję w odpowiedzi i link do pełnego mojego artykułu.
Libor,

Odpowiedzi:

10

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Wykorzystanie maksimum na mapie ujawnia największy wpisany kwadrat:

wprowadź opis zdjęcia tutaj

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:

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

Atul Ingle
źródło