Progressive Classification: A Multiresolution Approach

We describe and analyze a new algorithm for performing efficient classification on large two-dimensional data sets, typically large digital images. We use non-parametric classifiers on a lower resolution representation of the data set, namely the lowest sub-band of its Discrete Wavelet Transform decomposition (DWT). In this representation, each sample corresponds to a block of samples from the original data. At each step of the classification process, we decide to either classifty the whole block as belonging to a certain class, or to re-examine the data at a higher-resolution level, by moving down one level in the wavelet decomposition pyramid. In the parametric case, our analysis shows that, compared to traditional sample-by-sample classification techniques, this new progressive scheme is not only more efficient (in terms of the number of operations required), but also, under certain conditions, it is more accurate in its results. To illustrate this we present experimental results on the classification of large satellite images.