We propose a perceptually based system for pattern retrieval and matching. The central idea is that similarity judgment has to be modeled along perceptual dimensions. Hence, we detect basic visual categories that people use in their judgment of similarity, and design a computational model that accepts patterns as input and, depending on the query, produces a set of choices that follow human behavior in pattern matching. There are two major research aspects to our work. The first one addresses the issue of how humans perceive and measure similarity within the domain of color patterns. To understand and describe this mechanism, we performed a subjective experiment which yielded five perceptual criteria used in comparison between color patterns (vocabulary), as well as a set of rules governing the use of these criteria in similarity judgment (grammar). The second research aspect is the implementation of the perceptual criteria and rules in an image retrieval system. Following the processing typical for human vision, we design a system to: (1) extract perceptual features from the vocabulary and (2) perform the comparison between the patterns according to the grammar rules. The modeling of human perception of color patterns is new--starting with a new color codebook design, compact color representation, and texture description through multi-scale edge distribution along different directions. Moreover, we propose new color and texture distance functions that correlate with human performance. The performance of the system is illustrated with numerous examples from image databases from different application domains.

We determine the basic categories and the hierarchy of rules used by humans in judging similarity and matching of color patterns. The categories are: (1) overall color; (2) directionality and orientation; (3) regularity and placement; (4) color purity; (5) complexity and heaviness. These categories form the pattern vocabulary which is governed by the grammar rules. Both the vocabulary and the grammar were obtained as a result of a subjective experiment. Experimental data were interpreted using multidimensional scaling techniques yielding the vocabulary and the hierarchical clustering analysis, yielding the grammar rules. Finally, we give a short overview of the existing techniques that can be used to extract and measure the elements of the vocabulary.

We propose a perceptually-based system for pattern retrieval and matching. The central idea of the work is that similarity judgment has to be modeled along perceptual dimensions. Hence, we detect basic visual categories that people use in judgment of similarity, and design a computational model which accepts patterns as input, and depending on the query, produces a set of choices that follow human behavior in pattern matching. To understand how humans perceive color patterns we performed a subjective experiment The experiment yielded five perceptual criteria used in comparison between color patterns (vocabulary), as well as a set of rules governing the use of these criteria in similarity judgment (grammar). This paper describes the actual implementation of the perceptual criteria and rules in the image retrieval system. Following the processing typical for human vision, we designed a system to: (a) extract perceptual features from the vocabulary and (b) perform the comparison between the patterns according to the grammar rules. We propose new color and texture features, as well as new distance functions that correlate with human performance. The performance of the system is illustrated with numerous examples from image databases from different application domains.

We present a novel application for Content Based Retrieval Techniques in Electronic Commerce using Interactive Multimedia, in which visual queries play a central role. We address some of the technical issues in representing and analysing image primitive features that are the building blocks of the MIRACLE system. These can be generalized into a much broader range of applications as well. We believe that Electronic Commerce is a very promising area with much potential for growth and that it covers a spectrum of rich research topics.

Embedded zerotree wavelet coding (EZW), introduced by Shapiro (1993) and improved by Said and Pearlman (1996) using an algorithm based on set partitioning in hierarchical trees (SPIHT), is a computationally inexpensive image coding technique and has proven to be very effective at minimizing the mean-square error (MSE) distortion measure. However, minimizing MSE does not guarantee preservation of good perceptual qualities in the decoded image, especially at low bit rates. In this paper we propose a perceptually-tuned embedded zerotree image codec (PEZ) that introduces a perceptual weighting to the wavelet transform coefficients prior to EZW encoding. In this coder the EZW minimizes a perceptually based distortion measure instead of MSE. The perceptual weights for all subbands are computed based on the just noticeable distortion (JND) thresholds for uniform noise. The new perceptually tuned codec has the same complexity as the original EZW/SPIHT techniques and results in a comparable or superior coding performance. Coding results are presented to illustrate the performance of the new coder.

We propose an algorithm for deinterlacing of interlaced video sequences. It successively builds approximations to the deinterlaced sequence by weighting various interpolation methods. A particular example given here uses four interpolation methods, weighted according to the errors each one introduces. Due to weighting, it is an adaptive algorithm. It is also time-recursive, since the motion-compensated part uses the previously interpolated frame. Furthermore, bidirectional motion estimation and compensation allow for better performance in the case of scene changes and covering/uncovering of objects. Experiments are run both on "real-world" and computer generated sequences. Finally, subjective testing is performed to evaluate the quality of the algorithm.

This paper involves designing, implementing, and testing of a locally adaptive perceptual masking threshold model for image compression. This model computes, based on the contents of the original images, the maximum amount of noise energy that can be injected at each transform coefficient that results in perceptually distortion-free still images or sequences of images. The adaptive perceptual masking threshold model can be used as a pre-processor to a JPEG compression standard image coder. DCT coefficients less than their corresponding perceptual thresholds can be set to zero before the normal JPEG quantization and Huffman coding steps. The result is an image-dependent gain in the bit rate needed for transparent coding. In an informal subjective test involving 318 still images in the AT&T Bell Laboratory image database, this model provided a gain in bit-rate saving on the order of 10 to 30%.

Over the last few years three technologies have reached the stage of maturation where then can become synergistic. These are wideband, high speed networking, high quality video compression (MPEG-I and II), and high capacity affordable digital storage media. This paper addresses the interaction of these three technologies. In particular, it examines the problem of taking a compressed video data stream that is stored on a server, and transmitting it over an ATM channel which has a capacity smaller than that required by the data stream. The conventional approach to this problem would be to transcode by decoding the video data, and then re-encoding so as to meet the channel constraints. Currently this is not a cost effective solution since, while MPEG decoders are relatively inexpensive, encoders are not. Our approach to this problem is to partially decompress the video bitstream. Then, perform the transcoding in the quantized data domain. Finally, a valid bitstream is reassembled and transmitted. This approach has the advantage of providing nearly identical quality as the traditional transcoding approach, at a fraction of the hardware cost.

Quantization is a critical procedure in lossy image compression. Linear (uniform) quantizers are used in most of the present image (sequence) compression standards for their simplicity and flexibility. Unfortunately, the resulting representation is often inefficient, preventing potentially significant gains in image compression. We introduce a new class of linear, low complexity, variable dimension quantizers (VDQ) that efficiently reduces the redundancy of the data stream while retaining the design flexibility and signal-to-noise performance of a linear quantizer. When applied to frequency domain representations in the JPEG image compression standard, this approach resulted in SNR improvements of almost 9 dB over the baseline quantizer at comparable bit rates. The algorithm presented is near optimal and runs in O(N) time, making it suitable for real time applications. Its low complexity and effectiveness make VDQ a promising alternative to conventional quantization for image codecs.

The notion of perceptual coding, which is based on the concept of distortion masking by the signal being compressed, is developed. Progress in this field as a result of advances in classical coding theory, modeling of human perception, and digital signal processing, is described. It is proposed that fundamental limits in the science can be expressed by the semiquantitative concepts of perceptual entropy and the perceptual distortion-rate function, and current compression technology is examined in that framework. Problems and future research directions are summarized.>

Vision sensor output can be processed to yield a multitude of low-level measurements, where each is inherently uncertain, which must somehow be combined to verify the locations of an object. It is shown that this combination can be accomplished via Dempster-Shafer theory using binary frames of discernment (BFODs). A special advantage of BFODs is the computational ease with which they allow information from disparate sources to be combined, which is particularly significant in light of recent concerns about the exponential complexity of a brute-force implementation of this theory.>

The authors present a 16-band subband coder arranged as four equal-width subbands in each dimension, It uses an empirically derived perceptual masking model, to set noise-level targets not only for each subband but also for each pixel in a given subband. The noise-level target is used to set the quantization levels in a DPCM (differential pulse code modulation) quantizer. The output from the DPCM quantizer is then encoded, using an entropy-based coding scheme, in either 1*1, 1*2, or 2*2 pixel blocks. The type of encoding depends on the statistics in each 4*4 subblock of a particular subband. One set of codebooks, consisting of less than 100000 entries, is used for all images, and the codebook subset used for any given image is dependent on the distribution of the quantizer outputs for that image. A block elimination algorithm takes advantage of the peaky spatial energy distribution of subbands to avoid using bits for quiescent parts of a given subband. Using this system, high-quality output is obtainable at bit rates from 0.1 to 0.9 bits/pixel, and nearly transparent quality requires 0.3 to 1.5 bits/pixel.>

Multistage quantization is used to encode the intensity waveform in the most dominant subband. The reconstruction error in the first stage of the process is itself quantized and first-stage reconstruction is refined by removing from it the most objectionable components of quantized reconstruction error. The reconstruction error is coded on the basis of a bit allocation algorithm that utilizes the fact that perceptually significant error samples tend to occur in clusters in high-entropy parts of the input image frame. Application of this technique to a 512*512 monochrome image results in good communications quality at a rate of 0.5 bit per pixel for the simplest case of a two-band partition in horizontal and vertical frequencies, for a total of four subbands. By increasing the number of subbands to 16, significantly higher image quality can be realized at the same bit rate.>