United States Patent [191
`Brady et al.
`
`[54] METHOD AND APPARATUS FOR MACHINE
`VISION CLASSIFICATION AND TRACKING
`
`[75] Inventors: Mark J. Brady. Cottage Grove; Darin
`G. Cemy. St. Paul; Michelle C.
`Granholm. Woodbury; Belayneh W.
`Million. St. Paul. all of Minn.
`
`[73] Assignee: Minnesota Mining and
`Manufacturing Company. St. Paul.
`Minn.
`
`[21] Appl. No.: 429,943
`[22] Filed:
`Apr. 27, 1995
`
`Related US. Application Data
`
`[63] Continuation-impart of Ser. No. 163,820, Dec. 8, 1993, Pat.
`No. 5,434,927.
`
`[51] Int. Cl.6 ............................ .. G06K 9/00; G06K 9/48;
`H04N 9/47; G08G 1/054
`[52] US. Cl. ........................ .. 382/103; 382/104; 382/199;
`348/148; 395/905; 340/937
`[58] Field of Search ................................... .. 382/103. 104.
`382/160. 199; 348/148; 395/905. 21; 340/937
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,490,851 12/1984 Gerhart et a]. .......................... .. 382/43
`4,709,264 11/1987 Tamura et al. ..
`358/93
`4,839,648
`6/1989 Beucher et a1. ...... ..
`. 340/933
`4,847,772
`7/1989 Michalopoulos et a1
`. 364/436
`4,881,270 11/1989 Knecht et a1. .... ..
`382/17
`4,942,533
`7/1990 Kakmami et a].
`5,046,111
`911991 Cox et al. ..... ..
`5103305 4/1992 Wanna‘?
`541L232 5/1992 Tsmfefull """ "
`222mm et a1‘
`....................................... ..
`(List continued on next page‘)
`
`'
`
`'
`
`. 364/449
`
`382/8
`- 353/105
`354mm
`
`,
`
`FOREIGN PATENT DOCUMENTS
`
`0454 166 10/1991 European Pat. O?. ....... .. G086 l/04
`WO 93/19441
`9/1993 WIPO .......................... .. U086 U017
`
`Hlllllllllllllllllllllllllllllulllllllllllllllllllllllllllllllllllll
`
`[11] Patent Number:
`[45] Date of Patent:
`
`5,761,326
`Jun. 2, 1998
`
`OTHER PUBLICATIONS
`
`Gilbert et a1; “Dynamic Tra?ic Information from Remote
`Video Monitors”: Environmental Research Institute of
`Michigan; Oct.. 1991. pp. 213-231.
`Zielke et al.; “Intensity and Edge-Based Symmetry Detec
`tion Applied to Car-Following"; Lecture Notes in Computer
`Science. vol. 588; G. Sandini (ed.); Computer Vision
`ECCV’92.
`Michalopoulos; “Vehicle Detection Video Through Image
`Processing: The Autoscope System”; IEEE Transactions on
`Vehicular Technology; vol. 40. No. 1, Feb. 1991.
`Ali et al.; “Alternative Practical Methods for Moving Object
`Detection”; International Conference on Image Processing
`and Its Applications (Conf. Publ No. 354); 1992.
`Naito et al.; “A Car Detection System Using Neural Network
`for Image Processing”; OMRON Corporation. Japan.
`AUTOSCOPE—Advanced Wide-Area Vehicle Detection
`Technology from Econolite Control Products. Inc.
`Brochure entitled AUTOSCOPE-2003 Video Vehicle
`Detection System from Econolite Ceontrol Products. Inc.
`
`Primary Examiner-Andrew W. Johns
`Assistant Examiner—Monica S. Davis
`Attome); Agent, or Finn-Stephen W. Bucln'ngham
`[57]
`ABSTRACT
`
`A method and apparatus for classi?cation and tracking
`objects in three-dimensional space is described. A machine
`vision system acquires images from roadway scenes and
`processes the images by analyzing the intensities of edge
`elements within the image. The system then applies fuzzy
`set theory to the location and angles of each pixel after the
`pixel intensities have been characterized by vectors. Aneural
`network interprets the data created by the fuzzy set operators
`and classi?es objects within the roadway scene. The system
`can also track objects within the roadway scene. such as
`vehicles. by forecasting potential track regions and then
`calculating match Scores for web potential track region
`based on how well the edge elements from the target track
`regions match those from the source region as weighted by
`the extent the edge elements have moved.
`
`17 Claims, 14 Drawing Sheets
`
`2
`
`moon VJEW
`moms-non
`
`VIDEO lMAGE /12
`PREPFIOCESSOR
`
`VEHICLE
`]
`‘ IDENTIFICATION &
`
`ELASSIFICATION
`24/
`
`TRAFFIC
`INTERPFIETER
`
`Page 1 of 25
`
`SAMSUNG EXHIBIT 1007
`Samsung v. Image Processing Techs.
`
`

`

`5,761,326
`Page 2
`
`US. PATENT DOCUMENTS
`
`5,263,120 11/1993 Bickel ..................................... .. 395/11
`5,280,566
`1/1994 Nakamura
`395/51
`5,283,575
`2/1994 Kao et a1. ............................. .. 340/990
`
`5,296,852
`5,335,297
`5,432,712
`5,434,927
`5,555,312
`
`3/1994 Rathi .... ..
`8/1994 Pullen
`7/1995 Chan _______ ._
`7/1995 Brady et a1. ..
`9/1996 Shima e1 a1v ..
`
`. 340/933
`. 382/103
`_ 332/199
`. 382/104
`. ................. .. 382/104
`
`SAMSUNG EXHIBIT 1007
`Page 2 of 25
`
`

`

`U.S. Patent
`
`Jun. 2, 1998
`
`Sheet 1 of 14
`
`5,761,326
`
`10
`
`SAMSUNG EXHIBIT 1007
`Page 3 of 25
`
`

`

`U.S. Patent
`
`Jun. 2, 1998
`
`Sheet 2 of 14
`
`5,761,326
`
`DIGITAL VIEW
`ACQUISTION
`
`I
`
`VIDEO IMAGE
`PREPROCESSOR
`
`/-12
`
`I
`
`I
`
`VEHICLE
`IDENTIFICATION &
`CLASSIFICATION
`24/
`
`DATA
`
`Fig.
`2
`
`VEHICLE
`TRACKING
`
`{/22
`
`I
`I
`
`26
`TRAFFIC /
`INTERPRETER
`
`CONTROL
`
`ALARM
`
`2
`
`m
`2
`
`29
`
`SAMSUNG EXHIBIT 1007
`Page 4 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 3 of 14
`
`5,761,326
`
`IMAGE
`ACQUISITION &
`STABILIZATION
`
`EDGEL
`DEFINITION
`
`K40
`
`44
`
`i/sv
`L43
`I
`
`GEOMETRIC
`TRANSFORM /
`45
`
`TO VEHICLE
`TRACKING
`
`REGION
`SELECTION
`
`/46
`
`1
`REGION
`PRIORITY
`
`/47
`
`7
`
`VECTORIZATION / 51
`
`I
`
`VEHICLE
`CLASSIFICATION
`
`52
`
`53
`/
`VEHICLE
`LEARNING
`
`I
`
`ICON
`‘
`ASSIGNMENT
`
`TO VEHICLE
`TRACKING
`
`55
`
`Fig. 3 I
`
`SAMSUNG EXHIBIT 1007
`Page 5 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 4 0f 14
`
`5,761,326
`
`SAMSUNG EXHIBIT 1007
`Page 6 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 5 of 14
`
`5,761,326
`
`
`
`SAMSUNG EXHIBIT 1007
`
`Page 7 of 25
`
`SAMSUNG EXHIBIT 1007
`Page 7 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 6 0f 14
`
`5,761,326
`
`1 0
`
`II
`
`_ l O 1 O
`
`3'6
`
`0, (DEGREES)
`
`54/152
`
`T
`180
`
`ig. 6A
`
`66
`
`I
`18
`20
`
`Q, (DEGREES)
`
`Fig. 6B
`
`SAMSUNG EXHIBIT 1007
`Page 8 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 7 of 14
`
`5,761,326
`
`SAMSUNG EXHIBIT 1007
`Page 9 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 8 0f 14
`
`5,761,326
`
`\ 208
`
`\ 202
`
`SAMSUNG EXHIBIT 1007
`Page 10 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 9 of 14
`
`5,761,326
`
`250
`
`0-1 8
`1 9-36
`37-54
`55-72
`73-90
`91 -1 08
`1 09-1 26
`1 27-1 44
`1 45-1 62
`1 63-1 80
`
`262
`
`\— 270
`
`I
`260
`
`Fig. 8
`
`SAMSUNG EXHIBIT 1007
`Page 11 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 10 0f 14
`
`5,761,326
`
`/ w._o_zw>>>wz +
`
`@520 $3222 A n
`
`
`
`zmomwzék o??zowo + m m
`mm
`
`\ PL: R /3
`4 mm 4 E S
`
`T 8
`
`5 V@ a
`s ww?o s w w
`GE \8 MR M C
`V IE E
`E
`E H H M N
`S H E E mm 0 T O VIAE 0.6 Am wP
`N L M E U E A T
`nm N MR Rm '
`
`4 Hm“ 8 w
`
`,w
`
`,
`
`_ o o o. u E \1 MY% Mmmm m0.
`
`
`_ m6 'TR ' mAAN FV
`_ 2 F ERH R_
`
`
`s. m 1 s
`
` T R _ “w \mnbs \NNEWE If 0 0 u m H m cGN
`
`
`
`...... ................. i"
`
`
`
`
`
`-iw ....... ...... i... 9/ <\
`
`/92
`
`TRAFFIC
`‘NTERPRETER
`
`llllmu,
`405.200
`
`<._.<Q ,
`
`3 9
`
`L95
`§m5< 4
`
`Fig. 10
`
`SAMSUNG EXHIBIT 1007
`Page 12 of 25
`
`

`

`U.S. Patent
`
`Jun. 2, 1998
`
`Sheet 11 of 14
`
`5,761,326
`
`CAMERAS
`
`210N
`
`212 COMMERCIAL
`VIDEO
`
`/214 B
`CO-AX
`210C\u':
`//
`2108M 216/2 MICROWAVE
`210A
`\D:
`FIBER OPTIC \218 lr-Fl
`260
`
`220
`
`CENTRAL
`CONTROL
`
`250
`
`WORKSTATION
`
`VIDEO
`SWITCHER
`I
`‘CONTROL
`
`\240A
`\24oB
`\240O
`
`\240N
`
`IMAGE PROCESSORS
`
`Fig. 12
`
`SAMSUNG EXHIBIT 1007
`Page 13 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 12 0f 14
`
`5,761,326
`
`310
`
`300/
`
`i
`340
`
`'
`
`l
`l
`|
`i
`
`\ /g‘
`
`Alarm Noti?cation
`3
`Flea
`r-end collision
`co ision has occurred in the site
`by camera #3.
`
`__ Swt hioSi 7
`a E
`
`J
`350/ I
`36,52
`360
`Fig. 14
`
`SAMSUNG EXHIBIT 1007
`Page 14 of 25
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 13 of 14
`
`5,761,326
`
`
`
`X_m._.<_29‘04
`
`EDP/3355091
`
`9.3mm
`
`x_m._.<_>_
`
`EOE/335509».
`
`V;
`
`HszOmmmamv
`
`Imow
`
`m;
`
`956m
`
`xEEs.2955529.0..553295..
`
`5:332:02523.230252.5.2302
`
`
`
`
`9.3062.5282m52.522020$232309m55%m5532mx_E<s_
`
`
`zOfioéEDmoz.zo¢o<Em3m
`
`
`x_E.<s_m;o;xEEs.9:.
`
`8v
`
` vmvé52.52302um5:332:02
`
`
`xEE:mayxEEs.
`
`w?
`
`
`
`vmvX_m,_.<_>_
`
`EOF<43§DOO<
`
`Ne.
`
`mm<30w
`
`._.OOm_
`
`#3..
`
`>5
`
`
`
`9%AVnmgomvv‘mAumvxm5:332:02
`
`33.uE
`
`x_m._.<s_
`
`X_m._.<_>_
`
`mO._.<.5_>_DOO<
`ZO_._.<O_.E_H.5_>_
`
`\‘smmv
`
`SAMSUNG EXHIBIT 1007
`
`Page 15 of 25
`
`
`
`
`
` m.m.vowNOVm00%aFzmmmsavEmaommmamvhzmmmaov
`
`6.98.8
`
`SAMSUNG EXHIBIT 1007
`Page 15 of 25
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jun. 2, 1998
`
`Sheet 14 of 14
`
`5,761,326
`
`
`
`XEEQE04.04
`
`mOHSDEDOO<
`
`
`
`x_m.r<_2Q<O._
`
`EOH<AD§DOO<
`
`om
`
`03V
`
`X_m._.<_>_
`
`EOFSDEDOO<
`
`9.3mm
`
`x_m._.<_>_
`
`EOHSDEDOO/x
`
`NE“
`
`0xmO._.<.5_>500<AEmx_m._.<s_
`
`X_m._.<2
`
`ZO_._.O<m._.mDm
`
`EOHSDEDOO,‘
`
`m._.3.._Omm<
`
`m3._<>
`
`X_m._.<_2
`
`EOFSDEDOO<
`
`Eu
`m
`
`v x
`
`m-
`A
`
`.¢
`
`o
`
`9.3566
`>35Ema
`gemOFSDEDOO<
`
`x_m._.<_>_
`
`mmv
`
`
`
`S.EOHSDEDOO<
`
`SAMSUNG EXHIBIT 1007
`
`Page 16 of 25
`
`_.
`
`AU
`m
`
`1m-9.3mmEmu
`
`m0h<432300<
`
`x_m._.<_2
`
`vmv
`
`x_m._.<s_
`
`ZO_._.<O_._n=._H_DS_
`
`
`
`No.32.xw<§mmN
`
`xmé
`
`va
`
`ZOF0<mHmDm
`
`x_m._.<_>_
`
`mm
`
`NEOFSDEDOO/x
`
`x_m._.<_2
`
`SAMSUNG EXHIBIT 1007
`Page 16 of 25
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`1
`METHOD AND APPARATUS FOR MACHINE
`VISION CLASSIFICATION AND TRACKING
`
`5.761.326
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation-in-part of U.S. appli
`cation Ser. N o. 08/ 163.820. ?led Dec. 8. 1993. now U.S. Pat.
`No. 5.434.927.
`
`FIELD OF THE INVENTION
`
`This invention relates generally to systems used for tra?ic
`detection. monitoring. management. and vehicle classi?ca
`tion and tracking. In particular. the invention is directed to
`a method and apparatus for classifying and tracking objects
`in images provided by real-time video from machine vision.
`
`10
`
`2
`tion Video Through Image Processing: The Autoscope
`System. IEEE Transactions on Vehicular Technology. Vol.
`40. No. 1. February 1991. The Michalopoulos et al. patent
`discloses a video detection system including a video camera
`for providing a video image of the tra?ic scene. means for
`selecting a portion of the image for processing. and proces
`sor means for processing the selected portion of the image.
`The Michalopoulos et al. system can detect traf?c in
`multiple locations. as speci?ed by the user. using interactive
`graphics. The user manually selects detection lines. which
`consist of a column of pixels. within the image to detect
`vehicles as they cross the detection lines. While the manual
`placement of the detection lines within the image obviates
`the expense of placing inductance loops in the pavement as
`well as provides ?exibility in detection placement. the
`Michalopoulos et al. system still roughly emulates the
`function of point detection systems. The system still detects
`vehicles at roughly ?xed locations and derives tra?ic param
`eters by induction. using mathematical and statistical for
`mulas. For example. the system classi?es a vehicle based on
`its length and calculates velocity of a vehicle based on the
`known distance between detection locations divided by
`average travel time. M61’. if a vehicle crosses through an
`area within the image where the user has not placed a
`detection line. the system will not detect the vehicle. Thus.
`the system does not automatically detect all vehicles within
`the image.
`Before a machine vision system can perform any traffic
`management capabilities. the system must be able to detect
`vehicles within the video images. The Michalopoulos et al.
`system detects vehicles by analyzing the energy. intensity or
`re?ectivity of every pixel in the prede?ned detection lines
`and comparing an instantaneous image at every pixel with a
`threshold derived from analysis of the background scene
`without the presence of any vehicles.
`Other systems have utilized edge detection for detecting
`vehicles. These systems often perform “blob analysis" on
`the raw image. which constitutes a grouping of elements.
`The goal of such an analysis is determining which pixels
`belong together. based on pixel location. intensity and
`previous grouping decisions. The basic process may be
`described as region growing. First. the system picks a center
`pixel that it determines belongs in a grouping. Then. the
`system looks to neighboring pixels and determines whether
`to include the pixels in the grouping. This process continues
`for each included pixel. Blob detectors of this type have run
`into di?iculties because all the decisions are interdependent.
`Once the system has made
`decisions to include or
`exclude pixels. subsequent decisions will be based on the
`decisions already made. Thus. once the system makes an
`incorrect decision. future decisions are often also incorrect.
`This series of incorrect decision making may lead to failure
`of proper convergence. The same is true of edge detection
`based systems which rely on sequential decision processes.
`A further desirable capability of machine vision systems
`is the capability to track the detected vehicles. Systems that
`track vehicles usually share some common characteristics.
`First. the system must identify the starting point of the track.
`The system may do this by detecting the vehicle by com
`paring an input image with a background image andjudging
`objects having an area within a predetermined range as
`vehicles. Other systems perform motion detection to initiate
`the tracking sequence. Those systems using motion alone to
`initiate tracking are prone to errors because they must set
`some baseline amount of motion to initiate tracking. Thus.
`it is always possible for systems to fail to track slow moving
`or stalled vehicles.
`
`BACKGROUND OF THE INVENTION
`With the volume of vehicles using roadways today. traf?c
`detection and management has become ever important. For
`example. control of intersections. detection of incidents.
`such as tra?ic accidents. and collection of data related to a
`tra?ic scene are all integral to maintaining and improving the
`state of tra?ic management and safety. Since the 1950s.
`point detection devices. such as in-ground inductive loops.
`have primarily been used for intersection control and tra?ic
`data collection. The in-ground inductive loops basically
`consist of wire loops placed in the pavement. detecting the
`presence of vehicles through magnetic induction.
`Many limitations exist with point detection devices such
`as the inductive loops. Namely. the inductive loops are
`limited in area coverage for each individual loop. expensive
`to install. requiring a roadway to be dug up for their
`installation. and are dif?cult to maintain. Further. such point
`detectors possess substantial limitations in their ability to
`accurately assess a trailic scene and extract useful informa
`tion relating to the scene. While point detection devices can
`detect the presence or absence of vehicles at a particular.
`?xed location. they cannot directly determine many other
`useful tra?ic parameters. Rather. they must determine such
`parameters through multiple detection and inference. For
`instance. to calculate the velocity of a vehicle. a traffic
`management system employing point detection devices
`requires at least two detection devices to determine the time
`between detection at two points. thereby resulting in a
`velocity measurement. Other methods of detection. such as
`ultrasonic and radar detection also possess similar limita
`tions.
`A tra?ic scene contains much more information than point
`detection devices can collect. While a point detection device
`can provide one bit of data. a video image can provide a
`300.000 byte description of the scene. In addition to the
`wide-area coverage provided by video images. the image
`sequences capture the dynamic aspects of the tra?ic scene.
`for example at a rate of 30 images a second. Therefore.
`advanced traffic control technologies have employed
`machine vision. to improve the vehicle detection and infor
`mation extraction at a tra?ic scene. These machine vision
`systems typically consist of a video camera overlooking a
`section of the roadway and a processor that processes the
`images received from the video camera. The processor then
`attempts to detect the presence of a vehicle and extract other
`tra?ic related information from the video image.
`An example of such a machine vision system is described
`in U.S. Pat. No. 4.847.772 to Michalopoulos et al.. and
`further described in Panos G. Michalopoulos. Vehicle Detec
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`SAMSUNG EXHIBIT 1007
`Page 17 of 25
`
`

`

`5.761.326
`
`3
`After identifying a starting point. the systems perform a
`searching sequence. The systems have a current vehicle
`location. initially. the starting point. Then they look for
`potential displacement locations. The systems compare the
`potential displacement locations and select the location with
`the greatest suitability. They determine suitability by extract
`ing a subimage region surrounding the current track loca
`tion. Then. they displace the entire subimage region to
`potential new locations on the subsequent image frame.
`Thus. the systems perform a displacement of location and
`time. The systems perform a pixel-by-pixel correlation to
`determine which location‘s image best “matches" the pre
`vious location’s image. This type of correlation runs into
`limitations because the system treats the background pixels
`the same as the pixels of the moving vehicle. thereby
`causing problems with matching. Further. since all pixel
`intensities are weighted equally in importance. large areas of
`uniformity. such as the hood of a vehicle. are redundant. In
`such areas of uniformity. the system will be able to match a
`majority of pixels. but still may not line up the boundaries
`of the vehicle. While the edges of the vehicle constitute a
`minority of the pixels. they are the pixels that are most
`important to line up.
`Tra?ic detection. monitoring and vehicle classi?cation
`and tracking all are used for tra?ic management. Tra?ic
`management is typically performed by a state Department of
`Transportation (DOT). A DOT control center is typically
`located in a central location. receiving video from numerous
`video cameras installed at roadway locations. The center
`also receives tra?ic information and statistics. from sensors
`such as inductive loop or machine vision systems. '[I'a?ic
`management engineers typically have terminals for alter
`nately viewing video and traffic information. They scan the
`numerous video feeds to try to ?nd “interesting scenes” such
`as tra?ic accidents or tral?c jams. It is often dif?cult for
`tra?ic management engineers to locate a particular video
`feed which has the most interesting scene because they must
`perform a search to locate the video line containing the video
`feed with the interesting scene. Current tra?ic management
`systems also generate alarms based on inferred trends. which
`tell the tra?ic management engineers the location of a
`potentially interesting scene. Because the systems infer
`trends at a location. the systems require time for the trend to
`develop. Thus. a delay is present for systems which infer
`trends. After such delay. the tra?c management engineers
`can then switch to the correct video feed.
`
`SUMMARY OF THE INVENTION
`To overcome the limitations in the prior art described
`above. and to overcome other limitations that will become
`apparent upon reading and understanding the present
`speci?cation. the present invention provides a method and
`apparatus for classifying and tracking objects in an image.
`The method and apparatus disclosed can be utilized for
`classifying and tracking vehicles from a plurality of roadway
`sites. the images from the sites as provided in real-time by
`video cameras. The images from the real-time video are then
`processed by an image processor which creates classi?cation
`and tracking data in real-time and sends the data to some
`interfacing means.
`The apparatus of the present invention includes a plurality
`of video cameras situated over a plurality of roadways. the
`video cameras filming the sites in real-time. The video
`cameras are electrically interconnected to a switcher. which
`allows for manual or automatic switching between the
`plurality of video cameras. The video is sent to a plurality of
`image processors which analyze the images from the video
`
`20
`
`25
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4
`and create classi?cation and tracking data. The classi?cation
`and tracking data may then be sent to a workstation. where
`a graphical user interface integrates the live video from one
`of the plurality of video cameras with tra?ic statistics. data
`and maps. The graphical user interface further automatically
`displays alarm information when an incident has been
`detected. The classi?cation and tracking data may further be
`stored in databases for later use by traffic analysts or tra?ic
`control devices.
`The present invention provides for a method for classi
`fying vehicles in an image provided by real-time video. The
`method ?rst includes the step of determining the magnitude
`of vertical and horizontal edge element intensities for each
`pixel of the image. Then. a vector with magnitude and angle
`is computed for each pixel from the horizontal and vertical
`edge element intensity data. Fuzzy set theory is applied to
`the vectors in a region of interest to fuzzify the angle and
`location data. as weighted by the magnitude of the intensi
`ties. Data from applying the fuzzy set theory is used to create
`a single vector characterizing the entire region of interest.
`Finally. a neural network analyzes the single vector and
`classi?es the vehicle.
`After classi?cation. a vehicle can further be tracked. After
`determining the initial location of the classi?ed vehicle.
`potential future track points are determined. Inertial history
`can aid in predicting potential future track points. A match
`score is then calculated for each potential future track point.
`The match score is calculated by translating the initial
`location’s region onto a potential future track point‘s region.
`The edge elements of the initial location’s region are com
`pared with the edge elements of the future track point’s
`region. The better the edge elements match. the higher the
`match score. Edge elements are further weighted according
`to whether they are on a vehicle or are in the background.
`Finally. the potential future track point region with the
`highest match score is designated as the next track point.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`In the drawings. where like numerals refer to like ele
`ments throughout the several views;
`FIG. 1 is a perspective view of a typical roadway scene
`including a mounted video camera of the present invention;
`FIG. 2 is a block diagram of the modules for an embodi
`ment of the classi?cation and tracking system of the present
`invention;
`FIG. 3 is a ?ow diagram of the steps for classifying a
`vehicle;
`FIG. 4 is a top-view of a kernel element used in the
`classi?cation process;
`FIG. 5 is a graphical representation of an image of a
`scene. illustrating the placement of potential regions of
`interest;
`FIG. 6A and 6B are graphs used to describe the angle
`fuzzy set operator;
`FIG. 7A is a top-view of a location fuzzy set operator as
`used in a preferred embodiment;
`FIG. 7B illustrates the placement of location fuzzy set
`operators with respect to the region of interest;
`FIG. 8 illustrates the process of organizing information
`from location and angle fuzzy set theory in matrix form;
`FIG. 9 illustrates the placement of icons on classi?ed
`vehicles;
`FIG. 10 is a ?ow diagram of the steps for tracking a
`vehicle;
`
`SAMSUNG EXHIBIT 1007
`Page 18 of 25
`
`

`

`5,761,326
`
`5
`FIG. 11 is a graphical representation of an image of the
`scene. illustrating the placement of potential future track
`regions;
`FIG. 12 is a diagram of a preferred embodiment of the
`system of the present invention;
`FIG. 13 is a graphical representation of an image dis
`played by the monitor of a graphical user interface;
`FIG. 14 is a graphical representation of an image dis
`played by the monitor of a graphical user interface. illus
`trating an alarm message; and
`FIGS. 15a and 15b show a hardware implementation of
`the vehicle match score generator shown in FIG. 10.
`
`l0
`
`15
`
`25
`
`6
`nation and Subtraction for a Monocular Vision System”.
`?led Apr. 27. 1995.
`Vehicle identi?cation and classi?cation module 24 and
`vehicle tracking module 22 then process the stabilized video
`image information. Vehicle identi?cation and classi?cation
`may be used for vehicle tracking or may be directly output
`as data for further analysis or storage. The results of vehicle
`classi?cation module 24 and vehicle tracking module 22 are
`consolidated in tra?ic interpreter 26. which may include a
`user interface and the system central processing unit. Results
`of the image processing are then available for other modules.
`such as tra?ic data module 27. control module 28. or alarm
`information module 29 which signals abnormalities in the
`scene.
`FIG. 3 is an image processing ?ow diagram of the data
`?ow for vehicle classi?cation. At module 40. the video
`image is digitized and stabilized. eliminating noise due to
`vibration and other environmental etfects for a discrete
`image array a at time ta. The discrete image array a may
`consist of a matrix of numbers. such as a 512x512 pixel
`image having an integer de?ning the intensity of each pixel.
`with a definition range for each color of 0-255. Successive
`image arrays would be a+1 at time tw?) etc.
`At edgel de?nition module 41. each pixel of the image
`array output from the stabilized image is evaluated for the
`magnitude of its edge element (edgel) intensity. Edgel
`intensity indicates the likelihood that a given pixel is located
`on some edge having particular orientation and contrast. The
`greater the contrast between a particular pixel and the pixels
`surrounding it in a particular orientation. the greater the
`edgel intensity. An edge differs from an edgel in that an edge
`is a more global phenomena involving many edgels. Edgel
`de?nition module 41 takes the data of the image array and
`produces two edgel images for each pixel. A ?rst edgel
`inmge represents the likelihood that each pixel lies on a
`horizontal edge. or the degree of horizontal edgeness at each
`pixel. x_edgel. calculated according to equation 1.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`In the following detailed description of the preferred
`embodiment. reference is made to the accompanying draw
`ings which form a part hereof. and in which is shown by way
`of illustration of a speci?c embodiment of which the inven
`tion may be practiced It is to be understood that other
`embodiments may be utilized and structural changes may be
`made without departing from the scope of the present
`invention.
`The fundamental component of information for machine
`vision systems is the image array from a scene of a speci?c
`section of a roadway as provided by video. FIG. 1 illustrates
`a scene where video camera 2 is positioned above roadway
`4 viewing scene 6. Scene 6 contains various stationary items
`such as trees 7. barrier 8. light poles 9 and position markers
`10. Scene 6 also may contain moving objects such as
`vehicles 12. Video camera 2 is electrically coupled. such as
`by electrical or ?ber optic cables. to electronic processing
`equipment 14 located locally. and further transmits infor
`mation to centralized location 16. Video camera 2 can
`thereby send real-time video images to centralized location
`16 for use such as viewing. processing. analysis or storage.
`Image information in the form of digitalized data for each
`pixel of an electronic video image of scene 6 is processed
`according to the ?ow diagram as illustrated in FIG. 2. For
`example. the image array may be a 512x512 pixel three
`color image having an integer number de?ning intensity
`with a de?nition range for each color of 0-255. If image
`information is not in digitized form. video image prepro
`cessor module 12 will digitize the image information. The
`camera image input is subject to environmental e?’ects
`including roadway vibration. wind. temperature change and
`other destabilizing factors. To counter the undesirable effects
`of camera motion. video image preprocessor module 12
`electronically performs image stabilization. Reference
`markers 10 are mounted within the view of video camera 2.
`Using frame to frame correlation with respect to reference
`markers 10. compensating translation and rotation is calcu
`lated. The appropriate warping of the image may be per
`formed in real time by machines such as Datacube Corpo
`ration’s (Danvers. Mass.) “Miniwarper”. Video image
`preprocessor 12 may then calibrate the stabilized video
`image information by mapping the real world measurements
`of the image to the pixel space of the image. Video image
`preprocessor 12 may further perform background
`subtraction. eliminating any image information not associ
`ated to a vehicle. Thus. the image is segmented into vehicle
`related pixels and nonvehicle/background pixels. A pre
`ferred embodiment of a method and apparatus for back
`ground subtraction for use with the present invention is
`described in commonly-assigned US. patent application
`entitled “Method and Apparatus for Background Determi
`
`35
`
`45
`
`55
`
`65
`
`Within equation 1. sign(v) is +1 when v is positive and —1
`when v is negative. IG-HWW) are the pixel intensities sur
`rounding pixel (i.j) and the kernel is of size 2k+l by 2k+l
`where k is equal to two in one embodiment of the system
`The second image represents the likelihood that a pixel lies
`on a vertical edge. or the degree of vertical edgeness.
`y_edgel. calculated according to equation 2.
`
`Within equation 2. sign(u) is +1 when u is positive and —1
`when u is negative. Therefore. edgel detection module 41
`determines the likelihood that each pixel within the image
`array lies on a horizontal or vertical edge.
`FIG. 4 shows a plot of a sample 8X8 kernel used to
`calculate edgel intensities. Edgel detection module 41 suc
`cessively applies kernel 59 to each pixel within the image
`array to perform convolution. The convolution takes into
`account the pixels surrounding the pixel in question. thereby
`determining the likelihood that the pixel in question is
`located on an edge. Edgel detection module 41 replaces the
`original pixel value with the outputs from applying kernel 59
`twice in two orientations. resulting in two new integers
`representing both the horizontal and vertical edgeness of the
`pixel.
`Edgel de?nition module 41 sends forward the horizontal
`edgeness data (x_edgel) and vertical edgeness data
`
`SAMSUNG EXHIBIT 1007
`Page 19 of 25
`
`

`

`5.761.326
`
`7
`(y_edgel) of the array a to geometric transform module 45.
`Geometric transform module 45 converts the discrete pixel
`data pairs (x_edgel.y_edgel) from degree of horizontal
`edgeness and vertical edgeness values to a vector with
`direction and magnitude for each pixel (id). The direction
`may be expressed in angle format while the magnitude may
`be expressed by an integer. In a preferred embodiment. the
`angle is between 0-180 degrees while the intensity may be
`between O-255. The transform of data is analogous to
`transforming rectangular coordinates to polar coordinates in
`a Euclidean space. The geometric transform is performed. in
`a preferred embodiment. according to equations 3 and 4. The
`magnitude value is a calculation of total edgel intensity
`(sum_edgel) of each pixel. and is calculated according to
`equation 3.
`
`Equation 3
`The angle value or developed in geometric transform module
`45 for pixel i.j is calculated according to equation 4.
`
`1O
`
`15
`
`25
`
`8
`value is compared to the like average sum_edgel value for
`the previous and subsequent frames. When comparison
`indicates that a local maximum for the sum_edgel value has
`been reached. or local minirna. if some different criteria is
`used. the candidate region becomes a region of interest.
`Once a region of interest has been identi?ed. the region
`priority module 47 selects the region of interest and sends it
`forward for vehicle identi?cation by class.
`While the data available would be su?icient for classi?
`cation purposes. the amount of data is too voluminous for
`real-time processing. Further. there is great redundancy in
`the data. Finally. the data has too little invariance in both
`translation and rotation. Therefore. the system of the present
`invention reduces the amount of data. reduces the redun
`dancy and increases the invariance of the data by applying
`fuzzy set theory. Vectorization module 51 converts the
`geometrically transformed data to vector data by applying
`fuzzy set theory to the transformed data. Vectorization
`module 51 may apply separate fuzzy set operators on both
`the location and the angular characteristics of each geometri
`cally transformed edgel. Vectorization module 51 deter
`mines a vector which characterizes the entire region of
`