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

[mr.The]

Сабж. Нужна реализация алгоритма скелетизации изображения(желательно бинарного) на любом языке высокого уровня. C#\C++\Delphi приветствуется. Алгоритм Зонга-Суня не предлагать.

[slesh]

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

[St0nX]

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

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

[mr.The]

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

[ZagZag]

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

Вот хорошие статьи по теме скелетизации и вообще компьютерному зрению.
Непрерывный скелет бинарного растрового изображения (http://www.graphicon.ru/1998/Image_Processing_&%20_Computational_Geometry/Mestetskiy_p.pdf)

РАСПОЗНАВАНИЕ АВТОМОБИЛЬНОГО РЕГИСТРАЦИОННОГО НОМЕРНОГО ЗНАКА С ЛОКАЛИЗОВАННОЙ ОБЛАСТИ (http://www.inf.tsu.ru/library/DiplomaWorks/CompScience/2006/burenin/diplom.pdf)

[Dr.Jekill]

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

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

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

[mr.The]

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

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

[Dr.Jekill]

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

[ZagZag]

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

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

[altblitz]

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

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

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

[PandoraBox]

Зонга-Суня на С:
/* 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]

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

[Dr.Jekill]

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

[PandoraBox]

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