Void and cluster apparatus and method for generating dither templates

• US 5,535,020 A
• Filed: 10/15/1992
• Issued: 07/09/1996
• Est. Priority Date: 10/15/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Ulichney, Robert A.
• Primary Examiner(s): IP, SHIK LUEN PAUL
• Application Number:
  US07/961,244
• Time in Patent Office: 1,363 Days
• Field of Search: 358/164, 358/32, 358/457, 358/460, 358/443, 358/445, 358/466, 358/453, 358/461, 358/463, 358/166, 358/138, 382/50, 382/52, 382/54, 348/564, 348/574, 348/625
• US Class Current: 358/3.13
• CPC Class Codes: H04N 1/4051 producing a dispersed dots halftone pattern, the dots having substantially the same size different sizes H04N1/4057
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

An apparatus for dithering an input image to produce an output array for representation on an output device is described. The apparatus includes an input device to store input image pixels having a first plurality of chrominance or luminance levels; a dithering system including a dither template including an M by N matrix of integer threshold values, the uniform distribution of threshold values throughout the dither template possessing homogeneous attributes. The apparatus further includes a normalizer unit for normalizing the threshold values of the dither template for storage in a dither matrix according to the first plurality of chrominance or luminance levels of the input image pixels and a second plurality of chrominance or luminance levels of the output array and a summation unit to add the input image pixel chrominance or luminance values to the normalized threshold values of the dither matrix. A quantizer unit is provided to adjust summation unit output to a closest output array chrominance or luminance levels of an output device.

Claims

1. An apparatus comprising:

a memory device having locations corresponding to M rows and N columns of elements, said elements forming a binary bit pattern comprising majority type elements and minority type elements;

means for iteratively selecting and moving said minority type elements and said majority type elements between element locations within said pattern memory device, said minority type elements selected in relation to neighboring minority type elements according to a first spatial characteristic, and said majority type elements selected in relation to neighboring minority type elements according to a second, different spatial characteristic, until said minority type elements and said majority type elements have been uniformly distributed to locations within said pattern memory device to provide a modified pattern of first and second type bit elements having homogeneous attributes.

2. The apparatus of claim 1 further comprising means for providing a modified convolution result for each element of said pattern, including:

multiplication means for multiplying a binary element value of elements neighboring said selected element by a spatial domain function to generate a filter result; and

summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

3. The apparatus of claim 1, wherein said first spatial characteristic and said different spatial characteristic are respective modified convolution results for each element in said pattern memory device.

4. The apparatus of claim 3, wherein said first spatial characteristic is a highest modified convolution result of said minority type elements with relation to said modified convolution results of other minority type elements within said pattern memory device.

5. The apparatus of claim 3, wherein said second, different spatial characteristic is a lowest modified convolution value of a majority type element with relation to said modified convolution results of each of other majority type elements within said pattern memory device.

6. The apparatus of claim 2, wherein said spatial domain function comprises an M×

N distribution of weighted values used to determine a relative contribution of each of said neighboring elements to the modified convolution result for each element.

7. The apparatus of claim 2, wherein said means for calculating said modified convolution result further comprises:

means for calculating the indices of said pattern element for which said modified convolution result is provided in a weighted distribution of values having corresponding indices, and for adjusting selected indices of said weighted distribution for portions of said weighted distribution falling outside of said pattern.

8. The apparatus of claim 7, wherein said means for adjusting further comprises:

means for wrapping around said portions of said weighted distribution falling outside of said pattern into corresponding opposite portions of said pattern.

9. An apparatus comprising:

means for storing a binary bit pattern having M rows and N columns comprising first type bit elements and second type bit elements, wherein one of said first and said second type bit elements is a majority type bit element, and the other one of said first and said second type bit element is a minority type bit element;

means for storing a dither template having M rows and N columns of integer threshold values in a template memory device having corresponding M rows and N columns of element locations;

means for iteratively selecting a minority type element from said corresponding location from said pattern, said minority type element at said corresponding location selected in relation to neighboring minority type elements according to a first spatial characteristic, said means for iteratively selecting a minority type element further comprising;

means for replacing said minority type element at said corresponding memory location with a majority type element to provide a second pattern array, and concurrently assigning a threshold value to a corresponding element location of said template memory; and

means for iteratively selecting a majority type element from said pattern, said majority type element selected in relation to neighboring minority type elements according to a second, different spatial characteristic, said means for iteratively selecting a majority type element further comprising;

means for replacing said majority type element at said corresponding pattern location with a minority type element to provide a third modified pattern, and concurrently assigning a threshold value to a corresponding element location of said template memory.

10. The apparatus of claim 9 further comprising means for providing a modified convolution result for each element of said pattern, including:

multiplication means for multiplying binary values of said elements neighboring said selected element by a spatial domain function to generate a filter result; and

summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

11. The apparatus of claim 10, wherein said first spatial characteristic and said different spatial characteristic are respective modified convolution results for each element in said pattern memory device.

12. The apparatus of claim 10, wherein said first spatial characteristic is a highest modified convolution result of said minority type elements with relation to said modified convolution results of other minority type elements within said pattern.

13. The apparatus of claim 10, wherein said second, different spatial characteristic is a lowest modified convolution value of a majority type element with relation to said modified convolution results of each of other majority type elements within said pattern.

14. The apparatus of claim 10, wherein said spatial domain function comprises an M×

N distribution of weighted values used to determine a relative contribution of a neighboring element to the modified convolution result for each element.

15. The apparatus of claim 10, further comprising:

means for calculating the indices of said pattern element for which said modified convolution result is provided in a weighted distribution of values having corresponding indices, and for adjusting selected indices of said weighted distribution for portions of said weighted distribution falling outside of said pattern.

16. The apparatus of claim 15, wherein said means for adjusting further comprises:

means for wrapping around said portions of said weighted distribution falling outside of said pattern into corresponding opposite portions of said pattern.

17. An apparatus comprising:

a dithering system responsive to input image pixels from an input device having a first plurality of representation levels, including a memory for storing a dither template comprising an M by N array of elements representing a uniform distribution of unique integer threshold values having homogeneous attributes;

means, responsive to said first plurality of representation levels, a second plurality of representation levels of an output device, and to said threshold values of said dither template, for providing a normalized dither matrix comprising normalized threshold values;

adding means for adding said input image pixel representation levels to said normalized threshold values to provide summation signals;

quantizer means for mapping said summation signals to said second plurality of representation levels to provide output pixels; and

means for storing said output pixels.

18. The apparatus of claim 17, further comprising an input device to store an input image comprising a plurality of input image pixels having said first plurality of representation levels.

19. The apparatus of claim 17, further comprising means for converting said output pixels to provide a representation of said input image on an output device.

20. The apparatus of claim 17, wherein said dithering system further comprises:

means for storing a pattern having M by N element locations, said elements of said pattern comprising an initial binary pattern of first type bit elements and second type bit elements, wherein either said first type bit element or said second type bit elements are majority type elements and wherein said other one of said first type bit elements or said second type bit elements are minority type elements, wherein said majority type elements and said minority type elements are related by first and second spatial characteristics.

21. The apparatus of claim 20, further comprising:

means for iteratively selecting and moving said minority types and majority types between element locations within said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, and said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, until said first and majority types have been moved to element locations to form a modified pattern with homogeneous attributes.

22. The apparatus of claim 20 further comprises:

means for selecting a minority type element location of said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including means for replacing said minority type element with said majority type element and concurrently assigning a unique threshold value to a corresponding integer location of said dither template; and

means for selecting a majority type element location of said pattern, said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, including means for replacing said majority type element with said minority type element and concurrently assigning another unique threshold value to a corresponding location of said dither template.

23. The apparatus of claim 20, further comprising means for providing a modified convolution result for each element of said pattern, including:

multiplication means for multiplying the binary element value of said neighboring elements by a spatial domain function to generate a filter result; and

summing means for adding said filter result of each of said neighboring elements to produce said modified convolution result for said element.

24. The apparatus of claim 20, wherein said first spatial characteristic and said second, different spatial characteristic are respective modified convolution results for each element in said pattern.

25. The apparatus of claim 20, wherein said first spatial characteristic is a highest modified convolution value of a minority type element relative to said modified convolution values of each of said minority type elements of said pattern.

26. The apparatus of claim 20, wherein said different spatial characteristic is a lowest modified convolution value of a majority type element relative to said modified convolution values of each of said elements majority type elements of said pattern.

27. The apparatus of claim 20, wherein said spatial domain function comprises an M×

N distribution of weighted values used to determine a relative contribution of a neighboring element to the modified convolution result for each element.

28. The apparatus of claim 20, further comprising:

means for calculating the indices of said pattern element for which said modified convolution result is provided in a weighted distribution of values having corresponding indices, and for adjusting selected indices of said weighted distribution for portions of said weighted distribution falling outside of said pattern.

29. The apparatus of claim 28, wherein said means for adjusting further comprises:

means for wrapping around said portions of said weighted distribution falling outside of said pattern into corresponding opposite portions of said pattern.

30. A method comprising the steps of:

a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern of first type bit elements and second type bit elements, wherein one of either said first type or second type bit elements are majority type elements, and wherein the other one of said first type or second type bit elements are minority type elements; and

b. iteratively selecting and moving said minority type elements and said majority type elements in said memory device between memory locations, wherein said minority type element location in memory is selected in relation to neighboring minority type elements according to a first spatial characteristic and said majority type element location in memory is selected in relation to neighboring minority type elements according to a second, different spatial characteristic; and

repeating said step of iteratively selecting and moving until said minority type elements and majority type elements are uniformly distributed at pattern locations in said memory device to provide a modified pattern having homogeneous attributes.

31. The method of claim 30, further including the step of calculating a modified convolution result for each element of said pattern, comprising the steps of:

a. multiplying the binary element value of each of said neighboring elements by a spatial domain function to generate a filter result for each of said neighboring elements; and

b. summing said filter result of said neighboring elements to produce said modified convolution result of said element.

32. The method of claim 31, wherein said first spatial characteristic and said second, different spatial characteristic are determined by calculating a modified convolution result for each element in said pattern.

33. The method of claim 31, wherein said first spatial characteristic is a highest convolution result of said minority type elements with relation to said convolution results of the other minority type elements of said pattern.

34. The method of claim 31, wherein said second, different spatial characteristic is a lowest convolution result of said majority type elements in relation to said convolution results of the other majority type elements of said pattern.

35. The method of claim 31, wherein said spatial domain function comprises an M×

N distribution of weighted values used to determine a relative contribution of a neighboring element to the modified convolution result for each element.

36. The method of claim 31, further comprising the step of:

calculating the indices of said pattern element for which said modified convolution result is provided in a weighted distribution of values having corresponding indices, and adjusting selected indices of said weighted distribution for portions of said weighted distribution falling outside of said pattern.

37. The method of claim 36, wherein said step of adjusting further comprises the step of:

wrapping around said portions of said weighted distribution falling outside of said pattern into corresponding opposite portions of said pattern.

47. The method of claim 31, wherein said step of providing a modified convolution result for each element of said pattern includes the step of calculating:

##EQU3## wherein F (x,y) provides said modified convolution result of said element at location x,y of said pattern, and p and q are indices to a spatial domain function, and adjusting p and q to provide p'"'"' and q'"'"' respectively.

38. A method comprising the steps of:

a. storing in a memory device a pattern having M rows and N columns of locations, said pattern comprising a binary pattern first type bit elements and second type bit elements, wherein said one of either said first type bit elements or said second type bit elements are majority type elements, and wherein the other one of said first type bit elements or said second type bit elements are minority type elements;

b. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with a majority type element and concurrently assigning a unique threshold value to a corresponding location of said dither template until no minority type elements remain in said pattern; and

c. selecting a majority type element location from said pattern, said majority type element location selected in relation to neighboring minority type elements according to said second, different spatial characteristic, including replacing said majority type element with said minority type element and concurrently assigning another unique threshold value to a corresponding location of said dither template until the number of minority type elements in said pattern exceeds the number of majority type elements in said pattern.

39. The method of claim 38 further comprising the steps of:

a. evaluating the bit type of the majority type element and the minority type element, wherein the type bit element of greatest number in said pattern is a majority type element, and the type bit element of least number in said pattern is a minority type element; and

b. selecting a minority type element location from said pattern, said minority type element location selected in relation to neighboring minority type elements according to said first spatial characteristic, including replacing said minority type element with said majority type element and concurrently assigning another unique threshold value to a corresponding location of said dither template until unique threshold values have been assigned to each dither template location.

40. The method of claim 38, further including the step of calculating a modified convolution result for each element of said pattern, comprising the steps of:

a. multiplying the binary element value of each of said neighboring elements by a spatial domain function to generate a filter result for each of said neighboring elements; and

b. summing said filter result of said neighboring elements to produce said modified convolution result of said element.

41. The method of claim 40, wherein said first spatial characteristic and said second, different spatial characteristic are determined by calculating a modified convolution result for each element in said pattern.

42. The method of claim 40, wherein said first spatial characteristic is a highest convolution result of said minority type elements with relation to said convolution results of the other minority type elements of said pattern.

43. The method of claim 40, wherein said second, different spatial characteristic is a lowest convolution result of said majority type elements in relation to said convolution results of the other majority type elements of said pattern.

44. The method of claim 40, wherein said spatial domain function comprises an M×

N distribution of weighted values used to determine a relative contribution of a neighboring element to the modified convolution result for each element.

45. The method of claim 40, further comprising the step of:

calculating the indices of said pattern element for which said modified convolution result is provided in a weighted distribution of values having corresponding indices, and adjusting selected indices of said weighted distribution for portions of said weighted distribution falling outside of said pattern.

46. The method of claim 45, wherein said step of adjusting further comprises the step of:

wrapping around said portions of said weighted distribution falling outside of said pattern into corresponding opposite portions of said pattern.

48. The method of claim 46 wherein the step of adjusting p and q to provide p'"'"' and q'"'"' is calculated by the respective equations:

space="preserve" listing-type="equation">p'"'"'=(M+x-p) modulo M

space="preserve" listing-type="equation">q'"'"'=(N+y-q) modulo N

49. The method of claim 46, wherein said spatial domain function is a symetric Gaussian function, given by the equation:

space="preserve" listing-type="equation">f(p,q)=Ae.sup.-(p.spsp.2.sup./2σ

p.spsp.2.sup.+q.spsp.2.sup./2σ

q.spsp.2.sup.)

wherein that p² +q² is the distance from said element for which F(x,y) is provided to a neighboring element, σ

_p =σ

_q =σ

, and A is a constant.