Abstract:
A crowd segmentation system and method is described. The system includes a digital video capturing subsystem and a computing subsystem. The computing subsystem utilizes an emergent labeling technique to segment a crowd into individuals. The emergent labeling technique employs algorithms which can be used iteratively to place vertices associated with feature points in a captured digital video image into multiple cliques and, ultimately, in a single clique.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims the benefit of U.S. provisional application No. 60/570,644 filed May 12, 2004, which is incorporated herein in its entirety by reference. 
     
    
       [0002]     The invention relates generally to a system and method for identifying discrete objects within a crowded environment, and more particularly to a system of imaging devices and computer-related equipment for ascertaining the location of individuals within a crowded environment.  
         [0003]     There is a need for the ability to segment crowded environments into individual objects. For example, the deployment of video surveillance systems is becoming ubiquitous. Digital video is useful for efficiently providing lengthy, continuous surveillance. One prerequisite for such deployment, especially in large spaces such as train stations and airports, is the ability to segment crowds into individuals. The segmentation of crowds into individuals is known. Conventional methods of segmenting crowds into individuals utilize a model-based object detection methodology that is dependent upon learned appearance models.  
         [0004]     Also, automatic monitoring of mass experimentation on cells involves the high throughput screening of hundreds of samples. An image of each of the samples is taken, and a review of each image region is performed. Often, this automatic monitoring of mass experimentation relates to the injection of various experimental drugs into each sample, and a review of each sample to ascertain which of the experimental drugs has given the desired effect. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0005]     FIGS.  1 (A)-(C) illustrate the evolution of cliques in accordance with an exemplary embodiment of the invention.  
         [0006]     FIGS.  2 (A)-(C) illustrate the segmentation of a crowd into individuals in accordance with an exemplary embodiment of the invention.  
         [0007]     FIGS.  3 (A)-(E) illustrate the clustering and evolution of cliques to provide segmentation of a crowd into individuals in accordance with an exemplary embodiment of the invention.  
         [0008]     FIGS.  4 (A)-(C) illustrate the clustering and evolution of cliques to provide segmentation of a crowd into individuals in accordance with an exemplary embodiment of the invention.  
         [0009]      FIG. 5  is a schematic representation of a crowd segmentation system constructed in accordance with an exemplary embodiment of the invention.  
         [0010]     FIGS.  6 (A) and (B) illustrate initial and final binary matrices in accordance with an aspect of the invention.  
         [0011]      FIG. 7  illustrates a system for segmenting a crowded environment into individual objects in accordance with an exemplary embodiment of the invention. 
     
    
     SUMMARY  
       [0012]     One exemplary embodiment of the invention is a system for segmenting crowded environments into individual objects. The system includes an image capturing subsystem and a computing subsystem. The computing subsystem utilizes an emergent labeling technique to segment a crowded environment into individual objects.  
         [0013]     One aspect of the exemplary system embodiment is that the image capturing subsystem is a digital video capturing that is configured to detect feature points of objects of interest.  
         [0014]     Another exemplary embodiment of the invention is a method for segmenting a crowded environment into individual objects. The method includes the steps of capturing an image of a crowded environment, detecting feature points within the image of the crowded environment, associating a vertex with each of the feature points, and assigning each vertex with a single clique.  
         [0015]     Another exemplary embodiment of the invention is a method for segmenting an environment having multiple objects into individual objects. The method includes the steps of digitally capturing an image of an environment having multiple objects, detecting feature points within the image of the multiple objects, associating a vertex with each of the feature points, and assigning each vertex to a single clique and thereby segmenting individual objects from the multiple objects.  
         [0016]     These and other advantages and features will be more readily understood from the following detailed description of preferred embodiments of the invention that is provided in connection with the accompanying drawings.  
       DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS  
       [0017]     An alternative methodology to the conventional methods for segmenting crowded environments into individual objects includes utilizing an emergent labeling technique that makes use of only low-level interest points. The detection of objects of interest, such as, for example, individuals in a crowded environment, is formulated as a clustering problem. Feature points are detected, via the use of an imaging device, such as, for example, a digital video device such as a digital camera or a scanner or other analog video medium in conjunction with an analog-to-digital converter. The feature points are associated with vertices of a graph. Two or more vertices are connected with edges, based on the plausibility that the two vertices could have been generated from the same object, to form clusters. A cluster is a grouping of vertices in which each of the vertices is connected by an edge with at least one other vertex. From the clusters, cliques are identified. Cliques are a subset of clusters and are groupings of vertices in which all the vertices are connected to all the other vertices in the grouping.  
         [0018]     The main goal in image measurement is the identification of a set of interest points, V={v i }, that can be associated in a reliable way with objects of interest, such as, for example, individuals. As a first step, a probabilistic background model is generated. Then, image locations indicating high temporal and/or spatial discontinuity are selected as feature points. Each feature point is associated with a vertex plottable on a graph G. There exists an edge e ij  between a pair of vertices v i  and v j  if and only if it is possible that the two vertices could have been generated by the same individual. The strength a ij  of the edge e ij  may be considered a function of the probability that the two connected vertices belong to the same individual. Alternatively, the strength a ij  also may be a function of a given clique.  
         [0019]     Given the vertices embedded in a graph G, a goal is to determine the true state of the system. This issue is compounded in that (1) the number of individual objects in the scene is unknown, and (2) if there is little separation between individual objects, the inter-cluster edge strengths could be as strong as the intra-cluster edge strengths. Under crowded situations, conventional clustering algorithms, such as k-means and normalized cut, may not be useful, since such clustering algorithms presume that intra-cluster edge strengths are considerably stronger than inter-cluster edge strengths.  
         [0020]     Instead, an emergent labeling algorithm may be used. For a set of vertices within a clique c, there exists a line between every pair of the vertices in c. A maximal clique c max  on graph G is a clique that is not a subset of any other clique on graph G. In the emergent labeling algorithm, each vertex cluster in the estimate of the true state must be a clique on the graph G. The assignment of each vertex to a clique may be represented by a binary matrix L ( FIG. 6 (A)), where if v i  is assigned to c j  then L ij =1, otherwise L ij =0. Since each vertex can be assigned to only one maximal clique c max , the sum of all elements of each row of L must equal one.  
         [0021]     It has been observed that making vertex assignment decisions based solely on local context can be confusing. A global score function S(L) is utilized such that vertex assignment decisions are made on both local and global criteria. One criterion for judging the merit of a cluster is to take the sum of the edge strengths connecting all the vertices inside the cluster. The global score function S(L) can be computed from the following: 
 
 S ( L )=trace( L′AL ) 
 
 where A is an affinity matrix such that a ij  is equal to the edge strength of edge e ij . The assignment matrix L defines a sub graph of G where all edges that connect vertices that have been assigned to different cliques are removed. The global score function S(L) essentially is the sum of the edge strengths in that sub graph. 
 
         [0022]     Next, the optimal labeling matrix L must be found with respect to the optimization criteria S. Optimal labeling matrix L is initially viewed as a continuous matrix so that each vertex can be associated with multiple cliques. After several iterations, the matrix is forced to have only binary values. For iteration t+1, a soft assign procedure will be used as follows: 
 
 r   ij ( t+ 1)= e   βdS(L(t))/dLij  
 
 The derivative dS(L(t))/dLij=A i L j (t) where A i  is the i th  row of A and L j (t) is the j th  column of L(t). If the vertex v i  is not a member of clique c j , then r ij (t+1)=0, and the label coefficient equations is now defined as: 
 
 L   ij ( t+ 1)= r   ij ( t+ 1)/Σ k   r   ik ( t+ 1). 
 
 Initially, all label values for each vertex are uniformly distributed among the available cliques ( FIG. 6 (A)). After each iteration, the value of β increases, and thus the label for the dominant clique for each vertex gets closer to one and the rest of the labels approach zero ( FIG. 6 (B)). The optimal label matrix, as β approaches infinity, is then estimated to be defined as: 
 
 L   opt   =lim L   β . 
 
         [0023]     The aforementioned soft assign technique propagates assignment from high to low certainty across the graph. If a vertex is a member of a large number of maximal cliques, then based on local context there is much ambiguity. This occurs most often for vertices that are in the center of the foreground pixel cluster. Vertices near the periphery of the cluster, on the other hand, may be associated with a relatively small number of cliques. These lower ambiguity vertices help strengthen their chosen cliques. As these cliques get stronger through iterations, they begin to dominate and attract the remaining less certain vertices. This weakens neighboring cliques which lowers the ambiguity of vertices in the region.  
         [0024]     Referring now to FIGS.  1 (A)-(C), there is shown, via a synthetic experiment, the evolution of clique strength over time through the use of the soft assign technique.  FIG. 1 (A) shows an initial graph structure  10  in which all the vertices  12  are connected to adjacent vertices  12  with edges  14 .  FIG. 1 (A) is essentially the initial grouping of all the vertices into a cluster.  FIG. 1 (B) shows the evolution of cliques from the cluster shown in the initial graph structure  10 . The top left graph of  FIG. 1 (B) shows the clique centers  18 , while the remaining graphs in  FIG. 1 (B) illustrate the evolution of clique strength over time.  FIG. 1 (C) illustrates the identified cliques  16  in the final graph structure  10 ′.  
         [0025]     People are, on the whole, roughly the same height and stand perpendicular to the ground. As such, the foot plane and the head plane can be defined. Two homographies, H f  and H h , map the imaging planes for, respectfully, the foot and the head. If foot pixels p f  and head pixels p h  identified from a camera or other video medium are from the same person and the person is assumed to be standing perpendicular to the floor, then: 
 
 H   h   p   h   αH   f   p   f . 
 
 Further, a mapping between the foot pixel p f  and the head pixel p h  can be defined as: 
 
 p   h   αH   h   −1   H   f   p   f . 
 
         [0026]     An aspect of the invention may be separating pixels into foreground pixels and background pixels. When considering a foreground pixel clustering, the center pixel is set to a foot pixel, and the head pixel is determined via the homography H h   −1 H f . The height vector runs from the foot pixel to the head pixel. From an overhead angle, the width of each individual is assumed to be relatively constant. The width vector is set to be perpendicular to the height vector. By warping a local image, the individuals can be contained in a width w by height h bounding box. Head to foot mapping is valid given a minimum of four head to foot pixel pairs.  
         [0027]     A set of maximal cliques is to be determined from the clustering. Maximal cliques are those cliques in which respective vertices are correctly identified as belonging in their respective cliques. Conceptually, if a window that is sized w by h is placed in front of the foreground patch, the vertices inside the window constitute a clique. Upon any change in the set of interior vertices, a new clique is formed.  
         [0028]     Given a partitioning function Ω, a vertex for each partition may be defined by the equation: 
 
 v   i =max  v   εΩi   |▾|I−B *φ δ |( v ), 
 
 where φ δ  is a suitable band pass filter, I is the current image, and B is the background image. Vertices having a value below a given threshold are rejected from a particular clique. An orientation vector is associated with each vertex, and it is computed directly from the gradient of the absolute difference image. It is presumed that the background surrounds most individuals, and it is also assumed that most vertices are located on the boundary of an individual. Since the absolute difference is computed, the vertices located at the boundary of each individual should be pointing toward the center of the individual. 
 
         [0029]     To determine edge strength between two vertices, it may be assumed that both of the vertices are on the periphery of an individual&#39;s outline. From an overhead vantage point, each individual&#39;s shape is determined to be roughly circular. Since the orientation of each vector should be pointing toward the center of the individual, the following model is defined: 
 
ω j =π−ω i +2ω ij , 
 
 where ω j  is the orientation of the vertex i, ω j  is the orientation of the vertex j, and ω ij  is the orientation of the line between the vertices i and j. The strength a ij  of the edge e ij  may be defined as: 
 
 a   ij =1.0−|ω j −(π−ω i +2ω ij )|/π
 
 It should be appreciated that this is only one way to ascertain the strength a ij . One alternative way is to define more meaningful descriptors for vertices, such as head vertices and limb vertices. Classifiers on types of vertices and edge strength a ij  would represent consistency between the spatial relationship of vertices and the type of classification. 
 
         [0030]     With specific reference to FIGS.  2 (A)-(C), a foreground patch is broken up into clusters, and eventually, into maximal cliques.  FIG. 2 (A) illustrates a view from overhead of groupings of vertices  20 ,  22 ,  24 , and  26 .  FIG. 2 (B) illustrates clusters  20 ′,  22 ′,  24 ′, and  26 ′ formed from, respectively, the groupings of vertices  20 ,  22 ,  24 , and  26 . Finally, individual vertices are mapped over the image in the identification of maximal cliques  20 ″,  20 ″,  22 ″,  24 ″, and  26 ″ in  FIG. 2 (C).  
         [0031]     An example of the emergent labeling paradigm is shown in FIGS.  3 (A)-(E). A rectified image is generated using the foot to head transform H h   −1 H f p f . The gradient of the absolute background difference image is calculated and shown as  30   a  ( FIG. 3 (A)) and the oriented vertices are extracted and shown as  30   b  ( FIG. 3 (B)). An initial edge strength for the graph is shown as  30   c  in  FIG. 3 (C), while a final edge strength for the graph is shown as  30   d  in  FIG. 3 (D). The resulting state of the emergent labeling algorithm is shown as  30   e  in  FIG. 3 (E). One of the challenging problems is that the right hand pair of people  32  are close to one another, and the inter edge strengths between the vertices of these two individuals is strong, making it difficult for standard clustering algorithms to function properly.  
         [0032]     FIGS.  4 (A)-(C) also illustrate an extremely crowded case. An initial edge strength for the graph is shown as  40   a  in  FIG. 4 (A), while a final edge strength for the graph is shown as  40   b  in  FIG. 4 (B). The resulting state of the emergent labeling algorithm is shown as  40   c  in  FIG. 4 (C).  
         [0033]     The partitioning function L and the associated state X are computed deterministically. It is the uncertainty of which interest points are associated with foreground objects and their orientation that needs to be captured. Shadow regions may cause any number of interest points, and the orientation of each vertex can be misleading. Thus, an acceptance probability that a vertex v i , given the magnitude of its response r, is a foreground vertex should be derived. The acceptance probability can be written as: 
 
 p ( vεF|r )= p ( r|vεF ) p ( F )/ p ( r ). 
 
 F denotes the foreground area. The distributions p(r|vεF), p(F), and p(r) are estimated from training data. The orientation confidence estimate is based on the background/foreground separation of the pixels. The confidence is based on the minimal distance to a background pixel location. 
 
         [0034]      FIG. 5  schematically illustrates a segmentation system  45  that includes an image capturing device  50 , such as a digital video camera or a scanner and an analog-to-digital converter, and a computing subsystem  52 . The computing subsystem  52  includes a computing component  54  that performs the calculations necessary for distinguishing foreground from background and to identify individuals within crowds.  
         [0035]     Although embodiments of the invention have been illustrated and described in terms of segmenting crowds into individual people, it should be appreciated that the scope of the invention is not that restrictive. For example,  FIG. 7  illustrates another embodiment of the invention. A segmentation system  145  is shown including an image capturing device  150 , a microscope  156 , and a computing subsystem  52 . The computing subsystem  52  includes a computing component  54 . A sample  158  is placed in front of the viewer of the microscope  156 . The image capturing device  150  captures the image of a region of the sample  158 . The image capturing device  150  may be either digital format or analog format in conjunction with an analog-to-digital converter. The digitized image captured by the image capturing device  150  is then transferred to the computing subsystem  52 . The computing component  54  performs the calculations necessary to identify individual cells within the region of the sample  158  captured. It is unnecessary to separate foreground and background regions, since everything within the region of the sample  158  captured is foreground.  
         [0036]     While the invention has been described in detail in connection with only a limited number of embodiments, it should be readily understood that the invention is not limited to such disclosed embodiments. Rather, the invention can be modified to incorporate any number of variations, alterations, substitutions or equivalent arrangements not heretofore described, but which are commensurate with the spirit and scope of the invention. Additionally, while various embodiments of the invention have been described, it is to be understood that aspects of the invention may include only some of the described embodiments. Accordingly, the invention is not to be seen as limited by the foregoing description, but is only limited by the scope of the appended claims.