Pedestrian tracking method and pedestrian tracking device

[0001] The present invention relates to a pedestrian tracking method and a pedestrian tracking device for tracking a pedestrian based on images obtained by continuously capturing a pedestrian.

[0002] Conventionally, there is a method and device which automatically tracks the motion of a moving object, particularly motion of a human body, on the basis of image data, and which is used, for example, in the music field and the sports field for ability development based on the analysis and evaluation of motion and for various purposes. For example, a body motion analysis device is known which: extracts human silhouette images from a video image of a dancing examinee input by a computer; detects respective parts of the examinee from the human silhouette images based on color processing; converts the human silhouette images to skeleton images; subjects the skeleton images to Hough transform to approximate the respective parts by lines; and tracks the respective parts in time using a Kalman filter (refer to e.g. Japanese Laid-open Patent Publication 2005-339100).

[0003] The above-described body motion analysis device is a device which subjects Hough parameters having been tracked in time to SVD (Singular Value Decomposition) to detect a motion feature of the body motion, and thereafter Fourier-transforms time-series data of the extracted motion feature for frequency analysis so as to extract and evaluate rhythmic elements of the entire body motion of the examinee.

[0004] Further, in a pedestrian tracking method and a pedestrian tracking device for automatically tracking a pedestrian based on image data, attempts have been made to increase the accuracy and efficiency to suit uses such as accident prevention, surveillance and so on. More specifically, a more secure and faster pedestrian tracking method or device without malfunction (mistracking) is required.

[0005] Now, various filter technologies are used as means to process images for estimating the motion of a pedestrian, and associating it with the time direction. A filter is a method or device for outputting an estimate of a desired response to an input signal such as image data. A filter used for pedestrian tracking removes noise from the current input signal with added noise, and outputs a future signal value as the estimate of the desired response. Such future estimation using a filter is called filter prediction.

[0006] For example, a Kalman filter is widely used in the field of object tracking to perform tracking of moving objects in general as used in the above-described patent document (Japanese Laid-open Patent Publication 2005-339100), and is also applied to the pedestrian tracking.

[0007] An outline of tracking using a Kalman filter will be described. A Kalman filter estimates state vector x_t from observation vector y_t sequentially at each time. Here, the subscript t in y_t, x_t and later-described F_t indicates a certain time, while a time one step before the time is indicated by t−1. In other words, observation (e.g. capture of time-series images) is made at respective time intervals (steps). The time notation using these subscripts will be similarly used hereinafter. The observation vector y_t is a vector in observation space which is mathematically defined by observable time-series data. The state vector x_t is a vector in space, called state space, representing the state of a system to essentially determine the observation vector, and is assumed to follow a Gauss-Markov process (refer to e.g. “Applied Kalman Filter” by Toru Katayama, Asakura Publishing Co., 1983).

[0008] Further, a Kalman filter assumes linearity and gaussianity in both the system model equation x_t=F_tx_t−1+G_tv_t which characterizes the transition of the state vector in the time direction, and the observation model equation y_t=H_tx_t+w_t which characterizes the mapping from the state vector to the observation vector. Here, v_t and w_t are Gaussian white noises, called plant noise and observation noise, respectively, while F_t, G_t and H_t are matrices, called state transition matrix, driving matrix and observation matrix, respectively. It is seen from the form of these equations that the observation vector y_t and the state vector x_t have linearity.

[0009] The assumption of gaussianity in each of the above-described models corresponds to setting an assumption of Gaussian distribution in the probability distribution of the state vector x_t in the state space, namely state probability distribution p(x). In the pedestrian tracking, the state probability distribution deviates in some cases from the Gaussian distribution in situations such as presence of occlusion to cause a pedestrian to be temporarily hidden behind, sudden change in velocity of a tracking target (pedestrian), presence of multiple objects similar to the tracking target, and so on. If a Kalman filter is applied in such cases, it means that the state is estimated using a Gaussian distribution as shown in FIG. 36B although a distribution as shown in FIG. 36A, which is different from a Gaussian distribution, is assumed as an actual state probability distribution. Thus, due to the application limit of a Kalman filter which assumes a Gaussian distribution, it is not possible to estimate the state with sufficient accuracy.

[0010] Thus, there has been proposed a tracking method, called CONDENSATION (conditional density propagation), using a Monte Carlo filter which does not assume Gaussianity or linearity (refer to e.g. “Conditional Density Propagation for Visual Tracking” by Michael Isard and Andrew Blake, International Journal on Computer Vision, Vol. 29, pp 5-28(1989)).

[0011] If a Monte Carlo filter is used, a state vector at each time is sequentially estimated based on an observation vector, similarly as in the case where a Kalman filter is used. In the estimation using a Monte Carlo filter, a state probability distribution is generated based on the distribution of particles each with a vector pointing to a point in the state space. Thus, a Monte Carlo filter can handle nonlinear and non-Gaussian type models obtained by generalizing the state space model and the system model in the above-described Kalman filter (refer, for example, to “Introduction to Time Series Analysis” by Genshiro Kitagawa, Iwanami Publishing Company, 2005).

[0012] Thus, it is considered that the CONDENSATION can achieve a highly accurate probabilistic state estimation, namely tracking with less malfunction, even in a situation of presence of occlusion and sudden velocity change where conventional methods e.g. assuming Gaussianity may fail.

[0013] (Outline of Monte Carlo Filter)

[0014] Here, an outline of a Monte Carlo filter will be described. The system model and the observation model in a Monte Carlo filter are expressed by the following equations (1) and (2):

[0015] System Model:
x_t=F(x_t−1,v_t)  (1)

[0016] Observation Model:
y_t=H(x_t,w_t)  (2)

[0017] The state probability distribution p(x_t) of the state vector x_t in the state space can be expressed by a set of N particles {s_t⁽ⁿ⁾, n=1, . . . , N} as in the following equations (3) and (4), where s_t⁽ⁿ⁾ is a vector which an n-th particle has and which points to a point in the state space X, while δ(x) is a delta function:

[0018] $\begin{array}{cc}p\left(x_t\right)\cong \frac{1}{N}\sum _{n=1}^N\delta \left(x_t-s_t^{\left(n\right)}\right)& \left(3\right)\\ \delta \left(x\right)=\{\begin{array}{cc}+\infty & x=0\\ 0& x\ne 0\end{array}& \left(4\right)\end{array}$

[0019] The state probability distribution of a Monte Carlo filter is represented by a discrete density of particles. For example, in the case where the distribution shown in FIG. 37A is a true probability distribution, the probability distribution in a Monte Carlo filter is expressed by the discrete density of particles as shown in FIG. 37B. Thus, a higher number of particles leads to a more accurate representation of the state probability distribution. Any state probability distribution can be represented by such a representation using particles.

[0020] (State Estimation Algorithm Using Monte Carlo Filter)

[0021] Next, a state estimation algorithm using the above-described Monte Carlo filter will be described. FIG. 38 shows a process performed at time steps for N particles s⁽¹⁾,s⁽²⁾, . . . ,s^(N). In this Figure, the horizontal axis is a time axis while the vertical axis represents state space (represented by one dimension). The size of each particle shown by a black circle or a white dashed circle indicates the likelihood (likeliness or possibility of occurrence) of the state. As shown in this Figure, the process using a Monte Carlo filter is a repetition of a three-step process of prediction, measurement and resampling (resetting).

[0022] Based on the above-described repetition of the three-step process, the state probability distribution p(x_t) at time t is sequentially obtained by using observed data and state probability distribution p(x_t−1) at previous time t−1, and the state probability distribution at each time is sequentially estimated. Further, the state probability distribution is flexibly determined without assuming Gaussianity. Thus, the state probability distribution is corrected by the observed data, and the next state probability distribution is obtained by using the corrected state probability distribution, so that the trajectory of a particle in the state space representing a tracking result becomes more true.

[0023] For the respective particles (n=1, . . . , N), the prediction step predicts the following state s′_t⁽ⁿ⁾ according to the process probability density p(x_t|x_t−1=s_t−1⁽ⁿ⁾) (hereafter refer to the above-described “Introduction to Time Series Analysis” by Genshiro Kitagawa).

[0024] For the respective particles, the measurement step calculates the likelihood π_t⁽ⁿ⁾ in the predicted state according to the observation probability density p(y_t|x_t). In other words, this step obtains the similarity (likelihood) between the state of a tracking target model corresponding to the respective particles and the observed data (image of the tracking target) by making a comparison based on properly set comparison method. Here, y_t is an observation vector (observed data) at time t.

[0025] The resampling step repeats the following process (i), (ii) and (iii) N times according to the number of particles N so as to sample a set of particles {s_t⁽ⁿ⁾, n=1, . . . , N} at time t. In other words, this step redistributes (resets) the N particles in the state space by using the likelihood of each particle representing the predicted state to allocate a larger number of particles at locations of particles with a higher likelihood, and allocate a smaller number, or none, of particles at locations of particles with a lower likelihood, so as to determine the state probability distribution at time t which reflects the correction by the observed data.

[0026] (i) Generate a random number u_t⁽ⁿ⁾ ∈[0,1] following uniform distribution;

[0027] (ii) Obtain a natural number i satisfying the following inequality and equation;

[0028] $\begin{array}{cc}\frac{1}{C}\sum _{l=1}^{i-1}{\pi }_t^{\left(l\right)}<u_t^{\left(n\right)}\le \frac{1}{C}\sum _{l=1}^i{\pi }_t^{\left(l\right)}\mathrm{where}& \left(5\right)\\ C=\sum _{l=1}^N{\pi }_t^{\left(l\right)}\left(\mathrm{iii}\right)s_t^{\left(n\right)}=s_t^{\prime \left(i\right)}\mathrm{is}\mathrm{set}.& \left(6\right)\end{array}$

[0029] The state probability distribution p(x_t) of particles at time t is obtained by the above-described three-step process of prediction, measurement and resampling (resetting). When using a Monte Carlo filter, it is necessary, depending on applications, to properly set conditions such as: how to form a state space X, i.e. a model of target and so on; how to make a state transition in the prediction step such as, inter alia, constraint conditions for the transition; what to use as a calculation method, i.e. comparison method, of the likelihood of particles in the measurement step; and so on.

[0030] Next, a contour tracking to track a target using the contour(s) of the target will be described as an example of using CONDENSATION. The contour tracking method models the contour of the tracking target by B-spline curve, and defines a space composed e.g. of the coordinate values of control points of the spline curve as a state space. The motion (transition) of a state vector pointing to a point in the state space is estimated (predicted) using a Monte Carlo filter. In other words, a point in the state space is in one-to-one correspondence with a state of the contour, so that in the state space, the current state moves, i.e. transitions, from a point (state) to another point (state) as time passes. The transition is considered to be probabilistically achieved under certain constraint conditions.

[0031] When predicting the state transition, it is possible to increase the accuracy of prediction by restricting transitionable states in advance, i.e. by constraining the state transition. In the conventional contour tracking using CONDENSATION, the state transition is constrained by pre-learning using principal component analysis. In the following, the state space, state transition and calculation of likelihood in the contour tracking using CONDENSATION will be shown.

[0032] (State Space)

[0033] Approximate a contour of a tracking target by B-spline curve, defining the positions and velocities of control points of the B-spline curve as a state space X.

[0034] (State Transition)

[0035] Use principal component analysis to pre-learn supervised data. When the state space has M dimensions, determine state transition (s_t′−s_t−1) based on a linear combination of the first principal component vector to the L-th principal component vector (L<M) to reduce the degree of freedom from M to L. This constrains the state transition to allow the state to scatter in the direction of the localized supervised data, i.e. to follow the characteristics of the supervised data.

[0036] (Calculation of Likelihood)

[0037] The likelihood π of particles is calculated by comparing the B-spline curve with input image according to the following procedure. First, set base points consisting of K points on the predicted B-spline curve, and set lines extending therefrom in the normal direction and having a length of μ. Next, detect, on each of these lines, an edge (image contour of target portion) which is a feature point of the image, and assume that the distance from the k-th base point to the detected edge is δ_k. The likelihood π of particles in the state space representing the state of the contour is calculated using this δ_k according to the following formula (7):

[0038] $\begin{array}{cc}\pi \propto \exp \left\{-\sum _{k=1}^K\frac{1}{2\mathrm{rK}}{\left(\min \left({\delta }_k,\mu \right)\right)}^2\right\}& \left(7\right)\end{array}$

[0039] The above-described contour tracking using CONDENSATION is applied to the tracking of hand palms and leaves, achieving excellent results. Further, a pedestrian tracking method using a framework of CONDENSATION has been proposed (refer to e.g. “A Bayesian Multiple-Blob Tracker” by Isard and MacCormick, IEEE International Conference on Computer Vision, pp 34-41, 2001).

[0040] However, the application of the contour tracking using CONDENSATION to pedestrian tracking has the following problem. An object such as a pedestrian considerably changes with time in the direction and magnitude of contour transition. It is generally difficult to properly constrain the state transition for the contour of such object, so that the contour tracking using CONDENSATION is not suitable for pedestrian tracking.

[0041] Referring to FIGS. 39A, 39B and 39C, the contour transition of a pedestrian will be described. These Figures show regions of a pedestrian detected by three successive frames in an actual sequence. Between the two pedestrian regions of FIGS. 39A and 39B, there is a significant change in the lower body contour although there is no significant change in the upper body contour. On the other hand, between FIGS. 39B and 39C, there is no significant change in the lower body contour although there is a significant change in the upper body contour. This shows that the contour of a pedestrian changes with time, i.e. transitions in state, in which the changing parts and the magnitude of the change also change with time.

[0042] Further, as described above, the contour tracking using CONDENSATION constrains the state transition based on principal component analysis. Thus, significant effects of constraint can be obtained when the supervised data in the state space is localized in a certain direction. However, there are various contour transitions of a pedestrian, and the supervised data is scattered in distribution with less tendency. It is impossible in principle to properly constrain the state transition for such state space based on principal component analysis. The constraint of the state transition is for the purpose of increasing the accuracy of predicting the state transition. Thus, if the constrain is not possible, an increase in the accuracy of prediction cannot be expected, making it impossible to achieve tracking without malfunction.

[0043] Thus, in order to achieve a robust pedestrian tracking with high stability without malfunction, a feature which allows better stability of the direction and magnitude of the state transition needs to be used instead of the method using contour as a feature so as to increase the accuracy of prediction based on the feature.

[0044] Further, the use of a Monte Carlo filter eliminates the need for assuming Gaussianity as in the case of using a Kalman filter, making it possible to achieve a more robust tracking, so that various tracking methods using this framework have been proposed. However, there has not been proposed a practical method suitable for pedestrian tracking. For example, the pedestrian tracking using CONDENSATION as disclosed in the above-described paper by Isard and MacCormick is used in the case of an image having a large pedestrian region, and performing tracking based on accurate pedestrian models e.g. using three-dimensional information, and is not suitable for practical use in which it is required to be adapted to an image with a small pedestrian region.

[0045] Further, in pedestrian tracking for surveillance applications, a grey scale image with a large dynamic range is used, and in addition an infrared camera is considered to be used. Thus, a tracking method which does not use color information is desired in order to enable pedestrian tracking adapted to such situations.

[0046] An object of the present invention, to solve the problems described above, is to provide a pedestrian tracking method and a pedestrian tracking device with a simple structure for predicting the motion of a pedestrian in images without using color information, making it possible to achieve a robust pedestrian tracking.

[0047] In order to achieve the above object, the present invention provides a pedestrian tracking method provided in time series with a certain pedestrian region appearing in images captured continuously in time for predicting and associating motion of the pedestrian region with time direction by use of a Monte Carlo filter so as to track the pedestrian region, comprising the steps of: building a skeleton model of a pedestrian model with multiple nodes and multiple sticks connecting the nodes, and defining, in a state space of a multidimensional space representing points in one-to-one correspondence with states of the skeleton model, particles at the points provided with realization probability attributes of the states represented by the points of the state space, and further setting multiple particles of the skeleton model as an initial state in the state space; predicting, for a set of particles set in the state space at a first time, a set of particles representing a state at a second time after the first time using Monte Carlo filter method; converting a pedestrian region given at the second time to a binary image, and subjecting the binary image to distance transform so as to generate observed data comprised of the distance-transformed image; comparing each skeleton model predicted in the prediction step with the distance-transformed image so as to calculate a likelihood of each state of the skeleton model at the second time; and sampling a set of particles of the skeleton model in the state space based on the respective likelihoods of the skeleton model calculated in the above step, and setting the sampled set of particles as a new set of particles in the state space at the second time, wherein the pedestrian region is tracked by performing, at each time increment, the steps from the above step of predicting the set of particles to the step of setting the sampled set of particles as the new set of particles so as to predict and associate, with time direction, the motion of the particles of the skeleton model in the state space.

[0048] According to such a structure, a Monte Carlo filter is used, and a skeleton model is used as a model of a pedestrian. Thus, it is possible to achieve more robust tracking, following changes with time of the shape of a pedestrian region in an image, than when using a contour model of the pedestrian. More specifically, the skeleton model can model the trunk and limbs of the pedestrian, so that in contrast to the use of contour, the changes of the shape of the skeleton model can be constrained based on the structural constraints of the trunk and limbs of a human body. Thus, the state transition of the skeleton model in the state space can be reliably and rationally constrained. The imposition of such constraints improves the reliability of tracking, enabling a robust pedestrian tracking.

[0049] Further, since a distance-transformed image obtained by transforming a binary image of a pedestrian region is used as a comparison for calculating the likelihood, it is possible to calculate the likelihood more accurately. More specifically, the distance-transformed image of the pedestrian region reflects the state of the limbs of the pedestrian which appear on the outer shape of the pedestrian region, and thus is suitable as observed data to be compared with the skeleton model, making it possible to calculate the likelihood with high accuracy. Further, since a binarized image is used, it is not necessary to use color information of the image, enabling an accurate and robust pedestrian tracking even when applied to pedestrian tracking for surveillance e.g. using infrared images at night.

[0050] According to the present invention, it is preferable in the improved invention described above that the skeleton model is built of eight sticks consisting of: a trunk stick; a shoulder stick intersecting and connected to an upper end of the trunk stick; a waist stick intersecting and connected to a lower end of the trunk stick; a head stick as an extension of the trunk stick; and four limb sticks connected to both ends of the waist stick and the shoulder stick, respectively.

[0051] According to such structure, it is possible to easily build a skeleton model properly reflecting the characteristic structure of a human body. Further, an appropriate, not excessive, number can be selected as a number of variables representing a state of the skeleton model, so that the number of state variables can be reduced, making it possible to reduce the number of transitional states, and thus to increase the tracking accuracy.

[0052] According to the present invention, it is preferable in the improved invention as described above that the skeleton model can have a state with zero length of the shoulder and waist sticks, a state with zero length of the shoulder, waist and both hand sticks, and a state with zero length of the shoulder and both hand sticks.

[0053] According to such a structure, a skeleton model can be selected by reflecting the moving direction of the pedestrian appearing in the images. For example, a pedestrian moving left or right in the images is walking, showing one side of the body, with the shoulder width or the waist width being hardly recognized. Thus, the skeleton model with zero length of the shoulder stick and the waist stick is suitably used.

[0054] According to the present invention, it is preferable in the improved invention as described above that a state of the skeleton model is determined by positions and angles of the respective sticks, which build the skeleton model, and is constrained so that mutual spatial arrangement of the sticks is a spatial distribution which is possible in human body structure.

[0055] According to such a structure, the mutual spatial arrangement of the mutually connected sticks is constrained by the positions and angles of the respective sticks so as to be a spatial distribution which is possible in human body structure. Thus, it is possible to constrain the state transition of the skeleton model by constraining and preventing the changes in the appearance of a pedestrian from being unnatural.

[0056] According to the present invention, it is preferable in the improved invention as described above that the distance-transformed image used in the step of likelihood calculation is an image represented by a black and white density such that its intensity increases as its position shifts from a black contour part representing the pedestrian region to the inside of the contour, wherein the likelihood of the predicted skeleton model is calculated, with the distance-transformed image being superimposed on the skeleton model, by using a distance from each of the multiple points on the sticks building the skeleton model to a maximum intensity point of the distance-transformed image present on a normal of each stick at the each point.

[0057] According to such a structure, the likelihood of each estimated skeleton model can be calculated with high accuracy, because both the sticks of the skeleton model and the high intensity portions of the distance-transformed image reflect the bone structure of a human body, and the degree of their superimposition can be estimated by the distance to the maximum intensity point. For example, as the sum of the distances to the maximum intensity points decreases, the degree of superimposition increases, increasing the likelihood.

[0058] According to the present invention, it is preferable in the improved invention as described above that random numbers are used in the step of predicting the set of particles and the step of setting the new set of particles, and the random numbers are generated using a pseudo-random number generation algorithm.

[0059] According to such a structure, the random numbers generated using a pseudo-random number generation algorithm have characteristics of long-period and high dimensional uniform distribution, and thus are suitable for a Monte Carlo filter, making it possible to achieve highly accurate pedestrian tracking.

[0060] According to the present invention, it is preferable in the improved invention as described above that the pedestrian tracking method further comprises a step of calculating a variance of coordinates of a node between trunk stick and head stick, and ending the tracking if such variance exceeds a certain value.

[0061] According to such a structure, it is possible to determine from the variance of the coordinates of the node that even if a non-pedestrian is erroneously extracted as a pedestrian region, the tracking target is not a pedestrian, and thus to end the mistracking.

[0062] Further, the present invention provides a pedestrian tracking device comprising: image receiving means for receiving, in time series, images captured continuously in time; pedestrian region selecting means for sampling candidate pedestrian regions from an image received by the image receiving means, and classifying the sampled candidate pedestrian regions into pedestrian regions and non-pedestrian regions, and for selecting a certain pedestrian region; tracking means provided in time series with the pedestrian region selected by the pedestrian region selecting means for predicting motion of the pedestrian region by use of the pedestrian tracking method according to any one of claims 1 to 7 so as to track the pedestrian region; and pedestrian trajectory display means for displaying, in time series, the pedestrian region tracked by the tracking means.

[0063] According to such a structure, it is possible to achieve a robust pedestrian tracking with a simple structure for predicting the motion of a pedestrian in images without using color information even in situations such as presence of occlusion to cause a pedestrian to be temporarily hidden behind, sudden change in velocity of a pedestrian, presence of multiple objects similar to the pedestrian of interest, and so on, making it possible to automatically track the motion of a human, analyze its intention and motion, and monitor intruders.

[0103] Hereinafter, a pedestrian tracking device and a pedestrian tracking method according to an embodiment of the present invention will be described with reference to the drawings.

[0104] (Pedestrian Tracking Device)

[0105] FIG. 1 shows a block diagram of a pedestrian tracking device 1 according to an embodiment of the present invention, while FIG. 2 shows a process flow in the pedestrian tracking device 1. The pedestrian tracking device 1 comprises: an image receiving means 2 for receiving, in time series, images captured continuously in time by an image capturing device 10; a pedestrian region selecting means 3 for sampling candidate pedestrian regions from an image received by the image receiving means 2 and classifying the sampled candidate pedestrian regions into pedestrian regions and non-pedestrian regions, and for selecting a certain pedestrian region; a tracking means 4 provided in time series with the pedestrian region selected by the pedestrian region selecting means 3 for predicting motion of the pedestrian region and associating it with time direction by use of a skeleton model obtained by modeling a pedestrian, a distance-transformed image obtained from the pedestrian region and a Monte Carlo filter so as to track the pedestrian region; and a pedestrian trajectory display means 5 for displaying, in time series, the pedestrian region tracked by the tracking means 4.

[0106] The process in the above-described pedestrian tracking device 1 comprises four major process elements: one-frame image input (S1) by the image receiving means 2; candidate pedestrian region sampling (S2) by the pedestrian region selecting means 3; candidate region classification (S3) by the same pedestrian region selecting means 3; and pedestrian state prediction (pedestrian tracking) (S4) by the tracking means 4.

[0107] The above-described image capturing device 10 e.g. uses a television camera using an image sensor and so on. The image receiving means 2 receives an image input from the image capturing device 10, and subjects the image to proper preprocesses such as noise removal and contour emphasis, and inputs the processed image to the pedestrian region selecting means 3.

[0108] The pedestrian region selecting means 3 subjects the input image to processes such as background subtraction method, optical flow detection, three-dimensional distance measurement by stereo matching, flesh color detection, face contour detection and so on, and then samples candidate pedestrian regions from the image which are assumed to be image portions showing an entire body image of the pedestrian. The sampled candidate pedestrian regions usually include many misdetected regions. Thus, the pedestrian selecting means 3 classifies the sampled candidate regions into pedestrian regions and non-pedestrian regions. This classification is performed, for example, by machine learning based on neural network, support vector machine or boosting, and by a process based on a feature of an image as obtained by Haar transform, Gabor transform or the like.

[0109] The tracking means 4 performs tracking which, based on the pedestrian regions classified as pedestrians, associates a pedestrian region with time direction. More specifically, the above-described sampling and classification of candidate pedestrian regions by the pedestrian region selecting means is generally performed for each frame, namely, independently for each image, so that none of the pedestrian regions in this process is associated with, or can be associated with the time direction. Thus, the tracking means 4 associates a pedestrian region with the time direction. This process by the tracking means 4 is performed based on a pedestrian tracking method described later.

[0110] The main purpose of the pedestrian tracking by the tracking means 4 is to estimate information of pedestrian motion, and associate a pedestrian region with time direction. The pedestrian tracking makes it possible to estimate the pedestrian motion in the case where a pedestrian cannot be detected from one image, for example, due to an effect of the so-called occlusion in which a pedestrian overlaps another object, preventing image information of the pedestrian from being obtained. Information obtained by the pedestrian tracking can be used e.g. in a process for detecting collision of a camera-equipped car with a pedestrian, and a process for identifying and tracking a certain pedestrian in a situation where there are many pedestrians present.

[0111] (Outline of Pedestrian Tracking Method)

[0112] FIG. 3 shows a flow chart of a process in a pedestrian tracking method according to an embodiment of the present invention, and FIG. 4 shows a state space X used in the pedestrian tracking method, while FIG. 5 shows a relation between images and pedestrian models in the pedestrian tracking method. The pedestrian tracking method is a method provided in time series with a certain pedestrian region each appearing in images captured continuously in time for predicting motion of the pedestrian region and associating the motion of the pedestrian region with time direction by use of a Monte Carlo filter so as to track the pedestrian region. This method is performed by the tracking means 4 in the above-described pedestrian tracking device 1.

[0113] As shown in FIG. 3, the pedestrian tracking method comprises an initial setting step (S12), a state transition and prediction step (S13), an observed data generation step (S15), a likelihood calculation step (S16), a particle resetting step (S17) and so on.

[0114] First, a time variable t is initialized (t=0) in step S1, and then the initial setting step (S12) is performed.

[0115] The initial setting step (S12) is a step of: building skeleton models each of a pedestrian with multiple nodes and multiple sticks connecting the nodes; defining, in a state space X of a multidimensional space representing points in one-to-one correspondence with states of skeleton models, particles at the points provided with realization probability attributes of states represented by the points of the state space X; and setting multiple particles of skeleton models as an initial state in the state space X.

[0116] The state transition and prediction step (S13) is a step to predict, for a set of particles set in the state space X at a first time, a set of particles representing a state at a second time after the first time using Monte Carlo filter method. After this step, the time variable t is advanced by one, namely t=t+1 (increment).

[0117] The observed data generation step (S15) is a step of converting a pedestrian region given at the second time to a binary image, and subjecting the binary image to distance transform so as to generate observed data comprised of the distance-transformed image.

[0118] The likelihood calculation step (S16) is a step of comparing each predicted skeleton model with the distance-transformed image (observed data) provided using distance transform so as to calculate a likelihood of the state of each skeleton model at the second time.

[0119] The particle resetting step (S17) is a step of sampling a set of particles of skeleton models in the state space X based on the likelihoods of the respective skeleton models, and setting the sampled set of particles as a new set of particles in the state space X at the second time.

[0120] The pedestrian tracking is achieved by performing, at each time increment, the steps from the above-described step (S13) of predicting the set of particles to the step (S17) of setting the sampled set of particles as the new set of particles. In other words, the above-described respective steps predict the motion of the particles of the skeleton models in the state space and associate it with time direction, so as to track the pedestrian region, thus performing tracking.

[0121] (Probabilistic Tracking)

[0122] The above-described steps S13, S15 and S16 are based on the so-called CONDENSATION framework for probabilistically tracking a pedestrian by using a Monte Carlo filter. This framework (method) is effective for pedestrian tracking in a situation of disordered and complex background image or image of a pedestrian itself, if the state space X is properly set, that is, setting a proper pedestrian model, setting a proper state transition model and proper setting for constraining the state transition. In other words, this enables robust tracking which is robust to occlusion of a target object or pedestrian, sudden change in velocity of the pedestrian, and so on.

[0123] Referring to FIG. 4, the pedestrian tracking using a Monte Carlo filter corresponds to probabilistically finding a trajectory tr of a point which represents a pedestrian model in the state space X and moves (state transition) with time t. The points representing a pedestrian model in the state space X at each time t are distributed according to a probabilistic distribution, in which the trajectory tr connecting, in time, points with the highest probability of presence is the tracking result. Thus, referring to FIG. 5, an image G of a pedestrian region in real space corresponds to particles in the state space X which represent pedestrian models M₁, M₂, . . . M_N (refer to FIGS. 37A, 37B, 38 and the description of these Figures in the Background Art).

[0124] An increase in the number of pedestrian models N, i.e. the number of particles N representing the state probability distribution, causes an increase in the calculation amount, but can increase the approximation accuracy. In other words, it is possible to easily satisfy system requirements such as accuracy by selecting a proper number N according to the application.

[0125] (Use of Skeleton)

[0126] A change with time of the skeleton (bone structure) of a pedestrian used as a pedestrian model is more stable than the contour of the pedestrian, showing a stable state transition in time direction. Thus, the state space X based on the skeleton is a proper setting for the pedestrian tracking. In other words, the use of a skeleton increases the likelihood that the next state predicted from the current state is close to the true value, enabling highly accurate pedestrian tracking.

[0127] (Constraint on State Transition)

[0128] If a target to be tracked is restricted to a pedestrian, accurate pedestrian tracking can be achieved without pre-learning the target by expressing the pedestrian using a skeleton and by constraining the state transition. For example, it is considered that a skeleton causing a stick representing a leg to intersect a stick representing the neck occurs with an extremely low occurrence probability. A prediction of state closer to a true value can be achieved by removing states with a low occurrence probability from the destination of the state transition. More specifically, this can be done by constraining the state transition such that among possible states of the skeleton model when simply connecting the nodes and the sticks, those states with a low occurrence probability are removed in advance from the destination of the state transition. This shows that when using the skeleton, it is possible to more properly and more effectively constrain the state transition than when using the contour.

[0129] (Calculation of Likelihood Using Distance-Transformed Image)

[0130] As described in the Background Art, the contour tracking using CONDENSATION is based on model curve (B-spline curve) of the contour and the contour edge of an image so as to calculate the likelihood of model curve particles in a state space. In the above-described steps S15 and S16, this concept is applied to the pedestrian tracking (in which the skeleton corresponds to the contour, and the distance-transformed image corresponds to the contour edge). A binary image having a candidate pedestrian region in white is distance-transformed, and the image generated thereby is used as observed data y_t to be input to a Monte Carlo filter.

[0131] (Random Number Generation)

[0132] A pseudo-random number generation algorithm (Mersenne Twister: introduced by Makoto Matsumoto and Takuji Nishimura in 1997) is used to generate random numbers used in the above-described state transition and prediction step S13 and the step S17 for resampling and setting a new set of particles. The random numbers generated thereby have characteristics of long-period and high dimensional uniform distribution, and are random numbers suitable for a Monte Carlo filter, making it possible to achieve highly accurate pedestrian tracking.

[0133] (Process Flow of Pedestrian Tracking)

[0134] A process flow of pedestrian tracking using a Monte Carlo filter is summarized below, including mathematical expressions. FIG. 6 shows a concept of pedestrian tracking based on the Monte Carlo filter in the pedestrian tracking method, and corresponds to FIG. 38 described in the Background Art.

[0135] First, a state probability distribution p(x₀) is generated by adding noise to a given initial state vector x₀ (S12 in FIG. 3). Next, a Monte Carlo filter is used at time t (t=1, 2, . . . ) to estimate p(x_t) from p(x_t−1). The prediction is achieved by repeating the three steps of prediction, measurement and resampling.

[0136] (Prediction) A state transition is performed by using a skeleton model and constraining the state transition. For respective particles s_t−1⁽ⁿ⁾ (n=1, . . . . ,N), the next state s′_t⁽ⁿ⁾ is predicted according to the process probability density p(x_t|x_t−1=s_t−1⁽ⁿ⁾) (S13 in FIG. 3).

[0137] (Measurement) The likelihood of each predicted particle is calculated by comparing each particle with distance-transformed image. More specifically, for each particle, the likelihood π_t⁽ⁿ⁾ of the predicted state is calculated according to the observation probability density p(y_t|x_t) (S15, S16 in FIG. 3). Here, y_t is an observation vector (observed data, i.e. vector in observation space representing distance-transformed image) at time t.

[0138] (Resampling) Random numbers are generated, and the generated random numbers are used to determine a likelihood so as to sample, based on inequality (5) and equation (6) described in the Background Art, a predicted state from the next state s′_t⁽ⁿ⁾ predicted as above. By repeating it N times, which is the number of particles, a set of particles {s_t⁽ⁿ⁾,n=1, . . . ,N} at time t is sampled, and is set as a set of particles at time t (S17 in FIG. 3). Based on these processes, the state probability distribution p(x_t) at each time t (t=1, 2, . . . ) is finally obtained. Based on the obtained state probability distribution at each time, a trajectory tr in the state space X is determined as shown in FIG. 4 described above. This is the tracking result.

[0139] As described above, the likelihood of each particle representing the predicted state is used to allocate a larger number of particles at locations of particles with a higher likelihood, and allocate a smaller number, or none, of particles at locations of particles with a lower likelihood so as to resample the N particles in the state space and redistributes (resets) these particles, whereby the state probability distribution p(x_t) at each time t (t=1, 2, . . . ) reflecting the correction by the observed data is determined.

[0140] The pedestrian tracking method according to the embodiment of the present invention uses a Monte Carlo filter and a skeleton model as a model of a pedestrian. Thus, it is possible to achieve more robust tracking, following changes with time of the shape of a pedestrian region in an image, than when using a contour model of the pedestrian. More specifically, the skeleton model can model the trunk and limbs of the pedestrian, so that in contrast to the use of contour, the changes of the shape of the skeleton model can be constrained based on the structural constraints of the trunk and limbs of a human body. Thus, the state transition of the skeleton model in the state space can be reliably and rationally constrained. The imposition of such constraints improves the reliability of tracking, enabling a robust pedestrian tracking.

[0141] Further, since a distance-transformed image obtained by transforming a binary image of a pedestrian region is used as a comparison for calculating the likelihood, it is possible to calculate the likelihood more accurately. More specifically, the distance-transformed image of the pedestrian region reflects the state of the limbs of the pedestrian which appear on the outer shape of the pedestrian region, and thus is suitable as observed data to be compared with the skeleton model, making it possible to calculate the likelihood with high accuracy. Further, since this pedestrian tracking method uses a binarized image, it is not necessary to use color information of the image, enabling an accurate and robust pedestrian tracking when applied to pedestrian tracking for surveillance e.g. using infrared images at night.

[0142] Hereinafter, the individual element technologies and processes in the pedestrian tracking method, i.e. skeleton model, state space X, state transition model and calculation method of likelihood π_t⁽ⁿ⁾, will be described in detail.

[0143] (Validity of Skeleton Model of Pedestrian)

[0144] FIGS. 7A1 to 7A3 show examples of images of pedestrian regions to be processed by the pedestrian tracking method, and FIGS. 7B1 to 7B3 show morphological skeletons obtained from the images, while FIGS. 7C1 to 7C3 show states in which the concept of limbs is reflected in the morphological skeletons. Here, examples of morphological skeletons as so-called morphological images, which are obtained by subjecting the images of pedestrian regions to image processing, are shown to explain the validity of modeling a pedestrian using sticks.

[0145] A morphological skeleton of a pedestrian is obtained by the following process. Assume that I_b is a discrete binary image (FIGS. 7A1 to 7A3), and P is a binary pattern containing the origin (0,0). Now, consideration is given by fixing P. Assuming M=max{i≧0; I_b⊚iP≠φ}, each S_i defined by S_i=(I_b⊚iP)−(I_b⊚iP)⋄P is referred to as a skeleton element. Here, A⊚B is an erosion of A by B, and A⋄B represents an opening of A by B, while (A⊚kB) represents an erosion repeated k time as defined by the following equation: (A⊚kB)=( . . . (A⊚B)⊚B⊚ . . . )⊚B.

[0146] A morphological skeleton SK(I_b) is defined as a union of all S_i as in the following equation (8). Thus, the morphological skeleton SK(I_b) as shown in FIGS. 7B1 to 7B3 is uniquely obtained from each binary image.

[0147] $\begin{array}{cc}\mathrm{SK}\left(I_b\right)=\underset{i=0}{\bigcup ^M}{S}_i& \left(8\right)\end{array}$

[0148] When the knowledge that the skeleton of a pedestrian has “four branches at the neck position” and “three branches at the waist position” is applied to the above-described morphological skeleton SK(I_b), the state of the bone structure of the pedestrian becomes clearer as shown in FIGS. 7C1 to 7C3. Conversely, it is possible to stably predict changes in the state of the pedestrian between the images by considering the bone structure of a human.

[0149] It is seen from the above that the state transition of the skeleton model enables easier prediction than the state transition of the pedestrian contour. More specifically, the state transition of a skeleton is more stable in time direction than the state transition of a contour, so that the predicted next state is closer to a true value. Thus, a more robust pedestrian tracking can be achieved by using, as state space X, a space consisting of parameters representing a skeleton model of a pedestrian.

[0150] (Skeleton Model Building)

[0151] FIGS. 8A to 8D show skeleton models used in the pedestrian tracking method. As the precision of modeling a bone structure of a pedestrian is increased, finer elements can be considered in the likelihood calculation, so that the accuracy of the likelihood calculation can be expected to increase. However, an excessive precision causes an increase in the number of parameters for the state expression which in turn increases the degree of freedom in the state transition, resulting in a decrease in the percentage of particles which transition to a state closer to the true value. In other words, the accuracy of likelihood calculation and the accuracy of state transition are in a trade-off relationship.

[0152] Thus, as shown in FIG. 8C, in the pedestrian tracking method according to the present embodiment, a skeleton model is built by eight sticks consisting of: a trunk stick; a shoulder stick intersecting and connected to an upper end of the trunk stick; a waist stick intersecting and connected to a lower end of the trunk stick; a head stick as an extension of the trunk stick; and four limb sticks connected to both ends of the waist stick and the shoulder stick, respectively.

[0153] The skeleton model of a pedestrian using eight sticks as shown in FIG. 8C described above makes it possible to easily build a skeleton model properly reflecting the characteristic structure of a human body. Further, an appropriate, not excessive, number can be selected as a number of variables representing a state of the skeleton model, so that the number of state variables can be reduced, making it possible to reduce the number of transitional states, and thus to increase the tracking accuracy.

[0154] In addition, it is set that the state of the skeleton model is further restricted so that it can have a state as shown in FIG. 8A with zero length of the shoulder and waist sticks, a state as shown in FIG. 8B with zero length of the shoulder, waist and both hand sticks, and a state as shown in FIG. 8C with zero length of the shoulder and both hand sticks.

[0155] The skeleton model with the above-described restriction suppresses an increase in the degree of freedom in the state transition, and reflects the moving direction of the pedestrian appearing in the images. For example, a pedestrian moving left or right in the images is walking, showing one side of the body, with the shoulder width or the waist width being hardly recognized. Thus, the skeleton model with zero length of the shoulder stick and the waist stick is suitably used. Note that in the following, the multiple nodes and the multiple sticks connecting the nodes, which build a skeleton model, are each expressed by stick ST_pq connecting node p and node q.

[0156] When expressing a pedestrian by sticks as described above, a skeleton model as shown in FIG. 8A, which is built of six sticks representing the limbs, waist and head, can be considered. This is referred to as skeleton model (a). When detecting pedestrian regions from actually captured images, it may occur that hand regions are not detected if the resolution is low, or a hand overlaps the trunk. In this case, the skeleton model (a) makes it impossible to properly calculate elements originating from ST_bd and ST_bf at the time of the likelihood calculation, thereby lowering the accuracy of the likelihood calculation.

[0157] Thus, a skeleton model (b) as shown in FIG. 8B is set which is built of four sticks by removing ST_bd and ST_bf from the skeleton model. This makes it possible to reduce the degree of freedom as compared with the skeleton model (a), and increases the accuracy of the likelihood calculation in a situation that the hands are not detected. This means that either one of the skeleton models can be selectively used, depending on the situation, for example, whether the hand (arm) regions are detected. Further, when the pedestrian is showing its side in the images, that is walking left or right, the shoulder width is hardly recognized, so that the skeleton models (a) and (b) make it possible to obtain sufficient calculation accuracy.

[0158] Now, when the pedestrian is showing its front or back in the images, that is walking up or down, or in the front direction, the shoulder width and the waist width are recognized. Specifically, this causes the node b of the arm stick and the node g of the leg stick to be respectively offset by the width of the trunk, causing the likelihood calculated using the skeleton models (a) and (b) to contain a large error. Thus, shoulder stick ST_ce and waist stick ST_hj are added to the skeleton models (a) and (b), respectively, to build skeleton models (c) and (d). By using such models, the calculation accuracy can be increased.

[0159] As described above, an optimum model in the skeleton models (a) to (d) depends on the characteristics of the image sequence (hereafter referred to as sequence) which is a target of the pedestrian tracking. Thus, by appropriately selecting a model from these skeleton models (a) to (d) according to the orientation or the moving direction of a pedestrian in the images, a highly accurate pedestrian tracking can be achieved. Such model is referred to here as an adaptive skeleton model, and will be described in the Examples.

[0160] (Setting of State Space X)

[0161] Next, state space X to describe the states of the skeleton models described above will be described. FIG. 9 shows a coordinate system for defining stick coordinates of a skeleton model used in the pedestrian tracking method.

[0162] The state space X is a multidimensional space represented by vectors each formed by characteristic points of a pedestrian, and is defined based on variables (parameters) representing a skeleton model obtained by modeling the pedestrian using a skeleton. It is desirable that the state space X is based on a model with appropriate degree of freedom, not too high and not too low, in order to accurately predict the state transition. Thus, the state space X is set for the four patterns of skeleton models (a) to (d) built of four to eight sticks as described above.

[0163] In order to represent the shape of a skeleton model by coordinates, an image coordinate system fixed to the time-series images as targets for pedestrian tracking is used as an absolute coordinate system. A state of a pedestrian occupies a point in the state space X based on a set of values of parameters (variables) representing the respective sticks.

[0164] Thus, each of the skeleton models (a) to (d) is expressed by parameters so as to make a state of the pedestrian correspond to a point in the state space X. An xy coordinate system as an image coordinate system (absolution coordinate system) is set as shown in FIG. 9, in which the coordinate of a node p (p=a,b, . . . ) in the xy coordinate system is set as (x_p,y_p). Several methods can be considered as methods of expressing a skeleton model in the state space X. For example, as in state space X_abs represented by the following equation (9), the state space X can be defined by using the absolute coordinates, as is, of the respective nodes of a skeleton. Here, the capital letter X represents state space, and the equal sign with three lines indicates that the equation is a defining equation, while the parentheses { } represents a vector with the variables (parameters) in the parentheses as components, and the superscript T of the parentheses { } denotes transposition of vector or matrix:
X_abs≡{x_a,y_a,x_b,y_b, . . . }^T  (9)

[0165] However, the state space expressed by the above equation (9) is inconvenient for easy removal of impossible states of a skeleton of the pedestrian which include, for example, a state in which the head and the trunk move in separate directions. Thus, a single point of the nodes with absolute coordinates is specified, and this point is set as a reference point (base point) so as to express the other nodes by relative coordinates from the base point. As shown in the following equations (10) to (12), the relative coordinates are expressed by a rectangular image coordinate system using the base point as the origin. Here, (x_base,y_base) are absolute coordinates of the base point, while x_p′,y_p′ are relative coordinates of node p given by equations (11) and (12), respectively. The space represented by such coordinate system is defined as X_rel:
X_rel≡{x_base,y_base,x′_a,y′_a,x′_b,y′_b, . . . }^T  (10)
x′_p=x_p−x_base  (11)
y′_p=y_p−y_base  (12)

[0166] By using the state space X_rel, it becomes easy to individually adjust the noise variance to control transition of the relative coordinates and the noise variance to control transition of the absolute coordinates at the time of the state transition, making it possible to easily restrict the above-described possibility of motions of the head and the trunk in separate directions.

[0167] The state space X_rel according to the above-described equation (10) is further improved to define state equation X_pol using a relative coordinate system based on the lengths and angles of the respective sticks. This is based on the principle that when the position of the node g of the waist is fixed, the position of the toe of a leg is likely to be on the circumference of a circle with a center at the waist and a radius equal to the length of the leg. The state equation X_pol can easily express constraints on the state transition. The state equation X_pol can be expressed by the following equation (13). Here, the length l_pq and angle a_pq are defined by equations (14) and (15), respectively, as shown in FIG. 9.

[0168] $\begin{array}{cc}{X}_{\mathrm{pol}}\equiv {\{x_{\mathrm{base}},y_{\mathrm{base}},l_{\mathrm{ab}},l_{\mathrm{bg}},\dots ,a_{\mathrm{ab}},a_{\mathrm{bg}},\dots \}}^T\mathrm{where}\begin{array}{cc}{l}_{\mathrm{bd}}=l_{\mathrm{bf}}& \left[\mathrm{Skeleton}\mathrm{model}\left(a\right)\right]\\ l_{\mathrm{gi}}=l_{\mathrm{gk}}& \left[\mathrm{Skeleton}\mathrm{model}\left(a\right),\left(b\right)\right]\\ l_{cd}=l_{\mathrm{ef}}& \left[\mathrm{Skeleton}\mathrm{model}\left(c\right)\right]\\ l_{\mathrm{hi}}=l_{\mathrm{jk}}& \left[\mathrm{Skeleton}\mathrm{model}\left(c\right),\left(d\right)\right]\\ l_{\mathrm{ce}}=l_{\mathrm{hj}}& \left[\mathrm{Skeleton}\mathrm{model}\left(c\right)\right]\\ a_{\mathrm{ce}}=a_{\mathrm{jn}}=0& \left[\mathrm{skeleton}\mathrm{model}\left(c\right),\left(d\right)\right]\end{array}& \left(13\right)\\ l_{\mathrm{pq}}=\sqrt{{\left(x_p-x_q\right)}^2+{\left(y_p-y_q\right)}^2}& \left(14\right)\\ a_{\mathrm{pq}}={\tan }^{-1}\frac{y_p-y_q}{x_p-x_q}& \left(15\right)\end{array}$

[0169] In the above, the state spaces X_abs, X_rel and X_pol according to the three expressions have been described. Hereinafter, a description will be given using the state space X_pol with the node b of the neck as a base point. Assuming the use of the state space X_pol, state space X_(i),(i=a,b,c,d), which corresponds to each of the four skeleton models (a) to (d), can be expressed by the following equations (16), (17), (18) and (19). The numbers of dimensions of the state spaces are twelve dimensions, nine dimensions, fourteen dimensions and ten dimensions, respectively. The number of dimensions corresponds to the degree of freedom in the state transition.
X_(a)≡{x_b,y_b,l_ab,l_bd,l_bg,l_gi,a_ba,a_bd,a_bf,a_bg,a_gi,a_gk}^T  (16)
X_(b)≡{x_b,y_b,l_ab,l_bg,l_gi,a_ba,a_bg,a_gi,a_gk}^T  (17)
X_(c)≡{x_b,y_b,l_ab,l_cd,l_hi,l_hj,l_bg,l_ce,a_ba,a_cd,a_ef,a_bg,a_hi,a_jk}^T  (18)
X_(d)≡{x_b,y_b,l_ab,l_hi,l_bg,l_hj,a_ba,a_bg,a_hi,a_jk}^T  (19)

[0170] Such state space X_(i), is required to be uniquely transformable to the absolute coordinate space X_abs for likelihood calculation described later. It is seen that in the case of the skeleton model (a), this can be achieved by the following equation (20). The coordinate transformation can be similarly performed for the other skeleton models (b), (c) and (d).

[0171] $\begin{array}{cc}{X}_{\mathrm{ab}s}=\left[\begin{array}{c}{x}_a\\ y_a\\ x_b\\ y_b\\ x_d\\ y_d\\ x_f\\ y_f\\ x_g\\ y_g\\ x_i\\ y_i\\ x_k\\ y_k\end{array}\right]=\left[\begin{array}{c}{x}_b+l_{\mathrm{ab}}*\cos \left(a_{\mathrm{ba}}\right)\\ y_b+l_{\mathrm{ab}}*\sin \left(a_{\mathrm{ba}}\right)\\ x_b\\ y_b\\ x_b+l_{\mathrm{bd}}*\cos \left(a_{\mathrm{bd}}\right)\\ y_b+l_{\mathrm{bd}}*\sin \left(a_{\mathrm{bd}}\right)\\ x_b+l_{\mathrm{bd}}\cos \left(a_{\mathrm{bf}}\right)\\ y_b+l_{\mathrm{bd}}*\sin \left(a_{\mathrm{bf}}\right)\\ x_b+l_{\mathrm{bf}}*\cos \left(a_{\mathrm{bg}}\right)\\ y_b+l_{\mathrm{bg}}*\sin \left(a_{\mathrm{bg}}\right)\\ x_b+l_{\mathrm{bg}}*\cos \left(a_{\mathrm{bg}}\right)+l_{\mathrm{gi}}*\cos \left(a_{\mathrm{gi}}\right)\\ x_b+l_{\mathrm{bg}}*\sin \left(a_{\mathrm{bg}}\right)+l_{\mathrm{gi}}*\sin \left(a_{\mathrm{gi}}\right)\\ x_b+l_{\mathrm{bg}}*\cos \left(a_{\mathrm{bg}}\right)+l_{\mathrm{gi}}*\cos \left(a_{\mathrm{gk}}\right)\\ x_b+l_{\mathrm{bg}}*\sin \left(a_{\mathrm{bg}}\right)+l_{\mathrm{gi}}*\sin \left(a_{\mathrm{gk}}\right)\end{array}\right]=U\left(X_{\left(a\right)}\right)& \left(20\right)\end{array}$

[0172] (State Transition)

[0173] Next, state transition models of the skeleton models (a) to (d) in the state space X defined above will be described. A state transition model is desired to be a model with proper constraints imposed thereon so as to prevent transition to a normally impossible state for the motion of the body of a pedestrian, namely a human body. This is achieved by using the above-described coordinate system and state space, and by adjusting the Gaussian noise variance in the autoregressive model.

[0174] Further, the state of each skeleton model determined by the positions and angles of the respective sticks, which build the skeleton model, is constrained so that the mutual spatial arrangement of the sticks is a spatial arrangement which is possible in human body structure. More specifically, the movable range of the stick is restricted for the angle of each stick. In addition, a restriction is imposed that the length ratio among multiple sticks is kept constant during both the previous time and the current time. The imposition of restrictions (constraints) on the possible states means that points representing a skeleton model are localized in an area in the state space X. Further, the imposition of constraints on the state transition means that the state does not transition between mutually remote points in the state space X.

[0175] The state transition model with variance adjustment and constraints imposed on the state transition as described above makes it possible to constrain the state transition of the skeleton model by reflecting changes in the appearance of a pedestrian which are prevented from being unnatural. It also makes it possible to eliminate the possibility of transition to a skeleton in a state which cannot normally be considered as a pedestrian, allowing the particles to scatter toward a higher likelihood of presence of the state of the skeleton in the state space X.

[0176] (State Transition of Absolute Coordinates of Base Point)

[0177] An equation of a state transition model reflecting the above will be described for each variable. First, for the state transition of the absolute coordinates x_b, y_b of the base point, a second-order autoregressive model (AR model: refer to the above-described “Introduction to Time Series Analysis” by Genshiro Kitagawa) which can consider velocity is applied. Here, assuming that u_t is a predicted value of the state of each variable after the state transition, that u_t−1 and u_t−2 are respectively states one period and two periods before (in which “one period before” means “one step before”, which also applies below), and that w_c is a Gaussian noise with zero average, the state transition model can be expressed by the following equation (21):
u_t=2u_t−1−u_t−2+w_c  (21)

[0178] (State Transition of Stick Length)

[0179] The state transition of the stick length l_pq is performed by a two-step process. First, a zoom parameter z is probabilistically determined by the following equation (22). Thereafter, the state u_t−1 one period before is multiplied by z, and then the state is transitioned by a first-order autoregressive model as shown in equation (23).
z=γ^wz  (22)
u_t=zu_t−1+w_l  (23)

[0180] Here, w_z is a Gaussian noise with zero average, γ is a positive constant, and w_l is a Gaussian noise with zero average. This can be appropriately adapted to enlargement and reduction of the skeleton model corresponding to the approach and departure of the pedestrian, with the length ratio among the sticks at previous time being kept, by making the contribution of the first-order autoregressive model smaller than the contribution of the zoom parameter z in determining the length. Such adjustment is achieved by controlling the variances of w_z and w_l.

[0181] (State Transition of Stick Angle)

[0182] FIG. 10 shows a specific example of constraints on the shape of a skeleton model used in the pedestrian tracking method. More specifically, the movable range of the neck stick is set within an upper 90 degrees, while setting the movable ranges of the left and right legs to be up to the horizontal position. Considering these movable ranges, the following restrictions are imposed on the respective skeleton models for the state transition of the stick angle a_pq:

[0183] −3π/4<a_ba<−π/4 [Skeleton model (a),(b),(c),(d)]

[0184] π/4<a_bg<3/π/4 [Skeleton model (a),(b),(c),(d)]

[0185] 0<a_bd,a_bf<π [Skeleton model (a)]

[0186] 0<a_gi,a_gk<π [Skeleton model (a),(b)]

[0187] 0<a_cd,a_ef<π [Skeleton model (c)]

[0188] 0<a_hi,a_jk<π [Skeleton model (c),(d)]

[0189] (a_bd−a_bg)(a_bf−a_bg)<0 [Skeleton model (a)]

[0190] (a_gi−a_bg)(a_gk−a_bg)<0 [Skeleton model (a),(b)]

[0191] (a_cd−a_bg)(a_ef−a_bg)<0 [Skeleton model (c)]

[0192] (a_hi−a_bg)(a_jk−a_bg)<0 [Skeleton model (c),(d)]

[0193] A second-order autoregressive model considering average is applied under these restrictions. This can be expressed by the following equation (24):
u_t=α×(2u_t−1−u_t−2)+(1−α)×σ+w_d  (24)

[0194] Here, σ represents an average which is −π/2 for the transition of angle a_ba and π/2 for the transition of the other angles a_pq, while α is a constant satisfying 0≦α≦1, controlling the influence exerted by the average σ. In particular, if α=1, the average is not considered. Further, w_a is a Gaussian noise with zero average, and is determined not to exceed the restrictions described above.

[0195] According to the state transition model described above, the state transition in the case of e.g. the skeleton mode (a) can be expressed by the following equation (25), where F₁, F₂, C, σ and W are given by equations (26) to (30), respectively:

[0196] $\begin{array}{cc}{x}_t=F_1·x_{t-1}+F_2·x_{t-2}+C\sigma +W& \left(25\right)\\ F_1=\left[\begin{array}{ccc}2I_2& O_{2\times 4}& O_{2\times 6}\\ O_{4\times 2}& {\gamma }^{w_z}{I}_4& O_{4\times 6}\\ O_{6\times 2}& O_{6\times 4}& 2\alpha I_6\end{array}\right]& \left(26\right)\\ F_2=\left[\begin{array}{ccc}-I_2& O_{2\times 4}& O_{2\times 6}\\ O_{4\times 2}& O_{4\times 4}& O_{4\times 6}\\ O_{6\times 2}& O_{6\times 4}& -\alpha I_6\end{array}\right]& \left(27\right)\\ C=\left[\begin{array}{cc}{O}_{6\times 6}& O_{6\times 6}\\ O_{6\times 6}& \left(1-\alpha \right)I_6\end{array}\right]& \left(28\right)\\ \sigma ={\left[\begin{array}{ccccccc}{O}_{1\times 6}& -\pi /2& \pi /2& \pi /2& \pi /2& \pi /2& \pi /2\end{array}\right]}^T& \left(29\right)\\ W={\left[\begin{array}{cccccccccccc}{w}_c& w_c& w_l& w_l& w_l& w_l& w_a& w_a& w_a& w_a& w_a& w_a\end{array}\right]}^T& \left(30\right)\end{array}$

[0197] Here, I_N is a unit matrix of N×N, and O_N×M is a zero matrix of N×M. Important parameters to determine the performance of the state transition model are variances of the added Gaussian noises w_c, w_z, w_l and w_a. These are required to be determined according to disorder and complexity of the target to be processed. Assume that the transition of the absolute coordinate u_t of a node is given by the following equation (31) depending on the respective Gaussian noises, and consider respective influences ρ as in the following equation (32) which are exerted on u_t by the respective noises:
u_t=f(u_t−1,w_c,w_z,w_l,w_a)  (31)
ρ_c=|f(u_t−1,w_c,w_z,w_l,w_a)−f(u_t−1,0,w_z,w_l,w_a)|
ρ_z=|f(u_t−1,w_c,w_z,w_l,w_a)−f(u_t−1,w_c,0,w_l,w_a)|
ρ_l=|f(u_t−1,w_c,w_z,w_l,w_a)−f(u_t−1,w_c,w_z,w_l,0)|
ρ_a=|f(u_t−1,w_c,w_z,w_l,w_a)−f(u_t−1,w_c,w_z,w_l,0)|  (32)

[0198] In the following, the determination of the relationship in magnitude among the above-described influences ρ will be described. First, the relative positional relationship of the respective nodes is determined by ρ_z, ρ_l and ρ_a, so that the positional relationship of the nodes at previous time (t−1) can be maintained by setting ρ_c>ρ_z,ρ_l,ρ_a. Further, ρ_a>ρ_z,ρ_l is set since the probability for the stick length to suddenly change is considered to be low. However, note that for w_a, it is not necessary to use the same variance for all stick angles a_pq. For example, the waist angle a_bg is less likely to much transition than the hand angle a_bd. Thus, the variance of the Gaussian noise used for the transition of a_bg is set to be smaller than the variance of the Gaussian noise used for the transition of a_bd. For ρ_z,ρ_l, ρ_z>ρ_l is set to maintain the length ratio among the sticks at the previous time as described above.

[0199] In summary, the above leads to ρ_c>ρ_a>ρ_z>ρ_l. By controlling the variances of w_c, w_z, w_l and w_a to satisfy this inequality, it is possible to constrain the state transition so that the respective particles transitioned in state are more likely to scatter toward a higher possibility of a skeleton model of a pedestrian while, in contrast, less likely to scatter toward its lower possibility.

[0200] (Likelihood Calculation of Particles

[0201] As a method of calculating likelihood π_t⁽ⁿ⁾, a method based on the maximum value search in a distance-transformed image is used, which is obtained by ex_t ending a method used in the contour tracking using CONDENSATION. These will be described in detail below. More specifically, the distance-transformed image to be used in the likelihood calculation step is an image represented by a black and white density such that its intensity increases as its position shifts from a black contour part representing a pedestrian region to the inside of the contour. The likelihood of each predicted skeleton model is calculated, with the distance-transformed image being superimposed on the skeleton model, by using a distance from each of the multiple points on the sticks building the skeleton model to an extreme intensity point, e.g. maximum intensity point, of the distance-transformed image present on a normal of each stick at the each point.

[0202] The likelihood calculation method as described above can calculate the likelihood of each estimated skeleton model with high accuracy, because both the sticks of the skeleton model and the high intensity portions of the distance-transformed image reflect the bone structure of a human body, while the degree of their superimposition can be estimated by the distance to the maximum intensity point. For example, as the sum of the distances to the maximum intensity points decreases, the degree of superimposition increases, increasing the likelihood.

[0203] As described above, the concept of the likelihood calculation used in the contour tracking using CONDENSATION is applied to calculate the likelihood π of particles. In the contour tracking using CONDENSATION, edges in an input image are searched with respect to several points on the predicted B-spline curve to use the distances between the predicted contour and edges so as to evaluate the likelihood of the particles. Thus, in the pedestrian tracking method according to the present embodiment, the likelihood is calculated by comparing the predicted skeleton model with a morphological skeleton (skeleton model obtained from an image by image processing) of the observed data.

[0204] More specifically, points on the morphological skeleton which are on the normal of, and closest to, the sticks are searched with respect to several points on the sticks building the skeleton model, so as to use their distances to the predicted skeleton model to calculate the likelihood of the particles corresponding to the skeleton model. Note that points on the skeleton model used as starting points of the search are referred to as search base points.

[0205] (Distance-Transformed Image)

[0206] FIG. 11A shows a pedestrian region image as a target to be tracked, while FIG. 11B shows an example of a distance-transformed image obtained by subjecting the image to distance transform. A morphological skeleton is obtained as a distance-transformed image obtained by subjecting a binary image to distance transform. The distance-transformed image is generated such that the distance from a pixel of interest to a pixel having a pixel value of 0 (zero) in the binary image is transformed as a pixel value of the pixel of interest. If the pixel value of the pixel of interest is 0 (zero), the distance is 0 (zero). Here, assuming that the region of the pixel value of zero in a binary image is B, the pixel value D(x,y) of a pixel with coordinates (x,y) in a distance-transformed image can be expressed by the following equation (33):

[0207] $\begin{array}{cc}D\left(x,y\right)=\{\begin{array}{cc}0& \left(x,y\right)\in B\\ {\min }_{\left(x_i,y_i\right)\in B}\sqrt{{\left(x-x_i\right)}^2+{\left(y-y_i\right)}^2}& \left(x,y\right)\notin B\end{array}& \left(33\right)\end{array}$

[0208] (Simple Likelihood Calculation)

[0209] FIG. 12A shows a state in which a predicted skeleton model is superimposed on a distance-transformed image, while FIG. 12B shows a method of obtaining a likelihood from the Figure with the superimposition. In the present embodiment, a binary image assuming the pixel value of the candidate pedestrian region to be 1 (one) is used as an image before the distance transform, where 1 (one) represents white and 0 (zero) represents black. This binary image is obtained at a preliminary stage of tracking.

[0210] Assume that a skeleton as shown in FIG. 12A is predicted in the prediction step. The search of the morphological skeleton in the distance-transformed image is achieved by obtaining extreme intensity points, e.g. maximum points, in the distance-transformed image which are each on the normal of, and closest to, each search base point on the predicted skeleton model.

[0211] Assume that δ_i⁽ⁿ⁾ is a distance from an i-th search base point to the searched maximum point on the skeleton model. An extremely simple method of calculating the likelihood of a particle n calculates e⁽ⁿ⁾ given by the following equation (34). Here, r is a constant for scaling, and μ is a constant representing a search range. Equation (34) follows formula (7) for calculating the likelihood in the contour tracking using CONDENSATION. The likelihood π⁽ⁿ⁾ of the particle n is calculated by normalizing the thus calculated e⁽ⁿ⁾ as in equation (35):

[0212] $\begin{array}{cc}{e}^{\left(n\right)}=\exp \left\{-\frac{1}{r}\sum _i{\left(\min \left({\delta }_i^{\left(n\right)},\mu \right)\right)}^2\right\}& \left(34\right)\\ {\pi }^{\left(n\right)}=\frac{e^{\left(n\right)}}{\sum _{k=1}^N{e}^{\left(k\right)}}\left(35\right)& \left(35\right)\end{array}$

[0213] (Higher Accuracy Likelihood Calculation)

[0214] FIGS. 13A and 13B show other methods of obtaining the likelihood in the pedestrian tracking method. It can be mentioned that the above-described simple likelihood calculation method has the following two problems: (1) the likelihood increases when the hand stick overlaps the waist stick; and (2) the likelihood increases as the length of the stick decreases. Improvements on the two points will be described below.

[0215] (1. Countermeasure to the Overlap between Hand and Waist Sticks)

[0216] When a maximum point of a distance-transformed image is searched using a point on e.g. hand stick ST_bd as a search base point, a maximum point originating from the waist cannot be distinguished from a maximum point originating from the hand. Thus, when a skeleton model causing predicted hand stick to overlap waist stick ST_bg, there is a problem that from the search using points on both sticks as search base points, maximum points both originating from the trunk are detected, resulting in the obtainment of high likelihood.

[0217] Thus, when using a search base point on the hand stick, a maximum point is searched from an upper portion to a lower portion of a circumference having a center angle of π/2 as shown in FIG. 13A. The likelihood is calculated based on length ε to a search base point which is on a search line and obtained from the angle at a first detected maximum point. In other words, a maximum point closer to the horizontal direction is prioritized to solve the above-described problem. This is based on the fact that maximum points detected at angles closer to the vertical direction are likely to originate from the trunk. A value obtained based on such search from a j-th search base point is assumed to be ε_j⁽ⁿ⁾.

[0218] (2. Countermeasure to the Higher Likelihood of Shorter Sticks)

[0219] With a decrease in the stick length, the search base points aggregate more. This means that a higher likelihood is calculated if a maximum point in the distance-transformed image is present near the aggregated points. This may cause the problem that each stick length becomes shorter each time the state transition is repeated. Thus, as shown in FIG. 13B, an end point (distance ζ) of the morphological skeleton is to be searched in the direction of the stick. A value obtained based on such search from a k-th search base point is assumed to be ζ_k⁽ⁿ⁾. In order to solve the above-described problem, the distance to the end point is additionally considered in the likelihood so as to allow ζ to be larger when the stick length is shorter.

[0220] (Improved Likelihood)

[0221] Using the thus obtained δ_i⁽ⁿ⁾, ε_j⁽ⁿ⁾ and ζ_k⁽ⁿ⁾, e⁽ⁿ⁾ is calculated by the following equation (36). Here, ξ_i, ξ_j and ξ_k are weighting factors. The likelihood π⁽ⁿ⁾ is calculated by normalizing the thus calculated e⁽ⁿ⁾ of the following equation (36) using the above equation (35):

[0222] $\begin{array}{cc}{e}^{\left(n\right)}=\exp \left[-\frac{1}{r}\left\{\sum _i{{\xi }_i\left(\min \left({\delta }_i^{\left(n\right)},\mu \right)\right)}^2+\sum _j{{\xi }_j\left(\min \left({\varepsilon }_j^{\left(n\right)},\mu \right)\right)}^2+\sum _k{{\xi }_k\left(\min \left({\zeta }_k^{\left(n\right)},\mu \right)\right)}^2\right\}\right]& \left(36\right)\end{array}$

[0223] Hereinafter, the above-described pedestrian tracking method is applied to various image sequences (time-series images) for evaluation. First, an implementation method will be shown. Next, the pedestrian tracking method according to the embodiment of the present invention (hereafter referred to as proposed method) and tracking methods to be compared will be applied to artificially generated sequences and actual sequences, respectively, so as to show the validity of the present invention based on the results.

[0224] (Implementation Method)

[0225] Generally, causes of failure in pedestrian tracking are, for example, occlusion, sudden change in the velocity of a pedestrian, presence of an object similar to the pedestrian as a tracking target, and so on. In order to evaluate the performance of the pedestrian tracking method of the present invention, it is desirable to evaluate using various actual sequences including these causes. However, it is difficult to obtain e.g. an actual sequence in which parameters such as velocity of a tracking target are finely controlled. Further, for the evaluation, true values are needed, but its manual input is inefficient. Thus, first, the characteristics of the proposed method will be examined by use of sequences artificially generated using a software. Next, the proposed method will be applied to several kinds of actual sequences to evaluate the tracking accuracy. Further, the number of particles and the four patterns of skeleton models (a), (b), (c) and (d) will be compared for comparison with the existing methods and examination.

[0226] In the following, the tracking methods to be compared will be described, and then evaluation criteria will be described. Finally, the artificial sequences and the actual sequences used for evaluation will be described respectively. Further, misdetections of a pedestrian region are classified into the following two kinds. One is a misdetection e.g. due to a stationary object in the foreground to cause a part or whole of the pedestrian region to be lost, which is referred to as static misdetection. The other is a misdetection e.g. due to a moving object other than the tracking target to cause a region different from a true pedestrian region to be detected as a pedestrian region, which is referred to as dynamic misdetection. The causative objects of these misdetections are referred to as static misdetection and dynamic misdetection, respectively.

[0227] (Tracking Methods to be Compared)

[0228] Tracking methods to be compared with the proposed method, to be mentioned here, are a center-of-gravity tracking method using a Kalman filter, and a contour tracking method using CONDENSATION. Their implementations will be briefly described. The center-of-gravity tracking using a Kalman filter searches pixels in a candidate pedestrian region closest from a center-of-gravity position predicted by a Kalman filter so as to obtain, in a contiguous region with the pixels, center-of-gravity coordinates to be corrected by a Kalman filter for tracking.

[0229] The contour tracking using CONDENSATION performs learning based on principal component analysis, using true values of 15 (fifteen) frames preceding the starting frame of the tracking. The number of nodes of B-spline curve to approximate the contour is set 32 (thirty-two). The 3×3 Sobel operator is used to detect edges to be used for the likelihood calculation (measurement).

[0230] The contour tracking using CONDENSATION can generally track an object with any shape by pre-learning using principal component analysis. Thus, a method obtained by exclusively ex_t ending the contour tracking using CONDENSATION to the pedestrian tracking, and by increasing its accuracy, is implemented and added as a method to be compared. This method is hereafter referred to as pedestrian contour tracking.

[0231] As above, the following four methods are to be evaluated: (1) proposed method; (2) center-of-gravity tracking using a Kalman filter; (3) contour tracking using CONDENSATION; and (4) pedestrian contour tracking using CONDENSATION.

[0232] (Pedestrian Contour Tracking)

[0233] In the following, the pedestrian contour tracking using CONDENSATION, which is one of the tracking methods to be compared, will be described. The pedestrian contour tracking using CONDENSATION constrains a state transition by restricting the tracking target to pedestrians instead of constraining the state transition by using principal component analysis. First, the 32 control points on the B-spline curve to approximate the contour of a pedestrian are classified into six groups that are the head, trunk and four limbs. Similarly as in the proposed method, a base point is set, and respective nodes are expressed by their distances from the base point and angles to the x-axis in the coordinate system representing the control points of the B-spline curve. Assume that θ_Ij is an angle of a node belonging to Group I and having a node index j in Group I. Then, as shown in FIG. 14, the angle θ_Ij is expressed as a sum of a common angle Φ_I in the group and a relative angle φ_Ij therefrom, that is θ_Ij=Φ_I+φ_Ij.

[0234] The state transition of the angle θ_Ij is performed in two separate stages. First, the common angle Φ_I in the group is transitioned by a second-order autoregressive model, and then the relative angle θ_Ij is transitioned by a first-order autoregressive model. More specifically, the state transition model of the following equation (37) is used:

[0235] $\begin{array}{cc}\begin{array}{c}{\theta }_{\mathrm{Ij},t}={\Phi }_{I,t}+{\varphi }_{\mathrm{Ij},t}\\ =2{\Phi }_{I,t-1}-{\Phi }_{I,t-2}+w_g+{\Phi }_{\mathrm{Ij},t-1}+w_l\end{array}& \left(37\right)\end{array}$

[0236] By making the variance of the Gaussian noise w_l smaller than the Gaussian noise w_g here, the relationship of relative angles among nodes in the group is maintained, so that an efficient pedestrian tracking is expected to be achievable. Further, the state transition models of the absolute coordinates of the base point and the distances between the base point and the respective nodes use a second-order autoregressive model and a first-order autoregressive model, respectively.

[0237] (Evaluation Criteria)

[0238] FIG. 15 shows evaluation criteria for evaluating the tracking accuracy in the pedestrian tracking method. A tracking result according to the proposed method is shown by a skeleton of the pedestrian, and a result of the center-of-gravity tracking using a Kalman filter to be compared is shown by center-of-gravity coordinates, while results of the contour tracking using CONDENSATION and the pedestrian contour tracking using CONDENSATION to be further compared are each shown by a contour of the pedestrian.

[0239] In order to compare and examine these results in a unified manner, a rectangle as shown in FIG. 15 to contain an object estimated by the tracking is used to obtain (1) a center-of-gravity error Δg that is a Euclid distance between the center-of-gravity position of the estimated rectangle and the true value, and (2) a scale error that is a ratio between height d1 of the estimated rectangle and height d0 of the true value so as to use these values as evaluation criteria.

[0240] The unit of the center-of-gravity error Δg is pixel. A smaller center-of-gravity error indicates a higher tracking accuracy, while a scale error closer to 1 (one) indicates predictability of the shape of the pedestrian with higher accuracy. Now, the state estimate using a Monte Carlo filter is a probabilistic method which obtains a different tracking result each time. Thus, the pedestrian tracking is performed 100 (hundred times) for each sequence so as to calculate an average of these as the above-described values for evaluation.

[0241] (Artificial Sequence)

[0242] A software to artificially generate sequences was implemented using C language. Each generated sequence is a binary image having a candidate pedestrian region having a pixel value of 1 (one), in which this image is distance-transformed and input to the proposed method. The size of the image is set as 720×480, and the number of frames as 200. This software can output not only the sequences for input, but also true values used for evaluation, initial value setting and pre-learning. This software will be described below.

[0243] FIGS. 16A to 16I show a part of image sequences used for the evaluation of the pedestrian tracking method. These images are images obtained by enlarging each pedestrian region in a part of the sequences in the simplest case without the static misdetection or dynamic misdetection. As shown in these Figures, 8 (eight) ellipses were used to form a human-shaped object. Each human-shaped object image was generated by respectively calculating, in each frame, the coordinates of the center of each ellipse as well as the lengths of the major and minor axes and the inclination of the major axis of each ellipse, and by setting the pixel value of the region in each ellipse as 1 (one).

[0244] The above-described software for generating the artificial sequences can be controlled in the initial position, velocity, acceleration and the like of the human-shaped object. Further, both the static detection and the dynamic detection can be added, and can be controlled in shape, position and the like. Thus, the sequences shown below were generated for evaluation.

[0245] (Normal Sequence)

[0246] A sequence without added static misdetection and dynamic misdetection is used for evaluation. This sequence is referred to below as sequence N.

[0247] (Reverse Reproduction Sequence)

[0248] In the middle of sequence N, the sequence is reversely reproduced to change the velocity of the pedestrian to the opposite direction so as to generate a sequence to be used for evaluation. This sequence is referred to below as sequence R. In sequence R, the sequence was reversely reproduced at the 59th frame and 107th frame.

[0249] (Sequence with Added Guardrail Type Static Misdetection)

[0250] FIGS. 17A and 17B show a part of image sequences to evaluate guardrail type static misdetection used for the evaluation of the pedestrian tracking method. As shown in these Figures, sequences with static misdetections GR likened to two patterns of guardrails and added to the sequence N were prepared. These sequences are referred to below as sequences G1 and G2, respectively. In these sequences, a part of pedestrian region G is lost from the 18th frame and onward due to the static misdetection.

[0251] (Sequence with Added Pole Type Static Misdetection)

[0252] FIGS. 18A, 18B and 18C show a part of image sequences to evaluate pole type static misdetection used for the evaluation of the pedestrian tracking method. As shown in these Figures, sequences with static misdetections P likened to three patterns of poles and added to the sequence N were prepared. These sequences are referred to as sequences P1, P2 and P3, respectively. In sequence P1, a part of the pedestrian region is lost due to the static misdetection in the 9th to 40th, 72nd to 92nd, and 124th to 144th frames. In sequence P2, a part of the pedestrian region is lost due to the static misdetection in the 9th to 42nd, 72nd to 95th, and 124th to 152nd frames. In sequence P3, a part of the pedestrian region is lost due to the static misdetection in the 9th to 42nd, 48th to 70th, 77th to 96th, and 101st to 160th frames.

[0253] (Sequence with Added Car Type Dynamic Misdetection)

[0254] FIGS. 19A and 19B show a part of image sequences to evaluate dynamic misdetection used for the evaluation of the pedestrian tracking method. As shown in these Figures, there were prepared sequences with four patterns of dynamic misdetections added to the sequence N, which are composed of dynamic misdetections C likened to two patterns of cars with a moving direction of the car the same as that of the pedestrian and to those with the opposite direction. These sequences are referred to as sequences C1, C2, C3 and C4. In sequences C1 and C3, the moving direction of the car is opposite to that of the pedestrian, while in sequences C2 and C4, the moving direction of the car is the same direction as the pedestrian. In sequence C1, the pedestrian region G overlaps the dynamic misdetection region in the 18th to 37th, 96th to 109th, and 169th to 180th frames. In sequence C2, the pedestrian region G overlaps the dynamic misdetection region in the 9th to 34th, and 141st to 158th frames. In sequence C3, the pedestrian region G overlaps the dynamic misdetection region in the 18th to 41st, 91st to 113th, and 163rd to 185th frames. In sequence C4, the pedestrian region G overlaps the dynamic misdetection region in the 2nd to 40th, and 128th to 165th frames.

[0255] (Actual Sequences)

[0256] FIGS. 20A, 20B and 20C show a part of actual image sequences used for the evaluation of the pedestrian tracking method, while FIG. 20D shows a binary image obtained from FIG. 20A. A data set provided by PETS (IEEE International Workshop on Performance Evaluation of Tracking and Surveillance:http://www.cvg.cs.rdg.ac.uk/slides/pets.html) was used as true values of the actual sequences and tracking target coordinates used for the evaluation. FIGS. 20A, 20B and 20C show a part of three sequences used for the evaluation. The rectangle G in each Figure indicates a pedestrian as a tracking target. Hereafter, the sequence shown in FIG. 20A is referred to as sequence U, the sequence shown in FIG. 20B as sequence S1, and the sequence shown in FIG. 20C as sequence S2. These sequences were captured by a fixed camera. The image size of sequence U is 768×576, and the image size of sequences S1 and S2 is 720×576. The number of frames for tracking is set 200.

[0257] In sequence U, the motion of the tracking target is simple, but an occlusion occurs in the 135th to 140th frames due to an electric pole in the foreground. In sequences S1 and S2, the motion of the tracking target is complex, and many other objects similar to the tracking target are present in the image. Further, in sequence S2, the tracking target almost completely overlaps another object in the 12th to 23rd, 112th to 121st, and 154th to 166th frames, causing it to be a sequence which is extremely difficult to track.

[0258] (Initial State Vector and Distance-Transformed Image)

[0259] The proposed method requires input of an initial state vector x₀ and a distance-transformed image. The initial state vector x₀ is to be provided manually. The distance-transformed image is generated based on a difference image obtained using background subtraction. Assuming that I_orig(x,y) is a pixel value of an original image at coordinates (x, y), and I_bg(x,y) is a pixel value of the background image, the pixel value I_sub(x,y) of the difference image can be obtained as an absolute difference value between the original image and the background image as in the following equation (38):
I_sub(x,y)=|I_orig(x,y)−I_bg(x,y)|  (38)

[0260] A pixel value of a binary image, I_bin(x,y), is calculated from the difference image by a thresholding shown in the following equation (39). This allows to obtain a binary image having a pixel value of 1 (one) in a region thereof in which a moving object is present in the original image, where τ is a threshold value:

[0261] $\begin{array}{cc}{I}_{\mathrm{bin}}\left(x,y\right)=\{\begin{array}{cc}1& \left(I_{\mathrm{sub}}\left(x,y\right)\ge \tau \right)\\ 0& \left(I_{\mathrm{sub}}\left(x,y\right)<\tau \right)\end{array}& \left(39\right)\end{array}$

[0262] FIG. 20D shows an image obtained by background subtraction from sequence U shown in FIG. 20A. A distance-transformed image was generated by subjecting the thus obtained binary image to distance transform shown in equation (33).

[0263] (Evaluation Results)

[0264] The following shows evaluation results using the above-described evaluation methods for respective sequences, and describes the validity of the proposed method. In FIG. 21 to FIG. 35 showing the evaluation results, curves a, b, c and d correspond to the results of the following methods, respectively:

[0265] Proposed method (curve a);

[0266] Center-of-gravity tracking using Kalman filter (curve b);

[0267] Contour tracking using CONDENSATION (curve c); and

[0268] Pedestrian contour tracking using CONDENSATION (curve d).

[0269] (Sequence N)

[0270] First, in the case where the proposed method was applied to sequence N, and the number of particles for each of the above-described skeleton models was varied, the tracking accuracy is evaluated based on a center-of-gravity error calculated as an average of all the frames. The evaluation results are shown in Table 1.

[0271]

TABLE 1
Evaluations Results in Sequence N (Center-of-Gravity)
	Number of Particles	100	1,000	10,000
	Skeleton model (a)	7.192	3.365	2.248
	Skeleton model (b)	9.004	7.425	6.416
	Skeleton model (c)	10.129	7.469	5.935
	Skeleton model (d)	8.986	7.421	6.411

[0272] It could be found from this result that an increase in the number of particles causes an increase in tracking accuracy. It is expected that the skeleton model (a) is most suitable for sequence N because of hand detection and no shoulder width. It could be found from the result that the expected result is obtained. In the evaluation of the artificial sequences below, the number of particles is set 1,000, and the skeleton model (a) is used.

[0273] FIG. 21A shows evaluation results of the center-of-gravity errors for sequence N, while FIG. 21B shows evaluation results of the scale errors. The horizontal axis represents time, and its unit is frame.

[0274] The results indicate that the center-of-gravity tracking using a Kalman filter (curve b) showed a performance with substantially no error. This is because the center of gravity of the tracking target can be accurately extracted in sequence N in which there is no noise at all. The proposed method (curve a) shows a better performance than the contour tracking using CONDENSATION (curve c) and the pedestrian contour tracking using CONDENSATION (curve d), but shows periodic variations in the center-of-gravity errors. This period is the same as the period of walking, causing larger errors in frames as in FIGS. 15E and 15F (sic, correctly 16E and 16F). It is considered that this is because the knee joints are not modeled in the proposed method so that the accuracy of the likelihood calculation of particles decreases. It can be found in the contour tracking using CONDENSATION (curve c) that scale errors increase. This indicates that the constraint(s) on the state transition using principal component analysis is not proper. An increase in the scale errors causes the likelihood of the particles to decrease, thereby causing the tracking target to be lost as in FIG. 21A. Further, in a general-purpose tracking method such as the contour tracking using CONDENSATION (curve c), once the error becomes large, it is unlikely that it becomes small again. On the other hand, in the proposed method (curve a), it could be found that even when the error becomes temporarily large, the error can be made small again.

[0275] (Sequence R)

[0276] FIG. 22A shows evaluation results of the center-of-gravity errors for sequence R, while FIG. 22B shows evaluation results of the scale errors. In sequence R, substantially similar results to those for sequence N were obtained. It is considered that this is because the moving distance of the tracking target between frames is small so that even a sudden reverse reproduction exerts substantially no influence.

[0277] (Sequences G1 and G2)

[0278] FIGS. 23A and 23B show evaluation results for sequence G1, while FIGS. 24A and 24B show evaluation results for sequence G2. Sequences G1 and G2 show a more noticeable reduction than sequence N in accuracy of the center-of-gravity tracking using a Kalman filter (curve b) because the pedestrian region is divided by the static misdetection. On the other hand, the proposed method (curve a) does not show such a large reduction in accuracy, while the pedestrian contour tracking using CONDENSATION (curve d) showed an approximately equivalent accuracy to the proposed method. In sequence G2, the proposed method (curve a) shows a large error in the 60th to 120th frames. This is because the end points of the legs of the skeleton are not detected for a long time due to the static detection, causing it as a whole to shift in the (−y) direction.

[0279] (Sequences P1, P2 and P3)

[0280] FIG. 25A shows evaluation results for sequence P1, and FIGS. 26A and 26B show evaluation results for sequence P2, while FIGS. 27A and 27B show evaluation results for sequence P3. According to the proposed method (curve a), in any sequence of sequences P1, P2 and P3, a center-of-gravity error having become temporarily large can be made small again, showing the best performance. The pedestrian contour tracking using CONDENSATION (curve d) showed an approximately equivalent performance in sequences G1 and G2, but showing particularly large errors in sequences P2 and P3. It is considered that this is because a contour was detected at an interface with a tracking target due to the static misdetection. Further, the center-of-gravity tracking using a Kalman filter (curve b) caused instable center-of-gravity positions due to the static misdetection, failing in tracking.

[0281] (Sequences C1, C2, C3 and C4)

[0282] FIGS. 28A and 28B show evaluation results for sequence C1, and FIGS. 29A and 29B show evaluation results for sequence C2, while FIGS. 30A and 30B show evaluation results for sequence C3, and FIGS. 31A and 31B show evaluation results for sequence C4. In any sequence of sequences C1, C2, C3 and C4, the proposed method (curve a) showed the best performance. Particularly, in sequences C3 and C4, although substantially the entire region of the tracking target temporarily overlaps the region of the dynamic detection, the proposed method has succeeded in tracking. On the other hand, in the other methods (curves b, c and d), large errors were found due to the dynamic misdetection. The pedestrian contour tracking using CONDENSATION (curve d) caused significant distortion of the contour shape of the pedestrian as indicated by increases in the scale errors in the case where the moving directions of the pedestrian and the dynamic misdetection are the same, failing in tracking. The center-of-gravity tracking using a Kalman filter (curve b) mistracked a region of the dynamic misdetection.

[0283] (Actual Sequence U)

[0284] First, in the case where the proposed method was applied to sequence U, and the number of particles for each of the skeleton models was varied, the accuracy is evaluated based on a center-of-gravity error calculated as an average of all the frames. The evaluation results are shown in Table 2.

[0285]

TABLE 2
Evaluations Results in Sequence U (Center-of-Gravity)
	Number of Particles	100	1,000	10,000
	Skeleton model (a)	8.505	6.966	6.537
	Skeleton model (b)	7.461	6.588	6.392
	Skeleton model (c)	9.418	8.459	7.698
	Skeleton model (d)	9.720	9.427	8.263

[0286] It could be found from this result that an increase in the number of particles causes an increase in tracking accuracy. It is expected that the skeleton model (b) is most suitable for sequence U because of no hand detection and substantially no shoulder width. It could be found from the result that the expected result is obtained.

[0287] FIGS. 32A and 32B show evaluation results for sequence U. In each method, the number of particles was set 1,000 while the skeleton model (b) was used in the proposed method. As a result, the proposed method (curve a) achieved the best tracking accuracy, while the center-of-gravity tracking using a Kalman filter (curve b) and the pedestrian contour tracking using CONDENSATION (curve d) showed approximately equivalent accuracies to the proposed method.

[0288] (Actual Sequence S1)

[0289] First, in the case where the proposed method was applied to sequence S1, and the number of particles for each of the skeleton models was varied, the accuracy is evaluated based on a center-of-gravity error calculated as an average of all the frames. The evaluation results are shown in Table 3.

[0290]

TABLE 3
Evaluations Results in Sequence S1 (Center-of-Gravity)
	Number of Particles	100	1,000	10,000
	Skeleton model (a)	71.738	41.222	26.238
	Skeleton model (b)	52.440	27.688	6.820
	Skeleton model (c)	53.786	26.761	11.584
	Skeleton model (d)	48.727	27.633	8.659

[0291] It could be found from this result that an increase in the number of particles causes an increase in tracking accuracy. Further, although the skeleton model (d) is expected to be most suitable because of many frames with no hand detection and frames with shoulder width in sequence S1, the results indicate that the skeleton model (b) showed the best performance. This indicates that the influence of shoulder width is not a big problem because the region of the tracking target in sequence S1 is small.

[0292] FIGS. 33A and 33B show evaluation results for sequence S1. In each method, the number of particles was set 10,000 while the skeleton model (b) was used in the proposed method. As a result, the proposed method (curve a) and the pedestrian contour tracking using CONDENSATION (curve d) show an approximately equivalent performance. On the other hand, the center-of-gravity tracking using a Kalman filter (curve b) cannot adapt to sudden changes in the velocity of the tracking target, and mistracked a different object from the 20th frame and onward.

[0293] (Actual Sequence S2)

[0294] First, in the case where the proposed method was applied to sequence S2, and the number of particles for each of the skeleton models was varied, the accuracy is evaluated based on a center-of-gravity error calculated as an average of all the frames. The evaluation results are shown in Table 4.

[0295]

TABLE 4
Evaluations Results in Sequence S2 (Center-of-Gravity)
	Number of Particles	100	1,000	10,000
	Skeleton model (a)	108.847	32.693	12.333
	Skeleton model (b)	75.874	12.270	7.801
	Skeleton model (c)	110.883	36.250	23.430
	Skeleton model (d)	58.349	20.794	7.847

[0296] It could be found from this result that an increase in the number of particles causes an increase in tracking accuracy. Further, sequence S2 has many frames with no hand detection in a former part, and many frames with hand detection in a latter part. Further, it has many frames with substantially no shoulder width, so that the skeleton model (a) or (b) is expected to be most suitable. The results indicate that the skeleton model (b) showed the best performance. It is considered that this is because when there are many errors in the former part, the errors are propagated to the latter part.

[0297] (Adaptive Skeleton Model)

[0298] FIG. 34 shows evaluations results of the center-of-gravity errors when an adaptive skeleton model was used for the pedestrian tracking. It is considered that the tracking accuracy is further increased by using the skeleton model (b) for up to the 97th frame with no hand detection, and changing it to the skeleton model (a) from the 97th frame and onward. This model is referred to as an adaptive skeleton model. FIG. 34 shows a comparison of the center-of-gravity errors when the adaptive skeleton model and the skeleton model (b) were used. The number of particles was set 10,000 in each. As a result, the adaptive skeleton model showed a better performance than the skeleton model (b) in the latter part. Although the skeleton models were changed manually here, the accuracy can be further increased by automatically changing the skeleton models while performing tracking.

[0299] FIGS. 35A and 35B show evaluation results for sequence S2. In each method, the number of particles was set 10,000 while the skeleton model (b) was used in the proposed method. As a result, the proposed method (curve a) showed the best tracking accuracy. However, as shown FIG. 35B, the scale errors are significant. This indicates that in sequence S2, the enlargement of an object region due to the motion of the tracking target from the back of the image to the front of the image cannot be accurately predicted. The pedestrian contour tracking using CONDENSATION (curve d) shows significant scale errors around the 20th frame where the tracking target overlaps another object. This means a significant distortion of the estimated contour shape, thus failing in tracking. The center-of-gravity tracking using a Kalman filter (curve b) mistracked another object from the 120th frame and onward.

[0300] (Summary)

[0301] As demonstrated above, the center-of-gravity tracking using a Kalman filter (curve b) showed good accuracy when the noise was small, but often mistracked dynamic misdetections. In the contour tracking using CONDENSATION (curve c), it is difficult to constrain the transition of the pedestrian contour using principal component analysis, resulting in an increase in the scale error, and having failed in tracking. In the pedestrian contour tracking using CONDENSATION (curve d), an overlap of the tracking target with a region of dynamic misdetection caused a significant distortion of the estimated contour, resulting in a significant reduction in the accuracy.

[0302] On the other hand, the proposed method (curve a) achieved stable tracking even in sequences in which the conventional methods (curves b, c and d) failed in tracking. As a result of the comparison of the four patterns of skeleton models (a) to (d), the skeleton model (b) showed a stable accuracy in any sequence. Further, it could be found that an increase in the number of particles causes an increase in the tracking accuracy of the proposed method.

[0303] Note that in the proposed method, namely the pedestrian tracking method and the pedestrian tracking device according to the present invention, the static misdetection as in sequence G2 can be improved by adaptively changing the weight factors ξ in equation (36) in the likelihood calculation of particles. Further, for adaptation to an enlarging object, the adaptation can be done by reflecting a factor depending on the moving direction to the calculation of the zoom parameter z shown in equation (22). Further, the proposed method makes it possible to automatically generate an initial state vector from an image. The proposed method can be independently applied to multiple pedestrians in an image, respectively. This makes it possible to track multiple pedestrians at the same time. In this case, the multiple pedestrians can be more efficiently tracked by reflecting the motions of mutually adjacent pedestrians to the likelihood calculation of each other.

[0304] Further, it is possible to calculate a variance σ² of the coordinates of the node b in the skeleton models shown in FIG. 8 and FIG. 10, and end the tracking by determining that the tracking target is not a pedestrian if such variance exceeds a certain value. The variance σ² can be given by the following equation (40) where the coordinates of the node b are x,y (coordinates values x_i,y_i; i=0˜N with averages of x_m,y_m):

[0305] $\begin{array}{cc}{\sigma }^2=\frac{\stackrel{N}{\sum _{i=0}}\left\{{\left(x_m-x_i\right)}^2+{\left(y_m-y_i\right)}^2\right\}}{N}& \left(40\right)\end{array}$

[0306] As described above, the addition of the above-described step of calculating the variance σ² of the coordinates of the node b between the trunk stick and the head stick in each skeleton model predicted by a prediction step, and ending the tracking if such variance σ² exceeds a certain value makes it possible to determine from the variance σ² of the coordinates of the node b that the tracking target is not a pedestrian even if a non-pedestrian is erroneously extracted as a pedestrian region, and thus to end the mistracking.

[0307] Besides, the present invention is not limited to the arrangements described above, and various modifications are possible. For example, if the pedestrian tracking is fed back to the classification of the candidate regions at a previous stage, it can be used to increase the accuracy. Further, as the morphological skeleton (skeleton model obtained from an image by image processing) to be compared with a skeleton model for the likelihood calculation, not only the method using a distance-transformed image described above, but also a morphological skeleton obtained using an erosion (A⊚B) and an opening (A⋄B) can be used. In addition, the pedestrian tracking method and the pedestrian tracking device of the present invention can be applied to various objects such as moving objects including e.g. animals, robots and so on by modeling each of them using a skeleton, not limited to pedestrians.

[0308] Note that the pedestrian tracking method and the pedestrian tracking method of the present invention can be formed by a set of processes or functions on a computer having a general structure comprising a CPU, a memory, an external storage device, a display device and an input device.

[0309] This application claims priority based on the Japanese patent application dated Jul. 10, 2006, the entire content of which is incorporated by reference into this application.