半自動化拼圖系統

Abstract

本論文中，我們提出一個全新的半自動化拼圖系統，這個系統針對任何型態的拼圖進行還原，並且不受該拼圖的特性所限制，例如拼圖碎片的形狀、相鄰拼圖碎片的數目…等等。我們的系統利用拼圖碎片的形狀和顏色資訊來還原拼圖碎片，大致上，可以分成四個步驟。第一，從輸入影像中擷取出拼圖碎片。第二，將每一個拼圖碎片的形狀和顏色資訊擷取出來，並且利用這些資訊來建立形狀特徵序列 (shape feature string)和顏色特徵序列 (color feature string)。第三，針對每兩片拼圖碎片，利用形狀特徵序列和顏色特徵序列來找出能將這兩片拼圖碎片接合在一起的可能邊界，並計算這個邊界的相似度。第四、根據上個步驟求出來的相似度，將兩片具有最高相似度的拼圖碎片接合在一起，我們不斷地重複此步驟，直到該拼圖被完整還原。而在第四步驟當中，我們提供了一個使用者決策功能，讓使用者決定，每一次被挑選出來的拼圖碎片是否確實可以被接合在一起。藉由這個功能，我們就能完整的將拼圖碎片還原成原始拼圖。 我們使用真實世界的拼圖和人為產生的拼圖對我們的系統進行測試。實驗結果證明我們的系統可以有效的將任何型態的拼圖還原成原始圖片。

This thesis proposes a new technique on puzzle solving. The novelty of the proposed technique is that it provides a semi-automatic puzzle solution which can reconstruct all kinds of puzzles without any initial restriction about the shapes of pieces, the number of neighbor pieces, etc. This technique uses both shape and color information to cope with the puzzle solving problem and consists of four steps. First, puzzle pieces are extracted from the input image. Second, shape and color features are extracted from each puzzle piece to form the shape and color feature strings. Third, the possible common boundary of each pair of puzzle pieces is found and its similarity measure is estimated by using their shape and color feature strings. Fourth, based on the similarity measure of each pair of pieces, a recurrent procedure is applied; it merges puzzle pieces with the largest similarity measure in pair until the original puzzle image is reformed. In the merging step, we provide a simple user interactive method, which allows a user to decide if each pair of pieces selected by the solver is adjacent or not. Our solver will select another pair of puzzle pieces which may be adjacent as soon as the user decides previous selected pieces are not adjacent pieces. This method makes our solver be able to restore puzzle pieces completely. And a user can easily reconstruct a puzzle through our puzzle solver. We tested this technique by employing real-world and artificial puzzle images containing dozens of pieces. The experimental results show that our technique is efficient and effective for restoring all kinds of puzzles.