Abstract:
A digital halftoning device for converting digitized contoned image data representing an input image into a halftoned image to be displayed in a visually discernible manner comprising: dividing a digitized contoned image data into a plurality of contoned macrocells at predetermined, integrally spaced locations; determining the optical density of each of the macrocells; converting the contoned macropixels to their halftoned representation, including: comparing the optical density of the macrocells against a predetermined threshold; and suppressing chosen macropixels on integer centers in regions of the image where the threshold code value is exceeded; converting the macropixel pattern into a micropixel image pattern; and outputting the micropixel image pattern to be displayed in a visually discernible manner. The result is the creation of a superpixel in areas of high optical density to create a greater number of gray levels at the expense of spatial resolution.

Description:
FIELD OF THE INVENTION 
     The invention relates generally to the field of digital halftoning, and in particular to representing images having high optical densities with halftone images employing multiple resolutions. 
     BACKGROUND OF THE INVENTION 
     A problem that exists in halftone imaging is that there is a tradeoff between the number of addressable gray levels (contrast resolution) and the image sharpness (spatial resolution). 
     A halftone screener of the tiling type creates images by arranging halftone dots in a repeating regular pattern, similar to laying tiles on a floor. Each tile contains a halftone dot whose black area coverage will produce an effective density when viewed with the naked eye. 
     If a tile is divided into N equal area micropixels, the maximum number of gray levels possible in a binary halftone (2 halftone states) is equal to N+1. Given that there is a practical limit to how small one can make a micropixel, the only remaining way to increase N is to increase the area of the tile. However, increasing the area of the tile reduces the spacial resolution that the screener is capable of reproducing. 
     In halftone imaging, problems exist in images having high optical densities. The spacing of printed density levels becomes sparse and densities in the source image cannot be reproduced accurately, leading to the production of image artifacts such as contours. This problem has typically been solved in the case of digital halftones by using many tiny micropixels to make up the halftone dot or macropixel. However, this strategy is limited by the degree to which very small, very closely spaced micropixels can be produced. Therefore, a problem in the halftone imaging is that there is a tradeoff between the number of addressable gray levels (contrast resolution) and the image sharpness (spatial resolution). 
     Raster image processing algorithms which convert digital continuous tone images to digital halftones fall into at least two families, tiliers and samplers. Within these families there are subcategories such as dither dot, cluster dot, error diffusion, etc. Tiliers have only 1 screen pattern, usually oriented at zero or 90 degrees to the viewing direction. Sampling screeners may have several different screens, particularly in color systems and the screens are at different angles to the viewing direction and to each other. Many of the prior art references refer to screeners in the sampling family. Many of them are involved with cures for the problem of image Moire, which does not occur in tiling screeners. 
     As can be seen from the foregoing description, there remains a need in the art for a halftone imager that can more adequately represent areas of high optical densities. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to overcoming one or more of the problems set forth above. At high optical densities, loss of image sharpness (resolution) is less visible to the human eye. Thus one way to increase the number of gray levels in a halftone imaging system is to have a lower resolution in areas having high optical densities than those areas having optical densities below a predetermined threshold. The tiling screener of the present invention converts a digitized continuous tone image to a digital halftone image where the resolution in areas having high optical densities above a threshold D th , where the sharpness loss would not be noticeable, is reduced in order to increase the number of gray levels. 
     Briefly summarized, according to one aspect of the present invention, a method for generating a digital halftone images comprises providing a digitized version of an analog image; dividing the digitized image into a series of macropixel elements; representing, separately, the light and dark area of the macropixel; generating reference coordinates that represent a center of a macropixel; determining a difference value that represents the difference between macropixel centers; and adjusting the difference as a function of density as determined by the contone value of the macropixel 
     The above and other objects of the present invention will become more apparent when taken in conjunction with the following description and drawings wherein identical reference numerals have been used, where possible, to designate identical elements that are common to the figures. 
     ADVANTAGEOUS EFFECT OF THE INVENTION 
     The multiresolution halftone tilier balances the screening process so that more gray levels are available at high densities where they are needed, without using exceedingly small micropixels to get the required area coverage. Large macropixels are used where the loss of resolution will not be noticeable and small macropixels are used at low optical densities where high resolution is needed and there is no shortage of available gray levels. This should allow the construction of dry laser printers for medical images with less precise and costly optical systems and mechanical systems that would be otherwise needed since larger, less precisely controlled optical beams can be used. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a system as envisioned by the preferred embodiment of the present invention; 
     FIG. 2 is diagram illustrating macrocells; 
     FIG. 3 is a diagram showing a digital halftone macropixel that comprises many micropixels in relation to a digital source image; 
     FIG. 4 is a flow chart illustrating the steps used to perform the halftoning algorithm of the present invention; 
     FIG. 5a is an illustration of an analog image to be represented by the halftoned image of the present invention; 
     FIG. 5b is an illustration of the digitized version of the analog image of FIG. 1 that is to be represented by the halftoned image of the present invention; 
     FIG. 5c is an illustration of a prior art halftoned image of the digitized FIG. 6b; and 
     FIG. 5d is an illustration of the halftoned image of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     It is been discovered, within the art of digital halftoning, that areas having high optical densities can be represented with a lower resolution. At high optical densities, loss of image sharpness (resolution) is less visible to the human eye. Thus one way to increase the number of gray levels in a halftone imaging system is to have a lower resolution in areas having high optical densities than those areas having optical densities below a predetermined threshold. 
     Referring to FIG. 1, which is a system block diagram as envisioned by the present invention. Computer 10 has an interface 12 with a Halftone Image Processor 14 (HIP). In the preferred embodiment, image source 22 is an X-ray device that is capable of generating a digital image to be used by HIP 14. In this type of embodiment, interface 12 is a workstation interface. The preferred interface would place the HIP 14 on a PCI bus with an IBM compatible computer. The HIP within the preferred embodiment is based on Application Specific Integrated Circuits (ASICs), however, it is also envisioned that the algorithms run by the HIP 14 could be done on a general purpose computer. Placing the processing functions of the HIP within hardware results in a faster system. The HIP 14 is capable of performing halftone image algorithms upon image data that is received from interface 12. The image data received is a digitized version of a contone image received from image source 22. The computer 10 takes the contone image data and divides it into a series of elements that each have a code value which indicates the density of that macropixel. In the preferred embodiment, the image source 10 is a conventional X-ray device capable of creating the digital contone image having macropixel elements with their associated code values. This digital contone image is received by the interface 12 which performs page make up interface, and makes up page and general processing. It is also envisioned that an analog image could be generated from an image source 12, in which event the interface 12 would also have to perform the aforementioned functions of creating a digital contone image having macropixel elements with their associated code values. 
     The HIP 14 performs the tiling screener function of the present invention by converting the digitized continuous tone image to a digital halftone image wherein the resolution in areas having high optical densities above a threshold D th . (where the sharpness loss would not be noticeable) is reduced in order to increase the number of gray levels. The problems associated in areas having high optical, densities and the tradeoffs that occur between the number of addressable gray levels (contrast resolution) and the image sharpness (spatial resolution) are solved by the present inventions provision of increased gray areas in the areas of higher optical density. 
     Referring to FIG. 2 in conjunction with FIG. 3, consider a halftone screener which &#34;tiles&#34; images&#34; by arranging macrocells 24 with halftone dots 26 in a repeating regular pattern like a tiled floor. Each macrocell 24 contains a halftone dot 26 whose black area coverage that will produce an effective density when viewed at a distance. This is illustrated by FIG. 2 with Δx and Δy representing the horizontal and vertical spacing of the macropixels. The effective density being given by the Murray-Davies equation as shown in Equation 1 below. 
     
         D.sub.i =D.sub.min -log.sub.10 (1-a.sub.i (1-10.sup.-(Dmax-Dmin)))Equation1 
    
     where D max  and D min , are the maximum and minimum densities in the tile. 
     Referring to FIG. 3, if a macrocell 24 is divided into N equal area micropixels 25, the maximum number of gray levels possible in a binary halftone is then equal to N+1. Given that there is a limit to how small one make a micropixel, the only way to increase the area the number of gray levels is to increase the area of the tile. However, increasing the area of the tile reduces the spatial resolution that the screener is capable of reproducing. The maximum unambiguous spatial frequency (Nyquist frequency) is illustrated in Equations 2a and 2b. 
     
         f.sub.nx =1/2Δx                                      Equation 2a 
    
     
         f.sub.ny =1/2Δy                                      Equation 2b 
    
     where Δx and Δy are, respectively, the x and y dimensions of the macropixel having an area, A, as indicated by Equation 3 below. 
     
         A=ΔxΔy                                         Equation 3 
    
     The relationship shown by Equations 2 and 3 is illustrated in FIG. 3. 
     The following is a brief mathematical representation of the algorithm of the invention. From the well known Murray-Davies halftoning equation, a formula for the area coverage, a c , of a halftone macropixel cell 10 (which is one tile in the invention) can be derived. The area coverage is the fraction of the macropixel 10 which is black. In Equation 4, D is the desired optical density, D s  is the density of the film support without any light absorber, and D d  is the density of the unexposed light absorbing layer. ##EQU1## 
     The fraction of the macropixel which is white is 1-a c . If we build the macropixel out of N d  equal area micropixels we may define a number n dots  which is the number of white dots needed to produce a density D by the relationship shown in Equation 5. 
     
         n.sub.dots =(1-a.sub.c).N.sub.d                            Equation 5 
    
     Typical prior art devices only contain N d  =N micropixels per macropixel. The present invention forms a superpixel containing N d  =M 2  *N micropixels by merging together M 2  macropixels. This increases contrast resolution (M 2  more micropixels to change) at a cost in spatial resolution (sharpness) due to 1/M fewer macropixels per unit length. Therefore, we make this change at high optical densities where the sensitivity of the eye to detail has decreased to the point that the loss of sharpness is not discernible, i.e. at densities D&gt;D threshold . 
     This process performed by the present invention is illustrated in FIG. 4 which is a flowchart of the steps performed by the system of FIG. 1 as envisioned by the present invention. Initially, Determine Density 30 determines the density of the macropixel from the version of the Murray-Davies discussed for Equation 1. The step of Determine Area Coverage 31 performs the calculation of a c  from the Equation 4 derivation of the Murray-Davies equation as discussed above. The density value determined from the Determine Density 30 step is then compared with the predetermined threshold value for density, D threshold . A code density value, where the code value represents a distinct density chosen from a predetermined density code value function, is performed. Set m=M, generally referred to as 32a, is performed if the density value for that macropixel exceeds the D threshold  value. Otherwise, if the density value for that macropixel is not exceeded then m=1, generally referred to as 32b, is performed. Following the calculation of m, Calculate N dots  33 is performed. The determination of the value of N dots  is used direct the step of Retrieve Dot Pattern From Font Memory 34 to the correct area of font memory to retrieve the dot pattern that will be placed on the output bus and displayed. The Increment Macropixel 35 position is performed and the process is repeated. 
     Referring to FIG. 5a through FIG. 5d, which are illustrations an analog image in FIG. 5a having a high optical density area 41 having a density greater than D threshold  and a low optical density area 42 that is less than D threshold . FIG. 5b is an illustration of the digitized version of the analog input image of FIG. 5a with the high optical density area that has exceeded D threshold , shown as a plurality of discrete areas, each labeled A, and the area that has not exceeded D threshold  shown as a plurality of discrete areas, each labeled B. FIG. 5c shows as prior art halftoned image of FIG. 5b. FIG. 5d is the halftoned output image of FIG. 5b according to the present invention. We may express the formation of this supercell, shown in FIG. 5d, mathematically in the following way. If x n  and y n  are the co-ordinates of the center of the nth macropixel, and macropixels are ordinarily spaced Δ apart we may express the co-ordinates of the n+1 macropixel by the relationship shown in Equation 10 
     
         x.sub.n+1 =x.sub.n +Δ and y.sub.n+1 =y.sub.n +ΔEquation 10 
    
     In accordance with the present invention, the spacing relationship is altered in area having a high optical density greater than a threshold value, D threshold . Expressed mathematically we change the two previous equations to the relation shown by Equation 11. 
     
         x.sub.n+1 =x.sub.n +m*Δ and y.sub.n+1 =y.sub.n +m*ΔEquation 11 
    
     where m is an integer dependent upon the density. 
     For values of D equal to or greater than D threshold , m is greater than 1 and has a value of M=2 in the case illustrated in the drawings. This would yield a superpixel having m 2 , or 4, times as many micropixels per pixel. By still increasing the integer amount, M, even larger superpixels are obtainable, yielding still greater amounts of gray levels. 
     For D&lt;D threshold , M is 1.0 and the halftoning proceeds as given by Equation 1.0, retaining spacial resolution in areas having lower optical densities where the spacial resolution is discernible. 
     The preferred embodiment discussed hereinabove, employs a digitizer to the analog image data seen in FIG. 5b. Once the digitized data is divided into macrocells, a comparison is then performed on each macrocell to determine if that macrocell exceeds the predetermined threshold. This digital approach is preferred because of the relative sophistication in modern digital electronics. Moreover, once digitized, the macrocells have been clearly identified and no additional analog circuitry is required for the task of identifying each macrocell with its respective threshold levels. 
     However, the present invention envisions that the analog image shown in FIG. 5a having higher optical density areas 41 and lower optical density areas 42, may have the relative optical density of these areas determined in various ways. A comparison of the image data may be accomplished using analog devices, at the front end of the system. Here, a comparison may done with the input data to give an indication of whether the image data exceeds a predetermined threshold. The result of this comparison is fed into a digital computer. It should be understood by those skilled in the art that care must be taken to insure that the results of this comparison is fed into the computer synchronized with the image data that it represents a comparison for. Additionally, accuracy in analog systems can not be as easily controlled as digital systems. Therefore, using an analog comparison is not preferred though certainly possible as those skilled in the art are aware. 
     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. 
     Parts list 
     
         ______________________________________Parts List:______________________________________   10   computer   12   input   14   halftoning image processor   16   font memory   18   output   22   image source   24   Macropixel   25   micropixel   26   Halftone dot   30   Determine Density Step   31   Determine area coverage, a.sub.c   32a  Set m = M   32b  Set m = 1   33   Calculate N.sub.dots = m.sup.2 N   34   place dot pattern   35   Increment position   41   high optical density   42   low optical density______________________________________