TweetFollow Us on Twitter

Programmer's Challenge

Volume Number: 18 (2002)
Issue Number: 11
Column Tag: Programmer's Challenge

Programmer's Challenge

by Bob Boonstra

Penultimate

When I took over this column from Mike Scanlin back in June, 1995, I had no idea that I would still be writing it seven and one-half years later. Running the Programmer's Challenge contest has been both a rewarding and an increasingly demanding experience, but the time has come for me to move on. The title of this column, my 90th, refers, not to the name of a new Challenge, but to the fact that my next column will be the last one. Besides announcing the winner of my final Challenge, the October Area Challenge, next month will include a retrospective on the Programmer's Challenge, the problems, the contestants, the evolution of the column, and perhaps a few anecdotes. Until then, I hope you have enjoyed reading the column as much as I have enjoyed writing it.

Winner of the September, 2002 Challenge

The August, 2000, Challenge problem asked readers to write code that would solve a sequence of chess end-game positions. Unfortunately, the problem must have been too difficult, and no entries were submitted. I thought someone might have adapted and extended the code from the problem in my first column, the June, 1995, Check Checkmate Challenge, but this was not to be. Perhaps an omen ....

So, taking advantage of an extended deadline for this issue, we will look at the winner of the September PhotoMosaic Challenge. Announced with a tongue-in-cheek reference to the 25th anniversary of the death (or abduction by aliens, whichever you choose to believe) of Elvis, this problem asked readers to generate a mosaic of smaller images that approximated a target image. Congratulations, once again, to Ernst Munter (Kanata, Ontario), for submitting the fastest and most accurate mosaic generator.

Both Ernst and second-place finisher Jan Schotsman use the Altivec programming model. Ernst divides the elements and images into "spots" of 4 pixels by 4 pixels, which allows one color plane of the spot to be represented in 64 bits - 8 bits/color for each of the 16 pixels. The image elements used to construct the mosaic are divided into "slices", or portions of the element corresponding to the desired tile size, and the slices are sorted by luminence. Ernst uses the luminence of a tile in the target image to select a position in the sorted slice array, and searches within the array to find the most appropriate slice. The depth of the search is limited to control execution time. The slice is selected to minimize the distance from the target image in RGB space. There are additional refinements to the algorithm, as described in the extensive commentary contained in the code.

I tested the entries submitted using twelve test cases, using three sets of mosaic elements, one set from lighthouse photos I took at Isle au Haut, another set from pictures taken by my son on a trip to France, and the last set from pictures taken in the British Virgin Islands. Ernst's solution produced better mosaics in 9 of the 12 test cases, and used significant less execution time than the second-place entry. Below, I have posted an example mosaic produced by Ernst's code, along with the original image, at the MacTech web site as:

http://www.mactech.com/progchallenge/WinningMosaic/OutputImage.jpg

and

http://www.mactech.com/progchallenge/WinningMosaic/InputImage.jpg.

The table below lists, for each of the solutions submitted, the number of test cases processed correctly, the total distance between pixels of the mosaic and the target image, execution time in milliseconds, and the total score for each solution. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name                   Cases           Distance   Time     Score
                       Correct                    (msecs)
                       
Ernst Munter(882)      12              15598       92522   16914
Jan Schotesman (18)    12              16754      337847   22198
Tony Cooper (20)       12              18625      440358   25951

Top Contestants ...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank   Name                Points   Wins      Total
                           (24 mo)  (24 mo)   Points 
1.     Munter, Ernst       241         8        902  
2.     Saxton, Tom          65         2        230  
3.     Taylor, Jonathan     54         2         90  
4.     Stenger, Allen       53         1        118  
5.     Hart, Alan           34         1         59  
6.     Cooper, Tony         27         1         27  
7.     Rieken, Willeke      22         1        134  
8.     Sadetsky, Gregory    22         0         24  
9.     Landsbert, Robin     22         1         22  
10.    Schotsman, Jan       21         0         28  
11.    Gregg, Xan           20         1        140  
12.    Mallett, Jeff        20         1        114  
13.    Wihlborg, Claes      20         1         49  
14.    Truskier, Peter      20         1         20  

Here is Ernst winning PhotoMosaic solution.

    Mosaic-v2.cp

    Copyright (c) 2002

    Ernst Munter

/*
      "Photo Mosaic"
      Version 2
      
The task is to assemble a photomosaic resembling a "desired image" from tiles cut
out from a number of "element images".  The criteria are closeness of the fit
in terms of the color distance (RMS sum of the RGB color components of all pixels) 
between   the desired image and the mosaic image, and speed.
Solution Strategy
-----------------
There is a trade-off between achievable color distance and speed.  The number of
degrees of freedom given - choice of tile size above a minimum, position of the
tile cut from the chosen element - is too large to allow for an exhaustive search
of all possible tile cuts ("element slices") for all possible tile sizes.
I select the two smallest tile sizes that can be used to fill the mosaic.
Each element, as well as the tiles to be matched, are represented as an array of
"Spots", a spot being a 4 by 4 cluster of pixels.  
In a next step, all possible slices of the elements are assigned a luminance value,
and the slice is stored in an array of lists, the array being indexed by luminance.
To match a desired image then, each tile of the mosaic is processed independently.
The luminance of the tile (in the desired picture) is used as an index into the
slice array.  The position in the slice array will be in the center of a range of 
slices of similar luminance as the tile to be matched.
In the next step, all slices within the indicated range are compared (RMS color
distance) with the tile, and the closest slice identified.
Up to this point, only slices on the 4-pixel grid were considered.  The closest
identified slice is then taken as the center of a small area within the element,
and slices on a 1-pixel grid are evaluated to make the final selection.
The method to control running time is to choose the size of the range of slices
within the slice array that are evaluated.  
Since the running time penalty 1% per second is fixed, but running time is roughly 
proportional to image size, the range is chosen as the reciprocal of the image size 
times an arbitrary factor, to yield about a 10 to 20% penalty on a large (2-3Mpixel) 
image. 
Vector Processor
----------------
The processor in the G4 Macs contains a vector processing unit (Altivec).  This
processor is very efficient at processing up to 16 bytes in parallel, just the
thing to process pixels in parallel, as long as the pixels are represented
in planar form.  For example 3 vectors can hold 16 pixels (16 bytes of the same 
color in each vector).  An RGB representation (32-bit pixels) of a Spot, containing
4 by 4 pixels of an image, can be efficiently converted into a planar vector
representation.
This then allows the RMS color difference of sets of 16 pixels to be computed 
with a very small number of instructions.
I use an approximation of the true RMS value, by adding the largest absolute
differences between corresponding pixel planes (R,G, or B) to 5/16 of the sum of 
the absolute differences of the other planes.  
This is the most busy function of the algorithm;  it takes 25 vector instructions 
to compute the sum of the RMS color difference of 16 pixel pairs.
Version 2 changes are described in "MosaicClasses-v2.h".
*/
#include "Mosaic.h"
#include "MosaicClasses-v2.h"
static Ernst::Mosaic* gM;// Mosaic classes are in namespace Ernst
InitMosaic
void InitMosaic(
   short numMosaics,      
      /* number of pixmaps from which the mosaic should be created */
   const PixMapHandle element[]
      /* element[i] is a PixMapHandle to the i-th image used in constructing mosaic */
) 
// Called once to initialize the elements in a new Mosaic class.
// Mosaic element images are pixel-locked in InitMosaic, and remain locked
//      until TermMosaic() is called.
{
   assert(gM==0);
   gM=new Ernst::Mosaic(element,numMosaics);
}
Mosaic
void Mosaic(
   const PixMapHandle desiredImage,
      /* PixMapHandle populated with the desired image to be constructed */
   const Rect minPieceSize,
      /* mosaic pieces must be of this size or larger */
   PixMapHandle mosaic,
      /* PixMapHandle to preallocated image in which the mosaic is to be placed */
      /* initialized to black */
   MosaicPiece *piece,
      /* pointer to array of mosaic pieces */
      /* populated by your code */
   long *numMosaicPieces
      /* number of mosaic pieces created by your code */
)
// May be called multiple times with different desiredImages, 
//               and possibly with a different minPieceSize.
// The function locks/unlocks the image pixels,
// The mosaic is prepared (a private set of image parameters of the desired image),
//             solved (element slices assigned to mosaic tile coordinates)
//             and cleaned up (the private set deleted).
{
   LockPixels(desiredImage);
   LockPixels(mosaic);   
   
   *numMosaicPieces = 
      gM->PrepareMosaic(desiredImage,minPieceSize);
   
   gM->SolveMosaic(mosaic,piece);
   
   gM->Cleanup();
   
   UnlockPixels(mosaic);
   UnlockPixels(desiredImage);
}
TermMosaic
void TermMosaic(void)
   /* deallocate any memory allocated by InitMosaic or multiple Mosaic calls */
{
   delete gM;
   gM=0;
}
MosaicClasses-v2.h
#ifndef MOSAIC_CLASSES_H
#define MOSAIC_CLASSES_H
/*
      "Photo Mosaic"
      
Version 2:
----------
Simplification in luminance retrieval: 
      cast return value directly from memory to unsigned long.
In MatchTile():
      Try the best slice from the previous tile first.
Alternative scheme (SCHEME = 2) added:
      Do preliminary match on the average color of each spot,
      instead of on the individual pixels of the spot.
      This provides a significant speedup, at the expense of
      slightly higher overall distances, resulting in similar scores.
      
      The original scheme 1 is preferred because it produces a slightly better 
      match (kSearchRangeFactor set to optimize for a 1% / sec time penalty).
*/
#define NDEBUG
#include <cassert>
#include <cstring>
#define SCHEME 1
// A namespace is created to avoid name clashes with Apple headers or test code
namespace Ernst {
typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned long ulong;
typedef ulong Pixel;
typedef vector unsigned char vuchar;
typedef vector unsigned short vushort;
typedef vector signed long vlong;
typedef vector unsigned long vulong;
typedef vector bool char vboolchar;
// Macros extract the red, green, and blue components of a 32-bit RBG pixel
#define mRED(pixel)         (0xFF & ((pixel)>>16))
#define mGREEN(pixel)   (0xFF & ((pixel)>>8))
#define mBLUE(pixel)    (0xFF & (pixel))
enum {
   kSpotSize   = 4,            // 4 by 4 pixels
   kSpotHeight = kSpotSize,
   kSpotWidth    = kSpotSize,
   kNumLuminanceLevels = 1+255*3,   // sum of R+G+B ranges from 0 to 755 
   kSearchRangeFactor = 1000*1000*1000 // chosen to yield reasonable   
                                                   // run times
};
// Vector function, computes the absolute difference between all pairs of 
// the vector-elements in a and b (T is an unsigned vector type)
template <class T> inline T AbsDifference(T a,T b)
{
   T max=vec_max(a,b);
   T min=vec_min(a,b);
   return vec_sub(max,min);
}
// Vector functions, computes an estimate of the RMS sum of the color
// differences of all pairs of color planes 1 (vr1,vg1,vb1) and 2 (vr2,vg2,vb2) 
// The algorithm is
//         max = the largest among the components R, G, and B
//         minA and minB are the other two components
//         RMS ~= max + (minA+minB)*5/16
// Returns the sum of the sixteen RMS distances so computed
inline void VColorDistance(
   vuchar vr1,
   vuchar vg1,
   vuchar vb1,
   vuchar vr2,
   vuchar vg2,
   vuchar vb2,
   long* result)
{   
   vuchar dRed=AbsDifference<vuchar>(vr1,vr2);
   vuchar dGreen=AbsDifference<vuchar>(vg1,vg2);
   vuchar dBlue=AbsDifference<vuchar>(vb1,vb2);
   
   vuchar vMax=vec_max(dRed,dGreen);
   vuchar vMinA=vec_min(dRed,dGreen);
   vuchar vMinB=vec_min(vMax,dBlue);
   vMax=vec_max(vMax,dBlue);
   
   vulong k4=(vulong)(4,4,4,4);
   vuchar k5=(vuchar)(5,5,5,5, 5,5,5,5, 5,5,5,5, 5,5,5,5);
   
   vulong   k0=(vulong)(0,0,0,0);
   
   vulong partSumMax=vec_sum4s(vMax,k0);
   vlong sumMax=vec_sums((vlong)partSumMax,(vlong)k0);
   
   vulong intermediateMinA=vec_msum(vMinA,k5,k0);// *5
   vulong intermediateMinB=vec_msum(vMinB,k5,k0);// *5
   intermediateMinA=vec_add(intermediateMinA,intermediateMinB);
   
   intermediateMinA=vec_sr(intermediateMinA,k4);// /16
   
   vlong sum=vec_sums((vlong)intermediateMinA,sumMax);
   sum=vec_splat(sum,3);
   
   vec_ste(sum,0,result);
}
inline void VColorDistanceLong(vulong v1,vulong v2,long* result)
{
   vulong delta=AbsDifference<vulong>(v1,v2);
   vulong dRed=vec_splat(delta,1);
   vulong dGreen=vec_splat(delta,2);
   vulong dBlue=vec_splat(delta,3);
   
   vulong vMax=vec_max(dRed,dGreen);
   vulong vMinA=vec_min(dRed,dGreen);
   vulong vMinB=vec_min(vMax,dBlue);
   vMax=vec_max(vMax,dBlue);
   
   vulong k4=(vulong)(4,4,4,4);
   vushort k5=(vushort)(5,5,5,5, 5,5,5,5);
   
   vulong k0=(vulong)(0,0,0,0);
   
   vulong sum=vec_add(vMinA,vMinB);
   sum=vec_msum((vushort)sum,k5,k0);   // *5
   sum=vec_sr(sum,k4);               // /16
   sum=vec_add(sum,vMax);
   
   vec_ste((vlong)sum,0,result);
}
class Spot
////////////////////////////////////////////////////////////////////////////////////
//
// A Spot represents a square of 4 by 4 pixels, 
// This is the smallest screen element representable 
// as a set of vectors, each vector in a different color plane
// Color planes are R, G, B, and alpha, 
// The alpha values (x) are ignored.
//
////////////////////////////////////////////////////////////////////////////////////
class Spot
{
   vuchar   xrgb[kSpotSize];
public:
   void Init(Pixel* pixels,int rowPitch)
// Initializes a full spot of 16 pixels and computes spot luminance.  
// We copy the 16 pixels into vectors, 
//      using memcpy because the original pixels may not be 16-byte aligned
   {
      for (int i=0;i<kSpotSize;i++,pixels+=rowPitch)
         std::memcpy(xrgb+i,pixels,sizeof(vuchar));
          
      MakeColorPlanes();
   }
   
   ulong ColorDistance(Spot& S)
// Wrapper for the inline vector function VColorDistance()
   {
      long result;
      VColorDistance(
         xrgb[1],xrgb[2],xrgb[3],
         S.xrgb[1],S.xrgb[2],S.xrgb[3],
         &result);
      return result;
   } 
   
   
   ulong ColorDistanceLong(Spot& S)
// Wrapper for the inline vector function VColorDistanceLong()
   {
      long result;
      VColorDistanceLong(
         (vulong)(xrgb[0]),
         (vulong)(S.xrgb[0]),
         &result);
      return result;
   }
   
   ulong Luminance() const 
// Returns the spot luminance stored at xrgb[0]
   {
      return *((ulong*)(xrgb));
   }
private:
   
   void MakeColorPlanes() 
// Transforms 4 rows of 4 pixels each into 3 color planes and a luminance plane.   
// Uses vector operations to efficiently move the 16 R,G,B pixel values around.
   {
      vuchar vXRGB0=xrgb[0];
      vuchar vXRGB1=xrgb[1];
      vuchar vXRGB2=xrgb[2];
      vuchar vXRGB3=xrgb[3];
      
      vuchar vRB01=vec_pack((vushort)vXRGB0,(vushort)vXRGB1);
                                                               //extract RB
      vuchar vRB23=vec_pack((vushort)vXRGB2,(vushort)vXRGB3);
   
      vuchar k8=(vuchar)(8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8);
      vuchar v0XRG0=vec_sro(vXRGB0,k8);               //shift right 
      vuchar v0XRG1=vec_sro(vXRGB1,k8);
      vuchar v0XRG2=vec_sro(vXRGB2,k8);
      vuchar v0XRG3=vec_sro(vXRGB3,k8);
   
      vuchar vXG01=vec_pack((vushort)v0XRG0,(vushort)v0XRG1);   
                                                               // extract XG
      vuchar vXG23=vec_pack((vushort)v0XRG2,(vushort)v0XRG3);
   
   
      vuchar vB=vec_pack((vushort)vRB01,(vushort)vRB23);      
                                                               // extract B
      xrgb[3]=vB;                                    // store B
      vuchar vG=vec_pack((vushort)vXG01,(vushort)vXG23);      
                                                               // extract G
      xrgb[2]=vG;                                    // store G
   
      vuchar v0R01=vec_sro(vRB01,k8);                  //shift right 
      vuchar v0R23=vec_sro(vRB23,k8);
   
      vuchar vR=vec_pack((vushort)v0R01,(vushort)v0R23);      
                                                               // extract R
      xrgb[1]=vR;                                    // store R
         
// Add all R G B components to obtain the spot luminance:
      vulong   k0=(vulong)(0,0,0,0);
      vulong   sumB = vec_sum4s(vB,k0);
      vulong   sumG = vec_sum4s(vG,k0);   
      vulong   sumR = vec_sum4s(vR,k0);
      vulong   sumBG= vec_add(sumB,sumG);
      vulong   sumRBG=vec_add(sumBG,sumR);
      vlong    lrgb = vec_sums((vlong)sumRBG,(vlong)k0);
#if SCHEME==2
// Compute the individual RGB sums ( = average color of a spot)
// lrgb = luminance, red, green, blue
      lrgb = vec_sld((vulong)lrgb,k0,12);
      sumR = (vulong)vec_sums((vlong)sumR,(vlong)k0);
      sumR = vec_sld(sumR,k0,8);
      sumG = (vulong)vec_sums((vlong)sumG,(vlong)k0);
      sumG = vec_sld(sumG,k0,4);
      sumB = (vulong)vec_sums((vlong)sumB,(vlong)k0);
      lrgb = vec_or(lrgb,sumR);
      lrgb = vec_or(lrgb,sumB);
      lrgb = vec_or(lrgb,sumG);
#else
// Splat luminance into all 4 words 
// lrgb = luminance only
      lrgb = vec_splat(lrgb,3);                           
#endif
      xrgb[0]=(vuchar)lrgb;      // store luminance (and avg RGB in SCHEME 2)
   }
   
};
struct Slice
////////////////////////////////////////////////////////////////////////////////////
//
// A Slice is an element in a singly linked list.
// A slice identifies a slice (of arbitrary dimension) in an element 
//      by its top left corner.
//
////////////////////////////////////////////////////////////////////////////////////
struct Slice
{
   Slice*   next;
   short   elementId;
   uchar   top;
   uchar   left;
   Slice():next(0),elementId(0),top(0),left(0)   {}
   Slice(Slice* s,long id,long t,long l):
      next(s),
      elementId(id),
      top(t),
      left(l)
   {}
};
typedef Slice* SlicePtr;
class Image
////////////////////////////////////////////////////////////////////////////////////
//
// An Image is represented by a reference to the original (32-bit) RGB pixels
// The pixels may converted into a representation as spots.
// All elements, the desired image, the mosaic, and the current tile, are 
// represented by an image structure.   
//
// When used for elements and the current tile, spots are allocated (planar copies
// of the pixels), and corresponding data members initialized and used.
//
////////////////////////////////////////////////////////////////////////////////////
class Image
{
   Pixel*   pixels;         // pixel pointer to original pixels
   Spot*   spots;            // spots are allocated for elements and tiles
   bool   allocedPixels;
   bool   allocedSpots;
   
   short   width;            // width of the image in pixels
   short   height;
   short   rowPitch;      // rowBytes / 4
   long   elementId;         // needed when element is copied to a mosaic piece
   
   long   numSpots;         // spots related dimensions
   short   numSpotsH;      // horizontal
   short   numSpotsV;      // vertical
   
public:   
// Image Constructors
   Image():
      pixels(0),spots(0),
      allocedPixels(false),allocedSpots(false)
   {}
   Image(Pixel* c_pixels,
         Spot* c_spots,
         bool c_allocPixels,
         bool c_allocSpots,
         long c_Width,
         long c_Height,
         long c_RowPitch,
         long id):
      pixels(c_pixels),
      spots(c_spots),
      allocedPixels(c_allocPixels),
      allocedSpots(c_allocSpots),
      width(c_Width),
      height(c_Height),
      rowPitch(c_RowPitch),
      elementId(id)
   {}
   
// Image Destructor
   ~Image()
   {
      if (allocedSpots && spots) delete [] spots;
      if (allocedPixels && pixels) delete [] pixels;
   }
// Image accessor functions   
   long Width() const {return width;}
   long Height() const {return height;}
   ulong* Pixels(int row,int col) const 
   {
      return pixels+col+row*rowPitch;
   }
   long RowPitch() const {return rowPitch;}
   
   
   void Init(const PixMapHandle pm,long id)
// Initializes an Image from a QuickDraw PixMapHandle
   {
      pixels=(Pixel*)GetPixBaseAddr(pm);
      allocedPixels=false;
      allocedSpots=false;
      width=(**pm).bounds.right-(**pm).bounds.left;
      height=(**pm).bounds.bottom-(**pm).bounds.top;
      rowPitch=(0x3FFF & (**pm).rowBytes)/sizeof(Pixel);
      elementId=id;
      spots=0;
   }
   
// Update Functions change the image information for a previously initialized image.
// Saves deleting/reconstructing successive slices or tiles during the search.
   void Update(Pixel* c_pixels,long c_Width,long c_Height)
   {
      pixels=c_pixels;
      width=c_Width;
      height=c_Height;
   }
   
   void Update(Pixel* c_pixels)
   {
      pixels=c_pixels;
   }
   
   void AllocateSpots()
// Computes number of spots, and allocates new spots for the image.
   {
      numSpotsH=width/kSpotWidth;
      numSpotsV=height/kSpotHeight;
      numSpots=numSpotsH*numSpotsV;
      spots = new Spot[numSpots];
      allocedSpots=true;
   }
   
   Spot* InitSpots()
// Allocates spots if necessary.
// Initializes the spots on a 4-pixel grid (kSpotWidth=kSpotHeight=4).
// If image width or height are not multiples of four, pixels
// along the bottom and right edges are not represented in spots.
// Returns the (possibly newly allocated) spots.
   {
      if (!spots) AllocateSpots();
         
      numSpotsH=width/kSpotWidth;
      numSpotsH=height/kSpotHeight;
      
      Spot* SP=spots-1;
      Pixel* pRow=pixels;   
      Pixel* pCol=pRow;
      long col;   
      for (int row=0;row<numSpotsV;row++)
      {
         for (col=0;col<numSpotsH;col++,pCol+=kSpotWidth)
         {
            (++SP)->Init(pCol,rowPitch);
          }
         
         pRow+=kSpotHeight*rowPitch;
         pCol=pRow;
      }
      return spots;
   }
   
   long PrepareSlices(Slice** sliceIndex,long tileRangeH,
                                          long tileRangeV)
// For each possible slice in an element, computes slice luminance and
//       attaches the slice to a list in sliceIndex[luminance].
// Returns the number of slices.
   {
      assert(spots);
      long spotRangeH=numSpotsH-tileRangeH;
      long spotRangeV=numSpotsV-tileRangeV;
      for (long spotRow=0;spotRow<spotRangeV;spotRow++)
      {
         for (long spotCol=0;spotCol<spotRangeH;spotCol++)
         {
            ulong luminance=
            SliceLuminance(spotRow,spotCol,tileRangeH,tileRangeV);
            assert(luminance < kNumLuminanceLevels);
            Slice* newSlice=new Slice(sliceIndex[luminance],elementId,
               4*spotRow,4*spotCol);
            sliceIndex[luminance]=newSlice;
         }
      }
      return spotRangeV*spotRangeH;
   }
   
   long SliceLuminance(long spotRow,long spotCol,
                                          long tileRangeH,long tileRangeV)
// Returns a normalized sum of luminance values of a tile or slice.
   {
      Spot* S=spots+spotCol+spotRow*numSpotsH;
      ulong sum=0;
      for (long r=0;r<tileRangeV;r++)
      {
         for (long c=0;c<tileRangeH;c++)
         {
            ulong lu=S[c].Luminance();
            sum+=lu;
         }
         S+=numSpotsH;
      }
      sum /= tileRangeV*tileRangeH*kSpotSize*kSpotSize;
      assert(sum<kNumLuminanceLevels);
      return sum;
   }
   
   long TileLuminance()
// Returns a normalized sum of luminance values of a tile.
   {
      long lum=SliceLuminance(0,0,numSpotsH,numSpotsV);
      return lum;
   }
   
   ulong RawDistance(Slice* slice,Image& tile,ulong minDistance)
// Computes the raw color distance between a slice in an element, and the image tile.
// Breaks computation off early if (previously found) minimum distance is exceeded.
// Returns the accumulated color distance.
   {
      long bottom=slice->top/4+tile.numSpotsV;
      long right=slice->left/4+tile.numSpotsH;
      Spot* elementSpot=spots+slice->top/4*numSpotsH;
      Spot* tileSpot=tile.spots;
      ulong diff=0;
      for (long row=slice->top/4;row<bottom;row++)
      {
         for (long col=slice->left/4;col<right;col++)
         {
#if SCHEME==2
            long d=elementSpot[col].ColorDistanceLong(tileSpot[0]);
#else
            long d=elementSpot[col].ColorDistance(tileSpot[0]);
#endif
            diff+=d;
            if (diff>minDistance)
               return diff;
            tileSpot++;
         }
         elementSpot+=numSpotsH;
      }
      return diff;
   }
   
   ulong ColorDistance(Image& tile)
// The same purpose as Image::RawDistance, but used when the class instance of 
// the image is a custom copy of a slice (on a 1-pixel grid).
// This avoids having to deal with unaligned spots.
   {
      assert(spots);
      assert(tile.spots);
      assert(numSpots==tile.numSpots);
      ulong diff=0;
      for (int i=0;i<numSpots;i++)
      {
         long d=spots[i].ColorDistance(tile.spots[i]);
         diff+=d;
      }
      return diff;
   }
   
   ulong MatchVicinity(Slice& slice,Image& tile)
// After having found a good candidate slice, this function is used to micro-align
//       the slice on a 1-pixel grid, in order to obtain a possibly better match.
// A +-3 pixel vicinity of the original slice position is explored.
   {
      enum {DELTA=3};
      ulong minDistance=0xFFFFFFFF;
      int r0=slice.top-DELTA;if (r0<0) r0=0;
      int c0=slice.left-DELTA;if (c0<0) c0=0;
      int r1=slice.top+DELTA;
         if (r1>=height-tile.height) r1=height-tile.height;
      int c1=slice.left+DELTA;
         if (c1>=width-tile.width) c1=width-tile.width;
      Image sliceImage 
         (Pixels(r0,c0),0,0,0,tile.width,tile.height,rowPitch,0);
      for (int row=r0;row<r1;row++)
      {
         for (int col=c0;col<c1;col++)
         {
            sliceImage.Update(Pixels(row,col));
            sliceImage.InitSpots();
            ulong colorDistance=sliceImage.ColorDistance(tile);
            if (colorDistance<minDistance)
            {
               minDistance=colorDistance;
               slice.top=row;
               slice.left=col;
            }
         }
      }
      return minDistance;   
   }
   
   void CopyToPiece(
      MosaicPiece& piece,int top,int left,
      int pieceWidth,int pieceHeight,
      int sliceTop,int sliceLeft)
// Copies the pixels identified by a slice in an element, to a MosaicPiece.
   { 
      piece.elementIndex=elementId;
      Rect elementRect={sliceTop,sliceLeft,sliceTop+pieceHeight,
            sliceLeft+pieceWidth};
      piece.elementRect=elementRect;
      Rect mosaicRect={top,left,top+pieceHeight,left+pieceWidth};
      piece.mosaicRect=mosaicRect;
   }
   void CopySlice(Image& E,
      int top,int left,
      int pieceWidth,int pieceHeight,long sliceTop,long sliceLeft)
// Copies the pixels identified by a slice in an element, into the mosaic image
   { 
      int srcRow=sliceTop,srcCol=sliceLeft;   // TL corner of slice
      Pixel* src=E.Pixels(srcRow,srcCol);   // slice pixels
      Pixel* dest=pixels+left+top*rowPitch;   // mosaic pixels
      for (int row=0;row<pieceHeight;row++)
      {
         for (int col=0;col<pieceWidth;col++)
         {
            dest[col]=src[col];
         }
         src+=E.rowPitch;
         dest+=rowPitch;
      }
   }
};
class Mosaic
////////////////////////////////////////////////////////////////////////////////////
//
// The class Mosaic is initialized by InitMosaic() and destroyed in TermMosaic().
// It provides the links to the elements, builds tiles as required,
//      and matches the element slices to the desired image(s).
//
////////////////////////////////////////////////////////////////////////////////////
class Mosaic
{
// The following data members are defined when InitMosaic() function runs
   const PixMapHandle*   element;
   long   numElements;
   Image*   elementImages;
   
// The following data members vary with the image and are defined when Mosaic() 
// function runs
   Slice**   sliceIndex;         // Array of linked lists of slices
   
   Image*   desiredImage;      // the desired image to be matched
   short   imageWidth;
   short   imageHeight;
   
   short   tileWidth;            // min tile width compatible with desired image
   short   tileHeight;         // min tile height compatible with desired image
   short   tileRangeH;         // tile width in terms of spots
   short   tileRangeV;         // tile height in terms of spots
   long    numTileColsNarrow;  // number of narrow columns of tiles of tileWidth
   long   numTileCols;         // total number of tile columns (narrow + wide)
   long   numTileRowsShort;// number of short rows of tiles of tileHeight
   long   numTileRows;         // total number of tile rows (short + tall)
   long   numTiles;               // = number of mosaic pieces
   long   searchRange;         // value controlling extent of search in sliceIndex
   short   previousTileRangeH;   // if successive calls to Mosaic() result in identical
   short   previousTileRangeV; // tileRanges, we can avoid some recomputations.
   
public:
// An instance of class Mosaic is constructed with the element images to be used later. 
   Mosaic(const PixMapHandle c_element[],long c_numElements) :
      element(c_element),
      numElements(c_numElements),
      elementImages(new Image[c_numElements]),
      sliceIndex(0),
      desiredImage(0),
      searchRange(0),
      previousTileRangeH(0),
      previousTileRangeV(0)
   {
      for (int i=0;i<numElements;i++)
      {
         LockPixels(element[i]);      // element pixels locked in constructor
         elementImages[i].Init(element[i],i);
         elementImages[i].InitSpots();
      }
   }
   
// Destructor runs when TermMosaic is called
   ~Mosaic()
   {
      for (int i=0;i<numElements;i++)
      {
         UnlockPixels(element[i]);   // element pixels unlocked in destructor
      }
      if (desiredImage) delete desiredImage;
      DeleteSliceIndex();
      if (elementImages) delete [] elementImages; 
   }
   
   long PrepareMosaic(const PixMapHandle c_desiredImage,
                                    const Rect c_minPieceSize)
// Called from Mosaic(), to prepare the image and the elements for the search.
// Chooses a (initial) search range, to achieve reasonable quality and run time.
// The plan was to update this number periodically as the search progresses (TBD).
// Returns the number of tiles that will be used to construct the mosaic.
   {      
      PrepareDesiredImage(c_desiredImage,c_minPieceSize);
      PrepareElements();
      ChooseInitialSearchRange();
      return numTiles;
   }
   
   double SolveMosaic(PixMapHandle mosaic,MosaicPiece *piece)
// Each tile of the mosaic is independently chosen, after comparison with the
//       selected range of candidate slices.
   {
      Pixel* P=desiredImage->Pixels(0,0);
      long rowPitch=desiredImage->RowPitch();
      Pixel* mosaicP=(Pixel*)GetPixBaseAddr(mosaic);
      assert(mosaicP);
      long mosaicRowPitch=
            (0x3FFF & (**mosaic).rowBytes)/sizeof(Pixel);
      
      assert(mosaicRowPitch==desiredImage->RowPitch());
      Image mosaicImage;
      mosaicImage.Init(mosaic,0);
      long pixelRow=0;
      long pieceHeight;
      // preallocate largest tile
      Image tileToMatch(0,0,0,0,tileWidth+1,tileHeight+1,
               rowPitch,-1001);
      tileToMatch.AllocateSpots();
         
      Slice bestSlice;
      SlicePtr sliceP=0;
      
      for (long tileRow=0; tileRow<numTileRows; 
                                 tileRow++,pixelRow+=pieceHeight)
      {
         long pixelCol=0;
pieceHeight=(tileRow<numTileRowsShort)?tileHeight:tileHeight+1;
         long pieceWidth;
         for (long tileCol=0; tileCol<numTileCols; 
                     tileCol++,pixelCol+=pieceWidth)
         {
            pieceWidth=
               (tileCol<numTileColsNarrow)?tileWidth:tileWidth+1;
      tileToMatch.Update(P+pixelCol+pixelRow*rowPitch,pieceWidth,
                                       pieceHeight);
            tileToMatch.InitSpots();
            
// The call to MatchTile, once per mosaic piece, obtains the best matching slice on
//       the 4-pixel grid.
            MatchTile(tileToMatch,&sliceP);
            assert(sliceP);
            
// Starting from the slice on the 4-pixel grid, MatchVicinity scans the neighborhood
//       of this slice in an effort to obtain the "best slice".
            bestSlice=*sliceP;
            elementImages[bestSlice.elementId].MatchVicinity(bestSlice,
                                          tileToMatch);
               
// The best slice is copied into the next MosaicPiece structure,
            elementImages[bestSlice.elementId].CopyToPiece(
               *piece++,pixelRow,pixelCol,
               pieceWidth,pieceHeight,
               bestSlice.top,bestSlice.left);
// ... and copied into the mosaic.
            mosaicImage.CopySlice(
               elementImages[bestSlice.elementId],
               pixelRow,pixelCol,pieceWidth,pieceHeight,
               bestSlice.top,bestSlice.left);
         }
      }
      return 0;
   }
   
   void Cleanup()
// Cleanup is needed after each desired image has been made into a mosaic, to delete it.
   {
      delete desiredImage;
      desiredImage=0;
   }
   
private:
   void DeleteSliceIndex()
// DeleteSliceIndex contains a loop to delete all individually allocated slices.
   {
      if (!sliceIndex) return;
      for (int i=0;i<kNumLuminanceLevels;i++)
      {
         Slice* S=sliceIndex[i];
         while (S)
         {
            Slice* nextSlice=S->next;
            delete S;
            S=nextSlice;
         }
      }
      delete [] sliceIndex;
   }
   
   long FindTileSize(long x,long t,long& n,long& m)
// Solves the diophantine equation: n*t + m*(t+1) == x.
//       x = image size (width or height),
//       t = initially the minimum tile size,
// sets n (number of tiles size t) and m (number of tiles size t+1),
// This function is useful in finding the smallest possible tile dimensions,
//      that are compatible with the image dimensions.
// The assumption is that smaller tiles provide better matches
// Returns t which may have been increased from the initial value.
   {
      for (;;)
      {
         n=x/t;
         m=x-n*t;
         n=(x-m*(t+1))/t;
         if (n>=0)
            break;
         t++;
      }
      return t;
   }
   
   void PrepareDesiredImage(const PixMapHandle c_desiredImage,
                                    const Rect c_minPieceSize)
// Analyses the dimensions of the desired image, and minPieceSize,
//       and determines tiling constants.
// Determines the total number of mosaic pieces needed (numTiles).
   {
      desiredImage=new Image;
      desiredImage->Init(c_desiredImage,-1);
   
      const Rect& iBounds=(**c_desiredImage).bounds;
      imageWidth=iBounds.right-iBounds.left;
      imageHeight=iBounds.bottom-iBounds.top;
      
      tileWidth=c_minPieceSize.right-c_minPieceSize.left;
      tileHeight=c_minPieceSize.bottom-c_minPieceSize.top;
      
      long numTileColsLong;
      tileWidth=FindTileSize(imageWidth,tileWidth,
                                 numTileColsNarrow,numTileColsLong);
      numTileCols=numTileColsNarrow+numTileColsLong;
      
      long numTileRowsLong;
      tileHeight=FindTileSize(imageHeight,tileHeight,
                                 numTileRowsShort,numTileRowsLong);
      numTileRows=numTileRowsShort+numTileRowsLong;
      
      tileRangeH=tileWidth/kSpotWidth;
      tileRangeV=tileHeight/kSpotHeight;
      
      numTiles=numTileCols*numTileRows;
   }
   
   void PrepareElements()
// Using tile size information, prepares the slice inventory based on average 
//   luminance.
// If tile size has not changed from the previous image, there is no need to redo this.
   {
      if ((tileRangeH == previousTileRangeH) && 
                                          (tileRangeV == previousTileRangeV))
         return;
         
      previousTileRangeH=tileRangeH;
      previousTileRangeV=tileRangeV;      
   
      if (sliceIndex) DeleteSliceIndex();
      sliceIndex=new SlicePtr[kNumLuminanceLevels];
      std::memset(sliceIndex,0,
                     kNumLuminanceLevels*sizeof(SlicePtr));
      for (int i=0;i<numElements;i++)
      {
         elementImages[i].
            PrepareSlices(sliceIndex,tileRangeH,tileRangeV);
      }
   }
   
   void ChooseInitialSearchRange()
// A simple attempt to define a search range that will give a good match,
//       without running unreasonably long. 
   {
      long imageSize=desiredImage->Width()*desiredImage->Height();
      searchRange=kSearchRangeFactor/imageSize;   
   }
   
   ulong MatchTile(Image& tileToMatch,SlicePtr* bestSliceP)
// Function MatchTile matches the tile against all slices within the search range.
// It starts in the slice inventory with slices of the same luminance as the tile.
// Then slices of higher and lower luminance are considered, until the search range
//      is exhausted.
// For each slice, the color distance to the tile is determined,
//      the smallest distance is retained as minDistance, together with bestSliceP.
// Returns the minimum distance, and a pointer to the best slice in the invetory.
   {   
      long tileLuminance=tileToMatch.TileLuminance();
      assert(tileLuminance<kNumLuminanceLevels);
      assert(sliceIndex);
      
      ulong minDistance=0xFFFFFFFF;
      if (*bestSliceP) // try previous best slice first to benchmark minDistance.
      {   
         minDistance=
            elementImages[(*bestSliceP)->elementId].
            RawDistance(*bestSliceP,tileToMatch,minDistance);
      }
      
      int leftToCheck=searchRange/2;
      for (int i=tileLuminance;i<kNumLuminanceLevels;i++)
      {
         leftToCheck=MatchSliceList(
                  sliceIndex[i],tileToMatch,*bestSliceP,
                     minDistance,leftToCheck);
         if (leftToCheck<=0) break;   
      }
      
      leftToCheck=searchRange/2;
      for (int i=tileLuminance-1;i>0;i--)
      {
         leftToCheck=MatchSliceList(
                        sliceIndex[i],tileToMatch,*bestSliceP,
                        minDistance,leftToCheck);
         if (leftToCheck<=0) break;   
      }
      return minDistance;
   }
   
   int MatchSliceList(Slice* slice,Image& tileToMatch,
                                                   SlicePtr& bestSlice,
      ulong& minDistance,int leftToCheck)
// Function MatchSliceList matches slices in a list against a tile.
// Returns when the list exhausted, or earlier if the list is longer than
//      the parameter "leftToCheck".
// Returns the reduced value of leftToCheck.
   {
      while (slice) 
      {                                       
         ulong colorDistance=
            elementImages[slice->elementId].
            RawDistance(slice,tileToMatch,minDistance);
         if (colorDistance < minDistance)
         {
            minDistance=colorDistance;         
            bestSlice=slice;
         }
         if (--leftToCheck <= 0) break;
         slice=slice->next;
      }         
      return leftToCheck;   
   }
   
};
} // namespace
#endif

 
AAPL
$97.67
Apple Inc.
+0.64
MSFT
$44.50
Microsoft Corpora
+0.10
GOOG
$589.02
Google Inc.
-4.33

MacTech Search:
Community Search:

Software Updates via MacUpdate

Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more
Autopano Giga 3.6 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more
Airfoil 4.8.7 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
Microsoft Remote Desktop 8.0.8 - Connect...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
xACT 2.30 - Audio compression toolkit. (...
xACT stands for X Aaudio Compression Toolkit, an application that encodes and decodes FLAC, SHN, Monkey’s Audio, TTA, Wavpack, and Apple Lossless files. It also can encode these formats to MP3, AAC... Read more

Latest Forum Discussions

See All

This Week at 148Apps: July 21-25, 2014
Another Week of Expert App Reviews   At 148Apps, we help you sort through the great ocean of apps to find the ones we think you’ll like and the ones you’ll need. Our top picks become Editor’s Choice, our stamp of approval for apps with that little... | Read more »
Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »
Jacob Jones and the Bigfoot Mystery : Ep...
Jacob Jones and the Bigfoot Mystery : Episode 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Jacob Jones is back in Episode 2 of one of Apples 'Best of 2013' games and an App Store... | Read more »
New Trailer For Outcast Odyssey, A New K...
New Trailer For Outcast Odyssey, A New Kind of Card Battler Posted by Jennifer Allen on July 25th, 2014 [ permalink ] Out this Fall is a new kind of card battle game: Outcast Odyssey. | Read more »
Hay Day – Tip, Tricks, Strategies, and C...
Recently got into Supercell’s other huge hit, Hay Day and could do with some advice on what to do? We’ve got you covered with some helpful trips and tricks to bear in mind! Ticking Along One of the key things to keep in mind while building up that... | Read more »
Monster Head Review
Monster Head Review By Nadia Oxford on July 25th, 2014 Our Rating: :: FEEDING TIMEUniversal App - Designed for iPhone and iPad Racking up a high score with Monster Head is trickier than it first appears. The appeal wears out fairly... | Read more »
Garfield: Survival of the Fattest Coming...
Garfield: Survival of the Fattest Coming to iOS this Fall Posted by Jennifer Allen on July 25th, 2014 [ permalink ] Who loves lasagna? Me. Also everyone’s favorite grumpy fat cat, Garfield. | Read more »
Happy Flock Review
Happy Flock Review By Andrew Fisher on July 25th, 2014 Our Rating: :: HERD IT ALL BEFOREUniversal App - Designed for iPhone and iPad Underneath the gloss of Happy Flock’s visuals is a game of very little substance. It’s cute, but... | Read more »
Square Register Updates Adds Offline Pay...
Square Register Updates Adds Offline Payments Posted by Ellis Spice on July 25th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Looking For Group – Hearthstone’s Curse...
For the first time since its release (which has thankfully been a much shorter window for iPad players than their PC counterparts), Blizzard’s wildly successful Hearthstone: Heroes of Warcraft CCG is sporting some brand new content: the single... | Read more »

Price Scanner via MacPrices.net

Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more
Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more
Save on 5th generation refurbished iPod touch...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
What Should Apple’s Next MacBook Priority Be;...
Stabley Times’ Phil Moore says that after expanding its iMac lineup with a new low end model, Apple’s next Mac hardware decision will be how it wants to approach expanding its MacBook lineup as well... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
WW Sales Program Manager, *Apple* Online St...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
Lead Software Engineer, *Apple* Online Stor...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
Manager, *Apple* Fullfillment Operation (AF...
…cross-functional teams to drive the highest level of program management quality for Apple . You will help plan launch strategy and demand generation programs with Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.