Need help about palette colour quantization : java - Android

Question

I am developing a project on Android, this requires that I filter up to 5 different colors - including the background color (approximate white). I can't use advanced maths algorithms because I don't know too much maths (and I will get lost completely), but with some simple logics algorithms which I derived partly by trial and error, partly logical, I have been able to a result that works up to say 70%. But I need suggestions on how to make it work 100%.

To test the algorithm, I scribbled random words/letters with 4 different colored pens on a plain white (5th color) paper, and wrote some code to decode the colors. So in the code the algorithm ...

• if red pen ink pixel is decoded, pixel is set to digital red
• if blue pen ink pixel is decoded, pixel is set to digital blue
• if green pen ink pixel is decoded, pixel is set to digital green
• if black pen ink pixel is decoded, pixel is set to digital yellow

The black ink pixel is set to digital yellow (not black, because black was hard to distinguish from ink black visually).

My code is below, but first here is one of the best results I had. As you can see there is an overlap at the fringes between black (represented by digital yellow) and red (represented by digital red). Like I said my code was a partly logic partly trial and error.

My first question is how can I improve this algorithm so as to decode/filter the colors perfectly (I chose this method because I get lost very quickly with very complex maths)?

Secondly how can I make it work for different shades of light (white light, yellow light...)?

EDIT: upon further comments and discussions I've realised that the help i need is palette color quantization Adroid java code example , thanks

if(  (Blue > Green) &&(Red > Blue) && (Red - Green) > 25 )
    copyOfBM.setPixel(x,  y, Color.RED); //red
else if(  (Blue > Red) && ( (Blue > Green)) )
    copyOfBM.setPixel(x,  y, Color.BLUE);
else if( (Green >= 82) && ((Green - Blue) >= 12)  && 
  ((DecodeLuminaceColor( x, y, copyOfBM )>= 82 ) && 
   (DecodeLuminaceColor( x, y, copyOfBM )< 124))  )
    copyOfBM.setPixel(x,  y, Color.GREEN);
else if( ((Red - Green) > 6) &&((Red - Green) < 17) &&((Green - Blue) < 8) 
  && (DecodeLuminaceColor( x, y, copyOfBM )< 118 ) )
    copyOfBM.setPixel(x,  y, Color.YELLOW);



void DecodeLuminaceColor( int _x, int _y, Bitmap cBM  ){
    float avrLum = 0;
    Red = 0; Green = 0; Blue = 0;  //Color.green(green_encoded_color);

    red_encoded_color = cBM.getPixel(_x, _y);
    green_encoded_color = cBM.getPixel(_x, _y);
    blue_encoded_color  = cBM.getPixel(_x, _y);

    Red   = ( (red_encoded_color >> 16) & 0xff );
    Green = ( (green_encoded_color >> 8) & 0xff);
    Blue  = ( (blue_encoded_color >> 0) & 0xff );
}

Answer 1

I would use HSV color space

it is better to detect colors (more human perception like) that should help a lot. You can also use HSV Histogram to detect how many distinct colors you have.

If you still want RGB than compare differently

You have pen color0=(r0,g0,b0) and pixel color=(r,g,b) so compute distance between them:

d=((r-r0)*(r-r0))+((g-g0)*(g-g0))+((b-b0)*(b-b0))

No need for sqrt. Now you just compute d for every color you have (pens) and choose the smallest d ... You can also use less precise:

d=abs(r-r0)+abs(g-g0)+abs(b-b0)

If you do not know the colors prior this and do not want to use histograms

1. form a (re)color table (set of distinct visible colors you will set to each found new pen)
2. create empty list of found colors
3. process all pixels of input image
4. compute distance d to all found colors in a list
5. if d is smaller then some treshold constant the pixels belong to that color in found colors list. Else add it as new found color.
6. recolor pixel with color from recolor table.

This will eliminate the shading and anti-aliasing color distortions. You can also ignore the recolor table and use the color from the found colors list. This process is form of Color Quantization.

[Edit1] After using HSV color and recoloring to found color list (no histogram) I got this result:

This shows that your image has not the same lighting conditions (not a render but real photo). So Ilumination normalization should improve this even more. Also I use 2 tresholds one for gray scales and one for colors ... to distinguish the two ... Also you can detect background color by:

• pixel count (should be much bigger then the color of text)
• dispersion along the image (should cover large area with relatively high density uniformly dispersed ... Text is localized)

Here C++/VCL source for this:

backbuffer bmp; // source and target image
struct _color { DWORD rgb; int h,s,v; };    // color entry in (re)color table
_color ld_rgb(DWORD rgb)                    // just RGB -> HSV conversion
    {
    const int _b=0;
    const int _g=1;
    const int _r=2;
    const int _a=3;
    union { DWORD dd; BYTE db[4]; } c;
    double r,g,b,min,max,del,h,s,v,dr,dg,db;
    c.dd=rgb;
    r=c.db[_r]; r/=255.0;
    g=c.db[_g]; g/=255.0;
    b=c.db[_b]; b/=255.0;
    min=r; if (min>g) min=g; if(min>b) min=b;
    max=r; if (max<g) max=g; if(max<b) max=b;
    del=max-min;
    v=max;
    if (del<=0.1) { h=0; s=0; } // grayscale
    else{
        s=del/max;
        dr=(((max-r)/6.0)+(del/2.0))/del;
        dg=(((max-g)/6.0)+(del/2.0))/del;
        db=(((max-b)/6.0)+(del/2.0))/del;
        if      (fabs(r-max)<1e-10) h=db-dg;
        else if (fabs(g-max)<1e-10) h=(1.0/3.0)+dr-db;
        else if (fabs(b-max)<1e-10) h=(2.0/3.0)+dg-dr;
        if (h<0.0) h+=1.0;
        if (h>1.0) h-=1.0;
        }
    _color ccc;
    ccc.rgb=rgb;
    ccc.h=255.0*h;
    ccc.s=255.0*s;
    ccc.v=255.0*v;
    return ccc;
    }
void recolor() // this is the recolor you want
    {
    // load input jpg file to bmp image
    TJPEGImage *jpg=new TJPEGImage();
    jpg->LoadFromFile("in.jpg");
    bmp.bmp->Assign(jpg);
    bmp.resize(bmp.bmp->Width,bmp.bmp->Height);
    delete jpg;

    // recolor bmp
    int i,x,y,d;
    _color c0,c1;
    List<_color> col;                   // color list
    col.num=0;                          // clear colro list
    for (y=0;y<bmp.ys;y++)              // process all pixels
     for (x=0;x<bmp.xs;x++)
        {
        c0=ld_rgb(bmp.pyx[y][x]);       // pixel color -> hsv

        if ((c0.h==0)&&(c0.s==0))       // compare it to found colors (grayscales)
         for (i=0;i<col.num;i++)
            {
//          i=-1; c1.rgb=0x00202020; break;
            c1=col[i];
            if ((c1.h!=0)||(c1.s!=0)) continue;
            d=abs(c1.v-c0.v);
            if (d<32) { i=-1; break; }  // match found ?
            }
        else                            // compare it to found colors
         for (i=0;i<col.num;i++)
            {
//          i=-1; c1.rgb=0x0000FF00; break;
            c1=col[i];
            if ((c1.h==0)&&(c1.s==0)) continue;
            d=(abs(c1.h-c0.h))+(abs(c1.s-c0.s));
            if (d<50) { i=-1; break; }  // match found ?
            }
        if (i>=0) { c1=c0; col.add(c1); }   // if not add new color
        bmp.pyx[y][x]=c1.rgb;               // recolor;
        }
    bmp.bmp->Canvas->Brush->Style=bsClear;
    bmp.bmp->Canvas->Font->Color=0x00802040;
    bmp.bmp->Canvas->TextOutA(5,0,"Found colors: "+AnsiString(col.num));
    bmp.bmp->Canvas->Brush->Style=bsSolid;
    for (d=16,i=0;i<col.num;i++)
     for (y=d;y<=d+d;y++)
      for (x=d*i+1;(x<d*i+d)&&(x<bmp.xs);x++)
       bmp.pyx[y][x]=col[i].rgb;
    }

• List<T> l; is dynamic array like std::vector<T> ... represents T l[l.num];
• backbuffer bmp; is mine image class ... bmp.bmp Holds GDI bitmap and bmp.xs,bmp.ys is the resolution
• col holds found colors ...

[Edit1] bi-cubic Illumination normalization

I recently was rewriting my DIP lib upgrading mine illumination normalization so I give a shot at your input image (as one of many test images) and here the result (with forced (detected) empty space recolor):

As you can see the middle red-ish lighting spot is gone. You can try your algo on this so you know if applying illumination normalization helps before encoding it (it is a bit complicated if done properly). This one is done like this:

1. create grid (table) for your image

   each cell contains average color and cumulative delta (noise) of the cell area. Also single flag telling if cell is paper or ink. Cell size should be around <0.5 - 1.5> of min detail size (like letter or pen width ...)

2. set all cells with high delta as ink the rest as paper

3. compute average color of all paper cells combined

4. each paper cell neighboring ink cell

   set as ink if its average color is too far from the global average paper color. Be carefull not to take those newly ink set cells as neighbor condition for this step. (use temp flag or different flag bit and restore after this is done...

5. find 16 control points uniformly dispersed along image (use only paper cells)

   they should be around coordinates 0%,33%,66%,100% of image resolution So the bi-cubic interpolation is valid.

6. for each pixel

   bi-cubically compute the cell color and call it c0 Then apply normalization to pixel (in RGB space!!!):

   • pixel+=global_avg_color-c0;

   This will equalize the paper color along the whole image to very close match to global_avg_color. Leaving the non paper details undistorted.

7. optionally recolor all paper cells area with global_avg_color

   This is not necessary but it will eliminate much of the noise from background. Like paper texture ...