A Modified 2-D Logarithmic Search Technique for Video

Abstract

Video coding is a process for representing video se-quences in a compact manner. A significant step in video coding is searching for similar segments in previous frames and use only the difference information for reconstruction thus reducing space requirement. Different search techniques including Full search and 2-D logarithmic search etc. are used in the current literature. Full search restricts its application because of its computational load. 2D logarithmic search is computationally less expensive although there are some spaces for improvement. In this paper we propose a new search technique by modifying the 2-D logarithmic search that requires less search points with insignificant loss in visual quality. Experimental results demonstrate the effectiveness of the proposed technique.

Keywords: video coding, 2-D logarithmic search.

I. INTRODUCTION

Video is a sequence of still images representing scenes in motion. A video is created by capturing a numbers of still images in a short time interval. When these still images are displayed very quickly, it represents the mo-tion of the object in the images.

Video represent the huge amount of data. In order to transfer video data from one place to another efficiently it is required to compress the size of video data. One way to compress the size of video data is video coding [1][2]. The principal goal in the design of a video-coding system is to reduce the transmission rate subject to some picture quality constraint. In transmission side, the first frame (normally called the reference frame) is transmitted as it is and the remaining frames are sent as a function of the reference frame. The frame to be sent is divided into a number of blocks and the best match for the block is looked for in the search window of the reference frame. This processing is called the search technique in video coding literature.

There exist a number of video coding techniques includ-ing MPEG-1/2/4 [2][7], H.26X [8] etc. uses search techniques like Full search [1], 2-D logarithmic search [3], Coarse-Fine-Three-Step search [4], Conjugate Di-rection search [5], and Pyramid search [6]. Each of the-se search techniques has merits and demerits in their favor. Full search finds the best match for a block as it searches all the candidate positions in the search win-dow. Full search however is computationally expensive and renders difficulty for real time implementation. Some variants exist that applies some heuristics to re-duce the candidate search points and reduce the computational complexity although compromising the image quality a bit.

2-D logarithmic search is one such search technique that reduces the search points to a subset of the search window (to be detailed in literature review) and finds the near-optimal best match with reduced computational complexity. Although computationally inexpensive it contains some redundancy in the search space. We aim to reduce this redundancy and aim to find a modified 2-D logarithmic search technique with even reduced computational load. Experimental results demonstrate that the proposed technique reduces the number of search points and thus reduces search time with insignificant sacrifice of image quality.

The paper is organized as follows. In Section II we elaborate some related works. In Section III we present our proposed search approach. Some experimental re-sults to demonstrate the effective of the proposed ap-proach is presented in Section IV. Finally Section V concludes the paper.

II. RELATED WORKS

In this section we present full search technique and the logarithmic search technique. In both cases the frame to be coded is divided into a number of non-overlapping equal size blocks of size p×q. The best match is looked for in a search window of size (2d+1)×(2d+1) in the reference frame .

Fig 1: Block matching process in video coding that uses search techniques.

A. FULL SEARCH

In Full search [1] finds the best match by inspecting all the (2d+1)×(2d+1) candidate positions within the search window. Full search procedure is brute force in nature. The advantage of Full Search is that it delivers good accuracy in searching for the best match. The disadvantage is that it involves a large amount of computation.

B. 2-D LOGARITHMIC SEARCH

Jain and Jain [3] developed a 2-D logarithmic search technique that successively reduces the search area, thus reducing the computational burden. The first step computes the similarity for five points in the search window. These five points are as follows: the central point of the search window and the four points surrounding it, with each being a midpoint between the central point and one of the four boundaries of the window. Among these five points, the one corresponding to the minimum dissimilarity is picked as the winner. In the next step, surrounding this winner, another set of five points are selected in a similar fashion to that in the first step, with the distances between the five points remaining unchanged. The exception takes place when either a central point of a set of five points or a boundary point of the search window gives a minimum dissimilarity. In these cir-cumstances, the distances between the five points need to be reduced. The procedure continues until the final step, in which a set of candidate points are located in a 3x3 2-D grid. The steps in a 2-D logarithmic search technique are presented in Fig 2.

Fig 2: The 2-D logarithmic search technique. The circle num-bered n is searched at the n-th step. The arrows indicate the points selected as the center of the search for the next pass.

The 2-D logarithmic search hits a maximum of 18 points and a minimum of 13 search points. The ad-vantage of this technique is that it successively reduces the search area, thus reducing the computational burden. One of the disadvantages is that some points are searched more than once thus leave some space for improvement. Moreover, it follows a greedy approach by selecting the minimum dissimilar point at each step thus posing a threat to follow a local minimum trend. Considering these facts we propose to modify the 2-D logarithmic search to overcome the local minimum problem and also eliminate the redundant computing as described in the following section.

III. PROPOSED SEARCH TECHNIQUE

We mainly modified the 2-D logarithmic search tech-nique to eliminate the redundancy and local minimum problem associated with it. The search technique is elaborated next under the light of 2-D logarithmic search technique.

Our