International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 116
ISSN 2229-5518
Chetan S.Dhamande,Prashant.A.Bhalge
Abstract— Motion Estimation is one of the most critical modules in a typical digital video encoder. many implementation tradeoffs should be considered while designing such a module. It can define ME as a part of inter coding technique inter-coding refers to a mechanism of finding co-relation between two frames (still images), which are not far away from each other as far as the order of occurrence is concerned, one frame is called the reference frame and the other frame called the current frame, and then encoding the information which is a function of this co-relation‟ instead of the frame itself. This paper focuses more on block matching algorithms which comes under feature/region matching. Block motion estimation algorithms are widely adopted by video coding standards, mainly due to their simplicity and good distortion performance In FS every candidate points will be evaluated and more time will be taken for predicting the suitable motion vectors. based on the above noted drawback, the above said adaptive pattern is proposed Optimization is proposed at algorithm/code-level for both encoder and decoder to make it feasible to perform real-time H.264/AVC video encoding/decoding on mobile device for mobile multimedia applications. For encoder an improved motion estimation algorithm based on hexagonal pattern search is proposed exploit- ing the temporal redundancy of a video sequence. For decoder, at code level memory access minimization scheme is proposed and at algorithm level a fast interpolation scheme is proposed.
————————— ——————————
The motion search pattern is important in terms of search speed and correctness of the motion information, it consider various search patterns and search strategies. By ana- lyzing the block matching algorithm as a function of the block size and distance in the search area, find analytic search pat- terns for initial motion estimation. it also propose an adaptive motion search algorithm, where it exploit the correlation be- tween block difference and motion magnitude. Important pa- rameters in motion estimation are: size of block, search area, search pattern, search strategy, and matching criterion. [1]Various algorithms for fast block search have been devel- oped to reduce the computational burden associated with the full-search block matching algorithm (BMA). They mainly focus on the search strategy using heuristic methods. Recently, it is known that the motion search pattern has an important influence on search speed and correctness of the motion in- formation. Since the search strategy depends on search pat- terns for efficient motion estimation, it analyze search patterns for fast motion estimation. In a teleconferencing video, most image blocks are regarded as stationary or quasistation- ary.Motion vectors for stationary image blocks are mostly around (0,0). In order to decide if a block is stationary. Block
motion estimation algorithms are widely adopted by video coding standards, mainly due to their simplicity and good distortion performance. Using block motion estimation, a vid- eo frame is divided into non-overlapping block of equal size and the best matched block is determined from reference frames to that block in the current frame within a predefined search window. Normally, this is performed by minimizing a block distortion measure (BDM) between these two blocks such as the sum of absolute difference (SAD). The most straightforward BMA is the full search (FS), which exhaustively searches for the best matching block within the search win- dow. However, FS yields very high computational complexity and makes ME the main bottleneck in real-time video coding applications. Thus, using a fast BMA is indispensable to re- duce the computational cost. To reduce the number of search points, three classes of BMAs have been exploited:
1) Methods based on a set of fixed search patterns
2)Methods exploiting inter-block correlation, and
3)Methods applying hierarchical or multi resolution
framework.
a current frame into no overlapping rectangular
blocks/macro blocks of equal size, a block-matching method
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 117
ISSN 2229-5518
attempts to find a block from a reference frame (past or future frame) that best matches a predefined block in the current frame. Matching is performed by minimizing a matching crite- rion, which in most cases is the mean absolute error/difference between this pair of blocks. The block in the reference frame moves inside a search window centered around the position of the block in the current frame.
Figure 1[2]
Diamond Search Motion Estimation
The DS algorithm [1] comprises two search patterns. The
first pattern, called large diamond search pattern (LDSP) shown in Figure 2(a), comprises nine checking points from which eight points surround the center one to compose a diamond shape. The second pattern consisting of five checking points forms a small diamond shape, called small diamond search pattern (SDSP) shown in Figure. 2(b). In the searching procedure of the DS algo- rithm, LDSP is repeatedly used until the minimum block distor- tion (MBD) occurs at the center point. DS algorithm consistently performs well for the image sequence with wide range of motion content
the search pattern (LDSP or SDSP) is near to or at the search window boundary, the checking points outside the search window are truncated. That is, the search is confined within the search window boundary. Note that this is a necessary constraint in MPEG standards since the variable-length codebook size for encoding motion vectors is limited.
DS algorithm doesn't restrict the number of search steps essentially. The MBD point found in each step has less or equal matching comparison of the average number of search points ap- plying DS, 4SS, and NTSS to “Caltrain” sequence individually when (a) frame distance = 1 and (b) frame distance = 2.error com- pared with all the other checking points in the search pattern, which includes the MBD point found in the previous step, thus the MBD values found along the search path are in a non increas- ing order If the center point of LDSP produces the MBD, the search pattern is changed from LDSP to SDSP in the final search. In this case, only four new points are required to be tested, as shown in Fig. 3(c).the compact shape of the search patterns used in the DS algorithm increases the possibility of finding the global minimum point located inside the search pattern
Figure 2[4]
(a)Large Diamond Search Pattern (LDSP), (b) Small Diamond Search Pattern (SDSP)
DS by 538% at average search points and FS by 405 times and the average PSNR quality is slightly better (0.10–0.19 dB) than all the other algorithms including FS. This may be due to the fact that our scheme often prefers a smaller value MV, which requires fewer bits in coding. And a few additional bits are available for texture (DCT coefficients) coding, which results in better overall PSNR.
[4]Figure 3(a)the corner point(b)the edge point
(c) the center point
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 118
ISSN 2229-5518
Motion estimation in H.264 follows hexagon-based search pattern which is depicted in Fig.4. It consists of seven checking points (shaded dots) with the center surrounded by six endpoints of the hexagon with the two edge points (up and down) being excluded. Of the six endpoints in the hexagon, two horizontal points are away from the center with distance 2 and the remaining four points have a distance of √5 from the center point, respectively that the hexagonal search pattern also contains seven checking points at the beginning. Then the search process, the hexagon-based search pattern keeps advancing with the cen- ter moving to any of the six endpoints. Whichever endpoint the center of the search pattern moves to, there are always three new endpoints emerging, and the other three endpoints are being overlapped
Figure 4[5]
In order to speed up the motion estimation process, it divide the motion estimation process into two parts
2. 1.Dynamic motion detection
A motion detection method is suggested to separate out
moving and stationary blocks within a frame. A frame is seg- mented in to blocks (7 modes for H.264).Each selected block is then identified as moving or stationary. The stationary block is assumed with zero motion vectors. And for the motion vector estimation of moving block temporal redundancies of video se- quence are exploited to minimize the search points using stand- ard motion estimation techniques
2.2 Motion Estimation For Moving Block
For a moving block motion estimation is carried out by
exploiting the temporal correlation between the frames in a video sequence. When matching a block from the current frame with a block from the previous frame, the matching criterion is usually evaluated using all samples within the block. Block matching is based on the assumption that all samples in a block move accord- ing to the same motion vector.
[6]A hexagonal search pattern is depicted in Fig. 1 and
the inner search for the HEXBS algorithm is carried out using the shrunk hexagonal pattern covering the points 2, 4, 5, and 7. In
[10], a one-more-step HEXBS is also presented to cover an addi- tional pair of points of the four other points inside the hexagonal search pattern, i.e., points 1 and 3 if point 2 wins in the last step of the HEXBS algorithm, points 1 and 6 if point 4 wins, points 3 and
8 if point 5 wins, and points 6 and 8 if point 7 wins. Note that a complete inner search within the large hexagon would require the evaluation of all the eight patterned points inside, excluding the center point. Hence, a more efficient inner search is desired to speed up the search process
Figure 5[6]
2.2 Fast Hexagonal Inner Search
In the original hexagonal search (HEXBS) algorithm two search procedures are involved. The coarse search procedure first locates a region where the optimal motion vector is expected to lie, using the large hexagon search pattern consisting of six end- points in Fig. 6 The coarse search continues based on a gradient scheme until the center point of the hexagon has the current smallest distortion. After a hexagonal area is located in the coarse search, then the following fine-resolution search looks into the small area enclosed by the large hexagon for focused inner search using the shrunk hexagon pattern, which is not a full inner search. if full search is required for the inner search, eight search points inside the large hexagon will be evaluated, which is computation- ally inefficient. Interestingly, it find that strong correlation exists between the inner search points to be checked (i.e., the eight la- belled points in Fig. 6 and their surrounding checked points (here the six endpoints of the hexagon in Fig. 6 Based on the monotonic distortion characteristic in the localized area around the global minimum, propose to check only a portion of the inner search points that are nearer to the checked points with smaller distor- tions, which can save more than half of the eight search points inside it will present such an efficient inner search scheme by ex- ploiting the distortion information of the six checked endpoints of the large hexagon. There can be several different ways to exploit the distortion information. By trial and error it find the most effi- cient inner search method in terms of minimizing both number of search points evaluated and the corresponding distortion. The method is referred to as 6-side-based fast inner search, which is
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 119
ISSN 2229-5518
found to be most reliable and robust among some other variants tried in maintaining almost the same distortion as the full inner search.
ME is highly scene dependent, and, no one technique can be fully relied to generate good visual quality for all kinds of vid- eo scenes. Instead, it is the quintessence of a variety of techniques, such as motion starting point, motion search patterns, and adap- tive control to curb the search, avoidance of search stationary re- gions, etc., that makes an ME algorithm robust and efficient across the board.[3] For the Initial Search: The shape of our rood pattern is symmetrical, with four search points locating at the four vertices, as depicted in Fig 7. The main structure of ARP has a rood shape, and its size refers to the distance between any vertex point and the center point. (Since symmetrical, four vertex points have equal distance to the center point.) As a special case, when the size of ARP is zero, the ARP will be shrunk from its normal rood shape to the center point itself.
Figure 6[7]
adjacent MBs belong to the same moving object have the similar motions. Therefore, the current block’s motion behavior can be reasonably predicted by referring to its neighbouring blocks’ MVs in the spatial and/or temporal domains. As for the second issue, it use two types of search patterns. One is the adap- tive rood pattern (ARP) with adjustable rood arm (thus, the pattern size), which is dynamically determined for each MB according to its predicted motion behavior. Note that ARP will be exploited only once at the beginning of each MB search. The objective is to find a good starting point for the remaining local search so as to avoid unnecessary intermediate search and reduce the risk of be- ing trapped into local minimum in the case of long search path.
A typical image watermark algorithm must satisfy the fol-
lowing two properties: transparency and robustness. Trans- parency means that the embedded watermark pattern does not visually spoil the original image fidelity and should be invisible. Robustness means the watermark pattern is not easy to detect and remove illegally. Moreover, any modifications of the image values have to be invisible, and the watermark method has to be robust or fragile in order to provide protec- tion against attackers.method has to be robust or fragile in or- der to provide protection against attackers.
There are various innovative ideas and extensions exist for the basic visual cryptographic model introduced till now. In the existing VC schemes no security is provided to the secret shares and adversaries can alter its bit sequences to create fake shares. And in proposed scheme, the vulnerability of these binary secret shares is overcome by hiding them invisibly into some host images. During the decryption phase, the secret shares are extracted from their cover images without needing any of the cover image characteristics because of watermark extraction technique.
ACKNOWLEDGMENT
The authors wish to thank Babasaheb Naik colleage of Engi- neering,Pusad.
REFERENCES
[1] Deepa Mary Thomas,,Subha Varier “A Novel Based Approach for Find- ing Motion Estimation in Video Compression” International Journal of Advanced Research in Computer and Communication Engineering Vol. 1, Issue 8, October 2012
[2] Dong-Keun Lim and Yo-Sung Ho “Adaptive Motion Search Based on
Block Difference and Motion Magnitude” IDMS/PROMS 2002, LNCS 2515, pp. 118-129, 2002
[3] T. Wiegand, G. J. Sullivan, G. Bjøntegaard, and A. Luthr, “Overview of the H.264/AVC video coding standard,” IEEE Trans. Circuits Syst.Video Technol., vol. 13, no. 7, pp. 560–576, Jul. 2003.
[4]S. Zhu and K.-K. Ma, “A new diamond search algorithm for fast block- matching motion estimation,” in Proc. Int. Conf. Inf. Commun. Signal Pro- cess. (ICICS ’97), vol. 1, Sep. 9–12, 1997, pp. 292–296
[5] C. Zhu, X. Lin, and L.-P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349–355, May 2002.Y.
[6] Nie and K.-K. Ma, Y. Nie and K.-K. Ma, “Adaptive irregular pattern
search with matching prejudgment for fast block-matching motion esti- mation,” IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 6, pp. 789–794,
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 6, June-2013 120
ISSN 2229-5518
Jun. 2005.
[7] NIE AND MA: “Adaptive rood pattern search for fast block matching motion estimation,” IEEE Trans. Image Process., vol. 11, no. 12, pp. 1442–
1449, Dec. 2002.
.[8] S. Immanuel Alex Pandian, Dr.G. Josemin Bala, and Becky Alma George” A Study on Block Matching Algorithms for Motion Estimation” S. Immanuel Alex Pandian et al. / International Journal on Computer Science and Engineering ISSN : 0975-3397 Vol. 3 No. 1 Jan 2011
[9] Sourabh Rungta , Dr.Neeta Tripathi and Kshitij Verma” Hexagonal Based Search Pattern for Motion Estimation in H.264/AVC” World of Computer Science and Information Technology Journal
ISSN: 2221-0741 Vol. 1, No. 4, 162- 166, 2011
[10] L.-M. Po and W.-C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 6, pp. 313–317, Jun. 1996
.
IJSER © 2013 http://www.ijser.org