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

[ertaquo]

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]);
   }
  }
}

[GMile]

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]);
    }
  }
}


[liq]

Ну кто же алгоритмы CV без картинок объясняет?

[agorkov]

Я много думал, но так и не придумал, куда здесь можно вставить картинки.

[liq]

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

[Qbit]

Здесь картинки ещё прикольнее.

[liq]

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

[Qbit]

Парсер лох. Плюс «Вы не можете комментировать чаще, чем 1 раз в 5 минут».
bik-top.livejournal.com/37060.html

[liq]

Не думаю, что получится. Ну для начала, вы сможете аналитически представить изображение цифр?
Даже если сможете подогнать что-то похожее то у вас будет много параметров, а с ростом количества параметров растет сложность. В общем не для этого он был сделан.

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

[Error_403_Forbidden]

Я этот алгоритм применял для нахождения и устранения прямых в капче мегафона.
Так что студент прав.

[JerryJJ]

Можно и более мирные применения придумать :)

Например, распознавание линий дорожной разметки для системы автоматизированного управления автомобилем или анализ научных фотоснимков (в атомной физике, например).

[KL7]

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

За статью спасибо, но без картинок все-таки не хорошо =)

[GetWindowsDirectory]

Спасибо за алгоритм. Добавлю в избранное.

[SovGVD]

еще один торт! =) спасибо за алгоритм — люблю над картинками по извращаться в свободное время всякими формулами/сравнениями и т.д.

[Orion]

>вдоль строк ® и столбцов ©
Я считаю самое классное использование значков прав и коприрайта! :)

[GetWindowsDirectory]

Очень оригинально, поначалу даже и не понял что они значат.

[futureader]

В двух словах — Hough transform строит отображение из пространства изображения в пространство параметров заданного типа кривых. Еще студентом занимался — алгоримом было легко определить легкий поворот страницы. В курсовике была подазадача по нарезке таблицы на ячейки. Кстати говоря — в матлабе есть спец функция для Hough transform

[Vamp]

www.rob.cs.tu-bs.de/content/04-teaching/06-interactive/HNF.html
Тут лежит занятная демка ня java-апплете. С исходниками.

[Constantine]

Тема интересна, ждем продолжения! :)

[dapa]

Очень интересно. Можно подробнее про алгоритмы обнаружения именно кривых 2го или 3го порядка?

[agorkov]

А можно конкретнее? Просто алгоритм Хафа легко расширяется на любые кривые.

[dapa]

Надо выловить кривые Безье… много кривых, круто «замешаных», что-то типа лекал.
я предполагаю искать кривые второго порядка, потом из них уже составлять полные Безье. Только вот на вскидку получается что-то около 6ти параметров для подбора кривой… как-то имхо многовато будет. Особенно если искать на А3 и кривые считаются тысячами. Мысли есть такие: можно сканировать в пределах скользящего окна, можно приблизительно определять угол касательной в точке, что-бы сократить количество коэффициентов… в общем, можно использовать 2 точки вместо одной, много вариантов…

[agorkov]

Если кривых сотни, то Хаф ту может и не справиться. Надо искать другие варианты.