ERL-MPP: Evolutionary Reinforcement Learning with Multi-head Puzzle Perception for Solving Large-scale Jigsaw Puzzles of Eroded Gaps

📄 arXiv: 2504.09608v1 📥 PDF

作者: Xingke Song, Xiaoying Yang, Chenglin Yao, Jianfeng Ren, Ruibin Bai, Xin Chen, Xudong Jiang

分类: cs.CV

发布日期: 2025-04-13

备注: 9 pages, 5 figures

💡 一句话要点

提出ERL-MPP框架，解决带侵蚀间隙的大规模拼图难题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 拼图求解 进化强化学习 多头感知 图像组装 大规模拼图

📋 核心要点

  1. 现有拼图求解方法主要集中于小规模或无间隙拼图，无法有效解决大规模带间隙拼图难题。
  2. ERL-MPP框架通过多头拼图感知网络MPPN和进化强化学习EvoRL智能体，实现对带间隙拼图的有效感知和高效求解。
  3. 实验结果表明，ERL-MPP在JPLEG-5和MIT数据集上显著优于现有方法，证明了其有效性。

📝 摘要（中文）

本文提出了一种基于进化强化学习和多头拼图感知的框架（ERL-MPP），用于解决大规模带间隙的拼图难题。针对带间隙拼图的感知挑战，设计了一个具有共享编码器的多头拼图感知网络（MPPN），其中多个拼图头全面感知局部组装状态，判别器头提供拼图的全局评估。为了高效探索巨大的交换动作空间，设计了一个进化强化学习（EvoRL）智能体，其中actor基于感知的拼图状态从大型动作空间中推荐一组合适的交换动作，critic使用估计的奖励和拼图状态更新actor，评估器与进化策略相结合，根据历史组装经验进化动作。在具有大间隙的JPLEG-5数据集和大规模的MIT数据集上进行了全面评估，结果表明，所提出的ERL-MPP显著优于所有最先进的模型。

🔬 方法详解

问题定义：论文旨在解决大规模带侵蚀间隙的拼图难题。现有方法在处理此类问题时，面临图像理解和组合优化的双重挑战。图像理解方面，间隙的存在使得局部特征提取和匹配更加困难。组合优化方面，大规模拼图的交换动作空间巨大，难以高效搜索最优解。

核心思路：论文的核心思路是结合多头感知网络和进化强化学习，实现对拼图状态的全面感知和对动作空间的高效探索。多头感知网络用于提取拼图的局部和全局特征，进化强化学习用于学习最优的交换动作策略。

技术框架：ERL-MPP框架主要包含以下几个模块：1) 多头拼图感知网络（MPPN）：用于提取拼图的局部和全局特征，包括多个拼图头和一个判别器头。2) 进化强化学习（EvoRL）智能体：包含actor、critic和evaluator三个部分。Actor根据拼图状态推荐交换动作，critic评估动作的奖励并更新actor，evaluator使用进化策略优化动作。3) 拼图组装模块：根据actor推荐的动作执行拼图交换，并更新拼图状态。

关键创新：论文的关键创新在于：1) 提出了多头拼图感知网络MPPN，能够有效感知带间隙拼图的局部和全局特征。2) 设计了进化强化学习EvoRL智能体，能够高效探索大规模交换动作空间，并根据历史经验优化动作。3) 将多头感知网络和进化强化学习相结合，实现了对带间隙大规模拼图难题的有效求解。

关键设计：MPPN网络采用共享编码器，减少了参数量，提高了训练效率。多个拼图头分别关注不同的局部组装状态，判别器头用于评估拼图的全局一致性。EvoRL智能体使用策略梯度方法更新actor，使用进化策略优化actor的动作选择。损失函数包括actor的策略梯度损失、critic的均方误差损失和判别器头的交叉熵损失。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

ERL-MPP在JPLEG-5数据集和MIT数据集上取得了显著的性能提升。在JPLEG-5数据集上，ERL-MPP的组装准确率比现有最佳方法提高了超过10%。在MIT数据集上，ERL-MPP也取得了类似的性能提升，证明了其在大规模拼图问题上的有效性。

🎯 应用场景

该研究成果可应用于文物修复、图像重建、生物信息学等领域。例如，在文物修复中，可以利用该方法自动拼接破碎的文物碎片。在图像重建中，可以用于恢复被遮挡或损坏的图像区域。在生物信息学中，可以用于组装基因序列。

📄 摘要（原文）

Solving jigsaw puzzles has been extensively studied. While most existing models focus on solving either small-scale puzzles or puzzles with no gap between fragments, solving large-scale puzzles with gaps presents distinctive challenges in both image understanding and combinatorial optimization. To tackle these challenges, we propose a framework of Evolutionary Reinforcement Learning with Multi-head Puzzle Perception (ERL-MPP) to derive a better set of swapping actions for solving the puzzles. Specifically, to tackle the challenges of perceiving the puzzle with gaps, a Multi-head Puzzle Perception Network (MPPN) with a shared encoder is designed, where multiple puzzlet heads comprehensively perceive the local assembly status, and a discriminator head provides a global assessment of the puzzle. To explore the large swapping action space efficiently, an Evolutionary Reinforcement Learning (EvoRL) agent is designed, where an actor recommends a set of suitable swapping actions from a large action space based on the perceived puzzle status, a critic updates the actor using the estimated rewards and the puzzle status, and an evaluator coupled with evolutionary strategies evolves the actions aligning with the historical assembly experience. The proposed ERL-MPP is comprehensively evaluated on the JPLEG-5 dataset with large gaps and the MIT dataset with large-scale puzzles. It significantly outperforms all state-of-the-art models on both datasets.