111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US008805001B2
`
`c12) United States Patent
`Pi rim
`
`(10) 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 of this
`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. 09/792,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
`
`1111988 Sadjadi
`4/1991 Ando
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`
`2/1982
`0046110 A1
`0 380 659 A1
`8/1990
`(Continued)
`
`OTHER PUBLICATIONS
`
`Swain et a!., 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
`(D1), time constant (CO), first axis (x(m)), and second axis
`(y(m)).
`
`13 Claims, 13 Drawing Sheets
`
`1 2.24
`a __ ------y,--J-
`Yw.xj
`------ -ylftii~,-
`I
`
`:
`
`:
`
`A-nti: Yt-trK
`
`I
`I
`I
`:
`XA-n.KI
`' Xs+nK
`I
`I
`I
`I
`I
`I
`XH~MAX
`
`2.22
`
`. . /
`
`Exhibit 2003
`IPR2017-01218
`Petitioner- Samsung Electronics Co., Ltd., et al.
`Patent Owner- Image Processing Technologies LLC
`1
`
`

`

`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
`1111992 Kosaka
`5,163,095 A
`5,263,098 A * 1111993 Horikami .
`5,278,921 A *
`111994 Nakamura et a!.
`5,359,533 A
`10/1994 Ricka eta!.
`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 a!.
`5,546,475 A *
`8/1996 Bolle eta!.
`5,565,920 A
`10/1996 Lee et al.
`111997 Lee et al.
`5,592,226 A
`111997 Greenway et a!.
`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.
`12/1997 Hara eta!.
`5,694,495 A
`5,712,729 A
`111998 Hashimoto
`6/1998 Fassnacht eta!.
`5,774,581 A
`5,793,888 A
`8/1998 Delanoy
`5,912,980 A *
`6/1999 Hunke
`5,982,944 A * 1111999 Vaidyanathan et a!.
`6,226,388 B1 *
`5/2001 Qian eta!.
`6,256,608 B1
`7/2001 Malvar
`6,304,187 B1
`10/2001 Pirim
`6,486,909 B1
`1112002 Pirim
`6,597,738 B1
`7/2003 Park eta!.
`6,717,518 B1
`4/2004 Pirim
`7,181,047 B2
`2/2007 Pirim
`7,650,015 B2 *
`112010 Pirim
`2002/0101432 A1
`8/2002 Ohara eta!.
`2002/0120594 A1
`8/2002 Pirim
`2002/01567 53 A1
`10/2002 Pirim
`2002/0169732 A1
`1112002 Pirim
`2003/0067978 A1
`4/2003 Pirim
`2003/0152267 A1
`8/2003 Pirim
`2007/0140526 A1
`6/2007 Pirim
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`FR
`FR
`JP
`wo
`wo
`wo
`wo
`wo
`wo
`
`10/1990
`0 394 959 A2
`574831 A1 * 12/1993
`2611063 A1
`8/1988
`2751772 A1
`111998
`06-205780 A
`7/1994
`wo 98/05002
`2/1998
`wo 99/36893
`7/1999
`wo 99/36894
`7/1999
`WO 00/11609 A1
`3/2000
`WO 00/11610 A1
`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
`
`G01N 21188
`
`Stephane C. Mallat, "A Theory for Multiresolution Signal Decom(cid:173)
`position: The Wavelet Representation", IEEE Transactions on Pat(cid:173)
`ternAnalysis 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., eta!., "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 a!., "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 o5
`(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 AI 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 Ia 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-1134.
`"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 a!; "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 a!., IEEE Publication, Aug. 1998, "Colour Based Object
`Tracking" (pp. 4).*
`
`* cited by examiner
`
`2
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 1 of 13
`
`US 8,805,001 B2
`
`TRz
`
`\_ l3a
`
`11.2
`11.17-
`- - - - -QO ¢ _ _ _ _ _
`
`ZH ( V.Dl l
`
`(
`I
`{
`I
`\
`
`SR
`
`S(PI)
`
`12
`
`n
`
`11
`
`FIG. I
`
`3
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 2 of 13
`
`US 8,805,001 B2
`
`··············· .... !. ?. .. -~ ..................................................................... - ......... :
`i
`\
`LI
`sfPn
`s:
`flS
`:' .. ·-·-:
`. -1
`.
`:
`/_
`.
`.
`J
`f15
`.
`:¥ ........... :
`!'-
`HPl BL 1
`
`,.. 16
`
`r
`
`17
`
`tlla
`
`LO
`
`I
`Cl
`/3
`co /3
`
`I
`
`I
`
`l&
`4
`
`, .. _
`.·
`"
`
`4
`
`/
`
`20
`
`HP
`
`DP co
`11
`
`fJ
`
`SfPD
`
`!
`
`.
`.
`19 -V
`.
`
`SL
`sc
`HP
`
`F
`z - ~ .. 0 " • • •o " " '"'" oo • • • ... -~' ro • • " • • • • - • • oo oo ~ ..... '" o 0 . • • • •
`
`.... ~:
`.... L..--3
`.... 1---3
`,...i---1
`3
`co
`vr
`v
`DI
`..... "'"'" • • • ........................ ...
`
`' " ' I • • • • -~-· • • • 0 . . . . . "" 0 0 ' " " " . . . . . . . " ' " I . . . o o 001 "'o . . . " ~ o
`
`lSR
`
`FrG. 2
`
`FIG.3
`~---------------------------------------------
`
`I Pl-U l-AB ~ !Sa r 15
`-
`
`!
`:
`:
`:
`~
`' :DP
`
`r- 15b
`
`20 d-i S~:~
`J~· .
`
`13
`
`15e \ - .... ,
`
`SE -·..........
`!" ........ :
`
`N
`
`15f J .......... · Lrl l
`15 1
`' I
`3 I :
`o....r~-' cf :
`t-...f--'--+-+--i--lot
`'
`3 .. ~---.... ~ 15
`:
`CO
`LO
`
`•
`
`:
`
`I
`
`6 -
`
`I
`I
`
`:
`
`4
`
`N
`
`i
`
`:
`,
`:
`
`SE
`AB }s
`-,·
`18 AB>SE 4 DP ... !
`AB :SSE-+ DP=O
`
`~1
`
`DP
`
`DP =I -+
`DP = 0 ....
`
`co,.cr- u
`CO = CI + U - 1Sc
`
`: .
`• I • I •
`Os CO~N
`• I
`:co
`......... 3
`co r------------r----~
`I • • I
`
`...!:!_
`
`t
`
`: S(Pt)
`
`LO = LI + PI - LI
`co
`' ' '
`~----·------------~LO
`
`I
`
`I
`I
`
`' . I • • •
`
`\_ 15d
`
`' •
`' J
`
`I
`I
`
`~~-~-----~----------~--•••----w-~~------------•
`
`18 J
`
`4
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 3 of 13
`
`US 8,805,001 B2
`
`18
`
`HP BL
`
`co
`l
`
`SL
`
`sc
`
`\_ 19
`
`rl6 ::\
`
`~a JL c~ M3
`lrd ~ ~~
`g :n
`
`1
`~-y--
`
`PB.BJ
`
`TR. 1
`
`FIG. 4
`
`FIG.S
`
`FIG. 6
`
`5
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 4 of 13
`
`US 8,805,001 B2
`
`FlG. 7
`
`+ l
`
`0
`
`0
`
`+ 1
`
`o
`
`~.-MJ
`
`M9
`
`- 1
`
`0
`
`0
`
`FIG. a
`
`6
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 5 of 13
`
`US 8,805,001 B2
`
`' /
`
`FIG. 9
`
`FIG. 9Cl..
`
`·····················~-~ .. --=\···-· ·---········ .................. _ ......... .! .. -... -... ~~-~--·~ ....... ........ L. .. ~.~---
`
`1
`I
`
`I z1
`
`~
`'
`SR I
`' •
`v
`• I
`VL:
`'
`DL ' I
`I co:
`
`S(PI)
`
`F
`
`I
`
`I
`I
`
`I
`
`I'
`....
`
`)
`
`v
`
`--. -· ·- ......... -·-~ ............. ·- .............. - ..... ·--~ ........................ ······: •••••• ·-·- ..... - •••• ·••t• ...................................... '
`
`' . I
`1 z
`
`I
`
`F1G. 10
`
`7
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 6 of 13
`
`US 8,805,001 B2
`
`F
`
`co
`v
`VL
`SR
`--~---------· ·------·---------·-··- --------·-- ---------- ·--------------------- ---~
`
`Dl
`
`24 -..., ~i5T06AAM
`IDRH~no~
`Ml'D
`VI ~"'"""' PRCCfS>i».J
`
`25 .......
`
`V2
`
`26-.....
`
`2 7 \
`
`VJ
`
`V4
`
`.
`xy(m)
`36 ~ CDHPD~Tff t)!GNH
`,...:....__;_.......:;...,
`~HnViN~ kf.tA '£LO{)(
`l.___.......-~l
`
`ZH
`
`35
`
`~L-x~(m)z
`
`y(m)z
`
`V6
`
`28 _/
`
`"- 29
`
`37
`
`HP
`
`SL
`sc
`
`"DATA UJJE
`
`Cfll\N&£ BLoc.K
`
`1 x(m)o
`
`FTG. 11
`
`'7
`
`8
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 7 of 13
`
`US 8,805,001 B2
`
`•.• ~41
`
`": ' " ~:
`
`40
`
`Ia
`
`FIG. 12
`
`lb
`
`X
`
`'POINTS
`CONCfltNE'D
`BY ANf'tLY5I'<;
`
`1)= kBPT5
`R. Hf1X
`1~R<sroP
`
`' "\
`' ...
`' ..
`
`' ' ' '
`
`'
`•
`' ' ...
`'
`
`y
`
`yM
`
`y
`
`FIG. 14a.,
`
`X
`
`FIG.14
`
`9
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 8 of 13
`
`US 8,805,001 B2
`
`110
`
`/
`2:
`+1/+0
`
`VALIDATION V2
`
`H ISTOGRAM
`FO RMATION %--
`25a
`
`DATA(V) ---i-t
`COUNTER -l~
`
`DATA
`
`MUX oul
`102
`I
`[NIT
`
`r----
`
`f- r--
`
`MUX
`104
`t
`IN IT
`
`INIT
`DATA
`
`CLOCK
`VAlJDATrDN
`
`112'\
`
`MIN
`MAX
`RMAX
`POSRMAX
`NbPTS
`
`DATA
`lN
`
`OUT
`
`MEMORY
`100
`
`ADDRESS
`
`I I ~I I I CLASSIFIER 25b
`
`DATA(V)
`
`(
`
`10
`
`OUT
`
`108~1
`
`p
`
`I
`
`I
`inp
`
`31
`our• ('
`2 1 0
`I
`I
`
`I
`
`I
`
`23
`
`FKG.l3
`
`10
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 9 of 13
`
`US 8,805,001 B2
`
`rv
`G
`p\
`
`I
`
`43
`
`11
`
`42
`
`s
`
`ZH
`
`lOb
`
`\3
`
`FiG.15
`
`I 13A
`
`[t 3
`
`4
`
`__.
`
`l
`
`2
`
`ffG·24
`
`11
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 10 of 13
`
`US 8,805,001 B2
`
`. . I
`
`I
`_j--T
`I
`
`f
`I
`
`I
`I
`~
`
`y
`
`126d /-
`
`124y
`
`I
`I
`
`127a
`
`Ya
`
`Xd
`
`27d
`
`v/ I
`
`I
`1
`I
`I
`/ .
`....
`
`,..._ ___
`
`Fig.
`
`'G
`
`-------
`z
`
`7b
`
`Ffg. 17
`
`X
`
`12
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 12, 2014
`Aug.12, 2014
`
`US 8,805,001 B2
`
`Sheet 11 of 13
`Sheet 11 of 13
`
`US 8,805,001 B2
`
`Ya
`
`Yb
`
`Fig. 18
`Fig. 18
`
`13
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 12 of 13
`
`US 8,805,001 B2
`
`Cf\1'\i.lA
`
`~o"l-
`
`~ ~oces.S.tl G-
`)ysrGr'\
`
`5fi'll 0 M'OIOR F--+-------------'
`
`-
`?-ll
`
`?.lo
`
`~16
`
`14
`
`

`

`U.S. Patent
`
`Aug. 12, 2014
`
`Sheet 13 of 13
`
`US 8,805,001 B2
`
`212
`~
`
`!] ____ --------- YB
`(__Gff:.. -----= =-= = =---=- -yA-- 1c
`
`\I
`
`lt1
`Ill
`La t
`11:
`
`1 2.24
`YMNJ.
`[fl------- r-- -y6tnR1-
`.... - - -- X -- J_
`~·- - - -
`I
`I : :
`
`~:[G. 2Z
`
`:
`
`I
`I
`XA .. ttKX
`1 B+nK
`:
`:
`_./2.22
`XHIN h CXMAX
`
`I
`I
`
`I
`
`A-ht\ YHIH
`
`15
`
`

`

`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. 09/792,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. 09/792,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.
`a!, Proceedings ofMicroNeuro, 1996, pp. 15-22 (analog arti(cid:173)
`ficial retina), and Pierre-Francais 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
`
`16
`
`

`

`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)
`abies 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 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)
`ticularpixel; 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)
`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 of a 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 colunm. 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 colunm 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
`
`17
`
`

`

`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 + -----cD
`
`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, I6, Ic, 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 time constant for the pixel to be
`used in smoothing subsequent frames of the input signal;
`means for forming a first matrix comprising the binary
`60 values of a subset of the pixels of the frame spatially related to
`each particular pixel, and f