METHOD OF INTEREST POINT MATCHING FOR IMAGES

• US 20100310177A1
• Filed: 05/06/2010
• Published: 12/09/2010
• Est. Priority Date: 05/06/2009
• Status: Active Grant

• Current Assignee: Terris Earth Intelligence Incorporated
• Original Assignee: University of New Brunswick
• Inventors: Xiong, Zhen, Zhang, Yun
• Granted Patent: US 9,020,274 B2
• Time in Patent Office: Days
• US Class Current: 382/201
• CPC Class Codes: G06T 2207/10032 Satellite or aerial image; Remote sensing
• CPC Class Codes: G06T 2207/30181 Earth observation
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/344 involving models
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A computer implemented method for point matching comprising providing a pair of images captured, selecting first and second sets of interest points from the images; constructing a control network of super points for each set of interest points; assigning a position, with respect to the closest network control point of each control network, to other interest points on the images; locating conjugate points for each other interest point of each set based on its assigned position; and adding the conjugate points to the control network.

Claims

1. A computer implemented method for point matching comprising:

(a) providing a pair of images captured;

(b) selecting first and second sets of interest points from the images;

(c) constructing a control network of super points for each set of interest points;

(d) assigning a position, with respect to the closest network control point of each control network, to other interest points on the images;

(e) locating conjugate points for each other interest point of each set based on its assigned position; and

(f) adding the conjugate points to the control network.

2. The method of claim 1 further comprising repeating steps (d) to (f).

3. The method of claim 2, wherein the images are selected from the group consisting of images captured with overlapping area.

4. The method of claim 1 wherein the set of interest points are image points which have an interest strength greater than a specified threshold.

5. The method of claim 4 wherein the conjugate points are tie points.

6. The method of claim 4 further comprising:

selecting a first start point and a first root point from the first set wherein the other points of the first set are leaf points;

calculating a first distance between the first start point and the first root point;

selecting a second start point and a second root point from the second set wherein the second start point and the second root point are selected such that the distance between them is closest to the first distance;

and wherein assigning a position to the other points comprises;

assigning a relative position and angle to each other point (leaf point) of each network by

calculating a distance between each leaf point of the set and the root point of the set; and

calculating for each leaf point of the set, an angle from a line formed by the start point of the set and the root point of the set, to a line formed by the leaf point and the root point of the set

for each control network, grouping each interest point from a set with the closest node of the control network by;

constructing a sub-control network for each network with the closest node and the interest points grouped with the node; and

,

conducting interest point matching between the two sub-control networks.

7. The method of claim 6 further comprising selecting the interest points with the smallest relative position and angle as tie points.

8. The method of claim 7 wherein the selecting of the sets of interest points comprises using a Harris algorithm.

9. A computer implemented method for point matching for a pair of images comprising:

(a) constructing two control networks using points from the images;

(b) assigning a relative position to control network points;

(c) conducting a correspondence search for points of the control networks;

(d) selecting a root and a start point for each control network wherein the root is the point within the network with the most number of correspondences;

(e) grouping interest points;

(f) constructing a sub-control network from each control network;

(g) assigning a relative position to sub-control network points; and

(h) generating a further control network.

10. The method of claim 9 wherein step (a) comprises:

receiving first and second super point sets;

selecting a super point from each super point set as a root; and

constructing a control network for each super point set.

11. The method of claim 10 wherein step (b) comprises:

selecting a leaf for the first control network wherein the leaf is a starting point;

using the distance between the root and the leaf in the second control network to determine a corresponding starting point in the other network; and

assigning a relative position (distance between root and leaf) and an angle (clockwise from the starting point) to points in each of the control networks.

12. The method of claim 11 wherein step (c) comprises:

locating a corresponding point in the second control network for every leaf point in the first control network; and

selecting tie points wherein the tie points are the closest points with the smallest position differences and the smallest angle differences and where the differences are less than corresponding thresholds.

13. The method of claim 12 wherein the steps of steps (a) to (c) are repeated in iterations.

14. The method of claim 12 wherein step (d) comprises:

using a K-Means clustering method to group interest points with the closest node of the control network.

15. The method of claim 14 wherein step (f) comprises:

for each control network, taking a node as the root together with all the interest points grouped with it and selecting its father node as the starting point, with the closest node of the control network.

16. The method of claim 15 wherein step (g) comprises:

for every interest point in each control network, assigning a relative position and angle to the point with respect to the closest control network point.

17. The method of claim 16 wherein step (h) comprises:

performing interest point matching between the two sub-control networks whose root nodes are correspondences wherein correspondences are defined as those interest points with the minimum difference in position and angle;

adding new correspondences to each control network to construct a larger network; and

iterating until no new correspondence is added to each control network.