I lllll llllllll Ill lllll lllll lllll lllll lllll lllll lllll lllll llllll llll llll llll
`
`US008989445B2
`
`(12) United States Patent
`Pi rim
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 8,989,445 B2
`Mar.24,2015
`
`(54)
`
`IMAGE PROCESSING APPARATUS AND
`METHOD
`
`(71) Applicant: lmage Processing Technologies LLC,
`Suffern, NY (US)
`
`(72)
`
`Inventor: Patrick Pirim, Paris (FR)
`
`(73) Assignee: Image Pr ocessing Technologies, LLC,
`Suffern, NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the tenn of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`EP
`EP
`
`(56)
`
`References C ited
`
`U.S. PATENT DOCUMENTS
`
`3,725,576 A
`3.760,377 A
`
`4/1973 Crawford et al.
`9/ 1973 Attridge et al.
`(Continued)
`
`FORE IGN PA:rENT DOCUMENTS
`
`2/ l982
`0046JJO
`0380659
`8/ l990
`(Continued)
`OTrJER PUBLICATIONS
`
`(21) Appl. No.: 14/449,809
`
`(22) Filed:
`
`Aug.13, 2014
`
`(65)
`
`Prior Publication Data
`
`US 2015/0023559 A.I
`
`Jan. 22, 2015
`
`Related U.S. Application Data
`
`( 60) Continuation of application No. 14/215,358, filed on
`Mar. 17, 2014, which is a continuation of application
`No. 12/620,092, filed on Nov. 17, 2009, now Pat. No.
`8,805,001 , which is a continuation of application No.
`
`(Continued)
`
`(30)
`
`Foreign Application Priority Data
`
`Jul. 26, 1996
`
`(FR) ................. ..................... 96 09420
`
`(51)
`
`Int. C l.
`G06K9100
`G06T 7120
`
`(2006.01)
`(2006.01)
`(Continued)
`
`(52) U.S. C l.
`CPC ...
`
`G061' 712033 (2013.01); G06K 916212
`(2013.01); H04N 5123296 (2013.01); G06T
`1207110016 (2013.0 1); G06T 2207130241
`(2013.01)
`............ 382/103; 382/128; 382/168; 348/143
`USPC
`(58) Field of C lassification Search
`None
`See application file for complete search history.
`
`"British firm has eye on the future", Business & Technology(Nov. 18,
`1997) 41h Edition.
`
`(Continued)
`
`Primary Examiner - Manav Seth
`(74) Attorney. Agent. or Firm - Novak Dnice Connolly
`Bove+ Quigg, LLP
`ABSTRACT
`(57)
`A method and apparanis for localizing an area in relative
`movement and for determining the spt--ed 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 detenuiut.'CI. 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.
`ln the first matrix, it is detennined 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 dcten11ined in the second matrix whether the
`amplitude of these pixels varies in a known manner indicating
`movement in the oriented direction. ln each of several
`domains, histogram of the values in the first and second
`matrices falling in such domain is fom1ed. Using the histo(cid:173)
`grams, it is determined whether there is an area having the
`characteristics of the particular domain. The domains include
`h.uninance, hue, saturation, speed (V), oriented direction
`(D 1 ), time constant (CO), first axis (x(m)), and second axis
`(y(m)).
`
`30 C laims, 13 Drawing Sheets
`
`v
`
`13
`
`11
`
`42
`
`ZH
`
`10b
`
`Page 1 fo 30
`
`SAMSUNG EXHIBIT 1001
`Samsung v. Image Processing Techs.
`
`

`
`US 8,989,445 B2
`Page2
`
`Related U.S. Applicat ion Data
`
`I J/ 676,926, filedou Feb. 20, 2007, now Pat. No. 7,650,
`OJ 5 , which is a division ofapplic<llion No. 091792,294,
`filed on Feb. 23. 2001, now Pat. No. 7,181,047, which
`is a continuation-in-part of application No. 09/230,
`502, filed as application No. PCT/FR97/01354 on Jul.
`22, 1997, now Pat. No. 6 ,486,909, and a continuation-
`in-part of application No. PCT/EP98/05383, filed o n
`Aug. 25. 1998.
`
`(51)
`
`lnt. Cl.
`G06K9162
`H04N51232
`
`(2006.01)
`(2006.01)
`
`(56)
`
`References C ited
`
`U.S. PATENT DOCUM ENTS
`
`121 1982 Woolf son
`4 ,364,089 A
`6/ 1983 Clendenin el al.
`4 ,386,848 A
`4 ,706,120 A " 11/ 1987 Slaugh1 er et al. ............. 348/ 114
`4 ,719,584 A
`111988 Rue et al.
`1111988 Sadjadi
`4 ,783,828 A
`7/ 1989 Wang et al.
`4 ,847,786 A
`9/ 1989 Watson, lll
`4 ,868,871 A
`H713 H
`1111989 May el al.
`4 ,906,940 A
`311990 Greeneet al.
`4/ 199 1 Ando
`5,008.946 A
`10/ 199 J Nakamma
`5,059.796 A
`211992 Markowir.t et al.
`5,088,488 A
`5,109,425 A
`4/ 1992 Lawton
`5,123,055 A
`61l992 Kasdan
`5,163,095 A
`J 111992 Kosaka
`5,164,992 A
`11/ 1992 Turkel al.
`5, 18 1,254 A
`1/ 1993 Schweizer el al.
`911993 Kato etal.
`5,247,583 A
`5,263,098 A
`1111993 Horikami
`5,278,921 A
`111994 Nakamura et al.
`5,280,530 A
`l/ l994 Trew et al.
`6/ 1994 Kara et al.
`5,323,470 A
`5,359,533 A
`10/1994 Ricka et al.
`5,360,968 A
`1 l/ 1994 Scott
`5,384,865 A
`l/ 1995 Loveridge
`611995 Gaborsk.i et al.
`5,426,684 A
`5,430,809 A
`7/ 1995 Tomitaka
`5,452,367 A
`9/ l995 Bicket al.
`5,473.369 A
`121 1995 Abe
`5,481 ,622 A
`l/ 1996 Gerhardt et al.
`5,488,430 A
`l/ 1996 Hong
`3/ 1996 Markandey ct al.
`5,500,904 A
`511996 Hashima et al. .............. 700/253
`5,521 ,843 A "'
`8/ 1996 Bo lie et al ..................... 382/ 190
`5,546,475 A "
`5,565,920 A
`10/l996 Lee et al.
`J 111996 Sakamoto et al.
`5,574,498 A
`5,592.226 A
`l/ 1997 Lee et al.
`l/ 1997 Greenway et al.
`5,592,237 A
`211997 Pearson et al.
`5,604,822 A
`5,608,820 A
`3/ 1997 Vaidyanathan
`5,610,653 A
`311997 Abecassis
`5,625,717 A
`4/ l997 Hashimo10 et al.
`5/ 1997 Schindl er ...................... 345/592
`5,630,037 A "
`5,631 ,697 A
`5/ 1997 Nishimura et al.
`5,644,386 A
`7/I997 Jenkins et al.
`1111997 Palmer
`5,684.715 A
`5,694,495 A
`1211997 Hara et al.
`5,712,729 A
`l/ 1998 Hashimo10
`5,7 17 ,784 A
`21 l998 Yanagishila et al.
`5,774,581 A
`6/ 1998 Fassnacht et al.
`7/ 1998 Lobo et al.
`5,781.650 A
`5,793,888 A
`811998 Delanoy et al.
`811998 Yamagllchi et al.
`5,798.787 A
`9/ 1998 Tomi taka el al.
`5,8 12,193 A
`5,825,922 A
`10/ 1998 Pearson et al.
`5,883,969 A
`3/l999 Le Gouzouguec et al.
`5,912,980 A
`6/ 1999 Hunke
`611999 Norton et al.
`5.912,994 A
`
`5.930,379 A
`5,982,909 A
`5.982,944 A
`6.005,493 A
`6,037,976 A
`6.049,363 A
`6.084,989 A
`6.148,092 A
`6,226,388 BJ
`6.256,608 Bl
`6,263,088 Bl
`6.263,089 B I
`6,295,367 B l
`6.30 l ,370 B l
`6.304.1 87 Bl
`6,312,385 BJ
`6.335,985 Bl
`6,339,65 1 Bl
`6,38 1,363 B I
`6.400,830 B l
`6.434,254 Bl
`6,453,069 Bl
`6,486,909 BJ
`6,597,738 Bl
`6,704,045 Bl
`6.7 14,665 B l
`6.7 17,5 18 B l
`7.181,047 82
`7.190.725 B2
`7,650,015 B2
`8.116,527 B2
`8,805,001 B2
`2002/0071595 A I
`2002/0101432 Al
`2002/0120594 Al
`2002/0156753 Al
`2002/0169732 Al
`2003/0067978 A l
`2003/0 I 52267 Al
`2007/0140526 Al
`
`7/ 1999 Rehget al.
`JJ/ J 999 Erdem et al.
`l l/ J 999 Vaidyanathan et al.
`12/ 1999 Taniguchi et al.
`312000 Wixson
`4/2000 Courtney el al.
`712000 Eppler
`11/2000 Qian
`51200 I Qian et al.
`7/2001 Malvar
`7 /200 l Crabtree et al.
`712001 Otsuka el al.
`9/200 l Crabtree et al.
`l 0/200 l Steffens et al.
`10/2001 Pirim
`J J/2001 Mo et al.
`l/2002 Sambonsugi et al.
`1/2002 Tian e( al.
`4/2002 Murching et al.
`612002 Christian el al.
`812002 Wixson
`9/2002 Matsugu ct al.
`J J/2002 Pirim
`7/2003 Park et al.
`3/2004 Brel'l
`312004 Hanna er al.
`4/2004 Pi rim el al.
`2/2007 Pirim
`3/2007 Pirim
`J/2010 Pi rim
`2/20 12 Sabol el al.
`8120 14 Pi rim
`6/2002 Pirim
`812002 Ohara el al.
`812002 Pirim
`10/2002 Pirim
`J J/2002 Pirim
`4/2003 Pi ri rn
`812003 Pirirn
`612007 Pirim
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`FR
`FR
`JP
`JP
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`WO
`
`0394959
`0574831
`2751772
`2611063
`275 1772
`06205780
`11150676
`9805002
`9936694
`9936893
`9936894
`0011609
`0011610
`0011639
`0163557
`
`l0/ 1990
`12/1993
`l./ 1998
`8/ 1988
`111998
`7/ 1994
`6/ 1999
`2/ 1998
`7/ 1999
`7/ 1999
`7/ 1999
`3/2000
`3/2000
`3/2000
`8/2001
`
`OTHER PUBLICATIONS
`
`"Elektronik revue'', Eine Elsevier-Thomas-Publikation, Jahrgang
`(Mar. 8, 1997) JSSN: 0939-1134.
`.. Inside the Pentagon's, inside missile defense, an exclusive biweekly
`report on U.S. missile defense programs, procurement and
`policymaking", Missile Technology (Aug. 13, 1997) 3(16): 5.
`.. Le mechanisme de la vis.ion humane daJJs le silicum". Electronique
`le Mensuel des Tngenieurs de Conception (1997) 68: 11 57-1 151.
`"Objectif securite des reseaux". Es Profcssionnels de Linformatique
`en Enterprise Magazine (Jan. 1997).
`.. Realiser tm decodeur pom TV numberi que". Electronique, Le
`Mensuel des I ngenieurs de Conception ( 1997) 66.
`"Techniques de lingenieur", Revue Trimestrielle Des (Mar. 1997)
`5(40F). lSSN 0994-0758.
`Al Adsani, "For immediate release lhe generic visual perception
`processor", (Oct. 10, 1997). (I page).
`
`SAMSUNG EXHIBIT 1001
`Page 2 of 30
`
`

`
`US 8,989,445 B2
`Page3
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`
`Daugman, "Complete discrete 2-D Gabor transforms by neural net(cid:173)
`works for image analysis and compression", IEEE Transaction on
`Acoustics, Speech and Signal Processing (1988) 36(7): 1 169-14 179.
`Groupe Revenu Franca is, Ai r & Co, "Un calculal'eur de perceoption
`visuelle'', Hebdomada.ire. (Dec. 6, 1996) Annee No. 1590: 22F.
`Grove et al., "Colour based object tracking", lEEE (Aug. 1998). (4
`pages).
`Gru Svelle, .. Premier ... oeil", Electronicque TnternaJional Hebdo
`(Dec. 1996): 245.
`lndiveri et al .. ''System implementation of analog VLSI velocity
`sensor", IEEE Proceed.ings of MicroNemo ( 1996): 15-22.
`.Johnson, "Vision chip's ci rcuitry has its eye out for you", Retrieved
`from http:l/ l 92.215.107.74/wifdnews/1997/09/09013vision.honl (3
`pages), 1997.
`
`Mallat, "A theo1y for mu ltiresolution signal decomposition: The
`wavelet representation", TEEE Transactions on Patt em Analys is and
`Machine Intelligence (1989) 11(7): 674-693.
`Pa.rlelU", "Un processor de perception visuelle", Des Solutions
`Electroniques Pour Tous ( 1997) 25F: 1856.
`Revue Trimesu-ielle, "lnstantanes Technique". Techniques de
`lngenieur (1997). ISSN: 0994-0758.
`Ruedi, ''Motion detection silicon retina based on even! correlations",
`IEEE Proceedings of MicroNeuro (I 996): 23-29.
`Swain et a.I., "Indexing via color histograms", IEEE (1990): 390-393.
`Tomita, Jr. el al., "Hand shape extraction from a sequence of digitized
`gray-scale images". IECON 20th International Conference on Indus(cid:173)
`trial Electronics, Control and Instrumentation (1994) 3: 1925-1930.
`Yamada el a.I., "Image understanding based on edge hologram
`method
`for
`rear-end collision avoidance syslem", Vehicle
`Navigation & Information Systems Conference Proceedings (1994):
`445-450 .
`
`"'cited by examiner
`
`SAMSUNG EXHIBIT 1001
`Page 3 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 1of13
`
`US 8,989,445 B2
`
`- - - - -+ 000 - - - - - · - - - -
`
`a1.2 au ST
`\I I
`.......... ~ .....
`+TR'2
`
`S(PI)
`
`12
`
`ZH ( V.DI)
`
`,(cid:173)
`'t-----~.r•
`I
`~~~
`I
`/
`
`' I
`I \...
`
`SR
`
`10a
`
`13
`
`11
`
`14
`
`10
`
`13a
`
`FIG. 1
`
`SAMSUNG EXHIBIT 1001
`Page 4 of 30
`
`

`
`U.S. Patent
`
`Mar. 24,2015
`
`Sheet 2of 13
`
`US 8,989,445 B2
`
`!HP BL
`
`19
`
`SL
`SC
`HP
`
`17
`
`I
`:
`3.
`3
`3
`1
`co 1
`v
`VI DI
`• SR
`F
`1
`2'.. ~· -------------------------------------------------------- ------- ------ -------- ---.L...-2'..
`
`I
`
`FIG. 2
`
`13
`
`8
`
`16
`
`I Pl-LI I =AB
`
`15a
`
`15b
`
`;-------------------------------------------------------·:
`! S(PI)
`~
`.
`·
`·
`v1 s
`~
`20-- L_J
`-:
`15e
`:
`~-·······:
`:
`SE
`.
`'.
`'.
`: ............ :
`! ..... ...... . ,
`:
`;
`:
`N
`15f_.-............. LI !
`15
`:
`3 !
`......._ ....... Cl 1
`15
`.
`3
`co
`LO
`
`AB 8
`SE ~_....,,~---=-=--....,.---,
`AB> SE+ DP = 1
`8
`AB ~ SE-+ DP = 0
`,,__1 _______ D_P_
`.----D_P--'--------.
`DP = 1-+ CO = Cl - U
`.~~ .. '.: .. ~.~ .. ~.~ .. ~ ... ~! ... ~ ... ~.
`0 ~CO~ N
`co
`3
`co 1 - - - - - - - - . - - - . - --
`
`15C
`
`LO = LI + Pl - LI
`co
`'--~-----~ LO
`. ---·--·--··-····--·--·-·---·-···-···--·------------------
`FIG. 3
`
`15d
`
`18
`
`SAMSUNG EXHIBIT 1001
`Page 5 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 3of13
`
`US 8,989,445 B2
`
`18
`HPBL
`
`SL
`
`,........__r....._
`_............
`1
`'
`
`\
`r2
`
`lDP.CO
`
`YO
`1--1-----il--------+--+-----I ( 117)
`Y1
`_..,__--+-+--+--+---+---+--ol----1 ( 116)
`
`; 211
`~
`~
`TR1
`
`M3
`
`Pa.a
`
`d 15.1
`
`19
`
`r16
`\
`
`FIG.4
`
`A
`/f;~:
`
`t /
`
`~ TR1
`• : ;lxyt1 (Pl ijt1)
`TM
`~ 7 TR2
`;;;zPlxyt2 (Pl ijt2)
`~ TR,
`P1xyt3 (Pl ijt3)
`
`4
`
`2
`
`6
`
`0
`
`FIG. 5
`
`FIG. 6
`
`SAMSUNG EXHIBIT 1001
`Page 6 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 4of13
`
`US 8,989,445 B2
`
`0
`+ 1
`
`+ 1
`
`0
`
`M3
`
`0
`
`- 1
`
`M9
`
`0
`
`0
`
`- 1
`
`FIG. 7
`
`Ya
`
`Xa
`
`FIG. 8
`
`SAMSUNG EXHIBIT 1001
`Page 7 of 30
`
`

`
`U.S. Patent
`
`Mar. 24,2015
`
`Sheet 5 of 13
`
`US 8,989,445 B2
`
`FIG. 9
`
`FIG. 9a
`
`-- - -- - -- -- - ---- - --- ~ i-- ------ ----L__ -I
`
`z1
`:
`
`22a 22
`
`11
`
`1--
`
`j
`S(PI) 1
`~
`
`SR
`V
`
`j ZH
`'
`
`j
`
`~~
`.
`:
`. . z
`L ........................................................................................................ j ............................................................................ .J
`
`FIG. 10
`
`SAMSUNG EXHIBIT 1001
`Page 8 of 30
`
`

`
`U.S. Patent
`
`Mar. 24,2015
`
`Sheet 6of 13
`
`US 8,989,445 B2
`
`F
`
`z
`
`------------ -------------------- ----------
`
`SR
`
`v
`
`VL
`
`DI
`
`co
`
`--------- --------------------- ------ 1
`
`z
`
`24
`
`V1
`
`HISTOGRAM
`FORMATION
`AND
`PROCESSING
`
`31
`
`sv
`
`36
`
`xy(m)
`COMPOSITE
`SIGNAL
`
`23
`
`34
`
`LINEAR
`COMBINATION VS
`
`28
`
`HP
`
`32
`
`33
`
`sco
`
`ZH
`
`35
`
`SDI
`
`V6
`
`29
`
`x(m)0
`
`y(m)0
`
`FIG. 11
`
`SAMSUNG EXHIBIT 1001
`Page 9 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 7of13
`
`US 8,989,445 B2
`
`lb
`
`la
`xM
`FIG. 12
`
`110
`
`VALIDATION V2
`
`I:
`+1/+0 ---~
`
`INIT
`
`102 DATA
`
`25a 0
`HISTOGRAM
`FORMATION
`
`DATA(V)
`COUNTER
`
`INIT
`
`104
`
`out DATA
`IN
`
`OUTi----
`
`MEMORY
`100
`
`ADDRESS
`
`.............. ~~~__..__. } ~~~SSIFIER
`
`112
`
`MIN
`MAX
`
`RMAX
`POSRMAX
`NbPTS
`
`INIT
`DATA(V) 106
`
`OUT
`
`31
`
`OUT
`
`23
`
`FIG. 13
`
`SAMSUNG EXHIBIT 1001
`Page 10 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 8of13
`
`US 8,989,445 B2
`
`SCREEN
`
`',
`'
`ANALYSIS
`' .. ,,
`........ ,,AXIS
`... ,
`' ' '
`
`POSRMAX
`
`FIG. 14
`
`POINTS
`CONCERNED
`BY ANALYSIS
`
`R _ NBPTS
`1- R MAX
`
`1~R<STOP
`
`y
`
`FIG. 14a
`
`SAMSUNG EXHIBIT 1001
`Page 11 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 9of13
`
`US 8,989,445 B2
`
`v
`
`13
`
`s
`
`11
`
`42
`
`ZH
`
`43
`
`v
`
`10b
`
`FIG. 15
`
`FIG. 16
`
`SAMSUNG EXHIBIT 1001
`Page 12 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 10of13
`
`US 8,989,445 B2
`
`Xd
`
`127d
`
`..-----~--_,____-----!-----------
`,,-
`
`--------- ...
`
`-.........
`
`I
`I
`I
`'', ...... , __________________ ,
`I
`
`127b
`
`125b
`
`I l v
`
`I
`I
`r
`
`I
`I
`
`I
`I
`I
`I
`\
`\
`\
`'
`
`124y
`
`y
`
`0
`
`Xd
`
`Ya
`
`124x
`
`FIG. 17
`
`Xe
`FIG. 18
`
`SAMSUNG EXHIBIT 1001
`Page 13 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 11 of 13
`
`US 8,989,445 B2
`
`200
`
`202
`
`204
`
`206
`
`Image
`Processing
`System
`
`Controller
`
`Servomotor 14--4~-------------'
`
`208
`
`Monitor
`
`212
`
`210
`
`FIG. 19
`
`216
`
`220
`
`216
`
`FIG. 20
`
`SAMSUNG EXHIBIT 1001
`Page 14 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 12 of 13
`
`US 8,989,445 B2
`
`r
`
`212
`\
`
`FIG. 21
`
`224
`\
`
`lt::::::::::::::: ::: :::: ::~~~~~::~~:
`l
`. . .
`
`YA-nK
`
`YMIN
`
`Xs+nK
`
`. . .
`x
`:
`/222
`MIN t\ r!XMAX
`
`FIG. 22
`
`SAMSUNG EXHIBIT 1001
`Page 15 of 30
`
`

`
`U.S. Patent
`
`Mar.24,2015
`
`Sheet 13 of 13
`
`US 8,989,445 B2
`
`212
`\
`
`Inf---------------- --~~_::!'_!_{ _____ y MAX
`~-----------------~----------- y
`
`YA K
`-n
`
`MIN
`
`~
`
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`
`FIG. 23
`
`13A
`/
`
`~
`
`,..
`
`7 5 -6
`--
`- 4
`,...
`
`3
`
`2
`
`1
`
`FIG. 24
`
`SAMSUNG EXHIBIT 1001
`Page 16 of 30
`
`

`
`US 8,989,445 B2
`
`1
`IMAGE PROCESSCNG APPARATUS AND
`METHOD
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`2
`and to is determined. The displacemenl 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
`5 object. There is also a delay in obtaining tbe spe€-xl and dis(cid:173)
`placement direction information corresponding to t I +R,
`where R is the time necessary for the calculations for the
`period tO-tl system. These two disadvantages limit applica-
`tions of this type of system.
`Another type of prior image processing system is sbowu in
`French Patent No. 2,61 I ,063, of which the inventor hereof is
`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 perfonn data compress ion. A
`15 histogram of signal levels from the camera is .fonned 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(cid:173)
`els o f the nex1 sequence are compared with the signal levels
`20 for the first sequence using a fixed time constant ideutical for
`each pixel. A binary classification signal is generated that
`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 posilion of a
`25 mnge 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
`repealed for subsequent sequences of the sequenced signal.
`111is prior process enables data compression, keeping only
`30 interesting parameters in the processed flow of sequenced
`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. lt is thus
`possible to classify, for example, brightness and/or chromi-
`35 nance levels of the signal and to characterize and localize an
`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 lime detection, location and determinalion oft he
`40 speed and direction of movement of all area of relative move(cid:173)
`ment in a scene. It includes a time processing unit ofa 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-
`45 ment by separately determining horizontal and vertical
`changes of the observed area. Difference signals are used to
`detect movements from righl 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-
`50 rying out an EXCLUSIVE OR function on horizontal/vertical
`difference signals and on frame difference signals, and by
`using a ratio of1hc smus of the horiz.ontal/vertical siguals and
`the stuns of frame difference sif,111als with respect to a Kx3
`window. Calculated values of the image along orthogonal
`55 horizontal and vertical directions are used with an identical
`repetitive difference K in the orthogonal directions, this dif(cid:173)
`ference K being defi ned as a :function of the displacement
`spe€-xls
`that are to be determined. The device detennines the
`direction of movement along each of the two orthogonal
`60 directions by applying a set of calculation operations to the
`di:ITerence 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 aniplitude of the speed,
`65 and calculation of the arctan function to obtain the oriented
`direction), starting from projections on lbe horizontal and
`vertical axes. This device also does not smooth the pixel
`
`The present application is a continuation of U.S. applica(cid:173)
`tion Ser. No. 14/215,358, filed on Mar. 17, 2014.
`U.S. application Ser. No. 14/215,358 was a continuation of
`U.S. application Ser. No . .12/620,092, filed on Nov . .17, 2009. 10
`U.S. application Ser. No. 12/620,092 was a continual ion of
`U.S. application Ser. No. 11/ 676,926, filed Feb. 20, 2007.
`U.S. application Ser. No. 11/ 676,926 is now U.S. Pat. No.
`7,650,015, issued Jan. 19, 2010.
`U.S. application Ser. No. 11 /676,926 was a divisional of
`priority to U.S. application Ser. No. 091792,294. filed Feb. 23,
`2001 .
`U.S. application Ser. No. 09/792,294 is now U.S. Pat. No.
`7, 181 ,047, issued Feb. 20, 2007.
`U.S. application Ser. No. 091792,294 is a continuarion-in(cid:173)
`part ofU.S. patent application Ser. No. 09/230,502, filed Sep.
`13, 1999.
`U.S. patent application Ser. No. 09/ 230,502 is now U.S.
`Pat. No. 6,486,909.
`U.S. paten I application Ser. No. 09/230,502 was a National
`Stage Entry ofapplicationNo. PCT/FR97/01354. filed on Jul.
`22, 1997.
`U.S. patent application Ser. No. 09/230,502 was also a
`conlinuation-iu-part of application No. PCT/EP98/05383,
`filed on Aug. 25, I 998.
`U.S. patent application Ser. No. 09/230,502 also claims
`foreign priority to French Patent Application 96 09420. filed
`Jul. 26, 1996.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`111e presenl inventiou relates generally to all 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
`·n1e human or animal eye is the best known system for
`identifying and localizing an object inrelativemovement. and
`for determining its speed and direction of movement. Various
`efforts have been made to mimic the fimction of the eye. One
`type of device for this purpose is refen-ed lo as an artificial
`retina, which is shown, for example, in Giocomo Indiveri et.
`al, Proceedings ofMicroNeuro. 1996. pp. 15-22 (analog arti(cid:173)
`ficial retina), and Pierre-Francois Ruedii, Proceedings of
`MicroNcuro, 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 on.ly limited information is obtained about the
`moving areas or objects observed Other examples of artificial
`retinas and similar devices are shown in U.S. Pat. Nos. 5,694,
`495 and 5,7 12,729.
`Another proposed method for detecting objects in au 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 representalive 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 ru1d tO the distanced by which the object, as
`represented by its pixels, has moved in the scene between t,
`
`SAMSUNG EXHIBIT 1001
`Page 17 of 30
`
`

`
`US 8,989,445 B2
`
`3
`values using a time constant, especially a time cons taut 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 lmages," lnstitute of Electrical and Electronics
`Engineers, Vol. 3, 1994, pp. 1925-1930, detects movement by
`subtracting between successive images, and forming histo(cid:173)
`grams based upon the shape of a human hand in order to
`extract the shape of a human band in a digitized scene. The
`histogram ai1alysis is based upon a gray scale inherent to the
`human hand. It does not include any means of forming his(cid:173)
`tograms in the plane coordinates. The sole purpose of the
`method is to detect the displacement of a human hand, for
`example, in order lo replace the uonnal computer mouse by a 15
`hru1d, the movements of which arc identified lo control a
`computer.
`It would be desirable to have an image processing system
`which has a relatively simple strncture and requires a rela(cid:173)
`tively small memory capacity, and by which infomiation on 20
`the movement of objects within an image can be obtained in
`real-time. It would also be desirable to have a method and
`apparatus for detecting movements that are not limited to the
`hai1d, but to any object (in the widest sense of the term) in a
`scene, aud which does nor use histograms based on the gray 25
`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 requiriug the detection of moving
`and non-moving objects.
`
`SUMMARY OF THE INVENTION
`
`·me 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 smoo1hed 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.
`TI1e time constant is preferably in the fom1 2P, 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)
`ticular pixel; and a 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)
`mi ned whetl1er the particular pixel ru1d the pixels along an
`oriented direction relative lo the particular pixel have binary
`values ofa particular value representing sit,rnificant variation,
`and, for such pixels, it is determined in the second matrix
`whether the anlplitude of the pixels along the oriented direc(cid:173)
`tion relative to the particular pixel va.ries iu a known mam1er
`indicating movement in the oriented direction of the particu(cid:173)
`lar pixel and the pixels along the oriented direction relative to
`the particular pixel. Tue amplitude of the variation of the
`pixels along the oriented direction determines the velocity of
`movemeut of tl1e particular pixel and the pixels along the
`oriented direction relative to the particular pixel.
`
`4
`ln 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
`5 domain. Histograms of the area of significant variation along
`coordinate axes are then fom1t-'CI. From these histograms, it is
`determined whether there is an area iu movement for the
`particular domain. The domains are preferably selected from
`the group consisting of i) luminance, ii) speed (V), iii) ori-
`10 ented direction (DJ), iv) time constant (CO), v) hue, vi)
`saturation, aud vii) first axis (x(m)), a.nd viii) second axis
`(y(m)).
`Jn one embodiLuenl, lhe first and second matrices are
`square matrices, with the same odd number of rows and
`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, aud the step of
`determining in the second matrix whether the amplitude sig-
`nal varies in a predetermined criteria along an oriented direc(cid:173)
`tion relative to the particular pixel, comprise applying nested
`nxn matrices, where n is odd, centered on the particular pixel
`lo the pixels within each ofthe first ru1d 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.
`ln an alternative embodiment, the first aud second matrices
`30 are hexagonal matrices center€.'CI on the particular pixel. In this
`embodiment, the steps of determining iu the first matrix
`whether the particular pixel and the pixels along an oriented
`direction relative to the particular pixel have binary values of
`35 a particular value representing significant variation. and the
`step of determining in the second matrix whetl1er the ampli(cid:173)
`tude signal varies in a predetermiued criteria along an ori(cid:173)
`ented direction relative to the particular pixel, comprise
`applying nested hexagonal matrices of varying size centered
`40 on the particular pixel to the pixels within each of the first and
`second matrices. The process then further includes determin(cid:173)
`ing the smallest nested matrix in which the amplitude signal
`varies along an oriented direction around the particular pixel.
`Jn a still further embodiment of the invention, the first and
`45 second matrices are inverted L-shaped matrices with a single
`row and a single column. In this embodiment, the steps of
`determining in the first matrix whether the particular pixel
`and the pixels along an oriented direction relative lo the
`particular pixel have binary values of a particular value rep-
`50 resenting significant variation. and the step of determining in
`the second matrix whether the amplitude signal varies in a
`predetennined 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
`55 determine the smallest matrix in which the amplitude varies
`on a line with the steepest slope and constant quantificat ion.
`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
`60 displacement, speed and orientation indications compatible
`with t11e value of p, is selected.
`In a process of smoothing au 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
`65 (LO), ii) it is determined whether there exists a significant
`variation between such pixel aud the same pixel in a previous
`frame, and iii) the time constant (CO) for such pixel lo be used
`
`SAMSUNG EXHIBIT 1001
`Page 18 of 30
`
`

`
`US 8,989,445 B2
`
`5
`in smoothing the pixel in subsequeut frames of lhe iupur
`signal is modified based upon the existence or non-existence
`of a significant variation.
`Tue step of determining the existence of a significant varia(cid:173)
`tion for a given pixel preferably comprises detenuining
`whether the absolute valueofthedifTereuce (AB) between the
`given pixel value (Pl) 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:
`
`P/-U
`LO=ll+CO
`
`Time constant (CO) is preferably in the fom1 2P. and p is 20
`incremented in the event that AB<SE and decremented in the
`event AB>=SE.
`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 25
`value of the rime 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 au area iu 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 magnin1de of each pixel between a
`current frame and a prior frame;
`generating a second array indicative of the magnitude of
`significant variation of each pixel between the current fr