SOLVING THE JIGSAW PUZZLE PROBLEM IN LINEAR TIME
作者:
TOM ALTMAN,
期刊:
Applied Artificial Intelligence
(Taylor Available online 1989)
卷期:
Volume 3,
issue 4
页码: 453-462
ISSN:0883-9514
年代: 1989
DOI:10.1080/08839518908949937
出版商: Taylor & Francis Group
关键词: Jigsaw puzzles;shape encoding;shape matching
数据来源: Taylor
摘要:
We introduce an algorithm that efficiently matches (fits together) parts of boundaries of two-dimensional objects in order to assemble apictorial jigsaw puzzles. A rotation-independent shape encoding allows us to find the best (longest) match between two shapes in time proportional to the sum of the lengths of their representations. In order to find this match, we use Weiner's string matching technique combined with compact position trees to find, in linear time, the longest shared pattern between two strings. The shape matching procedure is then used by two greedy algorithms to assemble the apictorial jigsaw puzzles.
点击下载:
PDF (229KB)
返 回