/*?Copyright?（c）?2001?C.?Grigorescu?*/

#include?
#include?
#include?“ByteImage.h“
#include?“IntImage.h“
#include?“ConnectedComponents.h“

int?ConnectedComponents（IntImage?&img?CONN_TYPE?connectivity?IntImage?&out）
{
??out?=?img;
??int?nr_comp?=?ConnectedComponents（out?connectivity）;
??return?（nr_comp）;
}

int?ConnectedComponents（ByteImage?&img?CONN_TYPE?connectivity?IntImage?&out）
{
??out.makeImage（img.getWidth（）?img.getHeight（））;
??for?（int?i=0;i????for?（int?j=0;j??????out[i][j]?=?img[i][j];
??int?nr_comp?=?ConnectedComponents（out?connectivity）;
??return?（nr_comp）;?????????????????????????????????????????????????????????????
}

int?ConnectedComponents（IntImage?&img?CONN_TYPE?connectivity?=?FOUR）
{
??/*?
??Computes?“Connected?Components“?using?Tarjan‘s?Union-Find?algorithm;
??the?result?is?returned?in?the?same?buffer?as?gray_level?image?with?values
??equal?to?the?label?of?the?component.

??Returns:?the?number?of?connected?components?*/

??int?l?p?r?curlab=1;
??int?i?j?n_up?n_left?n_right;
??int?lab[img.getSize（）];
??int?*pixels?=?img.getPixels（）;

??/*?Start?Tarjan‘s?algorithm?*/
??int?w?=?img.getWidth（）;
??int?h?=?img.getHeight（）;

??for?（i=0;?i????for?（j=0;?j??????if?（pixels[i*w+j]?>=?0）?{
??????p?=?pixels[i*w+j];
??????l?=?i*w+j;
??????lab[l]?=?l;
??????
??????n_up?=?i-1;
??????if?（（n_up?>=?0）?&&?（pixels[n_up*w+j]?==?p））
	Union（l?n_up*w+j?lab）;
??????
??????n_left?=?j-1;
??????if?（（n_left?>=?0）?&&?（pixels[i*w+n_left]?==?p））
	Union（l?i*w+n_left?lab）;
??????
??????n_right?=?j+1;
??????if?（connectivity?==?EIGHT）?{
	if?（（n_right?=?0）?&&?
	????（pixels[n_up*w+n_right]?==?p））
	??Union（l?n_up*w+n_right?lab）;
	if?（（n_left?>=?0）?&&?（n_up?>=?0）?&&?
	????（pixels[n_up*w+n_left]?==?p））
	??Union（l?n_up*w+n_left?lab）;
??????}
????}??????
??????else
	lab[i*w+j]?=?0;
????}
??for?（i=0;?i????for?（j=0;?j??????r?=?lab[i*w+j];
??????if?（r?==?i*w+j）?{
	pixels[i*w+j]?=?curlab;
	lab[i*w+j]?=?curlab++;
??????}?else?{?
	lab[i*w+j]?=?lab[r];
	pixels[i*w+j]?=?lab[r];
??????}
????}
??return?（curlab-1）;
}

int?Root（int?r?int?*lab?int?size_x?int?size_y）
{
??int?p;

??p?=?lab[（r/size_x）*size_x+（r%size_x）];
??while?（p?!=?r）?{
????r?=?p;
????p?=?lab[（r/size_x）*size_x+（r%size_x）];
??}
??return?p;
}
?
int?FindRoot（int?r?int?*lab）
{
??if?（?r?!=?lab[r]?）
????lab[r]?=?FindRoot（lab[r]?lab）;
??return?lab[r];
}

void?Union（int?x?int?y?int?*lab）
{
??int?r0?r1;
??r0?=?FindRoot（x?lab）;
??r1?=?FindRoot（y?lab）;
??if?（r0?>?r1）??
????lab[r0]?=?r1;
??else?
????lab[r1]?=?r0;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2508??2001-08-08?23:53??ConnectedComponents.h

?????文件????????679??2004-03-25?09:35??EightConnectedSE.hpp

?????文件????????671??2004-03-25?09:35??FourConnectedSE.hpp

?????文件???????2619??2001-07-17?19:15??ConnectedComponents.cpp

?????文件????????886??2004-03-25?09:35??EightConnectedSE.cpp

?????文件????????755??2004-03-25?09:35??FourConnectedSE.cpp

-----------?---------??----------?-----??----

?????????????????8118????????????????????6