Analysis of patterns

• US 7,620,249 B2
• Filed: 08/26/2005
• Issued: 11/17/2009
• Est. Priority Date: 09/17/2004
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Stentiford, Frederick W M
• Primary Examiner(s): Hung; Yubin
• Assistant Examiner(s): Bayat; Ali
• Application Number:
  US11/661,984
• Publication Number:
  US 20080075372A1
• Time in Patent Office: 1,544 Days
• Field of Search: 382/100, 382/181, 382/218, 382/209, 382/144, 382/305, 382/274, 358/1.9, 707/100
• US Class Current: 382/218
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries

Abstract

A first pattern (A) is represented by a first ordered set of elements (x_i) each having a value whilst a second pattern (B) is represented by a second ordered set of element (u_i) each having a value. The patterns are analysed by iteratively performing the steps of: selecting (e.g. at random) a plurality m of elements from the first ordered set; for each selected element x_i of the first ordered set, selecting an element u_i 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, comparing the value of each of the selected elements of the first ordered set with the value of the correspondingly positioned selected element of the second ordered set in accordance with a predetermined match criterion to produce a decision that the selected plurality of elements of the first ordered set does or does not match the selected plurality of elements of the second ordered set; and in the event of a match, updating at least one similarity score (S_AB). In the selection of the elements of the second ordered set, one chooses (e.g. at random) at least one parameter (R, β, α) and selects elements having a set of positional relationships (d_i′, d_i″)) that is transformed from the positional relationship set d_i of the selected elements of the first ordered set in accordance with the parameter(s). This transformation may include one or more of rotation, reflection or scaling. Other aspects include biasing the selection of the elements of the first ordered set towards a large extent, and of introducing variations in the number of elements selected, with the similarity score being updated by an amount that is a function of the number of elements. The method may also be applied to a single image.

Claims

1. A computer implemented 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:

using at least one computer with accessible input/output to perform the following steps;

(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 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) comparing the value of each of the selected elements of the first ordered set with the value of the correspondingly positioned selected element of the second ordered set in accordance with a predetermined match criterion to produce a decision that the selected plurality of elements of the first ordered set does or does not match the selected plurality of elements of the second ordered set;

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

wherein the step of selecting the elements of the second ordered set comprises choosing a value for at least one parameter (R, β

, α

) and selecting elements having a set of positional relationships (d_i′

, d_i″

) that is transformed from the positional relationship set (d_i) of the selected elements of the first ordered set in accordance with the parameter(s)

wherein the said parameter (R) determines whether or not a reflection should be applied to the positional relationships.

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

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 the said parameter (β

) determines whether and the degree to which a rotation is to be applied to the positional relationships.

6. A method according to claim 1 in which the said parameter (α

) determines whether and the degree to which a scaling is to be applied to the positional relationships.

7. A method according claim 1 including analysing those values of the parameters that result in a match.

8. A method according to claim 1 wherein the selections of elements in the first ordered set is such that their extent, within the ordered set, is biased towards a small extent rather than a large extent.

10. A method according to claim 8 comprising defining a bounded region of the first ordered set, said bounded region having a randomly selected size (D), and constraining selection of the elements such that the selected elements lie entirely within the defined bounded region.

11. A method according to claim 1 in which, on each iteration, the number of elements (m) to be selected from the first ordered set is selected at random, and in which the step of updating the score increments the score by an amount which is a monotonically increasing function of the number (m) of elements.

13. A method according to claim 11 in which the function of the number (m) of elements is equal to the number of elements.

14. A method according to claim 11 in which the function increases more rapidly than the number (m) of elements than does the number (m) of elements.

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

16. 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 and/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.

17. A method according to claim 1 including analysing those values of the selected element positions that result in a match.

2. A computer implemented method of analysing a pattern (A) represented by an ordered set of elements (x_i) each having a value, comprising iteratively performing the steps of:

using at least one computer with accessible input/output to perform the following steps;

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

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

(iii) comparing the value of each of the first selected elements of the ordered set with the value of the correspondingly positioned selected further element of the ordered set in accordance with a predetermined match criterion to produce a decision that the selected first plurality of elements of the ordered set does or does not match the selected further plurality of elements of the ordered set;

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

wherein the step of selecting the further elements of the ordered set comprises choosing a value for at least one parameter (R, β

, α

) and selecting elements having a set of positional relationships (d_i′

, d_i″

) that is transformed from the positional relationship set (d_i) of the selected first elements of the ordered set in accordance with the parameter(s)

wherein the said parameter (R) determines whether or not a reflection should be applied to the positional relationships.

9. A computer implemented 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 iteratively performing the steps of:

using at least one computer with accessible input/output to perform the following steps;

(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 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) comparing the value of each of the selected elements of the first ordered set with the value of the correspondingly positioned selected element of the second ordered set in accordance with a predetermined match criterion to produce a decision that the selected plurality of elements of the first ordered set does or does not match the selected plurality of elements of the second ordered set;

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

wherein the selections of elements in the first ordered set is such that their extent, within the ordered set, is biased towards a small extent rather than a large extent

wherein a parameter (R) associated with the second ordered set determines whether or not a reflection should be applied to the positional relationships.

12. A computer implemented 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 iteratively performing the steps of:

using at least one computer with accessible input/output to perform the following steps;

(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 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) comparing the value of each of the selected elements of the first ordered set with the value of the correspondingly positioned selected element of the second ordered set in accordance with a predetermined match criterion to produce a decision that the selected plurality of elements of the first ordered set does or does not match the selected plurality of elements of the second ordered set;

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

in which, on each iteration, the number of elements (m) to be selected from the first ordered set is selected at random, and in which the step of updating the score increments the score by an amount which is a monotonically increasing function (f(m)) of the number (m) of elements

wherein a parameter (R) associated with the second ordered set determines whether or not a reflection should be applied to the positional relationships.