arrays - 如何在二维中对颜色进行排序？

Question

我目前正在从事一个爱好项目，以自动解决流行的手机游戏 I Love Hue 中的谜题。游戏上线here .

基本上，游戏的整个前提是给你一堆排列在网格中的彩色矩形块。除了几个固定的块，你可以交换大部分块，这些块用黑点标记。游戏的目标是交换周围的块，以便获得二维的颜色光谱。颜色被排序，使得每个块的颜色大约是它周围颜色的平均值。 (对不起，我不知道任何颜色理论，但可能有一个词来说明我正在寻找的东西。)这是一个典型的谜题:



我已经能够通过 adb 截取屏幕截图，从块中提取 RGB 矩阵并标记哪些块是“固定的”。我在这个问题的实际算法部分遇到了麻烦。

这是我到目前为止所做的:

将 RGB 转换为 HSV 并按一维列表中的色调对颜色进行排序。这给了我一个光谱，但我不知道如何将这个结果转换成二维。

将颜色保留为 RGB 并尝试使用单一颜色。我可能在这里可以做一些多变量微积分，但困难在于某些颜色共享一个或多个 RGB 值。有必要考虑所有三种颜色。

使用欧几里得距离求出每对颜色之间的距离。我知道最终目标是让这个距离成为相邻颜色中最小的，但是二维网格使这变得更加困难。

使用欧几里德距离，我通过查看相邻块颜色的欧几里德距离，开发了一个衡量某个网格的理想程度的度量标准。但是，我找不到一种有效的算法来计算达到理想状态所需的交换。

Answer 1

如果您有更多 solved可以创建 RGB 图形绘图的图像

所以绘制 3D 图哪里x,y是像素位置和 z检查颜色 channel (R、G 或 B)。从中您可以确定梯度的一些属性。如果绘图是一个平面，那么您所需要的只是正常的(取自 3 个已知单元格)。如果它是曲面，取决于它有多少拐点，您可以确定使用了多大的多项式。从这一切你可以开始解决这个问题。

我会从简单的事情开始 (假设没有太大的差距或花哨的多项式):

分别处理每个颜色 channel 。我只会使用静态图块并仅从它们插入网格颜色。类似于:

Interpolating 3D Coordinates between known missing time intervals

没有看到 R,G,B 我无法估计您需要哪种插值。如果图形是线性的，请使用双线性或线性插值。如果不使用更高次多项式。

因此，尽可能填充任何网格单元格(具有已知颜色的邻居)。在此之后找到最接近计算颜色的可移动平铺(如果单元格插入了所有 3 个 channel )并放置它们(并设置为静态)。

现在只需重复该过程，直到计算出所有单元格。

[Edit1 Dec 14 2017] 一些额外的笔记和内容

很好奇，今天有时间，所以我试了一下。首先，我在 C++/VCL 中创建游戏，将您的图像作为输入(裁剪和调整大小)。然后我手动对瓷砖进行排序并绘制图形:



白点表示瓷砖放置正确(匹配内插颜色)。点周围的彩色圆圈是内插颜色(为了进行视觉比较，您需要放大才能看到它们)。

如您所见 R,G,B 3D 图看起来是线性的，所以(双)线性插值应该足够了。

如果我仅尝试对行进行线性插值，则求解器会立即解决难题。但是，当我为列(已知列之间的更多未知单元格)编码相同的代码时，求解器开始进行一些不正确的放置(使整个内容无效，因此出现错误的白点)。



我也试过 HSL 但过了一会儿，我因为撞到墙而把它扔掉了，因为 色相 可以穿越 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 渲染和窗口内容。重要的是类和 solve()在其中发挥作用。它用于正确放置检查和求解(取决于 _solve bool)。这是输入图像 map .bmp



我没有编写适当的保存/加载状态函数，而是选择直接使用位图本身(浪费空间但几乎没有代码工作)。

map 本身是 二维 32 位 DWORD形式为 SSBBGGRR hex 的数组哪里 SS是单元格的标志(固定/已解决/未解决)。

这里用源代码编译了demo

Win32 demo

阅读 readme.txt了解更多信息。这是求解后的结果(按 [S]):



由于双线性插值颜色与您的输入更匹配，因此您可以(不)看到圆圈消失。

程序期望大小为 7x9 的网格图像的分辨率并不重要。颜色从单元格的中点(黑点)和稍微向右(瓷砖颜色)采样

为了提高效率，您可以做两件事:

添加/使用包含未解析单元格的列表

而不是遍历整个 map ，只遍历 Unresolved 单元格列表。

转换 T(N^2)搜索到 T((N^2)/2)按三角形搜索

这还是O(N^2)但是，恒定时间较小。

使用 3D RGB LUT 表

对于大网格，您可以创建 32K 个条目 3D LUT 表在 O(1) 中查找搜索到的匹配单元格.只需将 RGB 转换为 15 位颜色并使用

DWORD LUT[32][32][32];

哪里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)时间。