Anyone know the algorithum of bwconncomp/bwlabel ?/Coding problem

I have wrote my own code. However, too many bugs there.

    number=0;
    abc=[];
    abcd=[];
    N=300;
    k=1;
    q=1;
    l=q+1;
    v=1:272;
    constant=1;
    control=[0];
    testvalue=[0];
    Structure(N).result=zeros(15);
    Cell=im2bw(imread('Ims.png')); % convert input image into binary image
    [R C]=size(Cell);
    temp1=[];
     num=0;
     result=[];
     counter=1;
____________________________________________________________
    for i= 1:R
        for j=1:C
    Cell(j,i);
    if (find(Cell(j,i))==1)  % find all the white pixel on image
        temp=[i j];
        temp1=cat(2,temp1,temp); % store all the white pixel coordinate into array
         num=num+1;
    end
        end
    end
__________________________________________________________________________________
    a=temp1(counter); % convert coordinate back to (m,n) format
    b=temp1(counter+1);% convert coordinate back to (m,n) format

    while (counter<=(size(temp1,2)-2))
    j=(a-1)*300+b;
    result=cat(2,result,j);
    c=temp1(counter+2);  %Next a coordinate
    d=temp1(counter+3);  % Next b coordinate
    x=((c-a)^2+(d-b)^2)^(1/2); % test the next (a,b) which is connected to current (a,b)

    if (x <= (2)^(1/2))  % if it is connected, go on to store coordinate into result

    else
            temp00=[];

            temp00=result;

            Structure(k).result=temp00; % store a set connected pixel coordinate into Structure

            k=k+1;
            result=[];
            number=number+1;
        end 
    counter=counter+2;  
    a=temp1(counter);  % Next a 
    b=temp1(counter+1); % Next b
    end
__________________________________________________________________________

*Not complete code* 
while (l<=number)
      tempcon=(abs(bsxfun(@minus,Structure(q).result',Structure(l).result))); %do subtraction on each cell array

        ans=(tempcon==300)|(tempcon==299)|(tempcon==301); % find the value to check that they are connect region

        Tr=find(ans==1);
    if (Tr~=0) %if it is connected, store all arrays into new array and use the new array to do the subtraction

        Structure(q).result=struct('object',[Structure(q).result Structure(l).result]); 
        Structure(q).result=Structure(q).result.object;
        Structure(l).result=[];
        control=[control,q,l]; % record all the q,l coordinate of connected region.

    end
           end

           if (l==number) % when l is last cell array inside structure
               v=setdiff(v,control); % find non repeated number 

           else
                 l=l+1;
           end
    end

      end

I am quite new to programming. So the last part I want to do is that use Structure(1) to minus other Structure(i) to find those value which == 299|300|301 If it is , combine Structure(1)+Structure(i) and so on doing the subtraction.

If i ==the last cell array, store current structure into new structure. and exclude the combined Structure number(this)EG (1,2,4) and do the subtraction from (2,3,5 and so forth). The last part of my code is not completed. Cause I don't know how to write it. I tried serval times, It can't work well. Any ideas?

I don't know this algorithm is good way to find the connected object and its size or not.

If not, Anyone could tell me another method?

My code is very rough and messing. Sorry about that

Thanks

Answer 1

[Ahmet Cecen]

In a BW image, I would first find the boundaries, using shifts. Then do systematic marching along the boundaries, as in, start from any unmarched pixel, then march along the boundary until you come back to that pixel. Once you have a full loop, color that loop then repeat.

[tabw]

What Shifts?

Could you be more specific?

I am quite new to matlab.

[Ahmet Cecen]

Lets assume we are using a connectivity of 4. (First neighbors)

 checkx=(BW-circshift(BW,[0 -1]));
 leftboundary=1+find(checkx==-1);
 rightboundary=find(checkx==1);

Do the y direction or higher connectivity in a similar fashion. Then you would do:

 Boundary=zeros(size(BW));
 Boundary(leftboundary)=1;
 Boundary(rightboundary)=1;

And so on. That gives you your boundary image. Now you march across the boundaries using a while loop.

[tabw]

How to count the pixel inside the boundary?

You are saying you can start marching from the boundaries point to another boundaries point ?

[Ahmet Cecen]

Boundaries are 1 everywhere else is 0.

 i=2
 While nnz(Boundary)>0
   select any pixel that is 1
   paint it "i"
   if there is a pixel in nearest neighbors that is also 1 
       move over to that pixel and paint it "i"
   if not
       i=i+1;
   end
 end

Something like the above. It is not that trivial to write, I don't have the time to write the whole thing for you, but if you make some progress, I can look over/improve the code. The problem is, unless you write this in C and mex it, it will be considerably slower due to loops being involved. I am not aware of a better way to do this, but that doesn't mean there isn't a better way.

Answer 2

[Image Analyst]

For bwlabeln they give this reference:

Sedgewick, Robert, Algorithms in C, 3rd Ed., Addison-Wesley, 1998, pp. 11-20.

Not sure but it might be the same for bwconncomp, though I know bwconncomp is supposed to be a faster implementation of bwlabeln.