BibTeX entry

@PHDTHESIS{200308Roberto_Fraile,
  AUTHOR={Roberto Fraile},
  TITLE={The Minimum Description Length Method with an Application
    to the Visual Estimation of Vehicle Trajectories},
  SCHOOL={Reading University},
  MONTH=Aug,
  YEAR=2003,
  URL={http://www.bmva.org/theses/2003/2003-fraile.pdf},
}

Abstract

This thesis investigates methods for comparing models of different complexity, using the Minimum Description Length (MDL) method. Some applications to Computer Vision are described. The data are sequences of filmed images, and the models are vehicles and their trajectories. In the MDL approach, a model is favoured if it can be used to obtain good compression of the data. A major problem in Computer Vision is the choice of adequate model complexity. Simple models might not capture the essential properties of the data, whereas complex models might be strongly affected by noise, resulting in overfitting. Model Selection methods such as Maximum Likelihood are biased towards complex models. Such overfitting can be avoided by carefully weighting the models according to their complexity. MDL overcomes the problem of overfitting by considering models as Turing machines, and assigning to each model a prior probability. Models are favoured if they have a low prior probability and if they achieve a good compression of the data. The MDL method is presented, from a combinatorial point of view, as an enumeration of the leaves of a binary tree. This binary tree corresponds to the input language of a Universal Turing machine. Since the enumeration, and with it the MDL method, is not computable, computable approximations to it are devised. A software package written in the language Mathematica is used to facilitate the development of these computable approximations to MDL. The computable approximations to MDL have been tested with experiments in vehicle tracking and trajectory modelling and estimation. Entire image sequences are compressed using 3D models for vehicle shapes and trajectories. In separate experiments, trajectory data are compressed using a dynamics-based model for trajectories. The experiments show that the length after compression is the basis of a reliable method for choosing between trajectory models. In addition, vehicle trajectories produced by a vehicle tracker are segmented and labelled using a Hidden Markov Model. Experimental results illustrate that a simple model is able to filter out noise and produce a simple segmentation of the trajectory based on the driver’s actions. The conclusion is that it is possible to compare models according to their ability to compress data. The data compression can be carried out with the aid of generic and standard algorithms, such as the Lempel-Ziv-Welch (LZW) compression algorithm or the logstar code.