Текущая ситуация: я пытаюсь извлечь сегменты из изображения. Благодаря методу openCV findContours()
у меня теперь есть список точек с 8 связями для каждого контура. Однако эти списки не могут использоваться напрямую, потому что они содержат много дубликатов.
Проблема: Учитывая список 8-связанных точек, которые могут содержать дубликаты, извлеките из него отрезки.
Возможные решения:
- Сначала я использовал метод openCV
approxPolyDP()
. Однако результаты довольно плохие... Вот масштабные контуры:
Вот результат approxPolyDP()
: (9 сегментов! Некоторое перекрытие)
но я хочу больше:
Это плохо, потому что approxPolyDP()
может преобразовать что-то, что "выглядит как несколько сегментов" в "нескольких сегментах". Однако у меня есть список точек, которые имеют тенденцию к повторению нескольких раз над собой.
Например, если мои точки:
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), то сегменты, извлеченные approxPolyDP()
, к сожалению, не дублируются (то есть: они перекрывают друг друга, но не являются строго равными, поэтому я не могу просто сказать "удалить дубликаты", в отличие от пикселей, например)
- Возможно, у меня есть решение, но оно довольно длинное (хотя и интересное). Прежде всего, для всех 8-связанных списков я создайте разреженную матрицу (для эффективности) и установите для значений матрицы значение 1, если пиксель принадлежит списку. Затем я создаю график, с узлами, соответствующими пикселям, и ребрами между соседними пикселями. Это также означает, что я добавить все недостающие края между пикселями (сложность маленькая, возможная из-за разреженной матрицы). Затем я удаляю все возможные "квадраты" (4 соседних узла), и это возможно, потому что я уже работаю над довольно тонкими контурами. Затем я могу запустить алгоритм минимального связующего дерева. И, наконец, я могу аппроксимировать каждую ветвь дерева с помощью openCV
approxPolyDP()
сегментация http://img197.imageshack.us/img197/4488/segmentation.png
Вот фантастические снимки (спасибо Paint!) исходного списка и связанный граф. Затем, когда я добавляю ребра между соседями. И, наконец, когда я удаляю ребра и создаю минимальное остовное дерево (здесь не полезно)
Подводя итог: у меня есть утомительный метод, который я еще не реализовал, поскольку он кажется подверженным ошибкам. Тем не менее, я прошу вы, люди из StackOverflow: существуют ли другие существующие методы, возможно, с хорошими реализациями?
Изменить: Чтобы уточнить, как только у меня есть дерево, я могу извлечь "ветки" (ветки начинаются у листьев или узлов, связанных с 3 или более другими узлами). Тогда алгоритм в openCV approxPolyDP()
является алгоритм Рамера-Дугласа-Пьюкера, и вот фотография Википедии о том, что она делает:
С этой картинкой легко понять, почему она терпит неудачу, когда точки могут быть дублирующими друг друга
Другое редактирование: В моем методе есть что-то интересное отметить. Когда вы рассматриваете точки, расположенные в сетке (например, пиксели), то, как правило, минимальный алгоритм связующего дерева не полезен, так как существует много возможных минимальных деревьев
X-X-X-X
|
X-X-X-X
фундаментально отличается от
X-X-X-X
| | | |
X X X X
но оба являются минимальными связующими деревьями
Однако в моем случае мои узлы редко образуют кластеры, потому что они должны быть контурами, и уже существует алгоритм прореживания, который выполняется заранее в findContours()
.
Ответ на комментарий Томалака:
Если алгоритм DP возвращает 4 сегмента (сегмент от точки 2
до центра, который будет там дважды), я был бы счастлив! Конечно, с хорошими параметрами я могу добраться до состояния, где "случайно" у меня одинаковые сегменты, и я могу удалить дубликаты. Однако, очевидно, алгоритм не предназначен для него.
Вот реальный пример с слишком большим количеством сегментов: