Combining Multiple-candidate Search With One-bit Transform For Motion Estimation
Motion estimation using one-bit information (1BT) to represent a pixel or a group of pixels becomes popular in recently years [1-2] as the distortion function between the reference block and the search block can be computed very efficiently. In [1], each frame is filtered and compared with the original frame to extract the edge information. However, its performance is not good enough as it degrades the predicted image by 1dB on the average comparing with full search. In this paper, we improve the performance using the results of one-bit transform as the initial estimation of the motion vector, and use re-examination strategies to find the final motion vector. Experiment results show that the proposed method improves the performance of the one-bit transform range up to 0.9 dB and it outperforms other motion estimation algorithms such as the Three-Step Search (3SS), New Three-Step Search (N3SS) and the Four-Step Search (4SS). 1. REVIEW OF MOTION ESTIMATION USING ONE-BIT TRASFORM For convenience, we use similar symbols in [1]. Each 8-bit frame F is filter with a 17?17 kernel K which is a bandpass filter and given by (1). The filtered frame F' is then compared with the original frame F to create a 1-bit frame G. The creation of G is formulated in (2). Sum of exclusive OR (SXOR) is used as the distance measure instead of Sum Absolute Difference (SAD). Let each block consists of N?N pixels and ui,j and vi,j denote the value of the pixel at row i and column j of block u and v respectively. The distance measure between two blocks is formulae as (3). where ? denotes the exclusive-or operation. For each reference block in a frame to be predicted, it search within a searching window to find a best match which has the least distortion from the reference block. 2. MULTIPLE CANDIDATES REEXAMINATION We observe that the performance of 1BT can be significantly improved if we re-examine the best N results from the IBT using other approach instead of using the best result. This can be explained that the 1BT limits the variation of small searching region. We propose the multiple candidates one-bit transform (M1BT) and the multiple candidates onebit tra nsform – full search (M1BTFS) approach to improve the performance of 1BT by reexamination process. The M1BT is simply to re-examine the best N results obtained from the 1BT . The M1BTFS consists of two stages . In the first stage, the distortion for the best result obtain ed from by the 1BT is first compared with a threshold. If the distortion is greater than the threshold, we examine the second best result , if the distortion is still above the threshold, we examine the next best result and so on. This stage will stop when either the distortion is below the threshold or the best N motion vectors are examined. If the minimum distortion obtained after the best N candidates are examined is still above twice of the threshold, the process proceeds to the second stage at which Full Search is employed. The threshold value is the average distortion of the last frame. 2.1. Distortion Measure To measure the distortion between the blocks, we compute the sub-sampled Sum Absolute Difference (SSAD) of the blocks. We used the checker board pattern to reduce the computational complexity by a factor of 2. Mathematically, for two blocks u and v, let uij and vij denote the intensity of a pixel in the i-th row and j-th column of u and v (3) ,