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

14

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

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

введите описание изображения здесь

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

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

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

введите описание изображения здесь

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

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

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

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

ЛИБОР
источник
2
Это полезно? mathworks.com/matlabcentral/fileexchange/…
Атул Ингл
@AtulIngle Точно! Благодарю. Не могли бы вы добавить ответ, чтобы я мог принять его? Затем я попытаюсь отредактировать ответ, чтобы более подробно остановиться на алгоритме, но я не хочу просто отвечать на свой вопрос, используя предоставленную вами ссылку ...
Libor
Большой! Я с нетерпением жду вашего сложного ответа, так как не прочитал код.
Атул Ингл
@AtulIngle Хорошо, я добавил обсуждение в ответ и ссылку на полную мою статью.
Libor

Ответы:

10

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

введите описание изображения здесь

Атул Ингл
источник