Parameter estimation apparatus, parameter estimation method, and computer-readable recording medium

Abstract

A parameter estimation apparatus 10 is an apparatus for calculating a threshold for separating a plurality of data points into outliers and inliers and estimating a parameter fitting the inliers. The parameter estimation apparatus 10 includes: a parameter estimation unit 13 configured to estimate the parameter by using the plurality of data points as input; a threshold setting unit 14 configured to calculate the threshold based on statistical information of residuals of the data points; and a convergence determination unit 15 configured to determine whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, and to cause the parameter estimation unit 13 and the threshold setting unit 14 to each execute processing again if the convergence determination unit 15 determines that convergence is not reached.

Claims

1. An apparatus for calculating a threshold for separating a plurality of data points into outliers and inliers and estimating a parameter fitting the inliers, the apparatus comprising: one or more computer-readable memories having program instructions stored therein; one or more processors that when executing the program instructions implement: a parameter estimation unit configured to estimate the parameter by using the plurality of data points as input; a threshold setting unit configured to calculate the threshold based on statistical information of residuals of the plurality of data points; a convergence determination unit configured to determine whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, and to cause the parameter estimation unit and the threshold setting unit to each execute processing again if the convergence determination unit determines that convergence is not reached; a residual calculation unit configured to acquire the plurality of data points and an initial value of the parameter and to calculate residuals of the plurality of data points relative to the acquired initial value; and a weight updating unit configured to, based on the calculated residuals, update weights assigned to the plurality of data points, wherein the parameter estimation unit estimates the parameter by also using, as input, the updated weights of the plurality of data points in addition to the plurality of data points, the threshold setting unit specifies residuals of the inliers, from among the calculated residuals, and calculates the threshold based on the statistical information of the specified residuals of the inliers, and the convergence determination unit outputs the estimated parameter as a parameter fitting the inliers if the convergence determination unit determines that convergence is reached, and sets the estimated parameter as the initial value and causes the residual calculation unit, the weight updating unit, the parameter estimation unit, and the threshold setting unit to each execute processing again if the convergence determination unit determines that convergence is not reached.

2. The parameter estimation apparatus according to claim 1, wherein the parameter estimation unit estimates the parameter by executing the iteratively reweighted least squares or M-estimation.

3. The parameter estimation apparatus according to claim 1, wherein the threshold setting unit calculates the statistical information from a prior probability distribution of the residuals of the inliers, and calculates the threshold based on the calculated statistical information.

4. The parameter estimation apparatus according to claim 3, wherein the prior probability distribution is expressed by a mixed normal distribution, and the threshold setting unit calculates an average and a standard deviation of the residuals of the inliers as the statistical information.

5. A method for calculating a threshold for separating a plurality of data points into outliers and inliers and estimating a parameter fitting the inliers, the method, performed by a computer, comprising: (a) estimating the parameter by using the plurality of data points as input; (b) calculating the threshold based on statistical information of residuals of the plurality of data points; and (c) determining whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, wherein the (a) and the (b) are each executed again if it is determined in the (c) that convergence is not reached; the method further comprising: (d) acquiring the plurality of data points and an initial value of the parameter and calculating residuals of the plurality of data points relative to the acquired initial value; and (e) based on the calculated residuals, updating weights assigned to the plurality of data points, wherein in the (a), the parameter is estimated by also using, as input, the weights of the plurality of data points updated in the (e) in addition to the plurality of data points, in the (b), residuals of the inliers, from among the residuals calculated in the (d), are specified and the threshold is calculated based on the statistical information of the specified residuals of the inliers, if it is determined in the (c) that convergence is reached, the estimated parameter is output as a parameter fitting the inliers in the (c), and if it is determined in the (c) that convergence is not reached, the parameter estimated in the (a) step is set as the initial value and the (d), the (e), the (a), and the (b) are each executed again.

6. The parameter estimation method according to claim 5, wherein, in the (a), the parameter is estimated by executing the iteratively reweighted least squares or M-estimation.

7. The parameter estimation method according to claim 5, wherein, in the (b), the statistical information is calculated from a prior probability distribution of the residuals of the inliers, and the threshold is calculated based on the calculated statistical information.

8. The parameter estimation method according to claim 7, wherein the prior probability distribution is expressed by a mixed normal distribution, and in the (b), an average and a standard deviation of the residuals of the inliers are calculated as the statistical information.

9. A non-transitory computer readable recording medium that includes a program recorded thereon that causes a computer to calculate a threshold for separating a plurality of data points into outliers and inliers and estimate a parameter fitting the inliers, the program including instructions that causes a computer to carry out: (a) a step of estimating the parameter by using the plurality of data points as input; (b) a step of calculating the threshold based on statistical information of residuals of the plurality of data points; and (c) a step of determining whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, and the (a) step and the (b) step are each executed again if it is determined in the (c) step that convergence is not reached; the program further incudes instructions that cause the computer to carry out: (d) a step of acquiring the plurality of data points and an initial value of the parameter and calculating residuals of the plurality of data points relative to the acquired initial value; and (e) a step of, based on the calculated residuals, updating weights assigned to the plurality of data points, in the (a) step, the parameter is estimated by also using, as input, the weights of the plurality of data points updated in the (e) step in addition to the plurality of data points, in the (b) step, residuals of the inliers, from among the residuals calculated in the (d) step, are specified and the threshold is calculated based on the statistical information of the specified residuals of the inliers, if it is determined in the (c) step that convergence is reached, the estimated parameter is output as a parameter fitting the inliers in the (c) step, and if it is determined in the (c) step that convergence is not reached, the parameter estimated in the (a) step is set as the initial value and the (d) step, the (e) step, the (a) step, and the (b) step are each executed again.

10. The non-transitory computer-readable recording medium according to claim 7, wherein, in the (a) step, the parameter is estimated by executing the iteratively reweighted least squares or M-estimation.

11. The non-transitory computer-readable recording medium according to claim 7, wherein, in the (b) step, the statistical information is calculated from a prior probability distribution of the residuals of the inliers, and the threshold is calculated based on the calculated statistical information.

12. The non-transitory computer-readable recording medium according to claim 11, wherein the prior probability distribution is expressed by a mixed normal distribution, and in the (b) step, an average and a standard deviation of the residuals of the inliers are calculated as the statistical information.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram illustrating a schematic configuration of a parameter estimation apparatus of an example embodiment of the present invention.

(2) FIG. 2 is a block diagram illustrating a specific configuration of the parameter estimation apparatus of the example embodiment of the present invention.

(3) FIG. 3 is a flowchart illustrating operations of the parameter estimation apparatus of the example embodiment of the present invention.

(4) FIG. 4 is a diagram illustrating a transition of residual distributions of inliers and outliers in the example embodiment of the present invention.

(5) FIG. 5 is a block diagram illustrating one example of a computer realizing the parameter estimation apparatus of the example embodiment of the present invention.

EXAMPLE EMBODIMENT

(6) In the following, a parameter estimation apparatus, a parameter estimation method, and a program of an example embodiment of the present invention will be described with reference to FIGS. 1 to 5.

(7) [Apparatus Configuration]

(8) First, the configuration of a parameter estimation apparatus 10 in the present example embodiment will be described with reference to FIG. 1. FIG. 1 is a block diagram illustrating a schematic configuration of the parameter estimation apparatus of the example embodiment of the present invention.

(9) The parameter estimation apparatus 10 in the present example embodiment, which is illustrated in FIG. 1, is an apparatus that calculates a threshold for separating a plurality of data points into outliers and inliers and estimates a parameter fitting the inliers. As illustrated in FIG. 1, the parameter estimation apparatus 10 includes a parameter estimation unit 13, a threshold setting unit 14, and a convergence determination unit 15.

(10) The parameter estimation unit 13 estimates a parameter by using the plurality of data points as input. The threshold setting unit 14 calculates the threshold based on statistical information of residuals of the plurality of data points. The convergence determination unit 15 determines whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold. Furthermore, the convergence determination unit 15 causes the parameter estimation unit 13 and the threshold setting unit 14 to each execute processing again if the convergence determination unit 15 determines that convergence is not reached.

(11) In such a manner, in the present example embodiment, a threshold for separating data points into outliers and inliers is calculated based on statistical information of residuals when a parameter is estimated iteratively. Due to this, according to the present example embodiment, a threshold for separating outliers and inliers in the estimation of a geometrical parameter fitting a plurality of data points, or to be more specific, the threshold in the IRLS, can be automatically set in an appropriate manner.

(12) Next, the configuration of the parameter estimation apparatus 10 in the present example embodiment will be described in detail with reference to FIG. 2. FIG. 2 is a block diagram illustrating a specific configuration of the parameter estimation apparatus of the example embodiment of the present invention. In the present example embodiment, the parameter estimation apparatus 10 includes a residual calculation unit 11 and a weight updating unit 12 in addition to the parameter estimation unit 13, the threshold setting unit 14, and the convergence determination unit 15, as illustrated in FIG. 2.

(13) The residual calculation unit 11 first acquires, as input, a plurality of data points and an initial value of a parameter. Furthermore, the residual calculation unit 11 calculates residuals of the plurality of data points relative to the acquired initial value.

(14) The weight updating unit 12, based on the calculated residuals, updates weights assigned to the plurality of data points. Furthermore, in the present example embodiment, the weight updating unit 12 updates the weights of the data points using a predetermined weighting function.

(15) In the present example embodiment, the parameter estimation unit 13 estimates a parameter fitting the weighted data points by also using, as input, the updated weights of the data points in addition to the plurality of data points.

(16) In the present example embodiment, the threshold setting unit 14 specifies the residuals of inliers, from among the residuals calculated by the residual calculation unit 11, and calculates a threshold based on statistical information of the specified residuals of the inliers. Specifically, the threshold setting unit 14 first acquires an initial value of the threshold. Next, the threshold setting unit 14 updates the acquired initial value using the statistical information and calculates a new threshold. Following this, the threshold setting unit 14 further updates the previously-updated threshold if the threshold needs to be calculated again.

(17) Furthermore, in the present example embodiment, examples of the statistical information include the average, standard deviation, median, skewness, kurtosis, entropy, and the like of the residuals of the inliers. The value of the statistical information changes depending on the probability distribution that the residuals of the inliers are expected to have.

(18) In the present example embodiment, the convergence determination unit 15 outputs the estimated parameter to the outside as a parameter fitting the inliers, if the convergence determination unit 15 determines that convergence is reached. Furthermore, if the convergence determination unit 15 determines that convergence is not reached, the convergence determination unit 15 sets the estimated parameter as an initial value and causes the residual calculation unit 11, the weight updating unit 12, the parameter estimation unit 13, and the threshold setting unit 14 to each execute processing again. That is, in the present example embodiment, parameter estimation is performed iteratively while updating the initial value of the parameter, until convergence of the parameter estimation is reached. Note that a specific example of the determination processing by the convergence determination unit 15 will be described later.

(19) In such a manner, in the present example embodiment, the parameter estimation apparatus 10 sets a threshold for separating data points into inliers and outliers based on residuals of the data points relative to the parameter, and further, iterates the processing for setting the threshold until the residuals converge. Then, when convergence is reached, the parameter estimation apparatus 10 outputs a parameter fitting the inliers.

(20) [Apparatus Operation]

(21) Next, the operations of the parameter estimation apparatus 10 in the present example embodiment will be described with reference to FIG. 3. FIG. 3 is a flowchart illustrating the operations of the parameter estimation apparatus of the example embodiment of the present invention. FIGS. 1 and 2 will be referred to as needed in the following description. Furthermore, in the present example embodiment, a parameter estimation method is implemented by causing the parameter estimation apparatus 10 to operate. Accordingly, the following description of the operations of the parameter estimation apparatus 10 is substituted for the description of the parameter estimation method in the present example embodiment.

(22) As illustrated in FIG. 3, first, when a plurality of data points, an initial value of a parameter, and an initial value of a threshold are input to the parameter estimation apparatus 10, the residual calculation unit 11 calculates, for each data point, a residual of the data point relative to the initial value of the parameter (step S1).

(23) For example, in step S1, a random number may be given as the initial value of the parameter, or predetermined default values (for example, “slope=1” and “intercept=0” for a straight line) may be given as the initial value of the parameter. Furthermore, when the data points and the parameter change continuously in time series, a parameter calculated at a previous time may be input as the initial value of the parameter. Also, if the reliability of the data points is acquired in advance as in the case of matching scores of image feature points, the initial value may be given by a least squares method using weighting based on the reliability.

(24) Furthermore, for example, the greatest-possible real-number value in the program may be given as the initial value of the threshold, or in cases in which the maximum of residuals is known through experimentation or experience, such values may be given as the initial value of the threshold. Also, when the data points and the parameter change continuously in time series, a value yielded by multiplying the maximum value of the residuals at a previous time by a constant may be given as the initial value of the threshold.

(25) Furthermore, it suffices for the number of data points input to be no less than the minimum number of data points required to express the parameter to be estimated. For example, the number is two or more if the parameter is a straight line and three or more if the parameter is a plane. Furthermore, if the number of points is not enough for parameter estimation, the parameter estimation apparatus 10 may output a flag indicating that parameter estimation cannot be executed or a parameter indicating that parameter estimation cannot be executed (for example, a parameter all values of which are zero or infinity) and end processing.

(26) Furthermore, in the present example embodiment, a residual is an indicator indicating the degree of fit of each data point with respect to the parameter. For example, examples of the residuals include geometrical distances formed by perpendicular lines extended down from data points to a line or plane expressed by the parameter, the Mahalanobis distance, which takes into account the noise dispersion of data points, and the like.

(27) Next, the weight updating unit 12 uses the residuals calculated in step S1 as input, and updates the weights of the data points in accordance with a predetermined weighting function (step S2). Examples of the weighting function to be used in step S2 include a function that returns values inversely proportional to the residuals, or to be specific, a function returning smaller values for greater residuals and returning greater values for smaller residuals.

(28) Next, the parameter estimation unit 13 estimates a parameter that fits the weighted data points by using, as input, the data points and the weights of the data points updated in step S2 (step S3).

(29) Next, the threshold setting unit 14 uses, as input, the residuals of the inliers, from among the residuals calculated in step S1, and sets a new threshold using statistical information of the residuals of the inliers (step S4).

(30) Next, the convergence determination unit 15 determines whether or not convergence of parameter estimation is reached, based on the parameter estimated in step S3 and the threshold calculated in step S4 (step S5).

(31) If the result of the determination in step S5 is that convergence is not reached, the convergence determination unit 15 sets the parameter estimated in step S3 as the initial value of the parameter and sets the threshold calculated in step S4 as the initial value of the threshold. Following this, the residual calculation unit 11 executes step S1 again using the new initial values. Accordingly, steps S2 to S4 are also executed again.

(32) On the other hand, if the result of the determination in step S5 is that convergence is reached, the convergence determination unit 15 outputs the parameter estimated in step S3 (step S6). Accordingly, processing by the parameter estimation apparatus 10 ends.

(33) Furthermore, the “convergence of parameter estimation” as used in the present example embodiment has the same meaning as “convergence” as used in common optimization calculations and numerical calculations, and refers to a state for which a determination is made that the values of the parameter and threshold would not change even if iterative calculations were repeated any further.

(34) Thus, for example, the convergence determination unit 15 can calculate at least one of the difference in the parameter and the difference in the threshold between a previous iteration of processing from step S1 to step S4 and the latest iteration of processing from step S1 to step S4, and can determine that convergence is reached when the difference is no greater than a certain value. Furthermore, for example, the convergence determination unit 15 can also determine that convergence is reached when the threshold set in the latest instance of step S4 is no greater than a certain value.

Specific Example

(35) Next, a specific example of the processing performed by the parameter estimation apparatus 10 will be described below. Note that in the specific example below, the vector θ is the parameter to be estimated, the vector x.sub.i is the ith data point, and f(x.sub.i; θ) is the function for calculating the residual of the ith data point relative to the parameter θ. Further, suppose that w.sub.i is the weight of the ith data point and λ is the threshold, and the total number of data points is N. Note that, in the present specific example, the weight w.sub.i is a real number between 0 and 1 (0≤w.sub.i≤1) because the weights assigned to the data points are relative.

(36) First, the IRLS is defined. The IRLS is an operation in which the optimization expressed by Formula. 1 below is repeated while gradually decreasing the threshold X from the initial value.

(37) $\begin{array}{cc}\underset{\varkappa }{\min }\underset{i=1}{\overset{N}{.Math.}}{w}_i{f\left(x_i;\theta \right)}^2+\lambda g\left(w_i\right)& \left[\mathrm{Formula}.1\right]\end{array}$

(38) Here, the function g(w.sub.i) is referred to as a penalty function, and is an arbitrarily-defined function that takes zero if w.sub.i approaches one. The present specific example will be described assuming that Formula. 2 below holds true.
g(w.sub.i)=1−√{square root over (w.sub.i)}).sup.2  [Formula. 2]

(39) In a given iteration (steps S1 to S4), each weight w.sub.i can be yielded by solving the equation expressed by Formula. 3 below, which is yielded when Formula. 1 above is differentiated with respect to w.sub.i and equated to zero.

(40) $\begin{array}{cc}{f\left(x_i;\theta \right)}^2+\lambda \frac{\partial g}{\partial w}{.Math.}_{w=w_i}=0& \left[\mathrm{Formula}.3\right]\end{array}$

(41) Formula. 4 below is yielded if Formula. 3 is solved for a case in which Formula. 2 above holds true.

(42) $\begin{array}{cc}{w}_i={\left(\frac{\lambda }{\lambda +{f\left(x_i;\theta \right)}^2}\right)}^2& \left[\mathrm{Formula}.4\right]\end{array}$

(43) If Formula. 4 above is seen as a function of X, it can be seen that X takes a value from zero to one. Furthermore, above-described Non-Patent Document 4 indicates that Formula. 4 above corresponds to the weighting function in the M-estimation according to Geman-McClure.

(44) Here, the above-described specific example will be further described in line with steps S1 to S5 illustrated in FIG. 3. First, in step S1, the residual calculation unit 11 calculates the residuals f(x.sub.i; θ) of data points x.sub.i in relation to the parameter θ.

(45) Next, in step S2, the weight updating unit 12 updates the weights w.sub.i of the data points x.sub.i in accordance with the threshold X and Formula. 4 above.

(46) Next, in step S3, the parameter estimation unit 13 substitutes the weights w.sub.i updated in step S2 into Formula. 1 above, and estimates the parameter θ that minimizes the optimization problem. For example, the solution of the optimization problem can be calculated using the Gauss-Newton method, the Levenberg-Marquardt method, and the like, taking advantage of the fact that Formula. 1 above is the sum of squares of mf(x.sub.i; θ).

(47) Next, in step S4, the threshold setting unit 14 uses the residuals f(x.sub.i; θ) calculated in step S1 and the weights w.sub.i updated in step S2 to set a new threshold X.

(48) Specifically, the threshold setting unit 14 first determines whether each data point is an inlier, based on the weight w.sub.i. Since the weights take a value between zero and one, the threshold setting unit 14 determines data points having weights w.sub.i no smaller than 0.5 as inliers, for example. Note that stricter determination results would be yielded if data points are determined as inliers when having weights w.sub.i close to one.

(49) Next, the threshold setting unit 14 sets the new threshold X using only the residuals of the inliers. Here, when supposing that the residuals of the inliers follow a normal distribution with an expectation value of μ and a standard deviation of σ, it can be considered that the residuals of the inliers are distributed within a range of μ+βσ, where β is a given constant. For example, given β=1 and β=2, approximately 84% and approximately 97% of the residuals f(x.sub.i; θ), respectively, would be within the range, and these residuals would be no greater than μ+βσ. That is, by performing an update so that λ=μ+βσ, an arbitrarily-defined ratio of inliers at the point of the iteration can be extracted.

(50) Next, in step S5, the convergence determination unit 15 determines whether or not convergence of the parameter estimation is reached, by using, as input, the parameter θ estimated in step S3 and the threshold λ set in step S4.

(51) As described above, for example, the convergence determination unit 15 compares the difference between the parameter θ or threshold λ yielded by executing a previous iteration of processing from step S1 to step S4 and the parameter θ or threshold λ yielded by executing the latest iteration of processing from step S1 to step S4, and determines that convergence is reached if the difference is no greater than a certain value. Further, the convergence determination unit 15 may determine that convergence is reached if the threshold λ set in the latest iteration of step S4 is smaller than a predetermined minimum value.

(52) If the result of the determination is that convergence is not reached, the convergence determination unit 15 sets the parameter estimated in step S3 as the initial value of the parameter and sets the threshold calculated in step S4 as the initial value of the threshold. Following this, step S1 and the following steps are executed again. On the other hand, if the result of the determination is that convergence is reached, the convergence determination unit 15 outputs the parameter estimated in step S3.

(53) [Effects in Example Embodiment]

(54) As described above, according to the present example embodiment, the threshold in the IRLS can be set automatically and appropriately, and outliers and inliers can be separated with high accuracy. Furthermore, as a result of this, a parameter that fits the inliers can be estimated with high accuracy.

(55) Here, the principle of how the inliers and outliers can be separated by iteratively executing above-described steps S1 to S4 will be described with reference to FIG. 4. FIG. 4 is a diagram illustrating the transition of residual distributions of inliers and outliers in the example embodiment of the present invention. FIG. 4 provides illustration from an initial state to a converged state, from the top level toward the bottom level.

(56) As illustrated in FIG. 4, two residual distributions are mixed in the initial state in the top level, or that is, the state in which hardly any distinction can be made between inliers and outliers. Based on the central limit theorem, this can be assumed as being a mixed normal distribution. Here, defining λ=μ+βσ in step S4 means that the weights w.sub.i of data points having residuals f(x.sub.i; θ) greater than μ+βσ rapidly decrease. Furthermore, the provision of larger weights to data points is equivalent to an increase in the proportion occupied by inliers in the parameter. If Formula. 1 above is solved in a state in which the inlier ratio has increased, a parameter θ better fitting the inliers is yielded through the calculation, and the state transitions to the state in the middle level of FIG. 4. Furthermore, if steps S1 to S4 are iterated, convergence to a state in which the inliers and outliers are separated is eventually reached, as illustrated in the bottom tier of FIG. 4.

(57) [Modifications]

(58) Here, modifications 1 to 4 in the present example embodiment will be described. The present invention is not limited to only the above-described example embodiment. In the present invention, various changes that can be understood by a so-called person skilled in the art can be applied to the above-described example embodiment. For example, the present invention can also be implemented in the forms indicated in the following modifications.

(59) (1) Modification 1

(60) The penalty function to be used is not limited to the above-described example embodiment. For example, Non-Patent Document 4 discloses various specific examples of penalty functions in detail. Furthermore, Non-Patent Document 4 discloses a method of conversion between the IRLS and the M-estimation. Thus, the various M-estimation functions disclosed in Non-Patent Document 3 can be used.

(61) (2) Modification 2

(62) The method for setting the threshold is not limited to the above-described example embodiment. For example, rapid decay may be suppressed by storing the threshold acquired through a previous iteration (the execution of steps S1 to S4) and setting the threshold so that the difference between the threshold acquired through the previous iteration and the threshold acquired through the present iteration is no greater than a certain value. Furthermore, for example, a calculation based on the conventional method using the decay constant may also be performed, and the smaller one or greater one of the values may be used as a new threshold. Also, for example, in a case in which the residual distribution of inliers is a Cauchy distribution, there would be no expectation value or standard deviation, and thus, a scale constant giving the mode and the half-width at half-maximum in place may be used.

(63) (3) Modification 3

(64) The method for determining convergence is not limited to the above-described example embodiment. For example, as the criterion for making the determination of convergence, the difference in the objective function expressed by Formula. 1 above before and after an iteration may be used, or the differences in the weights w.sub.i of data points may be used. Here, the convergence determination unit 15 receives, as input, the objective function expressed by Formula. 1 above or the weights w.sub.i.

(65) (4) Modification 4

(66) Data input to the parameter estimation apparatus 10 is not limited to the examples described in the above-described example embodiment. For example, an initial value of weight can be input in place of an initial value of a parameter. In this case, the parameter estimation unit 13 executes processing first, and then processing is executed in the order of the residual calculation unit 11, the weight updating unit 12, the threshold setting unit 14, and the convergence determination unit 15 in the parameter estimation apparatus 10. Note that the order in which processing performed by the respective units is executed can be changed as appropriate.

(67) [Program]

(68) It suffices for the program in the present example embodiment to be a program that causes a computer to execute steps S1 to S6 illustrated in FIG. 3. The parameter estimation apparatus and the parameter estimation method in the present example embodiment can be realized by installing this program onto a computer and executing the program. In this case, the central processing unit (CPU) of the computer functions and performs processing as the residual calculation unit 11, the weight updating unit 12, the parameter estimation unit 13, the threshold setting unit 14, and the convergence determination unit 15.

(69) Furthermore, the program in the present example embodiment may be executed by a computer system structured using a plurality of computers. In this case, for example, each computer may function as one out of the residual calculation unit 11, the weight updating unit 12, the parameter estimation unit 13, the threshold setting unit 14, and the convergence determination unit 15.

(70) Here, a computer that realizes the parameter estimation apparatus 10 by executing the program in the present example embodiment will be described with reference to FIG. 5. FIG. 5 is a block diagram illustrating one example of a computer realizing the parameter estimation apparatus of the example embodiment of the present invention.

(71) As shown in FIG. 5, a computer 110 includes a CPU 111, a main memory 112, a storage apparatus 113, an input interface 114, a display controller 115, a data reader/writer 116, and a communication interface 117. These units are each connected so as to be capable of performing data communications with each other through a bus 121.

(72) The CPU 111 opens the program (code) according to this example embodiment, which has been stored in the storage device 113, in the main memory 112 and performs various operations by executing the codes in a predetermined order. The main memory 112 is typically a volatile storage device such as a DRAM (Dynamic Random Access Memory). Also, the program according to this example embodiment is provided in a state stored in a computer-readable recording medium 120. Note that the program according to this example embodiment may be distributed on the Internet, which is connected through the communications interface 117.

(73) Also, other than a hard disk drive, a semiconductor storage device such as a flash memory can be given as a specific example of the storage device 113. The input interface 114 mediates data transmission between the CPU 111 and an input device 118, which may be a keyboard or mouse. The display controller 115 is connected to a display device 119, and controls display by the display device 119.

(74) The data reader/writer 116 mediates data transmission between the CPU 111 and the recording medium 120, and executes reading of a program from the recording medium 120 and writing of processing results in the computer 110 to the recording medium 120. The communications interface 117 mediates data transmission between the CPU 111 and other computers.

(75) Also, general-purpose semiconductor storage devices such as CF (Compact Flash (registered trademark)) and SD (Secure Digital), a magnetic recording medium such as a Flexible Disk, or an optical recording medium such as a CD-ROM (Compact Disk Read-Only Memory) can be given as specific examples of the recording medium 120.

(76) Note that the parameter estimation device 10 according to this example embodiment can be realized not only by a computer with a program installed, but also by using hardware corresponding to each part. Further, a configuration may be adopted in which a portion of the parameter estimation device 10 is realized by a program, and the remaining portions are realized by hardware. Also, in the parameter estimation device 10, each unit may be realized as a separate unit.

(77) Some portion or all of the example embodiments described above can be realized according to (supplementary note 1) to (supplementary note 15) described below, but the below description does not limit the invention.

(78) (Supplementary Note 1)

(79) An apparatus for calculating a threshold for separating a plurality of data points into outliers and inliers and estimating a parameter fitting the inliers, the apparatus including:

(80) a parameter estimation unit configured to estimate the parameter by using the plurality of data points as input;

(81) a threshold setting unit configured to calculate the threshold based on statistical information of residuals of the plurality of data points; and

(82) a convergence determination unit configured to determine whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, and to cause the parameter estimation unit and the threshold setting unit to each execute processing again if the convergence determination unit determines that convergence is not reached.

(83) (Supplementary Note 2)

(84) The parameter estimation apparatus according to Supplementary Note 1, further including:

(85) a residual calculation unit configured to acquire the plurality of data points and an initial value of the parameter and to calculate residuals of the plurality of data points relative to the acquired initial value; and

(86) a weight updating unit configured to, based on the calculated residuals, update weights assigned to the plurality of data points, wherein

(87) the parameter estimation unit estimates the parameter by also using, as input, the updated weights of the plurality of data points in addition to the plurality of data points,

(88) the threshold setting unit specifies residuals of the inliers, from among the calculated residuals, and calculates the threshold based on the statistical information of the specified residuals of the inliers, and

(89) the convergence determination unit

(90) outputs the estimated parameter as a parameter fitting the inliers if the convergence determination unit determines that convergence is reached, and

(91) sets the estimated parameter as the initial value and causes the residual calculation unit, the weight updating unit, the parameter estimation unit, and the threshold setting unit to each execute processing again if the convergence determination unit determines that convergence is not reached.

(92) (Supplementary Note 3)

(93) The parameter estimation apparatus according to Supplementary Note 2, wherein the parameter estimation unit estimates the parameter by executing the iteratively reweighted least squares or M-estimation.

(94) (Supplementary Note 4)

(95) The parameter estimation apparatus according to Supplementary Note 2 or 3, wherein the threshold setting unit calculates the statistical information from a prior probability distribution of the residuals of the inliers, and calculates the threshold based on the calculated statistical information.

(96) (Supplementary Note 5

(97) The parameter estimation apparatus according to Supplementary Note 4, wherein the prior probability distribution is expressed by a mixed normal distribution, and

(98) the threshold setting unit calculates an average and a standard deviation of the residuals of the inliers as the statistical information.

(99) (Supplementary Note 6)

(100) A method for calculating a threshold for separating a plurality of data points into outliers and inliers and estimating a parameter fitting the inliers, the method including:

(101) (a) a step of estimating the parameter by using the plurality of data points as input;

(102) (b) a step of calculating the threshold based on statistical information of residuals of the plurality of data points; and

(103) (c) a step of determining whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, wherein

(104) the (a) step and the (b) step are each executed again if it is determined in the (c) step that convergence is not reached.

(105) (Supplementary Note 7)

(106) The parameter estimation method according to Supplementary Note 6, further including:

(107) (d) a step of acquiring the plurality of data points and an initial value of the parameter and calculating residuals of the plurality of data points relative to the acquired initial value; and

(108) (e) a step of, based on the calculated residuals, updating weights assigned to the plurality of data points, wherein

(109) in the (a) step, the parameter is estimated by also using, as input, the weights of the plurality of data points updated in the (e) step in addition to the plurality of data points,

(110) in the (b) step, residuals of the inliers, from among the residuals calculated in the (d) step, are specified and the threshold is calculated based on the statistical information of the specified residuals of the inliers,

(111) if it is determined in the (c) step that convergence is reached, the estimated parameter is output as a parameter fitting the inliers in the (c) step, and

(112) if it is determined in the (c) step that convergence is not reached, the parameter estimated in the (a) step is set as the initial value and the (d) step, the (e) step, the (a) step, and the (b) step are each executed again.

(113) (Supplementary Note 8)

(114) The parameter estimation method according to Supplementary Note 7, wherein, in the (a) step, the parameter is estimated by executing the iteratively reweighted least squares or M-estimation.

(115) (Supplementary Note 9)

(116) The parameter estimation method according to Supplementary Note 7 or 8, wherein, in the (b) step, the statistical information is calculated from a prior probability distribution of the residuals of the inliers, and the threshold is calculated based on the calculated statistical information.

(117) (Supplementary Note 10)

(118) The parameter estimation method according to Supplementary Note 9, wherein the prior probability distribution is expressed by a mixed normal distribution, and

(119) in the (b) step, an average and a standard deviation of the residuals of the inliers are calculated as the statistical information.

(120) (Supplementary Note 11)

(121) A computer readable recording medium that includes a program recorded thereon that causes a computer to calculate a threshold for separating a plurality of data points into outliers and inliers and estimate a parameter fitting the inliers, the program including instructions that causes a computer to carry out:

(122) (a) a step of estimating the parameter by using the plurality of data points as input;

(123) (b) a step of calculating the threshold based on statistical information of residuals of the plurality of data points; and

(124) (c) a step of determining whether or not convergence of the estimation of the parameter is reached based on the estimated parameter and the calculated threshold, and

(125) the (a) step and the (b) step are each executed again if it is determined in the (c) step that convergence is not reached.

(126) (Supplementary Note 12)

(127) The computer-readable recording medium according to Supplementary Note 11, wherein the program further includes instructions that cause the computer to carry out:

(128) (d) a step of acquiring the plurality of data points and an initial value of the parameter and calculating residuals of the plurality of data points relative to the acquired initial value; and

(129) (e) a step of, based on the calculated residuals, updating weights assigned to the plurality of data points,

(130) in the (a) step, the parameter is estimated by also using, as input, the weights of the plurality of data points updated in the (e) step in addition to the plurality of data points,

(131) in the (b) step, residuals of the inliers, from among the residuals calculated in the (d) step, are specified and the threshold is calculated based on the statistical information of the specified residuals of the inliers,

(132) if it is determined in the (c) step that convergence is reached, the estimated parameter is output as a parameter fitting the inliers in the (c) step, and

(133) if it is determined in the (c) step that convergence is not reached, the parameter estimated in the (a) step is set as the initial value and the (d) step, the (e) step, the (a) step, and the (b) step are each executed again.

(134) (Supplementary Note 13)

(135) The computer-readable recording medium according to Supplementary Note 12, wherein, in the (a) step, the parameter is estimated by executing the iteratively reweighted least squares or M-estimation.

(136) (Supplementary Note 14)

(137) The computer-readable recording medium according to Supplementary Note 12 or 13, wherein, in the (b) step, the statistical information is calculated from a prior probability distribution of the residuals of the inliers, and the threshold is calculated based on the calculated statistical information.

(138) (Supplementary Note 15)

(139) The computer-readable recording medium according to Supplementary Note 14, wherein the prior probability distribution is expressed by a mixed normal distribution, and

(140) in the (b) step, an average and a standard deviation of the residuals of the inliers are calculated as the statistical information.

(141) The present invention has been described with reference to an example embodiment above, but the present invention is not limited to the above-described example embodiment. Within the scope of the present invention, various changes that could be understood by a person skilled in the art could be applied to the configurations and details of the invention.

INDUSTRIAL APPLICABILITY

(142) As described above, according to the present invention, a threshold for separating outliers and inliers can be set appropriately in the estimation of a geometrical parameter fitting a plurality of data points. The present invention is useful in fields in which geometrical parameters fitting a plurality of data points need to be estimated, such as statistics, signal processing, image processing, computer vision, and the like.

LIST OF REFERENCE SIGNS

(143) 10 Parameter estimation apparatus 11 Residual calculation unit 12 Weight updating unit 13 Parameter estimation unit 14 Threshold setting unit 15 Convergence determination unit 110 Computer 111 CPU 112 Main memory 113 Storage apparatus 114 Input interface 115 Display controller 116 Data reader/writer 117 Communication interface 118 Input device 119 Display apparatus 120 Recording medium 121 Bus