Алгоритм Хафа для обнаружения произвольных кривых на изображениях

    Преобразование Хафа — это метод обнаружения прямых и кривых линий на полутоновых или цветных изображениях. Метод позволяет указать параметры семейства кривых и обеспечивает поиск на изображении множества кривых заданного семейства. Мы рассмотрим его применение для поиска на изображении прямолинейных отрезков и дуг окружностей.

    В алгоритме преобразования Хафа используется аккумуляторный массив, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых. Например, при обнаружении прямых, описываемых уравнением y=m*x+b, для каждой прямой необходимо вычислить значения двух параметров m и b. При этом в массиве в элементах A[M,B] накапливаются значения, указывающие на вероятность наличия на изображении прямой y=m*x+b, где M и B соответствуют дискретным значениям m и b.

    Массив A используется в алгоритме Хаффа для проверки каждого пиксела изображения и его окрестности. Определяется присутствует ли в данном пикселе выраженный край. Если присутствует, то вычисляются параметры искомой кривой, проходящей через данный пиксел. После оценки параметров прямой в данном пикселе они дискретизируются для получения соответствующих значений M и B, и значение массива A[M,B] увеличивается. В некоторых реализациях увеличение выполняется на единицу, в других на величину мощности края в обработанном пикселе. После обработки всех пикселов выполняется поиск локальных максимумов в аккумуляторном массиве. Точки локальных максимумов соответствуют параметрам наиболее вероятных прямых на изображении.

    Аккумуляторный массив позволяет определить параметры бесконечно протяжённых прямых или кривых, но с его помощью невозможно определить, где именно начинаются и заканчиваются отрезки этих линий. Для получения этой информации можно завести ещё одну структуру данных PTLIST. Элемент PTLIST[M,B] содержит список координат всех пикселов, которые внесли вклад в значение аккумуляторного массива A[M,B]. По содержанию этих списков можно найти присутствующие на изображении отрезки или сегменты кривых.

    Сейчас мы рассмотрели общие принципы метода Хафа, но мы не рассмотрели некоторые важные детали, которые необходимо знать при программной реализации.

    Уравнение прямой y=m*x+b не подходит для представления вертикальных прямых. Удобнее представлять прямые в виде d=x*cos(f)+y*sin(f), где d — это длина перпендикуляра к прямой, а f — угол между перпендикуляром и горизонтальной осью. В системе координат изображения оси направлены вдоль строк и столбцов изображения. Так координата c соответствует x, а координата r — координате (-y), то уравнение прямой принимает вид: d=c*cos(f)-r*sin(f).

    Индексы аккумуляторного массива A соответствуют дискретным значениям d и f. В серии экспериментов 1976 О'Горман и Кловс дискретизировали значения d с шагом 3 и значения f с шагом 10. Ниже в виде процедуры accumulate_lines приведён алгоритм О'Гормана и Кловса для заполнения аккумуляторного массива A и массива списков PTLIST.

    Алгоритм работает в двумерном координатном пространстве. Функция row_gradient и column_gradiet обрабатывают окрестности пикселов для оценки компонент градиента в направлении строк и столбцов. Функция gradient комбинирует комбинирует две эти компоненты для получения величины градиента. Функция atan2 возвращает по заданным компонентам градиента угол в соответствующем квадранте. Процедура accumulate_lines представляет собой версию преобразования Хафа. Оригинальный метод Хафа не предусматривает стандартного метода выделения отрезков прямых. Поэтому была разработана процедура find_lines. Функция pick_greatest_bin возвращает максимальное значение из аккумуляторного массива, присваивая параметрам DQ и THETAQ соответствующие дискретные значения d и f. Функция reader упорядочивает список точек в элементе массива по координате столбца при f<45 или f>135 и по координате строки при 45<=f<=135. Предполагается, что в массивах D и THETA для пикселов содержатся дискретные значения. Аналогично в массиве GRADIENT должны находиться вычисленные значения величины градиента. Процедура merge объединяет список точек соседнего пиксела со списком точек для данного пиксела. При этом сохраняется пространственное упорядочение точек. Процедура set_to_zero обнуляет элемент аккумуляторного массива, чтобы он не был найден повторно. Наконец, процедура create_segments просматривает окончательный упорядоченный список точек и ищет в нём промежутки длиннее одного пиксела. Важно понимать, что преобразование Хафа может обнаружить посторонние разрывные или фиктивные линии, например образованные тенью.



    Для обнаружения окружностей нам придётся добавить в массив A ещё одно измерение, т.к. стандартное описание окружности содержит три параметра:
    r=r0+d*sin(f)
    c=c0-d*cos(f)
    где d — радиус окружности, а r и c — вертикальная и горизонтальная координаты центра окружности.

    На самом деле метод Хафа может использоваться для обнаружения любых кривых, описываемых аналитически. пусть кривая представлена в виде f(x,a)=0, где x — точка изображения, а a — вектор параметров. Процедура поиска подобных кривых состоит из трёх шагов:
    1. Инициализация массива A нулевыми значениями.
    2. Для каждого краевого пиксела x определяется вектор a, что f(x,a)=0 и выполняется увеличение значения соответствующего элемента массива A[a]:=A[a]+1.
    3. Локальные максимумы в аккумуляторном массиве A соответствуют вероятным кривым f на изображении.

    Если вектор a содержит m параметров и каждый из этих параметров принимает M дискретных значений, то временная сложность алгоритма составляет O(M^(m-2)).

    На самом деле, существует множество методов выделения различных линий на изображениях. Если тема интересна, то я могу рассказать о них. Спасибо за внимание.
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 25
    • +14
      S[R, C] — входное полутоновое изображение
      NLINES — количество строк на изображении
      NPIXELS — количество пикселов в строке изображения
      A[DQ, THETAQ] — аккумуляторный массив
      DQ — дискретное расстояние от прямой до начала координат
      THETAQ — дискретный угол между направлением строк и перпундикуляром к прямой, опущенным их начала координат
      procedure accumulate_line(S, A);
      {
       A := 0;
       PTLIST := 0;
       for R := 1 to NLINES
        for C := 1 to NPIXELS
        {
         DR := row_gradient(S, R, C);
         DC := col_gradient(S, R, C);
         GMAG := gradient(DR, DC);
         if GMAG > gradient_treshold
         {
          THETA := atan2(DR, DC);
          THETAQ := quantize_angle(THETA);
          D := abs(C * cos(THETAQ) — R * sin(THETAQ));
          DQ := quantize_distance(D);
          A[DQ, THETAQ] := A[DQ, THETAQ] + GMAG;
          PTLIST(DQ, THETAQ) := append(PTLIST(DW, THETAQ), [R, C]);
         }
        }
      }
      • +14
        S[R, C]       — входное полутоновое изображение
        NLINES        — количество строк на изображении
        NPIXELS       — количество пикселов в строке изображения
        A[DQ, THETAQ] — аккумуляторный массив
        DQ            — дискретное расстояние от прямой до начала координат
        THETAQ        — дискретный угол между направлением строк и перпундикуляром к прямой, опущенным их начала координат

        procedure accumulate_line(S, A);

          A := 0;
          PTLIST := 0;

          for R := 1 to NLINES
          for C := 1 to NPIXELS
          {
            DR   := row_gradient(S, R, C);
            DC   := col_gradient(S, R, C);
            GMAG := gradient(DR, DC);

            if GMAG > gradient_treshold
            {
              THETA  := atan2(DR, DC);
              THETAQ := quantize_angle(THETA);
              D      := abs(C * cos(THETAQ) — R * sin(THETAQ));
              DQ     := quantize_distance(D);

              A[DQ, THETAQ]      := A[DQ, THETAQ] + GMAG;
              PTLIST(DQ, THETAQ) := append(PTLIST(DW, THETAQ), [R, C]);
            }
          }
        }
      • +13
        Ну кто же алгоритмы CV без картинок объясняет?
        • –4
          Я много думал, но так и не придумал, куда здесь можно вставить картинки.
          • +3
            Тут есть прикольные картинки. Вообще когда прогоняешь алгоритм через реальные примеры, он становится намного понятнее.
            • 0
              Здесь картинки ещё прикольнее.
              • 0
                Вот она демократия хабра.
                Все вроде равны, а я ровнее вас и могу использовать теги.
                • +4
                  Парсер лох. Плюс «Вы не можете комментировать чаще, чем 1 раз в 5 минут».
                  bik-top.livejournal.com/37060.html
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              Не думаю, что получится. Ну для начала, вы сможете аналитически представить изображение цифр?
              Даже если сможете подогнать что-то похожее то у вас будет много параметров, а с ростом количества параметров растет сложность. В общем не для этого он был сделан.

              Единственное можно искать элементы цифр(окружности, линии), а потом их скармливать чему-то более высокоуровневому. Ну или как вариант на простых капчах можно искать всякие зашумляющие линии, синусоиды и прочие штуки и их вырезать, а потом распознавать классическими способами.
              • Я этот алгоритм применял для нахождения и устранения прямых в капче мегафона.
                Так что студент прав.
              • 0
                Можно и более мирные применения придумать :)

                Например, распознавание линий дорожной разметки для системы автоматизированного управления автомобилем или анализ научных фотоснимков (в атомной физике, например).
                • +2
                  На хабре уже была статья про распознавание капч, в которой использовался Хаф для удаления прямых, препятствующих распознаванию. Там же линк на визуальную реализацию алгоритма.

                  За статью спасибо, но без картинок все-таки не хорошо =)
                • +1
                  Спасибо за алгоритм. Добавлю в избранное.
                  • 0
                    еще один торт! =) спасибо за алгоритм — люблю над картинками по извращаться в свободное время всякими формулами/сравнениями и т.д.
                    • +3
                      >вдоль строк ® и столбцов ©
                      Я считаю самое классное использование значков прав и коприрайта! :)
                      • Очень оригинально, поначалу даже и не понял что они значат.
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • 0
                          В двух словах — Hough transform строит отображение из пространства изображения в пространство параметров заданного типа кривых. Еще студентом занимался — алгоримом было легко определить легкий поворот страницы. В курсовике была подазадача по нарезке таблицы на ячейки. Кстати говоря — в матлабе есть спец функция для Hough transform
                          • 0
                            www.rob.cs.tu-bs.de/content/04-teaching/06-interactive/HNF.html
                            Тут лежит занятная демка ня java-апплете. С исходниками.
                            • 0
                              Тема интересна, ждем продолжения! :)
                              • 0
                                Очень интересно. Можно подробнее про алгоритмы обнаружения именно кривых 2го или 3го порядка?
                                • 0
                                  А можно конкретнее? Просто алгоритм Хафа легко расширяется на любые кривые.
                                  • 0
                                    Надо выловить кривые Безье… много кривых, круто «замешаных», что-то типа лекал.
                                    я предполагаю искать кривые второго порядка, потом из них уже составлять полные Безье. Только вот на вскидку получается что-то около 6ти параметров для подбора кривой… как-то имхо многовато будет. Особенно если искать на А3 и кривые считаются тысячами. Мысли есть такие: можно сканировать в пределах скользящего окна, можно приблизительно определять угол касательной в точке, что-бы сократить количество коэффициентов… в общем, можно использовать 2 точки вместо одной, много вариантов…
                                    • 0
                                      Если кривых сотни, то Хаф ту может и не справиться. Надо искать другие варианты.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое