Pattern matching system utilizing discrete curve matching with a mapping operator
First Claim
1. A method for performing curve matching between a target discrete curve and a template discrete curve, the method comprising:
- acquiring a target data set;
determining a target discrete curve from the target data set, wherein the target discrete curve corresponds to a respective object in the target data set;
analyzing 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;
characterizing an object of interest to produce a mapped template discrete curve, wherein said characterizing the object of interest comprises;
determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest;
determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves;
mapping the template discrete curve that corresponds to the object of interest to the mapped template discrete curve using the mapping operator;
performing curve matching on the target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve, and wherein said performing curve matching on the target discrete curve and the mapped template discrete curve comprises determining whether the respective object in the target data set corresponds to the object of interest; and
generating curve matching results based on the distances.
5 Assignments
0 Petitions
Accused Products
Abstract
System and method for determining the presence of an object of interest in a target data set. Portions of a target data set may be located that match an object of interest, e.g., in a template data set, with respect to various information, e.g., edge or boundary information. The invention includes improved methods for mapping point sets or curves to new point sets or curves for curve matching. The method determines the presence of an object of interest in a target data set despite of or using various types of topological transformations of the object of interest in the target data set. One or more mapping operators are determined based on template curves and/or example target curves. Pattern matching is performed on one or more target data sets using the mapping operator(s) to generate pattern matching results, and the pattern matching results output.
-
Citations
110 Claims
-
1. A method for performing curve matching between a target discrete curve and a template discrete curve, the method comprising:
-
acquiring a target data set; determining a target discrete curve from the target data set, wherein the target discrete curve corresponds to a respective object in the target data set; analyzing 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; characterizing an object of interest to produce a mapped template discrete curve, wherein said characterizing the object of interest comprises; determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; mapping the template discrete curve that corresponds to the object of interest to the mapped template discrete curve using the mapping operator; performing curve matching on the target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve, and wherein said performing curve matching on the target discrete curve and the mapped template discrete curve comprises determining whether the respective object in the target data set corresponds to the object of interest; and generating curve matching results based on the distances. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. A method for matching discrete curves, the method comprising:
-
acquiring a target data set; determining a plurality of target discrete curves from the target data set, wherein each target discrete curve corresponds to a respective object in the target data set; analyzing one or mare 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; characterizing an object of interest to produce a mapped template discrete curve, wherein said characterizing the object of interest comprises; determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; mapping the template discrete curve to the mapped template discrete curve using the mapping operator, wherein the mapped template discrete curve corresponds to the object of interest; for each of the plurality of target discrete curves, performing curve matching on each of the target discrete curves and the mapped template discrete curve, wherein said performing curve matching computes a distance for the each of the mapped target discrete curves relative to the mapped template discrete curve, and wherein said performing curve matching on the target discrete curve and the mapped template discrete curve comprises determining whether the respective object in the target data set corresponds to the object of interest; and generating curve matching results based on the distances. - View Dependent Claims (33, 34, 35)
-
-
36. A computer readable memory medium which stores program instructions for performing curve matching between a target discrete curve and a template discrete curve, wherein the program instructions are executable to perform:
-
acquiring a target data set; determining a target discrete curve from the target data set wherein the target discrete curve corresponds to a respective object in the target data set; analyzing 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, characterizing an object of interest to produce a mapped template discrete curve, wherein said characterizing the object of interest comprises; determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; mapping the template discrete curve that corresponds to the object of interest to the mapped template discrete curve using the mapping operator; performing curve matching on the target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve, and wherein said performing curve matching on the target discrete curve and the mapped template discrete curve comprises determining whether the respective object in the target data set corresponds to the object of interest; and generating curve matching results based on the distances. - View Dependent Claims (37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66)
-
-
67. A computer readable memory medium which stores program instructions for performing curve matching between target discrete curves and a template discrete curve, wherein the program instructions are executable to perform:
-
acquiring a target data set; determining a plurality of target discrete curves from the target data set, wherein each target discrete curve corresponds to a respective object in the target data set; analyzing 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; characterizing an object of interest to produce a mapped template discrete curve, wherein, said characterizing the object of interest comprises; determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; mapping the template discrete curve to the mapped template discrete curve using the mapping operator, wherein the mapped template discrete curve corresponds to the object of interest; for each of the plurality of target discrete curves, performing curve matching on each of the target discrete curves and the mapped template discrete curve, wherein said performing curve matching computes a distance for the each of the mapped target discrete curves relative to the mapped template discrete curve, and wherein said performing curve matching on the target discrete curve and the mapped template discrete curve comprises determining whether the respective object in the target data set corresponds to the object of interest; and generating curve matching results based on the distances. - View Dependent Claims (68)
-
-
69. A system for matching discrete curves, the system comprising:
-
a computer system, comprising; a processor; and a memory medium coupled to the processor; and a data acquisition device coupled to the processor and the memo medium; wherein the data acquisition device is operable to; acquire a target data set; and wherein the memory medium stores program instructions which are executable by the processor to; determine a target discrete curve from the target data set, wherein the target discrete curve corresponds to a respective object in the target data set; analyze 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; characterize an object of interest to produce a mapped template discrete curve, wherein to characterize the object of interest the program instructions are executable to; determine a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; determine the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; map the template discrete curve to the mapped template discrete curve using the mapping operator; perform curve matching on the target discrete curve and the mapped template discrete curve, wherein the mapped template discrete curve corresponds to an object of interest, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve, and wherein to perform curve matching on the target discrete curve and the mapped template discrete curve the program instructions are executable to determine whether the respective object in the target data set corresponds to the object of interest; and generate curve matching results based on the distances.
-
-
70. A system for determining the presence of an object of interest in a target data set, the system comprising:
-
a computer system, comprising; a processor; and a memory medium coupled to the processor; and a data acquisition device coupled to the processor and the memory medium; wherein the data acquisition device is operable to; acquire the target data set; and wherein, the memory medium stores program instructions which are executable by the processor to; determine a plurality of target discrete curves from the target data set, wherein each target discrete curve corresponds to a respective object in the target data set; analyze 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; characterize an object of interest to produce a mapped template discrete curve, wherein to characterize the object of interest the program instructions are executable to; determine a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; determine the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; and map the template discrete curve to the mapped template discrete curve using the mapping operator; determine a plurality of target discrete curves from the target data set, wherein each of the target discrete curves corresponds to a respective object in the target data set; for each of the target discrete curves, perform curve matching on each of the mapped target discrete curves and the mapped template discrete curve corresponding to the object of interest, wherein said performing curve matching computes a distance for the each of the target discrete curves relative to the mapped template discrete curve, and wherein to perform curve matching on each the target discrete curves and the mapped template discrete curve the program instructions are executable to determine whether the respective object in the target data set corresponds to the object of interest; and generate curve matching results based on the distances. - View Dependent Claims (71)
-
-
72. A system for determining the presence of an object of interest in a target data set, the system comprising:
-
means for acquiring the target data set; means for analyzing 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; means for characterizing an object of interest to produce a mapped template discrete curve, wherein said means for characterizing the object of interest comprises; means for determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; means for determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; and means for mapping the template discrete curve to the mapped template discrete curve using the mapping operator; means for determining a target discrete curve from the target data set, wherein the target discrete curve corresponds to a respective object in the target data set; means for performing curve matching on the target discrete curve and the mapped template discrete curve, wherein the mapped template discrete curve corresponds to the object of interest, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve, and wherein said means for performing curve matching on the target discrete curve and the mapped template discrete curve comprises means for determining whether the respective object in the target data set corresponds to the object of interest; and means for generating curve matching results based on the distances. - View Dependent Claims (73)
-
-
74. A system for determining the presence of an object of interest in a target data set, the system comprising:
-
means for acquiring the target data set; means for determining a plurality of target discrete curves from the target data set, wherein each of the target discrete curves corresponds to a respective object in the target data set; means for analyzing 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; means for characterizing an object of interest to produce a mapped template discrete curve, wherein said characterizing the object of interest comprises; means for determining a template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; means for determining the mapping operator based on the determined template discrete curve and the one or more example target discrete curves; and means for mapping the template discrete curve to the mapped template discrete curve using the mapping operator; means for performing curve matching on each of the target discrete curves and the mapped template discrete curve corresponding to the object of interest, wherein said performing curve matching computes a distance for the each of the target discrete curves relative to the mapped template discrete curve, and wherein said performing curve matching on the target discrete curves and the mapped template discrete curve comprises determining whether the respective objects in the target data set correspond to the object of interest; and means for generating curve matching results based on the distances. - View Dependent Claims (75)
-
-
76. A method for characterizing an object of interest for a pattern matching application, the method comprising:
-
receiving data containing the object of interest; determining a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; and analyzing the object of interest and one or more example target data sets to determine one or more terms for a mapping operator, wherein the mapping operator comprises a weight vector; mapping the template discrete curve to a mapped template discrete curve using the mapping operator, wherein said tapping comprises; applying the weight vector terms respectively to corresponding points in the template discrete curve; wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in acquired target data. - View Dependent Claims (77, 78, 79, 80, 81, 82, 83, 84)
-
-
85. A computer readable memory medium which stores program instructions for characterizing an object of interest for a pattern matching application, wherein the program instructions are executable to perform:
-
receiving data containing the object of interest; determining a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; analyzing the object of interest and one or more example target data sets to determine one or more terms for the mapping operator wherein the mapping operator comprises a weight vector; and mapping the template discrete curve to a mapped template discrete curve using the mapping operator, wherein said mapping comprises; applying the weight vector terms respectively to corresponding points in the template discrete curve; wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in acquired target data. - View Dependent Claims (86, 87, 88, 89, 90, 91, 92, 93)
-
-
94. A system for characterizing an object of interest for a pattern matching application, the system comprising:
-
a computer system, comprising; a processor; and a memory medium coupled to the processor; and wherein the memory medium stores program instructions which are executable by the processor to; receive data containing the object of interest; determine a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; analyze the object of interest and one or more example target data sets to determine one or more terms for the mapping operator, wherein the mapping operator comprises a weight vector; and map the template discrete curve to a mapped template discrete curve using the mapping operator, wherein to map the template discrete curve the program instructions are executable to; apply the weight vector terms respectively to corresponding points in the template discrete curve; wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in acquired target data.
-
-
95. A method for performing curve matching between a target discrete curve and a template discrete curve, the method comprising:
-
mapping a template discrete curve to a mapped template discrete curve using a mapping operator, including characterizing an object of interest to produce the mapped template discrete curve, wherein said characterizing the object of interest comprises; determining the template discrete curve from information regarding the object of interest, wherein the template discrete curve corresponds to the object of interest; analyzing the mapped template discrete curve and one or more example target discrete curves generated from one or more example target data sets to determine at least one parameter for the mapping operator; configuring the mapping operator according to the determined at least one parameter; performing curve matching on a target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve; and generating curve matching results based on the distances. - View Dependent Claims (96)
-
-
97. A method for performing curve matching between a target discrete curve and a template discrete curve, the method comprising:
-
receiving first information regarding an object of interest; receiving second information regarding one or more objects that are not of interest; determining at least one parameter for the mapping operator based on the first information and the second information, wherein the at least one parameter is determined to enhance a distance between mapped discrete curves corresponding to an object of interest and mapped discrete curves corresponding to the one or more objects that are not of interest; and configuring the mapping operator according to the determined at least one parameter; mapping a template discrete curve to a mapped template discrete curve using the mapping operator; performing curve matching on a target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve; and generating curve matching results based on the distances.
-
-
98. A method for performing curve matching between a target discrete curve and a template discrete curve, the method comprising:
-
mapping a template discrete curve to a mapped template discrete curve using a mapping operator; performing curve matching on a target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve; and generating curve matching results based on the distances; wherein the mapping operator comprises a weight vector w; wherein the template discrete curve comprises a first vector; wherein said weight vector w, and said first vector have the same number of elements; and wherein said mapping the template discrete curve to the mapped template discrete curve comprises; multiplying each element of the weight vector w with corresponding elements in the first vector to generate a second vector, wherein elements of the second vector comprise the mapped template discrete curve.
-
-
99. A computer readable memory medium which stores program instructions for performing curve matching between a target discrete curve and a template discrete curve, wherein the program instructions are executable to perform:
-
acquiring a target data set; determining a target discrete curve from the target data set, wherein the target discrete curve corresponds to a respective object in the target data set; analyzing the mapped template discrete curve and one or more example target discrete curves generated from one or more example target data sets to determine at least one parameter for the mapping operator; configuring the mapping operator according to the determined at least one parameter; mapping a template discrete curve to a mapped template discrete curve using a mapping operator, including characterizing an object of interest to produce the mapped template discrete curve, wherein the mapped template discrete curve corresponds to the object of interest, and wherein said characterizing the object of interest comprises; determining a template discrete curve corresponding to the object of interest from information regarding the object of interest; performing curve matching on the target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve, wherein said performing curve matching on the mapped target discrete curve and the mapped template discrete curve comprises determining whether the respective object in the target data set corresponds to the object of interest; and generating curve matching results based on the distances. - View Dependent Claims (100)
-
-
101. A computer readable memory medium which stores program instructions for performing curve matching between a target discrete curve and a template discrete curve, wherein the program instructions are executable to perform:
-
receiving first information regarding an object of interest;
receiving second information regarding one or more objects that are not of interest;determining at least one parameter for a mapping operator based on the first information and the second information, wherein the at least one parameter is determined to enhance a distance between mapped discrete curves corresponding to an object of interest and mapped discrete curves corresponding to the one or more objects that are not of interest; configuring the mapping operator according to the determined at least one parameter; mapping a template discrete curve to a mapped template discrete curve using a mapping operator; performing curve matching on a target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve; and generating curve matching results based on the distances.
-
-
102. A computer-readable memory medium which stores program instructions for performing curve matching between a target discrete curve and a template discrete curve, wherein the program instructions are executable to perform:
-
mapping a template discrete curve to a mapped template discrete curve using a mapping operator; performing curve matching on a target discrete curve and the mapped template discrete curve, wherein said performing curve matching computes a distance for the target discrete curve relative to the mapped template discrete curve; and generating curve matching results based on the distances; wherein the mapping operator comprises a weight vector W; wherein the template discrete curve comprises a first vector; wherein said weight vector W, and said first vector have the same number of elements; and wherein said mapping the template discrete curve to the mapped template discrete curve comprises; multiplying each element of the weight vector W with corresponding elements in the first vector to generate a second vector, wherein elements of the second vector comprise the mapped template discrete curve.
-
-
103. A method for characterizing an object of interest for a pattern matching application, the method comprising:
-
receiving data containing the object of interest; determining a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; and analyzing the object of interest and one or more example target data sets to determine at least one parameter for a mapping operator; configuring the mapping operator according to the determined at least one parameter; 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 acquired target data. - View Dependent Claims (104)
-
-
105. A method for characterizing an object of interest for a pattern matching application, the method comprising:
-
receiving first information regarding the object of interest, including receiving data containing the object of interest; determining a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; receiving second information regarding one or more objects that are not of interest; determining at least one parameter for the mapping operator based on the first information and the second information; configuring the mapping operator according to the determined at least one parameter; mapping the template discrete curve to a mapped template discrete curve using a mapping operator; wherein the mapped template discrete curve is useable to perform pattern matching to locate instances of the object of interest in acquired target data. - View Dependent Claims (106)
-
-
107. A computer readable memory medium which stores program instructions for characterizing an object of interest for a pattern matching application, wherein the program instructions are executable to perform:
-
receiving data containing the object of interest; determining a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; analyzing the object of interest and one or more example target data sets to determine at least one parameter for the mapping operator; and configuring the mapping operator according to the determined at least one parameter; 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 acquired target data. - View Dependent Claims (108)
-
-
109. A computer readable memory medium which stores program instructions for characterizing an object of interest for a pattern matching application, wherein the program instructions are executable to perform:
-
receiving first information regarding the object of interest including receiving data containing the object of interest; determining a template discrete curve from the data, wherein the template discrete curve corresponds to the object of interest in the data; receiving second information, regarding one or more objects that are not of interest; determining at least one parameter for the mapping operator based on the first information and the second information; and configuring the mapping operator according to the determined at least one parameter; 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 acquired target data. - View Dependent Claims (110)
-
Specification