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

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

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

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

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

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

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

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

Изменить: Чтобы уточнить, как только у меня есть дерево, я могу извлечь "ветки" (ветки начинаются у листьев или узлов, связанных с 3 или более другими узлами). Тогда алгоритм в openCV approxPolyDP() является алгоритм Рамера-Дугласа-Пьюкера, и вот фотография Википедии о том, что она делает:

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

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

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

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

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

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

Ответы

Ответ 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]

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

Ответ 2

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

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

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

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

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

Другая идея.

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

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

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

Ответ 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, поэтому единственные результаты, которые у меня есть, - это. Здесь результат приведенного выше алгоритма на изображении:

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