Abstract:
A computationally efficient approach to determining inner products between feature vectors is provided that eliminates or reduces the need for multiplication, and more specifically, provides an efficient and accurate basis selection for techniques such as Orthogonal Matching Pursuit.

Description:
BACKGROUND 
     This invention relates to an approach to efficient computation of inner products, and in particular relates to efficient inner product computation in image or video processing. 
     A number of image and video analysis approaches involve computation of feature vector representations for an entire image or video, or portions (e.g., spatial patches) of such representations. Approaches to determining similarity of vector representations include distance-based and direction-based approaches. An example of a distance-based approach uses a Euclidean distance (i.e., square root of the sum of squared differences of corresponding elements of the vectors), while an example of a direction-based approach uses an inner product metric (i.e., a sum of the products of corresponding elements of the vectors). Some approaches involve projection of a vector representation unto a basis vectors from a predetermined set. Such projections also involve inner product calculations. 
     Projection approaches include basis selection approaches in which the basis vectors to represent a particular feature vector are selected from a larger predetermined “dictionary” of basis vectors. One such approach is called “Orthogonal Matching Pursuit (OMP)” in which a series of sequential decisions to add basis vectors for the representation are made. These decisions involve computations of inner products between the as-yet unselected basis vectors from the dictionary and a residual vector formed from the component of the feature vector not yet represented in the span of the selected basis vectors from the dictionary. 
     One prior approach to computation of an inner product between two vectors u and ν uses a random projection technique. The Johnson-Lindenstrauss theorem is a basis for “Location Sensitive Hashing” (LSH) for a given a data vector ν, a bit vector h(ν)ε{0,1} p  is computed such that 
                 h   i     ⁡     (   v   )       =     {             1             r   i   T     ⁢   v     ≥   0             0       otherwise         ⁢     
     ⁢   i     ∈     1   ⁢           ⁢   …   ⁢           ⁢   p               
Here, r i &#39;s are random projection vectors, and p is the number of projections. Let └x┘ denote an operator such that └x┘=1 if x≧0 else └x┘=0. Let P be a projection matrix of random vectors P=[r 1  . . . r p ] T . We can write the bit-vector construction as h(ν)=└Pν┘.
 
     As a consequence of the Johnson-Lindenstrauss theorem, the dot-product between two data vectors, u and ν, can be approximated with the hamming distance between their bit vectors, ∥h(u)−h(ν)∥ 1   
     
       
         
           
             
               
                 u 
                 T 
               
               ⁢ 
               v 
             
             ≈ 
             
               
                 
                    
                   u 
                    
                 
                 2 
               
               ⁢ 
               
                 
                    
                   v 
                    
                 
                 2 
               
               ⁢ 
               
                 cos 
                 ⁡ 
                 
                   ( 
                   
                     π 
                     ⁢ 
                     
                       
                         
                            
                           
                             
                               h 
                               ⁡ 
                               
                                 ( 
                                 u 
                                 ) 
                               
                             
                             - 
                             
                               h 
                               ⁡ 
                               
                                 ( 
                                 v 
                                 ) 
                               
                             
                           
                            
                         
                         1 
                       
                       p 
                     
                   
                   ) 
                 
               
             
           
         
       
     
     Another prior approach provides a way of choosing P to be sparse, with non-zero entries that are ±1. An approach referred to as “Comparison Random Projection” (CRP) uses a construction of P as: 
               P   ij   CRP     =         q   m       ⁢     {           +   1           with   ⁢           ⁢   probability   ⁢           ⁢     1   /   2     ⁢   q             0           with   ⁢           ⁢   probability   ⁢           ⁢   1     -     1   /   q                 -   1           with   ⁢           ⁢   probability   ⁢           ⁢     1   /   2     ⁢   q                     
for example, where q=1 or 3. Because the projection Pν does not require multiplications, the overall computation is reduced.
 
     Another prior approach provides a way of choosing P as a product of a sparse random projection (SRP) matrix P SRP  with s non-zero elements per row drawn from normal distribution multiplied by a Hadamard matrix H and a random ±1 diagonal matrix D as:
 
 P   FJLT   =P   SRP   HD  
 
     Note that a sparse feature vector ν applied to the projection P FJLT ν can be computed as P FJLT =P SRP  (H Dν)=P SRP  {tilde over (ν)} where {tilde over (ν)}=HDν has the effect of making {tilde over (ν)} non-sparse even if ν is sparse. 
     There is a need for computationally efficient approaches to determining inner products between feature vectors, and more specifically, there is a need for efficient and accurate basis selection for techniques such as Orthogonal Matching Pursuit. 
     SUMMARY 
     In one aspect, in general, a method for machine-implemented image feature processing includes accepting a data representation of a plurality of m dimensional feature vectors ν representing a processing of an image or video signal. For each feature vector ν, a p dimensional binary vector h is formed from the data representation of the first feature vector ν using to first procedure. This first procedure includes transforming the feature vector ν to form a transformed first feature vector {tilde over (ν)}, including applying a machine implemented computation to compute elements of the transformed feature vector as an additive combination of elements of the feature vector. Each element of h is determined according to a sign of a selected additive combination of elements of {tilde over (ν)}. For each feature vector ν a data transformation of the feature vector ν is formed by computing at least one approximation of an inner product of ν with another vector u using a second procedure including comparing the bit vector h formed from ν with a bit vector formed from u. An image analysis process is then performed according to the plurality of transformed feature vectors. 
     Advantages can includes reducing or eliminating the need for multiplication operations, thereby increasing processing speed, reducing power requirements for processing, and/or reducing circuit complexity of processing hardware. Furthermore, the approach can improve the accuracy of the approximation of the inner product in situations in which one or both of the input vectors are sparse or have a small number of relatively larger magnitude elements. This advantage can be particularly significant when an input vector to an inner product is a residual vector in a sequential basis selection (e.g., Orthogonal Matching Pursuit) procedure. 
     Other features and advantages of the invention are apparent from the following description, and from the claims. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is a block diagram of a image feature processing system and  FIGS. 2A-2B  are flowcharts. 
     
    
    
     DESCRIPTION 
     The use of a computationally efficient inner product is described in the context of an Orthogonal Matching Pursuit (OMP) for determining representations of feature vectors for image or video signals received by a signal analysis system. It should be understood that this same approach to efficient computation of inner products is applicable in a variety of other image and video analysis approaches. 
     Generally, the OMP approach can be summarized as follows, recognizing that computational implementations do not necessarily implement mathematical operations in the order or manner as shown. A dictionary Φ=[a i ;i=1, . . . , n] with a i ε             m  such that m&lt;&lt;n and            m =Span(Φ). We also assume that the a i  are unit norm vectors. Very generally, the OMP process involves an iteration selecting vectors a k     1   , a k     2   , . . . from the dictionary for representing a feature vector ν such that at the p th  iteration, k p  is chosen such that
               k   p     =     arg   ⁢           ⁢       max   k     ⁢            a   k   T     ⁢     v     p   -   1                        
where ν p  is the residual (I−P S     p   )ν where P S     p    is a projection onto the span of S p ={a k     1   , . . . , a k     p   }, and ν 0 =ν. The coefficients of the selected dictionary entries are selected to optimize ∥ν−Φ T α∥ where α where has non-zero entries at the selected elements k 1 , k 2 , . . . k p .
 
     Note that determining the p th  value k p  can take n−p+1 inner products. Although certain approximations of this step are known, the computation of the inner products in the selection of the dictionary elements remains a key computation requirement in the OMP and similar approaches. 
     Referring to  FIG. 1  and the flowcharts in  FIGS. 2A-B  a feature processing system for image and video analysis includes an OMP module  110  that receives feature vectors x  104  and produces transformed feature vector α  106 . In various examples, the feature vectors ν are formed from images  102  (e.g., acquired using a digital camera of a physic scene) according a selection of conventional feature extraction approaches. For example, the feature vectors may be pixel values or portions of images or SIFT vectors. Generally, each input feature vector x is processed by the OMP module is represented as a vector α such that 
             x   ≈       ∑     i   =   1     p     ⁢       α     k   i       ⁢       a     k   i       .               
The coefficients α k  of the selected dictionary vectors a k  are determined using a procedure described below with further reference to  FIG. 1 . The transformed feature vectors are then applied to image analysis tasks, such as scene detection using conventional techniques. Optionally, these vectors are applied to processing using techniques described in a co-pending application titled “IMAGE ANALYSIS USING COEFFICIENT DISTRIBUTIONS WITH SELECTIVE BASIS FEATURE REPRESENTATION,” Ser. No. 13/668,886, filed on Nov. 5, 2012, which is incorporated by reference.
 
     An approach to computing an inner product u T ν between two vectors (e.g., between a dictionary vector and a feature vector or a residual of the feature vectors) uses a comparison random projection approach. First, transformed vectors ũ=HDu and {tilde over (ν)}=HDν are computed. Note that multiplication by the Hadamard matrix H (which has entries ±1), the a random ±1 diagonal matrix D, or their product does not involve multiplications. Rather, such a product involves only addition or subtraction of the elements of the vector being multiplied, with each entry occurring only once in the sum (i.e., either as a positive or negative term in the sum). Therefore, this matrix product does not require multiplications (i.e., does not include multiplications or sets of additions that effectively implement multiplications). Note that because H T  H=n I and D T D=I, u T ν=ũ T {tilde over (ν)}/n. Then we define
 
 h (ν)=└ P{tilde over (ν)}┘=└PHD ν┘.
 
and chose P as the sparse matrix P CRP  as defined above P CRP 
 
               P   ij   CRP     =         q   m       ⁢     {           +   1           with   ⁢           ⁢   probability   ⁢           ⁢     1   /   2     ⁢   q             0           with   ⁢           ⁢   probability   ⁢           ⁢   1     -     1   /   q                 -   1           with   ⁢           ⁢   probability   ⁢           ⁢     1   /   2     ⁢   q                     
with q=3 so that the inner product is approximated as
 
     
       
         
           
             
               
                 u 
                 T 
               
               ⁢ 
               v 
             
             ≈ 
             
               
                 
                    
                   u 
                    
                 
                 2 
               
               ⁢ 
               
                 
                    
                   v 
                    
                 
                 2 
               
               ⁢ 
               
                 cos 
                 ⁡ 
                 
                   ( 
                   
                     π 
                     ⁢ 
                     
                       
                         
                            
                           
                             
                               h 
                               ⁡ 
                               
                                 ( 
                                 u 
                                 ) 
                               
                             
                             - 
                             
                               h 
                               ⁡ 
                               
                                 ( 
                                 v 
                                 ) 
                               
                             
                           
                            
                         
                         1 
                       
                       p 
                     
                   
                   ) 
                 
               
             
           
         
       
     
     Note that because P CRP  has non-zero entries that are ±1, the matrix computation P{tilde over (ν)} does not require multiplications in its implementation. When the original feature vector ν is of dimension m, H and D are m×m matrices, and P CRP  is an m×p rectangular matrix, generally with p&gt;m and s non-zero entries per row, s/2 positive and s/1 negative. For example, for m=64 (e.g., pixel values in 8×8 patches), p=248 and s=2, 8, 16, 24 or 32. 
     Referring again to  FIG. 1 , processing of an input vector x involves computing inner products between x or residuals ν computed from x and dictionary vectors a i . In  FIG. 1 , a projected dictionary  122  represents precomputations of h(a i ) h(a i )=PHDa i  for all the dictionary elements in a dictionary  120 . Note that such precomputation is not required, and the computations of h(a i ) may be performed during operation. 
     Computation of a transformed feature vector α corresponding to the input vector x involves an iteration processing successive residuals ν p    142 , where ν 0 =h(x)=└PHDx┘ is computed by a random projection module  140 . h(ν p )=└PHDν p ┘ p th  the OMP procedure involves a search 
               k   p     =       arg   ⁢           ⁢       max   k     ⁢            a   k   T     ⁢     v     p   -   1                  =     arg   ⁢           ⁢       min   k     ⁢              h   ⁡     (     a   k     )       -     h   ⁡     (     v     p   -   1       )              1                 
where ∥h(a k )−h(ν p-1 )∥ 1  is computed by the comparison inner product module  150 , which also controls the search (arg max) over dictionary elements k. The comparison inner product module  150  augments the selected basis  152  with k p . The residual and basis computation module  160  then determined the best coefficient vector α for the selected dictionary items, and computes the next residual ν p , which to passes to the random projection module  140 , which updates the projected residual h(ν p )  142  for the next iteration.
 
     After all the iterations (e.g., determined by a stopping rule such as a total number of iterations, characteristic of the residual, etc.) the transformed feature vector α  162  is output from the OMP module  110  as one of the transformed feature vectors  106 . 
     Note that application of the transformation HD to the feature and dictionary vectors as described above is only one example of a broader range of transforms that preserve the inner product and that generally reduce the sparse nature of vector. Other choice include Wavelet transforms etc. Furthermore, the choice of sparse random projection P CRP  can be replaced with other 0 and ±1 matrices. 
     Experimental application of the techniques described above have been applied to scene analysis and a novel video classification. The video classification application involves applying the OMP algorithm on visual feature vectors, e.g. Scale Invariant Feature Transform (SIFT), Speeded Up Robust Transform (SURF). After OMP, distribution statistics of the resultant projection coefficients are computed, and then video classification is performed based on these statistics. The video classification application is especially computationally challenging, requiring the use of the OMP algorithm on a very large number of feature vectors. To give an example of the amount of computation, typical feature extraction techniques result in approximately a thousand vectors per video frame; therefore, even a short five minute video clip captured at 30 Hz frame rate will have 9 million feature vectors. Several current video research projects attempt analyzing data sets having hundreds of thousands of videos, effectively requiring processing billions of feature vectors. The algorithmic speedup described here becomes especially crucial in such computationally intensive applications. Further examples, applications, and comparisons to other techniques are found in “Efficient Orthogonal Matching Pursuit using sparse random projections for scene and video classification,”  Proc.  2011  IEEE International Conference on Computer Vision  ( ICCV ), 6-13 Nov. 2011, pp 2312-2319, which is incorporated herein by reference. 
     Implementations of the approach described above can include software, hardware, or a combination of hardware and software. For example, a hardware implementation may include special-purpose circuitry for computing the term ∥h(a k )−h(ν p-1 )∥ 1 . Software can include instructions for causing a data processing system to perform steps of the approaches. The data processing system can include a special-purpose processor, a general purpose processor, a signal processor, etc. The instructions can be machine-level instructions, or may be represented in a programming language, which may be compiled or interpreted. The software may be stored on a non-transitory medium (e.g., a volatile or non-volatile memory). In some examples, a system includes image acquisition modules, feature extraction modules, and/or feature extraction modules integrated together with the feature processing involving inner product implementations as described above. Some such examples may include integration within a single integrated circuit or multi-chip module. In some examples, a data representation in a hardware description language (e.g., Verilog) of circuitry for implementing an approach described above may be stored on a non-transitory medium and provided to impart functionality on a device specification system that is uses as part of a process of designing and manufacturing integrated circuits embodying the approach. 
     It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other embodiments are within the scope of the following claims.