From ultrasound images to block based region motion estimation
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
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 . 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 . 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 .
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
. 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 . Further, block-matching has been
used to identify the precise dimensions in 3-D ultrasound images , and this
ability has led to the use of block-matching to identify fetal development and
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 . 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
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) .
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 .
Invariably, 50-90% of motion vectors are within a circle of a two pixel radius,
its centre bearing zero motion .
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
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
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 , 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
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
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
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.
Kokkinidis I, Strintzis MG. Maximum likelihood motion estimation in ultrasound image sequences. IEEE Signal Processing Letters 1997; 4(6):156-7.
Behar V, Adam D, Lysyansky P et al. Improving motion estimation by accounting for local image distortion. Ultrasonics 2004; 43(1):57-65.
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.
Boukerroui D, Noble JA, Brady M. Velocity estimation in Ultrasound images:a block matching approach. Lecture Notes in Computer Science 2003; 2732:586-98.
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.
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.
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.
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.
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.
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.
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.
Kim BG, Song SK, Mah PS. Enhanced Block Motion Estimation Based on Distortion-Directional Search Patterns. Pattern Recognition Letters 2006; 27(12):1325-35.
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: firstname.lastname@example.org (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