Detection of sky in digital color images

A method of detecting sky in a digital color image having pixels is disclosed. The method includes identifying pixels from the digital color image representing an initial sky region; developing a model based on the identified sky pixels, wherein such model is a mathematical function that has inputs of pixel position and outputs of color; and using the model to operate on the digital color image to classify additional pixels not included in the initial sky region as sky.

FIELD OF INVENTION

The present invention relates to digital image processing in general, and to detecting sky in images in particular.

BACKGROUND OF THE INVENTION

Sky is among the most important subject matters frequently seen in photographic images. In a digital color image, a pixel or region represents sky if it corresponds to a sky region in the original scene. In essence, a pixel or region represents sky if it is an image of the earth's atmosphere. Detection of sky can often facilitate a variety of image understanding, enhancement, and manipulation tasks. Sky is a strong indicator of an outdoor image for scene categorization (e.g., outdoor scenes vs. indoor scenes, picnic scenes vs. meeting scenes, city vs. landscape, etc.). See, for example M. Szummer and R. W. Picard, “Indoor-Outdoor Image Classification,” inProc. IEEE Intl. Workshop on Content-based Access of Image and Video Database,1998 and A. Vailaya, A. Jain, and H. J. Zhang, “On hnage Classification: City vs. Landscape,” inProc. IEEE Intl. Workshop on Content-based Access of Image and Video Database,1998 (both of which are incorporated herein by reference). With information about the sky, it is possible to formulate queries such as “outdoor images that contain significant sky” or “sunset images” etc. (e.g., see J. R. Smith and C.-S. Li, “Decoding Image Semantics Using Composite Region Templates,” inProc. IEEE Intl. Workshop on Content-based Access of Image and Video Database,1998, incorporated herein by reference). Thus, sky detection can also lead to more effective content-based image retrieval.

For recognizing the orientation of an image, knowledge of sky and its orientation may indicate the image orientation for outdoor images (contrary to the common belief, a sky region is not always at the top of an image). Further, in detecting main subjects in the image, sky regions can usually be excluded because they are likely to be part of the background.

The most prominent characteristic of sky is its color, which is usually light blue when the sky is clear. Such a characteristic has been used to detect sky in images. For example, U.S. Pat. No. 5,889,578, entitled “Method and Apparatus for Using Film Scanning Information to Determine the Type and Category of an Image” by F. S. Jamzadeh, mentions the use of color cue (“light blue”) to detect sky without providing further description.

Commonly assigned U.S. Pat. No. 5,642,443, entitled, “Whole Order Orientation Method and Apparatus” by Robert M. Goodwin, (which is incorporated herein by reference) uses color and (lack of) texture to indicate pixels associated with sky in the image. In particular, partitioning by chromaticity domain into sectors is utilized by Goodwin. Pixels with sampling zones along the two long sides of a non-oriented image are examined. If an asymmetric distribution of sky colors is found, the orientation of the image is estimated. The orientation of a whole order of photos is determined based on estimates for individual images in the order. For the whole order orientation method in Goodwin to be successful, a sufficiently large group of characteristics (so that one with at least an 80% success rate is found in nearly every image), or a smaller group of characteristics (with greater than a 90% success rate, which characteristics can be found in about 40% of all images) is needed. Therefore, with Goodwin, a very robust sky detection method is not required.

In a work by Saber et al. (E. Saber, A. M. Tekalp, R. Eschbach, and K. Knox, “Automatic Image Annotation Using Adaptive Color Classification”, CVGIP:Graphical Models and Image Processing, vol. 58, pp. 115-126, 1996, incorporated herein by reference), color classification was used to detect sky. The sky pixels are assumed to follow a 2D Gaussian probability density function (PDF). Therefore, a metric similar to the Mahalonobis distance is used, along with an adaptively determined threshold for a given image, to determine sky pixels. Finally, information regarding the presence of sky, grass, and skin, which are extracted from the image based solely on the above-mentioned color classification, are used to determine the categorization and annotation of an image (e.g., “outdoor”, “people”).

Recognizing that matching natural images solely based on global similarities can only take things so far. Therefore, Smith, supra, developed a method for decoding image semantics using composite regions templates (CRT) in the context of content-based image retrieval. With the process in Smith, after an image is partitioned using color region segmentation, vertical and horizontal scans are performed on a typical 5×5 grid to create the CRT, which is essentially a 5×5 matrix showing the spatial relationship among regions. Assuming known image orientation, a blue extended patch at the top of an image is likely to represent clear sky, and the regions corresponding to skies and clouds are likely to be above the regions corresponding to grass and trees. Although these assumptions are not always valid, nevertheless it was shown in Smith, supra, that queries performed using CRTs, color histograms and texture were much more effective for such categories as “sunsets” and “nature”.

In commonly assigned U.S. Pat. No. 6,504,951, Luo and Etz show that blue sky appears to be desaturated near the horizon, causing a gradual gradient across a sky region. Sky is identified by examining such gradient signal of candidate sky region. The classification of sky is given to regions exhibiting an acceptable gradient signal. While the method described provides excellent performance, especially in eliminating other objects with similar colors to blue sky, the algorithm may fail to detect small regions of sky (e.g. a small region of sky visible between tree branches) because the small region is not large enough to exhibit the proper gradient signal.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide improved ways of detecting sky in digital images.

This object is achieved by a method of detecting sky in a digital color image having pixels, the method comprising:

a) identifying pixels from the digital color image representing an initial sky region;

b) developing a model based on the identified sky pixels, wherein such model is a mathematical function that has inputs of pixel position and outputs of color; and

c) using the model to operate on the digital color image to classify additional pixels not included in the initial sky region as sky.

It is an advantage of the present invention that more regions and pixels can be correctly identified as representing sky than was possible with heretofore known methods.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, a preferred embodiment of the present invention will be described as a software program. Those skilled in the art will readily recognize that the equivalent of such software may also be constructed in hardware. Because image manipulation algorithms and systems are well known, the present description will be directed in particular to algorithms and systems forming part of, or cooperating more directly with, the method in accordance with the present invention. Other aspects of such algorithms and systems, and hardware and/or software for producing and otherwise processing the image signals involved therewith, not specifically shown or described herein may be selected from such systems, algorithms, components, and elements known in the art. Given the description as set forth in the following specification, all software implementation thereof is conventional and within the ordinary skill in such arts.

The present invention may be implemented in computer hardware. Referring toFIG. 1, the following description relates to a digital imaging system which includes an image capture device10, a digital image processor20, an image output device30, and a general control computer40. The system can include a display device50such as a computer console or paper printer. The system can also include an input control device60for an operator such as a keyboard and or mouse pointer. The present invention can be used on multiple image capture devices10that produce digital images. For example,FIG. 1can represent a digital photofinishing system where the image capture device10is a conventional photographic film camera for capturing a scene on color negative or reversal film, and a film scanner device for scanning the developed image on the film and producing a digital image. The digital image processor20provides the means for processing the digital images to produce pleasing looking images on the intended output device or media. The present invention can be used with a variety of output devices30that can include, but are not limited to, a digital photographic printer and soft copy display. The digital image processor20can be used to process digital images to make adjustments for overall brightness, tone scale, image structure, etc. of digital images in a manner such that a pleasing looking image is produced by an image output device30. Those skilled in the art will recognize that the present invention is not limited to just these mentioned image processing functions.

The general control computer40shown inFIG. 1can store the present invention as a computer program product having a program stored in a computer readable storage medium, which may include, for example: magnetic storage media such as a magnetic disk (such as a floppy disk) or magnetic tape; optical storage media such as an optical disc, optical tape, or machine readable bar code; solid state electronic storage devices such as random access memory (RAM), or read only memory (ROM). The associated computer program implementation of the present invention may also be stored on any other physical device or medium employed to store a computer program indicated by offline memory device70. Before describing the present invention, it facilitates understanding to note that the present invention is preferably utilized on any well-known computer system, such as a personal computer.

It should also be noted that the present invention can be implemented in a combination of software and/or hardware and is not limited to devices which are physically connected and/or located within the same physical location. One or more of the devices illustrated inFIG. 1may be located remotely and may be connected via a wireless connection.

A digital image includes one or more digital image channels. Each digital image channel is a two-dimensional array of pixels. Each pixel value relates to the amount of light received by the imaging capture device corresponding to the physical region of pixel. For color imaging applications, a digital image will often consist of red, green, and blue digital image channels. Motion imaging applications can be thought of as a sequence of digital images. Those skilled in the art will recognize that the present invention can be applied to, but is not limited to, a digital image channel for any of the above mentioned applications. Although a digital image channel is described as a two dimensional array of pixel values arranged by rows and columns, those skilled in the art will recognize that the present invention can be applied to non rectilinear arrays with equal effect. Those skilled in the art will also recognize that for digital image processing steps described hereinbelow as replacing original pixel values with processed pixel values is functionally equivalent to describing the same processing steps as generating a new digital image with the processed pixel values while retaining the original pixel values.

The digital image processor20shown inFIG. 1and programmed to perform the method of the present invention is illustrated in more detail inFIG. 2. An original digital image102can be received from the image capture device10(shown inFIG. 1) in a variety of different color representations. However, the most typical implementation of the present invention receives the original digital image as a color digital image with red, green, and blue digital image channels. Preferably, the pixel values of the original digital image are related to the log of the scene intensity and each pixel value of each color channel is represented as a 12-bit value 0 to 4095. Preferably, every 188 code values represents a doubling of scene intensity (i.e. a photographic stop). For example, a first pixel having a value of 1688 represents a scene intensity that is twice as great as a second pixel having a value of 1500. The present invention can operate successfully with other encodings, including 8-bits RGB, although modification to equation constants and shapes of functions may be required.

The digital image102is input to an initial sky detector110to output an initial sky belief map112. The initial sky belief map112indicates regions or pixels of the digital image102determined to have a non-zero belief that the regions or pixels represent blue sky. A region is a group of spatially connected pixels in a digital image, generally with a common characteristic (for example, similar pixel value). Preferably, the initial sky belief map112is an image having the same number of rows and columns of pixels as the digital image102. The pixel value of a pixel from the initial sky belief map112indicates the belief or probability that the pixel represents blue sky. For example, a pixel value of 255 represents a 100% belief that the pixel is blue sky, a pixel value of 128 represents a 50% belief, and a 0 represents high belief that the pixel is NOT sky. Preferably, the initial sky detector110uses the method described by Luo and Etz in U.S. Pat. No. 6,504,951 the disclosure of which is incorporated by reference herein to produce the initial sky belief map. Briefly summarized, the method of producing the initial sky belief map includes extracting connected components of the potential sky pixels; eliminating ones of the connected components that have a texture above a predetermined texture threshold; computing desaturation gradients of the connected components; and comparing the desaturation gradients of the connected components with a predetermined desaturation gradient for sky to identify true sky regions in the image. The method of Luo and Etz is advantageous because of its low false positive detection rate, which is essential for preventing the subsequent steps from including other objects having similar colors.

The initial sky belief map112need not be represented as an image. For example, the initial sky belief map112can be a list of pixels or regions corresponding to locations in the digital image102and associated belief values.

The initial sky belief map112is passed to a model fitter114for fitting a model116to the pixel colors of at least one region having non-zero belief in the initial sky belief map112. Preferably the model116is fitted to the color values of pixels from the region. The preferred model116is a two-dimensional second order polynomial of the form:
R′(x,y)=r0x2+r1xy+r2y2+r3x+r4y+r5(1)
G′(x,y)=g0x2+g1xy+g2y2+g3x+g4y+g5(2)
B′(x,y)=b0x2+b1xy+b2y2+b3x+b4y+b5(3)
In matrix notation:

Cloudless sky generally changes slowly in color throughout an image and can be well modeled with the second order polynomial.

The dependent variables (i.e. inputs) of the model116are pixel positions x and y. The model coefficients are r0. . . r5, g0. . . g5, and b0. . . b5. The output of the model116is the estimated pixel color value [R′(x,y), G′(x,y), B′(x,y)] of a pixel at position (x,y). The coefficients are preferably determined such that the mean squared error between the actual pixel values and the estimated pixel color value is minimized. Such least—squares polynomial fitting techniques are well known in the art. A preferred method involves forming the Vandermonde matrix from N pixels selected from the at least one region having non-zero belief in the initial sky belief map112. If the initial map has multiple non-zero belief regions, then the largest or highest-belief region may be selected as the region for constructing the model116. For a second order polynomial, the Vandermonde matrix has N rows and 6 columns where each row corresponds to the position coordinates of one of the selected pixels:

V=[x02x0⁢y0y02x0y01x12x1⁢y1y12x1y11⋮⋮⋮⋮⋮1xN-12xN-1⁢yN-1yN-12xN-1yN-11](5)
Additionally, for each color, an array A is defined of the actual pixel values from the digital image at the corresponding location:

A=[C⁡(x0,y0)C⁡(x1,y1)⋮C⁡(xN-1,yN-1)](6)
Where C(x,y) represents the value of a particular channel of the digital image102at position (x,y). Then, the least squares solution for the coefficients for channel C can be shown to be:
[c0c1c2c3c4c5]T=(VTV)−1VTA(7)

The model error for each color channel can also be determined by computing the square root of the mean squared difference between the array A and the array V[c0c1c2c3c4c5]T(the estimate of pixel color for a particular channel). The model error relates to the “goodness of fit” of the model to the known non-zero belief region.

In summary, the model116has inputs of pixel position and outputs an estimate of color (the model expectation). The model116(equations and coefficients) is input to the model applicator118along with candidate pixels or regions122extracted from the digital image102. Segmentation is used to generate the candidate sky regions122. Segmentation is performed by well known techniques such as color clustering algorithm (e.g. the well known K-Means clustering algorithm.) Preferably, the candidate sky regions122are generated by using a neural network followed by connected component analysis as described in U.S. Pat. No. 6,504,951 such that these candidate sky regions have colors typical of blue sky. The model applicator118uses the model116to classify pixels as sky that were not originally classified as sky in the initial sky belief map112. The model applicator118outputs an improved sky belief map120indicating pixels or regions of the digital image102that are believed to represent sky. The model applicator118can be applied repeatedly to different pixels or regions122from the digital image, until all pixels or regions (excluding pixels or regions originally corresponding with non-zero belief value in the initial sky belief map112) have been considered by the model applicator118.

FIG. 3shows a more detailed view of the model applicator118. The model applicator118considers candidate sky regions or pixels122from the digital image102and determines if the color values of the candidate sky regions or pixels122are well explained by the model116and satisfy additional criteria. The model evaluator130evaluates the model116for all pixel positions of the candidate sky regions or pixels122, creating a model expectation132of the color values for the candidate sky regions or pixels122. A model satisfier134determines whether the color values of the candidate pixels or regions122of the digital image102are similar enough to the model explanation132and a classifier136considers the result of the model satisfier134and an additional criteria analyzer138and determines whether to classify the candidate sky regions or pixels122as “sky” or “not sky”.

The model satisfier134considers the actual color values and the color values of the model expectation132of the candidate sky regions or pixels122. A pixel is considered to satisfy the model when the corresponding color value of the model expectation is close to the actual color value of the pixel. Preferably, the model color estimate is considered to be close to the actual color when the difference between the model color estimate and the actual color value of the pixel for each color channel is less than T0times the model error for that color channel. Preferably T0=4.

Additional criteria that is considered by the additional criteria analyzer138is the hue of the model's color estimate. The method of the present invention is primarily directed at detecting blue sky (although with modification it could be used to detect other smoothly varying sky signals, such as certain sunrise or sunset skies). In order for a pixel to satisfy the additional criteria, the model's color estimate must be blue or nearly blue (e.g. the ratio R′(x, y)/B′(x, y) must be less than T1, where preferably T1=0.9). Those skilled in the art will recognize that the additional criteria may include other features related to the color or structure of the candidate pixels or regions122or the model116itself. For example, because sky is smoothly varying, in the case where the candidate pixel or region122is a region, the additional criteria may specify a limit below which the standard deviation of the color values of the regions pixel's must fall in order to satisfy the additional criteria. Furthermore, the additional criteria that may be considered can include the size (e.g. number of pixels) of a candidate sky region122. For example, in addition to the aforementioned requirements, satisfaction of the additional criteria may require that the region contain at least T2pixels. Preferably T2=20. Still furthermore, satisfaction of the additional criteria may require that at least T3*100% of the candidate sky region's pixels satisfy the model satisfier134. Preferably T3=0.80.

Finally, the classifier136considers the result of the model satisfier134and the additional criteria analyzer138and determines whether to classify the candidate sky regions or pixels122as “sky” or “not sky”. When the candidate pixel or region122is a pixel, then the classifier136simply labels the pixel as “sky” when the additional criteria analyzer138indicates that the additional criteria is satisfied and the model satisfier134indicates that the model116is also satisfied.

When the candidate pixels or region122is a region of pixels, then the classifier136must consider multiple results from the model satisfier134and then classifies the region as “sky” or “not sky”. Preferably, the classifier136classifies a region as “sky” when the additional criteria analyzer138indicates that all of the additional criteria are met.

The classifier136outputs an improved sky belief map120. Preferably the improved sky belief map120is the same as the initial sky belief map112for pixels and regions having non-zero belief of representing sky in the initial sky belief map112. The improved sky belief map120also indicates the pixels and regions judged by the classifier136as being “sky” with non-zero belief values equal to (alternatively a function of) the belief value of the non-zero belief region(s) of the initial sky belief map112that was (were) originally used to generate the model116by the model fitter114ofFIG. 2. Regions or pixels classified as “not sky” are indicated with a belief value of 0 in the improved sky belief map120.

Alternatively, the model satisfier134outputs a probability P that indicates a probability that the candidate pixel or region is sky. The probability is determined based on the aforementioned difference between the model color estimate and the actual color value of each pixel. As the difference increases, the probability decreases. For example, if the difference is 0 for all pixels in the region, then the model satisfier134outputs a probability P=100% that the region is sky. If the (Root Mean Square) average pixel difference is 3 times the model error, then the model satisfier134outputs a probability P=60%. The classifier136then classifies the pixel or region as “sky” or “not sky” based on the probability P from the model satisfier134and the information from the additional criteria analyzer138. For example, the classifier136classifies regions as “sky” when the probability P is greater than 50% (assuming the additional criteria is met.) In this embodiment, a probability that a pixel or region represents sky is assigned based on the difference between the model color estimate and the actual color value of each pixel. Then the assigned probability is used to determine if the pixel or region is sky.

FIG. 4shows an alternative view of the digital image processor20. As previously described, the initial sky detector110outputs an initial sky belief map112. The initial sky belief map112and a candidate sky region122is input to the model fitter114. In this case the model fitter114constructs two models116. A first model1161is the model relating to a non-zero belief region of the initial sky belief map112, as previously described with respect toFIG. 2. A second model1162is generated using the same process of fitting a two dimensional second order polynomial to pixels of a non-zero belief region of the initial sky belief map and pixels from the candidate sky region122. The models116are input to the model analyzer140. The model analyzer140determines whether or not to classify the candidate sky region122as “sky” or “not sky” based on the first and second models. The candidate sky region is classified to be “sky” when the following conditions are met:1. The model error for the pixels belonging to the non-zero belief region of the initial sky belief map112is not more than T4% greater (preferably T4=50) for the second model than for the first.2. The model error for the candidate sky region with the second model is not more than T5% (preferably T5=50) the model fit error of the pixels belonging to the non-zero belief region of the initial sky belief map112with the first model.3. The average color of the candidate sky region [RaGaBa] is such that Ra/Ba<T5(preferably T5=0.9).
The model analyzer140outputs an improved sky belief map120. Preferably the improved sky belief map120is the same as the initial sky belief map112for pixels and regions having non-zero belief of representing sky in the initial sky belief map112. The improved sky belief map120also indicates the pixels and regions judged by the classifier136as being “sky” with non-zero belief values equal to (alternatively a function of) the belief value of the non-zero belief region(s) of the initial sky belief map112that was (were) originally used to generate the model116by the model fitter114ofFIG. 2. Regions or pixels classified as “not sky” are indicated with a belief value of 0 in the improved sky belief map120.

FIGS. 5A-Cshow images that illustrate the effect of the present invention.FIG. 5Ashows a drawing representing an original image with sky. Trees spatially break of the sky on the image into two sky regions, a smaller region162and a larger region160.FIG. 5Bshows a representation of an initial sky belief map112. A dark region164indicates a region having non-zero belief that initially identifies a sky region. However, sky region162ofFIG. 5Awas not correctly identified as sky because it is not big enough to exhibit the gradient signal typical of blue sky.FIG. 5Cshows a representation of the improved, sky belief map120where dark regions166and164correctly identify the two sky regions160and162of the original image shown inFIG. 5A.

The method of the present invention can be performed in a digital camera, a digital printer, or on a personal computer.

PARTS LIST