Method and an apparatus for elimination of color Moiré

• US 7,023,576 B1
• Filed: 05/09/2000
• Issued: 04/04/2006
• Est. Priority Date: 05/09/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Phase One A/S
• Inventors: Knudsen, Niels V., Andersen, Casper Find, Jønsson, Michael
• Primary Examiner(s): NGUYEN, ANH-VINH THI
• Application Number:
  US09/567,278
• Time in Patent Office: 2,156 Days
• Field of Search: 382/169, 382/176, 382/203, 382/252, 382/262, 382/167, 382/164, 382/261, 382/300, 382/282, 382/254, 382/264, 382/305, 358/3.07, 358/1.9, 358/518, 358/520, 358/525, 358/533, 358/535, 348/578, 375/240.03, 345/592, 708/490
• US Class Current: 358/1.9
• CPC Class Codes: H04N 1/52 Circuits or arrangements for halftone screening

Abstract

A digital image processing method for eliminating Moiré in a digital image divided into pixels holding pixel component values includes selecting a first pixel and defining a pixel window around the selected first pixel. Then, a set of pixels are identified which consist of pixels within the window that have pixel component values within a pixel component value range that is related to the selected first pixel. A pixel component value is calculated based on corresponding pixel component values of pixels in the set of pixels and then this calculated pixel component value is allocated to the selected first pixel.

Claims

1. A digital image processing method of eliminating Moiré

in a pixilated digital image wherein each pixel is associated with at least a first pixel component value and a second pixel component value of different type, the method comprising;

selecting a pixel;

defining a pixel window around the selected pixel;

identifying a set of pixels consisting of pixels within the pixel window having a first pixel component value within a range that is related to the first pixel component value of the selected pixel;

calculating a new second pixel component value for the selected pixel using corresponding second pixel component values of pixels in the set of pixels; and

allocating the calculated new second pixel component value to the selected pixel.

2. A method according to claim 1, wherein said calculating comprises calculating a weighted average of second pixel component values of pixels in the set of pixels.

3. A method according to claim 2, wherein weights of the weighted average are identical to one.

4. A method according to claim 2, further comprising calculating hue values for a selected pixel (x₀,y₀) in the CIELAB color space:

$a^{*}=500<br><br>\left({\left(\frac{x}{x_N}\right)}^{\frac{1}{3}}-{\left(\frac{y}{y_N}\right)}^{\frac{1}{3}}\right)$$b^{*}=200<br><br>\left({\left(\frac{y}{y_N}\right)}^{\frac{1}{3}}-{\left(\frac{z}{z_N}\right)}^{\frac{1}{3}}\right)$$\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\underset{\underset{\_}{\_}}{M}<br><br>\left(\begin{array}{c}r\\ g\\ b\end{array}\right);<br><br>\left(\begin{array}{c}{x}_N\\ y_N\\ z_N\end{array}\right)=\underset{\underset{\_}{\_}}{M}<br><br>\left(\begin{array}{c}255\\ 255\\ 255\end{array}\right)$$\underset{\underset{\_}{\_}}{M}=\left(\begin{array}{ccc}0<br><br>\text{,}<br><br>431& 0<br><br>\text{,}<br><br>342& 0<br><br>\text{,}<br><br>178\\ 0<br><br>\text{,}<br><br>222& 0<br><br>\text{,}<br><br>707& 0<br><br>\text{,}<br><br>071\\ 0<br><br>\text{,}<br><br>020& 0<br><br>\text{,}<br><br>130& 0<br><br>\text{,}<br><br>939\end{array}\right)$

and for a macro square centered around the selected pixel with a first side length, calculating;

VarMak(x₀,y₀)=std.dev(MDC_ab(x_i,y_i))

and for a micro square centered around the selected pixel with a second side length, calculating;

VarMik(x₀,y₀)=std.dev(MDC_ab(x_i,y_i)),

wherein;

${\mathrm{MDC}}_{\mathrm{ab}}<br><br>\left(x_0,y_0\right)=\frac{1}{N<br><br>\left(x_0,y_0,d\right)}<br><br>\underset{i=1}{\overset{N<br><br>\left(x_0,y_0,d\right)}{\sum <br><br>}}<br><br>{\mathrm{\Delta <br><br>C}}_{{\mathrm{ab}}_i}$

Δ

C<sub>α

b</sub>=√

{square root over ((α

*(x₀,y₀)−

α

(x_i,y_i))²+(b*(x₀,y₀)−

b*(x_i,y_i))²)}{square root over ((α

*(x₀,y₀)−

α

(x_i,y_i))²+(b*(x₀,y₀)−

b*(x_i,y_i))²)}{square root over ((α

*(x₀,y₀)−

α

(x_i,y_i))²+(b*(x₀,y₀)−

b*(x_i,y_i))²)}{square root over ((α

*(x₀,y₀)−

α

(x_i,y_i))²+(b*(x₀,y₀)−

b*(x_i,y_i))²)}

and calculating a threshold value;

$t<br><br>\left(x,y\right)=t<br><br>\frac{\mathrm{VarMak}<br><br>\left(x,y\right)}{\mathrm{VarMik}<br><br>\left(x,y\right)},$

and setting a flag V_c(x₀,y₀) is set according to the following;

V_c(x,y)=1 when VarMak(x,y)<

t(x,y)

V_c(x,y)=0 otherwise.

5. A method according to claim 4, further comprising substituting red and blue pixel component values of the selected pixel (x₀,y₀) with originally or interpolated pixel component values when the flag V_c(x₀,y₀) is equal to zero.

6. A method according to claim 4, wherein the first side length is 13, the second side length is 4, and t is 4.6.

7. A method according to claim 4, further comprising:

for a selected pixel (x₀,y₀) calculating $k_1=\left(\begin{array}{ccc}2& -1& -1\\ -1& 2& -1\\ -1& -1& 2\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$k_2=\left(\begin{array}{ccc}-1& 2& -1\\ -1& 2& -1\\ -1& 2& -1\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$k_3=\left(\begin{array}{ccc}-1& -1& 2\\ -1& 2& -1\\ 2& -1& -1\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$k_4=\left(\begin{array}{ccc}-1& -1& -1\\ 2& 2& 2\\ -1& -1& -1\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$\mathrm{and}$$\begin{array}{c}\mathrm{std}.\mathrm{dev}<br><br>\left(k\right)=<br><br>\frac{1}{N}<br><br>\sqrt{\underset{i=1}{\overset{4}{\sum <br><br>}}<br><br>{\left(k_i-\stackrel{\_}{k}\right)}^2}\\ \stackrel{\_}{k}=<br><br>\frac{1}{4}<br><br>\underset{i=1}{\overset{4}{\sum <br><br>}}<br><br>k_i\end{array}$

and setting a flag V_s(x₀,y₀) to one when std.dev(k) is less than 2 and otherwise setting the flag V_s(x₀,y₀) to zero;

substituting red and blue pixel component values of the selected pixel (x₀,y₀) with originally or interpolated pixel component values when the flag V_s(x₀,y₀) is equal to zero; and

combining the flags V_s(x₀,y₀) and V_c(x₀,y₀) into a flag V(x₀,y₀) so that;

V(x₀,y₀)=1 when V_c(x₀,y₀)=1 and V_s(x₀,y₀)=1;

V(x₀,y₀)=0 otherwise,

and substituting red and blue pixel component values of the selected pixel (x₀,y₀) with the originally or interpolated pixel component values when the flag V(x₀,y₀) is equal to zero.

8. A method according to claim 1, wherein the pixel window is centered around the selected pixel.

9. A method according to claim 1, wherein the pixel window is a rectangle.

10. A method according to claim 9, wherein the pixel window is a square.

11. A method according to claim 1, further comprising:

for a selected pixel (x₀,y₀) calculating $k_1=\left(\begin{array}{ccc}2& -1& -1\\ -1& 2& -1\\ -1& -1& 2\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$k_2=\left(\begin{array}{ccc}-1& 2& -1\\ -1& 2& -1\\ -1& 2& -1\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$k_3=\left(\begin{array}{ccc}-1& -1& 2\\ -1& 2& -1\\ 2& -1& -1\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$k_4=\left(\begin{array}{ccc}-1& -1& -1\\ 2& 2& 2\\ -1& -1& -1\end{array}\right)*\left(\begin{array}{ccc}g<br><br>\left(x_{-1},y_{-1}\right)& g<br><br>\left(x_0,y_{-1}\right)& g<br><br>\left(x_1,y_{-1}\right)\\ g<br><br>\left(x_{-1},y_0\right)& g<br><br>\left(x_0,y_0\right)& g<br><br>\left(x_1,y_0\right)\\ g<br><br>\left(x_{-1},y_1\right)& g<br><br>\left(x_0,y_1\right)& g<br><br>\left(x_1,y_1\right)\end{array}\right)$$\mathrm{and}$$\begin{array}{c}\mathrm{std}.\mathrm{dev}<br><br>\left(k\right)=<br><br>\frac{1}{N}<br><br>\sqrt{\underset{i=1}{\overset{4}{\sum <br><br>}}<br><br>{\left(k_i-\stackrel{\_}{k}\right)}^2}\\ \stackrel{\_}{k}=<br><br>\frac{1}{4}<br><br>\underset{i=1}{\overset{4}{\sum <br><br>}}<br><br>k_i\end{array}$

and setting a flag V_s (x₀,y₀) to one when std.dev(k) is less than 2 and otherwise setting the flag to zero.

12. A method according to claim 11, further comprising substituting red and blue pixel component values of the selected pixel (x₀,y₀) with originally or interpolated pixel component values when the flag V_s(x₀,y₀) is equal to zero.

13. A method according to claim 1, further comprising applying a smoothing filter along boundaries between regions of pixels with modified pixel values and pixels with recorded and interpolated values for elimination of an abrupt change from modified pixel values {overscore (r)}_m, {overscore (b)}_m to un-modified pixel values r, b across a boundary:

{overscore (r)}_final(x,y)=α

{overscore (r)}_m(x,y)+(1−

α

)r(x,y)

{overscore (b)}_final(x,y)=α

{overscore (b)}_m(x,y)+(1−

α

)b(x,y)$\mathrm{\alpha <br><br>}=\frac{N_{\mathrm{do}}}{N_{\mathrm{do}}+N_{\mathrm{don}\text{'}"\text{'}"\text{'}<br><br>t}}$

wherein N_do is a number of pixels within a smoothing window with modified pixel values and N_don'"'"'t is a number of pixels within the smoothing window with un-modified pixel values.

14. A method according to claim 1, further comprising:

selecting a second pixel; and

interpolating a color (A) value of the selected second pixel by calculating the color (A) value from color values of a selected set of pixels that are positioned adjacent to the selected second pixel, the influence of at least one pixel abutting the selected second pixel being significantly reduced whereby blurring of distinct features of the digital image is substantially avoided.

15. A method according to claim 14, further comprising:

forming a first set of pixels that are positioned adjacent to the selected second pixel;

calculating a first variation value of color values of the pixels of the first set of pixels;

forming a second set of pixels that are positioned adjacent to the selected second pixel;

calculating a second variation value of color values of the pixels of the second set;

comparing the first and second variation values; and

calculating the color (A) value from color values of the set of pixels with the lowest variation value.

16. A method according to claim 15, wherein color (B) values of the set of pixels with the lowest variation value are included in the calculation of the color (A) value.

17. A method according to claim 15, wherein color (B) values are included in the calculation of variation values of the first and second set of pixels, respectively.

18. A method according to claim 17, wherein each of said calculating variation values of the first and second set of pixels, respectively, comprises:

calculating the ratio between color (A) values and color (B) values of abutting pixels of the respective set of pixels;

calculating a mean value of the calculated ratios; and

calculating the variation value of the respective set of pixels as a sum of an absolute value of a difference between each of the ratios and the mean value.

19. A method according to claim 15, wherein said calculating the color (A) value comprises:

calculating a weighted sum of color (B) values of the set of pixels with the lowest variation value;

calculating a weighted sum of color (A) values of the set of pixels with the lowest variation value; and

calculating the color (A) by multiplying a color (B) value of the selected second pixel with a ratio between the weighted sums of color (A) and color (B) values.

20. A method according to claim 14, wherein the color (A) value is calculated form an arbitrary number of colors.

21. A method according to claim 14, wherein the selected set of pixels comprises a plural number of selected sets of pixels.

22. A method according to claim 21, wherein the selected sets of pixels are arranged in rows and columns parallel to rows and columns of the pixels in the image.

23. A method according to claim 21, wherein the selected sets of pixels are arranged in rows at an angle of approximately 45 degrees relative to rows and columns of the pixels in the image.

24. A method according to claim 21, wherein the selected sets of pixels are arranged in rows at an angle of approximately 45 degrees relative to rows and columns of the pixels in the image and in rows and columns parallel to the rows and columns of the pixels in the image.

25. A method according to claim 21, wherein the selected sets of pixels are arranged in rows at an arbitrary angle relative to rows and columns of the pixels in the image.

26. A method according to claim 21, wherein the number of selected sets of pixels is 4.

27. An image processing apparatus with a processor that is adapted for performing a method according to claim 1.

28. An image recording system with a processor that is adapted for performing a method according to claim 1.

29. A software program residing in a computer readable medium for performing a method according to claim 1.

30. A data carrier residing in a computer readable medium for performing a method according to claim 1.