Piecewise linear models with guaranteed closeness to the data.

This paper addresses the problem of piecewise linear approximation of point sets without any constraints on the order of data points or the number of model components (line segments). We point out two problems with the maximum likelihood estimate (MLE) that present serious drawbacks in practical applications. One is that the parametric models obtained using a classical MLE framework are not guaranteed to be close to data points. It is typically impossible, in this classical framework, to detect whether a parametric model fits the data well or not. The second problem is related to accurately choosing the optimal number of model components. We first fit a nonparametric density to the data points and use it to define a neighborhood of the data. Observations inside this neighborhood are deemed informative; those outside the neighborhood are deemed uninformative for our purpose. This provides us with a means to recognize when models fail to properly fit the data. We then obtain maximum likelihood estimates by optimizing the Kullback-Leibler Divergence (KLD) between the nonparametric data density restricted to this neighborhood and a mixture of parametric models. We prove that, under the assumption of a reasonably large sample size, the inferred model components are close to their ground-truth model component counterparts. This holds independently of the initial number of assumed model components or their associated parameters. Moreover, in the proposed approach, we are able to estimate the number of significant model components without any additional computation.

Using virtual scans for improved mapping and evaluation.

In this paper we present a system to enhance the performance of feature correspondence based alignment algorithms for laser scan data. We show how this system can be utilized as a new approach for evaluation of mapping algorithms. Assuming a certain a priori knowledge, our system augments the sensor data with hypotheses ('Virtual Scans') about ideal models of objects in the robot's environment. These hypotheses are generated by analysis of the current aligned map estimated by an underlying iterative alignment algorithm. The augmented data is used to improve the alignment process. Feedback between data alignment and data analysis confirms, modifies, or discards the Virtual Scans in each iteration. Experiments with a simulated scenario and real world data from a rescue robot scenario show the applicability and advantages of the approach. By replacing the estimated 'Virtual Scans' with ground truth maps our system can provide a flexible way for evaluating different mapping algorithms in different settings.