System and method for the dynamic thresholding of grayscale image data

[0002] This invention relates generally to the processing of grayscale image data. More particularly, this invention relates to the conversion of grayscale image data containing text and line art features on a non-white background into a halftone image.

[0003] Grayscale images use many shades of gray to represent an image. Halftone images, in contrast, typically use black and white dots to form an image. The pattern and density of the black and white dots is varied to represent different shades. Problems arise when converting a grayscale image into a halftone image when the grayscale image background is a non-white color or the foreground color is not black. Current methods of converting grayscale image into halftone image data result in the text and line art features in the grayscale image on a non-white background being obscured when converted into a halftone image. When converting a grayscale image which contains many different shades of gray, the conversion algorithm must determine whether to fill the corresponding position on the halftone image being created with a black dot or a white space. Current algorithms used in the conversion process have difficulty picking out the edge of text and line art features in grayscale images from backgrounds which are not white, resulting in lack of definition of the text and line art features in the new halftone image.

[0004] The present invention addresses problems caused by the current methods of converting grayscale image data into halftone images when the grayscale image data has a non-white background and contains text and line art features. One embodiment of the invention utilizes a conversion algorithm which uses a combination of pixel averages formed from different subsets of pixel values of pixels located within the grayscale image data. The different pixel averages are weighted differently depending on the particular characteristics of the area of the grayscale image data being converted to halftone image data. Pixels are examined one pixel at a time in the grayscale image. The pixel being examined is the focus pixel. Running averages are maintained for both the average pixel value of pixels located in the row of pixels containing the focus pixel and the average pixel value of pixels located in the column pixels containing the focus pixel. Additionally, a pixel window is superimposed over the grayscale image area near the focus pixel, and the average pixel value of the pixels in that pixel window is tracked. The conversion algorithm examines the area near the focus pixel in the grayscale image data for edges indicative of text and line art features and adjusts the weight given to the different averages depending upon whether or not an edge indicating a text or line art feature was found in the grayscale image data. If an edge is detected in the grayscale image, the conversion algorithm gives more weight to the local pixel average. If, on the other hand, the presence of an edge is not detected in the area of the focus pixel, more weight is given in the conversion algorithm to the running horizontal and vertical averages. After assigning the proper weight to the averages, the conversion algorithm produces a threshold value which is compared against the pixel value and used to determine whether that pixel will be depicted as a 1, that is a black dot, or a 0, that is a white space in the halftone image. By shifting the weight given to the various pixel averages depending upon the presence or non-presence of an edge, the conversion algorithm is better able to isolate text and line art features from a non-white background in a grayscale image.

[0005] FIG. 1 is a flow chart of the steps taken by an illustrated embodiment of the present invention to produce a halftone pixel value from a grayscale pixel value;

[0006] FIG. 2 is a block diagram depicting the calculating of the horizontal and vertical running averages used by the illustrated embodiment;

[0007] FIG. 3 is a block diagram depicting the calculation of the local pixel average used by the illustrated embodiment;

[0008] FIG. 4A is a block diagram of the horizontal edge correlator used in the illustrated embodiment of the present invention; and

[0009] FIG. 4B is a depiction of the vertical edge correlator used by the illustrated embodiment of the present invention.

[0010] The illustrated embodiment of the present invention addresses the problems encountered when converting grayscale images into halftone images. The illustrated embodiment addresses the difficulties encountered in converting grayscale images which contain line art and text features on a non-white background into halftone images. Current conversion methods have difficulties converting the multi-bit grayscale values into single bit halftone values when the background of the image is non-white because the algorithms have difficulties extracting the edges of the text and line art features from the non-white background. The conversion process of the illustrated embodiment tracks continuous horizontal and vertical running pixel value averages which are aggregated into a single average, and also tracks a separate local pixel value average. A weight driven conversion algorithm is used which takes the aggregate average and local pixel average into account, thereby enabling more efficient extraction of text and line art features from the non-white background of a grayscale image.

[0011] FIG. 1 depicts the steps followed by the conversion algorithm of the illustrated embodiment to convert a multi-bit grayscale pixel value into a single bit halftone pixel value of either 1 or 0. A halftone value of 1 corresponds to a black pixel color, and a halftone value of 0 corresponds to a white pixel color. The conversion algorithm begins by selecting a pixel to examine in the grayscale image data, a focus pixel (step 2). The pixels immediately adjacent to the focus pixel are examined to see if their pixel values indicate the presence of an edge in the grayscale image data horizontally oriented to the focus pixel (step 4). Similarly, the pixels in the grayscale image data immediately adjacent to the focus pixel are examined to see if their pixel values indicate the presence of an edge vertically oriented to the focus pixel (step 6). These examinations utilize horizontal and vertical edge correlator algorithms which are explained more fully below.

[0012] The output from the horizontal edge examination (step 4) and the vertical edge examination (step 6) are added together and then divided by a normalizing factor such that the result of the division always yields a result that will be between 0 and 1 (step 8). This result is utilized as a weight factor by the conversion algorithm. The conversion algorithm uses the weight factor to shift the level of emphasis on different pixel averages used by the conversion algorithm.

[0013] The conversion algorithm next determines three pixel value averages of subsets of pixels located within the grayscale image data. A horizontal pixel average is determined by averaging the pixel values of pixels located in the grayscale image data on the same horizontal row as the focus pixel (step 10). A vertical pixel value average is determined by averaging the pixel values of pixels located in the grayscale image data in the same vertical column as the focus pixel (step 12). A local pixel average is determined consisting of the average pixel value of the pixels located in a pixel window centered on the focus pixel. In one embodiment of the present invention, such a pixel window is 5 pixels by 5 pixels. The 25 individual pixel values are added together by the conversion algorithm and divided by 25 to arrive at a local pixel average for use by the conversion algorithm.

[0014] Once the three pixel averages and the weight factor have been calculated, the conversion algorithm calculates a threshold value which is used to decide whether the focus pixel will be represented as a black or white pixel in the halftone image being created (step 16). The conversion algorithm applies the weight factor (step 8) to the horizontal and vertical pixel averages (step 10 and step 12) and the local pixel average (step 14). The conversion algorithm averages the horizontal and vertical running averages, multiplies them by 1 minus the weight factor (i.e.: a number between 0 and 1) and adds the results to the result of the local average multiplied by the weight factor (a number between 0 and 1). When the weight factor is large, the first multiplier used with the horizontal and vertical running averages will be smaller than the second multiplier used with the local pixel average. When the weight factor is small, the opposite is true. This calculation gives more weight to the local pixel average if an edge is detected in the immediate vicinity of the focus pixel, and more weight to the horizontal and vertical running averages in the event no edge has been detected. The result of the algorithm produces a threshold value (step 18) which is applied to the focus pixel value (step 20) to produce a halftone output (step 22). If the focus pixel value exceeds the threshold value, a halftone output of 1 indicating a black halftone pixel is produced. If the focus pixel value does not exceed the threshold value, a halftone output of 0 is produced, indicating a halftone white pixel is produced. Every pixel in the grayscale image data is analyzed in this manner.

[0015] FIG. 2 depicts a focus pixel 26 located within grayscale image data. The pixels in the same horizontal row 28 as the focus pixel 26 are used to calculate the running pixel value average of the horizontal pixels. Similarly, the pixels in the same vertical column 30 as the focus pixel 26 are used to calculate the pixel value average of the vertical pixels. These averages are given more weight by the conversion algorithm in the illustrated embodiment in the event the examination of the the grayscale image data near the focus pixel does not detect the presence of an edge. If the running horizontal and pixel value averages are given more weight by the conversion algorithm, a lower threshold value is generated compared to the occasions when an edge is detected. The lower the threshold value, the higher the likelihood that the focus pixel value exceeds the threshold value and is to be represented by a black pixel in the halftone image being created.

[0016] FIG. 3 depicts a focus pixel 34 located within grayscale image data and a pixel window 36 (indicated by darkened lines in FIG. 3) superimposed on the grayscale image data and centered on the focus pixel 34. Those skilled in the art will realize that while the depicted pixel window 36 is centered on the focus pixel 34, in other embodiments of the present invention the pixel window may overlay the focus pixel in a non-centered orientation. The pixel window 36 is used to calculate a local average of pixel values. The local average for pixel values is given more weight by the conversion algorithm in the event the horizontal and vertical edge correlator algorithms indicate the likely presence of an edge in the grayscale image data adjacent to the focus pixel 34 being examined. The edge correlator algorithms are explained more fully below. By giving more weight to the local pixel value average in the presence of an edge, the conversion algorithm generates a threshold value closer to the value of a focus pixel than would be generated by emphasizing the horizontal and vertical running pixel averages. A larger threshold value forces the focus pixel value to be larger in order to generate a dark halftone output value. The presence of the edge values increases the local pixel pixel value average and the conversion algorithm must adjust accordingly.

[0017] FIG. 4A indicates the horizontal edge correlator used in the illustrated embodiment of the present invention. The pixel values of pixels adjacent to a focus pixel 38 are examined to evaluate the likely presence of an edge in the grayscale image data horizontally oriented to the focus pixel. The pixel values for pixels 39, 40, and 41 are added together and subtracted from the aggregate of the pixel values for pixels 42, 43, and 44. The result is used to inform the conversion algorithm of the presence of an horizontally oriented edge in the grayscale image data near the focus pixel. In general terms, the larger the the result of the horizontal edge correlator, the more likely it is that a horizontally oriented edge is present in the grayscale image data.

[0018] Similarly, FIG. 4B depicts a vertical edge correlator being applied around a selected focus pixel 46. The pixel values for pixels 50, 51, and 52 are added together to form a first aggregate value, and the pixel values 47, 48, and 49 are added together to form a second aggregate value which is subtracted from the first aggregate value. The result is used to inform the conversion algorithm of a vertically oriented edge in the grayscale image data near the focus pixel. In general terms, the higher the value produced by the computation, the more likely it is that an edge vertically oriented to the focus pixel exists in the grayscale image data.

[0019] It will thus be seen that the invention efficiently attains the objectives stated in the previous description. Since certain changes may be made without departing from the scope of the present invention, it is intended that all matter contained in the above description or shown in the accompanying drawings be interpreted as illustrative and not in a literal sense. Practitioners of the art will realize that the sequence of steps in the conversion algorithm may be altered without departing from the scope of the present invention and that the illustrations contained herein are singular examples of a multitude of possible depictions of the present invention.