Comparison of patterns

• US 7,574,051 B2
• Filed: 06/01/2006
• Issued: 08/11/2009
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Stentiford, Frederick W M
• Primary Examiner(s): Bella; Matthew C
• Assistant Examiner(s): Bayat; Ali
• Application Number:
  US11/916,475
• Publication Number:
  US 20080205760A1
• Time in Patent Office: 1,167 Days
• Field of Search: 382/100, 382/181, 382/218, 382/219, 382/144, 382/305, 382/274, 358/1.9, 707/100
• US Class Current: 382/218
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 2201/11 Technique with transformation invariance effect

Abstract

A first visual image or other pattern (A) is represented by a first ordered set of elements (x_i) each having a value and a second pattern (B) is a represented by a second ordered set of element (u_i) each having a value. Iteratively, a comparison is made by: (i) selecting a plurality of elements from the first ordered set;(ii) for each selected element of the first ordered set, selecting an element from the second ordered set, such that the selected elements of the second ordered set have, within the second ordered set, a set of positional relationships relative to each other that is the same as, or a transformation of, the set of positional relationships that the selected plurality of elements of the first ordered set have relative to each other; (iii) selecting a random shift value (γ); and (iv) determining whether the selected elements meet the match criterion that the value of each of the selected elements of the first ordered set differs from the value of the correspondingly positioned selected element of the second ordered set by an amount that is equal to, or within a set margin of, and in the same sense as, said shift value. In the event of a match, a similarity score (S_AB) is updated. Alternatively, or in addition, the shift amount in the event of a match is recorded and, at the conclusion of the iteration, a single representative shift value is estimated from said recorded shift value.

Claims

1. A method of comparing a first pattern (A) represented by a first ordered set of (X_i) each having a value with a second pattern (B) represented by a second ordered set of (u_i) each having a value, comprising iteratively performing the steps of:

(i) selecting a plurality of elements from the first ordered set;

(ii) for each selected element of the first ordered set, selecting an element from the second ordered set, such that the selected elements of the second ordered set have, within the second ordered set, a set of positional relationships relative to each other that is the same as, or a transformation of, the set of positional relationships that the selected plurality of elements of the first ordered set have relative to each other;

(iii) determining whether the selected elements meet a match criterion; and

(iv) in the event of a match, updating at least one similarity score (S_AB);

characterized by, on each iteration, generating a random shift value (γ

), and in that the match criterion is that the value of each of the selected elements of the first ordered set differs from the value of the correspondingly positioned selected element of the second ordered set by an amount that is equal to, or within a set margin of, and in the same sense as, said shift value.

4. A method according to claim 1 in which the selection of the parameter(s) is random or pseudo-random.

5. A method according to claim 1, in which each value (a) comprises a plurality of components, and the shift value has a corresponding number of components.

6. A method according to claim 1 in which the patterns are visual images and the components are brightness or color values.

7. A method according to claim 1, comprising firstly processing the first and second ordered set to identify regions thereof containing significant detail, and in which the selection of elements is constrained such that at least one of the selected elements of the first ordered set shall lie in the or an identified region of the first ordered set or that at least one of the selected elements of the first ordered set shall lie in the or an identified region of the first ordered set.

2. A method of comparing a first pattern (A) represented by a first ordered set of elements (x_i) each having a value with a second pattern (B) represented by a second ordered set of element (u_i) each having a value, comprising iteratively performing the steps of:

(i) selecting a plurality of elements from the first ordered set;

(ii) for each selected element of the first ordered set, selecting an element from the second ordered set, such that the selected elements of the second ordered set have, within the second ordered set, a set of positional relationships relative to each other that is the same as, or a transformation of, the set of positional relationships that the selected plurality of elements of the first ordered set have relative to each other; and

(iv) determining whether the selected elements meet a match criterion;

characterized in that each iteration includes the step of generating a random shift value (γ

);

the match criterion is that the value of each of the selected elements of the first ordered set differs from the value of the correspondingly positioned selected element of the second ordered set by an amount that is equal to or within a set margin of, and in the same sense as, said shift value; and

by, in the event of a match, recording the shift value; and

, at the conclusion of said iteration, estimating from said recorded shift values a single representative shift value.

3. A method according to claim 2 including applying to one image a correction based on said single representative shift value.