mosaic.cpp

Go to the documentation of this file.
00001 //==============================================
00002 //  copyright            : (C) 2003-2005 by Will Stokes
00003 //==============================================
00004 //  This program is free software; you can redistribute it
00005 //  and/or modify it under the terms of the GNU General
00006 //  Public License as published by the Free Software
00007 //  Foundation; either version 2 of the License, or
00008 //  (at your option) any later version.
00009 //==============================================
00010 
00011 //Systemwide includes
00012 #include <qimage.h>
00013 #include <qstring.h>
00014 #include <qapplication.h>
00015 #include <cstdlib>
00016 #include <time.h>
00017 #include <math.h>
00018 
00019 //Projectwide includes
00020 #include "mosaic.h"
00021 #include "manipulationOptions.h"
00022 #include "../tools/imageTools.h"
00023 #include "../../gui/statusWidget.h"
00024 
00025 #include <iostream>
00026 using namespace std;
00027 
00028 //----------------------------------------------
00029 // Inputs:
00030 // -------
00031 // QString filename -       location of original image on disk
00032 // MosaicOptions* options - various options that will be used like tile size, filenames 
00033 //                          that can be used to create an image-based tile set, and a pointer
00034 //                          to the status widget for alerting the user about progress.
00035 //
00036 // Outputs:
00037 // --------
00038 // QImage* returned - constructed image
00039 //
00040 // Motivation:
00041 // -----------
00042 // Where do I start? I suppose I'll begin with my motivation to write 
00043 // this manipulation. Then touch on stuff I looked at while formulating my 
00044 // approach, then descrive in gory detail how this actually works.
00045 //
00046 // While getting my masters in computer graphics at the Cornell Program of 
00047 // Comptuer Graphics ( http://www.graphics.cornell.edu ), I would see a photo 
00048 // mosaic of Don Greenberg in the hall every day:
00049 //
00050 // http://www.acm.org/tog/editors/erich/DPG/DPG_mosaic.jpg
00051 //
00052 // The photo was printed out all big and put on the wall at the end of a semi-long
00053 // hallway. If you came up the stairs at the other end of the hallway it 
00054 // seriously looked just like Don, despite being made up of lots of tiny 
00055 // pictures of people who at some point or other were students at the PCG. 
00056 // Several of us figured this looked like a pretty simple algorithm to write.
00057 // For each chunk of pixels you're going to smack a tile down on simply get 
00058 // the average brightness and use the tile that best matches the brightness for 
00059 // that area. It turns out to be a slightly more difficult problem. First, Eric 
00060 // Haynes, or created the Don photomosaic, kinda cheated by using grayscale 
00061 // instead of color. Color matching is a bit trickier. Second, simply picking 
00062 // the best tile to use at any location can result in various aliasing 
00063 // artifacts I'll get to later.
00064 //
00065 // So anyways, that was my motivation, sadly I didn't find this page which 
00066 // descrives how Eric created the mosaic until after I finished my technique, 
00067 // although I'm not sure it would change how I did it anyways.
00068 //
00069 // http://www.acm.org/tog/editors/erich/DPG/DPG.html
00070 //
00071 // Prior Art:
00072 // ----------
00073 // Photo mosaics are neither a novel or new techinque. They've been around for 
00074 // years, but how you accomplish them seems to vary like crazy. Creating grayscale
00075 // photomosaics is a much simpler process than using color for a few reasons. When
00076 // creating color photomosaics you not only need to match luminance but also the 
00077 // average hue and saturation for any region. Creating a good tileset is even trickier. 
00078 // If you are working with 256 gray levels it isn't that hard to construct a tile 
00079 // set that spans the entire range of luminance values. However, creating a tileset 
00080 // that spans the 256 x 256 x 256 = 16,777,216 range of color values is simply out 
00081 // of the question. Not only will finding a good set of tiles be difficult, but even 
00082 // if we get a decent set of tiles together it is clear we'll need to adjust them for 
00083 // each use in order to get them to match up better.
00084 //
00085 // But before get ahead of myself, before I started designing my own photo 
00086 // mosiac algorithm I studied a few others. First, I found there are quite a few 
00087 // programs out there, but most cost a few bucks to try out, so being the cheap 
00088 // person I am I based a lot of my "research" on surfing around and looking at 
00089 // these programs output. I was particuarly impressed with Andrea Mosaic:
00090 //
00091 // http://www.andreaplanet.com/andreamosaic/
00092 //
00093 // Unfortunately it is closed source. The only source code I looked at was 
00094 // the pmosaic gimp plugin:
00095 // http://www.kirchgessner.net/photo-mosaic.html#DETAIL
00096 //
00097 // Approach:
00098 // ---------
00099 // I wasn't too impressed with this latter link, although it was nice to actually
00100 // look at some code. What I figured thus far was that I would develop an algorithm 
00101 // that supported generated color photo mosaics and that meant picking the best tile 
00102 // to splat down using a distance quantity loosely based on 3d coordinates using the 
00103 // red, green, and blue color values, such as:
00104 //
00105 // D = sqrt( dr*dr + dg*dg + db*db );
00106 //
00107 // where d[r,g,b] refer to the difference in red/green/blue values between the 
00108 // source image and a particular tile. This quantity could either be computed at each 
00109 // pixel for a given tile with respect to the original image and averaged, or the
00110 // average color for the tile and the region of hte image the tile woudl be smacked
00111 // onto could be precomputed, making computing the distance quantity substantially faster.
00112 //
00113 // I actually experimented with both approaches and was fairly happy with 
00114 // the results provided by both of them. However; my perception background told 
00115 // me computing the distance in 3-space like this wasn't exactly right because our
00116 // eyes are more sensative to variation in the green component then the red and 
00117 // the blue. I forget how, but I stumbled on this alternative techinque for 
00118 // computing the distance in color space:
00119 //
00120 // http://www.compuphase.com/cmetric.htm
00121 // D = sqrt {  [2 + rbar/256 ]*dR*dR   +  4*dG*dG  +  [2 + (255-rBar) / 256]*db*dB  }
00122 //
00123 // This is an approximate to a properly weighted Euclidean distance function. 
00124 // In my actual implementation I don't take the square root. If I simply picked
00125 // the tile with the smallest distance that probably woudl work just fine, but 
00126 // I pick probablisitically, so in theory I'm biasing myself too much towards 
00127 // tiles that very closely match the color I'm looking for, but it appears to work 
00128 // just fine regardless and saves a few cycles.
00129 //
00130 // Algorithm:
00131 // ----------
00132 // So, I should wrap this up with an outline of how a photomosaic is created:
00133 //
00134 // 1.) "mosaicEffect" is called and provided an image filename and a collection of options
00135 //
00136 // 2.) A tileset is constructed in one of two ways. If one or more filenames 
00137 //     for tiles has been provided in the options an image-based tileset is 
00138 //     constructed using "constructImageTiles." Otherwise a solid-color based 
00139 //     tileset is created using "constructColorTiles."
00140 //
00141 // 3.) The manipulation was first developing using solid-color tilesets, then 
00142 //     extended to support image-based tilesets. I'm not sure if people want to 
00143 //     use solid color tilesets, but they are useful for providing a fast manipulation 
00144 //     preview without any user intervention (like specifying what images ot ue for 
00145 //     tiles) while still conveying the effect the manipulation will have on the source image.
00146 //
00147 // So, how to create a color tileset. I've find old-school web pallettes did well 
00148 // using 216 colors that span the entire color gammut by equally spacing the red, 
00149 // green, and blue color components from 00 to FF spaced by 51 (aka 00, 33, 66, 
00150 // 99, CC, FF). That's 6 unique red, green, and blue, or 6^3 = 216 unique colors. 
00151 // For each color I simply fill a tile with that color.
00152 //
00153 // Image tile sets are a bit more complicated. A list of filenames are passed in as 
00154 // one of the options. In order to avoid creating too many tiles we randomly 
00155 // pick no more than MAX_TILES (216) of these files for creating image tiles.
00156 //
00157 // Once a chosen list has been created, it is time to create the actual image 
00158 // tiles. For each tile I scale it down so that it still fills the tile, but 
00159 // still is larger in one of the two dimensions. Scaling down to the exact 
00160 // tile dimensions would result in skewing the aspect ratio and would be a big no-no.
00161 //
00162 // The scaled image is then ceneter and cropped to fit the specified tile size.
00163 //
00164 // While creating the tile, we also compute the average red, green, and blue 
00165 // color value, in addition to the average luminance and saturation (but not hue).
00166 //
00167 // 4.) Once a tileset has been constructed, it is time to start smacking tiles 
00168 //     down. We iterate over blocks of the image to put tiles onto. For each 
00169 //     image block we compute the average color, hue, luminance, and saturation. 
00170 //     The distance between each tile and the image block is computed using the 
00171 //     average color data only.
00172 //
00173 // Now, at this point we could simply pick the tile that has the shortest 
00174 // distance (most closely matches the intended color), and while I experimented 
00175 // with this at first, I quickly ran into trouble. Smooth gradations in the source 
00176 // image resulted in sudden changes from one tile to the next one surfaces like 
00177 // walls. For example, if the wall behind a subject had luminances that look like this:
00178 //
00179 // 255 255 240  220 200 180 180 180
00180 // 255 255 240  220 200 180 180 180
00181 // 255 255 240  220 200 180 180 180
00182 //
00183 // I'd notice the tiles that are used woudl suddenly change like so:
00184 //
00185 // A A B B C C C C
00186 // A A B B C C C C
00187 // A A B B C C C C
00188 //
00189 // The resulted image looks weird, almost like egdes has been created where edges 
00190 // were not located before. Instead of simply picking the best tile, I decided to 
00191 // use a pseudo-random approach. The reciprocal distances are first computed, then 
00192 // summed. A random number if picked bewteen 0-sumRecipDistance and distates which 
00193 // tile will be used. By defintion, tiles that have small distances will have the 
00194 // largest reciprocal distances and thus are most likely to be picked. A tile with 
00195 // a large distance will be a tiny reciprocal distance and will almost certainly not 
00196 // be picked. This results in a slow change from using A to B to C like this;
00197 //
00198 // A B B B B C C C
00199 // A A A C C C C C
00200 // A B B B C C C C
00201 //
00202 // The change is "blurred" so to speak and "blooming" like effects don't show up any more.
00203 //
00204 // Ok, so at this point we can pick the tile to spat, but how do we splat it? If we 
00205 // simply pasted the tile directly we'd see:
00206 // -a shift in hue
00207 // -a shift in luminance
00208 // -a shift in saturation
00209 //
00210 // If we simply converted the RGB color of each tile pixel to HSV and replaced the 
00211 // HSV values we simply be pasting down a solid color and that woudln't do us much good :-)
00212 //
00213 // We want to see the small pictures still, that means keeping the variation in luminance 
00214 // and saturation, while most closely matching the hue. Our distance techinque will 
00215 // help us pick tiles that don't differ in hue much, so replacing the hue at each pixel 
00216 // with the hue we want will help us achieve the hue we need without causing too much damage.
00217 //
00218 // We can match the average luminance and saturation by simply shifting all saturation 
00219 // and luminance values by the differnce in the averages between the image chunk and 
00220 // the chosen tile. The result is a tile that will provide the desired hue, and when 
00221 // you consider all tile pixels the same average saturation and luminance. Meaning 
00222 // if you stand back the top level image will look great, but if you get up close 
00223 // you can still see all the details of the source tile images.
00224 //
00225 // Future Work:
00226 // ------------
00227 // There are a few things that could be explored in the future:
00228 //
00229 // -A better tile picking algorithmn that considers the average hue of potential 
00230 //  tile images and what hues have not been found already, thus producing a better 
00231 //  tile hue gammut.
00232 //
00233 // -Exploring the use of outlines between tiles (like a white pixel border), or 
00234 //  even other tile shapes than rectangles like puzzle pieces. Personally I consider 
00235 //  these effects gimmicky, they detract from the overall image which I don't like.
00236 //
00237 // -A differnt distance-based picking algorthm that just works in the hue domain. 
00238 //  I'm not sure this is a good thing since the current approach also most closely 
00239 //  matches luminance and saturation making any modifications along these dimensions 
00240 //  minimal, and minimally changing the tile images is a good thing.//
00241 //----------------------------------------------
00242 
00243 
00244 //====================================================
00245 MosaicOptions::MosaicOptions( QStringList files, QSize tileSize, StatusWidget* status ) 
00246                             : ManipulationOptions( status )
00247 {
00248   this->files = files;
00249   this->tileSize = tileSize;
00250 }
00251 QStringList MosaicOptions::getFileList() { return files; }
00252 QSize MosaicOptions::getTileSize() { return tileSize; }
00253 //====================================================
00254 
00255 //a decent color set uses 216 colors
00256 #define MAX_TILES 216
00257 
00258 //==============================================
00259 struct Tile
00260 {
00261   //tile image
00262   QImage image;
00263   
00264   //average color
00265   QColor avgColor;
00266   
00267   //average saturation, and luminosity
00268   int avgS, avgL;
00269 };
00270 //==============================================
00271 struct TileSet
00272 {
00273   //tiles
00274   Tile tiles[MAX_TILES];
00275   
00276   //number of initialized tiles in set
00277   int numInitialized;
00278 };
00279 //==============================================
00280 //create to tilesets. color tiles will be used for fast previews,
00281 //image tiles will be used when actually applying the effect
00282 TileSet colorTiles;
00283 TileSet imageTiles;
00284 //==============================================
00285 //declare these functions here, we'll define them below
00286 void constructColorTiles(QSize tileSize);
00287 void constructImageTiles(QStringList files, QSize tileSize);
00288 void splatBestTile(QImage* image, QPoint topLeftCorner, TileSet* tileSet);
00289 //==============================================
00290 QImage* mosaicEffect( QString filename, MosaicOptions* options )
00291 {
00292   //load image
00293   QImage* editedImage = new QImage( filename );
00294   
00295   //convert to 32-bit depth if necessary
00296   if( editedImage->depth() < 32 )
00297   {
00298     QImage* tmp = editedImage;
00299     editedImage = new QImage( tmp->convertDepth( 32, Qt::AutoColor ) );
00300     delete tmp; tmp=NULL;
00301   }
00302   
00303   //determine if busy indicators will be used
00304   bool useBusyIndicators = false;
00305   StatusWidget* status = NULL;
00306   if( options != NULL && options->getStatus() != NULL )
00307   {
00308     useBusyIndicators = true;
00309     status = options->getStatus(); 
00310   }
00311   
00312   //intialize seed using current time
00313   srand( unsigned(time(NULL)) );
00314   
00315   //determine tile size
00316   QSize tileSize;
00317   if(options == NULL) tileSize = QSize(6,6); //6 is big enough to be visible, but not so blocky the image looks bad
00318   else                tileSize =options->getTileSize();
00319   
00320   //construct tile set
00321   TileSet* tileSet = NULL;
00322   if( options != NULL && options->getFileList().size() > 0 )
00323   {
00324     constructImageTiles(options->getFileList(), tileSize);
00325     tileSet = &imageTiles;
00326   }
00327   else
00328   { 
00329     constructColorTiles(tileSize);
00330     tileSet = &colorTiles;
00331   }
00332 
00333   //setup progress bar
00334   if(useBusyIndicators)
00335   {
00336     QString statusMessage = qApp->translate( "mosaicEffect", "Applying Mosaic Effect:" );
00337     status->showProgressBar( statusMessage, 100 );
00338     qApp->processEvents();  
00339   }
00340 
00341   //update progress bar for every 1% of completion
00342   const int updateIncrement = (int) ( (0.01 * editedImage->width() * editedImage->height()) / 
00343                                       (tileSize.width() * tileSize.height()) );
00344   int newProgress = 0; 
00345 
00346   //iterate over each selected scanline 
00347   int x, y;
00348   for(y=0; y<editedImage->height(); y+=tileSize.height())
00349   {
00350     for( x=0; x<editedImage->width(); x+=tileSize.width())
00351     {
00352       //splat the best tile
00353       splatBestTile( editedImage, QPoint(x,y), tileSet );
00354      
00355       //update status bar if significant progress has been made since last update
00356       if(useBusyIndicators)
00357       {
00358         newProgress++;
00359         if(newProgress >= updateIncrement)
00360         {
00361           newProgress = 0;
00362           status->incrementProgress();
00363           qApp->processEvents();  
00364         }
00365       }
00366 
00367     }
00368   }
00369    
00370   //return pointer to edited image
00371   return editedImage;  
00372 }
00373 //==============================================
00374 //Initialize a general color tile set using pure tones.
00375 void constructColorTiles(QSize tileSize)
00376 {
00377   //max tiles must be allocated across all colors, so find resolution we'll have for each color
00378   //channel (e.g. if max tiles is 100, 100^(1/3) ~= 4.6 so we'll use 4 unique red, green, and
00379   //blue color values for constructing tiles and use 4^3=64 tiles out of the 100 allocated
00380   int colorRes = (int)pow( MAX_TILES, 1.0/3 );
00381   
00382   //always include 0 and 255 so increment is always totalSpan/(count-1)
00383   int colorIncrement = 255 / (colorRes-1);
00384   
00385   colorIncrement = 51;
00386   
00387   //create actual tiles
00388   int tile=0;
00389   int r,g,b;
00390   for(r=0; r<=255; r+=colorIncrement)
00391   {
00392     for(g=0; g<=255; g+=colorIncrement)
00393     {
00394       for(b=0; b<=255; b+=colorIncrement)
00395       {
00396         colorTiles.tiles[tile].image.create( tileSize.width(), tileSize.height(), 32);
00397         colorTiles.tiles[tile].image.fill( qRgb(r, g, b) );
00398         
00399         colorTiles.tiles[tile].avgColor = QColor(r,g,b);
00400         
00401         int h;
00402         QColor(r,g,b).getHsv( &h, &(colorTiles.tiles[tile].avgS), &(colorTiles.tiles[tile].avgL) );
00403         tile++;
00404       }
00405     }
00406   }
00407   
00408   //setup number of initialized tiles
00409   colorTiles.numInitialized = tile;
00410 }
00411 //==============================================
00412 //Initialize an image based tile set
00413 void constructImageTiles(QStringList files, QSize tileSize)
00414 {
00415   //---------------------------------  
00416   //setup number of initialized tiles
00417   imageTiles.numInitialized = QMIN(files.size(), MAX_TILES);
00418   //---------------------------------  
00419   //create file index list, we'll use this to construct a
00420   //list of indices to the randomply picked files from the master list
00421   int* fileIndices = new int[imageTiles.numInitialized];
00422   int* fileIndicesUsed = new int[files.size()];
00423   int i;
00424   for(i=0; i<imageTiles.numInitialized; i++) { fileIndices[i] = -1;    }
00425   for(i=0; i<((int)files.size()); i++)              { fileIndicesUsed[i] = 0; }
00426   //---------------------------------  
00427   //pick the random files, updating the file indices list
00428   for(i=0; i<imageTiles.numInitialized; i++)
00429   {
00430     double percentage = ((double)rand()) / RAND_MAX;
00431     int fileNum = (int) (  (files.size() - (i+1)) * percentage);
00432     
00433     //correct index by offsetting by all files that have been picked before this one 
00434     int j = 0;
00435     int realFileNum = fileNum;
00436     while( fileNum >= 0)
00437     {
00438       if( fileIndicesUsed[j] == 1 )  { realFileNum++; }
00439       else                           { fileNum--;     }
00440        
00441       j++;      
00442     }
00443     
00444     //record file index into list
00445     fileIndices[i] = realFileNum;
00446     fileIndicesUsed[realFileNum] = 1;
00447   }
00448   
00449   //---------------------------------  
00450   //sort the file index list - bubble sort is fast enough right? :-)
00451   int j;
00452   for( i=imageTiles.numInitialized-1; i>0; i--)
00453   {
00454     for( j=0; j<i; j++)
00455     {
00456       if( fileIndices[j] > fileIndices[j+1] )
00457       {
00458         int tmp = fileIndices[j+1];
00459         fileIndices[j+1] = fileIndices[j];
00460         fileIndices[j] = tmp;
00461       }
00462     }
00463   }
00464   //---------------------------------  
00465   //construct truncated list of files that we'll use
00466   QStringList chosenFiles;
00467   QStringList::iterator it;
00468   int curFileIndex = 0;
00469   int nextDesiredFileIndex = 0;
00470   for(it = files.begin(); it != files.end(); it++ )
00471   {
00472     if( curFileIndex == fileIndices[nextDesiredFileIndex] )
00473     {
00474       chosenFiles.append( *it );
00475       nextDesiredFileIndex++;
00476       
00477       if( nextDesiredFileIndex >= imageTiles.numInitialized ) break;
00478     }
00479 
00480     curFileIndex++;  
00481   }
00482 
00483   //resetting numInitialized should not be necessary, we should have the right
00484   //number of files in chosenFiles, but as a sanity check, we'll reset it here again.
00485   imageTiles.numInitialized = QMIN((int)chosenFiles.size(), imageTiles.numInitialized);
00486 
00487   //---------------------------------  
00488   //free up the temporary index list, it's nolonger needed since we now have an
00489   //actual list of the chosen files
00490   delete fileIndices;
00491   delete fileIndicesUsed;
00492   fileIndices = NULL;
00493   fileIndicesUsed = NULL;  
00494   //---------------------------------  
00495   //ok, we now have a list of files we actually want to use to create tiles from, that have
00496   //been randomly chosen from the huge list we were given. now actually create the tiles
00497   int tile = 0;
00498 
00499   for(it = chosenFiles.begin(); it != chosenFiles.end(); it++ )
00500   {
00501     //scale image to definately fill a tileSizeW x tileSizeH region, we'll crop down afterwards
00502     QSize imageRes;
00503     getImageSize( *it, imageRes );
00504   
00505     int intermediateWidth = -1;
00506     int intermediateHeight = -1;
00507     if( ((double)imageRes.width()) / tileSize.width() > ((double)imageRes.height()) / tileSize.height() )
00508     {
00509       intermediateHeight = tileSize.height();
00510       intermediateWidth = (int) ( ((1.0*intermediateHeight*imageRes.width()) / imageRes.height()) + 0.5 );
00511     }
00512     else
00513     {
00514       intermediateWidth = tileSize.width();
00515       intermediateHeight = (int) ( ((1.0*intermediateWidth*imageRes.height()) / imageRes.width()) + 0.5 );
00516     }
00517     
00518     QImage scaledImage;
00519     scaleImage( *it, scaledImage, intermediateWidth, intermediateHeight );
00520     
00521     //scaleImage does not like to scale more than 2x, so if image is not the right size scale it up again
00522     if( scaledImage.width() != tileSize.width() || scaledImage.height() != tileSize.height() )
00523       scaledImage = scaledImage.scale( tileSize, QImage::ScaleFree );
00524     
00525     //construct tile image
00526     imageTiles.tiles[tile].image.create( tileSize.width(), tileSize.height(), 32);
00527     imageTiles.tiles[tile].image.fill( qRgb(255,255,255) );
00528             
00529     //crop scaledimage to tileSizeW x tileSizeH - simultaniously compute statistics about tile
00530     int xOffset = (scaledImage.width()  - tileSize.width())/2;
00531     int yOffset = (scaledImage.height() - tileSize.height())/2;
00532     int x, y;
00533     uchar* scaledScanLine;
00534     uchar* croppedScanLine;
00535     QRgb* scaledRgb;
00536     QRgb* croppedRgb;
00537      
00538     double avgR=0; double avgG=0; double avgB=0;
00539     double avgS=0; double avgL=0;
00540 
00541     //sometimes corrupt images can get through, so this check
00542     //bulletproofs the code
00543     if( scaledImage.isNull() )
00544     {
00545       avgR = avgG = avgB = 255;
00546       avgS = avgL = 255;
00547     }
00548     else
00549     {
00550       for( y=0; y<tileSize.height(); y++)
00551       {
00552         scaledScanLine  = scaledImage.scanLine(y + yOffset);
00553         croppedScanLine = imageTiles.tiles[tile].image.scanLine(y);
00554         
00555         for( x=0; x<tileSize.width(); x++)
00556         {
00557           scaledRgb  = ((QRgb*) scaledScanLine) +x + xOffset;
00558           croppedRgb = ((QRgb*) croppedScanLine)  + x;
00559           
00560           //copy pixel color over
00561           *croppedRgb = *scaledRgb;
00562           
00563           //update statistics
00564           QColor color( *croppedRgb );
00565           
00566           avgR += color.red();
00567           avgG += color.green();
00568           avgB += color.blue();
00569           
00570           int h,s,l;
00571           color.getHsv( &h, &s, &l );
00572           avgS += s;
00573           avgL += l;
00574         }
00575       }
00576       
00577       //average red, green, blue, saturation, and luminance sums
00578       int pixelCount = tileSize.width()*tileSize.height();
00579       avgR /= pixelCount;
00580       avgG /= pixelCount;
00581       avgB /= pixelCount;
00582       avgS /= pixelCount;
00583       avgL /= pixelCount;
00584     }    
00585     //store statistics    
00586     imageTiles.tiles[tile].avgColor = QColor( (int)avgR, (int)avgG, (int)avgB );
00587     imageTiles.tiles[tile].avgS = (int)avgS;
00588     imageTiles.tiles[tile].avgL = (int)avgL;
00589                             
00590     //move on to next tile
00591     tile++;
00592   }
00593   //---------------------------------  
00594 }
00595 //==============================================
00596 //Pseudo-randomly pick the best tile from the specified tileset and splat
00597 //it on the image
00598 void splatBestTile(QImage* image, QPoint topLeftCorner, TileSet* tileSet)
00599 {
00600   int x, y;
00601   QRgb* imageRgb;
00602   QRgb* tileRgb;
00603   uchar* imageScanLine;
00604   uchar* tileScanLine;
00605   //------------------------------  
00606   //dermine boundary we'll be iterating over
00607   int xMin = 0; 
00608   int xMax = QMIN( tileSet->tiles[0].image.width(),   image->width() - topLeftCorner.x() );
00609   int yMin = 0;
00610   int yMax = QMIN( tileSet->tiles[0].image.height(), image->height() - topLeftCorner.y() );
00611   //------------------------------   
00612   //find most common hue, and average color, saturation and luminance for this portion of the image 
00613   double avgR=0; double avgG=0; double avgB=0;
00614   int hueHist[361];
00615   int i;
00616   for(i=0; i<361; i++) { hueHist[i] = 0; }
00617   double avgS=0; double avgL=0;
00618   
00619   for( y=yMin; y<yMax; y++)
00620   {
00621     imageScanLine = image->scanLine(y+topLeftCorner.y());
00622     for( x=xMin; x<xMax; x++)
00623     {
00624       imageRgb = ((QRgb*)imageScanLine+x+topLeftCorner.x());
00625       QColor color( *imageRgb );
00626       
00627       avgR += color.red();
00628       avgG += color.green();
00629       avgB += color.blue();
00630       
00631       int h,s,l;
00632       color.getHsv( &h, &s, &l );
00633       hueHist[ QMIN( QMAX(h,0), 360 ) ]++;
00634       avgS += s;
00635       avgL += l;
00636     }
00637   }
00638   
00639   //average red, green, blue, saturation, and luminance sums
00640   int pixelCount = (yMax-yMin) * (xMax-xMin);
00641   avgR /= pixelCount;
00642   avgG /= pixelCount;
00643   avgB /= pixelCount;
00644   avgS /= pixelCount;
00645   avgL /= pixelCount;
00646   
00647   //walk through hue histogram and find most common hue
00648   int mostCommonHue = 0;
00649   for(i=1; i<361; i++)
00650   {
00651     if( hueHist[i] > hueHist[mostCommonHue] ) { mostCommonHue = i; }
00652   }
00653   
00654   //------------------------------  
00655   //compute distance between this region and all initialized tiles
00656   double* distances = new double[tileSet->numInitialized];
00657   
00658   double dR, dG, dB;
00659   double rBar;
00660   for(i=0; i<tileSet->numInitialized; i++)
00661   {
00662     dR = tileSet->tiles[i].avgColor.red()   - avgR;
00663     dG = tileSet->tiles[i].avgColor.green() - avgG;
00664     dB = tileSet->tiles[i].avgColor.blue()  - avgB;
00665     rBar = 0.5* (tileSet->tiles[i].avgColor.red() + avgR);
00666     
00667     //we could find the distance between this region and the tile by comparing the colors
00668     //directly as 3d points (sqrt(dR*dR + dG*dG + dB*dB)) but this would not
00669     //take into account their reltive perceptual weights. I found
00670     //some work by Thiadmer Riemersma that suggest I use this equation instead...
00671     //http://www.compuphase.com/cmetric.htm
00672     distances[i] = ((2+(rBar/256)) * dR * dR) +
00673       (4 * dG * dG) +
00674       ((2 + ((255.0-rBar)/256)) * dB * dB);
00675   }
00676   //------------------------------  
00677   //pick tile using pseudo-random distance biased approach
00678  
00679   //take reciprocol of all distances and find sum
00680   double sum = 0;
00681   double epsilon = 0.000000001;
00682   for(i=0; i<tileSet->numInitialized; i++)
00683   {
00684     distances[i] = 1.0 / QMAX(distances[i], epsilon);
00685     sum += distances[i];
00686   } 
00687 
00688   //get a random number and find appropriate tile  
00689   double percentage = ((double)rand()) / RAND_MAX;
00690   double number = sum * percentage;
00691   int TILE = 0;  
00692   sum = 0;
00693   for(i =0; i<tileSet->numInitialized; i++)
00694   {
00695      sum += distances[i];
00696      if( sum >= number)
00697      {
00698        TILE = i; break;
00699       }  
00700   }
00701 
00702   delete distances;
00703   distances = NULL;
00704   //------------------------------  
00705   //determine saturation and luminance multipliers
00706   double sInc = avgS - tileSet->tiles[TILE].avgS;
00707   double lInc = avgL - tileSet->tiles[TILE].avgL;
00708   //------------------------------  
00709   
00710   //finally, splat the tile
00711   for( y=yMin; y<yMax; y++ )
00712   {
00713     //iterate over each selected pixel in scanline
00714     imageScanLine = image->scanLine( (y+topLeftCorner.y()) );
00715     tileScanLine = tileSet->tiles[TILE].image.scanLine(y);
00716     for( x=xMin; x<xMax; x++)
00717     {
00718       //get the tile color
00719       tileRgb = ((QRgb*) tileScanLine) + x;;
00720       QColor color( *tileRgb );
00721       
00722       //convert to hsl
00723       int h,s,l;
00724       color.getHsv( &h, &s, &l );
00725       
00726       //replace hue with the most common hue from this region of the target image
00727       h = mostCommonHue;
00728       
00729       //adjust saturation and luminance to more closely match the average values
00730       //found in this region of the target image.
00731       s = (int)QMIN( QMAX( s+sInc, 0), 255 );
00732       l = (int)QMIN( QMAX( l+lInc, 0), 255 );
00733       
00734       //convert back to rgb
00735       color.setHsv( mostCommonHue, s, l );
00736       
00737       //splat the adjusted tile color onto the image
00738       imageRgb = ((QRgb*)imageScanLine) + x + topLeftCorner.x();
00739       
00740       *imageRgb = color.rgb();
00741     }
00742   }
00743 
00744 }
00745 //==============================================

Generated on Wed Jan 24 05:38:28 2007 for AlbumShaper by  doxygen 1.5.1