java - 用输出知识解决真正的拼图游戏

Question

我想通过一个算法来解决java中的一个真正的n*m维拼图。实际输出，即图像是预先知道的这些是我目前的想法。
将所有拼图块对齐在一张纸上，该纸的颜色为拼图本身不包含的颜色，然后拍照。
将所有片段裁剪为n*m个子图像。
获取每块纸中每个像素的rgb值，忽略包含纸张颜色的像素（考虑每块纸的特殊形状）。
从实际输出图像中获取n*m个子图像。
这就是我遇到麻烦的地方如果我想比较这些拼图，我该如何考虑拼图的形状呢？
总之，比较rgb值是一种有前途的方法吗？我该怎么继续有没有更好的，更简单的方法，比如FFT或某种方法？
谢谢你的意见！

Answer 1

如果您的图像质量足够高，则只有当多个片段可以放入给定的槽中时，才能解决查看图片的问题。以下伪代码可能有效：
采用高对比度背景摄影法，确保补偿镜头的任何失真。
建立外环，通过识别所有外环件（一个或两个直边）和匹配他们的形状与所有其他。当两个部件紧贴在一起时考虑匹配：minimize(overlapArea + emptyArea)，其中overlapArea是一个接一个放置部件时的重叠量，emptyArea是相邻放置部件时的自由空间量使用颜色信息断开领带（和近领带）。将最初的4个角与框上的图像匹配应该相对简单。
建立一个连续的环，通过一个现有的环形角落，并找到下一块放在那个角落（其中放置的一块将有2个邻居）。在步骤2的末尾，将有4个角。在那个角落再放一块，就有5块了只需继续在角落里放几块，直到最后一块适合最后一个空间。
这种方法的几何部分需要两种成分：
获取图像轮廓：
校正失真（相机在侧面引入球形失真；如果照片不是从正上方拍摄，则透视可能会关闭）。这在一般情况下并不容易，单独问一个问题，让一些图像专家参与进来。
使用轮廓查找算法查找每个工件的轮廓几何图形我已经成功地将marching squares用于此任务。
要匹配图像轮廓，可以采取几个捷径来过滤不匹配的图像。例如，匹配的边框必须具有相似的长度和相反的方向首先匹配每对工件的两个角（必须具有相同的间隔）；然后使用几何库（我建议JTS）查看它们重叠的程度，如最小化(overlapArea + emptyArea)所定义的您可以找到混合jts和顶点序列的代码here。
图像匹配部分还需要两个成分：
准备要匹配的图像：
固定变形，无论是块图像还是盒图像另外，一定要在与单幅图像相同的光照条件下拍摄盒图像，否则匹配会更加困难这很难做到——再说一次，如果你需要细节的话，可以问另一个问题。
取每一块的中心像素的直方图，使用一个均匀的半径，保证不包含任何块边界这是旋转不变量。
根据盒子图像，从碎片的中心提取相同的直方图。请注意，大多数Jigsaw遵循相当严格的网格，行和列的间距相等在执行此操作之前，您需要输入或检测网格维度。
当决定一个工件是否在某个点上匹配时，检查比较其中心的颜色直方图和该网格位置的预期方框直方图。例如，使用均方误差作为匹配度量。也就是说，如果有两对红色、绿色和蓝色柱状图（r1、r2、g1、g2、b1、b2），每个柱状图有256个值（8bbp），每个值都是一个浮点值，用该像素强度计算对应圆中像素的分数，然后将所有差异平方并相加得出一个错误值：error = (R1[0]-R2[0])*(R1[0]-R2[0]) + ... + (B1[255]-B2[255])*(B1[255]-B2[255])。
只有当所有的片段都是唯一的时，几何才能工作，一般情况下不是这样的（几个谜题反复使用片段的轮廓）。只有在没有重复的图案，如大面积的天空、树木、窗户或砖石结构的情况下，图像才能正常工作。一般方法必须同时使用这两种信息源才能成功。
编辑以添加一些图像匹配，因为给定由OP链接的jigsaw示例，仅几何图形是不够的