Какую структуру данных подобрать для водораздела (watershed)?

Question

[Сергей]

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

Comments

[DmitryBB]

В зависимости от задачи и средств реализации можно попробовать готовые алгоритмы из библиотеки OpenCV.
Возможно, такое решение может дать выигрыш производительности и скорости разработки.

[Сергей]

OpenCV я тыкал, но, во-первых, я хочу в первую очередь понять, а во-вторых, у меня не совсем водораздел.

Answer 1

[xmoonlight]

Луч от пикселя на заданный радиус с поворотом на 3 неравных ацикличных угла.

Comments

[Сергей]

Я правильно понимаю, что массив надо представить как планарный ациклический граф?

[xmoonlight]

Сергей, зачем? что это даст?

[Сергей]

Я хочу увеличить скорость исполнения ценой расхода памяти и работать с массивами произвольной размерности (сегментация мультиспектральных снимков). Или Вы про мой комментарий выше?

[xmoonlight]

Сергей, зачем именно планарный ациклический граф? (что это даст в плане производительности?)

[Сергей]

xmoonlight, Значит, я совсем неверно понял ваш ответ. Можете чуть развернуть?
Я рассуждал, что такой граф исключит множественный обход, правда, сложность его построения я не оценивал.

[xmoonlight]

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

Радиус (длину луча) нужно делать в зависимости от требуемой минимальной детализации искомого объекта: меньше детализация => меньше объект => меньше радиус (короче хеш, больше итераций).

[Сергей]

xmoonlight, Принцип понял. А почему лучей советуете 3?

[xmoonlight]

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

[Сергей]

xmoonlight, а в чём принципиальная разница с Гауссовой пирамидой? Мы ж и там, и там делаем предположение по окрестности.

[xmoonlight]

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

[Сергей]

xmoonlight, каждый раз, когда мне кажется, что я понимаю ваш ответ, оказывается, что я излишне оптимистичен :) Можете, пожалуйста, псевдокод приложить?

[xmoonlight]

Сергей, Давайте так, чтобы по-честному.
Вы - пишите своё понимание псевдокодом, потом я - своё.

[Сергей]

xmoonlight, извините за задержку, полез смотреть точное определение ridge-ей в водоразделе и увлёкся. По поводу псевдокода: я так и не понял в каком алгоритме водораздела можно невозбранно пропускать пиксели/узлы. Если мы берём классический priority flood, то при замене "честной" окрестности на лучи у нас получаются оверсегментация и неправильные границы. Если мы берём watershed cuts (чужая реализация), то тоже узлы пропускать нельзя, иначе срез неправильно построится. К счастью, пока искал, наткнулся на решение, которое мне вполне подходит.

[xmoonlight]

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