Patent Publication Number: US-9886634-B2

Title: Video based matching and tracking

Description:
REFERENCE TO RELATED APPLICATION 
     This application is a continuation application of U.S. application Ser. No. 13/049,527 (now U.S. Pat. No. 8,600,172), the entirety of which is incorporated by reference. 
    
    
     BACKGROUND 
     Video tracking is the process of locating a moving object (or multiple objects) over time using a camera (or other image capturing device). Video tracking has a variety of uses, some of which include: security and surveillance; human-computer interaction; video communication and compression; augmented reality; traffic control; medical imaging; and video editing. Video tracking can be a time-consuming process due to the amount of data that is contained in video. Adding further to the complexity is the possible need to use object recognition techniques for tracking. 
     Typically, the objective of video tracking is to associate target objects in consecutive video frames. The association can be difficult when the objects are moving fast relative to the frame rate. Another situation that increases complexity of the problem is when the tracked object changes orientation over time. 
     Matching is an important component of the video tracking process in which part (or all) of a query image is matched to a part (or all) of another image. One general example is to match one image patch with a second image patch. A more specific example is to match one or more objects with one or more image patches in a query image. The object may be a person (or a part of a person, such as a face), a thing (such as an inanimate object), or the like. 
     One example of video tracking is illustrated in  FIG. 1 , which shows a simple example of image tracking a single object. In the present example depicted in  FIG. 1 , object A has been reliably tracked over three frames (shown to the left in  FIG. 1 ). In the fourth frame, which is referred to as the query frame, the goal is to locate the image patch (shown in shading in  FIG. 1 ) that corresponds to the object. In a more general scenario, there may be multiple objects that are matched and located in the query frame, and their corresponding image patches can overlap significantly. To add to this complexity, there can be lighting and appearance variation of an object from frame to frame. All this makes the task of matching a challenging problem. Therefore, a need exists to efficiently and accurately perform video tracking. 
     SUMMARY 
     An analytical device is disclosed that analyzes whether a first image is similar to (or the same as) as a second image. In a first aspect, the analytical device analyzes the first image by combining at least a part (or all) of the first image with at least a part (or all) of the second image, and by analyzing at least a part (or all) of the combined image. For instance, an abstraction of part or all of the first image may be combined with an abstraction of part or all of the second image. Part or all of the combination may be analyzed with respect to the abstraction of the first image and/or the abstraction of the second image. The abstraction may be based on a Bag of Features (BoF) description, based on a histogram of intensity values, or based on one or more other types of abstraction methodologies. The analysis may involve comparing one or more aspects of the combination (such as the entropy or randomness of the combination) with the one or more aspects of the abstracted first image and/or abstracted second image. Based on the comparison, the analytical device may determine whether the first image is similar to or the same as the second image. So that, if the entropy of the combined image increases a certain amount (such as increases minimally less than a predetermined level), the analytical device may conclude that the first image and the second image are similar. The analytical device may work with a variety of images in a variety of applications including a video tracking system, a biometric analytic system, or a database image analytical system. 
     In a second aspect, the analytical device may be a video tracking system that utilizes a Bag of Features (BoF) description in its analysis. The video tracking system attempts to track an object by determining whether an object is present in a query image. The query image may be broken down into one or more image patches, which may be different parts of the query image. The analytical device may analyze the one or more of the image patches in the query image to determine whether the object is present in the query image. The analysis may include determining whether one of the image patches in the query image is similar to the object being tracked. The BoF description of the image patch (and similarly the object) may represent a cloud of points in multidimensional feature space. The BoF description may be used in combination with the first aspect, described above. 
     In a third aspect, the object subject to tracking may be updated based on image patches matched from previous frames. The object may initially be defined in a variety of ways, such as using the characteristics of the image patch to which the object is first matched. In this way, the object is born or created. The tracking system then attempts to track the object in subsequent frames, using the tracking to update the definition of the object. 
     Other systems, methods, features and advantages will be, or will become, apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the following claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example of the matching problem in an object tracking scenario. 
         FIG. 2  is a block diagram of a system for analyzing one or more images. 
         FIG. 3  is a block diagram of a video tracking system. 
         FIG. 4  is a block diagram of a biometric analytical system. 
         FIG. 5  is a block diagram of database image analytical system. 
         FIG. 6  is an illustration of an abstraction of an image patch with points within the image patch described in terms of fundamental features. 
         FIG. 7  is one example of the construction of a Bag of Features (BoF) matrix B of an image patch with only five points in it, wherein each row in matrix B corresponds to point in the patch, and with the first, second and the third column of matrix B corresponds to the x-location, y-location and the grayscale value of the point(s). 
         FIG. 8  is an illustration of the BoF matrix B for the image patch being represented as a cloud of points in high dimensional feature space. 
         FIG. 9  is an illustration of two observation image patches, which are compared by first computing their BoF, followed by merging their probability density functions. 
         FIG. 10  is an illustration showing a sequence of the matching process, in which several subregions (shown in highlights) of an image patch are queried as possible matches to the object, with the BoF description for each subregion being computed separately, and the subregion that is closest to the object being chosen as the match. 
         FIG. 11  is an example of a flow diagram for matching an image patch to an object. 
         FIG. 12  is a table illustrating the change in asset scores corresponding to the reference datasets. 
     
    
    
     DETAILED DESCRIPTION 
     An analytical device is disclosed that analyzes whether a first image is similar to (or the same as) as a second image. In a first embodiment, the analytical device analyzes the first image by combining at least a part (or all) of the first image with at least a part (or all) of the second image, and by analyzing at least a part (or all) of the combined image. For instance, an abstraction of part or all of the first image may be combined with an abstraction of part or all of the second image. Part or all of the combination may be analyzed with respect to the abstraction of the first image and/or the abstraction of the second image. The abstraction may be based on a Bag of Features (BoF) description, based on a histogram of intensity values, or based on one or more other types of abstraction methodologies. The analysis may involve comparing one or more aspects of the combination (such as the entropy or randomness of the combination) with the one or more aspects of the abstracted first image and/or abstracted second image. For example, the analysis may comprise calculating a randomness parameter using the entropy measure based on information theory. Based on the comparison, the analytical device may determine whether the first image is similar to or the same as the second image. So that, if the entropy of the combined image increases minimally, the analytical device may conclude that the first image and the second image are similar. 
     The analytical device may work with a variety of images in a variety of applications. For example, the analytical device may comprise a video tracking system in which a part (or all) of the query frame may be compared with an object. The object may be defined based on matches to images in previous frames (such as an image patch in a previous frame or a combination of image patches in multiple previous frames). As another example, the analytical device may be used in biometrics. For example, in face biometrics, a query face image may be compared with one or more stored images, with the analytical device scoring and/or ranking the comparison of query face image with the one or more stored images. As still another example, the analytical device may be used to analyze images in large databases. In particular, the analytical device may analyze a query image in the database to determine whether the query image is similar with one or more stored images in the database (such as one or more separate images or one or more frames in a video). Similarity may be indicated based on a score and/or rank of the closeness of the query image with one, some, or all the stored images. 
     In a second embodiment, the analytical device may be a video tracking system that utilizes a Bag of Features (BoF) description in its analysis. The video tracking system attempts to track an object by determining whether an object is present in a query image. As discussed above, the object may be a person (or a part of a person), an object, or the like. The query image may be broken down into one or more image patches, which may be different parts of the query image. The analytical device may analyze the one or more of the image patches in the query image to determine whether the object is present in the query image. The analysis involves determining whether one of the image patches in the query image is similar to the object being tracked. The BoF description of the object and the image patches enable the capture of rich semantic information of the object and the image patch, and hence aid in better determining whether the object is similar to one of the image patches. In one aspect, the BoF description of the image patch (and similarly the object) represents a cloud of points in multidimensional feature space. The BoF description may be used in combination with the first embodiment, described above. 
     In a third embodiment, the object subject to tracking is updated based on image patches matched from previous frames. As discussed above, the object may be the person or thing being tracked in the video. The object may initially be defined in a variety of ways. One way is to assign the characteristics of the image patch to which the object is first matched. For example, after foreground/background segmentation, one or more image patches (or “blobs”) may be found in the current video frame (e.g., frame  1 ). If there are no objects in the current list to track, or if one of the image patches does not match to any of the objects on the current list to track, the image patch without a matched object may be used to characterize the object (e.g., image_patch frame 1 ). In this way, the object is born or created. The tracking system then attempts to track the object in subsequent frames. 
     In the subsequent frame, after foreground/background segmentation, one or more image patches are found in the current video frame (e.g., frame  2 ). Further, using image_patch frame 1 , the object is matched to one of the image patches in frame  2  (e.g., image_patch frame 2 ). After a match of the object to one of the image patches in frame  2 , the definition of the object is updated based on the match. For example, image_patch frame 1  and image_patch frame 2  may be used to define or characterize the object. In this way, the definition of the object may change dynamically from one frame to the next. In the instance where the image patch is defined as a cloud of points in a feature space, combining image_patch frame 1  and image_patch frame 2  may be accomplished by fusing the two clouds. 
     Referring to  FIG. 2 , there is illustrated an analytical device  210 , which may comprise an electronic device such as a computer. The analytical device  210  may include a controller  212 , such as a processor, microcontroller, or other type of arithmetic logic unit. The analytical device may further include a storage element  214 , which may comprise volatile and/or non-volatile memory, and may include one or more programs stored thereon. The storage element  214  may comprises an internal or externally accessible database, and may store one or more images. 
     The analytical device  210  may communicate, via a communication interface  216 , with an input/output device  220 . The input/output device  220  may be an input device, an output device, a combination of an input device and an output device, or a separate input device and a separate output device. As discussed subsequently, the analytical device  210  may work in combination with a video device (such as a video recorder or other device that records images and/or audio), as shown in  FIG. 3 , a biometric input device/control device, as shown in  FIG. 4 , or an image/video database, as shown in  FIG. 5 . 
     The storage element  214  may be a main memory, a static memory, or a dynamic memory. The storage element  214  may include, but may not be limited to, computer-readable storage media such as various types of volatile and non-volatile storage media including, but not limited to, random access memory, read-only memory, programmable read-only memory, electrically programmable read-only memory, electrically erasable read-only memory, flash memory, magnetic tape or disk, optical media and the like. 
     In one case, the storage element  214  may include a cache or random access memory for the controller  212 . Alternatively or in addition, the storage element  214  may be separate from the controller  212 , such as a cache memory of a processor, the system memory, or other memory. The storage element  214  may be an external storage device or database for storing data. Examples may include a hard drive, compact disc (“CD”), digital video disc (“DVD”), memory card, memory stick, floppy disc, universal serial bus (“USB”) memory device, or any other device operative to store data. The storage element  214  may be operable to store instructions executable by the controller  212 . The functions, acts or tasks illustrated in the figures (such as  FIG. 11 ) or described herein may be performed by the programmed controller  212  executing the instructions stored in the storage element  214 . The functions, acts or tasks may be independent of the particular type of instruction set, storage media, processor or processing strategy and may be performed by software, hardware, integrated circuits, firm-ware, micro-code and the like, operating alone or in combination. Likewise, processing strategies may include multiprocessing, multitasking, parallel processing and the like. 
     The analytical device  210  may also include a communication interface  216  to enable communication with multiple devices via the network. The communication interface  216  may be created in software or may be a physical connection in hardware. The communication interface may be configured to connect with a network, external media, the display, or any other components in system, or combinations thereof. The connection with the network may be a physical connection, such as a wired Ethernet connection or may be established wirelessly as discussed below. Likewise, the additional connections with other components of the system may be physical connections or may be established wirelessly. 
     The analytical device  210  may optionally include a display, such as a liquid crystal display (LCD), an organic light emitting diode (OLED), a flat panel display, a solid state display, a cathode ray tube (CRT), a projector, a printer or other now known or later-developed display device for outputting determined information. The display may act as an interface for the user to see the functioning of the controller  212 , or specifically as an interface with the software stored in the storage element  214  or in the drive unit. 
     Additionally, the analytical device  210  may optionally include an input device configured to allow a user to interact with any of the components of system. The input device may be a number pad, a keyboard, or a cursor control device, such as a mouse, or a joystick, touch screen display, remote control or any other device operative to interact with the system. 
     The analytical device  210  may also optionally include a disk or optical drive unit. The disk drive unit may include a computer-readable medium in which one or more sets of instructions, e.g. software, can be embedded. Further, the instructions may perform one or more of the methods or logic as described herein. The instructions may reside completely, or at least partially, within the storage element  214  and/or within the controller  212  during execution by the computer system. The storage element  214  and the controller  212  also may include computer-readable media as discussed above. For example, the instructions to perform the actions illustrated in  FIG. 11  (described below) may be included in the storage element  214 . 
     The present disclosure contemplates a computer-readable medium that includes instructions or receives and executes instructions responsive to a propagated signal. The instructions may be implemented with hardware, software and/or firmware, or any combination thereof. Further, the instructions may be transmitted or received over the network via a communication interface  216 . 
     Referring to  FIG. 3 , there is illustrated a tracking device  310 , which may track one or more objects in a video or in a series of still images representing scenes of motion. The tracking device  310  includes a controller  212 , which may be the same as controller  212  in the analytical device  210 . The tracking device  310  further includes a storage element  314 , which may include volatile or non-volatile memory. The storage element  314  may store archival or historical video recordings or archival or historical still images, and may store real-time video recordings and still images. The tracking device  310  may also include a communication interface  316  in order for the tracking device  310  to communicate with a video device  320 . The video device  320  may be a video camera, or a still camera which is configured to obtain a series of still images. 
     Referring to  FIG. 4 , there is shown a biometric analytical device  410 , which may analyze one or more biometric inputs. The biometric analytical device  410  may include methods by which to uniquely recognize humans based upon one or more intrinsic physical or behavioral traits. For example, biometrics may be used as a form of identity access management and access control. Biometrics may also be used to identify individuals in groups that are under surveillance. 
     Biometrics may relate to physiological unique traits. Examples of such traits include, but are not limited to fingerprint, face recognition, DNA, Palm print, hand geometry, iris recognition, retinal scan, and odor/scent. Biometrics may also relate to the behavior of a person. Examples include, but are not limited to typing rhythm (e.g., keystroke dynamics), gait, and voice. 
     The biometric analytical device  410  includes a controller  212 , which may be the same as controller  212  in the analytical device  210 . The biometric analytical device  410  further includes a storage element  414 , which may include volatile or non-volatile memory. The storage element  414  may store the captured biometric (such as a copy of a particular person&#39;s or an identifiable fingerprint, face recognition, DNA, palm print, hand geometry, iris recognition, retinal scan, etc.). The storage element  414  may further store biometric inputs (such as an image) received from a biometric input device  420  in order to compare with the captured biometric. The biometric analytical device  410  may also include a communication interface  416  in order for the biometric analytical device  410  to communicate with the biometric input device  420  and a control device  430 . The biometric input device  420  may include a fingerprint scanner, a retinal scanner, an iris scanner, or the like. The control device  430  may control access to one or more areas and resources in a given physical facility or control access to a computer-based information system. For example, the control device  430  may control access to an area (such as an electronic lock), or may control access to an electronic device (such as a computer, a database, etc.). 
     Referring to  FIG. 5 , there is shown an image analytical device  510 , which may analyze one or more images. The image analytical device  510  may include methods by which to analyze multiple images stored on image database  520 . The image analytical device  510  includes a controller  212 , which may be the same as controller  212  in the analytical device  210 . The image analytical device  510  further includes a storage element  414 , which may include volatile or non-volatile memory, and may store still images and/or video. A sample image may be compared against one or more images stored in a database. The result of the comparison may be a determination of which of the images stored in the database are similar to the sample image. For example, the analysis may be used in order to reduce the number of duplicate images that are stored in a database. As another example, the analysis may be used to determine whether the sample image was present in an archival database. In particular, if a particular image (such as of a person) is designated as the sample image, the analysis may review the images in archival video footage to determine whether the person was present in any of the images of the database. 
     As discussed above, the analytical device  210  may compare two different abstractions, and determine whether the abstractions are similar to one another. As one example, the analytical device may compare an abstraction of a first image (or a part of the first image) with an abstraction of a second image (or a part of the second image). The abstractions may then be used to track an object, to analyze a biometric input, or to analyze an image in a database. As discussed in more detail below, there are several ways in which to abstract an image patch or an object, including without limitation, a BoF description and a histogram of intensity values. The abstraction of the first image (or a part of the first image) may be at least partly combined with the abstraction of the second image (or a part of the second image), and the combination may be analyzed to determine whether the first image (or the part of the first image) is similar to the second image (or the part of the second image). 
     Similarly, the abstraction of the object being tracked (or a part of the object being tracked) may be combined with the abstraction of a query image (or a part of the query image), and the combination may be analyzed to determine whether the object being tracked (or the part of the object being tracked) is similar to the query image (or the part of the query image). In particular, the analytical device may compare an object being tracked (such as a person&#39;s face or body) with an image patch in a query frame in order to determine whether the object is similar to the image patch in the query frame. The object may be represented by an abstract representation, as discussed in more detail below, so that the abstract representation of the object may be combined with the abstract representation of the image patch. The combination may be analyzed to determine whether the object (as defined by its abstract representation) is similar to the image patch (as defined by its abstract representation). 
     One type of abstraction is the BoF based description. BoF focuses on defining an object or an image (or a part of an image, such as an image patch) based on various features.  FIG. 6  illustrates an example of an application of the BoF based description.  FIG. 6  illustrates an image patch (show as the shaded blob), with points within the image patch represented as circles. The BoF description may focus on features at various parts of the image patch (such as at the points within the image patch as shown in  FIG. 6 ). The BoF based description may be represented mathematically in a variety of ways, such as by using a BoF matrix, B, which characterizes the image patch. Referring to the example depicted in  FIG. 6 , the image patch may constitute “N” points, where each point can be described in terms of fundamental features, such as its X location, its Y location, its color value, its grayscale value, etc. In general, if each of the N points is described in terms of M features, this would lead to a BoF matrix B, where 
     
       
         
           
             
               
                 
                   B 
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               f 
                               1 
                               1 
                             
                           
                           
                             
                               f 
                               1 
                               2 
                             
                           
                           
                             … 
                           
                           
                             
                               f 
                               1 
                               M 
                             
                           
                         
                         
                           
                             
                               f 
                               2 
                               1 
                             
                           
                           
                             
                               f 
                               2 
                               2 
                             
                           
                           
                             … 
                           
                           
                             
                               f 
                               2 
                               M 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             … 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               f 
                               N 
                               1 
                             
                           
                           
                             
                               f 
                               N 
                               2 
                             
                           
                           
                             … 
                           
                           
                             
                               f 
                               N 
                               M 
                             
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     In the example given as shown in Equation (1), the BoF matrix includes [x, y, YImage, cbImage, crImage, GradientInYImage, OrientationInYImage] as the 7 features that describe a point in the image patch. For example, “x” and “y” represent the “X” and “Y” location of the point within the image patch. The YImage, cbImage, and crImage, represent Y Cb Cr, which is one way of encoding RGB information. These features are merely for illustration purposes. Other features may be used in addition to, or instead of, the features listed. 
     The ith row in this matrix corresponds to the ith point in the image patch. The jth column in the matrix corresponds to the jth feature.  FIG. 7  illustrates a simpler example of the construction of a BoF matrix B of a patch with only five points in it. Each row in matrix B corresponds to point in the patch. The first, second and the third column of B corresponds to the x-location, y-location and the grayscale value of the point(s). 
     The BoF matrix can be visualized in the high dimensional feature space as well. For the simple example illustrated in  FIG. 7 , in a 3-dimensional space spanned by the x-value, y-value, and grayscale value, there is a “cloud” of 5 points. In general, the mapping may be illustrated from an image patch/region to a cloud of points in the feature space, such as depicted in  FIG. 8  in which the BoF matrix B for a patch is represented as a cloud of points in the high dimensional feature space. The statistics of the cloud in this high dimensional space may capture the characteristics of the image region. Moreover, the cloud may be described in a variety of ways. One way is by using a probability density function (PDF) of the cloud as the descriptor of the cloud. 
     Another type of abstraction is the histogram of intensity values. For example, an image patch B 1  may be described simply using histograms of intensity values. One may assume: N data points with scalar values f 1 , . . . f N , each f i  are real numbers; and m intervals/bins defined by points b 0 , b 1 , . . . b m , where b i &lt;b i+1  (assuming uniformly spaced bins, then b i+1 −b i =b for i=1, . . . , m−1). The histogram h=(h 1 , . . . , h m ) records the number pints f j  that fall into each bin. It may be calculated as follows: Set h=(0, . . . , 0), then, for i=1: N, find the j such that b j ≦f i &lt;b j +1 and set h j =h j +1. 
     There are several variants of the histogram of intensity values that may be used to describe image patches, including without limitation: co-occurrence histograms; histogram of gradients; auto-correlograms. 
     After abstraction of the different image regions, the abstracted image regions may be compared. In one embodiment, the abstracted image regions are at least partly combined (such as combining some or all of the abstracted image regions), and at least a part (or all) of the combined abstracted image regions is analyzed. In a more specific embodiment, the combined abstracted image region is compared with one or both of the underlying abstracted image regions. 
     As discussed above, one way to abstract an image region is by computing a BoF matrix (and the corresponding PDF cloud) for the entire image region. To that end, in order to compare two image regions, the associated BoF matrix (and the PDF cloud) for each of the image regions are computed. To compare the two BoF matrices and hence their associated PDF cloud, the two PDFs are merged to form one single PDF. The single PDF is then analyzed. In one embodiment, the single PDF is analyzed for at least one aspect, such as randomness. For example, the single PDF (which was merged from the two PDFs) is compared with one (or both) of the two PDFs to determine randomness of the single PDF (such as determining whether the single PDF is more random than one (or both) of the two PDFs or determining how much more random the single PDF is compared to the two individual PDFs). 
     Alternatively, the image region may be divided into multiple sub-regions (such as 4 sub-regions), and the BoF representation may be generated for each of the multiple sub-regions. When comparing two image regions, the analytical device may compare each of the multiple sub-regions individually, or the entire image regions&#39;s BoF representation, and select the “best” score according to one or more specific rules. Examples of specific rules include without limitation a minimum rule (in which the image region and/or particular image sub-region is selected that has associated with it the minimum score), or a maximum rule (in which the image region and/or particular image sub-region is selected that has associated with it the maximum score). 
     Another way to abstract an image region is with an intensity histogram. In order to compare two patches B 1  and B 2 , a normalized histogram H 1  is generated for B 1  and a normalized histogram H 2  is generated for B 2 . The histograms (H 1  and H 2 ) may be combined, such as by creating an average histogram H avg =0.5(H 1 +H 2 ). The combined histogram may be analyzed in order to determine the similarity or dissimilarity between patches B 1  and B 2  as follows: 
     
       
         
           
             
               Delta 
               ⁡ 
               
                 ( 
                 
                   
                     B 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   , 
                   
                     B 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 Entrophy 
                 ⁡ 
                 
                   ( 
                   H 
                   ) 
                 
               
               - 
               
                 0.5 
                 ⁡ 
                 
                   [ 
                   
                     
                       Entropy 
                       ⁡ 
                       
                         ( 
                         
                           H 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                         ) 
                       
                     
                     + 
                     
                       Entropy 
                       ⁡ 
                       
                         ( 
                         
                           H 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                         ) 
                       
                     
                   
                   ] 
                 
               
             
           
         
       
       
         
           
             
               where 
               ⁢ 
               
                   
               
               ⁢ 
               
                 Entrophy 
                 ⁡ 
                 
                   ( 
                   H 
                   ) 
                 
               
             
             = 
             
               - 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     h 
                     i 
                   
                   ⁢ 
                   
                     
                       
                         log 
                         e 
                       
                       ⁡ 
                       
                         ( 
                         
                           h 
                           i 
                         
                         ) 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
     in which [h 1 , h 2 , . . . , h n ] are the bin values of the normalized histogram H. 
     B 1  could be described simply using histograms of intensity values. The dissimilarity measure in Equation 2 (described below) may then be defined on the histograms in a similar manner. As an example, H 1  may be the normalized histogram of B 1  and H 2  may be the normalized histogram of B 2 . An average histogram H=0.5(H 1 +H 2 ) thus results. 
     Referring to  FIG. 9 , there is shown one graphical example of generating the merged abstractions of the image regions. More specifically,  FIG. 9  illustrates two observation image patches (Obs 1  and Obs 2  in  FIG. 9 ) that are compared by first computing their BoF description, which is represented by their PDF clouds (pdf 1  and pdf 2  in  FIG. 9 ). The abstractions of the observation image patches may be combined by merging of their PDF clouds (as shown in the combined pdf in  FIG. 9 ). As discussed above, at least one aspect (such as randomness) of the merged cloud may be analyzed. One example of the analysis may include using entropy functions, in which H( ) corresponds to the entropy function computed for a given PDF. The dissimilarity metric that compares the two image clouds is:
 
delta(obs1, obs2)= H (combined_pdf)−0.5[ H (pdf1)+ H (pdf2)]
 
     Here obs 1  has a probability distribution function of pdf 1 , and the mean and covariance corresponding to the distribution is (μ G1 , Σ G1 ). Similarly, obs 2  has a probability distribution function of pdf 2 , and the mean and covariance corresponding to the distribution is (μ G2 , Σ G2 ). The combined distribution&#39;s PDF&#39;s mean and covariance matrices are (μ G , Σ G ). 
     Using the assumption that the pdfs&#39; follow a Gaussian distribution, H(pdf 1 )=K+0.5 log(determinant(Σ G1 )), H(pdf 2 )=K+0.5 log(determinant(Σ G2 )), and H(combined_pdf)=K+0.5 log(determinant(Σ G )), where K is a constant. 
     Thus, delta(obs 1 , obs 2 )=K+0.5 log(determinant(Σ G ))−0.5[2K+0.5 log(determinant(Σ G1 )+0.5 log(determinant(Σ G2 ))]. Hence, 
     
       
         
           
             
               
                 
                   
                     delta 
                     ⁡ 
                     
                       ( 
                       
                         
                           obs 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                         , 
                         
                           obs 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     log 
                     ⁢ 
                     
                       
                         
                            
                           
                             Σ 
                             G 
                           
                            
                         
                         
                           
                             
                                
                               
                                 Σ 
                                 
                                   G 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   1 
                                 
                               
                                
                             
                             ⁢ 
                             
                                
                               
                                 Σ 
                                 
                                   G 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   2 
                                 
                               
                                
                             
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     In the above formula, Σ G  corresponds to the covariance matrix corresponding to the combined PDF, while Σ G1  and Σ G2  correspond to the covariance matrices associated with PDFs for obs 1  and obs 2 , respectively. 
     Equation 2 provides an example of how two multivariate Gaussian distributions may be compared. A cloud of points in a feature space (such as a PDF cloud illustrated in  FIG. 8 ) may be described by a multivariate Gaussian with mean μ 1  and variance S 1 . If the first cloud is compared to a second cloud with mean μ 2  and variance S 2 , one may first “fuse” the two clouds to create an intermediate description. If the intermediate description is random or chaotic, one may conclude that the two clouds of points that are being compared are quite dissimilar. On the other hand, if the intermediate description of the cloud is less chaotic, it would imply that the two initial clouds being compared are very similar. 
     The following illustrates how one may compute Σ G  from Σ G1  and Σ G2 , respectively. Since it may not be computationally practical to carry the BoF matrix and the corresponding cloud in the high dimensional space, especially for tracked objects, the BoF matrix and the corresponding PDF may be represented using the M×1 mean vector μand the M×M covariance matrix Σ instead. The (i,j)th element of the matrix Σ G  can be expressed in terms of the elements in μ G1 , Σ G1 , μ G2 , Σ G2  as
 
Σ G ( i,j )=0.5[Σ G1 ( i,j )+Σ G ( i,j )+μ G1 ( i )μ G1 ( j )+μ G2 ( i )μ G2 ( j )]−μ G ( i )μ G ( j ),
 
     where
 
μ G ( i )=0.5[μ G1 ( i )+μ G2 ( i )] and μ G ( j )=0.5[μ G1 ( j )+μ G2 ( j )], respectively   (3)
 
     Thus, Equation 3 illustrates how to combine the mean vector corresponding to the first cloud with the mean vector corresponding to the second cloud in order to compute the mean vector of the intermediate or the fused cloud. It is essentially the average of the two mean vectors. 
     Choosing to ignore the μ-component of the statistics, the formula to create the merged covariance matrix simplifies further to:
 
Σ G ( i,j )=0.5[Σ G1 ( i,j )+Σ G2 ( i,j )].   (4)
 
     Thus, Equation 4 states that the covariance matrix of the intermediate or the fused cloud is an average of the individual covariance matrices. Of note, an object BoF is essentially a collection of the BoF of the individual image patches (one per frame) that have been matched to the object. Hence, the mean vector and the covariance vector of the object is computed and updated using Equation 3 or Equation 4, where G 1  corresponds to the Gaussian describing the object, and G 2  corresponds to the image patch that matched the object. After the match is established, G corresponds to the Gaussian describing the object. 
     One computation issue is the matching process of the image patch with the object. During the matching process, several subregions of the image patch may be queried. This is depicted in  FIG. 10 , in which the various boxes represent the subregions. In particular, during the matching process, several subregions (shown in boxes) of an image patch are queried as a possible match to the object. The BoF description for each patch may be computed separately, and the patch that is closest to the object is chosen. 
     Moreover, computing the mean vector and the variance matrix for a patch with N points involves several multiplications and additions. For example, the computation of Σ G1 (i,j) for obs_ 1  involves O(N) multiplications and O(N) additions. During the matching process in tracking, the computation of this element in the covariance matrix is repeated for several query patches in the image. Of note is that there may be several redundant elements that are computed during the search process. To streamline the process, the covariance matrix elements are computed using the integral image approach. For M underlying features, M(M−1)/2 cross images are computed. For example, the x-y cross image corresponds to the multiplication of the x-Image and the y-Image of the points in the patch, where x-Image corresponds to the image where the (k, l)th location in the image corresponds to the x-value of this point in the image, and so on. The integral image of each of the cross images is also computed. The (k, l)th location of the integral image stores the sum of all the entries corresponding to the sub image with (0,0) and (k, l) being the top-left and the bottom-right points of the image. Although the computation of the M(M−1)/2 cross image and the integral image may appear to be a computationally expensive task, the SSE instruction sets may speed up the computation. Since integral image computation is a recursive operation, where the value of the (k, l)th location depends on the neighboring values of the image, it may not be able to compute them in parallel using a naive implementation. In order to perform the computation, interleaving of the M(M−1)/2 integral images is performed, and observing that the (k, l)th location value of two integral images can be computed independent of each other. This assists in parallelizing the summation operations of the integral image computation through an SSE implementation. 
     The comparison of the two abstractions may generate various results, such as a score or a rank. For example, the abstractions for an object and an image patch may be compared, and a score or rank may be generated based on the comparison. As discussed in more detail in  FIG. 11 , a score or a rank above or at a predetermined amount may result in a determination of a “match” between the object and the image patch. Alternatively, when there are multiple image patches, the particular image patch/object combination that results in the highest score for similarity (or the lowest score if dissimilarity is the indicator) is declared the “match”. 
     Further, as discussed in  FIG. 11 , after an image patch is matched to an object, the definition of the object may be updated based on the matched image patch. One manner of updating the definition of the object is by fusing the abstraction of the image patch which is matched to the object with the abstraction of the object. Another manner of updating the definition of the object is by using the abstraction of the image patch as one mode in a multimodal abstraction. In particular, even when the object and the image patch are declared as a match, the dissimilarity value may be above a certain threshold (such as 0.2 for example). In those instances, instead of fusing the abstraction of the image patch to the abstraction of the object to maintain one single statistical description, a “multimodal” distribution may be used, such as a multimodal Gaussian distribution for the underlying BoF model of the object. In this way, an abstraction of an object may have several underlying Gaussian distributions, with each such distribution having an underlying mean and covariance matrix associated with it. When comparing an object with an image patch, the image patch Gaussian (which represents the image patch abstraction) may be compared to each of the object patch Gaussian using Equation 2 and the minimum value may be selected as the match dissimilarity. If it is later determined that the object has indeed matched the image patch, the object&#39;s BoF description is updated by either merging the image patch&#39;s Gaussian with the matching Gaussian corresponding to the object, or appending it to the object&#39;s BoF Gaussian set. 
     Therefore, at least a part of the combined image may be analyzed and compared with at least a part of each (or both) of the underlying images. For example, the entropy may be computed for the combined image, and compared with each (or both) of the underlying images, such as by subtracting the entropy for both of the underlying images (e.g., subtracting the average of the entropy for both of the underlying images). The result of subtracting the average entropy for both of the underlying images from the entropy of the combined image may then be analyzed. For example, the result of subtracting the average entropy for both of the underlying images from the entropy of the combined image may be compared to a threshold (such as the 0.2 threshold discussed above). If the result is equal to or less than the threshold, it may be determined that the underlying images (such as the object and the image patch) are a match. Alternatively, if the result is greater than the threshold, it may be determined that the underlying images (such as the object and the image patch) are not a match. 
     Referring to  FIG. 11 , there is shown a flow diagram  1100  for matching an image patch to an object. At  1102 , foreground/background segmentation is performed in order to generate list of potential image patches in current frame. The foreground/background segmentation may generate multiple image patches for the current frame. The image patches may be of any size and shape, and are not limited to the rectangular shapes as shown in  FIG. 1 . 
     At  1104 , the first image patch is selected. An abstraction of the first image patch may be generated, and at  1106 , combined with the abstraction of the object. As discussed above, various types of abstractions for the image patch may be used, including BoF description and a histogram of intensity values. Further, the abstraction of the object may be a BoF description and a histogram of intensity values, and may be a single mode or multimodal, as discussed above. For example, the two images (sample image patch and the object) may be abstracted into statistical representations of individual clouds (C 1  and C 2 ). The statistical representations (C 1  and C 2 ) may then be combined to form a combined cloud (C). 
     At  1108 , the combination may be analyzed. The analysis of the combination may be a comparison of the combination with one, some, or all of the abstractions used to generate the combination. For example, the combination (based on the abstraction of the image patch with the abstraction of the object) may be analyzed against the abstraction of the image patch and analyzed against the abstraction of the object. The analysis may be used to determine at least one feature of the combination as compared to the underlying image patch and object, such as the extent by which the randomness of the combination increases when compared to the image patch and when compared to the object. As discussed above, randomness is an indicator of whether the combination is more or less similar to the underlying image patch. The analysis of the combination may generate a score, which may be used thereafter to rank the various combinations. 
     In one embodiment, the analysis in  1108  may use a single metric (such as the BoF metric or the histogram metric). For example, the BoF metric may be used to generate BoF clouds of the image patch and the object. The BoF clouds of the image patch and the object may be combined to generate a BoF combined cloud. Further, the BoF combined cloud may be compared with the BoF cloud of the image patch and the BoF cloud of the object to determine the entropy or randomness of the combined cloud minus the average entropy or randomness of the individual clouds. Similarly, the histogram metric may be used to abstract the image patch and the object, with the abstractions being combined to generate a combined abstraction. 
     Assuming that the clouds follow Gaussian statistics, the entropy of cloud C 1  is the following:
 
 C   1   =K+ 0.5 log(determinant(Σ G1 ))
 
     where K is a constant and is the covariance matrix of the Gaussian representing the statistics of the cloud. In this way, the entropy or randomness may simplify to Equation 2, discussed above. 
     Alternatively, the analysis in  1108  may use a combination of metrics (such as the BoF metric and the histogram metric). As merely one example, one or more threshold values may be used for the BoF metric, and one or more threshold values may be used for the histogram metric. In particular, t 1  and t 2  may be used for the BoF metric, with t 1  being less than t 2 . Moreover, t 3  may be used for the histogram metric. Example values of t 1 , t 2 , and t 3  are 0.7, 1.5, and 0.5, respectively. The example values are merely for illustration purposes. 
     In practice, the comparison of the combination with the image patch used to generate the combination results in an indication of the closeness of the combination image with the underlying image patch. For example, using the BoF metric to analyze the combination results in d_b, an indicator of closeness of the combination with the underlying image patch. Likewise, using the histogram metric to analyze the combination results in d_h, an indicator of closeness of the combination with the underlying image patch. 
     One example of application of the thresholds is as follows: 
     If the d_b&lt;t 1 , then the indication of closeness is set equal to d_b. 
     If the d_b&gt;t 1  and d_h&lt;t 3 , then the indication of closeness is set equal to d_h. 
     If d_h&gt;t 3 , then the indication of closeness is set equal to infinity (meaning that the combination and one of the image patches do not correlate or match at all. 
     At  1112 , it is determined whether there is another image patch to analyze. If so, the next image patch is selected at  1110 , and the loop repeats. If not, the analytical device determines which of the image patches matches the object based on the analyses at  1114 . The analytical device may make this determination by examining one, some, or all of the combinations. For example, the analytical device may score each of the combinations based on the analysis at  1108 , and may thus rank the combinations based on the assigned scores. The rank may indicate which of the combinations is most similar to the underlying abstraction of the corresponding image patch and/or object, and in turn indicate which of the image patches is most similar to the object. Thus, the ranking may indicate which of the image patches matches the object. 
     At  1116 , the description of the object may be updated based on the matched image patch. One example of updating is to replace the definition of object O 1  by the definition of the image patch to which the object was matched in the current frame. Another example of updating is to fuse the definition of object O 1  with the definition of the image patch to which the object was matched in the current frame. An example of fusing is illustrated in  FIG. 9 . Still another example of updated is to add the definition of the matched image patch to the definition of the object O 1 . As discussed above, the abstraction of the object O 1  may be multimodal. Adding the definition of the matched image patch to the definition of the O 1  may comprise adding a mode as defined by the matched image patch. 
     Referring to  FIG. 12 , there is shown a table illustrating the change in asset scores corresponding to the reference datasets. Using BoF based dissimilarity computation to drive the matching process, one may observe an improvement in the asset and tracking scores on some of the reference datasets. The BoF description may capture the semantics of an object in an image in detail, and this is reflected in the improved scores. In a similar manner, tracking score results, both for indoor and outdoor scenes, may improve. From the computational load viewpoint, overall execution time may increase; however, the increase in computational time using the BoF may be less than 5% of the time while using the histogram based matching approach. In order to further reduce BoF computation load, the BoF features need only be performed on the foreground patch (or blob) areas. 
     While the invention has been described with reference to various embodiments, it should be understood that many changes and modifications can be made without departing from the scope of the invention. It is therefore intended that the foregoing detailed description be regarded as illustrative rather than limiting, and that it be understood that it is the following claims, including all equivalents, that are intended to define the spirit and scope of this invention.