( 12) United States Patent
`Pirim
`
`(54) METHOD AND DEVICE FOR AUTOMATIC
`VISUAL PERCEPI'ION
`
`(75)
`
`Inventor: Patrick Pirim, Paris (FR)
`
`(73) Assignee: Holding B.E.V.SA., Luxembourg (LU)
`
`( • ) Notice:
`
`Subject to any disclaimer, the term of this
`patent i5 extended or adjusted under 35
`U.S.C. 154(b) by 397 days.
`
`(21) Appl. No.: 09/792,436
`
`(22) Filed:
`
`Feb. 23, 2001
`
`(65)
`
`Prior Publication Data
`US 2002/0169732 Al Nov. 14, 2002
`(51) Int. Cl.7
`
`. •. .. •••. •. .. •••... .••••. G06F 15/18; G0lR 23/10;
`G06K 9/00
`(52) U.S. Cl . ............................ 706/20; 702/78; 382/133
`(58) Field of Search .. ........................... 706/20; 702/78;
`382/133
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,783,828 A
`5,008,946 A
`5,088,488 A *
`5,109,425 A
`5,163,095 A
`5,278,921 A
`5,359,533 A
`5,384,865 A
`5,488,430 A
`5,592,237 A
`5,625,717 A
`5,694,495 A
`5,712,729 A
`5,774,581 A
`5,793,888 A
`6,304,187 Bl
`6,4S6,909 Bl
`6,597,738 Bl
`2002/0101432 Al •
`
`11/1988
`4/1991
`2/1992
`4/1992
`* 11/1992
`1/1994
`* 10/1994
`1/1995
`1/1996
`* 1/1997
`4/1997
`12/1997
`1/1998
`6/ 1998
`8/1998
`10/2001
`11/2002
`7/2003
`8/2002
`
`Sad_jadi ....................... 382/170
`Ando ......................... 382/ 104
`Markowitz et al. ........... 607/ 27
`Lawton
`...................... 382/ 107
`Kosaka ....................... 382/ 133
`Naka0111ra el al.
`... 382/ 167
`Ricka el al. ....... ........... 702/ 78
`Loveridge ................... 382/262
`Hong ......................... 348/ 699
`Greenway et al. .......... 348nl6
`Hashimoto et al. .. ... .. .. 382/ 260
`Hara et al. .. .. .. . .. .. ... .. .. 382/324
`Hashimoto .................. 359/ 562
`Fassnacht et al.
`.. ........ 382/180
`Delanoy ..................... 382/219
`Pirim ......................... 340/576
`Pirim ......................... 348/143
`Park et al. ......... .... 375/240.16
`Ohara et al. ................ 345/589
`
`I 1111111111111111 11111 lllll lllll lllll lllll lllll lllll lllll 111111111111111111
`
`US006959293B2
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,959,293 B2
`Oct. 25, 2005
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`FR
`FR
`JP
`WO
`WO
`WO
`WO
`
`0 046 110
`0 380 659 Al
`0 394 959 A2
`2 611 063 Al
`2 751 772
`06-205780 A
`WO 98/05002
`WO 99/36893
`WO 99/36894
`WO 00/11610
`
`2/1982
`8/1990
`10/1990
`8/1988
`1/1998
`7/1994
`2/1998
`7/1999
`7/1999
`3/2000
`
`OTHER PUBLICATIONS
`
`Stephanie G. Mallat, "A Theory for Multiresolution Signal
`Decomposition: The Wavelet Representation", IEEE Trans(cid:173)
`actions on Pattern Analysis and Machine Intelligence, vol.
`11, No. 7, Jul. 1989, pp. 674-693.
`John G. Daugman, "Complete Discrete 2--D Gabor Trans(cid:173)
`forms by Neural Networks for Image Analysis and Com(cid:173)
`pression'', IEEE Transaction on Acoustics, Speech and Sig(cid:173)
`nal Processing, vol. 36, No. 7, Jul. 1988, pp. 1169- 1179.
`Alberto Tomita, Jr., et al., " Hand Shape Extraction from a
`Sequence of Digitized Gray-Scale Images", IECON '94,
`20th International Conference on Industrial Electronics,
`Control and Instrumentation, vol. 3 of 3, Special Sessions,
`Signal Processign and Control, pp. 1925-1930.
`Giacomo lndiveri et al., "System Implementations of Analog
`VLSI Velocity Sensors", 1996 IEEE Proceedings of M icro(cid:173)
`Neuro '96, pp. 15-22.
`
`(Continued)
`
`Primary Examiner-George Davis
`(74) Attorni!); Agent, or Finn-Townsend and Townsend
`and Crew LLP; Gerald T. Gray
`
`(57)
`
`ABSTRACT
`
`A visual perception processor compri5es histogram calcula(cid:173)
`tion units, which receive the data DATA(A), DATA(B), .
`DATA(E) via a single data bus and supplying cJa5-sification
`information to a single time coincidences bus. In a preferred
`embodiment the histogram calculation units are organized
`into a matrix.
`
`29 CJaims, 31 Drawing Sheets
`
`1016
`
`111
`
`Petitioner LG Ex-1001, 0001
`
`

`

`US 6,959,293 B2
`Page 2
`
`OIBER PUBLICATIONS
`
`Pierre-Francois Riiedi, "Motion Detection Silicon Retina
`Based on Event Correlations", 1996 IEEE Proceedings of
`MicroNeuro '96, pp. 23-29.
`Revue Trimestrielle Des <<Techniques de Lingenieur>>,
`"Instantanes Technique" Techniques De ingenieur, Mars
`1997-No 5 (40F), ISSN 0994--0758.
`Es Professionnels de Linformatique En Entreprise Maga(cid:173)
`zine, "Objectif Securite Des Reseaux", No 24, Janvier, 1997.
`Electroncique International Hebda, 5 Decembre 1996-No
`245, "Premier ... oeil", Francoise Gru svelet (with trans(cid:173)
`lation).
`Nabeel Al Adsani, "For Immediate Release The Generic
`Visual Perception 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/0913vi(cid:173)
`sion.html, pp. 1-3.
`The Japan Times, :"British firm has eye on the future",
`Business & Technology, Tuesday, Nov. 18, 1997, 4th Edi(cid:173)
`tion.
`Inside the Pentagon's, Inside Missile Defense, an exclusive
`biweekly report on U.S. missile defense programs, procure(cid:173)
`ment 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, Mars 1997, ISSN 1157-1151 (with
`translation).
`"Elecktronik Revue" ER, Eine Elsevier-Thomas-Publika(cid:173)
`tion, Jahrgang 8, Marz 1997, NR.3, ISSN0939-1134.
`"Un Processor de Perception Visuelle", LehAUT pAR(cid:173)
`LEUR, 25F Des solutions electroniques pour taus, No 1856,
`15 janvier 1997 (with translation).
`"Realiser Un Decodeur Pour TV Numberique", Electron(cid:173)
`ique, Le Mensuel Des Ingenieurs De Conception, No. 66,
`Janvier 1997.
`Groupe Revenu Frarn;ais, Air & Cosmos Aviation Interna(cid:173)
`tional, "Un Calculateur De perceoption Visuelle", Hebdo(cid:173)
`madaire, vendredi 6 decembre 1996, 34 Annee, No 1590,
`22F.
`Kenichi Yamada, et al; "Image Understanding Based on
`Edge Histogram Method for Rear-End Collision Avoidance
`System", Vehicle Navigation & Information Systems Con(cid:173)
`ference Proceedings; (1994), pp. 445 450 published Aug. 31,
`1994; XP 000641348.
`
`* cited by examiner
`
`Petitioner LG Ex-1001, 0002
`
`

`

`~ • rJ)
`
`•
`
`Mouse
`
`ACTION
`
`WRIT
`COUNTE
`
`FIG. I
`
`PRIOR ART
`
`Petitioner LG Ex-1001, 0003
`
`

`

`U.S. Patent
`U.S. Patent
`
`Oct. 25, 2005
`Oct. 25, 2005
`
`Sheet 2 of 31
`Sheet 2 of 31
`
`US 6,959,293 B2
`US 6,959,293 B2
`
`LS
`0900SLLFLtT
` a7ST2
`
`1-
`
`li
`
`aee
`
`eos:
`
`ee
`
`N
`•
`
`FIG.2
`(!) -u.
`
`
`
` MaxDATA
`
`0
`
`0
`
`<t
`
`r~
`DATA(A
`
`c§
`
`0:::
`(.f)
`
`a::
`oO
`UJ
`LL]
`I-
`z
`::>
`0
`u
`O
`
`—=2Oo
`
`wl
`WRITE
`._1
`o::: I·
`~
`
`.,_
`-
`z
`
`Petitioner LG Ex-1001, 0004
`
`2,17<>»
`
`I
`. 1
`j
`
`N
`T2
`1-
`
`N
`
`.!:I
`
`+ I
`
`' I
`
`-.!:i
`
`t I
`
`I
`
`-~
`
`Tt
`
`,.._
`11,17
`"":. -=
`
`STs rr
`
`C'H e
`eue
`Z'H 8 .
`zt e-
`&.'H B
`ate
`
`2,
`
`t't e
`z·i e
`l't ~
`f'l
`_J
`· (/)
`
`c'a. e
`l ' &. e
`l ' I. e
`N I-
`Cl')
`
`£'He
`~·i.1. e
`,.._ - "":.
`l'Ll e
`,.. - _J
`a:
`S(PI) $l4,1
`en
`
`(/)
`
`Petitioner LG Ex-1001, 0004
`
`

`

`1
`
`~ •
`00.
`•
`
`:
`............. -----------------··v: ··----.. -.. ---------
`,--·--··-·-··-·-··-·-··--~-----··
`ALIDA TIO N
`--
`s
`.
`I J+1/+0 -...
`
`I
`I
`I
`I
`I
`I
`
`107
`
`... I
`------············---·-·-·----
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`
`I : I
`I : :
`: I
`I : : : I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`I
`
`103,
`MIN
`INIT _ -
`MAX
`DATA_
`...
`RMAX
`POSRMAX
`VALIDATION
`NBPTS
`~
`102
`p
`/1 I
`102 r.7
`H, E
`in
`...
`
`102 s
`OUT
`2 1 0
`
`I
`
`I
`
`I
`
`I
`
`I : I
`I :
`1inCj 1inB j 'inA i I
`I :
`
`--
`
`DATA OUT
`IN
`
`-
`-
`
`104
`\
`,
`
`~
`
`1~6
`--,
`-+-
`~ux
`o-.
`t
`
`.. -
`
`INIT
`WRITE+
`-...
`~MUX
`' + \...105
`INIT
`
`-...
`
`COUNTER
`
`DATA(A)
`
`.
`! : I
`I : I
`; ·--~-----------·--
`
`MEMORY
`WR
`100
`ADRESS
`
`I I I I I "'101 r
`101
`OUT
`+ 101 s
`
`I
`
`I
`
`'
`\_ 111
`: :
`----------·--------------------------------------------------=
`FIG. 3
`
`I
`I
`I
`I
`
`Petitioner LG Ex-1001, 0005
`
`

`

`INIT
`
`WRITE
`
`END
`
`COUNTER
`SEQUENCER 1--- ----+-
`Val-Zone
`
`Clock
`SL
`ST
`
`Curve
`Col-Counter
`Curve
`Row-Counter
`
`106 1
`.----t-,1
`oMUX I
`I
`1
`
`~-------,
`. DATA OUT
`IN
`
`1QQ
`
`91
`
`LEARN i ... !1--4-+-___,·
`
`INIT~END
`110
`
`,·····--·-·-··-······-·· 107 ·----···············--············
`!
`. '\ s
`.
`i
`I +1/+0 I .
`i
`!
`i
`j
`i O
`13
`•
`1
`l 1 ~ ,--l-~ WR
`INIT l
`..... ~~JI§ __ ..;.1-, -1-09 _______ ,_-/ ms
`,
`.
`-.-1
`-
`t
`~ux 1
`,.i)MUX
`1 A I .
`
`1
`
`•
`
`--····G
`\ I
`
`104
`MIN
`MAX
`RMAX
`POSRMAX
`NBPTS
`POSMOYo
`POSMOY1
`
`~ • rJ)
`
`•
`
`12
`
`103 . r-.
`INIT
`.
`
`CATA
`
`.
`•
`VALIDATIOl_,I
`
`RWJ(
`
`!
`!14
`'•·, 1 15
`!
`i
`. i I
`}6 i
`L-'-- -P-i----........,, i
`:
`114
`
`· ADRESS
`..--~-....,-j··..r..,,~1--~---"'-=--::'.._,. ~ :-
`~ -~ ~ i
`
`Val-Zone
`c..,
`
`r
`
`CURVE
`!
`: GENERATOR 1 (7!;:::
`
`LSetlf,-.,.__--------'"-H,
`
`[
`
`END
`
`::
`
`1108
`
`'>- D~JA
`
`:
`
`PROGl:11'4ABLE
`
`INTE~~~NECT
`
`, 15
`~ COMBINATORIAL
`LOGIC ARRAY
`
`u_,
`
`END
`
`-Jli-l-+----1~----=-=-=---+t WR 101 f
`cgc~~~A~ ~:!--+---+~--l~UX :i----~- ADRESS
`I
`INIT i f ~~~
`Ou~,u; l=c+ i~E __ • • ·:~-.... -:--.... i~..1 ··
`i
`..
`-··-·- .
`.....
`---··-····---····
`····-·-·
`L
`(- - - - - - -+ - - - - \ '\. -Yr
`\[
`101s
`111
`FIG. 4
`
`i
`
`-:--....,
`. · .. .
`
`Petitioner LG Ex-1001, 0006
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 5 of 31
`
`US 6,959,293 B2
`
`CT
`WRITE :J
`INIT __jl.__ _ _ _ _ _ _ _ _ __ _ _ rt__
`END_jlL.-_ _ _ _ _ _ _ _ _ _ _ _ ___.n~- -
`
`OATA (A) _1!11 __ §
`
`FIG. 5
`
`-
`
`START
`MASTER
`I
`
`I ST•O; INIT• O; ENO•O; I
`
`SL•O;
`
`WRITE• O;
`
`I ST=1 I
`
`I INIT: 1 COUNTERzO I
`
`.
`< COUNTER• Max_OATA
`I CLOCK I
`
`I
`
`ST=O;
`COVNTER:COUNTER+1
`
`YES
`
`YES
`
`,
`'
`,
`
`-
`
`Reaisters
`Max DATA
`
`Row Size
`c 0Cs 1ze
`R ow_ C urve_ Size
`Col_Cu rve_ Size
`l n it_Row_ Curve
`l nit_ Col_ C urve
`
`YES
`
`4
`I CLOCK I
`
`INIT=O; WRJTE: O;
`Row_Counterso
`Col_Cooote,,,O; .
`
`Row_Counter-Row_Slze )
`;>
`
`Col CountePCol Size
`
`.
`
`Curve
`Sequence
`
`Val-Zone
`
`Row_Curve
`Col_Curve
`
`I CLOCK
`I SL=O
`
`I
`
`I
`
`I CLOCK I
`I SL=1 I
`
`END• 1
`
`cou::ounter-0
`Row_Counter-Row_Counter+ 1
`
`I
`I VVRITE .. O I
`I .
`I COUNTER=O
`-
`YES
`COUNTER•Max DATA>
`t
`I CLOCK I
`I CLOCK I
`I END"O I I COUNT ER=COUNTER+1 I
`1.-..-..-1
`
`.
`I ' C<ll_Counter-Col_Counter•1 I
`
`I CLOCK
`I SL=O I
`
`I ·
`
`FIG. 6
`
`Petitioner LG Ex-1001, 0007
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 6 of 31
`
`US 6,959,293 B2
`
`START
`SLAVE
`
`INIT•O; END=O;
`WRITE• O;
`
`Reaisters
`Max_DATA
`Row_$ize
`Col_Size
`Row_Curve_Size
`Col Curve Size
`lni(Row_Curve
`lnit_Col_Curve
`
`INIT•1
`COUNTER•O
`
`COUNTER-Mex DATA
`
`CLOCK
`
`COUNTER=COUNTER+1
`
`YES
`
`CLOCK
`
`fNIT•O;
`Row_Counter-0
`Col_Counter-0;
`
`SL•1
`NO
`Row_Counter=Row Size
`
`Col_Counter=Col_Size
`
`Curve
`Sequence
`
`Val-Zone
`
`Row_Curve
`Col_Curve
`
`WRITE•O
`
`WRITEsO
`
`CLOCK
`
`CLOCK
`
`Yl;S
`
`NO
`Col Counterao
`Row_Counter=Row_Counter+1
`
`END=1
`
`COUNTER:oO
`
`Col_ Counter-Col_ Counter+ 1
`
`YES
`
`COUNTER:Max_OATA
`
`CLOCK
`...... -:...-:..."1--:.--..... --' - -c~o-u-Nr=e=R~ .. ..1c""'o'""u,..N""'r""'E"'"R-•1.,....,
`
`FIG.7
`
`Petitioner LG Ex-1001, 0008
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 7 of 31
`
`US 6,959,293 B2
`
`CURVE
`SEQUENCE
`
`Row CotJnter>=lnit_Row_Curve
`NO
`
`Row_Counter <
`lniLRow_Curve+Row_Curve_Size
`
`Re isters
`Row_Curve_Size
`Col_Curve_Size
`lnit_Row _ Curve
`lnit_Col_Curve
`
`NO
`
`Col_Counter>=lnit_Col_Curve
`
`NO
`
`Col Counter <
`lnit_Col_Curve+Col_C urve_Size
`
`YES
`
`Val_Zone=0
`
`NO
`
`Val_Zone=1
`
`Row Curve -Counter=
`Row_Counter • lnit_Row_Curve
`
`Col Curve Counter(cid:173)
`Col_ Counter • init_ Col_ Curve
`
`Fig. ·s
`
`INIT
`SEQUENC
`
`INIT;o1
`NO
`R
`MIN=Max_Param
`MAX• O
`NBPTS=O
`POSRMX=0
`RMAX=O
`
`Data ln=O
`Adress=COUNTER
`WR=1
`
`CLOCK
`Yes ____ ___
`INIT=1
`
`WR=0
`
`104
`
`100
`
`Fig. 9
`
`Petitioner LG Ex-1001, 0009
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 8 of 31
`
`US 6,959,293 B2
`
`H
`Data ln=Data Out + Validation
`Adress=DATA-(A)
`WR=1
`
`Classifier
`Data_ Out=Resut_Memory
`Adress=DAT A (A)
`WR=0
`
`101
`
`MIN> DATA (A)
`
`NO
`
`MAX< DATA (A)
`
`NO
`
`RMAX < Data_ln
`
`104
`
`YES
`
`104
`
`NO
`
`RMAX=Oata_ln
`POSRMX=DAT A (A)
`
`YES
`
`104
`
`NBPTS=NBPTS+ 1
`
`Validation=1
`
`NO
`
`.CLOCK
`
`YES
`
`WRITE=1
`NO
`'-----------'
`
`Fig. 10
`
`Petitioner LG Ex-1001, 0010
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 9 of 31
`
`US 6,959,293 B2
`
`END
`SEQUENCE
`- I
`•
`I CLOCK I
`I
`, YES
`END= 1
`/
`'NO
`
`-
`-
`
`I
`
`•
`
`I
`
`''
`Reg=0
`POSMOY1 = POSMOYo
`_,
`H Memory
`Adress = COUNTER
`WR=0·
`Data_Out=A
`
`Update Classification
`
`I
`
`100
`-~
`
`' /
`
`YES
`
`I
`. I a= 11
`
`I
`
`L..--' 101
`
`-
`
`New
`POSMOY
`Computation
`
`<
`
`A>= RMAX/2
`i NO
`I a= o I
`,_
`
`.~
`
`Classifier
`
`Data_ln = a
`Adress = COUNTER
`WR= 1
`
`YES
`
`I
`I
`
`•
`
`•
`
`'f
`
`/ Reg> NBPTS/2
`'
`NO
`Reg= Reg +A
`POSMOYo = COUNTER
`_,
`I CLOCK
`I
`~ END= 1
`.L •
`
`YES
`
`Anticipation Application
`
`I
`
`Fig. 11
`
`Petitioner LG Ex-1001, 0011
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 10 of 31
`
`US 6,959,293 B2
`
`105
`
`QATA (A)
`COUNTER
`
`.1QQ
`ADRESS
`
`INIT
`110
`
`END
`
`11 9
`
`P>Q
`
`p
`'--------·-··-·------
`
`i
`_____ J
`I
`
`104
`RMAX
`NBPTS
`
`101
`
`11 5
`
`119s
`
`108
`
`END
`
`DATA (A}
`COUNTER
`
`INIT
`112
`
`END
`
`FIG. 12
`
`: · ---------------------------------------------------------------------·
`i
`120
`;
`:
`!
`:
`
`ill
`
`I
`
`i
`
`,--+-,...,
`0 -----1
`
`t-=,,......,,.~
`~- - RMAX
`
`7
`!
`I
`I
`:
`:
`
`119
`
`P>Q
`
`Q
`
`1 " 4 - - - - -
`i 114
`r---1MUX
`122
`!
`2----, ~~ f..,..,,=,,,=-i !
`A 14----i NBPTS
`!
`j
`_..--,--1A/B
`.........,,....3_,
`l
`!
`r-=,..,.,,..,~-:--:t:;:;:--~=-B __ _,
`
`:
`..................... ·--·-------··-··-·-----................. --·-· ... ------ ····--· ________ ............... - ................... _ ............. J
`124
`123
`
`FIG. 130 -
`
`Petitioner LG Ex-1001, 0012
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 11 of 31
`
`US 6,959,293 B2
`
`Data (A) ·
`
`12
`
`Fig. 31b.
`
`111
`
`RMAX
`
`Fig 13b
`
`B
`A
`Fig 13c
`
`Petitioner LG Ex-1001, 0013
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 12 of 31
`
`US 6,959,293 B2
`
`300
`
`117
`
`DATA OUT t--t----,
`IN
`
`INIT
`WRITE
`DAT A
`COUN .;;;.R---t._.
`
`~-"'1 WR
`
`100
`
`i--__., ADRESS
`
`INIT
`END
`
`INIT
`
`ill
`
`1153-
`
`1154
`1151
`
`1041
`
`r--+------..... ---t--;--..-i_ Borne-A
`-En
`- -
`1152
`
`1042 -
`
`.------_...-----t-~ someB
`En:
`
`FIG. 13d
`
`1043
`
`Petitioner LG Ex-1001, 0014
`
`

`

`INIT
`WRITE
`DATAA
`COUNTER ~ux
`
`05
`
`INIT
`
`DATA
`IN
`
`OUT
`
`A
`
`WR
`
`1QQ
`
`AORESS
`
`INIT
`END
`
`300
`
`117
`
`301
`
`+
`
`reg.
`
`p
`
`P>Q
`a
`
`COUNTER
`
`303
`
`302
`
`~04
`
`FIG. 14
`
`d •
`00
`•
`~
`
`~ ....
`=
`....
`
`~
`
`0
`(')
`l"""
`N
`~VI
`N
`~
`Vt
`
`00 :r
`~ ....
`
`~
`
`I--'
`~
`Q _,
`~
`I--'
`
`Petitioner LG Ex-1001, 0015
`
`

`

`DATA OUT1----4t-_..,.
`IN
`INIT
`MEMORY
`END
`WR
`1QQ
`.,__ _ __.,. ADRESS
`
`11I
`
`POSMOYo
`POSMOY1
`
`105
`DATA A
`COUNT~E ........ R-
`
`119
`
`312
`
`11
`
`RMAX
`NBPTS
`
`101
`
`Cj
`•
`rJl
`•
`'-= ~
`~ = ~
`
`~
`
`~
`r"'
`N
`~Ul
`N
`Q
`Q
`Ul
`
`31
`•
`•
`.....
`..,_H
`
`104
`
`r:,:i =-~
`~ ...
`Q -.
`
`(,.)
`),a
`
`),a
`~
`
`OUT
`
`FIG. 150
`
`101s
`
`Petitioner LG Ex-1001, 0016
`
`

`

`Cj
`•
`rJl
`•
`
`INlT
`END
`
`310
`
`POSMOYo
`II
`•
`POSMOYt
`--------+---+------+--ltt,11
`r - - - - - - -+ - - - . ; . _ - - -L -~~M
`
`. 104
`
`NBPTS
`Some-A
`BomeB
`
`312
`
`101
`
`108
`
`112
`
`INIT
`
`FIG.15b
`
`OUT
`
`101s
`
`Petitioner LG Ex-1001, 0017
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 16 of 31
`
`US 6,959,293 B2
`
`r·····-····-·····-·····-···i,.-- 315
`I
`•
`I
`DATA
`ao !
`i,..;:..;.,.;.IN.;;...;.----se~, o~----t-..u
`140o !
`!
`!
`a, l
`1401 j
`!
`l
`a2 l
`
`130
`
`WR
`i------1..-. En
`
`131
`
`OUT
`
`101s
`
`FIG. 16
`
`AORESS
`
`: .
`
`140n !
`. l
`.
`.
`i
`!
`--······-···--····-··-·--·
`
`Petitioner LG Ex-1001, 0018
`
`

`

`DATA our---(cid:173)
`lN
`MEMORY
`100
`WR
`.,___~ ADRESS
`
`111
`
`POSMOYo
`POSMOY1
`
`d •
`00
`•
`
`105
`
`DATA A ---
`
`COUNTER
`
`101
`
`104
`RMAX
`NBPTS
`'..._ _____ _.I
`
`. . ,..,._--c
`: .
`~
`11s
`1
`···-'
`'
`rr===:==;...~:_ ___ -4--f ETD la-bl Signe
`1-4------+-fT
`1-4------+-tSP
`..,._-----~SM
`
`119
`
`END
`
`i------+-PVIUNl:SSOIJT
`OUT
`
`Clock
`END~~~~--__,
`
`108
`DATA A
`COUNT~E~R.c
`
`INIT
`
`FIG. 17
`
`101s
`
`Petitioner LG Ex-1001, 0019
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 18 of 31
`
`US 6,959,293 B2
`
`Sel 1
`
`FIG. 18
`
`Qo
`
`Q1
`
`Qz_
`
`1
`SP
`Qo
`Q2
`SM
`Q2
`Qo
`
`01 ..
`
`02 ..
`
`On •
`
`150
`
`OUT1
`
`208
`
`I-
`
`D. en
`
`FIG. 19
`
`Petitioner LG Ex-1001, 0020
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 19 of 31
`
`US 6,959,293 B2
`
`w
`I-
`a:
`a
`0
`z
`I-
`~ w w
`
`I-
`
`Q. ~
`en
`en
`
`CUMUL
`
`SP
`SM
`,.__ ~
`
`RMAX
`
`RMAX/2
`
`to
`
`to
`
`b
`
`b
`
`ts
`
`FIG. 20
`
`Petitioner LG Ex-1001, 0021
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 20 of 31
`
`US 6,959,293 B2
`
`Anticipation
`Application
`r··-·········-·-····-·····-----·····-··························-·······················-·1
`!
`l
`YES
`310
`~ POSMOYo - POSMOY1 ~ 0 > - - - - - - - ,
`.':,
`.
`NO
`!
`J A= P9SMOY1 - POSMOYo
`j
`Sign=1
`L ............. _ .............. --.. --------------·-----------..... - .................................. _....
`.. ......................... , ___ J
`r· -
`· .-----_.._-__,
`.--------_,
`1
`ETD=1
`ETD=1·
`SM=1
`SP=1
`T=O
`T=O
`
`0
`i:,
`
`I
`
`:
`1
`:
`i
`A= POSMOYo- POSMOY1 !
`!
`Sign=0
`
`i,
`
`311
`
`Wait A•cIock
`
`Wait A*Clock
`
`SM=O
`SP=1
`T=1
`
`SP=O
`SM=1
`T=1
`
`Wait A*Clock
`
`Wait A*Clock
`
`FIG. 21
`
`i
`I
`ETD=0; SM=0; SP=0; T=0;
`:
`~---r-----
`I
`L .................................. ·-·······-····--···· .•. ··········-·····-·······-·····--············J
`
`Petitioner LG Ex-1001, 0022
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 21 of 31
`
`US 6,959,293 B2
`
`I .
`. I
`I·
`· I
`I
`I
`~ I
`-
`. I
`E
`I
`ii
`I
`CD
`I
`I
`I
`I
`I
`I
`I
`
`.
`Product term o
`
`Produ.ct term 1
`
`-------------------------~
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`uctterm n
`I
`_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ I
`
`12
`
`A Product teim
`
`FIG 22
`
`605
`
`,I
`
`I
`
`FIG. 39
`
`Petitioner LG Ex-1001, 0023
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 22 of 31
`
`US 6,959,293 B2
`
`,---······-···- ------------------
`i
`i
`
`j
`i
`i,
`
`i 14~
`l
`
`400
`
`·---··-····------------------C . ---····7
`l
`:_;
`I
`t
`i
`
`404
`
`410
`
`Reg_ao
`
`Reg_bO
`
`n
`
`ln_A
`
`in B
`
`FIG. 23
`--···-------- ---,
`
`: MAP
`12
`, ...... - - -- --r---, ~
`MLRN
`\,---------,
`~
`!
`I
`
`I
`
`I
`j FIG. 24
`Pr~cttennO
`I
`
`j
`E :,
`(I)
`CCI
`
`e .. ~ -I &
`
`In
`
`i
`!
`I i
`!
`I Ei n . ;
`
`<t
`
`I i
`[._ _______ _
`
`I
`
`Petitioner LG Ex-1001, 0024
`
`

`

`
`
`
`CONFIG 4
`
`
`_CONFIG2|
`
`
`
`Jsecsessn|
`
`
`CONFIG n
`
`
`
`eneresesoeeed
`
`12
`
`d •
`00
`•
`
`wwaIe*S"0
`
`
`S007‘SZ‘90
`T€J€%way
`
`
`
`'
`
`
` 7H£67'6S6'9SA
`
`
`PROGRAMMABLE
`
`INTERCONNECT
`. . . . . . .
`AND
`
`COMBINATORIAL
`
`LOGIC ARRAY
`i
`!
`i
`inA !
`!
`· - ····-·•·---'
`
`·--
`
`FIG. 25
`
`Petitioner LG Ex-1001, 0025
`
`Petitioner LG Ex-1001, 0025
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 24 of 31
`
`US 6,959,293 B2
`
`6
`
`X
`
`y
`
`Space
`transform
`
`PARAMETER
`
`1
`
`a
`
`FIG. 26
`
`111
`
`0
`
`FIG. 27
`
`Petitioner LG Ex-1001, 0026
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 25 of 31
`
`US 6,959,293 B2
`
`I
`SCREEN .
`
`MEMORY
`WR ~
`ADRESS
`
`58
`
`59
`r-·--·--··--····
`t--if---+--t----t---i~ Cursor
`I
`~t-----r----.. Generator:"'"--~
`~----
`·T---··--J
`352
`366 ../
`_S_R--1~
`
`353
`
`INIROW
`
`365
`
`S e q (cid:173)
`' - - - - , - , - - - - Val_Zone
`Fig. 28
`s1
`
`SV
`SH
`CLK
`
`INICOL Column Counter
`362
`
`361
`
`xt
`
`)
`364
`
`360
`
`363
`
`385
`
`Fig. 29
`
`Petitioner LG Ex-1001, 0027
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 26 of 31
`
`US 6,959,293 B2
`
`5
`
`S(t) _ __,
`
`ST-.-,
`SL--.-i
`
`QAT
`
`(A~
`
`DATA 8
`DATA (C)
`
`DATA (D)
`
`DATA E)
`
`6
`
`FIG. 30
`
`FIG. 310
`
`r ··-···-·-····· .. ;oo·-···-····-····--·-···-·····-······-··-· v1 a
`i 1h
`Irr
`
`Out
`~ - - - r - r - r
`
`12
`
`Petitioner LG Ex-1001, 0028
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 27 of 31
`
`US 6,959,293 B2
`
`r
`.
`! +
`!
`I
`i
`i
`i
`I
`i
`!
`i
`
`i
`
`t t
`
`I
`
`I
`
`f
`
`·- -
`
`6
`
`!
`i
`l
`!
`!
`!
`i
`I
`I
`I
`
`.
`
`.
`
`-~
`~513
`
`.
`
`..
`
`/
`EM8EOOEO
`N'PUCATION -
`
`~
`
`~ "' L
`~ITI!
`~NO,
`
`T s
`
`1
`
`V
`D
`MVT MVT ·
`
`API
`
`~
`
`2
`
`.
`
`)
`
`r
`
`pO
`~ !
`I
`p1
`~ j
`l
`p2
`~ !
`I
`I I
`
`1ACl2
`
`li2l
`
`j g ~
`~ -
`
`.1Jl.m
`
`lill"
`
`1m
`
`.!All
`
`~ .1al.t
`
`.1a22
`
`1m
`
`llJ1 ~ .1.ill
`
`5 0
`
`I
`I
`I
`I
`i
`! '
`ls
`!
`i
`i
`, , ..'.j_·--·· -·---•··•·--·· ·-·· ·--·····----· .
`-·-p-;:--.7
`1~, ~
`I
`111
`365 -CJ+
`510
`p1 5
`r-"'-: .... ~
`I
`t-·-····-····-··············-··-········ -- FIG: "32··--··---·
`-----,
`521
`
`I
`r--
`i I I
`!
`i I
`! !
`{--------~
`
`RETINE
`
`Out algnol
`
`CMOS lmager
`
`~---------~ ·
`1 ..... · -····--···-· · · · · -·-·· ··-········--·-······· · · - - -· -··· • ····- · · -· · · - · ........ . . ... ..... . . .. . ....... - -• .J
`FIG. 33
`
`Petitioner LG Ex-1001, 0029
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 28 of 31
`
`US 6,959,293 B2
`
`I
`
`!
`
`····--···,
`I I
`I
`!
`I I
`i
`i
`i
`I
`I
`!
`
`I
`
`i
`
`I i
`
`r~·-···· ·---······ .. ······················-·······-··-···-···-···· .. ··· ..
`!
`
`·--
`
`...J
`
`i
`
`i I I
`
`i
`I
`j
`i 1 .
`I
`· I
`i
`I
`I
`
`c~
`1 - - - - - - - 1
`
`i
`I
`j
`I
`i
`
`(/)
`~r---
`
`..J
`c5
`a.
`
`1.-
`i
`i
`!
`• I
`I
`
`i I
`
`!
`
`I i
`i
`i
`1
`I
`I
`l
`I
`l
`L.---...1.....----..J.----'---~ i
`i
`~ !
`l
`....
`.
`i
`!
`l
`i
`!.
`i L.. _ _;_ _ _.__...1............1~_,_ __________ _._~ I
`i
`;
`- - - - - - - - - -
`L.·-··-·· ·-·-··-··--····· ... ······-·-·····--·-··· ·-·---····-- ··------··'°······-- ·J
`FIG. 34
`.
`'-s3o
`
`Petitioner LG Ex-1001, 0030
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 29 of 31
`
`US 6,959,293 B2
`
`I
`
`:
`
`r-·-··-··-·-·-··--·•-"--·-·-·---···-··. ·-···--··------·--··--7
`I
`~
`j
`I
`i
`
`a
`
`COffllll(le9
`
`Out llgn(cid:127) I
`
`CMOS lmager
`
`CMOS lmager
`""'---·---···-·---···-·--
`
`l
`I
`' - - - - -. _-_-_-_--_-__ -_-_'-'-'=.J
`I
`
`v-
`
`FIG. 35
`
`/ 6
`(
`
`I+ V3
`
`FIG. 36
`
`5 - 'J
`
`1a
`
`FIG. 37
`
`V 1+
`
`I
`
`/
`
`6
`
`6
`_L-J
`
`V2
`
`'
`
`Petitioner LG Ex-1001, 0031
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 30 of 31
`
`US 6,959,293 B2
`
`36
`
`OPOATA---+-...
`
`CLRSCR - - - - , -
`
`SCREEN
`
`8
`
`SR
`
`365
`
`366
`
`15
`
`14
`
`1a
`
`510
`
`DAT A (A) t----i-----<~
`DATA (B) t---+--~
`
`DATA (E)t--+--~
`
`..--------.-START
`STOP
`--r-"f-MAP
`MLRN
`
`Out(i)
`
`FIG. 38
`
`11
`
`Petitioner LG Ex-1001, 0032
`
`

`

`U.S. Patent
`
`Oct. 25, 2005
`
`Sheet 31 of 31
`
`US 6,959,293 B2
`
`-....
`
`....
`-7_
`
`r-----
`(7
`~ I .. _
`
`------ ---------- - . _ j
`0 ....
`
`I()
`
`-----~--------7
`I .
`-
`- - - - - - - - - - - - - - - , I
`S .-- ~ - - - - - , I I
`
`§
`I
`\1.i
`.-.o
`I
`I
`___ $ __ ~ ______ J
`
`FIG. 40
`
`rl
`
`cu
`....
`
`I
`I
`I
`I
`I
`I
`
`I : ~
`
`I
`I
`I
`I
`L_
`
`Petitioner LG Ex-1001, 0033
`
`

`

`US 6,959,293 B2
`
`1
`METHOD AND DEVICE FOR AUTOMATIC
`VISUAL PERCEPTION
`
`BACKGROUND OF THE INVENTION
`
`20
`
`2
`nized into a matrix ; the histogram calculation units process
`data aijT associated with pixels forming together a multidi(cid:173)
`mensional space (i, j) evolving with the course of time and
`represented at a succession of instants (T), wherein the said
`5 data reaches the said calculation unit in the form of a digital
`signal DATA(A) in the form of a succession aijT of binary
`number of n bits associated with synchronization signals
`enabling to define the given instant (T) of the space and the
`position (i, j) of the pixel in this space, to which the signal
`10 aijT received at a given instant (t) is associated, and com(cid:173)
`prises:
`an analysis memory comprising a memory with
`addresses, each associated with possible values of the num(cid:173)
`bers of n bits of the signal DATA(A) and whose writing
`15 process is controlled by a signal <<WRITE>>,
`a classifier comprising a memory intended for receiving a
`selection criterion C of the parameter DATA(A), receiving
`the signal DATA(A) at the input and that outputs a binary
`output signal whose value depends on the result of the
`comparison of the signal DATA(A) with the selection cri(cid:173)
`terion C,
`a time coincidences unit receiving the output signal from
`the classifier and, from outside the histogram calculation
`unit, individual binary enabling signals affecting parameters
`other than DATA(A), wherein the said time coincidences
`unit outputs a positive global enabling signal when all the
`individual time coincidences signals are valid,
`a test unit,
`an analysis output unit,
`an address multiplexer,
`an incrementation enabling unit,
`wherein the counter of each address in the memory
`35 corresponds to the value d of a;j, at a given instant, which is
`incremented by one unit when the time coincidences unit
`outputs a positive global enabling signal,
`the unit intended for calculating and storing statistical
`data processes, after receiving the data aij, corresponding to
`the space at an instant T, the content of the memory in order
`to update its own memories,
`the memory is deleted before the beginning of each frame
`for a space at an instant T by an initialization signal
`<<INIT>>.
`the memory of the classifier is an addressable memory
`enabling real time updating of the selection criterion C and
`having one data input DATA IN, an address command
`ADDRESS and a writing command WR, receiving on its
`input the output from the analysis memory and a signal END
`50 on its writing command,
`it also comprises a data input multiplexer with two inputs
`and one output, receiving on one of its inputs a counting
`signal COUNTER and on its other input the succession of
`data a;j, to the address command of the memory of the
`55 classifier and an operator OR controlling the address mul(cid:173)
`tiplexer and receiving on its inputs an initialization signal
`INIT and the end signal END.
`the space (i, j) is two-dimensional and that the signal
`DATA(A) is associated with the pixels of a succession of
`images.
`it comprises means for anticipating the value of the
`classification criterion C.
`the means for anticipating the value of the classification
`65 criterion C comprise memories intended for containing the
`values of statistical parameters relating to two successive
`frames T0 and T1 .
`
`25
`
`The invention relates generally to methods and devices
`for automatic visual perception, and more particularly to
`methods and devices for processing image signals using one
`or more self-adapting histogram calculation units capable of
`implementing anticipation and learning modes. Such
`devices can be termed an electronic spatio-temporal neuron,
`and is particularly useful for image processing, but may also
`be used for processing of any other signals, such as sound
`signals.
`Image processing methods and devices are already
`known, which enable real-time recognition, localization
`and/or extraction of objects corresponding to certain criteria
`of their context. The selection criteria can be extremely
`varied. They may be related to speed, shape, color ... or a
`combination of these criteria. These methods and devices
`can be used to facilitate the acquisition of a scene or of a
`phenomenon by an observer or to control an automatism on
`the basis of information thus extracted. Such methods and
`devices are for example described in the following publica-
`tions FR-2.611063 and WO-98/05002.
`Certain of these methods and devices implement a spatial
`and temporal processing unit that, upon receiving a video(cid:173)
`type signal S(PI), produces a number of parameters for each
`pixel. It may be, for instance speed V, direction DL, a time 30
`constant CO and a binary enabling parameter VL in addition
`to the delayed video signal VR and the different frame, line
`and pixel synchronization signals gathered under the
`denomination F.
`In such devices, the importance of constituting histograms
`of these parameters and using them in a visual perception
`processor has already been outlined in order to acquire,
`manipulate and process statistical information.
`The purpose of such a visual perception processor
`includes outputting a signal S'(t) that carries for each pixel 40
`a significant piece of information of the result obtained when
`applying recognition or selection criteria. These criteria are
`predefined or prepared by the image processing methods and
`devices properly speaking.
`Such a method and such a device, in particular, are 45
`divulged in the patent application WO-98/05002, already
`mentioned, that has been integrated thereto for reference
`purposes.
`It is therefore desirable to provide an improved visual
`perception processor, and methods, as well as, in preferred
`embodiments, the auto-adapting, anticipation and learning
`functions.
`
`SUMMARY OF THE INVENTION
`
`This invention provides visual perception devices and
`methods for detecting automatically an event occurring in a
`space with respect to at least one parameter.
`According to the invention, a perception device comprises
`a control unit, a data bus, a time coincidences bus and at least
`a histogram calculation unit for processing the parameter.
`The present invention also covers the features that will be
`put in evidence by the following description and that will
`have to be considered either independently or in technical
`combinations:
`the device comprises, in order to process a number of
`parameters, a number of histogram calculation units orga-
`
`60
`
`Petitioner LG Ex-1001, 0034
`
`

`

`US 6,959,293 B2
`
`10
`
`15
`
`4
`lation unit in order to get a representative histogram of the
`parameter and to infer the desired result.
`The invention also relates to an analysis method of a
`parameter representative of an event in an electronic device,
`comprising a histogram calculation over data aij, associated
`with pixels forming together a multidimensional space (i, j)
`evolving with the course of time and represented at a
`succession of instants (1), wherein the said data reaches the
`said calculation unit in the form of a digital signal DATA(A)
`in the form of a succession aij, of binary number of n bits
`associated with synchronization signals enabling to define
`the given instant (T) of the space and the position (i, j) of the
`pixel in this space, to which the signal a;j,, received at a
`given instant (T) is associated, and comprises:
`to each data aij, is associated a classification binary signal
`whose value depends on the result of the comparison
`between the signal DATA(A) and the selection criterion C,
`a statistical distribution of the data a;j, is made for a given
`instant for which a global enabling signal is positive, the said
`global enabling signal being made of a set of individual time
`coincidences signals, each one corresponding to a parameter
`DATA(A), DATA(B), . . . , DATA(E), resulting from the
`comparison between a time coincidences criterion R and the
`25 classification signal and being positive.
`Reference to the remaining portions of the specification,
`including the drawings and claims, will realize other features
`and advantages of the present invention. Further features
`and advantages of the present invention, as well as the
`30 structure and operation of various embodiments of the
`present invention, are described in detail below with respect
`to the accompanying drawings. In the drawings, like refer(cid:173)
`ence numbers indicate identical or functionally similar ele(cid:173)
`ments.
`
`20
`
`3
`the statistical parameters are the average values of the
`data aij, enabled.
`the analysis output register constitutes and stores in its
`memory at least one of the following values: the minimum
`'MIN', the maximum 'MAX', the maximum number of 5
`pixels for which the signal V;j, has a particular value
`'RMAX', the particular value corresponding POSRMAX,
`the total number of enables pixels 'NBPTS'.
`the statistical comparison parameter used by the classifier
`is RMAX/2.
`it comprises a controlled multiplexer, capable of receiving
`at input several statistical parameters and that the nature of
`the comparison made by the classifier depends on the
`command of the said multiplexer.
`it comprises a learning multiplexer intended for receiving
`an external command signal and producing an operation
`according to a learning mode in which the registers of the
`classifier and of the time coincidences unit are deleted when
`starting to process a frame and that the analysis output
`register supplies values typical of the sequence of each of
`these registers.
`the memory of the classifier includes a set of independent
`registers D, each comprising one input, one output and one
`writing command, wherein the number of these registers D
`is equal to the number n of bits of the numbers of the
`succession V;j, and that it comprises a decoder enabling to
`output a command signal corresponding to the related input
`value (address) and a multiplexer controlled by this input
`value, thus enabling to read the chosen register.
`it comprises multiplexers, each of them being associated
`with the input of each register and combinatory modules
`connecting the registers to one another, wherein the said
`multiplexers enable to choose between sequential writing
`and a writing mode common to all the registers connected 35
`together by the combinatory modules.
`the combinatory modules comprise a morphological
`expansion operator including a thr