Image Partitioning

Image compression and compression in general is a really interessting topic and although the algorithm I'd like to talk about goes into that direction the algorithm is not meant to be a compression in terms of memory but has been born out of the idea to reduce drawing calls by drawing as big rectangles as possible instead of each pixel on its own.

The problem to find as big same colored rectangles as possible in an image quickly became so interessting, that I decided to try it, even though I didn't know whether it would be faster or not.

result, heuristic and source

Heuristic:
The first problem to solve is to find a good places to look for big same colored rectangles. Humans can easily spot interessting regions very fast and without even really thinking about it. In my case the guessing is done with a heuristic that weights each pixel based on how manysame colored pixels occur in a row aswell as column.

private function runlengthY():Void
{
 for ( x in 0...this.heightmap.width )
 {  
  var y_length:Int = this.heightmap.height;
  var y:Int = 0;
  
  while( y < y_length ) // run aslong as still in the image
  { 
   var color:Int = this.heightmap.getPixel( x, y );    
   var length:Int = 1;
   
   while( y + length < y_length ) // how long is the column?
   {
    var next_color:Int = this.heightmap.getPixel( x, y + length );
    
    if ( next_color != color ) 
     break;     
    
    length++;
   }
   
   for ( set in 0...length ) // add weight for all pixels in column
   {
    var index:Int =  x + (y + set) * this.heightmap.width; 
    
    var pixel:PixelWeight = this.weightList[ index ];      
     pixel.weight += length;
   }
   
   y += length;
  }
 }
}

The methode above depicts the second half of the heuristic. The first part is basically the same, just along the x axis, counting row length instead of column length. The result of the heurisitc can be seen at the 2. image of the illustration. A brighter pixel is more promising to be within a big square than a dark one.

You can also see that there are several pixels marked as very good candidates although they are not or at least just under certain circumstances. For example the first white pixel after a lot of really dark ones at the very top in middle. It has a long column down with another white spot in an akward place, marked with a red square. The resulting rectangle of that spot is not as big as the color suggests and the reason for this is the way the rectangles are calculated. The difference might not dramatic in this particular case but it illustrates the issue. I'll come back to it.

Partitioning:
Once every pixel is weighted, I sort it and pick out the pixels with the heighest weight first and "grow" a rectangle around them. Each growing-step a new pixel row or column is aquired to the rectangle aslong as it still has the same color, is within the image bounds and not already part of another rectangle.

I always tried to keep the code short on this blog, but I think its worth it considering that this piece of code is pretty much the whole algorithm. Its about code damned!

private function expandRec( rec:Rectangle, directionList:Array<StepDirection>, color:Int ):Rectangle
{  
 var direction:StepDirection = directionList[0];  
 directionList.push( directionList.shift );
 
 var expandedRec:Rectangle = this.calculateExpansion( rec, direction ); 
 var point:Point = this.calculateStartpoint( expandedRec, direction );   
 
 if ( this.heightmap.rect.containsRect( expandRec ) )        
  return this.retryExpand( rec, directionList, color );
 
 // -------------------------- // 
 
 var assignList:Array<PixelWeight> = new Array<PixelWeight>();  
 
 var maxSteps:Int = direction.isVertical ? Std.int(rec.width) : Std.int(rec.height);
 var counter:Int = 0;
 
 while ( counter++ < maxSteps )
 {
  var pixel:PixelWeight =  this.weightList[point.x + point.y * this.heightmap.width]; 
  
  if ( pixel.assigned )          
   return this.retryExpand( rec, directionList, color );
  
  var check:Int = this.heightmap.getPixel( point.x, point.y );
  
  if ( check != color )          
   return this.retryExpand( rec, directionList, color ); 
  
  // -------------------------- //
  
  if ( direction.isVertical ) point.x++;
  else       point.y++;
  
  assignList.push( pixel );  
 }  
 
 // ------------------------------- // 
 
 for ( assignPixel in assignList )
  assignPixel.assigned = true;
 
 return this.expandRec( expRec, directionList, color );
}

Line 3 and 4 are already the reason why some rectangles didn't grow as big as they could have. Here I pick into which direction the rectangle should expand. directionList contains 4 directions beginning with top, ordered clockwise. So each expand iteration another direction gets its shot, if the current expansion fails for any reason (color, already in another list or simply out of bounds) the current direction gets removed from the list (retryExpand). Once the list is empty the biggest rectangle with the given startingpoint has been found.

growing order

So the reason why the red marked spot doesn't create such a big rectangle is, because it first tried to expand up and then right. But because it expanded up first, the pixel column to the right is no longer of the same color only so the entire direction is dead already. Away to solve this issue could be to save also a side preference for each PixelWeight and try that direction first before any other one. Another idea could be to simply randomly choose directions, try it several times and stick to the best result. Maybe there is a smarter way to do all of it but so far I'm happy enough to let it be.

The performance is again not good for anything big or really noisy. I suspect the reason for this is mainly the stack festival caused by the recusive calls of expand and maybe even the thick datastructure for storing the weight of each pixel and sorting it. Maybe thats not an issue at all.

Same rule like last time: Performance is not the point of this post. I might talk about it once I played more with the algorithm or even have an actual use case.

Demo
Source