Title of Invention

APPARATUS FOR DETERMINING A MOTION VECTOR

Abstract An apparatus for determining a motion vector between a current frame and its reference frame of video signals comprises a search region formation section 22, candidate block formation sections 24-1 to 24-n and block matching sections 26-1 to 26-n for motion-estimating a search block with respect to its corresponding search region to thereby generate an error function and a displacement vector for each of the candidate blocks included in the corresponding search region; a comparator 28 and a multiplexer 29 for generating a multiple number of candidate motion vectors based on the error functions; a motion compensation block 31 and difference generators 32-1 to 32-M, responsive to the candidate motion vectors, for providing error signals of said multiple number; transform blocks 34-] to 34-M for obtaining transform data consisting of a corresponding multiple number of sets of transform coefficients by transforming each of the error signals into a set of transform coefficients; and a motion vector determining block 36-1 to 36-M, 38 and 39 for determining a motion vector for the search block based on the transform data.
Full Text Field of the Invention
The present invention relates tc a method and apparatus for determining notion vectors; and, nore particularly, to an improved method and apparatus for determining motion vectors through the use of temporal correlationship between the frarr.es and spatial correlationship between pixels of a notion compensated block signal.
Background of the Invention
Transmission of digitized video signals can deliver video images of nuch higher quality than thti transmission.of analog signals. When an image signal comprising a sequence of image "frame" is expressed ir. a digital form, a substantial amount of data is generated for transmission, especially in the case of a high definition televieion(HDTV) system. Since, however, the available frequency bandwidth of a conventional transmission channel is limited, in order to transmit the substantial amounts of digital data through the limited channel bandwidth, it is necessary to compress or reduce the; volume of the transmission data. Among various video compression techniques, the so-called hybrid coding technique,

-2-
which combines temporal and spatial compression techniques together with a statistical coding technique, is known to-be most effective.
Most hybrid coding techniques employ a motion compensated DPCM(differentiai pulse code modulation), two-dimensional DCT(di3crete cosine transform) , quantization of E>CT coefficients, and VLC(variable length coding). The motion compensated D?CM is a process of determining the movement of an object between a current frame a:id ita reference, e.g. , previous frame, and predicting the cu::rent frame according to the motion flow of the object to produce a differential signal representing the difference between tie currant frame and its prediction.
The two-dimensional DCT, which reduces or removes spatial redundancies between image data such as motion compensated DPCM data, converts a block of digital image data, for example, a block of'8x8 pixels, into a set of DCT coefficient data. This technic is described in Chen and Pratt, "Scene Adaptive Coder", IEEE Transactions on Communications, COM-32, =N0.3, pp.225-231 (March 1984). By processing such DCT coefficient data with a quantizer, zig2ag scanning,and VLC, the amounts of data to be transmitted can be effectively
compressed.
Specifically, in the motion compensated DPCM, a current frame data is predicted from a reference frame data based or. an estimation of the motion between the current and the

-3-
previous frames, e.g., through the use of a block matching algorithm (see, e.g., J.R. Jain et al., 'Displacement Measurement and Ics Application in interframe Image Coding", IESE Transactions of Communications, COM-29, No.12, pp.1799-1808 (December 1981)). Such estimated motion may be described in terns of two dimensional motion vsctors representing the displacement of pixels between the reference and the current frames.
According to the block matching algorithm, a current frame i& divided into a plurality of search blocks. The size of a search block typically ranges between 8x8. and 32x32 ¦ piuoie. To ciaT-oT^ina A nnt-fnn xTt^rtn" far A, xfi-a.TT$i.h,lr>ck, in the current frame, a similarity calculation is performed between the search block of the currant frame and each of a plurality of equal-sized candidate blocks included in a generally larger search region withir. a reference frame, hxi error is used to carry out a similarity measurement between the search block of the current fram and each of the candidate blocks in the search region. And a motion vector, by definition, represents a displacement between the search block "d a candidate block which yielda a aialaum ariror
function.
Although such a iciniaum error reflects a maximized
teirtporal cross-correlatior. between the search block and; a candidate block which yields a motion vector, it may not.

-4-
optimize the spatial correlation bettfeen pixels of an error signal provided by the motion compensated D?CM.
Summary of the Invention
It is, therefore, a primary object of the present invention to provide an improved method and apparatus for providing an optimum motion vector by employing a similarity measurement between a search block ar.d each of the candids.te blocks within a corresponding search region along with a spatial correlation measurement between pixel data in each of error signals generated from the search block and candidate blocks which are selected based on the similarity measurement.
A method for determining a motion vector between a current frame and i-cs reference frame of video signals, wherein the current frame is dividud into a plurality of search blocks of an identical size and the reference frame includes a corresponding number of search regions, each search region further including a multiplicity of candidate blocks of said identical size, which comprise the steps of :
motion-estimating a search block with respect to its corresponding search region to thereby select a multiple number of candidate blocks among the candidate blocks included in the corresponding search region, wherein said selected candidate blocks have error functions not larger than error functions of the unselected candidate blocks included in the

-5-corresponding search region;
generating error signals, each of which represents " a difference of pixel data between the Mearch block and each of the selected candidate blocks; .-
transforming each of the error signals into a. set of transform coefficients, to thereby provide a multiple number of sets of transform coefficients;
selecting an optimum error signal based on the sets of tranaform coefficients provided in said step (c); and
determining a motion vector for the search block, the motion vector representing a- displacement of pixels between the search block and a candidate bio:* which corresponds to said optimum error signal.
Brief Description of the Drawing
The above and other objects and features of the present invention will become apparent from the following description of preferred embodiments given in conjunction with the accompanying drawings, in which;
Fig.: Illustrates a bloc diagram of an apparatus for compressing an input digital video signal in accordance with
the invention;
Fig.2 depicts a block diagram of a candidate motion
vector determinates showr. in Fig.l.; and
Fig.3 represents a block diagram of an optimum motion

-6-
vector determinator shown in Fig.l.
Detailed Description of the Preferred ^hndimenta
Referring to -he Fig. I, there is shown a block diagram oi: an apparatus for compressing an inpvc digital video signal, which comprises a- motion estimator 15 of the pres"nt. invention wherein the motion estimator 15 includes e candidate motion vector determir.ator 20 and an optimum mot-or. vector determinator 30.
A current frame of an input digital video signal is tfec to the motion vector determinates 20 and 30 end a subtractox 10. Actually, the current frame vid"io signal is stored in an input memory (not shown), wherein the current frame ia divided into a plurality o£ search blocks, which are sequentially retrieved therefrom on a block^by-block basis, tha size of, a search blocic typically raging from 8x8 to 32x32 pixels. At the candidats motion vector determinatcr 20 of the peasant invention, a motion estimation is carried out, through the use
of the conventional block matching algorithm, between a jearcb OIOCK o£ tne current frame and each of the candxdata bj.ocKs
within a corresponding search regior. of a reference, e.g., previous, frame provided from a fra?ie memory 95, Outputs
from the candis-"*; motion vector determinator 20' to the optimum notion vector determinator 30 are a predetermined number of candidate motion vectors. -The optimum motion vector

-7-
determinator 30 selects one of the candidate motion vectore. and provides as a .-notion vector of the search block, the selected optimum motion vector no a notion compensator Details of the motion vector determinators 20 and 30 will be described hereinaf-er with respect to Figs. 2 and 3.
in response to the motion vector from the optimum motion vector dezerninator 30, a prediction signal, i.e., pixel data of the candidate block corresponding to the motion vector, is retrieved from the frame memory 95 and provided to the subtractor 10 and an adder 90 by the motion compensator 50.
The prediction signal from the motion compensator 50 is substrated from -he search block of the input digital video signal at subtractor 10; and the resultant data, i.e., an error signal or a notion compensated block signal, is dispatched to a transform section 60. At transform section 60, thd error signal is encoded in to a set of transform coefficients by using, e.g., th.i DCTfdiscrete cosine transform).
At a quantizer 70, the set of transform coefficients from the transform coder SO are quantized into a set of quantized transform coefficients which ie subsequently fed to a VLC . coder 7 5 and an inverse quantizer 80 At the VLC coder 75, the data received from the quantizer 70 is converted into a set of variable length coded data. The set of quantized transform coefficients are converted back to a set of transform coefficients at the inverse quantizer 80. The set.

-8-
of transform coefficients is then applied to an inverse transform section 85 and transformed therein into a block'of pixel data. At the adder 90, prediction signal, from the motion compensator 5 0 and the block of pixel data from inverse transform section 85 are sununed to provide a reconstructed block signal of the search block to bs written onto the frame memory 95. The frame memory 95 has two frame memory locations storir.g the current and the previous frame data. The output signal from the adder 90 comprises blocks of pixel data. When all of the blocks representing the current frame e>re stored in the frame memory 95., new frame data is provided from thd adder 90. At this moment, the new data is referred to as a current frame and the curren- frame data previously stored in the frame memory 95 is referred to as the previous frame. The encoded data from the VLC coder 75 is supplied to the transmitting end{not shown) for data transmission.
Referring to Fig.2, there is shown a detailed block diagram of the candidate motion vector detenr.inator 20 shown in Fig. 1. The previous frame signal stored in the £rs.me memory 95 shown Fig. I is applied to a search region formation section 22 The search region formation section 22 defines a corresponding search region to the search block with a certain _. si2e, shape and search pattern, whereby the motion, estimation of ^he search block is carried out. After the search region' is determined at tf.e search region fcrmation section 22, the search region data is applied to caididate block formation

-9-
sections 24-1 co 24-r.. There may oe a multiple number of candidate block formation sections; h owever, only 3 sections are depicted for the sake of simplicity. At each of candidate block formation sections 24-1 to -24-r., a candidate block of an identical size to that of the search block is generated within the search region; and pixel data of each candidate block is outoutted -herefrom to each of block matching sections 26-1 to 2 6-n. The relative displacements of tie candidate blocks from the location of the search block of ths current frame are also outputtecl from candidate block formation sections 24-1 to 24-r. to a comparator 2 8 and a multiplexer 29 as displacement vectors DV (24-i) to (2 4-n), respectively.
At each of the block matching sections 26-1 to 26-n, an error func-ior. is calculated betweun the pixel data of the search block of the current frame ar.ci the pixel data of the candidate block from each of the candidate block formation sections 24-1 to 24-r., wherein the MJE(mean square error) or the MAS (mean absolute error) i.s calculated between corresponding pixels in the search fclock and the candidate block to yisld trie error function tor that candidate block. The error function indicates the degree of similarity between the search block and the c.^^dide^e block.
All ^he error functions from the block matching sections . 2 6-1 to 25-n are applied to the comparator 28, The
comparator 2 3 compares the error functions and selects there:rom M number of error functions, and outputs to the

-10-
multiplexer 29 a first selection signals which indicates candidate blocks corresponding tc the selected error functions, M beir.g an integer larger than 1, wherein the seleted error functions includes' a laast error function and are selec-ed in a.- ascending order of their magnitude. In case, there exist more ~han one error functions having ar. identical magnitude, the select io;: is carried out by considering their corresponding displacement vectors in accordance with the present invention, that is, if there are one error functions of the minimum magnitude and four error functions of a second minimum magnitude while M is 4, displacement vectors corresponding to the four error functions are compared each other and three erro.- functions are selected out of four in an ascending order of their corresponding displacement vectors.
In response to the first selection signal, the multiplexer 29 then chooses each of the displacement vectors of the candidate blocks, which corrsspond to the selected error functions and sequentially provides, as candidate motion vectors MV(29-l) LO HV(29-M) for the search block, the chosen displacement vsctcrs to the optimum monion vector determinacor-"
30 * shown in Fig.1.
Referring zo Fig. 3, tr.ere is illustrated a detail block diagram of -he optimum motion vector ceterminator 30 shown ir. Fig.l. The candidate mo-ior. vectors MV(29-1) to MV(29-M) fram che multiplexer 29 showr. in Fig. 2 are fed to a motion

_ 1 1 _
compensation block 31, a comparator ;!8 and a multiplexer -'A 9 . The motion compensation block 31 rezrieves, iron the frame memory 95 show- in Fig.1, the candidate blocks which correspond to the cendidate motion vectors. The retrieved candidate block signals are fed to difference generator 3J-1 to 32-M, respectively.
Meantime,, the search block data of the input digital video signal is applied to the difference generators 32-1 to 32-M, simultaneously. At each of the difference generators, an error signal or a motion compensated block signal is calculated between the search block data ar.d each candidate block signal from the motion compensation block 31 in a similar manner as in the subtractor 10 shown in Fig.l
The error signals from the difference generators 32-1 to 32-M are applied to transform blocks 34-1 to 34-M, respectively. At each of the transform blocks, an error signal is converted into a set of transform coefficients by using, e.g., DCT in an identical fashion as in the transform section 60 shown in Fig. 1. The respective sets of transform coefficients frora the transform blocks 34-1 to 34-M are then applied to absolute value calculators 36-1 to 36-M.
3ach of the iisolute value calculators calculates a sum of the absolute values of the transform coefficients in a set and provides the calculated sum of the absolute values for each get to a comparator 39.
The comparator 38 comnares the fiujns from the absolutes

-12-
value calculator* 36-1 to 36-M and selects cherefrom a sun of a least magnitude, thereby providing the multiplexer 39 with, a second selection signal designating a candidate mot:.or. vector corresponding to the selected sum. If two or more SUIHE have the least value, the comparator 38 compares magnitude of candidate motion vectors corresponding to -he two ro more
vector having a least magnitude.
The multiplexer 39 then chooses,as an optimum motion vector, s candidate motion vector of the candidate block, which corresponds to the sum of the least absolute value, thereby providing the optimum motion vector ae the motion vector of the search block to the motion comparator 5 0 shewn in Fig.l.
While the present invention has seen shown and described with respect to the particular eirbodiments, it will be apparent to those 3killed in the art; that many changes and modifications nay be made without departing from the spirit and scope of the invention as defined in the appended claims.

-13-WE CLAIM :
1. A method for determining a notion vector between a current frame and its reference frame of video signals, wherein the current frame is divided into a plurality of search blocks of an identical size and the reference frame includes a corresponding number of search regions, each search region further including a multiplicity of candidate blocks of said identical size, which comprises the steps of :
(a) motion-estimating a search block with respect to its
corresponding search region to thereby select a multiple
number of candidate blocks among the candidate blocks included
in the corresponding search region, wherein said selected
candidate blocks have error functions not larger than error
functions of the unaelected candidate blocks included in the
corresponding search region;
(b) generating error 3ignals, each of which represents, a
difference of pixel data between the search block and each of
the selected candidate blocks;
(c) transforming each of the error signals into a set of
transform coefficients, to thereby provide a multiple number
of sets of transform coefficients;
(d; selecting an optimum error signal based on the sets of transform coefficients provided in said step (c); and
(e) determining a motion vector for the search block, the motion vector representing a displacement of pixels between

-14-
the search block and a candidate block which corresponds.to said optimum error signal.
2. The method according to claim 1, further comprising1,
after step(e), the step of :
(f) repeating said steps (a) to (e) with respecr to each
of the remaining search blocks within the current frame.
3. The method according zo claim 1, wherein said step (d)
includes the steps of :
(dl) calculating a sum of absolute values of the
transform coefficients in each eet;
(d2) selecting a sum of a least value; and
(d3) choosing an error signal corresponding to the
selected sum of the least value as the optimum error signal.
4. The method according to claim 3, wierein each of the error
functions is a mean absolute error.
5. The method according to claim 3, wherein each of the
error functions is a mean square error.
6. The method according zo claim 3. wherein said s-ep (a)
includes the steps of :

-15-
function and a displacement vector for each of the candidate blocks included in the corresponding search region, thrs displacement vector representing a displacement of. pixels between the search block and gaid each of the candidate block3; ar.d
(a2) selecting the multiple nuriber of candidate blocks and providing displacement vectors fcr the selected candidatee blocks as candidate mozion vectors/ none of the er:ror functions for said selected candidate blocks being greater than an error function for any unsslected candidate blocV within the corresponding search region.
7. The method according to claim 5, wherein the selectee
candidate blocks are determined 3uch t.hat if an error function
for a selected candidate block equals to any one of the error
functions for the undeleted candidate blocks, a magnitude of
a displacement vector for said selected candidate block is rot
greater than that of said any one of the error functions.
8. The method according zo claim 6, wherein said step includes the s-ep of :
(d2i) if only one sum has -he least value, selecting said only one sum as the sum of the least value and if two or more sums have -he least value, detecting a candidate motion vector of a minimum magnitude among candidate motion vectors corresponding to said two or more sums thereby select a sum

-16-
corresponding to the detected car.cicaze motion vector as the
sum of the least value.
9. 'The method accoriding to claim 8, wherein said reference
frame is a preceding frame of the current frame.
10. Ar. apparatus for determining a motion vector between a
current frame and its reference frame of video signals,
wherein the current frame is divided into a plurality oil
includes a corresponding number of search region, each search region further including a multiplicity of candidate blocks of said identical size, which comprising :
means for motion-estimating a search block with respect to its corresponding search region to thereby generate ar error function and a displacement sector for each of the candidate blocks included in the corresponding search region, the displacement vector representing a displacement of pixesls between the search block and said each of the candidate blocks;
means for generating a multiple number of candidate motion vectors based en the error functions, wherein the candidate motion vectors represent displacement vectors of candidate blocks which are selected such that none of the error functions thereof is greater than an error functions for any unselected candidate block;

-17-
means, responsive to the candidate notion vectors,for providing error signals of said multiple nunber, each or ths error signals representing a difference of pixel data between the search block and each of the selected candidate blocks;
means for obtaining transforn data consisting of 11 corresponding multiple number of gets of transform coefficients by transforming each of the error signals into set of transform coefficients; and
means for determini-nn- n mm-^nr w*"r-*- -fr>y *-)o>* "^"--*i.. block based on the transform data.
11. The apparatus according to claim 10/ wherein said means for determining the motion vector includes:
means for calculating a sum of absolute values of transform coefficients in each set included in the transform data to thereby provide a multiple number of sums;
means for detecting a sum of a minimum value among said multiple number of sums; and
means, responsive to the candidate motion vectors, for selecting a candidate motion vector corresponding to said detected sum as the metier, vector of the search block.
12 . The apparatus according to claim 11, wherein said determining means includes^
means for finding one or more suns of the minimum value; and, in response tO the candidate motion vectors/

-18-
means, if only one sun of the minimum value is found, determining said only one sum as the defected sum and if more than one sum have the minimum value, comparing magnitudes of candidate morion vectors corresponding to said more than or.e sum and determining, as the detected 3um, a sum corresponding to a candidate motion vector of a least magnitude.
An apparatus for determining a motion vector between a current frame and its reference frame of video signals comprises a search region formation section 22, candidate block formation sections 24-1 to 24-n and block matching sections 26-1 to 26-n for motion-estimating a search block with respect to its corresponding search region to thereby generate an error function and a displacement vector for each of the candidate blocks included in the corresponding search region; a comparator 28 and a multiplexer 29 for generating a multiple number of candidate motion vectors based on the error functions; a motion compensation block 31 and difference generators 32-1 to 32-M, responsive to the candidate motion vectors, for providing error signals of said multiple number; transform blocks 34-] to 34-M for obtaining transform data consisting of a corresponding multiple number of sets of transform coefficients by transforming each of the error signals into a set of transform coefficients; and a motion vector determining block 36-1 to 36-M, 38 and 39 for determining a motion vector for the search block based on the transform data.

Documents:

01194-cal-1996 abstract.pdf

01194-cal-1996 claims.pdf

01194-cal-1996 correspondence.pdf

01194-cal-1996 description(complete).pdf

01194-cal-1996 drawings.pdf

01194-cal-1996 form-1.pdf

01194-cal-1996 form-2.pdf

01194-cal-1996 form-5.pdf

01194-cal-1996 form-6.pdf

01194-cal-1996 g.p.a.pdf

01194-cal-1996 letters patent.pdf

01194-cal-1996 priority document others.pdf

01194-cal-1996 priority document.pdf

1194-CAL-1996-(27-09-2012)-ASSIGNMENT.pdf

1194-CAL-1996-(27-09-2012)-CORRESPONDENCE.pdf

1194-CAL-1996-(27-09-2012)-FORM-16.pdf

1194-CAL-1996-(27-09-2012)-PA.pdf

1194-CAL-1996-FORM-27.pdf


Patent Number 190404
Indian Patent Application Number 1194/CAL/1996
PG Journal Number 25/2007
Publication Date 22-Jun-2007
Grant Date 22-Jun-2007
Date of Filing 28-Jun-1996
Name of Patentee DAEWOO ELECTRONICS CORPORATION
Applicant Address 686 AHYEON-DONG, MAPO-GU, SEOUL, REPUBLIC OF KOREA.
Inventors:
# Inventor's Name Inventor's Address
1 SANG-HO KIM VIDEO RESEARCH CENTER, DAEWOO ELECTRONICS CO. LTD., 541, 5-GA, NAMDAEMOON-RO, JUNG-GU, SEOUL, KOREA.
PCT International Classification Number H 03 M 7/30
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 NA