8 locations +/- S pixels around location (0,0) Pick among the 9 locations searched, the one with minimum cost function If the minimum weight is found at center for search window: Set the new step size as S = S/2 (that is S = 1) Repeat the search procedure from steps 3 to 4 Select location with the least weight as motion vector If the minimum weight is found at one of the 8 locations other than the center: Set the new origin to this location Fix the step size as S = 2 Repeat the search procedure from steps 3 to 4. Depending on location of new origin, search through 5 locations or 3 locations Select the location with the least weight If the least weight location is at the center of new window go to step 5, else go to step 6 Diamond Search Diamond Search (DS) algorithm uses a diamond search point pattern and the algorithm runs exactly the same as 4SS. However, there is no limit on the number of steps that the algorithm can take. Two different types of fixed patterns are used for search, Large Diamond Search Pattern (LDSP) Small Diamond Search Pattern (SDSP) The algorithm runs as follows: LDSP: Start with search location at center Set step size S = 2 Search 8 locations pixels (X,Y) such that (|X|+|Y|=S) around location (0,0) using a diamond search point pattern Pick among the 9 locations searched, the one with minimum cost function If the minimum weight is found at center for search window, go to SDSP step If the minimum weight is found at one of the 8 locations other than the center, set the new origin to this location Repeat LDSP SDSP: Set the new search origin Set the new step size as S = S/2 (that is S = 1) Repeat the search procedure to find location with least weight Select location with the least weight as motion vector This algorithm finds the global minimum very accurately as the search pattern is neither too big nor too small. Diamond Search algorithm has a peak signal-to-noise ratio close to that of Exhaustive Search with significantly less computational expense. Adaptive Rood Pattern Search Adaptive rood pattern search (ARPS) algorithm makes use of the fact that the general motion in a frame is usually coherent, i.e. if the macro blocks around the current macro block moved