Improved coding of atoms in image compression by matching pursuits (MP) after a wavelet decomposition is achieved. The positions of atoms in the wavelet sub-bands are communicated by run length coding. The MERGE coding scheme replaces individual coding of any alphabet of symbols by dividing the symbols into groups and run length coding their positions. It is shown theoretically that the use of MERGE with an efficient run length coder approaches the theoretical entropy of an alphabet of symbols. The embedded nature of MERGE makes it a near-ideal coding scheme for the amplitudes of atoms. An additional layer of MERGE coding for the basis indices of atoms approaches the theoretical optimum and is superior to either separable or combined Huffman coding.

In this paper we propose a novel method of applying motion estimation techniques to human authentication by iris matching. By exploiting the inherent differences in vector fields generated by comparing same-class and different-class irises, good matching performance was obtained. The method was applied to 600 images of 150 eyes from the Bath database. The best settings of several parameters were determined through experimental minimization of equal error rate (EER), which was estimated from the matching and nearest non matching distributions. The effect of iris rotation was studied through circular shifts and seen to have minimal effects on match/non match scores. The standard deviation of the X-vector data was found to give best performance with 100% correct recognition rate (CRR) and a flat receiver operating characteristics (ROC) indicating no false accepts or rejects within the data with an estimated EER of 0.007. Images compressed with JPEG2000 at 0.5 bpp were similarly processed resulting in an EER of 0.014 at a normalized image size of 1536 bytes.

A first investigation into the effects of cataract surgery and pupil dilation on iris recognition performance is presented. Images from 3 patients were acquired before cataract surgery and two weeks afterwards. Successful iris segmentation was achieved in all cases despite additional specular reflections in the pupil due to the artificial lens. No visible change in iris structure was noticed and automatic matching of pre and postoperative images produced correct identification is all cases. To analyze the effect of dilation, images from 11 subjects were captured before administration of drops and fifteen minutes afterwards. Significant changes in pupil structure were observed with time and the deformation was found to be non-elastic in most cases. A novel shape-description method was used to model irregular pupil outlines, since conventional circle-based localization methods proved inadequate. Despite accurate localization, highly deformed irises failed to match correctly and the CRR obtained was only 86.67%. The results question the widely used assumption of elastic iris deformation and indicate that further research is required to develop a more realistic description of the behavior of iris structure upon dilation.

This paper presents a novel iris coding method based on differences of discrete cosine transform (DCT) coefficients of overlapped angular patches from normalized iris images. The feature extraction capabilities of the DCT are optimized on the two largest publicly available iris image data sets, 2,156 images of 308 eyes from the CASIA database and 2,955 images of 150 eyes from the Bath database. On this data, we achieve 100 percent Correct Recognition Rate (CRR) and perfect Receiver-Operating Characteristic (ROC) Curves with no registered false accepts or rejects. Individual feature bit and patch position parameters are optimized for matching through a product-of-sum approach to Hamming distance calculation. For verification, a variable threshold is applied to the distance metric and the False Acceptance Rate (FAR) and False Rejection Rate (FRR) are recorded. A new worst-case metric is proposed for predicting practical system performance in the absence of matching failures, and the worst case theoretical Equal Error Rate (EER) is predicted to be as low as 2.59 x 10(-4) on the available data sets.

In the above titled paper (ibid., vol. 29, no. 4, pp. 586-595, Apr 07), there was a transcription error in the definition of the DCT (Discrete cosine transform). The correct definition is provided here: http://csdl.computer.org/comp/trans/tp/2007/09/tp02.pdf

The resilience of identity verification systems to subsampling and compression of human iris images is investigated for three high-performance iris-matching algorithms. For evaluation, 2156 images from 308 irises from the extended Chinese Academy of Sciences Institute of Automation database were mapped into a rectangular format with 512 pixels circumferentially and 80 radially. For identity verification, the 48 rows that were closest to the pupil were taken and images were resized by subsampling their Fourier coefficients. Negligible degradation in verification is observed if at least 171 circumferential and 16 radial Fourier coefficients are preserved, which would correspond to sampling the polar image at 342 times 32 pixels. With JPEG2000 compression, improved matching performance is observed down to 0.3 b/pixel (bpp), attributed to noise reduction without a significant loss of texture. To ensure that the iris-matching algorithms studied are not degraded by image compression, it is recommended that normalized iris images should be exchanged at 512 times 80 pixel resolution, compressed by JPEG 2000 to 0.5 bpp. This achieves a smaller file size than the ANSI/INCITS 379-2004 iris image interchange format.

The resilience of identity verification systems to subsampling and compression of human iris images is investigated for three high performance iris matching algorithms. For evaluation, 2156 images from 308 eyes are mapped into a rectangular format with 512 pixels circumferentially and 80 radially. For identity verification, the 48 rows nearest the pupil were taken and the images were subsampled by Fourier domain processing. Negligible degradation in verification is observed if at least 171 circumferential and 16 radial Fourier coefficients are preserved, corresponding to sampling at 342 by 32 pixels. With compression by JPEG 2000, improved performance is observed down to 0.3 bpp, attributed to noise reduction without significant loss of texture. To ensure that no algorithm is degraded, it is recommended that normalized iris images should be exchanged at 512 times 80 pixel resolution, compressed by JPEG 2000 to 0.5 bpp. This achieves a smaller file size than the proposed M1 biometric data interchange format

We present a novel video coding system based on the motion compensation and estimation model of H.264 and a hybrid wavelet/matching pursuits image coder for residual frames. After wavelet pretransformation, a high performance matching pursuits codebook is used to find a series of atoms which are coded by the MERGE coder. The combination of these two techniques produces a highly embedded data stream that can be easily truncated at any desired point. Optimum settings of some key parameters are investigated and a series of experiments are performed. The system works very efficiently and can outperform H.264 at low and medium bit rates

Different dictionaries of basis functions are applied to the four types of sub-bands in coding a wavelet decomposed image by matching pursuits. A dictionary of 2D bases is formed separably from a set of previously determined ID bases. Four masks are defined which select different subsets of the dictionary for coding LL, HL, LH and HH sub-bands. Masks are found by progressively searching for bases which give the highest PSNR at a desired bit rate. It is found that the PSNR of a compressed image increases rapidly at first as bases are added to the masks. It then declines and oscillates. Over a range of small numbers of bases for any bit rate the PSNR is better than with the full codebook. Using sparse dictionaries adapted to different sub-bands gives low computational cost while maintaining high quality, but shows dependency on the bit rate and the image.

A novel eyelash removal method for preprocessing of human iris images in a human iris recognition system is presented. The method filters each occluded pixel along an axis perpendicular to the eyelash direction, and accepts the filtered value if it changes by more than a certain threshold. This allows partially occluded regions of the iris to be included in iris coding which would previously have been excluded. The method is applied with three iris coding algorithms on an extended 308 class CASIA database and large improvements are shown in the matching performance of two methods, with a modest improvement in the third.

The 'basis picking' algorithm is an effective method for selecting dictionaries of basis functions for coding of data by matching pursuits. For illustration, bases are picked for a hybrid wavelet/matching pursuits audio codec. Bases are added to a codebook successively from a set of 1289 candidates according to their ranked signal to residual ratio (SRR) performance. Two training sets are used, and the codebooks are evaluated on the training sets and two test sequences. Picked bases make a robust codebook, the best of which outperforms traditional selection by ranked frequency of usage by a significant margin over a range of compressions of the audio clips used in this study

This paper reports improvements in compression of both inter- and intra-frame images by the matching pursuits (MP) algorithm. For both types of image, applying a 2D wavelet decomposition prior to MP coding is beneficial. The MP algorithm is then applied using various separable ID codebooks. MERGE coding with precision limited quantization (PLQ) is used to yield a highly embedded data stream. For inter-frames (residuals) a codebook of only 8 bases with compact footprint is found to give improved fidelity at lower complexity than previous MP methods. Great improvement is also achieved in MP coding of still images (intra-frames). Compared to JPEG 2000, lower distortion is achieved on the residual images tested, and also on intra-frames at low bit rates.

The basis size and number of bases in a basis dictionary (codebook) are the dominant parameters in the complexity of coding data by matching pursuits (MP). By basis picking for a range of constrained basis widths on a training image coded by 1D MP, dictionaries are obtained for both still and residual images and applied in both ID and 2D coding. On still (intra) images fidelity measured by PSNR is optimum for widths in the range 9 to 13 and dictionary sizes from 14 to 18. For residual images similar results are obtained but the bias towards narrower, smaller dictionaries is even more marked. The resulting combinations of 1D and 2D dictionaries offer significantly lower computational cost while maintaining high quality.

A human iris coding technique is reported based upon differences in the power spectrum of fragments from normalized iris images. The procedure has been applied to a set of 2174 images from 308 eyes and tuned over a range of parameters. For identity recognition, 100% correct recognition is achieved using a weighted Hamming distance metric. For identity verification, a variable threshold is applied to the distance metric and the false acceptance and false rejection rates are recorded. After tuning the various parameters, the method achieves the lowest false acceptance rate at the point of first false rejection amongst the three algorithms tested, as well as the lowest complexity.

Improved coding of 3D spatio-temporal wavelet video is achieved using matching pursuits (MP) with a separable 2D basis dictionary and temporal replication of atoms. Using two temporal scales and the biorthogonal 5/3 wavelet filter incorporating motion compensation, four sets of four transform planes are combined into a group of temporal planes (GOTP). The planes are wavelet transformed to 4 scales spatially before the 2D MP algorithm is applied over the entire GOTP to select the optimum inner product with a 2D dictionary of 64 bases formed separably from 8 ID basis functions. The selected atom is conditionally replicated in the three corresponding temporal frequency planes within the GOTP. Compared to applying 2D MP to the planes without replication, a gain of up to 2 dB has been achieved. Comparisons with a standard H.263 codec and the classic MP enhanced H.263 MP codec, show significant gains at low bit rates.

Methods of reducing the complexity of the matching pursuits algorithm with minimal loss of fidelity when coding displaced frame difference (DFD) images in video compression are investigated. A full search using 2D basis functions is used as a benchmark. The use of separable 1D bases greatly reduces the complexity, and significant further reductions are achieved by using only a 1D inner product search to locate the atom position, followed by a further 1D inner product search in the opposite direction to identify the second 1D basis function. To avoid ignoring significant structures orthogonal to the search direction, it is proposed to alternate the initial search direction between horizontal and vertical scanning. This produces a modest increase in distortion compared to the full 2D search, with a complexity reduction in excess of an order of magnitude.

The novel 'Basis Picking' algorithm is applied to select dictionaries of 1D basis functions for coding of image data by Matching Pursuits. For both motion compensated residual images and normal still images, bases are picked with a hybrid Wavelet/Matching Pursuits image codec using 1D scanning. By successively adding bases one at a time from a set of 1289 candidates according to their ranked signal to residual ratio (SRR) performance, effective codebooks are constructed. These outperform traditional selection by ranked frequency of use from the same candidate bases over a range of compressions of both residuals and still images. This holds for both the training sets used for picking and other test images. Picked bases are also capable of good quality compression of still images, which was not previously thought to be feasible by matching pursuits.

An improved method is presented for coding the atoms found by the matching pursuits algorithm used in compressing displaced frame difference (DFD) images in motion compensated video coding. A list of atoms is collected, which are then communicated in the order of their most significant bit plane, rather than being communicated as they are found. The atom positions are run length coded, with the sign, extra bits of magnitude and code-book entry sent as side information. The magnitudes are represented by the most significant bit plus a specified number of additional bits. The distortion is never worse than the standard coding method, and can be up to 1dB better. The magnitude precision for best PSNR is found to be 2 at low bit rates and 1 at high bit rates in the examples considered.

We introduce a simple and effective technique for coding motion-compensated residuals based on the discrete cosine transform and embedded bit-plane coding. The encoding of each bit-plane is driven by a significance block map that is created to take advantage of the clustering of large (or small) variance coefficients inherent in motion-compensated residuals. A simple classification scheme based on the significance block map is then applied to the identified significant coefficients to improve coding efficiency. Experimental results show that the proposed method outperforms MPEG-II in coding of interframes by 0.3 - 2.5 dB. In most cases it also outperforms SPIHT-AC and has lower complexity. Blocking artifacts are also less visible in some sequences coded at low bitrates.

We propose a low-complexity, wavelet transform based video codec that transmits composite frames that include both intra- and inter-frame regions. Intra/inter partitioning is performed with the goal of minimising the error in the decoded video sequence. The image is partitioned in the wavelet domain by selecting combinations of spatially oriented coefficient trees. We evaluate a simple selection method based on comparison of tree variance. Optimal partitions can be found using a steepest descent search of the combination space, though this is computationally expensive. Results demonstrate that optimal intra/inter partitionining provides a significant improvement in objective and subjective quality when compared to a conventional interframe codec.

In wavelet image compression using embedded quantization, visual quality can be improved by limiting the number of bits used to refine each significant coefficient to some maximum which is different for each sub-band. At a fixed bit rate, the bits saved are used to augment the number of coefficients coded. In this work, a refinement strategy for just noticeable degradation is obtained experimentally for a 5-scale wavelet decomposition, giving a specification for visually lossless quantization. For a range of higher compression ratios, psychovisual experimentation to determine viewer preferences produces a scheme for the allocation of refinement bits at low bit rates. The results are consistent between subjects and across a range of standard test images. The work is a step towards wavelet image coding in which the data stream is fully embedded for optimum visual quality.

Fractal image compression successfully uses self-similarity within an image to achieve compression. By adapting fractal image compression techniques to image enhancement, an innovative new fractal technique for visual enhancement of JPEG compressed images is created. After detecting the self-similarity characteristics of a degraded JPEG image, details spoiled by quantization are enhanced using an iterative scheme and the fractal nature of the method allows resolution enhancement and fractal zooming. The effect of the scheme is an increase in the visual quality of edges in the image for almost all areas and sharper edges when the image resolution is increased. This application of fractal theory to the problem of image enhancement reveals a number of interesting avenues of investigation and promises techniques which can be used in combination with conventional methods, exploiting both self-similarity and statistical properties to achieve enhancement.

We evaluate two schemes for significance switching of DCT coefficients for block-based embedded DCT image compression. Both schemes deliver their best compression at any PSNR or vice versa, within a data stream that can be terminated within a few bits of any point. An image is partitioned into equal sized blocks, and a fixed point DCT of each block is calculated. The coefficients are then passed through successive 'significance sweeps' of the whole image from the most significant down to the least significant coefficient bitplanes. The coded data stream includes bits to refine only the significant coefficients at each sweep. With each new sweep, newly significant coefficients may appear within a block, and the two switching schemes evaluated are efficient methods based on block addressing and block masking. Both methods give good compression when used losslessly to the fixed point DCT precision. The best coder outperforms the baseline JPEG method in PSNR at any compression, and is similar to state of the art wavelet coders.

The performance of any block based image coder can be improved by applying fractal terms to selected blocks. Two novel methods are used to achieve this. Firstly the coder determines whether a local fractal term will improve each image block by examining its rate-distortion contribution, so that only beneficial fractal terms are used. Secondly, the decoder deduces the offset parameters for the local fractal transform from the basis functions alone, by inferring the dominant edge position, so that no offset information is required. To illustrate the method, we use a quadtree decomposed image with a truncated DCT basis. Using a standard test image, the proportion of the picture area enhanced by fractals decreases from 16.1% at 0.6 bpp to 8.1% at a high compression ratio of 80:1 (0.1 bpp). The fractal terms contribute less than 5% of the compressed code in all cases. The PSNR is improved slightly, and edge detail is visually enhanced.

We consider the rate/distortion benefits of aspects of fractal image compression, and introduce a new method of pruning the pool of parent blocks for optimum performance. Previous work questioned the value of searching in fractal compression, and found that the code used to represent block offsets was not compensated for by decreased error. This was because the searching process predominantly chose local parent blocks. Here we revisit this question using improved basis functions and orthogonalized parent blocks. The basis function is a limited number of DCT coefficients which has very low complexity compared to wavelet transforms or full DCTs. A zero-searching fractal transform in which the parent block is centred over the child block improves the basis function approximation. With orthogonalized parent blocks, searching of the image gives a slight PSNR benefit at higher compression ratios. A new scheme, in which the pool of parent blocks is pruned according to a rate/distortion criterion, gives greater improvement, and guarantees optimal use of the parent pool. The method advances the technique of fractal image compression and shows how to use fractal terms to improve the rate/distortion performance of image coding by any basis approximation.

We show that an efficient quantizer originally developed for wavelet compression can be applied to DCT coding with excellent results. We have implemented a system for block-based, embedded, progressive, DCT image compression which makes use of the embedded zerotree wavelet (EZW) algorithm of Shapiro (1993). The image is partitioned into a number of distinct square blocks and the DCT applied to each of these individually. The coefficients are then rearranged into a sub-band structure which outwardly resembles a wavelet transformed image, with the number of sub-bands being related to the size of the DCT used. The zerotree coding algorithm is then employed to quantize the coefficients. The system outperforms the embedded zerotree wavelet scheme in a rate-distortion sense, with good performance from lossless (to the fixed point DCT precision) to high compression. The system gives the best trade between accuracy and high frequency ringing with a DCT block size of 16/spl times/16, corresponding to four sub-band scales.

A novel algorithm is described for coding objects in video compression systems which gives complete control over the bit allocation to the video objects. The method is evaluated by application to a two layer codec, with background and foreground objects. Images in a sequence are divided into macroblocks, which are compared to a stored background model. Those whose mean square difference (MSD) exceeds a noise threshold are considered as foreground, and may be split into successively finer partitions described by a quadtree data structure. This defines more precisely the outline of the foreground object within each macroblock and gives a set of microblocks of variable size. The microblocks are transformed by the 2D DCT, and the DCT coefficients are coded bitplane by bitplane over the selected object using a zigzag masked (ZZM) technique. For robustness, data is then transmitted macroblock by macroblock, and intraframe or interframe coding of blocks can be selected adaptively at frame, macroblock or microblock level. The scheme is designed to stop sending bits when a certain bit allocation or PSNR is reached for any object, leading to fully controllable bit rates. The relationship between the average PSNR of the sequence and the average bits per pixel in a frame shows that the codec gives good performance over a range of peak bit rates from 0.1 bpp to 1 bpp. Over the whole range, the quality of the reconstructed sequence is significantly better than 'motion JPEG', while the codec is much simpler and faster than MPEG.

This paper shows how to design good biorthogonal FIR filters for wavelet image compression by balancing the space and frequency dispersions of analysis and synthesis low-pass filters. A quality metric is proposed which can be computed directly from the filter coefficients. By optimizing over the space of FIR filter coefficients, a filter bank can be found which minimizes the metric in about 60 seconds on a high performance workstation. The metric contains three parameters which weight the space and frequency dispersions of the low pass analysis and synthesis filters. A series of biorthogonal, symmetric wavelet filters of length 10 was found, each optimized for different weightings. Each of these filter banks was then evaluated by compressing and decompressing five test images at three compression ratios. Selecting each optimum provides fifteen sets of parameters corresponding to filter banks which maximize the PSNR in each case. The average of these parameters was used to define a 'mean' filter banks which was then evaluated on the test images. Individual images can produce substantially different weightings of the time dispersion at the optimum, but the PSNR of the mean filter is normally close to the optimum. The 'mean' filter also compares favourably with a maximum regularity biorthogonal filter of the same length.

One advantage of fractal image compression schemes is their multiresolution properties. An image can be decoded at higher or lower resolutions than the original, and it is possible to 'zoom-in' on sections of the image. Even so the problem of fractal zooming has received very little attention. In this paper we examine these multiresolution properties. We study the problem of fractal zooming in general and in particular with a hybrid fractal transform with implicit fractal terms. When decoding at a resolution higher than the original, artefacts can be created which affect the visual quality of the zoomed image. We present one solution to the problem of obtaining clear and sharp edges where the original approximation quality was good. Our enhanced implicit fractal transform method compares favourably with fractal zooming using previous standard fractal approximation algorithms.

An error concealment scheme for Motion Picture Experts Group (MPEG) video networking is proposed. During video transmission, video packet loss occurs in the presence of network congestion and buffer overflow. This phenomenon of packet loss transforms into single or multiple macroblock loss in the decoding process, which can severely degrade the viewing quality. The new method differs from the conventional concealment by its exploitation of temporal redundancies in a large scale. In many applications where there is significant camera motion (e.g., remote surveillance), the evolution from frame to frame can be well described by the affine motion. The motion estimation is carried out by registering images within a multiresolution pyramid. The global motion is estimated in the lowest resolution level, and is then used to update and refine the local motion. The local motion is further refined iteratively at higher resolution levels. An affine transform is used to extract translation, scaling and rotation parameters.

We present optimized biorthogonal and orthonormal wavelets for embedded zerotree wavelet compression of fingerprint images. These were obtained by simulated annealing over the wavelet filter coefficients using rms error between original and recovered images as the cost to be minimized. Linear-phase biorthogonal wavelets optimized for fingerprint image compression provide significantly improved fidelity compared either with standard wavelets or with wavelets optimized upon general images. These results are confirmed by psychovisual evaluation by two fingerprint experts whose independent rankings were in complete agreement. Filter coefficients for optimized orthonormal and linear-phase biorthogonal wavelets are tabulated.

This paper addresses the question: 'what makes a good wavelet for image compression?', by considering objective and subjective measurements of quality. A new metric is proposed for the design of the finite impulse response (FIR) filters used in the discrete wavelet transform (DWT). The metric is the diagonal of the Heisenberg uncertainty rectangle, with time weighted by a factor k relative to frequency. Minimization of the metric balances the time and frequency spreads of the filter response. The metric can be computed directly from the filter coefficients, so it can be used to optimize wavelets for image compression without the cost of repeatedly compressing and decompressing images. A psychovisual evaluation carried out with 24 subjects demonstrates that orthonormal FIR filters designed this way give good subjective results with zerotree image compression. With suitably chosen k, both better subjective quality and lower RMS error are achieved than with wavelets chosen for maximum regularity.

Intelligent identification of background and foreground in video scenes is used for gain compression. This is implemented as a two layer object model in a software-only video compressor with a bit rate range from less than 10 kbps up to to 1.2 Mbps. Quadtree decomposition on an error metric between the input and transmitted images directs the coder towards a foreground layer of active image fragments. A rate buffering system limits the bandwidth by transmitting only the foreground blocks which most improve the image and are above some error threshold. A high fidelity background layer is identified and communicated to the decoder, which can be used to redraw background fragments as foreground objects move across them. Blocks can be coded by various methods, such as fractal transforms or truncated DCTs. This system can be implemented in RISC processors without the need for dedicated hardware. It is suitable for low bit rate applications with slowly varying backgrounds, such as personal video communications over packet networks, or closed circuit TV surveillance using fixed or wireless links.

We present biorthogonal and orthonormal wavelets for embedded zerotree wavelet compression of fingerprint images. By simulated annealing over the wavelet filter coefficients, using a composite cost function dependent upon a parameter k/sup 2/ which weights the relative importance of the wavelet's bandwidth and time dispersion, a series of wavelets is obtained. Each of these is optimal in terms of a particular Heisenberg uncertainty 'footprint', i.e. a particular trade-off between bandwidth and time dispersion. The psychovisually optimal wavelet for fingerprint image compression is determined by fingerprint experts by examination of images compressed and recovered using the series of wavelets. Psychovisually tuned wavelets were found to yield superior visual fidelity to standard wavelets and also to wavelets optimized to produce minimum RMS error on either fingerprint or general test images.

We report a novel image coder which is a hybrid of fractal coding and vector quantisation. The approach to image compression is to form an approximate image by one method and clear up errors by another. In this realisation, image blocks are approximated by polynomial functions, and the residual image blocks are coded by vector quantisation into a codebook which is small enough to transmit with an image. The method is evaluated on a number of parameters, and the results are found to be intermediate between fractal and JPEG coding in their rate/distortion performance. Possible further improvements are indicated.

Evaluates the fidelity/compression performance of fractal transforms over a range of parameters, using an rms error metric. The authors consider order of approximation, different (fixed) block sizes and various degrees of image searching. They find that higher orders of the Bath fractal transform (BFT) are a better means of gaining accuracy at a given bit rate than searching of the image. The best rate/distortion performance is obtained with a lightly quantized higher order BFT, whose optimum block size increases with compression.

We report real time fractal coding of 168 by 144 pixel YUV colour images using a standard 33 MHz i486 computer. The Bath fractal transform (BFT) has nearly symmetrical coding and decoding cost. When applied to square image blocks of 144 pixels, the BFT codes in 560 /spl mu/sec and decodes in 450 /spl mu/sec. The biquadratic BFT compresses individual luminance blocks typically to 0.4 bpp. Our rate buffering system manages the video bit rate and can achieve any desired overall compression. Only the blocks most in error are transmitted, and the Y, U, and V components are treated separately. The overall compression at 64 Kbps is to 0.11 bpp average with a full colour moving head sequence, equivalent to 220:1 with a 24 bpp original.

An in-place algorithm for the fast, direct computation of the forward and inverse discrete cosine transform is presented and evaluated. The transform length may be an arbitrary power of two.

We study the fidelity/compression performance of fast fractal image coding. The Bath fractal transform (BFT) is a generalization of earlier methods with a range of implementation options for the order of approximation and degree of searching. All fractal transforms are fast to decode, and the zero searching variants are nearly as fast to code. We examine BFTs of zero order (flat), first order (bilinear) and second order (biquadratic). The degradation introduced by Lloyd-Max (1982) quantization of the fractal coefficients is evaluated. Further compression is achieved by exploiting correlation in one of the fractal coefficients through differential coding. The other coefficients are quantized directly, and Huffman coding of each gives a compressed image. Possibilities for further compression are discussed.>

We report real time fractal coding of 176 by 144 luminance images on a 33 MHz i-486 computer. With a zero searching first order (bilinear) Bath fractal transform, square blocks of 64 pixels are coded in 250 /spl mu/sec and decoded in 200 /spl mu/sec. This permits coding of 40% of each frame in a 25 Hz video sequence, or full coding at 10 Hz. By transmitting only those blocks of greatest error, we can obtain any degree of data compression. Useful video sequences of talking heads have been achieved with rates as low as 40 kbits/sec. We describe the techniques used, give illustrations of the degradation, and show the evolution of the errors in the decoded sequence as various events occur. The overall compression at 40 kbits/sec is 99:1, with further error reductions possible.>

The Bath Fractal Transform (BFT) defines a strategy for obtaining least squares fractal approximations and can be implemented using functions of varying complexity. The approximation method used in ITT-coding is itself the zero-order instance of the BFT. Some of the complexity options available are explored by combining various orders of BFT approximation with various degrees and types of searching. This may be regarded either as the inclusion of searching with the BFT or as a generalization of the matching criterion of ITT-coding. This is considered from the point of view of the cost-fidelity trade-offs incurred, and the implications for practical application to multimedia information retrieval systems and real-time video are discussed.>

The paper offers a solution to the problem of determining good quantization tables for use with the discrete cosine transform. Using the methods proposed, the designer of a system can choose a selection of test images and a coefficient weighting scenario, from which a quantization table can be produced, optimized for the choices made. The method is based on simulated annealing searches which the space of quantization tables to minimize some chosen measure.>

A method for block coding of images based on a least squares fractal approximation by a self-affine system (SAS) is presented. The computational cost of the approximation is linear in the number of pixels in the image. The approximation to a rectangularly tiled block involves evaluating various low-order moments over the block, and solving a system of four linear equations for each tile. The method is applied to a standard test image and the effects of various optimizations are shown. A quantitative comparison with the adaptive discrete cosine transform at 8:1 compression is made. The fidelity of the fractal method shows promise and its greater speed and simplicity compared to other fractal transforms suggest immediate applications such as interactive browsing of remote image archives or image representation in multimedia systems.>