Finding best neighbour pixel

Question

I am trying to do shape analysis of an object in an image in MATLAB (specifically). To do so, I have found boundary pixels. For each boundary pixel I am calculating it's neighbor using 8-neighborhood theory. Now I am calculating tangent of a point to its only one neighbor (depends how I select clockwise or other way). My algorithm works fine if every pixel has exactly two neighbors. For shapes shown in this picture (order 9 X 15 pixels).

But if there are more than 2 neighbors of a pixel then my algorithm gets confused. For example as shown in (order 9 X 15 pixels).

I want to take tangent of each boundary pixel with its neighbor pixel in clockwise or anti-clockwise direction and if you notice second image, which is valid boundary image, if I am moving in clockwise direction then neighbor of red pixel would be green and neighbor of green in clockwise direction would be "1" and neighbor of "1" is "2" but then I cannot come back to blue and brown pixel and I cannot visit and take tangent of each boundary pixel with its neighbor pixel.

I have learned graph's node visiting algorithms in which you maintain queue or stack but then in this case I don't just want to visit each pixel but also take tangent of every pixel with only right neighbor pixel according to what direction I am moving.

This is an example problem and similar problems can occur in some other way so I am trying to generate some generic algorithm for it. I will appreciate your help. Thank you.

Answer 1

Like btilly already said. The solution is to find the boundaries between the pixels and not the pixels self. I recommend you a part of the potrace Algorithm. It is an Algorith for vectorize binary images. The interesting part is for you the decompisition of the Path. Here is the idea of the Path decompisition:

The Potrace Algorithm you can find here.

An other Algorithm is from Wilhelm Burge and Burger in the Book "digital image processing an algorithmic introduction using enter link description here". In the link you can see some part of the book. The interisting part is the function "TraceContour" at page 538. This Algorithm work like you thought and walks around the "inner" pixels. I found some explenation of the Alorith here, at inner boundary tracing. You can do the Algorithm with a four or eight neighboor connectivity.