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

Question

Текущая ситуация : я пытаюсь извлечь сегменты из изображения.Благодаря findContours() методу openCV, у меня теперь есть список из 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 соседних узла), и это возможно, потому что я уже работаю над довольно тонкими контурами.Затем я могу запустить алгоритм минимального связующего дерева 1053 *.И, наконец, я могу аппроксимировать каждую ветвь дерева с помощью openCV approxPolyDP()

сегментация http://img197.imageshack.us/img197/4488/segmentation.png

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

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

---

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

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

---

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

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

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

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

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

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

---

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

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

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

Answer 1

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

Создайте морфологический график:

graph = MorphologicalGraph[binaryimage];

Тогда вы можетезапросите свойства графа, которые вас интересуют.

Это дает имена вершин в графе:

vertex = VertexList[graph]

Список ребер:

EdgeList[graph]

И это дает позиции вершины:

pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

Вот как выглядят результаты для первого изображения:

In[21]:= vertex = VertexList[graph]

Out[21]= {1, 3, 2, 4, 5, 6, 7, 9, 8, 10}

In[22]:= EdgeList[graph]

Out[22]= {1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4,  3 \[UndirectedEdge] 4, 
          3 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6,  6 \[UndirectedEdge] 7, 
          6 \[UndirectedEdge] 9, 8 \[UndirectedEdge] 9,  9 \[UndirectedEdge] 10}

In[26]:= pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

Out[26]= {{54.5, 191.5}, {98.5, 149.5},  {42.5, 185.5}, 
          {91.5, 138.5}, {132.5, 119.5}, {157.5, 72.5},
          {168.5, 65.5}, {125.5, 52.5},  {114.5, 53.5}, 
          {120.5, 29.5}}

Учитывая документацию, http://reference.wolfram.com/mathematica/ref/MorphologicalGraph.html, команда MorphologicalGraph сначала вычисляет скелет морфологическим истончением:

skeleton = Thinning[binaryimage, Method -> "Morphological"]

Затем обнаруживается вершина;они являются точками ветвления и конечными точками:

verteximage = ImageAdd[
                  MorphologicalTransform[skeleton, "SkeletonEndPoints"],   
                  MorphologicalTransform[skeleton, "SkeletonBranchPoints"]]

И затем вершины связываются после анализа их связности.

Например, одинможно начать с разрушения структуры вокруг вершины, а затем искать связанные компоненты, раскрывая края графика:

comp = MorphologicalComponents[
           ImageSubtract[
               skeleton, 
               Dilation[vertices, CrossMatrix[1]]]];
Colorize[comp] 

Дьявол кроется в деталях, ноэто звучит как надежная отправная точка, если вы хотите разработать собственную реализацию.

Answer 2

Попробуйте математическую морфологию. Сначала вам нужно dilate или close ваше изображение, чтобы заполнить отверстия.

cvDilate(pimg, pimg, NULL, 3);
cvErode(pimg, pimg, NULL);

Я получил это изображение

Следующим шагом должно стать применение алгоритма прореживание . К сожалению, это не реализовано в OpenCV (MATLAB имеет bwmorph с аргументом thin). Например, с MATLAB я улучшил изображение до этого:

Однако OpenCV имеет все необходимые базовые морфологические операции для осуществления прореживания (cvMorphologyEx, cvCreateStructuringElementEx и т. Д.).

Другая идея.

Говорят, что преобразование расстояния кажется очень полезным в таких задачах. Может быть и так. Рассмотрим функцию cvDistTransform. Создает изображение, подобное этому:

Затем используйте что-то вроде cvAdaptiveThreshold:

Это скелет. Я думаю, что вы можете перебирать все подключенные белые пиксели, находить кривые и отфильтровывать небольшие сегменты.

Answer 3

Я уже реализовывал подобный алгоритм и делал это в некотором порядке наименьших квадратов.Это сработало довольно хорошо.Псевдокод выглядит примерно так:

L = empty set of line segments
for each white pixel p
  line = new line containing only p
  C = empty set of points
  P = set of all neighboring pixels of p
  while P is not empty
    n = first point in P
    add n to C
    remove n from P
    line' = line with n added to it
    perform a least squares fit of line'
    if MSE(line) < max_mse and d(line, n) < max_distance
      line = line'
      add all neighbors of n that are not in C to P
  if size(line) > min_num_points
    add line to L

где MSE (линия) - среднеквадратичная ошибка линии (сумма по всем точкам в линии квадрата расстояния до наилучшей линии подгонки) и d(линия, n) - расстояние от точки n до линии.Хорошие значения для max_distance кажутся примерно равными пикселям, а max_mse, по-видимому, намного меньше и будет зависеть от среднего размера отрезков на вашем изображении.0,1 или 0,2 пикселя работали в довольно больших изображениях для меня.

Я использовал это на реальных изображениях, предварительно обработанных с помощью оператора Canny, так что единственные результаты, которые у меня есть, - это.Вот результат описанного выше алгоритма на изображении:

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

Answer 4

Вы можете начать с извлечения прямых линий из изображения контуров, используя HoughLinesP, который предоставляется с openCV:

HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLength = 0, double maxLineGap = 0)  

Если вы выберете threshold = 1 и minLineLenght small, вы можете даже получить всеотдельные элементы.Будьте осторожны, так как это дает много результатов, если у вас много краевых пикселей.