Comparing patterns

• US 20050169535A1
• Filed: 03/21/2003
• Published: 08/04/2005
• Est. Priority Date: 03/22/2002
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Stentiford, Frederick W M
• Granted Patent: US 7,570,815 B2
• Time in Patent Office: Days
• US Class Current: 382/218
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A first image (or other pattern) is represented by a first ordered set of elements A each having a value and a second pattern is represented by a second such set. A comparison of the two involves performing, for each of a plurality of elements x of the first ordered set the steps of selecting (103) from the first ordered set a plurality of elements x′ in the vicinity of the element x under consideration, selecting (102) an element y of the second ordered set and comparing the elements x′ of the first ordered set with elements y′ of the second ordered set (each of which has the same position relative to the selected element y′ of the second ordered set as a respective one x′ of the selected plurality of elements of the first ordered set has relative to the element x under consideration). The comparison itself 106 comprises comparing the value of each of the selected plurality of elements x′ of the first set with the value of the correspondingly positioned element y′ of the like plurality of elements of the second set in accordance with a predetermined match criterion to produce a decision that the plurality of elements of the first ordered set matches the plurality of elements of the second ordered set. The comparison is them repeated with a fresh selection of the plurality of elements x′ of the first set and/or a fresh selection of an element y of the second ordered set generating a similarity measure V as a function of the number of matches. Preferably, following a comparison resulting in a match decision, the next comparison is performed with a fresh selection of the plurality of elements x′ of the first set and the same selection of an element y of the second set.

Claims

1. A method of comparing a first pattern represented by a first ordered set of elements each having a value with a second pattern represented by a second ordered set of element each having a value, comprising performing, for each of a plurality of elements of the first ordered set the steps of:

(i) selecting from the first ordered set a plurality of elements in the vicinity of the element under consideration, the selected elements having, within the ordered set, respective mutually different positions relative to the element under consideration;

(ii) selecting an element of the second ordered set;

(iii) comparing the selected plurality of elements of the first ordered set with a like plurality of elements of the second ordered set each of which has within the second ordered set the same position relative to the selected element of the second ordered set as a respective one of the selected plurality of elements of the first ordered set has relative to the element under consideration, said comparison comprising comparing the value of each of the selected plurality of elements of the first ordered set with the value of the correspondingly positioned element of the like plurality of elements of the second ordered set in accordance with a predetermined match criterion to produce a decision that the plurality of elements of the first ordered set matches the plurality of elements of the second ordered set;

(iv) repeating said comparison with a fresh selection of the plurality of elements of the first ordered set and/or a fresh selection of an element of the second ordered set; and

(v) generating for the element under consideration a similarity measure as a function of the number of comparisons for which the comparison indicates a match.

2. A method according to claim 1 in which the plurality of elements of the first ordered set includes the element under consideration.

3. A method according to claim 1 in which the selection of the plurality of elements of the first ordered set is random or pseudo-random.

4. A method according to claim 1 in which the selection of an element of the second ordered set is random or pseudo-random.

5. A method according to claim 1 in which, following a comparison resulting in a match decision, a further comparison is performed with a fresh selection of the plurality of elements of the first ordered set and the same selection of an element of the second ordered set.

6. A method according to claim 1 in which, following a comparison resulting in a decision that there is no match, a further comparison is performed with a fresh selection of an element of the second ordered set and the same selection of the plurality of elements of the first ordered set.

7. A method according to claim 1, in which each value comprises a plurality of components.

8. A method according to claim 1, in which the comparison is performed a predetermined number of times.

9. A method according to claim 1, in which the similarity measure is a function of the number of comparisons for which the comparison indicates a match, excluding an initial number of comparisons.

10. A method according to claim 1 in which, when an element under consideration has resulted in a similarity measure indicative of a large number of matches and a further element of the first ordered set is to be considered, the first selection of an element of the second ordered set for comparison therewith is of that element of the second ordered set whose position, within the second ordered set, relative to an element of the second ordered set giving rise to said large number of matches, is the same as the position of the further element of the first ordered set relative to the previous element under consideration.