USO05430886A United States Patent [19] [11] Patent Number: 5,430,886 Furtek [45] Date of Patent: Jul. 4, 1995 [54] METHOD AND APPARATUS FOR MOTION Komarek et al. “Array architectures for block-match ESTINIATION ing algorithms”, 1989, pp. 1301-1308. Artieri and Jutand, “A Versatile and Powerfull Chip [76] Inventor: Frederick C. Furtek, 350 Sharon Park For Real Time Motion Estimation”, IEEE Computer, Dr., Menlo Park, Calif. 94025 pp. 2453-2456, (Feb. 1989). Considine, Bhandal and Gooding, “Single Chip Motion [21] Appl. N0.: 898,862 Estimator For Video Codec Applications”, Third Inter [22] Filed: Jun. 15, 1992 national Conference On Image Processing and Its Ap plications, pp. 285-289 (Jul., 1989). [51] Int. Cl.6 ..................... .. G06F 11/00; G06F 15/ 16 Dianysian and Baker, “Bit-serial architecture for real [52] US. Cl. .............................. .;. 395/800; 364/2306; time motion compensation”, SPIE vol. 1001 Visual Com 364/231.9; 364/265; 364/DIG. 1; 371/67.l; munications and Image Processing ’88, pp. 900-907. 348/416; 348/518 Primary Examiner-Alyssa H. Bowler [58] Field of Search ............. .. 395/ 800, 775, 500, 375, 395/575; 358/105, 107, 133, 135, 136, 139, 148, Assistant Examiner-Alpesh M. Shah 448, 452; 341/159, 163; 371/681, 67.1, 67.8, Attorney, Agent, or Firm-Pennie & Edmonds 68.3 [5 7] ABSTRACT [56] References Cited A method and apparatus for generating a sequence of U.S. PATENT DOCUMENTS displacement ‘vectors and associated minimal error val ues. The vectors and-associated values represent the 4,864,393 9/1989 Harradine et al. ................ .. 358/105 best match of a current block of elements of a ?rst frame 4,875,094 10/1989 Haghiri et al. ............. .. 358/105 of a signal with one of a plurality of search blocks of 4,924,306 5/ 1990 van der Meer et a1. .... .. 358/105 elements located within a corresponding search win 5,083,202 l/l992 Parke .......................... .. 358/105 dow of a second frame. A ?rst stream of data, represent 5,099,325 3/1992 Artieri et a1. .. .... .. 358/136 ing the elements of the ?rst frame is transmitted to a 5,138,447 8/1992 Shen et a.l. ........................ .. 358/133 linear array of processing units; a second stream of data, FOREIGN PATENT DOCUMENTS representing the elements of the second frame is trans 474276Al 9/1990 European Pat. Off. . mitted to the array; a hybrid stream of data from the 395293A1 10/1990 European Pat. Off. . elements of the second stream is synthesized such that 2214751 9/1989 United Kingdom . the elements of the hybrid stream are aligned in time 2236449 4/1991 United Kingdom . with the elements of the ?rst stream so as to enable each processing unit of the array to compute an error be OTHER PUBLICATIONS tween a particular current block and a different search Colavin et al. “A dedicated circuit for real time motion block of the corresponding search window. The error is estimation”, 1991, pp. 96-99. a measure of the difference between two blocks of ele Hsieh et al. “VLSI architecture for block-matching ments. Speci?cally, the errors are computed between motion estimation algorithm”, Jun. 1992, pp. 172-174. each current block and each search block of the corre Komarck et al. “VLSI architectures for block-match sponding search windows such that each processing ing algorithms”, 1989, pp. 2457-2460. unit of the array outputs the computed error essentially Sun et al. “A ?exible VLSI architecture for full search immediately after the previous unit outputs the error. block matching motion-vector estimation”, 1989, pp. 25 Claims, 18 Drawing Sheets 179-182. ,(-8’ -8W) '/(-7. -7/) ,1,221123 24 / - - -_ I (8,7) _ ______ __,_ __ (-B,—6)'- _ _ _____ ____ | 1 ' ,125 UPPER | l/ BAND : £( 0.0 ) r | 123 1 1g? - l (n+1) l ‘— >(_8,+7)~_..l.....-... :. 17. 126 129 - LOWER / BAND t : US. Patent July 4, 1995 Sheet 1 of 18 5,430,886 FIG.1 US. Patent July 4, 1995 Sheet 2 of 18 5,430,886 mmqo?i mmooxxwm mmaamm mm.|.__wm mmoomm wwooww ““66 mm::0 3¢mm ..4. mmoO4-mG mmooIImm “no5 mmaomm 3m..m_m mm::Z Imm ..;_ mmoomm mmoomw mo mam m._m m: mom mew mam moIw P .hNo._ N21 @015 mam m._m wow wow mu m: m._ moVI m al?l'glg‘lglglalalgl HHIHH 88.d5 8855 g2ma 33wm D8332 mm38 mm88 35 3S 111111111, US. Patent July 4,1995 Sheet 3 of 18 .p0m: and; US. Patent July 4, 1995 Sheet 4 of 18 5,430,886 m-8 m+22 ""8 UPPER BAND 31 SEARCH 30 WINDOW "+22 \‘ LOWER BAND 32 41 FIG. 4b m m+15 n CURRENT n+15 BLOCIK } 33 40 FIG. 40 US. Patent 5,430,886. July 4, 1995 Sheet 5 of 18 O 8 23 24 39 4O 55 16x16 16X16 ‘ 16X16 BLOCK BLOCK BLOCK n+15 FIG. 5