International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering
MenuISSN ONLINE(2278-8875) PRINT (2320-3765)
ISSN ONLINE(2278-8875) PRINT (2320-3765)
Christo Ananth1, A.Sujitha Nandhini2, A.Subha Shree2, S.V.Ramyaa2 and J.Princess2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering
In this paper two existing algorithms named as Cross-Diamond Search algorithm CDS and Fast Objected- Base Efficient Three Step Search algorithm are used. The cross-diamond search algorithm employs two diamond search patterns (a large and small) and a halfway-stop technique. It finds small motion vectors with fewer search points than the DS algorithm while maintaining similar or even better search quality. The efficient Three Step Search (E3SS) algorithm requires less computation and performs better in terms of PSNR. Modified objected block-base vector search algorithm (MOBS) fully utilizes the correlations existing in motion vectors to reduce the computations. Fast Objected- Base Efficient (FOBE) Three Step Search algorithm combines E3SS and MOBS. By combining these two existing algorithms CDS and MOBS, a new algorithm is proposed with reduced computational complexity without degradation in quality.
Keywords |
| Block-matching motion estimation, cross-center biased characteristic, cross-diamond search algorithm, Motion vector. |
INTRODUCTION |
| Block-matching motion estimation is the cardinal process for many motion-compensated video-coding standards [1]–[5], in which temporal redundancy between successive frames is efficiently removed. It divides frames into equally sized rectangular blocks and finds out the displacement of the best-matched block from the previous frame as the motion vector to the block in the current frame within a search window. However, the motion estimation could be very computational intensive and can consume up to 80% of computational power of the encoder if exhaustively evaluating all possible candidate blocks. Many fast block-matching algorithms (BMA) were proposed for alleviating the heavy computations consumed by the brute-force full-search algorithm (FS), such as the three-step search (3SS) [6], the new three-step search (N3SS) [7], the four-step search (4SS) [8], the block-based gradient descent search (BBGDS) [9], and the diamond search (DS) [10], [11] algorithms, etc. DS employs a diamond-shaped pattern and results in fewer search points with similar distortion performance as compared to N3SS and 4SS. Basically, DS performs block-matching just like 4SS. It rotates the square-shaped search pattern by 45 to form a diamond-shaped one and with its size kept unchanged throughout the search before the new minimum block distortion measure (BDM) reaches the center of the diamond. The merits that DS yields faster searching speed can be regarded as: 1) the diamond-shaped pattern, which tries to be having as an ideal circle-shaped coverage for considering possible directions of an investigating motion vector and 2) fewer checking points in the final converging step. we propose a novel fast BMAs called cross-diamond search (CDS) algorithm by introducing a cross-shaped search pattern (CSP) as the initial step, instead of the diamondshaped, to the DS algorithm. |
RELATED WORK |
| A. Cross-Diamond Searching Patterns |
| The DS algorithm uses a large diamond-shaped pattern (LDSP) and small diamond-shaped pattern (SDSP), as depicted in Fig. 1. As the motion vectors distribution possesses over 96% CCB characteristics in the central 5X5 DCB area, an initial CSP, as shown in Fig. 2. is proposed as the initial step to the DS algorithm, and is termed the CDS algorithm. |
| B. The CDS Algorithm |
| CDS differs from DS by: 1) performing a CCB CSP in the first step and 2) employing a halfway-stop technique for quasi- stationary or stationary candidate blocks. Below summarizes the CDS algorithm. |
STEP (I)—STARTING: |
| A minimum BDM is found from the nine search points of the CSP located at the center of search window. If the minimum BDM point occurs at the center of the CSP, the search stops. Otherwise, go to Step (ii) way to comply with the conference paper formatting requirements is to use this document as a template and simply type your text into it. |
 |
| Fig.1. shows the starting of Cross Shaped Pattern from which minimum BDM is found from the nine search points of the CSP located at the center of search window. Extended version of Large Diamond Shaped Pattern and Small Diamond Shaped Pattern are also shown diagrammatically. It is to be noted that when block distortion measure occurs at Cross Shaped Pattern center, the searching procedure stops. Or else the algorithm proceeds for Half Diamond Searching, Searching and Ending Steps. |
 |
STEP (II)—HALF-DIAMOND SEARCHING: |
| Two additional search points of the central LDSP closest to the current minimum of the central CSP are checked, i.e., two of the four candidate points located at(±1,±1) . |
| If the minimum BDM found in previous step located at the middle wing of the CSP, i.e.,( ±1,0)or (0, ±1), and the new minimum BDM found in this step still coincides with this point, the search stops. (This is called the secondstep stop, e.g., Fig. 4(b)). Otherwise, go to Step (iii). |
STEP (III)—SEARCHING: |
| A new LDSP is formed by repositioning the minimum BDM found in previous step as the center of the LDSP. If the new minimum BDM point is still at the center of the newly formed LDSP, then go to Step (iv) (Ending); otherwise, this step is repeated again. |
STEP (IV)—ENDING: |
| With the minimum BDM point in the previous step as the center, a new SDSP is formed. Identify the new minimum BDM point from the four new candidate points, which is the final solution for the motion vector. |
 |
PROPOSED METHOD |
| The Fast Objected-Base Efficient (FOBE) Three Step Search algorithm can be summarized as follows: |
| Step 1) |
| At the beginning, the outer eight points and middle five points are checked. If the minimum BDM point is found at the search window center the search will be stopped: otherwise go to step2. |
| Step 2) |
| If the minimum point is one of the outer eight points, the procedure is the same as in 3SS, otherwise go to step3. |
| Step 3) |
| If the minimum point is one of the small diamond four points, the small diamond moves its search centered to the current minimum BDM point and continues to search the other points on the small diamond until the minimum is found at the search window center. |
 |
 |
RESULTS AND DISCUSSION |
| First, CDS algorithm is applied and the results are obtained by calculating the motion vector for the video sequence selected. This is shown in Fig 6. |
 |
 |
 |
 |
 |
| The corresponding splitted frames of the video sequence is shown in Fig 7. |
References |
|