Однопикселизирование(скелетизация) монохромного изображения

[Halloween 0]

Есть монохромное изображение с линиями,но линии нечёткие.Пытаюсь однопикселизировать изображение так,чтобы потери были минимальные и остался только контур.

Например,изображение:

test.bmp

Нужно убрать нечеткости такого рода:

3.bmp

dilate.bmp

Кто сталкивался с подобной проблемой,буду рад за информацию.

[Smorodov 579]

Есть тут:

http://www.compvision.ru/forum/index.php?showtopic=30

[Halloween 0]

Это немного не то,мне нужна скорее именно однопикселизация,а не скелетизация!

[mrgloom 242]

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

я думаю только морфологией тут не обойтись. думаю тут надо присмотрется к сплайнам.

http://www.gamedev.ru/code/forum/?id=124256

[Nuzhny 243]

Посмотри довольно тупую мою реализацию для твоего изображения:

#include <list>

#include <limits>


#include <highgui.h>

#include <cv.h>

////////////////////////////////////////////////////////////////////////////


int main()

{

	IplImage* img = cvLoadImage("f:\\test.bmp", 0);


	IplImage* img2 = cvCloneImage(img);


	cvShowImage("original", img2);


	// Немного доработаем исходное изображение для удобного писка контуров

	cvSubRS(img, cvScalar(255), img);

	cvDilate(img, img, 0, 1);

	cvErode(img, img, 0, 1);


	cvShowImage("img", img);


	// Ищем контуры

	CvMemStorage *storage = cvCreateMemStorage(0);

	CvContourScanner traverse = cvStartFindContours(img, storage, sizeof(CvContour), CV_RETR_LIST, CV_CHAIN_APPROX_NONE);


	// Контейнер для концевых точек

	std::list<CvPoint> points;


	size_t ccounter = 0;

	for (CvSeq* contour = cvFindNextContour(traverse); contour; contour = cvFindNextContour(traverse))

	{

		// Совершено тупой и нерациональный поиск концевых точек

		size_t min1 = std::numeric_limits<size_t>::max();

		size_t min2 = std::numeric_limits<size_t>::max();

		CvPoint min_p1 = cvPoint(0, 0);

		CvPoint min_p2 = cvPoint(500, 500);


		for (int i = 0; i < contour->total; ++i)

		{

			CvPoint p1 = *(CvPoint*)cvGetSeqElem(contour, i);


			size_t near_count = 0;

			for (int j = 0; j < contour->total; ++j)

			{

				if (i != j)

				{

					CvPoint p2 = *(CvPoint*)cvGetSeqElem(contour, j);

					if (abs(p1.x - p2.x) < 5 && abs(p1.y - p2.y) < 5)

						++near_count;

				}

			}


			if ((near_count < min1) && (abs(p1.x - min_p2.x) > 10 || abs(p1.y - min_p2.y) > 10))

			{

				min1 = near_count;

				min_p1 = p1;

			}

			else if ((near_count < min2) && (abs(min_p1.x - p1.x) > 10 || abs(min_p1.y - p1.y) > 10))

			{

				min2 = near_count;

				min_p2 = p1;

			}

		}


		points.push_back(min_p1);

		points.push_back(min_p2);


		printf("%u\n", ++ccounter);

	}


	cvEndFindContours(&traverse);

	cvReleaseMemStorage(&storage);


	// Соединяем ближайшие концевые точки прямыми

	for (std::list<CvPoint>::iterator it1 = points.begin(); it1 != points.end(); it1 = points.erase(it1))

	{

		double min_dist = std::numeric_limits<double>::max();


		std::list<CvPoint>::iterator it2 = it1;

		std::list<CvPoint>::iterator best_it = it1;

		++best_it;

		for (++it2; it2 != points.end(); ++it2)

		{

			double dist = sqrt((double)((it1->x - it2->x) * (it1->x - it2->x) + (it1->y - it2->y) * (it1->y - it2->y)));

			if (dist < min_dist)

			{

				min_dist = dist;

				best_it = it2;

			}

		}


		cvLine(img2, *it1, *best_it, cvScalar(0));

		points.erase(best_it);

	}


	cvShowImage("result", img2);


	cvWaitKey();


	cvReleaseImage(&img2);

	cvReleaseImage(&img);

	cvDestroyAllWindows();


	return 0;

}

////////////////////////////////////////////////////////////////////////////

Сравни картинки original и result. Это то, что тебе надо?

[Halloween 0]

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

я думаю только морфологией тут не обойтись. думаю тут надо присмотрется к сплайнам.

http://www.gamedev.ru/code/forum/?id=124256

Мне скорее надо убрать лишние помехи (шумы) с линий!Просто если я сделаю кривую гладкой,то я не решу свою задачу ,потому что будут большие потери.А разрывность я устраняю другим методом.

[Halloween 0]

Посмотри довольно тупую мою реализацию для твоего изображения:

#include <list>

#include <limits>


#include <highgui.h>

#include <cv.h>

////////////////////////////////////////////////////////////////////////////


int main()

{

	IplImage* img = cvLoadImage("f:\\test.bmp", 0);


	IplImage* img2 = cvCloneImage(img);


	cvShowImage("original", img2);


	// Немного доработаем исходное изображение для удобного писка контуров

	cvSubRS(img, cvScalar(255), img);

	cvDilate(img, img, 0, 1);

	cvErode(img, img, 0, 1);


	cvShowImage("img", img);


	// Ищем контуры

	CvMemStorage *storage = cvCreateMemStorage(0);

	CvContourScanner traverse = cvStartFindContours(img, storage, sizeof(CvContour), CV_RETR_LIST, CV_CHAIN_APPROX_NONE);


	// Контейнер для концевых точек

	std::list<CvPoint> points;


	size_t ccounter = 0;

	for (CvSeq* contour = cvFindNextContour(traverse); contour; contour = cvFindNextContour(traverse))

	{

		// Совершено тупой и нерациональный поиск концевых точек

		size_t min1 = std::numeric_limits<size_t>::max();

		size_t min2 = std::numeric_limits<size_t>::max();

		CvPoint min_p1 = cvPoint(0, 0);

		CvPoint min_p2 = cvPoint(500, 500);


		for (int i = 0; i < contour->total; ++i)

		{

			CvPoint p1 = *(CvPoint*)cvGetSeqElem(contour, i);


			size_t near_count = 0;

			for (int j = 0; j < contour->total; ++j)

			{

				if (i != j)

				{

					CvPoint p2 = *(CvPoint*)cvGetSeqElem(contour, j);

					if (abs(p1.x - p2.x) < 5 && abs(p1.y - p2.y) < 5)

						++near_count;

				}

			}


			if ((near_count < min1) && (abs(p1.x - min_p2.x) > 10 || abs(p1.y - min_p2.y) > 10))

			{

				min1 = near_count;

				min_p1 = p1;

			}

			else if ((near_count < min2) && (abs(min_p1.x - p1.x) > 10 || abs(min_p1.y - p1.y) > 10))

			{

				min2 = near_count;

				min_p2 = p1;

			}

		}


		points.push_back(min_p1);

		points.push_back(min_p2);


		printf("%u\n", ++ccounter);

	}


	cvEndFindContours(&traverse);

	cvReleaseMemStorage(&storage);


	// Соединяем ближайшие концевые точки прямыми

	for (std::list<CvPoint>::iterator it1 = points.begin(); it1 != points.end(); it1 = points.erase(it1))

	{

		double min_dist = std::numeric_limits<double>::max();


		std::list<CvPoint>::iterator it2 = it1;

		std::list<CvPoint>::iterator best_it = it1;

		++best_it;

		for (++it2; it2 != points.end(); ++it2)

		{

			double dist = sqrt((double)((it1->x - it2->x) * (it1->x - it2->x) + (it1->y - it2->y) * (it1->y - it2->y)));

			if (dist < min_dist)

			{

				min_dist = dist;

				best_it = it2;

			}

		}


		cvLine(img2, *it1, *best_it, cvScalar(0));

		points.erase(best_it);

	}


	cvShowImage("result", img2);


	cvWaitKey();


	cvReleaseImage(&img2);

	cvReleaseImage(&img);

	cvDestroyAllWindows();


	return 0;

}

////////////////////////////////////////////////////////////////////////////

Сравни картинки original и result. Это то, что тебе надо?

Практически то,но маленькие разрывы всё-равно остались.Посмотрите как я реализовал свою задачу,воспользовавшись тем,что вы предложили ранее:

dist.cpp

Решение действенно,но для него нужно давать четкое изображение без шумов и утолщений,иначе будут баги.

Есть идея почистить изображение с помощью дифференцирования.Поясню алгоритм:

1.Двигаться по горизонтали,пока не найдется точка.

2.Если точка нашлась-двигаться при координате Х этой точки только уже по-вертикали(по Y):

-если точка не нашлась-оставляем найденную и двигаемся дальше;

-если нашлась,то накладываем точку ,найденную по-вертикали на точку,найденную по-горизонтали(логическое ИЛИ).Таким образом получаем нужную нам точку,а остальные отбрасываем.

3.Двигаемся дальше.

Алгоритм вроде оптимальный,но никак не дойду мыслями,как его красиво реализовать в VS.

[mrgloom 242]

связность какая должна быть? 4-х или 8-ми?

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

наверно можно как то пройтись по точкам и смотреть их связность и помечать/удалять лишние, но например какие лучше удалять внутри контура или снаружи, или без разницы?

+ алгоритмы не учитывают маленькие циклы.(если они появятся)

[Halloween 0]

связность какая должна быть? 4-х или 8-ми?

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

наверно можно как то пройтись по точкам и смотреть их связность и помечать/удалять лишние, но например какие лучше удалять внутри контура или снаружи, или без разницы?

+ алгоритмы не учитывают маленькие циклы.(если они появятся)

Желательно 8-ми связные.

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

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

[Halloween 0]

Доработал свою программу.Результатом удовлетворен на все 100!

Особая благодарность Nuzhny,направил на путь истины!Большущее спасибо