许多图像及其调色板的算法
Ben*_*lte 6 javascript sorting algorithm image colors
对于一个项目,我正在寻找一种算法,将大量图像转换为调色板图像,这些图像可以共享相同的调色板.
短篇小说
鉴于:
- 图像列表(RGB),已经具有应该使用的最终颜色.
结果:
- 图像列表(显示)
- 调色板列表
- 通过使用不同的调色板,可以将多个RGB图像转换为一个指示图像.
- 我想使用所需的最少量调色板所需的最少量图像.
限制:
- 最多有n个调色板
- 每个调色板最多有m种颜色
- 最多可以在结果中生成u图像
我的问题是什么:
- 我不知道如何构建算法,因此它可以决定先前的决定是否对未来的问题是错误的.(见下文)
- 我不知道如何解决重新排列调色板颜色和图像数据,因为重新排列一个图像数据可能会导致重新排列的后续问题,这可能会在无休止的重新排列战中结束:D(见下文)
这是完整的故事
结果
因此,这应该是结果:在这种情况下,一个颜色索引表(也称为指示图像)使用两个不同的调色板生成两个不同的RGB图像.
第一步
由于输入文件都是RGB图像,我们需要先将它们转换为具有匹配颜色索引的调色板.
在下图中,您可以看到算法如何开始使用前三个图像:
- 将它们转换为调色板和颜色索引
- 检查两个图像是否共享相同的颜色索引,如果是这样,我们可以重用颜色索引但创建一个调色板(不是必需的!)
- 否则,我们可以将四种新颜色添加到第一个调色板并创建一个新的颜色索引.(此图中未显示)
- 对于第三个图像,我们找到了一个已包含所有必需颜色的调色板,因此我们决定重复使用调色板,但重新排列我们的颜色索引以匹配现有调色板.
让我们变得复杂!
到现在为止还挺好.但是我们应该如何继续使用最后一张图片呢？它可以共享前一个的颜色索引,但它与任何现有的调色板都不匹配.实际上它与任何现有的调色板都不匹配.
因此下图描述了实际问题:如何确定最适合图像的内容？创建一个新的调色板,创建一个新的颜色索引,如果我们过去另有决定,一切都会好的怎么办？我们怎么知道？
重新排列
那么,这四个图像仍然是简单的情况.让我们假设算法已经处理了很多图像,并生成了一个调色板.我们的input-image-list中的下一个图像找到一个匹配的调色板,因此它可以很容易地创建新的颜色索引并且没问题.但是:结果应该是最少的图像和调色板,所以可能有另一种方式!
通过检查所有先前的图像,我们发现,我们可以使用前一图像的现有调色板和颜色索引,但我们必须重新排列调色板.重新排列要求我们检查所有以前的图像是否可以使用重新排列的调色板.
如您所见:最后一步中的调色板已重新排列,以匹配下面相同的颜色.但这可能是重新安排许多其他图像的复杂过程.
提前感谢您提供有关如何实现此类算法的任何提示,或者搜索的内容或现有算法产生的结果几乎相同.
编辑
这是一个真实的生活示例图像,其中一些图形从旧的amiga游戏中被盗:
此tileset包含256个16*16像素的RGB图像.这些图像中的每一个都是应该由算法处理的图块.前几张图像彼此相同,但稍后还有其他几张图像.可以将调色板分解为最多6个具有16种颜色的调色板,但是总是使第一种颜色为透明颜色的限制.(实际上每个调色板有15种颜色)
在这个例子中,它很容易重复使用相同的ColorIndices 4色键,门和diamants.
这是一个生成调色板的示例:
编辑第2号
这是我从旧游戏中拿出的另一个例子:
调色板可能如下所示:
看起来我对您的示例输入的第一个天真的方法甚至比您的参考更好：
左边是输入图像，中间是group[]仅使用全局调色板的精灵输出，没有空精灵。右侧是按组排序的独特调色板，最右侧的列是代表该组的组调色板。
正如您所看到的，我只有 5x 16 个调色板，而不是 6 个。第一个颜色索引 0 保留用于透明颜色（我硬编码白色，因为我无法访问原始索引颜色）。算法是这样的：
初始精灵
每个精灵都必须使用其调色板和全局调色板索引。
结构
为此我需要 2 个调色板列表。一个是一次使用的所有独特调色板的列表（整个图像/帧），我称之为它，
pal[]另一个被调用group[]并保存要使用的最终合并调色板。填充
pal[]因此，只需从所有精灵中提取所有调色板...测试唯一性（这只是为了提高搜索性能
O(n^2)）。为此，我对调色板进行了排序，这样我就可以直接比较它们O(n)而不是O(n^2).分组调色板
获取第一个未分组的调色板并用它创建新组。然后检查所有其他未分组的调色板 (
O(n^2))，如果可合并，则合并它们。通过可合并，我的意思是经过处理的pal[i]颜色至少有 50% 存在于 中group[j]，并且所有缺失的颜色仍然可以适合group[j]. 如果案例标记pal[i]为group[j]成员并将缺少的颜色添加到group[j]. 然后重复#4，直到没有未分组的调色板剩余。现在重新索引精灵以匹配
group[]调色板
这里有简单的 C++ 代码：
//---------------------------------------------------------------------------
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像素编码如下：
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