International Journal of Electrical and Computer Engineering (IJECE) Vol.
No.
February 2017, pp.
ISSN: 2088-8708.
DOI: 10.
11591/ijece.
A Three-Point Directional Search Block Matching Algorithm Paramkusam.
Laxma Reddy Department of Electronics and Communication Engineering.
MLR Institute of Technology.
India
Article Info
ABSTRACT
Article history:
This paper proposes compact directional asymmetric search patterns, which we have named as three-point directional search (TDS).
In most fast search motion estimation algorithms, a symmetric search pattern is usually set at the minimum block distortion point at each step of the search.
The design of the symmetrical pattern in these algorithms relies primarily on the assumption that the direction of convergence is equally alike in each direction with respect to the search center.
Therefore, the monotonic property of real-world video sequences is not properly used by these algorithms.
The strategy of TDS is to keep searching for the minimum block distortion point in the most probable directions, unlike the previous fast search motion estimation algorithms where all the directions are checked.
Therefore, the proposed method significantly reduces the number of search points for locating a motion vector.
Compared to conventional fast algorithms, the proposed method has the fastest search speed and most satisfactory PSNR values for all test sequences.
Received Oct 7, 2016 Revised Dec 30, 2016 Accepted Jan 14, 2017 Keyword:
Block matching algorithm Fast search algorithm Motion estimation Copyright A 2017 Institute of Advanced Engineering and Science.
All rights reserved.
Corresponding Author:
Paramkusam.
Department of Electronics and Communication Engineering.
MLR Institute of Technology.
India.
Email: adapa74@gmail.
INTRODUCTION
Motion estimation (ME) in video sequences, has been deeply analyzed by the research community, due its importance in the visual experience for a huge variety of visual tasks.
Motion estimation is an essential part in video coding process and greatly achieves significant compression by removing the temporal redundancy existing in a video sequence.
However, the intensive computation of ME is the major problem for real-time encoders.
In block based motion estimation, the current frame is divided into non-overlapping macro blocks of 16 x 16 pixels.
The ME part of video codec calculates the motion vector for each macroblock by searching best matching candidate block from the previously encoded reference frame.
Full Search (FS) is an exhaustive search algorithm and it is the simplest method to find the optimal motion vectors for each macroblock.
In it, the Sum of absolute difference (SAD) is calculated at each search point in the search area.
The SAD between a macroblock of size N yN at position .
, .
in the current frame ft and candidate block at position .
x, q .
in the reference frame ft-1 is defined in the eq .
N A1 N A1
SAD ( x , .
A Eu Eu ft ( p A i, q A .
A ft A1 ( p A x A i, q A y A .
i A0 j A0 With search range of W there will be .
W .
2 candidate blocks or search points.
So, for each motion vector the SAD function has to be evaluated .
W .
2 times.
At each search point N2 computations are required to calculate the SAD and one computation consists of one subtraction, one addition and one absolute value operations.
Thus the total computation per one motion vector is .
W .
2 y N2 y 3 operations.
Let a Journal homepage: http://iaesjournal.
com/online/index.
php/IJECE IJECE
ISSN: 2088-8708
fame size is K x L and frame rate is T fps, the amount of computation is 3TKL .
W .
2 per second.
This makes full search block matching algorithm as a very computationally intensive method.
To reduce the complexity of full-search, several fast search motion estimation algorithms have been proposed at the price of slightly impaired Peak Signal-to-Noise Ratio (PSNR) performance.
A possible classification of these fast search motion estimation algorithms into the following categories: reduction in search positions .
, predictive search .
, search pattern switching .
, .
, multi-resolution search .
and FractionalPixel Interpolation .
, .
Existing fast search motion estimation algorithms use one or a combination of these categories.
The main assumption of most fast search motion estimation algorithms is that the block distortion measure for example SAD is monotonic over the search range, implying that the SAD increases monotonically as the search position moves away from the minimum distortion point.
So, the best match point may be found by following the distortion trend without checking all search points in the search Accordingly, these fast search motion estimation algorithms employ various search patterns to reduce the number of search points, thereby speeding up the search.
The main drawback of these algorithms is that the search pattern of these algorithms is usually symmetric, and the magnitude of block matching error is not effectively used.
For most fast search motion estimation algorithms, the initial point of search is usually set at the center of the search window and the search occurs according to a symmetric pattern.
After comparison, the new center point is set at the point with the least amount of SAD, and then generates a new symmetric search pattern for the next search.
This procedure continues until the conditions of convergence are satisfied.
In block matching algorithm, the most important assumption is that the error surface is But, the structure of the symmetrical pattern assumes that the direction of convergence is equally alike in each direction with respect to the search center.
As a result, the monotonic property is not properly If the search direction can be correctly determined, the search speed will be further enhanced.
In this paper, a novel three-point directional search (TDS) algorithm is developed.
This algorithm consists of 9 possible search patterns of which eight are directional patterns and the remaining one is a compact symmetric search pattern which consists of nine search points.
The remainder of this paper is organized as follows.
In Section 2, we briefly describe the some conventional fast search motion estimation The details of the proposed TDS are given in Section 3.
Section 4 comprises a discussion of the experimental results.
Finally, conclusions are provided in Section 5.
FAST SEARCH MOTION ESTIMATION ALGORITHMS
The diamond search algorithm (DS) is proposed by S.
Zhu and K.
Ma .
It employs two search patterns as shown in Figure 1.
The first one is a coarse search with a large diamond search pattern (LDSP) to find a small area of optimal motion vector, and second one is a fine search using a small diamond search pattern (SDSP) to find the best motion vector in the located small area.
The search starts with the LDSP which is centered at the origin of the search window, and the 9 checking points of LDSP are tested.
the minimum sum of absolute difference (SAD mi.
calculated is not located at the centre position, new LDSP is formed which is centered at the SADmin point found in the search.
The search procedure is repeated until SADmin occurs at the centre point.
At any stage if SAD min occurs at centre of LDSP, the search pattern is switched to SDSP as reaching to the final search stage.
Among the five checking points in SDSP, the position yielding the SADmin provides the motion vector of the best matching block.
Generally, a circle-shaped search pattern with a uniform distribution of a minimum number of search points is desirable to achieve the fastest search speed uniformly.
The diamond shaped pattern is not close enough to a circle, which is just 900 rotation of a square.
Ce Zhu.
Xiao Lin, and Lap-Pui Chau .
propose a hexagonal search pattern (HS) to achieve substantial speed improvement over the DS algorithm with similar distortion performance.
The HS algorithm uses two search patterns, a large hexagonal pattern which is close enough to a circle and a small hexagonal pattern as shown in Figure 1.
In the first step of search, the large hexagonal pattern with seven checking points is used for coarse search.
In the second step if the SADmin is found at the centre, switch to use the small hexagonal pattern, including four checking points for the focused inner fine search.
Otherwise, the search continues around the point with SADmin using the same large hexagonal pattern.
The hexagonal search algorithm reduces the search points by improving the coarse search speed against the DS algorithm.
An enhanced hexagonal search (EHS) algorithm .
is proposed to reduce the search points further.
This EHS uses the 6-side-based fast inner search technique to improve the inner search speed against the HS .
In HS, the entire inner search points inside the large hexagon have to be evaluated, which is computationally ineffective.
The EHS algorithm only checks the most promising inner search points by exploiting the group-sum distortion information of the six checked endpoints of the large hexagon.
At first EHS starts coarse search with the large hexagonal pattern to trace a small area of optimal motion vector.
A Three Point Directional Search Block Matching Algorithm (A.
Paramkusa.
A ISSN: 2088-8708 After locating a small area in the coarse search.
EHS groups the six checked endpoints of the large hexagon as shown in Figure 2.
At each group, the group-sum distortion is calculated and then focused inner checking points nearest to the smallest distortion group will be evaluated to obtain the minimum distortion Three inner searching points nearby the smallest distortion group will be calculated in the focused inner search if the smallest distortion group is 3 or 6.
Otherwise, two inner searching points nearest to the smallest distortion group will be used in the focused inner search.
An enhanced hexagonal-based search using point-oriented inner search (EHS-POIS) is presented in .
for further reduction of the search points over EHS.
The EHS-POIS uses an efficient grouping method for the large hexagon which is based on minimizing mean internal distance (MID) for each inner point, as shown in Figure 2.
The eight inner points enclosed by large hexagon are divided into two sets by the MID First set contains a, c, e, f, g and h points and second set includes b and d points.
These points are surrounded by two or three nearest checked large hexagon points.
The normalized group distortions (NGD.
of the hexagon are calculated and the minimum NGDs in each set are found.
The two inner points related to minimum NGDs in two sets are finally evaluated to find the final motion vector.
The fine search of EHS requires 2 or 3 search points depending on the portion of inner points with smallest group distortion whereas the fine search of EHS-POIS requires only 2 search points constantly.
An enhanced hexagonal-based search using direction-oriented inner search (EHS-DOIS) .
has shown the considerable improvement over EHS-POIS by increasing the inner search speed double.
The EHS.
EHS-POIS, and EHS-DOIS algorithms use same large hexagonal search pattern for coarse search and find small hexagonal area using same procedural steps.
But, these algorithms have different prediction strategies to find the portion of inner checking points for fine search.
After finishing coarse search.
EHS-DOIS forms pseudo-points prediction pattern {A.
H} as shown in Figure 2.
The group distortions of these eight pseudo-points are calculated through six checked points of large hexagon.
Select one point in .
, b, c, d, e, f, g, .
that would be on the arrow from the center of large hexagon to the pseudo-point with minimum distortion among eight pseudo-points.
The SAD at this selected point is finally evaluated to find the final motion vector.
Figure 1.
Search patterns of DS and HS algorithms .
LDSP with 9 search points .
SDSP with 5 search points .
Large hexagonal pattern .
Small hexagonal pattern .
Figure 2.
Strategies used to predict portion of inner searches in EHS.
EHS-POIS and EHS-DOIS.
Group oriented prediction of EHS.
Point-oriented prediction of EHS-POIS.
Direction-oriented prediction of EHS-DOIS IJECE Vol.
No.
February 2017 : 230 Ae 237
IJECE
ISSN: 2088-8708
THREE-POINT DIRECTIONAL SEARCH (TDS) ALGORITHM
The TDS has been proposed to find out the motion vectors with fewer number of search points.
The strategy of TDS is to keep searching for the minimum block distortion (MBD) point in the most probable directions, unlike the previous fast search motion estimation algorithms where all the directions are checked.
As shown in Figure 3, the proposed TDS consists of 9 possible search patterns of which eight are directional patterns and the remaining one is initial search pattern.
The initial search pattern is a compact directional symmetric search pattern (Figure .
which consists of nine search points.
In the first step of the search, we follow the initial search pattern where we check eight adjacent points of the search centre in eight directions including the search centre in order to find out the most probable search direction in whose vicinity the MBD is present.
Thereafter, we continue the search using a particular search pattern from among the eight small three-point directional search patterns at each step of the search.
At any given search step, selection of a search pattern depends on the search direction of the previous search step.
Search direction is defined as the direction from the search centre to location of the MBD point.
The search centre and the MBD point are unique at each step of the search.
While the search continues, if the MBD is found in the centre at any search step, the search ceases and that search centre is the required motion vector.
There are eight directional search patterns corresponding to the eight possible directions.
Once the search direction is obtained, three additional search points according to the search direction .
he red diamonds in each directional search pattern as shown in Figure 3 are selected for the next step as follows:
Let the search centre and the MBD point in a given search step be denoted by ASA and AMA The straight line from ASA toward AMA indicates the search direction.
Extend the line SM in the search direction and select the search point which is closest to the MBD point on the extended line.
Let this search point be denoted by a as shown in Figure 3.
The remaining two points ABA and ACA (Figure .
are selected in such a way that the lines MB and MC are at angles A/4 and - A/4 with respect to MA.
The search procedure with TDS is summarized as follows.
Step .
The initial compact directional symmetric search pattern (Figure .
is centered at the origin of the search window.
Step .
The block distortions are calculated at nine search points of the compact directional symmetric search pattern.
If the location of the MBD occurs at the center, the search comes to an end and the search centre is considered as the motion vector.
Otherwise, proceed to step 3.
Step .
Set the location of the MBD as the new center, find the search direction, and select the proper search pattern for the next step according to the search direction.
Step .
Three additional search points .
he red diamonds in Figure .
are checked basing on the selected pattern.
If the location of the MBD remains unchanged, the search discontinues, and the motion vector is set at the location of the MBD.
If not, return to step 3.
An example of a search procedure by the TDS to locate the motion vector .
, -.
is shown in Figure 5.
Figure 3.
Search patterns of TDS.
Right pattern .
Up-right pattern .
Up pattern .
Up-left pattern .
Left pattern .
Down-left pattern .
Down pattern .
Down - right pattern A Three Point Directional Search Block Matching Algorithm (A.
Paramkusa.
A ISSN: 2088-8708 Figure 4.
The initial search pattern of the TDS Figure 5.
An example of a search procedure by the TDS to locate the motion vector .
, -.
Each candidate is marked with its step number, within which only one is the minimum BDM point .
illed by red colo.
EXPERIMENTAL RESULTS
To evaluate the performance of the proposed method, eleven video sequences which consist of different types of motion content and various formats including QCIF.
CIF, and HD are used.
The luminance components of the first 100 frames of these video sequences are considered in the simulation.
The block size is set to 16 y 16 and the search range to A63 for high definition video sequences (Kirsten-Sara.
Rocket launch and Football sequence.
and A15 for the remaining video sequences.
The SAD is used as the error measurement for finding the motion vector.
The Full-Search algorithm achieves the highest PSNR as it searches all possible search points in the search window and thus is guaranteed to find global minimum point.
So, the PSNR achieved by Full-Search algorithm is used as reference to compare or evaluate other fast block matching algorithms.
In fact, it is not possible to ground the quality of the results by excluding Full-Search algorithm.
The simulation results with proposed TDS algorithm are contrasted with those of other algorithms in two aspects, which are: .
The average search points per block and .
The average peak signal-to-noise ratio (PSNR) per frame.
The results pertaining to the speed performance .
, the average search points per bloc.
of all the fast block matching algorithms including the proposed TDS algorithm are summarized in Table 1.
From Table 1, it is clear that the number of search points can be reduced more by applying TDS algorithm than any other state-of-the-art fast block matching algorithms.
In other words, the TDS may find any motion vector in motion field with fewer search points than any other state-of-the-art fast block matching algorithms.
The results pertaining to the motion prediction quality .
, the average PSNR per fram.
of all the fast block matching algorithms including the proposed TDS algorithm are shown in Table 2.
It can be observed from Table 2 that the average PSNRs obtained by TDS are better than those of DS.
HS.
EHS.
EHSPOIS.
EHS-DOIS and DGDS algorithms in many cases.
The total average PSNR of the TDS is better by 24dB, 0.
52dB, 0.
64dB, 0.
51dB, 1.
29dB and 0.
15dB when compared to the total average PSNRs of the algorithms of DS.
HS.
EHS.
EHS-POIS.
EHS-DOIS and DGDS respectively.
The proposed TDS is better than DS algorithm with respect to the average PSNR per frame with least computational cost.
The PSNR performance of TDS is either approximately equal to that of DGDS or In a few cases, the PSNR performance is less which is insignificant.
However, the number of average search points per block has greatly reduced in the TDS when compared to this algorithm.
Coming to the HS algorithm, the proposed TDS shows better PSNR performance as well as speed When compared to the enhanced versions of HS i.
EHS.
EHS-POIS and EHS-DOIS algorithms, the TDS shows noticeable speed improvement against these algorithms.
However, the average PSNR per frame has greatly reduced in the TDS when compared to these algorithms.
IJECE Vol.
No.
February 2017 : 230 Ae 237
IJECE
ISSN: 2088-8708
Table 1.
Average Search Points per Block
Video
TDS
Foreman Mobile Rhinos Robot boat
Suzie Akiyo
Cricket
Flower
Kirsten-Sara
Rocket launch
Football Total Average Fast search motion estimation algorithms EHS
EHS-POIS
EHS-DOIS
DGDS
Full-search
DGDS
Full-search Table 2.
Average PSNR per Frame
Video
TDS
Foreman Mobile Rhinos Robot boat
Suzie Akiyo
Cricket
Flower
Kirsten-Sara
Rocket launch
Football Total Average Fast search motion estimation algorithms EHS
EHS-POIS
EHS-DOIS
To figure out the efficiency of proposed TDS algorithm more garishly, the average PSNR per frame and the average search points per block of all the fast block matching algorithms including the proposed TDS algorithm using Foreman and Football video sequences have been plotted in Figure 6 and Figure 7 Figure 6.
and Figure 7.
plot a frame-by-frame comparison of the average search points per block for the proposed TDS algorithm and fast block matching algorithms applied to the Foreman and Football video sequences respectively.
Figure 6.
and Figure 7.
plot a frame-by-frame comparison of average PSNR for the proposed TDS and fast block matching algorithms applied to the Foreman and Football video sequences respectively.
Figure 6.
and Figure 7.
clearly show the supremacy of the proposed TDS against DS.
HS.
EHS.
EHS-POIS.
EHS-DOIS and DGDS algorithms in terms of the average search points per block, while Figure 6.
manifest that the PSNR performance of the proposed TDS is closer to that of Full-Search like DS and DGDS algorithms and better than that of the enhanced versions of HS i.
EHS.
EHS-POIS and EHS-DOIS algorithms.
Figure 6.
Performance comparison of the fast block matching algorithms for AuForemanAy sequence in terms of: .
the average number of search points per block and .
average PSNR per frame A Three Point Directional Search Block Matching Algorithm (A.
Paramkusa.
A ISSN: 2088-8708 .
Figure 7.
Performance comparison of the fast block matching algorithms for AuFootballAy sequence in terms of:
the average number of search points per block and .
average PSNR per frame
CONCLUSION
In this paper, we have proposed a novel three-point directional search (TDS) for motion estimation in video coding.
We explored the relationship between search direction and search patterns.
With a known search direction, asymmetric search patterns are developed, and the search points on the outside of the direction were disregarded.
Since the unnecessary search points are eliminated, the search speed is greatly The experimental results have demonstrated the superiority of our proposed method.
REFERENCES