process subregions on an image/matrix

Discussion in 'Perl Misc' started by alexxx.magni@gmail.com, Nov 7, 2006.

1. Guest

Hi everybody, I need a bit of help on the programming side:

I'm trying to write a program to perform a filtering operation on an
image,
represented as a matrix of integers.
So I'm 1st thing writing a procedure that scans the image, and, when
finding a pixel in the color to be processed, it scans all the
neighboring pixels until all the cluster is processed (and, if its size
is in the correct range, it applies the transform).

Right now I perform this scanning of the cluster in the way I find most
elegant: recursion:

sub recurseinto
{
my (\$x,\$y)=@_;
my \$c;

\$flag[\$x][\$y]=1;
\$c=1;

if ((\$x-1>0)&&(\$flag[\$x-1][\$y]==0)&&(\$img[\$x-1][\$y]==\$col)) { \$c +=
recurseinto(\$x-1,\$y) }
if ((\$x+1<=\$width)&&(\$flag[\$x+1][\$y]==0)&&(\$img[\$x+1][\$y]==\$col)) {
\$c += recurseinto(\$x+1,\$y) }
if ((\$y-1>0)&&(\$flag[\$x][\$y-1]==0)&&(\$img[\$x][\$y-1]==\$col)) { \$c +=
recurseinto(\$x,\$y-1) }
if ((\$y+1<=\$height)&&(\$flag[\$x][\$y+1]==0)&&(\$img[\$x][\$y+1]==\$col))
{ \$c += recurseinto(\$x,\$y+1) }
return \$c;

}

Well, it works, but - I hate to admit it - it's slow.

The question is: in which other way you would perform this task?

thanks for any info...

Alessandro Magni

, Nov 7, 2006

2. Guest

"" <> wrote:
> Hi everybody, I need a bit of help on the programming side:
>
> I'm trying to write a program to perform a filtering operation on an
> image,
> represented as a matrix of integers.
> So I'm 1st thing writing a procedure that scans the image, and, when
> finding a pixel in the color to be processed, it scans all the
> neighboring pixels until all the cluster is processed (and, if its size
> is in the correct range, it applies the transform).
>
> Right now I perform this scanning of the cluster in the way I find most
> elegant: recursion:
>
> sub recurseinto
> {
> my (\$x,\$y)=@_;
> my \$c;
>
> \$flag[\$x][\$y]=1;
> \$c=1;
>
> if ((\$x-1>0)&&(\$flag[\$x-1][\$y]==0)&&(\$img[\$x-1][\$y]==\$col)) { \$c +=
> recurseinto(\$x-1,\$y) }
> if ((\$x+1<=\$width)&&(\$flag[\$x+1][\$y]==0)&&(\$img[\$x+1][\$y]==\$col)) {
> \$c += recurseinto(\$x+1,\$y) }
> if ((\$y-1>0)&&(\$flag[\$x][\$y-1]==0)&&(\$img[\$x][\$y-1]==\$col)) { \$c +=
> recurseinto(\$x,\$y-1) }
> if ((\$y+1<=\$height)&&(\$flag[\$x][\$y+1]==0)&&(\$img[\$x][\$y+1]==\$col))
> { \$c += recurseinto(\$x,\$y+1) }
> return \$c;
>
> }
>
> Well, it works, but - I hate to admit it - it's slow.
>
> The question is: in which other way you would perform this task?

You could use traditional methods to remove recursion using a stack.

my @stack = (@_); #starting point
#....
while (@stack) {
my (\$x,\$y)=splice @stack,0,2;
if whatever(\$x-1,\$y) { push @stack, \$x-1,\$y; \$c++};
if whatever(\$x+1,\$y) { push @stack, \$x+1,\$y; \$c++};
# etc.
}

But if you need it to be hugely faster, I'd look into switching languages,
either to C (Inline::C) or some specialized image processing language.

Xho

--
Usenet Newsgroup Service \$9.95/Month 30GB

, Nov 7, 2006

3. Guest

Sadly - I'm not a Perl guru at all - it's not clear to me how it works:
1st of all, the calls to "push @stack, \$x-1,\$y;": I believed that push
wanted just 2 arguments ( push ARRAY, LIST: This function treats
ARRAY as a stack and pushes the values of LIST onto the end of ARRAY
etc etc)
2nd, what's the use of \$c, continuously updated?
3rd (and last!) what is there in @stack? The matrix indices? It's not
clear what happens to @stack, since it is sometimes push-ed, but never
pop-ped, so how can it be exhausted?

sorry if I wrote stupid questions, I'm trying to learn...

Alessandro

ha scritto:

> "" <> wrote:
> > Hi everybody, I need a bit of help on the programming side:
> >
> > I'm trying to write a program to perform a filtering operation on an
> > image,
> > represented as a matrix of integers.
> > So I'm 1st thing writing a procedure that scans the image, and, when
> > finding a pixel in the color to be processed, it scans all the
> > neighboring pixels until all the cluster is processed (and, if its size
> > is in the correct range, it applies the transform).
> >
> > Right now I perform this scanning of the cluster in the way I find most
> > elegant: recursion:
> >
> > sub recurseinto
> > {
> > my (\$x,\$y)=@_;
> > my \$c;
> >
> > \$flag[\$x][\$y]=1;
> > \$c=1;
> >
> > if ((\$x-1>0)&&(\$flag[\$x-1][\$y]==0)&&(\$img[\$x-1][\$y]==\$col)) { \$c +=
> > recurseinto(\$x-1,\$y) }
> > if ((\$x+1<=\$width)&&(\$flag[\$x+1][\$y]==0)&&(\$img[\$x+1][\$y]==\$col)) {
> > \$c += recurseinto(\$x+1,\$y) }
> > if ((\$y-1>0)&&(\$flag[\$x][\$y-1]==0)&&(\$img[\$x][\$y-1]==\$col)) { \$c +=
> > recurseinto(\$x,\$y-1) }
> > if ((\$y+1<=\$height)&&(\$flag[\$x][\$y+1]==0)&&(\$img[\$x][\$y+1]==\$col))
> > { \$c += recurseinto(\$x,\$y+1) }
> > return \$c;
> >
> > }
> >
> > Well, it works, but - I hate to admit it - it's slow.
> >
> > The question is: in which other way you would perform this task?

>
> You could use traditional methods to remove recursion using a stack.
>
> my @stack = (@_); #starting point
> #....
> while (@stack) {
> my (\$x,\$y)=splice @stack,0,2;
> if whatever(\$x-1,\$y) { push @stack, \$x-1,\$y; \$c++};
> if whatever(\$x+1,\$y) { push @stack, \$x+1,\$y; \$c++};
> # etc.
> }
>
> But if you need it to be hugely faster, I'd look into switching languages,
> either to C (Inline::C) or some specialized image processing language.
>
> Xho
>
> --
> Usenet Newsgroup Service \$9.95/Month 30GB

, Nov 7, 2006
4. Guest

"" <> wrote:
> thank you for your help!
> Sadly - I'm not a Perl guru at all - it's not clear to me how it works:
> 1st of all, the calls to "push @stack, \$x-1,\$y;": I believed that push
> wanted just 2 arguments ( push ARRAY, LIST: This function treats
> ARRAY as a stack and pushes the values of LIST onto the end of ARRAY
> etc etc)

The 2nd argument is a list, which means it can look like more than one
argument. push @x, 1, 2 pushes the list (1,2) unto @x. It is the same
as push @x,1; push @x,2;

> 2nd, what's the use of \$c, continuously updated?

I don't know, I just carried that over from your code. I guess it keeps
track of the size of the "splotch"

> 3rd (and last!) what is there in @stack?

flattened Pairs of x,y coordinates. It might be more "perlish" for
@stack to have arrayrefs, each one to an two-element array. But that takes
more memory and probably is slower than the flattened list.

> The matrix indices? It's not
> clear what happens to @stack, since it is sometimes push-ed, but never
> pop-ped, so how can it be exhausted?

The code:
my (\$x,\$y)=splice @stack,0,2;

Is equivalent to:
my \$x=shift @stack;
my \$y=shift @stack;

(Which means I used a queue rather than a stack. It shouldn't change the
outcome, just the order of processing. To use a stack, you would
instead use "my (\$x,\$y)=splice @stack, -2, 2;")

Xho

--
Usenet Newsgroup Service \$9.95/Month 30GB

, Nov 7, 2006
5. Guest

now I got it - crystal clear!

thanks a lot

Alessandro

ha scritto:

> "" <> wrote:
> > thank you for your help!
> > Sadly - I'm not a Perl guru at all - it's not clear to me how it works:
> > 1st of all, the calls to "push @stack, \$x-1,\$y;": I believed that push
> > wanted just 2 arguments ( push ARRAY, LIST: This function treats
> > ARRAY as a stack and pushes the values of LIST onto the end of ARRAY
> > etc etc)

>
> The 2nd argument is a list, which means it can look like more than one
> argument. push @x, 1, 2 pushes the list (1,2) unto @x. It is the same
> as push @x,1; push @x,2;
>
> > 2nd, what's the use of \$c, continuously updated?

>
> I don't know, I just carried that over from your code. I guess it keeps
> track of the size of the "splotch"
>
>
> > 3rd (and last!) what is there in @stack?

>
> flattened Pairs of x,y coordinates. It might be more "perlish" for
> @stack to have arrayrefs, each one to an two-element array. But that takes
> more memory and probably is slower than the flattened list.
>
> > The matrix indices? It's not
> > clear what happens to @stack, since it is sometimes push-ed, but never
> > pop-ped, so how can it be exhausted?

>
> The code:
> my (\$x,\$y)=splice @stack,0,2;
>
> Is equivalent to:
> my \$x=shift @stack;
> my \$y=shift @stack;
>
> (Which means I used a queue rather than a stack. It shouldn't change the
> outcome, just the order of processing. To use a stack, you would
> instead use "my (\$x,\$y)=splice @stack, -2, 2;")
>
> Xho
>
> --
> Usenet Newsgroup Service \$9.95/Month 30GB

, Nov 8, 2006
6. -berlin.deGuest

<> wrote in comp.lang.perl.misc:
> "" <> wrote:
> > Hi everybody, I need a bit of help on the programming side:
> >
> > I'm trying to write a program to perform a filtering operation on an
> > image,
> > represented as a matrix of integers.
> > So I'm 1st thing writing a procedure that scans the image, and, when
> > finding a pixel in the color to be processed, it scans all the
> > neighboring pixels until all the cluster is processed (and, if its size
> > is in the correct range, it applies the transform).
> >
> > Right now I perform this scanning of the cluster in the way I find most
> > elegant: recursion:
> >
> > sub recurseinto
> > {
> > my (\$x,\$y)=@_;
> > my \$c;
> >
> > \$flag[\$x][\$y]=1;
> > \$c=1;
> >
> > if ((\$x-1>0)&&(\$flag[\$x-1][\$y]==0)&&(\$img[\$x-1][\$y]==\$col)) { \$c +=
> > recurseinto(\$x-1,\$y) }
> > if ((\$x+1<=\$width)&&(\$flag[\$x+1][\$y]==0)&&(\$img[\$x+1][\$y]==\$col)) {
> > \$c += recurseinto(\$x+1,\$y) }
> > if ((\$y-1>0)&&(\$flag[\$x][\$y-1]==0)&&(\$img[\$x][\$y-1]==\$col)) { \$c +=
> > recurseinto(\$x,\$y-1) }
> > if ((\$y+1<=\$height)&&(\$flag[\$x][\$y+1]==0)&&(\$img[\$x][\$y+1]==\$col))
> > { \$c += recurseinto(\$x,\$y+1) }
> > return \$c;
> >
> > }
> >
> > Well, it works, but - I hate to admit it - it's slow.
> >
> > The question is: in which other way you would perform this task?

>
> You could use traditional methods to remove recursion using a stack.
>
> my @stack = (@_); #starting point
> #....
> while (@stack) {
> my (\$x,\$y)=splice @stack,0,2;
> if whatever(\$x-1,\$y) { push @stack, \$x-1,\$y; \$c++};
> if whatever(\$x+1,\$y) { push @stack, \$x+1,\$y; \$c++};
> # etc.
> }
>
> But if you need it to be hugely faster, I'd look into switching languages,
> either to C (Inline::C) or some specialized image processing language.

I think the problem is equivalent to finding connected components of
a graph, a well-researched subject.. That's another direction to look
for algorithms and/or libraries.

Anno

-berlin.de, Nov 9, 2006
7. -berlin.deGuest

<> wrote in comp.lang.perl.misc:
> "" <> wrote:

[...]

> > clear what happens to @stack, since it is sometimes push-ed, but never
> > pop-ped, so how can it be exhausted?

>
> The code:
> my (\$x,\$y)=splice @stack,0,2;
>
> Is equivalent to:
> my \$x=shift @stack;
> my \$y=shift @stack;
>
> (Which means I used a queue rather than a stack. It shouldn't change the
> outcome, just the order of processing. To use a stack, you would
> instead use "my (\$x,\$y)=splice @stack, -2, 2;")

....or indeed

my ( \$y, \$x) = ( pop @stack, pop @stack);

to give the keyword "pop" an appearance in the show.

Anno

-berlin.de, Nov 9, 2006