如何在二维中对颜色进行排序？
How to sort colors in two dimensions?
我目前正在从事一个爱好项目，以自动解决流行手机游戏 I Love Hue 中的一个谜题。游戏可用 here。
基本上，游戏的整个前提是给你一堆排列在网格中的彩色矩形块。您可以交换除少数固定块以外的大部分块，这些块用黑点标记。游戏的目的是交换周围的方块，从而获得二维色谱。对颜色进行排序，使每个块的颜色近似于其周围颜色的平均值。 （抱歉，我不知道任何颜色理论，但我正在寻找的可能是一个词。）这是一个典型的拼图的样子：
我已经可以通过 adb 截屏，从块中提取 RGB 矩阵并标记哪些块是 "fixed"。我在解决这个问题的实际算法部分时遇到了麻烦。
这是我目前所做的：
- 将 RGB 转换为 HSV 并在一维列表中按色调对颜色进行排序。这给了我一个光谱，但我不知道如何将这个结果转换成二维。
- 保留 RGB 颜色并尝试使用单一颜色。我可以在这里做一些多变量微积分，但困难在于某些颜色共享一个或多个 RGB 值这一事实。有必要考虑所有三种颜色。
- 使用欧氏距离求出每对颜色之间的距离。我知道最终目标是让这个距离在相邻颜色中最小，但二维网格让这变得更加困难。
- 使用欧几里德距离，我通过查看相邻块颜色的欧几里德距离开发了一个衡量特定网格理想程度的指标。但是，我找不到一种有效的算法来计算出达到理想状态所需的交换。
如果您有更多 solved 图像，您可以创建 RGB 图 plot
所以绘制 3D 图，其中 x,y 是像素位置，z 是检查的颜色通道（R、G 或 B）。从中您可以确定渐变的一些属性。如果情节是一个平面，那么你所需要的只是正常的（取自 3 个已知单元格）。如果它是曲面，取决于它有多少个拐点，你可以确定它使用了多大的多项式。从这一切你可以开始解决这个问题。
我会从一些简单的事情开始（假设没有太大的差距或花哨的多项式）：
分别处理每个颜色通道。我会只使用静态图块并仅从它们中插入网格颜色。类似于：
没有看到 R,G,B 图表，我无法估计您需要哪种插值。如果图形是线性的，则使用双线性或线性插值。如果不使用高阶多项式。
因此请尽可能填写任何网格单元格（具有已知颜色的邻居）。在此之后找到最接近计算颜色的可移动图块（如果单元格已对所有 3 个通道进行插值）并放置它们（并设置为静态）。
现在只需重复该过程，直到计算完所有单元格。
[Edit1 Dec 14 2017] 一些额外的注释和内容
很好奇，今天有时间，所以我试了一下。首先，我用 C++/VCL 创建游戏，将您的图像作为输入（裁剪和调整大小）。然后我手动对图块进行排序并绘制图表：
白点表示图块放置正确（匹配插值颜色）。点周围的彩色圆圈是插值颜色（为了进行视觉比较，您需要缩放才能看到它们）。
如您所见，R、G、B 3D 图看起来是线性的，因此（双）线性插值应该足够了。
如果我尝试对行进行线性插值，则求解器会立即解决难题。但是，当我为列（已知单元格之间有更多未知单元格）编写相同的代码时，求解器开始进行一些不正确的放置（使整个内容无效，因此出现错误的白点）。
我也试过HSL但是过了一会儿我因为撞墙扔掉了因为Hue可以穿过0 和 360 度，这与没有交叉的情况没有区别。为此，它需要从邻近的已解决区域进行一些启发式或交叉关联，这对我来说编码太多了。没有它，结果比使用 RGB.
更糟糕
所以现在我正在考虑要么使用双线性插值，要么先解决短距离插值，然后再解决其余的...
[Edit2 Dec 14 2017] 双线性插值
看起来双线性RGB插值解决了所有问题。因此，如果您的电路板附有固定电池，它应该可以工作。如果不是，您需要迭代地解决电路板，然后使用新解决的单元格作为未解决区域的新边界。我还意识到我得到了 RGB 反转所以我也修复了它:)。
这里是游戏的 C++/VCL 源代码（完全没有优化）：
//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
//---------------------------------------------------------------------------
TForm1 *Form1;
bool _update=false;
//---------------------------------------------------------------------------
const _ILoveHue_state_fixed =255<<24;
const _ILoveHue_state_unsolved= 0<<24;
const _ILoveHue_state_solved = 1<<24;
const _ILoveHue_render_board=0;
const _ILoveHue_render_graph=1;
//---------------------------------------------------------------------------
int rgbdist(DWORD c0,DWORD c1) // AABBGGRR
{
int r0,g0,b0,r1,g1,b1;
r0=( c0 &255); r1=( c1 &255);
g0=((c0>> 8)&255); g1=((c1>> 8)&255);
b0=((c0>>16)&255); b1=((c1>>16)&255);
r0-=r1; g0-=g1; b0-=b1;
return (r0*r0)+(g0*g0)+(b0*b0);
}
//---------------------------------------------------------------------------
class ILoveHue
{
public:
// variables
bool _redraw; // redraw needed?
Graphics::TBitmap *bmp; // screen buffer
int sxs,sys,mxs,mys,gxs,gys;// screen,map,grid cell resolution
DWORD **map,**imap; // map[y][x] actual and interpolated
int mx,my,mx0,my0; // mouse position state actual and last
TShiftState sh,sh0; // mouse buttons and spec keys state actual and last
int render_mode;
// class constructors and destructors
ILoveHue() { bmp=new Graphics::TBitmap; bmp_resize(1,1); map=NULL; imap=NULL; mxs=0; mys=0; mx=-1; my=-1; mx0=-1; my0=-1; gxs=1; gys=1; render_mode=_ILoveHue_render_board; }
~ILoveHue() { map_free(); if (bmp) delete bmp; }
ILoveHue(ILoveHue& a) { *this=a; }
ILoveHue* operator = (const ILoveHue *a) { *this=*a; return this; }
//ILoveHue* operator = (const ILoveHue &a) { ...copy... return this; }
// game/Window API and stuff
void map_free() // relese map
{
if ( map) { if ( map[0]) delete[] map[0]; delete[] map; } map=NULL; mxs=0; mys=0;
if (imap) { if (imap[0]) delete[] imap[0]; delete[] imap; } imap=NULL;
}
void map_resize(int x,int y) // resize/allocate map
{
_redraw=true;
if ((x==mxs)&&(y==mys)) return; map_free();
map=new DWORD*[y]; if ( map==NULL) return; map[0]=new DWORD[x*y]; if ( map[0]==NULL) return;
imap=new DWORD*[y]; if (imap==NULL) return; imap[0]=new DWORD[x*y]; if (imap[0]==NULL) return;
mxs=x; mys=y; for (x=mxs,y=1;y<mys;y++,x+=mxs) { map[y]=map[0]+x; imap[y]=imap[0]+x; }
if (mxs) gxs=sxs/mxs; else gxs=1;
if (mys) gys=sys/mys; else gys=1;
}
void bmp_resize(int x=-1,int y=-1) // resize bmp
{
_redraw=true;
if ((x>=0)&&(y>=0)) bmp->SetSize(x,y);
bmp->HandleType=bmDIB;
bmp->PixelFormat=pf32bit;
sxs=bmp->Width;
sys=bmp->Height;
if (mxs) gxs=sxs/mxs; else gxs=1;
if (mys) gys=sys/mys; else gys=1;
}
void bmp_load(AnsiString file) // init game from image (map must be resized already)
{
_redraw=true;
// load file
bmp->LoadFromFile(file);
bmp_resize();
// convert to map
int x,y;
DWORD *p,c;
for (y=0;y<mys;y++)
for (p=(DWORD*)bmp->ScanLine[(y*gys)+(gys>>1)],x=0;x<mxs;x++)
{
c=p[(x*gxs)+(gxs>>1)+4]&0x00FFFFFF; // near mid point (0<<24 is unsolved state)
c=((c>>16)&0x000000FF) // RGB -> BGR (file has reverse RGB order than bmp)
|((c<<16)&0x00FF0000)
|( c &0x0000FF00);
map[y][x]=c;
c=p[(x*gxs)+(gxs>>1)]&0x00FFFFFF; // mid point
if ((((c)|(c>>8)|(c>>16))&255)<64) // ~max(R,G,B)<32
map[y][x]|=_ILoveHue_state_fixed;
}
}
void mouse(int x,int y,TShiftState s) // handle mouse
{
_redraw=true;
mx=x/gxs;
my=y/gys;
sh0=sh; sh=s;
bool q0=sh0.Contains(ssLeft);
bool q1=sh .Contains(ssLeft);
if ((!q0)&&( q1)){ mx0=mx; my0=my; } // mouse left button down
if (( q0)&&(!q1)) // mouse left button up (swap)
{
// swap if valid coordinates
if ((mx0>=0)&&(mx0<mxs)&&(my0>=0)&&(my0<mys)) if (DWORD(map[my0][mx0]&0xFF000000)!=_ILoveHue_state_fixed)
if ((mx >=0)&&(mx <mxs)&&(my >=0)&&(my <mys)) if (DWORD(map[my ][mx ]&0xFF000000)!=_ILoveHue_state_fixed)
{
DWORD c=map[my0][mx0]; map[my0][mx0]=map[my][mx]; map[my][mx]=c; // swap cells
map[my0][mx0]&=0x00FFFFFF; map[my0][mx0]|=_ILoveHue_state_unsolved; // set them as unsolved
map[my ][mx ]&=0x00FFFFFF; map[my ][mx ]|=_ILoveHue_state_unsolved;
map_solve(false); // check for solved state
}
// clear selection
mx0=-1; my0=-1;
}
}
void draw() // render game
{
_redraw=false;
int x,y,z,x0,x1,x2,y0,y1,y2,r;
DWORD c;
if (render_mode==_ILoveHue_render_board)
{
for (y0=0,y1=gys,y2=gys>>1,y=0;y<mys;y++,y0+=gys,y1+=gys,y2+=gys)
for (x0=0,x1=gxs,x2=gxs>>1,x=0;x<mxs;x++,x0+=gxs,x1+=gxs,x2+=gxs)
{
c=map[y][x];
bmp->Canvas->Pen->Color=TColor(c&0x00FFFFFF);
if ((x==mx )&&(y==my )) bmp->Canvas->Pen->Color=clYellow;
if ((x==mx0)&&(y==my0)) bmp->Canvas->Pen->Color=clGreen;
bmp->Canvas->Brush->Color=TColor(c&0x00FFFFFF);
bmp->Canvas->Rectangle(x0,y0,x1,y1);
if (DWORD(c&0xFF000000)!=_ILoveHue_state_fixed)
{
r=10;
bmp->Canvas->Pen->Color=imap[y][x]&0x00FFFFFF;
bmp->Canvas->Brush->Style=bsClear;
bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
bmp->Canvas->Brush->Style=bsSolid;
}
if (DWORD(c&0xFF000000)!=_ILoveHue_state_unsolved)
{
if (DWORD(c&0xFF000000)==_ILoveHue_state_fixed ) c=clBlack;
if (DWORD(c&0xFF000000)==_ILoveHue_state_solved) c=clWhite;
r=4;
bmp->Canvas->Pen->Color=c;
bmp->Canvas->Brush->Color=c;
bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
}
}
}
if (render_mode==_ILoveHue_render_graph)
{
bmp->Canvas->Pen->Color=clBlack;
bmp->Canvas->Brush->Color=clBlack;
bmp->Canvas->Rectangle(0,0,sxs,sys);
r=13; x0=15; y0=sys-15;
int c=r*double(256.0*cos(55.0*M_PI/180.0));
int s=r*double(256.0*sin(55.0*M_PI/180.0));
bmp->Canvas->Pen->Color=clRed;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x])&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clGreen;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>8)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clBlue;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>16)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
}
}
}
// Solver
void map_solve(bool _solve) // check for solved state and try to solve if _solve is true
{
_redraw=true;
const int _thr=10; // color comparison threshold
int x,y,x0,x1,y0,y1,xx,yy;
int r0,g0,b0,r,g,b;
int r1,g1,b1;
int r2,g2,b2;
int r3,g3,b3;
DWORD c;
// compute interpolated colors to imap (wanted solution)
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
for (x0=-1,xx=x;xx>= 0;xx--) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x0=xx; break; }
for (x1=-1,xx=x;xx<mxs;xx++) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x1=xx; break; }
for (y0=-1,yy=y;yy>= 0;yy--) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y0=yy; break; }
for (y1=-1,yy=y;yy<mys;yy++) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y1=yy; break; }
c=0;
if (int(x0|x1|y0|y1)>=0)
{
// bilinear interpolation
c=map[y0][x0]; r0=c&255; g0=(c>>8)&255; b0=(c>>16)&255;
c=map[y0][x1]; r1=c&255; g1=(c>>8)&255; b1=(c>>16)&255;
c=map[y1][x0]; r2=c&255; g2=(c>>8)&255; b2=(c>>16)&255;
c=map[y1][x1]; r3=c&255; g3=(c>>8)&255; b3=(c>>16)&255;
r0=r0+(r1-r0)*(x-x0)/(x1-x0);
g0=g0+(g1-g0)*(x-x0)/(x1-x0);
b0=b0+(b1-b0)*(x-x0)/(x1-x0);
r1=r2+(r3-r2)*(x-x0)/(x1-x0);
g1=g2+(g3-g2)*(x-x0)/(x1-x0);
b1=b2+(b3-b2)*(x-x0)/(x1-x0);
r =r0+(r1-r0)*(y-y0)/(y1-y0);
g =g0+(g1-g0)*(y-y0)/(y1-y0);
b =b0+(b1-b0)*(y-y0)/(y1-y0);
c=(r)+(g<<8)+(b<<16);
}
imap[y][x]=c;
}
// compute solved state
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
map[y][x]&=0x00FFFFFF;
if (rgbdist(map[y][x],imap[y][x])<_thr) map[y][x]|=_ILoveHue_state_solved;
else map[y][x]|=_ILoveHue_state_unsolved;
}
// solver/checker
if (_solve)
{
// process all unsolved cells
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)==_ILoveHue_state_unsolved)
// find match in unsolved cells
for (xx=0;xx<mxs;xx++)
for (yy=0;yy<mys;yy++)
if (DWORD(map[yy][xx]&0xFF000000)==_ILoveHue_state_unsolved)
if (rgbdist(map[yy][xx],imap[y][x])<_thr)
{
// swap if found
c=map[yy][xx];
map[yy][xx]=map[y][x];
map[y][x]=(c&0x00FFFFFF)|_ILoveHue_state_solved;
}
}
}
} gam;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
gam.map_resize(7,9);
gam.bmp_load("map.bmp");
gam.map_solve(false);
_update=true;
ClientWidth=gam.sxs;
ClientHeight=gam.sys;
_update=false;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
gam.render_mode=_ILoveHue_render_board;
gam.draw();
gam.bmp->SaveToFile("map.bmp");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender){ gam.draw(); Canvas->Draw(0,0,gam.bmp); }
void __fastcall TForm1::FormResize(TObject *Sender){ if (_update) return; gam.bmp_resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::Timer1Timer(TObject *Sender){ if (gam._redraw) FormPaint(Sender); }
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormKeyDown(TObject *Sender, WORD &Key, TShiftState Shift)
{
if (Key=='S') gam.map_solve(true); // try to solve
if (Key=='M') { gam.render_mode^=1; gam._redraw=true; } // swap render modes
if (Key==115) gam.bmp->SaveToFile("screenshot.bmp"); // [F4] screenshot
}
//---------------------------------------------------------------------------
BDS2006中的一个单窗体应用，上面有一个40ms的定时器。所以只需添加事件...您可以忽略 VCL 渲染和 window 东西。重要的是里面的class和solve()函数。它用于正确放置检查和求解（取决于 _solve 布尔值）。这是输入图像 map.bmp
我没有编写适当的 save/load 状态函数，而是选择直接使用位图本身（浪费 space 但几乎没有代码工作）。
地图本身是 2D 32 位 DWORD 数组，形式为 SSBBGGRR hex 其中 SS 是单元格的标志（fixed/solved/unsolved).
这里用源码编译demo
阅读 readme.txt 了解更多信息。解决后的结果（按[S]）：
您可以（看不到）看到圆圈消失，因为双线性插值颜色与您的输入更匹配。
程序需要大小为 7x9 的网格图像的分辨率并不重要。颜色是从单元格的中点（黑点）和稍微向右（平铺颜色）采样的
为了提高效率，您可以做两件事：
add/use 包含未求解单元格的列表
不是遍历整个地图，而是仅遍历未解决的单元格列表。
通过三角搜索
将T(N^2)搜索转换为T((N^2)/2)
这仍然是O(N^2)，但是常数时间更小。
使用 3D RGB LUT table
对于大网格，您可以创建 32K 个条目 3D LUT table 以在 O(1) 中找到搜索到的匹配单元格。只需将 RGB 转换为 15 位颜色并使用
DWORD LUT[32][32][32];
where LUT[r][g][b]=row+(column<<16); 这样您就可以知道每种颜色的位置。所有未使用的颜色设置为 0xFFFFFFFF。这里有一个将此技术用于类似目的的示例：
- Effective gif/image color quantization?
在代码中查找 recolor[32][32][32]...粗略的 15 位颜色可能不足以用于此目的，因此您可能需要更多位，例如 18 位，从而产生 256K 条目，这仍然是可管理的。
创建此 LUT 将花费 O(N) 时间，但使用和维护它只需 O(1) 时间。
我不知道这是否可行。我只是为了好玩而写它，无法对其进行真正的测试。如果您尝试一下并发表评论，我们将不胜感激。
struct pixel
{
public int R;
public int G;
public int B;
public bool Fixed;
public pixel(int r, int g, int b, bool _fixed)
{
this.R = r; this.G = g; this.B = b; this.Fixed = _fixed;
}
public int DistanceSQ(pixel px)
{
int r = this.R - px.R;
int g = this.G - px.G;
int b = this.B - px.B;
return r * r + g * g + b * b;
}
public override string ToString()
{
return string.Format("{0} {1} {2} {3}", this.R, this.G, this.B, this.Fixed);
}
public override int GetHashCode()
{
return this.R.GetHashCode() ^ this.G.GetHashCode() ^ this.B.GetHashCode();
}
public override bool Equals(object obj)
{
pixel px = (pixel)obj;
return this.R == px.R && this.G == px.G && this.B == px.B;
}
}
static void sort(pixel[,] img)
{
List<pixel> lst = new List<pixel>();
foreach (pixel px in img)
if (!px.Fixed)
lst.Add(px);
int rows = img.GetLength(0);
int cols = img.GetLength(1);
while (lst.Count > 0)
for (int row = 0; row < rows; row++)
for (int col = 0; col < cols; col++)
if (!img[row, col].Fixed)
{
pixel[] neighbors = getFixedNeighbors(img, row, col, rows, cols).ToArray();
int min = int.MaxValue;
pixel nearest = new pixel();
foreach (pixel n in lst)
{
int dist = neighbors.Select((a) => a.DistanceSQ(n)).Sum();
if (dist < min)
{
min = dist;
nearest = n;
}
}
nearest.Fixed = true;
img[row, col] = nearest;
lst.Remove(nearest);
if (lst.Count == 0)
return;
}
}
private static IEnumerable<pixel> getFixedNeighbors(pixel[,] img, int row, int col, int rows, int cols)
{
for (int r = Math.Max(0, row - 1); r < Math.Min(row + 2, rows); r++)
for (int c = Math.Max(0, col - 1); c < Math.Min(col + 2, cols); c++)
if (img[r, c].Fixed)
yield return img[r, c];
}
//test
{
bool b0 = false; bool b1 = true;//for easy editing
{
pixel[,] img = new pixel[3, 4];
img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1);
img[0, 1] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0);
img[0, 2] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0);
img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1);
sort(img);
}
{
pixel[,] img = new pixel[3, 4];
img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1);
img[0, 1] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0);
img[0, 2] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0);
img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1);
sort(img);
}
}
代码很简单。它将未评级的保留在列表中，并在找到它的位置时将其删除。为了决定应该为一个位置选择哪种颜色，选择具有最小平方距离和的颜色。 Sqrt 不是必需的，因为我们只需要它进行比较。
"sort"是改变不固定像素位置的主要功能。此函数的输入是像素的行列数组。 "sort" 函数对该数组进行更改。
我目前正在从事一个爱好项目，以自动解决流行手机游戏 I Love Hue 中的一个谜题。游戏可用 here。
基本上，游戏的整个前提是给你一堆排列在网格中的彩色矩形块。您可以交换除少数固定块以外的大部分块，这些块用黑点标记。游戏的目的是交换周围的方块，从而获得二维色谱。对颜色进行排序，使每个块的颜色近似于其周围颜色的平均值。 （抱歉，我不知道任何颜色理论，但我正在寻找的可能是一个词。）这是一个典型的拼图的样子：
我已经可以通过 adb 截屏，从块中提取 RGB 矩阵并标记哪些块是 "fixed"。我在解决这个问题的实际算法部分时遇到了麻烦。
这是我目前所做的：
- 将 RGB 转换为 HSV 并在一维列表中按色调对颜色进行排序。这给了我一个光谱，但我不知道如何将这个结果转换成二维。
- 保留 RGB 颜色并尝试使用单一颜色。我可以在这里做一些多变量微积分，但困难在于某些颜色共享一个或多个 RGB 值这一事实。有必要考虑所有三种颜色。
- 使用欧氏距离求出每对颜色之间的距离。我知道最终目标是让这个距离在相邻颜色中最小，但二维网格让这变得更加困难。
- 使用欧几里德距离，我通过查看相邻块颜色的欧几里德距离开发了一个衡量特定网格理想程度的指标。但是，我找不到一种有效的算法来计算出达到理想状态所需的交换。
如果您有更多 solved 图像，您可以创建 RGB 图 plot
所以绘制 3D 图，其中 x,y 是像素位置，z 是检查的颜色通道（R、G 或 B）。从中您可以确定渐变的一些属性。如果情节是一个平面，那么你所需要的只是正常的（取自 3 个已知单元格）。如果它是曲面，取决于它有多少个拐点，你可以确定它使用了多大的多项式。从这一切你可以开始解决这个问题。
我会从一些简单的事情开始（假设没有太大的差距或花哨的多项式）：
分别处理每个颜色通道。我会只使用静态图块并仅从它们中插入网格颜色。类似于：
没有看到 R,G,B 图表，我无法估计您需要哪种插值。如果图形是线性的，则使用双线性或线性插值。如果不使用高阶多项式。
因此请尽可能填写任何网格单元格（具有已知颜色的邻居）。在此之后找到最接近计算颜色的可移动图块（如果单元格已对所有 3 个通道进行插值）并放置它们（并设置为静态）。
现在只需重复该过程，直到计算完所有单元格。
[Edit1 Dec 14 2017] 一些额外的注释和内容
很好奇，今天有时间，所以我试了一下。首先，我用 C++/VCL 创建游戏，将您的图像作为输入（裁剪和调整大小）。然后我手动对图块进行排序并绘制图表：
白点表示图块放置正确（匹配插值颜色）。点周围的彩色圆圈是插值颜色（为了进行视觉比较，您需要缩放才能看到它们）。
如您所见，R、G、B 3D 图看起来是线性的，因此（双）线性插值应该足够了。
如果我尝试对行进行线性插值，则求解器会立即解决难题。但是，当我为列（已知单元格之间有更多未知单元格）编写相同的代码时，求解器开始进行一些不正确的放置（使整个内容无效，因此出现错误的白点）。
我也试过HSL但是过了一会儿我因为撞墙扔掉了因为Hue可以穿过0 和 360 度，这与没有交叉的情况没有区别。为此，它需要从邻近的已解决区域进行一些启发式或交叉关联，这对我来说编码太多了。没有它，结果比使用 RGB.
所以现在我正在考虑要么使用双线性插值，要么先解决短距离插值，然后再解决其余的...
[Edit2 Dec 14 2017] 双线性插值
看起来双线性RGB插值解决了所有问题。因此，如果您的电路板附有固定电池，它应该可以工作。如果不是，您需要迭代地解决电路板，然后使用新解决的单元格作为未解决区域的新边界。我还意识到我得到了 RGB 反转所以我也修复了它:)。
这里是游戏的 C++/VCL 源代码（完全没有优化）：
//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
//---------------------------------------------------------------------------
TForm1 *Form1;
bool _update=false;
//---------------------------------------------------------------------------
const _ILoveHue_state_fixed =255<<24;
const _ILoveHue_state_unsolved= 0<<24;
const _ILoveHue_state_solved = 1<<24;
const _ILoveHue_render_board=0;
const _ILoveHue_render_graph=1;
//---------------------------------------------------------------------------
int rgbdist(DWORD c0,DWORD c1) // AABBGGRR
{
int r0,g0,b0,r1,g1,b1;
r0=( c0 &255); r1=( c1 &255);
g0=((c0>> 8)&255); g1=((c1>> 8)&255);
b0=((c0>>16)&255); b1=((c1>>16)&255);
r0-=r1; g0-=g1; b0-=b1;
return (r0*r0)+(g0*g0)+(b0*b0);
}
//---------------------------------------------------------------------------
class ILoveHue
{
public:
// variables
bool _redraw; // redraw needed?
Graphics::TBitmap *bmp; // screen buffer
int sxs,sys,mxs,mys,gxs,gys;// screen,map,grid cell resolution
DWORD **map,**imap; // map[y][x] actual and interpolated
int mx,my,mx0,my0; // mouse position state actual and last
TShiftState sh,sh0; // mouse buttons and spec keys state actual and last
int render_mode;
// class constructors and destructors
ILoveHue() { bmp=new Graphics::TBitmap; bmp_resize(1,1); map=NULL; imap=NULL; mxs=0; mys=0; mx=-1; my=-1; mx0=-1; my0=-1; gxs=1; gys=1; render_mode=_ILoveHue_render_board; }
~ILoveHue() { map_free(); if (bmp) delete bmp; }
ILoveHue(ILoveHue& a) { *this=a; }
ILoveHue* operator = (const ILoveHue *a) { *this=*a; return this; }
//ILoveHue* operator = (const ILoveHue &a) { ...copy... return this; }
// game/Window API and stuff
void map_free() // relese map
{
if ( map) { if ( map[0]) delete[] map[0]; delete[] map; } map=NULL; mxs=0; mys=0;
if (imap) { if (imap[0]) delete[] imap[0]; delete[] imap; } imap=NULL;
}
void map_resize(int x,int y) // resize/allocate map
{
_redraw=true;
if ((x==mxs)&&(y==mys)) return; map_free();
map=new DWORD*[y]; if ( map==NULL) return; map[0]=new DWORD[x*y]; if ( map[0]==NULL) return;
imap=new DWORD*[y]; if (imap==NULL) return; imap[0]=new DWORD[x*y]; if (imap[0]==NULL) return;
mxs=x; mys=y; for (x=mxs,y=1;y<mys;y++,x+=mxs) { map[y]=map[0]+x; imap[y]=imap[0]+x; }
if (mxs) gxs=sxs/mxs; else gxs=1;
if (mys) gys=sys/mys; else gys=1;
}
void bmp_resize(int x=-1,int y=-1) // resize bmp
{
_redraw=true;
if ((x>=0)&&(y>=0)) bmp->SetSize(x,y);
bmp->HandleType=bmDIB;
bmp->PixelFormat=pf32bit;
sxs=bmp->Width;
sys=bmp->Height;
if (mxs) gxs=sxs/mxs; else gxs=1;
if (mys) gys=sys/mys; else gys=1;
}
void bmp_load(AnsiString file) // init game from image (map must be resized already)
{
_redraw=true;
// load file
bmp->LoadFromFile(file);
bmp_resize();
// convert to map
int x,y;
DWORD *p,c;
for (y=0;y<mys;y++)
for (p=(DWORD*)bmp->ScanLine[(y*gys)+(gys>>1)],x=0;x<mxs;x++)
{
c=p[(x*gxs)+(gxs>>1)+4]&0x00FFFFFF; // near mid point (0<<24 is unsolved state)
c=((c>>16)&0x000000FF) // RGB -> BGR (file has reverse RGB order than bmp)
|((c<<16)&0x00FF0000)
|( c &0x0000FF00);
map[y][x]=c;
c=p[(x*gxs)+(gxs>>1)]&0x00FFFFFF; // mid point
if ((((c)|(c>>8)|(c>>16))&255)<64) // ~max(R,G,B)<32
map[y][x]|=_ILoveHue_state_fixed;
}
}
void mouse(int x,int y,TShiftState s) // handle mouse
{
_redraw=true;
mx=x/gxs;
my=y/gys;
sh0=sh; sh=s;
bool q0=sh0.Contains(ssLeft);
bool q1=sh .Contains(ssLeft);
if ((!q0)&&( q1)){ mx0=mx; my0=my; } // mouse left button down
if (( q0)&&(!q1)) // mouse left button up (swap)
{
// swap if valid coordinates
if ((mx0>=0)&&(mx0<mxs)&&(my0>=0)&&(my0<mys)) if (DWORD(map[my0][mx0]&0xFF000000)!=_ILoveHue_state_fixed)
if ((mx >=0)&&(mx <mxs)&&(my >=0)&&(my <mys)) if (DWORD(map[my ][mx ]&0xFF000000)!=_ILoveHue_state_fixed)
{
DWORD c=map[my0][mx0]; map[my0][mx0]=map[my][mx]; map[my][mx]=c; // swap cells
map[my0][mx0]&=0x00FFFFFF; map[my0][mx0]|=_ILoveHue_state_unsolved; // set them as unsolved
map[my ][mx ]&=0x00FFFFFF; map[my ][mx ]|=_ILoveHue_state_unsolved;
map_solve(false); // check for solved state
}
// clear selection
mx0=-1; my0=-1;
}
}
void draw() // render game
{
_redraw=false;
int x,y,z,x0,x1,x2,y0,y1,y2,r;
DWORD c;
if (render_mode==_ILoveHue_render_board)
{
for (y0=0,y1=gys,y2=gys>>1,y=0;y<mys;y++,y0+=gys,y1+=gys,y2+=gys)
for (x0=0,x1=gxs,x2=gxs>>1,x=0;x<mxs;x++,x0+=gxs,x1+=gxs,x2+=gxs)
{
c=map[y][x];
bmp->Canvas->Pen->Color=TColor(c&0x00FFFFFF);
if ((x==mx )&&(y==my )) bmp->Canvas->Pen->Color=clYellow;
if ((x==mx0)&&(y==my0)) bmp->Canvas->Pen->Color=clGreen;
bmp->Canvas->Brush->Color=TColor(c&0x00FFFFFF);
bmp->Canvas->Rectangle(x0,y0,x1,y1);
if (DWORD(c&0xFF000000)!=_ILoveHue_state_fixed)
{
r=10;
bmp->Canvas->Pen->Color=imap[y][x]&0x00FFFFFF;
bmp->Canvas->Brush->Style=bsClear;
bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
bmp->Canvas->Brush->Style=bsSolid;
}
if (DWORD(c&0xFF000000)!=_ILoveHue_state_unsolved)
{
if (DWORD(c&0xFF000000)==_ILoveHue_state_fixed ) c=clBlack;
if (DWORD(c&0xFF000000)==_ILoveHue_state_solved) c=clWhite;
r=4;
bmp->Canvas->Pen->Color=c;
bmp->Canvas->Brush->Color=c;
bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
}
}
}
if (render_mode==_ILoveHue_render_graph)
{
bmp->Canvas->Pen->Color=clBlack;
bmp->Canvas->Brush->Color=clBlack;
bmp->Canvas->Rectangle(0,0,sxs,sys);
r=13; x0=15; y0=sys-15;
int c=r*double(256.0*cos(55.0*M_PI/180.0));
int s=r*double(256.0*sin(55.0*M_PI/180.0));
bmp->Canvas->Pen->Color=clRed;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x])&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clGreen;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>8)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clBlue;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>16)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
}
}
}
// Solver
void map_solve(bool _solve) // check for solved state and try to solve if _solve is true
{
_redraw=true;
const int _thr=10; // color comparison threshold
int x,y,x0,x1,y0,y1,xx,yy;
int r0,g0,b0,r,g,b;
int r1,g1,b1;
int r2,g2,b2;
int r3,g3,b3;
DWORD c;
// compute interpolated colors to imap (wanted solution)
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
for (x0=-1,xx=x;xx>= 0;xx--) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x0=xx; break; }
for (x1=-1,xx=x;xx<mxs;xx++) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x1=xx; break; }
for (y0=-1,yy=y;yy>= 0;yy--) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y0=yy; break; }
for (y1=-1,yy=y;yy<mys;yy++) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y1=yy; break; }
c=0;
if (int(x0|x1|y0|y1)>=0)
{
// bilinear interpolation
c=map[y0][x0]; r0=c&255; g0=(c>>8)&255; b0=(c>>16)&255;
c=map[y0][x1]; r1=c&255; g1=(c>>8)&255; b1=(c>>16)&255;
c=map[y1][x0]; r2=c&255; g2=(c>>8)&255; b2=(c>>16)&255;
c=map[y1][x1]; r3=c&255; g3=(c>>8)&255; b3=(c>>16)&255;
r0=r0+(r1-r0)*(x-x0)/(x1-x0);
g0=g0+(g1-g0)*(x-x0)/(x1-x0);
b0=b0+(b1-b0)*(x-x0)/(x1-x0);
r1=r2+(r3-r2)*(x-x0)/(x1-x0);
g1=g2+(g3-g2)*(x-x0)/(x1-x0);
b1=b2+(b3-b2)*(x-x0)/(x1-x0);
r =r0+(r1-r0)*(y-y0)/(y1-y0);
g =g0+(g1-g0)*(y-y0)/(y1-y0);
b =b0+(b1-b0)*(y-y0)/(y1-y0);
c=(r)+(g<<8)+(b<<16);
}
imap[y][x]=c;
}
// compute solved state
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
map[y][x]&=0x00FFFFFF;
if (rgbdist(map[y][x],imap[y][x])<_thr) map[y][x]|=_ILoveHue_state_solved;
else map[y][x]|=_ILoveHue_state_unsolved;
}
// solver/checker
if (_solve)
{
// process all unsolved cells
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)==_ILoveHue_state_unsolved)
// find match in unsolved cells
for (xx=0;xx<mxs;xx++)
for (yy=0;yy<mys;yy++)
if (DWORD(map[yy][xx]&0xFF000000)==_ILoveHue_state_unsolved)
if (rgbdist(map[yy][xx],imap[y][x])<_thr)
{
// swap if found
c=map[yy][xx];
map[yy][xx]=map[y][x];
map[y][x]=(c&0x00FFFFFF)|_ILoveHue_state_solved;
}
}
}
} gam;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
gam.map_resize(7,9);
gam.bmp_load("map.bmp");
gam.map_solve(false);
_update=true;
ClientWidth=gam.sxs;
ClientHeight=gam.sys;
_update=false;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
gam.render_mode=_ILoveHue_render_board;
gam.draw();
gam.bmp->SaveToFile("map.bmp");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender){ gam.draw(); Canvas->Draw(0,0,gam.bmp); }
void __fastcall TForm1::FormResize(TObject *Sender){ if (_update) return; gam.bmp_resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::Timer1Timer(TObject *Sender){ if (gam._redraw) FormPaint(Sender); }
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormKeyDown(TObject *Sender, WORD &Key, TShiftState Shift)
{
if (Key=='S') gam.map_solve(true); // try to solve
if (Key=='M') { gam.render_mode^=1; gam._redraw=true; } // swap render modes
if (Key==115) gam.bmp->SaveToFile("screenshot.bmp"); // [F4] screenshot
}
//---------------------------------------------------------------------------
BDS2006中的一个单窗体应用，上面有一个40ms的定时器。所以只需添加事件...您可以忽略 VCL 渲染和 window 东西。重要的是里面的class和solve()函数。它用于正确放置检查和求解（取决于 _solve 布尔值）。这是输入图像 map.bmp
我没有编写适当的 save/load 状态函数，而是选择直接使用位图本身（浪费 space 但几乎没有代码工作）。
地图本身是 2D 32 位 DWORD 数组，形式为 SSBBGGRR hex 其中 SS 是单元格的标志（fixed/solved/unsolved).
这里用源码编译demo
阅读 readme.txt 了解更多信息。解决后的结果（按[S]）：
您可以（看不到）看到圆圈消失，因为双线性插值颜色与您的输入更匹配。
程序需要大小为 7x9 的网格图像的分辨率并不重要。颜色是从单元格的中点（黑点）和稍微向右（平铺颜色）采样的
为了提高效率，您可以做两件事：
add/use 包含未求解单元格的列表
不是遍历整个地图，而是仅遍历未解决的单元格列表。
通过三角搜索
将T(N^2)搜索转换为T((N^2)/2)这仍然是
O(N^2)，但是常数时间更小。使用 3D RGB LUT table
对于大网格，您可以创建 32K 个条目 3D LUT table 以在
O(1)中找到搜索到的匹配单元格。只需将 RGB 转换为 15 位颜色并使用DWORD LUT[32][32][32];where
LUT[r][g][b]=row+(column<<16);这样您就可以知道每种颜色的位置。所有未使用的颜色设置为0xFFFFFFFF。这里有一个将此技术用于类似目的的示例：- Effective gif/image color quantization?
在代码中查找
recolor[32][32][32]...粗略的 15 位颜色可能不足以用于此目的，因此您可能需要更多位，例如 18 位，从而产生 256K 条目，这仍然是可管理的。创建此 LUT 将花费
O(N)时间，但使用和维护它只需O(1)时间。
我不知道这是否可行。我只是为了好玩而写它，无法对其进行真正的测试。如果您尝试一下并发表评论，我们将不胜感激。
struct pixel
{
public int R;
public int G;
public int B;
public bool Fixed;
public pixel(int r, int g, int b, bool _fixed)
{
this.R = r; this.G = g; this.B = b; this.Fixed = _fixed;
}
public int DistanceSQ(pixel px)
{
int r = this.R - px.R;
int g = this.G - px.G;
int b = this.B - px.B;
return r * r + g * g + b * b;
}
public override string ToString()
{
return string.Format("{0} {1} {2} {3}", this.R, this.G, this.B, this.Fixed);
}
public override int GetHashCode()
{
return this.R.GetHashCode() ^ this.G.GetHashCode() ^ this.B.GetHashCode();
}
public override bool Equals(object obj)
{
pixel px = (pixel)obj;
return this.R == px.R && this.G == px.G && this.B == px.B;
}
}
static void sort(pixel[,] img)
{
List<pixel> lst = new List<pixel>();
foreach (pixel px in img)
if (!px.Fixed)
lst.Add(px);
int rows = img.GetLength(0);
int cols = img.GetLength(1);
while (lst.Count > 0)
for (int row = 0; row < rows; row++)
for (int col = 0; col < cols; col++)
if (!img[row, col].Fixed)
{
pixel[] neighbors = getFixedNeighbors(img, row, col, rows, cols).ToArray();
int min = int.MaxValue;
pixel nearest = new pixel();
foreach (pixel n in lst)
{
int dist = neighbors.Select((a) => a.DistanceSQ(n)).Sum();
if (dist < min)
{
min = dist;
nearest = n;
}
}
nearest.Fixed = true;
img[row, col] = nearest;
lst.Remove(nearest);
if (lst.Count == 0)
return;
}
}
private static IEnumerable<pixel> getFixedNeighbors(pixel[,] img, int row, int col, int rows, int cols)
{
for (int r = Math.Max(0, row - 1); r < Math.Min(row + 2, rows); r++)
for (int c = Math.Max(0, col - 1); c < Math.Min(col + 2, cols); c++)
if (img[r, c].Fixed)
yield return img[r, c];
}
//test
{
bool b0 = false; bool b1 = true;//for easy editing
{
pixel[,] img = new pixel[3, 4];
img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1);
img[0, 1] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0);
img[0, 2] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0);
img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1);
sort(img);
}
{
pixel[,] img = new pixel[3, 4];
img[0, 0] = new pixel(0, 0, 0, b1); img[1, 0] = new pixel(0, 1, 0, b0); img[2, 0] = new pixel(0, 2, 0, b1);
img[0, 1] = new pixel(2, 0, 0, b0); img[1, 2] = new pixel(2, 1, 0, b0); img[2, 2] = new pixel(2, 2, 0, b0);
img[0, 2] = new pixel(1, 0, 0, b0); img[1, 1] = new pixel(1, 1, 0, b0); img[2, 1] = new pixel(1, 2, 0, b0);
img[0, 3] = new pixel(3, 0, 0, b1); img[1, 3] = new pixel(3, 1, 0, b0); img[2, 3] = new pixel(3, 2, 0, b1);
sort(img);
}
}
代码很简单。它将未评级的保留在列表中，并在找到它的位置时将其删除。为了决定应该为一个位置选择哪种颜色，选择具有最小平方距离和的颜色。 Sqrt 不是必需的，因为我们只需要它进行比较。
"sort"是改变不固定像素位置的主要功能。此函数的输入是像素的行列数组。 "sort" 函数对该数组进行更改。