[go: up one dir, main page]

CN1125375A - Computationally-efficient method for estimating image motion - Google Patents

Computationally-efficient method for estimating image motion Download PDF

Info

Publication number
CN1125375A
CN1125375A CN95100795A CN95100795A CN1125375A CN 1125375 A CN1125375 A CN 1125375A CN 95100795 A CN95100795 A CN 95100795A CN 95100795 A CN95100795 A CN 95100795A CN 1125375 A CN1125375 A CN 1125375A
Authority
CN
China
Prior art keywords
search
unit
search unit
units
pyramid level
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.)
Granted
Application number
CN95100795A
Other languages
Chinese (zh)
Other versions
CN1117481C (en
Inventor
S·C·徐
P·阿南丹
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
RCA Licensing Corp
Original Assignee
RCA Licensing Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by RCA Licensing Corp filed Critical RCA Licensing Corp
Publication of CN1125375A publication Critical patent/CN1125375A/en
Application granted granted Critical
Publication of CN1117481C publication Critical patent/CN1117481C/en
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—2D [Two Dimensional] image generation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/503—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving temporal prediction
    • H04N19/51—Motion estimation or motion compensation
    • H04N19/53—Multi-resolution motion estimation; Hierarchical motion estimation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/20—Analysis of motion
    • G06T7/223—Analysis of motion using block-matching
    • G06T7/238—Analysis of motion using block-matching using non-full search, e.g. three-step search
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/10—Image acquisition modality
    • G06T2207/10016—Video; Image sequence

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Signal Processing (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Image Analysis (AREA)

Abstract

A block-matching method for generating motion vectors performs block matching on successively higher resolution images by refining motion vectors determined in a lower resolution image. At respective higher resolution images, search areas of limited search range are defined via a motion vector associated with corresponding image areas in the immediately lower resolution search. For at least one level of image resolution, the search blocks are overlapped to provide a plurality of search areas of limited search range for performing block matching searches for each block in the next higher resolution level.

Description

Be used to estimate the visual effective calculation method that moves
In art technology, adopt the video signal digital processor of mobile estimator as you know.This kind processor is used to provide becoming the evaluation of moving represented in the image a period of time of being defined by the digitized picture frame sequence.This kind move to be estimated such as the motion compensation coding, frame frequency conversion, and scanning changes, and it is useful reducing noise and become application such as scene analysis and target following when computer is inspected condition three dimensions.
The relevant a kind of known method estimated that moves is the units match method that adopts a kind of two-dimensional space, wherein, finishes a search by the unit with complete pixel resolution between a current image frame and the previous image frame.Just each object element of current image says that its problem is to calculate the conversion displacement for the best match unit zone in this predictive image.With regard to being enough to contain the hunting zone that the typical case moves in the TV, implement this traditional type effort searching method is that cost is expensive or unpractical.And the mobile vector that derives from the effort search may reflect accurately not that the visible object in this scene moves, so, can not promote best image compression or concealed errors.
The relevant another kind of known force method of estimating that moves adopts a kind of minute level strategy (hierarchical slralegy), wherein the full resolution image is resolved into a plurality of continuous low resolution images by the pyramid technology, then, the thick certainly extremely thin evaluation that utilizes these images to provide an image to move.Illustrated in No. the 5276513rd, United States Patent (USP) with hardware by vand der Waal and to have been implemented and allow an example that moves this kind branch level strategy of estimating to finish in real time that this patent authorizes and transfer the same assignee with the application on January 4th, 1994.In this van der Waal patent, beginning is estimated mobile vector with regard to one roughly from pyramid and the image that reduced resolution, then, the mobile vector of these rough estimate is made with extra care continuously on the image that increases resolution, at last, produce the mobile vector of its complete resolution image, this derives from pyramid and has reduced resolution image and then be made up of the pixel greater than a kind of size of maximum image displacement between the continuous pictures.Maximum image displacement between the continuous pictures at each pyramid level place is this level place ± 1 pixel.In another example of this kind branch level strategy, it is with software implementation and adopt a kind of overlapping pyramid from thick extremely thin projection scheme design, in " measuring visual mobile calculating system and algorithm " literary composition, be described, this article appears in " international computer image magazine " 2283-No. 310 (1989), with the more accurate estimation that provides image to move.To analyze the calculating of only finishing on the full resolution image obviously more effective though the branch level strategy that this kind move to be estimated moves than overstepping one's bounds level, and van der waal and above-mentioned paper are still the cost costliness to necessary the totalizing of a series of high-resolution pictures.
As known, digital electric viewing system (comprise high-resolution and standard resolution both) all needed video compression in the past with the now desired the same digitized video that transmits on the finite bandwidth video link.So, a kind of video compression encoder that can calculate the feasible and practical mobile vector of corresponding cost with enough accuracy and effective and efficient manner must be arranged.
The invention relates to a kind of mobile method of estimation of units match image that reduces computational complexity that embodies.
More particularly, this kind units match image mobile estimating method is a full resolution two-dimensional space digitized picture of response one current image frame, the previous image frame of one full resolution two-dimensional space digitlization, this, N level of image frame derived from the continuous low resolution image of pyramid now, and the N level of this previous image frame derives from the continuous low resolution image of pyramid, and N has one and is at least 2 numerical value and the current and previous image frame of each these full resolution and all constitutes one zero (0) pyramid levels herein.
The step that this method comprises for (a) should now N pyramid level of image frame be divided into a kind of a plurality of search units of first size, these search units overlap at least one of its two-dimensional space, and (b) use each these overlapping search unit, so that be used in a match search of finishing the N pyramid level of this previous image frame in the known range zone, to determine that this mobile vector presents minimum matching value with respect to this search unit about the mobile vector of the N pyramid level unit of this previous image frame.By being projected to, each (N-1) pyramid level unit defines one group of relevant N pyramid level unit on this N level.All finish repeatedly (number that number equals correlation unit) units match search with regard to each (N-1) level unit, wherein use mobile vector of each relevant N level unit to define restriction (N-1) level region of search of this each each search of repeatedly searching for.With regard to each is repeatedly searched for, should select to cause the units match of lowest error value to search in corresponding (N-1) level unit.
Fig. 1 illustrates the present technique field with schematic diagram, an example of known a kind of traditional type cell moving method of estimation, this example adopts a kind of two-dimensional space units match method, wherein finishes search by the unit with full pel resolution between a current digitized picture picture and the previous image frame calculated according to front digitized picture picture.
Fig. 2 a, 2b and 2c illustrate the 1/2nd, 1/4 and 1/8 resolution elements and the current image frame that is adopted when the full resolution search unit of Fig. 1 and the current image frame of full resolution resolved into most preferred embodiment implementing mobile estimating method of the present invention with schematic diagram together.
Fig. 3 a, 36,3c and 4 helps to illustrate the mobile estimating method step of this most preferred embodiment of the present invention.
With reference to Fig. 1, the there expression has 16 * 16 pixel full resolution unit 100 and m * n pixel resolution image 102.Unit 100 can be the square of one 16 * 16 pixel, has the x that is selected from a plurality of these type of adjacent units, the y coordinate, and the current m * n pixel full resolution image frame of a source image is divided into these adjacent units, and image 102 is aforementioned m * n pixel full resolution image frame.Occur in image between this previous image frame and the current image frame move may zero pixel (that is, still image in this space) with the pixel of a known maximum number (that is, during a single frames in this space expected maximum move) between cause image displacement on each level and the vertical direction.In the previous method of Fig. 1 illustrated, on m * n pixel image 102 unit ambient level directions ± Rx is (for example, ± 128) Ry on individual pixel and the vertical direction (for example, ± 128) finish continuous coupling successively between the inherent m of the scope of individual pixel * 16 * 16 unit of n pixel images 102 and the selected cell 100 of 16 * 16 pixels, the pixel coordinate of the unit of this m * n pixel images 102 is then corresponding to the coordinates of pixels of selected cell 100.Like this, the size of this region of search just can be R (for example, ± 128 * ± 128=65.536) individual pixel.
The matched position of this selected cell 100 is being moved an independent pixel continuously between the coupling.This matching process comprises 256 absolute values to the difference between the digital value of each corresponding pixel (or positive function of this difference) that calculate a m * n pixel images unit 102 and this selected cell 100, then, with these 256 difference additions, in the hope of a matching value (matching value of therefore trying to achieve zero can be represented a Perfect Matchings) of this coupling.Cover this kind matching process (that is, 65536 times) with regard to each the pixel matched position counterpoise among the R of this region of search and have its smallest match value with which specific Unit 16 * 16 of decision m * n pixel images 102.
Calculated x with respect to selected cell 100, m * n that y pixel coordinate has the smallest match value resembles the x that counts visual Unit 102, displacement between the y pixel coordinate (that is, mobile vector) itself provide giving birth to the accurate estimation of the visual amount of movement between this previous image frame and current image frame.Yet, in the traditional type cell moving method of estimation of Fig. 1 but be with a kind of be that cost is reached the accurate image of this kind and moved (" computational complexity " used herein is quantitatively to be defined as: for the sum of searching for all necessary calculating operations in unit divided by the number of pixels N in the whole full resolution image) estimated herein than higher computational complexity.Once " calculating operation " is defined as between two pixels under the resolution of any pyramid level and a kind of comparison that is added to the remainder of accumulator.With regard to the R scope zone of a supposition, the complexity of search equals R as possible, because each full resolution pixel of this current image all compares with the different full resolution pixels of R previous image.
The method that can further improve this kind matching process is for producing the true pixel value of calking of interpolation pixel value in the image-region that is defined in this best-of-breed element coupling.Then, in a kind of ± 1/2 pixel coverage, finish an other units match search, so that the mobile vector with half pixel resolution precision to be provided.
Minimum coupling numerical value and x with selected cell 100 of current picture, the x of the previous picture unit of y coordinate, the difference between the y coordinate has determined and the relevant mobile vector of previous picture unit with this minimum coupling numerical value.
According to Fig. 2 a, 2b, 2c, 3 and 4 for example shown in, mobile estimating method of the present invention can reduce to original about 1/720 to the computational complexity of prior art mobile estimating method shown in Figure 1, thereby, image is moved estimates to become practicality and have cost benefit.
More particularly, the present invention uses known pyramid technology that the current image frame and the previous image frame of a full resolution of one full resolution source image are resolved into a plurality of continuous low resolution image frame.Though can adopt such as passband, different pyramid patterns such as low pass and energy are for the purpose of the diagram purpose, suppose to adopt and have filter zero line coefficient 1,4,6,4, a kind of four level Gaussian pyramids of 1 (that is, level 0,1,2 and 3), because this kind Gaussian pyramid provides effective enforcement of the present invention to guarantee.
Referring now to Fig. 2 a, 2b and 2c, wherein expression has the size that is present in these pixel units and the relation between a plurality of unit, a plurality of unit are with each the indivedual pyramid level 0 in the most preferred embodiment that is used in mobile estimating method of the present invention, 1,2 and 3 should now m * n pixel full resolution image frame divided and formed.Specifically, with regard to pyramid level 0, Fig. 2 a represents a plurality of 16 * 16 pixel full resolution unit 200 of 16 * 16 pixel full resolution unit 200 (this unit is identical substantially with the said units 100 of Fig. 1) and disposed adjacent 1,1200 M/16, n/16, constitute the pyramid level 0 of current m * n pixel full resolution image frame 202 together.With regard to the pyramid level, Fig. 2 a represents a plurality of 8 * 8 pixels, 1/2 resolution elements 204 of 8 * 8 pixels, 1/2 resolution (in each space of its two-dimensional space) unit 204 and disposed adjacent 1,1204 M/16, n/16Constitute the pyramid level 1 of current m/2 * n/2 pixel 1/2 resolution image picture 206 together.With regard to pyramid level 2, Fig. 2 b represents one 8 * 8 pixel 1/4 resolution elements 208 and a plurality of 8 * 8 pixels, 1/4 resolution elements 208 1,1208 M/16, n/16One 50% overlapping (each dimension space in) configuration constitute the pyramid level 2 of current m/4 * n/4 pixel 1/4 resolution image picture 210 together.With regard to pyramid level 3, Fig. 2 c represents 8 * 8 pixels, 1/8 resolution elements 212 and a plurality of 8 * 8 pixels, 1/8 resolution elements 212 1,1212 M/32, n/3250% overlapping (in each dimension space) configuration constitute the pyramid level 3 of current m/32 * n/32 pixel 1/8 resolution image picture 214 together.Obviously, this now image pyramid level 2 and every dimension space of 3 in this image unit overlapping reach at 50% o'clock and can cause number of unit is increased to 4 times that are a kind of non-overlapped (that is, in abutting connection with) configuration of cells.
In the two-dimensional space level 2 with 3 50% overlapping only for giving an example.This kind overlaps in the two-dimensional space may be different and two-dimensional space in each overlappingly may be greater than or less than 50%.The present invention can implement promptly only to form cells overlap in a level pyramid level or in 2 levels or more multi-layered level pyramid level by laxative remedy.
At Fig. 2 a, among 2b and the 2c, each 8 * 8 pixels, 1/2 resolution elements 204 all takies the identical big or small image region the same with 16 * 16 pixel full resolution unit 200; Each 8 * 8 pixels, 1/4 resolution elements 208 all takies four times with 16 * 16 pixel full resolution unit, 200 image regions of a size; And each 8 * 8 pixels, 1/8 resolution elements 212 all takies 16 times of the size image area the same with 16 * 16 pixel full resolution unit 200.Like this, shared identical of 64 pixels of each pixel area occupied of unit 212 and unit 200; Shared identical of each pixel area occupied of unit 208 and 16 pixels of unit 200; And shared identical of 4 pixels of the shared area of each pixel of unit 204 and unit 200.
The most preferred embodiment of mobile estimating method of the present invention comprises following four steps, and now details are as follows: step 1 with these four steps:
Each overlapped elements 212 with the pyramid level 3 of current m/8 * n/8 pixel 1/8 resolution image picture 214 1,1212 M/32, n/32As a search unit, so that in a known range region R, coordinate according to this search unit, carry out this 1/8 resolution previous image angle dimension level 3 a thorough match search (that is, all the mobile search unit reaches the pixel distance of an independent pyramid level in continuous each dimension space between the coupling), determine these mobile vectors of one in mating with the search unit of the pyramid level 3 that has minimum coupling numerical value by this.Step 2:
Utilize each overlapped elements 208 of the pyramid level 2 of current m/4 * n/4 pixel 1/4 resolution image picture 210 1,1208 M/16, n/16As a search unit, so that for example a kind of limited ± 1, in ± the pixel coverage, with the pyramid level 2 of the previous image of this 1/4 resolution with finishing the P match search according to each of mobile these P match search done of one independent " optant " projection, the mobile vector corresponding to each individual elements in these P pyramid level 3 overlapped elements is moved in this independent " optant " projection, be projeced on this overlapped elements be these pyramid level 2 search units a predetermined portions (for example, its central point), so as by these pyramid level 2 search units with minimum coupling numerical value determine these the coupling in one mobile vector.Step 3:
Utilize each adjacent unit 204 of the pyramid level 1 of current m/2 * n/2 pixel 1/2 resolution image picture 206 1,1204 M/16, n/16As a search unit, in a kind of ± 1.In ± the pixel coverage, move the Q match search that each these Q match search of being done are finished the pyramid level 1 of the previous image of this 1/2 resolution together according to one independent " optant " projection, the mobile vector corresponding to each individual elements in these Q pyramid level 2 overlapped elements is moved in this independent " optant " projection, being projected on this overlapped elements is a presumptive area of this level 1 search unit, so that determine one mobile vector in these couplings by this pyramid level 1 search unit with minimum coupling numerical value.Step 4:
Utilize each adjacent unit 204 of the pyramid level 0 of current m * n pixel full resolution image frame 206 1,1204 M/16, n/16As a search unit, so that in a kind of ± 1, in ± 1 pixel coverage, pyramid level Unit 1 according to the previous image of finding to have this minimum coupling numerical value during the match search of pyramid level 1, finish an independent match search of the pyramid level 0 of the previous image of this full resolution, so that determine one mobile vector in these couplings by this pyramid level 0 search unit with minimum coupling numerical value.
Correctly not moving corresponding to this but have a low remaining displacement just when being obtained smoothness aspect mobile when mating the probability of a low resolution unit and promoting pyramid level 0 with one reducing, is desirable with the use of big range searching unit in higher pyramid level.
On the other hand, problem is the boundary line between more may the cross-over connection different moving areas of big unit, and is to provide bad coupling, especially all the more so when this unit being divided into two about equally parts.Overlapping this problem that then can make that is adopted in the step 1 and 2 reduces to minimum.This measure is absolutely true, because, may be when the unit on the border between one group of two big object that center in this image scenery of search, some unit at least of this group unit can not split into two moieties.
Step 1 is at one ± Rx/8, finishes the units match search above the displacement of ± Ry/8 pixel, is equivalent to this full resolution scope ± Rx, the hunting zone of ± Ry with covering.Like this, each units match search just needs the coupling calculating operation of R/64.The ratio of the area of full resolution pyramid level 0 pixel and the area of every pyramid level 3 pixels is 1/64., because level in the step 1 and vertical vertical cause of folding, make this ratio increase to 4 times (with regard to 50% overlapping with regard to) to 1/16 times.Like this, " computational complexity " of step 1 (according to above defined) is R/64 * 1/16=R/1024.Based on each ± Rx and ± Ry is ± the above-mentioned supposition (so that the scope region R is 65536 full resolution pixels) of 128 full resolution pixels, " computational complexity " of step 1 only is 65536/1024=64.
Fig. 3 a, 3b and 3c help to be described in more detail step 2.Fig. 3 a represents four 50% levels and the 50% vertically superposed pyramid level 3 search unit 302S of the current frame image of a pyramid level 2 search unit 300S and its corresponding group, 304S, the relation of each unit among 306S and the 308S.In Fig. 3 b, unit 302P is for finding to have that unit with respect to the previous frame image of the minimum coupling numerical value of search unit 302S at this pyramid level 3 searching periods. Same unit 304P, 306P and 308P are respectively these pyramid level 3 searching periods and find to have with respect to search unit 304S the unit of the previous frame image of the minimum coupling numerical value of the corresponding unit among 306S and the 308S.Now with the unit 302P of Fig. 3 b, 304P, it is separation each other that 306P and 308P give in Fig. 3 c being shown on the space with schematic, in the hope of being shown clearly in each pyramid level 2 unit 300P-1 of this previous picture image, 300P-2, the situation of 300P-3 and 300P-4 etc., each of these unit are all corresponding to the search unit 300S of current picture image represented among Fig. 3 a.
As among Fig. 3 c further with the signal graphic representation, pyramid level 2 unit 300P-1 have one with respect to and " candidate " mobile vector 310-1 of the search unit 300S of its associated (should " candidate " mobile vector 310-1 corresponding to the pyramid level 3 search unit 302S of current frame image shown in Fig. 3 a with shown in Figure 36 the image between the pyramid level 3 unit 302P of the previous frame image of being found during the step 1 of searching for minimum matching value by search unit 302S move)." candidate " mobile vector 310-2,310-3 or 310-4 all with a kind of similar fashion respectively with its pyramid level 2 unit 300P-2,300P-3 and 300P-4 are associated.
Fig. 3 a, 3b and 3c are applicable to " candidate " mobile vector with the aforesaid way deciding step 3 identical with relevant step 2.
Step 2, each step in 3 and 4 for example must be included in one ± 1, ± 1 pixel displacement (see figure 4) of previous relatively picture unit 400 under the resolution of this step be limited carry out the units match search in the hunting zone.Like this, one ± 1,9 an of search unit that ± 1 units match search need have the resolution of each unit in 8 other mobile units that are used in matching unit 400 itself and Fig. 4 hunting zone are mated calculating operations.
So, because the cause of employing level and vertically superposed step 1, so step 2 needs the individual coupling calculating operation in 36 (that is 9 * 4) (with regard to 50% overlapping with regard to) of unit 208, so that cover its whole hunting zone with regard to each vector in its four " candidate " mobile vectors.The ratio of the zone of one full resolution pixel and each pyramid level 2 pixel area is 1/16.But because the level that adopted and vertical both 50% overlapping in the step 2, thus make this ratio increase by 4 times to 25%, so extra " computational complexity " (as defined above) of step 2 is as 1/4 * 36=9.
If step 2 also adopts 50% level and 50% vertically superposed, then step 3 needs the individual coupling calculating operation of 36 (that is, 9 * 4) of unit 204, to cover its whole hunting zone.The area of one full resolution pixel is 1/4 times to the ratio of the area of each pyramid level 1 pixel.Overlapping owing to not having in the step 3, so ratio does not increase.So extra " computational complexity " (as defined above) of step 3, this was as 1/4 * 36=9.
Step 3 does not adopt overlapping, thereby step 4 only needs 9 coupling calculating operations of unit 200 for covering its whole hunting zone.The area of a full resolution pixel is 1 to the ratio of the area of each pyramid level 1 pixel.Overlapping owing to not having in the step 4, so this ratio does not increase.So, step 4 extra " and computational complexity " (as defined above) itself also be 9.
Though " computational complexity " of the illustrated traditional type units match of Fig. 1 mobile estimating method is 65536, step 1 to 4 whole total " computational complexities " that units match of the present invention moves the above-mentioned most preferred embodiment of assessment method are 64+9+9+9=91.Therefore, " computational complexity " that the above-mentioned most preferred embodiment of units match mobile estimating method of the present invention provides is reduced to and is a bit larger tham 720 (that is, 65536/91) with respect to the illustrated conventional elements of Fig. 1 coupling mobile estimating method.
And, can also the mode identical improve precision with the mobile vector value of the independent unit associated of the obtained minimum coupling numerical value of the step 4 that is found most preferred embodiment with units match moving method of the present invention with the aforesaid way that moves estimation about the illustrated traditional type units match of Fig. 1.
This paper is not intended to the present invention is limited to a kind of special parameter of most preferred embodiment of said units matching images mobile estimating method.But the present invention is extensible for adopting principle of the present invention, to reduce any units match image mobile estimating method of " computational complexity ".

Claims (16)

1. units match image mobile estimating method, full resolution two-dimensional space digitized picture in response to a current image frame, the previous image frame of one full resolution two-dimensional space digitlization, the N level derives from the continuous low resolution image of the described current image frame of pyramid, and the N level derives from the continuous low resolution image of the described previous image frame of pyramid, here N is a positive integer, and described full resolution is current and previous image frame in each image frame all constitute a null value (0) pyramid level, described method is characterised in that and may further comprise the steps:
A) (M≤N) is divided into a plurality of search units (302S-308S) of first size, and these search units (302S to 308S) are all superimposed at least one dimension space of described two-dimensional space with M pyramid level of described current image frame; And
B) use each described overlapping search unit (302S to 308S), for being used in one of the M pyramid level of finishing described previous image frame on known range zone match search (302P to 308P), with the mobile vector of decision to the described M pyramid level unit of described previous image frame, this mobile vector shows minimum coupling numerical value with respect to this search unit.
2. described method as claimed in claim 1 is characterized in that further comprising the steps of:
C) (M-1) pyramid level with described current image frame is divided into a plurality of second search units that are not more than a described size; And
D) the unit X of the described M level of decision, one of one second search unit presumptive area is projeced on this unit;
E) utilize corresponding mobile vector with regard to each described unit X, with a restricted hunting zone X region of search in the decision level (M-1);
F) finish the units match search and select this units match search with regard to each the described region of search in the level (M-1), to produce a minimum error numerical value of described second search unit.
3. according to the described method of claim 2, it is characterized in that described a plurality of search units of described first size have 50% to overlap in two spaces of described two-dimensional space substantially.
4. according to the described method of claim 2, it is characterized in that:
The numerical value of N is 3;
This M pyramid level is that the 3rd pyramid level and (M-1) pyramid level are the 2nd pyramid level.
5. method according to claim 4 is characterized in that step (c) comprises that the 2nd pyramid level with current image frame is divided into a plurality of described second search units, and these second search units are superimposed at least one space of described two-dimensional space.
6. according to the described method of claim 5, it is characterized in that described a plurality of search units of described first size and described a plurality of described second search unit all have 50% to overlap in two spaces of described two-dimensional space substantially.
7. according to the described method of claim 6, it is characterized in that described first size described search unit be shaped as rectangle, and wherein:
Step (c) comprises that the 2nd pyramid level with described current image frame is divided into a plurality of rectangle second search units, and each space that each second search unit has is substantially half of corresponding space size of a search unit of described first size.
8. method according to claim 5 is characterized in that further comprising the steps of:
G) the first pyramid level with described current image frame is divided into a plurality of the 3rd search units, the size of these the 3rd search units all is not more than described second search unit, and each described the 3rd search unit all is projected on described overlapping second search unit of described current image frame; And
H) utilization known units one of in described the 3rd search unit, for the first module that is used in the described second pyramid level it ± 1, carry out in the independent match search in ± 1 scope, the described known units of described the 3rd search unit is projeced on the unit of this second pyramid level, wherein each independent match search all utilizes the mobile vector that is associated with a different units in the described second pyramid level unit to decide all described ± 1 of described independent match search, one of independent unit of ± 1 scope improved (refined) mobile vector, this mobile vector present with the minimum coupling numerical value in the coupling sum of being finished with respect to one of in described the 3rd search unit unit.
9. described method according to Claim 8 is characterized in that further comprising the steps of:
I) each described the 3rd search unit is used as described known units in described the 3rd search unit.
10. described method according to Claim 8 is characterized in that described a plurality of search units of described first size and described a plurality of described second search unit are substantially in 50% two spaces that overlap in the described two-dimensional space.
11. according to the described method of claim 10, it is characterized in that the search unit of described a plurality of described first sizes and the shape of described a plurality of described second search units are rectangle, and wherein:
Step (c) comprises that the second pyramid level with described current image frame is divided into a plurality of rectangle second search units, and each described second search unit has half of corresponding space size that each space is substantially one of described first size search unit; And
Step (g) comprises the 3rd search unit that the first pyramid level of described current image frame is divided into a plurality of rectangles, and the space separately that each described the 3rd search unit has is roughly half of corresponding space size of second search unit.
12. described method according to Claim 8 is characterized in that further comprising the steps of:
J) 0 pyramid level with described current image frame is divided into a plurality of the 4th search units, and the size of described the 4th search unit is not more than described the 3rd search unit; And
K) utilization known units one of in described the 4th search unit, with one ± 1 of each unit of the described 0 pyramid level that is used in described previous image frame, finish in the match search in ± 1 scope, ± 1 described to determine, the improvement mobile vector of the independent unit of ± 1 scope, this improvement mobile vector present the minimum coupling numerical value with respect to one of described the 4th search unit unit.
13. method according to claim 12 is characterized in that further comprising the steps of:
1) adopt each described the 4th search unit as the described known units in described the 4th search unit.
14. according to the described method of claim 12, it is characterized in that described a plurality of search units of described first size, the shape of described a plurality of described second search units and described the 3rd search unit all is a rectangle, and wherein:
Step (c) comprises that the 2nd pyramid level with described current image frame is divided into a plurality of rectangle second search units, and the space separately that each described second search unit has is half of corresponding space size of the search unit of described first size substantially;
Step (g) comprises that the 1st pyramid level with described current image frame is divided into a plurality of rectangle the 3rd search units, and the space separately that each this 3rd search unit has is half of the corresponding space of one second search unit size substantially; And
The 0 pyramid level that step (j) is included as described current image frame is divided into a plurality of rectangle the 4th search units, make space separately that each this 4th search unit had substantially with one the 3rd equal-sized step in the corresponding space of search unit.
15. according to the described method of claim 14, it is characterized in that the described the three, the second and the resolution of the first pyramid level be respectively 1/8,1/4 and 1/2 of in every dimension space of its two-dimensional space full resolution 0 pyramid level.
16. method according to claim 14, it is characterized in that the described the 3rd, each unit in the second and first pyramid level search unit includes the unit of 8 * 8 pixels of this pyramid level, and described 0 pyramid level search unit comprises the unit of 16 * 16 pixels of described 0 a pyramid level.
CN95100795A 1994-02-23 1995-02-22 Computationally-efficient method for estimating image motion Expired - Fee Related CN1117481C (en)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US200,599 1988-05-31
US20059994A 1994-02-23 1994-02-23
US200599 1994-02-23

Publications (2)

Publication Number Publication Date
CN1125375A true CN1125375A (en) 1996-06-26
CN1117481C CN1117481C (en) 2003-08-06

Family

ID=22742388

Family Applications (1)

Application Number Title Priority Date Filing Date
CN95100795A Expired - Fee Related CN1117481C (en) 1994-02-23 1995-02-22 Computationally-efficient method for estimating image motion

Country Status (5)

Country Link
US (1) US5742710A (en)
JP (1) JPH07262381A (en)
KR (1) KR100362038B1 (en)
CN (1) CN1117481C (en)
TW (1) TW321748B (en)

Families Citing this family (58)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2742248B1 (en) * 1995-12-06 1998-01-23 Thomson Multimedia Sa METHOD FOR PROCESSING DATA IN MATRIX NETWORKS IN A MOTION ESTIMATION SYSTEM
JP3631868B2 (en) * 1996-12-20 2005-03-23 株式会社東芝 Motion vector detection apparatus and method
JPH10210473A (en) * 1997-01-16 1998-08-07 Toshiba Corp Motion vector detection device
US6332002B1 (en) * 1997-11-01 2001-12-18 Lg Electronics Inc. Motion prediction apparatus and method
US6611287B1 (en) * 1997-11-28 2003-08-26 Sony Corporation Camera signal processing apparatus and camera signal processing method
US6259737B1 (en) * 1998-06-05 2001-07-10 Innomedia Pte Ltd Method and apparatus for fast motion estimation in video coding
US6459822B1 (en) * 1998-08-26 2002-10-01 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration Video image stabilization and registration
KR100457065B1 (en) * 1998-12-29 2005-05-19 주식회사 대우일렉트로닉스 Motion vector generator for video signals
KR20000044735A (en) * 1998-12-30 2000-07-15 전주범 Motion estimator
SG89282A1 (en) 1999-05-28 2002-06-18 Kent Ridge Digital Labs Motion information extraction system
US6842483B1 (en) 2000-09-11 2005-01-11 The Hong Kong University Of Science And Technology Device, method and digital video encoder for block-matching motion estimation
US6785427B1 (en) * 2000-09-20 2004-08-31 Arcsoft, Inc. Image matching using resolution pyramids with geometric constraints
US6941018B2 (en) * 2001-03-23 2005-09-06 Glory Ltd. Method of and apparatus for searching corresponding points between images, and computer program
EP1259079B1 (en) * 2001-04-30 2007-03-21 STMicroelectronics Pvt. Ltd An efficient low power motion estimation of a video frame sequence
KR100446235B1 (en) * 2001-05-07 2004-08-30 엘지전자 주식회사 Merging search method of motion vector using multi-candidates
FI110745B (en) * 2001-11-13 2003-03-14 Hantro Products Oy Encoding successive images has reference image divided into parts which includes 4x4 pixels referred to with indexes and number is formed from the values of pixels in each part to describe pixel values in a given part
US7400782B2 (en) * 2002-08-28 2008-07-15 Arcsoft, Inc. Image warping correction in forming 360 degree panoramic images
US7983446B2 (en) * 2003-07-18 2011-07-19 Lockheed Martin Corporation Method and apparatus for automatic object identification
US7409105B2 (en) * 2003-10-22 2008-08-05 Arcsoft, Inc. Panoramic maker engine for a low profile system
US7346109B2 (en) * 2003-12-23 2008-03-18 Genesis Microchip Inc. Motion vector computation for video sequences
US7463778B2 (en) * 2004-01-30 2008-12-09 Hewlett-Packard Development Company, L.P Motion estimation for compressing multiple view images
US7382915B2 (en) * 2004-03-16 2008-06-03 Xerox Corporation Color to grayscale conversion method and apparatus
FR2868579A1 (en) * 2004-03-30 2005-10-07 St Microelectronics Sa METHOD AND DEVICE FOR GENERATING CANDIDATE VECTORS FOR IMAGE INTERPOLATION SYSTEMS BY ESTIMATION AND MOTION COMPENSATION
JP4640338B2 (en) * 2004-08-23 2011-03-02 ソニー株式会社 Imaging apparatus, imaging result processing method, and integrated circuit
KR100677562B1 (en) * 2005-02-03 2007-02-02 삼성전자주식회사 Motion estimation method and apparatus
US20060215036A1 (en) * 2005-03-25 2006-09-28 Multivision Intelligent Surveillance (Hk) Ltd. Method and apparatus for video stabilization
DE102006030990A1 (en) * 2005-11-14 2007-05-16 Univ Muenster Wilhelms A method and apparatus for monoscopically displaying at least a portion of an image on an autostereoscopic display device
US8085849B1 (en) * 2006-11-03 2011-12-27 Keystream Corporation Automated method and apparatus for estimating motion of an image segment using motion vectors from overlapping macroblocks
EP2102805A1 (en) * 2006-12-11 2009-09-23 Cinnafilm, Inc. Real-time film effects processing for digital video
US8233748B2 (en) * 2007-07-20 2012-07-31 Samsung Electronics Co., Ltd. Image-resolution-improvement apparatus and method
KR101354899B1 (en) * 2007-08-29 2014-01-27 삼성전자주식회사 Method for photographing panorama picture
WO2009087493A1 (en) 2008-01-11 2009-07-16 Zoran (France) Sparse geometry for super resolution video processing
US8175160B1 (en) * 2008-06-09 2012-05-08 Nvidia Corporation System, method, and computer program product for refining motion vectors
US7983512B2 (en) * 2008-06-24 2011-07-19 Microsoft Corporation Embedding large images within one another
US8064733B2 (en) * 2008-06-24 2011-11-22 Microsoft Corporation Variable resolution images
US7933473B2 (en) * 2008-06-24 2011-04-26 Microsoft Corporation Multiple resolution image storage
US20100026897A1 (en) * 2008-07-30 2010-02-04 Cinnafilm, Inc. Method, Apparatus, and Computer Software for Modifying Moving Images Via Motion Compensation Vectors, Degrain/Denoise, and Superresolution
AT509025B1 (en) * 2009-01-21 2013-07-15 Arc Austrian Res Centers Gmbh METHOD FOR DETERMINING THE POSITIONS OF PASSPORTS
JP5141633B2 (en) * 2009-04-24 2013-02-13 ソニー株式会社 Image processing method and image information encoding apparatus using the same
JP5683153B2 (en) * 2010-07-09 2015-03-11 キヤノン株式会社 Image processing apparatus and image processing method
US8891626B1 (en) 2011-04-05 2014-11-18 Google Inc. Center of motion for encoding motion fields
EP2727357A1 (en) 2011-07-01 2014-05-07 Motorola Mobility LLC Motion vector prediction design simplification
US9185428B2 (en) 2011-11-04 2015-11-10 Google Technology Holdings LLC Motion vector scaling for non-uniform motion vector grid
TW201328359A (en) * 2011-12-19 2013-07-01 Ind Tech Res Inst Moving object detection method and apparatus based on compressed domain
US9762904B2 (en) 2011-12-22 2017-09-12 Qualcomm Incorporated Performing motion vector prediction for video coding
US8908767B1 (en) 2012-02-09 2014-12-09 Google Inc. Temporal motion vector prediction
ITVI20120087A1 (en) * 2012-04-17 2013-10-18 St Microelectronics Srl DIGITAL VIDEO STABILIZATION
US9172970B1 (en) 2012-05-29 2015-10-27 Google Inc. Inter frame candidate selection for a video encoder
US11317101B2 (en) 2012-06-12 2022-04-26 Google Inc. Inter frame candidate selection for a video encoder
US9485515B2 (en) 2013-08-23 2016-11-01 Google Inc. Video coding using reference motion vectors
US9503746B2 (en) 2012-10-08 2016-11-22 Google Inc. Determine reference motion vectors
US9313493B1 (en) 2013-06-27 2016-04-12 Google Inc. Advanced motion estimation
US9305362B1 (en) * 2014-02-28 2016-04-05 Xilinx, Inc. Image stabilization
KR102564477B1 (en) * 2015-11-30 2023-08-07 삼성전자주식회사 Method for detecting object and apparatus thereof
CN108230294B (en) * 2017-06-14 2020-09-29 北京市商汤科技开发有限公司 Image detection method, image detection device, electronic equipment and storage medium
IL271770B2 (en) * 2017-06-30 2024-03-01 Huawei Tech Co Ltd Search area for motion vector refinement
WO2021193648A1 (en) * 2020-03-25 2021-09-30 株式会社ソニー・インタラクティブエンタテインメント Image processing device and server
US12112451B2 (en) 2020-03-25 2024-10-08 Sony Interactive Entertainment Inc. Image processing apparatus and server

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4674125A (en) * 1983-06-27 1987-06-16 Rca Corporation Real-time hierarchal pyramid signal processing apparatus
US4703514A (en) * 1985-09-16 1987-10-27 Rca Corporation Programmed implementation of real-time multiresolution signal processing apparatus
EP0285902A3 (en) * 1987-04-07 1990-10-10 Siemens Aktiengesellschaft Method for the data reduction of digital picture sequences
DE3851786T2 (en) * 1987-06-09 1995-03-09 Sony Corp Selection of a motion vector in television pictures.
FR2623955B1 (en) * 1987-11-27 1990-04-27 Labo Electronique Physique METHOD AND DEVICE FOR ESTIMATING AND COMPENSATING MOTION IN AN IMAGE SEQUENCE AND THEIR APPLICATION IN A HIGH DEFINITION TELEVISION IMAGE TRANSMISSION SYSTEM
FR2633468B1 (en) * 1988-06-24 1990-11-09 France Etat METHOD OF ENCODING ASSISTANCE DATA FOR THE RECONSTRUCTION OF SUB-SAMPLE ANIMATED ELECTRONIC IMAGES
JPH0385884A (en) * 1989-08-29 1991-04-11 Sony Corp Image movement detecting circuit
FR2651399B1 (en) * 1989-08-29 1996-05-15 Thomson Consumer Electronics METHOD AND DEVICE FOR ESTIMATING AND HIERARCHIZED CODING OF THE MOTION OF IMAGE SEQUENCES.
JPH03117991A (en) * 1989-09-29 1991-05-20 Victor Co Of Japan Ltd Encoding and decoder device for movement vector
US4937666A (en) * 1989-12-04 1990-06-26 Bell Communications Research, Inc. Circuit implementation of block matching algorithm with fractional precision
FR2663178B1 (en) * 1990-06-06 1995-07-21 Thomson Csf METHOD FOR HIERARCHICAL ESTIMATION OF MOTION IN A SEQUENCE OF IMAGES.
JP2549479B2 (en) * 1991-12-06 1996-10-30 日本電信電話株式会社 Motion compensation inter-frame band division coding processing method
US5276513A (en) * 1992-06-10 1994-01-04 Rca Thomson Licensing Corporation Implementation architecture for performing hierarchical motion analysis of video images in real time

Also Published As

Publication number Publication date
TW321748B (en) 1997-12-01
KR100362038B1 (en) 2003-03-04
US5742710A (en) 1998-04-21
JPH07262381A (en) 1995-10-13
KR950033960A (en) 1995-12-26
CN1117481C (en) 2003-08-06

Similar Documents

Publication Publication Date Title
CN1117481C (en) Computationally-efficient method for estimating image motion
EP2101486B1 (en) Image processing apparatus and image processing method
CN1106768C (en) Method and apparatus for detecting motion vectors
US20090257498A1 (en) Image processing apparatus and image processing method
EP0395275A2 (en) Motion dependent video signal processing
JPH06506578A (en) Method for estimating motion content in video signals
US5012337A (en) Motion dependent video signal processing
JP3448868B2 (en) Image coincidence detecting device and image coincidence detecting method
EP0628234B1 (en) Motion compensated video image processing
JPH0935061A (en) Image processing method
US4998168A (en) Motion dependent video signal processing
JPWO1995004329A1 (en) Image match detection device and image match detection method
US5012336A (en) Motion dependent video signal processing
EP0395272B1 (en) Motion dependent video signal processing
EP1131955B1 (en) Method of global motion estimation
CN1723476A (en) Method and apparatus for depth sorting of digital images
US7110453B1 (en) Motion or depth estimation by prioritizing candidate motion vectors according to more reliable texture information
KR0178229B1 (en) Image processing apparatus using pixel-based motion estimation based on feature points
EP0367310B1 (en) Picture motion measurement
Barreto et al. Motion estimation techniques in super-resolution image reconstruction: a performance evaluation
KR0178230B1 (en) Image processing system using a feature point-based motion estimation
JPH0918685A (en) Image composition method
Farin et al. Enabling arbitrary rotational camera motion using multisprites with minimum coding cost
JPH0646383A (en) Apparatus and method for analysis of motion of animation
JPH1013835A (en) Motion vector detecting methd

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
C17 Cessation of patent right
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20030806

Termination date: 20130222