We present a multiresolution approach for video indexing and feature matching of subband-coded video databases. Four different scene-change detectors were tested; scene-change detection is applied only on the lowest subband for computational efficiency. Two kinds of scene changes, abrupt and smoothly accumulated, mark the beginning of new scene segments. The index for each scene segment is the pair of the histograms of two representative frames, the first and the last frame of the scene. Using the approach of query by example, the index-matching algorithm takes a multiresolution approach by hierarchically comparing histograms at different resolutions. The search algorithm for the match between example query and its target scene segment starts from the coarsest resolution and moves to the next finer resolution until the finest resolution is reached. Experimental results are presented, and the proposed indexing technique appears to be promising for its speed and its inherent hierarchical search procedure.

We present an adaptive model-driven bit-allocation algorithm for video sequence coding. The algorithm is based on a parametric rate-distortion model, and facilitates both picture-and macroblock-level bit allocation. A region classification scheme is incorporated into the algorithm, which exploits characteristics of human visual perception to efficiently allocate bits according to a region's visual importance. The application of this algorithm to MPEG video coding is discussed in detail. We show that the proposed algorithm is computationally efficient and has many advantages over the MPEG-2 TM5 bit-allocation algorithm.

This paper presents a new motion-compensated subband video-coding technique using variable reference-frame positions for motion estimation. The work builds on temporal segmentation for determining the reference-frame positions and incorporates multiresolution motion estimation in the subband domain. The key advantage of the new algorithm is the complexity reduction in motion estimation that uses the multiresolution property of subband decomposition. Temporal segmentation is performed with the lowest spatial subband, based on the detection of two types of scene change. The frames of input video are split into seven spatial subbands, and the motion vectors for each subband are generated by a hierarchical motion-estimation algorithm. Blockwise differential pulse code modulation (DPCM) and a uniform quantizer are used for the lowest subband of the first frame only, and the subbands of all other cases are coded by PCM with a dead zone quantizer. Simulation results show that our scene-adaptive scheme compares favorably with a fixed interpolation structure.

We investigate the use of gradient indexing for texture discrimination. From a histogram of its gradient field, a texture can be recognized. We find that gradient indexing is insensitive to the number of bins and to the choice of the gradient operator. We also find that the gradient direction and magnitude are both important in recognizing different textures. We further propose a modified gradient indexing technique called local activity spectrum, which has improved performance.

An adaptive watermarking technique is introduced in this work. A regional perceptual classifier is employed to assign a noise sensitivity index to each region. The watermark is inserted in the original image according to this index by using block DCT. The detection of the watermark is designed to achieve a desired false alarm probability.

Motion uncertainty and image quantization noise are two important factors affecting the performance of block motion compensation in a standard hybrid video coder. This paper models both these effects, and analyzes their nonstationary property. It proposes a strategy that jointly applies space-varying overlapped block motion compensation and loop filtering, achieving better rate-distortion performance than either method alone.

We derive here a parametric rate-quantization model, based on traditional rate-distortion theory, for MPEG encoders. Given the bit budget for a picture, our model calculates a baseline quantization scale factor. We compare our approach to a technique using an ad-hoc rate-quantization model, and also to TM5. In both cases, experimental results demonstrate that our approach produces an actual encoded bitrate closer to the target bit budget for the picture, as well as an improved peak signal-to-noise ratio.

We present an algorithm for joint optimization of anchor frame separation and bit allocation for motion-compensated video coders. The anchor frame separation is optimized in the sense that the distortion is minimized under a bit budget constraint. At the same time, the quantization for each frame in a group of pictures is also optimized in an operational rate distortion sense. The optimal anchor frame separation does depend on the quantization of each frame so that the two optimization problems cannot be separated. A Lagrange multiplier approach can be used to obtain the optimal solution if we assume that the rate-distortion curve is convex. Heuristic algorithms based on simulated annealing and greedy trellis selection are also presented to reduce the computational complexity.

A classified hierarchical template matching algorithm is presented in this work. In our system, a template is first classified into one of three classes: texture, edge and low-activity. Then different features are used for each class, thereby achieving a better recognition rate than with the commonly used l/sub 2/ metric. Furthermore, a two-level hierarchical searching algorithm is designed to reduce the amount of computation. The algorithm works in both spatial and DCT domains. It can be applied to image retrieval applications where a user is interested in finding images containing a small pattern.

We present a new subband video coding algorithm with temporally adaptive motion interpolation. In the approach proposed, the reference frames for motion estimation are adaptively selected using temporal segmentation in the lowest spatial subband. Variable target bit allocation for each picture type in a group of pictures is used to allow variable number of reference frames with the constraint of constant output bit rate. Block-wise DPCM, PCM, and run-length coding combined with truncated Huffman coding are used to encode the quantized data in the subbands. Simulation results of the adaptive scheme compare favorably with those of a non-adaptive scheme.>

In this paper, we present an algorithm for joint optimisation of motion compensation structure and bit allocation for motion compensated video coders. In this scheme, the motion compensation structure is optimized in the sense that the distortion is minimized under a bit budget constraint. At the same time, the quantisation for each frame in the group of pictures (GOP) is also optimized in an operational rate distortion sense.>

In this paper we present a novel technique to dynamically adapt motion interpolation structures by temporal segmentation. The number of reference frames and the intervals between them are adjusted according to the temporal variation of the input video. Bit-rate control for this dynamic group of pictures (GOP) structure is achieved by taking advantage of temporal masking in human vision. Constant picture quality can be obtained by variable-bit-rate coding using this approach. Further improvement can be made when the intervals between reference frames are chosen by minimizing a measure of the coding difficulty of a GOP. Advantages for low bit-rate coding and implications for variable-bit-rate coding are discussed. Simulations on test video are presented for various GOP structures and temporal segmentation methods, and the results compare favorably with those for conventional fixed GOP structures.

In this paper we present a novel technique to dynamically adapt motion interpolation structures by temporal segmentation. The interval between two reference frames is adjusted according to the temporal variation of the input video. The difficulty of bit rate control for this dynamic group of pictures (GOP) structure is resolved by taking advantage of temporal masking in human vision. Six different frame types are used for efficient bit rate control, and telescopic search is used for fast motion estimation because frame distances between reference frames are dynamically varying. Constant picture quality can be obtained by variable bit rate coding using this approach and the statistical bit rate behavior of the coder is discussed. Advantages for low bit rate coding and storage media applications and implications for HDTV coding are discussed. Simulations on test video including HDTV sequences are presented for various GOP structures and different bit rates, and the results compare favorably with those for conventional fixed GOP structures.

Relationships between locally interconnected neural networks that use receptive field representations and trellis or convolutional codes are explored. A fault tolerant neural network is described. It is patterned after the trellis graph description of convolutional codes and is able to tolerate errors in its inputs and failures of constituent neurons. This network incorporates learning, which adds failure tolerance; the network is able to modify its connection weights an internal representation so that spare neurons can replace neurons which fail. A brief review of trellis-coding concepts is included.

Associative memory networks consisting of highly interconnected binary-valued cells have been used to model neural networks. Tight asymptotic bounds have been found for the information capacity of these networks. The authors derive the asymptotic information capacity of these networks using results from normal approximation theory and theorems about exchangeable random variables.>

We define a piecewise AR model For a class of time series whose statistical properties change abruptly at some unknown time points. For such a model we consider the problems of jump detection and fast tracking of the changing parameters. A method based on the adaptive least squares lattice filter algorithm is proposed. The method automatically detects the occurrences of jumps and adjusts the adaptation rate of the adaptive lattice algorithm, so both accurate estimates and fast tracking ability are achieved.

Let(U_{1},U_{2}, \cdots)be a sequence of observed random variables and(T_{1}(U_{1}),T_{2}(U_{1}, U_{2}), \cdots)be a corresponding sequence of sufficient statistics (a sufficient sequence). Under certain regularity conditions, the sufficient sequence defines the input/output map of a time-varying, discrete-time nonlinear system. This system provides a recursive way of updating the sufficient statistic as new observations are made. Conditions are provided assuring that such a system evolves in a state space of minimal dimension. Several examples are provided to illustrate how this notion of dimensional minimality is related to other properties of sufficient sequences. The results can be used to verify the form of the minimum dimension (discrete-time) nonlinear filter associated with the autoregressive parameter estimation problem.

A time-recursive least-squares lattice estimation algorithm is presented. The reflection coefficients, kj, are estimated from residual energy estimates,\hat{RE}_{j}, so that|\hat{k}_{j}| < 1for all j. Thus the stability of the inverse filter is guaranteed. Computation and storage may be reduced by normalizing the forward and backward prediction errors throughout the lattice by the square roots of estimates of their respective energies. Also, this ensures that all lattice quantities are bounded in magnitude by one, facilitating fixed-point implementation. The computational requirement of both normalized and unnormalized forms is proportional to the lattice order per time update.

A sufficient statistic, having dimension3p+1, is constructed forpth order stationary Gaussian autoregressive processes. A computationally efficient discriminator based on the statistic is obtained. A derivation of the whitening filter-correlator detector for known signals in autoregressive noise is presented. A new formula for the signal-to-noise ratio of an optimal detector for a constant signal in stationary correlated Gaussian noise is presented and used to help study the nature of autoregressive approximations to more general processes in this application.

We study the problem of diagonalizing the DFT by finding eigenvectors through the use of commuting operators. An explicit form for the polar representation of the DFT is presented and powers of the DFT are studied. Possible applications to signal multiplexing and transform coding are suggested.

A new estimation technique for the reflection coefficients in the lattice filter formulation of linear predictive analysis is presented that is computationally more efficient than previous procedure. This procedure, requiring primarily addition operations, is based on a Markov Chain model of the hard-limited forwards and backwards prediction error sequence. By using only the polarity of the prediction error signal, the reflection coefficient estimates cannot be as accurate as those from optimum estimation techniques. However, the precision of the estimates is comparable to the quantization error of the reflection coefficients in speech encoding and transmission applications. The theoretical foundation of this estimation technique is presented. The estimates from this technique are compared with those from optimal algorithms.

Because a function of two variables which is positive definite over a rectangle may not have a positive definite extension to the entire plane, two-dimensional Markov spectrum estimates based on estimated autocorrelation data do not always exist. The ramifications of this fact are discussed.

We modify the usual lattice formulation of linear predictive analysis by using hard-limited versions of the forwards and backwards prediction error signals to compute estimates of the reflection coefficients. A four state Markov chain model is proposed for the resulting pair-process at each stage of the lattice. For a special case of the model, simple maximum likelihood estimates can be derived. The resulting estimation method reduces the sensitivity of the estimates to outliers in the observations, giving a more robust power spectrum estimate.

A variable rate speech encoding scheme is presented which determines linear predictive models over phonetically uniform intervals. Instead of using a fixed analysis frame length, the analysis interval is adjusted to span an entire steady sound or set at a minimum interval for transient sounds. This scheme offers the following advantages over a fixed frame-rate scheme: for the same perceived speech quality, the bit rate can be reduced or for the same bit rate, the quality of the perceived speech can be improved.

The use of least squares estimates and their residual energies for obtaining autoregressive estimates satisfying a stability property are investigated. The partial correlation coefficients are used to provide an appropriate parametrization for this purpose. An algorithm is presented for efficient calculation of the estimates. Recursive versions of the estimate and maximum entropy properties are briefly discussed.

A realization of a linear sequential circuit is called a canonical convolutional encoder if its state space has the smallest dimension among all realizations generating the same code. We give conditions for a realization to be a canonical oncoder and for two canonical encoders to generate the same code. The techniques used provide an enumeration of canonical encoders whose realizations are not isomorphic.