Switching Hypothesized Measurements: A Dynamic Model with Applications to Occlusion Adaptive Joint Tracking
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1326-1335.
© 2003 International Joint Conferences on Artificial Intelligence
Abstract
This paper proposes a dynamic model supporting multimodal state space probability distributions and presents the application of the model in dealing with visual occlusions when tracking multiple objects jointly. For a set of hypotheses, multiple measurements are acquired at each time instant. The model switches among a set of hypothesized measurements during the propagation. Two computationally efficient filtering algorithms are derived for online joint tracking. Both the occlusion relationship and state of the objects are recursively estimated from the history of measurement data. The switching hypothesized measurements (SHM) model is generally applicable to describe various dynamic processes with multiple alternative measurement methods.
- [Anderson and Moore, 1979] B. D. 0. Anderson and J. B. Moore, Optimal filtering, Prentice-Hall, 1979.
- [Ayer and Sawhney, 1995] S. Ayer and H. S. Sawhney, Layered representation of motion video using robust maximum- VISION likelihood estimation of mixture models and MDL encoding, In Proc. International Conf Computer Vision, pp. 777-784, 1995.
- [Bar-Shalom and Fortmann, 1988] Y. Bar-Shalom and T. E. Fortmann, Tracking and data association, Academic Press, 1988.
- [Brown, 1983] R. G. Brown, Introduction to random signal analysis and Kalman filtering, John Wiley & Sons, 1983 .
- [Cham and Rehg, 1999] T.-J. Cham and J. M. Rehg, A multiple hypothesis approach to figure tracking, In Proc. Conf Computer Vision and Pattern Recognition, vol. 2, pp. 239-245, 1999.
- [Cox and Hingorani , 1996] I. J. Cox and S. L. Hingorani, An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking, IEEE Trans . Patt. Anal. Mach. Intel., vol. 18, pp. 138-150, 1996.
- [Galvin et al., 1999] B. Galvin, B. McCane, and K. Novins, Virtual snakes for occlusion analysis, In Proc. Conf Computer Vision and Pattern Recognition, vol. 2, pp. 294-299, 1999.
- [Ghahramani and Hinton, 1998] Z. Ghahramani and G. E. Hinton, Variational learning for switching state-space models, Neural Computation, vol. 12, pp. 963-996, 1998.
- [Hager and Belhumeur, 1998] G. D. Hager and P. N. Belhumeur, Efficient region tracking with parametric models of geometry and illumination, IEEE Trans . Pall. Anal. Mach. Intel., vol. 20, pp. 1025-1039, 1998.
- [Isard and Blake, 1998] M. Isard and A. Blake, A mixed-state Condensation tracker with automatic model-switching, In Proc. International Conf Computer Vision, pp. I 07-112, 1998.
- [Isard and Blake, 1996] M. Isard and A. Blake, Contour tracking by stochastic propagation of conditional density, In Proc. European Conf Computer Vision, pp. 343-356, 1996.
- [Jojic and Frey, 2001] N. Jojic and B. J. Frey, Learning flexible sprites in video layers, In Proc. Conf Computer Vision and Pattern Recognition, vol. I, pp. 199-206, 2001.
- [Kim, 1994] C.-J. Kim, Dynamic linear models with Markov- switching, Journal of Econometrics, vol. 60, pp. 1-22, 1994.
- [Murphy, 1998] K. P. Murphy, Learning switching Kalman filter models, Technical Report 98-10, Compaq Cambridge Research Lab, 1998.
- [Pavlovic and Rehg, 2000] V. Pavlovic and J. M. Rehg, Impact of dynamic model learning on classification of human motion, In Proc. Conf Computer Vision and Pattern Recognition, vol. I , pp. 788-795, 2000.
- [Rasmussen and Hager, 2001] C. Rasmussen and G. D. Hager, Probabilistic data association methods for tracking complex visual objects, IEEE Trans. Patt. Anal. Mach. Intel., vol. 23, pp. 560-576, 200 I .
- [Rohr, 1994] K. Rohr, Towards model-based recognition of human movements in image sequences, Computer Vision, Graphics, and Image Processing: Image Understanding, vol. 59, pp. 94- 115, 1994.
- [Shumway and Stoffer, 1991] R. H . Shumway and D. S. Stoffer, Dynamic linear models with switching, Journal of the American Statistical Association, vol. 86, pp. 763-769, 1991.
- [Tao et al., 2002] H . Tao, H. S. Sawhney, and R. Kumar, Object tracking with Bayesian estimation of dynamic Layer representations, IEEE Trans. Patt. Anal. Mach. Intel., vol. 24, pp. 75-89, 2002.
- [Wang and Adelson, 1994] J. Y. A. Wang and E. H. Adelson, Representing moving images with layers, IEEE Trans . Image Processing, vol. 3, pp. 625-637, 1994.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Visual tracking is important in such application areas as human-computer interaction, surveillance, and visual reconstruction. Given a sequence of images containing the objects that are represented with a parametric motion model, parameters of the motion model are required to be estimated in successive frames. Tracking could be difficult due to the potential variability such as partial or full occlusions of objects, appearance changes caused by the variation of object poses or illumination conditions, as well as distractions from background clutter.
One principle challenge for visual tracking is to develop an accurate and effective model representation. The variability in visual environments usually results in a multimodal state space probability distribution. The Kalman filter [Brown, 1983; Rohr, 1994 ], a classical choice employed in tracking work, is restricted to representing unimodal probability distributions. Switching linear dynamic systems (SLDS) [Pavlovic and Rehg, 2000] and their equivalents [Shumway and Stoffer, 1991; Kim, 1994] have been used to describe dynamic processes. Intuitively, a complex dynamic system is represented with a set of linear models controlled by a switching variable. Joint probabilistic data association (JPDA) [Bar-Shalom and
Kia-Fock Loe
Dept. Computer Science, National Univ. Singapore loekf@comp.nus.edu.sg
Fortmann, 1988] and multiple hypothesis tracking (MHT) [Cox and Hingorani, 1996] techniques, which represent multimodal distributions by constructing data association hypotheses, can be cast in the framework of SLDS as well. Moreover, Monte Carlo methods such as the Condensation algorithm [Isard and Blake, 1996] support multimodal probability densities with sample based representation. By retaining only the peaks of the probability density, relatively fewer samples are required in the work of Cham and Rehg [1999]. A switching model framework of the Condensation algorithm is also proposed by Isard and Blake [1998].
On the other hand, the measurement process is another essential issue to deal with the potential variability. Measurements are not readily available from image sequences in visual tracking. Even an accurate tracking model may have a poor performance if the measurements are too noisy. Parametric models can be used to characterize appearance changes of target regions [Hager and Belhumeur, 1998]. In the work of Galvin et al. [1999], two virtual snakes, a background and a foreground snake for each object, are generated to resolve the occlusion when two objects intersect. Rasmussen and Hager [2001] describe a joint measurement process for tracking multiple objects enumerating all possible occlusion relationships. The measurement with respect to the most possible occlusion relationship is determined from the current frame. Moreover, layered approach [Wang and Adelson, 1994; Ayer and Sawhney, 1995; Jojic and Frey, 2001; Tao et al., 2002] is an efficient way to represent multiple moving objects. A moving object is characterized by a coherent motion model over its support region.
In this paper, the idea of switching hypothesized measurements (SHM), which results in a SHM model supporting multimodal distributions, is proposed to handle the potential variability in visual tracking. The approach acquires a set of hypothesized measurements for different occlusion hypotheses at each time instant. Comparing with the above mentioned state space models, the SHM approach switches among a set of hypothesized measurements rather than switches among a set of models. Two computationally efficient filtering algorithms are derived for jointly tracking multiple objects. Both the occlusion relationship and state of the objects are estimated from the history of measurements.
2 Model
2.1 Hypothesized Measurement
For a hidden state sequence {zk} (k E N), the objective of online tracking is to recursively estimate zk from the set of all available measurements Yt :k = {y;} 1s;s.t< up to time k. For a certain complex system, the estimation may be influenced by a mode or switching state sequence {sk} as well, with sk E {1, 2, . . . , L} (L E N). Specifically, the mode switching originates from the measurement process in our work. The notion of a measurement is extended to a set of L hypothesized measurements Yk = (Yk,I. Yk,2, ... , Yk.L) at each time instant. Each YkJ (1 ~ j ~ L) is called a hypothesized measurement since it is obtained by assuming that the switching state sk is j at time k.
To illustrate the idea of hypothesized measurement, consider the measurement process for jointly tracking two objects, e.g. a rectangle and a circle, in an image sequence {gd . To deal with occlusions between the two objects when measuring the kth frame gk. the switching state sk is introduced to describe the depth ordering at time k. sk E {I, 2}, where sk equals 1 if the rectangle is in front of the circle, and 2 if the circle is in front of the rectangle. The hypothesized measurement YkJ (1 ~ j ~ 2) is denoted as (y(l), y< 2 ) l, where y<I) is the measurement for the k,j k,j k,j
rectangle, and y~~j is the measurement for the circle under the jth hypothesis.
Under the hypothesis of sk = 1, i.e. the circle is occluded by the rectangle at time k, the rectangle should be measured first to acquire y~ 1 .~ · Then the observed rectangle is masked in the image. The occluded area of the circle is ignored and only the visible region is matched normally to get y~ 2 l. Similarly, under the hypothesis of sk = 2, i.e. the rectangle is occluded by the circle, the circle should be matched first to get y~~~, then the masked image is used to measure y~'_J2 . Thus, the occlusion will not affect the measurement result. It is obvious that both hypothesized measurements support the condition of nonocclusion since different depth orderings of nonoverlapping objects are visually equivalent. The probabilities of the hypotheses should be equal in the case
of nonocclusion.
Unfortunately, the occlusion relationship is not given before hand. The objective of our SHM approach is to estimate both the switching state and the hidden state from the history of the hypothesized measurements.
2.2 Linear SHM Model for Joint Tracking
For joint tracking of M (M E N) objects in the scene, the switching state sk represents the occlusion relationship at time k. sk E {1, 2, ... , L}, and L = M!. We assume the switching state follows a first order Markov chain with the following transition probability,
(z~l) ,z~ 2 ) , . .. ,z~M)l, with Z~m) (1 ·~ m ~ M) being the state for the mth object at time k. For a linear process with Gaussian noise, the hidden state transition model becomes
where F ERn, x R n, is the state transition matrix, n is a zero-mean Gaussian noise with covariance matrix Q, and N(z; m, ~) is a Gaussian density with argument z, mean m, and covariance ~-

Given the switching state sk at time k, the corresponding hypothesized measurement y k s could be considered as a ' k proper measurement centering on the hidden state, while every other Yk.i for j t:. sk is an improper measurement generated under a wrong assumption. The improper measurement should be weakly influenced by the hidden state zk and have a large variance. To simplify the computation, we assume a normal distribution for a proper measurement and a uniform distribution for an improper measurement. The measurement model is simplified as
where vkJ is a zero-mean Gaussian noise with covariance matrix RkJ· and w is a uniformly distributed noise, whose density is a small positive constant. For the measurement of M b . · d d ( (I) (2) (M))T d o ~ects, YkJ 1s enote as Yk,J·Yk,J· · .. ·Yk,J , an vk,i . . ( (I) (2) (M))T G' h IS wntten as v k,J, v k,J, ... , v k,J . 1ven t e current state, the conditional independence measurements is assumed computationally efficient. among the hypothesized to make the model
The SHM model can be represented by a dynamic Bayesian network shown in figure 1.
3 Method
3.1 Measurement
Multiple, occluding objects are modeled using layer representation. Layers are indexed by m = 1, 2 , ... , M, with layer I being the layer that is closest to the camera and layer m being behind layer I, 2, ... , m-1. There is one object in each layer. The number of all occlusion relationship hypotheses (or depth ordering permutations) is L = M!. Each permutation is tagged with a index} (l .:;.j.:;, L) .
Under each permutation hypothesis, the object in the front layer 1 should be measured first from the image gk at time k. Then the object in layer 2 can be matched from the masked image, and so on. At last, the object in layer M can be measured. Occluded points are not matched when measuring the objects. Measurement results of nonoverlapping objects should be equivalent for different depth ordering permutations. Given the reference image gr (r < k), the measurement is based on minimizing the mean of squared intensity differences between the current image and the reference region. Under the jth hypothesis, y~'J is
the hypothesized measurement of the mth object, and ek(m) is ,) the corresponding squared difference mean at time k. The ( (I) (2) (M))T . . Th vector ek ,J·ek ,J' ... ,ek,J IS wntten as ek,J. e covariance matrix RkJ is obtained by assuming that the components of the measurement noise are uncorrelated to each other, and the variances is proportional to the corresponding squared difference mean.
3.2 SHM Filter
From a Bayesian perspective, the online tracking problem is to recursively calculate the posterior state space distribution. Given the measurement data up to time k, the probability density function (pdf) of the state is expressed as
the conditional density p(zk I sk = }, y1,k) is modeled as a nonnal distribution N(zk; mkJ· PkJ) under each switching state hypothesis. Thus the pdf p(zk I Y!k) is a mixture of L Gaussians.
At time k+ 1, the set of hypothesized measurements Yk+I becomes available, and it is used to update {fJkJ· mkJ· PkJ} l 5JSL to {/JHJ,;, mk+1,;, Pk+J,;} 15;SL via Bayes' rule.
In principle, the filtering process has three stages: prediction, update, and collapsing [Murphy, 1998]. From (1), (2), (4) and (6), the approximate inference algorithm can be derived in a similar way as that in a Gaussian sum filter [Anderson and Moore, 1979].
From (7) it can be seen that the computation of the SHM filter is slightly more complex than that of multiple Kalman filters or Gaussian sum filters.
3.3 Fast SHM Filter
When occlusion is the main factor in the potential variability of joint tracking, we can assume that the measurement noise under the true occlusion hypothesis is small. When the noise becomes zero, the measurement model can be simplified as
where 80 is the Dirac delta function. minimized mean of squared differences as hypothesized measurement, so that the measurement can be generalized as Consider the a part of the definition of
Assume that ekJ is independent on YkJ and zk. and the posterior density of the squared difference mean is of exponential distribution for each object (More accurate expression could be derived using the x} distribution.) under the true hypothesis, the pdf of ekJ is factorized as
The generalized measurement model now becomes
At time k, the conditional pdf of the state is expressed as
where f3kJ is p(sk = j I Yi:k), and p(zk I sk = J,Yi:d equals ~zk- YkJ). From appendix A, the filtering algorithm is
The state at time k is estimated as
The result { y k,s, } can then be plugged into a Kalman filter to achieve improved performance. Such a SHM Kalman filter keeps the multimodality of the SHM model and has attractive computation requirement. In addition, the collapsing stage is not necessary in the fast SHM filter.
4 Implementation
In practice, we use the second order (constant velocity) model. The hidden state transition function is
where zk is the tracked entity (e.g. position and orientation). The hidden state and state transition matrix can be correspondingly defined. The switching state transition probability is set as
where It is a small positive value (0.1 in this paper) so that two successive switching states are more likely to be of the same label. At the beginning, the reference image gr is set as the initial image g0· When there is a high confidence in nonocclusion, the reference image can be adaptively updated. The objects are assumed to be separated from each other in g0. The initial f3o,~, m0,~, and P0,1 should be equal for
The initial mean m0J is set as a zero vector. The initial covariance matrix P0J is set as diagonal with small variances since the initialization is assumed to be accurate. When an object is totally occluded by the other objects, no points of the target region will be matched. The estimation is based on the result of time k using the state transition function when no visible region of the object is expected at time k+ 1.


should be totally 4! = 24 hypotheses if we directly apply the SHM filter in section 3.2. To reduce the computation, two reasonable assumptions are made to prune less plausible hypotheses. Firstly, one's legs can not simultaneously occlude and be occluded by the other's legs. Secondly, the occlusion relationship between the man and woman can be determined from their bodies. Thus the whole tracking procedure is divided into three trackers. The first one tracks the two bodies of the walkers. According to the detected occlusion relationship, the two shanks of the person in the front are then tracked. At last, the shanks of the other person are tracked in the masked image. Figure 3a shows the results for the four frames of the sequence (circles are marked on the man's body and shanks, and rectangles are marked on the woman). Figure 3b shows the posterior distributions for the horizontal position of the occluded body in figure 3a. l3a.3. When the two bodies are separated, the density is unimodal and of a small variance. The density variance increases when occlusions occur. It becomes multimodal under heavy occlusions. Figure 3c shows the probabilities of the woman's body being in the front. The probabilities for the four frames in figure 3a are circled.
Under realistic environments, it is understandable that comparing with the other hypothesized measurements, the measurement under the true occlusion hypothesis usually shows more regularity and has smaller variances (or squared difference means). Thus, the true information {the switching state and the hidden state) could be enhanced through the propagation. In addition, the acquirement of multiple measurements helps decrease the information loss (e.g. caused by background clutter) during the measurement process.
6 Conclusion
This paper proposes a SHM model for state space representation of dynamic systems and derives two effici.ent filtering algorithms. Our joint tracking approach explicitly
5 Results and Discussion
Test results of two video sequences are shown in our experiments. The state is the position and orientation, ~nd the second order model is employed. Each measurement IS a translation and rotation.
Figure 2 shows the tracking of two hands of a person as they cross several times in an image sequence. Figure 2a shows the three frames of the sequence. Appearance variation of the hands due to pose changes can be seen. Figure 2b and 2c demonstrate the tracking efficacy of the fast SHM filter versus the Kalman filter. The fast SHM filter successfully tracks both hands under different occlusion relationships. In figure 2b, one hand is drawn in black contour when the detected depth order indicates that it is in front of the other hand. The Kalman filter has a similar performance when occlusions are not severe, but poor under heavy occlusions. In figure 2c.3, the distraction from background clutter causes the Kalman tracker to fail. The normalized posterior distributions for the vertical position of the left hand in figure 2a.2 and 2a.3 are shown in figure 2d.l and 2d.2. When the occlusion is not severe, measurements under the two hypotheses are the same, and the distribution is unimodal. Under heavy occlusions, the distribution becomes multimodal since the two hypothesized measurements tend to be different. The measurement under true hypothesis matches the hand correctly, while the measurement under false hypothesis is distracted by background clutter. Figure 2e shows the probabilities of the first occlusion hypothesis (the left hand being in the front) over the first 300 frames. The probabilities for the three frames in figure 2a are circled. The probabilities of the two hypotheses are equal in the nonoverlapping cases, while the probability of the true hypothesis becomes dominant under occlusions.
Figure 3 shows the results of jointly tracking the four shanks of a man and a woman as they cross. The man's right shank has been totally occluded in the sequence. There reasons about the occlusion relationships. The occlusion relationship is quantitatively analyzed throughout the propagation. The information can be used for reference update and further analysis. Moreover, experimental results show that our method helps handle appearance changes and distractions.
The SHM model discusses the measurement switching in dynamic systems. It is complementary to the idea of model switching in [Ghahramani and Hinton, 1998]. Our future study is to effectively combine these two ideas in visual tracking. Furthermore, the SHM model is generally applicable to various dynamic processes in which there are multiple alternative measurement methods.
A Inference in Fast SHM Filter
After receiving the measurement Yk+I, the posterior density is updated using (6).
@inproceedings{ijcai2003p188,
title = {Switching Hypothesized Measurements: A Dynamic Model with Applications to Occlusion Adaptive Joint Tracking},
author = {Wang, Yang and Tan, Tele and Loe, Kia-Fock},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob and Toby Walsh},
pages = {1326--1335},
year = {2003},
url = {https://ijcai.org/proceedings/2003/188},
}
TY - CPAPER TI - Switching Hypothesized Measurements: A Dynamic Model with Applications to Occlusion Adaptive Joint Tracking AU - Wang, Yang AU - Tan, Tele AU - Loe, Kia-Fock T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1326 EP - 1335 UR - https://ijcai.org/proceedings/2003/188 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: