I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US007650015B2
`
`c12) United States Patent
`Pirim
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 7,650,015 B2
`Jan.19,2010
`
`(54)
`
`IMAGE PROCESSING METHOD
`
`(75)
`
`Inventor: Patrick Pirim, Paris (FR)
`
`(73) Assignee: Image Processing Technologies. LLC,
`Suffern, NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 134 days.
`
`(21) Appl. No.: 11/676,926
`
`(22) Filed:
`
`Feb.20,2007
`
`(65)
`
`Prior Publication Data
`
`US 2007/0140526Al
`
`Jun.21,2007
`
`(51)
`
`Int. Cl.
`G06K 9100
`(2006.01)
`(52) U.S. Cl. ........................ 382/103; 382/128; 382/168
`(58) Field of Classification Search ................. 382/100,
`382/103, 107, 128-132, 168-180, 199-206,
`382/224, 291
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`3,725,576 A *
`3,760,377 A *
`4,364,089 A *
`4,386,848 A *
`4,783,828 A
`4,847,786 A *
`4,868,871 A *
`H713 H *
`
`4/1973 Crawford et al ............. 348/170
`9/1973 Attridge et al .............. 382/103
`12/1982 Woolfson
`................... 348/169
`6/1983 Clendenin et al. .......... 356/5.01
`11/ 1988 Sadjadi
`7/1989 Wang et al .................. 382/171
`9/1989 Watson, III ................. 382/103
`1111989 May et al .................... 382/103
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`FR
`
`0046110 Al
`0 380 659 Al
`0 394 959 A2
`2611063 Al
`
`2/1982
`8/1990
`10/1990
`8/1988
`
`FR
`JP
`
`2751772 Al
`06-205780 A
`
`1/1998
`7 /1994
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`Stephane G. Mallat, "A Theory for Multiresolution Signal Decom(cid:173)
`position: The Wavelet Representation", IEEE Transactions on Pat(cid:173)
`tern Analysis and Machine Intelligence, vol. 11, No. 7, Jul. 1989, pp.
`674-693.
`
`(Continued)
`
`Primary Examiner-Manav Seth
`(74) Attorney, Agent, or Firm-Novak Druce+Quigg; J.
`Rodman Steele, Jr.; Gregory M. Lefkowitz
`
`(57)
`
`ABSTRACT
`
`A method and apparatus for localizing an area in relative
`movement and for determining the speed and direction
`thereof in real time is disclosed. Each pixel of an image is
`smoothed using its own time constant. A binary value corre(cid:173)
`sponding to the existence of a significant variation in the
`amplitude of the smoothed pixel from the prior frame, and the
`amplitude of the variation, are determined, and the time con(cid:173)
`stant for the pixel is updated. For each particular pixel, two
`matrices are formed that include a subset of the pixels spa(cid:173)
`tially related to the particular pixel. The first matrix contains
`the binary values of the subset of pixels. The second matrix
`contains the amplitude of the variation of the subset of pixels.
`In the first matrix, it is determined whether the pixels along an
`oriented direction relative to the particular pixel have binary
`values representative of significant variation, and, for such
`pixels, it is determined in the second matrix whether the
`amplitude of these pixels varies in a known manner indicating
`movement in the oriented direction. In each of several
`domains, histogram of the values in the first and second
`matrices falling in such domain is formed. Using the histo(cid:173)
`grams, it is determined whether there is an area having the
`characteristics of the particular domain. The domains include
`luminance, hue, saturation, speed (V), oriented direction
`(Dl), time constant (CO), first axis (x(m)), and second axis
`(y(m)).
`
`7 Claims, 13 Drawing Sheets
`
`11
`
`42
`
`ZH
`
`Page 1 of 31
`
`SAMSUNG EXHIBIT 1001
`Samsung v. Image Processing Techs.
`
`

`
`US 7,650,015 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`4,906,940 A *
`5,008,946 A
`5,059,796 A *
`5,088,488 A
`5,109,425 A
`5,163,095 A
`5,164,992 A *
`5,181,254 A *
`5,247,583 A *
`5,278,921 A
`5,280,530 A *
`5,323,470 A *
`5,359,533 A
`5,384,865 A
`5,426,684 A *
`5,430,809 A *
`5,452,367 A *
`5,473,369 A *
`5,481,622 A *
`5,488,430 A
`5,500,904 A *
`5,565,920 A
`5,574,498 A *
`5,592,226 A
`5,592,237 A
`5,604,822 A *
`5,625,717 A
`5,631,697 A *
`5,644,386 A *
`5,684,715 A *
`5,694,495 A
`5,712,729 A
`5,717,784 A *
`5,774,581 A
`5,781,650 A *
`5,793,888 A
`5,798,787 A *
`5,812,193 A *
`5,825,922 A *
`5,883,969 A *
`5,912,980 A *
`5,912,994 A *
`5,930,379 A *
`5,982,909 A *
`6,005,493 A *
`6,037,976 A *
`6,049,363 A *
`6,084,989 A *
`6,148,092 A *
`6,226,388 Bl *
`6,256,608 Bl
`6,263,088 Bl *
`6,263,089 Bl *
`6,295,367 Bl *
`6,301,370 Bl*
`6,304,187 Bl
`6,335,985 Bl *
`6,339,651 Bl*
`6,381,363 Bl*
`6,400,830 Bl *
`6,434,254 Bl *
`6,453,069 Bl *
`6,486,909 Bl *
`6,597,738 Bl
`6,704,045 Bl *
`6,714,665 Bl *
`6,717,518 Bl
`
`3/1990 Greene et al. ............... 382/100
`4/1991 Ando
`10/1991 Nakamura .................. 382/103
`2/1992 Markowitz et al.
`4/1992 Lawton
`1111992 Kosaka
`.................. 382/118
`1111992 Turk et al.
`111993 Schweizer et al.
`.......... 382/100
`9/1993 Kato et al.
`.................. 382/164
`111994 Nakamura et al.
`111994 Trew et al. .................. 382/103
`6/1994 Kara et al.
`.................. 382/103
`10/1994 Ricka et al.
`111995 Loveridge
`6/1995 Gaborski et al ............... 378/62
`7/1995 Tomitaka .................... 382/173
`9/1995 Bick et al ................... 382/128
`12/1995 Abe ........................... 348/169
`111996 Gerhardt et al. ............. 382/103
`111996 Hong
`3/1996 Markandey et al .......... 382/103
`10/1996 Lee et al.
`1111996 Sakamoto et al. ........... 348/169
`111997 Lee et al.
`111997 Greenway et al.
`2/1997 Pearson et al. .............. 382/199
`4/1997 Hashimoto et al.
`.......... 348/172
`5/1997 Nishimura et al.
`7/1997 Jenkins et al .............. 356/4.01
`1111997 Palmer ....................... 348/473
`12/1997 Hara et al.
`111998 Hashimoto
`2/1998 Yanagishita et al. ......... 382/180
`611998 Fassnacht et al.
`7/1998 Lobo et al. .................. 382/118
`8/1998 Delanoy
`8/1998 Yamaguchi et al. ......... 348/152
`9/1998 Tomitaka et al ............. 348/369
`10/1998 Pearson et al. .............. 382/199
`3/1999 Le Gouzouguec et al.
`.. 382/103
`6/1999 Hunke ........................ 382/103
`6/1999 Norton et al. ............... 382/283
`7/1999 Rehg et al. .................. 382/107
`1111999 Erdem et al. ................ 382/103
`12/1999 Taniguchi et al. ........... 340/990
`3/2000 Wixson ...................... 348/122
`412000 Courtney et al. ............ 348/700
`712000 Eppler ........................ 382/293
`1112000 Qian .......................... 382/118
`5/2001 Qian et al.
`.................. 382/103
`7/2001 Malvar
`7/2001 Crabtree et al. ............. 382/103
`7/2001 Otsuka et al. ............... 382/107
`9/2001 Crabtree et al. ............. 382/103
`10/2001 Steffens et al. .............. 382/103
`10/2001 Pirim
`112002 Sambonsugi et al. ........ 382/190
`112002 Tian et al .................... 382/105
`412002 Murching et al.
`........... 382/164
`612002 Christian et al ............. 382/103
`8/2002 Wixson ...................... 382/103
`912002 Matsugu et al. ............. 382/173
`1112002 Pirim ......................... 348/143
`7 /2003 Park et al.
`3/2004 Brett ....................... 348/222.1
`3/2004 Hanna et al ................. 382/117
`412004 Pirim
`
`7,181,047 B2 *
`7,190,725 B2 *
`2002/0071595 Al *
`200210101432 Al
`2002/0120594 Al
`2002101567 53 Al
`200210169732 Al
`2003/0067978 Al *
`2003/0152267 Al
`
`212007 Pi rim ......................... 382/107
`3/2007 Pi rim .................... 375/240.27
`612002 Pi rim ......................... 382/107
`8/2002 Ohara et al.
`8/2002 Pi rim
`10/2002 Pi rim
`1112002 Pi rim
`4/2003 Pi rim .................... 375/240.03
`8/2003 Pi rim
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`WO
`WO
`WO
`WO
`WO
`WO
`
`11150676 A *
`WO 98/05002
`WO 99/36893
`WO 99/36894
`WO 00/11609 Al
`WO 00/11610 Al
`WO 01163557 A2
`
`6/1999
`2/1998
`7 /1999
`7 /1999
`3/2000
`3/2000
`8/2001
`
`OTHER PUBLICATIONS
`
`John G. Daugman, "Complete Discrete 2-D Gabor Transforms by
`Neural Networks for Image Analysis and Compression", IEEE
`Transaction on Acoustics, Speech and Signal Processing, vol. 36, No.
`7, Jul. 1988, pp. 1169-1179.
`Alberto Tomita, Jr., et al., "Hand Shape Extraction from a Sequence
`of Digitized Gray-Scale Images", IECON '94, 20th International
`Conference on Industrial Electronics, Control and Instrumentation,
`vol. 3 of 3, Special Sessions, Signal Processign and Control, pp.
`1925-1930.
`Giacomo lndiveri et al., "System Implementations of Analog VLSI
`Velocity Sensors", 1996 IEEE Proceedings ofMicroNeuro '96, pp.
`15-22.
`Pierre-Francois Riiedi, "Motion Detection Silicon Retina Based on
`Event Correlations", 1996 IEEE Proceedings ofMicroNeuro '96, pp.
`23-29.
`Revue Trimestrielle Des <<Techniques de Lingenieur>>,
`"Instantanes Technique" Techniques De ingenieur, Mars 1997-N° 5
`(40F), ISSN 0994-0758.
`Es Professionnels de Linformatique En Entreprise Magazine,
`"Objectif Securite Des Reseaux", N° 24, Jan. 1997.
`Electroncique
`International Hebdo, Dec. 5, 1996-N° 245,
`"Premier ... oeil'', Francoise Gru svelet (with translation).
`Nabeel Al Adsani, "For Immediate Release The Generic Visual Per(cid:173)
`ception Processor", Oct. 10. 1997, p. 1.
`Colin Johnson, "Vision Chip's Circuitry Has Its Eye Out For You",
`http://192.215 .107.74/wire/news/1997 /09/0913vision.htrnl, pp. 1-3.
`The Japan Times, :"British firm has eye on the future", Business &
`Technology, Tuesday, Nov. 18, 1997, 4th Edition.
`Inside the Pentagon's, Inside Missile Defense, an exclusive biweekly
`report on U.S. missile defense programs, procurement and
`policymaking, "Missile Technology" vol. 3, No. 16-Aug. 13, 1997, p.
`5.
`Electronique, "Le Mechanisme de la Vision Humaine Dans Le
`Silicium", Electronique Le Mensuel Des Ingenieurs De Conception,
`No. 68, Mar. 1997, ISSN 1157-1151 (with translation).
`"Elecktronik Revue" ER, Eine Elsevier-Thomas-Publikation,
`Jalugang 8, Mar. 1997, NR. 3. ISSN0939-l 134.
`"Un Processor de Perception Visuelle", LehAUT pARLEUR, 25F
`Des solutions electroniques pour tous, N° 1856, Jan. 15, 1997 (with
`translation).
`"Realiser Un Decodeur Pour TV Numberique", Electronique, Le
`Mensuel Des Ingenieurs De Conception, No. 66, Jan. 1997.
`Kenichi Yamada, et al, "Image Understanding Based on Edge Histo(cid:173)
`gram Method for Rear-End Collision Avoidance System", Vehicle
`Navigation & Information Systems Conference Proceedings; ( 1994 ),
`pp. 445 450 published Aug. 31, 2004; XP 000641348.
`* cited by examiner
`
`SAMSUNG EXHIBIT 1001
`Page 2 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 1of13
`
`US 7,650,015 B2
`
`11.z
`_____ ooo _ _ _ _ _
`
`S(PI)
`
`12
`
`ZH < V.Dl)
`( 1----.,,,.L-_....,...J
`1
`lOa _J
`l
`
`SR
`
`13
`
`11
`
`14
`
`10
`
`\_ lla
`
`FIG. J
`
`SAMSUNG EXHIBIT 1001
`Page 3 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 2of13
`
`US 7,650,015 B2
`
`.... n·············I: ~- -·· . ... . .. -·~ ::·· ······ ..... ---· .... l
`r-:t.'.'A SfP
`:
`J=:
`:
`; :
`j : .••...• :
`:
`
`HP
`
`LO
`
`CI
`
`15
`
`3
`
`:
`:
`
`16
`
`S<Pn
`
`12
`
`20
`
`19
`
`i
`
`l
`l
`3
`1
`co
`or
`v
`~
`VT
`SR
`F
`z _: ···················-···········-················ ........................................................................... _: - z1
`FCG.2
`
`3
`
`)
`
`13
`
`• / r-~c;;;; ·--,--------;~!;-~~I-~~=-----~------·-r 15
`
`FIG.3
`
`BP: 1L..
`20 -r-1-:
`~ : ~~
`j
`15e \.......
`SE
`I
`:
`SE -.·,_____,.. _ _....., +--t-1+-
`:
`N
`j
`•
`!
`15f _/' .......... · LI
`/
`!
`lS I
`1--J-1-1_.:-+-+-+--tt DP= I -+ CO= CI- U
`._,_...,..... c{ 1
`DP=O.... CO=CI+U -
`
`AB }s
`AB > SE-+ DP ;:: I
`AB ~ SE--* DP = ()
`
`8-
`
`.d
`
`DP
`
`( ........ !
`
`I
`
`16 -
`
`:
`:
`:
`i
`
`:
`:
`:
`:DP
`.
`
`I
`
`15a
`
`l 5b
`
`lSc
`
`-
`
`I
`I
`:
`: •
`' . I
`I . . . I
`LO =LI + Pl - LI
`I • I • I
`co
`'
`' •
`.._--~~~~--~~-LO
`
`3 ........ "'1s
`co
`
`LO
`
`N
`
`LI
`.______.
`
`S(PI)
`
`I
`I
`
`I
`
`I
`I
`
`O~ COs:N
`
`co
`~~ 3
`co 1--~~~~~-.-~~--+
`
`18 j
`
`\_ 15d
`
`~--~-----------------------------~------------·
`
`SAMSUNG EXHIBIT 1001
`Page 4 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 3of13
`
`US 7,650,015 B2
`
`18
`
`HP BL
`
`DP co
`l
`
`r1 "\
`
`I rzJ
`
`SL
`
`SC
`
`HP
`
`\_ 19
`
`!a...!?.... c~M3
`I'd ~~I
`--,-,
`
`PB.B..:
`
`g :h
`
`I
`
`FIG.4
`
`2
`
`3~1
`•·~·o
`
`s
`
`6
`
`7
`
`FIG. 5
`
`FIG.6
`
`SAMSUNG EXHIBIT 1001
`Page 5 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 4of13
`
`US 7,650,015 B2
`
`FJG. 7
`
`+ I
`
`0
`
`0
`
`+ 1
`
`o
`
`l'-M3
`
`M9
`
`• 1
`
`0
`
`0
`
`- 1
`
`FIG.&
`
`SAMSUNG EXHIBIT 1001
`Page 6 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 5of13
`
`US 7,650,015 B2
`
`rMRu
`
`r L_.u.3
`/I 0 /
`DPll ....... 1 /I 1/1 ,// 1 /
`COu, ... /-.3 / 3 / 02 /2 /1 /1
`
`L.u.
`
`Ex
`
`/
`
`FIG.9
`
`FIG. 9a.
`
`I z1
`!---------------'-'--=\-------------- -------------!---- ~-'.--=\----L-~~-
`"
`
`F
`
`I
`
`I
`'
`'--··-· ••••••••• ••••••••••••••• •••••••&.•••• •·••• •••••••••••••••••••••••••••••·•~···••••••••••• "''''"'"'""''"""'"" ••••••••.,•u•••••••••• •
`
`I
`
`' I
`' I
`I . I
`' I z
`
`F1G. IO
`
`S(PI) ;
`
`•
`•
`' I
`
`I
`
`DL
`
`lo'
`
`ZH
`
`)
`
`'
`'
`' ' . . I
`'
`SR •
`I .
`v
`VL • .
`co • .
`
`SAMSUNG EXHIBIT 1001
`Page 7 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 6of13
`
`US 7,650,015 B2
`
`F
`
`co
`SR
`--~---------- ---------------------- ----------- ---------- ---------------------- ---~
`
`VL
`
`DI
`
`v
`
`24 ,
`
`~iSTObMM
`lbRHftilOlJ
`fdfb
`VI .--. PRDct5SiW
`
`25 -..
`
`V2
`
`y
`
`I- 30
`
`SSR
`
`~1
`
`23 J
`
`J •
`
`)
`34
`Li HEAR.
`COh8i Nf\TiON
`
`I
`
`V5
`
`I
`
`L/1
`l'-J
`
`'7
`
`26 -.......
`
`VJ
`
`27 \
`
`V4
`
`32
`
`l
`
`l
`
`SDI
`
`31 l SV
`
`.
`xy(m)
`36 ~ COHPO~f6 ~GN~/,
`r----.
`I.__~~~
`
`I MnVitJv AWA BLO{J(
`
`ZH
`
`35
`
`V6
`
`28 _/
`
`\_ 29
`
`y(m)i
`
`r37
`
`HP
`
`SL
`
`SC
`
`'
`
`x(m)1
`
`'PATA WJE
`
`Cltf'IN&& BlDc.J<:.
`
`1 x(m)o
`
`FIG. 11
`
`SAMSUNG EXHIBIT 1001
`Page 8 of 31
`
`

`
`U.S. Patent
`
`Jan. 19, 2010
`
`Sheet 7of13
`
`US 7,650,015 B2
`
`40
`
`xM
`
`lb
`
`x
`
`la
`
`FIG. 1:2
`
`1'Dltff~
`CON~R.Nep
`ey l\NiiLYS!'5
`
`~= KB>PT.5
`R. HflX
`1~R<sroP
`
`FIG. I+
`
`y
`
`.··
`
`·• .. · ..
`··· ......
`··· ...
`
`38
`
`Cn.
`x
`
`FrG. 14(1,
`
`SAMSUNG EXHIBIT 1001
`Page 9 of 31
`
`

`
`U.S. Patent
`
`Jan. 19, 2010
`
`Sheet 8of13
`
`US 7,650,015 B2
`
`112'\
`
`MIN
`MAX
`RMAX
`POSRMAX
`NbPTS
`
`31
`
`OUT
`
`(
`
`ADDRESS
`I I I I
`1--1-..L-J.-.....__._--'--'i-1 ) CLASSIFIER 25b
`J
`
`I
`106
`
`OUT
`
`110
`
`/
`2
`+1/+0
`
`VALIDATION V2
`
`DATA
`
`out DATA
`IN
`
`OUT
`
`MEMORY
`100
`
`INIT
`DATA
`
`CLOCK
`VALIDATION
`
`H ISTOGRAM
`FO RMAT!ON %--
`25a
`
`DATA(V)--
`c OUNTER
`
`'
`MUX
`102
`I
`INIT
`
`MUX
`104
`t
`INIT
`
`-
`
`,__
`
`......-
`
`DATA(V)
`
`23
`
`FilG.13
`
`SAMSUNG EXHIBIT 1001
`Page 10 of 31
`
`

`
`U.S. Patent
`
`Jan. 19, 2010
`
`Sheet 9of13
`
`US 7,650,015 B2
`
`rv
`13 G
`p\
`
`I 43
`
`11
`
`42
`
`s
`
`ZH
`
`10b B
`
`FiG.16
`
`13A
`
`3
`
`4
`
`2
`
`f,-G·24
`
`SAMSUNG EXHIBIT 1001
`Page 11 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 10 of 13
`
`US 7,650,015 B2
`
`I
`I
`~T
`J
`r
`J
`
`I
`I
`t'-
`
`Fig.
`
`IG
`
`y
`
`124y
`
`j127d
`Xd
`i--~~~~~~-t--~~--------
`
`I
`
`1 --------L-- ""
`v/ I
`
`t
`I
`J
`I
`.,. .
`/
`
`Sc
`
`'----------
`
`z
`
`7b
`
`Yb
`
`Fig.
`
`l7
`
`x
`
`I
`
`i26b/
`
`SAMSUNG EXHIBIT 1001
`Page 12 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 11 of 13
`
`US 7,650,015 B2
`
`XMIN
`
`XMAX
`
`r--rG-- 23
`
`Ya
`
`Yb
`
`Fig. 18
`
`SAMSUNG EXHIBIT 1001
`Page 13 of 31
`
`

`
`U.S. Patent
`
`Jan. 19, 2010
`
`Sheet 12 of 13
`
`US 7,650,015 B2
`
`')...OO
`
`Cf\t\~~~
`
`?o~
`
`~ ~oc.e.s-::.rJ G-
`'SysrG r'\
`
`?-lo
`
`Jll
`
`')\6
`
`SAMSUNG EXHIBIT 1001
`Page 14 of 31
`
`

`
`U.S. Patent
`
`Jan.19,2010
`
`Sheet 13 of 13
`
`US 7,650,015 B2
`
`212
`
`&-----------
`
`' 111
`
`1 11
`I 11
`I it
`
`---------
`-----------
`
`Z.24
`
`i
`YMAXJ
`- - - ... - -
`-Yff+nR1 -
`---------~--]-
`A-t1 it YMut
`:
`: ,
`I
`
`a
`
`:
`
`:
`
`I
`I
`I
`I
`XA-nKX
`1 B+nK
`:
`:
`.222
`){HIN~ ~XMAX~
`
`SAMSUNG EXHIBIT 1001
`Page 15 of 31
`
`

`
`US 7,650,015 B2
`
`1
`IMAGE PROCESSING METHOD
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`The present application claims the priority of U.S. appli(cid:173)
`cation Ser. No. 091792,294, filed Feb. 23, 2001, now U.S. Pat.
`No. 7,181,047; which claims priority to U.S. application Ser.
`No. 09/230,502, filed Jan. 26, 1999, now U.S. Pat. No. 6,486,
`909; which claims priority to International Application No.
`PCT/EP98/05383, filed Aug. 25, 1998; all of which are incor(cid:173)
`porated herein by reference in their entirety.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention relates generally to an image pro(cid:173)
`cessing apparatus, and more particularly to a method and
`apparatus for identifying and localizing an area in relative
`movement in a scene and determining the speed and oriented
`direction of the area in real time.
`2. Description of the Related Art
`The human or animal eye is the best known system for
`identifying and localizing an object in relative movement, and
`for determining its speed and direction of movement. Various
`efforts have been made to mimic the function of the eye. One
`type of device for this purpose is referred to as an artificial
`retina, which is shown, for example, in Giacomo Indiveri et.
`al, Proceedings ofMicroNeuro, 1996, pp. 15-22 (analog arti(cid:173)
`ficial retina), and Pierre-Francois Ruedii, Proceedings of
`MicroNeuro, 1996, pp. 23-29, (digital artificial retina which
`identifies the edges of an object). However, very fast and high
`capacity memories are required for these devices to operate in
`real time, and only limited information is obtained about the
`moving areas or objects observed Other examples of artificial 35
`retinas and similar devices are shown in U.S. Pat. Nos. 5,694,
`495 and 5,712,729.
`Another proposed method for detecting objects in an image
`is to store a frame from a video camera or other observation
`sensor in a first two-dimensional memory. The frame is com(cid:173)
`posed of a sequence of pixels representative of the scene
`observed by the camera at time to. The video signal for the
`next frame, which represents the scene at time to is stored in
`a second two-dimensional memory. If an object has moved
`between times to and tO the distanced by which the object, as 45
`represented by its pixels, has moved in the scene between t,
`and to is determined. The displacement speed is then equal to
`d/T, where T=tl-tO. This type of system requires a very large
`memory capacity if it is used to obtain precise speed and
`oriented direction. Information for the movement of the 50
`object. There is also a delay in obtaining the speed and dis(cid:173)
`placement direction information corresponding to tl+R,
`where R is the time necessary for the calculations for the
`period tO-tl system. These two disadvantages limit applica(cid:173)
`tions of this type of system.
`Another type of prior image processing system is shown in
`French Patent No. 2, 611, 063, of which the inventor hereofis
`also an inventor. This patent relates to a method and apparatus
`for real time processing of a sequenced data flow from the
`output of a camera in order to perform data compression. A 60
`histogram of signal levels from the camera is formed using a
`first sequence classification law. A representative Gaussian
`function associated with the histogram is stored, and the
`maximum and minimum levels are extracted. The signal lev-
`els of the next sequence are compared with the signal levels 65
`for the first sequence using a fixed time constant identical for
`each pixel. A binary classification signal is generated that
`
`2
`characterizes the next sequence with reference to the classi(cid:173)
`fication law. An auxiliary signal is generated from the binary
`signal that is representative of the duration and position of a
`range of significant values. Finally, the auxiliary signal is
`used to generate a signal localizing the range with the longest
`duration, called the dominant range. These operations are
`repeated for subsequent sequences of the sequenced signal.
`This prior process enables data compression, keeping only
`interesting parameters in the processed flow of sequenced
`10 data. In particular, the process is capable of processing a
`digital video signal in order to extract and localize at least one
`characteristic of at least one area in the image. It is thus
`possible to classify, for example, brightness and/or chromi(cid:173)
`nance levels of the signal and to characterize and localize an
`15 object in the image.
`Another system is also known from WO 98/05002, of
`which the inventor hereof is also an inventor. This system
`enables real time detection, location and determination of the
`speed and direction of movement of an area of relative move-
`20 ment in a scene. It includes a time processing unit of a spatial
`processing unit in order to determine said speed and direction
`of movement.
`U.S. Pat. No. 5,488,430 detects and estimates a displace(cid:173)
`ment by separately determining horizontal and vertical
`25 changes of the observed area. Difference signals are used to
`detect movements from right to left or from left to right, or
`from top to bottom or bottom to top, in the horizontal and
`vertical directions respectively. This is accomplished by car(cid:173)
`rying out an EXCLUSIVE OR function on horizontal/vertical
`30 difference signals and on frame difference signals, and by
`using a ratio of the sums of the horizontal/vertical signals and
`the sums of frame difference signals with respect to a Kx3
`window. Calculated values of the image along orthogonal
`horizontal and vertical directions are used with an identical
`repetitive difference K in the orthogonal directions, this dif(cid:173)
`ference K being defined as a function of the displacement
`speeds that are to be determined. The device determines the
`direction of movement along each of the two orthogonal
`directions by applying a set of calculation operations to the
`40 difference signals, which requires very complex computa(cid:173)
`tions. Additional complex computations are also necessary to
`obtain the speed and oriented direction of displacement (ex(cid:173)
`traction of a square root to obtain the amplitude of the speed,
`and calculation of the arctan function to obtain the oriented
`direction), starting from projections on the horizontal and
`vertical axes. This device also does not smooth the pixel
`values using a time constant, especially a time constant that is
`variable for each pixel, in order to compensate for excessively
`fast variations in the pixel values.
`Finally, Alberto Tomita Sales Representative. and Rokuva
`Ishii, "Hand Shape Extraction from a Sequence of Digitized
`Gray-Scale Images," Institute of Electrical and Electronics
`Engineers, Vol. 3, 1994, pp. 1925-1930, detects movement by
`subtracting between successive images, and forming histo-
`55 grams based upon the shape of a human hand in order to
`extract the shape of a human hand in a digitized scene. The
`histogram analysis is based upon a gray scale inherent to the
`human hand. It does not include any means of forming his-
`tograms in the plane coordinates. The sole purpose of the
`method is to detect the displacement of a human hand, for
`example, in order to replace the normal computer mouse by a
`hand, the movements of which are identified to control a
`computer.
`It would be desirable to have an image processing system
`which has a relatively simple structure and requires a rela(cid:173)
`tively small memory capacity, and by which information on
`the movement of objects within an image can be obtained in
`
`SAMSUNG EXHIBIT 1001
`Page 16 of 31
`
`

`
`US 7,650,015 B2
`
`3
`real-time. It would also be desirable to have a method and
`apparatus for detecting movements that are not limited to the
`hand, but to any object (in the widest sense of the term) in a
`scene, and which does not use histograms based on the gray
`values of a hand, but rather the histograms of different vari(cid:173)
`ables representative of the displacement and histograms of
`plane coordinates. Such a system would be applicable to
`many types of applications requiring the detection of moving
`and non-moving objects.
`
`SUMMARY OF THE INVENTION
`
`10
`
`4
`ti on relative to the particular pixel, comprise applying nested
`nxn matrices, where n is odd, centered on the particular pixel
`to the pixels within each of the first and second matrices. The
`process then includes the further step of determining the
`smallest nested matrix in which the amplitude signal varies
`along an oriented direction around the particular pixel.
`In an alternative embodiment, the first and second matrices
`are hexagonal matrices centered on the particular pixel. In this
`embodiment, the steps of determining in the first matrix
`whether the particular pixel and the pixels along an oriented
`direction relative to the particular pixel have binary values of
`a particular value representing significant variation, and the
`step of determining in the second matrix whether the ampli-
`15 tude signal varies in a predetermined criteria along an ori(cid:173)
`ented direction relative to the particular pixel, comprise
`applying nested hexagonal matrices of varying size centered
`on the particular pixel to the pixels within each of the first and
`second matrices. The process then further includes determin-
`20 ing the smallest nested matrix in which the amplitude signal
`varies along an oriented direction around the particular pixel.
`In a still further embodiment of the invention, the first and
`second matrices are inverted L-shaped matrices with a single
`row and a single column. In this embodiment, the steps of
`25 determining in the first matrix whether the particular pixel
`and the pixels along an oriented direction relative to the
`particular pixel have binary values of a particular value rep(cid:173)
`resenting significant variation, and the step of determining in
`the second matrix whether the amplitude signal varies in a
`30 predetermined criteria along an oriented direction relative to
`the particular pixel, comprise applying nested nxn matrices,
`where n is odd, to the single line and the single column to
`determine the smallest matrix in which the amplitude varies
`on a line with the steepest slope and constant quantification.
`If desired, successive decreasing portions of frames of the
`input signal may be considered using a Mallat time-scale
`algorithm, and the largest of these portions, which provides
`displacement, speed and orientation indications compatible
`with the value of p, is selected.
`In a process of smoothing an input signal, for each pixel of
`the input signal, i) the pixel is smoothed using a time constant
`(CO) for that pixel, thereby generating a smoothed pixel value
`(LO), ii) it is determined whether there exists a significant
`variation between such pixel and the same pixel in a previous
`frame, and iii) the time constant (CO) for such pixel to be used
`in smoothing the pixel in subsequent frames of the input
`signal is modified based upon the existence or non-existence
`of a significant variation.
`The step of determining the existence of a significant varia-
`tion for a given pixel preferably comprises determining
`whether the absolute value of the difference (AB) between the
`given pixel value (PI) and the value of such pixel in a
`smoothed prior frame (LI) exceeds a threshold (SE). The step
`of smoothing the input signal preferably comprises, for each
`pixel, i) modifying the time constant (CO) for pixel such
`based upon the existence of a significant variation as deter(cid:173)
`mined in the prior step, and ii) determining a smoothed value
`for the pixel (LO) as follows:
`
`The present invention is a process for identifying relative
`movement of an object in an input signal, the input signal
`having a succession of frames, each frame having a succes(cid:173)
`sion of pixels. For each pixel of the input signal, the input
`signal is smoothed using a time constant for the pixel in order
`to generate a smoothed input signal. For each pixel in the
`smoothed input signal, a binary value corresponding to the
`existence of a significant variation in the amplitude of the
`pixel between the current frame and the immediately previous
`smoothed input frame, and the amplitude of the variation, are
`determined.
`Using the existence of a significant variation for a given
`pixel, the time constant for the pixel, which is to be used in
`smoothing subsequent frames of the input signal, is modified.
`The time constant is preferably in the form 2F, and is
`increased or decreased by incrementing or decrementing p.
`For each particular pixel of the input signal, two matrices are
`then formed: a first matrix comprising the binary values of a
`subset of the pixels of the frame spatially related to the par(cid:173)
`ticularpixel; anda second matrix comprising the amplitude of
`the variation of the subset of the pixels of the frame spatially
`related to the particular pixel. In the first matrix, it is deter(cid:173)
`mined whether the particular pixel and the pixels along an 35
`oriented direction relative to the particular pixel have binary
`values of a particular value representing significant variation,
`and, for such pixels, it is determined in the second matrix
`whether the amplitude of the pixels along the oriented direc(cid:173)
`tion relative to the particular pixel varies in a known manner 40
`indicating movement in the oriented direction of the particu-
`lar pixel and the pixels along the oriented direction relative to
`the particular pixel. The amplitude of the variation of the
`pixels along the oriented direction determines the velocity of
`movement of the particular pixel and the pixels along the 45
`oriented direction relative to the particular pixel.
`In each of one or more domains, a histogram of the values
`distributed in the first and second matrices falling in each such
`domain is formed. For a particular domain, an area of signifi(cid:173)
`cant variation is determined from the histogram for that 50
`domain. Histograms of the area of significant variation along
`coordinate axes are then formed. From these histograms, it is
`determined whether there is an area in movement for the
`particular domain. The domains are preferably selected from
`the group consisting of i) luminance, ii) speed (V), iii) ori- 55
`ented direction (Dl), iv) time constant (CO), v) hue, vi)
`saturation, and vii) first axis (x(m)), and viii) second axis
`(y(m)).
`In one embodiment, the first and second matrices are
`square matrices, with the same odd number of rows and 60
`columns, centered on the particular pixel. In this embodi(cid:173)
`ment, the steps of determining in the first matrix whether the
`particular pixel and the pixels along an oriented direction
`relative to the particular pixel have binary values of a particu-
`lar value representing significant variation, and the step of 65
`determining in the second matrix whether the amplitude sig(cid:173)
`nal varies in a predetermined criteria along an oriented direc-
`
`PI-LI
`LO = LI + ----CO
`
`Time constant (CO) is preferably in the form 2P, and pis
`incremented in the event that AB<SE and decremented in the
`event AB>=SE.
`
`SAMSUNG EXHIBIT 1001
`Page 17 of 31
`
`

`
`US 7,650,015 B2
`
`5
`In this process, the system generates an output signal com(cid:173)
`prising, for each pixel, a binary value (DP) indicating the
`existence or non-existence of a significant variation, and the
`value of the time constant (CO). The binary values (DP) and
`the time constants (CO) are preferably stored in a memory
`sized to correspond to the frame size.
`A process for identifying an area in relative movement in
`an input signal includes the steps of:
`generating a first array indicative of the existence of sig(cid:173)
`nificant variation in the magnitude of each pixel between a 10
`current frame and a prior frame;
`generating a second array indicative of the magnitude of
`significant variation of each pixel between the current frame
`and a prior frame;
`establishing a first moving matrix centered on a pixel under 15
`consideration and comprising pixels spatially related to the
`pixel under consideration, the first moving matrix traversing
`the first array for consideration of each pixel of the current
`frame; and
`determining whether the pixel under consideration and 20
`each pixel of the pixels spatially related to the pixel under
`consideration along an oriented direction relative thereto
`within the first matrix are a particular value representing the
`presence of significant variation, and if so, establishing in a
`second matrix within the first matrix, centered on the pixel 25
`under consideration, and determining whether the amplitude
`of the pixels in the second matrix spatially related to the pixel
`under consideration along an oriented direction relative
`thereto are indicative of movement along such oriented direc(cid:173)
`tion, the amplitude of the variation along the oriented direc- 30
`ti on being indicative of the velocity of movement, the size of
`the second matrix being varied to identify the matrix size
`most indicative of movement