CPU üzerinde Connected Component Labelling

Önceki CUDA ile OpenCV kullanarak Webcam Görüntü İşleme 
başlıklı yazımızda bahsedilen projeye ekleme bir filtre olarak gerçekleştirilen Connected Component Labeling (Birleşik Eleman Etiketleme) filtresini OpenCV ile webcam görüntü işlemede nasıl kullandığımıza bakalım.

NOT: Bu yazıdaki kod örnekleri kısaltılarak verilmiştir. Kod belgeleri için Doxygen ile yaratılmış olan mikrositeyi inceleyebilirsiniz (yazıdaki eklemeleri içerecek şekilde güncellenmiştir).

NOT: Her tür fikir, öneri ve eleştirinizi yorumlara yazabilirsiniz, teşekkür ederiz.

İçindekiler

  • Gerekenler
  • CCL Nedir?
  • CCL için Önişleme
  • CPU CCL Filtresi: CpuCCLFilter
  • Filtre Örnekleri
  • İndirmeler

Gerekenler

  • VS 2010 ve C/C++ Bilgisi
  • OpenCV ile görüntü yakalama aşinalığı. Windows için OpenCV 2.2’yi patchlemeyi unutmayın! Önceki yazımızı inceleyebilirsiniz.
  • VS2010 ile CUDA projesi yaratabilmek. Önceki yazımızı inceleyebilirsiniz.
  • CUDA içeren kodları çalıştırabilmek için CUDA destekli bir ekran kartı.
  • Derleyici includeları, libraryleri ve hataları ile uğraşmak için bolca sabır.
  • Önceki yazımızda detayları bulabilirsiniz: CUDA ile OpenCV kullanarak Webcam Görüntü İşleme

CCL Nedir?

Connected Components Labeling, görüntüde birleşik olan nesneleri etiketleyerek birbirinden ayırdedebilecek hale getiren algoritmaya verilen addır. Burada en önemli tanım, “görüntüde birleşik” tamlamasıdır. Bu filtredeki kodlar, wikipediadaki CCL açıklamasından yola çıkılarak yazılmıştır.

Görüntünün birleşik olması, komşu piksellerin renklerinin aynı veya belli bir derecede yakın olması ile ölçülür. Komşulukları gözönüne alırken 4-komşu ve 8-komşu modelleri kullanılabilir. 4-komşu modeli, ana yönler olan kuzey, güney, doğu ve batı komşularıdır. 8-komşu modelinde ara yönlerdeki komşular da hesaba katılır.

4-komşuluk

8-komşuluk

CCL için Önişleme

Renk Benzerliği

Renk benzerliği, CCL filtremizde birbiri ile aynı olarak nitelendirilecek renkleri ayırdetmemize yarar. Basit olarak gri skala uzayında uzaklığı 10’dan küçük olan renkler aynı sayıldı. Standart bir webcamin yakaladığı görüntülerde (en azından benimkinde) RGB noise denilen her renkten gürültü vardır. Webcam sabit bir yere bakarken ve görüntüde hiç hareket yokken bile yakalanan resmin pikselleri kısıtlı bir aralıkta sürekli değişir. Renklerin aynı olmasını katı bir şekilde gerektirmeyerek saptanan etiket sayısını düşürüyoruz, bir bakıma bu gürültüye bağışıklık kazanıyoruz.

Thresholding

Thresholding, belli bir aralığa sahip değeri, iki adet değere indirgemenin bir yoludur. Örneğin değerimiz 0 ile 255 arasında ise, threshold değerimiz 90 ise, 90’dan küçük değerler 0, büyük ve eşit değerler 1 grubuna denk gelir. CCL, threshold işlemi görmüş görüntü üzerinde çalışır. CCL algoritması için 0 arkaplan, 1 nesne demektir.

CPU CCL Filtresi: CpuCCLFilter

ISingleImageFilter arayüzünü kullanarak yazılan filtrede en önemli metod olan findConnectedComponents kısaca anlatılarak gösterilmiştir.

/**
	\ref ptKernelLauncher tipinde metod.

	\param width Görüntünün piksel olarak genişliği
	\param height Görüntünün piksel olarak yüksekliği
	\param rowStride Görüntünün hafızadaki byte olarak genişliği.
	\param imageData Görüntü verisi.
	\param outImageData Etiket görüntü verisi.
	\param outLabelBitmap Etiket integer bitmap.

	Görüntüdeki birleşmiş birimleri bulur. Connected Component Labeler.
*/
template<bool eightConnected>
void CpuCCLFilter::findConnectedComponents(int width, int height, int rowStride, char* imageData, char* outImageData, int* outLabelBitmap)
{
	// label bitmap	

	// disjoint set için tip ve map tanımları.
	typedef std::map<short, std::size_t> rank_t; // element order.
	typedef std::map<short, short> parent_t;

	rank_t rank_map;
	parent_t parent_map;

	boost::associative_property_map<rank_t>   rank_pmap( rank_map );
	boost::associative_property_map<parent_t> parent_pmap( parent_map );

	// disjoint sets yaratılır.
	boost::disjoint_sets<boost::associative_property_map<rank_t>, boost::associative_property_map<parent_t>> 
		ds( rank_pmap, parent_pmap );

	boost::unordered_set<short> elements;

	short labelNumber = 0;

	for(int i = 0; i < height; i++)
	{
		for(int j = 0; j < width; j++)
		{
			outLabelBitmap[i*rowStride + j] = 0;
		}
	}

	// tüm pikseller gezilir
	for(int i = 0; i < height; i++)
	{
		for(int j = 0; j < width; j++)
		{
			// if pixel is not background.
			if( imageData[i*rowStride + j] != 0 )
			{
				if(j > 0 & i > 0 &
					isSameColor( imageData[i*rowStride + j - 1], imageData[(i - 1)*rowStride + j]) // same value
					& isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] )
				)
				{
					// west ve north aynı
					ds.union_set( outLabelBitmap[i*rowStride + j - 1], outLabelBitmap[(i - 1)*rowStride + j] );
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[i*rowStride + j - 1];
				}

				if(j==0 & i > 0 & isSameColor( imageData[i*rowStride + j], imageData[(i - 1)*rowStride + j] ))
				{
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[(i-1)*rowStride + j];
				}

				// West pixel
				if(j > 0 & isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] ))
				{
					// west pixel ile aynı label.
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[i*rowStride + j - 1];
				}

				// west farklı north aynı.
				if(
					(j > 0 & !isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] )) // west different value
					& (i > 0 & isSameColor( imageData[(i-1)*rowStride + j], imageData[i*rowStride + j] )) // north same value					
				)
				{
					// north ile aynı
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[(i-1)*rowStride + j];					
				}

				// west ve north farklı
				if(   ((j > 0 &;amp;& !isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] )) || j == 0) // west different value
					& ((i > 0 & !isSameColor( imageData[(i-1)*rowStride + j], imageData[i*rowStride + j] )) || i == 0) // north different value					
				)
				{
					labelNumber++;
					ds.make_set(labelNumber);
					elements.insert(labelNumber);
					outLabelBitmap[i*rowStride + j] = labelNumber;
				}

				// northeast ve northwest kontrol edilir. (çaprazlar).
				if(eightConnected)
				{
					// northwest
					if(j > 0 & i > 0
						& isSameColor( imageData[(i-1)*rowStride + j - 1], imageData[i*rowStride + j] )
					)
					{
						// northwest ile aynı
						ds.union_set( outLabelBitmap[(i-1)*rowStride + j - 1], outLabelBitmap[i*rowStride + j] );
					}

					// northeast
					if(j+1 < width & i > 0
						& isSameColor( imageData[(i-1)*rowStride + j + 1], imageData[i*rowStride + j] )
					)
					{
						// northeast ile aynı
						ds.union_set( outLabelBitmap[(i-1)*rowStride + j + 1], outLabelBitmap[i*rowStride + j] );
					}
				}
			}
		}
	}

	int cnt = ds.count_sets(elements.begin(), elements.end());

	printf("Component count: %i\n", cnt);

	// second pass - label output image and colorize.
	for(int i = 0; i < height; i++)
	{
		for(int j = 0; j < width; j++)
		{
			int labelNo = ds.find_set( outLabelBitmap[i*rowStride + j] ); // pikselin etiketi bulunur.
			int R =0, G=0, B=0;

			// etiketler renklendirilir.
			hsl_to_rgb( 1.0f * labelNo / labelNumber, .8f + .2f * labelNo / labelNumber, .75f, &R, &G, &B );

			int idx = i * rowStride + j;

			outImageData[idx * 3 + 0] = (char)(B);
			outImageData[idx * 3 + 1] = (char)(G);
			outImageData[idx * 3 + 2] = (char)(R);
		}
	}	
}

 

Filtre Örnekleri

CpuCCLFilter:

İndirmeler

Dosyalar 7-zip ile sıkıştırılmıştır.