Ordered connected components

17 views (last 30 days)
Dustin
Dustin on 6 Aug 2011
Answered: kevin on 30 Mar 2014
For connected components found by using bwconncomp(), the PixelIdxList is ordered according to columns and then rows. Is there a way to obtain the list of the pixels in the order in which they are connected?
My connected components are edges. I have tried bwtraceboundary(), but it yields a circular path along the edge, with most pixels except the start and end points being repeated. Besides, some intermediate pixels occur only once due to the order in which the connected pixels are searched for.
So, is there a better way to obtain a list of component pixels in connected order?
  5 Comments
Dustin
Dustin on 12 Aug 2011
I have extracted binary edges from an image. I need to compare intensities and gradients of adjacent edge pixels, which is why I need to know the order in which they lie.
This was the way I thought of doing things, and it seems like an interesting problem on its own to me. Nevertheless, if there is a better way to do this, I would be glad if you could advise me.

Sign in to comment.

Accepted Answer

Dustin
Dustin on 9 Aug 2011
I came up with a solution that just works. It isn't pretty or efficient, but it does work.
In all cases, I know that my edges have two termination points. This means that there are no circles, forks or branches.
Then, I first find the endpoints of each component using the 'endpoints' option in bwmorph().
Picking one endpoint, I check the 8 neighboring pixels in the order N,E,S,W,NE,SE,SW,NW (to ensure 4-connected pixels are given priority), set the current pixel to 0 and repeat it for the pixel I found among the neighbors. This continues until the other endpoint is reached.
By saving the coordinates of each pixel as it is set to 0, I have a list of connected pixels.
  2 Comments
Dustin
Dustin on 13 Aug 2011
Yes, you have it right. I am making a trip from one termination point to the other. There are two main reasons bwboundaries with 4-connectivity doesn't work for me.
1) I prefer 4-connectivity over 8-connectivity, but I still want to preserve 8-connectivity.
2) This one is the critical reason. bwboundaries() has no option to pick a starting point, so it isn't necessarily the termination point from where the trip will start. In this case, as I have explained in the comments to the original question, I end up with a list of points from an intermediate point to a termination point and back, and then another loop to the other termination point.
Nevertheless, I think I can improve this by finding the termination points, and then applying bwtraceboundary() which has an option for the initial point. Of course, I may end up losing a few points if I use 8-connectivity, but it is no big issue.
Thanks for getting me thinking :)

Sign in to comment.

More Answers (3)

Wolfgang Schwanghart
Wolfgang Schwanghart on 6 Aug 2011
Hi Dustin,
I don't have MATLAB at hand right now, so I cannot try, but I think bwboundaries should solve your problem.
[B,L,N,A] = bwboundaries(BW,8,'noholes')
The adjacency matrix should contain the information you need.
Cheers, Wolfgang
  4 Comments
Image Analyst
Image Analyst on 7 Aug 2011
Then just use bwboundaries with 4-connectivity and that's what you'll get.

Sign in to comment.


Sean de Wolski
Sean de Wolski on 7 Aug 2011
Use regionprops on the CC struct with the 'PixelList' option. That will return row/columns. Then use sortrows on that to find the order, keep the linear index and apply it:
I = logical([0 0 0 1 0 0 0 0 1 0;...
0 0 1 0 0 0 0 0 1 0;...
0 0 1 0 0 0 0 0 0 1;...
0 1 0 0 0 0 0 0 1 0;...
1 0 0 0 0 0 0 1 1 0;...
0 0 0 0 0 0 1 1 0 0]);
CC = bwconncomp(I); %cc struct
rp = regionprops(CC,'pixellist'); %subindexes
the_order = cell(1,CC.NumObjects); %preallocate
for ii = 1:CC.NumObjects
[junk the_order{ii}] = sortrows(rp(ii).PixelList,[1 -2]); %sort, only keep the order to extract
end
CCnew = CC; %copy
CCnew.PixelIdxList = cellfun(@(old,idx)old(idx),CC.PixelIdxList,the_order,'uni',false); %set copy to modified order
To view and check against your provided example:
CCnew.PixelIdxList{:} %woo!
  1 Comment
Dustin
Dustin on 9 Aug 2011
Thanks for the effort Sean. Your solution works on the example.
Unfortunately, it does not generalize well to other cases. For example, the left component is essentially going in the south-west to north-east direction. However, if it is going from the north-west to south-east direction, then the [1 -2] in sortrows() causes problems. I think hard-coding the sort order will affect some other cases too. Of course, I could calculate the slope of the component, and then use a switch-case to select the correct sort order.

Sign in to comment.


kevin
kevin on 30 Mar 2014
The bwdistgeodesic function can help you with the 'cityblock' or ' quasi-euclidean ' method :
For example, if you choose the first edge point(x1,y1) and you compute bwdistgeodesic(bw,y1,x1,'cityblock'), you will get a distance matrix whose values will be in the range [0 : number of connected components -1]. At the location (x1,y1) of your first point , the distance matrix value will be 0, those of the next pixel will be 1, the next 2 , etc... The order gives priority to 4-connectivity, I think it is that you want. Then you just have to sort the values to get your ordered list.
An example :
selected = bwselect(bw,y1,x1);
mat_dist = bwdistgeodesic(selected,y1,x1,'cityblock'); %'quasi-euclidean' for 8-connectivity
comp = find(selected);
comp(:,2) = mat_dist(comp(:,1));
ordered_list_ind = sortrows(comp,2);
[ordered_list_sub(:,1) ordered_list_sub(:,2)] = ind2sub(size(selected),ordered_list_ind(:,1));
Remarks : The 'cityblock' method works only for 4-connectivity. If you need this for 8-connectivity, replace the 'cityblock' method by the 'quasi-euclidean' one, sorting the values will allow the same result for 8-c.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by