Автоматическая обрезка произвольных фигур

У меня есть произвольная форма, определяемая бинарной маской (серый = форма, черный = фон).

Я хотел бы найти максимально возможный прямоугольник, содержащий только серые пиксели (такой прямоугольник изображен желтым цветом):

Форма всегда "одна часть", но она не обязательно выпуклая (не все пары точек на границе формы могут быть соединены прямой линией, проходящей через форму).

Иногда существует много таких «максимальных прямоугольников», и тогда могут быть введены дополнительные ограничения, такие как:

• Взятие прямоугольника с центром, ближайшим к центру масс фигуры (или центру изображения)
• Взятие прямоугольника с соотношением сторон, ближайшим к заранее заданному соотношению (т.е. 4: 3)

Моя первая мысль об алгоритме заключается в следующем:

1. Вычислить расстояние преобразования формы и найти ее центр масс
2. Увеличьте площадь, пока она содержит только пиксели фигуры
3. Увеличьте прямоугольник (изначально квадрат) по ширине или высоте, пока он содержит только пиксели формы.

Однако я думаю, что такой алгоритм будет медленным и не приведет к оптимальному решению.

Какие-либо предложения?

В Matlab Fileexchange есть код, который относится к вашей проблеме: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle/content/html/Incribed_Rectangle_demo.html

Обновить

Я написал эту учебную статью о вычислении самых больших вписанных прямоугольников, основываясь на приведенной выше ссылке из Atul Ingle.

Алгоритм сначала ищет самые большие квадраты в двоичной маске. Это делается с помощью простого алгоритма динамического программирования. Каждый новый пиксель обновляется с использованием трех уже известных соседей:

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

Пример бинарной маски и вычисленной карты выглядит следующим образом:

Взяв максимум на карте, вы обнаружите самый большой вписанный квадрат:

Алгоритм поиска прямоугольника, а не сканирования маски еще два раза в поисках двух классов прямоугольников:

• ширина больше размера квадрата (и высота, возможно, меньше)
• высота больше, чем размер квадрата (и ширина, возможно, меньше)

Оба класса ограничены самыми большими квадратами, поскольку ни один прямоугольник в данной точке не может иметь оба измерения больше, чем вписанный квадрат (хотя одно измерение может быть больше).

Нужно выбрать метрику для размеров прямоугольника, таких как площадь, окружность или взвешенная сумма размеров.

Вот итоговая карта для прямоугольников:

Удобно хранить положение и размер лучшего прямоугольника, найденного до сих пор в переменной, вместо того, чтобы строить карты и затем искать максимумы.

Практическое применение этого алгоритма - обрезка непрямоугольных изображений. Я использовал этот алгоритм в моей библиотеке сшивания изображений SharpStitch :