(12) United States Patent
`Ohtani et al.
`
`US006671321B1
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,671,321 B1
`Dec. 30, 2003
`
`(54)
`
`MOTION VECTOR DETECTION DEVICE
`AND MOTION VECTOR DETECTION
`METHOD
`
`(75) Inventors: Akihiko Ohtani, Osaka (JP); Takaaki
`Shingo, Osaka (JP)
`(73) Assignee: Mastsushita Electric Industrial Co.,
`Ltd., Osaka (JP)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 642 days.
`
`(*) Notice:
`
`Appl. No.: 09/653,483
`(21)
`Filed:
`Aug. 31, 2000
`(22)
`Foreign Application Priority Data
`(30)
`Aug. 31, 1999
`(JP) ........................................... 11-244717
`(51) Int. Cl." ............................ H04B 1/66; G06K 9/46;
`H04N 9/64; H04N 7/12
`(52) U.S. Cl. .................. 375/240.16; 382/236; 348/699;
`348/416.1
`(58) Field of Search ....................... 375/240.16, 240.01,
`375/240.24, 240.12, 240.23; 348/402.1,
`416.1, 169, 699, 700; 38.2/236, 238, 239
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,502,492 A * 3/1996
`::
`5,757,422 A + 5/1998
`::
`6,002,428 A * 12/1999
`6,169,766 B1 * 1/2001
`6,611,559 B1 * 8/2003
`
`::
`
`::
`
`Jung ..................... 375/240.14
`Matsumura ................. 348/169
`Matsumura et al. ........ 348/169
`Aoki et al. ............ 375/240.16
`Shingo et al. ......... 375/240.16
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`JP
`JP
`JP
`
`()4-049788
`08-084345
`9–224.249
`11-075.192
`
`2/1992
`3/1996
`8/1997
`3/1999
`
`OTHER PUBLICATIONS
`Copy of Office Action issued in corresponding Japanese
`application dated Dec. 3, 2002.
`* cited by examiner
`Primary Examiner—Gims Philippe
`(74) Attorney, Agent, or Firm—Snell & Wilmer, LLP
`(57)
`ABSTRACT
`A motion vector detection device of the present invention
`includes: a parameter setting section having parameters
`relating to N (N is a natural number equal to or greater than
`2) search regions obtained by dividing at least a portion of
`an entire search region in a search frame; a motion vector
`detection section for calculating an evaluation value which
`indicates a degree of correlation between an encoded object
`block in an object frame and a candidate block in one of the
`N search regions and for calculating a motion vector based
`on the evaluation value; a result storage section for storing
`the motion vector and the evaluation value calculated by the
`motion vector detection section; and a control section for
`controlling the motion vector detection section to calculate
`motion vectors and evaluation values for M (1=MsN)
`different ones of the N search regions until a predetermined
`condition is satisfied, for receiving the motion vectors and
`the evaluation values from the result storage section, and for
`determining the motion vector for the encoded object block.
`
`39 Claims, 13 Drawing Sheets
`
`Control
`section
`
`
`
`
`
`Activation
`
`30 º pdrometers
`Parqmeter setting section
`Setting
`Sedrch position le=|
`
`Motion vector
`detection section
`
`40
`Motion
`vector
`
`º ** |
`
`Hº-Ion Vector |||
`Evaluation IT Evaluation value T
`value =||
`Comp letion
`|
`
`2-100
`
`Object frame
`
`Sedrch frome
`
`Google Inc.
`GOOG 1039
`IPR2016-00212
`
`0001
`
`

`
`US 6,671,321 B1
`US 6,671,321 B1
`
`"I
`
`I I I I I I I I I I I I I I I I I I I I I I I I I I II II
`
`_I
`
`_8:2.Eco
`
`
`
`_o..8>come:-
`_o:_o>133>:o_..o:_o>m__:o__.o:_o>m_
`
`_
`
`U.S. Patent
`U.S. Patent
`
`3
`8
`
`
`
`:ozo>zo<
`
`0||
`o_
`
`vVN..mu_nh~
`
`V/ (f)I, H.
`
`2
`
`
`
`m0:5:tube
`
`f01
`
`
`
`Becu:zeoom
`
`
`
`mcozoomcozosbu%.B8>Como:
`
`m_E8.mEEo.M92%
`
`_8Eoo
`
`cozoom
`
`0002
`
`0002
`
`

`
`U.S. Patent
`U.S. Patent
`
`
`
`09
`
`MmEE._
`
`501.comMx83_s_z2%w§.8>8:02mBEEfiobo
`
`mQu
`
`n
`
`US 6,671,321 B1
`US 6,671,321 B1
`
`§8>some:
`
`
`
`v.83._o_§..%
`
`
`
`o:_o>:o__.o:_o>m_
`
`58>core:
`
`cons.Eco
`
`022co_..o=_c>m_
`
`
`
`.30?come:
`
`:o:o_.E8
`
`m§.aEEo.
`9__%m
`
`9
`
`MN.Q~...~
`
`0003
`
`0003
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 3 of 13
`
`US 6,671,321 B1
`
`FIG. 2A
`
`
`
`
`
`
`
`
`
`Set parameters
`
`Step 1
`
`Step 2
`
`Output results
`
`Step 3
`
`Step 4
`
`Calculation
`has been performed
`N times 2
`
`Yes
`Transfer results
`
`Step 5
`
`Select optimal vector
`
`Step 6
`
`End
`
`0004
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 4 of 13
`
`US 6,671,321 B1
`
`FIG.2B
`
`
`
`
`
`
`
`
`
`Set porometers
`
`Step 1
`
`Step 2
`
`
`
`
`
`Step 5'
`
`Output results
`
`Transfer results
`
`Predetermined
`ondition Sqtisfied?
`
`Yes
`
`
`
`Select optimal vector
`
`
`
`Step 6'
`
`0005
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 5 of 13
`
`US 6,671,321 B1
`
`FIG. 3A
`Entire seqrch
`region 300
`Candidate
`block 302
`
`Best match
`block 303
`
`
`
`Encoded object
`block 301
`
`E Hºlºd
`
`Search 4
`
`FIG. 3B
`
`
`
`Encoded object
`block 301
`
`Entire seqrch
`region 350
`
`0006
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 6 of 13
`
`US 6,671,321 B1
`
`oE_E£88m
`
`
`
`
`
`—-o:_o>co_..o=_o>m_--
`
`55..
`\
`
`8
`
`co_..o>_..o<
`
`cozoumcomoflmu588m.6$20
`
`
`58>core:—-m.=_o>
`
`bcocm
`
`_.E__._EomIe_w
`
`0007
`
`0007
`
`
`
`
`

`
`U.S. Patent
`U.S. Patent
`
`Dec. 30, 2003
`Dec. 30, 2003
`
`Sheet 7 of 13
`Sheet 7 of 13
`
`US 6,671,321 B1
`US 6,671,321 B1
`
`vouoocoon3v_oo_m
`
`
`
`comcoae528m
`
`2:5
`
`Se
`
`r¢/
`
`¢9...£u.«»u»«»«v».
`
`.‘‘‘‘‘Aouonononounu.
`
`V
`
`A
`1.
`
`A
`H
`
`
`
`
`
`
`
`
`
`
`
`$,:L>..7u&v__oEm0%528m.
`
`Qwm.¢$<v§=8§_§£28m.<£88m
`
`S_s_aE5_€05.
`2529__aEomu€m.
`
`mmGNR
`
`
`>__B=o~_§_m=__n_EomL.%_m_9___qE8:€m.
` mm.oim_.E.o.L8§>o_.$&=comma£28m.Md£88mNceoom3seo.N€95.
`
`
`
`...fl>:11:10.20%__28m.
`
`
`
`8fl>.mfl5E=_8E0%8.8m.
`
`28.8o,§.o§z_..__.%_.38..fem.om£88m_528m3Eco.
`
`0008
`
`§.E_.§.%.
`
`>__8Em>Ea>__3=oN_§_9___._E8:e.mN_
`
`8.m.\._e.€.8.._Veo=_oo§_§fiaem.ES£88mm6583.85.
`9__aE8L_=m.Afl>.m_atY..2mum£28m.
`3:0326:¢.€o__n_.
`
`¢506%E.85.
`
`
`
`>__3_to>9__aE8:e_mNEmcieomuém.
`
`.€oE.
`
`0008
`
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 8 of 13
`
`US 6,671,321 B1
`
`FIG. 5B Entire
`(0,0)
`seqrch region 520
`
`Encoded object block
`
`FIG. 5C
`Entire
`(0,0) search region 540
`
`
`
`Encoded object block
`
`Seqrch N
`
`Seqrch 0
`
`H–25—-—x4—-—x6—- (112,80)
`
`0009
`
`

`
`U.S. Patent
`U.S. Patent
`
`Dec. 30, 2003
`Dec. 30, 2003
`
`Sheet 9 of 13
`Sheet 9 of 13
`
`US 6,671,321 B1
`US 6,671,321 B1
`
`FIG. 5D
`FIG. 5D
`
`560
`560
`
`0010
`
`0010
`
`

`
`ux
`
`PhC.lGeSA
`
`Qh
`
`0011
`
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 11 of 13
`
`US 6,671,321 B1
`
`600
`General purpose
`computer
`
`FIG. 6
`
`
`
`vector
`detection
`
`FIG 7
`Best match block 706
`
`
`
`Motion vector 705
`
`Seqrch frome 701
`
`Object frame 702
`
`Passage º
`
`0012
`
`

`
`U.S. Patent
`
`Dec. 30, 2003
`
`Sheet 12 of 13
`
`US 6,671,321 B1
`
`FIG. 8
`
`
`
`Candidate block
`77 795 704
`
`0013
`
`

`
`U.S. Patent
`U.S. Patent
`
`D
`
`US 6,671,321 B1
`US 6,671,321 B1
`
`BmsasomEmM:28
`
`_o_a_mmen:.Boezfl
`
`58>8:08
`
`
`
`3E6809.mc.»_u,_%_ommm3._2_%men:Wm_.m8=9_£o~_wmom
`
`0014
`
`gmm.uE
`
`
`
`6 (5) I.H.
`
`
`
`
`
`
`
`
`
`
`0014
`
`
`

`
`US 6,671,321 B1
`
`1
`MOTION VECTOR DETECTION DEVICE
`AND MOTION VECTOR DETECTION
`METHOD
`
`BACKGROUND OF THE INVENTION
`
`2
`a first motion vector detection circuit 915 for performing a
`motion vector detection operation over a relatively large
`detection region but with a relatively coarse resolution and
`a second motion vector detection circuit 916 for performing
`a motion vector detection operation over a relatively small
`detection region but with a relatively fine resolution. The
`motion vector detection device 900 is arranged so that the
`relatively large detection region of the first motion vector
`detection circuit 915 includes the relatively small detection
`region of the second motion vector detection circuit 916.
`Thus, a motion vector for a relatively fast movement is
`detected by the first motion vector detection circuit 915
`having the relatively large detection region, whereas a
`motion vector for a relatively slow movement is detected by
`both of the two motion vector detection circuits (i.e., by the
`first motion vector detection circuit 915 having the relatively
`large detection region and by the second motion vector
`detection circuit 916 having the relatively small detection
`region). The values of correlation detected by the respective
`detectors- are compared with each other by a comparator
`917, thereby increasing the precision with which a motion
`vector for a relatively slow movement is detected.
`However, this conventional technique requires the two
`different motion vector detection circuits 915 and 916,
`thereby increasing the size and complexity of the entire
`circuit.
`As described above, conventional motion vector detection
`devices had a limited search region. One conventional
`solution to this problem was the motion vector detection
`device 900 illustrated in FIG. 9 which includes two different
`motion vector detection circuits, one for a relatively fine
`resolution and another for a relatively coarse resolution, in
`order to expand the search region.
`However, the motion vector detection device 900 requires
`the two different motion vector detection circuits 915 and
`916, thereby increasing the scale of the entire circuit. The
`increase in the circuit scale may present a potentially serious
`problem particularly for motion vector detection based on
`the block matching method, in which the optimal position
`(the optimal motion vector) is detected by accumulating the
`difference between each pixel in the encoded object block
`and the corresponding pixel in each of a plurality of candi
`date blocks over an entire search region.
`Moreover, it is expected that there will be a demand for
`a technique for detecting a motion of an image over an even
`larger search region in order to meet the existing demand for
`a higher definition and a higher image quality along with the
`increase in the size of the display screen.
`SUMMARY OF THE INVENTION
`In order to solve the above-described problems, the
`present invention provides a motion vector detection device
`in which a large search region is divided into a plurality of
`search regions and in which a motion vector with respect to
`one encoded object block is detected a plurality of times for
`each of the plurality of search regions. More specifically, the
`present invention provides a motion vector detection device
`capable of precisely detecting a motion vector for high
`image quality applications without substantially increasing
`the circuit scale, in which a single motion vector detection
`section may include a section for setting a plurality of
`parameters for a plurality of search regions, respectively,
`and a section for storing a plurality of motion vector
`detection results respectively corresponding to the search
`regions.
`According to one aspect of this invention, there is pro
`vided a motion vector detection device, including: a param
`
`1. Field of the Invention
`The present invention relates to a motion vector detection
`device used in a motion compensation/estimation encoding
`method, which is a type of method used for compressing/
`encoding digital motion picture data.
`2. Description of the Related Art
`A motion picture encoding method uses information
`(motion vector) which indicates the movement of a portion
`of the current image from the previous image so as to reduce
`the redundancy in time and quantity of data. The block
`matching method is a method for extracting such a motion
`Vector.
`FIG. 7 illustrates the principle of the block matching
`method. The image of an object frame 702 to be encoded is
`compared with the image of a search frame 701 so as to
`extract a block (best match block 706) from a search region
`704 in the search frame 701 that has an evaluation value
`indicating the highest degree of similarity to an encoded
`object block 703 (the term “encoded object block” as used
`herein refers to a block to be encoded, not a block which has
`already been encoded) in the object frame 702, thereby
`detecting a motion vector 705 therebetween. The block
`matching method has been widely used for motion
`compensation/estimation in image compression/encoding
`methods.
`FIG. 8 illustrates an enlarged version of the search frame
`701 shown in FIG. 7. In the block matching method, the
`degree of correlation is calculated between the single
`encoded object block 703 and each of a plurality of candi
`date blocks 707 within the search region 704 in the search
`frame 701 (the plurality of candidate blocks 707 are selected
`by scanning the search region 704 vertically or
`horizontally). Then, one of the candidate blocks 707 having
`the highest degree of correlation with respect to the encoded
`object block 703 is selected as the best match block 706, and
`the motion vector 705 is detected which extends from the
`position of the block 703 to the best match block 706.
`Some conventional motion vector detection devices
`which are based on the block matching method aim to
`reduce the amount of hardware resource needed.
`Japanese Laid-Open Publication No. 6-141304, for
`example, discloses a technique in which MXN calculation
`units are arranged in M rows and N columns, each calcu
`lation unit including a pixel storage register, a multiplexer
`and a differential absolute value calculator. Where the ref
`erence block size is MXN pixels, a candidate vector having
`the highest degree of correlation with respect to the encoded
`object block is determined for each of MXN candidate
`blocks. However, with this conventional technique, the
`degree of correlation can be calculated only for the MXN
`candidate blocks, and it is difficult to increase the number of
`candidate blocks by expanding the search region in order to
`select a candidate block which may have a higher degree of
`correlation with respect to encoded object block.
`Japanese Laid-Open Publication No. 9-224249, for
`example, discloses a motion vector detection device 900 as
`illustrated in FIG. 9. The motion vector detection device 900
`includes two different motion vector detection circuits for
`detecting two vectors for a given encoded object block, i.e.,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`0015
`
`

`
`US 6,671,321 B1
`
`3
`
`eter setting section having parameters relating to N (N is a
`natural number equal to or greater than 2) search regions
`obtained by dividing at least a portion of an entire search
`region in a search frame; a motion vector detection section
`for calculating an evaluation value which indicates a degree
`of correlation between an encoded object block in an object
`frame and a candidate block in one of the N search regions
`and for calculating a motion vector based on the evaluation
`value; a result storage section for storing the motion vector
`and the evaluation value calculated by the motion vector
`detection section; and a control section for controlling the
`motion vector detection section to calculate motion vectors
`
`and evaluation values for M (1 §M§N) different ones of the
`N search regions until a predetermined condition is satisfied,
`for receiving the motion vectors and the evaluation values
`from the result storage section, and for determining the
`motion vector for the encoded object block. Thus,
`it is
`possible to precisely detect a motion vector over a large
`search region despite a small circuit scale.
`In one embodiment of the invention, the control section
`inputs parameters relating to the N search regions to the
`parameter setting section.
`In one embodiment of the invention, M is equal to N.
`In one embodiment of the invention, the result storage
`section stores N motion vectors and N evaluation values and
`
`then outputs the evaluation values and the motion vectors to
`the control section.
`
`the parameters
`In one embodiment of the invention,
`relating to each search region include search position which
`indicates a position of a search region.
`the parameters
`In one embodiment of the invention,
`relating to each search region include search size which
`indicates a size of a search region.
`the parameters
`In one embodiment of the invention,
`relating to each search region include sub-sampling which
`indicates a degree and a direction of decimation in the search
`region.
`the parameters
`In one embodiment of the invention,
`relating to each search region include a priority which
`indicates a predetermined value to be added to or multiplied
`by the evaluation value.
`In one embodiment of the invention, a search region
`horizontally shifted from a center of the entire search region
`has a priority higher than that of a search region vertically
`shifted from the center of the entire search region.
`In one embodiment of the invention,
`the parameters
`relating to each search region include order of search which
`indicates an order in which the calculation of the motion
`
`vector and the evaluation value is performed.
`In one embodiment of the invention, a search region
`horizontally shifted from a center of the entire search region
`has an order of search higher than that of a search region
`vertically shifted from the center of the entire search region.
`In one embodiment of the invention,
`the parameters
`relating to each search region include at least two of search
`position, search size, sub-sampling, priority and order of
`search.
`
`In one embodiment of the invention, the predetermined
`condition is that the evaluation value being smaller than a
`predetermined value which the control section has.
`In one embodiment of the invention, the predetermined
`condition is limited by a predetermined amount of time.
`In one embodiment of the invention, N is 2.
`In one embodiment of the invention, N is 3.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`In one embodiment of the invention, the at least a portion
`of the entire search region is divided only along the vertical
`direction.
`
`In one embodiment of the invention, the at least a portion
`of the entire search region is divided only along the hori-
`zontal direction.
`
`In one embodiment of the invention, the at least a portion
`of the entire search region is divided into elliptical search
`regions.
`In one embodiment of the invention, each of the elliptical
`search regions is longer in the horizontal direction than in
`the vertical direction.
`
`In one embodiment of the invention, the at least a portion
`of the entire search region is divided into rectangular search
`regions.
`In one embodiment of the invention, the N search regions
`are such that no candidate block included in one of the N
`
`search regions has a complete overlap with another candi-
`date block which is included in another one of the N search
`
`regions.
`In one embodiment of the invention, at least two of the N
`search regions have different search sizes.
`In one embodiment of the invention, at least two of the N
`search regions have different sizes, and a search region
`having a larger size surrounds a search region having a
`smaller size.
`
`In one embodiment of the invention, one of the N search
`regions including a center of the entire search region has the
`smallest size.
`
`In one embodiment of the invention, one or more of the
`N search regions along a periphery of the entire search
`region has the largest size.
`In one embodiment of the invention, the at least a portion
`of the entire search region is rectangular, and one or more of
`the N search regions at corners of the at least a portion of the
`entire search region has the largest size.
`In one embodiment of the invention, at least two of the N
`search regions have different priorities.
`In one embodiment of the invention, one of the N search
`regions including a center of the entire search region has the
`lowest priority.
`In one embodiment of the invention, one or more of the
`N search regions along a periphery of the entire search
`region has the highest priority.
`In one embodiment of the invention, the at least a portion
`of the entire search region is rectangular, and one or more of
`the N search regions at corners of the at least a portion of the
`entire search region has the highest priority.
`In one embodiment of the invention, at least two of the N
`search regions have different sub-sampling parameters.
`In one embodiment of the invention, a search region
`vertically shifted from a center of the entire search region is
`sub-sampled in the vertical direction.
`In one embodiment of the invention, a search region
`horizontally shifted from a center of the entire search region
`is sub-sampled in the horizontal direction.
`In one embodiment of the invention, one or more of the
`N search regions along a periphery of the entire search
`region has the largest sub-sampling parameter.
`In one embodiment of the invention, the at least a portion
`of the entire search region is rectangular, and one or more of
`the N search regions at corners of the at least a portion of the
`entire search region has the largest sub-sampling parameter.
`According to another aspect of this invention, there is
`provided a motion vector detection method, including: an
`
`0016
`
`0016
`
`

`
`US 6,671,321 B1
`
`5
`input step of inputting parameters relating to N (N is a
`natural number equal to or greater than 2) search regions
`obtained by dividing at least a portion of an entire search
`region in a search frame to a motion vector detection section;
`a calculation step of calculating an evaluation value which
`indicates a degree of correlation between an encoded object
`block in an object frame and a candidate block in one of the
`N search regions based on the parameters of the one of the
`N search regions, and calculating a motion vector based on
`the evaluation value; and a determination step of determin
`ing whether a predetermined condition is satisfied based on
`the calculated evaluation values and motion vectors.
`In one embodiment of the invention, the motion vector
`detection method further includes the step of terminating the
`motion vector calculation when the predetermined condition
`is satisfied.
`In one embodiment of the invention, the motion vector
`detection method further includes the step of repeating the
`input step and the calculation step when the predetermined
`condition is not satisfied.
`Thus, the invention described herein makes possible the
`advantage of providing a motion vector detection device
`capable of detecting a motion vector with a high precision to
`realize a high image quality without increasing the circuit
`scale.
`This and other advantages of the present invention will
`become apparent to those skilled in the art upon reading and
`understanding the following detailed description with refer
`ence to the accompanying figures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1A is a schematic diagram illustrating a motion
`vector detection device of the present invention;
`FIG. 1B is a schematic diagram illustrating an alternative
`arrangement using a plurality of motion vector detection
`blocks;
`FIG. 2A is a flow chart illustrating an operation of the
`present invention;
`FIG. 2B is a flow chart illustrating another operation of
`the present invention;
`FIG. 3A illustrates an example of how an entire search
`region is divided into smaller search regions according to the
`present invention;
`FIG. 3B illustrates an alternative example of how an
`entire search region is divided into smaller search regions
`according to the present invention;
`FIG. 4 is a schematic diagram illustrating another motion
`vector detection device of the present invention;
`FIG. 5A illustrates an alternative example of how an
`entire search region is divided into smaller search regions
`according to the present invention;
`FIG. 5B illustrates an alternative example of how an
`entire search region is divided into smaller search regions
`along the horizontal direction according to the present
`invention;
`FIG. 5C illustrates an alternative example of how an
`entire search region is divided into smaller search regions
`along the vertical direction according to the present inven
`tion;
`FIG. 5D illustrates an alternative example of how an
`entire search region is divided into smaller elliptical search
`regions according to the present invention;
`FIG. 5E illustrates an alternative example of how an entire
`search region is divided into smaller search regions accord
`
`6
`ing to the present invention, in which any smaller search
`region is included by a larger search region;
`FIG. 6 is a schematic diagram illustrating a motion vector
`detection circuit of the present invention and a general
`purpose computer;
`FIG. 7 illustrates a block matching method;
`FIG. 8 illustrates an enlarged version of a search frame;
`and
`FIG. 9 illustrates a conventional motion vector detection
`circuit.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`Various embodiments of the present invention will now be
`described with reference to the accompanying drawings.
`Embodiment 1
`FIG. 1A illustrates a configuration of a motion vector
`detection device 100 according to Embodiment 1 of the
`present invention.
`The motion vector detection device 100 includes a control
`section 10, a motion vector detection section 20, a parameter
`setting section 30 and a result storage section 40. The control
`section 10 inputs search region setting parameters to the
`parameter setting section 30 and activates the motion vector
`detection section 20. The respective setting parameters
`(search positions in the present embodiment) which relate to
`N (N is a natural number equal to or greater than 2) search
`regions, respectively, which are obtained by dividing an
`entire search region (which may be a portion or the whole of
`a search frame) are input from the control section 10 to the
`parameter setting section 30. The motion vector detection
`section 20 is activated by the control section 10 and receives
`an object frame and a search frame from the outside and a
`parameter which relates to one search region from the
`parameter setting section 30. Then, the motion vector detec
`tion section 20 calculates a motion vector and an evaluation
`value for a single search region based on the received
`parameter, and outputs the motion vector and the evaluation
`value to the result storage section 40. The result storage
`section 40 stores the motion vector and the evaluation value
`calculated by the motion vector detection section 20. The
`control section 10 obtains the stored motion vector and the
`evaluation value from the result storage section 40, and a
`completion signal from the motion vector detection section
`20. The evaluation value indicates the degree of correlation
`between the encoded object block in the object frame and a
`candidate block in a search region within an entire search
`region.
`In the above description, for the purpose of illustration,
`the parameters relating to the N divided search regions are
`described to be input from the control section 10 to the
`parameter setting section 30. However, the parameters relat
`ing to the N divided search regions may alternatively be
`pre-stored in the parameter setting section 30. The result
`storage section 40 may output N motion vectors to the
`control section 10 after they are stored in the result storage
`section 40.
`The operation of the motion vector detection device 100
`will now be described with reference to the flow chart
`illustrated in FIG. 2A.
`Step 1: The control section 10 sets the N parameters
`relating to the search regions (i.e., N search positions) to the
`parameter setting section 30.
`Step 2: The control section 10 activates the motion vector
`detection section 20.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`0017
`
`

`
`US 6,671,321 B1
`
`15
`
`20
`
`30
`
`7
`Step 3: The motion vector detection section 20 calculates
`a motion vector and an evaluation value for one search
`position, outputs the motion vector and the evaluation value
`to the result storage section 40, and completes the motion
`vector detection operation for the search position.
`Step 4: Steps 2 and 3 are repeated N times.
`Step 5: The control section 10 obtains the N sets of motion
`vectors and evaluation values from the result storage section
`40.
`10
`Step 6: The control section 10 determines an optimal
`motion vector for the encoded object block based on the N
`sets of motion vectors and evaluation values.
`As a specific example, a search operation where an entire
`search region 300 is divided into four (N=4) search regions
`(designated respectively as “Search 1”, “Search 2”, “Search
`3” and “Search 4” in FIG. 3A) will now be described with
`reference to FIG. 3A. In FIG. 3A, the entire search region
`300 is divided into “Search 1”, “Search 2”, “Search 3” and
`“Search 4” which respectively correspond to the upper left,
`upper right, lower left and lower right regions of the entire
`search region 300. In the example shown in FIG. 3A, the
`search regions do not overlap with one another. A candidate
`block 302 of one search region does not have to be com
`pletely within the search region, but a portion thereof may
`25
`extend beyond the boundary thereof. However, a portion of
`the candidate block 302 may not extend beyond the bound
`ary to such an extent that the candidate block 302 would
`completely overlap with any other candidate block 302
`extending from any other search region.
`In the example shown in FIG. 3A, the entire search region
`300 is divided into smaller rectangular search regions.
`For example, where a motion vector detection operation
`is to be performed for each of the search regions (i.e., in FIG.
`3A, the calculation and the storage of a motion vector and
`an evaluation value are to be performed four times), the
`motion vector detection device 100 is configured so that
`search positions for four search regions can be set in the
`parameter setting section 30 and four sets of motion vectors
`and evaluation values can be stored in the result storage
`section 40. The control section 10 writes the position of each
`search region (e.g., a set of coordinates representing the
`upper left corner of the search region) in the parameter
`setting section 30.
`Specifically, four sets of coordinates respectively corre
`sponding to the four search regions (“Search 1”, “Search 2",
`“Search 3” and “Search 4”) are set. Then, the control section
`10 activates the motion vector detection section 20.
`Upon the first activation, the motion vector detection
`section 20 calculates a motion vector and an evaluation
`value for “Search 1” in FIG. 3A, stores the motion vector
`and the evaluation value in the result storage section 40 as
`a first set of results, and returns a completion signal to the
`control section 10, thus completing the first motion vector
`detection operation.
`Similarly, a motion vector and an evaluation value are
`calculated for “Search 2° and stored as a second set of
`results. This operation is similarly repeated for “Search 3”
`and “Search 4”.
`More specifically, each motion vector detection operation
`is performed as follows. First, the degree of correlation (i.e.,
`the evaluation value) between an encoded object block 301
`and the candidate block 302 in “Search 1” is obtained. Then,
`the candidate block 302 is shifted vertically or horizontally
`within “Search 1”, and an evaluation value is obtained in a
`similar manner. By repeating such an operation, the best
`
`35
`
`8
`matching block within “Search 1” is determined as a block
`which exhibits the highest degree of correlation with respect
`to the encoded object block 301, based on which a motion
`vector and an evaluation value are calculated for “Search 1”.
`By repeating such an operation for “Search 2” to “Search 4”,
`a motion vector and an evaluation value are calculated for
`each of the four search regions.
`After the motion vector detection section 20 have per
`formed the four motion vector detection operations respec
`tively for the four search regions, the control section 10
`obtains the calculation results stored in the result storage
`section 40. Then, the control section 10 selects one of the
`four motion vectors as the motion vector for the current
`encoded object block based on the evaluation values. Thus,
`a motion vector optimal for the encoded object block is
`determined. Since an evaluation value is typically calculated
`by accumulating the value of difference (or the square
`thereof) between each pixel in the encoded object block and
`the corresponding pixel in the candidate block, the motion
`vector for which the evaluation value is smallest is typically
`selected.
`As described above, in the present embodiment, the entire
`search region is divided into four search regions, and a
`single motion vector detection section is used to obtain
`respective motion vectors for the four search regions. Thus,
`it is possible to detect motion vectors over a large search
`region, thereby precisely selecting a motion vector, despite
`a small circuit scale.
`While the number (N) of search regions into which an
`entire search region is divided is set to 4 in the present
`embodiment, N can be any natural number equal to or
`greater than 2.
`In the present embodiment, the motion vector detection
`operation is performed to cover the whole of each of the N
`(=4 in the