RESUMO
Straightforward implementation of the exact pairwise nearest neighbor (PNN) algorithm takes O(N3) time, where N is the number of training vectors. This is rather slow in practical situations. Fortunately, much faster implementation can be obtained with rather simple modifications to the basic algorithm. In this paper, we propose a fast O(tauN2) time implementation of the exact PNN, where tau is shown to be significantly smaller than N, We give all necessary data structures and implementation details, and give the time complexity of the algorithm both in the best case and in the worst case. The proposed implementation achieves the results of the exact PNN with the same O(N) memory requirement.
RESUMO
This paper introduces a new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization. Reduced comparison search detects the activity of the code vectors and utilizes it on the classification of the training vectors. For training vectors whose current code vector has not been modified, we calculate distances only to the active code vectors. A large proportion of the distance calculations can be omitted without sacrificing the optimality of the partition. The new method is included in several fast GLA variants reducing their running times over 50% on average.
RESUMO
In this work, lossless grayscale image compression methods are compared on a medical image database. The database contains 10 different types of images with bit rates varying from 8 to 16 bits per pixel. The total number of test images was about 3000, originating from 125 different patient studies. Methods used for compressing the images include seven methods designed for grayscale images and 18 ordinary general-purpose compression programs. Furthermore, four compressed image file formats were used. The results show that the compression ratios strongly depend on the type of the image. The best methods turned out to be TMW, CALIC and JPEG-LS. The analysis step in TMW is very time-consuming. CALIC gives high compression ratios in a reasonable time, whereas JPEG-LS is nearly as effective and very fast.
