process subregions on an image/matrix

[alexxx.magni]

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]

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

 

[alexxx.magni]

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

(e-mail address removed) ha scritto:

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

 

[xhoster]

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

 

[alexxx.magni]

now I got it - crystal clear!

thanks a lot

Alessandro

(e-mail address removed) ha scritto:

 

[anno4000]

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

 

[anno4000]

[...]

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