Jump to content
Compvision.ru
Smorodov

Находим скелет (супер :))

Recommended Posts

skeleton.jpg

Архив с проектом здесь: skeleton.rar

  • Like 1

Share this post


Link to post
Share on other sites

Программка иллюстрирующая один из алгоритмов нахождения скелета изображения.

Щелкаем мышкой по левой зеленой сетке (задаем исходное изображение), затем нажимаем "итерация 1", дальше "<-->", потом "итерация 2", "<-->", и сначала. Программка очень простая. Разобраться несложно. Для компиляции нужны компоненты со странички http://smorodov.narod.ru/Builder.htm.

Архив с проектом: Skeletonizator.rar

Skeletonizator.jpg

Share this post


Link to post
Share on other sites

В комментариях в программе написано что описание работы процедуры скелетизации будет дано позже. Хотелось бы побольше узнать об этой процедуре. Как работает? Зачем фильтры и т.д. :(

Share this post


Link to post
Share on other sites
В комментариях в программе написано что описание работы процедуры скелетизации будет дано позже. Хотелось бы побольше узнать об этой процедуре. Как работает? Зачем фильтры и т.д. :(

Конкретно про алгоритм скелетизации тут: скелетизация.rar

Про свертку тут: Свертка.pdf

Оставшиеся вопросы можно задать на форуме :) или в комментах к статьям.

Share this post


Link to post
Share on other sites

В описании алогоритма есть строчки:

Где А(Р1)-число конфигураций 01 в последовательности P2,P3,P4,P5,P6,P7,P8,P9 , замыкая эту цепочку на Р2 ,т.е. вокруг этого пикселя существует только один переход от 0 к 1.

Собственно вопрос: А есть ли в OpenCV функция, возвращающая количество этих переходов из 0 в 1, или придется вручную гонять циклами?

Share this post


Link to post
Share on other sites
В описании алогоритма есть строчки:

Где А(Р1)-число конфигураций 01 в последовательности P2,P3,P4,P5,P6,P7,P8,P9 , замыкая эту цепочку на Р2 ,т.е. вокруг этого пикселя существует только один переход от 0 к 1.

Собственно вопрос: А есть ли в OpenCV функция, возвращающая количество этих переходов из 0 в 1, или придется вручную гонять циклами?

В OpenCV, в примере выше это делается последовательной сверткой изображения, полученного дистанционным преобразованием (из бинарного изображения) при помощи нескольких различных ядер, так как считать отдельные пиксели очень затратно.

Кусок кода оттуда:

// ядра ----------------------

float L0[]={
-1,-1,-1,-1,-1,
0, 0, 0, 0, 0,
2, 2, 2, 2, 2,
0, 0, 0, 0, 0,
-1,-1,-1,-1,-1
};
float L45[]={
0,-1,-1, 0, 2,
-1,-1, 0, 2, 0,
-1, 0, 2, 0,-1,
0, 2, 0,-1,-1,
2, 0,-1,-1, 0
};
float L90[]={
-1, 0, 2, 0,-1,
-1, 0, 2, 0,-1,
-1, 0, 2, 0,-1,
-1, 0, 2, 0,-1,
-1, 0, 2, 0,-1
};
float L135[]={
2, 0,-1,-1, 0,
0, 2, 0,-1,-1,
-1, 0, 2, 0,-1,
-1,-1, 0, 2, 0,
0,-1,-1, 0, 2
};
//........

cvDistTransform(back_project,distsrc,CV_DIST_L2,5);
cvFilter2D(distsrc,S00,&kern00);
cvFilter2D(distsrc,S45,&kern45);
cvFilter2D(distsrc,S90,&kern90);
cvFilter2D(distsrc,S135,&kern135);

for (int y=0; y < out->height; y++){
for (int x=0; x< out->width; x++){
Smax = MAX(
MAX(((float*)(S00->imageData + y* S00->widthStep))[x], ((float*)(S45->imageData + y* S45->widthStep))[x]),
MAX(((float*)(S90->imageData + y* S90->widthStep))[x], ((float*)(S135->imageData + y* S135->widthStep))[x]));
((float*)(out->imageData + y* out->widthStep))[x] = Smax > 0 ? Smax: 0.0;
}
}

cvThreshold(out,out,7,1,CV_THRESH_BINARY);[/code]

В документации описан альтернативный вариант, который применяется в демонстрационном примере.

Share this post


Link to post
Share on other sites

Архив с проектом skeleton.rar не запускается!Возникает ошибка следующего характера:

post-1323-0-75932600-1303509399_thumb.jp

Не пойму где прокол...

Share this post


Link to post
Share on other sites

Вначале файла надо поставить:

#define _STLP_NO_CSTD_FUNCTION_IMPORTS
#define _FM_NO_REMAP[/code]

Share this post


Link to post
Share on other sites

Поставил ,теперь вылезла такая история:

post-1323-0-93935100-1303572618_thumb.jp

А нету этого же проекта в Visual Studio,с ним запар поменьше будет?

Share this post


Link to post
Share on other sites

cos, sin, tan и иже с ними заменяете на cosl, sinl, tanl и т. д.

этого бага не будет.

Кстати, а заголовочники Вы родные, не правленые брали, или правленые с этого форума?

вот заголовочники отдельно:

opencv.rar

ЗЫ: Этого же проекта на VS нету.

Share this post


Link to post
Share on other sites

Заголовочные я с разных проектов пособирал.

Всё сделал как Вы сказали,проект прокомпилировался без ошибок ,но в результате выдал нерабочую форму:

post-1323-0-35075200-1303578183_thumb.jp

Share this post


Link to post
Share on other sites

Возможно камеру не нашел.

Share this post


Link to post
Share on other sites

А возможен вариант переделки программы под статическое изображение.Чтоб просто загружать нужную картинку?

Просто для меня сделать это в Builder туговато,поэтому и спрашивал про VS.

Share this post


Link to post
Share on other sites

Можно.

C и в Африке C.

Share this post


Link to post
Share on other sites

Все статьи лежат тут.

Конкретно про алгоритм скелетизации тут: скелетизация

Про фильтры и свертку

Более развернутое описание будет когда переведу еще кусок документации.

Док. по cvDistTransform сегодня будет там же.

Оставшиеся вопросы можно задать на форуме :) или в комментах к статьям.

Что-то ссылки не открываются

Share this post


Link to post
Share on other sites

Что-то ссылки не открываются

Да файлы отвалились при смене Wiki движка.

Документ по алгоритму Зонга-Суня прикрепил (выше), остальное восстановлю позже файлы уже нашел, из doku-wiki в человеческий вид переведу, и будут тут pdf-ки.

Share this post


Link to post
Share on other sites

Благодарю! Не сразу заметил прикрепленные файлы. Демонстрационный пример супер, не думал, что все настолько просто :)

Share this post


Link to post
Share on other sites

Zhang-Suen algorithm.

http://xa.yimg.com/kq/groups/1986690/749653118/name/skeleton.c

#include <OpenCV/cv.h>

#include <OpenCV/highgui.h>


#define NORTH 1

#define SOUTH 3


void skeletonize(IplImage *src); 


int main (int argc, char * const argv[]) {

	IplImage *image = 0, *srcCopy = 0;

	int w, h, i, j, r, g, b;

	CvScalar pixel, pixOut;


	if(argc != 2) {

		printf("Usage: skeletonize <image_file>\n");

		exit(1);

	}


	image = cvLoadImage(argv[1], CV_LOAD_IMAGE_GRAYSCALE);

	//image = cvLoadImage(argv[1], 1);

	if (!image) {

		printf("Can't find %s\n", argv[1]);

		exit(1);

	}


	w = image->width;

	h = image->height;

	//srcCopy = cvCreateImage(cvGetSize(image), IPL_DEPTH_8U, 3);

	srcCopy = cvCreateImage(cvGetSize(image), IPL_DEPTH_8U, 1);


  for (i = 0; i < h; i++) {

		for (j = 0; j < w; j++) { 

			pixel = cvGet2D(image, i, j);

			b = pixel.val[0];

			if (b > 50)

				pixOut.val[0] = 255;

			else

				pixOut.val[0] = 0;

			cvSet2D(srcCopy, i, j, pixOut);

		}

	}


	skeletonize(srcCopy);


	cvNamedWindow("Original", CV_WINDOW_AUTOSIZE);

  cvMoveWindow("Original", 100, 100);

	cvShowImage("Original", image);


	cvNamedWindow("Skeleton", CV_WINDOW_AUTOSIZE);

  cvMoveWindow("Skeleton", 150, 150);

	cvShowImage("Skeleton", srcCopy);


	cvWaitKey(0);


	// Release images' buffers...

	cvReleaseImage(&image);

	cvReleaseImage(&srcCopy);


	//...and windows

	cvDestroyWindow("Original");

	cvDestroyWindow("Skeleton");


  return 0;

}


// 1-neighbors of pixel.

int nays8(IplImage *im, int r, int c) {

	CvScalar pixel;

	int blue, k = 0, i, j;


  for (i = r-1; i <= r+1; i++) 

		for (j = c-1; j <= c+1; j++) 

			if (i != r || c != j) {

				pixel = cvGet2D(im, i, j);

				blue = pixel.val[0];

				if (blue >= 1)

					k++;

			}


	return k;

}


int connectivity(IplImage *im, int r, int c) {

	int N = 0, b1, b2;

	CvScalar pixel;


	pixel = cvGet2D(im, r, c+1);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r-1, c+1);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0) 

		N++;


	pixel = cvGet2D(im, r-1, c+1);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r-1, c);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	pixel = cvGet2D(im, r-1, c);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r-1, c-1);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	pixel = cvGet2D(im, r-1, c-1);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r, c-1);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	pixel = cvGet2D(im, r, c-1);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r+1, c-1);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	pixel = cvGet2D(im, r+1, c-1);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r+1, c);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	pixel = cvGet2D(im, r+1, c);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r+1, c+1);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	pixel = cvGet2D(im, r+1, c+1);

	b1 = pixel.val[0];

	pixel = cvGet2D(im, r, c+1);

	b2 = pixel.val[0];

	if (b1 >= 1 && b2 == 0)

		N++;


	return N;

}


void deleteCB(IplImage *im, IplImage *tmp) {

	int w, h, blue, i, j;

	CvScalar pixel;


	w = im->width;

	h = im->height;


	for (i = 1; i < h-1; i++)

		for (int j = 1; j < w-1; j++) {

			pixel = cvGet2D(tmp, i, j);

			blue = pixel.val[0];

			if (blue == 1) {

				pixel.val[0] = 0;

				cvSet2D(im, i, j, pixel);

				cvSet2D(tmp, i, j, pixel);

			}

		}

}


void stair(IplImage *im, IplImage *tmp, int dir) {

	int i, j, b1, b2, b3, b4, b5, b6, b7, b8, b9, w, h;

	CvScalar pixel;

	int N, S, E, W, NE, NW, SE, SW, C;


	w = im->width;

	h = im->height;


	if (dir == NORTH)

		for (i = 1; i < h-1; i++)

			for (j = 1; j < w-1; j++) {

				pixel = cvGet2D(im, i-1, j-1);

				b1 = pixel.val[0];

				pixel = cvGet2D(im, i-1, j);

				b2 = pixel.val[0];

				pixel = cvGet2D(im, i-1, j+1);

				b3 = pixel.val[0];

				pixel = cvGet2D(im, i, j-1);

				b4 = pixel.val[0];

				pixel = cvGet2D(im, i, j);

				b5 = pixel.val[0];

				pixel = cvGet2D(im, i, j+1);

				b6 = pixel.val[0];

				pixel = cvGet2D(im, i+1, j-1);

				b7 = pixel.val[0];

				pixel = cvGet2D(im, i+1, j);

				b8 = pixel.val[0];

				pixel = cvGet2D(im, i+1, j+1);

				b9 = pixel.val[0];

				if (b1 == 1)

					NW = 1;

				else

					NW = 0;

				if (b2 == 1)

					N = 1;

				else

					N = 0;

				if (b3 == 1)

					NE = 1;

				else

					NE = 0;

				if (b4 == 1)

					W = 1;

				else

					W = 0;

				if (b5 == 1)

					C = 1;

				else

					C = 0;

				if (b6 == 1)

					E = 1;

				else

					E = 0;

				if (b7 == 1)

					SW = 1;

				else

					SW = 0;

				if (b8 == 1)

					S = 1;

				else

					S = 0;

				if (b9 == 1)

					SE = 1;

				else

					SE = 0;


				if (dir == NORTH) {

					if (C && !(N && ((E && !NE && !SW && (!W || !S)) || 

						 (W && !NW && !SE && (!E || !S))))) {

						pixel.val[0] = 0;

						cvSet2D(tmp, i, j, pixel);

					} else {

						pixel.val[0] = 1;

						cvSet2D(tmp, i, j, pixel);

					}

				} else if (dir == SOUTH) {

					if (C && !(S && ((E && !SE && !NW && (!W || !N)) || 

						 (W && !SW && !NE && (!E || !N))))) {

						pixel.val[0] = 0;

						cvSet2D(tmp, i, j, pixel);

					} else {

						pixel.val[0] = 1;

						cvSet2D(tmp, i, j, pixel);

					}

				}

			}

}


// Zhang-Suen algorithm.

void skeletonize(IplImage *im) {

	int janelaAH[][2] = {

		{1, 0}, {0, -1}, {-1, 0}, {0, 1}

	};

	int janelaH[][2] = {

		{0, -1}, {1, 0}, {0, 1}, {-1, 0}

	};

	int aBlue[6];

	int w, h, i, v, j, k, blue, lin, col, iJanela, again = 1;

	CvScalar pixel, pixOut;	

	IplImage *tmp = 0;


	w = im->width;

	h = im->height;

	tmp = cvCreateImage(cvGetSize(im), IPL_DEPTH_8U, 1);


  for (i = 0; i < h; i++) {

		for (j = 0; j < w; j++) { 

			pixel = cvGet2D(im, i, j);

			blue = pixel.val[0];

			if (blue > 0)

				pixel.val[0] = 0;

			else

				pixel.val[0] = 1;

			cvSet2D(im, i, j, pixel);

			pixOut.val[0] = 0;

			cvSet2D(tmp, i, j, pixOut);

		}

	}


	while (again) {

		again = 0;

  	for (i = 1; i < h-1; i++) 

			for (j = 1; j < w-1; j++) { 

				pixel = cvGet2D(im, i, j);

				blue = pixel.val[0];

				if (blue != 1)

					continue;

				k = nays8(im, i, j);

				iJanela = 0;

				if ((k >= 2 && k <= 6) && connectivity(im, i, j) == 1) {

					for (v = 0; v < 6; v++) {

						col = j + janelaAH[iJanela][0];

						lin = i + janelaAH[iJanela][1];

						pixel = cvGet2D(im, lin, col);

						aBlue[v] = pixel.val[0];

						iJanela++;

						if (v == 2) 

							iJanela = 1;

					}

					if (aBlue[0]*aBlue[1]*aBlue[2] == 0 &&

							aBlue[3]*aBlue[4]*aBlue[5] == 0) {

						pixOut.val[0] = 1;

						cvSet2D(tmp, i, j, pixOut);

						again = 1;

					}

				}		// if ((k >= 2...

			}		// for (j = 1;...


			deleteCB(im, tmp);

			if (!again)

				break;


  	for (i = 1; i < h-1; i++) 

			for (j = 1; j < w-1; j++) { 

				pixel = cvGet2D(im, i, j);

				blue = pixel.val[0];

				if (blue != 1)

					continue;

				k = nays8(im, i, j);

				iJanela = 0;

				if ((k >= 2 && k <= 6) && connectivity(im, i, j) == 1) {

					for (v = 0; v < 6; v++) {

						col = j + janelaH[iJanela][0];

						lin = i + janelaH[iJanela][1];

						pixel = cvGet2D(im, lin, col);

						aBlue[v] = pixel.val[0];

						iJanela++;

						if (v == 2) 

							iJanela = 1;

					}

					if (aBlue[0]*aBlue[1]*aBlue[2] == 0 &&

							aBlue[3]*aBlue[4]*aBlue[5] == 0) {

						pixOut.val[0] = 1;

						cvSet2D(tmp, i, j, pixOut);

						again = 1;

					}

				}		// if ((k >= 2...

			}		// for (j = 1;...


		deleteCB(im, tmp);

	}		// while


	stair(im, tmp, NORTH);

	deleteCB(im, tmp);

	stair(im, tmp, SOUTH);

	deleteCB(im, tmp);


  for (i = 1; i < h-1; i++) 

		for (j = 1; j < w-1; j++) { 

			pixel = cvGet2D(im, i, j);

			blue = pixel.val[0];

			if (blue > 0)

				pixel.val[0] = 0;

			else

				pixel.val[0] = 255;

			cvSet2D(im, i, j, pixel);

		}

}		// End skeletonize

  • Like 1

Share this post


Link to post
Share on other sites

http://felix.abecassis.me/2011/09/opencv-morphological-skeleton/

http://en.wikipedia.org/wiki/Topological_skeleton

http://en.wikipedia.org/wiki/Medial_axis

http://www.ima.ge.cnr.it/ima/smg/research.html

алгоритмы скелетизации

Stentiford Thinning

Zhang Suen Thinning

Medial Axis Transform

Hilditch, Rosenfeld, Zhang-Suen,

and Nagendraprasad -Wang-Gupta Thinning

http://www.rupj.net/portfolio/docs/skeletonization.pdf

Stentiford thinning (F.W.M. Stentiford,R.G.Mortimer,"Some new Heuristics for thinning binary handprinted Characters for OCR",IEE Trans.on Sys,Man & Cybernetics,1983)

Holt's Staircase removal (C.M.Holt,et.al,"An Improved parallel Thinning Algorithm",ACM,1987).

Share this post


Link to post
Share on other sites

Была идея написать такой алгоритм, когда распознавание текста писал. Оказывается такое уже есть в большом количестве)

Сейчас вот думаю... Если у букв выделить скелет, а потом распознать с помощью Hu моментов, то поидее должно быть очень неплохо.

З.ы. В проге из второго поста есть небольшой баг - при нажатии на "<->" пиксели, лежащие на нижней границе первого изображения, не затираются.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×