Threshold matrix-employed error diffusion image conversion method

• US 6,108,450 A
• Filed: 11/17/1997
• Issued: 08/22/2000
• Est. Priority Date: 11/19/1996
• Status: Expired due to Term

• Current Assignee: Brother Kogyo Kabushiki Kaisha (Brother Industries Limited)
• Original Assignee: Brother Kogyo Kabushiki Kaisha (Brother Industries Limited)
• Inventors: Ueda, Masashi
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US08/971,189
• Time in Patent Office: 1,009 Days
• Field of Search: 382/237, 382/254, 382/270-273, 358/455-457, 358/463, 358/465
• US Class Current: 382/237
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

An input density for a subject pixel position (x, y) is retrieved in S230. A modified density value I'"'"'(x, y) is calculated in S240 based on the input density value I(x, y) and the error e(x, y) stored in the corresponding error buffer. Then, in S250, a discrimination value for the subject pixel position (x, y) is retrieved from the bilevel threshold value matrix Mat2( ) which is produced through the blue noise characteristic method. One of two threshold values is assigned to the retrieved discrimination value. Thus, a threshold value T is determined for the subject pixel (x, y). Then, an output density value O(x, y) is determined based on the modified density value I'"'"'(x, y) and the threshold value T in S260, S270, and S280. Then, an error value E(x,y) is calculated based on the output density value O(x, y) and the modified density value I'"'"'(x, y). The error value E(x,y) is distributed to the error buffer 16 in S300 dependently on the error distribution matrix Bat( ). The above-described process is performed onto all the pixels of the input image.

Claims

1. A method for converting a continuous tone image into a pseudo-halftone image, the method comprising the steps of:

preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value

receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein the threshold matrix is prepared to define the threshold values which are determined according to a blue noise mask producing manner.

2. A method as claimed in claim 1, wherein the error-distribution binary conversion process includes the steps of:

comparing a density value of each pixel on the continuous tone image with a threshold value defined by a corresponding element of the threshold matrix;

converting the density value of the pixel into a binary value based on the compared result; and

diffusing an error, generated between the binary value and the density value, to neighboring pixels.

3. A method as claimed in claim 2, wherein the comparing step includes the steps of:

modifying the density value of each pixel with errors distributed from already-converted neighboring pixels; and

comparing the modified density value with the corresponding threshold value.

4. A method as claimed in claim 1, wherein the threshold matrix includes a bilevel threshold matrix, each element in the threshold matrix defining either a first threshold value or a second threshold value different from the first threshold value.

5. A method as claimed in claim 4, wherein the threshold matrix preparing step includes the steps of:

preparing an initial matrix which has a plurality of elements, the plurality of elements being two-dimensionally arranged, each element having either a first value and a second value so that the first and second values being randomly arranged in the initial matrix; and

rearranging the first and second values in the initial matrix, thereby converting the initial matrix into the bilevel threshold matrix having a desired distribution state of the first and second values.

6. A method as claimed in claim 5, wherein the rearranging step includes the step of repeatedly performing a replacing step for replacing the first value at one element with the second value while replacing the second value at one element with the first value.

7. A method as claimed in claim 6, wherein the replacing step includes the steps of:

calculating, for each element, density of neighboring elements that have a value equal to the value of the subject element;

determining, for the first value, a first maximum density element that has a maximum neighboring element density among all the elements that have the first value;

determining, for the second value, a second maximum density element that has a maximum density among several elements that have the second value; and

setting the second value into the first maximum density element and setting the first value into the second maximum density element.

8. A method as claimed in claim 5, wherein the threshold matrix preparing step further includes the step of producing a multilevel threshold matrix based on the bilevel threshold matrix, the multilevel threshold matrix having the several elements arranged two-dimensionally, each element having either one of more than two different values, and

wherein the multilevel threshold matrix producing step includes the step of repeatedly performing a first setting step for setting a value in one of several elements in the multilevel threshold matrix to be produced, the value being decremented one by one as the first setting operation is repeated.

9. A method as claimed in claim 8, wherein the first setting step includes the steps of:

replacing, with the second value, the first value in the bilevel threshold matrix at an element located within a tight cluster of elements having the first value;

setting the total number of the first values left in the bilevel threshold matrix prior to the replacement operation onto an element of the multilevel threshold matrix that corresponds to the element of the bilevel threshold matrix, at which the first value is replaced with the second value.

10. A method as claimed in claim 9, wherein the multilevel threshold matrix producing step further includes the step of repeatedly performing a second setting step for setting a value in one of the several elements in the multilevel threshold matrix to be produced, the value being incremented one by one as the second setting operation is repeated.

11. A method as claimed in claim 10, wherein the second setting step includes the steps of:

replacing, with the first value, the second value in the bilevel threshold matrix at an element located within a void where elements having the first value are thinly dispersed;

setting the total number of the first values left in the bilevel threshold matrix after the replacement operation onto an element of the multilevel threshold matrix that corresponds to the element of the bilevel threshold matrix, at which the second value is replaced with the first value.

12. A method as claimed in claim 1, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to an error-diffusion binary conversion process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while diffusing generated errors to neighboring pixels.

13. A method as claimed in claim 1, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to a minimized average error process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels.

14. A method for converting a continuous tone image into a pseudo-halftone image, the method comprising the steps of:

preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein the threshold matrix preparing step includes the steps of;

preparing a uniform density matrix provided with several elements which are arranged two-dimensionally and which have equal density values;

subjecting all the elements of the uniform density matrix to an error-distribution binary conversion process to convert the density values of the elements into binary values while distributing generated errors to neighboring elements, thereby producing a binary value matrix based on the binary values produced for at least a part of all the elements; and

producing the threshold matrix based on the binary values located at least within a part of the binary value matrix.

15. A method as claimed in claim 14 wherein the error-distribution binary conversion process includes the steps of:

comparing a density value of each element on the uniform density matrix with a predetermined threshold value;

converting the density value of the pixel into a binary value based on the compared result; and

distributing an error generated between the binary value and the density value to neighboring elements.

16. A method as claimed in claim 15, wherein the comparing step includes the steps of:

modifying the density value of each element with errors distributed from already-converted neighboring elements; and

comparing the modified density value with the predetermined threshold value.

17. A method as claimed in claim 14, wherein the uniform density matrix preparing step prepares a plurality of uniform density matrices for a plurality of density values, each uniform density matrix being provided with several elements which are arranged two-dimensionally and which have a corresponding density value, and

wherein the error-distribution binary conversion step successively subjects the plurality of uniform density matrices to the error-distribution binary conversion process to convert the density values of the elements in each uniform density matrix into binary values while referring to binary values at corresponding elements on another already-processed uniform density matrix and while distributing generated errors to neighboring elements on the same uniform density matrix, thereby producing a plurality of binary value matrices.

18. A method as claimed in claim 17, wherein the threshold matrix preparing step further includes the step of producing a bilevel threshold matrix based on a binary value matrix which is produced through subjecting the uniform density matrix having a desired density to the error-distribution binary conversion process.

19. A method as claimed in claim 17, wherein the threshold matrix preparing step further includes the step of producing a threshold matrix through accumulating, at each element position, the binary values of all the produced plurality of binary value matrices and determining, based on the accumulated result, the threshold value of an element located at a corresponding position in the threshold matrix.

20. A method as claimed in claim 17, wherein the error-distribution binary conversion step subjects each uniform density matrix to the error-distribution binary conversion process to convert the density value at each element in the uniform density matrix into a binary value dependent on a binary value of a corresponding element on another uniform density matrix which has been already processed and which has a density value closest to that of the uniform density matrix.

21. A method as claimed in claim 20, wherein the density value of each element on each uniform density matrix is converted compulsively into a first value with a generated error being distributed to neighboring elements when a corresponding element on a closest uniform density matrix, which has been already processed and which has a density value closest to that of the uniform density matrix, has been converted to the first value.

22. A method as claimed in claim 17, wherein the error-distribution binary conversion step subjects each uniform density matrix to the error-distribution binary conversion process to convert the density value at each element in the uniform density matrix into a binary value dependent on both a binary value at a corresponding element on a higher-closest uniform density matrix, which has been already processed and which has a density value closest to and higher than that of the uniform density matrix, and a binary value of a corresponding element on a lower-closest uniform density matrix, which has been already processed and which has a density value closest to and lower than that of the uniform density matrix.

23. A method as claimed in claim 22, wherein the density value of each element on each uniform density matrix is converted compulsively into a first value with a generated error being distributed to neighboring elements when both of a corresponding element on the lower-closest uniform density matrix and a corresponding element on the upper-closest uniform density matrix have been converted to the first value, and

wherein the density value of each element on each uniform density matrix is converted compulsively into a second value with a generated error being distributed to neighboring elements when both of a corresponding element on the lower-closest uniform density matrix and a corresponding element on the upper-closest uniform density matrix have been converted to the second value.

24. A method as claimed in claim 14, wherein the threshold matrix producing step includes the step of producing a bilevel threshold matrix based on the binary values produced for a part of all the elements.

25. A method as claimed in claim 14, wherein the error-distribution binary conversion process includes the steps of:

comparing a density value of each pixel on the continuous tone image with a threshold value defined by a corresponding element of the threshold matrix;

converting the density value of the pixel into a binary value based on the compared result; and

diffusing an error, generated between the binary value and the density value, to neighboring pixels.

26. A method as claimed in claim 25, wherein the comparing steps includes the steps of:

modifying the density value of each pixel with errors distributed from already-converted neighboring pixels; and

comparing the modified density value with the corresponding threshold value.

27. A method as claimed in claim 14, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to an error-diffusion binary conversion process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while diffusing generated errors to neighboring pixels.

28. A method as claimed in claim 14, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to a minimized average error process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated error to neighboring pixels.

29. A method for converting a continuous tone image into a pseudo-halftone image, the method comprising the steps of:

preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein the threshold matrix preparing step includes the steps of;

storing, into a storage device, discrimination values indicative of the threshold values defined for all the elements in the threshold matrix, data amount of each discrimination value being smaller than that of a corresponding threshold value; and

producing a threshold value for each element position based on a discrimination value read from the storage device at a corresponding position.

30. A method as claimed in claim 29, wherein the storing step includes the step of storing, in a table, the discrimination values of all the elements in an order of the amount of the discrimination values together with information on corresponding element positions, and wherein the threshold value production step includes the step of dividing the table into several groups in correspondence with the total number of kinds of threshold values to be used and to set one threshold value onto element positions stored at each group in the table.

31. A method as claimed in claim 29, wherein the threshold matrix is prepared to define the threshold values which are determined according to a blue noise mask producing manner.

32. A method as claimed in claim 29, wherein the threshold matrix preparing step further includes the steps of:

preparing a uniform density matrix provided with several elements which are arranged two-dimensionally and which have equal density values;

subjecting all the elements of the uniform density matrix to an error-distribution binary conversion process to convert the density values of the elements into binary values while distributing generated errors to neighboring elements, thereby producing a binary value matrix based on the binary values produced for at least a part of all the elements; and

producing the threshold matrix based on the binary values located at least within a part of the binary value matrix, the discrimination values indicative of the threshold values in the threshold matrix being stored in the storage device.

33. A method as claimed in claim 29, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to an error-diffusion binary conversion process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while diffusing generated errors to neighboring pixels.

34. A method as claimed in claim 29, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to a minimized average error process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels.

35. A method for converting a continuous tone image into a pseudo-halftone image, the method comprising the steps of:

preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein each pixel of the continuous tone image has a density in a range defined between a lowest density value S and a highest density value L, where S is equal to or higher than zero, and L is higher than S, and

wherein the threshold matrix preparing step prepares the threshold matrix so that n kinds of different threshold values are distributed in the threshold matrix where n is an integer in a range from two to the total number of the elements, the n kinds of threshold values including at least a first threshold value H1 and a second threshold value H2, the first threshold value H2 being higher than the first threshold value H1, the number of the elements having the first threshold value H1 and the number of the elements having the second threshold value H2 being higher than those of elements having each of other threshold values, a sum T of the first and second threshold values H1 and H2 satisfying an inequality T>

L.

36. A method as claimed in claim 35, wherein the first threshold value H1 satisfies the following formula:

space="preserve" listing-type="equation">H1≈

S+(L-S)/4.

37. A method as claimed in claim 35, wherein the second threshold value H2 is preferably set to a value equal to or slightly smaller than the highest density L.

38. A method as claimed in claim 35, wherein the threshold matrix preparing step includes the step of adjusting at least one of the threshold values H1 and H2 before the error-distribution binary conversion process.

39. A method as claimed in claim 35, wherein the threshold matrix is prepared so that only the first and second threshold values H1 and H2 are distributed in the threshold matrix.

40. A method as claimed in claim 35, wherein the threshold matrix is prepared to define the threshold values which are determined according to a blue noise mask producing manner.

41. A method as claimed in claim 35, wherein the threshold matrix preparing step includes the steps of:

preparing a uniform density matrix provided with several elements which are arranged two-dimensionally and which have equal density values;

subjecting all the elements of the uniform density matrix to an error-distribution binary conversion process to convert the density values of the elements into binary values while distributing generated errors to neighboring elements, thereby producing a binary value matrix based on the binary values produced for at least a part of all the elements; and

producing the threshold matrix based on the binary values located at least within a part of the binary value matrix.

42. A method as claimed in claim 35, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to an error-diffusion binary conversion process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while diffusing generated errors to neighboring pixels.

43. A method as claimed in claim 35, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to a minimized average error process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels.

44. A method for converting a continuous tone image into a pseudo-halftone image, the method comprising the steps of:

preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein the threshold matrix preparing step prepares the threshold matrix so that n different threshold values are distributed in the threshold matrix where n is an integer in a range from two to the total number of the elements, the numbers of elements having the respective different threshold values being different from one another.

45. A method as claimed in claim 44, wherein the threshold matrix preparing step prepares the threshold matrix so that first and second threshold values are distributed in the threshold matrix, the number of first elements having the first threshold value being different from the number of second elements having the second threshold value.

46. A method as claimed in claim 45, wherein the threshold matrix preparing step includes the step of setting a rate of the number of the first elements relative to the number of the second elements.

47. A method as claimed in claim 46, the rate is set in accordance with a rate of an area of each density in the continuous tone image with respect to the total area of the continuous tone image.

48. A method as claimed in claim 47, the rate is set in correspondence with a density whose area is the minimum among all the areas for the respective densities.

49. A method as claimed in claim 48, wherein the second threshold value is higher than a 50% level of a highest density inputtable for the continuous tone image and the first threshold value is lower than a 50% level of the highest density inputtable for the continuous tone image, the number of the first elements being different from that of the second elements.

50. A method as claimed in claim 49, wherein the number of the second elements is higher than the number of the first elements.

51. A method as claimed in claim 50, wherein the rate of the number of the second elements is about 75% with respect to the total number of the elements.

52. A method as claimed in claim 44, wherein the threshold matrix is prepared to define the threshold values which are determined according to a blue noise mask producing manner.

53. A method as claimed in claim 44, wherein the threshold matrix preparing step includes the steps of:

preparing a uniform density matrix provided with several elements which are arranged two-dimensionally and which have equal density values;

subjecting all the elements of the uniform density matrix to an error-distribution binary conversion process to convert the density values of the elements into binary values while distributing generated errors to neighboring elements, thereby producing a binary value matrix based on the binary values produced for at least a part of all the elements; and

producing the threshold matrix based on the binary values located at least within a part of the binary value matrix.

54. A method as claimed in claim 44, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to an error-diffusion binary conversion process with using the threshold matrix, to thereby convert the density values of the pixels into binary values while diffusing generated errors to neighboring pixels.

55. A method as claimed in claim 44, wherein the error-distribution binary conversion process step subjects all the pixels of the continuous tone image to a minimized average error process with using the threshold matrix, to thereby convert the density values of the pixels into binary values of the pixels into binary values while distributing generated errors to neighboring pixels.

56. A data recording medium for storing data of a program for converting a continuous tone image into a pseudo-halftone image, the program comprising:

a program for preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

a program for receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

a program for subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein the threshold matrix is prepared to define the threshold values which are determined according to a blue noise mask producing manner.

57. A data recording medium for storing data of a program for converting a continuous tone image into a pseudo-halftone image, the program comprising:

a program of preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

a program of receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

a program of subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels;

wherein the threshold matrix preparing program includes;

a program of preparing a uniform density matrix provided with several elements which are arranged two-dimensionally and which have equal density values;

a program of subjecting all the elements of the uniform density matrix to an error-distribution binary conversion process to convert the density values of the elements into binary values while distributing generated errors to neighboring elements, thereby producing a binary value matrix based on the binary values produced for at least a part of all the elements; and

a program of producing the threshold matrix based on the binary values located at least within a part of the binary value matrix.

58. A data recording medium for storing data of a program for converting a continuous tone image into a pseudo-halftone image, the program comprising:

a program of preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

a program of receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

a program of subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels;

wherein the threshold matrix preparing program includes;

a program of storing, into a storage device, discrimination values indicative of the threshold values defined for all the elements in the threshold matrix, data amount of each discrimination value being smaller than that of a corresponding threshold value; and

a program of producing a threshold value for each element position based on a discrimination value read from the storage device at a corresponding position.

59. A data recording medium for storing data of a program for converting a continuous tone image into a pseudo-halftone image, the program comprising:

a program of preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

a program of receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

a program of subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein each pixel of the continuous tone image has a density in a range defined between a lowest density value S and a highest density value L, where S is equal to or higher than zero, and L is higher than S, and

wherein the threshold matrix preparing program prepares the threshold matrix so that n kinds of different threshold values are distributed in the threshold matrix where n is an integer in a range from two to the total number of the elements, the n kinds of threshold values including at least a first threshold value H1 and a second threshold value H2, the first threshold value H2 being higher than the first threshold value H1, the number of the elements having the first threshold value H1 and the number of the elements having the second threshold value H2 being higher than those of elements having each of other threshold values, a sum T of the first and second threshold values H1 and H2 satisfying an inequality T>

L.

60. A data recording medium for storing data of a program for converting a continuous tone image into a pseudo-halftone image, the program comprising:

a program of preparing a threshold matrix which has several elements which are two-dimensionally arranged, each element defining one threshold value;

a program of receiving data of a continuous tone image desired to be converted into a pseudo-halftone image, the continuous tone image having a plurality of pixels which are two-dimensionally arranged, each pixel having one density value; and

a program of subjecting all the pixels of the continuous tone image to an error-distribution binary conversion process using the threshold matrix, to thereby convert the density values of the pixels into binary values while distributing generated errors to neighboring pixels,

wherein the threshold matrix preparing program prepares the threshold matrix so that n different threshold values are distributed in the threshold matrix where n is an integer in a range from two to the total number of the elements, the numbers of elements having the respective different threshold values being different from one another.