Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

plfilterquantize.cpp

Go to the documentation of this file.
00001 /*
00002 /--------------------------------------------------------------------
00003 |
00004 |      $Id: plfilterquantize.cpp,v 1.1 2004/05/21 21:02:53 maxx Exp $
00005 |
00006 |      Copyright (c) 1996-1998 Ulrich von Zadow
00007 |
00008 |      Based on code:
00009 |
00010 |        Copyright (C) 1998 - 2000 by Punk Productions Electronic Entertainment.
00011 |                                http://cust.nol.at/ppee
00012 |        Content: Quantization/Dithering
00013 |        Programmer: Nikolaus Brennig (virtualnik@nol.at)
00014 |
00015 |      and
00016 |
00017 |        DIBQuant version 1.0
00018 |        Copyright (c) 1993 Edward McCreary.
00019 |        All rights reserved.
00020 |
00021 |        Redistribution and use in source and binary forms are freely permitted
00022 |        provided that the above copyright notice and attibution and date of work
00023 |        and this paragraph are duplicated in all such forms.
00024 |        THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR
00025 |        IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
00026 |        WARRANTIES OF MERCHANTIBILILTY AND FITNESS FOR A PARTICULAR PURPOSE.
00027 |
00028 \--------------------------------------------------------------------
00029 */
00030 
00031 #include "plstdpch.h"
00032 #include "plfilterquantize.h"
00033 #include "plbitmap.h"
00034 #include "plexcept.h"
00035 
00036 #include "../minmax.h"
00037 
00038 #define COLOR_MAX     32
00039 
00040 PLFilterQuantize::PLFilterQuantize (int DitherPaletteType, int DitherType)
00041   : PLFilter(),
00042     m_DitherPaletteType (DitherPaletteType),
00043     m_DitherType (DitherType),
00044     m_pUserPal (NULL),
00045     m_ppHisto (NULL),
00046     m_pQuBoxes (NULL)
00047 {
00048   initLUT();
00049 }
00050 
00051 PLFilterQuantize::~PLFilterQuantize()
00052 {
00053   deleteLUT();
00054   if (m_pUserPal != NULL)
00055   {
00056     delete[] m_pUserPal;
00057     m_pUserPal = NULL;
00058   }
00059 }
00060 
00061 void PLFilterQuantize::Apply(PLBmp * pBmpSource, PLBmp * pBmpDest) const
00062 {
00063   // PLBYTE ** pDstLines = pBmpDest->GetLineArray();
00064 
00065   // Only works for 32 bpp bitmaps.
00066   PLASSERT (pBmpSource->GetBitsPerPixel() == 32);
00067 
00068   pBmpDest->Create (pBmpSource->GetWidth(), pBmpSource->GetHeight(), 8, 
00069                     false, pBmpSource->GetResolution());
00070 
00071   if (m_DitherPaletteType != PLDTHPAL_DEFAULT &&
00072       m_DitherPaletteType != PLDTHPAL_USERDEFINED)
00073     genColorArray(pBmpSource);
00074 
00075   // Generate the palette.
00076   switch (m_DitherPaletteType)
00077   {
00078     case PLDTHPAL_MEDIAN:
00079       genMedianPalette (pBmpSource, pBmpDest);
00080       break;
00081     case PLDTHPAL_POPULARITY:
00082       genPopularityPalette(pBmpSource, pBmpDest);
00083       break;
00084     case PLDTHPAL_DEFAULT:
00085       genDefaultPalette(pBmpDest);
00086       break;
00087     case PLDTHPAL_USERDEFINED:
00088       // The destination bitmap contains already a palette (e.g. a custom halftone palette)
00089       if (m_pUserPal)
00090         pBmpDest->SetPalette(m_pUserPal);
00091       else
00092         genDefaultPalette(pBmpDest);    // Fallback to the default palette...
00093       break;
00094     default:
00095       // Incorrect palette type specified in constructor.
00096       PLASSERT (false);
00097   }
00098 
00099   ditherDestBmp(pBmpSource, pBmpDest);
00100 }
00101 
00102 void PLFilterQuantize::SetUserPalette(const PLPixel32* pPal)
00103 {
00104   if (m_pUserPal != NULL)
00105     delete[] m_pUserPal;
00106   m_pUserPal = new PLPixel32[256];
00107   memcpy(m_pUserPal, pPal, sizeof(PLPixel32)*256);
00108 }
00109 
00110 // Initialize local variables
00111 void PLFilterQuantize::initLUT()
00112 {
00113   PLULONG i;
00114 
00115   m_pQuBoxes = new QUBOX[256];
00116   if (!m_pQuBoxes)
00117     throw (PLTextException (PL_ERRNO_MEMORY, "Out of memory."));
00118 
00119   PLULONG len = (long)COLOR_MAX*(long)COLOR_MAX*(long)COLOR_MAX;
00120 
00121   // buffer to store every color in image
00122   m_ppHisto = new HISTONODE*[len];
00123   for (i=0; i<len; i++)
00124     m_ppHisto[i] = NULL;
00125 }
00126 
00127 void PLFilterQuantize::deleteLUT()
00128 {
00129   delete[] m_pQuBoxes;
00130 
00131   int len = (long)COLOR_MAX*(long)COLOR_MAX*(long)COLOR_MAX;
00132 
00133   int i;
00134   if (m_ppHisto)
00135     for (i=0; i<len; i++)
00136       if (m_ppHisto[i])
00137         delete m_ppHisto[i];
00138 
00139   delete[] m_ppHisto;
00140 }
00141 
00142 
00143 void PLFilterQuantize::genMedianPalette (PLBmp * pBmpSource, PLBmp * pBmpDest) const
00144 {
00145   //--------------------------------------------------------------
00146   // build new palette with median cut algorithm
00147   // I didn't write this, if you know who did, please let me know!
00148   //                                               Ed McCreary
00149   //--------------------------------------------------------------
00150 
00151   /* force the counts in the corners to be zero */
00152   addColor (PLPixel32 (0,0,0,0), 0L);
00153   addColor (PLPixel32 (31,0,0,0), 0L);
00154   addColor (PLPixel32 (0,31,0,0), 0L);
00155   addColor (PLPixel32 (0,0,31,0), 0L);
00156   addColor (PLPixel32 (31,31,0,0), 0L);
00157   addColor (PLPixel32 (0,31,31,0), 0L);
00158   addColor (PLPixel32 (31,0,31,0), 0L);
00159   addColor (PLPixel32 (31,31,31,0), 0L);
00160 
00161   /* assign the 1st eight boxes to be the corners */
00162   makeBox (PLPixel32 (0,0,0,0), 0, 1L);
00163   makeBox (PLPixel32 (31,0,0,0), 1, 1L);
00164   makeBox (PLPixel32 (0,31,0,0), 2, 1L);
00165   makeBox (PLPixel32 (0,0,31,0), 3, 1L);
00166   makeBox (PLPixel32 (31,31,0,0), 4, 1L);
00167   makeBox (PLPixel32 (0,31,31,0), 5, 1L);
00168   makeBox (PLPixel32 (31,0,31,0), 6, 1L);
00169   makeBox (PLPixel32 (31,31,31,0), 7, 1L);
00170 
00171   /* set up 9th box to hold the rest of the world */
00172   m_pQuBoxes[8].Corner0 = PLPixel32 (0,0,0,0);
00173   m_pQuBoxes[8].Corner1 = PLPixel32 (31,31,31,0);
00174   squeeze(&m_pQuBoxes[8]);
00175 
00176 
00177   /* split the rest of the boxes */
00178   int i;
00179   for(i=9; i<256; i++)
00180   {
00181     /* find biggest box */
00182     int Biggest = 8;
00183     int j;
00184     for( j=8; j<i; j++ )
00185       if(m_pQuBoxes[j].count > m_pQuBoxes[Biggest].count)
00186         Biggest = j;
00187     if (m_pQuBoxes[Biggest].count > 1)
00188     {
00189       /* decide which side to split the box along, and split it */
00190       PLPixel32 Corner0 = m_pQuBoxes[Biggest].Corner0;
00191       PLPixel32 Corner1 = m_pQuBoxes[Biggest].Corner1;
00192       int dr = Corner1.GetR () - Corner0.GetR ();
00193       int dg = Corner1.GetG () - Corner0.GetG ();
00194       int db = Corner1.GetB () - Corner0.GetB ();
00195       m_pQuBoxes[i] = m_pQuBoxes[Biggest];      /* copy info over */
00196 
00197       // Determine at which color component to split.
00198       int ColComp;
00199       if(dr>=dg && dr>=db)
00200         ColComp = PL_RGBA_RED;
00201       else if(dg>=db)
00202         ColComp = PL_RGBA_GREEN;
00203       else
00204         ColComp = PL_RGBA_BLUE;
00205 
00206       split (&m_pQuBoxes[i],&m_pQuBoxes[Biggest], ColComp);
00207     }
00208     else
00209     { // The biggest box has size 1. This means we've found all the colors.
00210       // Set rest of the palette to black.
00211       for (j=i; j<256; j++)
00212       {
00213         m_pQuBoxes[j].Corner0 = PLPixel32 (0,0,0,0);
00214         m_pQuBoxes[j].Corner1 = PLPixel32 (0,0,0,0);
00215         m_pQuBoxes[j].Average = PLPixel32 (0,0,0,0);
00216         m_pQuBoxes[j].count = 0;
00217       }
00218 
00219       // And make the loop exit.
00220       i = 256;
00221     }
00222   } /* end of i loop, we've found 256 boxes. */
00223 
00224 
00225   /* Generate the actual palette */
00226   PLPixel32 * pClrTab = pBmpDest->GetPalette();
00227 
00228   for( i=0; i<256; i++ )
00229   {
00230     // For each color component, find the average of the two corners of the box and
00231     // scale by the amount of colors in the palette.
00232     PLBYTE r = ((long)(m_pQuBoxes[i].Corner0.GetR ()+m_pQuBoxes[i].Corner1.GetR ()))*255/(2*31);
00233     PLBYTE g = ((long)(m_pQuBoxes[i].Corner0.GetG ()+m_pQuBoxes[i].Corner1.GetG ()))*255/(2*31);
00234     PLBYTE b = ((long)(m_pQuBoxes[i].Corner0.GetB ()+m_pQuBoxes[i].Corner1.GetB ()))*255/(2*31);
00235     pClrTab[i].Set (r,g,b,0);
00236   }
00237 }
00238 
00239 // Split a box into two at the average color.
00240 // (The actual split is done before the function is called. split() just
00241 // calculates new upper and lower bounds for the two boxes.)
00242 // ColComp is the color component that the split is done on, i.e. one of
00243 // PL_RGBA_RED, PL_RGBA_GREEN, PL_RGBA_BLUE
00244 void PLFilterQuantize::split (QUBOX * pBox0, QUBOX * pBox1, int ColComp) const
00245 {
00246   // If we had good accessor functions for the color components, this
00247   // would be more readable.
00248   PLBYTE * pB0C0 = (PLBYTE *)&(pBox0->Corner0);  // Box0, Color 0
00249   PLBYTE * pB0C1 = (PLBYTE *)&(pBox0->Corner1);
00250   //PLBYTE * pB0Ave = (PLBYTE *)&(pBox0->Average);
00251   PLBYTE * pB1C0 = (PLBYTE *)&(pBox1->Corner0);
00252   PLBYTE * pB1C1 = (PLBYTE *)&(pBox1->Corner1);
00253   PLBYTE * pB1Ave = (PLBYTE *)&(pBox1->Average);
00254 
00255   if (pB0C1[ColComp]-pB0C0[ColComp] == 2)
00256   { /* tight squeeze */
00257     pB0C1[ColComp] = pB0C0[ColComp];
00258     pB1C0[ColComp] = pB1C1[ColComp];
00259   }
00260   else
00261   { /* figure out where to split */
00262     PLBYTE j = pB1Ave[ColComp];
00263     if (j == pB1C1[ColComp])
00264       j--;
00265     pB1C1[ColComp] = j;
00266     pB0C0[ColComp] = j+1;
00267   }
00268   PLASSERT (pB0C0[ColComp] < 32);
00269   PLASSERT (pB1C0[ColComp] < 32);
00270   PLASSERT (pB0C1[ColComp] < 32);
00271   PLASSERT (pB1C1[ColComp] < 32);
00272 
00273   squeeze (pBox0);
00274   squeeze (pBox1);
00275 
00276 }
00277 
00278 // shrink a boxes extremes to fit tightly
00279 // if a box is 1x1x1 change its count to 1
00280 void PLFilterQuantize::squeeze(QUBOX * pBox) const
00281 {
00282   PLPixel32 Corner0, Corner1;
00283 
00284   Corner0 = pBox->Corner0;
00285   Corner1 = pBox->Corner1;
00286 
00287   pBox->Corner0 = PLPixel32 (31,31,31,0);
00288   pBox->Corner1 = PLPixel32 (0,0,0,0);
00289   pBox->Average = PLPixel32 (0,0,0,0);
00290 
00291   int r,g,b;
00292   int rsum = 0;
00293   int gsum = 0;
00294   int bsum = 0;
00295   PLULONG count = 0;
00296   for (r=Corner0.GetR (); r<=Corner1.GetR (); r++)
00297   {
00298     for (g=Corner0.GetG (); g<=Corner1.GetG (); g++)
00299     {
00300       for (b=Corner0.GetB (); b<=Corner1.GetB (); b++)
00301       {
00302         int index = getColorTableIndex (PLPixel32 (r,g,b,0));
00303         HISTONODE * pNode = m_ppHisto[index];
00304         if (pNode)
00305         {
00306           if (pNode->count>0L)
00307           {
00308             pBox->Corner0 = PLPixel32 (min (r, (int)pBox->Corner0.GetR ()),
00309                                       min (g, (int)pBox->Corner0.GetG ()),
00310                                       min (b, (int)pBox->Corner0.GetB ()),
00311                                       0);
00312             pBox->Corner1 = PLPixel32 (max (r, (int)pBox->Corner1.GetR ()),
00313                                       max (g, (int)pBox->Corner1.GetG ()),
00314                                       max (b, (int)pBox->Corner1.GetB ()),
00315                                       0);
00316             rsum += r*pNode->count;
00317             gsum += g*pNode->count;
00318             bsum += b*pNode->count;
00319 
00320             count += pNode->count;
00321           }
00322         }
00323       }
00324     }
00325   }
00326 
00327   /* box is now shrunk */
00328   if (count)
00329     pBox->Average = PLPixel32 ((PLBYTE)(rsum / count),
00330                               (PLBYTE)(gsum / count),
00331                               (PLBYTE)(bsum / count),
00332                               0);
00333 
00334   pBox->count = min (count, (PLULONG)0xFFFFL);
00335 
00336   if (pBox->Corner0 == pBox->Corner1)
00337   { /* box is min size */
00338     pBox->count = 1;  /* so it won't get split again */
00339   }
00340 }
00341 
00342 void SwapLong (long* pa, long* pb)
00343 {
00344   long tmp = *pa;
00345   *pa = *pb;
00346   *pb = tmp;
00347 }
00348 
00349 void PLFilterQuantize::genPopularityPalette (PLBmp * pBmpSource, PLBmp * pBmpDest) const
00350 {
00351   PLULONG PalCount[256];
00352   memset (PalCount, 0, sizeof(PLULONG)*256);
00353   PLPixel32 * pPal = pBmpDest->GetPalette();
00354 
00355   /* force corners of rgb color cube out of the running */
00356   addColor (PLPixel32 (0,0,0,0), 0L);
00357   addColor (PLPixel32 (31,0,0,0), 0L);
00358   addColor (PLPixel32 (0,31,0,0), 0L);
00359   addColor (PLPixel32 (0,0,31,0), 0L);
00360   addColor (PLPixel32 (31,31,0,0), 0L);
00361   addColor (PLPixel32 (0,31,31,0), 0L);
00362   addColor (PLPixel32 (31,0,31,0), 0L);
00363   addColor (PLPixel32 (31,31,31,0), 0L);
00364 
00365   /* force feed the corners into the palette */
00366   pPal[0] = PLPixel32 (0,0,0,0);
00367   pPal[1] = PLPixel32 (31,0,0,0);
00368   pPal[2] = PLPixel32 (0,31,0,0);
00369   pPal[3] = PLPixel32 (0,0,31,0);
00370   pPal[4] = PLPixel32 (31,31,0,0);
00371   pPal[5] = PLPixel32 (0,31,31,0);
00372   pPal[6] = PLPixel32 (31,0,31,0);
00373   pPal[7] = PLPixel32 (31,31,31,0);
00374 
00375   int r,g,b;
00376   int IndexCache = -1;
00377   HISTONODE * pNode;
00378   HISTONODE * pNodeCache = NULL;
00379   for (r=0; r<31; r++)
00380   {
00381     for (g=0; g<31; g++)
00382     {
00383       for (b=0; b<31; b++)
00384       {
00385         int index = getColorTableIndex (PLPixel32 (r,g,b,0));
00386         if (index == IndexCache)
00387           pNode = pNodeCache;
00388         else
00389         {
00390           pNode = m_ppHisto[index];
00391           pNodeCache = pNode;
00392           IndexCache = index;
00393         }
00394 
00395         if (pNode)
00396         {
00397           if(pNode->count > PalCount[255])
00398           {
00399             PalCount[255] = pNode->count;
00400             pPal[255].Set (r,g,b,0);
00401 
00402             int i = 255;        /* bubble up */
00403             while(PalCount[i] > PalCount[i-1] && i>8)
00404             {
00405               SwapLong ((long *)&PalCount[i], (long*)&PalCount[i-1]);
00406               SwapLong ((long *)&pPal[i], (long *)&pPal[i-1]);
00407               i--;
00408             }
00409           }
00410         }
00411       }       /* end of current chain */
00412     }       /* end of r loop */
00413   }
00414 
00415   int i;
00416   for (i=0; i<256; i++)
00417   {
00418     pPal[i].SetR ((int(pPal[i].GetR ())*255)/31);
00419     pPal[i].SetG ((int(pPal[i].GetG ())*255)/31);
00420     pPal[i].SetB ((int(pPal[i].GetB ())*255)/31);
00421   }
00422 }
00423 
00424 void PLFilterQuantize::genColorArray (PLBmp * pBmpSource) const
00425 {
00426   int x,y;
00427   int h = pBmpSource->GetHeight();
00428   int w = pBmpSource->GetWidth();
00429   PLPixel32 ** pSrcLines = pBmpSource->GetLineArray32();
00430   for (y=0; y<h; y++)
00431   {
00432     PLPixel32 * pSrcPixel = pSrcLines[y];
00433     for (x=0; x<w; x++)
00434     {
00435       addColor(*pSrcPixel, 1L);
00436       pSrcPixel ++;
00437     }
00438   }
00439 
00440 }
00441 
00442 PLBYTE DefaultPalette[] =
00443 {
00444   0,0,0,0,
00445   191,0,0,0,
00446   0,191,0,0,
00447   191,191,0,0,
00448   0,0,191,0,
00449   191,0,191,0,
00450   0,191,191,0,
00451   192,192,192,0,
00452   192,220,192,0,
00453   166,202,240,0,
00454   128,0,0,0,
00455   0,128,0,0,
00456   128,128,0,0,
00457   0,0,128,0,
00458   128,0,128,0,
00459   0,128,128,0,
00460   0,81,0,0,
00461   81,81,0,0,
00462   133,81,0,0,
00463   177,81,0,0,
00464   217,81,0,0,
00465   255,81,0,0,
00466   0,133,0,0,
00467   81,133,0,0,
00468   133,133,0,0,
00469   177,133,0,0,
00470   217,133,0,0,
00471   255,133,0,0,
00472   0,177,0,0,
00473   81,177,0,0,
00474   133,177,0,0,
00475   177,177,0,0,
00476   217,177,0,0,
00477   255,177,0,0,
00478   0,217,0,0,
00479   81,217,0,0,
00480   133,217,0,0,
00481   177,217,0,0,
00482   217,217,0,0,
00483   255,217,0,0,
00484   0,255,0,0,
00485   81,255,0,0,
00486   133,255,0,0,
00487   177,255,0,0,
00488   217,255,0,0,
00489   255,255,0,0,
00490   0,0,81,0,
00491   81,0,81,0,
00492   133,0,81,0,
00493   177,0,81,0,
00494   217,0,81,0,
00495   255,0,81,0,
00496   0,81,81,0,
00497   81,81,81,0,
00498   133,81,81,0,
00499   177,81,81,0,
00500   217,81,81,0,
00501   255,81,81,0,
00502   0,133,81,0,
00503   81,133,81,0,
00504   133,133,81,0,
00505   177,133,81,0,
00506   217,133,81,0,
00507   55,133,81,0,
00508   0,177,81,0,
00509   81,177,81,0,
00510   133,177,81,0,
00511   177,177,81,0,
00512   217,177,81,0,
00513   255,177,81,0,
00514   0,217,81,0,
00515   81,217,81,0,
00516   133,217,81,0,
00517   177,217,81,0,
00518   217,217,81,0,
00519   255,217,81,0,
00520   0,255,81,0,
00521   81,255,81,0,
00522   133,255,81,0,
00523   177,255,81,0,
00524   217,255,81,0,
00525   255,255,81,0,
00526   0,0,133,0,
00527   81,0,133,0,
00528   133,0,133,0,
00529   177,0,133,0,
00530   217,0,133,0,
00531   255,0,133,0,
00532   0,81,133,0,
00533   81,81,133,0,
00534   133,81,133,0,
00535   177,81,133,0,
00536   217,81,133,0,
00537   255,81,133,0,
00538   0,133,133,0,
00539   81,133,133,0,
00540   133,133,133,0,
00541   177,133,133,0,
00542   217,133,133,0,
00543   255,133,133,0,
00544   0,177,133,0,
00545   81,177,133,0,
00546   133,177,133,0,
00547   177,177,133,0,
00548   217,177,133,0,
00549   255,177,133,0,
00550   0,217,133,0,
00551   81,217,133,0,
00552   133,217,133,0,
00553   177,217,133,0,
00554   217,217,133,0,
00555   255,217,133,0,
00556   0,255,133,0,
00557   81,255,133,0,
00558   133,255,133,0,
00559   177,255,133,0,
00560   217,255,133,0,
00561   255,255,133,0,
00562   0,0,177,0,
00563   81,0,177,0,
00564   133,0,177,0,
00565   177,0,177,0,
00566   217,0,177,0,
00567   255,0,177,0,
00568   0,81,177,0,
00569   81,81,177,0,
00570   133,81,177,0,
00571   177,81,177,0,
00572   217,81,177,0,
00573   255,81,177,0,
00574   0,133,177,0,
00575   81,133,177,0,
00576   133,133,177,0,
00577   177,133,177,0,
00578   217,133,177,0,
00579   255,133,177,0,
00580   0,177,177,0,
00581   81,177,177,0,
00582   133,177,177,0,
00583   177,177,177,0,
00584   217,177,177,0,
00585   255,177,177,0,
00586   0,217,177,0,
00587   81,217,177,0,
00588   133,217,177,0,
00589   177,217,177,0,
00590   217,217,177,0,
00591   255,217,177,0,
00592   0,255,177,0,
00593   81,255,177,0,
00594   133,255,177,0,
00595   177,255,177,0,
00596   217,255,177,0,
00597   255,255,177,0,
00598   0,0,217,0,
00599   81,0,217,0,
00600   133,0,217,0,
00601   177,0,217,0,
00602   217,0,217,0,
00603   255,0,217,0,
00604   0,81,217,0,
00605   81,81,217,0,
00606   133,81,217,0,
00607   177,81,217,0,
00608   217,81,217,0,
00609   255,81,217,0,
00610   0,133,217,0,
00611   81,133,217,0,
00612   133,133,217,0,
00613   177,133,217,0,
00614   217,133,217,0,
00615   255,133,217,0,
00616   0,177,217,0,
00617   81,177,217,0,
00618   133,177,217,0,
00619   177,177,217,0,
00620   217,177,217,0,
00621   255,177,217,0,
00622   0,217,217,0,
00623   81,217,217,0,
00624   133,217,217,0,
00625   177,217,217,0,
00626   217,217,217,0,
00627   255,217,217,0,
00628   0,255,217,0,
00629   81,255,217,0,
00630   133,255,217,0,
00631   177,255,217,0,
00632   217,255,217,0,
00633   255,255,217,0,
00634   0,0,255,0,
00635   81,0,255,0,
00636   133,0,255,0,
00637   177,0,255,0,
00638   217,0,255,0,
00639   255,0,255,0,
00640   0,81,255,0,
00641   81,81,255,0,
00642   133,81,255,0,
00643   177,81,255,0,
00644   217,81,255,0,
00645   255,81,255,0,
00646   0,133,255,0,
00647   81,133,255,0,
00648   133,133,255,0,
00649   177,133,255,0,
00650   217,133,255,0,
00651   255,133,255,0,
00652   0,177,255,0,
00653   81,177,255,0,
00654   133,177,255,0,
00655   177,177,255,0,
00656   217,177,255,0,
00657   255,177,255,0,
00658   0,217,255,0,
00659   81,217,255,0,
00660   133,217,255,0,
00661   177,217,255,0,
00662   217,217,255,0,
00663   255,217,255,0,
00664   0,255,255,0,
00665   81,255,255,0,
00666   133,255,255,0,
00667   177,255,255,0,
00668   217,255,255,0,
00669   196,196,196,0,
00670   199,199,199,0,
00671   202,202,202,0,
00672   205,205,205,0,
00673   208,208,208,0,
00674   211,211,211,0,
00675   214,214,214,0,
00676   217,217,217,0,
00677   220,220,220,0,
00678   223,223,223,0,
00679   226,226,226,0,
00680   229,229,229,0,
00681   232,232,232,0,
00682   235,235,235,0,
00683   238,238,238,0,
00684   241,241,241,0,
00685   244,244,244,0,
00686   247,247,247,0,
00687   250,250,250,0,
00688   253,253,253,0,
00689   155,207,207,0,
00690   255,251,240,0,
00691   160,160,164,0,
00692   128,128,128,0,
00693   255,0,0,0,
00694   0,255,0,0,
00695   255,255,0,0,
00696   0,0,255,0,
00697   255,0,255,0,
00698   0,255,255,0,
00699   255,255,255,0,
00700 };
00701 
00702 const PLPixel32* PLFilterQuantize::GetDefaultPalette ()
00703 {
00704   return (PLPixel32*)DefaultPalette;
00705 }
00706 
00707 void PLFilterQuantize::genDefaultPalette (PLBmp * pBmpDest) const
00708 {
00709   PLPixel32 * pPal = pBmpDest->GetPalette();
00710   memcpy (pPal, DefaultPalette, 256*4);
00711 }
00712 
00713 // Adds a RGB Color into the color histogram.
00714 void PLFilterQuantize::addColor(PLPixel32 col, PLULONG count) const
00715 {
00716   HISTONODE * pNode;
00717 
00718   PLULONG index = getShiftedColorTableIndex(col);
00719   count = min (count, (PLULONG)0xFFFFL);
00720 
00721   pNode = m_ppHisto[index];
00722   if(!pNode)  // new color
00723   {
00724     pNode = m_ppHisto[index] = new HISTONODE;
00725     pNode->index = -1;
00726     pNode->count = count;
00727   }
00728   else
00729   {
00730     PLULONG NewCount;
00731     NewCount = pNode->count;
00732     NewCount += count;
00733     pNode->count = min (NewCount, (PLULONG)0xFFFFL);
00734   }
00735 }
00736 
00737 // make a 1x1x1 box at index with color rgb count c
00738 void PLFilterQuantize::makeBox(PLPixel32 col, int i, PLULONG c) const
00739 {
00740   m_pQuBoxes[i].Corner0 = col;
00741   m_pQuBoxes[i].Corner1 = col;
00742   m_pQuBoxes[i].count = c;
00743 }
00744 
00745 int PLFilterQuantize::getColorTableIndex (PLPixel32 col) const
00746 {
00747   int b = col.GetB ();
00748   int g = col.GetG ();
00749   int r = col.GetR ();
00750   return (b | g << 5 | r << 10);
00751 }
00752 
00753 int PLFilterQuantize::getShiftedColorTableIndex (PLPixel32 col) const
00754 {
00755   int b = col.GetB ()>>3;
00756   int g = col.GetG ()>>3;
00757   int r = col.GetR ()>>3;
00758   return (b | g << 5 | r << 10);
00759 }
00760 
00761 void PLFilterQuantize::ditherDestBmp(PLBmp * pBmpSource, PLBmp * pBmpDest) const
00762 {
00763 
00764   PLBYTE ** ppSrcLines = pBmpSource->GetLineArray();
00765   PLBYTE ** ppDestLines = pBmpDest->GetLineArray();
00766 
00767   int w = pBmpSource->GetWidth();
00768   int h = pBmpSource->GetHeight();
00769 
00770   // FS error accumulators.
00771   double * pOddErrors = NULL;
00772   double * pEvenErrors = NULL;
00773   double * pCurErrors = NULL;
00774   double * pNextErrors = NULL;
00775 
00776   // FS: current pixel as float values
00777   double r,g,b;
00778 
00779   if (m_DitherType == PLDTH_FS)
00780   {
00781     // Get memory for errors
00782     pOddErrors = new double[(w + 2) * 6];
00783     pEvenErrors = &pOddErrors[(w + 2) * 3];
00784     memset(pOddErrors, 0, (w + 2) * 6 * sizeof(double));
00785   }
00786 
00787   // Loop row by row, col by col, and of course dither...
00788   int y;
00789   int i;
00790   int SrcInc, DestInc;
00791   for (y=0; y<h; y++)
00792   {
00793     PLBYTE * pSrcLine = ppSrcLines[y];
00794     PLBYTE * pDestLine = ppDestLines[y];
00795     if (m_DitherType == PLDTH_FS)
00796     { // Floyd-Steinberg dithers in different directions in alternate rows.
00797       if (y&1) // odd row
00798       {
00799         // Start at last pixel in row.
00800         pSrcLine += w*4-4;
00801         pDestLine += w-1;
00802         SrcInc = -4;
00803         DestInc = -1;
00804 
00805         pCurErrors = pOddErrors + 3;
00806         pNextErrors = pEvenErrors + (w * 3);
00807       }
00808       else // even row
00809       {
00810         SrcInc = 4;
00811         DestInc = 1;
00812 
00813         pCurErrors = pEvenErrors + 3;
00814         pNextErrors = pOddErrors + (w * 3);
00815       }
00816 
00817       // Initialize the error constants for the first part of the row
00818       pNextErrors[0] = 0;
00819       pNextErrors[1] = 0;
00820       pNextErrors[2] = 0;
00821     }
00822     else
00823     {
00824       SrcInc = 4;
00825       DestInc = 1;
00826     }
00827 
00828     // go through the scanline...
00829     i = w;
00830     while(i--)
00831     {
00832       // Get RGB Values...
00833       PLPixel32 pixel = *(PLPixel32 *)pSrcLine;
00834       pSrcLine += SrcInc;
00835 
00836       // Now dither...
00837       switch (m_DitherType)
00838       {
00839 /*        case PLDTH_JITTER:
00840           jitterPixel( i, y, &pixel);
00841           break;
00842 */
00843         case PLDTH_ORDERED:
00844           ditherPixelOrdered (i, y, &pixel);
00845           break;
00846         case PLDTH_FS:
00847           r = pixel.GetR ();
00848           g = pixel.GetG ();
00849           b = pixel.GetB ();
00850           ditherPixelFS(&r, &g, &b, pCurErrors);
00851           pixel.Set ((PLBYTE)r, (PLBYTE)g, (PLBYTE)b, 0);
00852           break;
00853       }
00854 
00855       // Now get the best possible paletteindex matching the RGB Vals.
00856       PLBYTE index = getNeighbor (pixel, pBmpDest->GetPalette());
00857 
00858       // FS dithering now calculates the error we've introduced by
00859       // approximating.
00860       if (m_DitherType == PLDTH_FS)
00861       {
00862         PLPixel32 * pPal = pBmpDest->GetPalette();
00863         double PalR = (double)(pPal[index].GetR ());
00864         double PalG = (double)(pPal[index].GetG ());
00865         double PalB = (double)(pPal[index].GetB ());
00866 
00867         double error;
00868 
00869         // Red component
00870         error = (r - PalR) / 16.0;
00871         pNextErrors[-3] = error;
00872         pNextErrors[+3] += error*3;
00873         pNextErrors[+0] += error*5;
00874         pCurErrors[+3] += error*7;
00875 
00876         // Green component
00877         error = (g - PalG) / 16.0;
00878         pNextErrors[-2]  = error;
00879         pNextErrors[+4] += error*3;
00880         pNextErrors[+1] += error*5;
00881         pCurErrors[+4] += error*7;
00882 
00883         // Blue component
00884         error = (b - PalB) / 16.0;
00885         pNextErrors[-1]  = error;
00886         pNextErrors[+5] += error*3;
00887         pNextErrors[+2] += error*5;
00888         pCurErrors[+5] += error*7;
00889 
00890         pNextErrors -= 3;
00891         pCurErrors += 3;
00892       }
00893 
00894       // Set the pixel in the destination bitmap
00895       *pDestLine = (PLBYTE)index;
00896       pDestLine += DestInc;
00897     }
00898 
00899   }
00900 
00901   // clean up.
00902   if (m_DitherType == PLDTH_FS )
00903     delete [] pOddErrors;
00904 
00905 }
00906 
00907 
00908 void PLFilterQuantize::jitterPixel (int i, int y, PLPixel32 * pPixel) const
00909 {
00910 }
00911 
00912 void PLFilterQuantize::ditherPixelOrdered (int x, int y, PLPixel32 * pPixel) const
00913 {
00914   PLBYTE * pPx = (PLBYTE *)pPixel;
00915   ditherCompOrdered (x, y, &pPx[PL_RGBA_RED]);
00916   ditherCompOrdered (x, y, &pPx[PL_RGBA_GREEN]);
00917   ditherCompOrdered (x, y, &pPx[PL_RGBA_BLUE]);
00918 
00919 }
00920 
00921 void PLFilterQuantize::ditherCompOrdered (int x, int y, PLBYTE * pComp) const
00922 {
00923   const int DitherLUT[4][4] = { {-7, 1, -5, 3}, {5, -3, 7, -1}, {-4, 4, -6, 2}, {8, 0, 6, -2} };
00924 
00925   int Comp = *pComp;
00926   Comp += DitherLUT [x&3][y&3]<<1;
00927   Comp = clip (Comp);
00928   *pComp = (PLBYTE)Comp;
00929 }
00930 
00931 void PLFilterQuantize::ditherPixelFS (double * pR, double * pG, double * pB, double * pCurErrors) const
00932 {
00933   ditherCompFS (pR, pCurErrors[0]);
00934   ditherCompFS (pG, pCurErrors[1]);
00935   ditherCompFS (pB, pCurErrors[2]);
00936 }
00937 
00938 void PLFilterQuantize::ditherCompFS (double * pComp, double Error) const
00939 {
00940   *pComp += Error;
00941   if (*pComp > 255) *pComp = 255;
00942   if (*pComp < 0) *pComp = 0;
00943 }
00944 
00945 // Returns nearest color to the color passed in that's present
00946 // in the palette as a palette index.
00947 PLBYTE PLFilterQuantize::getNeighbor (PLPixel32 Color, PLPixel32 * pPal) const
00948 {
00949   HISTONODE * pNode;
00950 
00951 
00952   int TableIndex = getShiftedColorTableIndex (Color);
00953 
00954   pNode = m_ppHisto[TableIndex];
00955 
00956   if (!pNode)
00957   {
00958     m_ppHisto[TableIndex] = new HISTONODE;
00959     pNode = m_ppHisto[TableIndex];
00960     pNode->count = 0;
00961     pNode->index = -1;
00962   }
00963 
00964   int PalIndex = pNode->index;
00965   if( PalIndex == -1)
00966   {
00967     pNode->index = 0;
00968 
00969     PLPixel32 BestColor = pPal[0];
00970     int MinDist = colorDist (BestColor, Color);
00971 
00972     int c;
00973     for (c = 1; c<256; c++)
00974     {
00975       int Dist = colorDist (pPal[c], Color);
00976       if (Dist < MinDist)
00977       {
00978         pNode->index = c;
00979         MinDist = Dist;
00980       }
00981     }
00982     PalIndex = pNode->index;
00983   }
00984   return PalIndex;
00985 }
00986 
00987 int PLFilterQuantize::colorDist (PLPixel32 c0, PLPixel32 c1) const
00988 {
00989   int dr = c0.GetR ()-c1.GetR ();
00990   int dg = c0.GetG ()-c1.GetG ();
00991   int db = c0.GetB ()-c1.GetB ();
00992   return dr*dr+dg*dg+db*db;
00993 }
00994 
00995 /*
00996 /--------------------------------------------------------------------
00997 |
00998 |      $Log: plfilterquantize.cpp,v $
00999 |      Revision 1.1  2004/05/21 21:02:53  maxx
01000 |      Initial Version of vuVolume, moderatly changed to make it compile on my windows and linux machine.
01001 |
01002 |      Revision 1.4  2003/01/25 02:54:42  mspindle
01003 |      *** empty log message ***
01004 |
01005 |      Revision 1.3  2003/01/07 16:14:59  sbergner
01006 |      *** empty log message ***
01007 |
01008 |      Revision 1.2  2002/11/20 09:04:54  sbergner
01009 |      modified syntax for compliance with gcc 3.0.4 (onyx)
01010 |
01011 |      Revision 1.1  2002/11/13 01:59:48  mspindle
01012 |      *** empty log message ***
01013 |
01014 |      Revision 1.5  2001/10/21 17:12:40  uzadow
01015 |      Added PSD decoder beta, removed BPPWanted from all decoders, added PLFilterPixel.
01016 |
01017 |      Revision 1.4  2001/10/16 17:12:27  uzadow
01018 |      Added support for resolution information (Luca Piergentili)
01019 |
01020 |      Revision 1.3  2001/10/06 22:03:26  uzadow
01021 |      Added PL prefix to basic data types.
01022 |
01023 |      Revision 1.2  2001/10/06 15:32:22  uzadow
01024 |      Removed types LPBYTE, DWORD, UCHAR, VOID and INT from the code.
01025 |
01026 |      Revision 1.1  2001/09/16 19:03:23  uzadow
01027 |      Added global name prefix PL, changed most filenames.
01028 |
01029 |      Revision 1.7  2001/09/15 20:39:57  uzadow
01030 |      Added Quantization to user-defined palette (Andreas Köpf)
01031 |
01032 |      Revision 1.6  2001/02/04 14:31:52  uzadow
01033 |      Member initialization list cleanup (Erik Hoffmann).
01034 |
01035 |      Revision 1.5  2001/01/15 15:05:31  uzadow
01036 |      Added PLBmp::ApplyFilter() and PLBmp::CreateFilteredCopy()
01037 |
01038 |      Revision 1.4  2000/12/18 22:42:53  uzadow
01039 |      Replaced RGBAPIXEL with PLPixel32.
01040 |
01041 |      Revision 1.3  2000/12/09 12:16:26  uzadow
01042 |      Fixed several memory leaks.
01043 |
01044 |      Revision 1.2  2000/10/23 17:45:03  jmbuena
01045 |      Linux compatibility changes
01046 |
01047 |      Revision 1.1  2000/09/26 12:14:49  Administrator
01048 |      Refactored quantization.
01049 |
01050 |
01051 |
01052 \--------------------------------------------------------------------
01053 */

Generated on Wed Dec 15 21:20:30 2004 for vuVolume by  doxygen 1.3.9.1