Object Identification in a Bayesian Context

1 ·Introduction

Object identification-the task of deciding that two observed objects are in fact one and the same object-is a fundamental requirement for any situated agent that reasons about indi­ viduals. Our aim in this paper is to establish the patterns of reasoning involved in object identification. To avoid pos­ sibly empty theorizing, we couple this investigation with a real application of economic significance: identification of vehicles in freeway traffic. Each refinement of the theoretical framework is illustrated in the context of this application. We begin with a general introduction to the identification task. Section 2 provides a Bayesian foundation for computing the probability of identity. Section 3 shows how this probability can be expressed in terms of appearance probabilities, and Section 4 describes our implementation. Finally, Section 5 presents experimental results in the application domain.

*This work was sponsored by JPL's New Traffic Sensor Technol­ ogy program and by California PATH under MOU 152 and 214.

1.1 Conceptual and theoretical issues

The existence of individuals is central to our conceptualization of the world. While object recognition deals with assigning objects to categories, such as 1988 Toyota Celicas or adult humans, object identification deals with recognizing specific individuals, such as one's car or one's spouse. One can have specific relations to individuals, such as ownership or mar­ riage. Hence, it is often important to be fairly certain about the identity of the particular objects one encounters.

Formally speaking, identity is expressed by the equal­ ity operator of first-order logic. Having detected an ob­ ject C in a parking lot, one might be interested in whether C = MyCar. Because mistaken identity is always a possibil­ ity, this becomes a question of the probability of identity: P(C=MyCari all available evidence). There has been little work on this question in AI. 1 The approach we will take (Sec­ tion 2) is the standard Bayesian approach: define an event space, assign a prior, condition on the evidence, and identify the events corresponding to the truth of the identity sentence. The key step is the last, and takes the form of an identity criterion. Once we have a formula for the probability of iden­ tity, we must find a way to compute it in terms of quantities that are available in the domain model. Section 3 shows that one natural quantity of interest is the appearance probability. This quantity, which covers diverse domain-specific phenom­ ena ranging from the effects of motion, pose, and lighting to changes of address of credit applicants, seems to be more nat­ ural and usable than the usual division into sensor and motion models, which require calibration against ground truth.

1 In contrast, reasoning about category membership based on ev­ idence is the canonical task for probabilistic inference. Proposing that MyCar is just a very small category misses the point.

The authors are participants in Roadwatch, a major project aimed at the automation of wide-area freeway traffic surveil­ lance and control [Malik and Russell, 1997]. Object identi­ fication is required for two purposes: first, to measure link travel time-the actual time taken for traffic to travel between two fixed points on the freeway network; and second, to pro­ vide origin/destination (OlD) counts-the total number of vehicles traveling between any two points on the network in a given time interval. The sensors used in this project are video cameras placed on poles beside the freeway (Figure 1 ). The video streams are processed at each camera site by vehicle tracking software running on customized parallel hardware. The resulting streams of chronologically ordered vehicle re­ ports are sent to the TMC (Traffic Management Center). The TMC uses these reports to determine when a vehicle detected at one camera has reappeared at another. These matches are used to build up a path for each vehicle as it travels through the freeway network. The set of paths can be queried to compute link travel times and 0/D counts as desired. The output of the system is a traffic information display, updated in real time for use by traffic operations managers or by individual drivers.

Obviously, a license-plate reader would render the vehi­ cle identification task trivial, but for political and technical reasons, this is not feasible. In fact, because of very re­ stricted communication bandwidth, the vehicle reports sent to the TMC can contain only about one hundred bytes of informa­ tion. In addition, the measurements contained in the reports are extremely noisy, especially in rainy, foggy, and night-time conditions. Thus, with thousands of vehicles passing each camera every hour, there may be many possible matches for each vehicle. This leads to a combinatorial problem-finding most likely consistent assignments between two large sets of vehicles-that is very similar to that faced in data association, a form of the object identification problem arising in radar and sonar tracking. Section 4 explores this connection in more de­ tail. We adopt a solution from the data association literature, but also introduce a new "leave-one-out" heuristic for select­ ing reliable matches. This, together with a scheme for online learning of appearance models to handle changing viewing and traffic conditions, yields a system with performance good enough for practical deployment (Section 5).

2 Inferring identity from observations

This section shows how the probability of identity can be defined in terms of physical observations and events. We begin with the formal framework and then illustrate it in the traffic domain.

2.1 Formal Bayesian framework

Let 0 be a random variable whose domain is the set of com­ plete observation histories. That is, any particular value of 0 might correspond to the complete set of observations of objects made by some agent: 0 = { 01, . . . , on}. Let Oa and Ob be two specific observations made, which we may think of as having been caused by objects a and b. 2 Infor­ mally, we may write the probability of identity of a and b as P(a =biO = {OJ, .. . , On} ). 3

To make this probability evaluable, we define an event space S= (HI, .. . , HN). where each Hk is a random variable denot­ ing the "life history" of the kth object in the universe, and each event is anN-tuple specifying the life history of all N objects. We can think of the index k as an invisible "object identifica­ tion number." We impose a prior distribution P(S), with the restriction that the prior is exchangeable, i.e., invariant under any permutation of object indices. Also, we will use the no­ tation Oi E Hk to mean that observation Oi was generated by the kth object.

2 For the purposes of this paper, we will assume that each observa­ tion corresponds to exactly one physical object. This assumption can be relaxed, at the cost of introducing into the theory the mechanism whereby objects generate observations.

3 0ne is tempted to write this as P(a = b)o1, ·· · , o.), i.e., to condi­ tion on a conjunction of the "positive" observations. However, con­ ditioning on the positive observations is not the same as conditioning on both positive observations and negative observations-that is, observations of no vehicles at a given time and place. The temp­ tation therefore reflects a natural "semi-closed-world" assumption: one assumes that the stated positive observations are all that have been made in the past, and that all other observations were negative. Obviously, one does not make this assumption regarding the future.

Now the key step is to provide an identity criterion to select those events corresponding to a and b being the same object. We write this as

That is, the two observed objects are the same if each obser­ vation was generated by the life history of the same object. This is the basic step in relating propositional observations to identity sentences.

Since the propositions in this disjunction are mutually ex­ clusive, we have

Conditioning on the event space S yields

where Oa , Ob E Hk is shorthand for (oa E Hk) 1\ (ob E Hk) . Finally, we expand P(oa, Ob E Ht. Ols) to obtain

(1)

In this way, we express the probability of identity in terms of the probability of observations given events. We now make this framework more concrete in the context of the traffic domain.

2.2 Identity in the traffic domain

The basic vehicle identification task involves two cameras on a freeway, one upstream and one downstream. The TMC moni­ tors a vehicle's progress by matching the appropriate upstream observation of the vehicle with the appropriate downstream observation. It is natural to keep the observation history 0 separated in two parts, U (observations by upstream camera u) and D (observations by downstream camera d). Each obser­ vation oj E U of vehicle i is a pair (rf ,ft), where rf includes the location of the vehicle and the time of observation, while ft corresponds to observed values of intrinsic features of the vehicle, such as color and size. The same holds for observa­ tion of E D of vehicle j. It is reasonable to assume that each r is unique, since a vehicle cannot be in two places at once, nor can two vehicles be in the same place at once.

Hk can be thought of as a trajectory for the kth vehicle, specifying its position as a function of time. The identity criterion for observed vehicles a and b now becomes

To illustrate Eq. (1), consider the simplified case where the universe contains exactly two vehicles of similar appear­ ance, each moving at constant velocity along the same road. Two reliable cameras, located at Yu and yd, make observa­ tions whenever vehicles pass by. From time t=O to t= T, the observation history 0 consists of U = { o~} recorded at ta and D = {on recorded at tb . The event space S = (Ht , H2) therefore ranges over all possible trajectories for two vehicles; these can, in turn, be defined by the random variables (Yt, Vt) and (y2, v2), where Yt and Y2 are the positions of the vehicles at time ta, and v1 and v2 are the velocities. Figure 2 shows two possible events consistent with the observations--one where a=b and one where afb . .

It turns out that the probability of identity is easiest to compute from the ratio

so that P(O) in Eq. (1) cancels. Suppose now that Yd - Yu is 2000 meters and that tb - ta is 100 seconds. Furthermore, suppose P(S) is such that Yt and Y2 are independently and uniformly distributed in the range [y., Yd] and that Vt and v2 are independently and uniformly distributed in the range [ lOm/s, 40m/s]. In this case, P(s) is constant over the range of integration, and the above ratio is given by

Thus, P(a=biO) = 1/3.

3 Appearance models

The previous section showed how to express the probability of identity in terms of the probability of observations given events. Some domains, including traffic surveillance, involve observation sets that contain initial observations of objects as well as subsequent observations of objects. In these situations, appearance probabilities, which define how objects observed at some point in the past can be expected to appear at some point in the future, seem to provide a more usable model than standard motion and sensor models. In this section, we show how to express Eq. (1) in terms of appearance probabilities and describe the specific appearance probabilities used in the vehicle identification domain.

3.1 Identity in terms of appearance probabilities

Suppose we are given observation history 0 = U U D, where U consists of initial observations of objects, and D consists of subsequent observations of objects. Keeping these sets separate in Eq. (1) gives the following for P(a = biU, D):

Expanding P(U, Dloa, Ob E Hb s) yields

At this point, we define a new event space Q, which is a coarsening of S. First, we need some new terms: A matching is a pairing indicating that two observations were generated by the same object. For example, the matching (a, b) indicates that the same object generated Oa and Ob. Given a set of initial observations and a set of subsequent observations, an assignment is a set of matchings for every observation in each set. The assignment space Q is an event space that ranges over the space of possible assignments. It thus divides the space S into subsets of events, such that each subset is relatively homogeneous if we condition on the observations-because each subset then effectively specifies the starting point and ending point of each vehicle's trajectory.

Summing over only those assignments w that satisfy the identity criterion for a and b gives

Since the principle of exchangeability requires a uniform prior over Q, and since P(Uiw) is constant given no information about the observations to which the observations in U cor­ respond, these constant terms can be grouped outside of the summation along with the normalization constant P(U, D)- 1 so that we have

Finally, we assume that the probability of a specific subsequent observation, given a specific initial observation and a matching between the two observations, is independent of the other observations and matchings. Hence, we can factor P(DIU, w) into the product of the individual probabilities so that the identity equation becomes

In this expression, P(ojlo't, i = j) is an appearance probability, the probability that an object that initially generated observa­ tion oj subsequently generated observation of. We will write this as P(odlou) where no confusion is possible. It is important to note that the appearance probability is not the probability that i = j . This probability can only be computed by taking into account all other observations.

To ground this discussion, we will now discuss the specific observed features and appearance probability models used in the traffic domain.

3.2 Observed features for traffic

When a certain camera c observes some vehicle i, it generates a vehicle report consisting of various features. Thus, the observation of in our system is a vector of features. Currently, we use the features in this table:

The matching algorithm is designed to be independent of the specific features used; new features of arbitrary complexity, informativeness, and noise level can be added without chang­ ing the algorithm.

3.3 Appearance probabilities for traffic

The appearance probability is currently treated as the product of the following independent models:

• lane (x): discrete distribution P(~lxu)
• size (w, l): multivariate Gaussian

• color (h, s, v): multivariate Gaussian

• arrival time (t): univariate Gaussians conditioned on up­ stream and downstream lane

The arrival time model is particularly important, since it dras­ tically reduces the nu,mber of vehicle pairs that are considered to be plausible matches. The parameters f.L; .:i' and rT; .:i' rep­ resent the mean and standard deviation of the predicted link travel time for cars that start upstream in lane xu and end up downstream in lane~. This allows the system to accurately model , for example, the fact that cars in the car pool lane travel faster than cars in other lanes.

In examining the empirical distributions for the appearance probability, we were surprised by the level of noise and lack of correlation in measurements of the same feature at two different cameras. Some features, such as saturation, appear virtually uncorrelated. In all, we estimate that the size and color features provide only about 3 to 4 bits of information.

3.4 Online learning of appearance models

Because traffic and lighting conditions change throughout the day, our system uses online (recursive) estimation for the ap­ pearance probability model parameters. As new matches are identified by the vehicle matcher, the parameters are updated based on the observed feature values at the upstream and downstream sites. Figure 3 shows a sample set of x values for matched vehicles, from which P(x'lxu) can be estimated. Sim­ ilarly, Figure 4 shows a sample set of hue values for matched vehicles, from which P(hdW) can be estimated. To adapt to changing conditions, our system uses online exponential forgetting. For example, if a new match is found for a vehicle in Jane~ upstream and lane x' downstream, with link travel time t, then the mean travel time is updated as follows:

The 'Y parameter, which ranges from 0.0 to 1.0, controls the effective "window size" over which previous readings are given significant weight.

The above assumes that the match found is in fact correct. In practice, we can never be certain of this. A better motivated approach to model updates would be to use EM; this can be approximated by weighting each update by the probability that the match is correct.

4 Matching algorithm

We begin by describing the simplest case, where all vehicles detected at the upstream camera are also detected downstream, and there are no on ramps or offramps. In this case, the aim is to find pairs of vehicles a and b such that P(a = biU, D)> 1 - E for some small E. This problem is intractable in the worst case (it relates to computing the permanent of a matrix), so we adopt a heuristic approach.

The core of the approach is the observation, from [Cox and Hingorani, 1994], that a most probable assignment (pairing all n vehicles) can be found in time O(n 3 ) by formulating the problem as a weighted bipartite matching problem and using any of several well-known algorithms for this task. To do this, we construct an association matrix M of appearance probabilities, where each entry Mij =-Jog P(ojlo't), so that the assignment with least total weight in the matrix corresponds to the most probable assignment, according to Eq. (2).

For our purposes, knowing the most likely assignment is not enough. It can easily happen that some c of the n vehi­ cles are all very similar and fairly close to each other on the freeway. In this case, there will be c! assignments all having roughly the same probability as the most probable assignment. Since matches within this group may be very unreliable, we employ a leave-one-out heuristic that "forbids," in turn, each match contained in the best assignment. For each forbidden match, we measure the reduction in likelihood for the new best assignment. Matches whose forbidding results in a sig­ nificant reduction are deemed reliable, since this corresponds to a situation where there appears to be no other reasonable assignment for the upstream vehicle in question.

For example, suppose we have the following matrix:

I

II Downstream

Here the best assignment is {a= x, b = z, c = y}, with a total weight of 12.6. (Notice that a= y is the "closest" match for a, but leaves no good match for the others.) If we forbid a=x, the best assignment is {a=y,b=z,c=x} with weight 14.2. If the difference between these two weights is greater than some reliability threshold t, 4 i.e., if 14.2- 12.6 > t, then we accept the a =x match, since no other reasonable choice seems to exist. On the other hand, if we forbid b = z, the best assignment has weight 12.7. If 12.7- 12.6 <=t, then we reject b = z, since there is another match for b that yields a good overall assignment. By increasing the threshold t, we obtain more reliable matches, i.e., the error rate € is reduced; however, this reduces the overall number of accepted matches.

4 The value compared with the reliability threshold is the negative logarithm of the relative likelihood of the observations given the best

4.1 New and missing vehicles

In the general case, vehicles can appear from onramps between the cameras or can disappear onto offramps. (Equivalently, they can fail to be detected at the upstream or downstream camera.) To handle this, we add extra rows and columns to the association matrix. With m upstream and n downstream vehicles, the matrix now has m + n rows and columns to allow for all possibilities. Figure 5 illustrates the structure of the matrix for m = n = 2. Here, a is the probability that a vehicle exits the freeway, {3 is the number of vehicles entering the freeway between the cameras per unit time, and P(oi) refers to the prior probability of seeing a vehicle with features Oj. 5 The formulas in the table explain the interesting fact that human observers feel far more confident matching unusual vehicles than typical vehicles: not only is the probability of confusion with other vehicles lower, but the probability that the upstream vehicle exited, only to be replaced by another vehicle of the same unusual appearance, can be discounted because the extra multiplicative P(oi) factor for an unusual vehicle would be tiny.

4.2 Relationship to data association

The vehicle matching problem is closely related to the tradi­ tional "data association" problem from the tracking literature, in which new "observations" (from the downstream camera) must be associated with already-established "tracks" (from the upstream camera). Radar surveillance for air traffic control is a typical application: the radar dish determines an approx­ imate position for each aircraft every few seconds, and each new set of positions must be associated with the set of exist­ ing tracks. There is a large literature on data associationtypically over 100 papers per year. The standard text is by Bar­ Shalom and Fortmann [Bar-Shalom and Fortmann, 1988], and recent developments appear in [Bar-Shalom, 1992]. Ingemar Cox [Cox, 1993] surveys and integrates various developments, deriving formulas very similar to those in Figure 5. Cox's aim in his review paper is to present the ideas from the data asso­ ciation field to the computer vision and robotics community, where they might be used to resolve problems of identifying visual features seen in temporally separated images.

assignment and the observations given the best assignment with a forbidden match.

5 In our implementation, each of these models is learned online; a and (3 are also specific to individual lanes.

Major differences between our work and "standard" data association include the following:

1. Sensor noise and bias are large, unknown, time-varying, site-dependent, and camera-dependent, and sensor ob­ servations are high-dimensional.
2. Successive observations of a vehicle are widely separated in time and space, and all observations are asynchronous.
3. Vehicle trajectories are highly correlated.

5 Results

We tested the vehicle matcher with data from a region-based vehicle tracker on video sequences from the sites in Figure 1.

On any given run, the number of matches proposed by the vehicle matcher depends on the reliability threshold selected for that run. In the results discussed below, coverage refers to the percent of vehicles observed by both cameras for which matches were proposed, and accuracy refers to the percent of proposed matches that were in fact correct. In general, the coverage goes down as the reliability threshold is increased, but the accuracy goes up.

To verify the accuracy of the matcher, the ground-truth matches were determined by a human viewing the digitized sequences with the aid of a frame-based movie viewer. Since this method required about 3 hours of viewing to match each minute of video, it was used only during the early stages of testing. In subsequent testing, we first ran the matcher on the vehicle report data and then used the frame-based movie viewer to verify whether the suggested matches were correct.

Testing our system involved a start-up phase during which it estimated the appearance probability models online. For the results shown in Figure 6, we trained our system on a pair of 60-second video sequences and then ran it on the immediately following 60-second sequences. The sequences contained 29 vehicles upstream, along with numerous vehicles that either entered or exited the freeway in between the cameras. The resulting accuracy/coverage curve in figure 6 shows that de­ spite very noisy sensors, the system achieved 100% accuracy with a coverage of 14%, and 50% accuracy with a coverage of 80%. Incorporating additional features would probably improve system performance. The boxed vehicles in Figure 1 show a pair of vehicles correctly matched by our system.

Link travel times between each camera pair are currently calculated by averaging the observed travel times for matched vehicles. These times were accurate to within 1% over a dis­ tance of two miles, over a wide range of coverage/accuracy tradeoff points. This suggests that matched vehicles are rep­ resentative of the traffic flow-that is, the matching process does not select vehicles with a biased distribution of speeds.

Our results are comparable with those obtained by Petty et at. [Petty et al., to appear], who use an "ensemble" matching approach that detects downstream propagation of distinct ar­ rival time patterns. The two approaches are complementary, in that our approach allows identification of individual vehi­ cles (and hence the generation of OlD counts), whereas the Petty et al. approach provides a robust bootstrap method for initializing our arrival time models.

6 Conclusions and further work

This paper has described the patterns of reasoning involved in establishing identity from observations of objects. We pro­ posed a formal foundation based on a prior over the space of physical events, together with an identity criterion defin­ ing those events that correspond to observations of the same object. In the case of vehicle matching, the events are the different sets of trajectories of vehicles in a given freeway network. When a single trajectory passes through two vehicle observations, that implies that the observations correspond to the same object. This general approach makes it possible to define the probability of identity and to integrate the necessary patterns of reasoning into an intelligent agent.

This research can be seen as another step in the Carnapian tradition that views a rational agent as beginning with unin­ formative prior beliefs and then applying Bayesian updating throughout its lifetime. The general relationship between per­ ception and the formation of internal models is a subject that needs much more investigation [Bacchus et al., 1995].

We showed that the abstract probability of identity can be expressed in terms of measurable appearance probabilities, which define how, when, or where objects that were observed at some point in the past are expected to appear at some point in the future. These appearance probabilities can be learned online to adapt to changing conditions in the environment­ such as changing weather, lighting, and traffic patterns.

We have implemented and tested a system for vehicle matching using an efficient algorithm based on bipartite matching combined with a leave-one-out heuristic. Despite very noisy feature measurements from the cameras, our sys­ tem achieved a high level of accuracy in matching individual vehicles, enabling us to build the first reliable system for mea­ suring link travel times. Although experimental camera data were not available for the system to do so, it is already ca­ pable of tracking the path of a vehicle over a sequence of camera sites. Thus, 0/D counts for a time period can be computed by examining the complete set of recorded paths during that time period. For successful 0/D measurement over a long sequence of cameras, however, we need to im­ prove both matching coverage and the detection rate of the tracking subsystem.

The patterns of reasoning described here have broad appli­ cability to other domains. For example, the object identifica­ tion problem occurs in database management, where it is pos­ sible that two different records could correspond to the same entity. For example, US credit reporting agencies record over 500 million credit-using Americans, of whom only about 100 to 120 million are actually distinct individuals. Applying our approach to this problem could help with maintaining database consistency and with consolidating multiple databases con­ taining overlapping information.