GAを用いた方形ピースジグソーパズルの組立て

外山 史  東海林 健二  宮道 壽一  

誌名
電子情報通信学会論文誌 D   Vol.J89-D   No.4   pp.850-859
発行日: 2006/04/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 画像認識,コンピュータビジョン
キーワード: 
遺伝的アルゴリズム,  パズル組立て,  最適配置,  

本文: PDF(724KB)
>>論文を購入


あらまし: 
本論文では,方形ピースのジグソーパズルを組み立てる手法を提案する.ピースの形状は方形とし,パズルの表面は白と黒からなる2値画像とする.パズルの組立ては,ピースの輪郭線上の画素値の情報のみを用いて行われる.この問題は,類似したピースが多数存在するため,二つのピース間の局所的なマッチングでは解くことはできず大域的な探索が必要となる.本研究では,遺伝的アルゴリズム(GA)を用いて最適なピースの配置を求める.GAを用いる際,交叉や突然変異によって同じピースを重複して使用してはならないというパズルの制約条件を崩すことなく最適解を効率的に探索できるような,染色体のコーディング,交叉法を提案する.提案手法では9×9ピースのパズルの組立てに成功した.