Полигонизация пиксельной 2D-кривой

Question

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

Кто-нибудь знает какие-либо алгоритмы, которые могут сделать это в разумные сроки? Если это будет иметь значение, я буду реализовывать это в MATLAB.

Answer 1

Вы можете попробовать посмотреть алгоритм активных контуров (или Змей, если хотите). http://en.wikipedia.org/wiki/Active_contour_model

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

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

Вы можете начать с доступного набора инструментов (есть много других): http://www.mathworks.com/matlabcentral/fileexchange/11643-active-contour-toolbox