Patent Document

FIELD OF THE INVENTION  
       [0001]     Embodiments of the present invention comprise methods and systems for automatically detecting regions in digital images.  
       BACKGROUND  
       [0002]     The content of a digital image can have considerable impact on the compression of the digital image, both in terms of compression efficiency and compression artifacts. Pictorial regions in an image are not efficiently compressed using compression algorithms designed for the compression of text. Similarly, text images are not efficiently compressed using compression algorithms that are designed and optimized for pictorial content. Not only is compression efficiency affected when a compression algorithm designed for one type of image content is used on a different type of image content, but the decoded image may exhibit annoying compression artifacts.  
         [0003]     Further, image enhancement algorithms designed to sharpen text, if applied to pictorial image content, may produce visually annoying artifacts in some areas of the pictorial content. In particular, those areas of the pictorial content containing strong edges may be affected. While smoothing operations may enhance a natural image, the smoothing of text regions is seldom desirable.  
         [0004]     The detection of regions of a particular content type in a digital image can improve compression efficiency, reduce compression artifacts, and improve image quality when used in conjunction with a compression algorithm or image enhancement algorithm designed for the particular type of content.  
         [0005]     The semantic labeling of image regions based on content is also useful in document management systems and image databases.  
         [0006]     Reliable and efficient detection of regions of pictorial content type and other image regions in digital images is desirable.  
       SUMMARY  
       [0007]     Embodiments of the present invention comprise methods and systems for classifying an image into regions using a masking condition and an entropy measure.  
         [0008]     The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention taken in conjunction with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS  
       [0009]      FIG. 1  is an example of an image comprising a multiplicity of regions of different content type;  
         [0010]      FIG. 2  is a diagram of an exemplary region-detection system (prior art);  
         [0011]      FIG. 3  is an exemplary histogram showing feature value separation;  
         [0012]      FIG. 4  is an exemplary histogram showing feature value separation;  
         [0013]      FIG. 5  is a diagram showing exemplary embodiments of the present invention comprising a masked-entropy calculation from a histogram;  
         [0014]      FIG. 6  is a diagram showing an exemplary embodiment of masked-image generation;  
         [0015]      FIG. 7  is a diagram showing an exemplary embodiment of histogram generation;  
         [0016]      FIG. 8  is diagram showing pixel classification comprising an image window;  
         [0017]      FIG. 9  is a diagram showing block classification comprising an image window;  
         [0018]      FIG. 10  is a diagram showing exemplary embodiments of the present invention comprising a masked-entropy calculation from a histogram using confidence levels;  
         [0019]      FIG. 11  is a diagram showing an exemplary embodiment of masked-image generation using confidence levels; and  
         [0020]      FIG. 12  is a diagram showing an exemplary embodiment of histogram generation using confidence levels.  
     
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS  
       [0021]     Embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The figures listed above are expressly incorporated as part of this detailed description.  
         [0022]     It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the methods and systems of the present invention is not intended to limit the scope of the invention but it is merely representative of the presently preferred embodiments of the invention.  
         [0023]     Elements of embodiments of the present invention may be embodied in hardware, firmware and/or software. While exemplary embodiments revealed herein may only describe one of these forms, it is to be understood that one skilled in the art would be able to effectuate these elements in any of these forms while resting within the scope of the present invention.  
         [0024]      FIG. 1  shows an image  10  comprising three regions: a pictorial region  12 , a text region  14 , and a graphics region  16 . For many image processing, compression, document management, and other applications, it may be desirable to detect various regions in an image. Exemplary regions may include: a pictorial region, a text region, a graphics region, a half-tone region, a continuous-tone region, a color region, a black-and-white region, a region best compressed by Joint Photographic Experts Group (JPEG) compression, a region best compressed by Joint Bi-level Image Experts Group (JBIG) compression, a background region, and a foreground region.  
         [0025]     An exemplary region-detection system  20  is shown in  FIG. 2 . A region-detection system  20  may include a feature extractor  22  and a classifier  24 . The feature extractor  22  may measure, calculate, or in some way extract, a feature or features  23  from the image. The classifier  24  may classify portions of the image based on the extracted feature or features  23 . The classification  25  produced by the classifier  24  thereby provides detection of image regions.  
         [0026]     The effectiveness and reliability of a region-detection system may depend on the feature or features used for the classification.  FIG. 3  shows an example of a normalized frequency-of-occurrence plot of feature values for two image regions. The solid line  32  shows the frequency of occurrence of feature values extracted from image samples belonging to one region. The dashed line  34  shows the frequency of occurrence of feature values extracted from image samples belonging to a second region. The strong overlap of these two histograms may indicate that the feature may not be an effective feature for separating image samples belonging to one of these two regions.  
         [0027]      FIG. 4  shows another example of a normalized frequency of occurrence plot of feature values for two image regions. The solid line  42  shows the frequency of occurrence of feature values extracted from image samples belonging to one region. The dashed line  44  shows the frequency of occurrence of feature values extracted from image samples belonging to a second region. The wide separation of these two histograms may indicate that the feature will be an effective feature for classifying image samples as belonging to one of these two regions.  
         [0028]     Embodiments of the present invention comprise methods and systems for region detection in a digital image. Some embodiments of the present invention comprise methods and systems for region detection in a digital image wherein the separation between feature values corresponding to image regions may be accomplished by masking, prior to feature extraction, pixels in the image for which a masking condition is met. In some embodiments, the masked pixel values may not be used when extracting the feature value from the image.  
         [0029]     In exemplary embodiments of the present invention shown in  FIG. 5 , a masked image  51  may be formed  52  from an input image  50 . The masked image may be formed by checking a masking condition at each pixel in the input image  50 . An exemplary embodiment shown in  FIG. 6 , illustrates the formation of the masked image  52 . If an input image pixel  60  satisfies the masking condition  62 , the value of the pixel at the corresponding location in the masked image may be assigned a value, called a mask-pixel value,  66 , indicating that the masking condition is satisfied at that pixel location in the input image. If an input image pixel  60  does not satisfy the masking condition  64 , the value of the pixel at the corresponding location in the masked image may be assigned the value of the input pixel in the input image  68 . The masked image thereby masks pixels in the input image for which a masking condition is satisfied.  
         [0030]     In the exemplary embodiments of the present invention shown in  FIG. 5 , after forming  52  the masked image  51 , a histogram  53  may be generated  54  for a block, also considered a segment, section, or any division, not necessarily rectangular in shape, of the masked image  51 . For the purposes of this specification, associated claims, and included drawings, the term block will be used to describe a portion of data of any shape including, but not limited to, square, rectangular, circular, elliptical, or approximately circular.  FIG. 7  shows an exemplary embodiment of histogram formation. A histogram with bins corresponding to the possible pixel values of the masked image may be formed according to  FIG. 7 . In some embodiments, all bins may be initially considered empty with initial count zero. The value of a pixel  70  in the block of the masked image may be compared  71  to the mask-pixel value. If the value of the pixel  70  is equal  72  to the mask-pixel value, then the pixel is not accumulated in the histogram, meaning that no histogram bin is incremented, and if there are pixels remaining in the block to examine  76 , then the next pixel in the block is examined  71 . If the value of the pixel  70  is not equal  73  to the mask-pixel value, then the pixel is accumulated in the histogram  74 , meaning that the histogram bin corresponding to the value of the pixel is incremented, and if there are pixels remaining in the block to examine  77 , then the next pixel is examined  71 .  
         [0031]     When a pixel is accumulated in the histogram  74 , a counter for counting the number of non-mask pixels in the block of the masked image is incremented  75 . When all pixels in a block have been examined  78 ,  79 , the histogram may be normalized  80 . The histogram may be normalized  80  by dividing each bin count by the number of non-mask pixels in the block of the masked image. In alternate embodiments, the histogram may not be normalized and the counter may not be present.  
         [0032]     An entropy measure  55  may be calculated  56  for the histogram  53  of a block of the masked image. The entropy measure  55  may be considered an image feature of the input image. The entropy measure  55  may be considered any measure of the form:  
         -       ∑     i   =   1     N     ⁢       h   ⁡     (   i   )       *     f   ⁡     (     h   ⁡     (   i   )       )             ,       
 
 where N is the number of histogram bins, h(i) is the accumulation or count of bin i, and f(·) may be a function with mathematical characteristics similar to a logarithmic function. The entropy measure  55  may be weighted by the proportion of pixels that would have been counted in a bin, but were masked. The entropy measure is of the form:  
       -       ∑     i   =   1     N     ⁢       w   ⁡     (   i   )       ⁢     h   ⁡     (   i   )       *     f   ⁡     (     h   ⁡     (   i   )       )               
 
 where w(i) is the weighting function. In some embodiments of the present invention, the function f(h(i)) may be log 2 (h(i)). 
 
         [0033]     In the embodiments of the present invention shown in  FIG. 5 , after calculating  56  the entropy measure  55  for the histogram  53  corresponding to a block of the image centered at a pixel, the pixel may be classified  57  according to the entropy feature  55 . The classifier  57  shown in  FIG. 5  may be based on thresholding. A threshold may be determined a priori, adaptively, or by any of numerous methods. The pixel may be classified  57  as belonging to one of two regions depending on which side of the threshold the entropy measure  55  falls.  
         [0034]     In some embodiments of the present invention, a moving window of pixel values centered, in turn, on each pixel of the image, may be used to calculate the entropy measure for the block containing the centered pixel. The entropy may be calculated from the corresponding block in the masked image. The entropy value may be used to classify the pixel at the location on which the moving window is centered.  FIG. 8  shows an exemplary embodiment in which a block of pixels is used to measure the entropy feature which is used to classify a single pixel in the block. In  FIG. 8 , a block  80  is shown for an image  81 . The pixels in the masked image in the corresponding block may be used to calculate the entropy measure. The pixel in the center of the image  82  may be classified according the entropy measure.  
         [0035]     In other embodiments of the present invention, the entropy value may be calculated for a block of the image, and all pixels in the block may be classified with the same classification based on the entropy value.  FIG. 9  shows an exemplary embodiment in which a block of pixels is used to measure the entropy feature which is used to classify all pixels in the block. In  FIG. 9 , a block  90  is shown for an image  91 . The pixels in the masked image in the corresponding block may be used to calculate the entropy measure. All pixels  92  in the block  90  may be classified according to the entropy measure.  
         [0036]     In some embodiments of the present invention, the masking condition may be based on the edge strength at a pixel.  
         [0037]     In some embodiments of the present invention, a level of confidence in the degree to which the masking condition is satisfied may be calculated. The level of confidence may be used when accumulating a pixel into the histogram. Exemplary embodiments in which a level of confidence is used are shown in  FIG. 10 .  
         [0038]     In exemplary embodiments of the present invention shown in  FIG. 10 , a masked image  101  may be formed  102  from an input image  100 . The masked image may be formed by checking a masking condition at each pixel in the input image  100 . An exemplary embodiment shown in  FIG. 11 , illustrates the formation of the masked image  102 . If an input image pixel  110  satisfies the masking condition  112 , the corresponding pixel in the masked image may be assigned a value, mask-pixel value,  116  indicating that the masking condition is satisfied at that pixel. If an input image pixel  110  does not satisfy the masking condition  114 , the corresponding pixel in the masked image may be assigned the value of the corresponding pixel in the input image  118 . At pixels for which the masking condition is satisfied  112 , a further assignment  115  of a confidence value reflecting the confidence in the mask signature signal may be made. The assignment of confidence value may be a separate value for the masked pixels, or the mask-pixel value may be multi-level with the levels representing the confidence. The masked image may mask pixels in the input image for which a masking condition is satisfied, and further identify the level to which the masking condition is satisfied.  
         [0039]     In the exemplary embodiments of the present invention shown in  FIG. 10 , after forming  102  the masked image  101 , a histogram  103  may be generated  104  for a block of the masked image  101 .  FIG. 12  shows an exemplary embodiment of histogram formation  104 . A histogram with bins corresponding to the possible pixel values of the masked image may be formed according to  FIG. 12 . In some embodiments, all bins may be initially considered empty with initial count zero. The value of a pixel  120  in the block of the masked image may be compared  121  to the mask-pixel value. If the value of the pixel  120  is equal  122  to the mask-pixel value, then the pixel is accumulated  123  in the histogram at a fractional count based on the confidence value, and if there are pixels remaining in the block to examine  126 , then the next pixel in the block is examined  121 . If the value of the pixel  120  is not equal  123  to the mask-pixel value, then the pixel is accumulated in the histogram  124 , meaning that the histogram bin corresponding to the value of the pixel is incremented, and if there are pixels remaining in the block to examine  127 , then the next pixel in the block is examined  121 .  
         [0040]     When a pixel is accumulated in the histogram  124 , a counter for counting the number of non-mask pixels in the block of the masked image is incremented  125 . When all pixels in a block have been examined  128 ,  129 , the histogram may be normalized  130 . The histogram may be normalized  130  by dividing each bin count by the number of non-mask pixels in the block of the masked image. In alternate embodiments, the histogram may not be normalized and the counter not be present.  
         [0041]     An entropy measure  105  may be calculated  106  for the histogram of a neighborhood of the masked image as described in the previous embodiments. In the embodiments of the present invention shown in  FIG. 10 , after calculating  106  the entropy measure  105  for the histogram  103  corresponding to a block of the image centered at a pixel, the pixel may be classified  107  according to the entropy feature  105 . The classifier  107  shown in  FIG. 10  may be based on thresholding. A threshold may be determined a priori, adaptively, or by any of numerous methods. The pixel may be classified  107  as belonging to one of two regions depending on which side of the threshold the entropy measure  105  falls.  
         [0042]     In some embodiments of the present invention, the masking condition may comprise a single image condition. In some embodiments, the masking condition may comprise multiple image conditions combined to form a masking condition.  
         [0043]     In some embodiments of the present invention, the entropy feature may be used to separate the image into two regions. In some embodiments of the present invention, the entropy feature may be used to separate the image into more than two regions.  
         [0044]     The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention in the use of such terms and expressions of excluding equivalence of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.

Technology Category: 3