mosaic.cpp

Go to the documentation of this file.

//==============================================
//  copyright            : (C) 2003-2005 by Will Stokes
//==============================================
//  This program is free software; you can redistribute it
//  and/or modify it under the terms of the GNU General
//  Public License as published by the Free Software
//  Foundation; either version 2 of the License, or
//  (at your option) any later version.
//==============================================
 
//Systemwide includes
#include <qimage.h>
#include <qstring.h>
#include <qapplication.h>
#include <cstdlib>
#include <time.h>
#include <math.h>
 
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) < (y) ? (x) : (y))
 
//Projectwide includes
#include "mosaic.h"
#include "manipulationOptions.h"
#include "../tools/imageTools.h"
#include "../../gui/statusWidget.h"
 
#include <iostream>
using namespace std;
 
//----------------------------------------------
// Inputs:
// -------
// QString filename -       location of original image on disk
// MosaicOptions* options - various options that will be used like tile size, filenames 
//                          that can be used to create an image-based tile set, and a pointer
//                          to the status widget for alerting the user about progress.
//
// Outputs:
// --------
// QImage* returned - constructed image
//
// Motivation:
// -----------
// Where do I start? I suppose I'll begin with my motivation to write 
// this manipulation. Then touch on stuff I looked at while formulating my 
// approach, then descrive in gory detail how this actually works.
//
// While getting my masters in computer graphics at the Cornell Program of 
// Comptuer Graphics ( http://www.graphics.cornell.edu ), I would see a photo 
// mosaic of Don Greenberg in the hall every day:
//
// http://www.acm.org/tog/editors/erich/DPG/DPG_mosaic.jpg
//
// The photo was printed out all big and put on the wall at the end of a semi-long
// hallway. If you came up the stairs at the other end of the hallway it 
// seriously looked just like Don, despite being made up of lots of tiny 
// pictures of people who at some point or other were students at the PCG. 
// Several of us figured this looked like a pretty simple algorithm to write.
// For each chunk of pixels you're going to smack a tile down on simply get 
// the average brightness and use the tile that best matches the brightness for 
// that area. It turns out to be a slightly more difficult problem. First, Eric 
// Haynes, or created the Don photomosaic, kinda cheated by using grayscale 
// instead of color. Color matching is a bit trickier. Second, simply picking 
// the best tile to use at any location can result in various aliasing 
// artifacts I'll get to later.
//
// So anyways, that was my motivation, sadly I didn't find this page which 
// descrives how Eric created the mosaic until after I finished my technique, 
// although I'm not sure it would change how I did it anyways.
//
// http://www.acm.org/tog/editors/erich/DPG/DPG.html
//
// Prior Art:
// ----------
// Photo mosaics are neither a novel or new techinque. They've been around for 
// years, but how you accomplish them seems to vary like crazy. Creating grayscale
// photomosaics is a much simpler process than using color for a few reasons. When
// creating color photomosaics you not only need to match luminance but also the 
// average hue and saturation for any region. Creating a good tileset is even trickier. 
// If you are working with 256 gray levels it isn't that hard to construct a tile 
// set that spans the entire range of luminance values. However, creating a tileset 
// that spans the 256 x 256 x 256 = 16,777,216 range of color values is simply out 
// of the question. Not only will finding a good set of tiles be difficult, but even 
// if we get a decent set of tiles together it is clear we'll need to adjust them for 
// each use in order to get them to match up better.
//
// But before get ahead of myself, before I started designing my own photo 
// mosiac algorithm I studied a few others. First, I found there are quite a few 
// programs out there, but most cost a few bucks to try out, so being the cheap 
// person I am I based a lot of my "research" on surfing around and looking at 
// these programs output. I was particuarly impressed with Andrea Mosaic:
//
// http://www.andreaplanet.com/andreamosaic/
//
// Unfortunately it is closed source. The only source code I looked at was 
// the pmosaic gimp plugin:
// http://www.kirchgessner.net/photo-mosaic.html#DETAIL
//
// Approach:
// ---------
// I wasn't too impressed with this latter link, although it was nice to actually
// look at some code. What I figured thus far was that I would develop an algorithm 
// that supported generated color photo mosaics and that meant picking the best tile 
// to splat down using a distance quantity loosely based on 3d coordinates using the 
// red, green, and blue color values, such as:
//
// D = sqrt( dr*dr + dg*dg + db*db );
//
// where d[r,g,b] refer to the difference in red/green/blue values between the 
// source image and a particular tile. This quantity could either be computed at each 
// pixel for a given tile with respect to the original image and averaged, or the
// average color for the tile and the region of hte image the tile woudl be smacked
// onto could be precomputed, making computing the distance quantity substantially faster.
//
// I actually experimented with both approaches and was fairly happy with 
// the results provided by both of them. However; my perception background told 
// me computing the distance in 3-space like this wasn't exactly right because our
// eyes are more sensative to variation in the green component then the red and 
// the blue. I forget how, but I stumbled on this alternative techinque for 
// computing the distance in color space:
//
// http://www.compuphase.com/cmetric.htm
// D = sqrt {  [2 + rbar/256 ]*dR*dR   +  4*dG*dG  +  [2 + (255-rBar) / 256]*db*dB  }
//
// This is an approximate to a properly weighted Euclidean distance function. 
// In my actual implementation I don't take the square root. If I simply picked
// the tile with the smallest distance that probably woudl work just fine, but 
// I pick probablisitically, so in theory I'm biasing myself too much towards 
// tiles that very closely match the color I'm looking for, but it appears to work 
// just fine regardless and saves a few cycles.
//
// Algorithm:
// ----------
// So, I should wrap this up with an outline of how a photomosaic is created:
//
// 1.) "mosaicEffect" is called and provided an image filename and a collection of options
//
// 2.) A tileset is constructed in one of two ways. If one or more filenames 
//     for tiles has been provided in the options an image-based tileset is 
//     constructed using "constructImageTiles." Otherwise a solid-color based 
//     tileset is created using "constructColorTiles."
//
// 3.) The manipulation was first developing using solid-color tilesets, then 
//     extended to support image-based tilesets. I'm not sure if people want to 
//     use solid color tilesets, but they are useful for providing a fast manipulation 
//     preview without any user intervention (like specifying what images ot ue for 
//     tiles) while still conveying the effect the manipulation will have on the source image.
//
// So, how to create a color tileset. I've find old-school web pallettes did well 
// using 216 colors that span the entire color gammut by equally spacing the red, 
// green, and blue color components from 00 to FF spaced by 51 (aka 00, 33, 66, 
// 99, CC, FF). That's 6 unique red, green, and blue, or 6^3 = 216 unique colors. 
// For each color I simply fill a tile with that color.
//
// Image tile sets are a bit more complicated. A list of filenames are passed in as 
// one of the options. In order to avoid creating too many tiles we randomly 
// pick no more than MAX_TILES (216) of these files for creating image tiles.
//
// Once a chosen list has been created, it is time to create the actual image 
// tiles. For each tile I scale it down so that it still fills the tile, but 
// still is larger in one of the two dimensions. Scaling down to the exact 
// tile dimensions would result in skewing the aspect ratio and would be a big no-no.
//
// The scaled image is then ceneter and cropped to fit the specified tile size.
//
// While creating the tile, we also compute the average red, green, and blue 
// color value, in addition to the average luminance and saturation (but not hue).
//
// 4.) Once a tileset has been constructed, it is time to start smacking tiles 
//     down. We iterate over blocks of the image to put tiles onto. For each 
//     image block we compute the average color, hue, luminance, and saturation. 
//     The distance between each tile and the image block is computed using the 
//     average color data only.
//
// Now, at this point we could simply pick the tile that has the shortest 
// distance (most closely matches the intended color), and while I experimented 
// with this at first, I quickly ran into trouble. Smooth gradations in the source 
// image resulted in sudden changes from one tile to the next one surfaces like 
// walls. For example, if the wall behind a subject had luminances that look like this:
//
// 255 255 240  220 200 180 180 180
// 255 255 240  220 200 180 180 180
// 255 255 240  220 200 180 180 180
//
// I'd notice the tiles that are used woudl suddenly change like so:
//
// A A B B C C C C
// A A B B C C C C
// A A B B C C C C
//
// The resulted image looks weird, almost like egdes has been created where edges 
// were not located before. Instead of simply picking the best tile, I decided to 
// use a pseudo-random approach. The reciprocal distances are first computed, then 
// summed. A random number if picked bewteen 0-sumRecipDistance and distates which 
// tile will be used. By defintion, tiles that have small distances will have the 
// largest reciprocal distances and thus are most likely to be picked. A tile with 
// a large distance will be a tiny reciprocal distance and will almost certainly not 
// be picked. This results in a slow change from using A to B to C like this;
//
// A B B B B C C C
// A A A C C C C C
// A B B B C C C C
//
// The change is "blurred" so to speak and "blooming" like effects don't show up any more.
//
// Ok, so at this point we can pick the tile to spat, but how do we splat it? If we 
// simply pasted the tile directly we'd see:
// -a shift in hue
// -a shift in luminance
// -a shift in saturation
//
// If we simply converted the RGB color of each tile pixel to HSV and replaced the 
// HSV values we simply be pasting down a solid color and that woudln't do us much good :-)
//
// We want to see the small pictures still, that means keeping the variation in luminance 
// and saturation, while most closely matching the hue. Our distance techinque will 
// help us pick tiles that don't differ in hue much, so replacing the hue at each pixel 
// with the hue we want will help us achieve the hue we need without causing too much damage.
//
// We can match the average luminance and saturation by simply shifting all saturation 
// and luminance values by the differnce in the averages between the image chunk and 
// the chosen tile. The result is a tile that will provide the desired hue, and when 
// you consider all tile pixels the same average saturation and luminance. Meaning 
// if you stand back the top level image will look great, but if you get up close 
// you can still see all the details of the source tile images.
//
// Future Work:
// ------------
// There are a few things that could be explored in the future:
//
// -A better tile picking algorithmn that considers the average hue of potential 
//  tile images and what hues have not been found already, thus producing a better 
//  tile hue gammut.
//
// -Exploring the use of outlines between tiles (like a white pixel border), or 
//  even other tile shapes than rectangles like puzzle pieces. Personally I consider 
//  these effects gimmicky, they detract from the overall image which I don't like.
//
// -A differnt distance-based picking algorthm that just works in the hue domain. 
//  I'm not sure this is a good thing since the current approach also most closely 
//  matches luminance and saturation making any modifications along these dimensions 
//  minimal, and minimally changing the tile images is a good thing.//
//----------------------------------------------
 
 
//====================================================
MosaicOptions::MosaicOptions( QStringList files, QSize tileSize, StatusWidget* status ) 
                            : ManipulationOptions( status )
{
  this->files = files;
  this->tileSize = tileSize;
}
QStringList MosaicOptions::getFileList() { return files; }
QSize MosaicOptions::getTileSize() { return tileSize; }
//====================================================
 
//a decent color set uses 216 colors
#define MAX_TILES 216
 
//==============================================
struct Tile
{
  //tile image
  QImage image;
  
  //average color
  QColor avgColor;
  
  //average saturation, and luminosity
  int avgS, avgL;
};
//==============================================
struct TileSet
{
  //tiles
  Tile tiles[MAX_TILES];
  
  //number of initialized tiles in set
  int numInitialized;
};
//==============================================
//create to tilesets. color tiles will be used for fast previews,
//image tiles will be used when actually applying the effect
TileSet colorTiles;
TileSet imageTiles;
//==============================================
//declare these functions here, we'll define them below
void constructColorTiles(QSize tileSize);
void constructImageTiles(QStringList files, QSize tileSize);
void splatBestTile(QImage* image, QPoint topLeftCorner, TileSet* tileSet);
//==============================================
QImage* mosaicEffect( QString filename, MosaicOptions* options )
{
  //load image
  QImage* editedImage = new QImage( filename );
  
  //convert to 32-bit depth if necessary
  if( editedImage->depth() < 32 )
  {
    QImage* tmp = editedImage;
    editedImage = new QImage( tmp->convertDepth( 32, Qt::AutoColor ) );
    delete tmp; tmp=NULL;
  }
  
  //determine if busy indicators will be used
  bool useBusyIndicators = false;
  StatusWidget* status = NULL;
  if( options != NULL && options->getStatus() != NULL )
  {
    useBusyIndicators = true;
    status = options->getStatus(); 
  }
  
  //intialize seed using current time
  srand( unsigned(time(NULL)) );
  
  //determine tile size
  QSize tileSize;
  if(options == NULL) tileSize = QSize(6,6); //6 is big enough to be visible, but not so blocky the image looks bad
  else                tileSize =options->getTileSize();
  
  //construct tile set
  TileSet* tileSet = NULL;
  if( options != NULL && options->getFileList().size() > 0 )
  {
    constructImageTiles(options->getFileList(), tileSize);
    tileSet = &imageTiles;
  }
  else
  { 
    constructColorTiles(tileSize);
    tileSet = &colorTiles;
  }
 
  //setup progress bar
  if(useBusyIndicators)
  {
    QString statusMessage = qApp->translate( "mosaicEffect", "Applying Mosaic Effect:" );
    status->showProgressBar( statusMessage, 100 );
    qApp->processEvents();  
  }
 
  //update progress bar for every 1% of completion
  const int updateIncrement = (int) ( (0.01 * editedImage->width() * editedImage->height()) / 
                                      (tileSize.width() * tileSize.height()) );
  int newProgress = 0; 
 
  //iterate over each selected scanline 
  int x, y;
  for(y=0; y<editedImage->height(); y+=tileSize.height())
  {
    for( x=0; x<editedImage->width(); x+=tileSize.width())
    {
      //splat the best tile
      splatBestTile( editedImage, QPoint(x,y), tileSet );
     
      //update status bar if significant progress has been made since last update
      if(useBusyIndicators)
      {
        newProgress++;
        if(newProgress >= updateIncrement)
        {
          newProgress = 0;
          status->incrementProgress();
          qApp->processEvents();  
        }
      }
 
    }
  }
   
  //return pointer to edited image
  return editedImage;  
}
//==============================================
//Initialize a general color tile set using pure tones.
void constructColorTiles(QSize tileSize)
{
  //max tiles must be allocated across all colors, so find resolution we'll have for each color
  //channel (e.g. if max tiles is 100, 100^(1/3) ~= 4.6 so we'll use 4 unique red, green, and
  //blue color values for constructing tiles and use 4^3=64 tiles out of the 100 allocated
  int colorRes = (int)pow( MAX_TILES, 1.0/3 );
  
  //always include 0 and 255 so increment is always totalSpan/(count-1)
  int colorIncrement = 255 / (colorRes-1);
  
  colorIncrement = 51;
  
  //create actual tiles
  int tile=0;
  int r,g,b;
  for(r=0; r<=255; r+=colorIncrement)
  {
    for(g=0; g<=255; g+=colorIncrement)
    {
      for(b=0; b<=255; b+=colorIncrement)
      {
        colorTiles.tiles[tile].image.create( tileSize.width(), tileSize.height(), 32);
        colorTiles.tiles[tile].image.fill( qRgb(r, g, b) );
        
        colorTiles.tiles[tile].avgColor = QColor(r,g,b);
        
        int h;
        QColor(r,g,b).getHsv( &h, &(colorTiles.tiles[tile].avgS), &(colorTiles.tiles[tile].avgL) );
        tile++;
      }
    }
  }
  
  //setup number of initialized tiles
  colorTiles.numInitialized = tile;
}
//==============================================
//Initialize an image based tile set
void constructImageTiles(QStringList files, QSize tileSize)
{
  //---------------------------------  
  //setup number of initialized tiles
  imageTiles.numInitialized = MIN(files.size(), MAX_TILES);
  //---------------------------------  
  //create file index list, we'll use this to construct a
  //list of indices to the randomply picked files from the master list
  int* fileIndices = new int[imageTiles.numInitialized];
  int* fileIndicesUsed = new int[files.size()];
  int i;
  for(i=0; i<imageTiles.numInitialized; i++) { fileIndices[i] = -1;    }
  for(i=0; i<((int)files.size()); i++)              { fileIndicesUsed[i] = 0; }
  //---------------------------------  
  //pick the random files, updating the file indices list
  for(i=0; i<imageTiles.numInitialized; i++)
  {
    double percentage = ((double)rand()) / RAND_MAX;
    int fileNum = (int) (  (files.size() - (i+1)) * percentage);
    
    //correct index by offsetting by all files that have been picked before this one 
    int j = 0;
    int realFileNum = fileNum;
    while( fileNum >= 0)
    {
      if( fileIndicesUsed[j] == 1 )  { realFileNum++; }
      else                           { fileNum--;     }
       
      j++;      
    }
    
    //record file index into list
    fileIndices[i] = realFileNum;
    fileIndicesUsed[realFileNum] = 1;
  }
  
  //---------------------------------  
  //sort the file index list - bubble sort is fast enough right? :-)
  int j;
  for( i=imageTiles.numInitialized-1; i>0; i--)
  {
    for( j=0; j<i; j++)
    {
      if( fileIndices[j] > fileIndices[j+1] )
      {
        int tmp = fileIndices[j+1];
        fileIndices[j+1] = fileIndices[j];
        fileIndices[j] = tmp;
      }
    }
  }
  //---------------------------------  
  //construct truncated list of files that we'll use
  QStringList chosenFiles;
  QStringList::iterator it;
  int curFileIndex = 0;
  int nextDesiredFileIndex = 0;
  for(it = files.begin(); it != files.end(); it++ )
  {
    if( curFileIndex == fileIndices[nextDesiredFileIndex] )
    {
      chosenFiles.append( *it );
      nextDesiredFileIndex++;
      
      if( nextDesiredFileIndex >= imageTiles.numInitialized ) break;
    }
 
    curFileIndex++;  
  }
 
  //resetting numInitialized should not be necessary, we should have the right
  //number of files in chosenFiles, but as a sanity check, we'll reset it here again.
  imageTiles.numInitialized = MIN((int)chosenFiles.size(), imageTiles.numInitialized);
 
  //---------------------------------  
  //free up the temporary index list, it's nolonger needed since we now have an
  //actual list of the chosen files
  delete fileIndices;
  delete fileIndicesUsed;
  fileIndices = NULL;
  fileIndicesUsed = NULL;  
  //---------------------------------  
  //ok, we now have a list of files we actually want to use to create tiles from, that have
  //been randomly chosen from the huge list we were given. now actually create the tiles
  int tile = 0;
 
  for(it = chosenFiles.begin(); it != chosenFiles.end(); it++ )
  {
    //scale image to definately fill a tileSizeW x tileSizeH region, we'll crop down afterwards
    QSize imageRes;
    getImageSize( *it, imageRes );
  
    int intermediateWidth = -1;
    int intermediateHeight = -1;
    if( ((double)imageRes.width()) / tileSize.width() > ((double)imageRes.height()) / tileSize.height() )
    {
      intermediateHeight = tileSize.height();
      intermediateWidth = (int) ( ((1.0*intermediateHeight*imageRes.width()) / imageRes.height()) + 0.5 );
    }
    else
    {
      intermediateWidth = tileSize.width();
      intermediateHeight = (int) ( ((1.0*intermediateWidth*imageRes.height()) / imageRes.width()) + 0.5 );
    }
    
    QImage scaledImage;
    scaleImage( *it, scaledImage, intermediateWidth, intermediateHeight );
    
    //scaleImage does not like to scale more than 2x, so if image is not the right size scale it up again
    if( scaledImage.width() != tileSize.width() || scaledImage.height() != tileSize.height() )
      scaledImage = scaledImage.scaled( tileSize, Qt::IgnoreAspectRatio );
    
    //construct tile image
    imageTiles.tiles[tile].image.create( tileSize.width(), tileSize.height(), 32);
    imageTiles.tiles[tile].image.fill( qRgb(255,255,255) );
            
    //crop scaledimage to tileSizeW x tileSizeH - simultaniously compute statistics about tile
    int xOffset = (scaledImage.width()  - tileSize.width())/2;
    int yOffset = (scaledImage.height() - tileSize.height())/2;
    int x, y;
    uchar* scaledScanLine;
    uchar* croppedScanLine;
    QRgb* scaledRgb;
    QRgb* croppedRgb;
     
    double avgR=0; double avgG=0; double avgB=0;
    double avgS=0; double avgL=0;
 
    //sometimes corrupt images can get through, so this check
    //bulletproofs the code
    if( scaledImage.isNull() )
    {
      avgR = avgG = avgB = 255;
      avgS = avgL = 255;
    }
    else
    {
      for( y=0; y<tileSize.height(); y++)
      {
        scaledScanLine  = scaledImage.scanLine(y + yOffset);
        croppedScanLine = imageTiles.tiles[tile].image.scanLine(y);
        
        for( x=0; x<tileSize.width(); x++)
        {
          scaledRgb  = ((QRgb*) scaledScanLine) +x + xOffset;
          croppedRgb = ((QRgb*) croppedScanLine)  + x;
          
          //copy pixel color over
          *croppedRgb = *scaledRgb;
          
          //update statistics
          QColor color( *croppedRgb );
          
          avgR += color.red();
          avgG += color.green();
          avgB += color.blue();
          
          int h,s,l;
          color.getHsv( &h, &s, &l );
          avgS += s;
          avgL += l;
        }
      }
      
      //average red, green, blue, saturation, and luminance sums
      int pixelCount = tileSize.width()*tileSize.height();
      avgR /= pixelCount;
      avgG /= pixelCount;
      avgB /= pixelCount;
      avgS /= pixelCount;
      avgL /= pixelCount;
    }    
    //store statistics    
    imageTiles.tiles[tile].avgColor = QColor( (int)avgR, (int)avgG, (int)avgB );
    imageTiles.tiles[tile].avgS = (int)avgS;
    imageTiles.tiles[tile].avgL = (int)avgL;
                            
    //move on to next tile
    tile++;
  }
  //---------------------------------  
}
//==============================================
//Pseudo-randomly pick the best tile from the specified tileset and splat
//it on the image
void splatBestTile(QImage* image, QPoint topLeftCorner, TileSet* tileSet)
{
  int x, y;
  QRgb* imageRgb;
  QRgb* tileRgb;
  uchar* imageScanLine;
  uchar* tileScanLine;
  //------------------------------  
  //dermine boundary we'll be iterating over
  int xMin = 0; 
  int xMax = MIN( tileSet->tiles[0].image.width(),   image->width() - topLeftCorner.x() );
  int yMin = 0;
  int yMax = MIN( tileSet->tiles[0].image.height(), image->height() - topLeftCorner.y() );
  //------------------------------   
  //find most common hue, and average color, saturation and luminance for this portion of the image 
  double avgR=0; double avgG=0; double avgB=0;
  int hueHist[361];
  int i;
  for(i=0; i<361; i++) { hueHist[i] = 0; }
  double avgS=0; double avgL=0;
  
  for( y=yMin; y<yMax; y++)
  {
    imageScanLine = image->scanLine(y+topLeftCorner.y());
    for( x=xMin; x<xMax; x++)
    {
      imageRgb = ((QRgb*)imageScanLine+x+topLeftCorner.x());
      QColor color( *imageRgb );
      
      avgR += color.red();
      avgG += color.green();
      avgB += color.blue();
      
      int h,s,l;
      color.getHsv( &h, &s, &l );
      hueHist[ MIN( MAX(h,0), 360 ) ]++;
      avgS += s;
      avgL += l;
    }
  }
  
  //average red, green, blue, saturation, and luminance sums
  int pixelCount = (yMax-yMin) * (xMax-xMin);
  avgR /= pixelCount;
  avgG /= pixelCount;
  avgB /= pixelCount;
  avgS /= pixelCount;
  avgL /= pixelCount;
  
  //walk through hue histogram and find most common hue
  int mostCommonHue = 0;
  for(i=1; i<361; i++)
  {
    if( hueHist[i] > hueHist[mostCommonHue] ) { mostCommonHue = i; }
  }
  
  //------------------------------  
  //compute distance between this region and all initialized tiles
  double* distances = new double[tileSet->numInitialized];
  
  double dR, dG, dB;
  double rBar;
  for(i=0; i<tileSet->numInitialized; i++)
  {
    dR = tileSet->tiles[i].avgColor.red()   - avgR;
    dG = tileSet->tiles[i].avgColor.green() - avgG;
    dB = tileSet->tiles[i].avgColor.blue()  - avgB;
    rBar = 0.5* (tileSet->tiles[i].avgColor.red() + avgR);
    
    //we could find the distance between this region and the tile by comparing the colors
    //directly as 3d points (sqrt(dR*dR + dG*dG + dB*dB)) but this would not
    //take into account their reltive perceptual weights. I found
    //some work by Thiadmer Riemersma that suggest I use this equation instead...
    //http://www.compuphase.com/cmetric.htm
    distances[i] = ((2+(rBar/256)) * dR * dR) +
      (4 * dG * dG) +
      ((2 + ((255.0-rBar)/256)) * dB * dB);
  }
  //------------------------------  
  //pick tile using pseudo-random distance biased approach
 
  //take reciprocol of all distances and find sum
  double sum = 0;
  double epsilon = 0.000000001;
  for(i=0; i<tileSet->numInitialized; i++)
  {
    distances[i] = 1.0 / MAX(distances[i], epsilon);
    sum += distances[i];
  } 
 
  //get a random number and find appropriate tile  
  double percentage = ((double)rand()) / RAND_MAX;
  double number = sum * percentage;
  int TILE = 0;  
  sum = 0;
  for(i =0; i<tileSet->numInitialized; i++)
  {
     sum += distances[i];
     if( sum >= number)
     {
       TILE = i; break;
      }  
  }
 
  delete distances;
  distances = NULL;
  //------------------------------  
  //determine saturation and luminance multipliers
  double sInc = avgS - tileSet->tiles[TILE].avgS;
  double lInc = avgL - tileSet->tiles[TILE].avgL;
  //------------------------------  
  
  //finally, splat the tile
  for( y=yMin; y<yMax; y++ )
  {
    //iterate over each selected pixel in scanline
    imageScanLine = image->scanLine( (y+topLeftCorner.y()) );
    tileScanLine = tileSet->tiles[TILE].image.scanLine(y);
    for( x=xMin; x<xMax; x++)
    {
      //get the tile color
      tileRgb = ((QRgb*) tileScanLine) + x;;
      QColor color( *tileRgb );
      
      //convert to hsl
      int h,s,l;
      color.getHsv( &h, &s, &l );
      
      //replace hue with the most common hue from this region of the target image
      h = mostCommonHue;
      
      //adjust saturation and luminance to more closely match the average values
      //found in this region of the target image.
      s = (int)MIN( MAX( s+sInc, 0), 255 );
      l = (int)MIN( MAX( l+lInc, 0), 255 );
      
      //convert back to rgb
      color.setHsv( mostCommonHue, s, l );
      
      //splat the adjusted tile color onto the image
      imageRgb = ((QRgb*)imageScanLine) + x + topLeftCorner.x();
      
      *imageRgb = color.rgb();
    }
  }
 
}
//==============================================