determining region adjacency

[Vanderbilt]

Hi, gurus,

I am looking for suitable data structure and efficient algorithms to compute adjacent neighbors of an image segment.

I did mean-shift image segmentation on my source image. Now that segmented regions are labelled and each one has a Region Adjacency List. But my way of building the RAL is quite simple, adjacency is determined solely by local 4-neighbor touchness/or not.
Is there efficient algorithm for incoorporating spatial information of the neighbors as well? In other words, can I efficiently sort the sorrounding neighbors as a sequence of clockwise segments? And find out what's its neighbors in its north, etc?

thanks,
Van

[YvesDaoust]

Van,

if I understand correctly, you want every pixel in the image to know about its four immediate neighbors in the four cardinal directions.

Well, an easy way is to directly lookup the labels in the labeled image (I mean, if you are at pixel (X,Y) with label L, you can readout the value of pixel (X,Y-1) to see if the northern neighbor also has label L).

This is efficient in terms of storage and running time. If you want to enumerate all neighbors around a given pixel, just try the four directions, clockwise or otherwise.

If you repeatedly have to enumerate the neighbors, you can encode the neighborhood configuration by packing four bits in a byte that you store with each pixel.

Then, when you have to list the neighbors, a switch on the mask value will allow you to handle the 16 possible NESW combinations. This trick extends to 8-connexity, at the expense of handling 256 cases.

Is this what you needed ?

Yves

[Vanderbilt]

Yves,

By region, I mean a cluster of pixels connected and having similar colors. And this cluster share a common label L. By neighbors of a region, I mean all the other clusters touching this given segment/or cluster. So, for each segment(assume without holes inside), I have a list of its segments which border it. But these are solely organized in a list, without information of in which order (say, clockwise) they occur.

In that case, my direction is with regard to a given segment. Actually it is harder to define and determine its directions.

But your idea of packing neighborhood configuration in a byte is very interesting! I will see if similiar approach can be used.

Thanks!
Van