Histograms have been widely used for fast estimation of query result sizes in query optimization. In this paper, we propose a new histogram method, called the Skew-Tolerant Histogram (STHistogram) for two or three dimensional geographic data objects that are used in many real-world applications in practice. The proposed method provides a significantly enhanced accuracy in a robust manner even for the data set that has a highly skewed distribution. Our method detects hotspots present in various parts of a data set and exploits them in organizing histogram buckets. For this purpose, we first define the concept of a hotspot, and provide an algorithm that efficiently extracts hotspots from the given data set. Then, we present our histogram construction method that utilizes hotspot information. We also describe how to estimate query result sizes by using the proposed histogram. We show through extensive performance experiments that the proposed method provides better performance than other existing methods.

In this paper, a new low-complexity distortion estimation method for the H.264 rate-distortion optimized mode decision is proposed. Coding processes, such as discrete cosine transform (DCT), quantization, inverse quantization, inverse DCT, and reconstruction, are needed to compute the distortion in an H.264 encoder. To reduce these computations, we estimate the distortion using coefficients calculated in the quantization process and eliminate the inverse quantization, inverse DCT, and reconstruction processes. In the proposed method, the distortion is computed by integer operations, which is more efficient for the hardware implementation. The simulation results show that the proposed method can reduce the encoding time by about 10% with negligible degradation in the coding performance.

Next-generation mobile communication networks are supposed to provide various high capacity multimedia services to mobile users using various kinds of access networks. Among them, the WiNGS system developed by ETRI as one of 4G mobile system provides high performance RATs (Radio Access Technology) and network architecture with IP connectivity for merging them. In this paper, we propose a new link layer Selective-Repeat Automatic Repeat Request (SR-ARQ) mechanism that solves packet re-ordering problems during handovers and enhances handover performance in WiNGS system. In the proposed mechanism, we adopt an adaptive timer in the sending node in order to prevent unnecessary packet retransmission during handovers, and a delayed NAK scheme in the receiving node to prevent detection of temporal packet reordering due to handover delay. We implemented the proposed SR-ARQ mechanism in ns-2 simulator for performance evaluation. The simulation results show that the proposed SR-ARQ enhances handover performance for the WiNGS system by preventing unnecessary retransmission and reordering.

The macroblock (MB)-based adaptive interpolation filter method has been considered to be able to achieve high coding efficiency in H.264/AVC. Although the conventional cost functions have showed a good performance in terms of rate and distortion, it still leaves room for improvement. To improve coding efficiency, we introduce a new cost function which considers two bit rates, motion vector and prediction error, and reconstruction error of MB. The filter which minimizes the proposed cost function is adaptively selected per MB. Experimental results show that the adaptive interpolation filter with the proposed cost function significantly improves the coding efficiency compared to ones using conventional cost function. It leads to about a 5.19% (1 reference frame) and 5.14% (5 reference frames) bit rate reduction on average compared to H.264/AVC, respectively.

In this paper, we propose a computation reduction method for RDO mode decision in H.264/AVC. The distortion required for RDO mode decision has been shown to be equivalent to the total energy of quantization error. A statistical model of the quantization error for H.264/AVC was developed in order to approximate the distortion. In the proposed method, the reconstruction processes including quantization, inverse quantization, and inverse DCT are not needed. Simulation results demonstrate that the distortion is efficiently approximated with a quality and bit-rate comparable to conventional H.264/AVC.

The bit portion for motion-vector (MV) information becomes significant in very-low bitrate video coding as texture coding has been improved. Especially, the existing methods, such as minimum bitrate prediction (MBP)-based coding, do not work well for slow-moving video sequences, which are popular in video conferencing and videophone applications. It is because the characteristics of the video sequences are not fully exploited for the MV encoding. In this paper, we propose a new hybrid encoding scheme for MV. A new parameter called a skip rate (SR) is defined for estimating the degree of the locality for the MV difference in the proposed scheme. In addition, we suggest a joint coding with a new single codeword combined with the horizontal and vertical codewords. Either the joint coding or the MBP-based coding is determined by the SR. The simulation results show that the proposed scheme enhances the coding performance for various video sequences without additional memory.

An improved algorithm for the early detection of all-zero blocks in H.264 video encoding is proposed in this paper. Based on the theoretical analyzes for the integer transform and quantization in H.264, we derive a sufficient condition under which each quantized coefficient becomes zero. And then, a more precise sufficient condition is proposed by modifying the calculation order of the sum of absolute difference obtained in the motion estimation. The simulation results show that the proposed algorithm achieves approximately an 11%-36% computational saving without video-quality degradation, compared to the conventional method.

In this paper, a new early detection algorithm for all-zero DCT blocks in H.264 video encoding is proposed. We have analyzed the properties of the DCT and quantization in H.264. These analyses show that a great reduction in the number of calculations can be achieved by investigating the individual conditions for the frequency components of (1,1), (1,3), (3,1), and (3,3). Based on these facts, a more precise sufficient condition is proposed by modifying the calculation order of the minimum SAD. Simulation results show that the redundant DCT and Q are efficiently removed without video-quality degradation.

An improved fast full-search algorithm for motion estimation is proposed. The computational 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.

It is well known that a lot of computations are required for motion estimation in video encoding. Recently, the multilevel successive elimination algorithm (MSEA) has been proposed to reduce the computational complexity of block matching for motion estimation without degradation of estimation accuracy. In the MSEA, the block matching is hierarchically carried out and the invalid candidate block is successively eliminated. In this paper, we propose an improved MSEA based on a new efficient decision condition. The number of the calculations to eliminate the invalid block can be reduced by the new efficient decision condition in the proposed algorithm. The simulation results show that the proposed algorithm achieves about 30-40% computational saving as compared with the MSEA.

In this correspondence, we show that the number of iterations required for the convergence of the fractal image decoding algorithm can be reduced by selecting a suitable initial image. We consider fractal decoding to have two components, namely, "DC" and "AC". Our initial image is an approximation of the attractor of DC decoding, which is a good estimation of the "range-averaged" image, i.e., the image obtained by replacing all pixel intensities in a given block by the mean value of the block. From the simulation, it is demonstrated that the decoding speed is greatly improved.