Multi-level surround error diffusion

• US 8,274,705 B2
• Filed: 03/27/2009
• Issued: 09/25/2012
• Est. Priority Date: 03/27/2009
• Status: Active Grant

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Chang, Ching-Wei
• Primary Examiner(s): Tran, Dung
• Application Number:
  US12/412,648
• Publication Number:
  US 20100245924A1
• Time in Patent Office: 1,278 Days
• Field of Search: None
• US Class Current: 358/3.03
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

Machine-enabled methods of, and system, and processor readable media, embodiments for, tone quantization error diffusion comprising a first stage process and a second stage process. where pre-calibrated index tables may be applied by which quantized pixels may be expressed according to halftones.

Claims

1. A method of diffusing tone quantization error of a digital image comprising:

receiving a digital image having input pixel tone levels for one or more color channels according to i rows and j columns;

for alternate rows of pixels of the digital image;

quantizing an assigned pixel tone level of each pixel, or S_i,j, per color channel, in series j based on an integer downsizing, wherein the assigned tone level, or S_i,j, comprises an input tone value, or P_i,j, and, a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

determining for each pixel in series j of the alternate rows of pixels, and per color channel, a total quantization error, or D_i,j, based on the assigned pixel tone level of the pixel, or S_i,j, and the quantized assigned pixel tone level of the pixel, or Q_i,j, wherein the total quantization error, or D_i,j,comprises a partial tone quantization error, or N_i,j, and a remainder tone quantization error, or E_i,j; and

storing, per color channel, the remainder tone quantization error, or E_i,j; and

for rows of pixels interposed between the alternate rows of pixels of the digital image;

quantizing an assigned pixel tone level of each pixel, or S_i,j, per color channel, in series j based on an integer downsizing, wherein the assigned tone level, or S_i,j,comprises;

(a) an input tone value, or P_i,j;

(b) a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

(c) a sum of a weighted remainder tone quantization errors of two or more of the nearest neighbor pixels of the alternate rows comprising the sum;

w₂*E<sub>i−

1,j</sub>+w₅*E_i+1,j+w₆*E_i+1,j+1 and, at least one of;

(i) the sum;

w₁*E<sub>i−

1,j−

1</sub>+w₄*E<sub>i−

1,j−

1</sub> and (ii) the sum;

w₃*E<sub>i−

1,j+1</sub>+w₆*E_i+1,j+1, wherein w₁,w₂, w₃, w₄, w₅, and w₆, are weighted apportionments given to a set of tone quantization error remainders; and

determining, for each pixel in series j of the rows of pixels interposed between the alternate rows of pixels, and per color channel, a total quantization error, or D_i,j , based on the assigned pixel tone level of the pixel, or S_i,j, and the quantized assigned pixel tone level of the pixel, or Q _i,j, wherein the total quantization error, or D_i,j, comprises a partial tone quantization error, or N_i,j.

2. The method of diffusing tone quantization error of a digital image of claim 1 wherein the integer downsizing of an assigned pixel tone level comprises:

dividing the assigned pixel tone level of each pixel, or S_i,j, by 2^B+1 to generate a quotient having an integer component, wherein 2^B indicates a binary integer of length B, and wherein B is an integer value;

adding unity to the integer component of the quotient to generate a quantized tone value; and

testing to maintain the quantized tone value at least a value of unity and no more a value than 2^B ; and

wherein if the assigned pixel tone level of each pixel, or S _i,j, is an eight-bit integer, then B=4, and the quantized pixel tone level, or Q _i,j, is a four-bit integer.

3. The method of diffusing tone quantization error of a digital image of claim 2 wherein the total quantization error, or D_i,j, of the alternate rows of pixels, and the total quantization error, or D_i,j, of the rows of pixels interposed between the alternate rows of pixels are assigned the value of:

the assigned pixel tone level of each pixel, or S_i,j, plus (2^B+1), and less the value of the product of quantized pixel tone level, or Q _i,j, and (2^B+1).

4. The method of diffusing tone quantization error of a digital image of claim 1 wherein for rows of pixels interposed between the alternate rows of pixels of the digital image, the quantizing step comprises:

quantizing an assigned pixel tone level of each pixel, or S _i,j, in series j, of row i, based on an integer downsizing, wherein the assigned tone level, or S_j, comprises;

(a) an input tone value, or P_i,j;

(b) a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

(c) if remainder tone quantization errors E<sub>i−

1,j−

1</sub>, E<sub>i+1,j−

1</sub>, E<sub>i−

1,j+1</sub>, and E_i+1,j+1 are present, a sum of weighted remainder tone quantization errors of the nearest neighbor pixels of the alternate rows comprising;

the sum;

w₁*E<sub>i−

1,j−

1</sub>+w₂*E<sub>i−

1,j</sub>+w₃*E<sub>i−

1,j+1</sub>+w₄*E<sub>i+1,j−

1</sub>+w₅*E_i+1,j+w₆*E_i+1,j+1.

5. The method of diffusing tone quantization error of a digital image of claim 1 wherein w₁=⅛

;

w₂= 2/8;

w₃=⅛

;

w₄=⅛

;

w₅= 2/8; and

w₆=⅛

.

6. A system for producing image output comprising:

a image tone quantization module configured to;

input a digital image having input pixel tone levels for one or more color channels according to i rows and j columns;

for alternate rows of pixels of the digital image;

quantize an assigned pixel tone level of each pixel, or S_i,j, per color channel, in series j based on an integer downsizing, wherein the assigned tone level, or S_i,j, comprises an input tone value, or P_i,j, and, a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

determine for each pixel in series j, and per color channel, a total quantization error, or D_i,j, based on the assigned pixel tone level of the pixel, or S_i,j, and the quantized assigned pixel tone level of the pixel, or Q_i,j, wherein the total quantization error, or D_i,j, comprises a partial tone quantization error, or N_i,j, and a remainder tone quantization error, or E_i,j; and

store, per color channel, the remainder tone quantization error, or E_i,j; and

for rows of pixels interposed between the alternate rows of pixels of the digital image;

quantize an assigned pixel tone level of each pixel, or S _i,j, per color channel, in series j based on an integer downsizing, wherein the assigned tone level, or S comprises;

(a) an input tone value, or P_i,j;

(b) a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

(c) a sum of a weighted remainder tone quantization errors of two or more of the nearest neighbor pixels of the alternate rows comprising the sum;

w₂*E<sub>i−

1,j</sub>+w₅*E_i+1,j+w₆*E_i+1,j+1 and, at least one of;

(i) the sum;

w₁*E<sub>i−

1,j−

1</sub>+w₄*E<sub>i+1,j−

1</sub>; and

(ii) the sum;

w₃*E<sub>i−

1,j+1</sub> +w₆*E_i+1,j+1, wherein w₁,w₂, w₃, w₄, w₅, and w₆, are weighted apportionments given to a set of tone quantization error remainders; and

determine, for each pixel in series j, and per color channel, a total quantization error, or D_i,j, based on the assigned pixel tone level of the pixel, or S_i,j, and the quantized assigned pixel tone level of the pixel, or Q_i,j, wherein the total quantization error, or D_i,j, comprises a partial tone quantization error, or N_i,j.

7. The image tone quantization module of the system for producing image output of claim 6 wherein the image tone quantization module processing the integer downsizing of an assigned pixel tone level is configured to:

divide the assigned pixel tone level of each pixel, or S_i,j, by 2^B+1 to generate a quotient having an integer component, wherein 2^B indicates a binary integer of length B, and wherein B is an integer value;

add unity to the integer component of the quotient to generate a quantized tone value; and

test to maintain the quantized tone value at least a value of unity and no more a value than 2^B ; and

wherein if the assigned pixel tone level of each pixel, or S_i,j, is an eight-bit integer, then B=4, and the quantized pixel tone level, or Q_i,j, is a four-bit integer.

8. The image tone quantization module of the system for producing image output of claim 7 wherein the image tone quantization module processing the integer downsizing of an assigned pixel tone level is further configured to assign the total quantization error, or D_i,j, the value of:

the assigned pixel tone level of each pixel, or S_i,j, plus (2^B+1), and less the value of the product of quantized pixel tone level, or Q_i,j, and (2^B+1).

9. A processor readable non-transitory medium having processor executable instructions thereon which, when executed by a processor cause the processor to:

input a digital image having input pixel tone levels for one or more color channels according to i rows and j columns;

for alternate rows of pixels of the digital image;

quantize an assigned pixel tone level of each pixel, or S_i,j, per color channel, in series j based on an integer downsizing, wherein the assigned tone level, or S comprises an input tone value, or P_i,j, and, a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

determine for each pixel in series j, and per color channel, a total quantization error, or D_i,j, based on the assigned pixel tone level of the pixel, or S and the quantized assigned pixel tone level of the pixel, or Q_i,j, wherein the total quantization error, or D_i,j, comprises a partial tone quantization error, or N_i,j, and a remainder tone quantization error, or E_i,j; and

store, per color channel, the remainder tone quantization error, or E_i,j; and

for rows of pixels interposed between the alternate rows of pixels of the digital image;

quantize an assigned pixel tone level of each pixel, or S_i,j, per color channel, in series j based on an integer downsizing, wherein the assigned tone level, or S comprises;

(a) an input tone value, or P_i,j;

(b) a partial tone quantization error, or N<sub>i,j−

1</sub>, from the last quantized pixel in row i, if present; and

(c) a sum of a weighted remainder tone quantization errors of two or more of the nearest neighbor pixels of the alternate rows comprising the sum;

w₂*E<sub>i−

1,j</sub>+w₅*E_i+1,j+w₆*E_i+1,j+1 and, at least one of;

(i) the sum;

w₁*E<sub>i−

1,j−

1</sub>+w₄*E<sub>i+1,j−

1</sub> and (ii) the sum;

w₃*E<sub>i−

1,j+1</sub>+w₆*E<sub>i−

1,j+1</sub>;

wherein w₁,w₂, w₃, w₄, w₅, and w₆, are weighted apportionments given to a set of tone quantization error remainders; and

determine, for each pixel in series j, and per color channel, a total quantization error, or D_i,j, based on the assigned pixel tone level of the pixel, or S_i,j, and the quantized assigned pixel tone level of the pixel, or Q_i,j, wherein the total quantization error, or D_i,j, comprises a partial tone quantization error, or N_i,j.

10. The processor readable non-transitory medium having processor executable instructions thereon of claim 9 which, when executed by a processor cause the processor to:

divide the assigned pixel tone level of each pixel, or S_i,j, by 2^B+1 to generate a quotient having an integer component, wherein B is an integer value to indicate a binary integer of length B;

add unity to the integer component of the quotient to generate a quantized tone value; and

test to maintain the quantized tone value at least a value of unity and no more a value than 2^B ; and

wherein if the assigned pixel tone level of each pixel, or S_i,j, is an eight-bit integer, then B=4, and the quantized pixel tone level, or Q_i,j, is a four-bit integer.

11. The processor readable non-transitory medium having processor executable instructions thereon of claim 10 which, when executed by a processor cause the processor to assign the total quantization error, or D_i,j, the value of:

the assigned pixel tone level of each pixel, or S_i,j, plus (2^B+1), and less the value of the product of quantized pixel tone level, or Q_i,j, and (2^B+1).