Method and system for digital printing by density scheduling

1. A method for digital printing represented as a matrix I, comprising:

forming a sequence of matrices P k with entries 0 or 1 where a 1 at some entry in some P k represents that this pixel will be printed at stage k;

constructing as sequences of matrices I k with entries in [0, 1], so that I 0 =I;

determining, when considering all pixels in I k for all successive values of k, a next pixel having a largest weight indicating that said next pixel is to be printed next, so that P k+1 differs from P k by a zero at said next pixel in P k being replaced by a 1 at the same position in P k+1 ;

printing said pixel;

replacing the value of said pixel in I k by a 0 thus forming I k+1 ; and

incrementing the value of k, until enough pixels have been printed to represent the overall darkness of I by the printed image.

2. The method according to claim 1 , wherein with each printing of a pixel, an order of printing of remaining pixels is redefined.

3. The method according to claim 1 , further comprising reordering the pixels to be printed with each printing iteration.

4. The method according to claim 1 , wherein an original image is denoted as said matrix I={I(i, j)}, where 1≦i≦Himage and 1≦j≦Vimage, where Himage is a number of pixels along a horizontal direction of the image and where Vimage is a number of pixels along a vertical direction of the image, and

wherein each element I(i, j) of I is a real number between 0 and 1 where 0 represents “white”, 1 represents “black” and intermediate values represent levels of grey.

5. The method according to claim 4 , wherein said matrix forming comprises:

setting k=0 and defining P 0 as the constant Himage by Vimage zero matrix.

6. The method according to claim 5 , further comprising:

with each iteration of redetermining, replacing k by k+1; and

setting I k =I k−1 and P k =P k−1 except for a single pixel.

7. The method according to claim 6 , further comprising:

determining whether there has been a change in neighborhood V(i, j, I k ) of pixel (i,j) in matrix I k ;

computing all weighted averages W(i, j, I k ) of grey values in the neighborhood V(i,j,I k ) of pixel (i,j,) in matrix I k not computed previously and setting W(i, j, I k )=W(i, j, I k−1 ) if W(i, j, I k ) is not computed again, such that when k=1, all said weighted averages are computed, and for k>1, only said weighted averages which have been modified at a previous iteration are computed.

8. The method according to claim 7 , further comprising:

ordering all W(i, j, I k ) by decreasing order; and

considering Max(k) as a larger value of all W(i, j, I k )s.

9. The method according to claim 8 , further comprising:

determining whether W(i, j, I k )=Max(k).

10. The method according to claim 9 , further comprising:

for all pairs (i, j) such that W(i, j, I k )=Max(k), replacing P k (i, j)=0 with P k (i, j)=1 in P k , and I k (i, j)=I(i, j) with I k (i, j)=I(i, j)−1 in I k .

11. The method according to claim 9 , further comprising:

computing GreyTotal(k)=Σ i,j P k (i, j).

12. The method according to claim 11 , wherein if GreyTotal(k)<GreyTotal, then a next iteration is begun.

13. The method according to claim 11 , further comprising:

if GreyTotal≦GreyTotal(k), and |GreyTotal−GreyTotal(k)|<|GreyTotal−GreyTotal(k−1)|, then set P=P k .

14. The method according to claim 11 , further comprising:

if GreyTotal≦GreyTotal(k), and |GreyTotal−GreyTotal(k)|≧|GreyTotal−GreyTotal(k−1)|, then set P=P k−1 .

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

providing a multi-tone printer, such that a lightest grey darker than Max(k) is printed, and I k (i, j)=I(i, j)−1 is replaced by I k (i, j)=I(i, j) which represents a multibit grey level being printed.

16. The method according to claim 9 , further comprising:

compensating for isolated pixels by making weights in V(i, j, M) depend on what is printed at (i, j).

17. The method according to claim 1 , wherein a total number of black dots being printed is variable.

18. The method according to claim 1 , further comprising:

encoding the set of pixels to be printed after half-toning, in the matrix P={P(i, j)}, where 1≦i≦Himage and 1≦j≦Vimage, where Himage is a number of pixels along a horizontal direction of the image and where Vimage is a number of pixels along a vertical direction of the image, and

wherein each element P(i,j) of P has a value of either 0 or 1, where “0” represents “white” and “1”represents “black”.

19. The method according to claim 18 , further comprising:

given a Himage by Vimage matrix M with entries in [0, 1], selecting a neighborhood V(i, j, M) for each (i, j), whose shape and size selectively depends or not on (i, j), and a set of weights associated to all pixels in V(i, j, M).

20. The method according to claim 19 , wherein W(i, j, M) represents a weighted average of the elements of M in V(i, j, M), and GreyTotal=Σ i,j I(i, j).

21. A method of printing, comprising:

forming a matrix of pixels;

determining an order of printing of said pixels, said determining including finding a weight of said pixels and printing a pixel having a highest weight; and

reordering the remaining pixels and printing a pixel having the greatest weight of the remaining pixels until all pixels have been printed;

wherein the pixels are printed in turn based on the darkness of the local image being printed.

22. A method for digital printing, comprising:

forming a sequence of matrices P k with entries 0 or 1 where a 1 at some entry in some P k represents that this pixel will be printed at stage k;

constructing as sequences of matrices I k with entries in [0, 1], so that I 0 =I;

determining, for a plurality of pixels in I k for all successive values of k, a next pixel having a largest weight indicating that said first pixel is to be printed next;

printing said pixel; and

determining for each pixel of the remaining ones of pixels of said plurality of pixels a printing order of said remaining pixels such that subsequent pixels of said remaining ones of pixels of said plurality of pixels having a largest weight among the remaining pixels, are subsequently printed;

wherein the pixels are printed in turn based on the darkness of the local image being printed.

23. A system for printing, comprising:

means for forming a matrix of pixels;

means for determining an order of printing of said pixels, said determining including finding a weight of said pixels and printing a pixel having a highest weight; and

means for reordering the remaining pixels and printing a pixel having the greatest weight of the remaining pixels until all pixels have been printed;

wherein the pixels are printed in turn based on the darkness of the local image being printed.

24. The system according to claim 23 , wherein with each printing of a pixel, an order of printing of remaining pixels is redefined.

25. The system according to claim 23 , wherein said reordering means reorders the pixels to be printed with each printing iteration.

26. The system according to claim 23 , wherein an original image is denoted as said matrix I={I(i, j)}, where 1≦i≦Himage and 1≦j≦Vimage, where Himage is a number of pixels along a horizontal direction of the image and where Vimage is a number of pixels along a vertical direction of the image, and

wherein each element I(i, j) of I is a real number between 0 and 1 where 0 represents “white”, 1 represents “black” and intermediate values represent levels of grey.

27. The system according to claim 26 , wherein said matrix forming means includes:

means for setting k=0 and defining P 0 as the constant Himage by Vimage zero matrix.

28. The system according to claim 27 , further comprising:

with each iteration of redetermining, means for replacing k by k+1; and

means for setting I k =I k−1 and P k =P k−1 except for a single pixel.

29. The system according to claim 28 , further comprising:

means for determining whether there has been a change in neighborhood V(i, j, I k ) of pixel (i,j) in matrix I k ; and

means for computing all weighted averages W(i, j, I k ) of grey values in neighborhood V(i,j,I k ) of pixel (i,j) in matrix I k not computed so far and setting W(i, j, I k )=W(i, j, I k−1 ) if W(i, j, I k ) is not computed again, such that when k=1, all said weighted averages are computed, and for k>1, only said weighted averages which have been modified at a previous iteration are computed.

30. The system according to claim 29 , further comprising:

means for ordering all W(i, j, I k ) by decreasing order; and

means for considering Max(k) as a larger value of all W(i, j, I k )s.

31. The system according to claim 30 , further comprising:

means for determining whether W(i, j, I k )=Max(k).

32. The system according to claim 31 , further comprising:

for all pairs (i, j) such that W(i, j, I k )=Max(k), means for replacing P k (i, j)=0 with P k (i, j)=1 in P k , and I k (i, j)=I(i, j) with I k (i, j)=I(i, j)−1 in I k .

33. The system according to claim 31 , further comprising:

means for computing GreyTotal(k)=Σ i,j P k (i, j).

34. The system according to claim 33 , wherein if GreyTotal(k)<GreyTotal, then a next iteration is begun.

35. The system according to claim 33 , further comprising:

if GreyTotal≦GreyTotal(k), and |GreyTotal−GreyTotal(k) 1 <|GreyTotal−GreyTotal(k−1)|, means for setting P=P k .

36. The system according to claim 33 , further comprising:

if GreyTotal≦GreyTotal(k), and |GreyTotal−GreyTotal(k)|≧|GreyTotal−GreyTotal(k−1)|, means for setting P=P k−1 .

37. The system according to claim 36 , further comprising:

a multi-tone printer for printing, such that a lightest grey darker than Max(k) is printed, and I k (i, j)=I(i,j)−1 is replaced by I k (i, j)=I(i, j) which represents a multibit grey level being printed.

38. The system according to claim 31 , further comprising:

means for compensating for isolated pixels by making the weights in V(i, j, M) depend on what is printed at (i, j).

39. The system according to claim 23 , wherein a total number of black dots being printed is variable.

40. The system according to claim 23 , further comprising:

means for encoding the set of pixels to be printed after half-toning, in the matrix P={P(i, j)}, where 1≦i≦Himage and 1≦j≦Vimage, where Himage is a number of pixels along a horizontal direction of the image and where Vimage is a number of pixels along a vertical direction of the image,

wherein each element P(i,j) of P has a value of either 0 or 1, where “0” represents “white” and “1” represents “black”.

41. The system according to claim 40 further comprising:

given a Himage by Vimage matrix M with entries in [0, 1], means for selecting a neighborhood V(i, j, M) for each (i, j), whose shape and size selectively depends or not on (i, j), and a set of weights associated to all pixels in V(i, j, M).

42. The system according to claim 41 , wherein W(i, j, M) represents a weighted average of the elements of M in V(i, j, M), and GreyTotal=Σ i,j I(i, j).

43. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of printing, said method comprising:

forming a matrix of pixels;

determining an order of printing of said pixels, said determining including finding a weight of said pixels and printing a pixel having a highest weight; and

reordering the remaining pixels and printing a pixel having the greatest weight of the remaining pixels until all pixels have been printed;

wherein the pixels are printed in turn based on the darkness of the local image being printed.

44. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of printing, said method comprising:

forming a sequence of matrices P k with entries 0 or 1 where a 1 at some entry in some P k means that this pixel will be printed at stage k;

constructing as sequences of matrices I k with entries in [0, 1], so that I 0 =I;

determining, when considering all pixels in I k for all successive values of k, a next pixel having a largest weight indicating that said next pixel is to be printed next, so that P k+1 differs from P k by a zero at said next pixel in P k being replaced by a 1 at the same position in P k+1 ;

printing said pixel;

replacing the value of said pixel in I k by a 0 thus forming I k+1 ; and

incrementing the value of k, until enough pixels have been printed to represent the overall darkness of 1 by the printed image.