traversing all pixels in an area

Miscellaneous Topics
#1

I need an algorithm to travel through all the cells, in an area which has been defined, in a 2 dimenional map (i.e. image)

Currently i have made and am using a wall following routine with a stack of “Multiple Direction Fork” co-ordinates. My problem is that the stack can get very large.

basically the algorithm is:

  1. set current pixel to (0,0)
  2. set Direction to none.
  3. if pixel above current is empty and pixel left is non-empty, Direction = UP
  4. else if pixel left of current is empty and pixel below is non-empty, Direction = LEFT
  5. else if pixel below current is empty and pixel right is non-empty, Direction = DOWN
  6. else if pixel right of current is empty and pixel above is non-empty, Direction = RIGHT
  7. if Direction is UP
    6a. if pixels (-1,-1) and (+1,-1) or (+1,+1) are non empty then add current pixel to stack.
  8. if Direction is DOWN
    7a. if pixels (-1,+1) and (+1,+1) or (-1,-1) are non empty then add current pixel to stack.
  9. if Direction is RIGHT
    8a. if pixels (+1,-1) and (+1,+1) or (-1,+1) are non empty then add current pixel to stack.
  10. if Direction is LEFT
    9a. if pixels (-1,-1) and (-1,+1) or (+1,-1) are non empty then add current pixel to stack.
  11. if direction is not none process current pixel
    10a. else if there are pixels in the stack then pop a pixel and set the current pixel to it.
    10b. else exit algorithm
  12. move current pixel in direction specified.
  13. repeat 1

Does anyone know how to reduce the number of pixels entering the stack or indeed know of a better algorithm to traverse all the pixels in a shape.

The following pictures illusrate my problem:

With out stack pixel indicator(Blue):
www.geocities.com/budgetanime/lena.gif.txt

With stack pixel indicator (Blue)
www.geocities.com/budgetanime/lena1.gif.txt
www.geocities.com/budgetanime/server1.gif.txt

(shaded pixels are the pixels that have been processed, solid blue pixels are pixels that had been in the stack at some point, grey/white pixels define the bounding areas and black pixels are unprocessed pixels)

(you will have to change the file extension after you have downloaded it)

As you can see there are long diagonal lines of (blue) pixels that have been in the stack.

Any suggestions are welcome!

Thanks

#2

Do you mean a flood fill?

#3

Thanks for putting me on to flood fill, it is more than 50% faster than my current fill method.

However it seems cause stack overflows when filling large areas :frowning:

the flood fill method as it stands:


      public void FloodFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)
      {

            count=0;
            java.util.Random r=new java.util.Random();
            int colourR= r.nextInt(240);
            int colourG= r.nextInt(240);
            int colourB= r.nextInt(240);
            LinearFloodFill4(x,y,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);
      }


      private void LinearFloodFill4(int x, int y,int width,int height,boolean[][] PixelsChecked,byte[][] frame,int count,int colourR,int colourG,int colourB)
      {
        
    
    
            //FIND LEFT EDGE OF COLOR AREA
            int LFillLoc=x; //the location to check/fill on the left

            while(true)
            {
                   //fill with the color
                  count+=1;
                  frame[y*width+LFillLoc][0]=(byte) (colourR+count%15);
                  frame[y*width+LFillLoc][1]=(byte) (colourG+count%15);
                  frame[y*width+LFillLoc][2]=(byte) (colourB+count%15);
                  PixelsChecked[LFillLoc][y]=true;
                  LFillLoc--;               //de-increment counter

                  if(LFillLoc<=0 || 
                        (PixelsChecked[LFillLoc][y]))
                              //exit loop if we're at edge of bitmap or color area
                              break;
        
            }
            LFillLoc++;
    
            //FIND RIGHT EDGE OF COLOR AREA
            int RFillLoc=x; //the location to check/fill on the left

            while(true)
            {
                   //fill with the color
                  count+=1;
                  frame[y*width+RFillLoc][0]=(byte) (colourR+count%15);
                  frame[y*width+RFillLoc][1]=(byte) (colourG+count%15);
                  frame[y*width+RFillLoc][2]=(byte) (colourB+count%15);
                  PixelsChecked[RFillLoc][y]=true;
                  RFillLoc++;          //increment counter

                  if(RFillLoc>=width || 
                        (PixelsChecked[RFillLoc][y]))
                              //exit loop if we're at edge of bitmap or color area
                              break;
        
            }
            RFillLoc--;
    
    
            //START THE LOOP UPWARDS AND DOWNWARDS            
            
            for(int i=LFillLoc;i<=RFillLoc;i++)
            {
              //START LOOP UPWARDS
              //if we're not above the top of the bitmap 

              if(y>0 && 
                  (!(PixelsChecked[i][y-1])))
                     LinearFloodFill4(i,y-1,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);

              //START LOOP DOWNWARDS
              if(y<(height-1) && 
                      (!(PixelsChecked[i][y+1])))
                     LinearFloodFill4(i,y+1,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);
            }
        
      }

it is modified code from the Flood Fill Algorithms in C# and GDI+ tutorial by jdunlap:

http://www.codeproject.com/cs/media/floodfillincsharp.asp

i will now try using the queued floodfill rather than the linear flood fill as it is not going to cause a stack over flow, however it apparantly is much slower than the linear method…

#4

I have now implemented the Queued Flood Fill and have recieved quite dissapointing times :frowning:

Flood Fill - queue - 4 dir: 406 msec
Flood Fill - queue - 8 dir: 3187 msec
Flood Fill - linear - 4 dir: 47 msec
Follow Wall (my Algrthm): 125 msec

hmm, does anyone know of another filling algorithm which may peform better than my follow wall algorithm?

#5

A person suggested filling by rows, i.e. go left->right filling pixels until you hit a boundary pixel. then look above you to see if there are row(s) that are to be filled and then fill each of those.

then do the same for rows below you.

I have implemented a row Fill however it does not seem to improving processing time…

here is how i implemented it

Recursive Row Fill:



      public void RecRowFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)
      {

            count=0;
            java.util.Random r=new java.util.Random();
            int colourR= r.nextInt(240);
            int colourG= r.nextInt(240);
            int colourB= r.nextInt(240);
            rowFill(x,y,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);
      }
      
      public void rowFill(int x,int y,int width, int height,boolean[][] processedPixel,byte[][] frame,int count,int colourR,int colourG,int colourB)
      {
            int sx=x;
            
            while (sx<width && !processedPixel[sx][y])
            {
                  count+=1;
                  frame[y*width+sx][0]=(byte) (colourR+count%15);
                  frame[y*width+sx][1]=(byte) (colourG+count%15);
                  frame[y*width+sx][2]=(byte) (colourB+count%15);
                  processedPixel[sx][y]=true;
                  sx++;
            }
            if (y>0)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y-1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y-1]) tx--;
                              rowFill(tx+1,y-1,width,height, processedPixel,frame,count,colourR,colourG,colourB);
                        }
                  }
            }
            if (y<height-1)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y+1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y+1]) tx--;
                              rowFill(tx+1,y+1,width,height, processedPixel,frame,count,colourR,colourG,colourB);
                        }
                  }
            }
            
      }

Queued Row Fill:


      public void QueueRowFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)
      {
            LinkedList CheckQueue=new LinkedList();
            

            Integer Count=new Integer(0);
            java.util.Random r=new java.util.Random();
            int colourR= r.nextInt(240);
            int colourG= r.nextInt(240);
            int colourB= r.nextInt(240);
      

                  //start the loop
                  rowFillQ(x,y,width,height, PixelsChecked,frame,Count,colourR,colourG,colourB,CheckQueue);
                  //call next item on queue
                  while(CheckQueue.size()>0)
                  {
                        x=((Item) CheckQueue.get(0)).freq;
                        y=((Item) CheckQueue.get(0)).value;
                        CheckQueue.remove(0);
                        //System.out.println (CheckQueue.size());
                        rowFillQ(x,y,width,height, PixelsChecked,frame,Count,colourR,colourG,colourB,CheckQueue);
                  }

      }
      
      public void rowFillQ(int x,int y,int width, int height,boolean[][] processedPixel,byte[][] frame,Integer Count,int colourR,int colourG,int colourB,LinkedList queue)
      {
            int sx=x;
            
            while (sx<width && !processedPixel[sx][y])
            {
                  count =Count.intValue()+1;
                  Count=new Integer(count);
                  frame[y*width+sx][0]=(byte) (colourR+count%15);
                  frame[y*width+sx][1]=(byte) (colourG+count%15);
                  frame[y*width+sx][2]=(byte) (colourB+count%15);
                  processedPixel[sx][y]=true;
                  sx++;
            }
            if (y>0)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y-1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y-1]) tx--;
                              queue.add(new Item(tx+1,y-1));
                        }
                  }
            }
            if (y<height-1)
            {
                  for (int i=x;i<sx;i++)
                  {
                        if (!processedPixel[i][y+1])
                        {
                              int tx=i;
                              while (tx>0 && !processedPixel[tx][y+1]) tx--;
                              //rowFill(tx+1,y+1,width,height, processedPixel,frame,count,colourR,colourG,colourB);
                              queue.add(new Item(tx+1,y+1));
                        }
                  }
            }
            
      }

I have re-calculated the each algorithm times using a large image (1792x1200)

Recusive Row Fill: FAILED (Stack Overflow)
Queued Row Fill: 6496 msec
Linear Row Fill: FAILED (Stack Overflow)
Queued Flood Fill 8 dirs: 33047 msec
Queued Flood Fill 4 dirs: 14140 mesc
Wall Following Fill: 1328 msec

hmm, it is looking like my wall following fill is the best peformer on average. (i.e. linear Flood Fill easily beats it on small areas, however fails on larger areas, while my wall following fill seems to work very well on large areas)

It looks like i will be staying with the wall following fill unless anyone knows of another filling aglorithm.

#6

I think your queue is hurting your performance. All that new’ing of Items adds up. There is no need to use a queue as a stack will do the same. You can implement you own stack using an int array. It’s easy, just double the stack size when it needs to grow.

This way you will hopefully get the same execution time as the recursive versions, but without the stack overflows.

#7

hmm, i was thinking the same thing (that the new operation was the bottleneck)

you suggest an int array? i would need to use two i am thinking, one for the x co-ordinate and one for the y co-ordinate.

I will impelment the array stack (for all the algorithms) and see what the performance is like.

Cheers

#8

i have implemented a stack of my own based on int arrays… however it has had a major negative impact on peformance.



      class MyStack
      {
            int[] x;
            int[] y;
            int index;
            public MyStack()
            {
                  x= new int[1024];
                  y= new int[1024];
                  index=0;
            }
            
            public int size()
            {
                  return index;
            }
            
            public void add(int x1,int y1)
            {
                  if (index==x.length)
                  {
                        int[] temp= new int[2*x.length];
                        System.arraycopy(x,0,temp,0,x.length);
                        x=temp;
                        temp= new int[2*y.length];
                        System.arraycopy(y,0,temp,0,y.length);
                        y=temp;
                  }
                  x[index]=x1;
                  y[index]=y1;
                  index++;
            }
            
            public int getX() throws Exception
            {
                  return x[index-1];
            }
            
            public int getY() throws Exception
            {
                  return y[index-1];
            }
            
            public void remove() throws Exception
            {
                  index--;
            }
      }

the wall following algorithm using MyStack gives 37547 msecs as compared to the previous 1328.

The Flood Fill using My stack comes to 37672 msec which is worse than using the queue ( 4 direction )

Is there something inheritly wrong with my stack?

#9

[quote]However it seems cause stack overflows when filling large areas
[/quote]
I think it has some bugs.


if(LFillLoc<=0 || (PixelsChecked[LFillLoc][y]))
if(RFillLoc>=width || (PixelsChecked[RFillLoc][y]))
if(y>0 && (!(PixelsChecked[i][y-1])))
if(y<(height-1) &&  (!(PixelsChecked[i][y+1])))

All of the listed lines are missing a check to see if it is still inside the fill area.

Here is my version: (memeber variables not listed)


      private void linearFloodFill4(int x, int y) {
            int LFillLoc=x;
            while (true) {
                  image[y][LFillLoc] = fillcolor;
                  pixelsChecked[y][LFillLoc] = true;
                  LFillLoc--;
                  if (LFillLoc<=0 || (image[y][LFillLoc] != startcolor) || (pixelsChecked[y][LFillLoc]))
                        break;
            }
            LFillLoc++;
            int RFillLoc=x; 
            while (true) {
                  image[y][RFillLoc]=fillcolor;   
                  pixelsChecked[y][RFillLoc] = true;
                  RFillLoc++;
                  if (RFillLoc>=width || (image[y][RFillLoc] != startcolor) || (pixelsChecked[y][RFillLoc]))
                        break;
            }
            RFillLoc--;
            for (int i=LFillLoc;i<=RFillLoc;i++) {
                  if ((y>0) && (image[y-1][i]==startcolor) && !pixelsChecked[y-1][i]) {
                        linearFloodFill4(i, y-1);
                  }
                  if (y<(height-1) && (image[y+1][i] == startcolor) && !pixelsChecked[y+1][i]) {
                        linearFloodFill4(i, y+1);
                  }
            }
      }

[quote]A person suggested filling by rows, i.e. go left->right filling pixels until you hit a boundary pixel. then look above you to see if there are row(s) that are to be filled and then fill each of those.
[/quote]
This is exactly what the linear flood fill does.

[quote]I think your queue is hurting your performance.
[/quote]
I take that back. I implemented a non recursive linear flood fill using an array of int stack and a linked list. The linked list version was much faster.

As a conclusion I will suggest to get the linear flood fill working. It should not be as heavy on the stack as other methods. However, here is a non recursive version, if you still get stack overflows:


      public void linearFloodFill(int startx, int starty, int image[][], boolean pixelsChecked[][], int fillcolor) {
            LinkedList stack = new LinkedList();
            int height = image.length;
            int width = image[0].length;
            int startcolor = image[starty][startx];
            stack.addLast(getLineSeg(startx, starty, width, image, pixelsChecked, startcolor, fillcolor));
            while (stack.size() > 0) {
                  LineSeg nextLine = (LineSeg) stack.getLast();
                  if (nextLine.x >= nextLine.right) {
                        if (nextLine.doneTop == 0) {
                              nextLine.x = nextLine.left;
                              nextLine.doneTop = 1;
                        } else {
                              stack.removeLast();
                        }
                  }
                  int x = nextLine.x;
                  int y = nextLine.y;
                  nextLine.x++;
                  if (nextLine.doneTop == 0) {
                        if ((y>0) && (image[y-1][x]==startcolor) && !pixelsChecked[y-1][x]) {
                              stack.addLast(getLineSeg(x, y-1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  } else {
                        if ((y<height-1) && (image[y+1][x]==startcolor) && !pixelsChecked[y+1][x]) {
                              stack.addLast(getLineSeg(x, y+1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  }
            }
      }

      private LineSeg getLineSeg(int x, int y, int width, int image[][], boolean pixelsChecked[][], int startcolor, int fillcolor) {
            int left=x;
            while (true) {
                  image[y][left] = fillcolor;
                  pixelsChecked[y][left] = true;
                  left--;
                  if (left<=0 || (image[y][left] != startcolor) || (pixelsChecked[y][left])) {
                        break;
                  }
            }
            left++;
            int right=x; 
            while (true) {
                  image[y][right]=fillcolor;   
                  pixelsChecked[y][right] = true;
                  right++;
                  if (right>=width || (image[y][right] != startcolor) || (pixelsChecked[y][right])) {
                        break;
                  }
            }
            right--;
            return new LineSeg(left, right, y);
      }

      class LineSeg {
            int left, right, x, y, doneTop;
            LineSeg(int left, int right, int y) {
                  this.left = left;
                  this.right = right;
                  this.x = left;
                  this.y = y;
            }
      }

Hope this helps. Although I’m not sure if it’s faster than your wall following method :slight_smile:

#10

Correction. The linearFloodFill method should look like this:


      public void linearFloodFill(int startx, int starty, int image[][], boolean pixelsChecked[][], int fillcolor) {
            LinkedList stack = new LinkedList();
            int height = image.length;
            int width = image[0].length;
            int startcolor = image[starty][startx];
            stack.addLast(getLineSeg(startx, starty, width, image, pixelsChecked, startcolor, fillcolor));
            while (stack.size() > 0) {
                  LineSeg nextLine = (LineSeg) stack.removeLast();
                  int y = nextLine.y;
                  int right = nextLine.right;
                  for (int x=nextLine.left; x<=right; x++) {
                        if ((y>0) && (image[y-1][x]==startcolor) && !pixelsChecked[y-1][x]) {
                              stack.addLast(getLineSeg(x, y-1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  }
                  
                  for (int x=nextLine.left; x<=right; x++) {
                        if ((y<height-1) && (image[y+1][x]==startcolor) && !pixelsChecked[y+1][x]) {
                              stack.addLast(getLineSeg(x, y+1, width, image, pixelsChecked, startcolor, fillcolor));
                        }
                  }
            }
      }

Now it executes almost at the same speed as the recursive version. Only a 5% overhead because of the linked list.

#11

Thanks! your effort in creating a working implementation was unexpected is very much appreciated!

I will try your method and see if i gain processing speed.

will let you know.

#12

I have implemented a slighyly modified version of your code :slight_smile:

the changes:

image -> frame
checkedPixel[][] now [x][y] instead of [y][x]
checkedPixel contains the boundary points when first sent the the flood fill algorithm
added green shading for a processed pixel


      public void linearFloodFill(int startx,int starty,int width, int height,boolean[][] pixelsChecked,byte[][] frame) { 
       LinkedList stack = new LinkedList(); 
       int fcount=0; 
       stack.addLast(getLineSeg(startx, starty, width, frame, pixelsChecked,fcount)); 
       while (stack.size() > 0) { 
        LineSeg nextLine = (LineSeg) stack.removeLast(); 
        int y = nextLine.y; 
        int right = nextLine.right; 
        for (int x=nextLine.left; x<=right; x++) { 
         if ((y>0)  && !pixelsChecked[x][y-1]) { 
            stack.addLast(getLineSeg(x, y-1, width, frame, pixelsChecked,fcount)); 
         } 
        } 
    
        for (int x=nextLine.left; x<=right; x++) { 
         if ((y<height-1) && !pixelsChecked[x][y+1]) { 
            stack.addLast(getLineSeg(x, y+1, width, frame, pixelsChecked,fcount)); 
         } 
        } 
       } 
      }
      
      private LineSeg getLineSeg(int x, int y, int width, byte[][] frame, boolean pixelsChecked[][],int fcount) { 
       int left=x; 
       while (true) { 
        //image[y][left] = fillcolor; 
        fcount+=5;
        frame[y*width+left][0]=(byte) 0;
        frame[y*width+left][1]=(byte) (50+fcount%55);
        frame[y*width+left][2]=(byte) 0;
        pixelsChecked[left][y] = true; 
        left--; 
        if (left<=0 || (pixelsChecked[left][y])) { 
         break; 
        } 
       } 
       left++; 
       int right=x;  
       while (true) { 
        //image[y][right]=fillcolor;
        fcount+=5;
        frame[y*width+left][0]=(byte) 0;
        frame[y*width+left][1]=(byte) (50+fcount%55);
        frame[y*width+left][2]=(byte) 0;    
        pixelsChecked[right][y] = true; 
        right++; 
        if (right>=width || (pixelsChecked[right][y])) { 
         break; 
        } 
       } 
       right--; 
       return new LineSeg(left, right, y); 
      } 
 
      class LineSeg { 
       int left, right, x, y, doneTop; 
       LineSeg(int left, int right, int y) { 
        this.left = left; 
        this.right = right; 
        this.x = left; 
        this.y = y; 
       } 
      }

however it seems to be not filling each row correcty… and more than likely a problem due to my modifications :stuck_out_tongue: I cannot see the error myself, maybe you can?

see www.geocities.com/budgetanime/lena.tif.txt for an example of what i mean.

#13

damn you copy&paste! ;D

The problem was that when i copied:


        frame[y*width+left][0]=(byte) 0; 
        frame[y*width+left][1]=(byte) (50+fcount%55); 
        frame[y*width+left][2]=(byte) 0;

for the right fill, i forgot to chage the left variable to right ::slight_smile:

now for some comparisons…

#14

Looks good!!

for all the tests i run with both my wall following and your linear flood fill, your flood fill consistantly peformed faster than my wall following in some cases 50% or more. This is the same as for the original linear flood fill earlier in this post.

The good news is that your version is superior to the previous version as you implement your own stack and thus have no overflow errors. (worked on images 2360x2100)

thanks heaps!

#15

[quote]checkedPixel[][] now [x][y] instead of [y][x]
[/quote]
I used [y][x] because the algorithm iterates over the x variable. Then it will touch only memory in the same area, and that can give better cach performance. But I haven’t tested it so the gain is probably to smal to notice. But the other thing is that you can do this: “boolean line[] = checkedPixels[y]”. This will reduce array lookups.

I’ve also come up with a new optimazation that increased the speed with ~25%. It’s where the new LineSeg is added to the stack. X is set to newLineSeg.right, because it’s known that all pixels to the left is set. Also the loop is getting so tight that an int[] stack implementation is another 20% faster than the LinkedList. Here is the latest int[] stack version. It’s hopefully twice as fast as the last one I posted :slight_smile:

The stack:


      private static final int elementSize = 4;
      private static final int xOff           = 0-elementSize;
      private static final int yOff           = 1-elementSize;
      private static final int leftOff       = 2-elementSize;
      private static final int rightOff   = 3-elementSize;

      class LineSegStack {
            int[] data; 
            int size = 0;
            int offset; 
            
            public LineSegStack() {
                  data= new int[1024*elementSize]; 
                  offset=0; 
            } 

            public void push(int left, int right, int y) {
                  if (offset == data.length) {
                        int[] temp = new int[2*data.length]; 
                        System.arraycopy(data, 0, temp, 0, data.length); 
                        data = temp; 
                  }
                  offset+=elementSize; 
                  data[offset+leftOff] = left;
                  data[offset+rightOff] = right;
                  data[offset+xOff] = left;
                  data[offset+yOff] = y;
                  size++;
            } 

            public void pop(LineSeg s) {
                  s.x = data[offset+xOff];
                  s.y = data[offset+yOff];
                  s.left = data[offset+leftOff];
                  s.right = data[offset+rightOff];
                  offset -= elementSize; 
                  size--;
            }
      } 



 // members are initalized in constructor
      private int fillcolor = 0xffff00ff;
      private boolean pixelsChecked[][]; //[y][x]
      private int image[][]; //[y][x]
      private int startcolor = 0xffffffff;
      private int startx = 0;
      private int starty = 0;
      private int width;
      private int height;
      private LineSegStack stack = new LineSegStack();
      

public long floodStack() {
            LineSeg nextLine = new LineSeg(0, 0, 0);
            addLineSegToStack(startx, starty);
            while (stack.size > 0) {
                  stack.pop(nextLine);
                  int y = nextLine.y;
                  int right = nextLine.right;
                  if (y>0) {
                        int topLine[] = image[y-1];
                        boolean topChecked[] = pixelsChecked[y-1];
                        for (int x=nextLine.left; x<=right; x++) {
                              if ((topLine[x]==startcolor) && !topChecked[x]) {
                                    x = addLineSegToStack(x, y-1);
                              }
                        }
                  }
                  
                  if (y<height-1) {
                        int botLine[] = image[y+1];
                        boolean botChecked[] = pixelsChecked[y+1];
                        for (int x=nextLine.left; x<=right; x++) {
                              if ((botLine[x]==startcolor) && !botChecked[x]) {
                                    x = addLineSegToStack(x, y+1);
                              }
                        }
                  }
            }
      }
      
      private int addLineSegToStack(int x, int y) {
            int line[] = image[y];
            boolean checked[] = pixelsChecked[y];
            int left=x;
            do {
                  line[left] = fillcolor;
                  checked[left] = true;
                  left--;
            } while (left>=0 && (line[left] == startcolor) &&  !checked[left]);
            left++;
            int right=x; 
            do {
                  line[right]=fillcolor;   
                  checked[right] = true;
                  right++;
            } while (right<width && (line[right] == startcolor) && !checked[right]);
            right--;
            stack.push(left, right, y);
            return right;
      }

Enjoy!

#16

I have implemented your latest vesion.

I have quite interesting results:


            image size   Flood_new   Flood_old   Wall_Follow 
 
            640x337         172         78           105 
            512x512         140         78           141 
            1280x1024       203         609          985 
            2482x2688       1390        6110         5344

where:
Flood_new is your latest Linear Flood Fill Alg
Flood_old is your previous Linear Flood Fill Alg
and Wall_Follow is my wall following algorithm.

Time is measured in millisec and is the avg of 5 runs.

It seems for lower resolution images, your first method seems to out peform your newer version, however it is drastically faster once the image starts getting large.

There must be an inital over head with your second method which becomes less of an impact when more pixels are processed.

#17

and that the old method seems to get progressivly worse as compared to the wall following as the image gets very large.

#18

The only extra overhead with the new method is the int stack. You could try reusing it, if thats acceptable. Make it a static member, and reset it at the start of the flood fill. Reducing the inital stack size on smal images might also help.

Not sure why the old method slows downs that much.

There is one more improvement that can be made to the algorithm. It is to not check for “collision” from where it come from. Here’s an extract from the code:


if (y>0) {
 // fill the line above this line
      int topLine[] = image[y-1];
      boolean topChecked[] = pixelsChecked[y-1];
  // did we come from there?
      if (nextLine.fromtop == 1) {
   // check on the left side of where we come from
            int min = Math.min(nextLine.prevleft, right);
            for (int x=nextLine.left; x<=min; x++) {
                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                  }
            }
   // check on the right side of where we come from
            for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {
                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                  }
            }
      } else {
  // did not come from this side: check the whole line
            for (int x=nextLine.left; x<=right; x++) {
                  if ((topLine[x]==startcolor) && !topChecked[x]) {
                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                  }
            }
      }
}

Gave me a 10-15% improvement.

#19

Wow! :o just by using the same instance of the stack the fill operation has improved effeciency another 50% (the 512x512 image is filled in 68 msec and the 2482x2688 is filled in 609 msec.

From the latest code snippet, related to the do not “collision” detect from the line you have come from, i am unsure how the extra parameters are used in addLineSegToStack.

i.e. addLineSegToStack(x, y-1, nextLine.left, right, 0)

#20

Well, it has kind of a cascading effect, so everything is changed. I’ll post the changes.


class LineSeg:
// additianal members.
int prevleft, prevright, fromtop;

class LineSegStack:
private static final int elementSize = 7; // changed
private static final int prevleftOff  = 4-elementSize; // added
private static final int prevrightOff = 5-elementSize; // added
private static final int fromtopOff   = 6-elementSize; // added

// 3 extra paramters
public void push(int left, int right, int y, int prevleft, int prevright, int fromtop) {
 ...
 data[offset+prevleftOff] = prevleft;
 data[offset+prevrightOff] = prevright;
 data[offset+fromtopOff] = fromtop;
 ...
} 

public void pop(LineSeg s) {
...
s.prevleft = data[offset+prevleftOff];
s.prevright = data[offset+prevrightOff];
s.fromtop = data[offset+fromtopOff];
}

// addLineSegToStack(): only change is that the 3 extra parametrs are pushed on the stack
private int addLineSegToStack(int x, int y, int prevleft, int prevright, int fromtop) {
...
stack.push(left, right, y, prevleft, prevright, fromtop);
return right;
}

// the meat of floodStack(), which has grown a bit:
            while (stack.size > 0) {
                  stack.pop(nextLine);
                  int y = nextLine.y;
                  int right = nextLine.right;
                  if (y>0) {
                        int topLine[] = image[y-1];
                        boolean topChecked[] = pixelsChecked[y-1];
                        if (nextLine.fromtop == 1) {
                              int min = Math.min(nextLine.prevleft, right);
                              for (int x=nextLine.left; x<=min; x++) {
                                    if ((topLine[x]==startcolor) && !topChecked[x]) {
                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                                    }
                              }
                              for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {
                                    if ((topLine[x]==startcolor) && !topChecked[x]) {
                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                                    }
                              }
                        } else {
                              for (int x=nextLine.left; x<=right; x++) {
                                    if ((topLine[x]==startcolor) && !topChecked[x]) {
                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);
                                    }
                              }
                        }
                  }
                  
                  if (y<height-1) {
                        int botLine[] = image[y+1];
                        boolean botChecked[] = pixelsChecked[y+1];
                        if (nextLine.fromtop == 0) {
                              int min = Math.min(nextLine.prevleft, right);
                              for (int x=nextLine.left; x<=min; x++) {
                                    if ((botLine[x]==startcolor) && !botChecked[x]) {
                                          x = addLineSegToStack(x, y+1, nextLine.left, right, 1);
                                    }
                              }
                              for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {
                                    if ((botLine[x]==startcolor) && !botChecked[x]) {
                                          x = addLineSegToStack(x, y+1, nextLine.left, right, 1);
                                    }
                              }
                        } else {
                              for (int x=nextLine.left; x<=right; x++) {
                                    if ((botLine[x]==startcolor) && !botChecked[x]) {
                                          x = addLineSegToStack(x, y+1, nextLine.left, right, 1);
                                    }
                              }
                        }
                  }
            }

prevleft, prevright and fromtop is used to remember where the function was called from. The you don’t need to test that area again.