home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / rexx / library2 / gbmrexx / gbm / gbmhist.c < prev    next >
C/C++ Source or Header  |  1993-02-11  |  5KB  |  199 lines
  1. /*
  2.  
  3. GBMHIST.C  Histogram/Frequency-of-use method of colour reduction
  4.  
  5. */
  6.  
  7. /*...sincludes:0:*/
  8. #include <stdio.h>
  9. #include <stddef.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <memory.h>
  13. #include "standard.h"
  14. #include "gbm.h"
  15.  
  16. /*...vgbm\46\h:0:*/
  17. /*...e*/
  18.  
  19. /*...sgbm_hist:0:*/
  20. /*
  21. Determine the n_cols_wanted most frequently used colours from 24 bit data.
  22. Can be a problem since potentially 256*256*256 possible unique colours.
  23. Initially 8 bits green, 8 bits red, and 8 bits blue significant.
  24. When number of colours exceeds a limit number of bits of blue reduced by 1.
  25. Next time red, next time green, ...
  26. Sort most n_cols_wanted most frequently used colour in order of use.
  27. Put these in the returned palette.
  28. Map colours from n_cols_wanted exactly to colours in palette.
  29. For other colours, map them to the closest in the palette.
  30. */
  31.  
  32. #define    N_COLS    2049
  33. #define    N_HASH    5191
  34. #define    HASH(r,g,b)    (word) ( (((r)+(g))*((g)+(b))*((b)+(r))) % N_HASH )
  35.  
  36. typedef struct { byte b, g, r; dword freq; byte nearest; } FREQ;
  37.  
  38. BOOLEAN gbm_hist(
  39.     GBM *gbm, byte *data24,
  40.     GBMRGB gbmrgb [],
  41.     byte *data8,
  42.     int n_cols_wanted,
  43.     byte rm, byte gm, byte bm
  44.     )
  45.     {
  46.     int stride24 = ((gbm -> w * 3 + 3) & ~3);
  47.     int step24 = stride24 - gbm -> w * 3;
  48.     int stride8 = ((gbm -> w + 3) & ~3);
  49.     int step8 = stride8 - gbm -> w;
  50.     FREQ *f;
  51.     word *ht;
  52.     int i, x, y, n_cols;
  53.  
  54.     /* Frequency table */
  55.  
  56.     if ( (f = malloc(N_COLS * sizeof(FREQ))) == NULL )
  57.         return ( FALSE );
  58.  
  59.     /* Hash table, holding 0xffff for unused, index into f if used */
  60.  
  61.     if ( (ht = malloc(N_HASH * sizeof(word))) == NULL )
  62.         {
  63.         free(f);
  64.         return ( FALSE );
  65.         }
  66.  
  67.     for ( ;; )
  68.         {
  69.         byte *p = data24;
  70.         BOOLEAN notfull = TRUE;
  71.  
  72.         n_cols = 0;
  73.         memset(ht, 0xff, N_HASH * sizeof(word));
  74.         for ( y = 0; notfull && y < gbm -> h; y++, p += step24 )
  75.             for ( x = 0; notfull && x < gbm -> w; x++ )
  76. /*...sanalyse pixel:32:*/
  77. {
  78. byte b = (byte) (*p++ & bm);
  79. byte g = (byte) (*p++ & gm);
  80. byte r = (byte) (*p++ & rm);
  81. word hc = HASH(r,g,b);
  82. word inx;
  83.  
  84. for ( ;; )
  85.     {
  86.     inx = ht [hc];
  87.     if ( inx == 0xffff || (f [inx].r == r && f [inx].g == g && f [inx].b == b) )
  88.         break;
  89.     if ( ++hc == N_HASH ) hc = 0;
  90.     }
  91.  
  92. /* Note: loop will always be broken out of */
  93. /* We don't allow ht to fill up above half full */
  94.  
  95. if ( inx == 0xffff )
  96.     /* Not found in hash table */
  97.     {
  98.     f [n_cols].freq = (dword) 1;
  99.     f [n_cols].b    = b;
  100.     f [n_cols].g    = g;
  101.     f [n_cols].r    = r;
  102.     ht [hc] = n_cols;
  103.     if ( ++n_cols == N_COLS )
  104.         notfull = FALSE;
  105.     }
  106. else
  107.     /* Found in hash table */
  108.     /* update index inx */
  109.     f [inx].freq++;
  110. }
  111. /*...e*/
  112.  
  113.         if ( notfull )
  114.             break;
  115.  
  116.         if ( gm > rm )
  117.             gm <<= 1;
  118.         else if ( rm > bm )
  119.             rm <<= 1;
  120.         else
  121.             bm <<= 1;
  122.         }
  123.  
  124.     /* Above loop will always be exited as if masks get rough
  125.        enough, ultimately number of unique colours < N_COLS */
  126.  
  127.     /* Now find the n_cols_wanted most frequently used ones */
  128.  
  129.     for ( i = 0; i < n_cols_wanted && i < n_cols; i++ )
  130.         {
  131.         int j, max_j;
  132.         dword max_freq = 0;
  133.  
  134.         for ( j = 0; j < n_cols; j++ )
  135.             if ( f [j].freq > max_freq )
  136.                 {
  137.                 max_j    = j;
  138.                 max_freq = f [j].freq;
  139.                 }
  140.         f [max_j].nearest = (byte) i;
  141.         f [max_j].freq = (dword) 0; /* Prevent later use of f [max_j] */
  142.         gbmrgb [i].b = f [max_j].b;
  143.         gbmrgb [i].g = f [max_j].g;
  144.         gbmrgb [i].r = f [max_j].r;
  145.         }
  146.  
  147.     /* For the rest, find the closest one in the first n_cols_wanted */
  148.  
  149.     for ( i = 0; i < n_cols; i++ )
  150.         if ( f [i].freq != (dword) 0 )
  151.             {
  152.             int j, min_j;
  153.             int min_dist = 3*256*256;
  154.  
  155.             for ( j = 0; j < n_cols_wanted; j++ )
  156.                 {
  157.                 int db = (int) f [i].b - (int) gbmrgb [j].b;
  158.                 int dg = (int) f [i].g - (int) gbmrgb [j].g;
  159.                 int dr = (int) f [i].r - (int) gbmrgb [j].r;
  160.                 int dist = dr*dr + dg*dg + db*db;
  161.  
  162.                 if ( dist < min_dist )
  163.                     {
  164.                     min_dist = dist;
  165.                     min_j    = j;
  166.                     }
  167.                 }
  168.             f [i].nearest = (byte) min_j;
  169.             }
  170.  
  171.     /* Now transform the image data */
  172.  
  173.     for ( y = 0; y < gbm -> h; y++, data24 += step24, data8 += step8 )
  174.         for ( x = 0; x < gbm -> w; x++ )
  175.             {
  176.             byte b = (*data24++ & bm);
  177.             byte g = (*data24++ & gm);
  178.             byte r = (*data24++ & rm);
  179.             word hc = HASH(r,g,b);
  180.             word inx;
  181.  
  182.             for ( ;; )
  183.                 {
  184.                 inx = ht [hc];
  185.                 if ( f [inx].r == r && f [inx].g == g && f [inx].b == b )
  186.                     break;
  187.                 if ( ++hc == N_HASH ) hc = 0;
  188.                 }
  189.  
  190.             *data8++ = f [inx].nearest;
  191.             }
  192.  
  193.     free(ht);
  194.     free(f);
  195.  
  196.     return ( TRUE );
  197.     }
  198. /*...e*/
  199.