许多图片及其色板的算法

Question

我正在寻找一种算法，将大量图像转换为调色板图像，这些图像可以共享相同的调色板。

---

简短故事

给定：

• 一个图像列表（RGB），其中已经有了应该使用的最终颜色。

结果：

• 一个图像列表（索引）
• 一个调色板列表
• 多个RGB图像可以通过使用不同的调色板转换为一个索引图像。
• 我想使用所需的最少数量的图像和调色板。

限制：

• 调色板的最大数量为n
• 每个调色板的最大颜色数为m
• 结果中可以生成的图像的最大数量为u

我的问题是：

• 我不知道如何构建算法，以便它可以决定任何之前的决策是否对未来的问题有错。（见下文）
• 我不知道如何解决重新排列调色板颜色和图像数据的问题，因为重新排列一个图像数据可能会导致后续的重新排列问题，最终导致无休止的重新排列战斗 :D（见下文）

---

完整故事

结果

这里应该是结果：在这种情况下，一个颜色索引表（即索引图像）使用两个不同的调色板生成两个不同的RGB图像。

第一步

由于所有输入文件都是RGB图像，因此我们首先需要将它们转换为具有匹配颜色索引的调色板。

在接下来的图像中，您可以看到算法如何开始处理前三个图像：

1. 将它们转换为调色板和颜色索引
2. 检查两个图像是否共享相同的颜色索引，如果是，则可以重复使用颜色索引但不需要创建调色板。
3. 否则，我们可以将四种新颜色添加到第一个调色板中并创建新的颜色索引。（此图片未显示）
4. 对于第三个图像，我们找到了一个已包含所有必需颜色的调色板，所以我们决定重复使用调色板，但重新排列颜色索引以匹配现有的调色板。

让我们变得复杂起来！

到目前为止都很好。但是我们应该如何处理最后一个图像呢？它可能共享先前图像的颜色索引，但那时它没有匹配任何现有的调色板。实际上它没有匹配任何现有的调色板。

因此，以下图片描述了实际问题：如何决定什么对图像最好？创建新调色板、创建新颜色索引，如果我们过去做出不同的决策，一切都很好，那么怎么办？我们如何找出来？

重新排列

这四张图片仍然是简单情况。让我们想象一下，算法已经处理了许多图像，并生成了调色板。我们输入的下一个图像找到了匹配的调色板，因此它可以轻松地创建新的颜色索引并正常运行。但是：结果应该是最少的图像和调色板，因此可能还有另一种方法！

通过检查所有以前的图像，我们发现我们可以使用先前图像的现有调色板和颜色索引，但是我们必须重新排列调色板。重新排列需要我们检查所有以前的图像，以确保他们接受重新排列的调色板。

如您所见：最后一步中的调色板已被重新排列以匹配下面的相同颜色。但这可能是一个复杂的过程，需要重新排列许多其他图像。

---

非常感谢您提供任何有关如何实施此算法的提示，或者搜索什么，或者已经存在的算法生成几乎相同的结果。

编辑

这是一个真实的例子图片，其中一些图形是从旧的amiga游戏中偷来的：

这个tileset包含256个RGB图像，每个图像大小为16*16像素。这些图像中的每一个都是一个需要算法处理的瓦片。前几个图像都是相同的，但之后还有其他几个图像。可以将调色板分解成最多6种调色板，每种调色板有16种颜色，但始终要有第一种颜色作为透明颜色限制（因此实际上每个调色板只有15种颜色）。

在这个例子中，可以很容易地重复使用4个彩色钥匙、门和钻石的相同颜色索引。

这是一个生成的调色板示例：

---

编辑编号2

这是我从一个旧游戏中拿出来的另一个例子：

调色板可以看起来像这样：

- Benjamin Schulte

---

+1 有趣的问题。你需要完全匹配颜色吗？如果不需要，你可以像这样将相似的颜色分组 有效的gif /图像颜色量化？。你考虑过抖动吗？那需要为所有图像使用单个调色板...或者按主要颜色对图像进行分组，并为每个组设计特殊的调色板，降低噪音...此外，你真的需要“最小”解决方案吗？或者接近也可以？ - Spektre

@Spektre 谢谢！实际上，输入的RGB图像已经只有最终颜色（限制为n种颜色），不需要再进行修改。可能允许合并几乎相等的颜色，但这不是这个问题的一部分 :) 更多的是将所有图像调色板合并成一个调色板。 “最小化”解决方案会很好，但足够接近也足够好，我想。也可能在某个时候根本没有解决方案。 - Benjamin Schulte

非常好的问题。如果我理解正确，您正在尝试在不超过_m_的情况下最小化_palette的数量。我没有理解的是_u_。难道您不是想将尽可能多的图像放入一个_palette中吗？为什么有一个限制来分配到_palette中的图像数量呢？ - Manuel Otto

实际上，这个问题是用于超级任天堂游戏项目的工具。生成的图像将用于瓦片集（每个图像是一个瓦片）。SNES 仅限于 16（或 8）个调色板，每个调色板有 16 种颜色。此外，由于 RAM 有限，应尽可能减少图像数量。大多数开发人员会为每个游戏地图使用静态瓦片集和静态调色板，但我想要一个动态生成的瓦片集和动态生成的调色板。:) 如果它们可以共享颜色，则每个调色板可以有无限的图像。 - Benjamin Schulte

@Spektre，这是15位颜色，每个通道有5位。我编辑了帖子，并在末尾附上了一个手动生成的调色板的真实示例。 :) - Benjamin Schulte

Answer 1

看起来我的第一个天真的方法对于你的示例输入甚至比你的参考更好：

在左边是您的输入图像，在中间是使用全局group[]调色板输出的精灵，而没有空精灵。右边是按组排序的唯一调色板，最右边的列是代表该组的组调色板。

正如您所看到的，我只有5个16色调色板，而不是6个。第一个颜色索引0保留为透明颜色（我硬编码白色，因为我无法访问原始索引颜色）。算法如下：

1. 初始化精灵

   每个精灵都必须有其使用的全局调色板的调色板和索引。

2. 结构

   我需要两个调色板列表。一个是所有同时使用的唯一调色板列表（整个图像/帧），我称之为pal[]，另一个称为group[]，保存最终合并的调色板以供使用。

3. 填充pal[]

   只需从所有精灵中提取所有调色板...测试其唯一性（这只是为了提高O(n^2)搜索的性能）。为此，我对调色板进行了排序，以便可以直接在O(n)而不是O(n^2)中进行比较。

4. 分组调色板

   取第一个未分组的调色板并创建新组。然后检查所有其他未分组的调色板（O(n^2)），如果可合并，则合并它们。可合并指处理过的pal[i]在group[j]中至少有50%的颜色，并且所有缺失的颜色仍然可以适合group[j]。如果是这种情况，则将pal[i]标记为group[j]成员，并将缺失的颜色添加到group[j]中。然后重复#4，直到没有未分组的调色板为止。

5. 现在重新索引精灵以匹配group[]调色板

这是有关编程的简单C++代码：

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

请忽略VCL和GDI渲染内容。

我使用自己的图片类来处理图像，其中一些成员包括：

xs,ys是图像的像素大小
p[y][x].dd是位于(x,y)位置的像素，以32位整数类型表示
clear(color)用color清除整个图像
resize(xs,ys)将图像调整为新分辨率
bmp是封装了VCL的GDI位图，可访问Canvas
pf保存图像的实际像素格式：

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”和“pixels”的编码方式如下：

color和像素的编码方式如下：

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

这段文本的英译为：

这些乐队是：

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

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

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

我也使用我的动态列表模板，如下： List<double> xxx; 相当于 double xxx[]; xxx.add(5); 将 5 添加到列表的末尾 xxx[7] 访问数组元素（安全） xxx.dat[7] 访问数组元素（不安全但直接访问速度快） xxx.num 是数组的实际使用大小 xxx.reset() 清空数组并设置 xxx.num=0 xxx.allocate(100) 预分配空间以容纳 100 个项目

- Spektre

---

+1 非常感谢您在此方面的努力 :) 我尝试了您的方法，对于这个例子看起来很不错。我发现它忽略了“使用不同调色板共享具有相同ColorIndices的图像”的事情，但我检查了一下，发现并不是很多情况。我添加了一个昨天完成的第二个示例。该算法生成8个调色板（通过一些更多的代码行可以轻松压缩到7个，这没有问题），但原始版本使用5个调色板。我考虑过在这个上面使用某种astar算法？无论如何：非常感谢！ :D - Benjamin Schulte

你可以添加任何类型的调整，例如仅从最大的未分组调色板创建组，或首先按某些内容对调色板进行排序，或在实际组调色板中更改任何颜色后尝试重新合并，更改可合并阈值等等... 这只是一个起点，我会尝试按相似性将调色板排序到实际处理的组调色板，并首先添加最相似的... - Spektre