Localized signal data preservation within signal bandwidth

A system and method for reducing the noise induced in a particular section or level of a signal bandwidth. The section is isolated from the rest of the signal data, by rescaling this data to produce a buffer section adjacent the section with little or no data in it. The signal is then transmitted to the output device where all data is the buffer section is considered to be the result of noise, and is mapped back to the predetermined level. The signal data is inversely rescaled to move data back into the buffer section. In this way, more of the data that was input at the predetermined level, will also be at the predetermined level afterwards, thereby correcting noise induced in that level by noise inducing transmission techniques such as JPEG compression.

FIELD OF THE INVENTION

The present invention relates to electronic signal processing and in particular, reducing the level of noise in localized parts of a signal's bandwidth.

The following applications have been filed by the Applicant simultaneously with the present application:

The disclosures of these co-pending applications are incorporated herein by reference. The above applications have been identified by their filing docket number, which will be substituted with the corresponding application number, once assigned.

CROSS REFERENCES

The following patents or patent applications filed by the applicant or assignee of the present invention are hereby incorporated by cross-reference.

BACKGROUND OF THE INVENTION

Electronic signal processing will usually induce some level of noise into the output signal. In the transmission of signals, the induced noise is often due to ‘lossy’ transmission methods. Ordinary workers in this field will understand that ‘lossy’ refers to processing techniques that move some signal data to nearby data values.

Lossy signal compression techniques make transmission quicker and more efficient but introduce noise when the transmitted signal is compressed. This level of noise can be controlled and restricted to an acceptable level for the vast majority of the transmission. However, there are instances where the signal data at one or more particulars levels within the bandwidth are more important than others. Alternatively, noise at particular levels of the bandwidth has a more detrimental effect than it would at other levels of the bandwidth. The aggressiveness of the compression technique can be set so that the noise in these critical sections is acceptable, but then majority of the bandwidth is only lightly compressed and the data size remains large. Keeping the data size large tends to defeat the purpose of compressing the signal in the first place.

JPEG (Joint Photographic Experts Group) compression of contone image data is one example of a lossy signal compression technique. The noise induced by JPEG compression in particular sections of the bandwidth can cause particularly visible artifacts in the decompressed image. Because of its relevance to the present invention, the detailed description is directed to localized noise reduction in the compression and decompression of an image file. However, it will be appreciated that this is purely illustrative and the invention encompasses other types of signal transmission.

JPEG compression of image data uses one of a suite of standard algorithms to reduce data size for faster transmission and more efficient storage. The quality of the resultant image is determined by the level of compression. An aggressive compression greatly reduces the file size but introduces high levels of noise. Light compression reduces the noise but the data size remains relatively large. Therefore, the optimum level of compression is a trade off between image quality and data size, having regard to the characteristics of the output device (printer or monitor), processing capabilities and resolution requirements.

During JPEG compression, the image is analyzed in blocks of 8×8 pixels. Depending on the level of compression selected, the detail in each of the blocks is reduced. In more aggressive compressions, the 8×8 blocks can become visible in the final image. The compression should be at a level where the noise in the resulting image is imperceptible. Unfortunately, there are often certain components of an image that are far more prone to decompression artifacts than the rest of the image. In these cases, the noise is imperceptible for the majority of the image, but produces artifacts in certain parts.

The noise prone areas are hard edges between strongly contrasting colors such as text on a white background.FIG. 1is an image of a black shape10on a white background12without any noise.FIG. 2shows the associated grayscale histogram for the image. The histogram has 256 levels, with level0being white and level255being black. A black shape on a white background (without any noise) has pixels in levels0or255only. All other levels are shades of grey and therefore empty.

FIG. 3shows the image ofFIG. 1after it has been JPEG compressed and decompressed. The detail lost during compression manifests as random grey scale artifacts14around the periphery of the black shape10. The grey scale artifacts also exist within the black shape10but are obscured by the surrounding black. The artifacts14are confined to the 8×8 pixel blocks that cross the boundary between the shape and the white background. These artifacts are referred to as JPEG ‘ringing’.

FIG. 4shows the histogram forFIG. 3. While most of the pixels are in level0or255(white or black), the noise appears in the levels near the two extremities16and18. The noise is restricted to the ends of the histogram because compression tends to cause only small shifts in a pixels color level. In a ‘normal’ photographic image, most if not all of the intensity levels in each colour plane have some pixels. The noise from compression does not shift the colour levels very far from the original level, and mixes with the other color planes, so the artifacts occur at a high spatial frequency. The eye is insensitive to high frequency noise made up of small colour levels shifts. It is only the sharp edges between strongly contrasting colors where the artifacts become visible.

SUMMARY OF THE INVENTION

Accordingly the present invention provides a method of preserving signal data at a predetermined level within the bandwidth of an input signal to be processed for use by an output device, the method comprising:

rescaling the signal data in levels other than the predetermined level to move at least some of the signal data out of a buffer section of the bandwidth adjacent to the predetermined level;

processing the signal for use by the output device;

re-assigning any data in the buffer section to the predetermined level; and,

rescaling the signal data in levels other than the predetermined level to move data back into the buffer section.

Inaccuracies in the signal processing shifts some signal data from its original level in the input signal to different level in the output signal. This shift in data generates the noise in the output signal. If data does shift because of the signal processing, there is a high probability that it only shifts to a nearby level in the bandwidth. If the signal data at a particular level is of greater importance relative to most of the other levels, the invention allows this data to be preserved at its original level with very little, if any, lost to noise.

By rescaling the input signal, most or all of the data in levels near the important level can be shifted away. This effectively creates a buffer on one or both sides of the important level which quarantines the data in this level from the rest of the signal data. Any noise induced in the data from the important level is (highly likely to be) confined to the empty buffer, and so can be easily corrected. By re-mapping all data in the buffer back to the important level, the induced noise is removed. Once the data in the buffer has been mapped back to the important level, the initial rescaling of the input signal can be reversed to distribute signal data across the full bandwidth.

Optionally, the input signal is image data for a color plane of an image and the output device is a printer. In these embodiments, the signal data is pixel intensity values for the color plane quantized into a number of discrete intensity levels, such that the number of levels is the bandwidth of the input signal. In a further preferred form of these embodiments, the predetermined level is the intensity level corresponding to ‘white’ (or zero color intensity). Optionally, the method preserves the data in a second predetermined level, the second predetermined level being the maximum intensity level in the bandwidth.

Preferably, the processing of the signal involves lossy transmission of the signal data. In a further preferred form, the processing of the signal involves the lossy compression of the signal data. In a still further preferred from, the processing of the signal involves lossy image compression. In a particularly preferred form, the processing of the signal includes JPEG compression.

Optionally, the input signal is resealed by quantizing the image data into a lesser number of the discrete intensity levels except for image data in the or each predetermined level. In a preferred form the image data is resealed to floating point values and then rounded to the closest of the intensity levels.

In a particularly preferred form, the method further comprises converting the image data from a first color space to a second color space wherein the rescaling of the input image data is performed simultaneously with the color space conversion. In this form, the second color space is the printer color space. Optionally, the step of rescaling the image data back into the or each buffer section after JPEG compression is performed via a dither matrix by adjusting the threshold values in the dither matrix.

Preferably, the image includes text characters. Preferably, the image includes line art. Preferably the image has a white background. Optionally, the color intensity values are 8-bit values and the bandwidth of the input signal is 256 levels. Optionally the predetermined level is ‘0’. Optionally, the second predetermined level is ‘255’. Optionally, the buffer section corresponding to level0is levels1to16. Optionally, the buffer section corresponding to level255is levels240to254.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

As discussed in the Background to Invention,FIG. 1shows an image10on a white background12. The edge of the shape10is referred to as a ‘hard edge’ because the color intensity values drop from maximum intensity to zero (white) instantly. As there are no transition colors in the image, the histogram shown inFIG. 2only has data in levels0and255(8 bit color values).

When the image ofFIG. 1is JPEG compressed for efficient transmission, and subsequently decompressed at the output device, the edge of the shape10is surrounded grey pixel noise14. The noise14is sometimes referred to as mosquito noise as it is most visible as a cloud of dark dots on the light side of a hard edge such as text or line art. The loss of detail in the data during compression can shift pixels color values away from their input values. These shifts are likely to be small so in a contone image with smoother tone gradients, the noise is high frequency and invisible to the eye. However, the noise can become visible around hard edges where input data at level ‘0’ shifts to nearby grey levels from decompression errors. This noise14is shown in the histogram ofFIG. 4. Input data at level ‘255’ also shifts but is less visible amongst the predominantly level255pixels. This noise is shown at18on the histogram ofFIG. 4.

FIG. 5shows the settings for a histogram expansion to remedy the majority of the noise. Ordinary workers in this field will appreciate that a histogram expansion rescales the input data by reducing the number of levels in the bandwidth. InFIG. 5, levels1to16are mapped down to level0and levels240to254are mapped up to level255. Then the intermediate levels are resealed, or widened, to encompass the greys between the extremes. The resulting histogram has fewer levels (224), with more contrast between adjacent levels. Ordinarily, the increased color contrast is the primary purpose of histogram expansion, but in this case, the expansion has corrected most of the noise14as shown inFIG. 6. There is still some ‘ringing’ on either side of the edge between the shape10and the white background12, and this could be corrected with a more aggressive histogram expansion, but in contone images, a harsh reduction in levels leads to visible contouring in areas of gradual tone variation. Ordinary workers will appreciate that each system will have an optimum compromise between clipping all the noise and degrading the number of color levels.

It will also be appreciated that the buffers need not be the same size or symmetrically positioned in the signal bandwidth. It should also be noted that the buffers need not be at the extremes of the bandwidth. For example, if the signal is image data in a YCC-style color space (luminance, chroma red and chroma blue), the important data in the chroma channels is the neutral level in the middle of the bandwidth (level128in 8 bit color values). The important data in the luminance channel is at the extremes.

The image ofFIG. 1only has data in levels0and255, whereas most images have a much broader distribution of the data—usually across the full bandwidth.FIG. 7is a schematic representation of the histogram corresponding to a contone image such as a photograph. The image has some pixels at all levels of the 0 to 255 bandwidth. For storage and transmission, the image is typically JPEG compressed and then decompressed at the output device. Depending the quality of JPEG compression selected, the number of pixels in the output levels should be roughly the same as the corresponding input levels. Any errors that do occur, most likely put the pixel into a nearby level and this happens at high frequency so the noise is imperceptible. The exception to this is the hard edged components of the image such as text on a white background or line art. The eye does tend to register the noise generated in the 8×8 pixel blocks that span or contain such edges.

In these areas, all pixels that were level0in the input image should be preserved as level0pixels in the output image in order to avoid the visible ringing. Likewise level255pixels in the input image should be kept at that level in the output image although this is usually a less visible artifact.

The quality of the JPEG compression is known, and so the section on the bandwidth in which the majority of noise induced in the level0pixels12is also known. These buffer sections20and22of the bandwidth are chosen as levels1-16and levels240-254. For the purposes of this example, the vast majority of noise induced by decompressing levels0and255will appear in these buffer sections.

FIG. 8shows the image data moved out of the buffer section20and22by rescaling the input data24of levels1-254into levels17to239. Rescaling is done using a simple algorithm such as Equation 1 below:
Lr=L1+Li.(Lh−L1)/((Lmax−1)−Lmin)  eq.1

Where:Lris the resealed level that the pixels in the input level are mapped to;L1is the threshold of the buffer section at the lower end of the bandwidth;Lhis the threshold of the buffer section at the upper end of the bandwidth;Liis the input level being resealed;Lmaxis the upper extremity of the bandwidth; and,Lminis the lower extremity of the bandwidth.

Lrcan be rounded to the nearest integer or left as a floating point value to more accurately invert the rescaling process when the input data24is distributed back across the full bandwidth.

FIG. 8shows levels1to254resealed to move the input data out of the buffer sections20and22. The data12and10in levels0and255respectively, is not rescaled. This is the data that is being ‘quarantined’ from the rest of the data24by the buffer sections20and22.

FIG. 9shows the histogram corresponding to the image data after it has been JPEG compressed, transmitted to an output device and subsequently decompressed. The data16and18in the buffer sections20and22must be noise from levels0or10(or from the rest of the image data24, but as explained above, this noise is generally invisible to the eye). Therefore, mapping the data in buffer20back to level0and mapping the data in buffer22up to level255will correct any noise that would otherwise turn up in the white background or the full color side of a hard edge component in the image. Some noise in the buffers is from the rest of the data24. These pixels are also mapped to 0 or 255 and so end up slightly more erroneous in the output image, but the eye will not be able to see this.

Once the noise in levels0and255has been corrected, the rest of the data24can be redistributed back into the now vacant buffer sections20and22, as shown inFIG. 10. This is done by simply reversing Equation 1. Because the bandwidth was resealed to a smaller number of levels, expanding the data back out to the full bandwidth will mean the loss of some levels due to rounding. This means that the resulting contone image will be quantized slightly more coarsely. However, sacrificing 32 levels still leaves224which is ample for photographic quality image reproduction by the output device. Indeed, 90 to 100 levels is often deemed sufficient.

It should also be noted that the manipulation of the image data can be achieved in a computationally efficient way by incorporating it into existing data processing steps. The rescaling of the signal to move data out of the buffer sections can be done when the image data is color space converted from RGB to CMY(K). Furthermore, the re-distribution of data back across the full bandwidth can be done by adjusting the threshold values used in the dither matrix during halftoning. The Applicant's co-pending U.S. Ser. No. 11/482,980 incorporated herein by reference describes how the histogram can be expanded (or contracted) using the dither matrix. In light of this, the computational cost for preserving the data at one or more levels in the bandwidth is relatively little, yet the tangible image quality improvement is significant. The threshold values in the compressed range in the secondary matrix are determined using Equation 2:
Tnew=L1+Told.(Lh−L1)/256  Eq. 2
where:

Tnewis the compressed threshold values in the secondary dither matrix; and,

Toldis the threshold value in the primary dither matrix.

The adjusted dither matrix will not affect data at the extreme levels of the bandwidth as level0will still be below the lowest threshold value and level255will still be above the highest threshold level. Only data in the levels between the buffer sections will be ‘expanded’ by the adjusted dither matrix.

As discussed above, the noise in the white background of a hard edge is more visible than the noise in the full color area along the edge. This is particularly true if the output device is a printer. In light of this, only the data in level0can be preserved for a significant reduction in noise. This reduces the rescaling of the remaining signal so that when it is expanded back to the full bandwidth, less levels are lost and the contone image is not as coarse.

In other embodiments, the input signal is rescaled in a manner different to that the technique set out in Equation 1.FIG. 11shows the hard edged rescaling used in the above example. All the data in the buffer sections is shifted to the levels between16and240. However, the output image may be improved by rescaling the image with a non-linear function as shown inFIG. 12where most of the data is removed from the buffer sections but not all. Of course, Equations 1 and 2 would not apply to this method of rescaling.

The invention has been described herein by way of example only. Skilled workers in this field will readily recognize many variations and modification that do not depart from the spirit and scope of the broad inventive concept.