Abstract

The WaveStat algorithm deals with the exploratory Cluster Analysis of picture data and wavelet-built coefficients. Cluster Analysis means to collect elements (i.e. pixels) of the same property (in this context this means: gray value) to a cluster. These clusters can be visualized by colorizing them or by reconstructing them to a grayscale picture.

We are showing that a cluster analysis can be done directly on picture data (pixels) or on wavelet coefficients resulting from a wavelet analysis of the image. The clustered coefficients then are transformed back using the inverse wavelet tranform. The quality of this reconstruction depends on

• the used wavelet-transform,
• the used cluster algorithm and
• the number of iterations when performing the inverse wavelet-transform.

The WaveStat algorithm uses the redundancy of wavelet coefficients to apply cluster analysis on these to achieve an image compression.

Software

WaveStat is a software running under X-Windows (portation to other OS's would be simple) that provides all required functions within one program. The menu-driven user interface is simple and functional, all operations are selectable in the main dialog. All examined images are of square shape for simplicity and performance reasons; they all are grayscaled. In principle, an extension to coloured, non-square pictures is possible and planned for future work. WaveStat reads raw, binary and pgm-coded grayscale images.

Results

In general the results obtained with WaveStat can be divided up into two main groups: the results of the cluster analyses of the whole image value matrix and the results of the examination of wavelet coefficients.

A combination between those main procedures provides the analysis of standard transform wavelet coefficients. A division into subsets of wavelet coefficients according to the levels of iteration of the pyramid algorithm and a single cluster analysis of the coefficients of each iteration level is not possible so that the coefficients of the whole image have to be processed in one cluster analysis.

The type of cluster algorithm is a relevant factor for the analysis of nonstandard wavelet coefficients and the clustering of the original image. For the clustering of standard wavelet coefficients the obtained results show a minor importance because reconstruction artifacts are mainly caused by an interaction effect with the method of implementation of the wavelet transform. The best results for all types of images were achieved with the single linkage and the complete linkage method in combination with the optimization. By the introduction of a threshold or tolerance value the optimization strategy of the original cluster algorithm is changed with a kind of pre-clustering step. Methods like average linkage or flexible strategy have proven not being suitable for this additional optimization strategy.

The results of the of the cluster analysis of the standard transform wavelet coefficients could be neglected because during the inverse wavelet image reconstruction the resulting new clustered and averaged wavelet coefficients were processed as a whole and not separately as filter types and levels of iterations.

The quality of image reconstruction was less dependent on the type of clustering method or optimization methods but more influenced by the wavelet function type and the chosen values for the WaveStat parameters 'level' and 'tolerance'.

Generally the image reconstruction from clustered and averaged wavelets received from non-standard wavelet analysis algorithms has proven a high quality compared to the results for standard transform algorithms.

Some artifacts in the reconstruction, however, could be noticed according to the chosen wavelet basis function. For Daubechies wavelet basis functions there were wave-shaped irregularities in the reconstructed image increasing with the number of vanishing moments, reconstructions based on Haar wavelet coefficients showed artifacts in rectangular forms but without any blurring of contours or loss of edge detection.

Conclusion

WaveStat has shown some basic facts:

• clustering image data is possible and sensible; for image data as well as wavelet coefficients
• cluster analysis has to be modified to guarantee good results: the distance matrix must not be built the conventional way but differences have to be computed for each pair of pixels. This will raise the cost of computation significantly, so the algorithm has to be improved.
• The procedure does not work correctly on standard wavelet coefficients.
• WaveStat may be a good starting point for classification procedures as well as a new image compression method which works very effectively.

Examples

Fig. 2 shows a cluster analysis of a greyscale picture with reconstruction. First row: original picture (resolution: 128*128), colorized cluster visualization, reconstructed picture from cluster data, difference data between original and reconstructed picture.