Algorithm for many images and their color palettes

Question

For a project, I'm looking for an algorithm to convert a large number of images into image palettes that can share the same palettes.

---

Story

Given:

• A list of images (RGB) that already have the final colors to use.

Result:

• List of images (indicating)
• Palette list
• Multiple RGB images can be converted to a single displayed image using various palettes .
• I want to use the minimum number of images required with the minimum number of palettes needed.

Limitations:

• There are a maximum of n palettes
• The maximum number of colors on the palette
• The maximum number of images u that can be generated as a result

What is my problem:

• I do not know how to build an algorithm so that it can decide if any previous solution was wrong for future problems. (see below).
• I don’t know how to decide to reorder the colors of the palettes and the image data, because reformatting one image can lead to subsequent reordering problems, which can end with an endless brute force battle: D (see below)

---

Here is the full story

Result

So here should be the result . In this case, one color index table (similar to the displayed image) generates two different RGB images using two different palettes.

The first steps

Since the input files are all RGB images, we first need to convert them to palettes with the corresponding color indices.

In the following figure, you can see how the algorithm can start working with the first three images:

• Convert them to palettes and color indices
• Note that the two images share the same color indices , if so, we can reuse the color indices but create a palette (not necessary!)
• Otherwise, we could add four new colors to the first palette and create a new color index . (Not shown in this image)
• For the third image, we found a palette that already contains all the necessary colors, so we decided to reuse the palette, but change our color indices to match the existing palette.

Let it get complicated!

So far so good. But how can we continue working with the last image? It can share the color indices of the previous one, but then it does not match any existing palette. In fact, this does not match any existing palette.

So, the following image describes the actual problem : how to solve what works best for images? Creating a new palette, creating a new color index, what if everything goes well, if in the past we decided otherwise? How can we find out?

Reordering

Well, these four images are still simple. Suppose the algorithm has already processed many images and created a palette. The next image in our list of input images will find a suitable palette, so it can easily create new color indices and be fine. But: the result should be at least images and palettes, so there may be another way!

Checking all the previous images, we found out that we could use the existing color indices and the previous image, but we need to change the order of the palette. And the permutation requires us to check all previous images if they agree with the redone palette.

As you can see: the color palettes in the last step were rearranged to match the same colors below. But it can be a complicated process of rearranging many other images.

---

Thank you in advance for any advice on how to implement such an algorithm or what to look for or which existing algorithms generate almost the same result.

---

Edit

Here's a real-life lifestyle with graphics stolen from an old amiga game:

This panel contains 256 RGB images with 16 * 16 pixels. Each of these images is a fragment that must be processed by the algorithm. The first few images are equal to each other, but later there are several other images. You can split palettes into a maximum of 6 palettes with 16 colors , but with the limitation of always having the first color of a transparent color. (so actually its 15 colors per palette)

In this example, it is easy to reuse the same ColorIndices for 4 color keys, doors, and diamonds.

This is an example of a generated palette:

---

Change No. 2

Here is another example that I extracted from an old game:

The palette might look like this:

Answer 1

It seems like my first naive approach for sample input is even better than the link:

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

As you can see, I only have 5x 16 color palettes instead of 6. The first color index 0 is reserved for a transparent color (I am hard white because I do not have access to the original indexed colors). The algorithm is as follows:

• init sprites

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

• <strong> structures

  I needed 2 lists of palettes. One of them is a list of all unique palettes used simultaneously (the whole image / frame), I call it pal[] , and the other is called group[] and contains the final combined palettes that will be used.

• fill pal[]

  so just extract all the palettes from all the sprites ... check for uniqueness (this is just to improve O(n^2) search performance) To do this, I sorted the palettes to directly compare them in O(n) instead of O(n^2) .

• palette grouping

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

• now reindex sprites according to group[] palettes

Here is 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 files.

I use my own image class for images, so some members:

xs,ys - image size in pixels
p[y][x].dd - pixel at position (x,y) as a 32-bit integer type
clear(color) clears the whole image with color
resize(xs,ys) resizes the image to a new resolution
bmp VCL Encapsulated GDI Bitmap with Canvas Access
pf contains the 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 as follows:

 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; };*/ }; 

Ranges:

 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 my dynamic list template, therefore:

List<double> xxx; matches double xxx[];
xxx.add(5); adds 5 to the end of the list
xxx[7] access array element (secure)
xxx.dat[7] access array element (unsafe, but fast direct access)
xxx.num - actual used array size
xxx.reset() clears the array and sets xxx.num=0
xxx.allocate(100) preset space for 100 elements