Пиксельное перекрытие с полигоном: эффективный алгоритм (тип линии сканирования)
Постановка задачи: у меня есть прямоугольное и равномерно распределенное изображение пикселей с координатами вершины (i,j), (i+1,j), (i, j+1), (i+1, j+1) [i=0,..., м-1; j=0,...,n-1] и многоугольник P с координатами вершины (x_1,y_1), ..., (x_n, y_n). Теперь я хочу эффективно рассчитать процент каждого пикселя, перекрывающегося с P. P может быть невыпуклым или даже самопересечением.
По сути, это "мягкое" обобщение алгоритмов растеризации линий сканирования, которые эффективно проверяют, лежат ли центры пикселей внутри / снаружи многоугольника.
Я могу думать о следующих подходах:
(1) Повторите выборку изображения (например, в 10 × 10 раз), посчитайте, сколько субпиксельных центров находится внутри многоугольника, и разделите на 100. Проблемы: экономия времени, эффективность памяти, точность.
(2) Используйте алгоритм линии сканирования на немного большей и (0,5,0,5) переведенной сетке, чтобы вычислить пиксели, которые полностью лежат внутри / снаружи, создать список "пограничных" пикселей, пройти против часовой стрелки вдоль краев и вычислить области пересечения со всеми пикселями вдоль пути. Проблемы: требует тонкого кодирования, легко вносить ошибки.
Мой вопрос: кто-нибудь уже сталкивался с этой проблемой, и знаете ли вы третий, превосходящий подход? А если нет, то сделали ли вы лучший опыт с (1) или с (2)? Я предполагаю, что эта проблема может возникнуть в контексте сглаживания?
2 ответа
Выполнение точного геометрического анализа может быть не слишком сложным.
Сначала разберитесь с пикселями, которые частично покрыты многоугольником: вы можете использовать метод трассировки лучей, чтобы быстро найти все пиксели, которые пересекаются с краями многоугольника. Затем вы можете использовать алгоритм Коэна-Сазерленда, чтобы эффективно найти точки пересечения между краем и пикселем, и, следовательно, вы можете вычислить зону покрытия для этого пикселя.
Обратите внимание, что вы можете избежать одной из двух операций отсечения, связанных с Коэном-Сазерлендом, поскольку смежные пиксели будут иметь общую точку пересечения сегмента. Например, если у вас есть два смежных пикселя, A а также B которые пересекаются с сегментом p->q в точках a1, a2, b1 а также b2, затем a2 а также b1 будет таким же. Проходящий сегмент a2->q в рутине при стрижке B следует избегать повторения работы.
Вы должны будете обработать пиксели, которые содержат вершины многоугольника, особенно, но опять же это не должно быть слишком хитрым: Коэн-Сазерленд также поможет здесь.
Самопересекающиеся многоугольники также создают некоторые особые случаи - пиксели, которые пересекаются с двумя или более ребрами. Я легко могу себе представить, что обработка этих данных во всех случаях может оказаться сложной, поэтому я бы соблазнился просто использовать здесь метод повышающей дискретизации.
Как только эти краевые пиксели были идентифицированы, вы можете выполнить стандартную линию сканирования, чтобы заполнить внутренние пиксели многоугольника.
редактировать: На самом деле, теперь, когда я думаю об этом больше, вы можете полностью пропустить шаг Коэн-Сазерленд. Алгоритм в связанной статье может быть легко расширен, чтобы вернуть точки пересечения между сегментом и сеткой пикселей. Сегмент оставит данный пиксель в min( tMaxX, tMaxY ), Отслеживайте последнюю точку выхода для повторного использования в качестве точки входа для следующего пикселя.
Я бы сделал
1a) Upsample, когда пиксель частично перекрывается:
но не все изображение, только текущий пиксель, который нужно проверить, или все пиксели в текущей строке развертки, если это поможет.
Чем нет аргумента памяти.
скорость? до 16x16 я не думаю, что скорость это проблема.