Problems in Model Selection for Range Segmentation

Problems in Model Selection for Range Segmentation

The available information theoretic model selection criteria are based on the assumptions that noise is very small and the data size is large enough. However, in visual data segmentation algorithms, one usually deals with noisy regions of data, some of which are small localised regions that are to be extended later. As a result, neither of the above assumptions is usually valid.

The other crucial problem is that almost all the information-theoretic model selection criteria measure the complexity of a model only by its number of parameters1. Hence, if there are different models with the same number of parameters (i.e. same complexity), there will be some difficulty in selecting between those models. In fact, the available model selection information-theoretic model selection criteria assume the set of candidate models to be nested, whereas, in many applications, such as range segmentation of curved objects, the set of candidate models may consist of non-nested models.

Finally, all the available model selection methods have their roots in statistics, the physical and geometrical characteristics of the problem have been ignored.

As a result none of the existing model selection criteria is capable of identifying the true underlying model for visual data in motion segmentation and range segmentation applications.

Surface Selection Criterion

To overcome the above problems in model selection, we proposes to view the sum of bending and twisting energies of a surface as a measure of the surfaces roughness and the sum of squared residuals as a measure of fidelity to the true data. There should be an acceptable compromise between these two factors. To formulate the proposed Surface model Selection Criterion (SSC), different points of a surface are viewed as hypothetical springs constraining the surface as shown in Figure 1.

If the surface has little stiffness, then the surface bends and twists to meet the points. Hence, the surface fits itself to noise and the sum of squared residuals between the range measurements and their associated points on the surface will be small. This bending and twisting in turn increases the amount of strain energy accumulated by the surface.

Figure 1-Representation a malleable surface supported by hypothetical springs. The range measurements are shown by black circles.

As one may expect, increasing the number of parameters of a surface leads to larger bending and twisting energies as the surface has more degrees of freedom and consequently the surface can be fitted to the data by bending and twisting itself so that a closer fit to the measured data results. This can be inferred from the bending energy formula (Equation 1). However, the higher the number of parameters for a surface model, the less the sum of squared residuals. For instance, in the extreme case, if the number of parameters is equal to the number of data points (which are used in the fitting process), then the sum of squared residuals will be zero whereas its sum of energies will be maximised.

As shown in [2], if a plate is bent by a uniformly distributed bending moment so that the xy and yz planes are the principal planes of the deflected surface, then the strain energy (for bending and twisting) of the plate can be expressed as:

(1)

where D is the flexural rigidity of the surface and ν is Poisson’s ratio (ν should be very small because in real world-objects the twisting energy in comparison with the bending energy is small). In all the experiments reported in this thesis, n is assumed to be 0.01. As our experiments show, the performance of SSC is not sensitive to the small variation of n . The strain energy is computed as a measure of complexity of the model.

In order to scale the strain energy, it has been divided by the strain energyof the model with the highest number of parameters (E_max). Therefore, D has been eliminated from the following formulations.

To establish the trade-off between the sum of squared residuals and the strain energy E_{Bending+Twist}, a function SSC is defined such that:

where δ is the scale of noise for the highest surface (the surface with the highest number of parameters). The reason for using the scale of noise of the highest surface (as explained by Kanatani [1]) is that the scale of noise for the correct model and the scale of noise of the higher order models (higher than the correct model) must be close for the fitting to be meaningful. Therefore, it is the best estimation of the true scale of noise, which is available at this stage.

An accurate estimate of the scale of noise δ can be computed by where N is the number of data points and P is the number of parameters of the highest surface. Use of this formula for the scale of noise can be justified by the fact that if the model is correct, then is subjected to a χ² distribution with N-P degrees of freedom [1]. The energy term has been multiplied by the number of parameters P in order to penalise the choice of a higher order (than necessary) model. Such a simple measure produces good discrimination and improves the accuracy of the model selection criterion.

Having devised a reasonable compromise between fidelity to data and the complexity of the model, the model selection task is then reduced to choosing the surface that has the minimum value of SSC.

References

[1] Kanatani, K., What Is the Geometric AIC? Reply to My Reviewers,1987(unpublished).

[2] Timoshenko, p. S. and Krieger, S. W. Theory of Plates and Shells. In: Chapter 2, Pure Bending of Plates, eds. Timoshenko, p. S. and Krieger, S. W. McGraw-Hill, 1959.pp. 46-47.

Top

Index

Surface Selection Criterion (SSC)

Parametric Curved Surface Range Segmentation algorithm

Experimental Results

By Niloofar Gheissari and Alireza Bab-Hadiashar

May 2004