Velocity Reviews > Perl > process subregions on an image/matrix

# process subregions on an image/matrix

alexxx.magni@gmail.com
Guest
Posts: n/a

 11-07-2006
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

xhoster@gmail.com
Guest
Posts: n/a

 11-07-2006
"(E-Mail Removed)" <(E-Mail Removed)> 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

alexxx.magni@gmail.com
Guest
Posts: n/a

 11-07-2006
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

http://www.velocityreviews.com/forums/(E-Mail Removed) ha scritto:

> "(E-Mail Removed)" <(E-Mail Removed)> 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

xhoster@gmail.com
Guest
Posts: n/a

 11-07-2006
"(E-Mail Removed)" <(E-Mail Removed)> 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

alexxx.magni@gmail.com
Guest
Posts: n/a

 11-08-2006
now I got it - crystal clear!

thanks a lot

Alessandro

(E-Mail Removed) ha scritto:

> "(E-Mail Removed)" <(E-Mail Removed)> 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

Guest
Posts: n/a

 11-09-2006
<(E-Mail Removed)> wrote in comp.lang.perl.misc:
> "(E-Mail Removed)" <(E-Mail Removed)> 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

Guest
Posts: n/a

 11-09-2006
<(E-Mail Removed)> wrote in comp.lang.perl.misc:
> "(E-Mail Removed)" <(E-Mail Removed)> 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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Rithesh Pai ASP .Net 1 08-22-2005 03:02 PM rtm Perl 0 09-27-2004 10:06 PM jack ASP .Net 0 08-01-2004 09:49 PM Jerry ASP .Net 4 12-15-2003 06:07 PM walala VHDL 3 09-09-2003 07:47 AM