Search

Multiple description coding (MDC) decomposes one single media into several descriptions and transmits them over different channels for error resilience. Each description contributes to improving the reconstructed media quality when decoded. Distributed video coding (DVC) encodes multiple correlated images and utilizes error correction codes to shift the codec complexity to a joint decoder. Combining MDC with DVC (MDVC) yields a stable codec for mobile encoders. In this paper, to improve the MDVC codec performance, image correlations among the MDVC processing modules were exploited to improve reconstructed video quality and enhance transmission robustness. At the side encoder, a DVC-based adaptive differential pulse code modulation was designed to remove interframe redundancy to enhance rate-distortion performances. For the MDVC central decoding, intradescription and interdescription correlations were utilized to dynamically select the best reconstructed frames from two descriptions, instead of selecting just one description or all key-frames from two descriptions. Experiments showed that, as compared to previous methods, the proposed MDVC control method yielded 1–2 dB higher in image PSNRs for Wyner–Ziv reconstructed frames at the side decoder when encoding low-to-medium complexity videos. For high-complexity videos, it effectively prevents error correction of Wyner–Ziv frames from malfunctioning and yields about 3 dB higher in PSNR. The proposed MDVC central decoder control yields 1–4 dB higher PSNRs, as compared to side decoders. Under lossy transmission, it demonstrates 27–64% smaller PSNR variations, as compared to that of combining key-frames as the decoded video. The proposed MDVC system and control not only improve the DVC reconstructed video quality, but also reduce the quality fluctuation artifacts of MDC coded video for mobile coders. [ABSTRACT FROM PUBLISHER]

Distributed video coding (DVC) is a video coding paradigm that allows for a low-complexity encoding process by exploiting the temporal redundancies in a video sequence at the decoder side. State-of-the-art DVC systems exhibit a structural coding delay since exploiting the temporal redundancies through motion-compensated interpolation requires the frames to be decoded out of order. To alleviate this problem, we propose a system based on motion-compensated extrapolation that allows for efficient low-delay video coding with low complexity at the encoder. The proposed extrapolation technique first estimates the motion field between the two most recently decoded frames using the Lucas–Kanade algorithm. The obtained motion field is then extrapolated to the current frame using an extrapolation grid. The proposed techniques are implemented into a novel architecture featuring hybrid block-frequency Wyner–Ziv coding as well as mode decision. Results show that having references from both temporal directions in interpolation provides superior rate-distortion performance over a single temporal direction in extrapolation, as expected. However, the proposed extrapolation method is particularly suitable for low-delay coding as it performs better than H.264/AVC intra, and it is even able to outperform the interpolation-based DVC codec from DISCOVER for several sequences. [ABSTRACT FROM PUBLISHER]

Video transcoding is proposed for the bitrate adaption, spatial and/or temporal resolutions adaption, and video format conversion. In video streaming application, it converts videos at server to the compatible versions demanded by networks or clients' devices, so that the videos can be delivered over networks and displayed in the clients' devices successfully. This paper provides a universal rate control scheme for various video transcoding purposes. First, a new rate-distortion (R-D) model is established theoretically for better representing the real R-D feature of transcoding. Second, a window-level rate control algorithm is proposed for providing smooth visual quality with compliant buffer constraint by utilizing the two-pass R-D model and a new proposed sliding window buffer control strategy. Finally, a universal rate control scheme for transcoding is developed based on the established R-D model and the proposed window-level rate control algorithm. The extensive experimental results demonstrate that as compared to other state-of-the-art rate control algorithms for transcoding, the proposed scheme can achieve more bit control accuracy with the average mismatch below 0.2%, and much more consistent visual quality with 0.1 dB–0.3 dB peak-to-signal noise ratio improvement in average, while with low computational complexity. [ABSTRACT FROM PUBLISHER]

Early direct mode decision is a popular technique to improve the execution speed of inter-predictions in a B slice. However, the improvement is limited when this technique is applied to a hardware-based pipelined architecture or to the video sequences where the ratio of macroblocks (MBs) encoded as the direct mode is low. This paper proposes a novel fast inter-prediction algorithm for B slices which increases the encoding speed by early decision of the direction of the inter-prediction using spatial and temporal correlation in a video. A speed-up is achieved by selecting a prediction direction with a lower complexity and discarding a prediction direction with a higher complexity. For the case when early mode decision is not possible, additional speed-up is achieved by partially skipping unidirectional motion estimation (ME) if the estimated cost of the ME is greater than the result of the direct mode prediction that is completed much faster than ME. This proposed sequence of early decisions is referred to as cascaded direction filtering (CDF). The proposed algorithm increases the early mode decision rate, which improves the encoding speed effectively for a hardware-based pipelined architecture as well as videos with a low ratio of MBs encoded as the direct mode. The additional memory size and bandwidth overhead required for the proposed CDF are very small. Experimental results show that the proposed CDF scheme improves the encoding speed by 45% for B slices and 32% for overall sequences. The bitrate is increased by less than 1% with a small peak signal-to-noise ratio degradation of 0.03 dB on average. [ABSTRACT FROM AUTHOR]

An important recent application of image registration is the estimation of global motion parameters for object-based video coding. However, the main disadvantage of standard approaches to global motion estimation (GME) is the increased computational complexity with the higher degree of motion models when compared to block-based local motion estimation approaches. In this paper, we propose a new low complexity GME algorithm. In our proposed algorithm, full-precision images are replaced with 1 bit-per-pixel images which allows many of the arithmetic operations in the standard GME approach to be replaced with logic operations. Experimental results show that our proposed algorithm achieves the same registration accuracy as the standard GME approach but with significantly reduced computational complexity. Our results also demonstrate the superior performance of the proposed algorithm when compared with previously proposed low-complexity GME approaches. [ABSTRACT FROM AUTHOR]

The H.264/AVC video coding standard can achieve higher compression performance than previous video coding standards, such as MPEG-2, MPEG-4, and H.263. In order to improve the coding performance, the H.264/AVC encoder employs various modes and the rate-distortion (RD) optimization method for selection of an optimum mode. Since the encoder computes RD costs of all possible coding modes to decide the optimum mode, it induces high computational complexity. In this paper, we introduce a fast mode decision method for inter picture macroblocks to reduce the computational complexity. The proposed method significantly reduces the number of candidate modes for the RD optimization process by detecting spatially and temporally homogeneous regions and analyzing motion costs for inter modes and intra prediction costs for intra modes. Experimental results demonstrate that the proposed method drastically reduces the encoding time and the number of the RD cost calculation process while maintaining the high coding efficiency. [ABSTRACT FROM AUTHOR]

One of the primary goals of the airborne vehicle detection system is to reduce the risks of incident collisions and to relieve traffic jam caused by the increasing number of vehicles. Different from the stationary systems, which are usually fixed on buildings, the airborne systems in unmanned aircrafts or satellites take the advantages of wider view angle and higher mobility. However, detecting vehicles in airborne videos is a challenging task because of the scene complexity and platform movement. The direct application of the traditional image processing techniques to the problem may result in low detection rate or cannot meet the requirements of real-time applications. To address these problems, a new and efficient method composed by two stages, attention focus extraction and vehicle classification is proposed in this paper. Our work makes two key contributions. The first is the introduction of a new attention focus extraction algorithm, which can quickly detect the candidate vehicle regions to make the algorithm focus on much smaller regions for faster computation. The second contribution is a simple and efficient classification process, which is built using the AdaBoost learning algorithm. The classification process, which is a hierarchical structure, is designed to obtain a lower false alarm rate by looking for vehicles in the candidate regions. Experimental results demonstrate that, compared with other representative algorithms, our method can obtain better performance in terms of higher detection rate and lower false positive rate, while meeting the needs of real-time application. [ABSTRACT FROM AUTHOR]

Several algorithms were proposed to predict the zero-quantized DCT coefficients and reduce the computational complexity of transform and quantization. It is observed that these prediction algorithms achieve good performance for all-zero-quantized DCT blocks. However, the efficiency is much lower for non-all-zero-quantized DCT blocks. This paper proposes an algorithm to improve the prediction efficiency for non-all-zero-quantized DCT blocks. The proposed method extends the prediction to 1-D transforms by developing new Gaussian distribution based thresholds for 1-D transformation. Moreover, the proposed algorithm can perform the prediction on 1-D transforms in both the pixel domain and the transform domain. The prediction for the first stage of 1-D transforms is performed in the pixel domain. However, the second stage of 1-D transforms is performed in the 1-D DCT domain. Because after the first stage of 1-D transforms most energy is concentrated to a few low frequency 1-D DCT coefficients, many transforms in the second stage are skipped. Furthermore, the method fits well the traditional row and column transform structure, and it is more implementation friendly. Simulation results show that the proposed model reduces the complexity of transform and quantization more efficiently than competing techniques. In addition, it is shown that the overall video quality achieved by the proposed algorithm is comparable to the references. [ABSTRACT FROM PUBLISHER]

Recently, an efficient coding tool named adaptive interpolation filtering (AIF) has been proposed to hybrid video coding scheme. By introducing Wiener filter into the fractional-pixel interpolation procedure, AIF can reduce the inter-prediction error and improve coding efficiency significantly. However, the training-based Wiener filter mechanism brings AIF an inherent multi-pass encoding structure, which imposes big burdens on the encoder in terms of huge computational complexity and memory access. In this paper, we propose a single-pass-based localized adaptive interpolation filtering (SPL-AIF) algorithm for video coding, which can reduce the complexity of AIF dramatically without sacrifice of its outstanding coding performance. The proposed SPL-AIF algorithm is based on the observation that there is a high correlation among optimal interpolation filters of consecutive frames, and different regions in a frame often possess different statistical characteristics. Accordingly, the proposed algorithm can be designed including two major parts. First, a competitive filter set which includes the optimal interpolation filters of several previous frames as well as the fixed H.264/AVC interpolation filters is built up for the coding of the current frame. Then a rate-distortion optimization criterion is used to select the best one at macroblock (MB) level. In order to reduce overhead, a predictive coding method is used to compress the filter signaling flag for each MB. Experimental results show that, by using the proposed algorithm, the encoding complexity can be reduced significantly while the average coding gain in Bjöntegaard distortion bit-rate reduction can be improved about 1% compared with the multi-pass AIF. The proposed method has been adopted into the Video Coding Expert Group Key Technology Area software. [ABSTRACT FROM PUBLISHER]

H.264/AVC offers many coding tools for achieving high compression gains of up to 50% more than other standards. These tools dramatically increase the computational complexity of the block based motion estimation (BB-ME) which consumes up to 80% of the entire encoder's computations. In this paper, computationally efficient accurate skipping models are proposed to speed up any BB-ME algorithm. First, an accurate initial search center (ISC) is decided using a smart prediction technique. Thereafter, a dynamic early stop search termination (DESST) is used to decide if the block at the ISC position can be considered as a best match candidate block or not. If the DESST algorithm fails, a less complex style of the motion estimation algorithm which incorporates dynamic padding window size technique will be used. Further reductions in computations are achieved by combining the following two techniques. First, a dynamic partial internal stop search technique which utilizes an accurate adaptive threshold model is exploited to skip the internal sum of absolute difference operations between the current and the candidate blocks. Second, a dynamic external stop search technique greatly reduces the unnecessary operations by skipping all the irrelevant blocks in the search area. The proposed techniques can be incorporated in any block matching motion estimation algorithm. Computational complexity reduction is reflected in the amount of savings in the motion estimation encoding time. The novelty of the proposed techniques comes from their superior saving in computations with an acceptable degradation in both peak signal-to-noise ratio (PSNR) and bit-rate compared to the state of the art and the recent motion estimation techniques. Simulation results using H.264/AVC reference software (JM 12.4) show up to 98% saving in motion estimation time using the proposed techniques compared to the conventional full search algorithm with a negligible degradation in the PSNR by approximately 0.05 dB and a small increase in the required bits per frame by only 2%. Experimental results also prove the effectiveness of the proposed techniques if they are incorporated with any fast BB-ME technique such as fast extended diamond enhanced predictive zonal search and predictive motion vector field adaptive search technique. [ABSTRACT FROM PUBLISHER]

The H.264/AVC standard achieves a high coding efficiency compared to previous standards. However, this gain is accomplished at great computational cost, with mode decision being one of the most demanding subsystems. In this paper, a two-level classification-based approach to the inter mode decision problem is proposed. A first classifier detects SKIP/Direct modes, while a second one is able to decide whether to use a large (16\,\times\,16, 16\,\times\,8, and 8\,\times\,16) or a small mode (8\,\times\,8, 8\,\times\,4, 4\,\times\,8, and 4\,\times\,4). The suggested classifiers are binary and linear, and the input features in the classifiers have been carefully selected. A novel cost function that pays more attention to the most critical samples during the classifier training process has been designed. The experimental results show an average computational savings of 60% of the total encoding time with respect to JM10.2 over a comprehensive variety of sequences and formats. This is achieved with negligible degradation in rate-distortion performance and compares favorably with state-of-the-art fast mode decision methods. Furthermore, the proposed method has been successfully assessed at different levels of complexity reduction. [ABSTRACT FROM AUTHOR]

We propose in this paper an efficient, adaptive, and locality-based graph partitioning method for video scene clustering. First, a graph partitioning method is proposed to group video shots into scenes, and a peer-group filtering (PGF) scheme is used to identify all the shots similar to each particular shot based on Fisher's discriminant analysis. To work with computable shot similarity measures that have only limited discriminating power, we develop a graph partitioning scheme to cluster the shots by maximizing the likeness of shots within the same cluster and minimizing that between different clusters. Second, considering that video data are normally obtained and viewed sequentially, we propose to perform a locality-based PGF and graph partitioning on video segments with 50 shots, 100 shots, and so on. This proposed locality-based method has the advantage that the number of scene clusters is not required to be known a priori, and it can achieve performance comparable to that processing on the whole video sequence. Experimental results are presented to demonstrate the effectiveness and efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

Exhaustive mode decision has been exploited in multiview video coding for effectively improving the coding efficiency, but at the expense of yielding much higher computational complexity. In this paper, a fast mode decision algorithm, called the mode correlation-based mode decision (MCMD), is proposed to speed up the encoding process by reducing the number of the modes required to be checked. In our approach, all the prediction modes are first categorized into five motion-activity classes, and only one of them will be chosen to identify the optimal mode in a hierarchical manner, as follows. For each macroblock (MB), the proposed MCMD algorithm always begins with checking whether the rate-distortion cost computed at the SKIP mode (i.e., Class 1) is below an adaptive threshold for providing a possible early termination chance. If this early termination condition is not met, one of the remaining four motion-activity classes will be chosen for further mode checking according to the analysis of the predicted motion vector (PMV) of the current MB. The above-mentioned adaptive threshold and PMV are derived by exploiting the mode correlation between the current MB and a set of adjacent MBs (i.e., region of support) in the current view and its neighboring view. Experimental results have shown that compared with exhaustive mode decision, which is a default approach set in the joint multiview video model (JMVM) reference software, the proposed MCMD algorithm achieves a reduction of the computational complexity by 73.39% on average, while incurring only 0.07 dB loss in peak signal-to-noise ratio (PSNR) and 2.22% increment on the total bit rate. [ABSTRACT FROM AUTHOR]

Visual surveillance from low-altitude airborne platforms plays a key role in urban traffic surveillance. Moving vehicle detection and motion analysis are very important for such a system. However, illumination variance, scene complexity, and platform motion make the tasks very challenging. In addition, the used algorithms have to be computationally efficient in order to be used on a real-time platform. To deal with these problems, a new framework for vehicle detection and motion analysis from low-altitude airborne videos is proposed. Our paper has two major contributions. First, to speed up feature extraction and to retain additional global features in different scales for higher classification accuracy, a boosting light and pyramid sampling histogram of oriented gradients feature extraction method is proposed. Second, to efficiently correlate vehicles across different frames for vehicle motion trajectories computation, a spatio-temporal appearance-related similarity measure is proposed. Compared to other representative existing methods, our experimental results showed that the proposed method is able to achieve better performance with higher detection rate, lower false positive rate, and faster detection speed. [ABSTRACT FROM AUTHOR]

The main challenge in video capsule endoscopic system is to reduce the area and power consumption while maintaining acceptable video reconstruction. In this paper, a subsample-based data compressor for video endoscopy application is presented. The algorithm is developed around the special features of endoscopic images that consists of a differential pulse-coded modulation (DPCM) followed by Golomb–Rice coding. Based on the nature of endoscopic images, several subsampling schemes on the chrominance components are applied. This video compressor is designed in a way to work with any commercial low-power image sensors that outputs image pixels in a raster scan fashion, eliminating the need of memory buffer and temporary storage (as needed in transform coding schemes). An image corner clipping algorithm is also introduced. The reconstructed images have been verified by five medical doctors for acceptability. The proposed low-complexity design is implemented in a 0.18 \mum CMOS technology and consumes 592 standard cells, 0.16~mm\times 0.16~mm silicon area, and 42 \muW of power. Compared to other algorithms targeted to video capsule endoscopy, the proposed raster-scan-based scheme performs strongly with a compression ratio of 80% and a very high reconstruction peak signal-to-noise ratio (over 48 dB). [ABSTRACT FROM AUTHOR]

In centralized transportation surveillance systems, video is captured and compressed at low processing power remote nodes and transmitted to a central location for processing. Such compression can reduce the accuracy of centrally run automated object tracking algorithms. In typical systems, the majority of communications bandwidth is spent on encoding temporal pixel variations such as acquisition noise or local changes to lighting. We propose a tracking-aware, H.264-compliant compression algorithm that removes temporal components of low tracking interest and optimizes the quantization of frequency coefficients, particularly those that most influence trackers, significantly reducing bitrate while maintaining comparable tracking accuracy. We utilize tracking accuracy as our compression criterion in lieu of mean squared error metrics. Our proposed system is designed with low processing power and memory requirements in mind, and as such can be deployed on remote nodes. Using H.264/AVC video coding and a commonly used state-of-the-art tracker we show that our algorithm allows for over 90% bitrate savings while maintaining comparable tracking accuracy. [ABSTRACT FROM AUTHOR]

H.264/AVC, the latest video coding standard of the Joint Video Team, greatly outperforms previous standards in terms of coding bitrate and video quality, because it adopts several new techniques. However, the computational complexity is also considerably increased due to these new components. In this paper, we propose fast algorithms based on statistical learning to reduce the computational cost involved in three main components in H.264 encoder, i.e., intermode decision, multi-reference motion estimation (ME), and intra-mode prediction. First, representative features are extracted to build the learning models. Then, an offline pre-classification approach is used to determine the best results from the extracted features, thus a significant amount of computation is reduced based on the classification strategy. The proposed statistical learning-based approach is applied to the aforementioned three main components in H.264 encoder to speed up the computation. Experimental results show that the ME time of the proposed system is significantly sped up with 12 times faster than the conventional fast ME algorithm of H.264, and the total encoding time of the proposed encoder is greatly reduced with about four times faster than the fast encoder EPZS in the H.264 reference code with negligible video quality degradation. [ABSTRACT FROM AUTHOR]

This paper presents a real-time HD1080p view synthesis engine based on the reference algorithm from 3-D video coding team by solving high computational complexity and high memory cost problems. For the computational complexity, we propose the bilinear interpolation to simplify the hole filling process, and the Z scaling method with floating-point format to reduce the cost of homography calculation. For the memory cost, we propose the frame-level pipelining to reduce the requirement of warped depth maps, and the column-order warping method to remove the Z-buffer in occlusion handling. With the 90 nm complementary metal-oxide-semiconductor technology, our view synthesis engine can archive the throughput of 32.4 f/s for HD1080p videos with the gate count of 268.5 K and the internal memory of 69.4 kbytes. The experimental result shows our implementation has the similar synthesis quality as the original reference algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel variable bit rate (VBR) controller for real-time H.264/scalable video coding (SVC) applications. The proposed VBR controller relies on the fact that consecutive pictures within the same scene often exhibit similar degrees of complexity, and consequently should be encoded using similar quantization parameter (QP) values for the sake of quality consistency. In order to prevent unnecessary QP fluctuations, the proposed VBR controller allows for just an incremental variation of QP with respect to that of the previous picture, focusing on the design of an effective method for estimating this QP variation. The implementation in H.264/SVC requires to locate a rate controller at each dependency layer (spatial or coarse grain scalability). In particular, the QP increment estimation at each layer is computed by means of a radial basis function (RBF) network that is specially designed for this purpose. Furthermore, the RBF network design process was conceived to provide an effective solution for a wide range of practical real-time VBR applications for scalable video content delivery. In order to assess the proposed VBR controller, two real-time application scenarios were simulated: mobile live streaming and Internet protocol television broadcast. It was compared to constant QP encoding and a recently proposed constant bit rate (CBR) controller for H.264/SVC. The experimental results show that the proposed method achieves remarkably consistent quality, outperforming the reference CBR controller in the two scenarios for all the spatio-temporal resolutions considered. [ABSTRACT FROM AUTHOR]

This paper presents a new video compression framework over H.264/AVC scheme that integrates our proposed structured priority belief propagation (BP)-based inpainting prediction (IP) to exploit the intrinsic nonlocal and geometric regularity in video samples. Unlike the existing edge-based inpainting adopted in lossy image coding, the optimal predictor could maintain the pixel-wise fidelity and the robust error resilience without any assistant information. Beyond the local prediction limitation of traditional intra and inter-modes, the priority BP with regularized structure priors of a spatio-temporal Markov random field is imposed on the predictor in an adaptive and more convergent sense. Specifically, the structured sparsity of the predicted macroblock region is inferred by tensor voting projected from the co-located decoded regions. In turn, the priority and visiting order of nodes are assigned according to the sets of updated beliefs as the propagation of messages. Through relatively few iterations of forward and backward process, the sparse inference of priority BP would ensure a stable marginal belief distribution on the structure and texture through updating local messages and beliefs. Within the optimal mode selection on rate-distortion optimization (RDO), the IP-mode with structured priority BP outperforms the existing vision-based approaches, and specially achieves a better objective rate-distortion performance besides visual quality. The IP-mode with structured priority BP can be applied to both I and P frames to generate low entropy residue, e.g., homogeneous visual patterns, and the computation complexity is also competitive with one iteration of sparse inference. Moreover, it behaves more resilient with an intrinsic probabilistic inference than the intra and inter-modes. [ABSTRACT FROM AUTHOR]

Since different regions of a color image generally exhibit different spectral characteristics, the energy compaction of applying a single spectral transform to all regions is largely inefficient from a compression perspective. Thus, it is proposed that different subsets of wavelet coefficients of a color image be subjected to different spectral transforms before the resultant coefficients are coded by an efficient wavelet coefficient coding scheme such as that used in JPEG2000 or color set partitioning in hierarchical trees (CSPIHT). A quadtree represents the spatial partitioning of the set of high frequency coefficients of the color planes into spatially oriented subsets which may be further partitioned into smaller directionally oriented subsets. The partitioning decisions and decisions to employ fixed or signal-dependent bases for each subset are rate-distortion (R-D) optimized by employing a known analytical R-D model for these coefficient coding schemes. A compression system of asymmetric complexity, that integrates the proposed adaptive spectral transform with the CSPIHT coefficient coding scheme yields average coding gains of 0.3 dB and 0.9 dB in the Y component at 1.0 b/p and 2.5 b/p, respectively, and 0.9 dB and 1.35 dB in the U and V components at 1.0 b/p and 2.5 b/p, respectively, over a reference compression system that integrates the single spectral transform derived from the entire image with the CSPIHT coefficient coding scheme. [ABSTRACT FROM AUTHOR]

Face regions are visual focuses in conversational video communications, thus better reconstruction quality of the regions of interest (ROI) is highly desired or necessary in the bandwidth-constrained conversational video coding. In this paper, we introduce an efficient motion based face detection method to identify face blocks in the first step, which can reduce computational complexity substantially without any loss in face detection results. Then an active contour model is applied to find face contours for more refined and compact face regions. Based on the well-located and compact face regions, facial feature priority based bit allocation is proposed for face ROI based conversational video coding. Experimental results demonstrate that the proposed face region based coding can considerably improve the coding results in the face regions, compared with two other relevant video coding schemes, in terms of objective rate-distortion performance as well as subjective visual quality. [ABSTRACT FROM AUTHOR]

In recent years, video applications on handheld devices became more and more popular. Due to limited computational capability and power supply in handheld devices, rate-complexity-distortion optimization (RCDO) algorithms at encoder side draw increasing attention. The target of RCDO is to obtain the best rate-distortion (R-D) performance under a constraint of complexity. Generally, there are three essential problems in RCDO. First, complexity needs to be properly mapped to a target in terms of coding parameters such that the control over complexity can be achieved. Second, the complexity budget should be efficiently distributed among frames or other coding units. Third, the allocated budget for each coding unit has to be effectively used to obtain good R-D performance. In this paper, these problems are well addressed. To obtain a large dynamic range in complexity control, medium-granularity control methods are presented. Then, a frame level complexity allocation algorithm is developed based on dependent rate-distortion function. Finally, an adaptive mode and reference searching method is proposed for motion compensation process. Comprehensive simulations verify the proposed algorithms. In the environment of the H.264/AVC reference software, an average gain of over 0.5 dB and 0.7 dB in BD-PSNR was achieved for nine sequences at low complexity when compared to two RCDO methods from literature. Moreover, experiments on x264 (a practical implementation of H.264/AVC) show that the proposed algorithms outperform predefined complexity levels by x264 in terms of both coding efficiency and computational scalability. [ABSTRACT FROM AUTHOR]

This paper jointly considers the mechanisms of rate control and the rate-distortion optimization (RDO) for the H.264/AVC hardware encoder. The proposed architecture performs intra prediction and inter prediction with our rate control mechanism in the first two stages. In addition, a low complexity macroblock (MB)-level mean absolute difference (MAD) prediction algorithm which considers both the motion information and the MAD value in the neighboring and current MBs is proposed. The proposed rate control algorithm can reduce the computational complexity and does not suffer from data dependency problems which may decrease the rate-distortion performance, thus it is suitable for H.264/AVC hardware encoders. Furthermore, the RDO-based architecture for the H.264/AVC encoder reduces the number of accurate rate-distortion cost calculators while maintaining the high rate-distortion performance. Experimental results show that the proposed rate control algorithm with the RDO-based architecture can improve the rate-distortion performance of H.264/AVC. [ABSTRACT FROM AUTHOR]

This paper presents a highly efficient audio-visual recognition system in compression domain. For face recognition systems, the multiband feature fusion method selects the wavelet subbands that are invariant to illumination and facial expression variations. These subbands will be extracted directly from the inverse quantization in the compression system. By taking the inverse quantized wavelet coefficient of the video as the input, the inverse wavelet transform which corresponds to image reconstruction is omitted. As a result, the computational complexity of the conventional video-based face recognition system is reduced. We also present a set of new face localization methods to localize the facial wavelet coefficients from the wavelet subband image. The dual optimal multiband feature fusion method is then used to fuse the two set of wavelet coefficients and generate the visual scores. Experimental results show that with low computational complexity, the proposed system achieves high recognition accuracy in UNMC-VIER, CUAVE, and XM2VTS audio-visual database. [ABSTRACT FROM AUTHOR]

Corner feature point detection with both the high-speed and high-quality is still very demanding for many real-time computer vision applications. The Harris and Kanade-Lucas-Tomasi (KLT) are widely adopted good quality corner feature point detection algorithms due to their invariance to rotation, noise, illumination, and limited view point change. Although they are widely adopted corner feature point detectors, their applications are rather limited because of their inability to achieve real-time performance due to their high complexity. In this paper, we redesigned Harris and KLT algorithms to reduce their complexity in each stage of the algorithm: Gaussian derivative, cornerness response, and non-maximum suppression (NMS). The complexity of the Gaussian derivative and cornerness stage is reduced by using an integral image. In NMS stage, we replaced a highly complex sorting and NMS by the efficient NMS followed by sorting the result. The detected feature points are further interpolated for sub-pixel accuracy of the feature point location. Our experimental results on publicly available evaluation data-sets for the feature point detectors show that our low complexity corner detector is both very fast and similar in feature point detection quality compared to the original algorithm. We achieve a complexity reduction by a factor of 9.8 and attain 50 f/s processing speed for images of size 640\,\times\,480 on a commodity central processing unit with 2.53 GHz and 3 GB random access memory. [ABSTRACT FROM PUBLISHER]

This letter investigates source-channel coding for error-resilient video streaming using redundant encoding. We estimate the end-to-end distortion per redundantly encoded macroblock (MB) via extension of the recursive optimal per-pixel estimate to encompass redundant transmissions. Redundant encoding is formulated as joint optimization of the MB parameters in the primary and redundant transmissions. We present three encoding strategies with different gain-complexity tradeoffs. The proposed methods are general in nature, and could be implemented on top of any (hybrid) video codec. Simulation results employing H.264's redundant slice mechanism show significant performance gains over conventional error-resilient encoding methods and naive redundant encoding schemes. [ABSTRACT FROM PUBLISHER]

We present in this paper an integrated solution to rapidly recognizing dynamic objects in surveillance videos by exploring various contextual information. This solution consists of three components. The first one is a multi-view object representation. It contains a set of deformable object templates, each of which comprises an ensemble of active features for an object category in a specific view/pose. The template can be efficiently learned via a small set of roughly aligned positive samples without negative samples. The second component is a unified spatio-temporal context model, which integrates two types of contextual information in a Bayesian way. One is the spatial context, including main surface property (constraints on object type and density) and camera geometric parameters (constraints on object size at a specific location). The other is the temporal context, containing the pixel-level and instance-level consistency models, used to generate the foreground probability map and local object trajectory prediction. We also combine the above spatial and temporal contextual information to estimate the object pose in scene and use it as a strong prior for inference. The third component is a robust sampling-based inference procedure. Taking the spatio-temporal contextual knowledge as the prior model and deformable template matching as the likelihood model, we formulate the problem of object category recognition as a maximum-a-posteriori problem. The probabilistic inference can be achieved by a simple Markov chain Mento Carlo sampler, owing to the informative spatio-temporal context model which is able to greatly reduce the computation complexity and the category ambiguities. The system performance and benefit gain from the spatio-temporal contextual information are quantitatively evaluated on several challenging datasets and the comparison results clearly demonstrate that our proposed algorithm outperforms other state-of-the-art algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, a novel algorithm called spatially varying transform (SVT) is proposed to improve the coding efficiency of video coders. SVT enables video coders to vary the position of the transform block, unlike state-of-art video codecs where the position of the transform block is fixed. In addition to changing the position of the transform block, the size of the transform can also be varied within the SVT framework, to better localize the prediction error so that the underlying correlations are better exploited. It is shown in this paper that by varying the position of the transform block and its size, characteristics of prediction error are better localized, and the coding efficiency is thus improved. The proposed algorithm is implemented and studied in the H.264/AVC framework. We show that the proposed algorithm achieves 5.85% bitrate reduction compared to H.264/AVC on average over a wide range of test set. Gains become more significant at medium to high bitrates for most tested sequences and the bitrate reduction may reach 13.50%, which makes the proposed algorithm very suitable for future video coding solutions focusing on high fidelity video applications. The gain in coding efficiency is achieved with a similar decoding complexity which makes the proposed algorithm easy to be incorporated in video codecs. However, the encoding complexity of SVT can be relatively high because of the need to perform a number of rate distortion optimization (RDO) steps to select the best location parameter (LP), which indicates the position of the transform. In this paper, a novel low complexity algorithm is also proposed, operating on a macroblock and a block level, to reduce the encoding complexity of SVT. Experimental results show that the proposed low complexity algorithm can reduce the number of LPs to be tested in RDO by about 80% with only a marginal penalty in the coding efficiency. [ABSTRACT FROM AUTHOR]

This paper discusses a privacy-protected video surveillance system that makes use of JPEG extended range (JPEG XR). JPEG XR offers a low-complexity solution for the scalable coding of high-resolution images. To address privacy concerns, face regions are detected and scrambled in the transform domain, taking into account the quality and spatial scalability features of JPEG XR. Experiments were conducted to investigate the performance of our surveillance system, considering visual distortion, bit stream overhead, and security aspects. Our results demonstrate that subband-adaptive scrambling is able to conceal privacy-sensitive face regions with a feasible level of protection. In addition, our results show that subband-adaptive scrambling of face regions outperforms subband-adaptive scrambling of frames in terms of coding efficiency, except when low video bit rates are in use. [ABSTRACT FROM AUTHOR]

To achieve superior performance, rate-distortion optimized motion estimation (ME) for variable block size (RDO-VBSME) is often used in state-of-the-art video coding systems such as the H.264 JM software. However, the complexity of RDO-VBSME is very high both for software and hardware implementations. In this paper, we propose a hardware-friendly ME algorithm called RDOMFS with a novel hardware-friendly rate-distortion (RD)-like cost function, and a hardware-friendly modified motion vector predictor. Simulation results suggest that the proposed RDOMFS can achieve essentially the same RD performance as RDO-VBSME in JM. We also propose a matching hardware architecture with a novel Smart Snake Scanning order which can achieve very high data re-use ratio and data throughout. It is also reconfigurable because it can achieve variable data re-use ratio and can process variable frame size. The design is implemented with TSMC 0.18 \mum CMOS technology and costs 103 k gates. At a clock frequency of 63 MHz, the architecture achieves real-time 1920\,\times\,1080 RDO-VBSME at 30 frames/s. At a maximum clock frequency of 250 MHz, it can process 4096\,\times\,2160 at 30 frames/s. [ABSTRACT FROM AUTHOR]

Motion estimation (ME) is one of the most time-consuming parts in video coding. The use of multiple partition sizes in H.264/AVC makes it even more complicated when compared to ME in conventional video coding standards. It is important to develop fast and effective sub-pixel ME algorithms since: 1) the computation overhead by sub-pixel ME has become relatively significant while the complexity of integer-pixel search has been greatly reduced by fast algorithms, and 2) reducing sub-pixel search points can greatly save the computation for sub-pixel interpolation. In this letter, a novel fast sub-pixel ME algorithm is proposed which performs a “rough” sub-pixel search before the partition selection, and performs a “precise” sub-pixel search for the best partition. By reducing the searching load for the large number of non-best partitions, the computation complexity for sub-pixel search can be greatly decreased. Experimental results show that our method can reduce the sub-pixel search points by more than 50% compared to existing fast sub-pixel ME methods with negligible quality degradation. [ABSTRACT FROM AUTHOR]

Belief propagation based algorithms perform best in disparity estimation but suffer from high computational complexity and storage, especially in message passing. This paper proposes an efficient architecture design with three techniques to solve the problems. For the memory storage, we propose the spinning-message and the sliding-bipartite node plane that can reduce memory cost to 1.2% for image-scale algorithms and 23.4% for block-scale algorithms, when compared to the traditional approach. For the logic complexity, we propose a buffer-free processing element architecture that has 3.6 times hardware efficiency of the previous work. The three proposed techniques could be applied to various belief propagation based algorithms to save significant hardware cost as well as approach real-time speed. [ABSTRACT FROM PUBLISHER]

This paper proposes a motion estimation scheme to reduce the computational complexity of multilayer motion estimation for scalable video coding. Based on the result of the motion estimation of the lower resolution layer referred to as base layer, we developed a new approach for exploring the search range of the enhancement layer with high coding efficiency. This approach is based on the activity defined as the absolute difference between the motion vector predictor and the final motion vector. Based on the correlation of the activities between neighboring layers, an inter-layer activity model was developed using a curve-fitted linear equation to exploit the activity in the base layer for deciding the search center and the search range of the enhancement layer. Each activity pair in the neighboring layers is used to associate the relevant macroblock to one of two groups; boundary region and interior region. The base-layer motion vector predictor is basically selected over all the activity regions; for each activity region, the proposed motion estimation algorithm decides whether to include the median motion vector predictor or not. Minimal sufficient search range is also decided from the inter-layer activity prediction factor that is adjusted to the given sequence. The proposed scheme reduced the execution time of motion estimation by 99.26% at the cost of 1.56% bit-rate increase and 0.048 dB peak signal-to-noise ratio (PSNR) decrease on average compared with the conventional full-search algorithm. The fast full-search block matching algorithm can also be incorporated to obtain the extra CPU time reduction in the motion estimation process. By adopting the fast full-search block matching algorithm (FFSBMA) in JSVM reference software, the CPU time was reduced by up to 91.84% and the memory bandwidth was reduced by 90% at the sacrifice of 1.27% bit-rate increase and 0.041 dB PSNR decrease on average compared with the FFSBMA only. [ABSTRACT FROM PUBLISHER]

In this paper, a new computation-control motion estimation (CCME) method is proposed which can perform motion estimation (ME) adaptively under different computation or power budgets while keeping high coding performance. We first propose a new class-based method to measure the macroblock (MB) importance where MBs are classified into different classes and their importance is measured by combining their class information as well as their initial matching cost information. Based on the new MB importance measure, a complete CCME framework is then proposed to allocate computation for ME. The proposed method performs ME in a one-pass flow. Experimental results demonstrate that the proposed method can allocate computation more accurately than previous methods and, thus, has better performance under the same computation budget. [ABSTRACT FROM PUBLISHER]

This paper presents an efficient error concealment algorithm for video bitstream over error-prone channel suffering from damage. Moreover, hardware architecture design and chip implementation of the proposed error concealment algorithm are also presented. For spatial error concealment, a mode selection algorithm considering the reuse of intra mode information embedded in bitstream is developed for the adaptation of bilinear and directional interpolation. It suffers only 0.08 dB video quality drop in average but the speedup measured on a general purpose processor is up to 40 times compared with the conventional methods. It is also more suitable for low cost hardware design. For temporal error concealment, the decoded motion vectors of the neighboring blocks of the corrupted macroblock are reused to provide hints to estimate the motion vector of the corrupted macroblock. Moreover, for real-time applications, a data and computational results reuse scheme of motion vector estimation is proposed and 96% computation and memory bandwidth can be reduced compared with the conventional methods with 0.18 dB quality drop in average. With the UMC 90 nm 1P9M process, the proposed error concealment engine can process HDTV1080P 30 frames per second video data and the power consumption is 15.77 mW at 125 MHz operation frequency. [ABSTRACT FROM PUBLISHER]

The spatial-domain intra prediction scheme of H.264 has high computational complexity, especially for the High Profile as it incorporates the additional intra 8\,\times\,8 prediction mode. To address this issue, we explore the hierarchy of H.264 mode decision process in this paper and adopt an approach that is in synchrony with the mode decision hierarchy. In particular, we propose a variance-based algorithm for block size decision, an improved filter-based algorithm for prediction mode decision using contextual information, and a selection algorithm for intra block decision that exploits the relation between the rate-distortion characteristic and the best coding type. Performance comparison is provided to show the improvement of the proposed algorithms over previous methods. [ABSTRACT FROM PUBLISHER]

A prediction error prioritizing-based normalized partial distortion search algorithm for fast motion estimation is proposed in this letter. The distortion behavior of each pixel in a macroblock is first analyzed to point out the priority/order of sum of absolute difference calculation. Afterward, the normalized partial distortion search algorithm is applied for half-stop of the distortion calculation. In addition, a dynamic search range decision algorithm is adopted for automatically changing the size of the search range to further increase the motion estimation speed. The computational complexity can be reduced significantly through the proposed algorithm, though leaving a PSNR degradation that could be dismissed. [ABSTRACT FROM PUBLISHER]

The H.264/AVC achieves higher coding performance than the previous video coding standards, such as MPEG-2 and MPEG-4. In order to achieve this improved coding performance, H.264 adopts various advanced techniques including multiple reference frame motion estimation (MRF-ME), which requires very heavy encoding complexity in proportion to the number of reference frames. In this letter, we propose an efficient priority-based reference frame selection (PRFS) method to reduce the computational complexity. The PRFS method computes the priorities of all reference frames using spatial and temporal correlation of the reference frame index and motion vectors, and selects candidate reference frames to reduce the number of reference frames for each ME block. Experimental results show that the proposed method reduces the computational complexity of the MRF-ME and achieves similar coding performance to that of previous methods. [ABSTRACT FROM PUBLISHER]

In this letter, a new fast motion estimation (FME) algorithm capable of producing sub-sample motion vectors at low computational-complexity is proposed. Unlike existing FME algorithms, the proposed algorithm considers the low complexity sub-sample accuracy in designing the search pattern for FME. The proposed FME algorithm is designed in such a way that the block distortion measure is modeled as a parametric surface in the vicinity of the integer-sample motion vector; this modeling enables low computational-complexity sub-sample motion estimation (ME) without pixel interpolation. Experimental results on video test sequences show that the proposed FME algorithm reduces computational complexity of integer and sub-sample ME considerably compared with traditional methods at the cost of negligible performance degradation. [ABSTRACT FROM AUTHOR]

In this paper, an efficient mode decision algorithm and a high throughput hardware architecture with eight-pixel parallelism for improving the H.264/advanced video coding intra coding efficiency are proposed. Based on the inherent features of the discrete cosine transform, the input block is first transformed and then analyzed to determine its texture directional tendency. A few candidate modes are chosen for cost calculation, which adopts the error model in the sum of absolute integer-transformed differences (SAITD). Experimental results show that the proposed intra prediction algorithm has lower peak signal-to-noise ratio degradation and bit-rate increment compared to other recent designs. Using the SAITD technique, the proposed mode decision algorithm is effectively integrated into intra prediction rather than being a preprocessing unit. For hardware implementation, the proposed intra prediction algorithm in the macroblock level is implemented for prediction computation, mode decision, and reconstruction loop units. The synthesis results show that the proposed architecture can achieve a 100MHz operation frequency, allowing it to easily support the real-time requirements for video resolutions of up to the 16 source input format. [ABSTRACT FROM AUTHOR]

The intra mode prediction via exhaustive mode decision exploited in the H.264/advanced video coding effectively improves the coding efficiency, but at the expense of yielding higher computational complexity. In this letter, a fast intra mode decision algorithm, called the hierarchical intra mode decision (HIMD), is proposed to speed up the mode decision process by reducing the number of modes required to be checked for each macroblock. The novelty of the proposed HIMD algorithm lies at the following accounts. 1) An early decision with adaptive thresholding is developed for the mode decision of the luma component. 2) The candidate modes are selected according to their Hadamard distances and prediction directions. 3) Only one of the hierarchical paths will be chosen to compute its least rate-distortion cost. Experimental results have shown that the proposed HIMD algorithm achieves a reduction of 85.75% computational complexity on average, while incurring only 0.164 dB loss in peak signal-to-noise ratio (PSNR) and 2.336% increment on the total bit rate compared with that of exhaustive mode decision, which is a default approach set in the joint model reference software. [ABSTRACT FROM AUTHOR]

The emerging international standard for multiview video coding (MVC) is an extension of H.264/advanced video coding. In the joint mode of MVC, both motion estimation (ME) and disparity estimation (DE) are included in the encoding process. This achieves the highest coding efficiency but requires a very high computational complexity. In this letter, we propose a fast ME and DE algorithm that adaptively utilizes the interview correlation. The coding mode complexity and the motion homogeneity of a macroblock (MB) are first analyzed according to the coding modes and motion vectors from the corresponding MBs in the neighbor views, which are located by means of global disparity vector. According to the coding mode complexity and the motion homogeneity, the proposed algorithm adjusts the search strategies for different types of MBs in order to perform a precise search according to video content. Experimental results demonstrate that the proposed algorithm can save 85% computational complexity on average, with negligible loss of coding efficiency. [ABSTRACT FROM AUTHOR]

Due to its high-computational complexity and poor parallelism, the context-based adaptive binary arithmetic coder (CABAC) increasingly poses a bottleneck in the large-scale parallel video encoder like H.264 on a manycore platform. Motivated by the organization of the contexts models in CABAC, this letter presents a tri-thread parallel evolution of CABAC. The evolutional coder, which is named P3-CABAC, statically divides syntax elements into three predefined groups, each of which forms a parallel thread. Since the P3-CABAC is thread-level parallelizable and implementation-friendly for manycore processors, it presents a rational consideration for entropy coding in block-based video encoders in the manycore era. [ABSTRACT FROM AUTHOR]

A new object-based coding system for a class of dynamic image-based representations called plenoptic videos (PVs) is proposed. PVs are simplified dynamic light fields, where the videos are taken at regularly spaced locations along line segments instead of a 2-D plane. In the proposed object-based approach, objects at different depth values are segmented to improve the rendering quality. By encoding PVs at the object level, desirable functionalities such as scalability of contents, error resilience, and interactivity with an individual image-based rendering (IBR) object can be achieved. Besides supporting the coding of texture and binary shape maps for IBR objects with arbitrary shapes, the proposed system also supports the coding of grayscale alpha maps as well as depth maps (geometry information) to respectively facilitate the matting and rendering of the IBR objects. Both temporal and spatial redundancies among the streams in the PV are exploited to improve the coding performance, while avoiding excessive complexity in selective decoding of PVs to support fast rendering speed. Advanced spatial/temporal prediction methods such as global disparity-compensated prediction, as well as direct prediction and its extensions are developed. The bit allocation and rate control scheme employing a new convex optimization-based approach are also introduced. Experimental results show that considerable improvements in coding performance are obtained for both synthetic and real scenes, while supporting the stated object-based functionalities. [ABSTRACT FROM AUTHOR]

The newest video coding standard called scalable video coding (SVC) provides broad applications in multimedia communications. SVC encoder consumes great computational complexity when compared to previous video coding standards. This paper presents a fast mode decision algorithm that speeds up the SVC encoding process through probabilistic analysis. The mode of the enhancement layer is first predicted by statistical analysis. Afterward, Bayesian theorem is utilized to detect whether the prediction mode of the current macroblock is the best or not. The mode is further predicted and refined by the Markov process. Experimental results show that the proposed algorithm significantly reduces computational complexity with negligible peak signal-to-noise ratio degradation and bitrate increase in the enhancement layers. [ABSTRACT FROM AUTHOR]

A video-based monitoring system must be capable of continuous operation under various weather and illumination conditions. Moreover, background subtraction is a very important part of surveillance applications for successful segmentation of objects from video sequences, and the accuracy, computational complexity, and memory requirements of the initial background extraction are crucial in any background subtraction method. This paper proposes an algorithm to extract initial color backgrounds from surveillance videos using a probability-based background extraction algorithm. With the proposed algorithm, the initial background can be extracted accurately and quickly, while using relatively little memory. The intrusive objects can then be segmented quickly and correctly by a robust object segmentation algorithm. The segmentation algorithm analyzes the threshold values of the background subtraction from the prior frame to obtain good quality while minimizing execution time and maximizing detection accuracy. The color background images can be extracted efficiently and quickly from color image sequences and updated in real time to overcome any variation in illumination conditions. Experimental results for various environmental sequences and a quantitative evaluation are provided to demonstrate the robustness, accuracy, effectiveness, and memory economy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Real-time multiuser multimedia applications, such as surveillance or monitoring using multiple cameras, have recently started to be deployed over flexible and low-cost multihop wireless networks. In such multimedia systems, the various sources (cameras) share the limited network resources and collaboratively forward the captured video streams to a remote central monitor. However, existing resource allocation schemes often ignore the dynamic application-layer video and network characteristics by focusing on the steady-state or worstcase operating conditions. This may result in inefficient allocation of the network resources. In this paper, we focus on determining whether the resource allocation for wireless video surveillance systems should be performed based on steady-state or worstcase operating conditions, or whether perpetual adaptation to the dynamically changing source and network conditions is desirable. We analyze three different types of solutions that have different information requirements: a centralized optimization approach, a decentralized game-theoretic approach (which guarantees a stable allocation), and a distributed greedy approach (which perpetually adapts allocation based on the local information exchanged among the neighboring nodes). We compare these three approaches using the following four metrics: 1) the total video quality; 2) the computational complexity; 3) the required control information overhead; and 4) the timely adaptation to the network and source variation. We show that in a static network, the game theoretic resource allocation is only better than the distributed greedy approach when the network transmission rates are high. In a dynamic network, the distributed greedy approach can outperform the other two approaches significantly in terms of video quality (peak signal-to-noise ratio). This shows that resource allocation solutions for multicamera wireless surveillance networks need to explicitly consider both the dynamic source characteristics and network conditions, rather than always relying on stable, but predetermined, allocations. [ABSTRACT FROM AUTHOR]

A depth image-based error concealment algorithm for 3-D video transmission is proposed, which utilizes the strong correlations between 2-D video and its corresponding the depth map. We first investigate the internal characteristics of the macroblock in the depth map, and then take advantage of these characteristics to recover accurately the lost motion vector for the corrupted blocks, with the joint consideration of the neighbor information and the corresponding depth. Experimental results show that the proposed method provides significant improvements in terms of both objective and subjective evaluations. [ABSTRACT FROM AUTHOR]

One objective in MPEG-2 to H.264/advanced video coding transcoding is to improve the H.264/AVC compression ratio by using more advanced macroblock encoding modes. The motion re-estimation process is by far the most time consuming process in this type of video transcoding. In this paper, we present an efficient H.264/AVC block size partitioning prediction algorithm for MPEG-2 to H.264/AVC transcoding applications. Our algorithm uses rate-distortion optimization techniques and predicted initial motion vectors to estimate block size partitioning. It is also shown that using block size partitioning smaller than 8 × 8 (i.e., 8 × 4, 4 × 8, and 4 × 4) results in negligible compression improvements, and thus these sizes should be avoided in transcoding. Experimental results show that, compared to the state-of-the-art transcoding scheme, our transcoder yields similar rate-distortion performance, while the computational complexity is significantly reduced, requiring an average of 29% of the computations. Compared to the full-search scheme, our proposed algorithm reduces the computational complexity by about 99.47% for standard-definition television sequences and 98.66% for common intermediate format sequences. Compared to UMHexagonS, the fast motion estimation algorithm used in H.264/AVC, the experimental results show that our proposed algorithm is a better trade-off between computational complexity and picture quality. [ABSTRACT FROM AUTHOR]