From October 1998 to December 1999, a project called "Multiresolution texture compression and synthesis" was successfully performed in the Laboratory under contract with Intel Corporation.

First stage of the project was improvement of the popular “zero-tree” wavelet-based image compression algorithm. Afterwards the work concentrated around the two main problems:

• development of the texture compression method providing fast access to arbitrary pixel in compressed image file
• development of the technology for fast and resolution-independent generation of textures with desired properties

Texture Compression

The problem of texture compression with fast access to pixels was solved by developing an algorithm that compressed small (8-by-8 pixels) image blocks independently. The main idea was to use a set of local palettes for each block. Starting from a local palette of eight colors, more compact representation was developed, using 3 times less space for indices and 2 times less space for colors.

Compression of indices was achieved by partitioning the block into 4 independently palletized subsets (“clusters”), using only 2 or 4 colors for each cluster. In combination with original format of the palettes (sets of vectors in color space) representation, this allowed to obtain compression ratio 8 or 12, depending on local palettes format.

Well known format S3TC with similar functionality provides only 6 times compression. Results of the work were presented at ACM conference "Multimedia 2000" in Los-Angeles.

• Leonid Levkovich-Maslyuk, Pavel G. Kalyuzhny, Alexander Zhirkov. "Texture Compression with Adaptive Block Partitions". ACM Multimedia 2000, Los-Angelos.
• A. Pereberin "Hierarchical Approach for Texture Compression". GraphiCon'1999.
• S. Titov "Perceptually Based Image Comparison Method", Graphicon'2000.

Cascade texture generation

We have developed two algorithms for texture generation.
First of them, the cascade process, is described here. Under this process every pixel of the coarse version of the image is split into finer version pixels, using the predefined distribution of weights, as well as information of the adjacent pixels colors. The weights are chosen so as to satisfy the assumption of the image self-similarity, in particular, the energy distribution over the coarse pixel should be similar to energy distribution over the pixels of the surrounding 3-by-3 block (as shown in the picture). Similarity coefficient in the color space is chosen to be nonstationary, because for coefficient values < 0.5 the iterations converge to a smooth function; if the coefficient is too large, the resulting image becomes chaotic. In the suggested process we used normally distributed coefficients and stationary additive noise.

Changing the process parameters, one obtains textures with various statistical properties. When applied to natural starting image, the algorithm produces its “magnified version”, so that textured areas look approximately the same, and contours and edges are blurred according to “magnification”, i.e. look as if seen under microscope. Picture below shows original fragments of textures (left), and magnified textures after 3 iterations of the algorithm.

Team of researchers

• Leonid Levkovich-Maslyuk (Senior Scientist, The Keldysh Institute of Applied Mathematics, RAS)
  (levkovl@spp.keldysh.ru)

• Alexander Zhirkov:
  wavelet image compression, cluster texture compression, texture generation by the recursive fractal cascade partitioning
  (zh@graphics.cs.msu.su)
• Pavel Kalyuzhny:
  cluster texture compression
• Sergey Titov:
  compressed and original image comparison with the aid of ‘perceptual metric’ in LUV color space.
• Anton Pereberin:
  wavelet transforms, multiresolution texture generation with the aid of structuring image elements