(12) United States Patent
`Pirim
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006486909Bl
`US 6,486,909 Bl
`Nov. 26, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54)
`
`IMAGE PROCESSING APPARATUS AND
`METHOD
`
`(75)
`
`Inventor: Patrick Pirim, Paris (FR)
`
`(73) Assignee: Holding B.E.V., D'Esch (LU)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.:
`
`09/230,502
`
`(22) PCT Filed:
`
`Jul. 22, 1997
`
`(86) PCTNo.:
`
`PCT/FR97 /01354
`
`§ 371 (c)(l),
`(2), ( 4) Date:
`
`Sep. 13, 1999
`
`(87) PCT Pub. No.: W098/05002
`
`PCT Pub. Date: Feb. 5, 1998
`
`(30)
`
`Foreign Application Priority Data
`
`Jul. 26, 1996
`
`(FR) ............................................ 96 09420
`
`Int. Cl? .................................................. G06K 9/00
`(51)
`(52) U.S. Cl. ........................................ 348/143; 382/262
`(58) Field of Search .......................... 348/143; 382/262,
`382/107, 236
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,109,425 A *
`5,384,865 A *
`5,694,495 A
`5,712,729 A
`5,793,888 A
`
`Lawton ... .. ... ... ... ... ... .. ... 382/1
`Loveridge . . . . . . . . . . . . . . . . . . . . 382/54
`Hara et a!. .................. 382/324
`Hashimoto .................. 359!562
`Delanoy ..................... 382/219
`
`4/1992
`1!1995
`12/1997
`1!1998
`8/1998
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`FR
`FR
`wo
`wo
`
`0 046 110 A1
`2 611 063 A1
`2 751 772 A1
`wo 98/05002
`wo 00/11610
`
`2/1982
`8/1988
`1!1998
`2/1998
`3/2000
`
`OTHER PUBLICATIONS
`
`Stephane 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.
`Giacomo Indiveri et al., "System Implementations of Analog
`VLSI Velocity Sensors", 1996 IEEE Proceedings of Micro(cid:173)
`Neuro '96, pp. 15-22.
`
`(List continued on next page.)
`
`Primary Examiner-Chris Kelley
`Assistant Examiner-George A Bugg
`(74) Attorney, Agent, or Firm-Townsend and Townsend
`and Crew LLP
`
`(57)
`
`ABSTRACT
`
`The purpose of this invention is a process and a device
`operating in real time for identifying and localizing an area
`in relative movement in a scene and determining the speed
`and oriented direction of this relative movement in real time.
`
`The process carries out temporal processing of the digital
`video input signal S(PI) that consists in deducing, from the
`variations between the value of each pixel in a frame and in
`the immediately preceding frame, a binary signal DP iden(cid:173)
`tifying whether or not there was a significant variation and
`a digital signal CO representing the magnitude of this
`variation, and a spatial processing consisting in distributing
`in a matrix these two signals successively for a single frame
`that is scanned through the matrix, and deducing the
`required relative movement and its parameters from this
`matrix distribution. The device achieves this by including a
`temporal processing unit 15 associated with a memory 16
`and a spatial processing unit 17 associated with a delay unit
`18; the clock unit 20 and the control unit 19 control the rate
`of operation of units 15 and 17.
`
`36 Claims, 10 Drawing Sheets
`
`~~;\~L~
`( 5r_ al7,2
`a1.2--..::\
`a
`~···
`-TR'2
`
`lOa
`
`~ 13a
`
`Exhibit 2001
`IPR2017-00336
`Petitioner - Samsung Electronics Co., Ltd., et al.
`Patent Owner - Image Processing Technologies LLC
`1
`
`

`

`US 6,486,909 Bl
`Page 2
`
`01HER PUBLICATIONS
`
`Pierre-Francais 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, Mar.
`1997-W5 (40F), ISSN 0994-0758.
`Es Professionnels de Linformatique En Entreprise Maga(cid:173)
`zine, "Objectif Securite Des Reseaux", N° 24, Jan., 1997.
`Electroncique International Hebda, Dec. 5, 1996-N° 245,
`"Premier ... oeil", Francoise Gru svelet (with translation).
`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-
`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, Number 68, Mar. 1997, ISSN 1157-1151 (with
`translation).
`
`"Elecktronik Revue" ER, Eine Elsevier-Thomas-Publika(cid:173)
`tion, Jahrgang Mar. 8, 1997, NR.3, ISSN0939-1134.
`
`"Un Processor de Perception Visuelle", LehAUT pAR(cid:173)
`LEUR, 25F Des solutions electroniques pour taus, No 1856,
`Jan. 15, 1997 (with translation).
`
`"Realiser Un Decodeur Pour TV Numberique", Electron(cid:173)
`ique, Le Mensuel Des Ingenieurs De Conception, Number
`66, Jan. 1997.
`
`Groupe Revenu Fran«ais, Air & Cosmos Aviation Interna(cid:173)
`tional, "Un Calculateur De Perceoption Visuelle", Hebdo(cid:173)
`madaire, vendredi Dec. 6, 1996, 34 Annee, No 1590, 22F.
`
`* cited by examiner
`
`2
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 1 of 10
`
`US 6,486,909 Bl
`
`11,2
`11,17
`-----000-----
`
`~~,;\~1
`at,2J'h'jl cs~ I at7.2
`a
`TR'I ...
`-TR'2
`
`, \
`
`.------""~ ZH ( V.DI}
`
`lOa
`
`13a
`
`13
`
`S(PI)
`
`12
`
`II
`
`FIG.
`
`I.
`
`3
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 2 of 10
`
`US 6,486,909 Bl
`
`-
`1-J3A- -
`~~, S(PI)
`S(PI)
`I I
`I
`I
`12,
`I L _ _l
`I
`I
`I
`I HP BL
`I
`I
`I
`I
`19
`-f...,..
`I
`I
`I
`L.. '-----'------'---·'- -· .._ __ ...l-z·
`I
`'
`co
`I
`z-L ____
`
`r16
`
`- --15 - --- - - - - - - - - - -:
`''\
`... a
`15
`Ll
`I
`,
`l
`LO Ll5
`,
`3
`Cl
`,
`co 3
`,
`
`r20
`
`HP
`
`S(Pt)
`
`~
`
`SL
`sc
`HP
`
`F
`
`DP CO
`)'I , 3
`
`rl7
`
`18 4
`
`.
`.
`"4
`"
`
`SR
`
`I
`
`)'3 ' 3
`VI Dl
`
`v
`
`I
`I
`I
`I
`~-lla
`I
`I
`I
`I
`I
`I
`I
`3' I
`I
`
`FIG. 2.
`r----------------..,
`1..-
`I
`""
`v15a
`I S(PI)
`I
`
`15
`
`IPI-UI= AB
`
`13
`
`8,
`,
`
`20~ Ll
`
`.8
`
`8
`
`I
`AB
`I ~
`'8 AB >SE- DP=I
`I
`I
`ASS SE- DP=O
`I •
`I 1
`~I
`I
`
`,
`
`16-
`
`'
`
`3• l-
`co
`
`15e --~---.
`SE-1
`I
`N .---,
`~--..1
`J
`~
`15f ... "'--- LJ
`DP
`15' I
`DP= I - CO= Cl- U
`3,1
`DP=O-- CO=CI+U ~15c
`Cl I
`-----------
`I
`I ~ 05 co~ N
`15
`I
`N
`,3
`LO
`I
`co'
`I
`I
`I
`Jd_
`I
`LO = L I + PI-LI
`co
`I S(PI)
`I
`I
`LO
`\15d
`I
`L---------------~
`FIG. 3.
`
`15b
`
`DP
`
`co
`
`18)
`
`4
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 3 of 10
`
`US 6,486,909 Bl
`
`:
`
`~
`
`I Po,o
`I
`I
`I
`I
`
`d1,0 ......
`
`do,o, xo \ x1
`I DP, co " :::J\
`:I v
`I
`PI, I.,.... /
`
`... Xl4
`
`X2
`
`I
`
`XI5XI6
`p p
`d0,15,.
`p ~
`v
`
`P"-do,l
`P--dll
`I
`
`I
`
`I
`
`YO
`117)
`(
`Yl
`116)
`(
`
`lPI,2
`
`dJ,I6"'
`
`.r 21
`
`a b c ~M3
`d~f
`g h i
`
`S(PI) DP CO
`
`HP BL 18\~ ~ J
`
`I
`
`I
`
`rl\
`
`r27
`
`I
`
`I
`
`SL
`
`sc
`
`HP
`
`19
`
`rl6~
`
`I
`
`I
`
`7'
`
`Ps,s
`
`p
`p
`
`D--dl5,1 dJ6,15,
`~CI Cl
`D
`
`0 D
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`Yl5
`12)
`I
`(
`Yl6
`I
`:
`(II)
`SL
`p
`dl6,d
`F sc
`I
`16,16,
`v VL Dl co
`SR
`~----------- -- t--- -- :------ ___ I
`HP ...
`z ----- ------ ------------------------------
`FIG. 4.
`
`FIG. 5.
`
`FIG. 6.
`
`5
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 4 of 10
`
`US 6,486,909 Bl
`
`+I
`
`0
`
`0
`
`+I
`
`0
`
`~M3
`
`M9
`
`-I
`
`0
`
`0
`
`-I
`
`FIG. 7.
`
`FIG. 8.
`
`6
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 5 of 10
`
`US 6,486,909 Bl
`
`Lu
`
`FIG. 9.
`
`I z•
`----- -r-------:-----+-_[_ -:
`
`22a
`
`22
`
`I
`I
`I
`1zH
`I
`
`r -
`1
`I
`I
`I
`I
`I
`S(PI} I
`----1
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`L-----------------------~
`
`II
`
`.
`
`.r...._
`V"'
`
`I
`
`F
`
`:
`:
`SR I
`I
`v
`I
`VL I
`
`DL
`co
`
`z
`
`FIG. IQ
`
`7
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 6 of 10
`
`US 6,486,909 Bl
`
`F
`l z
`
`SR
`
`v
`
`VL
`
`Dl
`
`co
`
`z
`
`24-...,
`
`VI
`r-
`
`V2
`
`V3
`
`r30
`I
`
`I
`
`31
`
`I
`
`V4
`
`~
`
`1....---J.-.....L,.l 3 3
`
`SSR
`
`sv
`
`SDI
`
`34
`
`I
`
`f
`
`x.y(m)
`
`~~...~....--~-.,.r __ 35
`
`sco
`
`ZH
`
`V5
`
`HP
`SL
`sc
`
`x.(m)l
`
`~29
`
`y(m)l
`i/37
`
`FIG. II.
`
`8
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 7 of 10
`
`US 6,486,909 Bl
`
`y
`
`ld ~9x-----'------IT.~~f:-"':---t-­
`
`yM...y,.r,.c,.~~
`
`lc~f-----r-~~~~P'-1"-
`
`40
`
`Ia
`
`xM
`
`lb
`
`X
`
`FIG. 12.
`
`FIG. 13.
`
`v
`
`y
`
`Cn
`
`X
`
`FIG. 14.
`
`9
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 8 of 10
`
`US 6,486,909 Bl
`
`0
`
`3
`
`Bd
`
`Px
`
`Po/
`
`FIG. 168.
`
`FIG. /6C.
`
`' '
`
`-- ' ' '
`
`' ',
`'
`
`Bd
`
`VR-{J
`
`X
`
`FIG. 16A.
`
`10
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 9 of 10
`
`US 6,486,909 Bl
`
`13
`
`s
`
`II
`
`42
`
`ZH
`
`....---.....______., lOb
`
`FIG. 17.
`
`ZH
`
`NL
`
`45\
`
`13)
`
`s
`
`\..II
`
`SR _j
`44
`
`to,
`
`46
`
`_......._
`
`Cy
`
`FIG. 18.
`
`DG
`
`M
`
`~
`DG®
`
`FIG. 19.
`
`~
`
`SF
`
`ex
`
`11
`
`

`

`U.S. Patent
`
`Nov. 26, 2002
`
`Sheet 10 of 10
`
`US 6,486,909 Bl
`
`AA
`
`FIG. 20.
`
`FIG. 2l
`
`r 13A
`
`;J_ 5
`6
`4
`
`3
`
`2
`
`I
`
`FIG. 22.
`
`12
`
`

`

`US 6,486,909 Bl
`
`1
`IMAGE PROCESSING APPARATUS AND
`METHOD
`
`The purpose of this invention is a process and device for
`identifying and localizing an area in relative movement in a
`scene and for determining the speed and oriented direction
`of this relative movement, in real time.
`Relative movement means a movement of said area
`(which may be composed of an "object" in the broadest
`sense of the term including a living being or a portion of a
`living being, for example a hand) in an approximately
`motionless environment, or more or less complete immo(cid:173)
`bility of said area (or "object") in an environment that is at
`least partially in movement.
`The invention relates to the processing of a digital video
`output signal from an observation system composed of an
`optical imput system or objective capable of forming an
`image of the observed scene, and by an optoelectronic
`conversion system or sensor capable of converting said
`image that it receives into a digital output signal.
`In general, the observation system is composed of a
`video camera or camescope that observes the scene to be
`monitored (said digital output signal then being composed of
`the digital video signal output by a camera with a digital
`output or of the output of an analog/digital converter, the
`input of which is connected to the output of a camera
`outputting an analog video signal.
`The observation system may also be composed of the
`objective of an optical instrument (binoculars, sighting
`refracting instrument, view-finder), from which at least a
`portion of the outgoing light beam is sampled and by a
`photoelectronic sensor, for example of the CCD or CMOS
`type, with the normal associated electronic system, sensor
`receiving the image formed by said portion of the light beam
`and converting it through the associated electronic system
`into a digital video output signal.
`The invention consists mainly of processing the digital
`video output signal from an observation system, particularly
`a video camera, with a digital output to determine signals
`signaling the existence and localization of an area in relative
`movement in said scene, and the speed and oriented direc(cid:173)
`tion of the displacement if said area is actually moving in
`said scene relatively to an approximately motionless
`environment, in real time.
`The best system yet developed for identifying and local(cid:173)
`izing an object in relative movement and for determining its
`speed and oriented direction of displacement is animal or
`human sight, for example a hunter in his hide localizing the
`displacement of an animal, and the direction and speed of
`this displacement.
`Prior art surveillance devices like artificial retinas, either
`analog (Giacomo Indiveri et al, in Proceedings of MicroN(cid:173)
`euro'96 pp 15 to 22), or digital (Pierre-Fran«ois Ruedi in
`Proceedings of MicroNeuro'96 pp 23 to 29), have been
`proposed, but the first article deals with detectors and analog 55
`units with complex structures, and the second article deals
`with means of identifying the edges of an object;
`furthermore, very fast and high capacity memories are used
`in the devices described in order to operate in real time, and
`limited information is obtained about moving areas or 60
`objects.
`Thus the suggestion was made of memorizing a frame
`output signal from a video camera, or similar instrument,
`composed of a sequence of data relative to pixels represen(cid:173)
`tative of the scene observed by the camera at time t0 in a first 65
`two-dimensional memory, and then the video signal for the
`next corresponding frame representing said scene at time t1 ,
`
`2
`in a second two-dimensional memory. If an object has
`moved between t0 and t1 , on the one hand, the distance d by
`which the object has moved in the scene between t1 and t0
`and, on the other hand, the time T=t1-t0 between the
`5 beginnings of two successive corresponding frames relative
`to the same pixels are determined. The displacement speed
`is then equal to d/T. This type of system requires a very large
`total memory capacity if it is required to obtain precise speed
`and oriented direction indications characterizing the dis-
`10 placement. Furthermore, there is some delay in obtaining the
`speed and displacement direction indications; this inform a(cid:173)
`tion is not available until time t1 + R, where R is the time
`necessary for the calculations for the period t0 -t;.These two
`disadvantages (the need for a large memory capacity and the
`15 delay in obtaining the required information) limit applica(cid:173)
`tions of this type of system.
`Furthermore, French patent No. 2.611.063, of which one
`of the inventors (Mr. Patrick Pirim) is the inventor of the
`present invention, describes a process and a device for real
`20 time processing of a sequenced data flow, composed in
`particular of the output signal from a camescope, in order to
`perform data compression. According to this prior patent,
`the histogram of signal levels is formed using a classification
`law for a first sequence, the representative Gauss function
`25 associated with this histogram is memorized and the maxi(cid:173)
`mum and minimum levels are extracted from it, the levels of
`the next sequence or second sequence are compared with
`said signal levels for the first sequence memorized with a
`constant time constant identical for each pixel, a binary
`30 classification signal is generated that characterizes the next
`said sequence with reference to the classification law, an
`auxiliary signal is generated from this binary signal repre(cid:173)
`sentative of the duration and position of a range of signifi(cid:173)
`cant values, and finally said auxiliary signal is used to
`35 generate a signal localizing the range with the longest
`duration, called the dominant range, and these operations are
`repeated for subsequent sequences of the sequenced signal.
`This process and this device of classification enable data
`compression, keeping only interesting parameters in the
`40 processed flow of sequenced data. In particular, this process
`is capable of processing a digital video signal representative
`of a video image in order to extract and localize at least one
`characteristic of at least one area in said image. It is thus
`possible to classify brightness and/or chrominance levels of
`45 the signal and to characterize and localize an object in the
`image.
`U.S. Pat. No. 5,488,430 detects and estimates a displace(cid:173)
`ment by determining horizontal and vertical changes in the
`image of the observed area separately. Difference signals are
`50 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, firstly by
`carrying out the EXCLUSIVE OR logical function on
`horizontal/vertical difference signals and frame difference
`signals, and secondly by using a ratio of the sums of
`horizontal/vertical signals and the sums of frame difference
`signals with respect to a Kx3 window. In this U.S. Pat. No.
`5,488,430, calculated values of the image along two
`orthogonal horizontal and vertical directions are used with
`an identical repetitive difference K in these two orthogonal
`directions, this difference K being defined as a function of
`the displacement speeds that are to be determined. The
`device according to this US patent determines the direction
`of movements along each of the two orthogonal directions
`by applying a set of calculation operations indicated in
`columns 12 (at the beginning and end) and 13 (at the
`beginning) to the difference signals, which requires very
`
`13
`
`

`

`US 6,486,909 Bl
`
`20
`
`3
`complex (and therefore difficult to execute) electronic com(cid:173)
`puting units performing particularly division, multiplication
`and summation; furthermore, additional complex computing
`units are necessary to obtain the speed and oriented direction
`of displacement (extraction of square root to obtain the 5
`amplitude of the speed and calculation of the arc tan function
`to obtain the oriented direction), starting from projections on
`the two horizontal and vertical axes. Finally U.S. Pat. No.
`5,488,430 does not include any means of smoothing pixel
`values by means of a time constant, variable for each pixel, 10
`in order to compensate for excessively fast variations of
`these values.
`On the contrary, the process according to the invention is
`embodied by using a digital type of device, object of the
`invention, which has a relatively simple structure and a 15
`relatively small memory capacity, and by which the required
`information can be obtained quickly with a wide variety of
`results and applications (corresponding to a complete half(cid:173)
`image for interlaced frames or a complete image, depending
`on the application).
`An article by Alberto Tomita Sr. and Rokuya Ishii,
`entitled "Hand Shape Extraction from a Sequence of Digi(cid:173)
`tized Gray-Scale Images" in Institute of Electrical and
`Electronics Engineers, vol. 3, 1994, p 1925-1930, imple(cid:173)
`ments a movement detection by subtraction between sue- 25
`cessive images followed by the formation of histograms
`based on 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 on a gray scale inherent to the human hand.
`It does not include any means of forming histograms of the 30
`plane coordinates. The sole purpose of the authors of this
`article is to detect the displacements of a human hand, for
`example in order to replace the normal mouse by a hand, the
`displacements of which are identified, for inputting data into
`a computer.
`On the contrary, the present invention is not limited to
`detecting the displacement of a hand, but is capable of
`detecting the relative displacement of any object (in the
`widest sense of the term) in a scene, and does not use
`histograms based on the gray values of a hand, but rather the 40
`histograms of some particular digital variables representa(cid:173)
`tive of the displacement (if any) and histograms of plane
`coordinates.
`According to this invention:
`a digital video output signal from an observation system 45
`is processed, this signal being composed of a sequence
`of frames (corresponding to a half-image in the case of
`two interlaced frames per image or to a complete image
`in the case of a single frame per image) in the known
`manner, each consisting of a given number of succes- 50
`sive lines, and a given number of pixels or image points
`in each of these lines,
`in order to obtain, using a relatively small memory
`capacity, signals capable of indicating if there is an area
`in relative movement in the observed scene and, if so, 55
`to specify the localization, and speed and oriented
`direction of said area if it is actually moving with
`respect to its environment,
`by generating two digital signals, one characteristic of the
`significant variation or non-variation of the pixel 60
`signal, for the same pixel location, between two suc(cid:173)
`cessive corresponding frames, and the other character(cid:173)
`istic of the amplitude of this variation, if any, and
`performing a matrix distribution of these two signals
`for the pixels in a portion of a frame at a same instant. 65
`It is a first object of the invention to provide a process
`operating in real time for identifying and localizing an area
`
`35
`
`4
`in relative movement in a scene observed by an observation
`system with an output constituted by a digital video signal
`of the type comprising a succession of corresponding
`frames, each composed of a succession of lines, each
`composed of a succession of pixels, and for determining the
`speed and oriented direction of the displacement, said pro(cid:173)
`cess being characterized in that it consists in carrying out the
`following sequence of operations on the digital video output
`signal:
`a smoothing processing on said digital video output signal
`using a digital time constant, the numerical value of
`which may be modified independently for each pixel of
`said output signal,
`a memorization, on the one hand, of a frame of said output
`signal after smoothing and, on the other hand, of the
`smoothing time constant associated with said frame,
`a temporal processing for each pixel position, consisting
`in determining firstly the existence, and secondly the
`amplitude of a significant variation in the amplitude of
`the pixel signal between the current frame and the
`immediately preceding smoothed and memorized
`frame, and generating two digital signals, the first
`signal being a binary, or single bit, signal with two
`possible values, one of which represents the presence
`and the other represents the absence of a significant
`variation between two successive frames, the value of
`said binary signal modifying the memorized value of
`said time constant in order to reduce it if said signal
`represents a significant variation and in order to
`increase it if said signal does not represent such a
`variation, the reduction or increase being done in a
`quantified manner, whereas the second digital signal,
`i.e. the amplitude signal, is a multibit signal with a
`limited number of bits quantifying the amplitude of this
`variation; and
`a spatial processing consisting of the following steps for
`each frame of the digital video input signal:
`distributing only the values of a fraction of the pixels in
`a frame at a given observation instant (a fraction
`which is scanned across said matrix throughout the
`duration of the frame) firstly of said binary signal
`and secondly of said digital amplitude signal, into a
`matrix with a number of rows and columns that is
`small compared with the number of lines and the
`number of pixels per line in the video signal,
`respectively, in order to characterize the values of the
`pixels,
`determining in this double instantaneous matrix
`representation, a particular area in which said binary
`signal has the value sought for, representing the
`presence or absence of a significant variation, and
`said digital amplitude signal varies, or does not vary,
`by a significant value for adjacent pixels in the
`matrix along an oriented direction starting from an
`origin pixel, within the same portion of the frame and
`therefore at the same observation instant, and
`generating signals representing the existence and local(cid:173)
`ization of the area in relative displacement and the
`relative inter-frame speed and the oriented direction
`of this displacement, if any, relative to its
`environment, inferred from the instantaneous matrix
`distribution of these two binary and amplitude digital
`signals.
`Preferably, the process according to the invention is
`characterized in that it also consists of:
`forming firstly histograms of the signal values distributed
`in matrices, and secondly histograms of the inclinations
`of two coordinate axes, with variable slope, in a plane,
`
`14
`
`

`

`US 6,486,909 Bl
`
`5
`identifying a domain in which there is a significant
`variation of the processed values in each histogram
`formed, and
`for each identified domain, deducing whether or not there
`is an area in relative movement, and if so its 5
`localization, speed and oriented direction.
`In specific embodiments:
`said matrix is a square matrix with the same odd number
`of rows and columns (21+1), and nested matrices con(cid:173)
`taining 3x3, 5x5, 7x7, ... (21+1)x(21+1) elements, 10
`centered on the center of this square matrix, are con(cid:173)
`sidered in order to determine the smallest nested matrix
`in which said digital signal varies along an oriented
`direction starting from said center, the value of said
`binary signal showing that the threshold limit along this 15
`direction has been exceeded,
`said matrix is a hexagonal matrix, and nested hexagonal
`matrices of increasing size, centered on the center of
`this hexagonal matrix, are considered, in order to
`determine the smallest nested matrix in which said 20
`digital signal varies along an oriented direction,
`said matrix is an inverted L matrix with a single row and
`a single column, and nested matrices containing 3x3
`pixels, 5x5 pixels, 7x7 pixels, ... (21+1)x(21+1) pixels 25
`are considered for the single row and the single column,
`in order to determine the smallest matrix in which the
`signal varies along an oriented direction, namely the
`line with the steepest slope and constant quantification.
`Advantageously, said time constant is of the form 2!', 30
`where p is a number less than 16, and which can then be
`expressed in not more than 4 bits, the time constant being
`reduced or increased by subtracting or adding one unit to p.
`In this case, if it is required, successive decreasing por(cid:173)
`tions of complete frames are considered using the Mallat 35
`time-scale algorithm and the largest of these portions, which
`gives displacement, speed and orientation indications com(cid:173)
`patible with the value of p, is selected.
`Another object of the invention is a device operating in
`real time for identifying and localizing an area in relative 40
`movement in a scene observed by an observation system
`with an output constituted by a digital video signal of the
`type comprising a succession of corresponding frames,
`successive lines in each corresponding frame and successive
`pixels in each line, and for determining the speed and 45
`oriented direction of the displacement, by using the process
`described above, said device receiving said video output
`signal as input and being characterized in that it comprises
`in combination:
`means for smoothing said digital video output signal 50
`making use of a digital time constant, the numerical
`value of which may be modified independently for each
`of said output signal pixels;
`means for memorizing firstly a frame of said output signal
`after smoothing and secondly the smoothing time con(cid:173)
`stant associated with said frame,
`a temporal processing unit to analyze the variations with
`time of the amplitude of the pixel signal, for the same
`pixel position, between the current frame and the
`immediately preceding smoothed and memorized
`frame of said digital signal, said unit comprising a
`memory capable of receiving, storing and retrieving
`information about the corresponding previous
`smoothed frame, together with means of comparison to
`determine if the absolute value of the difference, 65
`between the current pixel signal and a representative
`value of the pixel signal for the same pixel position in
`
`6
`the previous frame stored in said memory, exceeds or
`does not exceed a threshold, for each position of the
`pixel in the input video signal frame, by generating a
`binary, or single bit, signal with two values, one of
`these two values showing that the threshold is exceeded
`and the other showing that it is not exceeded, and
`computing means capable of determining a multibit
`digital amplitude signal with a small number of bits, the
`value of which depends on the amplitude of the varia-
`tion in the value of the same pixel between the current
`frame and the immediately preceding, smoothed and
`memorized, frame of the digital video signal; and
`a spatial processing unit, into which the outputs from said
`successive binary and digital amplitude signals for the
`pixels in a given frame produced by the temporal
`processing unit are input, said spatial processing unit
`comprising means for characterizing the amplitude
`values of the pixels, these means distributing only said
`binary and digital amplitude signals relative to the same
`instant, i.e. to a single frame, into a matrix with fewer
`rows and columns than the number of lines and the
`number of pixels per line respectively in a frame of said
`digital video signal, the frame being scanned across
`said matrix throughout the duration of a frame, spotting
`means for determining an area of pixels within said
`matrix in which, at this instant, the binary signal has the
`searched value, and means of determining an area of
`pixels in said matrix, into which, at the same instant,
`the digital amplitude signal for adjacent pixels varies
`by a significant quantity, and means which, in response
`to the indications from the two preceding means, gen-
`erate signals representing this area of pixels and there(cid:173)
`fore the existence and localization of an area in relative
`movement within the observed scene and the relative
`inter-frame speed and oriented direction of this area
`when it actually moves relative to its environment.
`Preferably, the spatial processing unit will also include an
`output delivering a delayed digital video signal consisting of
`the input digital video signal with a delay equal to the
`duration of the rows of a matrix minus the duration of a row,
`in order to supply an output signal contemporary with the
`analysis of the matrix in said temporal processing unit.
`Preferably, the spatial processing unit of the device
`according to the invention, includes delay means in cascade,
`each of which imposes a delay equal to the time difference
`between the beginning of two successive lines, and delay
`means in cascade for each line, each importing a delay equal
`to the time difference between two successive pixels in a
`line, the outputs from all registers and the input to the first
`registers on each line delivering at a given instant the values
`of said binary signal and said digital amplitude signal at the
`same instant, to said identification means.
`Advantageously, the device according to the invention
`also comprises means for forming histograms of the output
`55 values from said spatial processing unit, and histograms of
`the inclinations of two, variable slope, coordinate axes
`within a plane, means for identifying a domain, in each
`histogram, in which there is a significant variation in the
`processed value, in order to validate this domain at their
`60 output, and to deduce, for all histograms, output signals that
`identify and localize an area of relative movement in the
`observed scene, if any, and the speed and oriented direction
`of this movement if said area is effectively moving with
`respect to its environment.
`If it is required to detect the movement of an object in an
`approximately motionless environment, it is necessary to
`determine the part of the matrix in which the value of the
`
`15
`
`

`

`US 6,486,909 Bl
`
`10
`
`7
`binary signal shows that the limit has been exceeded and at
`the same time the digital amplitude signal varies by a
`significant value between adjacent pixels in a frame.
`On the contrary, if it is required to detect a motionless
`object in an environment that is effectively in motion, it is 5
`necessary to determine the part of the matrix in which the
`value of the binary signal shows that the limit has not been
`exceeded and at the same time the digital amplitude signal
`does not vary between adjacent pixels in a frame.
`Preferably in the device for identifying, localizing and
`determining the speed and oriented direction of displace(cid:173)
`ment of an area in relative movement
`in a scene, embodying the above mentioned process: said
`smoothing means include an input receiving said digi-
`tal video signal and derive, for each successive pixel in 15
`a frame of said video signal, a smoothed signal in
`which the temporal variations of the input digital video
`signal are reduced by using a threshold