agorkov 29 авг 2010 в 12:40

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

4 мин

48K

Алгоритмы *

+63

Комментарии 25

ertaquo 29 авг 2010 в 13:00

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 29 авг 2010 в 14:05

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 29 авг 2010 в 13:05

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

agorkov 29 авг 2010 в 13:09

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

liq 29 авг 2010 в 13:18

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

Qbit 29 авг 2010 в 16:23

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

liq 29 авг 2010 в 16:27

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

Qbit 29 авг 2010 в 16:28

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

НЛО прилетело и опубликовало эту надпись здесь

liq 29 авг 2010 в 13:51

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

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

Error_403_Forbidden 29 авг 2010 в 16:16

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

JerryJJ 29 авг 2010 в 13:55

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

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

KL7 29 авг 2010 в 14:09

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

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

GetWindowsDirectory 29 авг 2010 в 13:54

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

SovGVD 29 авг 2010 в 13:57

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

Orion 29 авг 2010 в 14:12

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

GetWindowsDirectory 29 авг 2010 в 14:40

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

НЛО прилетело и опубликовало эту надпись здесь

futureader 29 авг 2010 в 20:00

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

Vamp 30 авг 2010 в 02:27

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

Constantine 30 авг 2010 в 11:08

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

dapa 2 фев 2011 в 06:28

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

agorkov 2 фев 2011 в 10:03

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

dapa 2 фев 2011 в 15:09

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

agorkov 2 фев 2011 в 15:16

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий