WO1992013421A1

WO1992013421A1 - Method and apparatus for generating from a continuous-tone image a signal representative thereof

Info

Publication number: WO1992013421A1
Application number: PCT/GB1992/000130
Authority: WO
Inventors: Trevor Grant Clarkson
Original assignee: University College London; Kings College London
Current assignee: University College London; Kings College London
Priority date: 1991-01-25
Filing date: 1992-01-23
Publication date: 1992-08-06
Anticipated expiration: 1993-07-25
Also published as: GB9101635D0

Abstract

A method is disclosed of generating from a continuous-tone image a signal representative thereof, which comprises scanning the image to produce therefrom a digital signal consisting of a stream of bytes, with the value of each byte being determined by the grey-scale level of the image at a given point, generating a stream of random numbers, comparing each byte with a respective random number, and generating for each byte an output signal 0 or 1 depending on the result of the comparison.

Description

METHOD AND APPARATUS FOR GENERATING FROM A CONTINUOUS-TONE IMAGE A SIGNAL REPRESENTATIVE THEREOF

This invention relates to a method and apparatus for generating from a continuous-tone image a signal representative thereof.

Half-tone images are used in many processes where only a single printing colour is available, for example in newspapers, laser printers and fax machines. In the process normally used in, for example, newspapers, a fine-meshed grid, known as a screen, is placed over an original continuous-tone image, for example a photograph. This divides the image into a large number of small squares. The image is scanned to determine the grey- scale level of each square, i.e. the average darkness within each square, and the image is printed using a rectangular array of dots of constant pitch (one dot per square) , with the size of each dot being proportional to the sensed darkness of the square, assuming the image is being printed black on white.

Although this process is acceptable where an image is to be printed using a printing process which is able to use dots of varying size, it cannot be used in, for example, a conventional laser printer, where the image produoed consists of pixels of uniform size. Also, it is difficult to use the process under circumstances where an image is to be scanned at one location and then transmitted electronically for printing at a second location, as occurs in a facsimile machine. This is because for each square of the grid a signal must be transmitted representing the lightness or darkness of the square as measured on the grey-scale.

One way in which it has been attempted to overcome these problems is by the use of what are referred to as superpixels. The image is scanned using a grid each of whose squares has the size of an array cf a number of pixels. This array is referred to as a superpixel. For example, each superpixel may consist of a 2 x 2 array of pixels. The lightness or darkness cf the square is then determined using a grey-scale having a number of divisions equal to the number of pixels in each superpixel plus one. Thus, when each superpixel consists cf a 2 x 2 array the grey-scale has five levels. When the image is printed either 0, 1, 2, 3 or 4 of the pixels in a given superpixel are printed black, and the remainder are left white, depending on the grey-scale level which is to be represented.

However, the process just described has a number of disadvantages. Firstly, the smallest feature which can be printed is now the size of a superpixel.

Secondly, for ease of electronic processing it is always the same pixels within a superpixel which are printed black to represent a given grey-scale level.

For example, when the grey-scale level requires one pixel in a superpixel to be printed black it might be always the top left-hand pixel which was so printed, and when the grey-scale level required two pixels in a superpixel to be printed black it might always be the top left-hand and bottom right-hand pixels which were printed black. Because of this images printed in this way tend to show false features, i.e. features which have no counterpart in the original image and which are there purely because of the way the image has been processed.

An object of the present invention is to provide a method and apparatus for generating from a continucus- tcne image a signal which is representative thereof, so that the signal can be used for printing, in which the problems identified above are eliminated or at least mitigated.

According to the present invention there is provided a method of generating from a continuous-tone image a signal representative thereof, which comprises scanning the image to produce therefrom a digital signal consisting of a stream of bytes, with the value of each byte being determined by the grey-scale level of the image at a given point, generating a stream of random numbers, comparing each byte with a respective random number, and generating for each byte an output signal 0 or 1 depending on the result of the comparison.

The invention further provides an apparatus for generating from a continuous-tone image a signal representative thereof, which comprises means for scanning the image to produce therefrom a digital signal consisting of a stream of bytes, with the value of each byte being determined by the grey-scale level of the image at a given point, a random number generator for generating a stream of random numbers, and a comparator having a first input connected to the output of the scanning means, a second input connected to the output cf the random number generator, and a signal output, the comparator being operable to compare each byte with a respective random number and generate for each byte at its output a signal 0 or 1 depending on the result of the comparison.

In the accompanying drawings:

Figure 1 is a block diagram showing a first embodiment of the invention;

Figures 2 and 3 are block diagrams showing a second embodiment of the invention;

Figure 4 is a graph showing how a memory store may be used in the second embodiment;

Figure 5 shows a modified embodiment by means of which graph B of Figure 4 may be implemented; and

Figure 6 illustrates the use of oversampling in the invention.

The embodiment shown in Figure 1 comprises a camera 1 which scans a continuous-tone image and produces therefrom an analogue signal representing the variations in darkness over the image. This analogue signal is supplied to the input of a digitiser 2 which converts the analogue signal into a stream of bytes, one byte per pixel. By way of example, each byte is considered here as consisting of eight bits, but some other number cf bits, say six bits, could be used instead. The bytes are fed sequentially to a first input cf a comparator 3. A random number generator 4 is connected to a second input cf the comparator, and feeds a stream of eight-bit random numbers to the comparator. A clock pulse generator 5 is connected to the random number generator 4 and the digitiser 2 so that at each clock pulse the next byte from the digitiser and the next random number are fed to the comparator.

The comparator 3 compares the byte from the digitiser 2 with the random number and produces at its output 6 a value either of 0 or 1, denoted in Figure 1 as the half-tone output, depending on the result cf the comparison. One way in which the comparator can operate is to add together the bytes being compared and hold the sum in a register. If the sum has eight bits the half¬ tone output is 0. If the sum has 9 bits the register overflows and causes a 1 to appear at the output 6.

Alternatively, the comparator can operate by subtracting the random number from the byte received from the digitiser 2, and generating a 1 at its output if the result is positive and a 0 at its output if the result is negative.

In either case, it will be seen that the probability of the half-tone output being 1 increases with the value of the byte fed from the digitiser to the comparator. The half-tone output is fed to a printer. The printer may be locally situated or may be at a remote location, as in the case of a facsimile machine. Because cf its digital nature the half-tone output can be transmitted without degradation. At the printer the half-tone output causes a black dot to be printed for each "1" in the half-tone output and a white space to be left for each "0" in the half-tone output. The element of randomness introduced by the random number generator prevents the printed image exhibiting false features of the type associated with the use of superpixels described above.

In the embodiment described in Figure 1 the probability of a black dot appearing at any given location on the printed image is directly proportional to the darkness of the corresponding scanned area of the original half-tone image. However, although this would appear to be mathematically a correct approach, the human eye is found to respond in a non-linear fashion tc the density of an array of dots, and it is desirable, therefore, to take this into account. The embodiment shown in Figures 2 and 3 makes it possible to do this. As shown in Figure 2, the comparator 3 and random number generator 4 are included in a device referred to as a pRAM. This is an acronym for a probabilistic random access memory. The concept of a pRAM is described in detail in Proceedings of the First IEE International Conference on Artificial Neural Networks, IEE, 1989, No. Ξ13, pp 242-246 and also in copending PCT Publications Nos. O92/00572 and O92/00573. However, for convenience a discussion of the pRAM is set out below.

The pRAM comprises a random access memory (RAM) 7 having a plurality of storage locations 8 equal to 2^N, where N is the number of bits in each address and is also equal, in the context of the present invention, to the number of bits in the digitised signal produced by the digitiser 2. Thus in this case the number of storage locations is 2^s = 256. Each storage location 8 holds a binary number having a number of bits equal to the number of bits present in the random numbers generated by the random number generator 4. This could once again be 8 bits, but some other number of bits could be used instead. The RAM 7 has an address decoder 9 to which each byte from the digitiser 2 is fed consecutively. Each of these bytes thus addresses one of the storage locations 8 and causes the contents of the addressed location to be sent to the comparator 3 where it is compared with a random number from the random number generator 4. A half-tone output 6, either 0 or 1, is produced as a result, in the same way as in the first embodiment.

By appropriately choosing the contents of the storage locations 8 any desired relationship can be achieved between the value of the bit received from the digitiser 2 and the probability cf a 0 cr 1 being produced at the output 6 as a result. The pRAM memory thus acts as a look-up table so that the resulting half¬ tone image can more accurately match the response of the human eye as it integrates the half-tone image back into one of continuous-tone, having regard to the fact that it is known that the eye responds in a logarithmic manner to intensity. Figure 4 illustrates in a graph how this may be achieved. Figure 4 illustrates in curve A a desired relationship between the darkness of an element of the image being scanned, plotted on the abscissa, versus the desired probability of the half-tone output being 1 plotted on the ordinate. It will be seen that this is non-linear.

To achieve this, the contents of the storage locations 8 increase with increasing memory address in a correspondingly non-linear fashion. Thus, if the storage locations 8 each hold an 8-bit number the contents cf storage location 0 will be 0, the contents of storage location 255 will be 255, but the contents cf, say, storage location 128 will be much less than 128. A further degree of sophistication can be achieved if the image at which the camera is directed is completely scanned before the half-tone processing begins. If this is done the maximum and minimum pixel values in the image can be recorded, and the half-tone image can then be expanded so that it is scaled to use the maximum dynamic range available. In other words, an image with a low degree of contrast can be converted into an image with a high degree of contrast, at least for the purposes of producing the half-tone output.

This is particularly advantageous if the output is to be transmitted to a remote location, since it can be transmitted with a high degree of contrast and then, if desired, reprinted with the original degree of contrast. Curve B in Figure 4 replaces curve A for this purpose. The range of contrast in the original image is assumed to be R. In terms of the numerical example given above for curve A, in the case of curve B only a subset of all addresses will be used, with an address greater than 0 having a contents of 0 and an address less than 255 having a contents of 255.

Figure 5 shows a modified embodiment with which graph B of Figure 4 can be implemented. This comprises a microprocessor system 10 which monitors the pixel data 11 produced by the digitiser 2 over the period of one frame. From this the system 10 records the maximum and minimum data values so that the range R can be calculated. For every data value within the range R, the system calculates a corresponding mean density value according to curve 3, and these mean density values are then written by the microprocessor system on its data bus 12 into the write port 13 of the pRAM, and thence into the storage locations 8 of the pRAM's memory 7. During the next frame, each byte of pixel data 11 acts as an address and is successively applied to the address decoder 9 of the pRAM to produce a half-tone output in a manner corresponding to that described above with reference to Figure 3.

The procedure just described, in which one frame is used to set the memory contents of the pRAM and the next frame so used to generate the half-tone output, can be used where the scanned image remains unchanged from one frame to the next (as in scanning in static photographs, for example) or changes very little from one frame to the next (as in scanning a typical television picture having 25 frames/second or a figure cf that order) . An alternative procedure, which can be used whether or not the image satisfies these conditions, is to store the pixel data relating to a given frame in a buffer within the microprocessor system 10, and use that data both for setting the memory contents of the pRAM and for generating the half-tone output.

It should also be mentioned that graph B cf Figure 4 could be implemented by keeping the memory contents of the pRAM unchanged and varying the output of the random number generator. However, it is simpler to vary the memory contents of the pRAM. Further, graph A of Figure 4 could be implemented using a pRAM with memory contents which vary linearly with the values of the addresses, by causing the random number generator to operate with a non-uniform probability. Once again, however, it is simpler to use a standard random number generator, and a pRAM with non-linearly varying memory contents.

Where the resolution of the output device on which the half-tone image is to be formed exceeds that of the input image, for example, where a full-screen PC digitised image of 640x480 pixels resolution is to be printed in a laser printer having a resolution of 300 dots per inch (12 dots/mm) , the present invention can employ the technique of oversampling to generate a more natural output. For each input pixel, a corresponding NxN array is produced in the output image. Each element cf ^'the NxN array is here called a micropixel. Instead cf presenting each input pixel to the pRAM to produce one half-tone output, each input pixel is presented N times, for comparison with N random numbers, to produce N half¬ tone outputs each having a probability of being l determined by the memory contents of the input pixel value. Each of the N half-tone outputs provides a respective one of the micropixels. This allows N²+l grey-scale levels to be represented for each pixel and gives an apparent increase in resolution by a factor of N in each direction. In this way, the noisy shading of the image is reduced to a finer grain.

Claims

CLAIMS :

1. A method of generating from a continuous-tone image a signal representative thereof, which comprises scanning the image to produce therefrom a digital signal consisting of a stream of bytes, with the value of each byte being determined by the grey-scale level of the image at a given point, generating a stream of random numbers, comparing each byte with a respective random number, and generating for each byte an output signal 0 or 1 depending on the result of the comparison.

2. A method according to claim 1, wherein the bytes cf the digital signal produced by scanning the image, and the bytes of each random number, have the same number of bits, and wherein the comparator is operable to add to the bytes which it is comparing and generate a 1 cr 0 depending on whether or not the addition produces an overflow bit.

3. A method according to claim 1, wherein the bytes of the digital signal produced by scanning the image, and the bytes of each random number produced by scanning the image, have the same number of bits, and wherein the comparator is operable to generate a 1 or 0 depending on which is the greater of the bytes being compared.

4. A method according to any preceding claim, wherein each byte of the digital signal produced by scanning the image is used as the address of a storage location in a memory device, the storage location having a byte held therein which is then sent to the comparator for comparison with a respective random number.

5. A method according to claim 4, wherein the bytes of the digital signal produced by scanning the image are inspected to determine the contrast range of the image, and the contents of the memory device are altered before comparison takes place so that a subset of all addresses contains a range of memory contents corresponding to the maximum range of byte values which can be compared by the comparator.

6. A method according to claim 4 or 5, wherein the values of the bytes stored in the memory locations of the memory device vary non-linearly with the values of the addresses by which those locations are addressed.

7. A method according to claim 4 or 5, wherein the values of the bytes stored in the memory locations of the memory device vary linearly with the values of the addresses by which those locations are addressed.

8. A method according to any preceding claim, wherein each byte is used to generate a plurality of output signals, by comparing the byte with a corresponding plurality of random numbers.

9. An apparatus for generating from a continuous- tone image a signal representative thereof, which comprises means for scanning the image to produce therefrom a digital signal consisting of a stream of bytes, with the value of each byte being determined by the grey-scale level of the image at a given point, a random number generator for generating a stream of random numbers, and a comparator having a first input connected to the output of the scanning means, a second input connected to the output of the random number generator, and a signal output, the comparator being operable to compare each byte with a respective random number and generate for each byte at its output a signal 0 or 1 depending on the result of the comparison.

10. An apparatus according to claim 9, wherein the bytes of the digital signal produced by scanning the image, and the bytes of each random number, have the same number of bits, and wherein the comparator is operable to add to the bytes which it is comparing and generate a 1 or 0 depending on whether or not the addition produces an overflow bit.

11. An apparatus according to claim 9 , wherein the bytes of the digital signal produced by scanning the image, and the bytes of each random number produced by scanning the image, have the same number of bits, and wherein the comparator is operable to generate a 1 or 0 depending on which is the greater of the bytes being compared.

12. An apparatus according to any one of claims 9 to 11, wherein each byte of the digital signal produced by scanning the image is used as the address of a storage location in a memory device, the storage location having a byte held therein which is then sent to the comparator for comparison with a respective random number.

13. An apparatus according to claim 12, comprising means for inspecting the bytes of the digital signal produced by scanning the image to determine the contrast range of the image, and means for altering the contents of the memory device before comparison takes place so that a subset of all addresses contains a range of memory contents corresponding to the maximum range of byte values which can be compared by the comparator.

14. An apparatus according to claim 12 or 13, wherein the values of the bytes stored in the memory locations of the memory device vary non-linearly with the values of the addresses by which those locations are addressed.

15. An apparatus according to claim 12 or 13, wherein the values of the bytes stored in the memory locations of the memory device vary linearly with the values of the addresses by which those locations are addressed.

16. An apparatus according to any one of claims 9 to 15, wherein the comparator is operable to generate a plurality of output signals for each byte, by comparing the byte with a corresponding plurality of random numbers.