finding connected neighbors [Matlab]

Prev: how to create a custom bit pattern in simulink
Next: find centroid of a moving object

From: Lucio Cetto on 25 Apr 2010 06:23

This is an idea (this looks like a fun project)

Start building a big graph (n^2 X n^2), every node represents a pixel in the image and edges can occur between adjacent pixels in the image (most of the pixels will have four neighbors). Use a logical sparse matrix to save memory. In this graph set all the edges according with the pixels in the image, edges should only exist between blank and red dots.

Now loop over every node, and for every node that is not a red pixel ( a connection point) you need to create a bridge between its neighbors and remove the edges comming out form this node.

Repeat the process until all the edges in your graph only come out of connected points.

Now finding the nearest (red) neighbors should be easy.

Trick: order your nodes in the sparse matrix in the same order linear indexing access pixels in the image, so at any point it will be easy to come back to the image to peek it ot it will be easy to figure out the coordinates of a pixel for a given node.

HTH
Lucio

"Krishna C" <chaitanya.alur(a)gmail.com> wrote in message <hqvpa0$678$1(a)fred.mathworks.com>...
> ImageAnalyst <imageanalyst(a)mailinator.com> wrote in message <12a13944-1d27-4ad5-aeda-da9e97d5819f(a)x7g2000vbc.googlegroups.com>...
> > Krishna Chaitanya:
> > I'm not exactly sure what you want. Do you want another image (with
> > only pixels that are immediately next to an intersection node pixel),
> > or a list of coordinates listing the intersection node coordinate
> > along with all coordinates connected to that node coordinate?
>
>
> Thanks for the reply sir,
>
> exactly i want the second one , for every intersection node(red marked) i want the list of node coordinates that are connected to it...
>
> Kindly have a look at the following image, so that you can get a better idea..
>
> http://www.flickr.com/photos/30274557(a)N05/4549284144/sizes/o/
>
> in the above pic, take some node (represented in blue circle), i want to extract the coordinates of its connected nodes ( represented in green circles). I want to make a list like this for every intersection node (marked by red star) in the image..
>
> The data i have is, the list of coordinates of all intersection nodes (red ones)..

From: Krishna C on 25 Apr 2010 10:27

many thanks for your message..

I have couple of doubts in your description...basically i dont know much about graph theory..

1. what does exactly 'n' represent??..its the size of image or the total no. of pixels in the image or the total no. of intersections (red points ) in the image

2. now, coming to building a graph, can you give brief description in the form of come.. this just to start with..

can you describe it briefly in the form of code..

sorry for my ignorance and thanks in advance..

"Lucio Cetto" <lcetto(a)nospam.mathworks.com> wrote in message <hr156b$5s$1(a)fred.mathworks.com>...
> This is an idea (this looks like a fun project)
>
> Start building a big graph (n^2 X n^2), every node represents a pixel in the image and edges can occur between adjacent pixels in the image (most of the pixels will have four neighbors). Use a logical sparse matrix to save memory. In this graph set all the edges according with the pixels in the image, edges should only exist between blank and red dots.
>
> Now loop over every node, and for every node that is not a red pixel ( a connection point) you need to create a bridge between its neighbors and remove the edges comming out form this node.
>
> Repeat the process until all the edges in your graph only come out of connected points.
>
> Now finding the nearest (red) neighbors should be easy.
>
> Trick: order your nodes in the sparse matrix in the same order linear indexing access pixels in the image, so at any point it will be easy to come back to the image to peek it ot it will be easy to figure out the coordinates of a pixel for a given node.
>
> HTH
> Lucio
>
> "Krishna C" <chaitanya.alur(a)gmail.com> wrote in message <hqvpa0$678$1(a)fred.mathworks.com>...
> > ImageAnalyst <imageanalyst(a)mailinator.com> wrote in message <12a13944-1d27-4ad5-aeda-da9e97d5819f(a)x7g2000vbc.googlegroups.com>...
> > > Krishna Chaitanya:
> > > I'm not exactly sure what you want. Do you want another image (with
> > > only pixels that are immediately next to an intersection node pixel),
> > > or a list of coordinates listing the intersection node coordinate
> > > along with all coordinates connected to that node coordinate?
> >
> >
> > Thanks for the reply sir,
> >
> > exactly i want the second one , for every intersection node(red marked) i want the list of node coordinates that are connected to it...
> >
> > Kindly have a look at the following image, so that you can get a better idea..
> >
> > http://www.flickr.com/photos/30274557(a)N05/4549284144/sizes/o/
> >
> > in the above pic, take some node (represented in blue circle), i want to extract the coordinates of its connected nodes ( represented in green circles). I want to make a list like this for every intersection node (marked by red star) in the image..
> >
> > The data i have is, the list of coordinates of all intersection nodes (red ones)..

From: Krishna C on 25 Apr 2010 10:46

ImageAnalyst <imageanalyst(a)mailinator.com> wrote in message <93009790-7887-46e0-b378-244b479ffe26(a)t17g2000vbk.googlegroups.com>...
> No, you don't want the second one. You want the nearest connected
> intersection nodes, not simply the nearest pixel, because the nearest
> pixel could be on a path to the nearest node. But you didn't circle
> the nearest pixel, you circled the adjacent intersection nodes that is
> on a direct path to the node in question. I don't know of a simple
> way to find those - only complicated ways - but maybe someone else
> who's more into graph theory can help you.

Sir,

I want to make an attempt using this,

http://blogs.mathworks.com/steve/2007/03/28/neighbor-indexing/

can you give me an idea of implementing the same thing to 8-connected neighborhood...

From: Krishna C on 25 Apr 2010 11:31

From: ImageAnalyst on 25 Apr 2010 12:48

On Apr 25, 11:31 am, "Krishna C" <chaitanya.a...(a)gmail.com> wrote:
> Sir,
> I want to make an attempt using this,
> http://blogs.mathworks.com/steve/2007/03/28/neighbor-indexing/
> can you give me an idea of implementing the same thing to 8-connected neighborhood...
------------------------
Sorry but that won't work. The reason is that your points you want to
find are not next to the points you're looking out from. They are
several pixels away, connected by a single pixel wide path of "lit up"
pixels. That method will only find the first pixels on the path, not
the ones at the ends of the path which is where the next intersection
point it. You're going to have to start at every node and go out from
there along each of the paths emanating from the node until you hit
another node. You could probably do it with some kind of a recursive
breadth first tree search algorithm. Maybe there's something in the
optimization toolbox that could do it as a canned routine - I don't
know since I don't have that toolbox.

First | Prev | Next | Last
Pages: 1 2 3 4 5
Prev: how to create a custom bit pattern in simulink
Next: find centroid of a moving object