Ordered connected components

9 Ansichten (letzte 30 Tage)
Dustin
Dustin am 6 Aug. 2011
Beantwortet: kevin am 30 Mär. 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 Kommentare
Image Analyst
Image Analyst am 7 Aug. 2011
Dustin: Can you take a step back and tell us why you think that you need an ordered list of which pixels are contained in the object? I have used the pixels in the object before but it was never needed that they be in some special or known order - I was able to do what I want to do without regard to that. What are you really trying to do?
Dustin
Dustin am 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.

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Dustin
Dustin am 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 Kommentare
Image Analyst
Image Analyst am 12 Aug. 2011
So you're making a one-way trip from one end to the other? I still don't see why this can't be done with bwboundaries with 4-connectivity, once you know the termination points.
Dustin
Dustin am 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 :)

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (3)

Wolfgang Schwanghart
Wolfgang Schwanghart am 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 Kommentare
Dustin
Dustin am 7 Aug. 2011
I would prefer the first one (as it includes all the pixels), but the other two are also acceptable.
Image Analyst
Image Analyst am 7 Aug. 2011
Then just use bwboundaries with 4-connectivity and that's what you'll get.

Melden Sie sich an, um zu kommentieren.


Sean de Wolski
Sean de Wolski am 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 Kommentar
Dustin
Dustin am 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.

Melden Sie sich an, um zu kommentieren.


kevin
kevin am 30 Mär. 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