Ordered connected components

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?

[Dustin]

I just realized that this may not be the best way to put this. By "a circular path", I mean that it starts at the initial point (which is rarely one of the termination points), goes to one termination point and then heads back along the edge to the other termination point, before coming back to the initial point.

T1-------IP-------T2

For an edge like that, it goes IP->T2->IP->T1->IP

[Sean de Wolski]

Can you provide us with a picture and the few lines of code. What about post sorting the PixelIdxList? What about labelling the image and then calling bwconncomp (or my label2CC on the FEX) which will keep the order of the labels?

[Dustin]

Hi Sean,

Here's a sample matrix I would like to work with.

a = [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]

Now, if I apply bwconncomp() to this, I get two components, but the pixels for each component listed in column order. What I need is for the pixels to be arranged in their adjacent order.

For instance, for the bigger component above, the PixelIdxList is:

[42 47 48 49 50 52 53 57]'

whereas I need it to be in the adjacency order:

[42 48 47 53 52 57 50 49]'

I don't think labelling would help as the pixel order is still not provided by bwconncomp.

[Image Analyst]

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]

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.

Answer 1

[Dustin]

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.

[Image Analyst]

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]

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 :)

Answer 2

[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

[Dustin]

Thanks Wolfgang, but I don't think this works. The adjacency matrix outlines parent-child hole dependencies, whereas I am looking for pixel adjacencies.

I tried it out using this simple code:

>> a = [0 0 1 1;0 1 0 0; 0 1 1 0;0 0 1 1]

a =

0 0 1 1

0 1 0 0

0 1 1 0

0 0 1 1

>> [B,L,N,A] = bwboundaries(a,8,'noholes')

B =

[10x2 double]

L =

0 0 1 1

0 1 0 0

0 1 1 0

0 0 1 1

N =

1

A =

All zero sparse: 1-by-1

B contains the same output as bwtraceboundary(). What I need is a matrix of the form [row,col] starting at (1,4) or (4,4) and terminating at the other point.

[Wolfgang Schwanghart]

How would your path go then?

0 0 2 1

0 3 0 0

0 4 5 0

0 0 6 7

or would that be ok, too?

0 0 2 1

0 3 0 0

0 4 0 0

0 0 5 6

or this?

0 0 2 1

0 3 0 0

0 4 5 0

0 0 0 6

[Dustin]

I would prefer the first one (as it includes all the pixels), but the other two are also acceptable.

[Image Analyst]

Then just use bwboundaries with 4-connectivity and that's what you'll get.

Answer 3

[Sean de Wolski]

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!

[Dustin]

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.

Answer 4

[kevin]

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.