Search

This paper presents a fast algorithm and its VLSI architecture for H.264 fractional motion estimation. Motivated by the high correlation of cost between neighboring fractional pel position, the proposed algorithm efficiently explores the neighborhood position around the minimum one and thus skips other unlikely ones. Thus, the proposed search pattern and early termination under constant quantization parameter can reduce about 50 % of computation complexity compared to that in reference software but only with 0.1–0.2 dB peak signal-to-noise ratio degradation and less than 2% of bit rate increase. The VLSI architecture of the proposed algorithm thus can save 40% of area cost due to only half of the processing elements and save 14 % of searching time when compared with the previous design. [ABSTRACT FROM AUTHOR]

In an H.264/AVC video encoder, integer motion estimation (IME) requires 74.29% computational complexity and 77.49% memory access and becomes the most critical component for low-power applications. According to our analysis, an optimal low-power IME engine should be a parallel hardware architecture supporting fast algorithms and efficient data reuse (DR). In this paper, a hardware-oriented fast algorithm is proposed with the intra-/inter-candidate DR considerations. In addition, based on the systolic array and 2-D adder tree architecture, a ladder-shaped search window data arrangement and an advanced searching flow are proposed to efficiently support inter-candidate DR and reduce latency cycles. According to the implementation results, 97% computational complexity is saved by the proposed fast algorithm. In addition, 77.6% memory bandwidth is further saved with the proposed DR techniques at architecture level. In the ultra-low-power mode, the power consumption is 2.13 mW for real-time encoding CIF 30-fps videos at 13.5-MHz operating frequency. [ABSTRACT FROM AUTHOR]

The coding efficiency of a Wyner-Ziv video codec relies significantly on the quality of side information extracted at the decoder. The construction of efficient side information is difficult thanks in part to the fact that the original video sequence is not available at the decoder. Conventional motion search methods are widely used in the Wyner-Ziv video decoder to extract the side information. This substantially increases the Wyner-Ziv video decoding complexity. In this paper, we propose a new method to construct side estimation based on the idea of universal prediction. This method, referred to as Wyner-Ziv video coding with universal prediction (WZUP), does not perform motion search or assume an underlying model of the original input video sequences at the decoder. Instead, WZUP estimates the side information based on its observations on the past reconstructed video data. We show that WZUP can significantly reduce decoding complexity at the decoder and achieve a fair side estimation performance, thus making it possible to design both the video encoder and the decoder with low computational complexity. [ABSTRACT FROM AUTHOR]

3-D video will be the most prominent video technology in the next generation. Among the 3-D video technologies, stereo video systems are considered to be realized first in the near future. Stereo video systems require double bandwidth and more than twice the computational complexity relative to mono-video systems. Thus, an efficient coding scheme is necessary for transmitting stereo video. In this paper, a new structure of prediction core in stereo video coding systems is proposed from the algorithm level to the hardware architecture level. The joint prediction algorithm (JPA), which combines three prediction schemes, is proposed for high coding efficiency and low computational complexity. It makes the system outperform MPEG-4 temporal scalability and simple profile by 2-3 dB in rate-distortion performance. Besides, JPA also utilizes the characteristics of stereo video and successfully reduces about 80% computational complexity. Then, a new hardware architecture of the prediction core based on JPA and a modified hierarchical search block-matching algorithm is proposed. With a special data flow, no bubble cycles exist during the block-matching process. The proposed architecture also adopts the near-overlapped candidates reuse scheme to save the heavy burden of data access. Besides, both on-chip memory requirement and off-chip memory bandwidth can be reduced by the proposed new scheduling. Compared with the hardware requirement for the implementation of full search block-matching algorithm, only 11.5% on-chip SRAM and 3.3% processing elements are needed with a tiny PSNR drop, making it area-efficient while maintaining high stereo video quality and processing capability. [ABSTRACT FROM AUTHOR]

Although the conventional post-compression rate distortion (PCRD) optimum algorithm in JPEG2000 can provide excellent rate-distortion performance, it remains troublesome for VLSI design. It requires high-complexity computation and a large quantity of working memory. In this paper, a novel rate-control system for JPEG2000 image coding, which consists of three stages, is proposed to efficiently reduce the computational complexity and memory usage, as well as maintaining the high image comparable with PCRD. In the precoding stage, the rate allocation for the image tiles (RAIT) can allocate the bit rates for different image tiles based on their internal information; moreover, in order to make VLSI design easier, the image edge-detect algorithms and the prediction algorithms are used to evaluate the information of the image tiles. In the tier1 coding stage, according to the given bit rate, the rate allocation based on the rest rate distortion (RARRD) can adaptively truncate code stream based on the rest rate distortion of the current image tile and the rate-distortion (RD) slope of the current coding pass during the current code-block coding, and all of the truncated data need not be encoded and stored. In the post-coding stage, a new fast rate control with approximately optimum truncation (RCAOT) can get the approximately optimum truncation points through searching among the 256 quality layers once, which are divided based on the 8-b RD-slopes expressed by means of a logarithm. This system can not only maintain high image quality through RCAOT and RAIT but also save working memory and encoding time by means of RARRD and RCAOT. Experimental results show that, for the image which has distinct objects and background, the PSNR of the reconstructed images compressed by our rate-control system are much higher than those using PCRD; for other images, our system has the comparative effect as PCRD. [ABSTRACT FROM AUTHOR]

A reduced-complexity convolutional formulation is presented for systolic implementation of the discrete cosine transform, where N-point transform can be computed by four numbers of nearly (N/4)-point circular-convolution-like operations. The proposed algorithm not only provides a reduction of computational complexity by four times over the conventional formulation, where N-point transform is computed via (N - 1)-point cyclic convolution, but also leads to concurrent pipelined execution in linear systolic arrays. It is shown that the multiplications in the processing elements can be implemented by lookup-tables using dual-port ROM. Two variants of systolic structures using ROM-based multipliers are presented for efficient implementation of the proposed algorithm. The proposed structures are found to offer significant saving of hardware, require less latency, and yield more throughput over the existing structures. Apart from simplicity and regularity, the proposed structures would also have flexibility of implementation by CORDIC circuits and canonical-signed-digit-based multipliers as well. [ABSTRACT FROM AUTHOR]

This paper addresses video error concealment techniques, focusing on motion vector recovery of P- and B-frames, to improve the decoded quality of videos when bit stream data incurs transmission errors. First, we propose a dynamic programming (DP) technique to optimize the path cost in a multistage topology and evaluate the goodness of boundary matching and side smoothness of recovered macroblocks. However, due to the high computational complexity of DP, a suboptimal alternative enhanced with an adaptive Kalman filtering algorithm is adopted instead. Experiments show that by considering the side smoothness between adjacent recovered MBs, the proposed algorithm improves the reconstructed video quality by about 0.4–0.9 dB with a packet loss rate up to 15%, compared to a traditional boundary matching algorithm. In addition, subjective image inspection demonstrates the efficiency of the proposed algorithm in retaining the continuity of lines and image details. [ABSTRACT FROM AUTHOR]

Scalable video coding is an ongoing standard, and the current working draft (WD) is an extension of H.264/AVC. In the WD, an exhaustive search technique is employed to select the best coding mode for each macroblock. This technique achieves the highest possible coding efficiency, but it results in extremely large encoding time which obstructs it from practical use. This paper proposes a fast mode decision algorithm for inter-frame coding for spatial, coarse grain signal-to-noise ratio, and temporal scalability. It makes use of the mode-distribution correlation between the base layer and enhancement layers. Specifically, after the exhaustive search technique is performed at the base layer, the candidate modes for enhancement layers can be reduced to a small number based on the correlation. Experimental results show that the fast mode decision scheme reduces the computational complexity significantly with negligible coding loss and bit-rate increases. [ABSTRACT FROM AUTHOR]

H.264/AVC significantly outperforms previous video coding standards with many new coding tools. However, the better performance comes at the price of the extraordinarily huge computational complexity and memory access requirement, which makes it difficult to design a hardwired encoder for real-time applications. In addition, due to the complex, sequential, and highly data-dependent characteristics of the essential algorithms in H.264/AVC, both the pipelining and the parallel processing techniques are constrained to be employed. The hardware utilization and throughput are also decreased because of the block/MB/frame-level reconstruction loops. In this paper, we describe our techniques to design the H.264/AVC video encoder for HDTV applications. On the system design level, in consideration of the characteristics of the key components and the reconstruction loops, the four-stage macroblock pipelined system architecture is first proposed with an efficient scheduling and memory hierarchy. On the module design level, the design considerations of the significant modules are addressed followed by the hardware architectures, including low-bandwidth integer motion estimation, parallel fractional motion estimation, reconfigurable intrapredictor generator, dual-buffer block-pipelined entropy coder, and deblocking filter. With these techniques, the prototype chip of the efficient H.264/AVC encoder is implemented with 922.8 K logic gates and 34.72-KB SRAM at 108-MHz operation frequency. [ABSTRACT FROM AUTHOR]

This paper presents a novel efficient prediction algorithm to reduce redundant discrete cosine transform (DCT) and quantization computations for H.264 encoding optimization. A theoretical analysis is performed to study the sufficient condition for DCT coefficients to be quantized to zeros. As a result, three sufficient conditions corresponding to three types of transform and quantization methods in H.264 are proposed. Compared with other algorithms in the literature, the proposed algorithm derives more precise and efficient conditions to predict zero quantized DCT coefficients. Both the theoretical analysis and experimental results demonstrate that the proposed algorithm is superior to other algorithms in terms of the computational complexity reduction, encoded video quality, false acceptance rate, and false rejection rate. [ABSTRACT FROM AUTHOR]

Block-based motion estimation is widely used in video compression for exploiting video temporal redundancy. Although effective, the process is arguably the most computationally intensive part of a typical video encoder. To speed up the process, a large number of fast block-matching algorithms (BMAs) have been proposed for motion estimation by limiting the number of search locations or simplifying the measure of match between the two blocks under comparison. In this paper we propose a new BMA that measures the match by using such features as block sum and block variance, which can be easily computed using integral frame attributes. Experimental results show that the proposed BMA can reduce the computational complexity notably and achieve compression performance very close to that of existing BMAs using conventional block-matching measures. [ABSTRACT FROM AUTHOR]

A novel reversible data hiding algorithm, which can recover the original image without any distortion from the marked image after the hidden data have been extracted, is presented in this paper. This algorithm utilizes the zero or the minimum points of the histogram of an image and slightly modifies the pixel grayscale values to embed data into the image. It can embed more data than many of the existing reversible data hiding algorithms. It is proved analytically and shown experimentally that the peak signal-to-noise ratio (PSNR) of the marked image generated by this method versus the original image is guaranteed to be above 48 dB. This lower bound of PSNR is much higher than that of all reversible data hiding techniques reported in the literature. The computational complexity of our proposed technique is low and the execution time is short. The algorithm has been successfully applied to a wide range of images, including commonly used images, medical images, texture images, aerial images and all of the 1096 images in CorelDraw database. Experimental results and performance comparison with other reversible data hiding schemes are presented to demonstrate the validity of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Matching pursuit (MP) is a greedy algorithm that decomposes a signal into a linear combination of bases within an overcomplete dictionary. The MP algorithm is usually only approximated due to its massive computational complexity. By approximating a residual in a subspace, we propose a multiple blocks MP update algorithm for video coding that achieves a faster and better MP approximation than traditional algorithms. As the subspace is dependent on a residual, our algorithm is content-dependent. We evaluate the coding performance, including the peak signal-to- noise ratio, runtime, and subjective quality, of our algorithm and compare it with traditional MP algorithms. [ABSTRACT FROM AUTHOR]

A complexity reduction algorithm for an H.264 encoder is proposed. Computational savings are achieved by identifying, prior to motion estimation, macroblocks (MBs) that are likely to be skipped and hence saving further computational processing of these MBs. This early prediction is made by estimating a Lagrangian rate-distortion cost function which incorporates an adaptive model for the Lagrange multiplier parameter based on local sequence statistics. Simulation results demonstrate that the algorithm can achieve computational savings of 19%-67% (depending on the source sequence) with no significant loss of rate-distortion performance. [ABSTRACT FROM AUTHOR]

In this paper, a configurable coding scheme is proposed and analyzed with respect to computational complexity and distortion (C-D). The major coding modules are analyzed in terms of computational C-D in the H.263 video coding framework. Based on the analyzed data, operational C-D curves are obtained through an exhaustive search, and the Lagrangian multiplier method. The proposed scheme satisfies the given computational constraint independently of the changing properties of the input video sequence. A technique to adaptively control the optimal encoding mode is also proposed. The performance of the proposed technique is compared with a fixed scheme where parameters are determined by off-line processing. Experimental results demonstrate that the adaptive approach leads to computation reductions of up to 19%, which are obtained with test video sequences and compared to the fixed, while the peak signal-to-noise ratio degradations of the reconstructed video are less than 0.05 dB. [ABSTRACT FROM AUTHOR]

In this paper, the problems of redundancy allocation for providing effective error-resilience and service class distribution for enhanced quality of service (QoS) in real-time MPEG-2 video transport are addressed. A real-time low-complexity con- tent-based adaptive error-resilient approach is proposed for the transport of MPEG-2 video streams, encapsulated using real-time transport protocol (RTP) and delivered over heterogeneous net- works. An algorithm is derived using spatial and temporal properties of MPEG-2 video for assigning weights to each packet based on the estimated perceptual error. These weights, which indicate the relative importance of RTP packets, together with the communication channel characteristics are used to determine the allocation of resources for providing improved error-resilience and for assigning data packets to various classes of service in order to enhance the quality of transmission. Parameters extracted from the RTP header are used to determine the weights, so that the proposed algorithm can be implemented in real-time. This algorithm is used for adaptively allocating redundant forward error correction packets as well as for marking and forwarding of RTP packets in differentiated services (DiffServ). Simulation results are presented to show the significant improvement in performance based on our proposed approach to video transport. [ABSTRACT FROM AUTHOR]

The embedded multireference frames selection with variable block-size motion compensation model drastically in- creases the computational complexity of the H.264/AVC video coding standard. This paper proposes an adaptive hierarchical motion estimation (ME) algorithm for H.264/AVC with the objective of minimizing the complexity while maximizing the visual quality. The proposed algorithm is based on a framework that exploits the "history" of the motion intensity from a video sequence in order to control ME. The complexity and memory requirement for this meta information is low. The algorithm determines the motion intensity of a video sequence at three levels and accordingly employs different ME techniques. The results certify that the history-based hierarchical information can be very effective in improving the efficiency of ME. [ABSTRACT FROM AUTHOR]

The block-based discrete cosine transform (BDCT) is often used in image and video coding. It may introduce block artifacts at low data rates that manifest themselves as an annoying discontinuity between adjacent blocks. In this paper, we address this problem by investigating a transform-domain Markov random field (TD-MRF) model. Based on this model, two block artifact reduction postprocessing methods are presented. The first method, referred to as TD-MRF, provides an efficient progressive transform-domain solution. Our experimental results show that TD-MRF can reduce up to 90% of the computational complexity compared with spatial-domain MRF (SD-MRF) methods while still achieving comparable visual quality improvements. We then discuss a hybrid framework, referred to as TSD-MRF, that exploits the advantages of both TD-MRF and SD-MRF. The experimental results confirm that TSD-MRF can improve visual quality both objectively and subjectively over SD-MRF methods. [ABSTRACT FROM AUTHOR]

We present a framework for the systematic analysis of video encoding complexity, measured in terms of the number of motion estimation (ME) computations, that we illustrate on motion compensated wavelet video coding schemes. We demonstrate the graceful complexity scalability of these schemes through the modification of the spatiotemporal decomposition structure and the ME parameters, and the use of spatiotemporal prediction. We generate a wide range of rate-distortion-complexity (R-D-C) operating points for different sequences, by modifying these options. Using our analytical framework we derive closed form expressions for the number of ME computations for these different coding modes and show that they accurately capture the computational complexity independent of the underlying content characteristics. Our framework for complexity analysis can be combined with rate-distortion modeling to determine the encoding structure and parameters for optimal R-D-C tradeoffs. [ABSTRACT FROM AUTHOR]

The new video coding standard, H.264/MPEG-4 AVC, uses variable block sizes ranging from 4 × 4 to 16 × 16 in interframe coding. This new feature has achieved significant coding gain compared to coding a macroblock (MB) using fixed block size. However, this feature results in extremely high computational complexity when brute force rate distortion optimization (RDO) algorithm is used. This paper proposes a fast intermode decision algorithm to decide the best mode in intercoding. It makes use of the spatial homogeneity and the temporal stationarity characteristics of video objects. Specifically, spatial homogeneity of a MB is decided based on the MB's edge intensity, and temporal stationarity is decided by the difference of the current MB and it colocated counterpart in the reference frame. Based on the homogeneity and stationarity of the video objects, only a small number of intermodes are selected in the RDO process. The experimental results show that the fast intermode decision algorithm is able to reduce on the average 30% encoding time, with a negligible peak signal-to-noise ratio loss of 0.03 dB or, equivalently, a bit rate increment of 0.6%. [ABSTRACT FROM AUTHOR]

Many studies have performed transcoding of com- pressed video streams in the discrete cosine transform (DCT) domain to reduce computational complexity. On the other hand, most video compression standards recommend motion compensation in the spatial domain. Thus, compressed data that is motion-compensated in the spatial domain should be motion-compensated in the transform domain for the transform-domain transcoding. However, this combination of encoding in the spatial domain and decoding in the transform domain degrades image quality due to mismatches of the inverse DCT and motion compensation. There have been few investigations into this mismatch problem. In this paper, we establish that the rounding in calculation is the major cause of the mismatch. We investigate the mismatch problem in detail and propose a precision lifting method to reduce the effects of the mismatch problem. Experimental results show that our proposed method can effectively reduce the mismatch problem. [ABSTRACT FROM AUTHOR]

The H.264 video coding standard provides considerably higher coding efficiency than previous standards do, whereas its complexity is significantly increased at the same tune. In an H.264 encoder, the most time-consuming component is variable block-size motion estimation. To reduce the complexity of motion estimation, an early termination algorithm is proposed in this paper. It predicts the best motion vector by examining only one search point. With the proposed method, some of the motion searches can be stopped early, and then a large number of search points can be skipped. The proposed method can work with any fast motion estimation algorithm. Experiments are carried out with a fast motion estimation algorithm that has been adopted by H.264. Results show that significant complexity reduction is achieved while the degradation in video quality is negligible. [ABSTRACT FROM AUTHOR]

Zernike moments have been proven to be very powerful image descriptors. However, their computational complexity makes them unsuitable for real-time applications. In this paper, a mathematical relationship between geometric and Zernike moments is extracted. In this way, the computation of geometric moments is adequate to derive Zernike moments. Since geometric moments can be efficiently implemented in hardware and their calculation can be performed in real-time, we propose here a new real-time hardware architecture for the computation of Zernike moments. This method outperforms existing software approaches, especially for large images, allowing real-time processing of images up to 4 Mpixels. [ABSTRACT FROM AUTHOR]

The MPEG-4 core profile enables object-based coding. A core profile encoder may also have to be able to carry out simple profile frame-based coding. Frame-based coding is, for instance, needed when the object-based functionalities are not used or the target decoder has only simple profile capabilities. cellular nonlinear networks (CNN) offer an effective method to implement the segmentation needed in object-based coding. CNN can be implemented very efficiently with dedicated parallel processor arrays. These parallel processor arrays can integrated with sensor arrays in low-power low bit-rate mobile video encoders. it is shown here that an object-based core profile encoder can have advantages in frame-based simple profile encoding. The intermediate results of a CNN segmentation algorithm can be used in computational complexity reduction of motion estimation (ME). The CNN intermediate results indicate areas of motion within a frame. The areas without motion can be then used to stop the ME or to indicate MPEG-4 skip modes. All block-based ME algorithms can benefit from this knowledge. The intermediate results of the segmentation algorithm are evaluated with the full search and MVFAST ME algorithms. Rate-distortion and computational complexity results are computed with four different reference frame schemes. Considerable improvement in output bits and computational complexity is seen without loss in subjective video quality. The method also has applications in scene change detection. [ABSTRACT FROM AUTHOR]

We propose a new highly scalable wavelet transform-based Image coder, called S-SPECK, on the extension of a well-known zero-block image coder SPECK, by achieving not only distortion scalability, resolution scalability, and region of interest (ROI) retrievability, but also excellent compression performance with very low computational complexity. Though new features have been introduced into S-SPECK, our coder is quite competitive with SPECK on compression performance (peak signal-to-noise ratio) and computational complexity (encoding and decoding times) at various bit rates for standard test images. A novel quality layer formatting method is implemented in S-SPECK, which is much simpler and faster than PCRD used in JPEG2000. Extensive experiments have verified all our claims for S-SPECK. [ABSTRACT FROM AUTHOR]

An appropriate complexity analysis stage is the first and fundamental step for any methodology aiming at the implementation of today's (complex) multimedia algorithms. Such a stage may have different final implementation goals such as defining a new architecture dedicated to the specific multimedia standard under study, or defining an optimal instruction set for a selected processor architecture, or to guide the software optimization process in terms of control-flow and data-flow optimization targeting a specific architecture. The complexity of nowadays multimedia standards, in terms of number of lines of codes and cross-relations among processing algorithms that are activated by specific input signals, goes far beyond what the designer can reasonably grasp from the "pencil and paper" analysis of the (soft- ware) specifications. Moreover, depending on the implementation goal different measures and metrics are required at different steps of the implementation methodology or design flow. The process of extracting the desired measures needs to be supported by appropriate automatic tools, since code rewriting, at each design stage, may result resource consuming and error prone. This paper reviews the state of the art of complexity analysis methodologies oriented to the design of multimedia systems and presents an integrated tool for automatic analysis capable of producing complexity results based on rich and customizable metrics. The tool is based on a C virtual machine that allows extracting from any C program execution the operations and data-flow information, according to the defined metrics. The tool capabilities include the simulation of virtual memory architectures. This paper shows some examples of complexity analysis results that can be yielded with the tool and presents how the tools can be used at different stages of implementation methodologies. [ABSTRACT FROM AUTHOR]

The most popular shape from focus (SFF) methods in the literature are based on the concept of focused image sur- face (FIS)-the surface formed by the best focus points. According to paraxial-geometric optics, there is one-to-one correspondence between the shape of an object and the shape of its FIS. Therefore, the problem of three-dimensional (3-D) shape recovery from image focus can be described as the problem of determining the shape of the FIS. The conventional SFF method is inaccurate because of piecewise constant approximation of the FIS. The SFF method based on the FIS has shown better results by exhaustive search of the FIS shape using planar surface approximation at the cost of considerably higher computations. In this paper, search of the FIS shape is presented as an optimization problem, i.e., maximization of the focus measure in the 3-D image volume. The proposed method searches the optimal focus measure in the whole image volume, instead of the small volume as adopted in previous methods. The dynamic programming, instead of the approximation techniques, is used to search the optimal FIS shape. A direct application of dynamic programming on a 3-D data is impractical, because of higher computational complexity. Therefore a fast heuristic model based on dynamic programming is proposed for the search of FIS shape. The shape recovery results of the new method are better than previous methods. The proposed algorithm is significantly faster than the FIS algorithm, but a little slower than the conventional algorithm. [ABSTRACT FROM AUTHOR]

An improved fast full-search algorithm for motion estimation is proposed. The computations process of the sum of absolute difference and the multilevel successive elimination algorithm (MSEA) are theoretically analysed. Based on these analyzes, a new detection criterion and an estimation of the starting level are proposed in order to reduce the computations required for judging invalid candidate blocks. The simulation results show that the proposed algorithm achieves a computational timesaving of about 40% compared with the MSEA. [ABSTRACT FROM AUTHOR]

We analyze the problem of optimal data partitioning of MPEG-2 coded video in an operational rate-distortion context. The optimal algorithm is characterized and shown to have high complexity and delay. A causally optimal algorithm based on Lagrangian optimization is proposed, that optimally solves the problem for intra (I) pictures, and provides an optimal solution for predicted/interpolated (P/B) pictures when the additional constraints of causal operation and/or low-delay are imposed. A memoryless version of the algorithm, theoretically optimal for intrapictures only, is shown to perform almost identically but with significantly less computational complexity. Finally, a fast, suboptimal algorithm using purely rate-based optimization is also proposed, and is shown to perform quite close (within 1 dB) to the causally optimal one. Experimental results are provided using actual MPEG-2 coded video bitstreams. [ABSTRACT FROM AUTHOR]

This paper presents a fast binary motion estimation (BME) algorithm using diamond search pattern for MPEG-4 shape coding, which is the key technology for supporting the content-based video coding. Based on the properties of binary shape information, a boundary mask for efficient search positions can be generated. Therefore, a large number of search points can be skipped. Simulation results show that our algorithm combined with diamond shaped zones takes equal bit rate in the same quality but reduces the number of search points marvelously in BME to 0.6% compared with full search algorithm, which is described in MPEG-4 verification mode. The proposed algorithm will reduce computational complexity of shape coding significantly and be suitable for real-time software and hardware applications of MPEG-4 shape coding. [ABSTRACT FROM AUTHOR]

In this letter, we explore the rate-distortion (R-D) characteristics of binary shape information in the MPEG-4 standard. The shape coding scheme is a block-based context-based arithmetic encoding approach and distortion is introduced by down and up sampling. Generally, the shape bit rate and non- normalized distortion increase in proportion with the number of border blocks. At any given resolution scale, the more complex an object, the more distortion that is introduced. Consequently, we propose an R-D model based on the parameters derived from the border blocks and a block-based shape complexity for the video object. The computational complexity is much lower than other existing methods. Experimental results show that it can accurately predict the bit rate and distortion of the binary shape for rate control purposes. [ABSTRACT FROM AUTHOR]

Many fast block-matching algorithms (BMAs) reduce the computational complexity of motion estimation by sophisticatedly inspecting a subset of checking points, and stop only once all those checking points are examined. This means that the searching process for each current block cannot be interrupted even when it is performed in a software-based computation environment. Our main goal in this study was to allow the searching process to stop once a specified amount of computation has been performed. A novel computation-aware scheme is proposed, which first dynamically determines the target amount of computation power allocated to a frame, and then allocates this to each block in a computation-distortion-optimized manner. We proposed a rate-control-like procedure and a predicted computation-distortion benefit heuristic to realize this scheme. Conventional BMAs, such as full-search block matching, three-step search, new three-step search, four-step search, and diamond search, can be transformed into their corresponding computation-aware BMAs versions. In our simulations, the resulting computation-aware BMAs not only exhibit higher efficiency than conventional BMAs, but also allow the motion estimation terminating after any specified amount of computation has been performed (in units of checking points). [ABSTRACT FROM AUTHOR]

In this paper, we investigate three new methods to predict motion vectors (MVs) across subbands for multi-resolution motion estimation (MRME): linear prediction, median filtering (MF), and multi-candidate techniques. Compared to the conventional MRME techniques, the proposed linear-prediction-based and the MF-based techniques effectively overcome the problem of propagation of false MVs. A significant feature of these two techniques is that they impose no demand for additional bandwidth, and simulation studies show that they not only improve prediction performance, but also reduce the number of bits needed to encode the motion information. It is further shown that the improvement in the performance thus achieved involves little increase in the computational complexity. [ABSTRACT FROM AUTHOR]

The conventional variable-size block motion compensation technique, even though superior to the fixed-size block motion-compensation technique, cannot fully utilize the motion information of a frame for its partitioning. This paper presents a quadtree structured region-wise motion-compensation technique that utilizes more effectively the motion content of a frame in terms of the shape, size, and location of the partitioned regions. The proposed technique is based on a new coding scheme of the quadtree structure, where a two-bit code is used. The partitioning of a given frame is carried out through the processes of merging and combining. The merging process partitions the frame into a number of regions by carrying out all possible 4-to-1, 3-to-1, and 2-to-1 merges along the quadtree hierarchy according to some specified criteria, while the combining process combines some of the partitioned regions that have the same motion vector into a single region. The motion vectors of the resulting partitioned regions are coded by a new coding scheme that uses the temporal correlation of the motion fields. Test results of applying the proposed method on a number of MPEG video sequences are included. These results indicate that the proposed method can provide a significantly improved rate-distortion performance [ABSTRACT FROM PUBLISHER]