Generating a curve matching mapping operator by analyzing objects of interest and background information

• US 7,136,505 B2
• Filed: 10/03/2002
• Issued: 11/14/2006
• Est. Priority Date: 04/10/2002
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Wenzel, Lothar, Schmidt, Darren R., Crotty, Kevin M., Rajagopal, Ram, Kumar, Satish V., Fisher, Matthew S.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): CONOVER, DAMON M
• Application Number:
  US10/264,059
• Publication Number:
  US 20030194134A1
• Time in Patent Office: 1,503 Days
• Field of Search: 382/103
• US Class Current: 382/103
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

System and method for determining a mapping operator for use in a pattern matching application, where the mapping operator enhances differences between respective objects of interest and background objects, e.g., objects not of interest. First and second information is received regarding an object of interest and objects that may appear with the object of interest in an acquired target data set, respectively. The mapping operator is determined using the first information and the second information by determining a template discrete curve characterizing the object of interest, determining one or more target discrete curves characterizing the background objects, and generating a mapping operator that enhances differences between the mapped template discrete curve and the mapped target discrete curves. The operator is stored in a memory and is operable to be used in a pattern matching application to locate instances of the object of interest in acquired target data sets or images.

Claims

1. A method for determining a mapping operator for use in a pattern matching application, the method comprising:

receiving first information regarding an object of interest, the first information comprising a template data set containing the object of interest;

determining a template discrete curve from the template data set, wherein the template discrete curve corresponds to the object of interest in the template data set;

receiving second information regarding objects that may appear with the object of interest in an acquired target data set, the second information comprising one or more example target data sets;

determining at least one parameter for a mapping operator based on the first information and the second information; and

configuring the mapping operator according to the determined at least one parameter,

wherein said determining and said configuring comprise;

analyzing the one or more example target data sets to determine one or more example target discrete curves, wherein each of the one or more example target discrete curves corresponds to a data object or part of a data object in the one or more example target data sets;

determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves, wherein said determining the mapping operator comprises;

normalizing the template discrete curve and the one or more example target discrete curves; and

computing a weight vector W, such that

$\langle <br><br>c_{n,}<br><br>c_m\rangle <br><br><br><br>w_m=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>c_{\mathrm{ni}}<br><br>c_{\mathrm{mi}}^{*}<br><br>W_i={\mathrm{\delta <br><br>}}_{\mathrm{nm}}$

wherein c_m comprises the normalized template discrete curve, wherein c_n comprises any one of the one or more normalized example target discrete curves, and wherein δ

_nm is the Kronecker delta;

storing the mapping operator in a memory; and

mapping the template discrete curve to a mapped template discrete curve using the mapping operator;

wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in an acquired target data set.

2. The method of claim 1,

wherein the mapping operator is operable to be used in a pattern matching application to locate instances of the object of interest in the acquired target data set.

3. The method of claim 1,

wherein the at least one parameter is configurable for different objects of interest.

4. The method of claim 1,

wherein the at least one parameter is configurable to enhance differences for respective objects of interest and objects not of interest.

5. The method of claim 1,

wherein the mapping operator comprises a weight vector;

wherein the at least one parameter comprises one or more terms in the weight vector; and

wherein the one or more terms are configurable for different objects of interest.

6. The method of claim 5,

wherein the one or more terms are configurable to enhance differences for respective objects of interest and objects not of interest.

7. The method of claim 1,

wherein the mapping operator is operable to be applied to information corresponding to objects to map the information to new information, wherein the new information operates to emphasize differences between respective objects.

8. The method of claim 1,

wherein the second information describes objects not of interest in the pattern matching application;

and

wherein the mapping operator is operable to be applied to information corresponding to objects to map the information to new information, wherein the new information operates to emphasize differences between the object of interest and the objects not of interest.

9. The method of claim 1,

wherein the mapping operator is useable to map a template discrete curve characterizing the object of interest to a mapped template discrete curve using the mapping operator;

and

wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in an acquired target data set.

10. The method of claim 9,

wherein the at least one parameter is used to create a distance between mapped discrete curves corresponding to the object of interest and mapped discrete curves corresponding to objects that are not of interest.

11. The method of claim 9, wherein said determining the at least one parameter for the mapping operator comprises:

determining a template discrete curve characterizing the object of interest;

determining one or more target discrete curves characterizing the objects that may appear with the object of interest in an acquired target data set; and

generating a value for the at least one parameter that enhances a difference between mappings of the template discrete curve and the one or more mapped target discrete curves.

12. The method of claim 11,

wherein the template discrete curve and the one or more target discrete curves comprise respective sequences of complex points;

and

wherein the mapping operator is a complex mapping operator.

13. The method of claim 1,

wherein the first information comprises a template discrete curve characterizing the object of interest.

14. The method of claim 1,

wherein the first information is derived from a template data set containing the object of interest.

15. The method of claim 1,

wherein the second information comprises one or more discrete curves characterizing objects expected to appear in an acquired target data set containing the object of interest.

16. The method of claim 1,

wherein the second information is derived from an acquired target data set containing the object of interest.

17. The method of claim 1, further comprising:

receiving a template data set containing the object of interest;

determining the first information from the template data set;

receiving one or more target data sets containing the object of interest and one or more background data objects; and

determining the second information from the one or more target data sets.

18. The method of claim 1,

wherein the mapping operator is a weighting operator.

19. The method of claim 1,

wherein the mapped template discrete curve is a unique discrete curve generated from the template discrete curve.

20. The method of claim 1,

wherein the mapped template discrete curve is an artificially created discrete curve that is more stable under data disruptions than the template discrete curve.

21. The method of claim 1, further comprising:

acquiring a target data set;

determining at least one target discrete curve from the target data set, wherein each target discrete curve corresponds to a respective data object in the target data set;

performing curve matching on the target image discrete curve and the mapped template discrete curve corresponding to the object of interest, wherein said performing curve matching computes a distance measure for the target discrete curve relative to the mapped template discrete curve; and

generating pattern matching results based on the distance measures.

22. The method of claim 21,

wherein said determining the at least one target discrete curve from the target data set comprises:

determining at least one initial target discrete curve from the target data set; and

mapping the at least one initial target discrete curve to a respective at least one mapped target discrete curve using the mapping operator, wherein the at least one mapped target discrete curve comprises the at least one target discrete curve; and

wherein said performing curve matching on the target discrete curve and the mapped template discrete curve comprises performing curve matching on the mapped target discrete curve and the mapped template discrete curve.

23. The method of claim 22, further comprising:

repeating said acquiring, said determining at least one initial target discrete curve, said mapping the at least one initial target discrete curve, said performing and said generating for each of a plurality of additional target data sets.

24. The method of claim 1,

wherein the acquired target data set comprises an acquired target image;

wherein the object of interest comprises an image object; and

wherein the mapping operator is operable to be used in a pattern matching application to locate instances of the object of interest in the acquired target image.

25. The method of claim 24,

wherein the second information is derived from objects appearing in a background of an acquired target image containing the object of interest.

26. A memory medium which stores program instructions for determining a mapping operator for use in a pattern matching application, wherein the program instructions are executable by a processor to perform:

receiving first information regarding an object of interest, the first information comprising a template data set containing the object of interest;

determining a template discrete curve from the template data set, wherein the template discrete curve corresponds to the object of interest in the template data set;

receiving second information regarding objects that may appear with the object of interest in an acquired target data set, the second information comprising one or more example target data sets;

determining at least one parameter for a mapping operator based on the first information and the second information; and

configuring the mapping operator according to the determined at least one parameter, wherein said determining and said configuring comprise;

analyzing the one or more example target data sets to determine one or more example target discrete curves, wherein each of the one or more example target discrete curves corresponds to a data object or part of a data object in the one or more example target data sets;

determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves, wherein said determining the mapping operator comprises;

normalizing the template discrete curve and the one or more example target discrete curves; and

computing a weight vector W, such that

$\langle <br><br>c_{n,}<br><br>c_m\rangle <br><br><br><br>w_m=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>c_{\mathrm{ni}}<br><br>c_{\mathrm{mi}}^{*}<br><br>W_i={\mathrm{\delta <br><br>}}_{\mathrm{nm}}$

wherein c_m comprises the normalized template discrete curve, wherein c_n comprises any one of the one or more normalized example target discrete curves, and wherein δ

_nm is the Kronecker delta;

storing the mapping operator in a memory; and

mapping the template discrete curve to a mapped template discrete curve using the mapping operator;

wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in an acquired target data set.

27. The memory medium of claim 26,

wherein the mapping operator is operable to be used in a pattern matching application to locate instances of the object of interest in the acquired target data set.

28. The memory medium of claim 26,

wherein the at least one parameter is configurable for different objects of interest.

29. The memory medium of claim 26,

wherein the at least one parameter is configurable to enhance differences for respective objects of interest and objects not of interest.

30. The memory medium of claim 26,

wherein the mapping operator comprises a weight vector;

wherein the at least one parameter comprises one or more terms in the weight vector; and

wherein the one or more terms are configurable for different objects of interest.

31. The memory medium of claim 30,

wherein the one or more terms are configurable to enhance differences for respective objects of interest and objects not of interest.

32. The memory medium of claim 26,

wherein the mapping operator is operable to be applied to information corresponding to objects to map the information to new information, wherein the new information operates to emphasize differences between respective data objects.

33. The memory medium of claim 26,

wherein the second information describes objects not of interest in the pattern matching application;

and

wherein the mapping operator is operable to be applied to information corresponding to objects to map the information to new information, wherein the new information operates to emphasize differences between the object of interest and the objects not of interest.

34. The memory medium of claim 26,

wherein the mapping operator is useable to map a template discrete curve characterizing the object of interest to a mapped template discrete curve using the mapping operator;

and

wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in an acquired target data set.

35. The memory medium of claim 34,

wherein the at least one parameter is used to create a distance between mapped discrete curves corresponding to the object of interest and mapped discrete curves corresponding to objects that are not of interest.

36. The memory medium of claim 34, wherein said determining the at least one parameter for the mapping operator comprises:

determining a template discrete curve characterizing the object of interest;

determining one or more target discrete curves characterizing the objects that may appear with the object of interest in an acquired target data set; and

generating a value for the at least one parameter that enhances a difference between mappings of the template discrete curve and the one or more mapped target discrete curves.

37. The memory medium of claim 36,

wherein the template discrete curve and the one or more target discrete curves comprise respective sequences of complex points;

and

wherein the mapping operator is a complex mapping operator.

38. The memory medium of claim 26,

wherein the first information comprises a template discrete curve characterizing the object of interest.

39. The memory medium of claim 26,

wherein the first information is derived from a template data set containing the object of interest.

40. The memory medium of claim 26,

wherein the second information comprises one or more discrete curves characterizing objects expected to appear in an acquired target data set containing the object of interest.

41. The memory medium of claim 26,

wherein the second information is derived from an acquired target data set containing the object of interest.

42. The memory medium of claim 26,

wherein the second information is derived from objects appearing in a background of an acquired target data set containing the object of interest.

43. The memory medium of claim 26, wherein the program instructions are further executable to perform:

receiving a template data set containing the object of interest;

determining the first information from the template data set;

receiving one or more target data sets containing the object of interest and one or more background data objects; and

determining the second information from the target data set.

44. The memory medium of claim 26,

wherein the mapping operator is a weighting operator.

45. The memory medium of claim 26,

wherein the mapped template discrete curve is a unique discrete curve generated from the template discrete curve.

46. The memory medium of claim 26,

wherein the mapped template discrete curve is an artificially created discrete curve that is more stable under data disruptions than the template discrete curve.

47. The memory medium of claim 26, wherein the program instructions are further executable to perform:

acquiring a target data set;

determining at least one target discrete curve from the target data set, wherein each target discrete curve corresponds to a respective data object in the target data set;

mapping the at least one target discrete curve to a respective at least one mapped target discrete curve using the mapping operator;

performing curve matching on the mapped target discrete curve and the mapped template discrete curve corresponding to the object of interest, wherein said performing curve matching computes a distance measure for the mapped target discrete curve relative to the mapped template discrete curve; and

generating pattern matching results based on the distance measures.

48. The memory medium of claim 26, wherein the program instructions are further executable to perform:

repeating said acquiring, said determining, said mapping, said performing and said generating for each of a plurality of additional target data sets.

49. A method for determining a mapping operator for use in a curve matching application, the method comprising:

receiving first information regarding an object of interest, the first information comprising a template data set containing the object of interest;

determining a template discrete curve from the template data set, wherein the template discrete curve corresponds to the object of interest in the template data set;

receiving second information regarding objects that may appear with the object of interest in acquired target data sets, the second information comprising one or more example target data sets;

determining one or more mapping operators based on the first information and the second information, including;

analyzing the one or more example target data sets to determine one or more example target discrete curves, wherein each of the one or more example target discrete curves corresponds to a data object or part of a data object in the one or more example target data sets;

determining the one or more mapping operators based on the determined template discrete curve and the one or more example target discrete curves, comprising;

normalizing the template discrete curve and the one or more example target discrete curves; and

for each mapping operator, computing a weight vector W, such that

$\langle <br><br>c_{n,}<br><br>c_m\rangle <br><br><br><br>w_m=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>c_{\mathrm{ni}}<br><br>c_{\mathrm{mi}}^{*}<br><br>W_i={\mathrm{\delta <br><br>}}_{\mathrm{nm}}$

wherein c_m comprises the normalized template discrete curve, wherein c_n comprises any one of the one or more normalized example target discrete curves, and wherein δ

_nm is the Kronecker delta;

storing the one or more mapping operators in a memory medium;

wherein the one or more mapping operators are usable to determine the presence of the object of interest in the acquired target data sets; and

mapping the template discrete curve to a mapped template discrete curve using at least one of the mapping operators;

wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in an acquired target data set.

50. A method for determining a mapping operator for use in a curve matching application, the method comprising:

receiving information regarding two or more objects of interest, wherein the two or more objects may appear in acquired target data sets, and wherein the information comprises one or more example target data sets that include the one or more objects of interest;

determining one or more mapping operators based on the information, wherein the one or more mapping operators are operable to enhance differences between the two or more objects of interest, said determining including;

analyzing the one or more example target data sets to determine two or more example target discrete curves, wherein each of the two or more example target discrete curves corresponds to a data object or part of a data object in the one or more example target data sets; and

determining the one or more mapping operators based on the two or more example target discrete curves, comprising;

normalizing the two or more example target discrete curves; and

for each mapping operator, computing a weight vector W, such that

$\langle <br><br>c_{n,}<br><br>c_m\rangle <br><br><br><br>w_m=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>c_{\mathrm{ni}}<br><br>c_{\mathrm{mi}}^{*}<br><br>W_i={\mathrm{\delta <br><br>}}_{\mathrm{nm}}$

wherein c_m and c_n comprise any two of the two or more example target discrete curves, and wherein δ

_nm is the Kronecker delta; and

storing the one or more mapping operators in a memory medium;

wherein the one or more mapping operators are usable to determine the presence of the objects of interest in the acquired target data sets.

51. A computer readable memory medium that stores program instructions for determining a mapping operator for use in a curve matching application, wherein the program instructions are executable by a processor to perform:

receiving first information regarding an object of interest, the first information comprising a template data set containing the object of interest;

determining a template discrete curve from the template data set, wherein the template discrete curve corresponds to the object of interest in the template data set;

receiving second information regarding objects that may appear with the object of interest in acquired target data sets, the second information comprising one or more example target data sets;

determining one or more mapping operators based on the first information and the second information, including;

analyzing the one or more example target data sets to determine one or more example target discrete curves, wherein each of the one or more example target discrete curves corresponds to a data object or part of a data object in the one or more example target data sets;

determining the one or more mapping operators based on the determined template discrete curve and the one or more example target discrete curves, comprising;

normalizing the template discrete curve and the one or more example target discrete curves; and

for each mapping operator, computing a weight vector W, such that

$\langle <br><br>c_{n,}<br><br>c_m\rangle <br><br><br><br>w_m=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>c_{\mathrm{ni}}<br><br>c_{\mathrm{mi}}^{*}<br><br>W_i={\mathrm{\delta <br><br>}}_{\mathrm{nm}}$

wherein c_m comprises the normalized template discrete curve, and wherein c_n comprises any one of the one or more normalized example target discrete curves; and

wherein δ

_nm is the Kronecker delta;

storing the one or more mapping operators in a memory medium;

wherein the one or more mapping operators are usable to determine the presence of the object of interest in the acquired target data sets; and

mapping the template discrete curve to a mapped template discrete curve using the mapping operator;

wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in an acquired target data set.

52. A computer readable memory medium that stores program instructions for determining a mapping operator for use in a curve matching application, wherein the program instructions are executable by a processor to perform:

receiving information regarding two or more objects of interest, wherein the two or more objects may appear in acquired target data sets, and wherein the information comprises one or more example target data sets that include the one or more objects of interest;

determining one or more mapping operators based on the information, wherein the one or more mapping operators are operable to enhance differences between the two or more objects of interest, said determining including;

analyzing the one or more example target data sets to determine two or more example target discrete curves, wherein each of the two or more example target discrete curves corresponds to a data object or part of a data object in the one or more example target data sets; and

determining the one or more mapping operators based on the two or more example target discrete curves, comprising;

normalizing the two or more example target discrete curves; and

for each mapping operator, computing a weight vector W, such that

$\langle <br><br>c_{n,}<br><br>c_m\rangle <br><br><br><br>w_m=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>c_{\mathrm{ni}}<br><br>c_{\mathrm{mi}}^{*}<br><br>W_i={\mathrm{\delta <br><br>}}_{\mathrm{nm}}$

wherein c_m and c_n comprise any two of the two or more example target discrete curves, and wherein δ

_nm is the Kronecker delta; and

storing the one or more mapping operators in a memory medium;

wherein the one or more mapping operators are usable to determine the presence of the objects of interest in the acquired target data sets.