用几何连续性解拼图,不依赖颜色形状,适合破损文物复原。
Nash Meets Wertheimer: Using Good Continuation in Jigsaw Puzzles
- 基于博弈论建模拼图为非合作多玩家游戏,求纳什均衡。
- 仅依赖线条连续性,在真实考古碎片上复原效果优于主流方法。
- 适合颜色形状失真严重的文物、壁画等脆弱图像重建。
拼图任务对计算机视觉构成挑战,需高层次的空间与语义推理。现有方法通常依赖颜色或形状信息,但在考古壁画等实际场景中,因碎片严重损毁,此类线索常不可靠,导致现有方法失效。相反,简单的几何线条模式在这些情况下反而成为有力线索。本文提出一种新拼图问题:刻意忽略颜色与形状,仅依赖线性几何模式进行重建。该过程基于格式塔感知组织的基本原则——韦特海默的“良好连续性”法则。为此,我们将拼图问题形式化为寻找非合作多玩家博弈的纳什均衡,并使用经典的多群体复制者动态求解。该方法通用性强,可处理任意形状、大小和方向的碎片。我们在合成数据与真实世界数据上评估,结果表明纯线条拼图本身具有内在复杂性,而所提博弈论框架表现出显著有效性。
原文摘要 · Abstract (English)
Jigsaw puzzle solving is a challenging task for computer vision since it requires high-level spatial and semantic reasoning. To solve the problem, existing approaches invariably use color and/or shape information but in many real-world scenarios, such as in archaeological fresco reconstruction, this kind of clues is often unreliable due to severe physical and pictorial deterioration of the individual fragments. This makes state-of-the-art approaches entirely unusable in practice. On the other hand, in such cases, simple geometrical patterns such as lines or curves offer a powerful yet unexplored clue. In an attempt to fill in this gap, in this paper we introduce a new challenging version of the puzzle solving problem in which one deliberately ignores conventional color and shape features and relies solely on the presence of linear geometrical patterns. The reconstruction process is then only driven by one of the most fundamental principles of Gestalt perceptual organization, namely Wertheimer's {\em law of good continuation}. In order to tackle this problem, we formulate the puzzle solving problem as the problem of finding a Nash equilibrium of a (noncooperative) multiplayer game and use classical multi-population replicator dynamics to solve it. The proposed approach is general and allows us to deal with pieces of arbitrary shape, size and orientation. We evaluate our approach on both synthetic and real-world data and compare it with state-of-the-art algorithms. The results show the intrinsic complexity of our purely line-based puzzle problem as well as the relative effectiveness of our game-theoretic formulation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。