`US008805001B2
`
`c12) United States Patent
`Pi rim
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 8,805,001 B2
`*Aug. 12, 2014
`
`IMAGE PROCESSING METHOD
`(54)
`Inventor: Patrick Pirim, Paris (FR)
`(75)
`(73) Assignee: Image Processing Technologies LLC,
`Suffern, NY (US)
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 528 days.
`
`( *) Notice:
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`(21) Appl. No.: 12/620,092
`Nov. 17, 2009
`(22) Filed:
`Prior Publication Data
`(65)
`
`Aug. 26, 2010
`US 2010/0215214Al
`Related U.S. Application Data
`
`(60) 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
`continuation-in-part of application No. 09/230,502,
`filed on Sep. 13, 1999, now Pat. No. 6,486,909, which
`is
`a
`continuation-in-part of application No.
`PCT/EP98/05383, filed on Aug. 25, 1998, and a
`continuation-in-part
`of
`application
`No.
`PCT/FR97/01354, filed on Jul. 22, 1997.
`Foreign Application Priority Data
`
`(30)
`
`(FR) ...................................... 96 09420
`
`(2006.01)
`
`Jul. 22, 1996
`Int. Cl.
`(51)
`G06K 9100
`(52) U.S. Cl.
`USPC ............................ 382/103; 382/128; 382/168
`( 58) Field of Classification Search
`USPC ......... 382/100, 103, 107, 128-132, 168-180,
`382/199-206,224,291
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`4,783,828 A
`5,008,946 A
`
`11/ 1988 Sadjadi
`4/1991 Ando
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`
`2/1982
`0046110 Al
`8/1990
`0 380 659 Al
`(Continued)
`
`OTHER PUBLICATIONS
`
`Swain et al., IEEE Publication, 1990, "Indexing via color histo(cid:173)
`grams" (pp. 390-393). *
`
`(Continued)
`
`Primary Examiner - Manav Seth
`(74) Attorney, Agent, or Firm -Novak Druce Connolly
`Bove + Quigg LLP
`
`(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)).
`
`13 Claims, 13 Drawing Sheets
`
`-- - - - -
`
`A-ntt Yt-trK
`
`1 Z.24
`a __ ------y,--J-
`Yw.xj
`-Ya+ii~,-
`I
`
`:
`
`:
`
`I
`I
`I
`:
`XA-n.K'
`' Xs+nK
`I
`I
`2.22
`I
`I
`I ~
`I
`XH~MAX
`
`Page 1 of 29
`
`SAMSUNG EXHIBIT 1001
`Samsung v. Image Processing Techs.
`
`
`
`US 8,805,001 B2
`Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`2/1992 Markowitz et al.
`5,088,488 A
`4/1992 Lawton
`5,109,425 A
`5,123,055 A *
`6/1992 Kasdan
`5,163,095 A
`1111992 Kosaka
`5,263,098 A * 1111993 Horikami .
`5,278,921 A *
`111994 Nakamura et al.
`5,359,533 A
`10/1994 Ricka et al.
`5,384,865 A
`111995 Loveridge
`5,430,809 A *
`7/1995 Tomitaka
`5,473,369 A * 12/1995 Abe
`5,488,430 A
`111996 Hong
`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.
`5,592,226 A
`111997 Lee et al.
`5,592,237 A
`111997 Greenway et al.
`5,608,820 A *
`3/1997 Vaidyanathan
`5,610,653 A *
`3/1997 Abecassis
`5,625,717 A
`4/1997 Hashimoto et al.
`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
`5,982,944 A * 1111999 Vaidyanathan et al.
`6,226,388 Bl *
`5/2001 Qian et al.
`6,256,608 Bl
`7/2001 Mal var
`6,304,187 Bl
`10/2001 Pirim
`6,486,909 Bl
`1112002 Pirim
`6,597,738 Bl
`7/2003 Park et al.
`6,717,518 Bl
`412004 Pirim
`7,181,047 B2
`212007 Pirim
`7,650,015 B2 *
`112010 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
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`FR
`FR
`JP
`WO
`WO
`WO
`WO
`WO
`WO
`
`10/1990
`0 394 959 A2
`574831 Al * 12/1993
`2611063 Al
`8/1988
`2751772 Al
`111998
`06-205780 A
`7 /1994
`WO 98/05002
`2/1998
`WO 99/36893
`7 /1999
`WO 99/36894
`7 /1999
`WO 00/11609 Al
`3/2000
`WO 00/11610 Al
`3/2000
`WO 01163557 A2
`8/2001
`OTHER PUBLICATIONS
`
`382/134
`
`382/128
`382/167
`
`382/173
`348/169
`
`700/253
`382/190
`
`382/169
`348/170
`
`382/103
`382/271
`382/103
`
`382/103
`
`GOlN 21188
`
`Stephane C. 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.
`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 Indiveri 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,
`"ObjectifSecurite Des Reseaux", No. 24, Janvier, 1997.
`Electroncique International Hebdo, Dec. 5, 1996-No. 245, "Pre(cid:173)
`mier ... 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, No. 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
`Histagram Method for Rear-End Collision Avoidance System",
`Vehicle Navigation & Information Systems Conference Proceedings;
`(1994), pp. 445 450 Published Aug. 31, 1994; XP 000841348.
`
`Grove et al., IEEE Publication, Aug. 1998, "Colour Based Object
`Tracking" (pp. 4).*
`
`* cited by examiner
`
`SAMSUNG EXHIBIT 1001
`Page 2 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 1of13
`
`US 8,805,001 B2
`
`TR.2
`
`\_ l3a
`
`11.2
`- - - - -Q0¢ ____ _
`
`ZH < V.Dl l
`
`(
`I
`{
`I
`\
`
`SR
`
`lOa
`
`10
`
`S(PI)
`
`12
`
`n
`
`ll
`
`FIG. I
`
`SAMSUNG EXHIBIT 1001
`Page 3 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 2of13
`
`US 8,805,001 B2
`
`:····r· l::IA
`................... !.?. ... ~ ..................................................................... -......... ;
`i
`~ ·· .... , SfPn
`; :
`:
`;
`SCP!)
`·
`J·.
`:
`~ L .... 1
`.
`
`;
`
`12
`
`\
`
`S:
`
`HP
`
`15
`
`15
`
`3
`
`i
`
`16
`
`3
`
`t Ila
`
`17
`
`LI
`LO
`
`Cl
`co
`
`l&
`4
`
`4
`
`DP CO
`
`20
`
`19
`
`BL
`
`Sf PD
`
`SL
`SC
`
`HP
`
`~
`~
`
`:
`
`1
`
`l
`3
`l
`~
`CO
`DI
`VI
`V
`SR
`F
`z -· .......................................................................................................................... _· z
`FCG. 2
`
`:
`'
`3
`
`3
`
`1
`
`13
`
`20 d-i s~;[
`
`FIG.3
`~---------------------------------------------
`
`JPI-LI 1-~ ~ 15a r IS
`
`15e \-·····
`SE -...........
`!' ........ :
`.
`
`N
`
`i SE
`
`/ 8
`
`:
`:
`•
`
`l 5f _.) .......... : LI I l
`._l_;f:__._: I--<-- DP = I -+ co ,,,. er -u
`
`6 -
`
`1st '
`
`I
`
`I
`........ _,... .... Cl
`
`co
`
`LO
`
`-+
`N
`
`LI
`..._
`
`S(Pt)
`
`'
`l
`l
`I
`:
`'
`:
`:
`I •
`' ' I
`LO = LI + PI - LI
`' t
`co
`' •
`' '
`'
`---~~·~~~~~~~~LO
`
`AB }s
`AB>SE 4 DP ... !
`AB :SSE-+ DP=O
`
`"1
`
`DP
`
`~
`!
`~
`'
`l DP
`:
`I •
`:
`DP = 0 .... CO = CI+ U ,... 1 Sc
`:
`................................................
`;
`.
`Os CO~N
`:
`~~3
`~co
`co 1--~~~~~~.....-~~--
`
`- 15b
`
`I
`I
`
`18 J
`
`\_ 15d
`
`~~-~-----~----------~--•••----w-~~------------•
`
`SAMSUNG EXHIBIT 1001
`Page 4 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 3of13
`
`US 8,805,001 B2
`
`18
`
`HP BL
`
`DP co
`l
`
`I r1 ~
`
`I rzJ
`
`SL
`
`SC
`
`\_ 19
`
`~a JL c~ M3
`I'd~~,
`g :n
`PB.B J
`
`I
`~-y--
`
`TR_ 1
`
`FIG. 4
`
`2
`
`3~1
`4'/K'"
`
`5
`
`6
`
`7
`
`FIG.S
`
`FIG. 6
`
`SAMSUNG EXHIBIT 1001
`Page 5 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 4of13
`
`US 8,805,001 B2
`
`FJG. 7
`
`+ l
`
`0
`
`0
`
`+ l
`
`o
`
`..- MJ
`
`M9
`
`- 1
`
`0
`
`0
`
`FIG.a
`
`SAMSUNG EXHIBIT 1001
`Page 6 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 5of13
`
`US 8,805,001 B2
`
`3
`
`Pp
`
`.:
`: Ex
`.l
`
`.. /
`
`FIG. 9
`
`FIG. 9ci..
`
`I z1
`
`
`..................... ~.'. .... =\···-· ·-············ ................ _ ......... .l.·-···----~~.~---·=\·· .. ·· ........ L .. ~.~---
`
`• I
`;
`'
`SR I
`' I
`' •
`v
`•
`'
`'
`VL •
`'
`'
`DL ' I
`co I
`
`F
`
`S(PI)
`
`"
`....
`
`ZH
`
`I
`
`I
`
`I
`
`I
`
`• • • •• •• •• .,. '•• •••• •• •• •' • •••• • ••' • • ••• •• • • • • •• • •• •--~ ••' • •••'""•""•••• • ••' • ••••••: •••••• •-•• ,.,.. ••••••••tr••• r• •••• •• •• •• •••• ••• •••• •• '"' •,
`
`' . I
`' 1 z
`
`F1G. 10
`
`SAMSUNG EXHIBIT 1001
`Page 7 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 6of13
`
`US 8,805,001 B2
`
`F
`
`co
`v
`VL
`DI
`SR
`__ f: __________ -------·--------··---- ----------- ---------- ---------------------- ---71
`
`24 ,
`
`~i5T06AAM
`IDRH~no~
`Ml'D
`VI ,........ PRCCfS>i».'..1
`
`25 .......
`
`V2
`
`26-......
`
`VJ
`
`27 \
`
`V4
`
`xy(m)
`
`.
`
`36 ~ CDHPD~Tff ')!GNH ,....__._.........,
`IHnViN~ A'f.tA !Loa<.
`l.___ __ ~l
`
`ZH
`
`35
`
`x(m)z
`
`~._.,
`
`y(m)z
`
`J ,
`
`'
`
`I
`
`3~N~5
`
`CDHBi NATiON
`
`vs
`
`28 _/
`
`HP
`
`SL
`SC
`t----~--~~--=-~
`
`V6
`
`f\_ 29
`
`y(m).f v-37
`
`"DATA U>JE
`
`Cfll\N&E BLDlK
`
`1 x(m)o
`
`FTG. 11
`
`SAMSUNG EXHIBIT 1001
`Page 8 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 7of13
`
`US 8,805,001 B2
`
`40
`
`la
`
`FIG. 12
`
`lb
`
`x
`
`'POINTS
`CONCfltNE'D
`BY ANf'tLY5I'<;
`
`I)= kBPT5
`R. Hf1X
`1~R<sroP
`
`' "\
`'
`...
`' ..
`
`' ' ' '
`
`'
`•
`' ' ...
`'
`
`FIG.14
`
`y
`
`.··
`
`•··
`
`38
`
`FIG. 14a.,
`
`x
`
`SAMSUNG EXHIBIT 1001
`Page 9 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 8of13
`
`US 8,805,001 B2
`
`110
`
`/
`2:
`+1/+0
`
`VALIDATION V2
`
`H ISTOGRAM
`FO RMATION
`25a
`
`ff--
`
`DATA
`
`-
`
`MUX oul
`102
`I
`[NIT
`
`DATA
`lN
`
`OUT
`
`MEMORY
`100
`
`-
`
`ADDRESS
`
`INIT
`DATA
`
`CLOCK
`VAlJDATrDN
`
`112~
`
`MIN
`MAX
`RMAX
`POSRMAX
`NbPTS
`
`DATA(V) - - i - i
`COUNTER ~--
`
`MUX
`1114
`t
`INIT
`
`--- ,...._ ........... l__,___._I __._l/...._I _._..__.I ) CIJ.SSIFIER 25b
`
`J
`106
`
`OUT
`
`DATA(V)
`
`31
`
`OUT
`(
`2 1 0
`I
`I :
`
`I
`
`l
`
`p
`
`I
`
`23
`
`FKG.13
`
`SAMSUNG EXHIBIT 1001
`Page 10 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 9of13
`
`US 8,805,001 B2
`
`rv
`13 G
`p\
`
`I
`
`43
`
`11
`
`42
`
`s
`
`ZH
`
`lOb
`
`\3
`
`FiG.15
`
`13A
`
`3
`
`2
`
`fi"G ·24
`
`SAMSUNG EXHIBIT 1001
`Page 11 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 10 of 13
`
`US 8,805,001 B2
`
`. ' I
`
`I
`_j--T
`I
`
`f
`I
`
`I
`I
`t'-
`
`Fig.
`
`'G
`
`126d /-
`
`124y
`
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`\
`\
`
`127a
`
`Ya
`
`5c
`
`Xd
`
`27d
`
`/
`v
`,..._ ___ ------
`
`I
`I
`l
`I
`I
`/ .
`....
`
`Xe
`
`7c
`
`-------
`z
`
`7b
`
`Yb
`
`-------
`
`~26a
`
`i26b /
`
`Ffg. 17
`
`x
`
`SAMSUNG EXHIBIT 1001
`Page 12 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 11 of 13
`
`US 8,805,001 B2
`
`In\ ___ -- --
`l_Ul ______ _
`
`l
`
`l
`t
`I
`
`Ya
`
`Yb
`
`Fig. 18
`
`SAMSUNG EXHIBIT 1001
`Page 13 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 12 of 13
`
`US 8,805,001 B2
`
`Cf\l'\i.JA
`
`".)o"l-
`
`~ ~oces.S.tl G-
`)ysrG r'\
`
`5fi'll O M'OIOR fot--+-------------J
`
`-
`?-ll
`
`?.lo
`
`~16
`
`SAMSUNG EXHIBIT 1001
`Page 14 of 29
`
`
`
`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 13 of 13
`
`US 8,805,001 B2
`
`212
`
`-----------
`--- - -- ---
`-----------
`
`' ll 1
`Ii I
`l1 t
`11 1
`
`SAMSUNG EXHIBIT 1001
`Page 15 of 29
`
`
`
`US 8,805,001 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. 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
`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
`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 50
`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 60
`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 65
`object. There is also a delay in obtaining the speed and dis(cid:173)
`placement direction information corresponding to tl+R,
`
`2
`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
`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
`10 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 of the next sequence are compared with the signal levels
`for the first sequence using a fixed time constant identical for
`15 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 position of a
`range of significant values. Finally, the auxiliary signal is
`20 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
`25 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
`30 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-
`35 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
`40 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
`45 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
`55 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
`
`SAMSUNG EXHIBIT 1001
`Page 16 of 29
`
`
`
`US 8,805,001 B2
`
`3
`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
`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 10
`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
`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(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
`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
`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(cid:173)
`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
`
`4
`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
`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-
`15 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
`to the pixels within each of the first and second matrices. The
`process then includes the further step of determining the
`20 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
`25 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(cid:173)
`tude signal varies in a predetermined criteria along an ori-
`30 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(cid:173)
`ing the smallest nested matrix in which the amplitude signal
`35 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
`determining in the first matrix whether the particular pixel
`40 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
`predetermined criteria along an oriented direction relative to
`45 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
`50 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
`55 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
`60 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(cid:173)
`tion for a given pixel preferably comprises determining
`65 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
`
`SAMSUNG EXHIBIT 1001
`Page 17 of 29
`
`
`
`US 8,805,001 B2
`
`5
`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
`
`10
`
`6
`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
`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
`15 frame. Pixels falling within limits Ia, 16, le, Id in the histo(cid:173)
`grams 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
`20 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
`25 subset of the pixels of the frame spatially related to such
`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(cid:173)
`resenting significant variation, and, for such pixels, determin-
`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 movement of the pixel and the
`pixels along an oriented direction relative to the particular
`pixel, the amplitude of the variation along the oriented direc-
`tion determining the velocity of movement of the particular
`pixel.
`A process for identifying a non-moving area in an input
`signal comprises:
`forming histograms along coordinate axes for pixels of the
`input signal without significant variation between the current
`frame and a prior frame; and
`forming a composite signal corresponding to the spatial
`position of such pixels within the frame.
`An apparatus for identifying relative movement in an input
`signal comprises:
`means for smoothing the input signal using a time constant
`for each pixel, thereby generating a smoothed input signal;
`means for determining 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 signal
`between the current frame and the immediately previous
`smoothed input frame, and for determining the amplitude of
`55 the variation;
`means for using the existence of a significant variation for
`a given pixel to modify the