United States Patent: 5,706,105

[US Patent & Trademark Office, Patent Full Text and Image Database]

( 1 of 1 )

United States Patent	*5,706,105*
Naylor, Jr.	January 6, 1998

Dither method and apparatus

Abstract

A method of creating a three dimensional halftone dither matrix, in which the matrix is divided into a predetermined number of levels with each level comprising a two dimensional matrix of activation indicators having positional values including x and y positional components. The method includes the steps of firstly creating a series of three dimensional curves, from a two dimensional array of dither values, the two dimensional array being of the same dimensions as the two dimensional matrix and including level value entries, each of the level value entries having a corresponding three dimensional curve, the three dimensional curve starting at a starting level corresponding to the dither matrix value and at a position corresponding to the x and y positional components of the level value entry, the three dimensional curve terminating at the highest level of the three dimensional halftone dither matrix and taking one x and y positional value on each level between the starting level and the highest level. Secondly, the method forms an objective function having at least two components, a first component being a measure of the evenness of the distribution of the positional values of the curves for a particular level, and the second component being a measure of the deviation of the curve from a straight vertical line. Thirdly, the method optimizes the objective function so that the positional values at any of the levels of the series of curves have a high degree of evenness of distribution and the curves have a low degree of deviation from a straight vertical line. Lastly, the method forms the three dimensional halftone dither matrix wherein the activation indicators are active in positions corresponding to the paths of each of the curves.

Inventors:	Naylor, Jr.; William Clark (Santa Clara, CA)
Assignee:	Canon Kabushiki Kaisha (Tokyo, JP)
Appl. No.:	509820
Filed:	August 1, 1995

Foreign Application Priority Data

Aug 01, 1994[AU]

PM 7194

Current U.S. Class: 358/3.23; 358/3.14; 382/274; 382/285

Intern'l Class: H04N 001/40

Field of Search: 395/108,118,119,120,124,125,127 358/429,455,456,457,459,465 382/169,237-239,270,274,285

References Cited [Referenced By]

U.S. Patent Documents

4985856	Jan., 1991	Kaufman et al.	364/522.
5038302	Aug., 1991	Kaufman	364/522.
5101475	Mar., 1992	Kaufman et al.	395/124.
5243441	Sep., 1993	Kawata	358/451.
5444551	Aug., 1995	Miller et al.	358/456.

Primary Examiner: Lee; Thomas D.
Assistant Examiner: Grant, II; Jerome
Attorney, Agent or Firm: Fitzpatrick, Cella, Harper & Scinto

Claims

I claim:

1. A method of creating a three dimensional halftone dither matrix, said matrix being divided into a predetermined number of levels with each level comprising a two dimensional matrix of activation indicators having positional values including x and y positional components, said method being performed using a computer and comprising the steps of:

(a) creating a series of three dimensional curves, from a two dimensional array of dither values, said two dimensional array being of the same dimensions as said two dimensional matrix and comprising level value entries, each of said level value entries having a corresponding three dimensional curve, said three dimensional curve starting at a starting level corresponding to said dither matrix value and at a position corresponding to the x and y positional components of said level value entry, said three dimensional curve terminating on the highest level of said three dimensional halftone dither matrix and taking one x and y positional value on each level between said starting level and said highest level,

(b) forming an objective function having at least two components, a first component being a measure of the evenness of the distribution of the positional values of said curves for a particular level, and the second component being a measure of the deviation of said curve from a straight vertical line,

(c) optimising said objective function so that the positional values at any of said levels of said series of curves have a high degree of evenness of distribution and said curves have a low degree of deviation from a straight vertical line, and

(d) forming said three dimensional halftone dither matrix wherein said activation indicators are active in positions corresponding to the paths of each of said curves.

2. A method as claimed in claim 1, wherein said optimising step includes the process of swapping a portion of a first of said curves from a first positional coordinate to a second positional coordinate on the same level, said second positional coordinate not being occupied by another of said curves.

3. A method as claimed in claim 2, wherein said optimising step includes the process of swapping all the portion of said curve between said same level and said highest level from said first positional coordinate to said second positional coordinate.

4. A method as claimed in claim 1, wherein said curves are initially straight lines.

5. A method as claimed in claim 1, wherein said second component is of the form: ##EQU22## where each point of a curve is represented by a three-tuple, having a x value, a y value, and a level value denoted l, and the weighting function w(l.sub.1 -l.sub.2) represents a weight applied which is proportional to the distance between the two levels l.sub.1 and l.sub.2, being the corresponding levels of the points P.sub.1 and P.sub.2.

6. A method as claimed in claim 1, wherein said first component is of the following form: ##EQU23## where dist(p1,p2) is a distance measure from the point p1 to the point p2 where distance is measured in a modulo or wrap around sense, and .gamma. is a positive number.

7. A method as claimed in claim 1, wherein said second component only measures the deviation of said curve from a straight line over a predetermined length of said curve.

8. A method as claimed in claim 1, wherein said first component is of the form: ##EQU24## where w.sub.I (intensity) is a weighting function which takes values substantially in accordance with the perception of the human eye of the corresponding intensity level, window.sub.-- radius is a predetermined constant and dist(p1,p2) is a distance measure modulo the size of the dither matrix.

9. A method of halftoning an image comprising an array of pixels with each pixel having an intensity level indication, said method utilising a dither matrix as claimed in claim 1 and comprising the steps of, for each of said pixels: utilising the intensity level indication to determine the level of a two dimensional bit map array within said three dimensional halftone dither matrix and a portion of the address of said pixel within the array of said pixels to determine a positional location within said two dimensional bit map array, so as to derive a marking output value for each of said pixels.

10. A method as claimed in claim 9 wherein said marking value is one of two values.

11. An apparatus for halftoning an input image comprising:

an inputting device for inputting pixel data values including intensity level and address data,

a table look up device, connected to said inputting device, and containing a series of two-dimensional arrays of dither values comprising level value entries, each of said level value entries having a corresponding three-dimensional curve starting at a starting level corresponding to a three-dimensional halftone dither matrix value and at a position corresponding to x and y positional components of said level value entry, said three-dimensional curve terminating on a highest level of said three-dimensional halftone dither matrix and taking one x and y positional value on each level between said starting level and said highest level wherein said level value entries have been optimised so that said level value entries of said curves have a high degree of evenness of distribution and said curves have a low degree of deviation from a straight vertical line, said intensity level data being used to select one of said series of two-dimensional arrays and address data being used to address a data value within said selected two-dimensional array, and

a marking device, connected to said look-up device, for making an output image when said data value exceeds a predetermined threshold.

Description

FIELD OF THE INVENTION

The present invention relates to reproduction of images through the use of halftoning and, more particularly, relates to a process of dithering utilised in the reproduction of images.

BACKGROUND ART

Halftoning techniques, such as dithering, are utilised when an output device is unable to display continuous tone values, and on it being to display a limited number of discrete levels for each pixel, The dithering process is intended to produce, on a desired output device having, for example, only a restricted grey scale capability, an image approximating, as close as possible, the original image. Although dithering has been shown to easily extend to multi-level output devices, in addition to colour printing devices, for the sake of clarity, it can be assumed that the output device is of the form of a bi-level black and white printing device.

The process of dithering traditionally involves the creation of a "dither matrix". Image pixel values are then normally compared with a corresponding value in the dither matrix. If the dither matrix value is less than the input pixel value, a marking device, such as a printer or display tube, produces a "on" pixel indication at that particular point.

The number of entries in the dither matrix is normally substantially smaller than the number of entries in the input pixel image. Therefore, the most common technique utilised in the art for addressing a dither matrix is one that utilises modulo arithmetic. This corresponds to repeating or "tiling" the dither matrix over the input image.

The formation of a dither matrix is the most significant portion of the dithering process and the dither matrix should have a number of desirable attributes. These include:

1. The dither matrix should be as large as possible so as to avoid the occurrence of repeated patterns in the output image produced by the repetitive or tiling nature of the dither matrix.

2. The dither matrix should have as fine a "granularity" as possible, the granularity preferably not exceeding the granularity of the input image. Hence, the number of levels that each value within the dither matrix can take should, preferably, be equal to the number of levels that the input pixels may take. This avoids the unnecessary loss of detail in the output image through over quantisation of the input image.

3. With larger dither matrix sizes, it is desirable that the values within the dither matrix be evenly distributed across all possible values of input pixels. This can effectively be achieved by repeating each level, in the dither matrix, the same number of times.

4. The distribution of the dither matrix values should be chosen so as to avoid unwanted artifacts in any output image. Unwanted artifacts can occur in areas of an image that are of the same intensity or slightly varying intensities due to regularities occurring in the dither matrix.

5. At each intensity level, it is desirable that the relevant output marking device creates a half tone image that is as evenly distributed as possible. This requirement can be met by "spreading out" those pixels which will be illuminated at each possible level.

The need to provide a dithering technique that "spreads out" the marked output points at each level is particularly important, as is the need to ensure areas with slightly varying levels of intensity also produce a dithered output where the output pixels are as evenly distributed, or are spread, out as far as possible.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide an alternative form of dithering which leads to improved output images for at least some class of images.

In accordance with a first aspect of the present invention there is provided a method of creating a three dimensional halftone dither matrix, the matrix being divided into a predetermined number of levels with each level comprising a two dimensional matrix of activation indicators having positional values including x and y positional components, the method being performed using a computer and including the steps of:

(a) creating a series of three dimensional curves, from a two dimensional array of dither values, the two dimensional array being of the same dimensions as the two dimensional matrix and comprising level value entries, each of the level value entries having a corresponding three dimensional curve, the three dimensional curve starting at a starting level corresponding to the dither matrix value and at a position corresponding to the x and y positional components of the level value entry, said three dimensional curve terminating on the highest level of the three dimensional halftone dither matrix and taking one x and y positional value on each level between the starting level and said highest level,

b) forming an objective function having at least two components, a first component being a measure of the evenness of the distribution of the positional values of the curves for a particular level, and the second component being a measure of the deviation of the curve from a straight vertical line,

(c) optimising the objective function so that the positional values at any of the levels of the series of curves have a high degree of evenness of distribution and the curves have a low degree of deviation from a straight vertical line, and

(d) forming the three dimensional halftone dither matrix wherein said activation indicators are active in positions corresponding to the paths of each of the curves.

In accordance with a second aspect of the present invention there is provided an apparatus for halftoning an input image including:

an inputting device of inputting pixel data values including intensity level and address data, a table look up device, connected to the inputting device, and containing a series of two dimensional arrays constructed in accordance with the preceding paragraph, the intensity level data being used to select one of the series of two dimensional arrays and address data being used to address a data value within the selected two dimensional array, and a marking device, connected to the lookup device, for making an output image when the data value exceeds a predetermined threshold.

BRIEF DESCRIPTION OF THE DRAWINGS

The preferred embodiment of the present invention are described with reference to accompanying drawings in which:

FIG. 1 illustrates the process of formation of dither matrices;

FIG. 2 is a graph illustrating the illumination of output pixels when dithered with the first row of the dither matrix of FIG. 1;

FIG. 3 illustrates the illumination of pixels when dithered with the matrices created in accordance with the preferred embodiment;

FIG. 4 is a flow chart of the simulated annealing process utilised in the preferred embodiment;

FIG. 5 illustrates the weighting function utilised in the simulated annealing process of the preferred embodiment;

FIG. 6 illustrates the incorporation of resultant matrices created in accordance with the preferred embodiment into a dithering system for outputting images on a bilevel device;

Appendix 1 is a computer program listing for the creation of a 3-dimensional matrix in accordance with the preferred embodiment;

Appendix 2 is a listing of the simulated annealing library routines; and

Appendix 3 is a listing of the simulated annealing codes.

DETAILED DESCRIPTION

Referring now to FIG. 1, there is shown an example of a 16.times.16 dither matrix 1. The dither matrix 1 comprises a large number of entries 2, the values of which are initially assigned in accordance with any of the standard techniques, for example the Bayer technique as outlined in standard text books such as "Computer Graphics--Principles and Practice", Foley et al., second edition 1990, Addison-Wesley Publishing Company, Inc. Reading, Mass. at pages 568-573.

However, the preferable method of assignment is as set out in detail hereinafter under the sub-heading "Initial Assignment of Dither Matrix Values". If the entries 2 have been assigned in accordance with the preferred method, the resultant values will produce, at each possible output level, a substantially evenly distributed output. The dither matrix formation process mentioned under the heading entitled "Initial Assignment of Dither Matrix Values" tends to produce a matrix with values distributed in a slightly random pattern due to the nature of the simulated annealing process which is also described hereinafter in greater detail. The first row of dither matrix 1 is shown in FIG. 1 containing a set of sample values which are assumed to form part of the resulting dither matrix after the completion of the assignment process.

Referring now to FIG. 2, there is shown a graph having a first axis (X value) having 16 graduations (0-15) corresponding to the 16 possible column positions of the first row of the dither matrix 1 of FIG. 1, The Y axis is represented by a level scale having graduations from 0-15. If it is assumed that input pixels take on one of 16 separate values (0-15), markers 5, illustrate the level value at which pixels which map to the corresponding X value are turned on. A line 6 illustrates those pixel level values greater than the corresponding marker value 5, which produce a corresponding "turning on" of the output pixel. Hence, if the dither matrix value in column 15 of the first row is 5, all corresponding input pixel level values in the range 5 to 15 cause the output value at this location to be turned on.

The method described hereinafter under the sub-heading "Initial Assignment of Dither Matrix Values" is directed to evenly spreading out those pixels which are currently turned "on" at each level. Of course, FIG. 2 represents only one row of the dither matrix and, as the method is applied in both the X and Y axis of the dither matrix, a three dimensional form of FIG. 2 is created, with FIG. 2 showing a slice through the Y axis at the first row of Y.

Unfortunately, when utilising a dither matrix assignment technique such as the one outlined below, once a dither matrix value 5 has been assigned a position in the array, the corresponding line 6 is fixed for all higher levels. Therefore, even though certain levels, (eg. level 1) may be in some form of equilibrium, the need to turn on more and more pixels within the dither matrix at higher levels disturbs this equilibrium and enforces higher levels to not be in the best possible equilibrium or "spread out" state.

One method which is utilised to overcome this problem is to store a separate bit map for each level indicating whether a pixel is on or off at that level. These bit maps are then separately optimised, for example using simulated annealing, to produce patterns which are of a spread out nature at each level. One such method for optimising separate bit maps for each level of output is disclosed in U.S. Pat. No. 4,920,501 entitled "Digital Halftoning with Minimum Visual Modulation Patterns" by Sullivan et al. However, that method is unsuitable as the separate optimisation of each bit map level has been found in practice not to produce optimal results for most images. Most images often comprise large regions of slowly varying pixel intensity levels. Therefore, in such slow varying areas, only a few contiguous levels are involved. In such areas, it has been found that the independent minimisation of the levels of the dither matrix result in interference effects occurring between levels such as to produce a sub-optimal result, with noticeable clumping of pixels a result of this interference.

In the preferred embodiment of the present invention, the line 6 of FIG. 2 is made to alter its path at higher levels if this results in a more evenly distributed or spaced out pattern, with a penalty being paid for the alteration.

Referring now to FIG. 3, there is shown an example of this process. In this example, a dither matrix value 10 is initially turned "on" in column 14 (X value) at level zero. Subsequently, a determination is made to turn on to the matrix value 11 at level 1. This causes the corresponding path or curve 13 to be altered in the vicinity of a matrix point 11 so as to produce a more spread out distribution at each level. Similarly, path 14 is altered in the vicinity of point 15, and the path 16 is also altered in the vicinity of the point 17. Although movement of the curve 13 from one layer to the next can produce unwanted interference effects, the resultant more even distribution of pixels illuminated at each level also produces an improved output image.

Unfortunately, the number of different combinations possible in optimising the process of the preferred embodiment is excessive. FIG. 3 shows only the X axis of one column. Inclusion of the Y axis adds an additional dimension to the problem. The finding of an exact combination or combinatorial solution of how best to assign values as is practically beyond current day computers for large size dither matrix system.

It should be noted that the preferred embodiment is not a traditional dither matrix system, as a bit map is required to be storm for each level indicating those tither matrix positions that are "turned on" at a particular level.

Additionally allowing the paths eg. 13, 14, 16 to change from the strictly vertical can, in some instances, produces unwanted interference effects between differing levels in slowly varying images.

The Simulated Annealing Process

The extreme complexity of the solution of the bit map production process suggests it is most likely of an NP-complete nature, and hence its attempted optimisation utilising a process such as "simulated annealing" would be beneficial. Simulated annealing is an efficient method for finding an approximation to a minimum value of a function of many independent variables. The function, usually called a "cost function" or "objective function" represents a quantitative measure of the "goodness" of some complex system.

The first step in the simulated annealing method is to generate an objective which has a value dependent upon a set of variables x1 to xm. The values of the variables x1 to xm are given a small random change and the objective is re-evaluated and compared to the old value of the objective. The change in the objective is referred to as .DELTA.obj.

If the change in the variables results in a lower objective value, then the new set of variables is always accepted. If the change in the variables results in a higher value for the objective, then the new set of variables may or may not be accepted. The decision to accept the new set of variables is determined with a given probability, the preferred probability of acceptance is: ##EQU1## where T is the simulated "temperature" of the system.

Hence for a given (.DELTA.obj), a high temperature T results in a high probability of acceptance of the change in the values of x1 to xm, where as at a low temperature T, there only is a small probability of acceptance. The temperature T is initially set to be quite high and is reduced slightly in each iteration of the annealing loop. The overall structure of a computer program, written in pseudo code, implementing the simulating annealing process is as follows: ##EQU2##

A flow chart for use in implementing the above is shown in FIG. 4. From the flow chart and the foregoing description, it is apparent that the procedure is not unlike the cooling of heated atoms to form a crystal. Hence the procedure is commonly known as "simulated annealing".

Initial Assignment of Dither Matrix Values

The preferred embodiment uses an initial assignment of dither matrix values that are determined by a simulated annealing process and which measure the "bunching" or "grouping" together of pixels of the same colour in the dithered image. By the same colour, it is meant that, for a particular intensity level, two separate dither cell values result in their respective pixels both being on, or both being off. It is likely that nearby pixels of the original image have the same or similar intensities; Therefore it is assumed that the original image has exactly the same intensity everywhere. For a given intensity in the original image, minimising a function of the form as shown in Equation 2 leads to a smoothly dithered pattern for that intensity. ##EQU3##

The function f is preferably one which decreases monotonically with distance, and dist() is a measure of the distance between points p1 and p2.

The preferred measure of distance dist() is the Euclidean distance between the points, but, because the dither matrix is generally repeated in the vertical and horizontal directions, dist() is measured modulo the size of the dither matrix.

If

p1=(x1,y1)

p2=(x2,y2)

are two arbitrary cells in the dither matrix at positions (x1,y1) and (x2,y2), then, for an (n.times.m) dither matrix, the preferred distance measure is: ##EQU4## where the mod function extends to negative numbers in accordance with the following relation, which holds for all x:

x mod m=(x-m)mod m (EQ 4)

For example, -3 mod 5=2 mod 5=2

The function f() is preferably chosen such that: ##EQU5## where .gamma. is a dispersion strength factor which is preferably equal to 1 although other positive values can be used.

Equation 2 gives the objective function for a single original image intensity level. To obtain an objective function which properly takes into account all possible image intensity levels, an objective function must be created which sums the quantity shown in Equation 2 for all possible intensities, as shown in Equation 6: ##EQU6## where w(intensity) is a weighting factor which assigns a relative importance to image quality at each intensity level. It will be assumed for the purposes of explanation of the preferred embodiment that each intensity level is treated equally and hence all the w(intensity) values are equal to 1.

Alternatively, if the intensity range is scaled to be in the range from 0 to 1, W.sub.I (intensity) can be of the following form: ##EQU7##

The preferred form of assignment leads to the final preferred objective function which is: ##EQU8##

To use simulated annealing to optimise a dither matrix, a method of specifying how to apply a random change (mutation) to a given dither matrix is required. The preferred random mutation method is to choose two (x,y) coordinates of the dither matrix using an unbiased random number generator. The entries of the dither matrix at these two places are then swapped. Whether this swap is accepted as the new solution, or rejected and therefore undone, is determined by the simulated annealing criteria previously discussed.

Theoretical considerations indicate that the anneal should begin at a temperature of infinity. In the preferred embodiment, this is achieved by randomly scrambling the dither matrix values by performing the above mentioned random swap process on a very large number of dither cells and accepting all swaps without evaluating the objective function.

Efficiency Methods in the Computation of the Initial Dither Matrix

Unfortunately, the time to compute the required medium or large sized initial dither matrix using the method of the preferred embodiment, in its present form, is excessive. Several methods can be adopted to reduce this time and will now be described.

For an (n.times.m) dither matrix, the number of entries in the dither matrix is;

#entries=n.times.m (EQ 9)

Equation 6 requires that each evaluation of the objective function has the following time order: ##EQU9##

For simulated annealing to work, every dither matrix entry must be swapped many times. If an `epoch` is defined to be approximately equal to a number of swaps corresponding to the number of cells in the array (ie. an epoch is approximately equal to n.times.m), then the simulated annealing process may typically take several hundred epochs. Therefore the time for completion is approximately as follows: ##EQU10##

For a 60.times.60 matrix for a 256 intensity level input image, annealed for 500 epochs, the number of iterations of the inner loop will be: ##EQU11##

Typical workstation computers can presently perform about 109 iterations per hour, so such a computer would take centuries to complete the above task for the defined array size.

Now, given that D(p) is the dither matrix value at point p, then the number of intensity levels for which two dither matrix locations p1 and p2 will have the same colour (as previously defined) is:

#intensifies p1, p2 have same colour=(#intensities-.vertline.D(p1)-D(p2).vertline.) (EQ 13)

Therefore Equation 8 is rearranged as follows: ##EQU12##

This removes the summation over all intensities of Equation 6 resulting in a substantial overall speedup.

The number of intensities (#intensities) is a constant and adding a constant to the objective function does not change the solution resulting from the optimisation. Therefore, this term can be removed from the objective function yielding: ##EQU13##

Further speedups are obtained by noting that the simulated annealing process only requires the computation of the change in the objective function due to the swapping of two dither matrix entries and computation of the objective is not actually required. Most of the points in Equation 15 are unaltered when two dither matrix entries are swapped and only pairs involving one of the two chosen points involved in the swap change their values. The contribution to Equation 15 of a dither matrix entry Dc being located at point pc (ob.sub.-- dp) is given by: ##EQU14##

Therefore, the change in the objective function given in Equation 15 due to swapping the dither matrix values located at the points p1 and p2 is given by:

.DELTA.objective=ob.sub.-- dp(D2,p1)+ob.sub.-- dp(D1, p2)-ob.sub.-- dp(D1,p1)-ob.sub.-- dp(D2,p2) (EQ 17)

where dither matrix value D1 starts at point p1 and moves to point p2, and dither matrix value D2 starts at point p2 and moves to point p1.

The evaluation of Equation 17 requires the examination of every point of the dither matrix four times, rather than examination of every pair of points of the dither matrix as required by Equation 15. This again results in a substantial speedup and Equation 16 and Equation 17 are preferably used in the creation of small and medium sized dither matrices. The analysis leading to Equation 16 and Equation 17 can also be applied to the more general Equation 6, leading to the more general formulation for Equation 16 given by: ##EQU15##

The time taken to create a dither matrix using Equation 18 is:

Time for Completion=#epochs.times.#evaluations per epoch.times.#time per evaluation =O(#epochs.times.n.sup.2 .times.m.sup.2) (EQ 19)

This compares favourably with Equation 11 and is practical for small to medium sized dither matrices (less than say 5,000 entries).

For large dither matrixes, further speedup is required to make the annealing practical. This is achieved by using simple approximations.

The computation involved in Equation 16 involves an inverse distance relationship. This involves a large number of points that contribute very little to the final result because they are a large distance away from pc which is the point of interest. The approximation involves neglecting the contribution of these points, and only using points which are within a small distance of pc. This imposes a circular window about pc with a radius designated to be "window.sub.-- radius",

Equation 16 can thus be approximated as follows: ##EQU16##

Use of Equation 20 is found, in practice, to provide inferior resulting dither matrices because of the discontinuity introduced when the dist() equals window.sub.-- radius. This discontinuity is remedied by using instead the following formula: ##EQU17## which removes this discontinuity and is used in the preferred embodiment when a larger dither matrix is required:

The function ob.sub.-- dp used in Equation 16 is defined for Equation 18 to be: ##EQU18##

The time to compute initial dither matrixes using Equation 21 or Equation 22 is then of the following order:

Time for Completion=O(#epochs.times.n.times.m.times.window.sub.-- radius.sup.2) (EQ 23)

This is found to be practical even for the creation of very large dither matrices. Reasonable values for window.sub.-- radius are found to be between 7 and 12.

In the present embodiment, Equation 21 is used to obtain an initial dither matrix of size 16.times.16 with each element taking one of 64 possible levels.

Formation of Preferred Embodiment

The formation of the preferred embodiment relies heavily upon the use of simulated annealing. As noted previously, in order to utilise the process of simulated annealing it is necessary to form an objective function. The objective function utilised in the preferred embodiment has two components. The first is a measure of the degree with which the pixel patterns on each level are spread out or distributed. The second factor is a penalising factor which penalises the alteration of the trajectory of paths eg. 13, 14, 16 of FIG. 3. Hence, the objective function involves these two competing factors and is represented as follows:

Objective=Spread out factor+Path alteration factor (EQ 24)

The spread out factor is similar to that disclosed above in relation to the formulation of the initial dither matrix and has the form: ##EQU19## where W.sub.I (intensity) is a weighting function which is a function having a relationship to the perceived magnitude by the human observer of each intensity level, with the preferable form being as set out in Equation 7.

Further, the function dist(p1,p2) is a distance measure between the points p1, p2 measured in a modulo sense with respect to the size of the dither matrix.

The path alteration factor is a measure of the amounts that a particular path deviates from a straight line. One such equation is as follows: ##EQU20##

In Equation 26, each point P of a path is represented by a three-tuple, having a x value, a y value, and a level value (l). The second weighting function w.sub.p (l.sub.1 -l.sub.2) represents a weight applied which is a function of the distance between the two levels l.sub.1 and l.sub.2. Many different weighting functions can be used, however, FIG. 5 shows the weighting function used with the preferred embodiment which restricts the summation to points which are spaced less than six intensity levels apart. This has the effect of substantially reducing the computational requirements necessary to calculate the Path alteration factor of Equation 26.

The use of the present form of the equation for the Spread out factor (EQ 25), results in an excessive time for evaluation. A number of substantial optimisations can be made to this equation, in addition to the application of a "window of influence" which further substantially reduces the computation time for the evaluation of the spread out factor. These optimisations are as previously set out in relation to the formulation of the initial dither matrix and should be utilised for anything but small matrix sizes. In a preferred embodiment, the equation utilised for the spreading out factor is as follows: ##EQU21## where window.sub.-- radius constitutes the window of influence and is preferably set to be seven pixels wide.

A three dimensional form of the initial dither matrix comprising a 16.times.16 array of X and Y values each having 64 possible levels was subjected to simulated annealing of a corresponding objective function of Equation 24 using the enclosed code on a Sun Microsystems Sparc 2 work station.

Although the present invention could start with any initial form of dither matrix, preferably, the initial dither matrix has some of the qualities 1 to 5 mentioned previously. Therefore, the initial matrix utilised is one constructed in accordance with the principles as outlined previously. The annealing process utilising the two competing objectives of Equation 24 was allowed to run for approximately four hours. Of course, larger dither matrix sizes and longer runs are more desirable, however, the time taken for completion of larger dither matrices will also increase substantially.

When the final series of bitmaps was used to dither a series of test images, it was found to produce superior results to other forms of dithering.

Referring now to FIG. 6, there is shown an apparatus for generating a halftone image utilising the series of bitmaps created with the preferred embodiment. A digital monochrome image composed of pixel values is generated by an input device 20 which can be a scanner device or a personal computer programmed to generate graphical output. The digital image is supplied as six bit pixel values representing one of 64 intensity levels. The x and y location of each pixel on a page is identified by two 16 bit words 28,29. Sixty-four, 16.times.16 bit half tone dot patterns 22, are generated as previously described and stored in bit pattern memory 24. A six bit level indicator 25 is used to select the requisite level and the lower four bits of the x and y address bits are used to select the relevant bit within a particular level. The output from the halftone bit pattern memory 24 is stored in a page memory 26 at the address specified by the x and y pixel addresses. When the bit map page memory 26 is full, the contents are supplied to a binary marking engine 27 such as a laser or ink jet printing device. Alternatively, if the input is synchronised with the marking engine, the output of the bit pattern memory is supplied to the marking engine without the need for page memory 26.

Appendix 1 included in this specification discloses a C-code program for the creation of a three dimensional matrix, with two dimensions being x and y and the third being the level, in accordance with the above embodiment. The enclosed code relies on a number of library routines, including a number of simulated annealing library routines, developed by the present applicant and utilised by the preferred embodiment and outlined in the manual entry set out in Appendix 2. The annealing codes are themselves set out in Appendix 3.

The foregoing describes only one embodiment of the present invention and modifications, obvious to those skilled in the art, can be made thereto without departing from the scope of the present invention.

For example, different formulations of the objective encompassing the spirit of the invention would be readily apparent to those skilled in the art in addition to different formulations of the weighting functions used in the preferred embodiment.

Additionally, the present invention can be readily applied to the display of colour images through the application of the preferred embodiment to each colour component of the image. Additionally, the extension of the invention to multi-level output devices will also be apparent to those skilled in the art. ##SPC1##

* * * * *

Current U.S. Class:	358/3.23; 358/3.14; 382/274; 382/285
Intern'l Class:	H04N 001/40
Field of Search:	395/108,118,119,120,124,125,127 358/429,455,456,457,459,465 382/169,237-239,270,274,285