Найдите самую большую выпуклую черную область на изображении

Question

У меня есть изображение, это небольшой вырез:

Как видите, это белые пиксели на черном фоне. Мы можем нарисовать воображаемые линии между этими пикселями (или, точнее, точками). С помощью этих линий мы можем заключить области.

Как найти самую большую выпуклую черную область на этом изображении, в которой нет белого пикселя?

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

P.S .: Изображение не является шумом, оно представляет простые числа ниже 10000000, упорядоченные по горизонтали.

Answer 1

Попытка найти максимальную выпуклую область - трудная задача. Разве вы не были бы в порядке с поиском прямоугольников с максимальной площадью? Эта проблема намного проще и может быть решена за O (n) - линейное время в количестве пикселей. Алгоритм следующий.

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

Вы можете сделать это очень эффективно, используя два прохода линейный O(n) время алгоритм (n - количество пикселей):

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

повтор, до:

2) во втором проходе , идти по строкам, читать current_number. Для каждого числа k отслеживайте суммы последовательных чисел, которые были >= k (то есть потенциальные прямоугольники высотой k). Закройте суммы (потенциальные прямоугольники) для k > current_number и посмотрите, больше ли сумма (~ площадь прямоугольника), чем текущий максимум - если да, обновите максимум. В конце каждой строки закройте все открытые потенциальные прямоугольники (для всех k).

Таким образом, вы получите все максимальные прямоугольники. Конечно, это не то же самое, что максимальная выпуклая область, но, вероятно, даст вам некоторые подсказки (некоторые эвристики) о том, где искать максимальные выпуклые области.

Answer 2

Я нарисую правильный алгоритм поли-времени.Несомненно, необходимо внести структурные улучшения данных, но я считаю, что, в частности, потребуется лучшее понимание этой проблемы для поиска очень больших наборов данных (или, возможно, специальной верхней границы для размеров блока, содержащегомногоугольник).

Основной цикл состоит из угадывания самой низкой точки p в самом большом выпуклом многоугольнике (разрыв связи в пользу самой левой точки) и затем вычисления самого большого выпуклого многоугольника, который может быть с p и точками q, такимичто (qy> py) ||(qy == py && qx> px).

Динамическая программа опирается на те же геометрические факты, что и Сканирование Грэма .Предположим без ограничения общности, что p = (0, 0), и отсортируем точки q по углу, который они делают против часовой стрелки относительно оси x (сравните две точки, учитывая знак их точечного произведения).Пусть точки в отсортированном порядке будут q ₁ ,…, q _n .Пусть q ₀ = p.Для каждого 0 ≤ i 0 , подмножество q ₁ ,…, q _{i- 1} , q _i и q _j .

Базовые случаи, когда i = 0, являются простыми, поскольку единственным «многоугольником» является нольСегмент q ₀ q _j .Индуктивно, чтобы вычислить запись (i, j), мы попробуем для всех 0 ≤ k ≤ i расширить полигон (k, i) с помощью (i, j).Когда мы можем это сделать?Во-первых, треугольник q ₀ q _i q _j не должен содержать других точек.Другое условие заключается в том, что угол q _k q _i q _j лучше не поворачивать направо (еще раз проверьте знак соответствующего точечного произведения).

В конце верните самый большой найденный многоугольник.Почему это работает?Нетрудно доказать, что выпуклые многоугольники имеют оптимальную подструктуру, требуемую динамической программой, и что программа рассматривает именно те многоугольники, которые удовлетворяют характеристике выпуклости Грэма.

Answer 3

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

Answer 4

Если я правильно понимаю вашу проблему, это экземпляр маркировки подключенного компонента.Вы можете начать, например, с: http://en.wikipedia.org/wiki/Connected-component_labeling

Answer 5

Я думал о подходе для решения этой проблемы:

Из множества всех точек генерируем все возможные 3-точечные подмножества.Это набор всех треугольников в вашем пространстве.Из этого набора удалите все треугольники, которые содержат другую точку, и вы получите набор всех пустых треугольников.

Для каждого из пустых треугольников вы затем увеличите его до максимального размера.То есть для каждой точки вне прямоугольника вы должны вставить ее между двумя ближайшими точками многоугольника и проверить, есть ли точки в этом новом треугольнике.Если нет, вы запомните эту точку и область, которую она добавляет.Для каждой новой точки вы хотите добавить ту, которая максимизирует добавленную область.Когда больше точки не могут быть добавлены, был построен максимальный выпуклый многоугольник.Запишите область для каждого многоугольника и запомните область с наибольшей площадью.

Решающим фактором для работы этого алгоритма является ваша способность определить а) находится ли точка внутри треугольника и б) остается ли многоугольник выпуклымпосле добавления определенной точки.

Я думаю, что вы можете уменьшить б) до проблемы а), и тогда вам нужно всего лишь найти наиболее эффективный метод, чтобы определить, находится ли точка в треугольнике.Сокращение пространства поиска может быть достигнуто следующим образом: возьмите треугольник и увеличьте все ребра до бесконечной длины в обоих направлениях.Это разделяет область за пределами треугольника на 6 субрегионов.Хорошо для нас, что только 3 из этих субрегионов могут содержать точки, которые будут придерживаться ограничения выпуклости.Таким образом, для каждой тестируемой точки вам нужно определить, находится ли она в выпукло-расширяющемся субрегионе, что опять-таки является вопросом, находится ли он в определенном треугольнике.круг будет иметь меньшие и меньшие области, которые все еще допускают выпуклое расширение.Однажды точка в вогнутой области больше не станет частью выпукло-расширяющейся области, поэтому вы можете быстро уменьшить количество точек, которые вам придется учитывать для расширения.Кроме того, при тестировании точек на расширение вы можете дополнительно сократить список возможных точек.Если точка проверена как ложная, то она находится в вогнутом субрегионе другой точки, и, следовательно, все другие точки в вогнутом субрегионе проверенных точек не должны рассматриваться, поскольку они также находятся в вогнутом субрегионе внутренней точки.Вы должны быть в состоянии сократить список возможных точек очень быстро.

И все же вам, конечно, нужно делать это для каждого пустого треугольника.

К сожалению, я не могу гарантировать это, добавляявсегда максимальная новая область, в которой ваш многоугольник становится максимально возможным многоугольником.