Ordered connected components

8 次查看（过去 30 天）
Dustin
Dustin 2011-8-6
回答： kevin 2014-3-30
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 个评论
显示 3更早的评论
Image Analyst
Image Analyst 2011-8-7
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 2011-8-12
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Dustin
Dustin 2011-8-9
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 个评论
Image Analyst
Image Analyst 2011-8-12
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 2011-8-13
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 :)

请先登录，再进行评论。

更多回答（3 个）

Wolfgang Schwanghart
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 个评论
显示 2更早的评论
Dustin
Dustin 2011-8-7
I would prefer the first one (as it includes all the pixels), but the other two are also acceptable.
Image Analyst
Image Analyst 2011-8-7
Then just use bwboundaries with 4-connectivity and that's what you'll get.

请先登录，再进行评论。

Sean de Wolski
Sean de Wolski 2011-8-7
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 个评论
Dustin
Dustin 2011-8-9
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.

请先登录，再进行评论。

kevin
kevin 2014-3-30
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.

类别

在 Help Center 和 File Exchange 中查找有关 Images 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by