Algorithm for many images and their color palettes

Question

For a project I'm looking for an algorithm to convert a lot of images to paletted images, which can share same palettes.

---

The short story

Given:

• A list of images (RGB), which already have the final colors which should be used.

Result:

• A list of images (indiced)
• A list of palettes
• Multiple RGB images can be converted to one indiced image by using different palettes.
• I want to use the minimum amount of images required with the minimum amount of palettes required.

Limitations:

• There is a maximum of n palettes
• There is a maximum of m colors per palette
• There is a maximum of u images which can be generated in the result

What is my problem:

• I don't know how to build the algorithm so it can decide whether any previous decision was wrong for future problems. (see below)
• I don't know how to solve rearranging palette colors and image data, because rearranging one image data might lead to follow up problems of rearranging which can end in an endless rearranging battle :D (see below)

---

Here is the full story

The result

So this here should be the result: In this case one color index table (aka indiced image) generates two different RGB images using two different palettes.

The first steps

As the input files all are RGB images, we need to convert them into palettes with their matching color indices first.

In the following image you can see how the algorithm could start working with the first three images:

1. Convert them into palettes and color-indices
2. Check whether two images share the same color indices, if so, we can reuse the color indices but create a palette (not required!)
3. Otherwise we could add the four new colors to the first palette and create a new color index. (Not shown in this image)
4. For the third image, we found a palette which already contains all required colors, so we decide to reuse the palette but rearrange our color indices to match the existing palette.

Let's get complicated!

So far so good. But how should we continue with the last image? It may share the color indices of the previous one, but it does not match any existing palette then. Actually it does not match any existing palette.

So the following image describes the actual problem: How to decide what's best for images? Creating a new palette, creating a new color index, what if everything would went good if we decided otherwise in the past? How can we find out?

Rearranging

Well, those four images are still the simple case. Let's imagine the algorithm already processed a lot of images, and generated a palette. The next image in our input-image-list finds a matching palette, so it could easily just create new color-indices and be fine. But: The result should be a minimum of images and palettes, so there could be another way!

By checking all previous images, we found out, that we could use the existing palette and color indices of the previous image, but we have to rearrange the palette. And rearranging requires us to check all previous images whether they are okay with the rearranged palette.

As you can see: The colors palettes in the last step have been rearranged to match the same colors below. But this might have been a complicated process of rearranging a lot of other images as well.

---

Thank you in advance for any tips of how to implement such an algorithm, or what to search for or what already existing algorithms generate the nearly same result.

---

Edit

Here is a real life example image with some graphics stolen from an old amiga game:

This tileset contains 256 RGB images of 16*16 pixel. Each of this images is a tile which should be processed by the algorithm. The first few images are equal to each other, but later on there are several other images. It is possible to break down the palettes into a maximum of 6 palettes with 16 colors but with the limitation of always having the first color being a transparent color. (so actually its 15 colors per palette)

In this example its easy to reuse the same ColorIndices for the 4 colored keys, doors and diamants.

This is an example generated palette:

---

Edit No. 2

Here is another example I took out of an old game:

The palette could look like this one:

Answer 1

Looks like my first naive approach for your sample input is even better than your reference:

On the left is your input image, in the middle is sprite output using global group[] palettes only without the empty sprites. On the right are unique palettes sorted by group and in the right most column is the group palette representing that group.

As you can see I have just 5x 16 color palettes instead of 6. The first color index 0 is reserved for transparent color (I hard-coded white as I do not have access to the original indexed colors). The Algorithm is like this:

1. init sprites

   Each sprite must have its palette and index of global palette used.

2. structures

   I needed 2 lists of palettes for this. One is list of all unique palettes used at once (the whole image/frame) I call it pal[] and the other is called group[] and holds the final merged palettes to be used.

3. populate pal[]

   so just extract all palettes from all the sprites ... test for uniqueness (that is just to boost performance of the O(n^2) searches). To do this I sorted the palettes so I can directly compare them in O(n) instead of O(n^2).

4. grouping palettes

   Take first ungrouped palette and create new group with it. Then check all other ungrouped palettes (O(n^2)) and if mergable then merge them. By mergable I mean the processed pal[i] have at least 50% of the colors present in the group[j] and all the missing colors can still fit into the group[j]. If the case mark pal[i] as a group[j] member and add the missing colors to group[j]. Then repeat #4 until no ungrouped palette is left.

5. now reindex the sprites to match the group[] palettes

Here simple C++ code for this:

//---------------------------------------------------------------------------
const int _sprite_size=16;      // resolution
const int _palette_size=16;     // colors per palette
//---------------------------------------------------------------------------
class palette   // sprite palette
    {
public:
    int pals;                   // num of colors
    DWORD pal[_palette_size];   // palete colors
    int group;                  // group index

    // inline constructors (you can ignore this)
    palette()   {}
    palette(palette& a) { *this=a; }
    ~palette()  {}
    palette* operator = (const palette *a) { *this=*a; return this; }
    //palette* operator = (const palette &a) { ...copy... return this; }

    void draw(TCanvas *can,int x,int y,int sz,int dir)  // render palette to GDI canvas at (x,y) with square size sz and direction dir = { 0,90,180,270 } deg
        {
        int i;
        color c;
        for (i=0;i<pals;i++)
            {
            c.dd=pal[i]; rgb2bgr(c);
            can->Pen->Color=TColor(0x00202020);
            can->Brush->Color=TColor(c.dd);
            can->Rectangle(x,y,x+sz,y+sz);
            if (dir==  0) x+=sz;
            if (dir== 90) y-=sz;
            if (dir==180) x-=sz;
            if (dir==270) y+=sz;
            }
        }
    void sort() // bubble sort desc
        {
        int i,e,n=pals; DWORD q;
        for (e=1;e;n--)
         for (e=0,i=1;i<n;i++)
          if (pal[i-1]<pal[i])
           { q=pal[i-1]; pal[i-1]=pal[i]; pal[i]=q; e=1; }
        }
    int operator == (palette &a) { if (pals!=a.pals) return 0; for (int i=0;i<pals;i++) if (pal[i]!=a.pal[i]) return 0; return 1; }
    int merge(palette &p)   // return true and merge if this and p are similar and mergable palettes
        {
        int equal=0,mising=0,i,j;
        DWORD m[_palette_size]; // mising palette colors
        for (i=0;i<p.pals;i++)
            {
            m[mising]=p.pal[i];
            mising++;
            for (j=0;j<pals;j++)
             if (p.pal[i]==pal[j])
                {
                mising--;
                equal++;
                }
            }
        if (equal+equal<p.pals) return 0;   // at least half of colors must be present
        if (pals+mising>_palette_size) return 0;    // and the rest must fit in
        for (i=0;i<mising;i++) { pal[pals]=m[i]; pals++; }
        return 1;
        }
    };
//---------------------------------------------------------------------------
class sprite    // sprite
    {
public:
    int xs,ys;                              // resoltuon
    BYTE pix[_sprite_size][_sprite_size];   // pixel data (indexed colors)
    palette pal;                            // original palette
    int gpal;                               // global palette

    // inline constructors (you can ignore this)
    sprite()    {}
    sprite(sprite& a) { *this=a; }
    ~sprite()   {}
    sprite* operator = (const sprite *a) { *this=*a; return this; }
    //sprite* operator = (const sprite &a) { ...copy... return this; }
    };
//---------------------------------------------------------------------------
List<sprite> spr;   // all sprites
List<palette> pal;  // all palettes
List<palette> group;// merged palettes
picture pic0,pic1,pic2; // input, output and debug images
//---------------------------------------------------------------------------
void compute() // this is the main code you need to call/investigate
    {
    bmp=new Graphics::TBitmap;
    bmp->HandleType=bmDIB;
    bmp->PixelFormat=pf32bit;

    int e,i,j,ix,x,y,xx,yy;
    palette p,*pp;
    DWORD c;
    // [load image and convert to indexed 16 color sprites]
    // you can ignore this part of code as you already got your sprites with palettes...
    pic0.load("SNES_images.png");
    // process whole image
    spr.num=0; sprite s,*ps;
    for (y=0;y<pic0.ys;y+=_sprite_size)
     for (x=0;x<pic0.xs;x+=_sprite_size)
        {
        // let white transparent color be always index 0
        s.pal.pals=1;
        s.pal.pal[0]=0x00F8F8F8;
        s.gpal=-1;
        e=0;
        // proces sprite image
        for (yy=0;yy<_sprite_size;yy++)
         for (xx=0;xx<_sprite_size;xx++)
            {
            // match color with palette
            c=pic0.p[y+yy][x+xx].dd&0x00F8F8F8; // 15 bit RGB 5:5:5 to 32 bit RGB
            for (ix=-1,i=0;i<s.pal.pals;i++)
             if (s.pal.pal[i]==c) { ix=i; break; }
            // add new color if no match found
            if (ix<0)
                {
                if (s.pal.pals>=_palette_size)
                    {
                    // fatal error: invalid input data
                    ix=-1;
                    break;
                    }
                 ix=s.pal.pals;
                 s.pal.pal[s.pal.pals]=c;
                 s.pal.pals++;
                 }
            s.pix[yy][xx]=ix; e|=ix;
            }
        if (e) spr.add(s);  // ignore empty sprites
        }

    // [global palette list]
    // here starts the stuff you need
    // cretae list pal[] of all unique palettes from sprites spr[]
    pal.num=0;
    for (i=0,ps=spr.dat;i<spr.num;i++,ps++)
        {
        p=ps->pal; p.sort(); ix=-1;
        for (x=0;x<pal.num;x++) if (pal[x]==p) { ix=x; break; }
        if (ix<0) { ix=pal.num; pal.add(p); }
        ps->gpal=ix;
        }

    // [palette gropus]
    // creates a list group[] with merged palette from all the pal[] in the same group
    group.num=0;
    for (i=0;i<pal.num;i++) pal[i].group=-1;
    for (i=0;i<pal.num;i++)
        {
        if (pal[i].group<0)
            {
            pal[i].group=group.num; group.add(pal[i]);
            pp=&group[group.num-1];
            }
        for (j=i+1;j<pal.num;j++)
         if (pal[j].group<0)
          if (pp->merge(pal[j]))
           pal[j].group=pp->group;
        }

    // [update sprites to match group palette]
    for (i=0,ps=spr.dat;i<spr.num;i++,ps++)
        {
        pp=&pal[ps->gpal];  // used global palette
        ps->gpal=pp->group; // update gpal in sprite to point to group palette (you can copy group palette into sprite instead)
        pp=&group[ps->gpal];// used group palette
        // compute reindex table
        int idx[_palette_size];
        for (x=0;x<ps->pal.pals;x++)
         for (idx[x]=0,y=0;y<pp->pals;y++)
          if (ps->pal.pal[x]==pp->pal[y])
           {idx[x]=y; break; }
        // proces sprite image
        for (yy=0;yy<_sprite_size;yy++)
         for (xx=0;xx<_sprite_size;xx++)
          if (ps->pix[yy][xx])  // ignore transparent pixels
           ps->pix[yy][xx]=idx[ps->pix[yy][xx]];
        }

    // [render groups]
    e=6;
    xx=(e*_palette_size);
    yy=(e*pal.num);
    pic2.resize(xx+e+xx,yy);
    pic2.clear(0);
    for (x=0,y=0,ix=0;ix<group.num;ix++,y+=e)
        {
        group[ix].draw(pic2.bmp->Canvas,x+xx,y,e,0);
        for (i=0;i<pal.num;i++)
         if (pal[i].group==ix)
            {
            pal[i].draw(pic2.bmp->Canvas,x,y,e,0);
            y+=e;
            }
        }

    // [render sprites to pic1 for visual comparison using merged palettes]
    pic1.resize(pic0.xs,pic0.ys);
    pic1.clear(0);
    for (x=0,y=0,i=0,ps=spr.dat;i<spr.num;i++,ps++)
        {
        pp=&group[ps->gpal];
        // proces sprite image
        for (yy=0;yy<_sprite_size;yy++)
         for (xx=0;xx<_sprite_size;xx++)
          if (ps->pix[yy][xx])  // ignore transparent pixels
           pic1.p[y+yy][x+xx].dd=pp->pal[ps->pix[yy][xx]];
        x+=_sprite_size; if (x+_sprite_size>pic1.xs) { x=0;
        y+=_sprite_size; if (y+_sprite_size>pic1.ys) break; }
        }
//---------------------------------------------------------------------------

Just ignore the VCL and GDI rendering stuff.

I use my own picture class for images so some members are:

xs,ys is size of image in pixels
p[y][x].dd is pixel at (x,y) position as 32 bit integer type
clear(color) clears entire image with color
resize(xs,ys) resizes image to new resolution
bmp is VCL encapsulated GDI Bitmap with Canvas access
pf holds actual pixel format of the image:

enum _pixel_format_enum
    {
    _pf_none=0, // undefined
    _pf_rgba,   // 32 bit RGBA
    _pf_s,      // 32 bit signed int
    _pf_u,      // 32 bit unsigned int
    _pf_ss,     // 2x16 bit signed int
    _pf_uu,     // 2x16 bit unsigned int
    _pixel_format_enum_end
    };

color and pixels are encoded like this:

union color
    {
    DWORD dd; WORD dw[2]; byte db[4];
    int i; short int ii[2];
    color(){}; color(color& a){ *this=a; }; ~color(){}; color* operator = (const color *a) { dd=a->dd; return this; }; /*color* operator = (const color &a) { ...copy... return this; };*/
    };

The bands are:

enum{
    _x=0,   // dw
    _y=1,

    _b=0,   // db
    _g=1,
    _r=2,
    _a=3,

    _v=0,   // db
    _s=1,
    _h=2,
    };

I also use mine dynamic list template so:

List<double> xxx; is the same as double xxx[];
xxx.add(5); adds 5 to end of the list
xxx[7] access array element (safe)
xxx.dat[7] access array element (unsafe but fast direct access)
xxx.num is the actual used size of the array
xxx.reset() clears the array and set xxx.num=0
xxx.allocate(100) preallocate space for 100 items