Webpraxis Consulting Ltd.: img2PhotographicMosaic(threaded).pl

Introduction

Metrics

Pruning

Blueprint

Threads

XML Input

Code Listing

Code Details

Benchmark

Gallery

img2PhotographicMosaic(threaded).pl

Photographic Mosaics: Part II - Threaded Photo-Mosaic Image Filter

With the tile-generator script prep4PhotographicMosaic(threaded).pl up and running, we now discuss composing photographic mosaics. The process primarily involves selecting the tiles that "best" match each sub-section of a reference image. Many rules are possible for deciding what constitutes a "best" match. We are restricting ourselves to criteria that select the tile whose mean normalized RGB value is "closest" to that of the associated area of the reference image. In turn, closeness is gauged by some distance measure as defined by a metric function.

Our mosaic filter offers the choice of three distance functions. All are members of the family of Minkowski metrics:

Setting k = 1 yields the Manhattan metric

whereas k = 2 yields the Euclidean metric

In the limit as k tends to infinity, we have the Max metric

The differences between them can be illustrated as follows. Set ε as the greater-than-zero value of the k-Minkowski metric for all values of k. Furthermore, let P be a fixed point in R³. Then the loci of points Q that satisfy L_k(P,Q) = ε define various nested geometrical figures. For k → ∞, the figure is a cube whereas, for k = 2, it's a sphere inscribed within the previous cube and, for k = 1, it's an octahedron inscribed within the previous sphere. Think of this as a set of Matryoshka dolls with the loci of the Manhattan metric being the innermost doll and that of the Max metric the outermost.

If the distances to a fixed point are computed for a discrete set of coordinates, then the points that minimize one metric will not necessarily do so for another metric. This is readily illustrated by the following simple example:

Point Coordinates			Distance to the Origin
x	y	z	Manhattan	Euclidean	Max
5	5	5	15.00	8.66	5.00
4	6	4	14.00	8.25	6.00
3	5	5.9	13.90	8.30	5.90

Thus, depending on which metric is used, different best-matching tiles will undoubtedly be chosen, resulting in different mosaics: see our gallery below for examples. Which variation leads to a more visually pleasing result is then a matter of subjective assessment.

Finding a best-matching tile amounts so far to evaluating a metric for every available tile and retaining the tile that minimizes the metric. Clearly though, for "large" tile sets, this linear search is a very computationally demanding process. The computational time can be drastically reduced however if one diminishes the tile set for each image sub-section under consideration.

So our program offers a pruning option. It is loosely inspired by the k-dimensional tree space-partitioning technique. All the tile RGB values are segregated according to three mutually orthogonal planes containing the centroid of the distribution as the common point: the planes are also orthogonal the RGB cube faces. For our collection of 3,111 tiles, this results in the following 8 sub-spaces of the normalized RGB cube:

It is a simple task to partition the tile data numerically. One only needs to ascertain whether an RGB triplet is above or below the centroid, to the left or right of it and in front or behind it: equalities are simply treated as one of the conditional branches. This is a one-time, computationally cheap task that is carried out before any tile matching commences.

When the time comes to find a best-matching tile, an image sub-section is first assigned membership to one of the sub-spaces. This is done by subjecting it to the same aforementioned conditionals. A linear search is then conducted with only the tiles in that sub-space. Though the number of tiles per sub-space is not likely to be balanced, it is hoped that, on average, the searches will approximately involve 1/8 of the total number of tiles.

As opposed to the standard nearest-neighbor search with a kd-tree, no attempt is carried out here to verify whether the "correct" best matching tile might actually lie in one of the adjacent sub-spaces. You may well think that this is heresy! However, remember that the final objective is the production of a visually pleasing mosaic. And to that end, different tile sets and metrics can be employed with more far-reaching consequences. There is no absolutely correct answer here whether the search is truncated or not.

As was indicated in our previous article regarding the tile-generator script prep4PhotographicMosaic(threaded).pl, our mosaic-filter script lets one specify which tiles sets are to be used. But what if one wants to exclude specific tiles within any given set? Recall that the nomenclature for the tile filenames is "tile_nnn.gif" where "nnn" denotes the positive integer representing the tile's code. Trying to identify a specific tile becomes quite an arduous task if one has to visually inspect the tiles in order to identify the desired tile.

Thus, along with the actual mosaic image, the filter script creates an HTML blueprint file. It contains all the necessary instructions for assembling the full-size mosaic, tile by tile. That is, upon loading, it will write out the required image tag for each tile file. All source attributes are absolute references to the local tile directory specified for the creation of the mosaic. Being therefore a very compact representation of the mosaic, the onus is placed on the browser's JavaScript engine to write out the instructions as quickly as possible and on the browser itself to render them.

With the mosaic now rendered piecewise, it is just a matter of clicking on a tile to have an "alert" box pop up with the tile's code. Moreover, as an aid in assessing the consequences of eventually excluding a tile, the blueprint file displays the tile histogram where the number of occurrences of each tile is listed. Here's a partial screenshot for one of our Mona Lisa mosaics:

It is then just a matter of specifying the codes in order to have those tiles excluded from consideration on the next run of the script.

The coding strategy used is similar in overall structure to that of the associated tile-generator script. Concurrent processing is again exploited using a parallel pipeline model. Tasks are allocated to various threads and the inter-thread communication is accomplished via thread queues as follows. Thread #0, i.e. the main program, is responsible for defining the mosaic parameters and listing all the tile specifications (layout index, width, height and coordinate offsets) to a first queue. Multiple secondary threads are assigned the task of matching a tile for each geometric specification retrieved from the queue. Moreover, each best-matching tile is then overlaid on the mosaic canvas. In turn, these threads report their results to a second queue. These latter values are concurrently dequeued by one last additional thread in order to create the HTML blueprint. After writing the mosaic image to file, the main program displays the result. Finally, note that all the secondary threads terminate "gracefully" upon being informed by an upstream thread, also via the thread queues, that no more data is forthcoming. The whole process can be illustrated by the following simplified conceptual Petri Net where the repetition arcs have been omitted:

Petri Net for img2PhotographicMosaic(threaded).pl

The above architecture is far from being the only possibility. After trying many variants, it was adopted as being better for dual-core systems. On systems supporting more cores, one could attempt having a certain number of threads just for tile matching and another number just for tile overlaying, acting either concurrently or sequentially. We leave it to the reader to try out different pipeline structures.

As was the case for the tile-generator script, entering all the script's specifications as arguments on the command line would not be practical. Instead, the path of an XML file, containing all the necessary processing specifications, will be the sole argument. It is a straightforward matter to create/edit such a file with any text-processing application. Moreover, it nicely documents how a mosaic was created.

To explain the required XML tags, let's examine the data file mona.xml ( Download ):

XML file "mona.xml"	Remarks
<img2PhotographicMosaic noThreads="" metric="Manhattan" pruning="yes">	Specifies the root as "img2PhotographicMosaic". The first attribute declares the number of tile-matching/overlaying threads to use. When not specified, the Perl script will default to the number of processors reported in the Windows environment. This latter value includes both real and logical processors. Next, the metric used to assess the tile matches is specified: "Manhattan" is the default and "Euclidean" and "Max" are the other two options. Finally, tile pruning is requested (default value). Setting it to "no" will invoke a strictly linear search.
<image file="_sources/Mona_Lisa.jpg" />	Declares the location of the source image to filter.
<mosaic file="_mosaics/Mona_Lisa.jpg" />	Sets the path for the resulting mosaic.
<blueprint file="_blueprints/Mona_Lisa.htm" />	Sets the path for the resulting HTML blueprint.
<tiles width="16" height="16" dir="_tiles/tiles_16x16" />	Specifies the pixel dimensions of the tiles. Moreover, it names the folder where the tiles are located along with the associated database file.
<collections>paris,plants,samples,sky,space</collections>	Lists the tile subsets to use by referencing their associated collection names. These are the same names that were defined when creating the tiles with the tile generator script, i.e., <images collection="paris" topDir="_images/ABB_paris" /> Note that, if all the tile subsets are to be considered, then the following wildcard declaration can be used instead of listing each collection individually: *<collections>< /collections>**
<exclude>68,1439,1632,2466,2471,2478,2552</exclude>	Lists the codes for the tiles to be excluded from consideration, as in "tile_68.gif". These are the values reported by the HTML blueprint when individual tiles are clicked on. They are also reported in the accompanying tile histogram. If no tiles are to be excluded, then this entry should be left blank, viz., <exclude></exclude> or, more simply. <exclude />.
</tiles>	Ends the declarations regarding the tiles.
</img2PhotographicMosaic>	end of the XML declarations

N.B.: There is no XSLT style sheet associated with the XML file. One is therefore at liberty to express daughter nodes as attributes and vice-versa. Moreover, they can be declared in any order. For example, one could write the following if all the tile subsets were to be used with no exclusions:

					<tiles collections="*" width="16"  exclude="" height="16" dir="_tiles/tiles_16x16" />
				

The above scheme was implemented on a Windows XP Pro platform using Perl with the imports for threads and thread queues, along with ImageMagick's drawing primitives accessed through its PerlMagick interface. The content of the XML file is read in with the aid of the CPAN modules XML::Simple and XML::Parser.

The resulting script, img2PhotographicMosaic(threaded).pl ( Download latest version: v2.0.1 - SHA1 Checksum: E6672DD5A4D3406C71A9D6984AEC3910A58E76B9 ), is released for personal, non-commercial and non-profit use only.

The listing includes the line numbers in order to reference them in the general remarks in the next section.

001 #ActivePerl v5.10.1, build 1007 for MSWin32-x86-multi-thread
002 #===== Copyright 2011, Webpraxis Consulting Ltd. - ALL RIGHTS RESERVED - Email: webpraxis@gmail.com ============================
003 # img2PhotographicMosaic(threaded).pl: Threaded photographic-mosaic image filter.
004 #===============================================================================================================================
005 #           Usage : perl img2PhotographicMosaic(threaded).pl XmlFile
006 #       Arguments : XmlFile = path of the XML file detailing the processing specifications.
007 #     Input Files : - The image file to be rendered as a mosaic.
008 #                   - The GIF tiles in the designated directory along with the associated database file "_tiles.dat"
009 #                     created by the Perl script "prep4PhotographicMosaic(threaded).pl".
010 #    Output Files : - Mosaic image, in accordance with the specified pathname.
011 #                   - A tentative backup copy of any previous mosaic file if one exists with the same filename. In which
012 #                     case, the basename will have the smallest possible positive integer, enclosed in parentheses, appended to
013 #                     it such that it ensured a non-conflicting filename. It will be retained only if it differs with the newly
014 #                     created mosaic.
015 #                   - A tentative backup copy of any previous blueprint file if one exists with the same filename. In which
016 #                     case, the basename will have the smallest possible positive integer, enclosed in parentheses, appended to
017 #                     it such that it ensured a non-conflicting filename. It will be retained only if it differs with the newly
018 #                     created blueprint.
019 # Temporary Files : None.
020 #         Remarks : See http://www.webpraxis.ab.ca/photo_mosaic_v2/img2PhotographicMosaic(threaded).php for details.
021 #         History : v2.0.1 - March 31, 2012 - Added chomp to tile-data read. v2.0.0 - April 20, 2011 - Original release.
022 #===============================================================================================================================
023 # 0) INITIALIZE:
024 use strict;                                                                                 #pragma to restrict unsafe constructs
025 use warnings;                                                                               #pragma for all optional warnings
026 use Time::HiRes qw(gettimeofday tv_interval);                                               #high resolution interval timer, v1.9721
027 use File::Basename;                                                                         #core module to parse file specifications
028 use File::Compare;                                                                          #core module to compare files
029 use File::Copy;                                                                             #core module to copy files
030 use File::Spec;                                                                             #core module to perform operations on file names
031 use Image::Magick;                                                                          #PerlMagick from ImageMagick-6.6.3-4-Q16 Win package
032 use POSIX qw(HUGE_VAL ceil);                                                                #core module
033 use Term::ANSIScreen qw/:color :cursor :screen/;                                            #terminal control using ANSI escape sequences, v1.42
034 use Win32::Console::ANSI qw/ Cursor /;                                                      #emulate ANSI console on Win32 system, v1.04
035 use threads;                                                                                #pragma for interpreter-based threads, v1.79
036 use threads::shared;                                                                        #pragma for sharing data structures between threads, v1.33
037 use Thread::Queue;                                                                          #core module for thread-safe queues, v2.11
038 use XML::Simple;                                                                            #module to maintain XML files, v2.18
039     $XML::Simple::PREFERRED_PARSER = 'XML::Parser';                                         #set module to parse XML documents, v2.36-r1
040 use constant FATAL => colored ['white on red'],"\n\n\aFATAL ERROR:",colored ['reset'], ' '; #intro msg when reporting a fatal error
041 
042 my $StartTime   = [gettimeofday];                                                           #record start of execution time
043 
044 $| = 1;                                                                                     #set STDOUT buffer to auto-flush
045 cls();                                                                                      #clear screen
046 print colored ['black on white'], "$0\n\n\n",                                               #display program name
047       colored ['bold white on black'], 'Initializing...';                                   #report start of processing
048 
049 ( my $XmlFile   = shift ) =~ tr#\\#/#;                                                      #get path of XML file (Unix style)
050 die FATAL, "Cannot locate the XML file '$XmlFile' -" unless -e $XmlFile;                    #check its existence
051 
052 my $Specs       = XMLin( $XmlFile, SuppressEmpty => undef );                                #read the XML data file for specifications
053 
054 my $N           = $$Specs{noThreads}        || $ENV{NUMBER_OF_PROCESSORS} + 1;              #parameterize number of tile-overlaying threads
055 my $L           = $$Specs{metric}           || 'Manhattan';                                 #parameterize Minkowski metric
056 my $Pruning     = lc( $$Specs{pruning} )    || 'yes';                                       #parameterize tile-pruning option
057 die FATAL, 'Invalid number of threads -' unless $N > 0;                                     #check that there's at least one thread
058 die FATAL, "Unrecognized metric selection '$L' -"                                           #check validity of metric specification
059  unless ( $L eq 'Manhattan' ) or ( $L eq 'Euclidean' ) or ( $L eq 'Max' );
060 die FATAL, "Unrecognized pruning option '$Pruning' -"                                       #check validity of pruning option
061  unless ( $Pruning eq 'yes' ) or ( $Pruning eq 'no' );
062 
063 my $ImageFile   = $$Specs{image}{file};                                                     #parameterize the source image path
064 my $MosaicFile  = $$Specs{mosaic}{file};                                                    #parameterize the mosaic image path
065 my $BluePrtFile = $$Specs{blueprint}{file};                                                 #parameterize the tiling blueprint path
066 die FATAL, "Cannot locate specified source image '$ImageFile' -" unless -e $ImageFile;      #check existence of the source image
067 
068 my $TileWidth   = $$Specs{tiles}{width};                                                    #parameterize pixel width of a tile
069 my $TileHeight  = $$Specs{tiles}{height};                                                   #parameterize pixel height of a tile
070 my $Collections = $$Specs{tiles}{collections};                                              #get tile collection names
071 my $TileDir     = $$Specs{tiles}{dir};                                                      #parameterize tile directory
072 my $TileData    = "$TileDir/_tiles.dat";                                                    #set the filepath for the tile data
073 die FATAL, "Invalid tile width '$TileWidth' -" unless $TileWidth > 0;                       #check validity
074 die FATAL, "Invalid tile height '$TileHeight' -" unless $TileHeight > 0;                    #check validity
075 die FATAL, "No tile collection names specified -" unless $Collections;                      #check validity
076 die FATAL, "Cannot locate specified tile directory '$TileDir' -" unless -d $TileDir;        #check existence of the tile directory
077 die FATAL, "Cannot locate the tile data file '$TileData' -" unless -e $TileData;            #check existence of the tile database
078 die FATAL, "The tile data file '$TileData' is empty -" unless -s $TileData;                 #check for non-empty tile database
079 
080 my $Manifest            = '';                                                               #tile-collection manifest report
081 my $NoExclude           = 0;                                                                #number of excluded tiles
082 my $NoTiles4Matching;                                                                       #number of tiles available for matching
083 my @Centroid;                                                                               #centroid RGB coordinates of the tile distribution
084 my @TileRGB;                                                                                #normalized RGB tile values for matching
085 {                                                                                           #start naked block
086     my %tileManifest;                                                                       # hash for the tile manifest
087     my %tileExclude = map{ 'tile_' . $_ . '.gif', 1 } split( /,/, $$Specs{tiles}{exclude} ) # hash for the tiles to be excluded
088      if defined $$Specs{tiles}{exclude};
089     $NoExclude      = scalar keys %tileExclude;                                             # count number of tiles to be excluded
090     my $collName;                                                                           # name of a tile's associated image collection
091     my $key;                                                                                # tile database key = tile filename
092     my $value;                                                                              # tile database value = TSV string of tile data
093     my @rgb;                                                                                # array of RGB values for a tile
094 
095     local *DATA;                                                                            # input filehandle for the tile database
096 
097     open( DATA, $TileData )                                                                 # open the tile data file for read
098      or die FATAL, "Cannot open the tile data file '$TileData' for read: $! -";
099     while( chomp( ( $key, $collName, @rgb ) = split /\t/, <DATA> ) ) {                      # repeat for each tile record; parse data
100         next if defined $tileExclude{$key};                                                 #  skip if record is to be excluded
101         next unless ( $Collections eq '*'                       ) or                        #  skip record unless all collections to be used or
102                     ( $Collections =~ /(^|,)\Q$collName\E(,|$)/ );                          #   collection specified explicitly
103         push @{ $TileRGB[8]{$key} }, @rgb;                                                  #  record tile's mean normalized RGB values
104         ++$tileManifest{"$collName"};                                                       #  update tile manifest
105         $Centroid[$_] += $rgb[$_] for( 0..2 );                                              #  sum RGB coordinate component for centroid
106     }                                                                                       # until all tile records processed
107     close( DATA );                                                                          # close the tile data file
108 
109     $NoTiles4Matching   = scalar keys %{$TileRGB[8]};                                       # determine number of tiles available for matching
110     die FATAL, " No tiles available for matching -" unless $NoTiles4Matching;               # check that tiles are available
111 
112     $Manifest           = join ",\n" . ' ' x 18,                                            # compose the manifest report
113                                 map{ "$_ [$tileManifest{$_}]" } sort keys %tileManifest;    #  as "collection name [tile total]"
114     $Centroid[$_]       /= $NoTiles4Matching for( 0..2 );                                   # compute centroid coordinate
115 
116     if( $Pruning eq 'yes' ) {                                                               # if pruning requested
117         while( ( $key, $value ) = each %{$TileRGB[8]} ) {                                   #  repeat for each tile: assign to octant
118             my $octant              = 0;                                                    #   init sub-space index
119             vec( $octant, $_, 1 )   = ( $Centroid[$_] > @{ $value }[$_] ) for ( 0..2 );     #   determine octant, bit by bit, relative to centroid
120             $TileRGB[$octant]{$key} = $TileRGB[8]{$key};                                    #   assign tile to octant
121             delete $TileRGB[8]{$key};                                                       #   delete tile from general population
122         }                                                                                   #  until all tiles segregated
123         pop @TileRGB;                                                                       #  shorten the array
124         do{ die FATAL, " No tiles available for matching in one of the octants -"           #  check for tiles in each octant
125              unless scalar keys %{$TileRGB[$_]};
126           } for( 0..7 );
127     } else {                                                                                # else no pruning
128         splice @TileRGB, 0, 8;                                                              #  shorten the array
129     }                                                                                       # end if-else
130 
131     undef %tileManifest;                                                                    # discard work hashes
132     undef %tileExclude;
133 }                                                                                           #end naked block
134 
135 my $Image           = Image::Magick->new();                                                 #instantiate an image object for the source image
136 $Image->Read( "$ImageFile" );                                                               #init with source image file
137 $Image->Quantize( colorspace => 'RGB' );                                                    #insure correct colorspace
138 my ( $ImageWidth, $ImageHeight ) = $Image->Get( 'width', 'height' );                        #get width & height of source image
139 
140 my $NoTileCols      = POSIX::ceil( $ImageWidth  / $TileWidth  );                            #compute integral number of tile columns
141 my $NoTileRows      = POSIX::ceil( $ImageHeight / $TileHeight );                            #compute integral number of tile rows
142 my $NoTiles         = $NoTileCols * $NoTileRows;                                            #compute total number of tiles in mosaic
143 my $MosaicWidth     = $NoTileCols * $TileWidth;                                             #compute pixel width of mosaic image
144 my $MosaicHeight    = $NoTileRows * $TileHeight;                                            #compute pixel height of mosaic image
145 my $MosaicComment   =     "XML input file: $XmlFile\n"                                      #create comment for mosaic image
146                         . "Source Image: $ImageFile\n"
147                         . "Mosaic Image: $MosaicFile\n"
148                         . "Blueprint: $BluePrtFile\n\n"
149                         . "Created with \"img2PhotographicMosaic(threaded).pl\",\n"
150                         . "Copyright 2010, Webpraxis Consulting Ltd. - ALL RIGHTS RESERVED\n"
151                         . "Web: http://www.webpraxis.ab.ca/ - Email: webpraxis\@gmail.com";
152 
153 my @Threads;                                                                                #thread description
154 push @Threads, "#0 = main";
155 push @Threads, "#$_ = create mosaic" for ( 1..$N );
156 push @Threads, "#" . ( $N + 1 ) . " = create blueprint.";
157 
158 print "\r", clline,                                                                         #echo initialization results
159       colored ['reset'], 'XML input file  : ', colored ['bold white'], $XmlFile, "\n\n",
160       colored ['reset'], 'Source Image    : ', colored ['bold white'], $ImageFile, "\n",
161       colored ['reset'], ' -Width         : ', colored ['bold white'], $ImageWidth, " px\n",
162       colored ['reset'], ' -Height        : ', colored ['bold white'], $ImageHeight, " px\n\n",
163       colored ['reset'], 'Mosaic Image    : ', colored ['bold white'], $MosaicFile, "\n",
164       colored ['reset'], ' -Width         : ', colored ['bold white'], $MosaicWidth, " px\n",
165       colored ['reset'], ' -Height        : ', colored ['bold white'], $MosaicHeight, " px\n\n",
166       colored ['reset'], 'Mosaic Details  : ', colored ['bold white'], $NoTiles, " tiles\n",
167       colored ['reset'], ' -Tile Width    : ', colored ['bold white'], $TileWidth, " px\n",
168       colored ['reset'], ' -Tile Height   : ', colored ['bold white'], $TileHeight, " px\n",
169       colored ['reset'], ' -No. of Rows   : ', colored ['bold white'], $NoTileRows, "\n",
170       colored ['reset'], ' -No. of Cols   : ', colored ['bold white'], $NoTileCols, "\n\n",
171       colored ['reset'], 'HTML Blueprint  : ', colored ['bold white'], $BluePrtFile, "\n\n",
172       colored ['reset'], 'Collections     : ', colored ['bold white'], $Manifest, "\n",
173       colored ['reset'], ' -No of Tiles   : ', colored ['bold white'], $NoTiles4Matching, " [$NoExclude excluded]\n",
174       colored ['reset'], ' -RGB Centroid  : ', colored ['bold white'], "($Centroid[0], $Centroid[1], $Centroid[2])\n\n",
175       colored ['reset'], 'Metric          : ', colored ['bold white'], $L, "\n",
176       colored ['reset'], 'Pruning         : ', colored ['bold white'], $Pruning, "\n\n",
177       colored ['reset'], 'Threads         : ', colored ['bold white'], join( ",\n" . ' ' x 18, @Threads ), "\n",
178       colored ['reset'], "\n", '-' x 80, "\n\n";
179 
180 my $CursorY         = ( Cursor() )[1];                                                      #record cursor row position
181 #-------------------------------------------------------------------------------------------------------------------------------
182 # 1) CREATE MOSAIC IMAGE & TILING BLUEPRINT:
183 &report( 0, 'bold green', 'Scaling source image to mosaic dimensions' );                    #report processing step
184 $Image->Scale( geometry => "${MosaicWidth}x${MosaicHeight}!" );                             #scale source image to mosaic size
185 my @ImageBlob:shared = $Image->ImageToBlob();                                               #convert source image to a shared blob
186 undef $Image;                                                                               #destroy source image object before thread launch
187 
188 my $Backup = &fileBackup( $MosaicFile );                                                    #tentatively backup any previous mosaic
189 my $Mosaic = Image::Magick->new();                                                          #instantiate an image object for the mosaic
190 $Mosaic->Set( size => "${MosaicWidth}x${MosaicHeight}!" );                                  #set canvas size
191 $Mosaic->Read( 'xc:none' );                                                                 #set no background
192 
193 my $NoThreadsDone:shared    = 0;                                                            #number of tile-overlayer threads that have ended
194 my $GeometryQueue           = Thread::Queue->new();                                         #create queue for the tile geometries
195 my $LayoutQueue             = Thread::Queue->new();                                         #create queue for the tile layout data
196 threads->create( \&createMosaic )->detach() for ( 1..$N );                                  #launch thread(s) for composing the mosaic
197 threads->create( \&createBlueprint );                                                       #launch thread for writing the HTML mosaic blueprint
198 
199 &report( 0, 'bold green', 'Populating geometry queue' );                                    #report processing step
200 {                                                                                           #start naked block for tile geometries
201     my $tileIdx = 0;                                                                        # init tile index for blueprint
202     for( my $y = 0; $y < $MosaicHeight - 1; $y += $TileHeight ) {                           # repeat for each tile row: work top to bottom
203         for( my $x = 0; $x < $MosaicWidth - 1; $x += $TileWidth ) {                         #  repeat for each tile column: work left to right
204             my $geometry = "${TileWidth}x${TileHeight}+$x+$y";                              #   define tile's geometry
205             $GeometryQueue->enqueue( $tileIdx++, $geometry );                               #   enqueue blueprint tile index & geometry
206         }                                                                                   #  until all tile columns processed
207     }                                                                                       # until all tile rows processed
208 }                                                                                           #end naked block
209 $GeometryQueue->enqueue( map{ undef } 1..2*$N );                                            #signal tile-overlayer threads to end
210 
211 &report( 0, 'bold yellow', 'Waiting...' );                                                  #report wait state
212 $_->join() for threads->list(threads::running);                                             #wait for the tiling-blueprint thread to end
213 
214 &report( 0, 'bold green', 'Writing Mosaic...' );                                            #report processing step
215 $Mosaic->Comment( $MosaicComment );                                                         #try to write main parameters to comment field
216 $Mosaic->Write( filename => "$MosaicFile" );                                                #output the mosaic to file
217 if( defined( $Backup ) ) {                                                                  #delete backup if no change
218     unlink $Backup unless compare( $MosaicFile, $Backup );
219 }
220 #-------------------------------------------------------------------------------------------------------------------------------
221 # 2) TERMINATE:
222 &report( 0, 'bold red', 'Done' );                                                           #report termination
223 my $Elapsed = tv_interval( $StartTime );                                                    #determine total elapsed time
224 print locate( $CursorY + $N + 3, 1 ),                                                       #report total elapsed time
225       colored ['reset'], "\aElapsed time: ",
226       colored ['bold white'], $Elapsed,
227       colored ['reset'], " secs\nThroughput: ",
228       colored ['bold white'], int( 100*$NoTiles/$Elapsed ) / 100, " tiles/sec\n";
229 exec( qq|imdisplay "$MosaicFile"| ) if -e "$MosaicFile";                                    #display mosaic
230 exit;                                                                                       #end processing
231 #===== SUBROUTINES =============================================================================================================
232 #            Usage : &fileBackup( Source )
233 #          Purpose : Copies the designated source file to a target file with a similar file specification. The target's basename
234 #                    will differ by having a positive integer, enclosed in parentheses, appended. The chosen integer will be the
235 #                    smallest possible value that ensures a non-conflicting filename.
236 #        Arguments : Source = Source file specification.
237 #          Returns : String containing the target file specification or the undefined value.
238 #  Externals -  In : FATAL.
239 #  Externals - Out : None.
240 #     Shared -  In : None.
241 #     Shared - Out : None.
242 #           Queues : None.
243 #             Subs : None.
244 #          Remarks : The undefined value is returned if the source file does not exist.
245 #          History : v1.0.0 - October 1, 2010 - Original release.
246 
247 sub fileBackup {                                                                            #begin sub
248     my $source      = shift;                                                                # parameterize the source file specification
249     my $target      = $source;                                                              # init backup file specification
250     my $modifier    = 0;                                                                    # init basename modifier
251 
252     return undef unless -e $source;                                                         # return undefined value if source does not exist
253 
254     fileparse_set_fstype('');                                                               # force Unix-style interpretation
255     my ( $basename, $path, $suffix ) = fileparse( $source, '\..*' );                        # split the source file spec into components
256     $target = "$path${basename}(" . ++$modifier . ')' . $suffix while -e $target;           # compose unique filename
257 
258     copy( $source, $target )                                                                # copy source file to target
259      or die FATAL, "Cannot backup the file '$source' to '$target': $! -";
260     return $target;                                                                         # return the target file specification
261 }                                                                                           #end sub fileBackup
262 #-------------------------------------------------------------------------------------------------------------------------------
263 #            Usage : &report( ThreadId, Colors, Msg );
264 #          Purpose : Reports a thread's processing status.
265 #        Arguments : ThreadId = thread integer id
266 #                    Colors   = color attribute of message
267 #                    Msg      = message to be displayed
268 #          Returns : None.
269 #  Externals -  In : $CursorY
270 #  Externals - Out : None.
271 #     Shared -  In : None.
272 #     Shared - Out : None.
273 #           Queues : None.
274 #             Subs : None.
275 #          Remarks : None.
276 #          History : v2.0.0 - October 1, 2010 - Original release.
277 
278 sub report {                                                                                #begin sub
279     my( $threadId, $colors, $msg ) = @_;                                                    # parameterize the arguments
280 
281     print locate( $CursorY + $threadId, 1 ), clline,                                        # clear line coresponding to thread
282           colored [ 'reset' ], "Thread #$threadId: ",                                       # display heading
283           colored [ $colors ], $msg;                                                        # display message
284 }                                                                                           #end sub report
285 #===== THREADED SUBROUTINES ====================================================================================================
286 #            Usage : &createMosaic();
287 #          Purpose : Finds the best matching tiles for specified tile geometries and overlays them on the mosaic canvas.
288 #        Arguments : None.
289 #          Returns : None.
290 #  Externals -  In : $Pruning, $L, $Mosaic, $N, $TileDir, @Centroid, @TileRGB
291 #  Externals - Out : $Mosaic
292 #     Shared -  In : $NoThreadsDone, @ImageBlob
293 #     Shared - Out : $NoThreadsDone
294 #           Queues : $GeometryQueue, $LayoutQueue
295 #             Subs : report
296 #          Remarks : - Dequeues $GeometryQueue for the tile blueprint layout index & geometry.
297 #                    - Enqueues $LayoutQueue with the filename and blueprint layout index of each best-matching tile.
298 #          History : v2.0.0 - November 10 - Original release.
299 
300 sub createMosaic {                                                                          #begin sub
301     my $threadId    = threads->tid();                                                       # parameterize thread id
302     &report( $threadId, 'bold white', 'Initializing...' );                                  # report initialization
303     ( my $image     = Image::Magick->new() )->BlobToImage( @ImageBlob );                    # init an image object from the image blob
304     my %file2index;                                                                         # mapping of filenames to image object indices
305     my $geometry;                                                                           # geometry of a tile: width, height & x,y offsets
306     my $layoutIdx;                                                                          # layout index for blueprint
307     my $tile        = Image::Magick->new( magick => "GIF" );                                # instantiate an image object for the tiles
308     my $tileCount;                                                                          # number of tiles processed
309     #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
310     sub meanColor {                                                                         # begin sub to compute a mean normalized channel color
311         my @colors = $image->GetPixels                                                      #  get channel intensities of all pixels:
312                                 (   map         => shift,                                   #   get color channel designation,
313                                     geometry    => $geometry,                               #   specify tile geometry,
314                                     normalize   => 'true'                                   #   request normalized values
315                                 );
316         my $mean = 0;                                                                       #  average value
317         $mean  += $_ for @colors;                                                           #  sum all intensities
318         $mean  /= scalar @colors;                                                           #  return the average value
319     }                                                                                       # end sub meanColor
320     #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
321     sub max {                                                                               # begin sub to compute a maximum value
322         my $max = shift;                                                                    #  init max with first value
323         do{ $max = $_ if $_ > $max } for @_;                                                #  update max following comparison with remaining values
324         return $max;                                                                        #  result maximum value
325     }                                                                                       # end sub max
326     #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
327     sub matchBestTile {                                                                     # begin sub to match a tile to an image area
328         my ( $red, $green, $blue )  = @_;                                                   #  parameterize the mean normalized RGB colors
329         my $minMetric               = &POSIX::HUGE_VAL;                                     #  minimum value of the metric
330         my $bestTile;                                                                       #  filename of tile that best matches mean colors
331         my $octant                  = 0;                                                    #  init "octant" restriction
332 
333         do{ vec( $octant, $_, 1 ) = ( $Centroid[$_] > $_[$_] ) for( 0..2 ); }               #  compute restriction, bit by bit, relative to centroid
334          if( $Pruning eq 'yes' );                                                           #   if pruning requested
335 
336         if( $L eq 'Manhattan' ) {                                                           #  case of Manhattan metric:
337             while( my ( $key, $value ) = each %{$TileRGB[$octant]} ) {                      #   repeat for each possible tile
338                 my $metric      = abs( $red   - @{$value}[0] ) +                            #    compute metric
339                                   abs( $green - @{$value}[1] ) +
340                                   abs( $blue  - @{$value}[2] );
341                 ( $minMetric, $bestTile ) = ( $metric, $key ) if $metric < $minMetric;      #    update minimum metric & best tile if metric is less
342             }                                                                               #   until all tiles processed
343         } elsif( $L eq 'Euclidean' ) {                                                      #  case of Euclidean metric:
344             while( my ( $key, $value ) = each %{$TileRGB[$octant]} ) {                      #   repeat for each possible tile
345                 my $deltaRed    = $red   - @{$value}[0];                                    #    compute difference in red colors
346                 my $deltaGreen  = $green - @{$value}[1];                                    #    compute difference in green colors
347                 my $deltaBlue   = $blue  - @{$value}[2];                                    #    compute difference in blue colors
348                 my $metric      = $deltaRed     * $deltaRed     +                           #    compute square of metric
349                                   $deltaGreen   * $deltaGreen   +
350                                   $deltaBlue    * $deltaBlue;
351                 ( $minMetric, $bestTile ) = ( $metric, $key ) if $metric < $minMetric;      #    update minimum metric & best tile if metric is less
352             }                                                                               #   until all tiles processed
353         } else {                                                                            #  case of Max metric:
354             while( my ( $key, $value ) = each %{$TileRGB[$octant]} ) {                      #   repeat for each possible tile
355                 my $metric      = &max( abs( $red   - @{$value}[0] ),                       #    compute metric
356                                         abs( $green - @{$value}[1] ),
357                                         abs( $blue  - @{$value}[2] )
358                                       );
359                 ( $minMetric, $bestTile ) = ( $metric, $key ) if $metric < $minMetric;      #    update minimum metric & best tile if metric is less
360             }                                                                               #   until all tiles processed
361         }                                                                                   #  end case of selected metric
362         return $bestTile;                                                                   #  return tile filename
363     }                                                                                       # end sub matchBestTile
364     #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
365     while( ( $layoutIdx, $geometry ) = $GeometryQueue->dequeue( 2 ) ) {                     # repeat; dequeue task specifications
366         last unless defined $layoutIdx;                                                     #  end repeat if end of queue encountered
367         my $bestTile = &matchBestTile                                                       #  match mean image-area colors to a tile:
368                         (   &meanColor( 'r' ),                                              #   compute mean normalized red color,
369                             &meanColor( 'g' ),                                              #   compute mean normalized green color,
370                             &meanColor( 'b' )                                               #   compute mean normalized blue color.
371                         );                                                                  #   record tile filename
372 
373         unless( defined $file2index{$bestTile} ) {                                          #  if current tile differs from previous ones
374             $tile->Read( "$TileDir/$bestTile" );                                            #   load tile object with its image file
375             $file2index{$bestTile} = $#$tile;                                               #   update mapping
376         }                                                                                   #  end if
377         $Mosaic->Composite( image       => $tile->[$file2index{$bestTile}],                 #  overlay mosaic canvas with tile
378                             compose     => 'Over',
379                             geometry    => $geometry
380                           );
381 
382         ++$tileCount;                                                                       #  update tile count
383         $LayoutQueue->enqueue( $bestTile, $layoutIdx );                                     #  enqueue task specs for blueprint thread
384         &report( $threadId, 'bold green', "Matched $bestTile for $geometry" );              #  report best tile match
385     }                                                                                       # until all end of queue marker encountered
386     {   lock $NoThreadsDone;                                                                # get lock on threads-done counter
387         $LayoutQueue->enqueue( undef, undef )                                               # signal blueprint thread that no more data forthcoming
388          if ++$NoThreadsDone == $N;                                                         #  if this is the last tile-overlaying thread to end
389     }                                                                                       # release lock on counter
390     &report( $threadId, 'bold red', "Done ($tileCount tiles overlaid)" );                   # report end of processing
391 }                                                                                           #end sub createMosaic
392 #-------------------------------------------------------------------------------------------------------------------------------
393 #            Usage : &createBlueprint()
394 #          Purpose : Creates the HTML blueprint file for displaying the individual tiles of the mosaic along with
395 #                    the tile histogram.
396 #        Arguments : None.
397 #          Returns : None.
398 #  Externals -  In : FATAL, $BluePrtFile, $MosaicHeight, $MosaicWidth, $TileDir, $TileHeight, $TileWidth
399 #  Externals - Out : None.
400 #     Shared -  In : None.
401 #     Shared - Out : None.
402 #           Queues : $LayoutQueue
403 #             Subs : fileBackup, report
404 #          Remarks : Dequeues $LayoutQueue for the filename and layout index of the best matching tiles.
405 #          History : v2.0.0 - November 10 - Original release.
406 
407 sub createBlueprint {                                                                       #begin sub
408     my $threadId = threads->tid();                                                          # parameterize thread id
409     my $backup  = &fileBackup( $BluePrtFile );                                              # tentatively backup any previous blueprint
410     my @layout;                                                                             # tile-code layout
411     my %codeBins;                                                                           # tile-code histogram bins
412     &report( $threadId, 'bold yellow', 'Waiting...' );                                      # report wait state
413     #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
414     sub aggregate {                                                                         # begin sub to aggregate tile runs in blueprint
415         my $codeList = join( ',', @layout ) . ',';                                          #  make CSV list of tile codes & append extra comma
416 
417         for ( keys %codeBins ) {                                                            #  repeat for each tile code
418             while( my( $leadIn, $run ) = $codeList =~ /(^|,)(($_,)(\3)+)/ ) {               #   repeat for each code run
419                 $codeList =~ s/$&/"$leadIn${_}x" . $run =~ tr#,#,# . ','/e;                 #    replace run with aggregate expression
420             }                                                                               #   until all runs processed
421         }                                                                                   #  until all tile codes processed
422         chop( $codeList );                                                                  #  remove trailing extra comma
423         return $codeList;                                                                   #  return aggregated list of tile codes
424     }                                                                                       # end sub aggregate
425     #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
426     while( my( $bestTile, $layoutIdx, ) = $LayoutQueue->dequeue( 2 ) ) {                    # repeat for each tile specification
427         last unless defined $bestTile;                                                      #  end repeat if end of queue encountered
428         ( $layout[$layoutIdx] ) = $bestTile =~ /^tile_(.+)\.gif/;                           #  update tile-code layout
429         ++$codeBins{ $1 };                                                                  #  update tile-code histogram
430         &report( $threadId, 'bold green', "Updated layout with tile code '$1'" );           #  report processing
431     }                                                                                       # until all tiles processed
432 
433     &report( $threadId, 'bold green', 'Creating the HTML tiling blueprint...' );            # report blueprint creation
434     ( my $tileDir   = File::Spec->rel2abs( $TileDir ) ) =~ tr#\\#/#;                        # convert tile directory to Unix-style absolute
435     my $histogram   = join ',', map{ "$_," . $codeBins{$_} }                                # compose histogram data list
436                         sort{ $codeBins{$b} <=> $codeBins{$a} } keys %codeBins;             #  in descending frequency order
437 
438     local *HTML;                                                                            # filehandle for the HTML blueprint file
439     open( HTML, ">$BluePrtFile" )                                                           # open blueprint file for write
440      or die FATAL, "Cannot create HTML blueprint file '$BluePrtFile': $! -";
441 
442     print HTML <<BLUEPRINT;                                                                 # write the HTML file
443 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
444 <html>
445 <head>
446     <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
447     <meta name="author"             content="Webpraxis Consulting Ltd. - ALL RIGHTS RESERVED; webpraxis\@gmail.com">
448     <style type="text/css">
449         BODY {
450             background-color:                   silver;
451             font-family:                        Verdana,Helvetica,sans-serif;
452             font-size:                          9pt;
453         }
454 
455         DIV#histogram {
456             float:                              left;
457         }
458         DIV#histogram TABLE {
459             border:                             3px double teal;
460             border-collapse:                    collapse;
461             margin-top:                         20px;
462             font-size:                          9pt;
463             table-layout:                       auto;
464         }
465         DIV#histogram TABLE TD,
466         DIV#histogram TABLE TH {
467             background-color:                   transparent;
468             border:                             1px solid teal;
469             padding-left:                       10px;
470             padding-right:                      10px;
471             text-align:                         left;
472         }
473         DIV#histogram TABLE TD:first-child,
474         DIV#histogram TABLE TH:first-child {
475             text-align:                         center;
476         }
477 
478         DIV#mosaic {
479             position:                           absolute;
480             top:                                30px;
481             left:                               250px;
482             width:                              ${MosaicWidth}px;
483             height:                             ${MosaicHeight}px;
484         }
485 
486         IMG {
487             height:                             ${TileWidth}px;
488             width:                              ${TileHeight}px;
489         }
490     </style>
491     <script type="text/javascript">
492         String.prototype.repeat = function( multiplier ) {
493             var newString = '';
494             while( multiplier-- > 0 ) {
495                 newString += this;
496             }
497             return newString;
498         }
499         String.prototype.displayMosaic = function() {
500             var blueprint = this.split(",");
501             for( var i = 0; i < blueprint.length; i++ ) {
502                 var operands    = blueprint[i].split("x"),
503                     img         = '<img src="file:///$tileDir/tile_' + operands[0] + '.gif" onclick="tileInfo(' + operands[0] + ');">';
504                 document.write( ( typeof operands[1] == 'undefined' ) ? img : img.repeat( operands[1]) );
505             }
506         }
507 
508         var tileHistogram = new Histogram( $histogram );
509         function Histogram()
510         {
511             var data    = arguments;
512             this.length = 0;
513             this.bins   = new Array();
514             for( var i = 0; i < data.length; i += 2 ) {
515                 this.bins[data[i].toString()] = data[i+1];
516                 this.length++;
517             }
518 
519             this.display = function() {
520                 document.write( '<table><tr><th>Tile</th><th>Code</th><th>Frequency</th></tr>' );
521                 for( var i = 0; i < data.length; i += 2 ) {
522                     document.write( '<tr id="' + data[i] + '">' );
523                     document.write( '<td><a name="' + data[i] + '"></a><img src="file:///$tileDir/tile_' + data[i] + '.gif"></td>' );
524                     document.write( '<td>' + data[i] + '</td>' );
525                     document.write( '<td>' + data[i+1] + '</td>' );
526                     document.write( '</tr>\\n' );
527                 }
528                 document.write( '<tr><th colspan="3">Total unique tiles = ' + this.length + '</th></tr></table>\\n' );
529             }
530         }
531 
532         var hilitedRow = null;
533         function tileInfo( code ) {
534             if( hilitedRow != null ) hilitedRow.style.backgroundColor = 'transparent';
535             hilitedRow = document.getElementById( code );
536             hilitedRow.style.backgroundColor = 'whitesmoke';
537             alert( 'Code = ' + code + '\\nFrequency = ' + tileHistogram.bins[code.toString()] )
538         }
539     </script>
540 </head>
541 <body>
542     <div id="histogram">
543         <script type="text/javascript">tileHistogram.display();</script>
544     </div>
545     <div id="mosaic">
546         <b>Click on a tile to highlight its entry in the histogram. Use the associated code to exclude it.</b>
547         <p>
548         <script type="text/javascript">"@{[ &aggregate() ]}".displayMosaic();</script>
549     </div>
550 </body>
551 </html>
552 BLUEPRINT
553     close HTML;                                                                             # close the HTML blueprint file
554 
555     if( defined( $backup ) ) {                                                              # delete backup if no change
556         unlink $backup unless compare( $BluePrtFile, $backup );
557     }
558     &report( $threadId, 'bold red', 'Done' );                                               # report end of processing
559 }                                                                                           #end sub createBlueprint
560 #===== Copyright 2011, Webpraxis Consulting Ltd. - ALL RIGHTS RESERVED - Email: webpraxis@gmail.com ============================
561 # end of img2PhotographicMosaic(threaded).pl

Lines 005-006: A typical invocation would be:
perl img2PhotographicMosaic(threaded).pl _xml/mosaics/mona.xml
where the processing will be done in accordance with the specifications listed in the XML file 'mona.xml' in the subdirectory '_xml/mosaics'.
Lines 023-040: Declaration of the required imports and constants along with their version numbers. Modules can be installed or upgraded via ActivePerl's packager manager "ppm.exe" with the exception of the PerlMagick module Image::Magick. The latter is best done as part of the regular installation of the ImageMagick suite. The modules Term::ANSIScreen and Win32::Console::ANSI are used to enhance the program's output with color and cursor control so that each thread may report its status in a compact yet clear fashion.
Lines 042-047: Records the start of the principal computational phase: the value will be used to assess the throughput of the script. Outputs the title of the program after clearing the screen and setting the STDOUT buffer to auto-flush.
Lines 049-052: Retrieves the path of the XML file from the command-line and reads its content into a referenced hash.
Lines 054-078: Parameterizes the various input specifications and checks for errors. Note that the default value for the number of tile-matching/overlaying threads is one plus the number of processors reported in the environment: this latter value normally includes both real and logical processors.
Lines 080-133: The objective of this section is to retain only the tiles designated for matching and, if pruning is in play, ascertain in which octant about the RGB centroid they lie. The results are stored in the array of hashes "@TileRGB". Each hash is populated in turn with an array reference for the mean RGB intensities of the tile, keyed on the tile's filename. The main array elements are indexed on the octant codes 0 to 7. If pruning has not been requested, then all the values are stored under the index value 0.
- Line 084: The array is not declared as shared. Thus each thread will inherit a copy. Consequently, "very large" tile sets may well deplete available system resources.
- Lines 087-088: A hash keyed on the filenames of the tiles to be excluded from consideration.
- Lines 100-102: Conditionals for tile exclusion.
- Line 103: The 8^th element of the array "@TileRGB" is used for temporary storage until the octant assignments are carried out.
- Line 119: Determines in which octant the tile lies when pruning has been invoked. The value of the variable "$octant" will range from 000_B to 111_B, in other words, from 0 to 7. It is constructed bit-by-bit, in accordance with the following rules:
  Bit #0: set to 1 if the centroid's red intensity exceeds that of the tile and to 0 otherwise,
  Bit #1: set to 1 if the centroid's green intensity exceeds that of the tile and to 0 otherwise,
  Bit #2: set to 1 if the centroid's blue intensity exceeds that of the tile and to 0 otherwise.
  Note that it doesn't matter how the octants are numbered as long as the same rules are applied when the time comes for tile matching.
- Lines 120-121: The tile's RGB values are moved out of temporary storage and into the corresponding octant element.
- Line 128: If pruning is not to be used, then the tile data is relocated from the 8^th to the zero^th element by simply collapsing the array.
Lines 135-138: An image object for the source image is instantiated and its width and height in pixels are determined. Note in passing that, with the version of ImageMagick being used here at least, an image object created via the read function cannot be safely inherited by threaded subroutines. It has been our experience that the Perl interpreter (up to v5.10.1, build 1007 for MSWin32-x86-multi-thread at least) will always crash when these subroutines terminate.
Lines 140-141: The number of integral tile columns and rows are computed in accordance with the specified tile width and height respectively.
Lines 143-144: Sets the width and height of the eventual mosaic.
Lines 153-178: Echoes the processing specifications and displays a terse role description of the various threads.
Line 180: Records the current cursor row position for the upcoming thread reports where each thread will display its processing status.
Lines 184-186: The final preparations on the source image are carried out before handing it over to the tile-matching/overlaying threads. First the image is sized to the computed mosaic dimension. Next, it is "blobbed" for access by the tile-matching/overlaying threads. The blob array is declared as shared. This sharing does slow down initialization of the threads, but still results in a faster startup than having each thread read and scale the source image. The last line of this section destroys the object for the source image. As stated previously, without this measure, the Perl interpreter crashes after the mosaic is correctly written to disk.
Lines 189-191: Defines a blank canvas for the mosaic. And here's a curious thing. Each tile-matching/overlaying thread will inherit a copy of this object. However, contrary to what can happen with the "$Image" object, the Perl interpreter will not crash upon termination.
Lines 193-197: This section implements the thread launch sequence. The shared variable "$NoThreadsDone" will be central in carrying out the dictum "Last person out please turn off the lights" with respect to the termination the tile-matching/overlaying threads. Two thread queues are then declared. The first one is a communication channel between the main program and the tile-matching/overlaying threads. Its purpose is to list all the tile layout indices and geometries, the latter following the ImageMagick string format "widthxheight+x+y". The second queue then allows the tile-matching/overlaying threads to communicate their findings to the supplementary tiling-blueprint thread. Along with each tile index, the filename of the best-matching tile is transmitted. Finally the threads are launched with the supplementary one being last, thus insuring that they will have the appropriate thread ids. Moreover, the supplementary thread is the only non-detached process, thus ensuring that the main thread will wait before attempting to write the mosaic to disk.
Lines 200-208: This block has the main program, Thread #0, populating the geometry queue. The nested loops work from top to bottom, left to right, spanning the mosaic dimensions.
Lines 209-219: By putting the appropriate number of undefined values in the geometry queue, the main program signals each tile-matching/overlaying thread that no more tile specifications are forthcoming. The program then waits for the tiling-blueprint thread to complete its task. After the return happens, the program attempts to write the mosaic image to disk along with a comment if the file format supports this feature.
Lines 222-230: This is the termination sequence. Reported are the execution time (in secs) and the throughput (in tiles/sec). Processing is handed over to the executable "imdisplay.exe" which is included with the ImageMagick package. On the other hand, if the mosaic was not created, then main program terminates processing.
Lines 231-284: Two utility subroutines:
- fileBackup: used to backup the mosaic image and blueprint files,
- report: called by all threads to report their processing status.
Lines 300-391: This subroutine defines the actions of a tile-matching/overlaying thread.
- Lines 301-308: The initialization part of the thread. The thread's id is recorded which will be in the range [1,$N] as guaranteed by the aforementioned thread launch sequence. Then an image object is initialized with the "blobbed" version of the scaled source image.
- Lines 310-319: The first of three ancillary subroutines. For a specified color channel ("r" for red, "g" for green and "b" for blue) and the current tile geometry, the routine returns the mean normalized intensity value for the corresponding image area. Note that the result is a simple arithmetic mean and not a weighed average.
- Lines 321-325: This subroutine is in support of the evaluation of the Max metric.
- Lines 327-363: The last ancillary subroutine which is at the core of the thread. Given the mean normalized color intensities for an area of the source image, it finds the tile with the closest RGB values in accordance with the requested metric.
  - Line 333: When pruning has been requested, the source image area is assigned to one of the octants of the RGB tile cube. This is accomplished with the same conditionals that were used to partition the cube about the centroid. The ensuing best-matching tile search will then be restricted to tiles within this octant.
  - Lines 336-361: For the specified metric, the associated loop finds the minimum value after iterating through either all the tiles or the appropriate subset. The code's structural duplication was chosen to optimize execution. If a single loop was used instead, then the conditionals for choosing the specified metric would have to be evaluated at each iteration.
- Lines 365-385: This loop governs the duration of a tile-matching/overlaying thread which will execute for as long as geometric specifications can be dequeued. After a best match has been determined, the tile is overlaid onto the mosaic canvas at the appropriate location. Next the tile's filename and layout index are enqueued for the blueprint-tiling thread to process.
  - Lines 373-376: Implements a simple caching of the tile images where the hash "%file2index" provides the mapping between tile filenames and sequence index. It exploits the fact that an image object can reference a multi-image sequence which is normally used in the creation of GIF animations. Be aware that this will also place an extra burden of the system's memory resources.
  - Lines 386-389: This section implements the dictum "Last person out please turn off the lights". It is the responsibility of the last executing tile-matching/overlaying thread to inform the supplementary blueprint-tiling thread that no more best tiles are forthcoming. The procedure works by incrementing the shared variable "$NoThreadsDone" after placing a lock on it. When this value equals the number of tile-matching/overlaying threads that were launched, the current thread places two undefined values in the appropriate queue. In all cases, thread execution simply ends with no return to the main program as the thread was launched detached from the main thread.
Lines 407-559: This final subroutine defines the actions of the supplementary thread. It creates a tiling blueprint in the form of a compact HTML file to display the mosaic tile by tile. It places the onus on the browser's JavaScript engine to compose the required image tags. As the only non-detached thread, its return signals the main program to try and display the mosaic image.
- Lines 414-424: This subroutine aggregates the runs of consecutive tile codes. It replaces each run with a single tile code followed by the multiplier symbol "x" followed by the number of occurrences. For example, the code list "1,2,2,2,2,3" would become "1,2x4,3".
- Lines 426-431: This loop runs for as long as information can be dequeued. Given that the tile filenames will arrive on a first-come first- served basis, the codes need to be stored in an array in order to reconstitute the correct order. The histogram's frequencies are also updated.
- Line 435: Packages the histogram data for display by a JavaScript function. The tile-code frequencies are sorted in descending numerical order. The resulting string will be of the form code,frequency,code,frequency,code,frequency,...
- Lines 438-553: Writes the HTML blueprint file to disk.
  - Lines 492-498: This method replicates a string a specified number of times by simply appending clones to form a new string.
  - Lines 499-506: This method generates the image tags corresponding to the tile-code list. Given the code list "1,2x4,3" for example, HTML tags similar to the following will be written out:
    
    <img src="file:///C:/Documents and Settings/Webpraxis/tiles_16x16/tile_1.gif" onclick="tileInfo(1);">
    <img src="file:///C:/Documents and Settings/Webpraxis/tiles_16x16/tile_2.gif" onclick="tileInfo(2);">
    <img src="file:///C:/Documents and Settings/Webpraxis/tiles_16x16/tile_2.gif" onclick="tileInfo(2);">
    <img src="file:///C:/Documents and Settings/Webpraxis/tiles_16x16/tile_2.gif" onclick="tileInfo(2);">
    <img src="file:///C:/Documents and Settings/Webpraxis/tiles_16x16/tile_2.gif" onclick="tileInfo(2);">
    <img src="file:///C:/Documents and Settings/Webpraxis/tiles_16x16/tile_3.gif" onclick="tileInfo(3);">
    
    Note that absolute URLs are used in the image sources. They point to the location of the user's tile directory that went into the creation of the mosaic.
  - Lines 508-530: Packages the histogram data into an associative array so that the frequencies can be displayed by the JavaScript function "tileInfo". Moreover, the data is saved in a regular array so that it may be displayed by the associated method in tabular format following the correct order.

To gauge the effectiveness of the script, a single mosaic was created repeatedly up to twelve times on a dual-core XP platform for various numbers of threads. The computer was started in its normal mode and not re-booted between each run. It is hoped that this approach yields a more realistic assessment. The screen saver was disabled and the only user-launched application was the command window with a screen width of 120 characters. Before each repetition, the same basic starting conditions were ensured in that any previous versions of the mosaic and blueprint were deleted. The test image was that of the Mona Lisa painting. The resulting mosaic consisted of 47,882 tiles, rendered in all cases with the Manhattan metric with pruning enabled.

In order to account for CPU contentions by the extraneous OS and background application threads, the following table lists the reported throughputs with the highest and lowest values discarded in the statistical calculations:

Throughputs (tiles/sec) for a Dell Dimension E520 ^[1]
	No. of Secondary Threads (N+1)
	1 + 1	2 + 1	3 + 1	4 + 1
Run #1	186.53	268.71	275.06	262.45
Run #2	~~189.50~~	~~278.18~~	283.66	266.72
Run #3	185.36	271.91	282.69	265.06
Run #4	188.93	269.80	278.78	267.89
Run #5	185.17	268.31	282.82	267.12
Run #6	189.25	276.32	280.06	~~253.42~~
Run #7	185.17	269.49	~~284.06~~	265.34
Run #8	189.04	269.02	274.98	261.27
Run #9	188.60	274.10	282.46	267.35
Run #10	~~184.74~~	270.59	~~274.71~~	263.54
Run #11	189.39	277.15	283.50	262.23
Run #12	185.21	~~268.12~~	283.77	~~268.50~~
Average	187.27	271.54	280.78	264.90
Std. Dev.	1.92	3.23	3.43	2.39

[1] Dell Dimension E520:

Intel^® Pentium^® D 805 (2.66 GHz dual core, 533 MHz FSB, 1 MiB L2 - no hyper-threading)
1 GiB RAM
Seagate Technology 250 GiB Barracuda: SATA II, 7,200 RPM
MS Windows^® XP Professional SP3 (supports Symmetric Multiprocessing (SMP))
Number of processors reported by the environment = 2

The "3+1" scenario is the unequivocal winner. At first glance it would appear to be contrary to one's expectation as a total of four secondary threads are contenting for execution on two cores. One would thus think that the system is being overtaxed. Clearly this does not turn out to be the case. With the Windows Task Manager's Performance application running in the background, one observes that the CPU usage in the "2+1" scenario fluctuates between 90 and 100% whereas, in the "3+1" case, it's between 97% and 100%; for completeness, the usage in "1+1" scenario is between 50 and 70%.

In order to possibly explain this behaviour, the crucial observation to make is that the tile-matching/overlaying threads are not close computational systems. They must all interact with the main thread in order to overlay their best-matching tiles unto a common mosaic canvas defined there. This would appear to be a blocking operation where each thread must now wait for a response by ImageMagick before proceeding with finding the next best-matching tile. If this assumption is true, then perhaps the reason why the "3+1" scenario is superior is that the overtaxing of the CPU causes the ImageMagick calls to be better staggered. For example, whilst one thread is waiting to proceed, a second thread has started finding a best tile whereas a third one is about to finish this latter task.

Hence, it is not clear what the a priori number of optimal threads might be for any given multicore system.

Software Corner

The following portfolio of mosaics was created using the three available metrics. All but two images were filtered with the our complete tile collection. The "School of Athens" had one tile excluded whereas the "Mona Lisa" images had forty-three. Despite these exclusions, the results for the latter are not particularly pleasing. We were forewarned however that such an image would prove to be problematic (as shown in our previous article) because our tile set is particularly deficient in the gold color region. Thus matching her skin tones in any acceptable manner is not possible in our case.

From the scatter plot of our tile collection, the distribution is seen to be tightly clustered about the grayscale line. So, to satisfy our curiosity, we converted the source "Mona Lisa" image to grayscale and then filtered the result, excluding two tiles only. The corresponding mosaics are surprisingly satisfactory despite the tiles having non-gray colors.

	Metric
	Manhattan	Euclidean	Max
Raphael The School of Athens (3820 x 2964, 2.35 MiB)	(3824 x 2976, 6.14 MiB)	(3824 x 2976, 6.08 MiB)	(3824 x 2976, 6.05 MiB)
da Vinci Mona Lisa (2835 x 4289, 3.34 MiB)	(2848 x 4304, 6.17 MiB)	(2848 x 4304, 6.18 MiB)	(2848 x 4304, 6.12 MiB)
da Vinci Mona Lisa (2835 x 4289, 3.34 MiB) converted to grayscale	(2848 x 4304, 5.20 MiB)	(2848 x 4304, 5.21 MiB)	(2848 x 4304, 5.22 MiB)
Versailles Hall of Battles Source image courtesy of Frances Reintjes (2048 x 1536, 1.40 MiB)	(2048 x 1536, 1.68 MiB)	(2048 x 1536, 1.69 MiB)	(2048 x 1536, 1.69 MiB)
Musée d'Orsay Rodin Ugolino Source image courtesy of Frances Reintjes (2048 x 1536, 1.29 MiB)	(2048 x 1536, 1.65 MiB)	(2048 x 1536, 1.65 MiB)	(2048 x 1536, 1.64 MiB)
Musée du Louvre Winged human-headed bulls Source image courtesy of Frances Reintjes (2048 x 1536, 1.24 MiB)	(2048 x 1536, 1.75 MiB)	(2048 x 1536, 1.76 MiB)	(2048 x 1536, 1.76 MiB)
Musée d'Orsay Great Hall Source image courtesy of Alwynne B. Beaudoin (2816 x 2112, 2.45 MiB)	(2816 x 2112, 3.16 MiB)	(2816 x 2112, 3.16 MiB)	(2816 x 2112, 3.17 MiB)
Paris Notre Dame Cathedral Source image courtesy of Alwynne B. Beaudoin (2112 x 2816, 2.53 MiB)	(2112 x 2816, 3.26 MiB)	(2112 x 2816, 3.26 MiB)	(2112 x 2816, 3.26 MiB)
Paris Neighborhood park Source image courtesy of Alwynne B. Beaudoin (2816 x 2112, 2.37 MiB)	(2816 x 2112, 3.24 MiB)	(2816 x 2112, 3.25 MiB)	(2816 x 2112, 3.25 MiB)
Hong Kong Legislative Council Building Source image courtesy of Keri Fisher (3648 x 2432, 2.09 MiB)	(3648 x 2432, 4.37 MiB)	(3648 x 2432, 4.41 MiB)	(3648 x 2432, 4.48 MiB)
Macau Grand Lisboa Hotel Source image courtesy of Keri Fisher (2432 x 3648, 1.97 MiB)	(2432 x 3648, 4.58 MiB)	(2432 x 3648, 4.58 MiB)	(2432 x 3648, 4.58 MiB)
Devonian Botanic Garden Kurimoto Japanese Garden Source image courtesy of Yves Beaudoin (2816 x 2112, 2.20 MiB)	(2816 x 2112, 3.06 MiB)	(2816 x 2112, 3.09 MiB)	(2816 x 2112, 3.12 MiB)