# Enhanced Logarithmic Search Technique for Motion Estimation with Three Step Reduction

Pranob K Charles ? , Dr. Habibulla Khan ? & Dr. K.S. Rao ? Abstract-Video compression is the one which has highest demand in the area of video processing. Motion estimation (ME) is the basic of Video compression. There are several algorithms to estimate the motion estimation of current block in reference frame. In the view of this a new novel technique has been proposed in namely Logarithmic Search with Three Step Reduction (LSTSR) which is computationally more efficient than many of the existing techniques. Simulation result shows that it performs better than that of Three Steps Search (TSS), New Three Step Search (NTSS) and reduces the checking points by almost 50% than that of TSS.


# I. introduction

ideo Processing has a lot of demand now a days as because lot of videos are to be transferred here and there especially when comes to the mobile communication. As video requires much more space to store than still image, video compression is very much useful in reducing the storage space and which will eventually lead to lesser cost. The main concept in video compression is to predict the future position of the current block by taking the reference of either past frame or future. The maximum displacement of an object from one frame to another is given by the coordinate of that position called motion vector (MV). The process by which we find out the best matching block in reference frame corresponding to each macro block of current frame is called motion estimation (ME). As video contains both spatial and temporal redundancy, we need to use Hybrid codec to reduce them. In hybrid codec, we predict the video and when we subtract it from input video, we get the residual error. Now if we encode this residual signal and pass it to decoder, we need not to encode each frame separately. This will require lesser bits to encode the video.

In the encoder side, the motion estimator compares the stored frame to that of incoming frame to find the MV. The motion compensator uses both the sored frame and MV to predict what the position of the current block will be. Then with the help of predicted video and encoded residual signal, the decoder produces the compensated frame of the current frame.


# II.


# Previous Work

For motion estimation we need to search for the best match in the reference frame which will give us the best MV. The search is done in many ways and depending upon the search pattern, in different techniques the complexity, time and PSNR values per macro block varies. The first and foremost technique was to search each point of search area for best match. This is called Full Search (FS) [14]. This has very high computation per macro block and also has high PSNR value. We can consider the result as optimal one. Due to high computational complexity, many Block based fast motion estimation techniques are implemented and few of them are Three Step Search (TSS) [21], New Three

Step Search (NTSS) [3], Diamond Search (DS) [6], 2 Dimensional Logarithmic Search (2DLS) [16] and Cross Search (CS) [2]. According research and experiment, it is seen that TSS checks an avg. of 25 points, NTSS checks an avg. of 17 to 33 points, DS checks an avg. of 13 points and 2 DLS takes avg. of 13 to 17 checking points per macro block. More and more techniques are being developed to reduce the computational complexity as well as increase the PSNR value of compensated image.

In this paper, a new algorithm is proposed named as Logarithmic Search with Reduced Three Step Reduction (LSTSR). This technique is applied on various video sequences and results are compared with already existing techniques in terms of search points required and PSNR values. In this paper section III defines the types of predictions used, Section IV explains the Block Matching Algorithm (BMA) concepts and matching criteria, section V defines the proposed method, section VI defines the Experimental Setup and Results Section VII gives Analysis of RTSLS followed by comparison, conclusion and references.


# III.


# Types of Estimation

We can estimate the best matching position of current block in the reference frame by using both past frame and future frame as a reference. If we use the past frame to predict the future position of the current block, we refer it as forward prediction and as we need to move back in time, so it is also called backward motion estimation. On the other hand if we use the future frame as a reference to predict the past, it is V called backward prediction and which is also known as forward motion estimation.


# IV. BMA and Matching Criteria

Matching of two macro blocks has to be done in different frames to compute the displacement. The matching can be done in pixel to pixel basis or block by block basis. However Pixel by pixel matching is time consuming as it needs more computations. So we match the center pixel along with its neighbor pixels. For that we divide the frame into blocks of size 8x8 or 16x16 and matching is done between corresponding blocks of current frame and reference frame. This process is called block matching and the algorithm is called block matching algorithm (BMA).

We used the matching criteria between two blocks as Mean Absolute Difference (MAD)

The performance measure used here is PSNR which is known as peak signal to noise ratio and calculated as: PSNR= 10 log 10 (2552 /MSE) For performance comparison PSNR difference is also calculated. It is defined as the difference in PSNR of the proposed algorithm with respect to FS algorithm. Within a video codec it is also advisable to calculate bit rate at different quantization parameters for the ratedistortion (bit rate versus PSNR) comparison.

V.


# Proposed Algorithm

Many techniques have been proposed to compute motion estimation in lieu of reducing number of computations, reduction in search points which are required per each macro block. We have seen the technique named as "Three step search" which searches for best matching macro blocks and continues for three steps only. The quality of the techniques is judged by the number of search points required and the PSNR ratios along with the quality of the compensated image. If we want to reduce the number of search points there are chances of low quality compensated image. Those techniques which give better compensated image but they require relatively higher number of search points.

Here we have proposed one algorithm which is computationally more efficient than earlier Three Step Search algorithm and few other already existing block matching algorithms.


# a) Logarithmic Search with Three Step Reduction (LSTSR)

It is because this search technique completes in three steps it can be called as three step search. However we reduced these steps and thereby calling this as reduced Three Step Search and mainly we have reduced the number of search points and is further called as logarithmic search because each time, step size is reduced by 2 i.e. logarithmically. For the searching purpose, we define the search range as +7 and we consider the block size of mxn. The steps are: i. We place the candidate block at the center of the reference frame and within the search range we start searching with initial step size 4. In 1st step we search 5 points including one center and 4 points at the end of a plus '+' for minimum cost.

The point with minimum cost will become the center of the next search step and we reduce the step size by 2.


# Fig.1: Search pattern in LSTSR

ii. Now we again start searching points at the ends of plus '+' with step size 2 for minimum cost. We don't calculate cost at those points at which cost is already calculated in last step. So we need to check only 4 points. We again shift the center to the point with minimum cost and reduce the step size to 1.

iii. This is the last step and we again search in similar fashion with step size 1 around the center. We again have to calculate cost at only 4 points for minimum cost and the point with minimum cost will be our required position and it will give us the final motion vector.

In the above mentioned algorithm the number of search points required per macro block is 5+4+4=13.


# VI.


# Experimental Setup

In our experiment we have taken the mean absolute difference (MAD) as a measure of matching criteria. We have implemented the techniques by taking both macro block size of 16x16 and 8x8.The maximum displacement in search area is taken as +7 and the search area as (2x7+1)*(2x7+1)=225.The simulation is performed on different sequences with different frame length as listed in table 5.1. The results and outputs are obtained as Average no. of searching points required


# Global Journal of Computer Science and Technology

Volume XVII Issue I Version I per macro block, the PSNR ratios. The various results obtained from experiment are discussed below.    obtained the compensated image and resulted motion vector using backward prediction method.

computations per macro blocks but still it retains similar quality of the compensated image with that of TSS and NTSS.

RTSLS: This is a modification of both TSS and NTSS.   


# Conclusion

Based on the TSS algorithm and 2 DLS, we have proposed Logarithmic Search with Three Step Reduction (LSTSR). From the results obtained in simulation using different techniques on 'missa' video sequence with mbSize 16x16, it is observed that the RTSLS is consuming almost 50% of the computations than that of TSS and 60% of computations than that taken by NTSS. From fig. 9, it can be seen that though LSTSR checks at much lesser no. of points still retained its PSNR values and they are almost similar than that of TSS and NTSS. So the quality of the compensated image is similar as produced by other two. It can be concluded that LSTSR is the most efficient among the discussed techniques.

IX.
23![Fig.2: Video used for experiment "SampleVideo.avi" Experimental Results: a) Comparison between compensated image obtained using mbsize of 8x8 vs 16x16](image-2.png "Fig. 2 :Fig. 3 :")
45![Fig.4: Forward prediction using 16x16 mbSizeIn the above figures, the compensated images are obtained using macro blocks of size 8x8 and 16x16. The fig.3is obtained when we used macro block of size 8x8 so a total of 20134 computations are needed. In fig.4is obtained by using 16x16 size macro block where the total of 4910 computations is required.](image-3.png "Fig. 4 :Fig 5 :")
67![Fig 6: Backward prediction using mbSize of 16x16 In the fig 5, we obtained the compensated image by using forward prediction and in fig.6, we](image-4.png "Fig 6 :Fig. 7 :F")
8![Fig.8: Average number of computations per macro block of 'missa' sequence](image-5.png "Fig. 8 :")
9![Fig.9: PSNR values per macro block of 'missa' sequence of different techniques VIII.](image-6.png "Fig. 9 :")
1
2
			Year 2017 ( ) © 20 7 Global Journa ls Inc. (US) 1
			© 2017 Global Journals Inc. (US)
		
		

			

## Acknowledgement

The author would like to thank Dr. Habibulla Khan and Dr. K. S. Rao for their valuable suggestions and thorough checking the paper with necessary enhancements incorporated where ever required.

			

			

				


* 
	
		An efficient block matching algorithm for motion compensated coding
		
			HMPuri
		
		
			DLHang
		
		
			Schilling
		
	
	
		Proc IEEE Int. Conf. Acoust., Speech, and Signal Proc
				IEEE Int. Conf. Acoust., Speech, and Signal
		
			1987
			
		
	




* 
	
		The cross search algorithm for motion estimation
		
			MGhanbari
		
	
	
		IEEE Trans. Commun
		
			
			Jul. 1990
		
	
	COM-38




* 
	
		A new three step search algorithm for block motion estimation
		
			RLi
		
		
			BZeng
		
		
			MLLiou
		
	
	
		IEEE Trans. On Circuits and Systems for Video Technology
		
			4
			4
			
			Aug. 1994
		
	




* 
	
		A novel four-step search algorithm for fast block motion estimation
		
			LMPo
		
		
			WCMa
		
	
	
		IEEE Trans. on Circuits and Systems for Video Technology
		
			6
			3
			
			Jun. 1996
		
	




* 
	
		A block based gradient descent search algorithm for block motion estimation in video coding
		
			Lurng-KuoLiu
		
		
			EphraimFeig
		
	
	
		IEEE Trans. on Circuits and Systems for Video Technology
		
			6
			4
			
			Aug. 1996
		
	




* 
	
		A new diamond search algorithm for fast block matching motion estimation
		
			SZhu
		
		
			KKMa
		
	
	
		IEEE Trans. Image Processing
		
			9
			2
			
			Feb. 2000
		
	




* 
	
		Efficient region-based motion estimation and symmetry oriented segmentation for image sequence coding
		
			PCicconi
		
		
			HNicolas
		
	
	
		IEEE Trans. on Circuits and Systems for Video Technology
		
			4
			3
			
			Jun. 1994
		
	




* 
	
		Video Coding, An Introduction to Standard Codecs, London: The Institute of Electrical Engineers
		
			MGhanbari
		
		
			1999. Ch.2, 5, 6, 7 & 8
		
	




* 
	
		A Simple and Efficent Search Algorithm for Block-Matching Motion Estimation
		
			JianhuaLu
		
		
			MingLLiou
		
	
	
		IEEE Trans. Circuits And Systems For Video Technology
		
			7
			2
			
			April 1997
		
	




* 
	
		Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation
		
			YaoNie
		
		
			Kai-KuangMa
		
	
	
		IEEE Trans. Image Processing
		
			11
			12
			
			December 2002
		
	




* 
	
		A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation
		
			Chun-HoCheung
		
		
			Lai-ManPo
		
	
	
		IEEE Trans. Circuits And Systems For Video Technology
		
			12
			12
			
			December 2002
		
	




* 
	
		A New Cross-Diamond Search Algorithm for Fast Block Matching Motion Estimation
		
			CWLam
		
		
			LMPo
		
		
			CHCheung
		
	
	
		Proceeding of 2003 IEEE International Conference on NNSP
				eeding of 2003 IEEE International Conference on NNSPNanjing, China
		
			Dec 2003