Palette quantization for pixel mixing

Question

For graphic modes using a hardware palette, an illusion of more colors can be achieved by quickly switching between two images (I don't know about any generic name for this).

What is some algorithm to calculate an optimal (or semi-optimal) palette from an ordinary full color image? Either the two target images share the same palette or have their own. Algorithms for both cases are of interest (if they are fundamentally different).

An example: Let's say I have a random full color PNG image with thousands of colors (8 bits per channel, full opacity) and want to create two GIF images (not animated) with 256 colors each. And let's say I switch between those GIF images every frame (at a frame rate of 60Hz) so the result appears as a blend between the two images. The question is: How do I calculate an optimal palette to be shared between the two GIF files? Or alternatively two different palettes, one for each file? (Both cases are of interest).

Update:

Just to create an example of what I want to do I forced a result by evolving a suitable palette using random mutation. To make it easy to visualize in 2D I used an image with the blue channel removed. This is what the original looks like.

The color distribution looks like this. Apart from some dark (almost black) grays used up to 90 times and some bright yellows used around 30 times the usage distribution is very even among the used colors.

This is the 16 color palette I came up with. I don't know how far it is from an optimal palette, but it appears to be close.

Blending the colors from two images yields a larger set of colors. How large depends on the allowed distance between the colors (the larger the distance the more visible the flickering). This has a maximum distance of 100.

These blended colors cover the colorspace quite well, as seen in this plot which shows the distance from each original color to the nearest (blended) palette color. A few fringe colors have a distance of up to 40. But almost all colors are in less than half of that distance.

This is the result then converting two images to use this palette. First the two 16 color images, then the blended result (how it would ideally look without any visible flickering at all).

It's not that easy to spot the differences (depending on the monitor you have of course). So here are two images of just the differences. The left one has values proportional to the actual differences and the right one has them exaggerated for it to become more visual in which areas to biggest differences occur. (Obviously there will be much bigger differences then operating in 3D colorspace.)

I understand that the (yet hypothetical) result can be improved by also applying dithering. And I understand that the visual perception of distances between colors is not constant throughout the colorspace. Not to mention all those little things that are hardware dependent. But first things first...

user_2521214 · Answer

well 2 images sounds reasonable as most retro HW used 50 or 60 Hz refresh rate and switching 2 frames will give 25 or 30 Hz which is still high enough for human sight.

Alternating 2 images bmp0,bmp1 with the same display time for both will blend together to their average:

bmp = (bmp0 + bmp1)/2

Now let bmp0 be a pal0 palette truncated image bmp then:

bmp0 = trunc(bmp,pal0)
bmp1 = trunc(2*bmp - bmp0,pal1)

so both images use just colors from their palette but their average is more closer to original image then each of them...

Here simple C++/VC example using color quantization described in link at the bottom of this answer:

//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include 
#include 
#include 
#pragma hdrstop
#include "win_main.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TMain *Main;
//---------------------------------------------------------------------------
Graphics::TBitmap *bmp0,*bmp1,*bmp,*bmpd;
//---------------------------------------------------------------------------
//--- Palette ---------------------------------------------------------------
//---------------------------------------------------------------------------
const int _pals=64+0*8192;                          // max 8K colors in palette
DWORD pal[_pals];                               // palette 0x00RRGGBB
int pals=0;                                     // colors inside palette
const int rgb_bpc=5;                            // bits per channel (after truncation)
const int rgb_sh=8-rgb_bpc;                     // bits to drop (truncation)
const int rgb_n=1<Width;
    ys=bmp->Height;
    n+=pals;
    // 15bit histogram
    for (x=0;x<32768;x++) { his[x]=0; idx[x]=x; }
    for (                           y=0;yScanLine[y],x=0;x>3)&0x1F)|((cc>>6)&0x3E0)|((cc>>9)&0x7C00);
        if (his[cc]<0xFFFFFFFF) his[cc]++;
        }
    // remove zeroes
     for (x=0,y=0;y<32768;y++)
        {
        his[x]=his[y];
        idx[x]=idx[y];
        if (his[x]) x++;
        } hists=x;
    // sort by hist
    for (i=1;i;)
     for (i=0,x=0,y=1;y> 5)&31;
        r=(cc>>10)&31;
        c0.db[0]=b;
        c0.db[1]=g;
        c0.db[2]=r;
        c0.dd=(c0.dd<<3)&0x00F8F8F8;
        // skip if similar color already in pal[]
        for (a=0,i=0;i=n) { x++; break; }
            }
        }
    }
//---------------------------------------------------------------------------
void  pal_compute_recolor()
    {
    int i,j,x,y,c,r,g,b,rr,gg,bb;
    // test all truncated rgb colors
    for (r=0;r> 8)&255; gg-=g<>16)&255; rr-=r<y){ x=y; j=i; }
            }
        // store it as recolor value
        rgb[r][g][b]=j;
        }
    }
//---------------------------------------------------------------------------
void rgb2chn(int &r,int &g,int &b,DWORD c)
    {
    b= c     &255;
    g=(c>> 8)&255;
    r=(c>>16)&255;
    }
//---------------------------------------------------------------------------
DWORD chn2rgb(int r,int g,int b)
    {
    return b+(g<<8)+(r<<16);
    }
//---------------------------------------------------------------------------
int chn2pal(int r,int g,int b)
    {
    return rgb[r>>rgb_sh][g>>rgb_sh][b>>rgb_sh];
    }
//---------------------------------------------------------------------------
int rgb2pal(DWORD c)
    {
    int r,g,b;
    b= c     &255;
    g=(c>> 8)&255;
    r=(c>>16)&255;
    return rgb[r>>rgb_sh][g>>rgb_sh][b>>rgb_sh];
    }
//---------------------------------------------------------------------------
DWORD pal2rgb(int ix)
    {
    return pal[ix];
    }
//---------------------------------------------------------------------------
void pal_render(Graphics::TBitmap *bmp,int y0)
    {
    int xs,ys,x,y,i,j,c,*p;
    xs=bmp->Width;
    ys=bmp->Height;
    for (c=y0,i=0;(iScanLine[y],j=i,x=0;(xxs) break; }}
    }
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
void compute() // bmp -> bmp0+bmp1 using pal[]
    {
    const int colors=64;
    int i,j,r,g,b,rr,gg,bb,x,y,xs,ys,c;
    int *p,*p0,*p1,*pd;
    int pal0[colors],pal1[colors];
    // allow direct pixel access and resize to coomon size
    xs=bmp->Width;
    ys=bmp->Height;
    bmp->HandleType=bmDIB;
    bmp->PixelFormat=pf32bit;
    bmp0->HandleType=bmDIB;
    bmp0->PixelFormat=pf32bit;
    bmp0->SetSize(xs,ys);
    bmp1->HandleType=bmDIB;
    bmp1->PixelFormat=pf32bit;
    bmp1->SetSize(xs,ys);
    bmpd->PixelFormat=pf32bit;
    bmpd->SetSize(xs,ys);
    // compute palette for bmp0
    pal_clear();
    pal_major(colors,bmp);
    pal_compute_recolor();
    for (i=0;iScanLine[y];
        p0=(int*)bmp0->ScanLine[y];
        p1=(int*)bmp1->ScanLine[y];
        for (x=0;x255) bb=255; if (bb<0) bb=0;
            gg=g+g-gg; if (gg>255) gg=255; if (gg<0) gg=0;
            rr=r+r-rr; if (rr>255) rr=255; if (rr<0) rr=0;
            // copy pixels to bmps
            p0[x]=pal[i];                   // quantized
            p1[x]=chn2rgb(rr,gg,bb);        // true color for now
            }
        }

    // compute palette for bmp1
    pal_clear();
    pal_major(colors,bmp1);
    pal_compute_recolor();
    for (i=0;iScanLine[y];
        for (x=0;xScanLine[y];
        p0=(int*)bmp0->ScanLine[y];
        p1=(int*)bmp1->ScanLine[y];
        pd=(int*)bmpd->ScanLine[y];
        for (x=0;x>1;
            g=(g+gg)>>1;
            b=(b+bb)>>1;
            // diff
            rgb2chn(rr,gg,bb,p[x]);
            i=2;    // scale
            rr=abs(r-rr)<255) rr=255;
            gg=abs(g-gg)<255) gg=255;
            bb=abs(b-bb)<255) bb=255;
            // copy pixels
            p[x]=chn2rgb(r,g,b);
            pd[x]=chn2rgb(rr,gg,bb);
            }
        }
    // render palettes
    for (i=0;iSaveToFile("out_blend.bmp");
    bmp0->SaveToFile("out_bmp0.bmp");
    bmp1->SaveToFile("out_bmp1.bmp");
    bmpd->SaveToFile("out_diff.bmp");
    }
//---------------------------------------------------------------------------
__fastcall TMain::TMain(TComponent* Owner) : TForm(Owner)
    {
    bmp=new Graphics::TBitmap;
    bmp0=new Graphics::TBitmap;
    bmp1=new Graphics::TBitmap;
    bmpd=new Graphics::TBitmap;
    // load jpg into bmp
    TJPEGImage *jpg = new TJPEGImage();
    jpg->LoadFromFile("in.jpg");
    bmp->Assign(jpg);
    delete jpg;
    // resize window
    ClientWidth=bmp->Width<<2;
    ClientHeight=bmp->Height;
    // compute
    compute();
    }
//---------------------------------------------------------------------------
void __fastcall TMain::FormDestroy(TObject *Sender)
    {
    delete bmp;
    delete bmp0;
    delete bmp1;
    delete bmpd;
    }
//---------------------------------------------------------------------------
void __fastcall TMain::tim_redrawTimer(TObject *Sender)
    {
/*
    // alternatin images
    static int cnt=0;
    cnt=(cnt+1)&1;
    if (cnt==0) Canvas->Draw(0,0,bmp0);
    if (cnt==1) Canvas->Draw(0,0,bmp1);
    Canvas->Draw(bmp->Width,0,bmpd);
*/
    // debug view of all images
    int x=0;
    Canvas->Draw(x,0,bmp ); x+=bmp ->Width;
    Canvas->Draw(x,0,bmp0); x+=bmp0->Width;
    Canvas->Draw(x,0,bmp1); x+=bmp1->Width;
    Canvas->Draw(x,0,bmpd); x+=bmpd->Width;

    }
//---------------------------------------------------------------------------

Just ognore the VCL stuff. Function compute will compute the bmp0,bmp1 and their corresponding palettes pal0,pal1. The number of colors is configurable by constant colors.

Here output for 64 colors palette:

original image:

The difference is 4 times exaggerated. Also the 2 used palettes are rendered there the top one is for bmp0 and the other is for bmp1.

Also to avoid flickering you should keep the difference between bmp0 and bmp1 as small as possible.

Palette quantization for pixel mixing

1 Answers