I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US008983134B2
`
`c12) United States Patent
`Pi rim
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 8,983,134 B2
`*Mar. 17, 2015
`
`(54)
`
`IMAGE PROCESSING METHOD
`
`(56)
`
`References Cited
`
`(71) Applicant: Image Processing Technologies LLC,
`Suffern, NY (US)
`
`(72)
`
`Inventor: Patrick Pirim, Paris (FR)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`EP
`EP
`
`(21) Appl. No.: 14/215,358
`
`(22)
`
`Filed:
`
`Mar. 17, 2014
`
`(65)
`
`Prior Publication Data
`
`US 2014/0198952Al
`
`Jul. 17, 2014
`
`Related U.S. Application Data
`
`(60) Continuation of application No. 12/620,092, filed on
`Nov. 17, 2009, now Pat. No. 8,805,001, which is a
`
`(Continued)
`
`(30)
`
`Foreign Application Priority Data
`
`Jul. 26, 1996
`
`(FR) ...................................... 96 09420
`
`(51)
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`Int. Cl.
`G06K9/00
`G06T 7120
`G06K9/62
`(52) U.S. Cl.
`CPC ............ G06T 712033 (2013.01); G06K 916212
`(2013.01)
`USPC ............................ 382/103; 382/128; 382/168
`( 58) Field of Classification Search
`CPC ........... G06T 2207/30221; G06T 2207/30236;
`G06T7/0083; G06T7/208; G06T 11/001;
`G06T 2207/20144; G06T 7/20; G06T 7/2093;
`G06T 2207/30232; G06K 2209/23; G06K
`916202; G06K 9/00771; G06K 2209/09;
`G06K 9/00201; G06K 2009/3291; G06K
`9/00342; G06K 9/00362; G06K 9/00664;
`G06K 9/00791; H04N 7/368; B60R 2300/802;
`B60R 2300/804; B60R 2300/806
`See application file for complete search history.
`
`U.S. PATENT DOCUMENTS
`
`4,706,120 A
`4,719,584 A *
`
`1111987 Slaughter et al.
`1/1988 Rue et al. ...................... 348/171
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`2/1982
`0046110 Al
`2611063 Al
`8/1988
`(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 Connolly
`Bove+ Quigg
`ABSTRACT
`(57)
`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)).
`
`6 Claims, 13 Drawing Sheets
`
`II
`
`42
`
`ZH
`
`Page 1 of 29
`
`SAMSUNG EXHIBIT 1001
`Samsung v. Image Processing Techs.
`
`

`

`US 8,983,134 B2
`Page 2
`
`Related U.S. Application Data
`
`FOREIGN PATENT DOCUMENTS
`
`continuation of application No. 11/676,926, filed on
`Feb. 20, 2007, now Pat. No. 7,650,015, which is a
`division of application No. 091792,294, filed on Feb.
`23, 2001, now Pat. No. 7,181,047, which is a continu(cid:173)
`ation-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 on Aug. 25,
`1998.
`
`EP
`EP
`EP
`EP
`JP
`WO
`WO
`WO
`WO
`WO
`WO
`
`0380659 A
`0394959 A2
`0574831
`2751772 Al
`06-205780
`98/05002
`99/36694
`99/36893
`00/11639 Al
`01111610 Al
`01163557 A2
`
`8/1990
`10/1990
`12/1993
`111998
`7 /1994
`2/1998
`7 /1999
`7 /1999
`3/2000
`3/2000
`8/2001
`
`OTHER PUBLICATIONS
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1111988 Sadjadi
`4,783,828 A
`5,008,946 A
`4/1991 Ando
`2/1992 Markowitz et al.
`5,088,488 A
`4/1992 Lawton
`5,109,425 A
`6/1992 Kasdan
`5,123,055 A
`1111992 Kosaka
`5,163,095 A
`5,263,098 A
`1111993 Horikami
`111994 Nakamura et al.
`5,278,921 A
`10/1994 Ricka et al.
`5,359,533 A
`5,360,968 A * 1111994 Scott .
`5,384,865 A
`111995 Loveridge
`5,430,809 A
`7/1995 Tomitaka
`5,473,369 A
`12/1995 Abe
`111996 Hong
`5,488,430 A
`5,521,843 A
`5/1996 Hashima et al.
`5,546,475 A
`8/1996 Bolle et al.
`5,565,920 A
`10/1996 Lee et al.
`111997 Lee et al.
`5,592,226 A
`111997 Greenway et al.
`5,592,237 A
`5,608,820 A
`3/1997 Vaidyanathan
`5,610,653 A
`3/1997 Abecassis
`5,625,717 A
`4/1997 Hashimoto et al.
`5,630,037 A
`5/1997 Schindler
`5,694,495 A
`12/1997 Hara et al.
`111998 Hashimoto
`5,712,729 A
`5,774,581 A
`6/1998 Fassnacht et al.
`5,793,888 A
`8/1998 Delanoy
`5,912,980 A
`6/1999 Hunke
`1111999 Vaidyanathan et al.
`5,982,944 A
`6,226,388 Bl
`5/2001 Qian et al.
`6,256,608 Bl
`7/2001 Mal var
`6,263,089 Bl * 7/2001 Otsuka et al.
`10/2001 Pirim
`6,304,187 Bl
`6,312,385 Bl
`1112001 Mo et al.
`6,486,909 Bl
`1112002 Pirim
`6,597,738 Bl
`7/2003 Park et al.
`6,717,518 Bl
`412004 Pirim et al.
`212007 Pirim
`7,181,047 B2
`7,650,015 B2
`112010 Pirim
`8,116,527 B2
`212012 Sabol et al.
`8,805,001 B2
`8/2014 Pirim
`2002/0101432 Al
`8/2002 Ohara et al.
`2002/0120594 Al
`8/2002 Pirim
`2002101567 53 Al
`10/2002 Pirim
`200210169732 Al
`1112002 Pirim
`2003/0067978 Al
`4/2003 Pirim
`2003/0152267 Al
`8/2003 Pirim
`2007/0140526 Al
`6/2007 Pirim
`
`235/454
`
`382/107
`
`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-14179.
`Alberto Tomita, Jr. et al., "Hand Shape Extraction from a Sequence of
`Digitized Gray-Scale Images", IECON '94, 20th International Con(cid:173)
`ference on Industrial Electronics, Control and Instrumentation, vol. 3
`of 3, Special Sessions, Signal Processing and Control, pp. 1925-
`1930.
`Giacomo Indiveri et al, "System Implementations of Analog VLSI
`Velocity Sensor", 1996 IEEE Proceedings of MicroNeuro '96, pp.
`15-22.
`VePierre-Francois Riiedi, "Motion Detection Silicon Retina Based
`on Event Correlations", 1996 IEEE Proceedings ofMicroNeuro '96,
`pp. 23-29.
`Revue Trimestrielle <<Techniques de Lingenieur>>, "Instantanes
`Technique" Techniques De ingenieur, Mar. 1997-N o. 5 ( 40F), ISSN
`0994-0758.
`Es Professionnels de Linformatique En Enterprise Magazine,
`"ObjectifSecurite Des Reseaux", No. 24, Jan. 1997.
`Electroncique International Hebdo, Dec. 5, 1996-No. 245, "Pre(cid:173)
`mier ... oeil", Francoise Gru svelte (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 .741 wire/news/1997/09/09013vision.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 lngenieurs De Conception,
`No. 68, Mar. 1997, ISSN 1157-1151 (with translation).
`"Un Processor de Perception Visuelle", Lehaut Parleur, 25F Des
`solutions electroniques pour tous, No. 1856, Jan. 15, 1997.
`"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
`Halogram Method for Rear-End Collision Avoidance System",
`Vehicle Navigation & Information Systems Conference Proceedings;
`(1994), pp. 445-450 published Aug. 31, 1994; XP 000641348.
`* cited by examiner
`
`SAMSUNG EXHIBIT 1001
`Page 2 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 1of13
`
`US 8,983,134 B2
`
`TR 1
`
`11.2
`_ _ _ _ _ ooo _ _ _ _ --.
`
`S(PI)
`
`12
`
`ZH < V.DI)
`
`(
`I
`~
`I
`~
`
`lOa _ /
`
`SR
`
`13
`
`11
`
`14
`
`10
`
`\_ lJa
`
`FIG. 1
`
`SAMSUNG EXHIBIT 1001
`Page 3 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 2of13
`
`US 8,983,134 B2
`
`:·:J:.l3A S~~ . ·····:-·~······ . . ........... ···~·· . ·:~·················· ··-··· ···1
`S<Pn
`: :
`J·.
`
`12
`
`~ '·······
`
`LO
`
`15
`
`20
`
`~HP BL
`
`DP CO
`
`CI
`co
`
`3
`
`3
`
`18
`4
`
`HP
`
`S<Pn
`
`SL
`
`SC
`
`:
`:
`
`16
`
`17
`
`t Jla
`
`19
`
`z
`
`HP
`
`4
`
`FlG. 2
`
`I
`
`J
`
`3
`
`3:
`
`13
`
`8
`
`I
`I
`I
`
`I
`
`1L...
`_..V-8
`
`FIG. 3
`.---------------------------------------------
`y-
`, I
`I .
`I
`HP
`20 -0--l
`-· ...........
`
`I PI - LI l=AB
`
`I
`
`15
`
`~
`
`15a
`
`'- 15b
`
`I
`I
`
`I
`
`: DP
`
`l
`j
`~
`1 ................................. ~ ....................... ~.~-···············~···· .... ~ ....... ~~-- ....... ~~- ... i Z 1
`S{Pl) I
`
`I
`I
`
`~E
`I 8
`
`AB
`
`}s
`AB> SE-+ DP=I
`AB :SSE-+ DP=O
`
`i,J
`
`lSe ~ ...... ,
`s
`E
`N
`f
`15
`
`:·········!
`_/ .......... :
`
`16 -
`
`LI_,
`157
`3 I
`I
`CI
`
`L..-
`
`3 .. ~ ....
`co
`
`15
`LO
`
`DP
`DP= l .... CO= CI-U
`DP=O ... CO= CI+U - J Sc
`
`·············································-··
`Os CO$N
`co ... L---3
`
`'--+
`
`N
`
`I
`I
`I
`I
`
`I •
`
`co
`
`~
`
`S(PI)
`
`I
`I
`I
`I
`I
`
`.
`
`I
`
`LO =LI + PI - LI
`co
`.
`. .
`ILO ~ •
`.
`
`15d
`
`I
`
`~---------------------------------------------·
`
`18 J
`
`SAMSUNG EXHIBIT 1001
`Page 4 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 3of13
`
`US 8,983,134 B2
`
`co
`l
`
`18
`
`DP
`
`HP BL
`
`r1 \
`
`I rzJ
`
`SL
`
`SC
`
`HP
`
`\_ 19
`
`rl6 ~
`
`f1.1
`
`:21
`
`!a
`...!?... c~ M3
`'.d ~r·I
`--,-,
`lg /h
`i
`
`?8.8...:
`
`0
`YI5
`1 -+ - - t - - - - - - - 4 - -+ - - I (12)
`D 0
`Yl6
`
`F ~I il SR j L.~16.~ ........... :.l.~J~r.kd
`
`.
`
`l ~
`
`~
`
`\ (11)
`:~~:~~J
`
`Z ------- ----------------------------------------------------------------------~Z1
`
`FIG.4
`
`2
`
`3~]
`4• //I"(. 0
`
`5
`
`6
`
`7
`
`FIG. 5
`
`FIG.6
`
`SAMSUNG EXHIBIT 1001
`Page 5 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 4of13
`
`US 8,983,134 B2
`
`FJG. 7
`
`+ I
`
`0
`
`0
`
`+ l
`
`O
`
`- M3
`
`M9
`
`- 1
`
`0
`
`0
`
`- 1
`
`FIG.8
`
`SAMSUNG EXHIBIT 1001
`Page 6 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 5of13
`
`US 8,983,134 B2
`
`DPll .... ~I/// ;/, / 7.
`
`I
`
`3
`
`:
`/ 2
`
`1
`
`0
`
`2
`
`/
`
`1
`
`0
`
`I
`
`L.u.
`
`\l
`COU.. ......... 3
`
`Ex
`
`~ /
`
`3
`
`/
`
`FIG. 9
`
`FIG. 9~
`
`I z1
`······················-~-~---·=\······ .......................................... .l. ........... ~~~---=\······ ........ L .. ~~---
`I . v
`"
`I . .
`
`•
`I
`
`I
`I
`I
`
`F
`
`SR
`
`=
`:
`
`i
`
`S(PI) ~
`
`v
`VL
`
`DL
`co
`
`MC3
`
`ZH
`
`· ....................................................................................................................... ·······-·············· ..
`
`' . I .
`lz
`
`F1G. 10
`
`SAMSUNG EXHIBIT 1001
`Page 7 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 6of13
`
`US 8,983,134 B2
`
`F
`
`v
`co
`SR
`--~---------- ---------------------- ----------- ---------- ---------------------- ---~
`
`VL
`
`DI
`
`__ l
`
`,..._l_
`
`24 --.... l-HSTDb.k.f\M
`lbRHATIO»
`AN!>
`P~oct5S1W
`
`vi -
`
`25 -,.
`
`V2
`
`27 ~
`
`VJ
`
`V4
`
`, __ _.Y ~ s: .._,_..,..-.""'l JI Ly
`
`.....,_
`
`I 32 LOI
`
`33 J sco
`
`l
`
`/l....__'--'-~-'-----'--'--'-~--'~~.._.__._~~~~L.....!..-1-~__:___J
`
`~r-~~-r--r-.,--.,.~~~~-r~~~~-.--.--.-~~~~
`ZH
`
`xy(m)
`36 ~ COMPD~T5 l)Jf7/'1Ftl
`
`I MnVitJL1 mA P:LOO<.
`
`•
`
`~_;._~
`
`l.___-"""l
`
`35
`
`23 j
`34 5
`
`I .
`
`Li NEAR.
`COHBi N f\TiON
`
`l
`
`V5
`
`y(mlz
`
`V6
`
`[\_ 29
`
`y(m)i v-37
`
`x(m)z
`r------.
`
`28 _ /
`
`HP
`
`SL
`
`"DATA UJJE
`
`1 x(m)o
`
`FIG. 11
`
`SAMSUNG EXHIBIT 1001
`Page 8 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 7of13
`
`US 8,983,134 B2
`
`y
`
`Ld \
`
`.;-.c;·S·:1<}~ 41
`
`ld--E~~--'-~~+
`
`~~~+---
`
`yM
`
`40
`
`xM
`
`lb
`
`x
`
`la
`
`FIG. 12
`
`?DINTS
`CONQ;RNfD
`P>Y ANftLY51S
`
`~- f'iBPT5
`-
`R. Hf'iX
`1{J<<sror
`
`..... ,
`'
`' ' ...
`
`'
`
`'
`'
`
`' ' ... ...
`
`' ...
`
`y
`
`.··
`
`FIG. 14
`
`38
`·.
`·· ...
`·· ... ..
`
`FIG. 14 a,
`
`x
`
`SAMSUNG EXHIBIT 1001
`Page 9 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 8of13
`
`US 8,983,134 B2
`
`110
`
`/
`2::
`+1/+0
`
`VALIDATION V2
`
`DATA
`
`112'\
`
`HISTOGRAM
`FORMATION %-
`25a
`
`DATA(V)-(cid:173)
`COUNTER ----
`
`'
`MUX
`102
`I
`INIT
`
`MUX
`JM
`t
`INIT
`
`oul DATA
`IN
`
`OUT
`
`INl_T
`DATA
`
`MEMORY
`100
`
`CLOCK
`VALIDATION
`
`MIN
`MAX
`RMAX
`POSRMAX
`NbPTS
`
`- ~~l__._l__._l _._IJ_.__I -'---'--II l CLASSIFIER 25b
`OUT 11
`
`~ ADDRESS
`
`I
`106
`
`OUT
`
`DATA(V)
`
`p
`
`2 1 0
`I
`I
`
`I
`
`I
`
`I
`
`108 .... --
`
`23
`
`FilG.13
`
`SAMSUNG EXHIBIT 1001
`Page 10 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 9of13
`
`US 8,983,134 B2
`
`rv
`13 B
`~ \ I 43
`
`11
`
`42
`
`s
`
`ZH
`
`I Ob
`
`\3
`
`FIG.15
`
`I 13A
`
`~ 3
`
`A
`
`___.
`
`1
`
`2
`
`flG·24
`
`SAMSUNG EXHIBIT 1001
`Page 11 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 10 of 13
`
`US 8,983,134 B2
`
`~\3
`-~
`.,,,.. .,,,,. "'I
`..,,,,,,,,. ,.
`"'I
`,...,....... ~/I
`,-
`I
`
`-
`
`123a )_.-..-
`....
`
`------
`
`2a' /
`
`/
`
`/
`
`/
`
`/
`
`I
`
`I
`
`I
`I
`/-l23b
`
`I
`
`I
`•'
`I
`I
`_J--T
`I
`
`f
`
`I
`
`I
`
`/
`JI--
`
`Fig.
`
`'G
`
`1--~~~~~~-;-~~---.-------
`
`124y
`
`/
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`\
`\
`
`1.27a
`
`Ya
`
`5c
`
`I
`I
`I
`J
`
`...... ____ _ ----
`
`Xd
`
`-----
`
`f127d
`
`I
`------ '\
`v/ I
`/ -·
`
`z
`
`7b
`
`Yb
`
`Fig. ,7
`
`x
`
`SAMSUNG EXHIBIT 1001
`Page 12 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 11 of 13
`
`US 8,983,134 B2
`
`XMIN
`
`XMAX
`
`~-f G-- 23
`
`Ya
`
`Yb
`
`Fig. 18
`
`SAMSUNG EXHIBIT 1001
`Page 13 of 29
`
`

`

`U.S. Patent
`
`Mar. 17,2015
`
`Sheet 12 of 13
`
`US 8,983,134 B2
`
`r:rG-. '~
`
`~p..G-E:
`~ e-oc.e>>N G-
`~'/ SrG r'\
`
`?-lo
`
`?.\G
`
`?-\~
`
`SAMSUNG EXHIBIT 1001
`Page 14 of 29
`
`

`

`U.S. Patent
`
`Mar.17,2015
`
`Sheet 13 of 13
`
`US 8,983,134 B2
`
`212
`
`-----------
`---------
`-----------
`
`•••
`
`1 11
`•11
`II•
`
`~:rG. 21
`
`/
`
`iZ24
`IfT- - - ... - - """ -yB+tiK 1 -j
`YMAX I
`~--- - -----~--]-
`:
`:
`A-ti K YMut
`I
`I
`I
`I
`I
`XA-nKx
`I
`B+nK
`:
`:
`../222
`XHIN {l CXMAx
`
`I
`
`SAMSUNG EXHIBIT 1001
`Page 15 of 29
`
`

`

`US 8,983,134 B2
`
`1
`IMAGE PROCESSING METHOD
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`The present application is a continuation of U.S. applica(cid:173)
`tion Ser. No. 12/620,092, filed on Nov. 17, 2009.
`U.S. application Ser. No. 12/620,092 was a continuation 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. 091792,294 is now U.S. Pat. No.
`7,181,047, issued Feb. 20, 2007.
`U.S. application Ser. No. 091792,294 is a continuation-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. patent application Ser. No. 09/230,502 was a National
`Stage Entry of application No. PCT/FR97 /01354, filed on Jul.
`22, 1997.
`U.S. patent application Ser. No. 09/230,502 was also a
`continuation-in-part of application No. PCT/EP98/05383,
`filed on Aug. 25, 1998.
`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
`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
`1dent1fies 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
`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
`represented by its pixels, has moved in the scene between t,
`and to is determined. The displacement speed is then equal to 65
`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
`
`2
`oriented direction. Information for the movement of the
`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 hereof is
`also an inventor. This patent relates to a method and apparatus
`10 for real time processing of a sequenced data flow from the
`output of a camera in order to perform data compression. A
`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
`15 maximum and minimum levels are extracted. The signal lev(cid:173)
`els of the next sequence are compared with the signal levels
`for the first sequence using a fixed time constant identical for
`each pixel. A binary classification signal is generated that
`characterizes the next sequence with reference to the classi-
`20 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
`25 repeated for subsequent sequences of the sequenced signal.
`This prior process enables data compression, keeping only
`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
`30 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
`object in the image.
`Another system is also known from WO 98/05002, of
`35 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(cid:173)
`ment in a scene. It includes a time processing unit of a spatial
`processing unit in order to determine said speed and direction
`40 of movement.
`U.S. Pat. No. 5,488,430 detects and estimates a displace(cid:173)
`ment by separately determining horizontal and vertical
`changes of the observed area. Difference signals are used to
`detect movements from right to left or from left to right, or
`45 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
`difference signals and on frame difference signals, and by
`using a ratio of the sums of the horizontal/vertical signals and
`50 the sums of frame d1flerence 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
`55 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
`difference signals, which requires very complex computa(cid:173)
`tions. Additional complex computations are also necessary to
`60 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.
`
`SAMSUNG EXHIBIT 1001
`Page 16 of 29
`
`

`

`US 8,983,134 B2
`
`3
`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(cid:173)
`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(cid:173)
`tograms in the plane coordinates. The sole purpose of the 10
`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
`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 25
`many types of applications requiring the detection of moving
`and non-moving objects.
`
`SUMMARY OF THE INVENTION
`
`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-
`t1cularp1xel; anda secondmatnx compnsmg 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
`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 kuown manner
`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. 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
`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-
`
`4
`cant variation is determined from the histogram for that
`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(cid:173)
`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
`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
`15 relative to the particular pixel have binary values ofa particu(cid:173)
`lar value representing significant variation, and the step of
`determining in the second matrix whether the amplitude sig(cid:173)
`nal varies in a predetermined criteria along an oriented direc(cid:173)
`tion relative to the particular pixel, comprise applying nested
`20 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
`30 a particular value representing significant variation, and the
`step of determining in the second matrix whether the ampli(cid:173)
`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
`35 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.
`In a still further embodiment of the invention, the first and
`40 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 to the
`particular pixel have binary values of a particular value rep-
`45 resenting significant variation, and the step of determining in
`the second matrix whether the amplitude signal varies in a
`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
`50 determme the smallest matnx m 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
`55 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
`60 (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
`65 of a significant variation.
`The step of determining the existence of a significant varia(cid:173)
`tion for a given pixel preferably comprises determining
`
`SAMSUNG EXHIBIT 1001
`Page 17 of 29
`
`

`

`US 8,983,134 B2
`
`5
`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:
`
`PI-LI
`LO = LI + ----CO
`
`25
`
`6
`for each pixel of the input signal, analyzing the pixel and
`providing an output signal for each domain containing infor(cid:173)
`mation to identify each domain in which the pixel is classi(cid:173)
`fied;
`providing a classifier for each domain, the classifier
`enabling classification of pixels within each domain to
`selected classes within the domain;
`providing a validation signal for the domains, the valida(cid:173)
`tion signal selecting one or more of the plurality of domains
`10 for processing; and
`forming a histogram for pixels of the output signal within
`the classes selected by the classifier within each domain
`selected by the validation signal.
`The process further includes the steps of forming histo-
`grams along coordinate axes for the pixels within the classes
`selected by the classifier within each domain selected by the
`validation signal, and forming a composite signal corre(cid:173)
`sponding to the spatial position of such pixels within the
`20 frame. Pixels falling within limits la, 16, le, Id in the histograms
`along the coordinate axes are then identified, and a composite
`signal from the pixels falling within these limits is formed.
`A process for identifying the velocity of movement of an
`area of an input signal comprises:
`for each particular pixel of the input signal, forming a first
`matrix comprising binary values indicating the existence or
`non-existence of a significant variation in the amplitude of the
`pixel signal between the current frame and a prior frame for a
`subset of the pixels of the frame spatially related to such
`30 particular pixel, and a second matrix comprising the ampli(cid:173)
`tude of such variation;
`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-
`35 resenting significant variation, and, for such pixels, determin(cid:173)
`ing in the second matrix whether the amplitudes of the pixels
`along an oriented direction relative to the particular pixel vary
`in a known manner indicating movem