Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > process subregions on an image/matrix

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
 
Reply With Quote
 
 
 
 
alexxx.magni@gmail.com
Guest
Posts: n/a
 
      11-07-2006
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)
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
>
> --
> -------------------- http://NewsReader.Com/ --------------------
> Usenet Newsgroup Service $9.95/Month 30GB


 
Reply With Quote
 
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

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB
 
Reply With Quote
 
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
>
> --
> -------------------- http://NewsReader.Com/ --------------------
> Usenet Newsgroup Service $9.95/Month 30GB


 
Reply With Quote
 
anno4000@radom.zrz.tu-berlin.de
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
 
Reply With Quote
 
anno4000@radom.zrz.tu-berlin.de
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Process Cannot access file "file_name" because it is being used by another process Rithesh Pai ASP .Net 1 08-22-2005 03:02 PM
(Win32) Timing out a process while reading process' output? rtm Perl 0 09-27-2004 10:06 PM
A process serving application pool 'DefaultAppPool' exceeded time limits during start up. The process id was '216'. jack ASP .Net 0 08-01-2004 09:49 PM
The process cannot access the file because it is being used by another process. Jerry ASP .Net 4 12-15-2003 06:07 PM
Are all the signals read in the process should appear in the sensitivity list of the process? walala VHDL 3 09-09-2003 07:47 AM



Advertisments