Biomedical Imaging and Intervention Journal Follow BIIJ on Twitter Find BIIJ on Facebook

Current issue Contact us

Editorial Board
Instruction for Authors
Editorial Workflow
Recorded Presentations
Remote Education

Free subscription

Subscription will allow you to receive automatic alerts and announcements from biij

13th Asian Oceanian Congress of Radiology (AOCR), Taipei, Taiwan March 20-23, 2010

5th Congress of Asian Society of Cardiovascular Imaging, Hong Kong, 18-19 June 2011

Engineering and Physical Sciences in Medicine and the Australian Biomedical Engineering Conference, Australia, 14-18 August 2011

Home > Contents


Biomed Imaging Interv J 2009; 5(3):e32
doi: 10.2349/biij.5.3.e32
© 2009 Biomedical Imaging and Intervention Journal

PDF version Technical Report

From ultrasound images to block based region motion estimation

SSS Ranjit*,1, BEng, KS Sim2, PhD, R Besar2, PhD, CP Tso2, PhD
1 Faculty of Electronics Engineering and Computer Engineering, Universiti Teknikal Malaysia Melaka, Malacca, Malaysia
2 Faculty of Engineering and Technology, Multimedia University, Malacca, Malaysia


By applying a hexagon-diamond search (HDS) method to an ultrasound image, the path of an object is able to be monitored by extracting images into macro-blocks, thereby achieving image redundancy is reduced from one frame to another, and also ascertaining the motion vector within the parameters searched. The HDS algorithm uses six search points to form the six sides of the hexagon pattern, a centre point, and a further four search points to create diamond pattern within the hexagon that clarifies the focus of the subject area. © 2009 Biomedical Imaging and Intervention Journal. All rights reserved.

Keywords: Hexagon search, motion estimation, ultrasound images, diamond search, block-matching


The current status quo in ultrasound research lends itself to a process where anticipated motion coordinates are calculated through the identification of objects in motion within a series of images [1]. The incorporation of block-matching into the process allows the prediction of the expected range of motion, by comparing the previous and current image instances in the series [2]. Further extension of these principles occurs through focusing on a specific region of interest within an image, and in this way block-matching can be used to interpret ultrasound images for such purposes as medical heart translation [3].

By combining block-matching processes with optical flow, atrial septal defects have since been able to be diagnosed with great accuracy, simply by identifying the incongruent elements inherent in two consecutive frames [4]. While applying this measurement of difference to ultrasound images, Singh’s formula also incorporated block-matching, and the application of velocity estimation in ultrasound images [5]. Further, block-matching has been used to identify the precise dimensions in 3-D ultrasound images [6], and this ability has led to the use of block-matching to identify fetal development and movement [7].

Due to the fact that compression of video often leads to temporary redundancy, the block-matching algorithm is found to be able to decrease this redundancy in many frameworks, and has enjoyed great favour by users [8]. To identify the precise change in position of the most favourably matched block vis-a-vis the preceding frame, block-based motion estimation mimics the motion vector to the block in the current frame within the search area, by dividing the frames similarly, into equally sized rectangular blocks.

Clearly, the hexagon-diamond search (HDS) technique warrants being applied to ultrasound imaging through video sequences. These video sequences, apart from assisting a diagnosis, will capture the true condition of subjects, and as less memory is utilised to store data, high transmission of data is possible to affect video conferencing.

MATLAB (The Mathworks, Natick, MA) is used to execute these intensive computations, and allows for the dynamic monitoring of motion translation within the video sequence. This allows calculation of the motion vector, which is then incorporated into the process when the challenging area is scrutinised.

Proposed Solution

The combination of the hexagon search pattern and its corresponding diamond search pattern is in essence a process of primary searching followed by verification of primary coordinates to result in a far more precise output.

The focus of the search is within the six search points of the outer hexagon pattern, with a seventh point taking up position at its centre. Around this centre, another four search points form a small diamond pattern within the hexagon pattern, which clarifies the search.

The hexagon is the one shape that addresses the vertical and horizontal block displacement that is found in most video sequences, by adapting its operation to match this directionality.

In order to affect faster block-matching computation speed, the mean absolute difference (MAD) is the criteria of choice that is compared. When the MAD is utilised in this fashion, the peak signal to noise ratio (PSNR) of the target video is reduced, and it enables bleeding edge analysis of block matching algorithms (BMA) [9].

If one is familiar with search methods applied to various parameters and shapes, fast block-matching algorithms are able to successfully analyse the search speed and performance of any given search method [10]. Invariably, 50-90% of motion vectors are within a circle of a two pixel radius, its centre bearing zero motion [9].

The following search method uses two different sub-searches, each of a different shape.

  • Step 1 The six search points that form the hexagonal and the seventh point at its centre undergo verification and comparison with one another. The minimum motion vector will then be identified; if the minimum MAD calculation is to be had at the centre of the hexagon, jump to Step 4.
  • Step 2 If not, the hexagonal search is repeated until the minimum MAD is at the centre of the hexagonal.
  • Step 3 The minimum MAD that is now the centre of the hexagonal now forms the centre of the small diamond.
  • Step 4 The search then jumps to the small diamond search to clarify the minimum motion vector and make comparisons between the four points of the diamond to ascertain the best minimum MAD.
  • Step 5 Once this search has found the minimum MAD in the current block it will move to the next one.

Due to their configuration, the search points above will resolve vertical and horizontal block displacements. It is with respect to this inherent ability that the region of interest will be scrutinised. The use of less frequent search points reduces processing time, and increases the overall performance of the algorithm in when locating the region of interest

Results and Discussion

In order to monitor performance of the HDS algorithm, in addition to capturing each frame and calculating its PSNR points, the predicted frame is compared to the reference frame. The resulting displacement is used to reveal the condition of the region of interest.

The following initialisation is implemented:

  • MAD block size 16 x 16 pixels
  • Search window size 15 x 15 pixels
  • Ultrasound video sequence 176 x 144 pixels at 5 frame per second (f.p.s.)

The hexagon pattern with its six points and centre point is used to search until the optimum motion vectors are identified (MAD0, MAD1, MAD2 and MAD3). Then the small diamond search pattern clarifies MAD4 and verifies that it is the optimal motion vector from comparing the four search points of the small diamond pattern.

The number of PSNR points in the reference video sequence is greater than in the newly constructed video sequence. This is apparently due to the compression of the image [9], but a reduction in PSNR points has the collateral benefit of also offering an image with higher definition.

Adding to better image quality, converse to the frequency of PSNR points, the number of search points increases when the image is compressed to produce the reconstructed video sequence (an increase of 1.22 search points at 5 f.p.s. and an increase of 2.42 search points at 10 f.p.s).

As a result of the HDS algorithm, at 5 f.p.s. the PSNR of the original video sequence undergoes a 29.4% compression, and at 10 f.p.s. it undergoes 27.6% compression. This is conclusive evidence of temporal redundancy being reduced, and the increase in the number of search points makes the exercise of realising of the best matching block in the processed target frame more accurate.

The results of the HDS algorithm in use reveal a small change from original image to the reconstructed image. Figures 4(a), 5(a), 6(a), and 7(a) all represent the original video sequence, and Figures 4(b), 5(b), 6(b) and 7(b) the reconstructed sequence. When the HDS algorithm is applied, the best motion vector for the target image for the fine tuning search comprises of the following respectively: (8,7), (9,9), (8,9) and (8,9). These coordinates are the point at which motion can be monitored with precision; they are the position of the best matching block in the preceding frame. When the frames of the original video sequence are compared to the reconstructed frames, the temporal redundancy is patently obvious. Compression is evident in the number of PSNR points decreasing in the resultant video sequence (Table 1), which shows that compression is taking place and removes the temporal redundancy. This vector smoothing technique is a result of the fact that the motion vector has a more pronounced impact on the compression ratio.

As in Figures 4(b), 6(b), and 7(b), when the motion vector magnitudes are increasing in order, the change from the reference point will not be constant. The best matching point in both these instances is on the vertical plane. The motion vector magnitude in Figure 5(b), however, can be read to be getting larger or smaller, and the coordinates reveal that the best matching point is on the horizontal plane.


The hexagon-diamond search algorithm has the ability to optimise ultrasound video sequence block-matching for motion estimation. This functionality is indispensable in diagnostics, and is portable enough to be applied to image compression and reconfiguration of ultrasound video sequences. In this manner, bleeding edge transmission can take place even with conduits of meagre capacity.

Figure 1 A schematic of hexagon-diamond search algorithm.

Figure 2 HDS method flowchart.

Figure 3 Motion vector search method.

Figure 4 (a) Original ultrasound image and (b) Predicted ultrasound image

Figure 5 (a) Re-processed original ultrasound image and (b) Predicted ultrasound image

Figure 6 (a) Original ultrasound image and (b) Predicted ultrasound image

Figure 7 (a) Re-processed original ultrasound image and (b) Predicted ultrasound image

Table 1 Algorithm output at 5 and 10 f.p.s


  1. Potocnik B, Zalula D. Automatic analysis of a sequence of ovarian ultrasound images. Part II: Prediction-based object recognition from a sequence of images. J Image & Vision Comput 2002; 20:227-35.  
  2. Kokkinidis I, Strintzis MG. Maximum likelihood motion estimation in ultrasound image sequences. IEEE Signal Processing Letters 1997; 4(6):156-7.  
  3. Behar V, Adam D, Lysyansky P et al. Improving motion estimation by accounting for local image distortion. Ultrasonics 2004; 43(1):57-65.   [Medline]
  4. Linguraru MG, Kabla A, Vasilyev NV et al. Real-time Block Flow Tracking of Atrial Septal Defect Motion in 4D Cardiac Ultrasound. Biomedical Imaging 2007; 356-9.  
  5. Boukerroui D, Noble JA, Brady M. Velocity estimation in Ultrasound images:a block matching approach. Lecture Notes in Computer Science 2003; 2732:586-98.  
  6. Pedersen PC, Mitra V, Dey J. Boundary Detection in 3D Ultrasound Reconstruction using Nearest Neighbor Map. International Society for Optical Engineering 2006; 6147:617-707.  
  7. Lee GI, Park RH, Song YS et al. Real-time 3-D ultrasound fetal image enhancement techniques using motion compensated frame rate up-conversion. International Society for Optical Engineering 2003; 5035:375-85.  
  8. Fouard C, Malandain G, Prohaska S et al. Blockwise processing applied to brain microvascular network study. IEEE Trans Med Imaging 2006; 25(10):1319-28.   [Medline]
  9. Zhu S, Ma KK. A New Diamond Search Algorithm for Fast Block Matching Motion Estimation. IEEE Transactions on Image Processing 2000; 9(2):287-90.  
  10. Tham JY, Ranganath S, Ranganath M et al. A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology 1998; 8:367-77.  
  11. Po LM, Ma WC. A Novel Four-Step Search Algorithm for Fast Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology 1996; 6(3):313-7.  
  12. Lam CW, Po LM, Cheong CH. A Novel Kite-Cross-Diamond Search Algorithm for Fast Block Matching Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology 2004; 729-32.  
  13. Kim BG, Song SK, Mah PS. Enhanced Block Motion Estimation Based on Distortion-Directional Search Patterns. Pattern Recognition Letters 2006; 27(12):1325-35.  
  14. Hai BY, Xiang ZF, Hua Y et al. Motion Vector Smoothing for True Motion Estimation. IEEE International Conference on Acoustics, Speech and Signal Processing 2006; 2:241-4.  

Received 7 May 2009; received in revised form 17 September 2009; accepted 30 September 2009

Correspondence: Faculty of Electronics Engineering and Computer Engineering, Universiti Teknikal Malaysia Melaka, Malacca, Malaysia. Tel.: +6065552161; Fax: +6065552112; E-mail: (Ranjit Singh).

Please cite as: Ranjit SSS, Sim KS, Besar R, Tso CP, From ultrasound images to block based region motion estimation, Biomed Imaging Interv J 2009; 5(3):e32

University of Malaya, Kuala Lumpur, Malaysia


Bayer Healthcare
Elekta Fujifilm Barco Transmedic

Official publication of

ASEAN Association of Radiologists
ASEAN Society of Interventional Radiology
Asia-Oceania Federation of Organizations for Medical Physics
Asian Oceania Society of Radiology
College of Radiology, Academy of Medicine Malaysia
Southeast Asian Federation of Organisations of Medical Physics
South East Asian Association of Academic Radiologists

Published by

Department of Biomedical Imaging, Faculty of Medicine, University of Malaya, Malaysia


Biomedical Imaging and Intervention Journal. ISSN 1823-5530 RSS | Facebook | Twitter

Creative Commons License
Except where otherwise noted, articles published in the Biomedical Imaging and Intervention Journal
are distributed under the terms of the Creative Commons Attribution License, which permits
unrestricted use, distribution, and reproduction in any medium, provided the original work is properly
cited, including full bibliographic details and the URL, and this statement is included.