Patent Publication Number: US-8526760-B2

Title: Multi-scale representation of an out of focus image

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is the national phase of International (PCT) Patent Application Serial No. PCT/IL2009/000055, filed on Jan. 14, 2009, published under PCT Article 21(2) in English, which claims priority to and the benefit of U.S. Provisional Patent Application No. 61/021,705, filed on Jan. 17, 2008, the disclosure of each of which is incorporated herein by reference in its entirety. 
    
    
     FIELD OF THE DISCLOSED TECHNIQUE 
     The disclosed technique relates to multi-scale representation of a signal, in general, and to methods and systems for generating a multi-scale representation of an out-of-focus image, in particular. 
     BACKGROUND OF THE DISCLOSED TECHNIQUE 
     Multi-scale representation of an input image is employed in many visual processing applications such as feature detection (e.g. edge, blob, junction or ridge), feature classification, object recognition, object classification, image classification, shape analysis, and the like. A plurality of images, each of the images is at a different scale, are generated by smoothing the input image with ascending Gaussian kernels. 
     Optical blurring of an input image, resulting from the input image being out-of-focus, is modeled as a convolution of an input focused image with a Gaussian kernel of certain variance value. The value of the variance of the convolving Gaussian kernel corresponds to the blur level of the input image. Image convolution with a Gaussian kernel is described by equation (1):
 
 f*g (σ 3 )=( f*g (σ 1 ))* g (σ 2 ); σ 3 =√{square root over ((σ 1   2 +σ 2   2 ))}  (1)
     f—A focused image   g—A Gaussian kernel of certain variance   *—A convolution operator.
 
When the input image is blurred (i.e., out-of-focus input image), generating a multi-scale representation of the input image, might result in a removal of important details from the image (i.e., over smoothing the input image). One way of overcoming the over-smoothing problem of a blurred input image, is to reconstruct a focused image from the blurred image by estimating the Gaussian kernel corresponding to the blur level of the image, de-convolving the input image with the estimated Gaussian kernel, and generating a multi-scale representation of the de-convolved image.
   

     Reference is now made to  FIG. 1 , which is a schematic illustration of a method for generating a multi-scale representation of a blurred input image, operative as known in the art. In procedure  100 , a Gaussian kernel, corresponding to the blur level of the input image, is estimated. The Gaussian kernel estimation is achieved by any of the blur level estimation techniques known in the art. In procedure  102 , the blurred input image is de-convolved in order to reconstruct a focused image. The blurred image is de-convolved according to the Gaussian kernel, corresponding to the blur level of the image, estimated in procedure  100 . In procedure  104 , a multi-scale representation of the de-convolved image is generated by convolving the de-convolved image with a plurality of Gaussian kernels of ascending values of variance. In procedure  106 , a visual processing is performed on the multi-scale representation of the input image. 
     Reference is now made to “Scale space theory in computer vision” by Tony Lindeberg, a book published by Springer (1994). This publication is directed at a formal framework, scale-space representation, for handling the notion of scale in image data. The book gives an introduction to the general foundations of the scale space theory and shows how it applies to essential problems in computer vision such as computation of image features. 
     Reference is now made to an article entitled “Estimating Image Blur in The Wavelet Domain”, by Filip Rooms et al. This reference is directed to a method for estimating the blur level of an input image, according to information contained in the input image. A blurred image is modeled as the corresponding focused image convolved with a Point Spread Function (PSF). The method includes the procedures of: calculating the Lipschitz exponent; generating a histogram; and estimating the blur of the image according to the center of gravity of the histogram and according to the maximum of the histogram. The Lipschitz exponent is calculated in all points, where there is a change in intensity in either the horizontal or the vertical direction. The histogram of the Lipschitz exponents, of the blurred image, is a single peak histogram with a certain distribution around that peak. The blur level of the image is estimated according to the center of gravity of the distribution around the peak and according to the maximum of the peak. 
     Reference is now made to an article entitled “Pyramid Method in Image Processing” written by E. H. Adelson et al. This reference is directed to a method for constructing an image pyramid of different resolutions. The image pyramid is employed for a variety of visual processing applications such as pattern recognition. The image pyramid consists of a sequence of copies of an original image in which both sample density and resolution are decreased. The method includes the procedures of convolving the original image with a set of Gaussian-like weighing functions, subtracting each Gaussian pyramid level from the next lower level in the pyramid, and interpolating sample values between those in a given level before that level is subtracted from the next lower level. 
     A zero level of the pyramid is the original image. The convolution procedure acts as a low-pass filter with the band limit reduced by one octave, with each level, correspondingly. The procedures of subtracting and interpolating act as a band-pass filter. The procedure of interpolating is necessary since the subtraction is between levels of different sample densities. 
     SUMMARY OF THE PRESENT DISCLOSED TECHNIQUE 
     It is an object of the disclosed technique to provide a novel method and system for generating a multi-scale representation of an input out-of-focus image, which overcomes the disadvantages of the prior art. 
     In accordance with the disclosed technique, there is thus provided a method for generating a multi-scale representation of an input image. The method comprising the procedures of: estimating a scale factor corresponding to the input image; determining a set of Gaussian difference kernels; and generating a multi-scale representation of the input image. 
     The procedure of determining the set of Gaussian difference kernels is performed according to the estimated scale factor, and according to a predetermined set of Gaussian kernels. The procedure of generating a multi-scale representation is performed by applying each of the set of Gaussian difference kernels on the input image. 
     In accordance with another aspect of the disclosed technique, there is thus provided a system for generating a multi-scale representation of an input image, the system comprising: a scale space level estimator; and a multi-scale representation generator. The scale space level estimator estimates a scale factor corresponding to the input image. The multi-scale representation generator is coupled with the scale space level estimator. 
     The multi-scale representation generator receives the estimated scale factor, and determines a set of Gaussian difference kernels according to the estimated scale factor and according to a predetermined set of Gaussian kernels. The multi-scale representation generator further generates a multi-scale representation of the input image by applying each of the set of Gaussian difference kernels to the input image. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The disclosed technique will be understood and appreciated more fully from the following detailed description taken in conjunction with the drawings in which: 
         FIG. 1 , is a schematic illustration of a method for generating a multi-scale representation of a blurred input image, operative as known in the art; 
         FIG. 2 , is a schematic illustration of a scale space representation of an input image, constructed in accordance with an embodiment of the disclosed technique; 
         FIG. 3 , is a schematic illustration of a system for generating a multi-scale representation of a blurred input image, generally referenced  160 , constructed and operative in accordance with another embodiment of the disclosed technique; 
         FIG. 4 , is a schematic illustration of a multi-scale representation generating method, operative in accordance with a further embodiment of the disclosed technique; 
         FIG. 5 , is a schematic illustration of a method for generating a multi-scale representation (procedure  196  of  FIG. 4 ), operative in accordance with another embodiment of the disclosed technique; 
         FIG. 6A , is a schematic illustration of a multi-scale representation of an input focused image, generally referenced  250 , constructed in accordance with a further embodiment of the disclosed technique; and 
         FIG. 6B , is a schematic illustration of a multi-scale representation of an input blurred image, generally referenced  264 , constructed in accordance with another embodiment of the disclosed technique. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     The disclosed technique overcomes the disadvantages of the prior art by generating a multi-scale representation of a hypothetic focused image that relates to the blurred input image, without reconstruction of the focused image. The multi-scale representation starts at a scale level, which is lower than that of the blurred input image. 
     According to one embodiment of the disclosed technique, the multi-scale representation of the hypothetic focused image is produced by the procedures of estimating the blur level of a blurred input image (i.e., estimating the value of the variance of the Gaussian kernel corresponding to the blur level of the image—the scale factor), generating a set of Gaussian difference kernels from a set of pre-determined Gaussian kernels, and convolving the input image with the set of Gaussian difference kernels. 
     The value of variance of each of the set of Gaussian difference kernels is determined from formula (2):
 
σ diff =√{square root over (σ required   2 −σ blur   2 )}  (2)
     σ diff —is the value of variance of a specific Gaussian difference kernel.   σ required —is the value of variance of a predetermined difference Gaussian, corresponding to the specific Gaussian difference kernel.   σ blur —is the estimated value of variance of the blurred input image (i.e., the blur level).
 
Formula (2) is derived from formula (1). It is noted, that when the value of variance of the estimated Gaussian kernel is higher than that of a certain Gaussian kernel, that certain Gaussian kernel is omitted from the set of Gaussian difference kernels.
   

     The term “Multi-scale representation” herein below refers to a representation of an image by a set of images, each of the images relating to a different scale. Each of the images in the multi-scale representation is generated by convolving the original image with a respective Gaussian kernel. The value of variance of a Gaussian kernel, employed for generating an image of the multi-scale representation, is referred to as a scale factor. The scale factors of the multi-scale representation are of ascending order. By convolving the input image with a Gaussian kernel, image structures of spatial size, which corresponds to the scale factor, are removed from that image (i.e., image structures are smoothed from the image by convolution). The term “Scale space level” herein below refers to the position of an image within a multi-scale representation (i.e., a scale space level corresponds to the value of the variance of a Gaussian kernel—scale factor). 
     Reference is now made to  FIG. 2 , which is a schematic illustration of a scale space representation of an input image, constructed in accordance with an embodiment of the disclosed technique.  FIG. 2  includes an input image  130 , a first image  132 , a second image  134 , a third image  136 , a fourth image  138 , and a fifth image  140 . First image  132  is generated by applying a first Gaussian (not shown) having a first scale factor (not shown) to input image  130 . Second image  134  is generated by applying a second Gaussian (not shown) having a second scale factor (not shown) to input image  130 . It is noted, that the second scale factor is larger than the first scale factor. 
     Third image  136  is generated by applying a third Gaussian (not shown) having a third scale factor (not shown) to input image  130 . It is noted, that the third scale factor is larger than the second scale factor. Fourth image  138  is generated by applying a fourth Gaussian (not shown) having a fourth scale factor (not shown) to input image  130 . It is noted, that the fourth scale factor is larger than the third scale factor. Fifth image  140  is generated by applying a fifth Gaussian (not shown) having a fifth scale factor (not shown) to input image  130 . It is noted, that the fifth scale factor is larger than the fourth scale factor. 
     Reference is now made to  FIG. 3 , which is a schematic illustration of a system for generating a multi-scale representation of a blurred input image, generally referenced  160 , constructed and operative in accordance with another embodiment of the disclosed technique. System  160  includes an image source  162 , a scale space level estimator  164 , a multi-scale representation generator  166 , and a visual processor  168 . Image source  162  is coupled with scale space level estimator  164 . Space level estimator  164  is coupled with multi-scale representation generator  166 . Multi-scale representation generator  166  is coupled with application processor  168 . It is noted that, either any pair of, or all of scale space level estimator  164 , multi-scale representation generator  166 , and visual processor  168  can be integrated together on a single processor. 
     Image source  162  provides an input image (not shown) to scale space level estimator  164 . Image source  162  can be an image capture device, a storage unit storing the input image, a communication interface receiving the input image from an external source (e.g., a network), and the like. Scale space level estimator  164  estimates the scale factor corresponding to the input image (i.e., the scale factor of the Gaussian kernel employed for modeling the input image). The scale factor estimation can be achieved by any of the methods known in the art. Scale space level estimator  164  sends the input image and the estimated scale factor of the input image to multi-scale representation generator  166 . 
     Multi-scale representation generator  166  determines the scale space level of the input image, according to the estimated scale factor thereof. Multi-scale representation generator  166  predetermines a set of Gaussian kernels, each of the Gaussian kernels having scale factor higher than that of the previous Gaussian kernel in the set. 
     Multi-scale representation generator  166  substitutes each of the values of variance of the pre-determined Gaussian kernels with σ required  of formula (2):
 
σ diff =√{square root over (σ required   2 −σ blur   2 )})
 
for generating each of a set of Gaussian difference kernels, respectively. Multi-scale representation generator  166  omits from the set of Gaussian difference kernels every Gaussian kernel having negative scale factor. A negative scale factor is received for each of the set of predetermined Gaussian kernels having scale factor lower than that of the estimated scale factor corresponding to the input image.
 
     Multi-scale representation generator  166  applies each of the Gaussian difference kernels to the input image, for generating a scaled image of the input image. The set of the generated scaled images is referred to as a multi-scale representation of the input image. Multi-scale representation generator sends the multi-scale representation of the input image to visual processor  168 . Visual processor  168  performs a visual processing, such as feature detection, feature classification, object recognition, object classification, image classification, shape analysis, and the like, on the multi-scale representation of the input image. 
     Reference is now made to  FIG. 4 , which is a schematic illustration of a multi-scale representation generating method, operative in accordance with a further embodiment of the disclosed technique. In procedure  190 , an input image is received. With reference to  FIG. 3 , communication interface  162  receives an input image. In procedure  192 , the scale factor corresponding to the input image is estimated (i.e., the blur level of the input image is estimated). With reference to  FIG. 3 , scale space level estimator  164  estimates the scale factor corresponding to the input image. 
     In procedure  194 , a set of Gaussian difference kernels are determined according to the estimated scale factor and according to a predetermined set of Gaussian kernels. The set of Gaussian difference kernels are determined by formula (2), according to the estimated scale factor corresponding to the input image, and according to each of the scale factors of the predetermined set of Gaussian kernels. The predetermined set of Gaussian kernels is predetermined such that, the scale factors of the Gaussian kernels are of ascending order. With reference to  FIG. 3 , multi-scale representation generator  166  determines a set of Gaussian difference kernels according to the estimated scale factor and according to a predetermined set of Gaussian kernels. 
     In procedure  196 , a multi-scale representation of the input image is generated by applying each of the set of Gaussian difference kernels to the input image. With reference to  FIG. 3 , multi-scale representation generator  166  applies each of the set of Gaussian difference kernels to the input image, for generating a multi-scale representation of the input image. Procedure  194  is further detailed in  FIG. 5 . In procedure  198 , a visual processing is performed on the multi-scale representation of the input image. With reference to  FIG. 3 , visual processor  168  performs a visual processing (e.g., feature detection, feature classification, object recognition, object classification, image classification, and shape analysis) on the multi-scale representation of the input image. 
     Reference is now made to  FIG. 5 , which is a schematic illustration of a method for generating a multi-scale representation (procedure  196  of  FIG. 4 ), operative in accordance with another embodiment of the disclosed technique. In procedure  220 , a first image of a set of images of the multi-scale representation is generated by applying a Gaussian kernel having scale factor of √{square root over (σ M   2 −σ B   2 )} (i.e., scale factor), to the input image. σ B  Is the scale factor of the Gaussian kernel corresponding to the input image (i.e., the Gaussian kernel corresponding to the blur level of the input image). σ M  Is the scale factor of the first Gaussian kernel of a set of predetermined Gaussian kernels, which value is greater than σ B . σ B  is estimated by scale space level estimator  164  of  FIG. 3 . With reference to  FIG. 3 , multi-scale representation generator  166  generates the first image of the multi-scale representation of the input image by applying a first Gaussian difference kernel to the input image. 
     In procedure  222 , a second image of the multi-scale representation of the input image is generated by applying a Gaussian kernel having scale factor of √{square root over (σ M+1   2 −σ B   2 )} to the input image. With reference to  FIG. 3 , multi-scale representation generator  166  generates the second image of the multi-scale representation of the input image by applying a second Gaussian difference kernel to the input image. 
     It is noted that, each of the images of the multi-scale representation of the input image are created by applying each of the Gaussian difference kernels having scale factor greater than σ B , to the input image, starting at √{square root over (σ M   2 −σ B   2 )} and finishing at √{square root over (σ N   2 −σ B   2 )}. In procedure  224 , a last image in the multi-scale representation is generated by applying a Gaussian kernel having scale factor of √{square root over (σ N   2 −σ B   2 )} to the input image. It is noted that, the number of images N (i.e., the actual number of images in the multi-scale representation is N−(M+1)), as well as the scale factors σ 1 , σ 2 , σ 3  . . . σ N  are predetermined by a user. 
     Reference is now made to  FIGS. 6A and 6B .  FIG. 6A  is a schematic illustration of a multi-scale representation of an input focused image, generally referenced  250 , constructed in accordance with a further embodiment of the disclosed technique.  FIG. 6B  is a schematic illustration of a multi-scale representation of an input blurred image, generally referenced  264 , constructed in accordance with another embodiment of the disclosed technique. 
     With reference to  FIG. 6A , multi-scale representation  250  includes a focused input image  252 , a first convolved image  254 , a second convolved image  256 , an M convolved image  258 , an (M+1) convolved image  260 , and an N convolved image  262 . Focused original image  252  can be modeled as an image convolved with a Gaussian kernel having scale factor of σ 0 =0. Multi-scale representation generator  166  ( FIG. 3 ) generates first convolved image  254  by convolving original image  252  with a Gaussian kernel having scale factor of σ 1 . 
     Multi-scale representation generator  166  generates second convolved image  256  by convolving original image  252  with a Gaussian kernel having scale factor of σ 2 . The value of σ 2  is greater than that of σ 1 . Multi-scale representation generator  256  generates M convolved image  258  by convolving original image  252  with a Gaussian kernel having scale factor of σ M . The value of σ M  is greater than that of σ M+1  (i.e., the scale factor of the previous Gaussian kernel, of the set of predetermined Gaussian kernels, —not shown). Multi-scale representation generator  166  generates (M+1) convolved image  260  by convolving original image  252  with a Gaussian kernel having scale factor of σ M+1 . The value of σ M+1  is greater than that of σ M . 
     Multi-scale representation generator  166  generates all the images of multi-scale representation  250  in a manner similar to that described herein above with reference to  FIG. 6A . The last image of multi-scale representation  250  is N convolved image  262 . Multi-scale representation generator  166  generates N convolved image  262  by convolving original image  252  with a Gaussian kernel having scale factor of σ N . The value of σ N  is greater than that of any of the previous variances. 
     With reference to  FIG. 6B , multi-scale representation  264  includes a blurred input image  266 , an M convolved image  268 , an M+1 convolved image  270 , and an N convolved image  272 . Blurred original image  266  can be modeled as an image convolved with a Gaussian kernel having scale factor of σ B . Multi-scale representation generator  166  ( FIG. 3 ) generates a first convolved image (not shown) by convolving original image  266  with a Gaussian kernel having scale factor of σ 1 −σ B . In case the value of σ B  is greater than that of σ 1 , Multi-scale representation generator  166  does not generate the first convolved image and starts the multi-scale representation of original image  266  from a second convolved image. 
     Multi-scale representation generator  166  ( FIG. 3 ) generates the second convolved image by convolving original image  266  with a Gaussian kernel having scale factor of σ 2 −σ B . In case the value of σ B  is greater than that of σ 2 , Multi-scale representation generator  166  does not generate the second convolved image and starts the multi-scale representation of original image  266  from a third convolved image. 
     In the example set forth in  FIG. 6B , the first Gaussian kernel of the predetermined set of Gaussian kernels having scale factor higher than σ B , is Gaussian kernel M. Multi-scale representation generator  166  ( FIG. 3 ) generates M convolved image  268  by convolving original image  266  with a Gaussian kernel having scale factor of σ M −σ B . It is noted that, M convolved image  258  of  FIGS. 6A  and M convolved image  268  of  FIG. 6B  are substantially similar, since convolution with a Gaussian kernel obeys equation (1) as described herein above. 
     Multi-scale representation generator  166  generates all the images of multi-scale representation  264  in a manner similar to that described herein above with reference to  FIG. 6B . The last image of multi-scale representation  264  is the N convolved image  272 . Multi-scale representation generator  166  generates N convolved image  272  by convolving original image  264  with a Gaussian kernel having scale factor of σ N −σ B . 
     It is noted that, image M, M+1, . . . N of multi-scale representation  250  ( FIG. 6A ) and images of M, M+1, . . . N of multi-scale representation  264  ( FIG. 6B ) are substantially similar, respectively. It is further noted that, the number of images in multi-scale representation  264  is (N−(M+1)). It will be appreciated by persons skilled in the art that the disclosed technique is not limited to what has been particularly shown and described hereinabove. Rather the scope of the disclosed technique is defined only by the claims, which follow.