United States Patent 19
`Brady et al.
`
`||||||||||||III
`USOO5434927A
`11) Patent Number:
`5.434,927
`45
`Date of Patent:
`Jul.18, 1995
`
`(54) METHOD AND APPARATUS FOR
`MACHINE VISION CLASSIFICATION AND
`TRACKING
`75 Inventors: Mark J. Brady, Cottage Grove;
`Darin G. Cerny, Minneapolis;
`Michelle C. Granholm, Woodbury;
`Belayneh W. Million, St. Paul, all of
`Minn.
`73) Assignee: Minnesota Mining and
`Manufacturing Company, St. Paul,
`Mirl.
`21 Appl. No.: 163,820
`22 Filed:
`Dec. 8, 1993
`51) Int. Cl.' ............................................... G06K9/00
`52 U.S.C. .................................... 382/104; 382/159;
`382/199; 348/148; 395/21; 395/905
`58 Field of Search ....................... 382/22, 28, 36, 14,
`382/1; 395/3, 21, 905, 61; 348/148, 149
`References Cited
`U.S. PATENT DOCUMENTS
`4,490,851 12/1984 Gerhart et al. ....................... 382/43
`4,709,264. 11/1987 Tamura et al. ....................... 358/93
`4,839,648 6/1989 Beucher et al. .............
`... 340/933
`4,847,772 7/1989 Michalopoulos et al........... 364/436
`4,942,533 7/1990 Kakisami et al. .......
`... 364/449
`5,046,111 9/1991 Cox et al. ................................ 382/8
`5,103,305 4/1992 Watanabe....
`... 358/105
`5,111,232 5/1992 Tsunefuji ............
`... 354/402
`5,172,226 12/1992 Morimura et al.
`... 358/105
`5,263,120 11/1993 Bickel ..........
`... 395/2
`5,280,566 l/1994 Nakamura ............................. 395/51
`5,296,852 3/1994 Rathi ................................... 340/933
`FOREIGN PATENT DOCUMENTS
`0454.166A2 4/1991 European Pat. Off. ...... G08G 1/08
`WO93/19441 9/1993 WIPO ......................... G08G 1/017
`OTHER PUBLICATIONS
`Gilbert and Holmes, Dynamic Traffic Information from
`
`(56)
`
`Remote Video Monitors, Environmental Research In
`stitute of Michigan, Oct. 1991, pp. 213-231.
`Zielke, Brauckmann and von Seelen, Intensity and Ea
`gle-Based Symmetry Detection Applied to Car-Following,
`Lecture Notes in Computer Science, vol. 588, G. San
`dini (Ed.), Computer Vision-ECCV '92, Springer-Ver
`lag Berlin Heidelberg 1992, pp. 865-873.
`Michalopoulos, Vehicle Detection Video Through Image
`Processing: The Autoscope System, IEEE Transactions on
`Vehicular Technology, vol. 40, No. 1, Feb. 1991, pp.
`21-29.
`Ali and Dagless, University of Bristol, UK, Alternative
`Practical Methods for Moying Object Detection, Interna
`tional Conference on Image Processing and its Applica
`tions (Conf Publ No. 354), pp. 77-80, 1992.
`Primary Examiner-Yon J. Couso
`Attorney, Agent, or Firm-Gary L. Griswold; Walter N.
`Kirn; Michael K. Ouyang
`57
`ABSTRACT
`A method and apparatus for classification and tracking
`objects in three-dimensional space is described. A ma
`chine vision system acquires images from roadway
`scenes and processes the images by analyzing the inten
`sities 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 charac
`terized by vectors. A neural network interprets the data
`created by the fuzzy set operators and classifies objects
`within the roadway scene. The system can also track
`objects within the roadway scene, such as vehicle, by
`forecasting potential track regions and then calculating
`match scores for each potential track region based on
`how well the edge elements from the target track re
`gions match those from the source region as weighted
`by the extent the edge elements have moved.
`
`29 Claims, 12 Drawing Sheets
`
`
`
`
`
`---
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 1 of 12
`
`5,434,927
`
`
`
`Sz\4NZ
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 2 of 12
`
`5,434,927
`
`
`
`DIGITAL VIEW
`ACOUISTION
`
`
`
`
`
`VIDEO MAGE
`PREPROCESSOR
`
`2
`
`
`
`
`
`VEHICLE
`IDENTIFICATION &
`CLASSIFICATION
`
`VEHICLE
`TRACKING
`
`22
`
`26
`
`TRAFFIC
`INTERPRETER
`-
`
`S
`
`
`
`Fig. 2
`
`27
`
`28
`
`29
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 3 of 12
`
`5.434,927
`
`40
`
`IMAGE
`ACOUSTION &
`STABILIZATION
`57
`
`EDGEL
`DEFINITION
`
`41
`
`43
`
`GEOMETRIC
`TRANSFORM
`
`REGION
`SELECTION
`
`44
`
`45
`
`46
`
`REGION
`PRIORITY
`
`47
`
`
`
`
`
`
`
`
`
`TO VEHICLE
`TRACKING
`
`. VECTORIZATION 1
`
`52
`
`53
`
`VEHICLE
`CLASSIFICATION
`
`VEHICLE
`LEARNING
`
`O
`
`Fig. 3
`
`ICON
`ASSIGNMENT
`
`4. 5
`
`5 5
`
`TO VEHICLE
`TRACKING
`
`

`

`U.S. Patent
`U.S. Patent
`
`July 18, 1995
`July 18, 1995
`
`Sheet 4 of 12
`Sheet 4 of 12
`
`5,434,927
`5,434,927
`
`
`
`
`
`Ex.1007 / Page 5 of 24
`TESLA, INC.
`
`

`

`U.S. Patent
`U.S. Patent
`
`
`
`Sheet 5 of 12
`Sheet 5 of 12
`
`5,434,927
`
`July 18, 1995
`July 18, 1995
`
`5,434,927
`
`Ex.1007 / Page 6 of 24
`TESLA,INC.
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 6 of 12
`
`5.434,927
`
`e (DEGREES)
`Fig. 6A
`
`
`
`e (DEGREES)
`Fig. 6B
`
`

`

`U.S. Patent
`U.S. Patent
`
`July 18, 1995
`July 18, 1995
`
`Sheet 7 of 12
`Sheet 7 of 12
`
`5,434,927
`5.434,927
`
`
`
` VMK SCL Uaioe
`
`LRTTELA
`
`17
`
`-
`
`Ex.1007 / Page 8 of 24
`TESLA,INC.
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 8 of 12
`
`5.434,927
`
`21O-
`
`2O6
`
`204
`
`208
`
`202
`
`
`
`
`
`W 2
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 9 of 12
`
`5,434,927
`
`250 Y 0-18
`
`19-36
`37-54
`55-72
`73-90 H.
`91-108
`109.126
`|
`|
`|
`|
`|
`|
`|
`|
`|
`1272
`127-144
`||
`|
`|
`|
`|
`|
`|
`|
`145-162
`163-180
`|
`|
`|
`|
`|
`|
`|
`|
`
`
`
`262
`
`i II.
`(I
`
`Fig. 8
`
`(x)
`
`I.
`Nr.
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 10 of 12
`
`5,434,927
`
`44
`
`55
`
`>
`5s X
`22
`it
`3 EXISTING
`S is
`VEHICLE
`C. E.
`& O
`g
`81
`82
`
`d c s
`CD
`
`(OE)
`
`- - - - - - - - - - - -
`. VEHICLE -
`LOG
`
`INERTIAL
`HISTORY OF
`SCENE
`
`
`
`
`
`
`
`EDGEL FRAME
`SUBTRACTION
`
`VEHICLE MATCH
`SCORE GENERATOR
`
`
`
`86C
`
`
`
`CANDDATE
`GENERATOR
`NEWMATCH
`PONTS
`
`TRAFFIC
`SUPERVISOR
`
`87
`
`NEW TRACK
`POINT
`
`N80
`92 .
`
`TRAFFIC
`INTERPRET
`ER
`-
`
`d
`
`s
`
`93
`
`94
`
`95
`
`Fig. 10
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 11 of 12
`
`5,434,927
`
`a.
`
`22, COMMERCIAL
`A VIDEO
`
`CAMERAS
`21 ONN
`-
`CO-AX
`210CNY
`N
`210Bi - K 216-24MICROWAVE
`D
`FIBER OPTIC Na
`
`21 OA
`
`260
`n
`
`N
`
`220
`
`
`
`VIDEo
`s
`N
`SWITCHER
`WORKSTATION Ke2ST
`CONTROL
`
`CENTRAL
`CONTROL
`
`250
`
`
`
`
`
`Roc
`R.4ON
`IMAGE PROCESSORS
`Fig. 12
`
`

`

`U.S. Patent
`
`July 18, 1995
`
`Sheet 12 of 12
`
`5.434,927
`
`310
`
`320
`
`330
`
`
`
`Site/Camera: 3
`incident Type: Rear-end collision
`A rear-end collision has occurred in the site
`tracked by camera #3.
`
`

`

`10
`
`15
`
`1.
`
`METHOD AND APPARATUS FOR MACHINE
`VISION CLASSIFICATION AND TRACKING
`
`FIELD OF THE INVENTION
`This invention relates generally to systems used for
`traffic detection, monitoring, management, and vehicle
`classification 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.
`BACKGROUND OF THE INVENTION
`With the volume of vehicles using roadways today,
`traffic detection and management has become ever
`important. For example, control of intersections, detec
`tion of incidents, such as traffic accidents, and collec
`tion of data related to a traffic scene are all integral to
`maintaining and improving the state of traffic manage
`ment and safety. Since the 1950s, point detection de
`vices, such as in-ground inductive loops, have primarily
`been used for intersection control and traffic data col
`lection. The in-ground inductive loops basically consist
`of wire loops placed in the pavement, detecting the
`presence of vehicles through magnetic induction.
`25
`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 difficult to maintain. Fur
`30
`ther, such point detectors possess substantial limitations
`in their ability to accurately assess a traffic scene and
`extract useful information relating to the scene. While
`point detection devices can detect the presence or ab
`sence of vehicles at a particular, fixed location, they
`35
`cannot directly determine many other useful traffic
`parameters. Rather, they must determine such parame
`ters through multiple detection and inference. For in
`stance, 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 simi
`lar limitations.
`45
`A traffic scene contains much more information than
`point detection devices can collect. While a point detec
`tion 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
`50
`images, the image sequences capture the dynamic as
`pects of the traffic scene, for example at a rate of 30
`images a second. Therefore, advanced traffic control
`technologies have employed machine vision, to im
`prove the vehicle detection and information extraction
`55
`at a traffic scene. These machine vision systems typi
`cally 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 traffic related information from the video image.
`An example of such a machine vision system is de
`scribed in U.S. Pat. No. 4,847,772 to Michalopoulos et
`al., and further described in Panos G. Michalopoulos,
`Vehicle Detection Video Through Image Processing:
`65
`The Autoscope System, IEEE Transactions on Vehicu
`lar Technology, Vol. 40, No. 1, February 1991. The
`Michalopoulos et al. patent discloses a video detection
`
`5,434,927
`2
`system including a video camera for providing a video
`image of the traffic scene, means for selecting a portion
`of the image for processing, and processor means for
`processing the selected portion of the image.
`The Michalopoulos et al. system can detect traffic in
`multiple locations, as specified by the user, using inter
`active 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 induc
`tance loops in the pavement as well as provides flexibil
`ity in detection placement, the Michalopoulos et al.
`system still roughly emulates the function of point de
`tection systems. The system still detects vehicles at
`roughly fixed locations and derives traffic parameters
`by induction, using mathematical and statistical formu
`lae. For example, the system classifies 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. Further, 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 automati
`cally 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 Mi
`chalopoulos et al. system detects vehicles by analyzing
`the energy, intensity or reflectivity of every pixel in the
`predefined detection lines and comparing an instanta
`neous image at every pixel with a threshold derived
`from analysis of the background scene without the pres
`ence of any vehicles.
`Other systems have utilized edge detection for de
`tecting vehicles. These systems often perform "blob
`analysis' on the raw image, which constitutes a group
`ing of elements. The goal of such an analysis is deter
`mining 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 neigh
`boring pixels and determines whether to include the
`pixels in the grouping. This process continues for each
`included pixel. Blob detector of this type have run into
`difficulties because all the decisions are interdependent.
`Once the system has made initial 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 incor
`rect. 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 sys
`tems is the capability to track the detected vehicles.
`Systems that track vehicles usually share some common
`characteristics. First, the system must identify the start
`ing point of the track. The system may do this by detect
`ing the vehicle by comparing an input image with a
`background image and judging objects having an area
`within a predetermined range as vehicles. Other sys
`tens 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
`
`

`

`10
`
`15
`
`20
`
`5,434,927
`3
`4
`always possible for systems to fail to track slow moving
`roadways, the video cameras filming the sites in real
`or stalled vehicles.
`time. The video cameras are electrically interconnected
`After identifying a starting point, the systems per
`to a switcher, which allows for manual or automatic
`form a searching sequence. The systems have a current
`switching between the plurality of video cameras. The
`vehicle location, initially, the starting point. Then they
`video is sent to a plurality of image processors which
`look for potential displacement locations. The systems
`analyze the images from the video and create classifica
`compare the potential displacement locations and select
`tion and tracking data. The classification and tracking
`the location with the greatest suitability. They deter
`data may then be sent to a workstation, where a graphi
`mine suitability by extracting a subimage region sur
`cal user interface integrates the live video from one of
`rounding the current track location. Then, they displace
`the plurality of video cameras with traffic statistics, data
`the entire subimage region to potential new locations on
`and maps. The graphical user interface further automat
`the subsequent image frame. Thus, the systems perform
`ically displays alarm information when an incident has
`a displacement of location and time. The systems per
`been detected. The classification and tracking data may
`form a pixel-by-pixel correlation to determine which
`further be stored in databases for later use by traffic
`location's image best "matches' the previous location's
`analysts or traffic control devices.
`image. This type of correlation runs into limitations
`The present invention provides for a method for
`because the system treats the background pixels the
`classifying vehicles in an image provided by real-time
`same as the pixels of the moving vehicle, thereby caus
`video. The method first includes the step of determining
`ing problems with matching. Further, since all pixel
`the magnitude of vertical and horizontal edge element
`intensities are weighted equally in importance, large
`intensities for each pixel of the image. Then, a vector
`areas of uniformity, such as the hood of a vehicle, are
`with magnitude and angle is computed for each pixel
`redundant. In such areas of unifornity, the system will
`from the horizontal and vertical edge element intensity
`be able to match a majority of pixels, but still may not
`data. Fuzzy set theory is applied to the vectors in a
`line up the boundaries of the vehicle. While the edges of
`region of interest to fuzzify the angle and location data,
`the vehicle constitute a minority of the pixels, they are
`25
`as weighted by the magnitude of the intensities. Data
`the pixels that are most important to line up.
`from applying the fuzzy set theory is used to create a
`Traffic detection, monitoring and vehicle classifica
`single vector characterizing the entire region of inter
`tion and tracking all are used for traffic management.
`est. Finally, a neural network analyzes the single vector
`Traffic management is typically performed by a state
`and classifies the vehicle.
`Department of Transportation (DOT). A DOT control
`After classification, a vehicle can further be tracked.
`center is typically located in a central location, receiv
`After determining the initial location of the classified
`ing video from numerous video cameras installed at
`vehicle, potential future track points are determined.
`roadway locations. The center also receives traffic in
`Inertial history can aid in predicting potential future
`formation and statistics, from sensors such as inductive
`track points. A match score is then calculated for each
`loop or machine vision systems. Traffic management
`35
`potential future track point. The match score is calcu
`engineers typically have terminals for alternately view
`lated by translating the initial location's region onto a
`ing video and traffic information. They scan the numer
`potential future track point's region. The edge elements
`ous video feeds to try to find "interesting scenes' such
`of the initial location's region are compared with the
`as traffic accidents or traffic jams. It is often difficult for
`edge elements of the future track point's region. The
`traffic management engineers to locate a particular
`better the edge elements match, the higher the match
`video feed which has the most interesting scene because
`score. Edge elements are further weighted according to
`they must perform a search to locate the video line
`whether they are on a vehicle or are in the background.
`containing the video feed with the interesting scene.
`Finally, the potential future track point region with the
`Current traffic management systems also generate
`highest match score is designated as the next track
`alarms based on inferred trends, which tell the traffic
`45
`point.
`management engineers the location of a potentially
`interesting scene. Because the systems infer trends at a
`BRIEF DESCRIPTION OF THE DRAWINGS
`location, the systems require time for the trend to de
`In the drawings, where like numerals refer to like
`velop. Thus, a delay is present for systems which infer
`elements throughout the several views; FIG. 1 is a
`trends. After such delay, the traffic management engi
`50
`perspective view of a typical roadway scene including a
`neers can then switch to the correct video feed.
`mounted video camera of the present invention;
`SUMMARY OF THE INVENTION
`FIG. 2 is a block diagram of the modules for an em
`bodiment of the classification and tracking system of the
`To overcome the limitations in the prior art described
`present invention;
`above, and to overcome other limitations that will be
`55
`FIG. 3 is a flow diagram of the steps for classifying a
`come apparent upon reading and understanding the
`present specification, the present invention provides a
`vehicle;
`method and apparatus for classifying and tracking ob
`FIG. 4 is a top-view of a kernel element used in the
`classification process;
`jects in an image. The method and apparatus disclosed
`FIG. 5 is a graphical representation of an image of a
`can be utilized for classifying and tracking vehicles
`scene, illustrating the placement of potential regions of
`from a plurality of roadway sites, the images from the
`sites as provided in real-time by video cameras. The
`interest;
`images from the real-time video are then processed by
`FIG. 6A and 6B are graphs used to describe the angle
`fuzzy set operator;
`an image processor which creates classification and
`FIG. 7A is a top-view of a location fuzzy set operator
`tracking data in real-time and sends the data to some
`65
`interfacing means.
`as used in a preferred embodiment;
`The apparatus of the present invention includes a
`FIG. 7B illustrates the placement of location fuzzy
`plurality of video cameras situated over a plurality of
`set operators with respect to the region of interest;
`
`30
`
`

`

`O
`
`15
`
`20
`
`5,434,927
`6
`5
`FIG. 8 illustrates the process of organizing informa
`ing any image information not associated to a vehicle.
`tion from location and angle fuzzy set theory in matrix
`Thus, the image is segmented into vehicle related pixels
`form;
`and nonvehicle/background pixels. A preferred en
`FIG. 9 illustrates the placement of icons on classified
`bodiment of a method and apparatus for background
`vehicles;
`subtraction for use with the present invention is de
`FIG. 10 is a flow diagram of the steps for tracking a
`scribed in commonly-assigned U.S. patent application
`vehicle;
`entitled "Method and Apparatus for Background De
`FIG. 11 is a graphical representation of an image of
`termination and Subtraction for a Monocular Vision
`the scene, illustrating the placement of potential future
`System’’ and identified by attorney docket number
`track regions;
`49805USA1A, filed on even date herewith and now
`FIG. 12 is a diagram of a preferred embodiment of
`U.S. patent application Ser. No. 08/163,422 now pend
`the system of the present invention;
`FIG. 13 is a graphical representation of an image
`Ing.
`displayed by the monitor of a graphical user interface;
`Vehicle identification and classification module 24
`and vehicle tracking module 22 then process the stabi
`and
`FIG. 14 is a graphical representation of an image
`lized video image information. Vehicle identification
`displayed by the monitor of a graphical user interface,
`and classification may be used for vehicle tracking or
`illustrating an alarm message.
`may be directly output as data for further analysis or
`storage. The results of vehicle classification module 24
`DETAILED DESCRIPTION OF THE
`and vehicle tracking module 22 are consolidated in
`PREFERRED EMBODIMENT
`traffic interpreter 26, which may include a user inter
`In the following detailed description of the preferred
`face and the system central processing unit. Results of
`embodiment, reference is made to the accompanying
`the image processing are then available for other mod
`drawings which form a part hereof, and in which is
`ules, such as traffic data module 27, control module 28,
`shown by way of illustration of a specific embodiment
`25
`or alarm information module 29 which signals abnor
`of which the invention may be practiced. It is to be
`malities in the scene.
`understood that other embodiments may be utilized and
`FIG. 3 is an image processing flow diagram of the
`structural changes may be made without departing from
`data flow for vehicle classification. At module 40, the
`the scope of the present invention.
`video image is digitized and stabilized, eliminating noise
`The fundamental component of information for ma
`30
`chine vision systems is the image array from a scene of
`due to vibration and other environmental effects for a
`a specific section of roadway as provided by video.
`discrete image array a at time ta. The discrete image
`FIG. 1 illustrates a scene where video camera 2 is posi
`array a may consist of a matrix of numbers, such as a
`tioned above roadway 4 viewing scene 6. Scene 6 con
`512X512 pixel image having a integer defining the in
`tains various stationary items such as trees 7, barrier 8,
`tensity of each pixel, with a definition range for each
`35
`light poles 9 and position markers 10. Scene 6 also may
`color of 0-255. Successive image arrays would be a-- 1
`contain moving objects such as vehicles 12. Video cam
`at timet(a+1) etc.
`era 2 is electrically coupled, such as by electrical or
`At edgel definition module 41, each pixel of the image
`fiber optic cables, to electronic processing equipment 14
`array output from the stabilized image is evaluated for
`located locally, and further transmits information to
`the magnitude of its edge element (edgel) intensity.
`centralized location 16. Video camera 2 can thereby
`Edgel intensity indicates the likelihood that a given
`send real-time video images to centralized location 16
`pixel is located on some edge having particular orienta
`for use such as viewing, processing, analysis or storage.
`tion and contrast. The greater the contrast between a
`Image information in the form of digitalized data for
`particular pixel and the pixels surrounding it in a partic
`each pixel of an electronic video image of scene 6 is
`45
`ular orientation, the greater the edgel intensity. An edge
`processed according to the flow diagram as illustrated
`differs from an edgel in that an edge is a more global
`in FIG. 2. For example, the image array may be a
`phenomena involving many edgels. Edgel definition
`512X512 pixel three color image having an integer
`number defining intensity with a definition range for
`module 41 takes the data of the image array and pro
`duces two edgel images for each pixel. A first edgel
`each color of 0-255. If image information is not in digi
`50
`tized form, video image preprocessor module 12 will
`image represents the likelihood that each pixel lies on a
`digitize the image information. The camera image input
`horizontal edge, or the degree of horizontal edgeness at
`is subject to environmental effects including roadway
`each pixel, X-edgei, calculated according to equation 1.
`vibration, wind, temperature change and other destabi
`lizing factors. To counter the undesirable effects of
`55
`camera motion, video image preprocessor module 12
`electronically performs image stabilization. Reference
`markers 10 are mounted within the view of video cam
`era 2. Using frame to frame correlation with respect to
`reference markers 10, compensating translation and
`rotation is calculated. The appropriate warping of the
`image may be performed in real time by machines such
`as Datacube Corporation's (Danvers, Mass.) “Mini
`warper'. Video image preprocessor 12 may then cali
`brate the stabilized video image information by map
`65
`ping the real world measurements of the image to the
`pixel space of the image. Video image preprocessor 12
`may further perform background subtraction, eliminat
`
`Within equation I, sign(v) is -- 1 when v is positive and
`-1 when v is negative, I-90) are the pixel intensi
`ties surrounding pixel (i,j) and the kernel is of size2k+1
`by 2k-1 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.
`
`A
`Equation 1
`k
`Single-(2+2)/202 Ig
`X-edgelij = s
`u,yl-kV 2ntor?
`
`

`

`7
`
`k s
`
`S.
`
`Equation 2
`t e-(u2+2)/2a2 ) is a
`
`10
`
`15
`
`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
`successively 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 orienta
`tions, resulting in two new integers representing both
`20
`the horizontal and vertical edgeness of the pixel.
`Edgel definition module 41 sends forward the hori
`zontal edgeness data (x edgel) and vertical edgeness
`data (y-edgel) of the array a to geometric transform
`module 45. Geometric transform module 45 converts
`25
`the discrete pixel data pairs (x-edgely ledgel) from
`degree of horizontal edgeness and vertical edgeness
`values to a vector with direction and magnitude for
`each pixel (i,j). The direction may be expressed in angle
`format while the magnitude may be expressed by an
`30
`integer. In a preferred embodiment, the angle is be
`tween 0-180 degrees while the intensity may be be
`tween 0-255. The transform of data is analogous to
`transforming rectangular coordinates to polar coordi
`nates in a Euclidean space. The geometric transform is
`35
`performed, in a preferred embodiment, according to
`equations 3 and 4. The magnitude value is a calculation
`of total edgel intensity (sun-edgel) of each pixel, and is
`calculated according to equation 3.
`
`sum edgelii = x-edgelii + |y-edgeli
`Equation 3
`The angle value a developed in geometric transform
`module 45 for pixel i,j is calculated according to equa
`tion 4.
`45
`
`5,434,927
`8
`may be used. Candidate regions may be dynamically
`generated according to prior calibration of the scene.
`Regions of interest are overlapped within the image
`space. In a preferred embodiment, overlapping regions
`are confined to the lower half of the image space. In the
`illustrated example, the candidate regions of interest are
`truck sized trapezoids, with some centered in the traffic
`lanes and others centered on the lane marker overlap
`ping the traffic lanes. The number of overlapping trape
`Zoids may vary, depending on the coverage preferred.
`Another set of overlapping trapezoids 36 could be, for
`example, car sized. Classification regions may be prede
`fined.
`Region selection module 46 scans the predefined
`regions of interest to determine presence of vehicles,
`selecting regions for analysis based on a minimum
`threshold of change in the average edgel value within a
`candidate region. The minimum threshold value only
`need be high enough such that changes in average edgel
`intensity will not rise above the threshold value due to
`noise within the region. Region selection module sums
`the individual sum-edgel values for all of the pixels for
`each candidate region and calculates an average sun
`edgel value. Region selection module 46then compares
`the candidate regions of array a with the regions of
`frames a-1 and a-i-1, which are the previous and subse
`quent frames. The average sum-edgel value is com
`pared to the like average sum-edgel value for the pre
`vious and subsequent frames. When comparison indi
`cates that a local maximum for the sum-edgel value has
`been reached, or local minima, if some different criteria
`is used, the candidate region becomes a region of inter
`est. Once a region of interest has been identified, the
`region priority module 47 selects the region of interest
`and sends it forward for vehicle identification by class.
`While the data available would be sufficient for clas
`sification purposes, the amount of data is too volumi
`nous 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 redundancy and increases the in
`variance of the data by applying fuzzy set theory. Vec
`torization module 51 converts the geometrically trans
`formed 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 geometrically
`transformed edgel. Vectorization module 51 determines
`a vector which characterizes the entire region of inter
`est, the vector which contains sufficient information for
`classification of any vehicle within such region.
`In a preferred embodiment of the classification pro
`cess, vectorization module 51 applies ten overlapping
`wedge-shaped operators 66, as shown in FIG. 6A, to
`the angle components of the geometrically transformed
`edgels for angle fuzzification. Each wedge-shaped oper
`ator 66, has a width of 36 degrees and a unit height.
`When overlapping wedge-shaped operators 66 are ap
`plied to the angle components of each edgel, operators
`66 determine to what extent the angle should “count'
`toward each angle set. Each wedge-shaped operator is
`centered at a particular angle. For each angle compo
`nent not falling directly under the apex of a wedge, i.e.
`at an angle that a wedge is centered at, then the angle
`will be counted toward both wedges it falls under, tak
`ing into account which angle that each wedge is cen
`
`aj = b if y-edgelij = db
`
`ai E
`1 -
`
`90
`x -edgelij
`J-edgelij
`
`i x-