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

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Вы можете сделать это очень эффективно с помощью двухпроцессного алгоритма linear O(n) time (n - количество пикселей):

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

повторите, пока:

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

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

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

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

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

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