Systematic design analysis for a vision system

[0001] This application claims the benefit of U.S. Provisional Application No. 60/295,979, filed Jun. 5, 2001.

[0002] The present invention relates to computer vision techniques and, more particularly, to methods and systems for the systematic engineering of vision systems.

[0003] The computer vision field is at a stage where complete systems are increasingly being developed and tested for a variety of real-world applications. Statistical estimation/classification methods are increasingly the choice for these systems. This is because they provide flexibility in modeling, performance characterization, validation and adaptation through sequential estimation.

[0004] The systems analysis phase of performance characterization has been studied to some degree in the literature. However, the systems design phase and the interaction between systems design, analysis, test, and re-design cycle has not been explored in great detail.

[0005] Referring to FIG. 1, the system design and analysis phases for a vision system are shown. The typical scenario in an industrial research and development unit developing vision systems is that a customer defines a system specification and its requirements (102). An engineer then translates these requirements to a system design (110) and validates that the system design meets the user-specified requirements. Further, the process usually involves creating a system configuration (120), analyzing and optimizing the system (130), and performing performance characterization (140).

[0006] The system requirements in the video analysis setting often involves the specification of the operating conditions, the type of sensors, the accuracy requirements, and the computational requirements to be met by the system. The main problem, however, is that there is no known systematic way for vision systems engineers to go about doing this translation of the systems requirements to a detailed design. It is still an art to engineer systems to meet given application specific requirements. There are two fundamental steps in the design process: the choice of the system architecture and the modules for accomplishing the task, and the statistical analysis and validation of the system to check if it meets user requirements. In real-life, the system design and analysis phases typically follow each other in a cycle until the engineer obtains a design and an appropriate analysis that meets the user specifications. Automation of the design process is a research area with many open issues, although there have been very limited studies in the context of image analysis (e. g., automatic programming). The systems analysis (performance characteristics) or evaluation phase for vision systems is an active area of research in the last few years.

[0007] A technique is disclosed for building a vision system. Reusable components and replacement components of an existing vision system are identified. The replacement components may be modules that are influenced by the relaxation in application constraints. Statistical characterization is performed on the replacement components (or the hybrid design variations obtained by fusing modules with the replacement modules). Wrappers are developed that provide statistical consistency with existing interfaces and are integrated into the new vision system.

[0008] These and other aspects, features and advantages of the present invention will become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings.

[0013] One of the major issues in vision systems research is to identify how maximal re-use of components or system configurations can be achieved when one relaxes the operating constraints of a system. We wish to study this problem by examining how re-use can be achieved when a system is designed and analyzed by following a systematic engineering methodology.

[0014] Assuming that a system has been designed, analyzed, and tested for a given restricted application scenario, the question we would like to ask is how one can adapt the system to operate under a less restrictive input condition. In order to adapt the system configuration to meet extended system requirements one has to identify how a change in requirement influences the existing modules and the system architecture. A redesign of all modules affected is an option. Another way is to utilize third party modules to replace existing ones. To retain the advantages derived by following a systematic methodology during the design and analysis phases of the original system one has to choose external modules that satisfy the following constraints:

• • [0015] 1) They should be amenable to statistical analysis so that a probabilistic fusion of the component with the existing system is feasible, and
  • [0016] 2) They should facilitate ease of re-use of previous modules and their performance analysis.

[0017] The first point is important in order to be within the systems engineering formalism. Moreover, it is necessary to identify how the probabilistic fusion of two different modules addressing the same task can be fused to derive hybrid solutions that meet the new requirements. If one represents the system as an execution graph wherein the nodes are data structures and the edges correspond to the transformations, a statistical characterization is associated with each edge in the graph. The total system analysis essentially provides the relationship between the final output statistics and the input statistics as a function of all the system parameters. The replacement of a module within the larger system corresponds to the change of an edge in the graph. In order for the total systems analysis performed in the previous cycle to be re-usable, one has to choose a new module that satisfies the statistical distribution conditions for the input and output data types. Thus, the second point is needed to not re-do the entire system analysis phase as a result of modification of the input/output distribution in one module of the system. In situations where no existing external module satisfies this constraint, we propose to devise a wrapper transformation that essentially molds the external module and makes its statistical interfaces consistent with the existing framework.

[0018] FIG. 2 is a block diagram of a computer processing system 200 to which the present invention may be applied according to an embodiment of the present invention. The system 200 includes at least one processor (hereinafter processor) 202 operatively coupled to other components via a system bus 204. A read-only memory (ROM) 206, a random access memory (RAM) 208, a display adapter 210, an I/O adapter 212, an audio adapter 213, and a user interface adapter 214 are operatively coupled to the system bus 204.

[0019] A display device 216 is operatively coupled to system bus 204 by the display adapter 210. A disk storage device (e. g., a magnetic or optical disk storage device) 218 is operatively coupled to the system bus 204 by the I/O adapter 212. A speaker 219 is operatively coupled to the system bus 204 by the audio adapter 213.

[0020] A mouse 220 and a keyboard 224 are operatively coupled to the system bus 204 by the user interface adapter 214. The mouse 220 and the keyboard 224 are used to input and output information to and from the system 200.

[0021] Those skilled in the art will recognize that the exemplary computer processing system 200 illustrated in FIG. 2 is not intended to limit the present invention. Those skilled in the art will appreciate that other alternative computing environments may be used without departing from the spirit and scope of the present invention.

[0022] Referring to FIG. 3, the wrapper transformation approach includes identifying modules influenced by the translation of the relaxation in the application constraints (300), finding modules that satisfy the engineering constraints mentioned above (310), performing statistical analysis characterization of the replacement modules (or their hybrid design variations obtained by fusing existing modules with the replacement modules) (320), developing a wrapper that enables us to integrate it with the existing system with no re-analysis phase (330), and integrating the wrapper into the existing system (340). Once the design is accomplished, the validation and test phase follows.

[0023] The present invention discusses the statistical modeling and performance characterization of a dual-camera surveillance system. More particularly, we develop a system configuration so that application specific priors in the 3D geometry, camera geometry, the illumination model parameters, and object interaction/motion parameters are taken into account during the design of the object detection and zooming system. Further, we describe how it is possible to meet various real-time constraints while satisfying accuracy constraints (under certain restrictive assumptions). We illustrate how the application specific priors influence the choice of the system architecture and illustrate how perturbations can be propagated through the chosen surveillance system configuration involving change detection, people detection, people location determination and camera parameter estimation. The system estimates the foot positions and head positions of persons in omni-directional camera video and uses a foveal camera (a standard pan-tilt perspective camera) to zoom on the persons head based on the person location information.

[0024] An objective is to describe how this system can be refined to handle less restrictive input conditions while retaining most of the original system design intact. One goal is to apply the system to quasi-outdoor settings (i. e., lobbies with external illumination) with minimal re-design and analysis effort. (See Table 1 for the relaxed constraints). If the old system was designed to handle shadow effects and changes in camera gain, the new system must also handle slow changes in the background and fast changes between multiple background modes. The system needs to operate 24 hours a day, 7 days a week in an office building entrance lobby, that is lit by artificial light during night and primarily natural light during day time.

[0025]

	TABLE 1
	Previous System Constraints	New System Features
	Constant background	Changing background
	Constant illumination	Variable illumination
	Single mode background	Multi-modal background
	Restricted operational in black	Operational on full
	and saturated background areas	sensor input range

[0026] Since the constraint being relaxed has to do with illumination, we need to replace the relevant illumination invariant module in the original system. As we will see, the original system used the prior knowledge that the scene consisted of light sources with same spectra but arbitrary intensities. No background adaptation to handle the changes in spectra was done. The relaxation of this application constraint necessitates the use of a background adaptation module. In our review of the literature, we could not find a module that satisfies the requirements that the output distribution of the background adaptation module is of the form suitable for input into our people detection module. Therefore, we developed a technique which combines the advantages of our existing change detection module with the advantages of the background adaptation algorithm by Stauffer-Grimson. We will see that this fusion itself presents differences in the output feature space. We address this by adding an augmentation module that alters the output data to be in the same feature space.

[0027] We briefly describe our illumination invariant change detection method based on normalized color. The module takes as input a vector ({circumflex over (R)}, Ĝ, {circumflex over (B)})^T which is assumed to be normal distributed with mean (R, G, B)^T and covariance matrix Σ=diag(σ_R², σ_G², σ_B²), normalizes it by Ŝ={circumflex over (R)}+Ĝ+{circumflex over (B)} and provides a distance metric {circumflex over (d)}² between the current values {circumflex over (μ)}_c=({circumflex over (r)}_c, ĝ_c)^T and a background representation {circumflex over (μ)}_b=({circumflex over (r)}_c, ĝ_c) in the normalized space, where

[0028] $\hat{r}=\frac{\hat{R}}{\hat{S}},\text{and}\hat{g}=\frac{\hat{G}}{\hat{S}},$
when subscripts b, c for background respectively current image are omitted. The probability of a pixel being background corresponds to the distance measure

[0029] $\begin{array}{cc}{\hat{d}}^2={\left({\hat{\mu }}_b-{\hat{\mu }}_c\right)}^T{\left(2\sum _{{\hat{r}}_b,{\hat{g}}_b}\right)}^{-1}\left({\hat{\mu }}_b-{\hat{\mu }}_c\right)\text{with}\sum _{{\hat{r}}_b,{\hat{g}}_b}=\frac{{\sigma }_S^2}{S^2}\left(\begin{array}{c}\frac{{\sigma }_R^2}{{\sigma }_S^2}\left(1-\frac{2R}{S}\right)+\frac{R^2}{S^2}-\frac{{\sigma }_G^{2}R+{\sigma }_R^{2}G}{{\sigma }_S^{2}S}+\frac{\mathrm{RG}}{S^2}-\\ \frac{{\sigma }_G^{2}R+{\sigma }_R^{2}G}{{\sigma }_S^{2}S}+\frac{\mathrm{RG}}{S^2}\frac{{\sigma }_G^2}{{\sigma }_S^2}\left(1-\frac{2G}{S}\right)+\frac{G^2}{S^2}\end{array}\right)& \left(1\right)\end{array}$

[0030] where σ_S²=(σ_R²+σ_G²+σ_B²).

[0031] Note, that in the normalized space the covariance matrix Σ_{{circumflex over (r)}b,ĝb} for each pixel is different. This method was proved to perform very precisely and accurately in indoor situations with static illumination within our module framework, but it is not suitable for situations of varying light conditions and changes in the background. Due to the nature of normalization, this module ignores cues provided by the signal intensity. Key-features are invariance against shadows and changes in camera gain, and the notion of sensor uncertainty. Nevertheless, the miss detection rate is high in areas that are dark and saturated due to the large uncertainty in the normalized color space. It also fails when the input has no color information.

[0032] The statistical characterization for the normalized color segmentation module can be summarized as follows: For normal distributed input parameters {circumflex over (R)}, Ĝ, {circumflex over (B)}, the output statistic {circumflex over (d)}₂ (see Equation 1) is x² distributed with two degrees of freedom for background pixels. For object pixels, {circumflex over (d)}₂ can be approximated by a non-central x² distribution with two degrees of freedom, and non-centrality parameter c. {circumflex over (d)}₂ is exactly non-central x² distributed with two degrees of freedom if the covariance matrix for background and foreground are identical.

[0033] In the paper “Adaptive Background Mixture Models for Real Time Tracking,” Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 246–252, (IEEE, 1999), Stauffer and Grimson propose a background adaptation scheme that adapts to slowly drifting multi modal background intensities. They model each pixel as a mixture of K Gaussians with weights w_i, means μ_t, variances σ_i² and use an on-line approximation to update the model. They introduce a pixel labeling process, which is primarily based on the assumption that the least frequently occurring component in the mixture with large variance is more likely to be objects. This is done by the use of a threshold T that is based on the prior probability of a pixel being background. A pixel is labeled “background”, if it is closest in distance to one of the top B distribution components in the mixture where B=arg min_b(Σ_k=0^bw_k>T). The model parameters for the mode μ_i, variance σ_i², and weight w_i, which represent the current data best are updated following an exponential forgetting scheme with learning constant α. Pixels which are outside an 2.5σ_i-interval around each of the K modes are labeled “object” and modeled by a new Gaussian distribution. The mean of this Gaussian corresponds to the current pixel value, the variance is initialized with a high value σ_init², its weight w_init with a small value. The new mode replaces the background mode with least supporting evidence.

[0034] To characterize the statistical behavior of background adaptation module, we conducted numerous experiments on real data as well as on simulated data with similar results. We generated random samples from a mixture distribution with model parameters w_i, μ_t, σ_i² with iε{0, 1, 2, 3}. Table 2 shows the parameter settings used along with the ideal model parameters used. Initializations for the modes of the components were done randomly or in a deterministic fashion. For instance, in the example shown, we initialized all modes with the same parameters: w=1.88, μ=0, σ_i²=25 except for the first mode's mean, which we initialized with 10.

[0035]

TABLE 2
T	Winit	σinit2	α	w0	w1	w2	w3	μ0	μ1	μ2	μ3	σ02	σ12	σ22	σ32
0.9	0.05	25.0	0.03	0.05	0.16	0.3	0.4	10	50	150	205	0.3	0.3	0.3	0.3

[0036] The experimental analysis shows that only the modes of the mixture distribution are estimated and tracked correctly. The variance and the weights are unstable and unreliable. They do not track the data and do not converge. Even though the experiment uses a random sample from a stationary mixture distribution, the variance and weights tend to oscillate arbitrarily and are frequently re-initialized. Even if we assumed that the parameters do converge, for every sample that falls outside all of the 2.5σ-intervals, a new mode is introduced and initialized with a high variance and a small weight. For samples from the background mixture this occurs in approximately 1% of the cases. In other words, for every pixel the introduction of the new mode occurs on an average of less than every 10 seconds if the system processes more than 10 frames per second. Depending on the update factor α the model parameters σ_k,t², and w_k,t are somewhere between the initial and the true value but do not represent the parameters of the true underlying background distribution. Since the variances are not constrained to have a lower-bound, variances from most frequently occurring modes are constantly reduced and become significantly smaller than the true variances, such that this new mode introduction happens even more often. This is not a problem in the original implementation because the weights and the variances are not used in any way in a subsequent processing step. They use connected components followed by a region size threshold to prune false detection. On the contrary, in our methodology, we need to characterize the stability of these estimates in order to determine how they can be fused to another module and do the systems analysis. Since the experiments show the mean estimates are stable, we will explicitly use this feature to develop the hybrid algorithm. We further note, that the estimated modes are approximately normal distributed such that the difference between the current measurement and the closest background mode is approximately normal distributed with zero-mean and a covariance that is different from model parameter σ_i².

[0037] We now show how to fuse two modules statistically correctly to obtain a modified system to meet the old and newly added requirements simultaneously (FIG. 4 shows the block diagram). The main essence in the fusion algorithm is as follows. The change in background is modeled as two separate effects: one is the change due to the illumination spectrum and non-linear dynamics and the other is the change due to sudden camera gain/shadow changes. The Stauffer-Grimson (SG) algorithm is ideally suited to deal with changes in the illumination spectrum and slow dynamics, while the normalized color change detection algorithm is invariant to gain and shadows. By using SG algorithm first and feeding its internal state to the normalized color change detection algorithm we gain the advantages of both. We still have two issues to contend with: a) the SG algorithm does not discriminate between shadows and objects and b) the normalized color module fails when the input signal has no color and its discrimination power diminishes in dark and saturated areas. We will show that these problems can be solved by augmenting the SG algorithm to handle shadow information and by proper statistical fusion of the two algorithm outputs. The added requirement is that after we have done the fusion the output of the fused algorithm must have the same output distribution suitable for integration into the original system.

[0038] We have seen that an analysis of the Stauffer-Grimson module demonstrated that the modes of the mixture are stable within a time window. Further the distribution of estimated modes can be approximated by normal distributions thus matching the input distributional assumptions for the normalized color module. Therefore, we can use these estimates to compute μ_b and Σ_{{circumflex over (r)}b,ĝb} in our normalized-color background model. Formally, given a current pixel measurement {circumflex over (v)}_c, let the background mode from the SG algorithm mixture distribution closest in distance to the current measurement be μ_min, then μ_b=({circumflex over (r)}_min, ĝ_min) the normalized color values for the RGB vector μ_min. The covariance matrix Σ_{{circumflex over (r)}b,ĝb} is still the same as in the previous section description (dependent only on the sensor noise and the means value μ_min). Let {circumflex over (m)}u_c correspond to the normalized color vector corresponding to the measurement {circumflex over (v)}_c. The Mahalanobis distance {circumflex over (d)}² between the current normalized color value obtained from {circumflex over (μ)}_c and μ_b is used as the shadow/gain invariant change detection measure. The distribution of this statistic is approximately chi-squared distributed with 2 degrees of freedom.

[0039] As discussed above, the normalized color information should be augmented with intensity information to deal with dark/saturated areas and when no color information is present in the signal. Therefore, we apply the Stauffer-Grimson algorithm also to gray scale values I=(R+G+B)/3 and search for representation which allows statistically correct fusion of the two representations. The SG algorithm is not designed to distinguish between shadow and object pixels. They are both labeled as object, since they occur simultaneously and have large variance. Therefore, we add a computational test that augments the grayscale background state model in SG to include a shadow component. Under this assumption that shadow pixel values are multiplicative factors (identical in each color band) of the corresponding background color, pixels that are labeled as non-background pixels by the original SG algorithm are further classified as being shadow or object. This is done based on a classical statistical hypothesis test for the current pixel being shadow. Along with a label, this method also provides a probability that the given label is correct. Formally, the number of background modes is augmented to be B+1 where the last mode is the shadow mode. Let μ_i, i=1, . . . , B+1's denote the means of background mixture model for a given pixel. The distance between the current intensity value Î_c and the closest μ_i's, denoted by Î_b, is used as the change detection measure. Denote this minimum distance by d′. The distribution of this statistic is also approximated by a Gaussian distribution. Note that the σ values provided by SG algorithm are not used in this distance measure because of their instability. Moreover, the variance of the estimated mode is not the same as the variances of the components of the mixture. The variance of the estimated mode is obtained through an analysis of the empirical distribution of {circumflex over (d)}′ for the background pixels. The local fluctuations in the modes of the mixture distribution (within a small window of time) are primarily assumed to be due to a global illumination effect such as camera gain. Therefore, the trimmed standard deviation of the histogram of {circumflex over (d)}′ is used as an estimate of the standard deviation (σ_Îb) of Î_b.

[0040] The final goal is to statistically fuse the normalized color feature with the shadow invariant intensity feature such that the new feature statistic has the same characteristic as the old one. This is important in order to ensure that the modules which follow in the original system and take this new statistic as input can still be used, and the systems analysis conducted earlier remains valid. Therefore, we need to find a feature for the augmented intensity representation that will provide a change detection measure that is x² distributed, since the original test statistic {circumflex over (d)}² was also x² distributed (see Equation 1). Knowing from the analysis that the means are stable and approximately normal distributed, we define a Mahalanobis distance {circumflex over (d)}′² similar to {circumflex over (d)}² as proposed in Equation 1:

[0041] ${\hat{d}}^{\mathrm{\prime 2}}={\left(\begin{array}{c}{\hat{r}}_b-{\hat{r}}_c\\ {\hat{g}}_b-{\hat{g}}_c\\ {\hat{I}}_b-{\hat{I}}_c\end{array}\right)}^T{\left(2\sum _{{\hat{r}}_b,{\hat{g}}_b,{\hat{I}}_b}\right)}^{-1}\left(\begin{array}{c}{\hat{r}}_b-{\hat{r}}_c\\ {\hat{g}}_b-{\hat{g}}_c\\ {\hat{I}}_b-{\hat{I}}_c\end{array}\right)\text{with}$ $\left(\begin{array}{c}{\hat{r}}_b-{\hat{r}}_c\\ {\hat{g}}_b-{\hat{g}}_c\\ {\hat{I}}_b-{\hat{I}}_c\end{array}\right)~N\left(\left(\begin{array}{c}{\mu }_b-{\mu }_c\\ I_b-I_c\end{array}\right),2\sum _{{\hat{r}}_b,{\hat{g}}_b,{\hat{I}}_b}\right)$
with I_c denoting the current intensity value and I_b denoting the mode in the background mixture that is closest to I_c. Experiments show that the correlation between normalized color representation and the intensity based mixture model is negligible such that the new change detection measure:

[0042] ${\hat{d}}^{\mathrm{\prime 2}}={\hat{d}}^2+\frac{{\left({\hat{I}}_b-{\hat{I}}_c\right)}^2}{2{\sigma }_{{\hat{I}}_b}^2}$
where {circumflex over (d)}² is identical with the output of the change detection module for normalized color. Thus, we know that under the given conditions {circumflex over (d)}′² is approximately central x² distributed with 3 degrees of freedom for object pixels. This shows that the distributional form of the statistic which serves as input for the next module in our original system remains the same and the modules may remain untouched. The only difference is in the parameter of the distribution. The number of degrees of freedom changes from 2 to 3 in this case.

[0043] We have verified that new modifications to the system results in output statistics that are the same as that required by other components in our original system. Therefore, the systems analysis for the original system remains untouched and there is no need to re-do the theoretical analysis and validation experiments. However, we do need to check whether the approximation error introduced in the new module affect the final performance of the system and verify this in real experiments.

[0044] Our real experiments followed a similar protocol. The correctness of the pan, tilt, and zoom parameters estimated by our modules are compared against ground truth values of these control parameters to estimate the mean and variances of the running system. First, we marked six position P1–P6 of different radial distances and pan angles. Position, and test persons were chosen to simulate different positions, illuminations, and contrast. In the following table, we show the final foveal camera control parameters for one person. Ground truth values for the mean values were taken by measuring tilt angle α, and pan angle β by hand, and are compared against the corresponding mean of system measurements estimated from 100 trials per position and person. The variances calculated by the system for pan and tilt angles are compared against the corresponding variance-estimates calculated based on the theoretical analysis. The comparison between system output and ground truth demonstrates the closeness between theory and experiment (Table 3). The camera control parameters as well as the zoom parameter are functions of the geometry, as well as of the current uncertainties in the position estimates of the person. The more certain the estimate the more we can afford to zoom in. The uncertainties are functions of the current scene, quality of segmentation, geometry, and calibration uncertainties.

[0045]

TABLE 3
×10−5	P1	P2	P3	P4	P5	P6
{tilde over (σ)}sin{circumflex over (β)}2	37.3	35.9	63.1	83.0	142	220
{circumflex over (σ)}sin{circumflex over (β)}2	36.4	38.1	112	60.5	139	221
{tilde over (σ)}tan{circumflex over (α)}2	0.332	0.211	0.128	0.255	0.825	0.932
{circumflex over (σ)}tan{circumflex over (α)}2	0.271	0.206	0.120	0.252	0.832	0.904

[0046] One objective was to study the engineering design and test cycle through a case study involving the systematic engineering of a dual-camera video surveillance system for people detection and zooming. An important point we wish to make is that by following rigorous systematic engineering principles, one can minimize re-design and analysis efforts required to extend functionality of a vision system. The key conclusion is that by choosing appropriate modules and suitable statistical representations, we are able to re-use existing system design, software, and performance analysis results. We demonstrated this in the context of a dual-camera surveillance system for people detection and zooming. A new change detection algorithm fusing two different change detection algorithms was devised. One dealt with camera gain changes and shadows, while another dealt with dynamic illumination changes. The strengths of both these algorithms were retained, while their individual limitations were compensated by each other. The integration was done by paying attention to how the change detection component interfaces with the rest of the existing system. The system was successfully tested in the lobby scenario and was able to deal with shadows, gain control changes, dark and saturated measurements, and varying illumination conditions (over 24 hours per day, night, natural and artificial lighting). High sensitivity was achieved in detection while retaining precise and data-driven adaptive zooming of a person's head.

[0047] Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention.