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...

What hardware/device are you thinking of switching palettes on rapidly? — Mark Setchell, Nov 14 '20 at 11:43
@MarkSetchell Atari ST to begin with. But it's not so much about specific hardware, more about converting images to already existing graphics formats (with already existing viewers). Also it's not (only) about switching the palette, but switching the while image. I'm NOT asking about creating palettes for multi palette formats (such as SHAM, Spectrum512 or MPP). — Fabel, Nov 14 '20 at 13:30
@Fabel see [Effective gif/image color quantization?](https://stackoverflow.com/a/30265253/2521214) that can give you palette ... switching between palettes (exploiting sprite HW) is similar to [dithering](https://stackoverflow.com/a/36820654/2521214) but instead of bleeding missing colors to neighboring pixels you copy them to different sprite/image that is switching in the same place ...the idea is that the relative visual difference between alternating pixels is not big. All this is theory as I do not have such HW nor had one I am more used to architectures with SW rendering like ZX — Spektre, Nov 14 '20 at 16:17
maybe would be a good idea to post a sample input image and specifics for the target platform HW ... like bit depth, palette limitations, speed of switching, max/preferred overlapped/alternating sprites at single position, switching speed ... Also does each sprite has own palette or not? Do you want to alternate sprites uniformly or want to also PWM like tune the output by modulating the times each sprite is shown... and with what granularity your time is measured or switching can be done with ... — Spektre, Nov 14 '20 at 16:20
@Spektre You're basically saying that a palette that is optimal for one single image (such as for GIF) is also optimal for blending two images? I'm not so sure about that since you could potentially eliminate some colors that can be created by blending two other. I can also imagine how to create the two images once I have an optimal palette, I don't consider that the main problem. So my question doesn't really apply then you only have a limited set of colors to begin with (such as for ZX). — Fabel, Nov 14 '20 at 16:35
@Fabel not exactly optimal palette will significantly reduce the avg difference between palette colors and real color needed... Dithering uses specific fixed colors containing few shades of basic colors so you should combine the two together ... — Spektre, Nov 14 '20 at 16:40
Maybe consider adding the `image-processing` tag to your question to attract some top contributors. — Mark Setchell, Nov 14 '20 at 17:01
@Spektre I updated the question with a more verbose and visual example. As you can see the most used colors (corresponding to the high points of the histogram in your code) are not present in the palette. I suspect that a palette that is optimal for my use case could be very good then used with dithering as well. However I don't expect a very fast algorithm for this (but at least magnitudes faster than evolution through random mutation). — Fabel, Nov 16 '20 at 05:03
@Fabel algo will greatly differ from the limits I requested and you still did not specify... so can we assume: 16 color palette? Can each (of the switched) image have its own palette or all images have the same? How many images you want to switch? In example you got 2 but what is the max limit? Are the times of switch controllable and to what extent? or are they simply fixed with constant interval equal to all images? For fully 3D color space and 8 images and controllable times you could use trilinear interpolation modulating the switching times ... — Spektre, Nov 16 '20 at 07:55
@Spektre I'm interested in using it for different common sizes of palettes, at least 8, 16, 32 and 256 colors (with 3 to 8 bits per color channel). I realize it's two quite different situations if the images have their own palette or if it's shared. And I'm interested in both those different situations (maybe I should have written a separate question for each of them). — Fabel, Nov 16 '20 at 10:51
@Spektre We can assume the number images is always two and that they are always displayed an equal amount of time. For simplicity we can just assume they are switched "as fast as possible" since different displays/monitors probably have a bigger impact visual experience than the actual framerate. If you know of an algorithm that only works with one of the palette sizes but not the others, I'm still interested. (If the number of possible palettes are easily enumerable, trying them one by one is of course an option, but apart from that.) — Fabel, Nov 16 '20 at 10:51

Spektre · Answer 1 · 2020-11-20T09:23:28.933

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 <vcl.h>
#include <math.h>
#include <jpeg.hpp>
#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<<rgb_bpc;                     // colors per channel (after truncation)
int   rgb[rgb_n][rgb_n][rgb_n];                 // recolor table
void  pal_clear();                              // clear palette to empty
void  pal_dither(int n);                        // add up to n colors for dithering to pal[pals]
void  pal_major(int n,Graphics::TBitmap *bmp);  // add up to n major colors from bmp to pal[pals]
void  pal_compute_recolor();                    // compure recolor rgb[n][n][n] array from pal[pals] where n is power of 2, and compute sh (bits to drop from 8bit channel)
void  rgb2chn(int &r,int &g,int &b,DWORD c);    // rgb color to r,g,b
DWORD chn2rgb(int r,int g,int b);               // r,g,b to rgb color
int   chn2pal(int r,int g,int b);               // r,g,b to palette index
int   rgb2pal(DWORD c);                         // rgb color to palette index
DWORD pal2rgb(int ix);                          // palette index to rgb color
void pal_render(Graphics::TBitmap *bmp,int y0); // render palette at bmp,y0
//---------------------------------------------------------------------------
void pal_clear()
    {
    pals=0;
    }
//---------------------------------------------------------------------------
void pal_VGA(int n)
    {
    const DWORD pal_VGA256[256]=
        {       // 0x00RRGGBB
        0x00000000,0x000000A8,0x0000A800,0x0000A8A8,0x00A80000,0x00A800A8,0x00A85400,0x00A8A8A8,
        0x00545454,0x005454FC,0x0054FC54,0x0054FCFC,0x00FC5454,0x00FC54FC,0x00FCFC54,0x00FCFCFC,
        0x00000000,0x00101010,0x00202020,0x00343434,0x00444444,0x00545454,0x00646464,0x00747474,
        0x00888888,0x00989898,0x00A8A8A8,0x00B8B8B8,0x00C8C8C8,0x00DCDCDC,0x00ECECEC,0x00FCFCFC,
        0x000000FC,0x004000FC,0x008000FC,0x00BC00FC,0x00FC00FC,0x00FC00BC,0x00FC0080,0x00FC0040,
        0x00FC0000,0x00FC4000,0x00FC8000,0x00FCBC00,0x00FCFC00,0x00BCFC00,0x0080FC00,0x0040FC00,
        0x0000FC00,0x0000FC40,0x0000FC80,0x0000FCBC,0x0000FCFC,0x0000BCFC,0x000080FC,0x000040FC,
        0x008080FC,0x009C80FC,0x00BC80FC,0x00DC80FC,0x00FC80FC,0x00FC80DC,0x00FC80BC,0x00FC809C,
        0x00FC8080,0x00FC9C80,0x00FCBC80,0x00FCDC80,0x00FCFC80,0x00DCFC80,0x00BCFC80,0x009CFC80,
        0x0080FC80,0x0080FC9C,0x0080FCBC,0x0080FCDC,0x0080FCFC,0x0080DCFC,0x0080BCFC,0x00809CFC,
        0x00B8B8FC,0x00C8B8FC,0x00DCB8FC,0x00ECB8FC,0x00FCB8FC,0x00FCB8EC,0x00FCB8DC,0x00FCB8C8,
        0x00FCB8B8,0x00FCC8B8,0x00FCDCB8,0x00FCECB8,0x00FCFCB8,0x00ECFCB8,0x00DCFCB8,0x00C8FCB8,
        0x00B8FCB8,0x00B8FCC8,0x00B8FCDC,0x00B8FCEC,0x00B8FCFC,0x00B8ECFC,0x00B8DCFC,0x00B8C8FC,
        0x00000070,0x001C0070,0x00380070,0x00540070,0x00700070,0x00700054,0x00700038,0x0070001C,
        0x00700000,0x00701C00,0x00703800,0x00705400,0x00707000,0x00547000,0x00387000,0x001C7000,
        0x00007000,0x0000701C,0x00007038,0x00007054,0x00007070,0x00005470,0x00003870,0x00001C70,
        0x00383870,0x00443870,0x00543870,0x00603870,0x00703870,0x00703860,0x00703854,0x00703844,
        0x00703838,0x00704438,0x00705438,0x00706038,0x00707038,0x00607038,0x00547038,0x00447038,
        0x00387038,0x00387044,0x00387054,0x00387060,0x00387070,0x00386070,0x00385470,0x00384470,
        0x00505070,0x00585070,0x00605070,0x00685070,0x00705070,0x00705068,0x00705060,0x00705058,
        0x00705050,0x00705850,0x00706050,0x00706850,0x00707050,0x00687050,0x00607050,0x00587050,
        0x00507050,0x00507058,0x00507060,0x00507068,0x00507070,0x00506870,0x00506070,0x00505870,
        0x00000040,0x00100040,0x00200040,0x00300040,0x00400040,0x00400030,0x00400020,0x00400010,
        0x00400000,0x00401000,0x00402000,0x00403000,0x00404000,0x00304000,0x00204000,0x00104000,
        0x00004000,0x00004010,0x00004020,0x00004030,0x00004040,0x00003040,0x00002040,0x00001040,
        0x00202040,0x00282040,0x00302040,0x00382040,0x00402040,0x00402038,0x00402030,0x00402028,
        0x00402020,0x00402820,0x00403020,0x00403820,0x00404020,0x00384020,0x00304020,0x00284020,
        0x00204020,0x00204028,0x00204030,0x00204038,0x00204040,0x00203840,0x00203040,0x00202840,
        0x002C2C40,0x00302C40,0x00342C40,0x003C2C40,0x00402C40,0x00402C3C,0x00402C34,0x00402C30,
        0x00402C2C,0x0040302C,0x0040342C,0x00403C2C,0x0040402C,0x003C402C,0x0034402C,0x0030402C,
        0x002C402C,0x002C4030,0x002C4034,0x002C403C,0x002C4040,0x002C3C40,0x002C3440,0x002C3040,
        0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,
        };
    for (int i=0;(i<n)&&(i<256)&&(pals<_pals);i++,pals++) pal[pals]=pal_VGA256[i];
    }
//---------------------------------------------------------------------------
void pal_dither(int n)
    {
    }
//---------------------------------------------------------------------------
void pal_major(int n,Graphics::TBitmap *bmp)    // only for rgb_bits=5 !!!
    {
    union { DWORD dd; BYTE db[4]; } c0,c1;
    int i,x,y,xs,ys,a,aa,hists;
    DWORD *p,cc,r,g,b;
    DWORD his[32768];
    DWORD idx[32768];
    // init
    xs=bmp->Width;
    ys=bmp->Height;
    n+=pals;
    // 15bit histogram
    for (x=0;x<32768;x++) { his[x]=0; idx[x]=x; }
    for (                           y=0;y<ys;y++)
     for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
        {
        cc=p[x];
        cc=((cc>>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<hists;x++,y++)
      if (his[x]<his[y])
        {
        i=his[x]; his[x]=his[y]; his[y]=i;
        i=idx[x]; idx[x]=idx[y]; idx[y]=i; i=1;
        }
    // set pal color palete
    for (x=0;x<hists;x++) // main colors
        {
        cc=idx[x];
        b= cc     &31;
        g=(cc>> 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<pals;i++)
            {
            c1.dd=pal[i];
            aa=int(BYTE(c1.db[0]))-int(BYTE(c0.db[0])); if (aa<=0) aa=-aa; a =aa;
            aa=int(BYTE(c1.db[1]))-int(BYTE(c0.db[1])); if (aa<=0) aa=-aa; a+=aa;
            aa=int(BYTE(c1.db[2]))-int(BYTE(c0.db[2])); if (aa<=0) aa=-aa; a+=aa;
            if (a<=16) { a=1; break; } a=0; // *** treshold ***
            }
        if (!a)
            {
            pal[pals]=c0.dd; pals++;
            if (pals>=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<rgb_n;r++)
     for (g=0;g<rgb_n;g++)
      for (b=0;b<rgb_n;b++)
        {
        // find closest match in pal[m]
        for (j=-1,x=1000000,i=0;i<pals;i++)
            {
            c=pal[i];
            bb= c     &255; bb-=b<<rgb_sh; bb*=bb;
            gg=(c>> 8)&255; gg-=g<<rgb_sh; gg*=gg;
            rr=(c>>16)&255; rr-=r<<rgb_sh; rr*=rr;
            y=rr+gg+bb;
            if (x>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;(i<pals)&&(c+8<ys);c+=10,i=j)
     for (y=c;y<c+8;y++)
      for (p=(int*)bmpd->ScanLine[y],j=i,x=0;(x<xs)&&(j<pals);x++)
       { p[x]=pal[j]; if ((x&7)==7){ x++; j++; if (x+8>xs) 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;i<colors;i++) pal0[i]=pal[i];  // store palette for later
    // recolor bmp0,bmp1
    for (y=0;y<ys;y++)
        {
        p =(int*)bmp ->ScanLine[y];
        p0=(int*)bmp0->ScanLine[y];
        p1=(int*)bmp1->ScanLine[y];
        for (x=0;x<xs;x++)
            {
            // i = recolor(p)   // bmp0
            rgb2chn(r,g,b,p[x]); i=chn2pal(r,g,b);
            // p1 = (2*p-p0)    // bmp1
            rgb2chn(rr,gg,bb,pal[i]);
            bb=b+b-bb; if (bb>255) 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;i<colors;i++) pal1[i]=pal[i];  // store palette for later
    // recolor bmp1
    for (y=0;y<ys;y++)
        {
        p1=(int*)bmp1->ScanLine[y];
        for (x=0;x<xs;x++) p1[x]=pal[rgb2pal(p1[x])]; // quantized
        }

    // Blend and difference for debug
    for (y=0;y<ys;y++)
        {
        p =(int*)bmp ->ScanLine[y];
        p0=(int*)bmp0->ScanLine[y];
        p1=(int*)bmp1->ScanLine[y];
        pd=(int*)bmpd->ScanLine[y];
        for (x=0;x<xs;x++)
            {
            // get r,g,b
            rgb2chn(r ,g ,b ,p0[x]);
            rgb2chn(rr,gg,bb,p1[x]);
            // blend
            r=(r+rr)>>1;
            g=(g+gg)>>1;
            b=(b+bb)>>1;
            // diff
            rgb2chn(rr,gg,bb,p[x]);
            i=2;    // scale
            rr=abs(r-rr)<<i; if (rr>255) rr=255;
            gg=abs(g-gg)<<i; if (gg>255) gg=255;
            bb=abs(b-bb)<<i; if (bb>255) bb=255;
            // copy pixels
            p[x]=chn2rgb(r,g,b);
            pd[x]=chn2rgb(rr,gg,bb);
            }
        }
    // render palettes
    for (i=0;i<colors;i++) pal[i]=pal0[i]; pal_render(bmpd,0);
    for (i=0;i<colors;i++) pal[i]=pal1[i]; pal_render(bmpd,100*colors/xs+10);


    bmp ->SaveToFile("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.

I appreciate your effort, but how did you optimize the palette for the image to begin with? My question was specifically about how to "calculate an optimal (or semi-optimal) palette". The method I used to create the two images was to create an array with color pairs (for all colors not to far apart) and the color value they blend to, as a virtual palette, and remap to that. Not as fast as your solution but, I think, more precise. — Fabel, Nov 16 '20 at 17:30
Oh, just realized you used the standard VGA palette (went straight for the code without properly reading the comments, sorry). Yet, what I seek an answer to is how to "custom compute part of palette to include more close colors". — Fabel, Nov 16 '20 at 17:45
@Fabel what I did is a form of very soft dithering and standard VGA palette (both first 16 and 256 colors) is specially designed for dithering.... The algo from the GIF quantization will give you the close significant colors from image (how many is just constant) so I would combine those two ... like use first 16 colors from VGA and then add 16 from the quantization ... — Spektre, Nov 16 '20 at 20:36
I don't get it. You seem to describe basic techniques for color reduction in detail (including dithering) but only hint about the actual palette optimization. Those "16 [colors] from the quantization", do they constitute a (more) optimized palette? If so, a process there the resulting image is compared to the original yields data that is used to improve the palette, and iterating it would perhaps improve the palette further? If this is what you're saying could you please elaborate that part. — Fabel, Nov 17 '20 at 07:30
@Fabel I reedited my question ... had played with the code a bit and made some changes ... now the result is much better at the cost of 2 times quantization is used (which is now included in the code) its basically the same code as in the quantization link (where the process is also described) but you can use any quantization method. — Spektre, Nov 20 '20 at 09:25

Palette quantization for pixel mixing

1 Answers1