Dictionary generation method for video and image compression

Abstract

This invention relates to the creation of dictionary functions for the encoding of video signals using matching pursuit compression techniques. After an initial set of reference dictionary images is chosen, training video sequences are selected, and motion residuals are calculated. High energy portions of the residual images are extracted and stored when they match selection criteria with the reference dictionary. An energy threshold is used to limit the number of video signal “atoms” encoded for each frame, thus avoiding the encoding of noise. A new dictionary is then synthesized from the stored portions of the image residuals and the original reference dictionary. The process can then be repeated using the synthesized dictionary as the new reference dictionary. This achieves low bit rate signals with a higher signal-to-noise ratio than have been previously achieved.

1. A method for creating a dictionary for video compression, comprising:
 (a)  designating an initial reference dictionary of functions ,  stored in a memory; 
 (b)  designating a set of video sequences to be used as training sequences, ; 
 (c)  calculating the  a motion residual image for at least one of the frames of a video sequence from the set of video sequences, ; 
 (d)  determining an energy threshold for evaluating the residual image, ; 
 (e)  evaluating the residual image for portions above the energy threshold; 
 (f)  comparing a first high energy portion of the residual image to at least one function in the reference dictionary, ; 
 (g)  extracting the first high energy portion of the residual image, ; 
 (i)  storing the extracted high energy portion of the residual image ,  in the memory; and  
 (j)  synthesizing, using a processing device, the dictionary from the stored high energy portion of the residual image, in which the step of synthesizing comprises  by dividing the extracted high energy portions into at least two subsets based on an inner product calculation, and calculating an updated dictionary pattern from the elements in the two subsets.  
 
     
     
       2. The method of  claim 1 , in which the step of  wherein the calculating further comprises:
           x   ^       j   ,     n   +   1         =           ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢     ω   i         -           ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢     ω   i         .           
 
     
     
       3. The method of  claim 1 , further comprisingthe steps of :
 (k)  revising the residual image, ; and  
 (l)  repeating steps (f)-(i)  the comparing, extracting, and storing for at least a second high energy portion of the residual image, after said  the first high energy portion has been extracted.  
 
     
     
       4. A dictionary for use in video compression, said  the dictionary having been generated by:
 (a)  designating an initial reference dictionary of functions, ; 
 (b)  designating a set of video sequences to be used as training sequences, ; 
 (c)  calculating the motion residual image for at least one of the frames of a video sequence from the set of video sequences, ; 
 (d)  determining an energy threshold for evaluating the residual image, ; 
 (e)  evaluating the residual image for portions above the energy threshold; 
 (f)  comparing a first high energy portion of the residual image to at least one function in the reference dictionary, ; 
 (g)  extracting the first high energy portion of the residual image, ; 
 (i)  storing the extracted high energy portion of the residual image, ; 
 (j) synthesissynthesizing from the stored high energy portion of the residual image, in whichwherein the step of synthesissynthesizing comprises dividing the extracted high energy portions into at least two subsets based on an inner product calculation, and calculating an updated dictionary pattern from the elements in the two subsets.  
 
     
     
       5. The method  dictionary of  claim 4 , in which the step of  wherein the calculating further comprises:
           x   ^       j   ,     n   +   1         =           ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢     ω   i         -           ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢     ω   i         .           
 
     
     
       6. The method  dictionary of  claim 4 , wherein the generating further comprising the steps of  comprises:
 (k)  revising the residual image, ; and  
 (l)  repeating steps (f)-(i)  the comparing, extracting, and storing for at least a second high energy portion of the residual image, after said  the first high energy portion has been extracted.  
 
     
     
       7. A video encoding system containing  comprising a dictionary generated by:
 (a)  designating an initial reference dictionary of functions, ; 
 (b)  designating a set of video sequences to be used as training sequences, ; 
 (c)  calculating the motion residual image for at least one of the frames of a video sequence from the set of video sequences, ; 
 (d)  determining an energy threshold for evaluating the residual image, ; 
 (e)  evaluating the residual image for portions above the energy threshold; 
 (f)  comparing a first high energy portion of the residual image to at least one function in the reference dictionary, ; 
 (g)  extracting the first high energy portion of the residual image, ; 
 (i)  storing the extracted high energy portion of the residual image, ; and 
 (j) synthesissynthesizing from the stored high energy portion of the residual image, in which the step of synthesiswherein the synthesizing comprises dividing the extracted high energy portions into at least two subsets based on an inner product calculation, and calculating an updated dictionary pattern from the elements in the two subsets.  
 
     
     
       8. The method  video encoding system of  claim 7 , in which the step of  wherein the calculating comprises:
           x   ^       j   ,     n   +   1         =           ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢     ω   i         -           ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢     ω   i         .           
 
     
     
       9. The method  video encoding system of  claim 7 , further comprising the steps of  wherein the dictionary is further generated by:
 (k)  revising the residual image, ; and  
 (l)  repeating steps (f)-(i)  the comparing, extracting, and storing for at least a second high energy portion of the residual image, after said  the first high energy portion has been extracted.  
 
     
     
       10. A machine readable medium , upon which are stored  having instructions to generate a dictionary for video compression according to the method comprising steps of  stored thereon that are executed by a processing device causing the processing device to perform operations comprising:
 (a)  designating an initial reference dictionary of functions, ; 
 (b)  designating a set of video sequences to be used as training sequences, ; 
 (c)  calculating the motion residual image for at least one of the frames of a video sequence from the set of video sequences, ; 
 (d)  determining an energy threshold for evaluating the residual image, ; 
 (e)  evaluating the residual image for portions above the energy threshold; 
 (f)  comparing a first high energy portion of the residual image to at least one function in the reference dictionary, ; 
 (g)  extracting the first high energy portion of the residual image, ; 
 (i)  storing the extracted high energy portion of the residual image, ; and 
 (j) synthesissynthesizing from the stored high energy portion of the residual image, in which the step of synthesiswherein the synthesizing comprises dividing the extracted high energy portions into at least two subsets based on an inner product calculation, and calculating an updated dictionary pattern from the elements in the two subsets.  
 
     
     
       11. The method  machine readable medium of  claim 10 , in which the step of  wherein the calculating comprises:
           x   ^       j   ,     n   +   1         =           ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   +   )           ⁢     ω   i         -           ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢       ω   i     ⁢     x   i             ∑       x   i     ∈     S     j   ,   n       (   -   )           ⁢     ω   i         .           
 
     
     
       12. The method  machine readable medium of  claim 10 , further comprising the steps of :
 (k)  revising the residual image, ; and  
 (l)  repeating steps (f)-(i)  the comparing, extracting, and storing for at least a second high energy portion of the residual image, after said  the first high energy portion has been extracted.  
 
     
     
       13. A video system comprising:
   a memory;        a processor configured to:      calculate a residual image from at least one frame in a video sequence;        identify a high energy portion of the residual image above a predetermined threshold;        match regions of varying dimension centered about the high energy portion of the residual image with elements in an initial dictionary;        extract the matched region from the residual image;        store the matched region in the memory as a pattern;        repeat the calculate, identify, match, extract, and store for other residual images in other frames of the video sequence until all high energy portions in the other residual images are matched;        synthesize an updated dictionary according to the initial dictionary and the stored patterns;        calculate a set of inner products between the stored patterns and elements in the initial dictionary;        divide the stored patterns in at least two sets of patterns and the elements in the initial dictionary into at least two sets of elements responsive to a sign of a corresponding one of the inner products; and        calculate code vectors for the updated dictionary according to the at least two sets of patterns and the at least two sets of elements.       
     
     
       14. The video system of  claim 13  wherein the processor is further configured to:
   replace the initial dictionary with the updated dictionary.   
 
     
     
       15. The video system of  claim 13  wherein the processor is further configured to:
   update code vectors of the updated dictionary; and    
   replace the initial dictionary with the updated dictionary after the update.   
 
     
     
       16. The video system of  claim 13  wherein the processor is further configured to:
   calculate the code vectors for the updated dictionary according to an energy of at least one of the stored patterns.   
 
     
     
       17. A video system comprising:
   a storage means;        a processing means configured to:      calculate a residual image from at least one frame in a video sequence;        identify a high energy portion of the residual image above a predetermined threshold;        match regions of varying dimension centered about the high energy portion of the residual image with elements in an initial dictionary;        extract the matched region from the residual image;        store the matched region in the storage means as a pattern;        repeat the calculating, identifying, matching, extracting, and storing for other residual images in other frames of the video sequence until all high energy portions in the other residual images are matched;        synthesize an updated dictionary responsive to calculating at least one metric between the stored patterns and elements in the initial dictionary;        calculate a set of inner products between the stored patterns and elements in the initial dictionary;        divide the stored patterns in at least two sets of patterns and the elements in the initial dictionary into at least two sets of elements responsive to a sign of corresponding one of the inner products; and        calculate code vectors for the updated dictionary according to the at least two sets of patterns and the at least two sets of elements.       
     
     
       18. The video system of  claim 17  wherein the processing means is further configured to:
   replace the initial dictionary with the updated dictionary.   
 
     
     
       19. The video system of  claim 17  wherein the processing means is further configured to:
   update code vectors of the updated dictionary; and    
   replace the initial dictionary with the updated dictionary after the updating.   
 
     
     
       20. The video system of  claim 17  wherein the processing means is further configured to:
   calculate the code vectors for the updated dictionary according to an energy of at least one of the stored patterns.