Petite size image processing engine

[0002] This invention relates to the field of digital image processing, and more particularly to methods for producing very low resolution, low bit depth images.

[0003] It would be desirable to display consumer images on the display panels of cellular telephones and personal digital assistants (PDA's). Unfortunately, the displays on currently available cellular telephones and personal digital assistants have a very low resolution (e.g. 95×45 to 302×98 pixels) and low bit depth (e.g. 1 bit). A digital image of a high resolution (e.g. 1536×1024 pixels) and a high bit depth (e.g. 24 bits) can be produced by a digital camera or by scanning a consumer film. If it is subsampled to the resolution of the small display and halftoned to produce a 1-bit depth binary image, the features in the resulting image are rendered indistinctly.

[0004] One approach to producing a low resolution, low bit depth digital image is to first reduce the bit depth of the image using the “stamp filter” available in Adobe Photoshop™, and then sub-sample the image to reduce the resolution. It is believed that the stamp filter employs a rank order filter and a thresholding operation to reduce the bit depth of the image. The resulting images, when displayed on a cellular telephone or PDA, tend to have too much dark areas, obscuring details in these dark areas.

[0005] There is a need therefore for an improved method of processing digital images to produce low resolution, low bit depth images.

[0006] The need is met according to the present invention by providing a digital image processing method for generating a low resolution, low bit depth digital image from a higher resolution, higher bit depth input color digital image that includes the steps of: generating a gray scale image from the input color digital image; generating a low resolution sketch image from the grayscale image; generating a low resolution halftone image from the gray scale image; and combining the low resolution sketch image and the low resolution halftone image to form the low resolution, low bit depth digital image.

[0007] The present invention has the advantage of producing a low resolution low bit depth digital image that is recognizable for its scene/event content on a mobile device with limited display area and bit depth.

[0008] FIG. 1 is a schematic diagram illustrating a system according to the present invention;

[0009] FIG. 2 is a flow chart illustrating the method of processing a digital image according to the present invention;

[0010] FIG. 3 is a flow chart illustrating a preferred method for generating a sketch image used with the present invention; and

[0011] FIG. 4 shows several illustrations of images at different stages in the method and system as shown in the preceding figures.

[0012] The present invention relates to a Petite Size Image Processing Engine (PSIPE) for generating a low resolution, low bit depth digital image from a higher resolution, higher bit depth input color digital image. The low resolution, low bit depth digital image can be transmitted to cellular telephones and PDA's through wireless channel and viewed on the display panels of cellular telephones and PDA's. The method of the present invention is preferably implemented in a programmed digital computer. The programming techniques for producing a program based on the following description are well known in the art.

[0013] Referring to FIG. 1, a typical system architecture for processing, transmitting, and displaying digital images to handheld devices such as cellular telephones and PDA's is shown. The Petite Size Image Processing Engine (PSIPE) consists a single process 12 that applies to the input images from an image database 10 adequate rendering components (pre-processing followed by spatial/bit-depth decimation) given the cell phone display characteristics being extracted from a database 14. The engine then outputs a rendered image 16 that suits the cell phone screens.

[0014] Referring to FIG. 2, in accordance with the present invention, an input color digital images I(x,y) in the Image Database will be processed by PSIPE before being transmitted to cellular telephones and PDA's. Typically, I(x,y) is a digital image of high resolution (e.g. 1536×1024 pixels) and high bit depth (e.g. 24 bits) produced by a digital camera or by scanning a consumer film. If the size of I(x,y) is larger than a predetermined size (e.g. 480×320), I(x,y) is first subsampled 18 to generate an input color digital image I′(x,y) of the predetermined size; otherwise, I′(x,y) will be same as I(x,y). I′(x,y) will then be converted 20 to a gray scale image G(x,y). A typical equation used to generate a gray scale image from a RGB image is given as following:

[0015] G(x,y)=aR′(x,y)+bG′(x,y)+cB′(x,y)

[0016] where R′(x,y), G′(x,y) and B′(x,y) are the red, green and blue channels of the input digital color image I′(x,y). A typical set of coefficients according to the NSTC standard is a=0.3,b=0.59, and c=0.11.

[0017] The gray scale image can be further enhanced prior to further processing. For example, the display panels of cellular telephones and PDA's, in general, are not as bright as those of desktop computers and TV sets. Consequently, image quality may be degraded if the images to be displayed are not bright enough. Thus, it is reasonable to lighten up the gray scale image to a predetermined level if it is too dark. A simple approach to address this problem comprises the following steps:

[0018] 1. calculate the average of the gray scale image; and

[0019] 2. if the average of the gray scale image is below a predetermined value X by Y, add Y to the value of each pixel of the gray scale image, and clip the modified pixel values to the 8 bit range.

[0020] Next, a sketch image 21 and a halftone image 22 are generated from the gray scale image, respectively. After that, the binary sketch image and the binary halftone image are combined 23 to produce a combined image, which remains binary and has the desired low resolution of the display of the cellular telephones or PDA's. The combined image is then ready to be displayed on the display of the cellular telephones or PDA's.

[0021] Various halftone techniques may be used to generate a halftone image from a gray scale image, including error diffusion and blue noise dithering. The preferred halftone technique for this invention is error diffusion. To generate a halftone image, the gray scale image G(x,y) is first sub-sampled to the desired low resolution of the display of the cellular telephones or PDA's, then the subsampled gray scale image is halftoned with the error diffusion technique to produced a halftone image H(x,y).

[0022] Detail steps to generate a sketch image from the gray scale image are given below.

[0023] Referring to FIG. 3, a valley image V(x,y) is generated from the gray scale image G(x,y). A typical way to generate a valley image from a gray scale image consists of the following steps:

[0024] a) blurring 24 the gray scale image G(x,y) to generate a blurred gray scale image B(x,y);

[0025] b) subtracting 26 the blurred gray scale image B(x,y) from the gray scale image G(x,y) to generate the valley image V(x,y).

[0026] The valley image V(x,y) is then filtered 28 with a rank order filter to produce a filtered valley image R(x,y). The rank order filtering is performed using a kernel running across the image. The kernel size, shape, and the rank for the rank filter are set based on the resolution and bit depth of the display of the corresponding cellular telephones and PDA's. Specifically, the subsampling factor F, i.e. the ratio of the pre-determined size (e.g. 480×360) and the size of the display panel, plays an important role. Typically, a square-shaped kernel of 7×7 pixels is used. If desirable, a circular kernel or any other specifically-shaped kernels can be used. The features in the final low resolution, low bit depth digital image should be at least one pixel wide to be visible, therefore the corresponding features in the filtered valley image R(x,y) need to be at least F pixels wide in order to survive the subsampling. Typically, if the subsampling factor F is 4 in each direction, the 15^thranked pixel in an ascending order within the 7×7kernel (a total of 49 pixels) is selected to replace the value of the pixel the current kernel is centered at. If the subsampling factor F is higher, a lower ranked value should be used; and vise versa. For example, if F=1 (no subsampling), the 25^th(median in a 7×7kernel) ranked value is appropriate; if F=2, the 21^stranked value is selected; if F=3, the 18^thranked values is selected; and so on.

[0027] The filtered valley image R(x,y) is further thresholded 30 to generate a binary valley image T(x,y). The preferred threshold for this operation is 250.

[0028] From the gray scale image G(x,y), a histogram H is generated 32. H is further smoothed to generate a smoothed histogram H′. The preferred smoothing technique is a 7 by 1 moving window. From the smoothed histogram H′, the first local minimum BH from the shadow end (corresponding to low intensity values) is located as well as the first local minimum WH from the highlight end (corresponding to high intensity values). Next, a shadow image S(x,y) is generated from the gray scale image G(x,y) such that all the pixels with values below BH are set to zero, and a highlight image L(x,y) is generated from the gray scale image G(x,y) such that all the pixels with values above WH are set to one.

[0029] A composite binary image C(x,y) is further generated 34 from the binary valley image T(x,y), the shadow image S(x,y) and the highlight image L(x,y) in the following way:

[0030] a) if a pixel value in the shadow image S(x,y) is a zero, set the corresponding pixel value in the composite binary image C(x,y) to zero;

[0031] b) if a pixel value in the highlight image L(x,y) is a one, set the corresponding pixel value in the composite binary image C(x,y) to one; and

[0032] c) otherwise, set the corresponding pixel value in the composite binary image C(x,y) to the value of the binary valley image T(x,y).

[0033] The composite binary image C(x,y) is then sub-sampled 36 to a sketch image K(x,y) with the desired low resolution of the display of the cellular telephones or PDA's.

[0034] Finally, the sketch image K(x,y) and the halftone image H(x,y), are combined to produce a combined image O(x,y). The combining step comprises the steps of:

[0035] i) if the pixel value is black in the sketch image, assigning the corresponding pixel value in the combined image to black;

[0036] ii) if the pixel value is white and a neighboring pixel value is black in the sketch image, assigning the corresponding pixel value in the combined image to white; and

[0037] iii) if the pixel value is white and all the neighboring pixel values are white in the sketch image, assigning the corresponding pixel value in the combined image to the value of the corresponding pixel in the halftone image.

[0038] The combined image, which is binary and with the desired low resolution of the display of the cellular telephones or PDA's, is then ready to be displayed on the display of the cellular telephones or PDA's.

[0039] In order to illustrate the result of the foregoing processing, FIG. 4 shows an input image 40, a low resolution, low bit depth image 42 produced by sub-sampling and halftoning, a low resolution, low bit depth image produced by “stamp-filtering” and sub-sampling 44, and a low resolution, low bit depth image 46 produced by the method of the present invention.

[0040] The invention has been described with reference to a preferred embodiment. However, it will be appreciated that variations and modifications can be effected by a person of ordinary skill in the art without departing from the scope of the invention.

[0041] 10 an image database

[0042] 12 Petite Size Image Processing Engine (PSIPE)

[0043] 14 Cell Phone Characteristic Data

[0044] 16 rendered images

[0045] 18 subsampling

[0046] 20 converting RGB image to gray scale image

[0047] 21 generating a sketch image

[0048] 22 generating a halftone image

[0049] 23 combining the sketch image and the halftone image

[0050] 24 blurring an image

[0051] 26 subtracting

[0052] 28 rank order filtering

[0053] 30 thresholding

[0054] 32 histogram analysis

[0055] 34 compositing

[0056] 36 sub-sampling

[0057] 40 an input image

[0058] 42 a low resolution, low bit depth image produced by sub-sampling and halftoning

[0059] 44 a low resolution, low bit depth image produced by “stamp-filtering” and sub-sampling

[0060] 46 a low resolution, low bit depth image produced by the method of the present invention