AlbumShaper  1.0a3
mosaic.cpp
Go to the documentation of this file.
1 //==============================================
2 // copyright : (C) 2003-2005 by Will Stokes
3 //==============================================
4 // This program is free software; you can redistribute it
5 // and/or modify it under the terms of the GNU General
6 // Public License as published by the Free Software
7 // Foundation; either version 2 of the License, or
8 // (at your option) any later version.
9 //==============================================
10 
11 //Systemwide includes
12 #include <qimage.h>
13 #include <qstring.h>
14 #include <qapplication.h>
15 #include <cstdlib>
16 #include <time.h>
17 #include <math.h>
18 
19 #define MIN(x,y) ((x) < (y) ? (x) : (y))
20 #define MAX(x,y) ((x) < (y) ? (x) : (y))
21 
22 //Projectwide includes
23 #include "mosaic.h"
24 #include "manipulationOptions.h"
25 #include "../tools/imageTools.h"
26 #include "../../gui/statusWidget.h"
27 
28 #include <iostream>
29 using namespace std;
30 
31 //----------------------------------------------
32 // Inputs:
33 // -------
34 // QString filename - location of original image on disk
35 // MosaicOptions* options - various options that will be used like tile size, filenames
36 // that can be used to create an image-based tile set, and a pointer
37 // to the status widget for alerting the user about progress.
38 //
39 // Outputs:
40 // --------
41 // QImage* returned - constructed image
42 //
43 // Motivation:
44 // -----------
45 // Where do I start? I suppose I'll begin with my motivation to write
46 // this manipulation. Then touch on stuff I looked at while formulating my
47 // approach, then descrive in gory detail how this actually works.
48 //
49 // While getting my masters in computer graphics at the Cornell Program of
50 // Comptuer Graphics ( http://www.graphics.cornell.edu ), I would see a photo
51 // mosaic of Don Greenberg in the hall every day:
52 //
53 // http://www.acm.org/tog/editors/erich/DPG/DPG_mosaic.jpg
54 //
55 // The photo was printed out all big and put on the wall at the end of a semi-long
56 // hallway. If you came up the stairs at the other end of the hallway it
57 // seriously looked just like Don, despite being made up of lots of tiny
58 // pictures of people who at some point or other were students at the PCG.
59 // Several of us figured this looked like a pretty simple algorithm to write.
60 // For each chunk of pixels you're going to smack a tile down on simply get
61 // the average brightness and use the tile that best matches the brightness for
62 // that area. It turns out to be a slightly more difficult problem. First, Eric
63 // Haynes, or created the Don photomosaic, kinda cheated by using grayscale
64 // instead of color. Color matching is a bit trickier. Second, simply picking
65 // the best tile to use at any location can result in various aliasing
66 // artifacts I'll get to later.
67 //
68 // So anyways, that was my motivation, sadly I didn't find this page which
69 // descrives how Eric created the mosaic until after I finished my technique,
70 // although I'm not sure it would change how I did it anyways.
71 //
72 // http://www.acm.org/tog/editors/erich/DPG/DPG.html
73 //
74 // Prior Art:
75 // ----------
76 // Photo mosaics are neither a novel or new techinque. They've been around for
77 // years, but how you accomplish them seems to vary like crazy. Creating grayscale
78 // photomosaics is a much simpler process than using color for a few reasons. When
79 // creating color photomosaics you not only need to match luminance but also the
80 // average hue and saturation for any region. Creating a good tileset is even trickier.
81 // If you are working with 256 gray levels it isn't that hard to construct a tile
82 // set that spans the entire range of luminance values. However, creating a tileset
83 // that spans the 256 x 256 x 256 = 16,777,216 range of color values is simply out
84 // of the question. Not only will finding a good set of tiles be difficult, but even
85 // if we get a decent set of tiles together it is clear we'll need to adjust them for
86 // each use in order to get them to match up better.
87 //
88 // But before get ahead of myself, before I started designing my own photo
89 // mosiac algorithm I studied a few others. First, I found there are quite a few
90 // programs out there, but most cost a few bucks to try out, so being the cheap
91 // person I am I based a lot of my "research" on surfing around and looking at
92 // these programs output. I was particuarly impressed with Andrea Mosaic:
93 //
94 // http://www.andreaplanet.com/andreamosaic/
95 //
96 // Unfortunately it is closed source. The only source code I looked at was
97 // the pmosaic gimp plugin:
98 // http://www.kirchgessner.net/photo-mosaic.html#DETAIL
99 //
100 // Approach:
101 // ---------
102 // I wasn't too impressed with this latter link, although it was nice to actually
103 // look at some code. What I figured thus far was that I would develop an algorithm
104 // that supported generated color photo mosaics and that meant picking the best tile
105 // to splat down using a distance quantity loosely based on 3d coordinates using the
106 // red, green, and blue color values, such as:
107 //
108 // D = sqrt( dr*dr + dg*dg + db*db );
109 //
110 // where d[r,g,b] refer to the difference in red/green/blue values between the
111 // source image and a particular tile. This quantity could either be computed at each
112 // pixel for a given tile with respect to the original image and averaged, or the
113 // average color for the tile and the region of hte image the tile woudl be smacked
114 // onto could be precomputed, making computing the distance quantity substantially faster.
115 //
116 // I actually experimented with both approaches and was fairly happy with
117 // the results provided by both of them. However; my perception background told
118 // me computing the distance in 3-space like this wasn't exactly right because our
119 // eyes are more sensative to variation in the green component then the red and
120 // the blue. I forget how, but I stumbled on this alternative techinque for
121 // computing the distance in color space:
122 //
123 // http://www.compuphase.com/cmetric.htm
124 // D = sqrt { [2 + rbar/256 ]*dR*dR + 4*dG*dG + [2 + (255-rBar) / 256]*db*dB }
125 //
126 // This is an approximate to a properly weighted Euclidean distance function.
127 // In my actual implementation I don't take the square root. If I simply picked
128 // the tile with the smallest distance that probably woudl work just fine, but
129 // I pick probablisitically, so in theory I'm biasing myself too much towards
130 // tiles that very closely match the color I'm looking for, but it appears to work
131 // just fine regardless and saves a few cycles.
132 //
133 // Algorithm:
134 // ----------
135 // So, I should wrap this up with an outline of how a photomosaic is created:
136 //
137 // 1.) "mosaicEffect" is called and provided an image filename and a collection of options
138 //
139 // 2.) A tileset is constructed in one of two ways. If one or more filenames
140 // for tiles has been provided in the options an image-based tileset is
141 // constructed using "constructImageTiles." Otherwise a solid-color based
142 // tileset is created using "constructColorTiles."
143 //
144 // 3.) The manipulation was first developing using solid-color tilesets, then
145 // extended to support image-based tilesets. I'm not sure if people want to
146 // use solid color tilesets, but they are useful for providing a fast manipulation
147 // preview without any user intervention (like specifying what images ot ue for
148 // tiles) while still conveying the effect the manipulation will have on the source image.
149 //
150 // So, how to create a color tileset. I've find old-school web pallettes did well
151 // using 216 colors that span the entire color gammut by equally spacing the red,
152 // green, and blue color components from 00 to FF spaced by 51 (aka 00, 33, 66,
153 // 99, CC, FF). That's 6 unique red, green, and blue, or 6^3 = 216 unique colors.
154 // For each color I simply fill a tile with that color.
155 //
156 // Image tile sets are a bit more complicated. A list of filenames are passed in as
157 // one of the options. In order to avoid creating too many tiles we randomly
158 // pick no more than MAX_TILES (216) of these files for creating image tiles.
159 //
160 // Once a chosen list has been created, it is time to create the actual image
161 // tiles. For each tile I scale it down so that it still fills the tile, but
162 // still is larger in one of the two dimensions. Scaling down to the exact
163 // tile dimensions would result in skewing the aspect ratio and would be a big no-no.
164 //
165 // The scaled image is then ceneter and cropped to fit the specified tile size.
166 //
167 // While creating the tile, we also compute the average red, green, and blue
168 // color value, in addition to the average luminance and saturation (but not hue).
169 //
170 // 4.) Once a tileset has been constructed, it is time to start smacking tiles
171 // down. We iterate over blocks of the image to put tiles onto. For each
172 // image block we compute the average color, hue, luminance, and saturation.
173 // The distance between each tile and the image block is computed using the
174 // average color data only.
175 //
176 // Now, at this point we could simply pick the tile that has the shortest
177 // distance (most closely matches the intended color), and while I experimented
178 // with this at first, I quickly ran into trouble. Smooth gradations in the source
179 // image resulted in sudden changes from one tile to the next one surfaces like
180 // walls. For example, if the wall behind a subject had luminances that look like this:
181 //
182 // 255 255 240 220 200 180 180 180
183 // 255 255 240 220 200 180 180 180
184 // 255 255 240 220 200 180 180 180
185 //
186 // I'd notice the tiles that are used woudl suddenly change like so:
187 //
188 // A A B B C C C C
189 // A A B B C C C C
190 // A A B B C C C C
191 //
192 // The resulted image looks weird, almost like egdes has been created where edges
193 // were not located before. Instead of simply picking the best tile, I decided to
194 // use a pseudo-random approach. The reciprocal distances are first computed, then
195 // summed. A random number if picked bewteen 0-sumRecipDistance and distates which
196 // tile will be used. By defintion, tiles that have small distances will have the
197 // largest reciprocal distances and thus are most likely to be picked. A tile with
198 // a large distance will be a tiny reciprocal distance and will almost certainly not
199 // be picked. This results in a slow change from using A to B to C like this;
200 //
201 // A B B B B C C C
202 // A A A C C C C C
203 // A B B B C C C C
204 //
205 // The change is "blurred" so to speak and "blooming" like effects don't show up any more.
206 //
207 // Ok, so at this point we can pick the tile to spat, but how do we splat it? If we
208 // simply pasted the tile directly we'd see:
209 // -a shift in hue
210 // -a shift in luminance
211 // -a shift in saturation
212 //
213 // If we simply converted the RGB color of each tile pixel to HSV and replaced the
214 // HSV values we simply be pasting down a solid color and that woudln't do us much good :-)
215 //
216 // We want to see the small pictures still, that means keeping the variation in luminance
217 // and saturation, while most closely matching the hue. Our distance techinque will
218 // help us pick tiles that don't differ in hue much, so replacing the hue at each pixel
219 // with the hue we want will help us achieve the hue we need without causing too much damage.
220 //
221 // We can match the average luminance and saturation by simply shifting all saturation
222 // and luminance values by the differnce in the averages between the image chunk and
223 // the chosen tile. The result is a tile that will provide the desired hue, and when
224 // you consider all tile pixels the same average saturation and luminance. Meaning
225 // if you stand back the top level image will look great, but if you get up close
226 // you can still see all the details of the source tile images.
227 //
228 // Future Work:
229 // ------------
230 // There are a few things that could be explored in the future:
231 //
232 // -A better tile picking algorithmn that considers the average hue of potential
233 // tile images and what hues have not been found already, thus producing a better
234 // tile hue gammut.
235 //
236 // -Exploring the use of outlines between tiles (like a white pixel border), or
237 // even other tile shapes than rectangles like puzzle pieces. Personally I consider
238 // these effects gimmicky, they detract from the overall image which I don't like.
239 //
240 // -A differnt distance-based picking algorthm that just works in the hue domain.
241 // I'm not sure this is a good thing since the current approach also most closely
242 // matches luminance and saturation making any modifications along these dimensions
243 // minimal, and minimally changing the tile images is a good thing.//
244 //----------------------------------------------
245 
246 
247 //====================================================
248 MosaicOptions::MosaicOptions( QStringList files, QSize tileSize, StatusWidget* status )
249  : ManipulationOptions( status )
250 {
251  this->files = files;
252  this->tileSize = tileSize;
253 }
254 QStringList MosaicOptions::getFileList() { return files; }
256 //====================================================
257 
258 //a decent color set uses 216 colors
259 #define MAX_TILES 216
260 
261 //==============================================
262 struct Tile
263 {
264  //tile image
265  QImage image;
266 
267  //average color
268  QColor avgColor;
269 
270  //average saturation, and luminosity
271  int avgS, avgL;
272 };
273 //==============================================
274 struct TileSet
275 {
276  //tiles
277  Tile tiles[MAX_TILES];
278 
279  //number of initialized tiles in set
281 };
282 //==============================================
283 //create to tilesets. color tiles will be used for fast previews,
284 //image tiles will be used when actually applying the effect
287 //==============================================
288 //declare these functions here, we'll define them below
289 void constructColorTiles(QSize tileSize);
290 void constructImageTiles(QStringList files, QSize tileSize);
291 void splatBestTile(QImage* image, QPoint topLeftCorner, TileSet* tileSet);
292 //==============================================
293 QImage* mosaicEffect( QString filename, MosaicOptions* options )
294 {
295  //load image
296  QImage* editedImage = new QImage( filename );
297 
298  //convert to 32-bit depth if necessary
299  if( editedImage->depth() < 32 )
300  {
301  QImage* tmp = editedImage;
302  editedImage = new QImage( tmp->convertDepth( 32, Qt::AutoColor ) );
303  delete tmp; tmp=NULL;
304  }
305 
306  //determine if busy indicators will be used
307  bool useBusyIndicators = false;
308  StatusWidget* status = NULL;
309  if( options != NULL && options->getStatus() != NULL )
310  {
311  useBusyIndicators = true;
312  status = options->getStatus();
313  }
314 
315  //intialize seed using current time
316  srand( unsigned(time(NULL)) );
317 
318  //determine tile size
319  QSize tileSize;
320  if(options == NULL) tileSize = QSize(6,6); //6 is big enough to be visible, but not so blocky the image looks bad
321  else tileSize =options->getTileSize();
322 
323  //construct tile set
324  TileSet* tileSet = NULL;
325  if( options != NULL && options->getFileList().size() > 0 )
326  {
328  tileSet = &imageTiles;
329  }
330  else
331  {
332  constructColorTiles(tileSize);
333  tileSet = &colorTiles;
334  }
335 
336  //setup progress bar
337  if(useBusyIndicators)
338  {
339  QString statusMessage = qApp->translate( "mosaicEffect", "Applying Mosaic Effect:" );
340  status->showProgressBar( statusMessage, 100 );
341  qApp->processEvents();
342  }
343 
344  //update progress bar for every 1% of completion
345  const int updateIncrement = (int) ( (0.01 * editedImage->width() * editedImage->height()) /
346  (tileSize.width() * tileSize.height()) );
347  int newProgress = 0;
348 
349  //iterate over each selected scanline
350  int x, y;
351  for(y=0; y<editedImage->height(); y+=tileSize.height())
352  {
353  for( x=0; x<editedImage->width(); x+=tileSize.width())
354  {
355  //splat the best tile
356  splatBestTile( editedImage, QPoint(x,y), tileSet );
357 
358  //update status bar if significant progress has been made since last update
359  if(useBusyIndicators)
360  {
361  newProgress++;
362  if(newProgress >= updateIncrement)
363  {
364  newProgress = 0;
365  status->incrementProgress();
366  qApp->processEvents();
367  }
368  }
369 
370  }
371  }
372 
373  //return pointer to edited image
374  return editedImage;
375 }
376 //==============================================
377 //Initialize a general color tile set using pure tones.
379 {
380  //max tiles must be allocated across all colors, so find resolution we'll have for each color
381  //channel (e.g. if max tiles is 100, 100^(1/3) ~= 4.6 so we'll use 4 unique red, green, and
382  //blue color values for constructing tiles and use 4^3=64 tiles out of the 100 allocated
383  int colorRes = (int)pow( MAX_TILES, 1.0/3 );
384 
385  //always include 0 and 255 so increment is always totalSpan/(count-1)
386  int colorIncrement = 255 / (colorRes-1);
387 
388  colorIncrement = 51;
389 
390  //create actual tiles
391  int tile=0;
392  int r,g,b;
393  for(r=0; r<=255; r+=colorIncrement)
394  {
395  for(g=0; g<=255; g+=colorIncrement)
396  {
397  for(b=0; b<=255; b+=colorIncrement)
398  {
399  colorTiles.tiles[tile].image.create( tileSize.width(), tileSize.height(), 32);
400  colorTiles.tiles[tile].image.fill( qRgb(r, g, b) );
401 
402  colorTiles.tiles[tile].avgColor = QColor(r,g,b);
403 
404  int h;
405  QColor(r,g,b).getHsv( &h, &(colorTiles.tiles[tile].avgS), &(colorTiles.tiles[tile].avgL) );
406  tile++;
407  }
408  }
409  }
410 
411  //setup number of initialized tiles
412  colorTiles.numInitialized = tile;
413 }
414 //==============================================
415 //Initialize an image based tile set
416 void constructImageTiles(QStringList files, QSize tileSize)
417 {
418  //---------------------------------
419  //setup number of initialized tiles
420  imageTiles.numInitialized = MIN(files.size(), MAX_TILES);
421  //---------------------------------
422  //create file index list, we'll use this to construct a
423  //list of indices to the randomply picked files from the master list
424  int* fileIndices = new int[imageTiles.numInitialized];
425  int* fileIndicesUsed = new int[files.size()];
426  int i;
427  for(i=0; i<imageTiles.numInitialized; i++) { fileIndices[i] = -1; }
428  for(i=0; i<((int)files.size()); i++) { fileIndicesUsed[i] = 0; }
429  //---------------------------------
430  //pick the random files, updating the file indices list
431  for(i=0; i<imageTiles.numInitialized; i++)
432  {
433  double percentage = ((double)rand()) / RAND_MAX;
434  int fileNum = (int) ( (files.size() - (i+1)) * percentage);
435 
436  //correct index by offsetting by all files that have been picked before this one
437  int j = 0;
438  int realFileNum = fileNum;
439  while( fileNum >= 0)
440  {
441  if( fileIndicesUsed[j] == 1 ) { realFileNum++; }
442  else { fileNum--; }
443 
444  j++;
445  }
446 
447  //record file index into list
448  fileIndices[i] = realFileNum;
449  fileIndicesUsed[realFileNum] = 1;
450  }
451 
452  //---------------------------------
453  //sort the file index list - bubble sort is fast enough right? :-)
454  int j;
455  for( i=imageTiles.numInitialized-1; i>0; i--)
456  {
457  for( j=0; j<i; j++)
458  {
459  if( fileIndices[j] > fileIndices[j+1] )
460  {
461  int tmp = fileIndices[j+1];
462  fileIndices[j+1] = fileIndices[j];
463  fileIndices[j] = tmp;
464  }
465  }
466  }
467  //---------------------------------
468  //construct truncated list of files that we'll use
469  QStringList chosenFiles;
470  QStringList::iterator it;
471  int curFileIndex = 0;
472  int nextDesiredFileIndex = 0;
473  for(it = files.begin(); it != files.end(); it++ )
474  {
475  if( curFileIndex == fileIndices[nextDesiredFileIndex] )
476  {
477  chosenFiles.append( *it );
478  nextDesiredFileIndex++;
479 
480  if( nextDesiredFileIndex >= imageTiles.numInitialized ) break;
481  }
482 
483  curFileIndex++;
484  }
485 
486  //resetting numInitialized should not be necessary, we should have the right
487  //number of files in chosenFiles, but as a sanity check, we'll reset it here again.
488  imageTiles.numInitialized = MIN((int)chosenFiles.size(), imageTiles.numInitialized);
489 
490  //---------------------------------
491  //free up the temporary index list, it's nolonger needed since we now have an
492  //actual list of the chosen files
493  delete fileIndices;
494  delete fileIndicesUsed;
495  fileIndices = NULL;
496  fileIndicesUsed = NULL;
497  //---------------------------------
498  //ok, we now have a list of files we actually want to use to create tiles from, that have
499  //been randomly chosen from the huge list we were given. now actually create the tiles
500  int tile = 0;
501 
502  for(it = chosenFiles.begin(); it != chosenFiles.end(); it++ )
503  {
504  //scale image to definately fill a tileSizeW x tileSizeH region, we'll crop down afterwards
505  QSize imageRes;
506  getImageSize( *it, imageRes );
507 
508  int intermediateWidth = -1;
509  int intermediateHeight = -1;
510  if( ((double)imageRes.width()) / tileSize.width() > ((double)imageRes.height()) / tileSize.height() )
511  {
512  intermediateHeight = tileSize.height();
513  intermediateWidth = (int) ( ((1.0*intermediateHeight*imageRes.width()) / imageRes.height()) + 0.5 );
514  }
515  else
516  {
517  intermediateWidth = tileSize.width();
518  intermediateHeight = (int) ( ((1.0*intermediateWidth*imageRes.height()) / imageRes.width()) + 0.5 );
519  }
520 
521  QImage scaledImage;
522  scaleImage( *it, scaledImage, intermediateWidth, intermediateHeight );
523 
524  //scaleImage does not like to scale more than 2x, so if image is not the right size scale it up again
525  if( scaledImage.width() != tileSize.width() || scaledImage.height() != tileSize.height() )
526  scaledImage = scaledImage.scaled( tileSize, Qt::IgnoreAspectRatio );
527 
528  //construct tile image
529  imageTiles.tiles[tile].image.create( tileSize.width(), tileSize.height(), 32);
530  imageTiles.tiles[tile].image.fill( qRgb(255,255,255) );
531 
532  //crop scaledimage to tileSizeW x tileSizeH - simultaniously compute statistics about tile
533  int xOffset = (scaledImage.width() - tileSize.width())/2;
534  int yOffset = (scaledImage.height() - tileSize.height())/2;
535  int x, y;
536  uchar* scaledScanLine;
537  uchar* croppedScanLine;
538  QRgb* scaledRgb;
539  QRgb* croppedRgb;
540 
541  double avgR=0; double avgG=0; double avgB=0;
542  double avgS=0; double avgL=0;
543 
544  //sometimes corrupt images can get through, so this check
545  //bulletproofs the code
546  if( scaledImage.isNull() )
547  {
548  avgR = avgG = avgB = 255;
549  avgS = avgL = 255;
550  }
551  else
552  {
553  for( y=0; y<tileSize.height(); y++)
554  {
555  scaledScanLine = scaledImage.scanLine(y + yOffset);
556  croppedScanLine = imageTiles.tiles[tile].image.scanLine(y);
557 
558  for( x=0; x<tileSize.width(); x++)
559  {
560  scaledRgb = ((QRgb*) scaledScanLine) +x + xOffset;
561  croppedRgb = ((QRgb*) croppedScanLine) + x;
562 
563  //copy pixel color over
564  *croppedRgb = *scaledRgb;
565 
566  //update statistics
567  QColor color( *croppedRgb );
568 
569  avgR += color.red();
570  avgG += color.green();
571  avgB += color.blue();
572 
573  int h,s,l;
574  color.getHsv( &h, &s, &l );
575  avgS += s;
576  avgL += l;
577  }
578  }
579 
580  //average red, green, blue, saturation, and luminance sums
581  int pixelCount = tileSize.width()*tileSize.height();
582  avgR /= pixelCount;
583  avgG /= pixelCount;
584  avgB /= pixelCount;
585  avgS /= pixelCount;
586  avgL /= pixelCount;
587  }
588  //store statistics
589  imageTiles.tiles[tile].avgColor = QColor( (int)avgR, (int)avgG, (int)avgB );
590  imageTiles.tiles[tile].avgS = (int)avgS;
591  imageTiles.tiles[tile].avgL = (int)avgL;
592 
593  //move on to next tile
594  tile++;
595  }
596  //---------------------------------
597 }
598 //==============================================
599 //Pseudo-randomly pick the best tile from the specified tileset and splat
600 //it on the image
601 void splatBestTile(QImage* image, QPoint topLeftCorner, TileSet* tileSet)
602 {
603  int x, y;
604  QRgb* imageRgb;
605  QRgb* tileRgb;
606  uchar* imageScanLine;
607  uchar* tileScanLine;
608  //------------------------------
609  //dermine boundary we'll be iterating over
610  int xMin = 0;
611  int xMax = MIN( tileSet->tiles[0].image.width(), image->width() - topLeftCorner.x() );
612  int yMin = 0;
613  int yMax = MIN( tileSet->tiles[0].image.height(), image->height() - topLeftCorner.y() );
614  //------------------------------
615  //find most common hue, and average color, saturation and luminance for this portion of the image
616  double avgR=0; double avgG=0; double avgB=0;
617  int hueHist[361];
618  int i;
619  for(i=0; i<361; i++) { hueHist[i] = 0; }
620  double avgS=0; double avgL=0;
621 
622  for( y=yMin; y<yMax; y++)
623  {
624  imageScanLine = image->scanLine(y+topLeftCorner.y());
625  for( x=xMin; x<xMax; x++)
626  {
627  imageRgb = ((QRgb*)imageScanLine+x+topLeftCorner.x());
628  QColor color( *imageRgb );
629 
630  avgR += color.red();
631  avgG += color.green();
632  avgB += color.blue();
633 
634  int h,s,l;
635  color.getHsv( &h, &s, &l );
636  hueHist[ MIN( MAX(h,0), 360 ) ]++;
637  avgS += s;
638  avgL += l;
639  }
640  }
641 
642  //average red, green, blue, saturation, and luminance sums
643  int pixelCount = (yMax-yMin) * (xMax-xMin);
644  avgR /= pixelCount;
645  avgG /= pixelCount;
646  avgB /= pixelCount;
647  avgS /= pixelCount;
648  avgL /= pixelCount;
649 
650  //walk through hue histogram and find most common hue
651  int mostCommonHue = 0;
652  for(i=1; i<361; i++)
653  {
654  if( hueHist[i] > hueHist[mostCommonHue] ) { mostCommonHue = i; }
655  }
656 
657  //------------------------------
658  //compute distance between this region and all initialized tiles
659  double* distances = new double[tileSet->numInitialized];
660 
661  double dR, dG, dB;
662  double rBar;
663  for(i=0; i<tileSet->numInitialized; i++)
664  {
665  dR = tileSet->tiles[i].avgColor.red() - avgR;
666  dG = tileSet->tiles[i].avgColor.green() - avgG;
667  dB = tileSet->tiles[i].avgColor.blue() - avgB;
668  rBar = 0.5* (tileSet->tiles[i].avgColor.red() + avgR);
669 
670  //we could find the distance between this region and the tile by comparing the colors
671  //directly as 3d points (sqrt(dR*dR + dG*dG + dB*dB)) but this would not
672  //take into account their reltive perceptual weights. I found
673  //some work by Thiadmer Riemersma that suggest I use this equation instead...
674  //http://www.compuphase.com/cmetric.htm
675  distances[i] = ((2+(rBar/256)) * dR * dR) +
676  (4 * dG * dG) +
677  ((2 + ((255.0-rBar)/256)) * dB * dB);
678  }
679  //------------------------------
680  //pick tile using pseudo-random distance biased approach
681 
682  //take reciprocol of all distances and find sum
683  double sum = 0;
684  double epsilon = 0.000000001;
685  for(i=0; i<tileSet->numInitialized; i++)
686  {
687  distances[i] = 1.0 / MAX(distances[i], epsilon);
688  sum += distances[i];
689  }
690 
691  //get a random number and find appropriate tile
692  double percentage = ((double)rand()) / RAND_MAX;
693  double number = sum * percentage;
694  int TILE = 0;
695  sum = 0;
696  for(i =0; i<tileSet->numInitialized; i++)
697  {
698  sum += distances[i];
699  if( sum >= number)
700  {
701  TILE = i; break;
702  }
703  }
704 
705  delete distances;
706  distances = NULL;
707  //------------------------------
708  //determine saturation and luminance multipliers
709  double sInc = avgS - tileSet->tiles[TILE].avgS;
710  double lInc = avgL - tileSet->tiles[TILE].avgL;
711  //------------------------------
712 
713  //finally, splat the tile
714  for( y=yMin; y<yMax; y++ )
715  {
716  //iterate over each selected pixel in scanline
717  imageScanLine = image->scanLine( (y+topLeftCorner.y()) );
718  tileScanLine = tileSet->tiles[TILE].image.scanLine(y);
719  for( x=xMin; x<xMax; x++)
720  {
721  //get the tile color
722  tileRgb = ((QRgb*) tileScanLine) + x;;
723  QColor color( *tileRgb );
724 
725  //convert to hsl
726  int h,s,l;
727  color.getHsv( &h, &s, &l );
728 
729  //replace hue with the most common hue from this region of the target image
730  h = mostCommonHue;
731 
732  //adjust saturation and luminance to more closely match the average values
733  //found in this region of the target image.
734  s = (int)MIN( MAX( s+sInc, 0), 255 );
735  l = (int)MIN( MAX( l+lInc, 0), 255 );
736 
737  //convert back to rgb
738  color.setHsv( mostCommonHue, s, l );
739 
740  //splat the adjusted tile color onto the image
741  imageRgb = ((QRgb*)imageScanLine) + x + topLeftCorner.x();
742 
743  *imageRgb = color.rgb();
744  }
745  }
746 
747 }
748 //==============================================
#define MAX_TILES
Definition: mosaic.cpp:259
int updateIncrement
MosaicOptions(QStringList files, QSize tileSize, StatusWidget *status)
Definition: mosaic.cpp:248
QStringList getFileList()
Definition: mosaic.cpp:254
int avgS
Definition: mosaic.cpp:271
StatusWidget * getStatus()
QColor avgColor
Definition: mosaic.cpp:268
void incrementProgress()
Updates the progress bar by one step.
QImage * mosaicEffect(QString filename, MosaicOptions *options)
Definition: mosaic.cpp:293
void showProgressBar(QString message, int numSteps)
Initializes the progress bar.
long b
Definition: jpegInternal.h:125
void splatBestTile(QImage *image, QPoint topLeftCorner, TileSet *tileSet)
Definition: mosaic.cpp:601
QImage image
Definition: mosaic.cpp:265
Tile tiles[MAX_TILES]
Definition: mosaic.cpp:277
QStringList files
Definition: mosaic.h:35
TileSet imageTiles
Definition: mosaic.cpp:286
StatusWidget * status
int avgL
Definition: mosaic.cpp:271
Definition: mosaic.cpp:262
#define MAX(x, y)
Definition: mosaic.cpp:20
bool scaleImage(QString fileIn, QString fileOut, int newWidth, int newHeight)
Scale image and save copy to disk.
Definition: imageTools.cpp:157
QSize tileSize
Definition: mosaic.h:36
bool getImageSize(const char *filename, QSize &size)
Get image dimensions.
Definition: imageTools.cpp:192
#define MIN(x, y)
Definition: mosaic.cpp:19
void constructImageTiles(QStringList files, QSize tileSize)
Definition: mosaic.cpp:416
QSize getTileSize()
Definition: mosaic.cpp:255
TileSet colorTiles
Definition: mosaic.cpp:285
QImage * editedImage
void constructColorTiles(QSize tileSize)
Definition: mosaic.cpp:378
int newProgress
int numInitialized
Definition: mosaic.cpp:280