Алгоритм скелетизации изображения [Ищу]

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by mr.The, 11 Mar 2009.

  1. mr.The

    mr.The Elder - Старейшина

    Joined:
    30 Apr 2007
    Messages:
    1,093
    Likes Received:
    459
    Reputations:
    38
    Сабж. Нужна реализация алгоритма скелетизации изображения(желательно бинарного) на любом языке высокого уровня. C#\C++\Delphi приветствуется. Алгоритм Зонга-Суня не предлагать.
     
  2. slesh

    slesh Elder - Старейшина

    Joined:
    5 Mar 2007
    Messages:
    2,704
    Likes Received:
    1,224
    Reputations:
    455
    Я когдато пробывал делать распознование, пытался писать свой алгоритм, но алг. зонга суня довал самые хорошие результаты, а если переписать на ASM то и скорость становилась очень хорошей
     
  3. St0nX

    St0nX Elder - Старейшина

    Joined:
    19 May 2007
    Messages:
    257
    Likes Received:
    46
    Reputations:
    0
    Волновой алгоритм
    http://ocrai.narod.ru/vectory.html
    Canny
    http://en.wikipedia.org/wiki/Canny_edge_detector

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

    mr.The Elder - Старейшина

    Joined:
    30 Apr 2007
    Messages:
    1,093
    Likes Received:
    459
    Reputations:
    38
    slesh, мне скорость не сильно существенна. а переписывать с асма на нужный мне язык будет гемором..
    St0nX, мне нужна готовая реализация. Волновой алгоритм находил, но несмог его реализовать. Слишком много кода получается. А канни попробую. Спасибо.
    ----
    Тема остаётся актуальной.
     
  5. ZagZag

    ZagZag Elder - Старейшина

    Joined:
    22 Feb 2007
    Messages:
    149
    Likes Received:
    22
    Reputations:
    1
    Теории много, а на практике практически никто ничего не реализовал. А если и реализовал, то не делятся этим, и правильно делают.

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

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

    Dr.Jekill New Member

    Joined:
    4 Nov 2009
    Messages:
    13
    Likes Received:
    0
    Reputations:
    0
    Распознавание номера

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

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

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

    mr.The Elder - Старейшина

    Joined:
    30 Apr 2007
    Messages:
    1,093
    Likes Received:
    459
    Reputations:
    38
    Dr.Jekill, нет, я, в итоге, юзал алгоритм Зонга-Суня(реализацию находил в инете, на С, если не ошибаюсь). Но после оказалось, Нейронную сеть нужно было слишком долго учить, и нужно было использовать другие варианты НС(у меня был достаточно примитивный вариант). В итоге, я оставил эту затею.

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

    Dr.Jekill New Member

    Joined:
    4 Nov 2009
    Messages:
    13
    Likes Received:
    0
    Reputations:
    0
    mr.The, спасибо за ссылку - сейчас буду смотреть.
    А Вы случайно не скачивали себе, по ZagZag'овской ссылке "РАСПОЗНАВАНИЕ АВТОМОБИЛЬНОГО РЕГИСТРАЦИОННОГО НОМЕРНОГО ЗНАКА С ЛОКАЛИЗОВАННОЙ ОБЛАСТИ"? Может сохранилось, а то ZagZag, по ходу отписался от темы.
     
  9. ZagZag

    ZagZag Elder - Старейшина

    Joined:
    22 Feb 2007
    Messages:
    149
    Likes Received:
    22
    Reputations:
    1
    Нашел у себя в архиве. Презалил по просьбе.
    http://depositfiles.com/files/l3qr5mt67

    Кстати, у меня та ссылка открывается, там PDF'ка лежит
     
    #9 ZagZag, 22 Nov 2009
    Last edited: 22 Nov 2009
  10. altblitz

    altblitz Elder - Старейшина

    Joined:
    5 Jun 2009
    Messages:
    3,524
    Likes Received:
    2,873
    Reputations:
    231
    самое неочевидное, казалось бы на первый взгляд.
    развлекался с подругами на сайтах - "оденься и раденься"

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

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

    PandoraBox Elder - Старейшина

    Joined:
    6 May 2007
    Messages:
    262
    Likes Received:
    176
    Reputations:
    7
    Зонга-Суня на С:
    Code:
    /* 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:
    Code:
    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 (слабо эффективный):
    Code:
    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ки, так что если что-то не понятно можете посмотреть в ее исходники.
     
    #11 PandoraBox, 13 Dec 2009
    Last edited: 14 Dec 2009
  12. Dr.Jekill

    Dr.Jekill New Member

    Joined:
    4 Nov 2009
    Messages:
    13
    Likes Received:
    0
    Reputations:
    0
    Ящик Пандоры - GREAT!

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

    Dr.Jekill New Member

    Joined:
    4 Nov 2009
    Messages:
    13
    Likes Received:
    0
    Reputations:
    0
    Добавил к репутации.
    Вы пишите: "...можете посмотреть в ее исходники...".
    Извините, я не понял. А где?
     
  14. PandoraBox

    PandoraBox Elder - Старейшина

    Joined:
    6 May 2007
    Messages:
    262
    Likes Received:
    176
    Reputations:
    7
    по теме база хранения знаний http://cerebrum.codeplex.com/Release/ProjectReleases.aspx?ReleaseId=21360
     
    #14 PandoraBox, 19 Dec 2009
    Last edited: 19 Dec 2009
Loading...