Source: http://www.google.com/patents/US5949486?dq=6778979
Timestamp: 2016-12-11 04:25:57
Document Index: 643972688

Matched Legal Cases: ['art 3', 'art 3', 'art 12', 'art 1', 'art 12', 'art 12', 'art 12', 'art 12', 'art 122', 'arts 12', 'arts 12', 'arts 12', 'art 2']

Patent US5949486 - Unit for detecting motion vector for motion compensation - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsEach of element processors arranged in correspondence to pixels of a template block and a search window block respectively includes an A register and a B register provided in parallel with each other for storing search window block pixel data respectively, and a T register for storing template block...http://www.google.com/patents/US5949486?utm_source=gb-gplus-sharePatent US5949486 - Unit for detecting motion vector for motion compensationAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS5949486 APublication typeGrantApplication numberUS 08/795,217Publication dateSep 7, 1999Filing dateFeb 5, 1997Priority dateSep 3, 1996Fee statusLapsedPublication number08795217, 795217, US 5949486 A, US 5949486A, US-A-5949486, US5949486 A, US5949486AInventorsKazuya Ishihara, Shinichi Uramoto, Tetsuya Matsumura, Satoshi Kumaki, Atsuo Hanami, Shinichi MasudaOriginal AssigneeMitsubishi Denki Kabushiki Kaisha, Mitsubishi Electric Engineering Co., Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (9), Non-Patent Citations (2), Referenced by (30), Classifications (20), Legal Events (6) External Links: USPTO, USPTO Assignment, EspacenetUnit for detecting motion vector for motion compensation
US 5949486 AAbstract
Each of element processors arranged in correspondence to pixels of a template block and a search window block respectively includes an A register and a B register provided in parallel with each other for storing search window block pixel data respectively, and a T register for storing template block pixel data. Motion vector evaluation value calculation is performed through a first one of the A and B registers and the pixel data stored in the T register, while operated data is transferred to the second one of the A and B registers from the first one of the A and B registers in parallel with the calculation operation, for storing head search window block pixel data of a next search window. A motion vector is detected at a high speed in excellent coding efficiency.
1. A motion vector detection unit for obtaining a motion vector employed for motion compensation predictive coding through block matching of a current screen image and a reference screen image, said motion vector detection unit comprising:a plurality of first registers, arrayed in a matrix of rows and columns, and arranged in correspondence to pixels of a template block of said current screen image to be subjected to motion vector detection, for storing corresponding template block pixel data; a plurality of second registers arranged in correspondence to respective ones of said plurality of first registers in said matrix for storing pixel data of a first reference block in a search area of said reference screen image related to said template block; a plurality of third registers being provided in correspondence to respective ones of said plurality of first registers in parallel with said plurality of second registers for storing pixel data of a second reference block in said search area of said reference screen image related to said template block; a plurality of data buffers arranged in correspondence to columns of said matrix and interconnected with each other such that input parts and outputs parts thereof form a one-dimensional array for transferring pixel data along one direction, for storing pixel data of said search area other than those of said reference blocks; selective coupling means arranged on said columns respectively for coupling initial stage registers of either said second or third registers of corresponding columns with the output parts of said data buffers of the corresponding columns while coupling final stage registers of either said second or third registers of the corresponding columns with initial stage registers of either said third or second registers of columns adjacent to said corresponding columns respectively; a plurality of operation means provided in correspondence to said first registers and sets of said second and third registers for performing prescribed operation on pixel data stored in corresponding registers to calculating components of evaluation values serving as candidates for said motion vector; evaluation value calculation means for receiving output signals of said plurality of operation means for performing prescribed arithmetic processing on the received output signals and calculating evaluation values of said reference block, said search area defined by predetermined horizontal and vertical vector ranges, and control means for switching the connection path of said selective coupling means in units of said horizontal vectors and controlling connection for performing data transfer through interconnection over said columns of said second and third registers from said horizontal vector updating up to transfer of all pixel data of said fist reference block to said adjacent columns while supplying pixel data of registers being coupled to corresponding data buffers to said operation means among said second and third registers. 2. The motion vector detection unit according to claim 1, wherein said selective coupling means includes a plurality of first select gates provided corresponding to respective columns of the sets of the second and third registers and between the output parts of corresponding data buffers and the initial stages of the corresponding columns of the sets of the second and third registers, for selectively transferring output pixel data of the corresponding data buffers or applied search window pixel data, anda plurality of second select gates provided corresponding to respective columns of the sets of second and third registers and between final stages of the corresponding columns of the sets of the second and third registers and upstream adjacent first select gates, for selectively transferring output pixel data from the corresponding columns of the second registers and the corresponding columns of the third registers, and said control means includes means for causing said plurality of second select gates to select the output pixel data from the corresponding data buffers for application to the corresponding second register columns and to apply pixel data received from downstream adjacent second select gates to corresponding third register columns, and means for causing the second select gates to select pixel data received from the corresponding second register columns. 3. The motion vector detection unit according to claim 2, wherein each of said plurality of operation means includes a selector for selecting pixel data of corresponding second and third registers in a same manner as the selection of the second select gates.
In case of the aforementioned motion vector detection unit, the respective processors are arranged in correspondence to the displacement vectors (evaluation points) serving as motion vector candidates. When the search area is in the range of +16 to -16 in the vertical direction and -16 to +16 in the horizontal direction, the number of the displacement vectors serving as motion vector candidates is 33×33=1089. Thus, the number of the processors is extremely increased to disadvantageously increase the occupied area of the unit.
An object of the present invention is to provide a motion vector detection unit which can detect a motion vector at a high speed, and a method therefor.
FIG. 1 schematically illustrates the overall structure of a motion vector detection unit according to an embodiment 1 of the present invention;
FIG. 1 schematically illustrates the overall structure of a motion vector detection unit according to an embodiment 1 of the present invention. This figure shows a structure coding pixels in units of frames.
Description is now made on an evaluation value calculation operation performed when a search window is formed by pixels of (m+n) rows and (p+1) columns and a search window block is formed by n by (p+1) pixels, as shown in FIG. 20. Referring to FIG. 20, an element processor stores pixel data a01 to ap1, . . . , a0n to apn. A data buffer stores pixel data b01 to bp1, . . . , b0m to bpm of a side window block.
Structure of Selector
FIG. 27A schematically illustrates exemplary structures of selectors SLa and SLb included in the processor array. Referring to FIG. 27A, the selector SLa includes a transfer gate 30a which conducts in response to a control signal φ1A for transferring pixel data outputted from an A register train AR to an output node 33o, and a transfer gate 30b which conducts in response to a control signal φ1B for transferring pixel data outputted from a B register train BR to the output node 33o.
Structure of Control Signal Generation Part
FIG. 28A illustrates the structure of a switching control signal φSH generation part. Referring to FIG. 28A, the switching signal φSH generation part includes an (m+1) counter 50 which is started in response to a motion vector detection operation start instruction signal φST for counting the clock signal CLK, and a T flip-flop 51 for changing the state of the signal φSH from its output Q in response to a count-up signal cup from the counter 50. The start instruction signal fST is supplied to a reset input R of the T flip-flop 51. The (m+1) counter 50 brings the count-up signal cup into a high level of an active state when the same detects rise of the clock signal CLK (m+1) times in starting.
Structure of Comparison Part
FIG. 33 schematically illustrates the structure of the comparison part 3 shown in FIG. 1. Referring to FIG. 33, the comparison part 3 includes a comparison circuit 3a for obtaining a motion vector as to the template block, i.e., the block motion vector Vb, a comparison circuit 3b for obtaining a motion vector as to the odd subtemplate block, i.e., the odd field block motion vector Vo, and a comparison circuit 3c for obtaining a motion vector as to the even subtemplate block, i.e., the even field block motion vector Ve. The comparison circuits 3a to 3c are identical in structure to each other, and hence FIG. 33 specifically shows only the structure of the comparison circuit 3a for obtaining the motion vector as to the template block, i.e., the block motion vector Vb.
FIG. 34 schematically illustrates the overall structure of a motion vector detection unit according to an embodiment 2 of the present invention. The motion vector detection unit shown in FIG. 34 is adapted to encode pixels in units of fields. In the motion vector detection unit shown in FIG. 34, a summation part 12 included in an operation part 1 outputs evaluation values Σ|a-b|, Σu|a-b| and Σl|a-b| with respect to a template block, an upper half block of the template block, and a lower half block of the template block respectively in parallel with each other. The summation part 12 and a processor array 10 are substantially identical in structure to those shown in FIG. 1, except for connection between element processors included in the processor array 10 and summation circuits included in the summation part 12 depending on the change of division of the blocks.
FIG. 37 illustrates the correspondence between element processor groups and template block pixels in a motion vector detection unit according to an embodiment 3 of the present invention. Referring to FIG. 37, a template block 43 comprises pixels which are arranged in 16 rows, for example. The template block 43 is divided on a screen along a vertical direction into an upper subtemplate block 43u which is formed by pixel data #0 to #7 of an upper half block and a lower subtemplate block 43l which is formed by pixel data #8 to #15 of the lower half block respectively. In correspondence to the subtemplate blocks 43u and 43l, the element processors are similarly divided into groups.
Modification of Total Sum Part
FIG. 39 illustrates the structure of a modification of the summation part 12 shown in FIG. 38. This summation part 12 includes summation circuits 120a, 120b, 120c and 12d provided in correspondence to respective element processor groups PE#uo, PE#lo, PE#ue and PE#le of a processor array for obtaining the sums of outputs |a-b|uo, |a-b|o, |a-b|ue and |a-b|le of the corresponding groups respectively, and a classification change part 122 for switching propagation paths for output data of two of the four summation circuits 120a to 120d, i.e., the summation circuits 120b and 120c.
FIG. 40 schematically illustrates the structure of each element processor PE of a motion vector detection unit according to an embodiment 4 of the present invention. Referring to FIG. 40, the element processor PE includes A and B registers 26 and 27 for storing search window block pixel data respectively, a selector 29 for selecting the pixel data stored in either the A or B register 26 or 27 in accordance with a switching control signal φSH, and T registers 25-1 to 25-3 storing pixel data of different template blocks respectively. The A and B registers 26 and 27, which are identical to those employed in the embodiments 1 to 3, are alternately switched every horizontal vector component updating. The T registers 25-1 to 25-3 store pixel data of different template blocks respectively, whereby a processor array including this element processor PE simultaneously calculates evaluation values as to motion vectors of three template blocks. The T registers 25-1 to 25-3 are identical in structure to those in the embodiments 1 to 3.
FIG. 44 schematically illustrates the overall structure of a motion vector detection unit according to an embodiment 5 of the present invention. The motion vector detection unit shown in FIG. 44 is adapted to detect motion vectors employed in a coding system for coding pixels in units of fields. The remaining structure is identical to that of the motion vector detection unit according to the embodiment 4, and corresponding parts are denoted by the same reference numerals. In the structure shown in FIG. 44, each element processor PE included in a processor array 10 can store pixel data of three template blocks, whereby summation parts 12-1, 12-2 and 12-3 are provided in correspondence to the respective template blocks. The respective ones of the summation parts 12-1 to 12-3 calculate evaluation values as to the template blocks, evaluation values as to upper subtemplate blocks corresponding to pixels of the upper halves of the template blocks, and evaluation values of lower subtemplate blocks formed by pixels of lower halves of the template blocks respectively in parallel with each other. The summation parts 12-1 to 12-3 are identical in structure to that shown in FIG. 36.
FIG. 45 illustrates the structure of a motion vector detection unit according to an embodiment 6 of the present invention.
FIG. 46 illustrates the structure of each element processor PE according to an embodiment 7 of the present invention. Referring to FIG. 46, the element processor PE includes TA and TB registers 25a and 25b for storing different template block pixel data respectively, a multiplexer 150 for transferring template block pixel data PX supplied from an adjacent element processor or an input part to either the TA or TB register 25a or 25b in accordance with a switching control signal φX, a selector 152 for transmitting pixel data stored in the TA or TB register 25a or 25b to the adjacent element processor in accordance with the switching control signal 4x, and a selector 154 for selecting the pixel data stored in either the TA or TB register 25a or 25b in accordance with a switching control signal Z+X. The switching control signals φX and ZφX are complementary to each other.
FIG. 48 schematically illustrates the overall structure of the motion vector detection unit 70 according to the embodiment 7 of the present invention. This figure shows a structure for controlling the transfer of template block pixel data. A control unit 210 also controls a transfer operation for search window block pixel data (refer to the embodiment 1).
FIG. 49 illustrates the structure of a first modification of the embodiment 7 of the present invention. This figure shows the structure of only an initial stage element processor PE for receiving template block pixel data from an input part 2. The remaining element processors included in a processor array are identical in structure to the element processor PE shown in FIG. 49.
FIG. 50 illustrates the structure of a second modification of the embodiment 7 of the present invention. This figure shows the structures of TA and TB registers 25a and 25b for storing template block pixel data in a single element processor PE. The remaining structure is identical to that shown in FIG. 46 or 49, and corresponding parts are denoted by the same reference numerals.
FIG. 53 illustrates the structure of a main part of a motion vector detection unit according to an embodiment 8 of the present invention. This figure shows only the structure of each data buffer DL included in a processor array. As to the remaining structure, the structure of any of the embodiments 1 to 7 is employed.
FIG. 54 illustrates the structure of a first modification of the data buffer DL. Referring to FIG. 54, the data buffer DL includes a plurality of cascaded registers RGa to RGr. It is possible to transfer search window pixel data through these registers RGa to RGr, in response to a transfer clock signal (not shown). The registers RGa to RGr are provided at output parts thereof with selector gates SELa to SELr, which conduct in response to selection signals φsa to φsr respectively. These selection signals φsa to φsr are supplied from the exterior of the unit, so that any one is activated. The corresponding selector gate is brought into a conducting state in response to the activated selection signal, so that search window pixel data outputted from the corresponding register is transmitted to a data line 302. This data line 302 is supplied to the lowermost element processor of this linear processor array through a selector SLb, and connected to an initial register (RGa) of an adjacent upstream data buffer.
FIG. 55 illustrates the structure of a main part of a motion vector detection unit according to an embodiment 9 of the present invention. This figure shows the structure of a single data buffer DL included in a processor array.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5398079 *Jan 27, 1993Mar 14, 1995General Instrument CorporationHalf-pixel interpolation for a motion compensated digital video systemUS5400087 *Jul 6, 1993Mar 21, 1995Mitsubishi Denki Kabushiki KaishaMotion vector detecting device for compensating for movements in a motion pictureUS5568203 *May 5, 1993Oct 22, 1996Samsung Electronics Co., Ltd.Apparatus for estimating real-time motion an a method thereofUS5594813 *Feb 19, 1992Jan 14, 1997Integrated Information Technology, Inc.Programmable architecture and methods for motion estimationUS5604546 *Oct 18, 1994Feb 18, 1997Sony CorporationImage signal processing circuit for performing motion estimationUS5696836 *Mar 17, 1995Dec 9, 1997Lsi Logic CorporationMotion estimation processor architecture for full search block matchingUS5737020 *Jan 7, 1997Apr 7, 1998International Business Machines CorporationAdaptive field/frame encoding of discrete cosine transformJPH0696209A * Title not availableJPH02265387A * Title not available* Cited by examinerNon-Patent CitationsReference1F. Jutand, "A Versatile and Powerfull Chip for Real Time Motion Estimation" 1989, pp. 2453-2456.2 *F. Jutand, A Versatile and Powerfull Chip for Real Time Motion Estimation 1989, pp. 2453 2456.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6122317 *Nov 20, 1997Sep 19, 2000Mitsubishi Denki Kabushiki KaishaMotion vector detectorUS6298086 *Dec 22, 1998Oct 2, 2001Mitsubishi Denki Kabushiki KaishaMotion vector detecting apparatusUS6366616 *Aug 31, 2000Apr 2, 2002Nec CorporationMotion vector estimating apparatus with high speed and method of estimating motion vectorUS6380987 *May 27, 1999Apr 30, 2002Nec CorporationMotion vector detection circuit enabling high-speed search of motion vectorUS6516031 *May 27, 1998Feb 4, 2003Mitsubishi Denki Kabushiki KaishaMotion vector detecting deviceUS6567469 *Mar 23, 2000May 20, 2003Koninklijke Philips Electronics N.V.Motion estimation algorithm suitable for H.261 videoconferencing applicationsUS6624849 *Dec 1, 1998Sep 23, 2003Nikon CorporationSolid-state imaging apparatus for motion detectionUS6765965 *Oct 22, 1999Jul 20, 2004Renesas Technology Corp.Motion vector detecting apparatusUS7126991 *Feb 3, 2003Oct 24, 2006Tibet MIMARMethod for programmable motion estimation in a SIMD processorUS7782957 *Mar 20, 2006Aug 24, 2010Novatek Microelectronics Corp.Motion estimation circuit and operating method thereofUS7782959 *Dec 12, 2003Aug 24, 2010Sony CorporationImage processing apparatusUS7894518 *Mar 21, 2006Feb 22, 2011Novatek Microelectronic Corp.Motion estimation circuit and motion estimation processing elementUS7912128 *May 11, 2006Mar 22, 2011Quanta Computer Inc.Motion vector estimation system and method thereofUS8055025 *Jun 14, 2008Nov 8, 2011City University Of Hong KongMotion estimation methodUS8416856 *Jun 21, 2005Apr 9, 2013Novatek Microelectronics Corp.Circuit for computing sums of absolute differenceUS20020101927 *Nov 14, 2001Aug 1, 2002Mitsubishi Denki Kabushiki KaishaMotion vector detecting device and motion vector detecting methodUS20030012283 *Jun 4, 2002Jan 16, 2003Mitsubishi Denki Kabushiki KaishaMotion vector detecting device and self-testing method thereinUS20040240553 *May 5, 2004Dec 2, 2004Sony CorporationMotion vector detecting method and image processing appparatus using the sameUS20060020929 *Jul 19, 2005Jan 26, 2006Kun LiuMethod and apparatus for block matchingUS20060023959 *Jun 21, 2005Feb 2, 2006Hsing-Chien YangCircuit for computing sums of absolute differenceUS20060120628 *Dec 12, 2003Jun 8, 2006Tetsujiro KondoImage processing apparatusUS20070002950 *Mar 20, 2006Jan 4, 2007Hsing-Chien YangMotion estimation circuit and operating method thereofUS20070053440 *May 11, 2006Mar 8, 2007Quanta Computer Inc.Motion vector estimation system and method thereofUS20070110164 *Mar 21, 2006May 17, 2007Hsing-Chien YangMotion estimation circuit and motion estimation processing elementUS20070217515 *Mar 15, 2006Sep 20, 2007Yu-Jen WangMethod for determining a search pattern for motion estimationUS20090310875 *Jun 14, 2008Dec 17, 2009City University Of Hong KongMotion estimation methodCN1328910C *Mar 10, 2005Jul 25, 2007北京中星微电子有限公司Method for reading search window data for motion estimation by hardwareCN100470591CNov 24, 2005Mar 18, 2009联咏科技股份有限公司Mobile estimation circuitEP1241892A1 *Mar 6, 2001Sep 18, 2002Siemens AktiengesellschaftHardware accelerator for video signal processing systemEP1845730A1 *Apr 13, 2006Oct 17, 2007Novatek Microelectronics Corp.Motion estimation circuit and motion estimation processing element* Cited by examinerClassifications U.S. Classification348/402.1, 348/416.1, 375/E07.105, 375/E07.102, 348/420.1, 348/699, 348/E05.066International ClassificationH04N19/51, H04N19/423, H04N19/436, H04N19/50, H03M7/36, H03M7/30, H04N5/14Cooperative ClassificationH04N19/51, H04N19/433, H04N5/145European ClassificationH04N7/26L4B, H04N5/14M2, H04N7/26M2Legal EventsDateCodeEventDescriptionFeb 5, 1997ASAssignmentOwner name: MITSUBISHI DENKI KABUSHIKI KAISHA, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:ISHHARA, KAZUYA;URAMOTO, SHINICHI;MATSUMURA, TETSUYA;ANDOTHERS;REEL/FRAME:008456/0249Effective date: 19970130Owner name: MITSUBISHI ELECTRIC ENGINEERING CO., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:ISHHARA, KAZUYA;URAMOTO, SHINICHI;MATSUMURA, TETSUYA;ANDOTHERS;REEL/FRAME:008456/0249Effective date: 19970130Oct 13, 1998ASAssignmentOwner name: MITSUBISHI DENKI KABUSHIKI KAISHA, JAPANFree format text: TO CORRECT THE NAME OF THE FIRST INVENTOR OF THE SECOND ASSIGNEE APPEARING AT REEL 8456, FRAME 0249.;ASSIGNORS:ISHIHARA, KAZUYA;URAMOTO, SHINICHI;MATSUMURA, TETSUYA;AND OTHERS;REEL/FRAME:009392/0164Effective date: 19970130Owner name: MITSUBISHI ELECTRIC ENGINEERING CO., LTD., JAPANFree format text: TO CORRECT THE NAME OF THE FIRST INVENTOR OF THE SECOND ASSIGNEE APPEARING AT REEL 8456, FRAME 0249.;ASSIGNORS:ISHIHARA, KAZUYA;URAMOTO, SHINICHI;MATSUMURA, TETSUYA;AND OTHERS;REEL/FRAME:009392/0164Effective date: 19970130Feb 13, 2003FPAYFee paymentYear of fee payment: 4Mar 28, 2007REMIMaintenance fee reminder mailedSep 7, 2007LAPSLapse for failure to pay maintenance feesOct 30, 2007FPExpired due to failure to pay maintenance feeEffective date: 20070907RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services