# US 2010/0166295 A1 · Method and system for searching for global minimum > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2010/0166295 A1 - Document ID: US20100166295A1 - Status: Published application - Kind: A1 - Application number: 12/534,861 - Filed: 2009-08-04 - Published: 2010-07-01 - Earliest claimed: 2008-12-31 - Assignees: Industrial Technology Research Institute - Inventors: Wen-Chao Chen; Zen Chen; Chiao-Wen Cheng - Web page: https://patentgrep.com/patent/US20100166295A1 ## CPC - G06V 10/147: Details of sensors, e.g. sensor lenses (fingerprint or palmprint sensors G06V40/13; vascular sensors G06V40/145; eye sensors G06V40/19) - G06V 10/76: {based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds} - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract A method and a system for searching for a global minimum are provided. First, a subclass of a plurality of space points in a multidimensional space is clustered into a plurality of clusters through a clustering algorithm, wherein each of the space points is corresponding to an error value in an evaluation function. Then, ellipsoids for enclosing the clusters in the multidimensional space are respectively calculated. Next, a designated space corresponding to each of the ellipsoids is respectively inputted into a recursive search algorithm to search for a local minimum among the error values corresponding to the space points within each designated space. Finally, the local minimums of all the clusters are compared to obtain the space point corresponding to the minimum local minimum. ## Claims ### Claim 1 A global minimum searching method, comprising: clustering a subclass of a plurality of space points in a multidimensional space into a plurality of clusters through a clustering algorithm, wherein each of the space points is corresponding to an error value in an evaluation function; respectively calculating a plurality of ellipsoids for enclosing the clusters in the multidimensional space; respectively inputting a designated space corresponding to each of the ellipsoids into a recursive search algorithm to search for a local minimum among the error values corresponding to the space points within the designated space; and comparing the local minimums to obtain the space point corresponding to the minimum local minimum. ### Claim 2 (depends on 1) The global minimum searching method according to claim 1, wherein before the step of clustering the subclass of the space points in the multidimensional space into the clusters, the global minimum searching method further comprises: capturing a plurality of corresponding feature points in a first image and a second image, wherein the first image and the second image are obtained by capturing a same object from different angles; and calculating the space points according to the feature points. ### Claim 3 (depends on 2) The global minimum searching method according to claim 2, wherein the step of calculating the space points according to the feature points comprises: randomly selecting k of the feature points through a robust estimation method; calculating a fundamental matrix between the first image and the second image according to the k feature points, so as to obtain one of the space points; and repeating the step of randomly selecting k of the feature points t times to calculate t space points, wherein t and k are predetermined positive integers. ### Claim 4 (depends on 3) The global minimum searching method according to claim 3, wherein before the step of clustering the subclass of the space points in the multidimensional space into the clusters, the global minimum searching method further comprises: selecting p space points having the smallest error values from the t space points and defining the p space points as the subclass, wherein p is a positive integer smaller than or equal to t. ### Claim 5 (depends on 3) The global minimum searching method according to claim 3, wherein the robust estimation method is one of a least median of squares (LMedS) method, a random sample consensus (RANSAC) method, and a M-estimator method. ### Claim 6 (depends on 1) The global minimum searching method according to claim 1, wherein the clustering algorithm is one of a minimum spanning tree (MST) algorithm and a K-means algorithm. ### Claim 7 (depends on 1) The global minimum searching method according to claim 1, wherein each of the ellipsoids comprises N axes, each of the designated spaces is located at a center of the corresponding ellipsoid, each of the designated spaces comprises a designated range on each of the axes of the corresponding ellipsoid, and the N axes of each of the ellipsoids are arranged according to an execution order. ### Claim 8 (depends on 7) The global minimum searching method according to claim 7, wherein the execution order is determined according to an eigenvalue of each of the N axes of each of the ellipsoids. ### Claim 9 (depends on 7) The global minimum searching method according to claim 7, wherein the recursive search algorithm comprises: receiving an input designated space, wherein the input designated space is a subclass of one of the designated spaces; in the input designated space, all the designated ranges on the axes having their execution orders smaller than i are single values, all the designated ranges on the other axes are value ranges, and i is a positive integer smaller than or equal to N+1; and if the input designated space is equal to one of the designated spaces, i is equal to 1; if i is equal to N+1, serving the error value corresponding to the input designated space as the local minimum of the input designated space; if a length of the designated range on the ith axis of the input designated space is smaller than a predetermined threshold, serving a corresponding value of a median within the designated range on the ith axis in a predetermined function as the local minimum of the input designated space; if the length of the designated range on the ith axis of the input designated space is greater than the predetermined threshold, selecting a plurality of sectional values within the designated range on the ith axis; comparing a plurality of corresponding values of the sectional values in the predetermined function to select a first subspace or a first subspace and a second subspace in the input designated space; if only the first subspace is selected, inputting the first subspace into the recursive search algorithm to search for a local minimum of the first subspace, and serving the local minimum of the first subspace as the local minimum of the input designated space; and if the first subspace and the second subspace are selected, respectively inputting the first subspace and the second subspace into the recursive search algorithm to respectively search for the local minimum in the first subspace and the second subspace, and serving the smaller local minimum as the local minimum of the input designated space. ### Claim 10 (depends on 9) The global minimum searching method according to claim 9, wherein the step of calculating the corresponding value of the predetermined function comprises: changing the designated range on the ith axis of the input designated space to an input value of the predetermined function to define a third subspace, wherein the input value is one of the median and the sectional values; inputting the third subspace into the recursive search algorithm to search for a local minimum of the third subspace; and serving the local minimum of the third subspace as the corresponding value of the predetermined function. ### Claim 11 (depends on 9) The global minimum searching method according to claim 9, wherein the sectional values comprise two end values of the designated range on the ith axis of the input designated space, and the other sectional values are generated according to the two end values and a predetermined ratio. ### Claim 12 (depends on 9) The global minimum searching method according to claim 9, wherein the input designated space is equal to the first subspace plus the second subspace, and a junction between the first subspace and the second subspace on the ith axis of the input designated space is one of the sectional values. ### Claim 13 A global minimum searching system, comprising: a clustering module, for clustering a subclass of a plurality of space points in a multidimensional space into a plurality of clusters through a clustering algorithm, wherein each of the space points is corresponding to an error value in an evaluation function; a calculation module, for respectively calculating a plurality of ellipsoids for enclosing the clusters in the multidimensional space; and a search module, for respectively inputting a designated space corresponding to each of the ellipsoids into a recursive search algorithm to search for a local minimum among the error values corresponding to the space points within each of the designated spaces, and comparing the local minimums to obtain the space point corresponding to the minimum local minimum. ### Claim 14 (depends on 13) The global minimum searching system according to claim 13 further comprising: a feature capturing module, for capturing a plurality of corresponding feature points in a first image and a second image, wherein the first image and the second image are obtained by capturing a same object from different angles; and a prediction module, for calculating the space points according to the feature points, wherein the prediction module randomly selects k of the feature points through a robust estimation method and calculates a fundamental matrix between the first image and the second image according to the k feature points, so as to obtain one of the space points, and the prediction module repeats the step of randomly selecting k of the feature points t times to calculate t space points, wherein t and k are predetermined positive integers. ### Claim 15 (depends on 14) The global minimum searching system according to claim 14, wherein the robust estimation method is one of a LMedS method, a RANSAC method, and a M-estimator method. ### Claim 16 (depends on 14) The global minimum searching system according to claim 14, wherein the clustering module further selects p space points having the smallest error values from the t space points and defines the p space points as the subclass, wherein p is a positive integer smaller than or equal to t. ### Claim 17 (depends on 16) The global minimum searching system according to claim 16, wherein the clustering algorithm is one of a MST algorithm and a K-means algorithm. ### Claim 18 (depends on 13) The global minimum searching system according to claim 13, wherein each of the ellipsoids comprise N axes, each of the designated spaces is located at a center of the corresponding ellipsoid, each of the designated spaces comprises a designated range on each of the axes of the corresponding ellipsoid, and the N axes of each of the ellipsoids are arranged according to an execution order. ### Claim 19 (depends on 18) The global minimum searching system according to claim 18, wherein the calculation module further calculates an eigenvalue of each of the N axes in each of the ellipsoids to determine the execution order according to the eigenvalues. ### Claim 20 (depends on 18) The global minimum searching system according to claim 18, wherein the recursive search algorithm comprises: receiving an input designated space, wherein the input designated space is a subclass of one of the designated spaces; in the input designated space, all the designed ranges on the axes having their execution orders smaller than i are single values, all the designated ranges on the other axes are value ranges, and i is a positive integer smaller than or equal to N+1; and if the input designated space is equal to one of the designated spaces, i is equal to 1; if i is equal to N+1, serving the error value corresponding to the input designated space as the local minimum of the input designated space; if a length of the designated range on the ith axis of the input designated space is smaller than a predetermined threshold, serving a corresponding value of a median within the designated range on the ith axis in a predetermined function as the local minimum of the input designated space; if the length of the designated range on the ith axis of the input designated space is greater than the predetermined threshold, selecting a plurality of sectional values within the designated range on the ith axis; comparing a plurality of corresponding values of the sectional values in the predetermined function to select a first subspace or a first subspace and a second subspace in the input designated space; if only the first subspace is selected, inputting the first subspace into the recursive search algorithm to search for the local minimum of the first subspace, and serving the local minimum of the first subspace as the local minimum of the input designated space; and if the first subspace and the second subspace are selected, respectively inputting the first subspace and the second subspace into the recursive search algorithm to respectively search for the local minimum in the first subspace and the second subspace, and serving the smaller local minimum as the local minimum of the input designated space. ### Claim 21 (depends on 20) The global minimum searching system according to claim 20, wherein the step of calculating the corresponding value of the predetermined function comprises: changing the designated range on the ith axis of the input designated space into an input value of the predetermined function to define a third subspace, wherein the input value is one of the median and the sectional values; inputting the third subspace into the recursive search algorithm to search for a local minimum of the third subspace; and serving the local minimum of the third subspace as the corresponding value of the predetermined function. ### Claim 22 (depends on 20) The global minimum searching system according to claim 20, wherein the sectional values comprise two end values of the designated range on the ith axis of the input designated space, and the other sectional values are generated according to the two end values and a predetermined ratio. ### Claim 23 (depends on 20) The global minimum searching system according to claim 20, wherein the input designated space is equal to the first subspace plus the second subspace, and a junction between the first subspace and the second subspace on the ith axis of the input designated space is one of the sectional values.