Lossless compression using inversions on multiset permutations

Summary form only given. Linear prediction schemes, such as JPEG or BJPEG, are simple and normally result in a significant reduction in source entropy. Occasionally the entropy of the prediction error becomes greater than that of the original image. Such situations frequently occur when the image data has discrete gray-levels located within certain intervals. To alleviate this problem, various authors have suggested different methods. However, the techniques reported require two-pass algorithms. In this paper, we give a one-pass algorithm based on inversions of a multiset permutation. We obtain comparable results when we applied JPEG and even better results when we applied BJPEG on preprocessed image, which is treated as a multiset permutation. Lehmer [1964] describes a relatively short method for recovering a permutation π from its inversion vector. Lehmer-type inversion methods may create more compact data (which has a lower dynamic range, with respect to the original data). We extend the definition of Lehmer-type inversions from permutations to multiset permutations in a similar manner. We give algorithms that generate inversion vectors of multiset permutations and then methods for recovering a multiset permutation from a corresponding inversion vector [Arnavut, 1995]. Results obtained from some images (green band) of the USC-database are shown