Force field halftoning

Claim 3

A method as claimed in claim 1, wherein the under result is determined by assigning to it a value of zero if the output value of the pixel is greater than or equal to the input value and assigned a value equal to the input value less the output value if the output value of the pixel is less than the input value, and wherein the over result is determined by assigning to it a value of zero if the output value is less than or equal to the input value and assigned a value equal to the output value less the input value if the output of the current pixel is greater than the input value.

Claim 4

A method as claimed in claim 2, wherein the under and over results are determined using an error measure between the output value and the input value that preserves a ratio of error between the under result and the over result.

Claim 5

A method as claimed in claim 1 or 2, wherein the first output state value is the least output state value which is greater than or equal to the input value of the current pixel, and said second output state value is the greatest output state value which is less than or equal to the input value of the current pixel.

Claim 6

A method as claimed in claim 1 or 2, wherein the under result repulsive measure is determined from the under result of at least one of the previously halftoned pixels and an under result for the current pixel when the current pixel is halftoned to the second output (state) value, and the over result repulsive measure is determined from the over result of at least one of the previously halftoned pixels and an over result for the current pixel when the current pixel is halftoned to the first output value.

Claim 7

A method as claimed in claim 1, wherein said image is any one image of a series of images.

Claim 8

A method as claimed in claim 1, wherein the under result repulsive measure and over result repulsive measure are determined utilizing a set of geometrically reducing weight values.

Claim 9

A method as claimed in claim 1, wherein the under result and the over result are each determined for each previously halftoned pixel of said image.

Claim 10

A method as claimed in claim 1, wherein said pixels are halftoned in raster-display order and said previously halftoned pixels are divided into at least two groups and step (b) comprises determining repulsive measures for each of said groups, said repulsive measures being summed prior to step (c).

Claim 11

A method as claimed in claim 1, of wherein said image comprises (y) scanlines and (x) pixels per scanline, and said current pixel has a location (i,j) (where 1≦i≦x, 1≦j≦y) in said image, and said previously halftoned pixels are divided into two groups, a first one of said groups being bounded by pixels at locations (1,1), (i-j,1) (1,j) and (i-1, j), and the second one of said groups being bounded by pixels at locations (i,1), (x,1), (i,j-1) and (x,j-1).

Claim 12

A method as claimed in claim 10, wherein each of said groups is divided into a plurality of subgroups each extending substantially radially from said current pixel, said repulsive measures being determined for each of said sub-groups.

Claim 13

A method as claimed in claim 10, wherein pixels in a current scanline of said image are halftoned by at least one forward pass proceeding in the raster scan direction, and at least one reverse pass proceeding in a reverse raster scan direction, the forward pass determining the contribution to the repulsive measures of pixels in the current scanline by the first one of said groups, and the reverse passes determining the contribution to the repulsive measures of pixels in the next scanline by the second one of said groups.

Claim 14

A method as claimed in claim 10, wherein pixels in a current scanline of said image are halftoned by at least one pass proceeding either left to right or right to left but in the opposite direction to a pass of the previous scanline.

Claim 15

A method as claimed in claim 1, further comprising, before step (a), the step of: (aa) preprocessing said current pixel using an inverse transform to correct for non-linearity in the halftoning method.

Claim 16

A method as claimed in claim 1, wherein said pixel has more than one colour component.

Claim 19

A method as claimed in claim 16, wherein the predetermined value is assigned a value equal to the output value of a corresponding pixel of a previous frame.

Claim 20

A method as claimed in claim 17, wherein the predetermined value is assigned a value equal to an output value to said pixel determined by a process of dithering an input value of said pixel.

Claim 21

A method as claimed in claim 16, wherein said dithering is performed using one of an inverse dither matrix or a displaced dither matrix.

Claim 22

A method as claimed in claim 16, wherein the predetermined value is assigned a value equal to an output value of said pixel determined by selection from a dot pattern indexed by the pixel input value.

Claim 23

A method as claimed in claim 20, wherein said dot patterns are at least partly uncorrelated.

Claim 24

A method as claimed in claim 21, wherein said input dot pattern is optimized by simulated annealing.

Claim 25

A method as claimed in claim 16, wherein the predetermined value is determined by another halftoning process.

Claim 26

A method as claimed in claim 16, wherein the predetermined value is assigned a value equal to an output value of said pixel determined by a process of dithering an input value of said pixel, and wherein the dither matrix used for dithering is selected from a set of dither matrices using a function of the nearby pixel input values.

Claim 27

A method as claimed in claim 24, wherein said function comprises including but not limited to indexing a dither matrix by the pixel input value.

Claim 28

A method as claimed in claim 16, wherein said minimum repulsive measure is an over repulsive measure in the event that the predetermined value is less than an input value of the pixel.

Claim 29

A method as claimed in claim 16, wherein said minimum repulsive measure is an under repulsive measure in the event that the predetermined value is greater than an input value of the pixel.

Claim 30

Apparatus for halftoning a current pixel of an image, said image comprising a plurality pixels each having an input value and an assignable output value that can take on one of at least two output values, said apparatus comprising: first means for determining an under result and an over result for a plurality of previously halftoned pixels of said image, whereby said under result and said over result for a pixel are dependent upon an output value assigned to that pixel; second means for determining, using the under results and the over results, an under result repulsive measure and an over result repulsive measure for the current pixel, whereby said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; means for comparing the under result repulsive measure; and means for assigning a first output value as the output value for the current pixel in the event that the under result repulsive measure is greater than the over result repulsive measure, and assigning a second output value as the output value for said current pixel in the event that the over result repulsive measure is greater than the under result repulsive measure.

Claim 31

Apparatus for halftoning a current pixel of an image, said image comprising a plurality pixels each having an input value and an assignable output value that can take on one of at least two output values, said apparatus comprising: first means for determining an under result and an over result for a plurality of previously halftoned pixels of said image, whereby said under result and said over result for a pixel are dependent upon an output value assigned to that pixel; second means for determining, using the under results and the over results, an under result repulsive measure and an over result repulsive measure for the current pixel, whereby said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; means for comparing the under result repulsive measure; and means for assigning a first output value as the output value for the current pixel in the event that the under result repulsive measure is greater than the over result repulsive measure, and assigning a second output value as the output value for said current pixel in the event that the over result repulsive measure is greater than the under result repulsive measure.

Claim 32

Apparatus as claimed in claim 28, wherein said first means for determining determines the under result by assigning to the under result a value of zero if the output value of said current pixel is greater than or equal to the input value, and assigning a value equal to the input value less the output value if the output value of said current pixel is less than the input value, and wherein first means for determining determines the over result by assigning to the over result a value of zero if the output value is less than or equal to the input value and assigning a value equal to the output value less the input value if the output of the current pixel is greater than the input value.

Claim 33

Apparatus as claimed in claim 28, wherein the first output state value is the least output state value which is greater than or equal to the input value of the current pixel, and said second output state value is the greatest output state value which is less than or equal to the input value of the current pixel.

Claim 34

Apparatus as claimed in claim 28, wherein the under result repulsive measure is determined from the under result of at least one of the previously halftoned pixels and an under result for the current pixel assuming the current pixel is to be halftoned to the second output value, and wherein the over result repulsive measure is determined from the over result of at least one of the previously halftoned pixels and an over result for the current pixel assuming the current pixel is to be halftoned to the first output value.

Claim 35

Apparatus as claimed in claim 28, wherein said image is any one image of a series of images.

Claim 36

Apparatus as claimed in claim 28, wherein the under result repulsive measure and over result repulsive measure are determined utilizing an set of geometrically reducing weight values.

Claim 37

Apparatus for halftoning one or more images, each image comprising pixels, said apparatus comprising: means for assigning a predetermined value to an output value of a current pixel; means for determining an under result and an over result for the current pixel and for a plurality of previously halftoned pixels of said image, wherein said under result and said over result for a pixel are dependent upon an output value assigned to that pixel; means for determining a repulsive measure between the current pixel and a plurality of previously halftoned pixels of the current image wherein said repulsive measure is one of an under result repulsive measure and an over result repulsive measure, and wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and wherein said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; means for comparing the repulsive measure to a minimum repulsive measure achievable for the pixel in combination with a threshold value; and means for retaining the value as the output value of said current pixel if the repulsive measure is less than a sum of the minimum repulsive measure and the predetermined threshold value.

Claim 38

Apparatus for halftoning one or more images, each image comprising pixels, said apparatus comprising: means for assigning a predetermined value to an output value of a current pixel; means for determining an under result and an over result for the current pixel and for a plurality of previously halftoned pixels of said image, wherein said under result and said over result for a pixel are dependent upon an output value assigned to that pixel; means for determining a repulsive measure between the current pixel and a plurality of previously halftoned pixels of the current image wherein said repulsive measure is one of an under result repulsive measure and an over result repulsive measure, and wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and wherein said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; means for comparing the repulsive measure to a minimum repulsive measure achievable for the pixel in combination with a threshold value; and means for retaining the value as the output value of said current pixel if the repulsive measure is less than a sum of the minimum repulsive measure and the predetermined threshold value.

Claim 39

Apparatus as claimed in claim 34, wherein the predetermined value is assigned a value equal to the output value of a corresponding pixel of a previous frame.

Claim 40

Apparatus as claimed in claim 34, wherein the predetermined value is assigned a value equal to an output value to said pixel determined by a process of dithering an input value of said pixel.

Claim 41

Apparatus as claimed in claim 34, wherein said minimum repulsive measure is an over repulsive measure in the event that the predetermined value is less than an input value of the pixel.

Claim 42

Apparatus as claimed in claim 34, wherein said minimum repulsive measure is an under repulsive measure in the event that the predetermined value is greater than an input value of the pixel.

Claim 43

Apparatus as claimed in 34, wherein said pixel has more than one colour component.

Claim 44

A computer software system for executing instructions on a general purpose computer, wherein said instructions comprise a plurality of process modules for halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, said modules comprising: a first determining module for determining an under result and an over result for a current pixel and for a plurality of previously halftoned pixels of said image, wherein said under result and said over result for a pixel are dependent upon an output value assigned to that pixel; a second determining module for determining using the under results and the over results an under result repulsive measure and an over result repulsive measure for the current pixel, wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; a comparing module for comparing the under result repulsive measure to the over result repulsive measure; and an assigning module for assigning a first output value as the output value for the current pixel in the event that the under result repulsive measure is greater than the over result repulsive measure, and assigning a second output value as the output value for said current pixel in the event that the over result repulsive measure is greater than the under repulsive measure.

Claim 45

A computer software system for executing instructions on a general purpose computer, wherein said instructions comprise a plurality of process modules for halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, said modules comprising: a first determining module for determining an under result and an over result for a current pixel and for a plurality of previously halftoned pixels of said image, wherein said under result and said over result for a pixel are dependent upon an output value assigned to that pixel; a second determining module for determining using the under results and the over results an under result repulsive measure and an over result repulsive measure for the current pixel, wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; a comparing module for comparing the under result repulsive measure to the over result repulsive measure; and an assigning module for assigning a first output value as the output value for the current pixel in the event that the under result repulsive measure is greater than the over result repulsive measure, and assigning a second output value as the output value for said current pixel in the event that the over result repulsive measure is greater than the under repulsive measure.

Claim 46

A system as claimed in claim 40, wherein said instructions are configured for operation via a computer readable medium, said medium being one of a memory device, a computer, and a computer network.

Claim 47

A computer software system for executing instructions on a general purpose computer, wherein said instructions comprise a plurality of process modules for halftoning a series of images, each image comprising a plurality of pixels, said modules comprising: an assigning module for assigning a predetermined value to an output value of the current pixel, a determining module for determining a repulsive measure between the current pixel and a plurality of previously halftoned pixels of the current image, wherein said repulsive measure is one of an under result repulsive measure and an over result repulsive measure, and wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; a comparing module for comparing the repulsive measure to a minimum repulsive measure in combination with a threshold value; and a decision module for retaining the predetermined value as the output value of said pixel if the repulsive measure is less than a sum of the minimum repulsive measure and a threshold value.

Claim 48

A computer software system for executing instructions on a general purpose computer, wherein said instructions comprise a plurality of process modules for halftoning a series of images, each image comprising a plurality of pixels, said modules comprising: an assigning module for assigning a predetermined value to an output value of the current pixel, a determining module for determining a repulsive measure between the current pixel and a plurality of previously halftoned pixels of the current image, wherein said repulsive measure is one of an under result repulsive measure and an over result repulsive measure, and wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the under result for the current pixel and the under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of the over result for the current pixel and the over result for a previously halftoned pixel; a comparing module for comparing the repulsive measure to a minimum repulsive measure in combination with a threshold value; and a decision module for retaining the predetermined value as the output value of said pixel if the repulsive measure is less than a sum of the minimum repulsive measure and a threshold value.

Claim 49

A system as claimed in claim 42, wherein said instructions are configured for operation via a computer readable medium, said medium being one of a memory device, a computer, and a computer network.

Claim 50

A computer system comprising: input means for receiving an image or a sequence of images; halftoning means for halftoning said image(s), said halftoning being characterized by a determination of relative repulsive forces between a current pixel of the image(s) being halftoned, and a plurality of previous pixels of the image(s) that have been halftoned, wherein said relative repulsive forces are an under result repulsive measure and an over result repulsive measure, wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an under result for the current pixel and an under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an over result for the current pixel and an over result for a previously halftoned pixel; and a discrete level display for displaying the image(s) output from said halftoning means.

Claim 51

A computer system comprising: input means for receiving an image or a sequence of images; halftoning means for halftoning said image(s), said halftoning being characterized by a determination of relative repulsive forces between a current pixel of the image(s) being halftoned, and a plurality of previous pixels of the image(s) that have been halftoned, wherein said relative repulsive forces are an under result repulsive measure and an over result repulsive measure, wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an under result for the current pixel and an under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an over result for the current pixel and an over result for a previously halftoned pixel; and a discrete level display for displaying the image(s) output from said halftoning means.

Claim 54

A method as claimed in claim 45, wherein image is halftoned on a pixel-by-pixel basis in raster display order and said plurality of previous pixels comprises all previous pixels of the image.

Claim 55

An image processor comprising: input means for receiving pixel data of an image to be displayed; means for determining repulsive measure data from repulsive forces between said pixel data and a plurality of previously halftoned pixels, wherein said repulsive forces are one of an under result repulsive measure and an over result repulsive measure, and wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an under result for the current pixel and an under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an over result for the current pixel and an over result for a previously halftoned pixel; and pixel calculator means for determining halftone output data of said image processor from said pixel data and said repulsive measure data.

Claim 56

An image processor comprising: input means for receiving pixel data of an image to be displayed; means for determining repulsive measure data from repulsive forces between said pixel data and a plurality of previously halftoned pixels, wherein said repulsive forces are one of an under result repulsive measure and an over result repulsive measure, and wherein said under result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an under result for the current pixel and an under result for a previously halftoned pixel, and whereby said over result repulsive measure is dependent upon a sum, over the plurality of previously halftoned pixels, of a product of an over result for the current pixel and an over result for a previously halftoned pixel; and pixel calculator means for determining halftone output data of said image processor from said pixel data and said repulsive measure data.

Claim 57

An image processor as claimed in claim 47, wherein said pixel calculator means determines pixel excess values for a current pixel of said image, and said means for determining comprises; first pixel group calculator means for determining first pixel group excess values from said pixel excess values and previously calculated first pixel group excess values; first group memory means for storing said first pixel group excess values and supplying said previously calculated first pixel group excess values to said first pixel group calculator means and to said pixel calculator means; a pixel result memory means for storing said pixel excess values; second pixel group calculator means for determining second pixel group excess values from said pixel excess values output from said pixel result memory means and from previously calculated second pixel group excess values; and second group memory means for storing said second group excess values and supplying said previously calculated second group excess values to said second pixel group calculator means and to said pixel calculator means, said previously determined first group and second group excess values collectively comprising said repulsive measure data.

Claim 58

An image processor as claimed in claim 48, wherein said pixel result memory means, said first group memory means and said second group memory means each comprise serial memory.

Claim 59

An image processor as claimed in claim 49, wherein each said serial memory is operable to alter a direction of data movement therethrough.

Claim 60

An image processor as claimed in claim 50, wherein said pixel groups comprise respective portions of all previously halftoned pixels in said image.

Claim 61

An image processor as claimed in claim 49 wherein said pixel groups comprises left and right wedges of said previously halftoned pixels and, for a current pixel i[x][y] of said image: inputs of said pixel calculator means comprise said current pixel i[x][y], left wedge excess values WBbl[x-1][y], WBtl[x-1][y-1], WWbl[x-1][y], and WWtl[x-1][y-1] output from the first group memory means, right wedge excess values WBtr[x][y-1], WBbr[x+1][y-1], WWtr[x][y-1], and WWbr[x+1][y-1] output from the second group memory means, said pixel calculator means outputs a pixel halftone output value o[x][y] pixel excess black value b[x][y], and a pixel excess white value w[x][y] determined by: b=i[x][y]; w=255-i[x][y]; Fb=Fleft*WBbl[x-1][y]+Ftop -- left*WBtl[x-1][y-1]+Ftop*WBtr[x][y-1]+Ftop -- right*WBbr[x+1][y-1]; Fb=Fb*b; Fw=Fleft*WWbl[x-1][y]+Ftop -- left*WWtl[x-1][y-1]+Ftop*WWtr[x][y-1]+Ftop -- right*WWbr[x+1][y-1]; Fw=Fw*w; if (Fb>=Fw) then (o[x][y]=255, b[x][y]=0 and w[x][y]=w) or (o[x][y]=0, b[x][y]=b and w[x][y]=0); inputs of the first (left) pixel group calculator means comprise the pixel excess black value b[x][y], the pixel excess white value w[x][y] both output from the pixel calculator means, and both left wedge excess black values WBbl[x-1][y], WBbl[x-1][y-1], WBbl[x-2][y-1], WBtl[x-1][y-1], WBtl[x][y-1], and WBtl[x-1][y-2] and left wedge excess white values WWbl[x-1][y], WWbl[x-1][y-1], WWbl[x-2][y-1], WWtl[x-1][y-1], WWtl[x][y-1], and WWtl[x-1][y-2] output from said first group memory means, and output of said first pixel group calculator means comprise left wedge excess black values WBbl[x][y] and WBtl[x][y], and left wedge excess white values WWbl[x][y] and WWtl[x][y], given by: WBbl[x][y]=b[x][y]+Fleft*WBbl[x-1][y]+Ftop -- left*WBbl[x-1][y-1]-Fleft*top -- left*WBbl[x-2][y-1]; WBtl[x][y]=b[x][y]+Ftop -- left*WBtl[x-1][y-1]+Ftop*WBtl[x][y-1]-Ftop -- left*Ftop*WBtl[x-1][y-2]; WWbl[x][y]=w[x][y]+Fleft*WWbl[x-1][y]+Ftop -- left*WWbl[x-1][y-1]-Fleft*top -- left*WWbl[x-2][y-1]; WWtl[x][y]=w[x][y]+Ftop -- left*WWtl[x-1][y-1]+Ftop*WWtl[x][y-1]-Ftop -- left*Ftop*WWtl[x-1][y-2], and inputs of said second pixel group (right) calculator means comprise the pixel excess black value b[x][y], the pixel excess white value w[x][y], right wedge excess black values WBtr[x][y-1], WBtr[x+1][y-1], WBtr[x+1][y-2], WBbr[x+1][y-1], WBbr[x+1][y], and WBbr[x+2][y-1] and right wedge excess white values WWtr[x][y-1], WWtr[x+1][y-1], WWtr[x+1][y-2], WWbr[x+1][y-1], WWbr[x+1][y], and WWbr[x+2][y-1] output from the second group memory means, wherein outputs of said second pixel group (right) calculator means comprise right wedge excess black values WBtr[x][y] and WBbr[x][y], right wedge excess white values WWtr[x][y] and WWbr[x][y] given by: WBtr[x][y]=b[x][y]+Ftop*WBtr[x][y-1]+Ftop -- right*WBtr[x+1][y-1]-Ftop*Ftop -- right*WBtr[x+1][y-2]; WBbr[x][y]=b[x][y]+Ftop -- right*WBbr[x+1][y-1]+Fright*WBbr[x+1][y]-Ftop -- right*Fright*WBbr[x+2][y-1]; WWtr[x][y]=w[x][y]+Ftop*WWtr[x][y-1]+Ftop -- right*WWtr[x+1][y-1]-Ftop*Ftop -- right*WWtr[x+1][y-2]; WWbr[x][y]=w[x][y]+Ftop -- right*WWbr[x+1][y-1]+Fright*WWbr[x+1][y]-Ftop -- right*Fright*WWbr[x+2][y-1].