# US 2004/0080790 A1 · Dither mask creating method and creating device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0080790 A1
- Document ID: US20040080790A1
- Status: Published application
- Kind: A1
- Application number: 10/468,308
- Filed: 2003-08-19
- Published: 2004-04-29
- Earliest claimed: 2001-03-02
- Assignees: Dai Nippon Printing Co., Ltd.
- Inventors: Yoshito Abe
- Web page: https://patentgrep.com/patent/US20040080790A1

## CPC

- H04N 1/4055: {producing a clustered dots or a size modulated halftone pattern}
- H04N 1/405: Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A dither mask for conversion of a continuous-tone image into a halftone image is generated using a computer. A pixel array, having a size that is in accordance with the dither mask to be generated, is defined and is partitioned into a plurality of blocks (S1). Initial pixel values are determined in a manner such that the frequencies of occurrence of pixel values will be substantially uniform in each individual block (S2). A pair of exchange target pixels are selected at random from among the pixels in a single block and function values of a predetermined evaluation function that indicates a characteristic of the pixel value configuration of the pixels in this block are computed for the two cases of the case where pixel values are exchanged among the exchange target pixels and the case where the exchange is not carried out (S3), and these function values are compared to judge whether or not exchange should be performed (S4, S5, S6). If it has been judged that exchange should be performed, the exchange is performed (S7). The above processes are executed repeatedly for all blocks until a predetermined condition is met (S8, S9, S10).

## Claims

### Claim 1

A method of generating a dither mask (10) which is used for conversion of a continuous-tone image (100) into a halftone image (200), said method comprising the steps of:
a preparation step (S1) for defining a pixel array (M) having a size in accordance with a dither mask to be generated and partitioning said pixel array into a plurality of blocks (B(u, v));
an initial pixel value determination step (S2) for determining an initial pixel value (f(i, j)) for respective pixels which are members of said pixel array, in a manner such that frequencies of occurrence of pixel values within a predetermined numerical value range that is required by said dither mask become substantially uniform in each individual block;
a function value computation step (S3) for selecting a plurality of exchange target pixels at random from among pixels in a single block and computing function values of a predetermined evaluation function that indicates a characteristic of a pixel value configuration of pixels in said single block for two cases of performing exchange of pixel values among said plurality of exchange target pixels and not performing said exchange;
an exchange judgment step (S4, S5, S6) for judging whether or not the exchange of pixel values among said plurality of exchange target pixels should be performed by comparing said function values for the two cases; and
a pixel value exchange step (S7) for performing a process of the exchange of pixel values among said plurality of exchange target pixels, when it has been judged in said exchange judgment step that the exchange should be performed;
wherein said function value computation step, said exchange judgment step and said pixel value exchange step are executed repeatedly for all blocks until a predetermined condition is met (S8, S9, S10) and the dither mask is generated by pixel values of said pixel array that is finally obtained.

### Claim 2 (depends on 1)

The dither mask generating method according to claim 1, wherein:
in the exchange judgment step, a judgment that exchange should be performed is made if a function value of the evaluation function approaches a predetermined target value as a result of performing the exchange (S4), and if a function value of the evaluation function does not approach a predetermined target value as a result of performing the exchange (S4), a judgment that exchange should be performed is made based on a predetermined exchange probability (S5, S6) and said exchange probability is decreased in accordance with the number of times of repetitions (S9).

### Claim 3 (depends on 2)

The dither mask generating method according to claim 2, wherein:
an initial value of a temperature parameter Tn (0<Tn) and a temperature decrease factor α (0<α<1) are set in advance, a process of renewing a value of the temperature parameter Tn with a new value of Tn×α is performed each time the number of repetitions increases, and the exchange probability P is determined by the formula of P=exp(−|ΔE|/Tn), where ΔE is a difference in function values for the two cases.

### Claim 4 (depends on 1, 2, 3)

The dither mask generating method according to any of claims 1 through 3, wherein:
a function, which indicates a difference of pixel values of a plurality of pixels that are positioned near each other, is used as the evaluation function and exchange judgment is made based on whether or not a function value approaches a target value of 0 as a result of the exchange.

### Claim 5 (depends on 4)

The dither mask generating method according to claim 4, wherein:
a function, which determines “an absolute value of a difference between pixel values of a noted pixel and another pixel adjacent said noted pixel” for each of all pixels within a single block as being a noted pixel and then indicates a sum of determined values, is used as the evaluation function.

### Claim 6 (depends on 4)

The dither mask generating method according to claim 4, wherein:
a function, which determines “an absolute value of two-dimensional Laplacian for a pixel in the case where a pixel value configuration within a single block is expressed by a function f (x, y) in a two-dimensional xy-coordinate system” for each of all pixels within a single block and then indicates a sum of determined values, is used as the evaluation function.

### Claim 7 (depends on 4)

The dither mask generating method according to claim 4, wherein:
a two-dimensional xy-coordinate system having an x-axis and a y-axis as coordinate axes is defined on the pixel array and a function, which determines “with respect to a noted pixel, a sum of absolute values of one-dimensional Laplacians for four axial directions of the x-axis direction, the y-axis direction, and two axial directions that form a 45° angle with respect to the coordinate axes” for each of all pixels within a single block and then indicates a total sum of determined sums, is used as the evaluation function.

### Claim 8 (depends on 7)

The dither mask generating method according to claim 7, wherein:
a function expressed by the following formula is used as the evaluation function:
E=Σi=0 to I−1, j=0 to J−1
4 [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i - 1 , j ) - f ⁡ ( i + 1 , j ) [RightBracketingBar] + [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i , j - 1 ) - f ⁡ ( i , j + 1 ) [RightBracketingBar] + [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i - 1 , j - 1 ) - f ⁡ ( i + 1 , j + 1 ) [RightBracketingBar] + [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i + 1 , j - 1 ) - f ⁡ ( i - 1 , j + 1 ) [RightBracketingBar]
wherein
E: function value of the evaluation function
I: total number of rows of a pixel array that makes up a single block
J: total number of columns of the pixel array that makes up the single block
i: row number of a noted pixel in the single block (0, 1, 2, . . . , I−1)
j: column number of the noted pixel in the single block (0, 1, 2, . . . , J−1)
f(i, j): pixel value of a pixel of i-th row and j-th column.

### Claim 9 (depends on 1, 2, 3)

The dither mask generating method according to any of claims 1 through 3, wherein:
a function, which indicates a difference of pixel values of a plurality of pixels that are positioned near each other, is used as the evaluation function and exchange judgment is made based on whether or not a function value approaches a target value of ∞ as a result of the exchange.

### Claim 10 (depends on 9)

The dither mask generating method according to claim 9, wherein:
a function, which determines “an absolute value of a difference between pixel values of a noted pixel and another pixel positioned near said noted pixel” for each of all pixels within a single block as being a noted pixel and then indicates a sum of determined values, is used as the evaluation function.

### Claim 11 (depends on 10)

The dither mask generating method according to claim 10, wherein:
a function, which defines, for a noted pixel, a plurality of near pixels that are positioned near said noted pixel, determines “a sum of absolute values of differences between pixel values of said noted pixel and said near pixels,” for each of all pixels within a single block as being a noted pixel, and then indicates a total sum of determined sums, is used as the evaluation function.

### Claim 12 (depends on 11)

The dither mask generating method according to claim 11, wherein:
a function expressed by the following formula is used as the evaluation function:
E=Σi=0 to I−1, j=0 to J−1Σk=−q to q, m=−q to q|f(i, j)−f(i+k, j+m)|
wherein
E: function value of the evaluation function
I: total number of rows of a pixel array that makes up a single block
J: total number of columns of the pixel array that makes up the single block
i: row number of a noted pixel in the single block (0, 1, 2, . . . , I−1)
j: column number,of the noted pixel in the single block (0, 1, 2, . . . , J−1)
k: separation from the noted pixel in the row direction (number of pixels)
m: separation from the noted pixel in the column direction (number of pixels)
q: parameter that sets a range of near pixels (number of pixels)
f(i, j): pixel value of a pixel of i-th row and j-th column.

### Claim 13 (depends on 11)

The dither mask generating method according to claim 11, wherein:
a function expressed by the following formula is used as the evaluation function:
E=Σi =0 to I−1, j=0 to J−1Σk2+m2≦r2|f(i, j)−f(i+k, j+m)|
wherein
E: function value of the evaluation function
I: total number of rows of a pixel array that makes up a single block
J: total number of columns of the pixel array that makes up the single block
i: row number of a noted pixel in the single block (0, 1, 2, . . . , I−1)
j: column number of the noted pixel in the single block (0, 1, 2, . . . , J−1)
k: separation from the noted pixel in the row direction (number of pixels)
m: separation from the noted pixel in the column direction (number of pixels)
r: parameter that sets a range of near pixels
f(i, j): pixel value of a pixel of i-th row and j-th column
Σk2+m2≦r2 indicates a total sum concerning pixels within a circular region of radius r.

### Claim 14 (depends on 1, 2, 3)

The dither mask generating method according to any of claims 1 through 3, wherein:
a function, which indicates a difference of a pixel value configuration in a single block that makes up the dither mask and a pixel value configuration of a priorly prepared primitive design image, is used as the evaluation function and exchange judgment is made based on whether or not a function value approaches a target value of 0 as a result of the exchange.

### Claim 15 (depends on 14)

The dither mask generating method according to claim 14, wherein:
a primitive design image, which has a same pixel array as a pixel array of a single block that makes up the dither mask, is prepared, an absolute value of a difference between pixel values of a pair of corresponding pixels at mutually corresponding positions in the respective pixel arrays is determined for all pixels inside the single block and a function that indicates a sum of determined values is used as the evaluation function.

### Claim 16 (depends on 15)

The dither mask generating method according to claim 15, wherein:
a function expressed by the following formula is used as the evaluation function:
E=Σi=0 to I−1, j=0 to J−1|f(i, j)−g (i, j)|
wherein
E: function value of the evaluation function
I: total number of rows of a pixel array that makes up a single block
J: total number of columns of the pixel array that makes up the single block
i: row number of a noted pixel in the single block (0, 1, 2, . . . , I−1)
j: column number of the noted pixel in the single block (0, 1, 2, . . . , J−1)
f(i, j): pixel value of a pixel of i-th row and j-th column of the dither mask
g(i, j): pixel value of a pixel of i-th row and j-th column of the primitive design image.

### Claim 17 (depends on 14, 15, 16)

The dither mask generating method according to any of claims 14 through 16, wherein:
in addition to the evaluation function, a function, which indicates a difference of pixel values of a plurality of pixels that are positioned near each other, is used as a sub-evaluation function and whether or not a function value of said sub-evaluation function approaches 0 as a result of the exchange is added as a condition of the exchange judgment.

### Claim 18 (depends on 17)

The dither mask generating method according to claim 17, wherein:
a function, which determines “an absolute value of a difference between pixel values of a noted pixel and another pixel adjacent said noted pixel” for each of all pixels within a single block as being a noted pixel and then indicates a sum of determined values, is used as the sub-evaluation function.

### Claim 19 (depends on 17)

The dither mask generating method according to claim 17, wherein:
a function, which determines “an absolute value of two-dimensional Laplacian for a pixel in the case where a pixel value configuration within a single block is expressed by a function f (x, y) in a two-dimensional xy-coordinate system” for each of all pixels within a single block and then indicates a sum of determined values, is used as the sub-evaluation function.

### Claim 20 (depends on 17)

The dither mask generating method according to claim 17, wherein:
a two-dimensional xy-coordinate system having an x-axis and a y-axis as coordinate axes is defined on the pixel array and a function, which determines “with respect to a noted pixel, a sum of absolute values of one-dimensional Laplacians for four axial directions of the x-axis direction, the y-axis direction, and two axial directions that form a 45° angle with respect to the coordinate axes” for each of all pixels within a single block and then indicates a total sum of determined sums, is used as the sub-evaluation function.

### Claim 21 (depends on 20)

The dither mask generating method according to claim 20, wherein:
a function expressed by the following formula is used as the sub-evaluation function:
Esub=Σi=0 to I−1, j=0 to J−1
5 [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i - 1 , j ) - f ⁡ ( i + 1 , j ) [RightBracketingBar] + [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i , j - 1 ) - f ⁡ ( i , j + 1 ) [RightBracketingBar] + [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i - 1 , j - 1 ) - f ⁡ ( i + 1 , j + 1 ) [RightBracketingBar] + [LeftBracketingBar] 2 ⁢ f ⁡ ( i , j ) - f ⁡ ( i + 1 , j - 1 ) - f ⁡ ( i - 1 , j + 1 ) [RightBracketingBar]
wherein
Esub: function value of the sub-evaluation function
I: total number of rows of a pixel array that makes up a single block
J: total number of columns of the pixel array that makes up the single block
i: row number of a noted pixel in the single block (0, 1, 2, . . . , I−1)
j: column number of the noted pixel in the single block (0, 1, 2, . . . , J−1)
f(i, j): pixel value of a pixel of i-th row and j-th column.

### Claim 22 (depends on 21)

The dither mask generating method according to claim 21, wherein:
a synthetic evaluation function G=We·E+Ws·Esub (where We and Ws are parameters that indicate weight), which is defined as a linear sum of an evaluation function E and a sub-evaluation function Esub, is used and the exchange judgment is made based on whether or not a function value of said synthetic evaluation function G approaches a target value of 0 as a result of the exchange.

### Claim 23 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)

The dither mask generating method according to any of claims 1 through 22, wherein:
in order to generate a dither mask to be used for conversion of a continuous-tone image with W-bit pixel values to a halftone image with 1-bit pixel values,
in the preparation step, block partitioning is performed in a manner such that each individual block contains one or a plurality of unit cells with 2w pixels,
in the initial pixel value determination step, a total of (2w−1) types of pixel values, corresponding to pixel values in a range of 0 to (2w−2) or pixel values in a range of 1 to (2w−1), are made to be respectively written into predetermined positions for (2w−1) pixels among the 2w pixels of each unit cell, and for a remaining odd pixel, any one pixel value among the total of (2w−1) pixel values is made to be written.

### Claim 24 (depends on 23)

The dither mask generating method according to claim 23, wherein:
frequencies of occurrence of pixel values that are respectively written into the odd pixel of each of the plurality of unit cells are made substantially uniform for the total of (2w−1) pixel values.

### Claim 25 (depends on 23, 24)

The dither mask generating method according to claim 23 or 24, wherein:
a unit cell comprising a square pixel array in which 2w/2 pixels are aligned along one side is defined.

### Claim 26 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)

The dither mask generating method according to any of claims 1 through 22, wherein:
in order to generate a dither mask to be used for conversion of a continuous-tone image with W-bit pixel values to a halftone image with 1-bit pixel values,
in the preparation step, block partitioning is performed in a manner such that each individual block contains one or a plurality of unit cells with (2w−1) pixels,
in the initial pixel value determination step, a total of (2w−1) types of pixel values, corresponding to pixel values in a range of 0 to (2w−2) or pixel values in a range of 1 to (2w−1), are made to be respectively written into predetermined positions of each unit cell.

### Claim 27 (depends on 26)

The dither mask generating method according to claim 26, wherein:
a unit cell with a rectangular pixel array arrangement having (2w−1) pixels is defined.

### Claim 28 (depends on 27)

The dither mask generating method according to claim 27, wherein:
W=8 and a unit cell with a rectangular pixel array arrangement, selected from the group consisting of 1×255, 3×85, 5×51, 15×17, 17×15, 51×5, 85×3, or 255×1, is defined.

### Claim 29 (depends on 1)

The dither mask generating method according to claim 1, wherein:
a Simulated Annealing Method is used in making judgment in the exchange judgment step.

### Claim 30 (depends on 1)

The dither mask generating method according to claim 1, wherein:
a process using a Discrete Combinatory Optimization Method, selected from the group consisting of Genetic Algorithms, Great Deluge Algorithm, Ant Colony Algorithm, and Tabu Search Algorithm, is executed to gradually vary a pixel value configuration and make pixel values finally converge.

### Claim 31

A dither mask generating device, which generates a dither mask (10) for conversion of a continuous-tone image (100) into a halftone image (200), said dither mask generating device comprising:
a mask storage unit (1) which stores a pixel array (M) along with pixel values of individual pixels, said pixel array having a size that is in accordance with the dither mask to be generated;
a block partitioning unit (2) which partitions the pixel array stored in said mask storage unit into a plurality of blocks (B(u, v));
a random number generating unit (3) which has a function of generating predetermined random numbers and executes an initial pixel value determination process, by which for each pixel that is a member of said pixel array, pixel values (f(i, j)) are allocated randomly in a manner such that frequencies of occurrence of the pixel values within a predetermined numerical value range that is deemed necessary for the dither mask are substantially uniform in each individual block, and an exchange target pixel selection process, by which a plurality of exchange target pixels are selected randomly from among the pixels in a single block;
an evaluation function value computing unit (4) which computes function values of a predetermined evaluation function that indicates a characteristic of a pixel value configuration of the pixels in a single block for two cases of a case where pixel values of said plurality of exchange target pixels are exchanged and a case where exchange is not performed;
an exchange judgment unit (5) which compares function values determined for said two cases by said evaluation function value computing unit to judge whether or not pixel values should be exchanged among said plurality of exchange target pixels;
a pixel value exchange unit (6) which performs a process of exchanging the pixel values among said plurality of exchange target pixels that are stored in said mask storage unit, when said exchange judgment unit makes a judgment that exchange should be performed; and
a repetitive process unit (7) which performs control so that a process concerning a pixel exchange for a single block, that are executed by said random number generating unit, said evaluation function value computing unit, said exchange judgment unit, and said pixel value exchange unit, are executed repeatedly until a predetermined condition is satisfied with all blocks.

### Claim 32 (depends on 31)

The dither mask generating device according to claim 31, wherein:
a primitive design image storage unit (8) which stores image data that make up a primitive design image, is furthermore equipped and the evaluation function value computing unit (4) computes function values by using an evaluation function that indicates a degree of matching or a difference of an image, which is expressed by pixels in a single block that makes up the dither mask, and said primitive design image.

### Claim 33 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)

An image conversion device (20) which uses a dither mask that has been generated by a dither mask generating method according to any of claims 1 through 30 to convert a continuous-tone image into a halftone image.

### Claim 34 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)

A program for making a computer execute the respective steps that make up a dither mask generating method according to any of claims 1 through 30 and computer-readable recording medium, in which said program is stored.

### Claim 35 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)

A computer-readable recording medium, in which is recorded data of a pixel array that makes up a dither mask that has been generated by a dither mask generating method according to any of claims 1 through 30.

### Claim 36 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)

A computer-readable recording medium, in which is stored an image data of a halftone image obtained by performing a conversion process on a continuous-tone image using a dither mask that has been generated by a dither mask generating method according to any of claims 1 through 30.

### Claim 37 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)

A computer-readable recording medium, in which is stored an image data of a multi-color halftone image obtained by performing a conversion process on color separated images of respective color components of a multi-color continuous-tone image using a same dither mask that has been generated by a dither mask generating method according to any of claims 1 through 30.

### Claim 38 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)

A computer-readable recording medium, in which is stored an image data of a multi-color halftone image obtained by performing a conversion process on color separated images of respective color components of a multi-color continuous-tone image using different dither masks that has been generated by a dither mask generating method according to any of claims 1 through 30.

### Claim 39 (depends on 36, 37, 38)

A printed matter prepared using image data according to any of claims 36 through 38.
