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
    #1
    1. Advertising

  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

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
     
    , Nov 7, 2006
    #2
    1. Advertising

  3. Guest

    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

    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
    >
    > --
    > -------------------- http://NewsReader.Com/ --------------------
    > Usenet Newsgroup Service $9.95/Month 30GB
     
    , Nov 7, 2006
    #3
  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

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
     
    , Nov 7, 2006
    #4
  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
    >
    > --
    > -------------------- http://NewsReader.Com/ --------------------
    > Usenet Newsgroup Service $9.95/Month 30GB
     
    , Nov 8, 2006
    #5
  6. -berlin.de Guest

    <> 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
    #6
  7. -berlin.de Guest

    <> 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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Cristina e Cris

    open an image as matrix

    Cristina e Cris, May 5, 2005, in forum: C++
    Replies:
    1
    Views:
    503
    Ivan Vecerina
    May 5, 2005
  2. lvcargnini

    Matrix composed by two matrix

    lvcargnini, Jul 4, 2006, in forum: VHDL
    Replies:
    3
    Views:
    2,703
    Jonathan Bromley
    Jul 5, 2006
  3. Holgerson

    Matrix*Vector and Vector*Matrix

    Holgerson, Oct 25, 2007, in forum: C++
    Replies:
    3
    Views:
    429
    Holgerson
    Oct 26, 2007
  4. Terry Reedy
    Replies:
    0
    Views:
    573
    Terry Reedy
    Apr 2, 2009
  5. Robert Kern
    Replies:
    0
    Views:
    615
    Robert Kern
    Apr 2, 2009
Loading...

Share This Page