🚀 go-pugleaf

I    have given much  thought to    an agonizing  trade-off in   image
processing   loops in   c,  and have   not  come   up with a   totally
satisfactory solution-   I wonder  whether    anyone  has  any    good
suggestions.

Almost all image processing subroutines consist of a double (or more)
nested loop that visits every pixel in turn, something like this...

  #define XSIZE 128
  #define YSIZE 128
  subroutine(data)
  unsigned char data[YSIZE][XSIZE];
  {
    int x,y;

    for(y=0;y<YSIZE;y++){
      for(x=0;x<XSIZE;x++){
	data[y][x] = ... <<<< whatever you want to do >>>>
      }
    }
  }

now it is much more elegant to pass the  image size in with the image,
to make   the  routine more  general.  

  subroutine(data,xsize,ysize)
  int xsize,ysize;
  unsigned char data[ysize][xsize];  <=== PROBLEM!
  {
    int x,y;

    for(y=0;y<YSIZE;y++){
      for(x=0;x<XSIZE;x++){
	data[y][x] = ...
      }
    }
  }

The problem is that c will not allow the array data[][] to be declared
without   specifying  at compile-time at  LEAST  the  dimension of the
xsize.  Now you could define it to be  MAX_XSIZE, which is the largest
possible  xsize  that you would ever expect  to use, but this would be
very wasteful.  The other alternative is to go to pointers...
	
  /**** in main program- allocate data ****/
  data = (unsigned char*)malloc(xsize*ysize*sizeof(unsigned char));

  subroutine(data,xsize,ysize)
  int xsize,ysize;
  unsigned char *data;
  {
    int x,y;

    for(y=0;y<ysize;y++){
      for(x=0;x<xsize;x++){
	*(data+y*xsize+x) = ...
      }
    }
  }

This works o.k,  but  the problem now is  that   you are performing  a
multiplication  in  the innermost  loop  of the  program,  which slows
things down quite a bit.  You  can fix this  by using offsets that are
incremented  inside    the     loop- with    addition     instead   of
multiplication...

    yskip = 0;
    for(y=0;y<ysize;y++){
      for(x=0;x<xsize;x++){
	*(data+yskip+x) = ...
      }
      yskip += xsize;
    }

Now this solution works o.k, and  that  is basically  what I am using.
But the code looks very messy- maybe not  so bad in  this example, but
when you start adding extra inner loops like for an image convolution,
it really looks a mess, and might just as well be  written in assembly
language!

        /**** for each pixel ****/
        yskip = hafy*xsize;
        for(y=hafy;y<ysize-hafy;y++){
          for(x=hafx;x<xsize-hafx;x++){
            *(img2->data+yskip+x) = 0.0;

            /**** for each filter element ****/
            yyskip = -hafy*xsize;
            fyskip = 0;
            for(yy=0;yy<fysize;yy++){
              for(xx=0;xx<fxsize;xx++){
                *(img2->data+yskip+x) +=
                 (*(img1->data+yskip+yyskip+(xx-hafx)+x)) *
                 (*(filt->data+fyskip+xx));

              }
              yyskip += xsize;
              fyskip += fxsize;
            }/**** next filter element ****/

          }
          yskip += xsize;
        }/**** next pixel ****/

God forbid you should have to make any changes  to this  code!  I have
tried to think of some kind of macro that would simplify things a bit,
but I can't come up with anything  that is less  complicated than what
you see here.  Does anyone have an elegant solution to this problem?

--
(O)((O))(((O)))((((O))))(((((O)))))(((((O)))))((((O))))(((O)))((O))(O)
(O)((O))(((               slehar@park.bu.edu               )))((O))(O)
(O)((O))(((    Steve Lehar Boston University Boston MA     )))((O))(O)
(O)((O))(((    (617) 424-7035 (H)   (617) 353-6741 (W)     )))((O))(O)
(O)((O))(((O)))((((O))))(((((O)))))(((((O)))))((((O))))(((O)))((O))(O)