Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)
-   -   Алгоритм скелетизации изображения [Ищу] (https://forum.antichat.xyz/showthread.php?t=110560)

mr.The 11.03.2009 20:27
Алгоритм скелетизации изображения [Ищу]
 
Сабж. Нужна реализация алгоритма скелетизации изображения(желательно бинарного) на любом языке высокого уровня. C#\C++\Delphi приветствуется. Алгоритм Зонга-Суня не предлагать.

slesh 12.03.2009 10:53
Я когдато пробывал делать распознование, пытался писать свой алгоритм, но алг. зонга суня довал самые хорошие результаты, а если переписать на ASM то и скорость становилась очень хорошей

St0nX 12.03.2009 12:09
Волновой алгоритм
http://ocrai.narod.ru/vectory.html
Canny
http://en.wikipedia.org/wiki/Canny_edge_detector

ПС:Были попытки реализовать на С волновой алгоритм если найду скину.

mr.The 12.03.2009 16:16
slesh, мне скорость не сильно существенна. а переписывать с асма на нужный мне язык будет гемором..
St0nX, мне нужна готовая реализация. Волновой алгоритм находил, но несмог его реализовать. Слишком много кода получается. А канни попробую. Спасибо.
----
Тема остаётся актуальной.

ZagZag 17.03.2009 15:57
Теории много, а на практике практически никто ничего не реализовал. А если и реализовал, то не делятся этим, и правильно делают.

Вот хорошие статьи по теме скелетизации и вообще компьютерному зрению.
Непрерывный скелет бинарного растрового изображения

РАСПОЗНАВАНИЕ АВТОМОБИЛЬНОГО РЕГИСТРАЦИОННОГО НОМЕРНОГО ЗНАКА С ЛОКАЛИЗОВАННОЙ ОБЛАСТИ

Dr.Jekill 04.11.2009 20:57
Распознавание номера
 
Доброе время суток всем!
Сейчас занимаюсь системой контроля машин и встала острая проблема выделения области номерного знака. Несколько дней кошмарил поисковики, результат - одна вода. Практической реализации нигде не рассмотренно. Нашел много информации по Хаафу, Канни и Хоку, но преимущественно одна теория. Бьюсь уже второй день, как рыба об лёд.

mr.The, Вы реализовали, то что хотели? Может что-то посоветуете?

ZagZag, не могу достучаться по ссылке на "РАСПОЗНАВАНИЕ АВТОМОБИЛЬНОГО РЕГИСТРАЦИОННОГО НОМЕРНОГО ЗНАКА С ЛОКАЛИЗОВАННОЙ ОБЛАСТИ", а это было бы в тему. Может у Вас сохранилось на жестком? Пожалуйста, киньте на мыло object_pascal@inbox.ru или выложите на форуме, это будет очень полезно.
Заранее благодарен.

mr.The 04.11.2009 22:40
Dr.Jekill, нет, я, в итоге, юзал алгоритм Зонга-Суня(реализацию находил в инете, на С, если не ошибаюсь). Но после оказалось, Нейронную сеть нужно было слишком долго учить, и нужно было использовать другие варианты НС(у меня был достаточно примитивный вариант). В итоге, я оставил эту затею.

Про алгоритм зонга-суня, и ещё 1 алгоритм: _ttp://xain.hackerdom.ru/zine/online/issue0/Breaking%20Da%20CAPTCHA.html

Dr.Jekill 05.11.2009 03:03
mr.The, спасибо за ссылку - сейчас буду смотреть.
А Вы случайно не скачивали себе, по ZagZag'овской ссылке "РАСПОЗНАВАНИЕ АВТОМОБИЛЬНОГО РЕГИСТРАЦИОННОГО НОМЕРНОГО ЗНАКА С ЛОКАЛИЗОВАННОЙ ОБЛАСТИ"? Может сохранилось, а то ZagZag, по ходу отписался от темы.

ZagZag 22.11.2009 18:33
Нашел у себя в архиве. Презалил по просьбе.
http://depositfiles.com/files/l3qr5mt67

Кстати, у меня та ссылка открывается, там PDF'ка лежит

altblitz 22.11.2009 19:37
Цитата:
Сообщение от mr.The
Сабж. Нужна реализация алгоритма скелетизации изображения(желательно бинарного) на любом языке высокого уровня. C#\C++\Delphi приветствуется. Алгоритм Зонга-Суня не предлагать.
самое неочевидное, казалось бы на первый взгляд.
развлекался с подругами на сайтах - "оденься и раденься"

точно и верно трассируют строение тела 3D-сплайнами,

если не найду ссылки на тот сайт, было это года три тому назад,
можно лишь попробовать поиск по ключевым словам:
"размер одежда девушка одеть онлайн"

PandoraBox 13.12.2009 18:05
Зонга-Суня на С:
Код:
/* Zhang-Suen thinning */

int y [256][256];

main()
{

        int i,j,k,n,m;
        int im[256][256];


/*        Read the glyph                                                        */
        scanf ("%d", &n);        scanf("%d", &m);
        for (i=0; i<n; i++) {
          for (j=0; j<m; j++) {
                scanf ("%d", &k);
                im[i][j] = k;
        }  }

        iputim (im, n, m);
        thin_b (im, n, m);
        iputim (im, n, m);
}

iputim (image,n,m)
        int image[256][256],n,m;
{
        int i,j;

        for (i=0; i<n; i++) {
          for (j=0; j<m; j++)  {
                if (image[i][j] >= 100) image[i][j] = 9;
                printf ("%3d", image[i][j]);
          }
          printf ("\n");
        }
}


thin_b (image,nn,mm)
        int image[256][256], nn,mm;
{
/*                Thinning algorithm: CACM 1984 march (Zhang and Suen)        */

        int i,j,n,m,k, cont, br,ar,p1,p2, t1a();
        int a[8];

        printf ("Thinning algorithm: CACM 1984 march (Zhang and Suen)        \n");
        cont = 1;
        while (cont) {
                printf ("+\n");
                cont = 0;

/*        Sub-iteration 1: */
                for (i=0; i<nn; i++)
                  for (j=0; j<mm; j++) {                /* Scan the entire image */
                        if (image[i][j] == 0) {
                                y[i][j] = 0;
                                continue;
                        }
                        ar = t1a (image, i, j, a, &br,nn,mm);        /* Function A */
                        p1 = a[0]*a[2]*a[4];
                        p2 = a[2]*a[4]*a[6];
                        if ( (ar == 1) && ((br>=2) && (br<=6)) &&
                                (p1 == 0) && (p2 == 0) )  {
                                        y[i][j] = 1;
                                        cont = 1;
                        }
                        else y[i][j] = 0;
                }
                subtr (y, image,nn,mm);

/* Sub iteration 2: */
                for (i=0; i<nn; i++)
                  for (j=0; j<mm; j++) {                /* Scan the entire image */
                        if (image[i][j] == 0) {
                                y[i][j] = 0;
                                continue;
                        }
                        ar = t1a (image, i, j, a, &br,nn,mm);        /* Function A */
                        p1 = a[0]*a[2]*a[6];
                        p2 = a[0]*a[4]*a[6];
                        if ( (ar == 1) && ((br>=2) && (br<=6)) &&
                                (p1 == 0) && (p2 == 0) )  {
                                        y[i][j] = 1;
                                        cont = 1;
                        }
                        else y[i][j] = 0;
                }
                subtr (y, image,nn,mm);
        }
}

subtr (a, b, n,m)
        int a[256][256], b[256][256],n,m;
{
        int i,j;

        for (i=0; i<n; i++)
                for (j=0; j<m; j++)
                        b[i][j] -= a[i][j];
}


int t1a (image, i, j, a, b,nn,mm)
        int image[256][256];
        int i,j, *b,nn,mm;
        int a[8];
{
/*        Return the number of 01 patterns in the sequence of pixels
        P2 p3 p4 p5 p6 p7 p8 p9.                                        */

        int n,m;

        for (n=0; n<8; n++) a[n] = 0;
        if (i-1 >= 0) {
                a[0] = image[i-1][j];
                if (j+1 < mm) a[1] = image[i-1][j+1];
                if (j-1 >= 0) a[7] = image[i-1][j-1];
        }
        if (i+1 < nn) {
                a[4] = image[i+1][j];
                if (j+1 < mm) a[3] = image[i+1][j+1];
                if (j-1 >= 0) a[5] = image[i+1][j-1];
        }
        if (j+1 < mm) a[2] = image[i][j+1];
        if (j-1 >= 0) a[6] = image[i][j-1];

        m= 0;        *b = 0;
        for (n=0; n<7; n++) {
                if ((a[n]==0) && (a[n+1]==1)) m++;
                *b = *b + a[n];
        }
        if ((a[7] == 0) && (a[0] == 1)) m++;
        *b = *b + a[7];
        return m;
}

/*                End of method B                                        */
Зонга-Суня на Pas:
Код:
Procedure SkeletizeZS2;
var        i,j,n,m,k, cont, br,ar,p1,p2: integer;
        a:array [0..8] of integer;
begin
pixeldeleted:=false;
{        Sub-iteration 1: }
                for i:=0 to ImgBArrWidth do
                  for j:=0 to ImgBArrHeight do
      begin
                      { Scan the entire image }
                        if (ImgBArr[i,j] = r_false) then
      begin
                                ImgBArr2[i,j] := r_false;
                                continue;
                        end;
                        ar := t1a ( i, j, a, br);        { Function A }
                        p1 := a[0]*a[2]*a[4];
                        p2 := a[2]*a[4]*a[6];
                        if ( (ar = 1) and ((br>=2) and (br<=6)) and
                                (p1 = 0) and (p2 = 0) ) then
        begin
                                        ImgBArr2[i,j] := r_true;
                        end
                        else ImgBArr2[i,j] := r_false;
                end;
                subtr;

{ Sub iteration 2: }
                for i:=0 to ImgBArrWidth do
                  for j:=0 to ImgBArrHeight do
      begin                { Scan the entire image }
                        if (ImgBArr[i,j] = r_false) then
      begin
                                ImgBArr2[i,j] := r_false;
                                continue;
                        end;
                        ar := t1a ( i, j, a, br);        { Function A }
                        p1 := a[0]*a[2]*a[6];
                        p2 := a[0]*a[4]*a[6];
                        if ( (ar = 1) and ((br>=2) and (br<=6)) and
                                (p1 = 0) and (p2 = 0) ) then
        begin
                                        ImgBArr2[i,j] := r_true;
                        end
                        else ImgBArr2[i,j] := r_false;
                end;
                subtr;
end;

function t1a (i, j:integer; var a:array of integer; var b:integer):integer;
var
n,m:integer;
begin
{        Return the number of 01 patterns in the sequence of pixels
        P2 p3 p4 p5 p6 p7 p8 p9.                                        }

 //        int n,m;

        for n:=0 to 8-1 do a[n] := 0;

        if (i-1 >= 0) then
  begin
                a[0] := integer(ImgBArr[i-1,j]);
                if (j+1 < ImgBArrHeight) then
      a[1] := integer(ImgBArr[i-1,j+1]);
                if (j-1 >= 0) then
      a[7] := integer(ImgBArr[i-1,j-1]);
        end;

        if (i+1 < ImgBArrWidth) then
  begin
                a[4] := integer(ImgBArr[i+1,j]);
                if (j+1 < ImgBArrHeight) then
      a[3] := integer(ImgBArr[i+1,j+1]);
                if (j-1 >= 0) then
      a[5] := integer(ImgBArr[i+1,j-1]);
        end;

        if (j+1 < ImgBArrHeight) then
    a[2] := integer(ImgBArr[i,j+1]);
        if (j-1 >= 0) then
    a[6] := integer(ImgBArr[i,j-1]);

        m := 0;
  b := 0;
        for n:=0 to 6 do
  begin
                if ((a[n]=0) and (a[n+1]=1)) then  m:=m+1;
                b := b + a[n];
        end;

        if ((a[7] = 0) and (a[0] = 1)) then m:=m+1;
        b := b + a[7];
        result := m;
end;

procedure subtr;
  var
  i,j:integer;

begin

                for i:=0 to ImgBArrWidth do
                  for j:=0 to ImgBArrHeight do
if ImgBArr2[i,j]=r_true then
begin
                        ImgBArr[i,j] := r_false;
      pixeldeleted:=true;
end;
end;
MB2 на Pas (слабо эффективный):
Код:
Procedure SkeletizeMB;
var r1,r2:boolean;
p:array [0..25] of boolean;
x,y,x2,y2:integer;
v1,v2,v3,v4:integer;
c:integer;
b,a1,a2:boolean;
begin
 pixeldeleted:=false;
 for y:=1 to ImgBArrHeight-1 do
  for x:=1 to ImgBArrWidth-1 do
    ImgBArr2[x,y]:=r_false;

 for y:=2 to ImgBArrHeight-2 do
 begin
  for x:=2 to ImgBArrWidth-2 do
  begin

  c:=0;
  for y2:=1 to 5 do
  for x2:=1 to 5 do
  begin
  c:=c+1;
  p[c]:=boolean(ImgBArr[x+(x2-3),y+(y2-3)]);
  end;

  if ((x=11) and (y=2)) then
  begin
  c:=c+1;
 // showmessage('hi');
  end;

  b:= p[13] and p[19] and not (p[18] or p[14]);
  if b then
  continue;

  b:= p[13] and p[17] and not (p[18] or p[12]);
  if b then
  continue;

  b:= p[13] and p[7] and not (p[8] or p[12]);
  if b then
  continue;

  b:= p[13] and p[9] and not (p[8] or p[14]);
  if b then
  continue;

  a1:=p[13] and p[14] and p[15] and p[9] and p[19] and not(p[12]);
  a1:=a1 or (p[13] and p[18] and p[23] and p[17] and p[19] and not(p[8]));
  a1:=a1 or (p[13] and p[11] and p[12] and p[17] and p[7] and not(p[14]));
  a1:=a1 or (p[13] and p[8] and p[3] and p[7] and p[9] and not(p[18]));

  a2:= p[13] and p[14] and p[18] and p[19] and p[20] and p[24] and not (p[7] or p[8] or p[12]);
  a2:= a2 or ( p[13] and p[12] and p[16] and p[17] and p[18] and p[22] and not (p[8] or p[9] or p[14]));
  a2:= a2 or ( p[13] and p[6] and p[7] and p[8] and p[12] and p[2] and not (p[14] or p[18] or p[19]));
  a2:= a2 or ( p[13] and p[4] and p[8] and p[9] and p[10] and p[14] and not (p[12] or p[17] or p[18]));

  if a1 or a2 then
  begin
    ImgBArr2[x,y]:=r_true;
    pixeldeleted:=true;
  end;
 end;
 end;

  for y:=1 to ImgBArrHeight-1 do
  for x:=1 to ImgBArrWidth-1 do
  if ImgBArr2[x,y]=r_true then
    ImgBArr[x,y]:=r_false;
end;
Примечание: Pas файлы вырезаны с кода OCRки, так что если что-то не понятно можете посмотреть в ее исходники.

Dr.Jekill 14.12.2009 03:58
Ящик Пандоры - GREAT!
 
PandoraBox, тебе цены нет!
Может что-то посоветуешь по такой задаче:
Есть два кадра, первый снят во время t0 (далее предыдущий кадр), а второй во время t (далее текущий кадр). Кадры разбиваются на блоки пикселов и для каждого блока пикселов текущего кадра находится вектор движения (определяет смещение блока пикселов по x и y, относительно предыдущего кадра, основываясь на том, что интенсивность каждого пиксела постоянна). После этого производится обход блоков и сравнение их векторов движения, при этом блоки с похожими (по направлению, длине и т.п.) векторами движения объеденяются. Все эти действия направленны на сегментацию изображений, т.е. на выделение объектов отличных от статичного фона.
Проблема следующая: если предположить, что у нас нет проблем с освещеностью, что текстура объектов ярко выраженна, необходимо подобрать (как вариант усовершенствовать/разработать) быстрый алгоритм нахождения векторов движения. Главными требованиями для этого алгоритма будут: небольшая вычислительная сложность (соотв. время вычислений), и минимальное кол-во ложных векторов движения, не соотв. реальному движению нестатичных объектов. В идеале это кол-во должно приближаться к количеству, как при методе полного перебора (где-то ~35% от общего количества). В сущности проблема в выборе алгоритма. Однако можно подумать в направлении предварительной обработки сообщений для сужения зоны поиска и/или последующего исключения ложных векторов вижения, чтобы снизить риск рассегментации и потери объекта. В общем проблема такая. Может кто что посоветует? :confused:

Dr.Jekill 14.12.2009 04:01
Добавил к репутации.
Вы пишите: "...можете посмотреть в ее исходники...".
Извините, я не понял. А где?

PandoraBox 19.12.2009 19:52
по теме база хранения знаний http://cerebrum.codeplex.com/Release/ProjectReleases.aspx?ReleaseId=21360


Время: 12:34