使用输出知识解决真正的拼图游戏
Solving a real jigsaw puzzle with knowledge of the output
我想通过算法 运行 解决 Java 维度 n*m 的真实拼图游戏。实际输出，即图像是事先已知的。到目前为止，这些是我的想法。
在一张纸上对齐所有拼图，这张纸的颜色不是拼图本身的颜色，然后拍照。
将所有片段裁剪成 n*m 个子图像。
获取每张纸的每个像素点的RGB值，忽略包含纸张颜色的像素（考虑每张纸的特殊形状）
从实际输出图像中得到n*m个子图像
这就是我遇到问题的地方。如果我想比较拼图，如何考虑拼图形状？
综上所述，比较 RGB 值是否是一种有前途的方法？我将如何继续？是否有更好、更简单的方法，如 FFT 或某种方法？
感谢您的意见！
您正在寻找模板匹配（在另一个图像（原始图像）中查找图像（拼图））。
您可以遍历您的片段并将每个片段滑动到原始图像（按片段大小的步长）比较所有像素的相似性。如果你需要旋转棋子，你需要存储4个值（每个位置的方向）。
最大相似度将为您提供正确的位置方向。如果这些片段是从原始图像中裁剪出来的（并且具有相同的质量、相对大小），您将期望为每一个片段找到一个完美的匹配。
对于图像比较，最简单的方法是存储每个像素的聚合 RGB 距离，参见 here, or pHash (on java here)。
由于在普通的拼图游戏中，棋子不是矩形（形状有些不规则），所以在比较时，请确保您只比较原始图像的重叠部分（可通过多种方式实现）。
仅供参考：解决拼图游戏是 NP 完全的（请参阅相关论文 here）（想象最坏的情况，图像完全是纯绿色，没有形状，什么都没有；因此输出可能不提供任何线索:)
仅供参考 2：曾经有 Eternity Puzzle contest with real money prize, where winners (mathematicians) solved it in 7 months using two domestic PCs. Then Eternity II，没有赢家！
所以你明白这是一个艰巨的项目！
第一想法:
我会先尝试依次添加每个片段
几何学（这件作品在哪里紧密贴合？），
按颜色（以防不同的零件放在同一个地方）。
为此，您将保留一张图片，其中放置了先前的棋子，并保留了背景色。
在尝试新棋子之前，您必须获得自由区域的边界，这是一条曲线。 （添加一块后，可以在本地更新这条曲线）。
然后取一块并在其轮廓上选择一个点。通过在曲线上扫过这个点，你可以找到一个适合的地方，有明显的重叠。保留实现最长合身的那一块。
如果是平局（或准平局），请使用相似度分数（例如 SAD）检查颜色。
不过这会非常耗时。
再想:
现在可能有办法知道碎片的确切方向（除非轮廓的某些部分保证是 horizontal/vertical）。尝试不同的角度会使 运行 时间变差。
另一种方法是选择两个点，在一块的轮廓上相隔一些已知的距离。然后你在边界曲线上滑动第一个点并找到另一个点的位置，在轮廓上向前并遵守距离约束。
更新:
如果所有的碎片都相同，几何搜索就变得无关紧要了。但好消息是棋子的放置变得高度可预测（棋子只是在规则的网格上）。
所以每一块都可以在想要的地方依次尝试，正确的匹配是基于已知图像的颜色，或者相邻块的颜色，沿着公共边).
建议将达到最佳匹配的棋子放在最前面，以尽量减少错误匹配的概率。
如果您的图像质量足够好，那么只有在给定的插槽中可以放入多张图片时，您才可能解决看图片的问题。以下伪代码可能有效：
获取作品轮廓，使用高对比度背景照片方法，并确保补偿任何镜头失真。
通过识别所有外环部件（具有一个或两个直边）并将它们的形状与所有其他部件匹配来构建外环。考虑当两个部分紧贴在一起时的匹配：最小化 (overlapArea + emptyArea)，其中 overlapArea 是一个接一个放置时的重叠量，emptyArea 自由 space 当它们彼此相邻放置时，它们之间。使用颜色信息打破平局（和接近平局）。将最初的 4 个角与盒子上的图像相匹配应该相对简单。
通过取一个现有的环角并找到下一个要放置到该角的棋子来构建连续的环（放置的棋子将有 2 个邻居）。在第 2 步结束时，将有 4 个角。在那个角落放置另一个棋子后，将有 5 个。只需继续在角落放置棋子，直到最后一个棋子适合最后一个 space.
此方法的几何部分需要两个要素：
获取图像轮廓：
- 校正畸变（相机在侧面附近引入球形畸变；另外，如果照片不是从碎片正上方拍摄的，透视图可能会关闭）。 总的来说这并不容易，请在单独的问题中提问，让一些图像专家参与进来。
- 使用轮廓查找算法为每件作品找到轮廓几何形状。我已成功使用 marching squares 完成此任务。
要匹配图像轮廓，您可以使用几个快捷方式来过滤掉不良匹配。例如，匹配的边框必须具有 相似的长度，并且相反的方向。先匹配每对棋子的两个角（必须有相同的间距）；然后使用几何库（我推荐 JTS) to see how much they overlap, as defined by minimizing (overlapArea + emptyArea). You can find code to mix JTS and vertex-sequences here.
图像匹配部分还需要两个成分：
准备图像进行匹配：
- 修复块图像和方框图像中的失真。另外，请确保在与片图像相同的光照条件下拍摄方框图像，否则匹配会更加困难。这很难做到 - 再次，如果您需要详细信息，请在另一个问题中提问。
- 对每块的中心像素绘制直方图，使用统一的半径保证不包含任何块边界。这是旋转不变的。
- 根据方框图像从棋子的中心取相同的直方图。请注意，大多数拼图遵循相当严格的网格，具有相同的 spaced 行和列。在执行此操作之前，您需要输入或检测网格尺寸。
在确定一块是否在某个点匹配时，检查比较其中心的颜色直方图与该网格位置的预期框直方图。例如，使用均方误差作为匹配指标。也就是说，如果你有两对红色、绿色和蓝色直方图（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]).
只使用几何图形只有在所有棋子都是独一无二的情况下才有效，而通常情况并非如此（有几个谜题一遍又一遍地重复使用棋子的轮廓）。 image-only 只有在没有重复图案的情况下才有效，例如大面积的天空或树木或 windows 或砖石。通用方法必须使用两种信息来源才能成功。
编辑以添加一些图像匹配，因为考虑到 OP
链接的拼图示例，仅几何图形是不够的
我想通过算法 运行 解决 Java 维度 n*m 的真实拼图游戏。实际输出，即图像是事先已知的。到目前为止，这些是我的想法。
在一张纸上对齐所有拼图，这张纸的颜色不是拼图本身的颜色，然后拍照。
将所有片段裁剪成 n*m 个子图像。
获取每张纸的每个像素点的RGB值，忽略包含纸张颜色的像素（考虑每张纸的特殊形状）
从实际输出图像中得到n*m个子图像
这就是我遇到问题的地方。如果我想比较拼图，如何考虑拼图形状？
综上所述，比较 RGB 值是否是一种有前途的方法？我将如何继续？是否有更好、更简单的方法，如 FFT 或某种方法？
感谢您的意见！
您正在寻找模板匹配（在另一个图像（原始图像）中查找图像（拼图））。
您可以遍历您的片段并将每个片段滑动到原始图像（按片段大小的步长）比较所有像素的相似性。如果你需要旋转棋子，你需要存储4个值（每个位置的方向）。
最大相似度将为您提供正确的位置方向。如果这些片段是从原始图像中裁剪出来的（并且具有相同的质量、相对大小），您将期望为每一个片段找到一个完美的匹配。
对于图像比较，最简单的方法是存储每个像素的聚合 RGB 距离，参见 here, or pHash (on java here)。
由于在普通的拼图游戏中，棋子不是矩形（形状有些不规则），所以在比较时，请确保您只比较原始图像的重叠部分（可通过多种方式实现）。
仅供参考：解决拼图游戏是 NP 完全的（请参阅相关论文 here）（想象最坏的情况，图像完全是纯绿色，没有形状，什么都没有；因此输出可能不提供任何线索:)
仅供参考 2：曾经有 Eternity Puzzle contest with real money prize, where winners (mathematicians) solved it in 7 months using two domestic PCs. Then Eternity II，没有赢家！ 所以你明白这是一个艰巨的项目！
第一想法:
我会先尝试依次添加每个片段
几何学（这件作品在哪里紧密贴合？），
按颜色（以防不同的零件放在同一个地方）。
为此，您将保留一张图片，其中放置了先前的棋子，并保留了背景色。
在尝试新棋子之前，您必须获得自由区域的边界，这是一条曲线。 （添加一块后，可以在本地更新这条曲线）。
然后取一块并在其轮廓上选择一个点。通过在曲线上扫过这个点，你可以找到一个适合的地方，有明显的重叠。保留实现最长合身的那一块。
如果是平局（或准平局），请使用相似度分数（例如 SAD）检查颜色。
不过这会非常耗时。
再想:
现在可能有办法知道碎片的确切方向（除非轮廓的某些部分保证是 horizontal/vertical）。尝试不同的角度会使 运行 时间变差。
另一种方法是选择两个点，在一块的轮廓上相隔一些已知的距离。然后你在边界曲线上滑动第一个点并找到另一个点的位置，在轮廓上向前并遵守距离约束。
更新:
如果所有的碎片都相同，几何搜索就变得无关紧要了。但好消息是棋子的放置变得高度可预测（棋子只是在规则的网格上）。
所以每一块都可以在想要的地方依次尝试，正确的匹配是基于已知图像的颜色，或者相邻块的颜色，沿着公共边).
建议将达到最佳匹配的棋子放在最前面，以尽量减少错误匹配的概率。
如果您的图像质量足够好，那么只有在给定的插槽中可以放入多张图片时，您才可能解决看图片的问题。以下伪代码可能有效：
获取作品轮廓，使用高对比度背景照片方法，并确保补偿任何镜头失真。
通过识别所有外环部件（具有一个或两个直边）并将它们的形状与所有其他部件匹配来构建外环。考虑当两个部分紧贴在一起时的匹配：最小化
(overlapArea + emptyArea)，其中overlapArea是一个接一个放置时的重叠量，emptyArea自由 space 当它们彼此相邻放置时，它们之间。使用颜色信息打破平局（和接近平局）。将最初的 4 个角与盒子上的图像相匹配应该相对简单。通过取一个现有的环角并找到下一个要放置到该角的棋子来构建连续的环（放置的棋子将有 2 个邻居）。在第 2 步结束时，将有 4 个角。在那个角落放置另一个棋子后，将有 5 个。只需继续在角落放置棋子，直到最后一个棋子适合最后一个 space.
此方法的几何部分需要两个要素：
获取图像轮廓：
- 校正畸变（相机在侧面附近引入球形畸变；另外，如果照片不是从碎片正上方拍摄的，透视图可能会关闭）。 总的来说这并不容易，请在单独的问题中提问，让一些图像专家参与进来。
- 使用轮廓查找算法为每件作品找到轮廓几何形状。我已成功使用 marching squares 完成此任务。
要匹配图像轮廓，您可以使用几个快捷方式来过滤掉不良匹配。例如，匹配的边框必须具有 相似的长度，并且相反的方向。先匹配每对棋子的两个角（必须有相同的间距）；然后使用几何库（我推荐 JTS) to see how much they overlap, as defined by minimizing
(overlapArea + emptyArea). You can find code to mix JTS and vertex-sequences here.
图像匹配部分还需要两个成分：
准备图像进行匹配：
- 修复块图像和方框图像中的失真。另外，请确保在与片图像相同的光照条件下拍摄方框图像，否则匹配会更加困难。这很难做到 - 再次，如果您需要详细信息，请在另一个问题中提问。
- 对每块的中心像素绘制直方图，使用统一的半径保证不包含任何块边界。这是旋转不变的。
- 根据方框图像从棋子的中心取相同的直方图。请注意，大多数拼图遵循相当严格的网格，具有相同的 spaced 行和列。在执行此操作之前，您需要输入或检测网格尺寸。
在确定一块是否在某个点匹配时，检查比较其中心的颜色直方图与该网格位置的预期框直方图。例如，使用均方误差作为匹配指标。也就是说，如果你有两对红色、绿色和蓝色直方图（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]).
只使用几何图形只有在所有棋子都是独一无二的情况下才有效，而通常情况并非如此（有几个谜题一遍又一遍地重复使用棋子的轮廓）。 image-only 只有在没有重复图案的情况下才有效，例如大面积的天空或树木或 windows 或砖石。通用方法必须使用两种信息来源才能成功。
编辑以添加一些图像匹配，因为考虑到 OP
链接的拼图示例，仅几何图形是不够的