解决图片拼图问题！

Question

如果您想解决图片拼图问题，您会让计算机使用什么算法？

您可以从算法效率的角度进行讨论，但在这里，我真正关心的是应该采用哪些方法。

谢谢。

- Lazer

---

“图片拼图游戏”和“拼图游戏”是同一种游戏吗？ - user49117

拼图游戏还是滑块拼图？ - Nick Dandoulakis

我们可以假设（就像迄今为止发布的答案一样）每条边都可以精确匹配另一条边吗？这会大大简化事情。 - j_random_hacker

Answer 1

您需要做的是为拼图的每个面定义一个索引词汇，以便右侧面的索引可以告诉您相应左侧面的索引（例如，一个简单的词汇表：“凸面”和“凹面”，在一个面上使用“凸面”意味着匹配对面上使用“凹面”），然后根据索引词汇对每个拼图块进行分类。词汇表越精细，面匹配就越有区别性，算法运行速度就越快，不过您可以按照自己的实现方式来选择。（例如，“平边缘、直边向左倾斜、直边向右倾斜、凹面、凸面、旋钮、旋钮孔等）。我们假设索引方案抽象了边缘的实际形状，并且存在一个“完全匹配（piece1,edge1,piece2,edge2）”的谓词，仅当边缘完全匹配时才为真。我们进一步假设，一块拼图只与一个特定边缘完全匹配。

目标是扩展一组区域，例如一组连接的拼图块，直到无法再扩展为止。我们首先为所有拼图块标记唯一的区域名称，每个块一个，所有边缘均未匹配。然后我们以任意顺序枚举拼图块的边缘。对于每个枚举的拼图块P和边缘E，使用索引方案选择潜在匹配的拼图块/边缘对。检查完全匹配谓词；最多只有一块拼图块Q，其边缘F与之完全匹配。将P和Q的区域合并在一起形成一个大区域。重复此过程。我认为这样就解决了这个拼图问题。

- Ira Baxter

Answer 2

.1 找到2x2字节，以便四个边缘都可以配合。然后评估图像内容的匹配程度。

 
  P1 <--> P2
  ^       ^
  |       |
  v       v
  P3 <--> P4

.2 标记方向（手动或启发式），但仅将它们用作启发式得分（用于排名），而不是作为确定性搜索标准。

.3 形状上下文

- rwong

Answer 3

解决拼图问题基本上可以简化为将类似的边缘配对。在真正的拼图游戏中，只有一对拼图块能够沿着特定的边缘正确地锁合，每个拼图块都有角落，因此您知道特定侧的起点和终点。

因此，只需找到每个边缘的端点并选择一些控制点。然后迭代所有边缘未绑定的拼图块，直到找到正确的拼图块。当没有更多未绑定的边缘时，您已经解决了这个拼图问题。

- John Feminella

Answer 4

更进一步解释Ira Baxter的回答，另一个概念化问题的方式是将拼图看作一个图形，其中每个拼图块都是一个节点，每个接口都是一条边。

例如，如果您正在设计一个拼图游戏，以这种方式存储“答案”将使“检查是否合适”的代码更快，因为它可以缩减到某种哈希查找。

- Gregg Lind