CN100496130C - Estimation method for quick video motion - Google Patents
Estimation method for quick video motion Download PDFInfo
- Publication number
- CN100496130C CN100496130C CN 200610033468 CN200610033468A CN100496130C CN 100496130 C CN100496130 C CN 100496130C CN 200610033468 CN200610033468 CN 200610033468 CN 200610033468 A CN200610033468 A CN 200610033468A CN 100496130 C CN100496130 C CN 100496130C
- Authority
- CN
- China
- Prior art keywords
- point
- search
- mad
- central point
- displacement
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Compression Or Coding Systems Of Tv Signals (AREA)
Abstract
The disclosed estimation method for video fast motion comprises: (a) calculating the search block center point and the MAD of every vertex of large and small diamonds with the center point as center; and (b) according to the position of minimal MAD point, gradual reducing search area for fine search. This invention reduces calculation amount on matching block greatly, special fit to hardware implementation, and can be used widely to H.264, H.261, H.263, MPEG-2 and MPEG-4 standard, etc.
Description
Technical field
The invention belongs to the Digital Video Processing technical field, relate in particular to and a kind ofly be particularly suitable for hard-wiredly, can reduce the estimation method for quick video motion of computational complexity.
Background technology
For video sequence, there is very big temporal correlation between the consecutive frame, promptly the time redundancy by reducing time redundancy, can increase substantially the efficient of video coding.Motion estimation algorithm based on the piece coupling is a kind of effective method that reduces time redundancy information, this technology is widely used in the international standard of video compression, as ITU-T H.261/263, MPEG1/2/4, and by ITU-T VCEG and the common H.264 video encoding standard of formulating of MPEG tissue, it realizes that effect depends primarily on three factors: matching criterior, hunting zone and way of search.Practical matching criterior adopts mean absolute error (MAD) criterion mostly, and the hunting zone is a unit with macro block and piece generally, and way of search is the principal element that influences the BMA performance, also is the key technology in the motion estimation algorithm.
H.264 standard is a kind of video encoding standard of novelty, and it is all obtaining very big success aspect compression ratio and the video recovery quality, but its computation complexity is too big, and this has limited the H.264 application of standard to a certain extent, and especially real-time video is used.From the estimation aspect, H.264 standard allows multi-reference frame, multiple macroblock partitions mode and 1/4 pixel precision motion vector, and this has all improved the H.264 complexity of standard movement estimation greatly.Therefore, need research to be fit to the H.264 rapid motion estimating method of standard, and do not influence compression ratio and video recovery quality, otherwise the standard that just lost H.264 is in compression ratio with recover qualitative advantage.
Reducing a redundant example according to the conventional motion estimation method is to adopt full search (FS) as BMA.Full-search algorithm (FS) precision is the highest, it carries out matching operation to each pixel in the hunting zone, to obtain the motion vector of an optimum, but its computation complexity is too high, make estimation will account for 60%～80% of whole coding operand, be not suitable for real-time application, also be unfavorable for the software and hardware realization simultaneously.Be directed to this, the scientific research personnel has proposed multiple fast search algorithm in succession, as three-step approach (TSS), new three-step approach (NTSS), rhombus therapy (DS) etc., its thought all is by designing different search patterns and searching method, limit the number of searching position so that reduce amount of calculation, thereby the quick of realization motion vector being estimated effectively.
Classical three-step approach (TSS) is because effectively simple, recommended by H.261 RM8 and the SM3 of MPEG.New three step search methods (NTSS) based on the center are improvement to three-step approach (TSS), and the method that adopted for half step stopped has reduced computing time.Rhombus therapy (DS) is a kind of fast algorithm all relatively more outstanding on time performance and precision index.Above-mentioned fast search algorithm only carries out matching ratio to the macro block that partial pixel point determined in the search window, obtain the motion vector of an optimal approximation, so on computation complexity, obviously reduce than full-search algorithm (FS), yet compare with full search (FS), reduced search point just because of the fast motion estimation algorithm, may make that estimation is insufficient, thereby make compression rates reduce or the decline of recovery quality, these descend for some Video Applications is very disadvantageous.Therefore, still need guarantee compression ratio and recover under the prerequisite of video quality, carry out the method for estimating of quick piece coupling by reducing computational complexity.
Summary of the invention
In order to address the above problem, the invention provides a kind of under the prerequisite that guarantees compression ratio and video recovery quality, block matching motion method of estimation fast and effectively, a large amount of statistical tests show, the likelihood ratio that general object moves in the horizontal and vertical directions is bigger, the frequency spectrum of image becomes the rhomboid distribution of class more, the regular polygon that can comprehensively cover a search plane has equilateral triangle, square, three kinds of regular hexagons, because diamond search and square search respectively possess some good points, in order to take all factors into consideration the advantage of these two kinds of search patterns better.The invention discloses a kind of estimation method for quick video motion, it is characterized in that this method may further comprise the steps:
(a) calculate search block central point and be the big rhombus at center and the mean absolute difference (MAD) on each summit of little rhombus with this point;
(b), adopt the method for progressively dwindling square region of search to carry out fine search according to the position of the minimum MAD point of determining in the step (a).
Wherein, the big rhombus summit in the step (a) has identical predetermined step-length with little rhombus summit to central point to little rhombus summit.
Four summits of above-mentioned big rhombus equate all that to the distance of central point four summits of little rhombus also equate to the distance of its central point.
May further comprise the steps in the above-mentioned steps (b): (1) is the center with the minimum MAD point of determining in the step (a), introduce the square region of search search point of predetermined quantity, the displacement that these new search points and central point have the intended pixel distance, calculate the MAD value that institute introduces the search point, central point with introduce the position of a value point of determining to have minimum MAD in searching for; (2) be the center with the minimum MAD point of determining in the step (1), introduce the square region of search search point of predetermined quantity, the displacement that these new search points and central point have the intended pixel distance, calculate the MAD value of the search point of introducing, introduces the position that search determines to have the value point of minimum MAD in putting in central point and institute, wherein the displacement of new search point of Yin Jining and central point reduces by half; (3) be the center with the minimum MAD point of determining in the step (2), introduce the square region of search search point of predetermined quantity, the displacement that these new search points and central point have the intended pixel distance, and displacement reduces by half, calculate the MAD value of the new search point of introducing, in the position that central point and institute introduce the point of determining to have the minimum MAD value in search for putting, promptly the displacement vector of this point is motion vector.
The mean absolute difference (MAD) of the point that is calculated in the said method also can be the average variance (MSD) of calculation level, and adopting uses the same method carries out the search of motion vector.
The multi-reference frame estimation is carried out speed-optimization in The present invention be directed to H.264, be better than popular several fast motion-estimation algorithms at present, not only greatly reduce the amount of calculation of piece coupling, and the motion vector of search has very high matching rate with full search (FS) motion vector, biggest advantage is to be particularly suitable for hardware and realizes, thereby it recovers video quality and compression efficiency, is subjected to the influence of search point hardly.The method of the invention is simply effective, and versatility is very strong, not only is suitable for H.264 standard, other are widely popular H.261, H.263, video coding international standards such as MPEG-2, MPEG-4 also can use.
Description of drawings
Fig. 1 is the flow chart of the method for the invention;
Fig. 2 a, 2b, 2c and 2d represent four kinds of quadrature CLV Common Intermediate Format schematic diagrames respectively, as " Carphone ", " Foreman ", " Mom ﹠amp; Daughter " and each image sequence of " Susie " in motion vector distribution;
Fig. 3 represents the processing procedure schematic diagram of the method for the invention step b;
Fig. 4 represents intersection-accurate diamond search pattern schematic diagram;
Fig. 5 represents the example schematic of estimated motion vector (9 ,-13).
Embodiment
Below with reference to accompanying drawing the method for the invention is described in detail.
Fig. 1 is the flow chart of the method for the invention, and the fact of foundation method for estimating utilization of the present invention is that in the moving image of per second 20～30 frames, about 70% motion vector all concentrates on motion vector coordinate (0,0).Four kinds of quadrature CLV Common Intermediate Formats in Fig. 2 a, 2b, 2c and the 2d presentation video sequence are as " Carphone ", " Foreman ", " Mom ﹠amp; Daughter " and each image sequence of " Susie " in motion vector distribution.With reference to the accompanying drawings 2, motion vector distribution all concentrates on (0,0) on every side.
Method for estimating of the present invention is considered mean error (MSD) or the minimum direction motion of mean absolute difference (MAD) that most motion vector trends towards being scheduled to, this is easy to find at local smallest point place, and, on the peripheral direction of local smallest point, there is motion probably.Therefore, if with any one search point be defined as on this direction MAD value hour, then carry out fine search on every side at this point.Motion vector distribution is bigger than other directions that are distributed under the same radius at the probability of level and vertical direction.For example, it is to distribute in the horizontal and vertical directions that 74.76% motion vector is arranged approximately, and has only 7.05% motion vector distribution altogether on other directions of same radius.This explanation vector distributes and has the intersection biasing characteristic.According to this characteristic, designed intersection-accurate diamond search template, as shown in Figure 4, the method of the invention has two kinds of basic search shapes, rhombus and square adopt the rhombus of two different sizes to carry out extensive search, wherein in the method first step, intersection-accurate rhombus has been strengthened the search to the central area, and employing is later on progressively dwindled the method for square dimensions and carried out fine search.
The processing procedure schematic diagram of accompanying drawing 3 expression the method for the invention step b, as shown in Figure 3, central point and distance center point step size are respectively 8 and 16 rhombus summit and are confirmed as new search point, calculate the MAD value at determined new search point place; For each MAD value, determine the position of the point of minimum MAD value, with the center of this point, determine with this displacement to be 8 search points of ± 4 pixels for square search in next step, the MAD value of search point is determined in calculating; Determine the position of the point of minimum MAD value in above-mentioned nine points, as the central point of square search in next step; Increase with determined search center point displacement is 8 search points of ± 2 pixel distances, adopt little square to carry out focused search, the new MAD value of determining the search point of calculating, the position of finding out the point of MAD value minimum in nine points is as the medium and small foursquare center of this step; Increasing with determined search center point has ± 8 search points of 1 estimated distance, and computer center point and institute increase a MAD value of searching for, and the displacement vector that will have a search point of minimum MAD value is defined as motion vector.
Fig. 5 represents the example of an estimated motion vector.With reference to the accompanying drawings 5, on a large scale in the rough search, the search point of minimum MAD value is (8 ,-8) at the rhombus of the first step.According to the method for the invention, should adopt square to carry out fine search below, at first, determine that point (8 ,-8) is new search center point.And determine eight search points from this new search center (8 ,-8) displacement ± 4 pixel distances; The MAD value of search point is determined in calculating then, and eight search points from this search center point (12 ,-12) displacement ± 2 pixels as next step search center, are determined in the position (12 ,-12) that relatively draws the point of minimum MAD value; The MAD value of search point is determined in calculating, with minimum MAD value point (10,-14) be new search center point, introduction is from eight search points of determined search center point displacement ± 1 pixel, in central point and provide eight search points, determine the optimum points (9 of MAD value minimum,-13), and with the displacement vector conduct of optimum point decide motion vector.
As can be seen, finish the search of determining motion vector by above-mentioned steps, the quantity of search point is " 13+8+8+8=37 ", needs 1089 times with directly seeking, and amount of calculation reduces a lot.That is to say, reduced complexity of calculation significantly according to method for estimating of the present invention, and improved image compression speed.Although descend greatly according to method for estimating search point of the present invention, video recovery quality that obtains and full search suitable substantially, the PSNR that represents with decibel (db) is project as a comparison.That table 1 is represented is the result who 100 frames of every kind of test pattern is measured mean P SNR:
Table 1
| Carphone | Foreman | Mom?&?Daughter | Susie | |
| FS | 32.1984 | 30.619 | 37.4603 | 35.3273 |
| The present invention | 32.1098 | 30.4358 | 37.3986 | 35.2165 |
Reference table 1, method for estimating of the present invention is different with traditional method for estimating, can not damage picture quality during image compression, and greatly reduces computation complexity, has kept H.264 standard in compression ratio with recover qualitative advantage.
Claims (6)
1, estimation method for quick video motion is characterized in that this method may further comprise the steps:
(a) calculate search block central point and be the big rhombus at center and the mean absolute difference (MAD) on each summit of little rhombus with this point;
(b), adopt the method for progressively dwindling square region of search to carry out fine search according to the position of the minimum MAD point of determining in the step (a).
2, estimation method for quick video motion according to claim 1 is characterized in that the big rhombus summit in this method step (a) has identical predetermined step-length with little rhombus summit to central point to little rhombus summit.
3, estimation method for quick video motion according to claim 1 is characterized in that four summits of big rhombus in this method step (a) are equal to the distance of central point, and four summits of little rhombus equate to the distance of its central point.
4, estimation method for quick video motion according to claim 1 is characterized in that comprising in the described method step (b) following concrete steps:
(1) be the center with the minimum MAD point of determining in the step (a), introduce the square region of search search point of predetermined quantity, the displacement that these new search points and central point have the intended pixel distance, calculate the MAD value that institute introduces the search point, central point with introduce the position of a value point of determining to have minimum MAD in searching for;
(2) be the center with the minimum MAD point of determining in the step (1), introduce the square region of search search point of predetermined quantity, the displacement that these new search points and central point have the intended pixel distance, calculate the MAD value of the search point of introducing, introduces the position that search determines to have the value point of minimum MAD in putting in central point and institute, wherein the displacement of new search point of being introduced and central point reduces by half;
(3) be the center with the minimum MAD point of determining in the step (2), introduce the square region of search search point of predetermined quantity, the displacement that these new search points and central point have the intended pixel distance, and displacement reduces by half, calculate the MAD value of the new search point of introducing, in the position that central point and institute introduce the point of determining to have the minimum MAD value in search for putting, the displacement vector of this point is motion vector.
5, estimation method for quick video motion according to claim 1, the mean absolute difference (MAD) that it is characterized in that the point of the calculating in this method step (a) also can be the average variances (MSD) of calculation level.
6, estimation method for quick video motion according to claim 4 is characterized in that the quantity of the square region of search search point of predetermined quantity is 8.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 200610033468 CN100496130C (en) | 2006-01-26 | 2006-01-26 | Estimation method for quick video motion |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 200610033468 CN100496130C (en) | 2006-01-26 | 2006-01-26 | Estimation method for quick video motion |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101009841A CN101009841A (en) | 2007-08-01 |
| CN100496130C true CN100496130C (en) | 2009-06-03 |
Family
ID=38697916
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN 200610033468 Expired - Fee Related CN100496130C (en) | 2006-01-26 | 2006-01-26 | Estimation method for quick video motion |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN100496130C (en) |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101771870B (en) * | 2009-01-06 | 2013-06-19 | 上海中科计算技术研究所 | Quick searching method for block motion matching of video coding technique |
| CN102074017B (en) * | 2009-11-23 | 2012-11-28 | 北京工业大学 | Method and device for detecting and tracking barbell central point |
| CN101984651A (en) * | 2010-09-08 | 2011-03-09 | 北京中星微电子有限公司 | Image stabilization system, display device and method for stabilizing images |
| CN102025989A (en) * | 2010-11-05 | 2011-04-20 | 北京理工大学 | Quick searching method for digital video image movement estimation |
| CN102075748B (en) * | 2010-12-27 | 2013-12-25 | 北京自动测试技术研究所 | Search method for video coding motion estimation |
| CN102790883B (en) * | 2012-07-26 | 2015-06-10 | 中国航天科工集团第三研究院第八三五七研究所 | Image compression movement vector searching method |
| CN106331703B (en) * | 2015-07-03 | 2020-09-08 | 华为技术有限公司 | Video encoding and decoding method, video encoding and decoding device |
| CN106331722B (en) | 2015-07-03 | 2019-04-26 | 华为技术有限公司 | Image prediction method and relevant device |
| US10986209B2 (en) | 2018-04-19 | 2021-04-20 | Futurewei Technologies, Inc. | Secure and reliable on-demand source routing in an information centric network |
-
2006
- 2006-01-26 CN CN 200610033468 patent/CN100496130C/en not_active Expired - Fee Related
Non-Patent Citations (4)
| Title |
|---|
| 基于起点预测的自适应交叉-准菱形运动估计算法. 梁燕，刘文耀.光学精密工程，第13卷第2期. 2005 |
| 基于起点预测的自适应交叉-准菱形运动估计算法. 梁燕，刘文耀.光学精密工程，第13卷第2期. 2005 * |
| 用于块匹配运动估值的正方形-菱形搜索算法. 刘海峰，郭宝龙，冯宗哲.计算机学报，第25卷第7期. 2002 |
| 用于块匹配运动估值的正方形-菱形搜索算法. 刘海峰，郭宝龙，冯宗哲.计算机学报，第25卷第7期. 2002 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101009841A (en) | 2007-08-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN100496130C (en) | Estimation method for quick video motion | |
| US7099392B2 (en) | Motion vector searching method using plural search areas | |
| EP1198140A1 (en) | Method and apparatus for hybrid-type high speed motion estimation | |
| WO2002098137A1 (en) | A block motion estimation method | |
| JPH0634651A (en) | Method and device for detecting kinetic vector | |
| JP2009105950A (en) | Motion vector deriving method, motion vector deriving program, and data storage medium storing motion vector deriving program | |
| EP1389875A2 (en) | Method for motion estimation adaptive to DCT block content | |
| Chao et al. | A novel hybrid motion estimator supporting diamond search and fast full search | |
| CN103020138A (en) | Method and device for video retrieval | |
| Tedmori et al. | Hierarchical stochastic fast search motion estimation algorithm | |
| Manjunatha et al. | Comparison and implementation of fast block matching motion estimation algorithms for video compression | |
| US20050226329A1 (en) | Motion estimation method using multilevel succesive elimination algorithm | |
| KR100575733B1 (en) | Method for segmenting motion object of compressed motion pictures | |
| CN113613017B (en) | Method for improving V-PCC inter-frame prediction by three-dimensional inter-frame prediction | |
| CN110557642A (en) | Video frame coding motion searching method and image encoder | |
| Chan et al. | Adaptive partial distortion search for block motion estimation | |
| US10075691B2 (en) | Multiview video coding method using non-referenced view video group | |
| KR100451184B1 (en) | Method for searching motion vector | |
| CN108347618A (en) | Fast block motion estimation method in transmission of video | |
| US20060155701A1 (en) | Fast implementation of recursive diamond search | |
| Pal | An optimized block matching algorithm for motion estimation using logical image | |
| WO2002032145A1 (en) | A hexagon-based fast search method for block motion estimation in video encoding | |
| Wang et al. | An improve algorithm of motion compensation MPEG video compression | |
| CN111292357A (en) | Video inter-frame rapid motion estimation method based on correlation filtering | |
| CN1346216A (en) | Movement estimating method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| ASS | Succession or assignment of patent right |
Owner name: WUXI XIANGJIN COMPUTER TECHNOLOGY CO., LTD. Free format text: FORMER OWNER: AIKE CHUANGXIN MICROELECTRONIC CO., LTD. Effective date: 20120518 |
|
| C41 | Transfer of patent application or patent right or utility model | ||
| COR | Change of bibliographic data |
Free format text: CORRECT: ADDRESS; FROM: 518057 SHENZHEN, GUANGDONG PROVINCE TO: 214008 WUXI, JIANGSU PROVINCE |
|
| TR01 | Transfer of patent right |
Effective date of registration: 20120518 Address after: 214008 No. 401 Xingyuan North Road, Jiangsu, Wuxi Patentee after: Wuxi Xiang Xiang computer technology Co., Ltd. Address before: 518057, room 4, building 4, two software park, Nanshan District hi tech Zone, Shenzhen, Guangdong, 406-421 Patentee before: Aike Chuangxin Microelectronic Co., Ltd. |
|
| C17 | Cessation of patent right | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20090603 Termination date: 20140126 |