Method and apparatus for repurposing binary images

[0002] This application claims priority from U.S. Provisional application 60/080,369 filed Apr. 1, 1998.

[0003] The present invention pertains to the field of digital printing and imaging, and is specifically directed to the reproduction of digitized documents.

[0004] With the growing use of digital input means such as digital scanners and cameras, and digital printers, users will demand more flexibility in their choice of input and output devices. Thus it becomes important to be able to repurpose documents and images automatically and efficiently. The term repurpose is defined as follows. Any multimedia object such as text, images, audio and video is created with a specific purpose in mind, i.e. a target audience and conditions under which the object is consumed by the audience. By repurposing, we mean processing the multimedia object so that it serves a different purpose, i.e a different target audience and conditions governing the use of the object. For instance, a newspaper agency would like to format text and images for printing in a newspaper, and take the same content and repurpose it for on-line viewing on the Web. If a better printer becomes available, a user will be interested in taking pictures scanned and formatted for an original printer and printing them on an improved printer. Since the original scanned document or object is invariably not available, it is crucial for this repurposing to be done automatically from the available halftone.

[0005] With the growing use of multimedia objects as well as the increasing number of choices for output media, such as different printers and monitors, it is very hard to anticipate all the uses of an object at the time of creation, and it is also difficult to repurpose the object as it may involve very complex processing steps.

[0006] An instance of this problem is to take a halftoned image prepared for one printer, and process it such that when it is halftoned and printed on a second printer, the outputs of the two printers are visually as similar as possible. This problem is known as “descreening” or “inverse halftoning” in the literature.

[0007] A bi-level composite document containing both text and image areas, is comprised of a collection of individual pixels, each of which has only two values. These values could be “1” or a “0”, with “1” signifying black, such as a printed dot, and “0” signifying white. Currently, there is no satisfactory solution to repurposing this document for another printer. Some of the obstacles in solving this problem are as follows:

[0008] 1. Image and text areas need to be treated differently by a printer. Typically, image areas are halftoned with a repetitive screen, whereas text areas are not halftoned. The reason for this is that it is desirable for text to be printed with sharp edges.

[0009] 2. Due to the above mentioned dichotomy in text and image areas, a composite document containing both text and images needs to be segmented into regions containing only text and only images. This segmentation process needs to be done accurately.

[0010] 3. If a halftoned image prepared for one printer is printed on a second printer, there is a possibility of introducing Moire artifacts (interference fringes), which is a well known phenomenon. This shows up as an undesirable print quality problem.

[0011] In accordance with the method of the present invention, the first processing step is to segment a composite document into image and text areas. The text areas are left alone, to be combined at a later stage. The image areas are analyzed to determine their periodic screen frequency, and a smoothing filter is dynamically designed to eliminate the appearance of the screen (i.e. perform descreening). The descreened image is then re-halftoned while taking into consideration the characteristics of the second printer.

[0012] There are several potential uses for the method of the present invention:

[0013] 1. An original halftone prepared for one printer can be printed on another printer without loss of quality and the introduction of artifacts.

[0014] 2. This technique can also be used to perform image enhancement tasks. For instance, if the original halftoned image had poor contrast, we re-create an intermediate gray level representation, enhance the contrast, and then re-halftone the enhanced image. We can also add some random noise to improve the appearance of texture in the textured areas of the image.

[0015] FIG. 1 is a block diagram showing one example of an application of the present invention.

[0016] FIG. 2 is a flow chart of the overall method of the present invention.

[0017] FIG. 3 is a flow chart of the halftone-nonhalftone segmentation portion of the method of the present invention.

[0018] FIG. 4 is a plot of the distribution of gradient activity for text v. halftone regions of a binary image.

[0019] FIG. 5 is an illustration of data arrays for illustrating the shift and accumulate process of the present invention.

[0020] FIG. 6 is a plot of a typical sequence resulting from the shift and accumulate method of the present invention.

[0021] FIG. 7 is a block diagram illustrating the periodicity detection process of the present invention.

[0022] FIG. 8 is a plot of a Fourier power spectrum of the sequence of FIG. 6.

[0023] FIGS. 9 and 10 are pixel image maps for illustrating the method constructing an intermediate gray scale image of the present invention.

[0024] FIG. 11 is a pixel image map illustrating the rehalftoning method of the present invention.

[0025] FIG. 2 is a high-level description of the present invention. The input 201 to the system 200 is a bi-level image, containing one pixel per bit, where a “1” signifies that a dot is printed and a “0” signifies no dot is printed. The input image is first segmented 202 into halftone 204 and text 203 areas. The halftone areas 204 are then analyzed 205 to determine their periodicity. The periodic halftones are converted to an intermediate gray level representation 206 which is then re-halftoned 207. By re-halftoning, it means taking the gray level representation and halftoning it using well known techniques such as dither matrices or error-diffusion. The re-halftoned image areas are combined 208 with the non-periodic image areas and text areas to generate the final bi-level image 209.

[0026] Given a set of N labels L={l₁, l₂, . . . l_N}. the objective of segmentation is to assign a unique label l₁to every pixel in the image. In an illustrative embodiment two labels are used, l₁=1 meaning the pixel belongs to a halftone neighborhood and l₂=meaning the pixel belongs to a non-halftone neighborhood, which could be text or background. Thus the result of segmentation is a binary image where a pixel is assigned a label of “1” or “0”. The reason we wish to perform this segmentation is that text areas are better processed separately because text would lose its sharpness if halftoned.

[0027] Instead of making this assignment at every pixel in the original image, one can make it at every P^thpixel, where P is the sampling factor. For instance, the assignment can be made at every 10^thpixel, thereby reducing the number of computations significantly.

[0028] Thus, the result is an initial coarse segmentation, where a label is assigned to every P^thpixel. In order to extend the label assignment to every pixel in the original image, a clustering technique, described below is employed. (Note: P can be trivially set to 1, which results in the clustering step becoming redundant. However, this is computationally more expensive).

[0029] In accordance with the present invention, a segmentation technique based on gradient information is used. Prior art methods for segmentation use contrast information. However, the method using contrast is applicable only when the image is scanned as a gray-level image. This is because the contrast measure examines the difference in intensity values between the text characters and the background, which will be high. It is not likely that such high contrast exists in the image areas. However, the present problem is different as there is a bi-level image: the difference in intensity between text characters and the background can be either 1 or −1, and this value can just as well occur in the image areas. Thus contrast will not provide a mechanism to segment the image. Hence, the gradient-based technique of the present invention is needed.

[0030] FIG. 3 describes the procedure used to segment the halftone areas from the text areas from an original image 301. The segmentation is facilitated by the observation that halftone areas contain more transitions between black and white values than text areas. Since gradients 302 measure transitions, a simple measure to consider is the gradient activity per unit area 303. This measure is defined as follows. Let I denote the bi-level image, having U rows and V columns. Let I(i,j) represent the image intensity of a pixel at spatial coordinate (i,j) where i and j are the indices along the x and y directions. Since I is bi-level, I(i,j) is either 0 or 1. The image gradient at a pixel with spatial coordinates (i,j) is a two dimensional vector G(i,j) having x and y components G_x(i,j) and G_y(i,j) respectively.

[0031] G_x(i,j) is defined by

[0032] G_x(i,j)=I(i+1,j)−I(i−1,j)

[0033] and G_yis defined by

[0034] G_y(i−j)=I(i,j+1)−I(i,j−1)

[0035] The gradient magnitude ∥G(i,j)∥ at pixel (i,j) is

[0036] ∥G(i,j)∥={square root over ( )}[G_y²(i,j)+G_y²(i,j)]

[0037] The gradient activity per unit area is defined as $\stackrel{\_}{G\left(i,j\right)}=\left\{\frac{\sum _{k=1}^{k=M}\sum _{l=1}^{l=N}\Vert G\left(k,1\right)\Vert }{\mathrm{MN}}\right\}$

[0038] where the sums are calculated over a rectangular window of size M×N pixels such that pixel (i,j) is at the center of the this area. The shape of the window is not important, and any other window shape could have been chosen such as circular.

[0039] Instead of the gradient magnitude ∥G∥, one could also use the sum of the absolute values of the x and y gradients |G_x|+|G_y|, or simply a Boolean variable B, defined as follows: $B=\begin{array}{c}1\mathrm{if}{G}_x\ne 0\mathrm{or}{G}_y\ne 0\\ 0\mathrm{if}{G}_x=0\mathrm{and}{G}_y=0\end{array}$

[0040] These alternate measures of gradient activity are approximations to the gradient norm, which lend themselves to fast implementation as we do not have to compute the square root of the sums of squares. The preferred embodiment uses the Boolean variable B as a measure of gradient activity. It is expected that the gradient activity per unit area 303 will be high in halftone areas and low in the text areas. This observation is born out in practice as shown in FIG. 4, which is a plot of the distribution of gradient activity for text vs. halftone areas. The plots are histograms of non-zero gradient magnitude for text and halftone areas. A window size of 25×25 was used to calculate the gradient activity per unit area. FIG. 4 shows that the distribution of gradient activity for text 401 and halftone 402 regions are clearly different, and it is virtually impossible to find text regions which have a gradient activity of more than 50%. Whereas, there are a significant number of halftone pixels which have a gradient activity of more than 50%.

[0041] Thus, a simple rule to segment text from image halftone areas is:

[0042] If gradient-activity>gradient-threshold

[0043] pixel is image halftone

[0044] else

[0045] pixel is text

[0046] In the preferred embodiment, the size of the window used is M=25, N=25. These are adjustable parameters. The gradient threshold employed in the above rule is 50%, and is also adjustable. Note that the performance of the algorithm is not crucially dependent on the choice of this threshold. Any percentage that is reasonably high will do.

[0047] In the preferred embodiment a segmentation decision is made every K=15^thpixel. Note that the choice of K is not crucial, and any value of K>1 will generate computational savings.

[0048] The result of performing the clustering operation is a completely segmented image, where every pixel of the original image is assigned a “1” if it belongs to a halftone area or a “0” if it belongs to a text area.

[0049] The preferred clustering technique results in rectangular bounding boxes being drawn around the image areas 305, which are the results of the initial segmentation. It is assumed that the halftone image areas 305 are rectangular in shape, which is usually true. However, other circumscribing boundaries can be used, such as convex hulls (to be found in R. Sedgewick, Algorithms. Addison Wesley, 1983, London).

[0050] The well known union-find algorithm is used in order to perform clustering 306 (to be found in R. Sedgewich, Algorithms. Addison Wesley, 1983, London). The algorithm takes as input a set of points in a graph, and connects each pair of points that satisfy some clustering criterion. In the present case, two points are said to belong to the same cluster if they are less than some minimum distance apart. For instance, one can set the clustering criterion to be 100 pixels, so that any two points will belong to the same cluster if and only if they are within 100 pixels of each other.

[0051] The distance measure used is the city-block distance due to its computational efficiency. Other distance measures could be used such as Euclidean distance measure, but these involve more computations. The city-block distance, D, between two pixels located at (i,j) and (m,n) is defined as

[0052] D(i,j,m,n)=|i−m|+|j−n|

[0053] Each cluster found is assigned a rectangular bounding box 307 where the bounding box is defined to be the smallest rectangle that contains all the points in the cluster. The first round of clustering operations results in a set of bounding boxes that may overlap each other. The reason for the overlap is that the original clustering criterion uses the distance between pixels, and not distance between bounding boxes.

[0054] Hence we perform a second round of clustering 308, where two bounding boxes are merged if they overlap. The final result of these two clustering operations is a set of bounding boxes 309, where every pixel inside a given bounding box belongs to a halftone area, and every pixel outside the bounding box belongs to a non-halftone area, such as text.

[0055] It is noted that an alternate approach would be to perform binary connected component analysis (as described in D. H. Ballard and C. M. Brown, Computer Vision. Prentice Hall, 1982) on the initially segmented image, and then perform a single clustering operation. In the illustrative embodiment described herein, a clustering operation is performed instead of a binary connected component analysis as clustering is computationally more efficient.

[0056] Now that the original bi-level image is segmented into halftone and non-halftone areas, the method proceeds to re-halftone areas as follows.

[0057] A distinction is made between two types of halftones: those that contain screens, such as a 45° screen used in printing gray scale images, and those that do not contain screens, such as those created by error diffusion techniques. The re-halftoning of screened halftones is more problematic as there is a danger that Moire patterns may be introduced if the frequency of the re-halftoning process does not match the original screen frequency. However, such a danger does not exist in the case of screenless halftones such as those created by error diffusion. Hence, we focus most of our attention on detecting the presence of a screened halftone, and identifying the periodicity of the halftone.

[0058] Several methods for detecting periodicity were investigated such as autocorrelation and using “exclusive-or” operations. The autocorrelation method can be used but is not favored as it is computationally expensive, involving the shifting, multiplying and summing of a sequence with itself. Also, several rows or columns need to be analyzed since it is quite possible that a single row or column may not exhibit an easily detectable periodicity. A related method is to substitute the exclusive-or operation for the multiplication and summing operations, and to count the number of zero bytes instead of the number of bits. Counting by bytes is faster. However, this method is still computationally expensive compared to the preferred method described below, which is called “shift and accumulate”.

[0059] This method is illustrated in FIG. 5. The procedure will be described for detecting periodicity in the horizontal direction, across columns, without loss of generality. The procedure is the same for the vertical direction, along rows. The starting point is an accumulator array 507, which is initialized 503 to the first row 5011. The second row 5012 is shifted by one pixel to the left and added to the accumulator. The third row 5013 is shifted two pixels to the left and added to the accumulator, and so on. By the time the entire image is traversed, the accumulator array 507 contains the accumulated sum of shifted projections. This accumulated array is a one dimensional representation of the entire image, which amplifies any periodicity present in the original image. Periodic components reinforce each other in the final accumulated sum. FIG. 6 is a plot of a typical sequence resulting from the operation of the shift and accumulate method. The original sequence contained 1984 points, out of which the first 128 points are plotted for the sake of clarity. Note the strongly periodic nature of the plot.

[0060] Note that the shift-and-accumulate method of the present invention works best with a 45° halftone screen. However, it can be easily adapted to other screen angles by shifting every M^throw by N pixels such that the screen angle equals tan⁻¹(N/M).

[0061] The constructing method of a gray scale representation includes utilizing the estimate of the primary periodicity to construct a gray scale image that does not contain periodic content at the periodicity of the estimate of the primary periodicity.

[0062] The construction of a gray scale image further includes creating a filter with a spectral zero at the frequency corresponding to the estimate of the primary periodicity and applying the filter to the pixels in the halftone areas.

[0063] FIG. 7 shows the subsequent stages of processing the image to detect periodicity. The input image 701 is processed by the shift and accumulate method 702 and the cumulative sum is calculated at 703.

[0064] The accumulated sum is denoted by a sequence s. In the language of time series analysis (as described in W. Vandaele, Applied time series and Box-Jenkins models. New York: Academic Press, 1983), s typically contains trends which may mask the periodicity that we wish to isolate. Thus a first order differencing operation is performed at 704 as customary in time series analysis to remove trends. This results in a new sequence s₂where the i^thelement of s₂is

[0065] s₂(i)=s(i+1)−s(i)

[0066] In other words, the method differentiates the original sequence s. In order to suppress the well documented noise amplification characteristics of the differentiation operator (as described in A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, V. H. Winston & Sons, 1977), first s is smoothed by a Gaussian filter with a small kernel size, such as size 5. In the preferred embodiment the coefficients used are {1, 64, 256, 64, 1}, however, any set of smoothing coefficients can be used.

[0067] The next step is to take the Fourier Transform of s₂using an FFT implementation at 705 (such as the one described in W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press 1988.) In the following equation S₂represents the FFT of the sequence s₂, and S_2nrepresents the n^thelement of the FFT. $S_{2n}=\sum _{k=0}^{k=N-1}{S}_{2\mathrm{ke}}^{2\Pi \mathrm{ikn}/N}$

[0068] where N is the length of the sequence. Thus the original sequence is mapped into a set of complex numbers according to the above equation. The power spectrum P is defined to be a sequence of length N where the k^thelement is

[0069] P_k=S_2k×S*_2k

[0070] where the * operation denotes complex conjugation. The power spectrum calculated at 706 depicts the distribution of spectral energy content at different frequencies. In the time series literature, the power spectrum is also known as the periodogram (as described in W. Vandaele, Applied time series and Box-Jenkins models. New York: Academic Press, 1983). At decision block 707 a determination is made if there is a highly peaked distribution. In doing this, the dominant peak in the power spectrum is identified easily as the maximum value in the sequence P. In order to test for periodicity, the height of the second peak is calculated and the ratio between the first and second peaks is found. If the ratio is high, for example>3, the original sequence is deemed to be periodic, and the period is determined by the location of the first peak at 708. If the ratio is low, it means the spectral energy is distributed more or less equally, implying the original sequence is aperiodic or in other words does not contain dominant periodic function at 709. Other tests of periodicity are possible, and may be used just as well (as described in L. G. Tatum, “Control charts for the detection of a periodic component,” Technometrics, no. 2, pp. 152-60, May 1996).

[0071] FIG. 8 shows the output of the periodicity detector of the present invention. The Fourier power spectrum is shown of the sequence of FIG. 6 after smoothing and first order differencing.

[0072] It is also possible to perform a two dimensional Fast Fourier Transform (FFT) across the whole image. But the image size can be large (e.g. 6000×6000 pixels), and the computation of the 2D FFT is much more expensive than the above computation of the first order differencing.

[0073] Taking the horizontal and vertical periodicity detected in the previous step, the next step is to create an M×N smoothing box filter, where M is half the vertical period and N the horizontal period. In another embodiment, an M×N smoothing box filter is used where M is equal to the vertical period and N is equal to the horizontal period. This smoothing filter is moved across the input image (each of the areas of the original image that is deemed to be a periodic halftone area) to generate an intermediate gray level image. The center of the M×N box is assigned the smoothed value. This process is illustrated in FIGS. 9 and 10.

[0074] FIG. 9 shows an example when the smoothing filter is contained entirely within the input image. Both images 900A and 900B represent the original bi-level input image, with each of the square areas 902 representing individual pixels each having an image value. In this example, the box filter is a 3×6 pixel filter. For illustrative purposes, the image is only a 8×8 image, but it is well known that actual images will have many more pixels, such as 1024×1024. FIG. 9 shows how groups of 3×6 pixels are averaged to form a single value for a pixel in the intermediate gray level image 903. In image 900A, group 904 are averaged and the averaged value is assigned to pixel 905 in image 903. The box filter is shifted one pixel as shown in image 900B and the average value of group 901 is assigned to pixel 906 in image 903. The box filter is shifted until all 64 pixels in image 903 are assigned values. In order to fill all the pixels of the intermediate gray scale image, the box filter will sometimes lie only partially within the input image. FIG. 10 is an example of this case. Box filter 907 only covers three pixels of input image 900C. The value for pixel 908 of image 903 is computed by taking the sum of the image values inside the averaging block 907 and scale by the fraction of the image area that falls in the averaging block.

[0075] In the preferred embodiment, all the coefficients within the M×N box filter are set to “1”. However, other assignments are also possible, such as a Gaussian kernel. Any set of filter coefficients that is low-pass will perform comparably.

[0076] It is important to note that the intermediate gray level image does not contain any halftone screen since the periodic information of the screen is used to design the appropriate descreening filter.

[0077] This intermediate gray level image is then rehalftoned using any desired halftone technique. For instance, one can use a dither matrix as illustrated in FIG. 11.

[0078] FIG. 11 illustrates the process of halftoning by using a dither mask.

[0079] The dither mask 1103, is of size M×N where M, the number of rows, is half the vertical repetition period and N, the number of columns, is the horizontal repetition period.

[0080] The input gray level image 1104 is shown to be of size 8×16 though other sizes can just as well occur.

[0081] The pixel of the gray level image at location 1101 is compared with the corresponding dither mask pixel, and in this case, happens to be greater than the dither mask pixel. Hence, a “1” is placed at location 1105 in the output re-halftoned image. Location 1105 in the output re-halftoned image is the same as location 1101 in the input gray level image.

[0082] Similarly, the pixel of the gray level image at location 1102 is compared with the corresponding dither mask pixel, and in this case, happens to be less than the dither mask pixel. Hence, a “0” is placed at location 1106 in the output re-halftoned image. Location 1106 in the output re-halftoned image is the same as location 1102 in the input gray level image.

[0083] The dither mask 1003 is shifted by N pixels in the horizontal direction, and the entire comparison process is repeated till the boundary of the gray level image is reached.

[0084] Then the dither mask 1003 is moved down by M pixels and over by N/2 pixels, and the above procedure is repeated. A circular overlap of the dither matrix is assumed to ensure that the entire input image is processed.

[0085] The important point to note is that since the intermediate gray level image has been properly generated, there are no Moire patterns during the rehalftoning process.

[0086] During this rehalftoning process, use can be made of the printer characterization parameters of the second printer in order to make the printer halftoned image match the output of the first printer. This is how similarity is achieved between the two printed outputs.

[0087] During the rehalftoning process, one can use a calibrated dither matrix to ensure accurate tonal reproduction. Any halftone process can be used at this stage, such as dither matrices of smaller size (which generate finer line screens), or error diffusion.

[0088] In addition, one can employ image enhancement techniques such as sharpening and contrast improvement on the intermediate gray level image, prior to rehalftoning.

[0089] Finally, the rehalftoned areas are combined with the areas that were not processed (i.e. non-halftone areas such as text) in order to generate a complex image.

[0090] The method may be implemented in any means and manner to provide the concepts and advantages of the invention. This includes implementation as a computer program product, and a program storage device readable by machine.

[0091] While the invention has been particularly shown and described with respect to a preferred embodiment thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention.