图像局部区域匹配驱动的导航式拼图方法

Navigational Jigsaw Puzzle Driven by Local Image Region Matching

为了改善传统拼图拼接过程费时低效、影响拼图趣味性的问题,提出了一种图像局部区域匹配驱动的导航式拼图方法.首先,使用Canny边缘检测算法自动从输入的原始拼图中检测并分割出所有拼图模块.其次,采用D2分布函数和统计直方图,自动构造每个拼图模块的量化描述符.同时,使用属性邻接图描述原始拼图中所有拼图模块之间的拓扑邻接关系.之后,拼接过程中用户若需要帮助,根据用户动态传入(未拼接完成)的当前拼图,采用上述2步提取和描述当前拼图中所有的拼图模块,并基于描述符相似度计算、KM (Kuhn-Munkres)算法和属性邻接图拓扑关系一致性,在当前拼图和原始拼图之间建立拼图模块对应关系.最后,根据对应关系和原始拼图对应的属性邻接图,自动确定并提示用户当前拼图中下一可行的候选模块.开发了相应的原型系统,针对多个常见的拼图开展实验结果表明,所提方法对拼接过程帮助直观、高效,且未降低拼图的趣味性;与主流的电子拼图方法相比,无需实时跟踪,无需事先配备拼图数据库或训练库,可运行于具有拍摄功能的智能设备,适用性更加广泛.

To help users play the jigsaw puzzle more efficiently while enjoying the game, a navigational jigsaw puzzle method is proposed, which is driven by local image region matching. Firstly, all of the jigsaw puzzle pieces are automatically detected and segmented from an input original jigsaw puzzle image based on Canny algorithm. Secondly, the quantity descriptor for each jigsaw puzzle piece is automatically constructed by using D2 distribution function and statistical histogram graph. Meanwhile, the adjacent topological relationships among the above-mentioned pieces are described by developing an attributed adjacency graph. Now, when a user needs some help during the assembling process, the above two steps will be carried out on the current unfinished jigsaw puzzle image. After that, between the current jigsaw puzzle image and its original jigsaw puzzle image, the piece correspondence relationship will be established according to descriptor similarity, KM(Kuhn-Munkres) algorithm and adjacent topological relationship consistency. Finally, the next feasible candidate piece in the current jigsaw puzzle image will be automatically identified and prompted for the user based on the above correspondence relationship. To validate the proposed method, a corresponding prototype system is developed. Navigated jigsaw puzzle experiments also have been performed on the system with some typical jigsaw puzzle images. The results show that the proposed method,without decreasing the game enjoyments, is intuitive and efficient. Compared with the mainstream jigsaw puzzle methods, the proposed method does not need any real-time tracking or database, and can be worked on smart devices with cameras. Thus, it has the potential to be used more widely.