1 Introduction

Block based motion estimation (ME) has been implemented in most of the existing video coding (Barjatya 2004) criterions (Bergen et al. 1992). It reduces the temporal redundancy among frames. This is generally realized by permitting blocks from presently coded frames to be coordinated with ones from reference frames. Whole image or some portions of it are allied with Motion Vector (MV), which can characterize by a translational version to estimate the motion of actual cameras. The image categorizations forms the video, the video is functioned on the perception of compensation and ME. Block matching algorithms (BMA) (Schäffter et al. 1999) is depending on rectangular blocks and MV is formed for each block. It also comprises all Pixels inside each blocks has same motion, BMAs (Tanter et al. 2002) are also engaged for hardware consciousness because of its uniformity and easiness. The H.264/AVC standard has progressed video coding in the last few years and is the latest authorized and industrialized by ITU and ISO. H.264/AVC delivers up-to-date novelties in video compression techniques to deliver robust video quality with less bit rate per frame and save bit rate associated to other preceding standard methods (Nie and Ma 2002). It also used for many applications such as HD video, video conferencing, streaming, broadcasting, multimedia tools etc. different tools are used to realize high compression gain in H.264/AVC (Zhu and Ma 2000). Consequently, to advance coding performance, the computational complexity of the encoding method also amplified (Cheung and Po 2002). The most recognized developed BMA are fast in their speed namely DS algorithm, CDS algorithm, MCHDS algorithm and NCDS algorithm. In the last decade, many BMAs have been inspired by the characteristics of MV distribution. The DS is highly center-biased and works on two types namely diamond shaped search and highly unrestricted step search. It resolves the local minima. Further, it is classified into SDSP (Small Diamond Search Pattern) and LDSP (Large Diamond Search Pattern). A good wireless multimedia sensor network must be energy efficient (Priyadarshi et al. 2018a, b, c) for the opportunity of functioning in severe situation and absence of maintenance. There are also innumerable BMAs like Predictive BMA for Wireless Video Sensor (Priyadarshi et al. 2018d, e, 2019) is a way to considerably decline the computational intricacy of ME. Therefore, in the field of video stream transmission for wireless multimedia sensor networks, an energy-efficient BMA is of high importance.

2 Related work

2.1 Diamond search (DS) algorithm

As the name implies, DS algorithm takes nine points formed in a diamond shape. It has corner as well as edges point which force to use low frequency resulting in large delay. This algorithm uses an unobstructed center biased searching development. The DS uses LDSP and SDSP (Zhu and Ma 2000). As diamond search algorithm uses nine points, it calculates minimum block distortion measure (BDM) between reference frame and current frame. If smallest search point is occurring at edges then process will continue with large diamond shape. If smallest BDM point is coming at center then DS pattern uses small diamond shape, which consists of five search points. Again, if smallest BDM point is coming at center then process will be stopped otherwise it will continue from step 2.

2.2 Cross diamond search (CDS) algorithm

CDS Algorithm uses less search points than three step search and DS (Cheung and Po 2002). The CDS algorithm divides into two types based on their search point. One is small cross search pattern (SCSP) and another is large cross search pattern (LCSP). It has a cross shaped pattern having nine points as large DS and five points as SDSP. It will calculate the smallest BDM point. If smallest BDM point is lying on vertex, then it will create another large cross search pattern. If smallest BDM point is at centre (0, 0) then it will create a small search pattern and calculates smallest BDM point. If it is lying again on the centre then process will get stopped else it goes to step 4. If it is not occurring at centre then the process will continue. The final minimum BDM value will give the motion vector value.

2.3 Modified cross hexagon diamond search (MCHDS) algorithm

This algorithm uses hybrid architecture consisting of symmetric cross pattern with step size of 2, modified asymmetric hexagon with step size of 1 and SDSP with step size of 1. Initially, symmetric cross search pattern with step size of 2 has to be used. In that we have to find the MAD value. If the Mean absolute difference (MAD) value is at centre then go to step 3, else go to the step 2. After getting the MAD value other than the centre of symmetric cross pattern, take that point as centre and form a modified asymmetric hexagon with step size of 1 and get the MAD value. Draw the SDSP at the centre of the symmetric cross pattern search if the MAD value of the step 1 is (0,0) or else small diamond search pattern will form by taking MAD value of the step 2 as its centre and the final minimum cost value will be found. This modified cross diamond search has some advantages as it reduces the time required to process by an average of 18.05% compared to other algorithms. Also, it reduces number of search points required to 13.

2.4 New cross diamond search (NCDS) algorithm

This algorithm practices a small cross-shaped search pattern (SCSP) for 1st steps to increase the speed of blocks. Search technique used in NCDS follows two types, one is diamond search and other one is cross search. Each cross search and diamond search are further divided into SCSP and LCSP. By using Minimum BDM, it forms a small cross search pattern. Again, it calculates the minimum BDM and if it finds centre then stops, the search process or else goes to step 2. By highest point in 1st small cross shaped pattern as centre, a new small cross shaped pattern is formed. If smallest BDM point happens at centre of this SCSP, then search stops, else go to the step 3. A new LDSP is formed by using smallest BDM found in earlier step as centre of LDSP. If new smallest BDM point is at centre of newly formed LDSP, then go to Step 5 or else process continued by using minimum BDM point. Because of first two steps in SCSP, it reduces number of searches points and increases the speed. And it has much higher computational complexity than DS and CDS.

Video sequence has wide range of motion content and this algorithm offer stable performance. Star-diamond search pattern is the combination of star refinement and diamond search pattern which gives better result as compare to diamond search and is also having less complexity, due to this less complexity, number of computations are less and gives gain in PSNR. Form the study of various papers we find that the algorithms, which are used for, motion estimation is more time consuming and having more complex. So in this paper we propose diamond–hexagon search algorithm for motion estimation which gives less computations and better PSNR and also it can used in H.264/AVC which gives good bit rate and high quality video.

3 Proposed diamond–hexagon algorithm

We have done statistical study and investigation of the MVs in real images to diminish the calculating time. We proposed an algorithm diamond–hexagon search (DHS) that consists of making a coarse search “Star” made up of 9 points and the second search made up of 6 points of search forming Hexagon. First, we apply diamond search algorithm in current and previous frame, the compensated output image is considered as previous frame for Star diamond search and current frame is same as previous. The result of combined algorithm gives better PSNR and less computation than DS algorithm.

3.1 Proposed algorithm steps

Phase I:

Nine points are tested by centred the origin of current point by star diamond search. \(SAD_{min}\) Point searched then goes to phase II

Phase II:

The star pattern changed from star to small diamond search pattern and calculates \(SAD_{min}\) and continues till the search centre not located. This calculate the motion vector and Star pattern run only once to detect the direction of motion vectors, if it is stationary, vertical, diagonal or horizontal

Phase III:

The \(SAD_{min}\) point, which found in every stage, will be the centre point of the next step until this point will be a central point

Step 1:

Conversion into frame from test video

Step 2:

Assign first frame as a reference frame

Step 3:

Assign second frame as a target frame and the first frame act as a reference frame for the second frame

Step 4:

Find correlation between current frame and reference frame

Step 5:

Motion estimation will be done if there is correlation between current and reference frame and motion vector is calculated

Step 6:

Motion is compensated after motion vector calculation

Step 7:

Entropy coding done and encoded bit stream generated

Step 8:

Decoder side bit stream is converted into reconstructed frames

4 Simulation and results

For all image sequences, following performance parameters are used:

  1. 1.

    Mean square error:

    $$MSE = \frac{1}{{L^{2} }}\mathop \sum \limits_{X = 1}^{L} \mathop \sum \limits_{Y = 1}^{L} \left[ {I_{o} \left( {X,Y} \right) - I_{c} \left( {X,Y} \right)} \right]^{2}$$
    (1)

    where, \(I_{o} \left( {X,Y} \right)\) original image, \(I_{c} \left( {X,Y} \right)\) compressed image, L dimensions of image.

  2. 2.

    Mean absolute difference (MAD)

    $$MAD = \frac{1}{{L^{2} }}\mathop \sum \limits_{X = 1}^{L} \mathop \sum \limits_{Y = 1}^{L} \left[ {I_{o} \left( {X,Y} \right) - I_{c} \left( {X,Y} \right)} \right]^{1} .$$
    (2)
  3. 3.

    Peak signal to noise ratio (PSNR)

    $$PSNR = 10\log_{10} \left( {\frac{255 X 255}{MSE}} \right) .$$
    (3)
  4. 4.

    The number of calculated points (NCP) is defined by:

    $$NCP = \frac{P*SAD}{mb}$$
    (4)

    where P is the total number of SAD calculated between two frames.

In this paper many videos with a distance of 2 between current frame and reference frame is used to generate the frame-by-frame results of the algorithms which is named as Sequence A, B, C, D, E, F and G.

Figures 1 and 2 shows the Performance evaluation in terms of computations and PSNR of DS, SDS and Proposed Algorithm. Tables 1 and 2 are the comparison table for DS, SDS, DHS algorithms in terms of percentage evaluation of PSNR, Bit-rate and number of computation.

Fig. 1
figure 1

Performance evaluation in terms of PSNR

Full size image
Fig. 2
figure 2

Performance evaluation in terms of computations

Full size image
Table 1 Comparison between DS and DHS Algorithm
Full size table
Table 2 Comparison between SDS and DHS Algorithm
Full size table

5 Conclusion

In this paper, after evaluation of different parameters of proposed methods, it has been found that DHS algorithm outperform than DS algorithm and SDS in terms of PSNR and less number of search points. A DHS is also giving good results at an acceptable degradation in image quality. This paper shows the performance analysis of proposed DHS block matching algorithms for H.264 codec for reliable video compression with respect to bit-rate and gain in PSNR and less computation.