Patent ID: 6453064
Filing Date: 2002-09-17
Classification: G06K

Abstract:
A common structure extraction apparatus for extracting, from two point sets of sequenced points, a set of points of a common portion between the two point sets as a common structure between two three-dimensional structures formed by the two point sets, comprising:an entire structure superposition section for relatively moving the two point sets in parallel and by rotating in accordance with partial matching information for partial matching between the two point sets to superpose the two point sets on each other; a common portion length calculation section for calculating a number of points paired with each other to form at least one common portion between the two point sets superposed on each other by said entire structure superposition section as a common portion length; a cumulative distance calculation section for accumulating distances between the points paired with each other to form the at least one common portion between the two point sets superposed on each other by said entire structure superposition section to obtain cumulative distance information for each of the at least one common portion; and a common portion extraction section for extracting from the at least one common portion between the two point sets an extracted common portion representing a common structure, based on maximizing the common portion length calculated by said common portion length calculation section while minimizing the cumulative distance information calculated by said cumulative distance calculation section.