Thread Subject: all possible routes between two pixels in image

Hi!

I have a 5x5 pixel image, and I randomlly choose two pixels that I would like to connect. I want to generate all possible routes between these two pixels. I used this file from File Exchange:
http://www.mathworks.com/matlabcentral/fileexchange/12724
to generate all the possible combinations of a set of elements, but I ran out of memory.

I would appreciate your help on this.
Aleks

Hi

Are you sure, that you are doing it right? Assuming that you are
really calculating the routes inside of the 5x5 image - that are
elements of a subset of the possible states of an 5x5 binary image -
that is 2^(25) - that should still only take about 4 MB-s to store
(the full space) - you should not get out of memory.

By the way, may I ask why you would like do this?

Peter


On Jun 15, 1:26 pm, "Aleks " <di.eli...@gmail.com> wrote:
> Hi!
>
> I have a 5x5 pixel image, and I randomlly choose two pixels that I would like to connect. I want to generate all possible routes between these two pixels. I used this file from File Exchange:http://www.mathworks.com/matlabcentral/fileexchange/12724
> to generate all the possible combinations of a set of elements, but I ran out of memory.
>
> I would appreciate your help on this.
> Aleks

> Are you sure, that you are doing it right? Assuming that you are
> really calculating the routes inside of the 5x5 image - that are
> elements of a subset of the possible states of an 5x5 binary image -
> that is 2^(25) - that should still only take about 4 MB-s to store
> (the full space) - you should not get out of memory.
>
> By the way, may I ask why you would like do this?
>
> Peter

Peter,

Your solution does not take into account the order of the pixels, where the order of the pixels will influence the Euclidean lenght of the route (the pixels in my problem are 8-connected). I apologize if my post was not clear enough.

The purpose of this is to optimize between the length of the route and the values of the pixels.

Aleks

"Aleks " <di.elijen@gmail.com> wrote in message <h1607a$nb2$1@fred.mathworks.com>...
> Hi!
>
> I have a 5x5 pixel image, and I randomlly choose two pixels that I would like to connect. I want to generate all possible routes between these two pixels. I used this file from File Exchange:
> http://www.mathworks.com/matlabcentral/fileexchange/12724
> to generate all the possible combinations of a set of elements, but I ran out of memory.
>
> I would appreciate your help on this.
> Aleks

OK. I guess you have to limit the route to go backward, otherwise you are infinity number of solutions, even for two pixels very close.

First, just consider a simple case where route is horizontal or vertical (go diagonal is not allowed). Let's call (dx,dy) the separation between 2 pixels.

Take a route, it crosses the vertical axis in (dy+1) vertical positions. Le's call x(k) is how many pixels the route go horizontally in the vertical position #k. The array x() can be 0 to dx, and sum(x)=dx.

That mean a route is coded by
x() of dimension dy+1, sum(x)==dx.

How to generate all the routes, i.e., x as above? Using my file on FEX

http://www.mathworks.com/matlabcentral/fileexchange/17818

This File returns also the number of solutions. For example for two pixels separate by dx=2, dy=2

>> dx=2; dy=2; nroute=allVL1(dy+1,dx,'==',NaN)

nroute =

     6

>> x=allVL1(dy+1,dx,'==') %

x =

     0 0 2 % up 2 + right 2
     0 1 1 % up 1 + right 1 + up 1 + right 1
     0 2 0 % up 1 + right 2 + up 1
     1 0 1 % right 1 + up 2 + right 1
     1 1 0 % right 1 + up 1 + right 1 + up 1
     2 0 0 + right 2 + up 2

>>

It is possible to derive a diagonal routes from the above. I let you to have fun with it.

Bruno

Sorry, should read

> OK. I guess you have to limit the route NOT to go backward,


Bruno

"Aleks " <di.elijen@gmail.com> wrote in message <h185dm$ios$1@fred.mathworks.com>...

> The purpose of this is to optimize between the length of the route and the values of the pixels.


Shouldn't you then be using a shortest-path algorithm, e.g.

http://www.mathworks.com/matlabcentral/fileexchange/20025

instead of enumerating all the paths?

> Shouldn't you then be using a shortest-path algorithm, e.g.
>
> http://www.mathworks.com/matlabcentral/fileexchange/20025
>
> instead of enumerating all the paths?

Thank you,
Aleks