AlbumShaper
1.0a3
|
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 //==============================================