Method for optimizing frequency-modulated rasters upon utilization of threshold hills
BACKGROUND OF THE INVENTION 
     The present invention is in the field of electronic reproduction technology and is directed to a method for optimizing frequency-modulated rasters using threshold hills. 
     Different half-tone values (gray scale values) of an image to be reproduced can be produced in the print only on the basis of a surface modulation in that the gray scale values are resolved into highly resolved binary values having only two brightness values (black and white). 
     In autotype rastering (dot screening), the surface modulation ensues in that the gray scale values of the image are converted into picture elements of different sizes and are printed, whereby the picture elements are arranged in a regular raster structure having periodically repeating raster meshes. In order to minimize disturbing Moire patterns, the dot rasters of the individual inks are arranged at different screen angles. 
     German reference 2,827,596 discloses an autotype rastering method for generating dot rasters having arbitrary screen angling using a threshold hill. In this rastering method, a matrix is subdivided into a plurality of matrix elements and a threshold is allocated to every matrix element. The totality of thresholds, referred to as a threshold hill or raster hill, represents the repeating basic structure for every raster mesh of the dot raster. 
     The recording material for the rastered image is divided into a plurality of surface elements. When recording the rastered image in an output device (recorder), the picture elements in the individual raster meshes of the dot raster grid are composed of exposed surface elements (illumination pixels; device pixels). The check to determine whether or not a device pixel is to be illuminated or exposed as part of a picture element ensues on the basis of a comparison of the corresponding gray scale values of the image to the thresholds of the threshold hill. The results of the comparison are retained as bits in what is referred to as a bit map wherein every set bit corresponds to an exposed surface element or device pixel (or vice versa in the case of a negative presentation). The bit map generally has the size of the recording surface. The control of the exposure beam in the recorder ensues with reference to the bit map. 
     FIG. 1 shows an example of a threshold hill for an autotype rastering. In this example a two-dimensional threshold matrix 1 has 5×5 matrix elements 2 that are filled with the thresholds 1 through 255, namely for that case wherein the individual gray scale values of the image are represented by numbers between 0 and 255, whereby the number 0 corresponds to &#34;black&#34; and the number 255 corresponds to &#34;white&#34;. The threshold matrix 1 generally has the size of a raster mesh of the dot raster. In order, for example, to produce the gray scale value 192 (25% surface coverage), a check is carried out for every matrix element 2 within the threshold matrix 1 to determine if the gray scale value 192 is lower than the threshold allocated to the matrix element 2. When this is the case, the appertaining bit is set in the bit map and the corresponding device pixel is blackened; otherwise, the corresponding bit is not set. 
     FIG. 2 shows a pixel within a raster mesh 3, said pixel having been produced according to an autotype rastering method. The pixel is composed of seven exposed device pixels 4 of 25 possible device pixels 4 within a raster mesh 3 and thus represents a surface coverage of approximately 25% or, respectively, the gray scale value 192. Typically, the thresholds are assigned such that the set bits in the bit map or the exposed device pixels form a continuous, growing, black area (pixel, printing dot) given an increasing gray scale value. 
     Since the threshold matrix 1 for the threshold hill is noticeably smaller than the bit map, the allocation of the bits of the bit map to the thresholds of the threshold matrix 1 is continuously repeated in the x-direction and in the y-direction of the bit map, this being shown in FIG. 3. 
     FIG. 3 shows the periodic allocation of the thresholds of the raster meshes 3 or of the individual raster meshes 3 of a dot raster to a bit map 5. A few pixels 6 having a surface coverage of 25% are indicated in the raster meshes 3 respectively composed of 25×25 device pixels 4. Since the allocation of the threshold matrix 1 in the x-direction and the y-direction is continuously repeated, this leads to the formation of a grid structure. 
     Alternatively to autotype rastering, the surface modulation of the inks can also ensue according to a method for frequency-modulated rastering, for example according to the method set forth in the German reference 2,931,098. In frequency-modulated rastering, the gray scale values of the image are reproduced by an arrangement of small printing dots (device pixels) of the same size that are more or less arbitrarily selected in the recording surface. The plurality of device pixels per surface unit defines the gray scale value that is reproduced. 
     Various methods, for example error diffusion, ordered dither, etc., are known for frequency-modulated rastering. All methods are based thereon that the status of the neighboring pixel is taken into consideration with a certain weighting in the decision as to whether or not a device pixel is to be set. Further, an error propagation from one device pixel to the next is also undertaken, i.e. the status of the most recently set device pixel has influence on the next pixel to be processed. 
     FIG. 4 shows an example of a frequency-modulated rastering. The set bits or the corresponding device pixels 4 are more or less arbitrarily distributed within the surface unit in the bit map 5 and thus no longer form a continuous area. A surface coverage of 25% is shown. 
     The advantage of an autotype rastering method with a threshold hill is based on the rastering being carried out very quickly both in software as well as in hardware. In traditional, frequency-modulated rastering methods, a plurality of time-consuming calculation operations are required for every device pixel. This has a disadvantageous effect on the operating speed. 
     It is also known to combine an autotype rastering method and a frequency-modulated rastering method with one another and to fill a threshold hill with an arbitrary sequence of thresholds that do not form a contiguous area. To this end, FIG. 5 shows a threshold matrix 1 having a random sequence of 5×5 thresholds for the frequency-modulated rastering and FIG. 6 shows a pixel of seven randomly distributed, exposed device pixels 4 within a surface unit 7 that is produced by a frequency-modulated rastering. This procedure, however, has the disadvantage that disturbing residual structures result in color areas having constant tonal value even given the most dexterous selection of the random distribution of the thresholds. Since the threshold hill periodically repeats in the x-direction and in the y-direction, these residual structures are also repeated over the entire recording surface. Since the eye is especially sensitive to such residual structures, they are not tolerable in practice. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a method for optimizing frequency-modulated rastering for recording rastered images with which the creation of disturbing structures in the recording surface due to the periodic repetition of a threshold hill is avoided to the farthest-reaching extent and structures in the threshold hill itself are minimized. 
     In general terms the present invention is a method for optimizing frequency-modulated rasters for the recording of (black-and-white or chromatic) raster images. The image to be respectively recorded is optoelectronically scanned pixel-by-pixel and is digitally stored in a pixel memory in the form of gray scale values allocated to the individual pixels. Threshold decisions are implemented on the basis of the gray scale values, a decision being made with reference to these threshold decisions as to whether a pixel is or is not set in the recording of the image. A two-dimensional threshold memory is employed for threshold decision. This is superimposed on the pixel memory in two-dimensional periodic repetition for the implementation of the threshold decisions. The thresholds thereof are selected such that they form a topography, i.e. one or more threshold hills within the threshold memory (in a third dimension). The expanse of the threshold memory is selected larger in one dimension than in the other dimension. An offset is employed in one dimension of the repetition in the two-dimensional periodic repetition of the threshold memory. The threshold memory is subdivided into sub-memories that together form the overall threshold memory. The filling of the sub-memories with thresholds ensues by random selection of the thresholds of the threshold hill, by continuous quadranting of the thresholds, and by random distribution of the values within the sub-memories. 
     Advantageous developments of the present invention are as follows. 
     The method can be carried out with a variable offset that is defined by a random number that is constantly re-defined, or with a constant offset. 
     The sub-memories are fashioned as sub-quadrants that are formed of elements arranged in rows. The filling of the elements of the sub-quadrants ensues by continuous quadranting of the threshold hill and by random determination of the elements in the sub-quadrants. 
     The first element of a row is sought from the threshold hill with a random generator and the number zero is allocated to it. The threshold hill is subdivided into four quadrants of the first order and the second element of the row is determined in that quadrant of the first order which lies opposite the quadrant of the first order wherein the first element is located and the ordinal number one is allocated to the second element. One proceeds such with the assigning of the ordinal numbers two and three in the two remaining quadrants of the first order, as in the case of the two first quadrants of the first order. The four quadrants of the first order are subdivided into four groups of four quadrants of the second order, whereby the four ordinal numbers that are assigned each respectively fall into one respective quadrant of the second order within one of the four groups. The ordinal numbers four through seven are respectively assigned to one group of four quadrants within the quadrants of the second order, whereby the ordinal number four is allocated to that quadrant that lies opposite the quadrant that already contains one of the ordinal numbers one through three. In two further passes, respectively one quadrant of each group is occupied with a further ordinal number until all quadrants of the second order are occupied with an ordinal number. Four groups of quadrants of the third order are successively formed, whereby one of the four groups is formed first and four further ordinal numbers are assigned, a second group lying diagonally relative to the first group is formed, this being likewise occupied with four ordinal numbers, and, subsequently, a third group and fourth group are formed that are likewise each respectively occupied with four ordinal numbers. This procedure is then repeated twice. Another, two-time processing of the four groups of four quadrant groups of the third order ensues, whereby a different ordinal number is allocated to each of these quadrants. 
     The assigning of the ordinal numbers ensues into a random element and not into the element lying opposite when the quadrants are composed of only one element. 
     Only two ordinal numbers per quadrant are assigned when the quadrant of the last order is reached. 
     The dimensions of the threshold hill are selected such that the height thereof is a power of two and the width thereof is a multiple of the height and such that the threshold hill is filled with a plurality of quadratic basic shapes. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features of the present invention which are believed to be novel, are set forth with particularity in the appended claims. The invention, together with further objects and advantages, may best be understood by reference to the following description taken in conjunction with the accompanying drawings, in the several Figures of which like reference numerals identify like elements, and in which: 
     FIG. 1 depicts an example of a threshold hill for autotype rastering (prior art); 
     FIG. 2 depicts an example of an autotype pixel given approximately 25% surface coverage (prior art); 
     FIG. 3 depicts the periodic allocation of an autotype threshold hill to the bit map, whereby some pixels having approximately 25% surface coverage are indicated (prior art); 
     FIG. 4 depicts an example of frequency-modulated rastering, whereby a 25% surface coverage is indicated (prior art); 
     FIG. 5 depicts an example of a threshold hill for frequency-modulated rastering (prior art); 
     FIG. 6 depicts an example of a frequency-modulated pixel having approximately 25% surface coverage (prior art); 
     FIG. 7 depicts an example of a threshold hill having improved repetition period due to a fixed offset value wherein a 13% frequency-modulated tonal value is indicated; 
     FIG. 8 depicts an example of a frequency-modulated threshold hill having improved repetition period due to random offset values; 
     FIG. 9 depicts an example of a frequency-modulated threshold hill having improved repetition period upon employment of a non-rectangular basic shape; 
     FIG. 10 depicts an example of a frequency-modulated threshold hill having improved repetition period upon employment of a plurality of sub-threshold hills; 
     FIG. 11 depicts allocation of the number zero to an element from the threshold hill that is defined with a random generator; 
     FIG. 12 depicts subdivision of four quadrants of the first order into four groups of four quadrants of the second order; 
     FIG. 13 depicts the respective occupation of a quadrant of each group with a further ordinal number; 
     FIG. 14 depicts generation of a group of four quadrant groups; 
     FIG. 15 depicts occupation of a further, diagonally offset group of four quadrant groups having four further ordinal numbers; 
     FIG. 16 depicts the two-time repetition of the occupation of a further, diagonally offset group of four quadrant groups having four further ordinal numbers; 
     FIG. 17 depicts allocation of an ordinal number to quadrants by two-time processing of the total of four groups of four quadrant groups; and 
     FIG. 18 depicts threshold hill that proceeded from the combination of both versions. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The method of the present invention serves the purpose of minimizing periodic structures in the recording surface and of minimizing structures within the threshold hill. 
     1. Minimization of Periodic Structures 
     For minimizing periodic structures, it can first be observed that fainter structures become visible when the threshold hill is selected to have a larger expanse, for example 256×256 thresholds instead of 128×128, since the repetition period is then larger. Theoretically, the problem could be resolved in that the threshold hill is selected so large that the repetition period is no longer noticed. In practical terms, limits are quickly encountered since the need for memory space quadratically increases. Practical trials have shown that many megabyte memories would be required. In addition to the costs and the availability of existing devices, considerable disadvantages resulting the manipulation of such large data sets (loading times from a hard disk, etc.). 
     This problem can then be avoided without a substantial increase in the memory requirements. The goal is to achieve a repetition period with reasonable memory outlay such that no structures are visible to the eye in regions of smooth tonal values or at least are decisively alleviated. In order to achieve this, the threshold memory is inventively dimensioned substantially longer in one direction (for example, the x-direction) than in the other direction. For example, the dimension of the rectangular threshold matrix could be selected as 4096×16 thresholds instead of 256×256. The repetition period has thus substantially grown in the x-direction. However, it has become noticeably smaller in the y-direction. 
     In order to compensate this, the threshold matrix continues to be allocated in periodically repeating bits of the bit map 5 in the x-direction. In the y-direction, by contrast, the periodic allocation is overlaid with an offset. This offset can either be a random number that is repeatedly redefined, whereby an infinite repetition period would derive in the y-direction, or a fixed offset value whose selection must be undertaken such that an adequate repetition period is achieved. 
     FIG. 7 shows an example of a bit map 5 having an improved repetition period due to a fixed offset 8 of the threshold matrix within the bit map 5. The device pixels 4 within the individual, rectangular bit map regions 9 indicate a 13% frequency-modulated tonal value. 
     FIG. 8 shows an example of a bit map 5 wherein the respective offset 8 of the threshold matrix or of the bit map regions 9 is randomly selected. 
     Particularly when using a fixed offset value, it is not necessary to use threshold matrices or threshold hills having a rectangular basic shape. As long as these can be seamlessly joined to one another, any desired shape can be selected, for example L-shaped threshold matrices or threshold hills. 
     FIG. 9 shows another example of frequency-modulated rastering with improved repetition using a non-rectangular basic shape of the threshold matrix. In continuation of this idea, a plurality of sub-hills can be used that can in turn be correspondingly joined. 
     FIG. 10 shows an example of a frequency-modulated rastering with improved repetition using a plurality of sub-threshold hills. 
     2. Minimization of the Structures within the Threshold Hill 
     The simplest way of generating the thresholds of the threshold hill for a frequency-modulated rastering would be to cast the sequence of the lending of the thresholds with a random number generator. Unfortunately, this method does not produce good results since the uniformity of chance leaves much to be desired. This leads to the fact that some of the thresholds clump up in a small area given certain tonal values. This leads to visible structures. The method set forth below decisively alleviates this disadvantage. 
     For the sake of simplicity, let a quadratic threshold hill first be assumed whose width and height may be assumed to be a power of two. If the finding set forth above continues to be maintained, to wit that thresholds between 1 and 255 are used, then, dependent on the size of the threshold hill, all thresholds do not occur or thresholds are doubly assigned. The goal of the method set forth here is to define the sequence of the thresholds to be assigned, not the thresholds themselves. 
     The purpose of the method is to in fact achieve a random distribution by continuous &#34;squaring&#34; or quadranting of the threshold hill and by random determination of the elements in the sub-quadrants, and to achieve an approximately equal distribution of the blackened device pixels over the entire surface. The procedure in the formation and selection of the sub-quadrants is based on the method which has become known as &#34;ordered dither&#34;. 
     FIG. 11 shows how an element from the threshold hill is defined by the random number generator for the first element of this row or series and the number zero is allocated to it. Subsequently, the hill is subdivided into four quadrants (&#34;squaring&#34;) of the first order and the second element of the row or series is defined by the random generator in the quadrant which lies opposite the quadrant wherein the first element is located and the ordinal number one is allocated to it. Subsequently, the procedure is carried out in the same manner in the two remaining quadrants. 
     Next, the four quadrants of the first order are subdivided into four groups of four quadrants of the second order, as shown in FIG. 12. The four ordinal numbers assigned up to that point thus fall into one respective quadrant of the second order in order group. 
     In the next step, the ordinal numbers 4 through 7 are assigned. Again by random number generator, namely, one ordinal number is allocated to a respective quadrant of the second order from every group. The quadrant selected from each group for this purpose is that quadrant that lies diagonally opposite the quadrant that already contains an ordinal number. The purpose of the selection of the quadrants lying diagonally opposite one another is to achieve a higher equipartition and to avoid horizontal and vertical structures. The procedure is exactly the same in the quadrant groups, i.e. the ordinal number 4 is assigned in the upper left group, the next is assigned in the lower right group (lying diagonally opposite), then at the top right and, finally, at the bottom left, i.e. a crossed allocation ensues. 
     So far, two respective quadrants of the second order from each group are occupied with a respective ordinal number. In two further passes, respectively one quadrant of each group is occupied with a further ordinal number, as shown in FIG. 13. 
     All quadrants of the second order have now been occupied with an ordinal number. Four groups of four quadrant groups of the third order are therefore now successively formed. 
     First, a group of four quadrant groups is produced according to FIG. 14. The purpose of this arrangement is again a maximum equipartition. The assigning of the next four ordinal numbers in the individual quadrants of the third order of this group again ensues in the cross structure that has already been set forth. 
     After this, a further, diagonally offset group of four quadrant groups is formed and is occupied with four further ordinal numbers, as FIG. 15 shows. 
     This procedure is repeated twice more, as shown in FIG. 16. 
     FIG. 17 shows how two respective quadrants of a quadrant group of the third order are now occupied with ordinal numbers. By another, two-time processing of the total of four groups of four quadrant groups of the third order, an ordinal number is now assigned to each of these quadrants. 
     The procedure of quadrant formation is continued until a quadrant is composed of only one element and all elements of the threshold hill have ordinal numbers assigned to them. The actual thresholds are allocated after this. 
     At least two modifications of the above method are conceivable. 
     First, a pronounced checkerboard pattern of the device pixels very frequently results in the above method given a 50% tonal value. This is not always desirable. When the quadrants are composed of only one element, arbitrary quadrant from the group can be used instead of the quadrant lying diagonally opposite. This approach counteracts the checkerboard formation. 
     Second, it is more beneficial to divide the method in two for darker tonal values wherein there are optically white device pixels on a black background. For the quadrants of the last order, only two ordinal numbers per quadrant group are assigned, i.e. a total of only 50% of the elements are occupied. All device pixels are quasi placed a on a white background. Subsequently, the procedure of the continued quadranting is again repeated but begins with the highest number in the assigning of the ordinal numbers and assigns them in descending sequence. As a result, basically white is written on a black background and a better distribution is obtained in the dark tonal values. 
     FIG. 18 shows a complete threshold hill that has arisen from the combination of the two modifications set forth above. 
     The description for assigning the ordinal numbers has hitherto been limited to quadratic threshold hills. In order to also fill the threshold hill set forth in the first part, the dimensions thereof are selected such that the height thereof is a power of two and the width is a multiple of the height and fills them with a corresponding plurality of quadratic basic shapes produced according to the above method. 
     The invention is not limited to the particular details of the method depicted and other modifications and applications are contemplated. Certain other changes may be made in the above described method without departing from the true spirit and scope of the invention herein involved. It is intended, therefore, that the subject matter in the above depiction shall be interpreted as illustrative and not in a limiting sense.