Abstract:
Techniques for reducing the computational complexity of conventional similarity-based approaches for temporal event clustering of digital photograph collections include one or more approaches to select boundaries based on dynamic programming and the Bayes information criterion. Each method performs competitively with conventional approaches and offer significant computational savings.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to methods for clustering digital photograph collections.  
         [0003]     2. Description of the Related Art  
         [0004]     Digital cameras are coming into widespread use, and as a result, consumers are amassing increasingly large collections of digital photographs. There is a need for automatic tools to help manage, organize, and browse these collections. While a number of tools now exist for consumer photograph management, the vast majority feature light tables of thumbnails in chronological order. However, users typically group photographs chronologically into clusters based on “event.” 
         [0005]     Clustering photographs chronologically based on “event” is equivalent to partitioning the time interval over which the photographs were taken. Selecting boundaries at a single level from a hierarchical set of event boundaries can result in quadratic computational complexity in the number of photographs. As a consequence, processing times can be many seconds or even minutes to partition large photograph collection. This limits the suitability of these methods for interactive applications.  
       SUMMARY OF THE INVENTION  
       [0006]     This work is related to scale-space analysis and its application to the segmentation of text and video streams. In scale-space analysis, difference features are extracted from a data set and examined after smoothing with Gaussian kernel functions of varying standard deviation. The multiple smoothing filters reveal boundaries at the varying scales. The boundaries are detected and traced back from fine to coarse scale. Final segment boundaries are selected according to different criteria including the strength and extent of the maxima over the scales. This information can be used to construct a final flat (identifying only the points in the data where the context has changed) or hierarchical (detecting not only an event but also sub events within that event) segmentation.  
         [0007]     In this invention, event-based clustering of data files can be addressed using methods based on dynamic programming (DP) and Bayes information criterion (BIC). Data files comprise intrinsic information stored together with meta-data tag information, where the meta-tag relates to the parameters used to store the intrinsic information. For example, the data file of a digital photograph includes the intrinsic information relating to the pixels that make up the photograph and a meta-data tag which can include the type of file, the size of the file, a time stamp, and global positioning satellite positional data indicating the location where the photograph was taken. In the case of digital photographs, the DP and BIC methods perform the task significantly faster than for example similarity-based clustering criteria using similarity matrices. Although similarity analysis may be used for pre-processing to identify a set of potential event boundaries, any method can be used to pre-process.  
         [0008]     Given a set of candidate event boundaries, the methods only require the photographs&#39; timestamps. Alternatively meta-data tag or content-based features can be used as ordering criteria. Meta-data tags can include for example the time stamp or global positioning satellite positional data, while content-based features can include the low-level features such as color histograms or low-order discrete cosine transform coefficients. In addition, photographs can be ordered according to a non time-stamp based element (e.g., meta-data or content-based features), while a comparison can still be based on time-stamps or vice versa.  
         [0009]     In an embodiment of the invention where time stamps are extracted, ordering can be carried out based on increasing or decreasing time order. In an embodiment of the invention where an alphanumeric string can be extracted, ordering can be based on the alphabetic sequence of the first, second, . . . or last letter of the alphanumeric string. Alternatively, ordering can be based on the number of characters in the alphanumeric string and the increasing or decreasing size of the string or a combination of the length of the string and alphabetic order of a character in the string. In an embodiment of the invention where the size of the file can be extracted, ordering can be based on increasing or decreasing sizes of the files alone or in combination with some of the other ordering rules mentioned above. In an embodiment of the invention where more than one element can be extracted, ordering can be based on a combination of the above ordering rules.  
         [0010]     The present invention has been made in view of the above circumstances and provides methods for analyzing, browsing or retrieving digital photographs to determine cluster boundaries based on DP or BIC. In this manner, collections of digital photographs can be more rapidly and efficiently organized in a collection. The approach can be applied to segmentation of not only digital photographs but also other forms of media including video and audio streams. In such an embodiment, each frame in the stream of video or audio media can make up a data file in a collection of data files.  
         [0011]     In various exemplary embodiments of the systems and methods according to this invention, a desired set of data files can be organized by examining the timestamp, ordering the data files based on the time stamp, and then comparing the time-stamps for data files but using methods to reduce computational complexity involved in clustering the photograph collections. In one embodiment, BIC can be used to accelerate the computational step thereby reducing computational complexity involved in organizing a collection of photographs. In another exemplary embodiment a DP method can be used to accelerate the computational step and reduce the computational complexity involved in organizing a collection of photographs. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]     Preferred embodiments of the present invention will be described in detail based on the following figures, wherein:  
         [0013]      FIG. 1  illustrates a block diagram flow chart outlining a method for temporal clustering of digital photograph collections based on similarity analysis;  
         [0014]      FIG. 2  illustrates a block diagram flow chart outlining a method for temporal clustering of digital photograph collections based on similarity analysis using either DP or BIC in accordance with the present invention;  
         [0015]      FIG. 3  illustrates embedding photograph similarity measures based on the scalar time stamps corresponding to photograph ‘i’ and photograph ‘j’, t i  and t j  respectively are stored in a similarity matrix S K (i,j) at row ‘i’ and column ‘j’;  
         [0016]      FIG. 4  illustrates the regions of the similarity matrix S K (i,j) which contribute to within cluster similarity (shaded in horizontal lines) and the regions which contribute to dissimilarity between adjacent clusters (shaded in vertical lines);  
         [0017]      FIG. 5  illustrates a block diagram flow chart outlining a method for determining partitions and thereby the optimal number of clusters in digital photograph collections using DP in accordance with the present invention;  
         [0018]      FIG. 6  illustrates a block diagram flow chart outlining a method for determining the optimum boundaries in digital photograph collections using BIC in accordance with the present invention; and  
         [0019]      FIG. 7  illustrates a comparison between the precision, recall and F-score for different algorithms with similarity based confidence (C), BIC, and DP, using temporal similarity (TS) or joint temporal and content-based similarity (JS).  
         [0020]     The figures are more fully described in the Detailed Description of the Invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0021]     As outlined in  FIG. 1 , temporal event clustering techniques can be based on similarity analysis. This invention discloses accelerated methods for temporal event clustering of digital photographic collections.  FIG. 2  shows schematically embodiments for introducing DP or BIC methods to reduce computational complexity of temporal clustering.  
         [0022]     In one embodiment of the invention, similarity analysis of a collection of digital photographs can be used to determine initial boundaries. In similarity analysis a collection of digital photographs can be represented by a matrix of scale parameter K.  FIG. 3  illustrates a process of embedding a digital photograph similarity measure (see equation (1)) based on a time stamp in a similarity matrix S K (i,j).  
                 S   K     ⁡     (     i   ⁢     ,     ⁢   j     )       =     exp   ⁢           ⁢     (     -              t   i     -     t   j            K       )               equation   ⁢           ⁢     (   1   )               
 
 In S K (i,j), ‘i’ identifies rows of a matrix and ‘j’ identifies columns of a matrix corresponding to entries comparing the ‘i’th photograph scalar timestamp with the ‘j’th photograph scalar timestamp. In this manner a family of matrices can be constructed by varying a scale parameter K over a discrete set κ, where |κ|=M, the total number of scales. 
 
         [0023]     As indicated in  FIG. 1 , similarity matrices are used to compute a photograph indexed kernel correlation novelty score. Local maxima in a novelty score are detected as likely photograph boundaries for each K. As shown in  FIG. 1 , given a set of boundaries, B K  corresponding to a scale K, a similarity based confidence score (C S ) can be calculated according to equation (2).  
                       C   S     ⁢           ⁢     (     B   K     )       =       ⁢         ∑     l   =   1              B   K          -   1       ⁢       ∑     i   ,     j   =     b   l           b     l   +   1         ⁢         S   K     ⁢           ⁢     (     i   ⁢     ,     ⁢   j     )           (       b     l   +   1       -     b   l       )     2           -                     ⁢       ∑     l   =   1              B   K          -   2       ⁢       ∑     i   =     b   l         b     l   +   1         ⁢       ∑     j   =     b   l         b     l   +   2         ⁢         S   K     ⁢           ⁢     (     i   ⁢     ,     ⁢   j     )           (       b     l   +   1       -     b   l       )     ⁢     (       b     l   +   2       -     b     l   +   1         )                             equation   ⁢           ⁢     (   2   )               
 
         [0024]     The first term in equation (2) quantifies an average within-cluster similarity between photographs, while a second term quantifies average between-cluster similarity between photographs in adjacent clusters. By negating the second term in equation (2), the confidence measure combines each cluster&#39;s average similarity and the dissimilarity between adjacent clusters.  FIG. 4  illustrates this idea graphically. The within-cluster similarity terms are the means of the terms of horizontal lined regions along the main diagonal. The between-cluster terms are the means of the off-diagonal vertical lined regions. Finally, by determining maxima of the confidence score a list of optimized boundaries can be derived.  
         [0025]      FIG. 2  shows a schematic outlining a flowchart for embodiments of methods for organizing data according to this invention. It should be appreciated that, in various exemplary embodiments, an extracted timestamp can be used to organize data chronologically. Alternatively, if, for example, an extracted element can be a meta-data element where at least one extracted element of meta-data includes a file name or some other text string the data may be organized alphabetically using meta-data or organized according to some other predetermined rule.  
         [0026]     As shown in  FIG. 2  for one embodiment of the invention, operation of a method begins with extraction of time stamps from EXIF headers for each photograph in a collection of digital photographs. If EXIF information is not available, a modification time of a digital image file can be used instead. N photographs in a collection are then ordered in time so resulting timestamps, {t n : n=1, . . . , N}, satisfy t 1 ≦t 2 ≦ . . . ≦t N . Throughout, timestamps and rows and columns of similarity matrices are indexed by photograph in time order, not by absolute time. Thus, each photograph can be represented by its scalar timestamp.  
         [0027]     The computation of the score of equation (2) can incur quadratic computational cost in the number of photographs.  FIG. 2  details two alternative methods of reducing computational complexity of determining a list of boundaries for temporal event clustering. Introducing either DP or BIC reduces computational complexity of similarity analysis thereby more rapidly determining an optimized boundary list to organize a photograph collection.  
         [0028]     In one embodiment of the invention computational complexity can be reduced using DP. The total set of detected boundaries can be denoted by B={b 1 , . . . b NK } which can be the combined set of potential boundaries detected at all discrete scales K. B has cardinality β=|B|&lt;&lt;N. A cost of a cluster between photographs b i  and b j  can be defined to be an empirical variance of a corresponding timestamp according to equation (3).  
                 C   F     ⁢           ⁢     (       b   i     ,     b   j       )       =       1       b   j     -     b   i     -   1       ⁢       ∑     n   =     b   i           b   j     -   1       ⁢     (       (     t   n     )     -       1       b   j     -     b   i         ⁢       ∑     n   =     b   i           b   j     -   1       ⁢     (     t   n     )           )                 equation   ⁢           ⁢     (   3   )               
 
 As shown in  FIG. 5 , starting with this known set of boundaries b 1 , . . . b Nk  a DP algorithm successively builds optimal partitions with m boundaries based on optimal partitions with m-1 boundaries. First, optimal partitions are computed with two clusters according to equation (4),  
                   E   F     ⁢           ⁢     (     j   ⁢     ,     ⁢   2     )       =       min     2   ⁢           ≤           ⁢   i   ⁢           ≤           ⁢   j       ⁢     {         C   F     ⁡     (     1   ,     b   i       )       +       C     F   ⁢               ⁡     (       b   i     ,     b   j       )         }         ,           ⁢     i   ≤   j   ≤   β             equation   ⁢           ⁢     (   4   )               
 
 where E F (j,m) can be the optimal partition of photographs with indices  1 , . . . b j  with cardinality m. Next, this procedure can be repeated to compute E F (j,L) according to equation (5).  
                         E   F     ⁢           ⁢     (     j   ⁢     ,     ⁢   L     )       =       ⁢       min     L   ⁢           ≤           ⁢   i   ⁢           ≤           ⁢   j       ⁢     {         E   F     ⁡     (       i   ⁢     ,     ⁢   L     -   1     )       +       C   F     ⁡     (       b   i     ,     b   j       )         }         ,                   ⁢       L   ≤   j   ≤   β     ,     3   ≤   L   ≤   β                     equation   ⁢           ⁢     (   5   )               
 
 The result can be a set of optimal partitions with cardinality  3 , . . . , β. A trace back step identifies boundaries comprising each of the optimal partitions. As the number of clusters increases, the total cost of the partition decreases monotonically. A criteria for selecting the optimal number of clusters, L*, based on total partition cost can be described in equation (6).  
               L   *     =         arg   ⁢           ⁢   max       2   ⁢           ≤           ⁢   m   ⁢           ≤           ⁢     β   ⁢           -   1         ⁢           ⁢     {         E   F     ⁢           ⁢     (     β   ,   m     )           E   F     ⁢           ⁢     (     β   ,     m   +   1       )         }               equation   ⁢           ⁢     (   6   )               
 
 It is envisaged that one having skill in the art can utilize various other criteria to determine L*. 
 
         [0029]     In one embodiment of the invention, computational complexity can be reduced using BIC as shown in  FIG. 2 . A BIC is a method for model order selection, where model order can be the number of event clusters. In BIC analysis, it can be assumed that timestamps within an event are distributed normally around an event mean. As shown in  FIG. 6 , in one embodiment of the invention, a scalar parameter K can be determined. Next, a set of similarity matrices can be constructed for different values of K. Then a set of novelty scores can be determined via kernel correlation. From a novelty score a set of boundaries can be determined. The basic BIC process can test each boundary bεB to determine if an increase in model likelihood justifies the additional parameters used to describe the additional segment. This results in a simple test for each b, as described in expression (7).  
                       ⁢       L   ⁢           ⁢     (       b     l   -   1       ,     b   l       )       +                     ⁢       L   ⁢           ⁢         (     b   ,     b     l   +   1         )     ⁢             &gt;   &lt;     ⁢   L   ⁢           ⁢     (       b     l   -   1       ,     b     l   +   1         )       +                     ⁢       λ   2     ⁢   log   ⁢           ⁢     (       b     l   +   1       ,     b     l   -   1         )                     expression   ⁢           ⁢     (   7   )               
 
         [0030]     The left hand side of expression (7) is a log-likelihood term for a two-segment model. A two-segment model splits photographs between b l+1  and b l−1  into two clusters, separated by boundary b l . The right hand side of expression (7) represents a log-likelihood for a single segment model, and a penalty term for additional parameters in a two-segment model. A single segment model can be a single cluster of photographs b l−1 , . . . , b l+1 . In expression (7), λ can be the number of parameters required to represent a segment. If a likelihood gain associated with separate models for the two segments exceeds the penalty for additional parameters, b l  can be included in the final event partitioning. Since each segment can be described using a sample mean (μ l ), and variance (σ l ) of the photographs timestamp according to equation (8), then λ=2.  
               L   ⁢           ⁢     (       b   l     ,     b     l   +   1         )       =             b     l   +   1       -     b   l     -   1     2     ⁢   log   ⁢           ⁢   2   ⁢           ⁢     πσ   l       -     ∑         (       t   n     -     μ   l       )     2       2   ⁢           ⁢     σ   l   2                     equation   ⁢           ⁢     (   8   )               
 
 Equation (8) can be further simplified to equation (9).  
               L   ⁢           ⁢     (       b   l     ,     b     l   +   1         )       =           b     l   +   1       -     b   l     -   1     2     ⁢     (     1   +     log   ⁢           ⁢     (     2   ⁢           ⁢     πσ   l       )         )               equation   ⁢           ⁢     (   9   )               
 
         [0031]     The BIC for boundary selection can be applied in a coarse-to-fine framework (i.e. as K decreases). At each scale K, newly detected boundaries are tested using expression (7), and boundaries for which the left hand side of expression (7) is greater than the right hand side of expression (7) are added to selected boundaries as shown in  FIG. 6 .  
         [0032]     It is envisaged that one having skill in the art can utilize improved density estimates to further enhance effectiveness of BIC for temporal clustering or segmentation of digital photographs. For example, BIC can be used in conjunction with other probabilistic models that are more sophisticated or accurate including mixture models.  
         [0033]     Table 1 compares computational run time for processing multi-scale similarity analysis (Confidence) compared with DP and BIC methods, for several values of N. In addition, Table 1 gives run time required to construct a set of candidate event boundaries, B (Detection), which is included in Table 1.  
                                                           TABLE 1                           Run times (sec)            N   Detection   BIC   DP   Confidence                    500   0.017423   0.016808   0.016808   0.183231       1000   0.034846   0.036077   0.039077   0.563115       2000   0.076923   0.081731   0.128615   1.908038       4000   0.161077   0.179077   0.593769   8.718769       6030   0.271654   0.260231   1.459115   19.594962                  
 
         [0034]     Table 1 illustrates variation in document run times for different size photograph collections, where event clustering has been implemented in Java, and times here were produced using a personnel computer with a 2.66 GHz Pentium 4 processor. After doubling the number of photographs processed (N), time for the boundary detection increases linearly, while including “Confidence” incurs a quadratic cost. The times in Table 1 are averages over 25 runs. An imprecision in timing given the short duration of calculation is responsible for producing the results for N=500 in Table 1, where DP or BIC processing takes less time than “Detection” alone.  
         [0035]     The computational complexity of constructing a set of boundaries using multi-scale similarity analysis (Confidence) can be compared with DP and BIC methods. Generally, elements of a similarity matrix are zero far from the main diagonal, that is when |i-j| is large. Therefore to reduce storage and computation requirements, only a portion of a similarity matrix around the main diagonal is computed, The set of novelty scores computed using similarity matrices with varying specified values of K are then calculated. However, evaluation of “Confidence” potentially necessitates computation of the entire similarity matrix, since the extent of events can&#39;t be assumed in advance. In a worst case, this includes all N 2  terms of a similarity matrix. Because a temporal similarity measure decays exponentially as time difference increase, complexity can be reduced by using a mask, which zeros out elements of a matrix corresponding to photograph pairs taken far apart in time. Other heuristics can also be used to construct masks based on the number of photos taken between a pair of photos. Nonetheless, a worst-case complexity of 0(N 2 ) using “Confidence” is substantially greater than that of boundary detection.  
         [0036]     The methods based on DP and BIC both offer significantly reduced complexity of calculation. The DP-based peak selection can be of 0(β 2 ) where β&lt;N, where β is governed by the smallest scale in K. Table 1 suggests that DP can be roughly ten times faster than similarity-based peak selection for all values N tested. Computing costs of equation (3) accounts for two thirds of the total processing time in the DP-based method. The BIC-based method offers even more substantial computational savings, where 0(β) tests using expression (7) are performed. The computation of sample means and variances of 0(N. M), dominates total BIC method cost.  
         [0037]     Both DP and BIC methods perform competitively with the original similarity-based confidence score.  FIG. 7  shows the cumulative results of experimental testing using two photo collections manually clustered by the respective photographers and using measures given in equations (10), (11) and (12).  
             Precision   =       correctly   ⁢           ⁢   detected   ⁢           ⁢   boundaries       total   ⁢           ⁢   number   ⁢           ⁢   of   ⁢           ⁢   detected   ⁢           ⁢   boundaries               equation   ⁢           ⁢     (   10   )                 Recall   =       correctly   ⁢           ⁢   detected   ⁢           ⁢   boundaries             total   ⁢           ⁢   number   ⁢           ⁢   of               ground   ⁢           ⁢   truth   ⁢           ⁢   boundaries                     equation   ⁢           ⁢     (   11   )                 Fscore   =       2   ×   Precision   ×   Recall       Precision   +   Recall               equation   ⁢           ⁢     (   12   )               
 
         [0038]     Event-clustering performance for temporal (TS) and joint temporal and content-based similarity (JS) are reported with each of the three boundary selection techniques (Similarity based confidence, DP and BIC). As such the JS uses both a meta-data tag such as time together with a content-based parameter such as file size to generate similarity analysis based boundaries. For the JS results reported here, we used low order discrete cosine transform (DCT) coefficients as content-based features. The similarity-based confidence results are denoted by TS-C and JS-C, DP-based results by TS-DP and JS-DP, and BIC-based results by TS-BIC and JS-BIC. Although, DP and BIC accelerated versions of temporal algorithms perform at a high level, temporal-similarity-based confidence (TS-C) achieves a maximal cumulative F-Score of all the methods examined, as shown in Table 2. Of the accelerated methods, DP appears to be superior to BIC-based peak selection, particularly with respect to Precision. The three boundary selection techniques thus demonstrate a tradeoff between computational complexity and performance.  
         [0039]     Table 2 illustrates a boundary selection performance with similarity-based confidence (C), BIC, and DP, using temporal similarity (TS) and joint temporal and content-based similarity (JS).  
                                   TABLE 2                                   Algorithm   Precision   Recall   F-Score                           TS-C   0.8857   0.8304   0.8571           TS-DP   0.8448   0.7828   0.8126           TS-BIC   0.7374   0.8304   0.7811           JS-C   0.8829   0.8182   0.8493           JS-DP   0.8523   0.7768   0.8128           JS BIC   0.8709   0.8179   0.8436