Computer method and apparatus for matching between line drawings

Claim 2

In a computer system having a working memory storing (i) a first line drawing formed of a plurality of points, the points defining at least one drawing segment and (ii a second line drawing formed of at least one point, each point having a discrete position in a spatial coordinate system, apparatus for matching the position of each point form a non-empty first set of points defining a first drawing segment of the first line drawing to a point matched form a non-empty second set of points defining a second drawing segment of the second drawing, comprising: initial selection means for selecting a predetermined number of first working points from the first set of points and a same number of second working points from the second set of points, each working point representing the coordinate position of the corresponding selected point; initial association means coupled to the initial selection means for associating each first working point with a respective second working point; and a matcher coupled to the initial association means for determining correspondence of and thus matching the coordinate position of each non-selected point form the first set of points with the coordinate position of a matched point form the second set of points, the matcher performing a vector transformation of each non-selected point from the first set of points to a matched point from the second set of points, the vector transformation being defined by the working points as associated by the initial association means.

Claim 3

Apparatus as claimed in claim 1 wherein the initial association means includes a user interface for enabling a user to specify the association between the first working points and the second working points.

Claim 4

Apparatus as claimed in claim 1 wherein the second line drawing is a distortion of the first line drawing.

Claim 5

Apparatus as claimed in claim 1 wherein the second set of points has a different number of points than the firs set of points.

Claim 6

Apparatus as claimed in claim 1 wherein the matcher further provides a single match for each non-selected point from the first set of points with a non-selected point from the second set of points, by performing a ranking function.

Claim 7

Apparatus as claimed in claim 5 wherein the matcher further confirms matches between points from the first set of points and points from the second set of points by performing the ranking function.

Claim 8

Apparatus as claimed in claim 1 wherein the predetermined number is at least four.

Claim 9

Apparatus as claimed in claim 1 wherein the initial selection means includes a user interface for enabling a user to select at least one working point of the predetermined number of working points for each of the first and second set of points.

Claim 10

Apparatus as claimed in claim 8 wherein the user interface requires the user to select the predetermined number of second working points.

Claim 11

Apparatus as claimed in claim 1 wherein the matcher designates a first working point as a first origin point identifying the spatial coordinate system of the first set of points.

Claim 12

Apparatus as claimed in claim 10 wherein the second working point associated with the first origin point is designated as a second origin point identifying the spatial coordinate system of the second set of points.

Claim 13

Apparatus as claimed in claim 10 wherein the matcher includes a user interface for enabling a user to designate the first origin point.

Claim 14

Apparatus as claimed in claim 1 wherein the spatial coordinate system is a two-dimensional coordinate system.

Claim 15

Apparatus as claimed in claim 1 wherein the second drawing segment is of a different shape than the first drawing segment.

Claim 16

Apparatus as claimed in claim 1 wherein there are fewer than the predetermined number of points in an identified set of points, at least one point from the identified set of points is thus selected for a plurality of working points.

Claim 17

Apparatus as claimed in claim 13 wherein the identified set of points is the second set of points.

Claim 18

In a computer system having a working memory storing (i) a first line drawing formed of a plurality of points, the points defining at least one drawing segment and (ii) a second line drawing formed of at least one point, each point having a discrete position in a spatial coordinate system, a method of matching the position of each point from a non-empty first set of points defining a first drawing segment of the first line drawing to a matched point from a non-empty second set of points defining a second drawing segment of the second line drawing, comprising the steps of: selecting the coordinate position of a predetermined number of first working points from the first set of points and a same number of second working points from the second set of points, each working point representing the coordinate position of the corresponding selected point; associating each first working point with a respective second working point; defining a transform vector form the coordinate positions of the associated first and second working points, the transform vector providing a mathematical relationship between the coordinate positions of points in the first set of points and the coordinate positions of points in the second set of points; and determining correspondence of and thus matching the coordinate location of each non-selected point form the first set of points with the coordinate location of a matched point form the second set of points by applying the transform vector to each non-selected point in the first set of points.

Claim 19

In a computer system having a working memory storing (i) a first line drawing formed of a plurality of points, the points defining at least one drawing segment and (ii) a second line drawing formed of at least one point, each point having a discrete position in a spatial coordinate system, a method of matching the position of each point from a non-empty first set of points defining a first drawing segment of the first line drawing to a matched point from a non-empty second set of points defining a second drawing segment of the second line drawing, comprising the steps of: selecting the coordinate position of a predetermined number of first working points from the first set of points and a same number of second working points from the second set of points, each working point representing the coordinate position of the corresponding selected point; associating each first working point with a respective second working point; defining a transform vector form the coordinate positions of the associated first and second working points, the transform vector providing a mathematical relationship between the coordinate positions of points in the first set of points and the coordinate positions of points in the second set of points; and determining correspondence of and thus matching the coordinate location of each non-selected point form the first set of points with the coordinate location of a matched point form the second set of points by applying the transform vector to each non-selected point in the first set of points.

Claim 20

A method as claimed in claim 17 wherein the step of associating includes providing a user interface for enabling a user to specify the association between the first working points and the second working points.

Claim 21

A method as claimed in claim 17 further comprising the step of performing a ranking function to limit matching to a single match for each non-selected point from the first set of points with a non-selected point from the second set of points.

Claim 22

A method as claimed in claim 17 further comprising the step of performing a ranking function for confirming matches between non-selected points form the first set of points with non-selected points from the second set of points.

Claim 23

A method as claimed in claim 17 wherein the step of selecting includes selecting at least four first working points with a same number of second working points.

Claim 24

A method as claimed in claim 21 wherein the step of defining a transform vector includes calculating the transform vector from the equation ##EQU3## where is the transform vector; x 1 and Y 1 are vectors of a first one of the first working points, x 2 and y 2 are vectors of a second one of the first working points, x 3 and y 3 are vectors of a third one of the first working points, x' 1 and y' 1 are vectors of a first one of the second working points, x' 2 and y' 2 are vectors of a second one of the second working points, X' 3 and y' 3 are vectors of a third one of the second working points, each vector being in a two-dimensional spatial coordinate system, the first working point vectors being relative to the coordinate position of a fourth one of the first working points and the second working point vectors being relative to the coordinate position of a fourth one of the second working points.

Claim 25

A method as claimed in claim 17 wherein the step of selecting includes enabling a user to select at least one working point of the predetermined number of working points for each of the first and second set of points.

Claim 26

A method as claimed in claim 23 wherein the step of selecting further includes requiring the user to select the predetermined number of second working points.

Claim 27

A method as claimed in claim 17 wherein the step of defining includes designating a first working point as a first origin point to identify the spatial coordinate system of the first set of points.

Claim 28

A method as claimed in claim 25 wherein the step of defining further includes designating the working point associated with the first origin point as a second origin point to identify the spatial coordinate system of the second set of points.

Claim 29

A method as claimed in claim 25 wherein the step of designating includes enabling a user to designate the first origin point.

Claim 30

A method as claimed in claim 17 wherein there are fewer than the predetermined number of points in an identified set of points, the step of selecting including selecting at least one point form the identified set of points for a plurality of working points.

Claim 31

A method as claimed in claim 28 wherein the identified set of points is the second set of points.

Claim 32

In a computer system having a working memory storing (i) a first line drawing formed of a first plurality of points, the points defining at least one drawing segment and (ii) a second line drawing formed of a second plurality of points, each point having a discrete position in a two-dimensional spatial coordinate system, a method of matching the coordinate position of each point of the first line drawing to a matched point of the second line drawing, comprising the steps of: identifying at least one first drawing segment of the first line drawing, each first drawing segment defined by a non-empty first set of continuous points; identifying at least one second drawing segment of the second line drawing, each second drawing segment defined by a non-empty second set of continuous points; for each first drawing segment, matching the first set of points to one second set of point, the matching step comprising: a) selecting the position of four first working points form the first set of points and four second working points from the second set of points, each working point representing the coordinate position of the corresponding selected point; b) associating each first working point with a respective second working point; c) designating the two-dimensional coordinate systems such that the coordinate positions of the first working points are represented relative to the coordinate position of a designated one of the first working points and the coordinate positions of the second working points are represented relative to the coordinate position of a designated one of the second working points; d) defining a transform vector form the coordinate positions of the associated first and second working points, the transform vector providing a mathematical relationship between the coordinate positions of points in the first set of points and the coordinate positions of points in the second set of points; and e) determining correspondence of and thus matching the coordinate location of each remaining point from the first set of points with the coordinate location of a matched point form the second set of points by applying the transform vector to each non-selected point in the first set of points.

Claim 33

In a computer system having a working memory storing (i) a first line drawing formed of a first plurality of points, the points defining at least one drawing segment and (ii) a second line drawing formed of a second plurality of points, each point having a discrete position in a two-dimensional spatial coordinate system, a method of matching the coordinate position of each point of the first line drawing to a matched point of the second line drawing, comprising the steps of: identifying at least one first drawing segment of the first line drawing, each first drawing segment defined by a non-empty first set of continuous points; identifying at least one second drawing segment of the second line drawing, each second drawing segment defined by a non-empty second set of continuous points; for each first drawing segment, matching the first set of points to one second set of point, the matching step comprising: a) selecting the position of four first working points form the first set of points and four second working points from the second set of points, each working point representing the coordinate position of the corresponding selected point; b) associating each first working point with a respective second working point; c) designating the two-dimensional coordinate systems such that the coordinate positions of the first working points are represented relative to the coordinate position of a designated one of the first working points and the coordinate positions of the second working points are represented relative to the coordinate position of a designated one of the second working points; d) defining a transform vector form the coordinate positions of the associated first and second working points, the transform vector providing a mathematical relationship between the coordinate positions of points in the first set of points and the coordinate positions of points in the second set of points; and e) determining correspondence of and thus matching the coordinate location of each remaining point from the first set of points with the coordinate location of a matched point form the second set of points by applying the transform vector to each non-selected point in the first set of points.