Извлечение сегментов из списка 8-соединенных пикселей

Текущая ситуация : Я пытаюсь извлечь сегменты из изображения. Благодаря методу openCV findContours () , теперь у меня есть список точек с 8 соединениями для каждого контура. Однако эти списки нельзя использовать напрямую, потому что они содержат много дубликатов.

Проблема : Учитывая список из 8 связанных точек, который может содержать дубликаты, извлечь из него сегменты.

] Возможные решения:

• Вначале я использовал метод openCV приблизительноPolyDP () . Однако результаты довольно плохие ... Вот увеличенные контуры:

Вот результат приблизительноPolyDP () : (9 сегментов! Некоторые перекрываются)

, но я хочу большего например:

Это плохо, потому что приблизительноPolyDP () может преобразовать что-то, что «выглядит как несколько сегментов», в «несколько сегментов». Однако у меня есть список точек, которые, как правило, повторяются несколько раз сами по себе.

Например, если мои точки следующие:

0 1 2 3 4 5 6 7 8 
  9   

Тогда список точек будет 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9 ... И если количество точек становится большим (> 100), тогда сегменты, извлеченные с помощью приблизительноPolyDP () , к сожалению, не дублируются (т.е. они перекрывают друг друга, но не являются строго равными, поэтому я не могу просто сказать «удалить дубликаты», в отличие от пикселей, например)

• Возможно, у меня есть решение, но оно довольно длинное (хотя и интересно) . Прежде всего, для всего 8-связного списка я создаю разреженную матрицу (для эффективности) и устанавливаю значения матрицы на 1, если пиксель принадлежит списку. Затем я создаю граф с узлами, соответствующими пикселям, и краями между соседними пикселями. Это также означает, что я добавляю все недостающие края между пикселями (небольшая сложность, возможная из-за разреженной матрицы). Затем я удаляю все возможные «квадраты» (4 соседних узла), и это возможно, потому что я уже работаю над довольно тонкими контурами. Затем я могу запустить алгоритм минимального остовного дерева . И, наконец, я могу аппроксимировать каждую ветвь дерева с помощью сегментации openCV приблизительноPolyDP ()

http://img197.imageshack.us/img197/4488/segmentation.png

Вот фантастические картинки (спасибо Paint !) исходного списка и связанного графа. Затем, когда я добавляю края между соседями. И, наконец, когда я удаляю ребра и создаю минимальное остовное дерево (здесь бесполезно)

Подведем итог: у меня есть утомительный метод, который я еще не реализовал, поскольку он кажется подверженным ошибкам. Однако я спрашиваю вас , люди в StackOverflow: есть ли другие существующие методы, возможно, с хорошей реализацией?

Редактировать: Чтобы уточнить, как только у меня есть дерево, я могу извлекать «ветки» (ветки начинаются в листьях или узлах, связанных с 3 или более другими узлами) Затем алгоритм в openCV приблизительно да:

С этим рисунком легко понять, почему он не работает, когда точки могут быть дубликатами друг друга

Еще одно изменение: в моем методе есть кое-что, что может быть интересно отметить. Когда вы рассматриваете точки, расположенные в сетке (например, пиксели), то, как правило, алгоритм минимального остовного дерева бесполезен, потому что существует много возможных минимальных деревьев

X-X-X-X
|
X-X-X-X

, фундаментально сильно отличается от

X-X-X-X
| | | |
X X X X

, но оба являются минимальными остовными деревьями

] Однако в моем случае мои узлы редко образуют кластеры, потому что они должны быть контурами, и уже есть алгоритм прореживания, который заранее запускается в findContours () .

Ответ на комментарий Томалака:

Если алгоритм DP возвращает 4 сегмента (сегмент от точки 2 до центра присутствует дважды), я был бы счастлив! Конечно, при хороших параметрах я могу попасть в состояние, когда «случайно» у меня будут одинаковые сегменты, и я могу удалить дубликаты. Однако очевидно, что алгоритм не предназначен для этого.

Вот реальный пример со слишком большим количеством сегментов: