findConnectedComponents.cpp

/**
	\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);
		}
	}	
}