WO1999045697A1

WO1999045697A1 - Halftoning with pre-computed maps

Info

Publication number: WO1999045697A1
Application number: PCT/SE1999/000282
Authority: WO
Inventors: Fredrik Nilsson; Björn KRUSE
Original assignee: Forskarpatent I Linköping Ab
Priority date: 1998-03-05
Filing date: 1999-03-01
Publication date: 1999-09-10
Also published as: EP1066716A1; SE9800686L; SE513365C2; SE9800686D0

Abstract

Halftoning method based on the use of pre-computed maps, one for each possible tone value in the image, at halftoning the image value at a specific position gives the map from which a pixel is copied into the halftone at the corresponding position. The maps with low or high densities have maximally spread minority dots but in intermediate maps a successive transition takes place from maximally spread dots to structured dot clusters of defined type for instance straight lines.

Description

1 Halftoning with Pre-Computed Maps

1. Background

Halftoning methods based on threshold matrices are very attractive in terms of speed. Moreover, full control over the patterns produced in tints is possible and thus certain less visually pleasant patterns can be avoided. For these methods, however, there is always a trade-off between the quality in the tints produced and the quality of smoothly varying shades. Thus, the principle of the threshold matrix approach does not allow for the highest possible quality in both. The reason for this is that the dot pattern produced for a certain tone value will be present in all tints of less intensity. A pattern at one intensity level will thus restrict the appearance of all other tint values. This means that if there is a certain criterion for optimization of a tint, for instance requiring that the dots are as dispersed as possible, this can not be fulfilled for all tint levels. This restriction is illustrated in Figure 1.

We have developed a halftoning method that abandon the constraint of threshold matrix methods without any loss of speed. All tints produced have been individually designed and can thus have any desired property. The tints will therefore generally be less grainy than tints produced with a threshold matrix method and hence visually pleasant for both bright and dark tint values. Furthermore, the proposed design strategy allows for smooth transitions in halftoning of shades without any sudden structural changes. High quality in both tints and smoothly varying shades is thus possible.

The basic method has been described in the Swedish patent application 9504016-8. However the designing of the maps used is not trivial and the invention therefor has as its object to provide suitable maps and a method to make suitable maps.

The object of the invention is solved as is defined in the claims.

The invention will below be described with reference to the drawings:

Figure 1 An illustration of threshold-matrix-based halftoning techniques. A black micro 2 dot is placed at every image position where the value of the threshold matrix is greater than the image value. Thus, the dots produced for one tint value will be present in all darker tint values. This is a severe restriction when designing the tints possible to produce with the matrix.

2 Figure 2 Halftoning with the Pre-Computed Maps technique described in text. Maps describing the dot patterns for every possible image value (256 in the illustration) are stored in a halftoning volume. When halftoning, the image value is used as an index in the volume to point out the appropriate map. The value of the map is then copied into the halftone at the corresponding position.

Figure 3a - 3c Examples from the generation of maps. 3a) is a white noise image thresholded to get 20% minority pixels. The resulting pattern is used as the starting pattern. In 3b), the starting pattern is rearranged to get maximally dispersed dots. This map is stored in the halftoning volume. In 3c), extra dots have been added to the dot pattern in 3b) to get the initial map for the next level (25% level in the example). The pattern is rearranged before stored in the volume, 3d). Note that some of the dots in 3b) have been moved to obtain the pattern in 3d). This would not have been possible with a threshold-based-method.

Figure 4a - 4c The test images halftoned with the Pre-Computed Maps method described in text. The tints and ramps are in 100 dpi, the photograph in 150 dpi. The halftoning volume used is optimized with isotropic Gaussian low pass filters. The maps in the volume are of the order 64x64.

Figure 5 Some of the kernels used to compute maps with line like micro structures. The kernels gradually change from a Gaussian low-pass filter for maps with fewer than 30% minority dots to a directional band-pass filter. The size of the kernels are 9x9 but have been interpolated to 36x36 for illustration purposes

Figure 6a - 6c The test image halftoned with the Pre-Computed Maps method. The tints and ramps are in 100 dpi, the photograph in 150 dpi. The halftoning volume which is used is optimized with directed Gaussian low pass filters for mid gray maps. The maps in the 3 volume are of the order 64x64.

Figure 7 Some of the kernels used to compute maps with curved micro structures. The kernels gradually change from a Gaussian low-pass filter for maps with fewer than 30% minority dots to an isotropic band-pass filter. The size of the kernels are 9x9 but have been interpolated to 36x36 for the purpose of illustration.

Figure 8a - 8c The test images are halftoned with the Pre-Computed Maps method. The tints and ramps are printed in 100 dpi, the photograph in 150 dpi. The halftoning volume is optimized with isotropic band-pass filters for mid gray tints. The maps in the volume are of the order 64x64.

2. The Pre-Computed Maps technique

Instead of using a threshold matrix and a comparison technique to produce the halftones, the proposed method uses one pre-computed halftoning map for each possible tone value in the image. Each map is derived according to a specific optimization criterion and stored in a halftoning volume. The maps contain only zeros and ones, representing the presence and absence of a halftone dot respectively. When halftoning an image, the image value is used as an index into the volume. The position in the chosen map is derived from to the image position in the same manner as for matrix-based-methods. The value of the map at this position is then simply copied into the corresponding position in the resulting halftone. Thus, no comparison is necessary when halftoning. Figure 2 illustrates halftoning with the Pre- Computed Maps (PreCoM) technique.

Like threshold-based-methods, PreCoM is easily implemented in a truly parallel manner since no information from neighbouring pixels is required. However, the technique requires more memory than threshold matrix methods. For instance, given the task of halftoning an image with 256 gray levels (8 bits), the PreCoM method requires 256 one-bit maps whereas a threshold-matrix-based method requires one eight-bits matrix. If the same matrix and map size is used, PreCoM thus requires 32 times as much memory. As an example, assuming a map size of 64x64 pixels, the storage of the halftoning volume will require 128 kilobytes compared with the 4 kilobytes for the threshold matrix. 4

While PreCoM allows full control of the dot patterns for each tone value, severe discontinuity effects will be introduced when halftoning slowly varying shades if the maps in the volume are computed in isolation. Thus, adjacent maps in the volume must be correlated, i.e. exhibit similar dot patterns. The design of the maps must be done with this in mind. There is, however, no reason why the dot pattern of one gray level should be restricted by the dot pattern at a level far from it. This implies that this limitation will not be as severe as for threshold matrix based methods. The computation of the maps and the process of correlating adjacent maps is described in the next sections.

3. Computing the maps

The maps in the halftoning volume are derived individually in an iterative manner. The principles of the computation process are shared by all maps. However, by assigning a specific optimization criterion to each map, all maps can be given a specific characteristic. A variety of optimization criteria are possible, but for the production of visually pleasant halftones only some are of interest. One such criterion is to force the dots in a map to be as dispersed as possible which will minimize disturbing patterns as well as graininess in the halftoned images. In fact, maps optimized with this criterion will posses the desirable blue noise characteristics. The suggested optimization algorithm is closely related to the void and cluster method presented in [Ulic93] . The principle of the algorithm has also been used when deriving the Blue Noise Mask [YaPa94]. For the sake of completeness, the algorithm in its entirety is described below.

The computation of a map starts from any binary pattern with the appropriate ratio of white to black dots (ones and zeros), for instance a thresholded white noise image. The idea of the algorithm is to rearrange the minority dots, i.e. black dots for bright tint values and white ones for dark values, until they are as dispersed as possible. This is done in a iterative manner by successively moving minority dots from the tightest clusters to the largest voids. By representing the minority dots with ones and the majority dots with zeros, the tightest cluster of minority dots is located by finding the maximum of the low-pass filtered dot pattern. The minority dot at the maximum is removed and the low-pass image is updated by a local deconvolution, i.e. the low-pass kernel is subtracted from the low-pass image at that position. In a similar manner, the largest void is found by locating the minimum of the low- 5 pass image. The previously removed dot is then placed at this location and the low-pass image is again updated, now by adding the kernel. The process of rearranging minority dots continues until no further change occurs, i.e. the selected minority dot is placed at the very same location it was taken from. The algorithm is straightforward, but there are several factors which must be taken into consideration in order to ensure that the resulting maps behaves well. The two most important of these are discussed below.

Since the image size in general is much larger than the map size, the maps has to be tiled for complete coverage when halftoning the image. If this is not taken into account when computing the maps, disturbing artefacts will be introduced at the borders of the maps. A straightforward solution is to use circular convolution when low-pass filtering the dot pattern. This means that the influence from one dot is allowed to spread over the map edge into the opposite side of the map. Thus, each generated map can be tiled without introducing any discontinuity effects at the borders of the map.

The characteristics of the low-pass kernel used in the algorithm has great influence on the final dot pattern. Its shape as well as its size is of importance and should be adapted to the current density level. For instance, in bright and dark maps, the distances between the minority dots will be large. Thus, a wide kernel should be used to avoid unevenly spread dots. On the other hand, for maps of around 50% coverage, dots will be placed next to each other. A kernel designed to control the local behaviour of the dot pattern is thus needed. The iterative process described above is fairly time consuming. The time taken depends on the number of minority dots, the initial binary pattern, and the size of the kernel used for the optimization. If, however, the initial binary pattern is close to optimal, the computational cost is dramatically decreased. This is utilised in the correlation process described next. Besides, the computation is done off line and once and for all. The time required for generating the halftoning volume is thus of minor interest.

4. Creating the locally correlated volume The strength of the PreCoM technique lies in the possibility of producing both near optimal tints and nice transitions between them. Without the correlation between adjacent maps, disturbing irregularities and discontinuities will be detectable at the transitions. The proposed 6 method for the generation of the halftoning volume assigns an unique filter kernel to each map that is to be optimized. By changing the filter kernel gradually between adjacent maps, and by using the previously optimized map as the starting pattern to the next, maps that produce images with both desired properties can be derived.

Before generating the halftoning volume, decisions have to be made about the map size and the number of tint levels that should be defined. Any size of the map could be chosen, but all maps in one volume must have the same size. Furthermore, if the maps are too small, a disturbing periodical structure could be introduced into the produced halftones. Through experiments we have discovered that a map size of 64x64 seems to be sufficient for the elimination of such effects. This map size is thus used in the following. While it is possible that an optimal size could be established and proved, such experiments have not yet been done.

The image material we have been working with has a dynamic range of 8 bits, i.e. 256 gray levels are possible. It is doubtful whether more levels are meaningful for a human observer, at least for images reproduced in print. Possibly, it may be the case that even fewer levels could be acceptable. However, until investigated further, the volumes will contain 256 pre- computed maps, one for each possible intensity level in an 8 bit image.

Having decided on these two properties, the number of minority dots that differs between two adjacent maps can be computed. A fixed difference in dots between maps results in a linear reflectance function for the digital volume. Unfortunately, due to the dot gain in prints, this linearity does not carry over to the reflectance function for the print. However, if the dot gain function is known, the structure of the PreCoM technique allows dot gain compensation to be performed when the volume is computed. Since each map is designed individually, each map can contain the number of dots that produces the desired linear reflectance function in print. Dot gain compensation can thus be done at the same time as the image is halftoned, making pre-adjustments of the of the original image's histogram unnecessary. With the number of dots for each map decided, the halftoning volume can be calculated. The proposed procedure for this is described below. Examples of results during the process are given in Figure 3. 7

The process is initiated by generating a matrix of the desired map size containing white noise in the range [0,1]. By thresholding the matrix at for instance 0.2, a dot pattern with approximately 20% minority dots is obtained, see Figure 3 a). If necessary, extra dots can be added or removed of random to get the exact number of dots that the map should have. By using the assigned filter kernel and applying the iterative optimization process described above, the first map of the volume is computed and stored, Figure 3 b). To calculate the next map, the voids of the first map are located and the desired number of extra dots are added iteratively in these positions, still by using the filter assigned to the first map. Note that no rearrangement of the dots is made at this stage. See Figure 3 c) for an example. While the new dot pattern may be optimal with respect to the old filter, it will in general not be optimal with respect to the new filter which is assigned to this particular tint value. Thus, the dot pattern has to be optimized with the new filter before the new map can be stored, Figure 3 d). This procedure of iteratively deriving the next map from the previous map continues up to the level where the map consists of equally many ones and zeros. At this stage the representation of minority and majority dots is switched, and instead of adding dots, dots at the tightest clusters are removed before optimization. The procedure continues until all minority pixels are gone. The maps between 0% and 20% are derived in a similar manner, starting from the first generated map at 20% and removing minority dots.

The filter kernel used to make the dots as dispersed as possible in each map is a Gaussian shaped kernel. The width of the kernel function is changed according to the tint value. The fewer the minority dots, the wider the kernel. The filter kernel g(x,y) is defined by

(χ² + y²)

(C_J - ₂Γ) g y) = e (W, |y| ) < 5/2 0 otherwise

where T is the number of minority pixel divided with the map size, cl and c2 are positive constants chosen to make the expression cl-c2T positive, and where S is the size of the kernel in pixels. For an efficient implementation of the algorithm, the size of the kernel, S, could be made dependent on the function g(x,y). While a wide kernel size is necessary for 8 very bright or dark tints, a small kernel size is sufficient for tints around 50% . It is thus not necessary to use the large kernel size for all maps.

Experiments have shown that to get the smooth transition between tints around the 50% level, a change in filter characteristics is needed. Thus, for maps around this level, a small amount of band pass characteristics is introduced. This is further discussed in the next section. In Figure 4 a-c, the test images are halftoned with the PreCoM technique using a halftoning volume computed with the described procedure.

There are, however, some known problems with the described method. In rare cases, a dot is moved from its position in one map to a neighbouring position in an adjacent map. This could result an a micro cluster in the halftoned image in transitions between these two maps. By examining the test image above thoroughly, both small white and black clusters can be found. It is doubtful if such micro cluster actually lowers the overall visible quality, but if this is the case, it is probably possible to adjust such artefacts with a post-processing operation on the halftoned image.

5. Changing the filter characteristic

It is not obvious that the optimization criterion that results in maximally dispersed dots produces the most visually pleasant halftones. For instance, in maps with above 25% of minority dots, some of the dots must necessarily be placed in connection with each other, at least corner to corner. Moreover, for maps around the 50% density level, clusters of dots will always be generated, and due to the correlation criterion these may not always be visually pleasant. It may therefore be motivated to try other optimization criteria for maps with more that 25% of minority dots. For instance, instead of spreading the dots as much as possible, they could be arranged into supervised micro structures.

The use of micro structures may both facilitate the correlation between maps, thus producing smooth transitions, as well as increase the visual quality of the resulting tints. As an example, the visually pleasant impression of results from iterative and error diffusion methods could partly be explained by the micro structures introduced. The observer seems to exclude even clearly visible structures and focus on the image information it conveys. 9

Furthermore, the presence of structures appears to give a less grainy impression of the halftone. In theory, the PreCoM technique allows any micro structure to be used in the halftones. We have found two types of strucmres that we have experienced to result in less grainy halftones as well as an increase of the overall image quality.

5.1 Line like structures

Inspired by the conventional, but not commonly used, line screens that results in fairly clear images, we have introduced line like micro structures for the mid tones in the halftoning volume. This is realised by using directional band-pass filters in the optimization of these maps. Still, in bright and dark tints, the dots can be, and presumably should be maximally dispersed. For these maps, a Gaussian low-pass filter is thus used. This means that in order to maintain the correlation between adjacent maps, the band-pass characteristics has to be introduced gradually. Up to a certain level, for instance 30%, the same Gaussian filter as discussed above can be used. Passing this level, the Gaussian filter is modified by subtracting a function describing a directional low-pass filter. Choosing the bandwidths properly, the result from this operation will be a directional band-pass filter. By gradually increasing the influence from the subtractive term, the filter will become more and more band-pass like and thus suitable for the higher levels. Examples of such kernel, with the gradual change, are given in Figure 5.

Figure 6a-c shows the test images halftoned using the halftoning volume derived with these filters. A slight asymmetry can be noticed in the shades, where the line structure is visible further up on the bright side of the 50% level than on the dark side. The reason for this is that the initial binary pattern from which the computation of the volume started was derived at 20% white dots. Since previously derived maps will affect the appearance of the next, the maps above the 50% level will be affected by the heavy line structures in the 50% level. While it may be possible to derive a more symmetrical volume, experiments have shown that if the initial map is derived at the 50% level, unpleasant discontinuity effects are introduced around this level. The reason for this may be that the optimization results in a local minimum from which it is hard to derive the next map without major changes. 10

As an example, an optimal map for the 50% level could be a perfect chessboard pattern, but the next map derived from this will either be visually unpleasant or have a very different characteristic. The starting map should thus be derived at a level where a stable pattern is the optimum, i.e. a pattern which dots easily can be added to or removed from without really affecting the optimality or the characteristics. Such stable patterns could possibly be found at higher levels than 20% . If this is the case, a more symmetrical halftoning volume than the one used in the above can be computed. We have not yet, however, put any effort in developing such volumes since the general idea of introducing micro structures without losing the smoothness in transitions still holds with the proposed method.

As can be seen from the halftoned test images in Figure 6b and 6c, there are no obvious discontinuities in the shades due to the gradual changes in structure. The tints are slightly less grainy than without the micro structures, and the same goes for the face and hair of the woman in the photograph. In addition, since the influence from the dot gain is greater for several dispersed dots than for one large dot, the dot gain will be smaller with the line structures than with the maximally dispersed dots. This could prove useful when using print setups with heavy dot gain.

5.2 Curved structures

For low print resolutions, the line structure may become too obvious and details along the orientation of the lines will be less sharp than others. A remedy to these problems is to use curved micro structures instead of straight lines. Such structures can be obtained by using isotropic band-pass-like filters in the optimization process. The computation of the halftoning volume is done in the same manner as in the above. The curved structure is gradually introduced by changing the properties of the filters. The closer to the 50% level, the more band-pass characteristic will the filters get. Examples of such filters are shown in Figure 7.

In Figure 8 a-c, the test images have been halftoned with the PreCoM technique using a volume derived with isotropic band-pass filters. The transitions in the shades are even smoother than for the line-like micro structure and the structures themselves are less obvious. Since there is no preferred orientation in the micro structure, the reproduction of of details does not depend 11 on their orientation. This can be noticed for some details in the photograph, for instance at the feathers of the crane. Moreover, not much graininess can be detected in neither the tints nor the homogenous areas of the photograph.

6. Conclusions

Halftoning with PreCoM introduces the possibility of producing well-behaved tints as well as smooth transitions between them without any loss in speed compared to methods based on threshold matrices. The method can be implemented in a truly parallel manner, speeding up the halftoning procedure even further. Moreover, since every map is designed individually, under the constraint that the correlation is not lost, specific characteristics that improves the image quality can be introduced. This, together with the possibility of compensating for the dot gain in the halftoning procedure itself, makes this method attractive in applications where both speed and quality are important. With the print-on-demand concept lying around the corner, the future for the PreCoM technique seems to be very promising.

Whitin the the frame of the invention the man skilled in the art has many options. There are many parameters available in the design of the maps: the widths of the structures, their orientation, the intensity level where it should be introduced, etc. To find the optimal filters, and thus the optimal halftoning volume, and to compare the success of PreCoM to other methods, objective quality measures can be used.

Claims

12Claims

1. Halftoning method based on the use of pre-computed maps, one for each possible tone value in the image, at halftoning the image value at a specific position gives the map from which a pixel is copied into the halftone at the corresponding position characterized in that in the maps with low or high densities maximally spread minority dots are used, and in intermediate maps a successive transition takes place from maximally spread dots to structured dot clusters of defined type.

2. Halftoning method according to claim 1, characterized in the use of structure clusters from a density level of ca: 25% to a density level of ca 75% .

3. Halftoning method according to claim 1 or 2, characterized in that the structures are straight lines.

4. Halftoning method according to claim 1 or 2, characterized in that the strucmres are curved lines.

5. Halftoning method according to claim 1 or 2, characterized in that the strucmres are larger dots.

6. Halftoning method according to claim 3 or 4, characterized in the strucmres varying in both length and width.

7. Halftoning method according to claim 3, characterized in the lines being angled 45┬░.

8. Method for the fabrication of maps for use in the halftoning method defined in claim 1, characterized in that to a preceding map a number of dots are added corresponding to the difference in density level, the dots being placed by means of a low pass filter, then a band pass filter is used to rearrange the dots. 13

9. Method according to claim 8, characterized in the band pass character of the filters increasing until the 50% density level is reached, then to diminish again.

10. Method according to claim 8 or 9, characterized in the band pass filter being isotropic, producing curved structures.

11. Method according to claim 6 or 7, characterized in the band pass filter being directional producing straight line strucmres.