A Minimum Description Length-Based Image Segmentation Procedure, and its Comparison with a Cross-Validation-Based Segmentation Procedure

Abstract

Image segmentation is a very important problem in image analysis, as quite often it is a key component of a good practical solution to a real-life imaging problem. It aims to partition a digital image into a set of nonoverlapping homogeneous regions. One approach to segmenting an image is to fit a piecewise constant function to the image and define the segmentation by the discontinuity points of the fitted function. The article's first contribution is to present a new and automatic segmentation procedure which follows this piecewise constant function fitting approach. This procedure is based on Rissanen's minimum description length (MDL) principle and consists of two components: (a) an MDL-based criterion in which the “best” segmentation (i.e., the “best” fitted piecewise constant function) is defined as its minimizer and (b) a fast-merging algorithm that attempts to locate this minimizer. As a second contribution, the new MDL-based procedure is compared with a cross-validation based segmentation procedure. Empirical results from a simulation study suggest the new MDL-based procedure is superior. Some possible extensions of the MDL-based procedure are also described.

Key Words:

• Cross-validation
• Image segmentation
• Minimum description length
• Piecewise constant function fitting
• Region merging
• Segmentation quality evaluation.