AU646002B2

AU646002B2 - Resolution conversion of bitmap images using error term averaging

Info

Publication number: AU646002B2
Application number: AU68038/90A
Authority: AU
Inventors: Kathleen Irwin
Original assignee: Wang Laboratories Inc
Current assignee: EISTREAM TECHNOLOGIES Inc
Priority date: 1986-06-26
Filing date: 1990-12-13
Publication date: 1994-02-03
Anticipated expiration: 2006-06-26
Also published as: JPS63503529A; CA1274021A; EP0270534A4; DE3687460D1; DE3687460T2; WO1988000377A1; EP0270534B1; JP2635034B2; EP0270534A1; AU6803890A; US4742553A

Description

COMMONWEALTH OF AUSTRALIA Patent Act 1952 Ab 0 .C M P E T E RPERQTFTrAT TnN

(ORIGINAL)

Class Int. Class Application Number Lodged Complete Specification Lodged Accepted Published Priority: Related Art Name of Applicant S Address of Applicant

S

SActual Inventor Address for Service WANG LABORATORIES, INC.

One Industrial Avenue LOWELL MA 01851 USA Kathleen IRWIN F.B. RICE CO., Patent Attorneys, 28A Montague Street, BALMAIN. 2041.

Complete Specification for the invention entitled: "RESOLUTION CONVERSION OF BITMAP IMAGES USING ERROR TERM AVERAGING" The following statement is a full description of this invention including the best method of performing it known to us:- I la RESOLUTION CONVERSION OF BITMAP IMAGES USING ERROR TPRM AVERAGING FIELD OF THE INVENTION The present invention relates to digital image processing, and in particular to the conversion of bitmap images from one resolution to another resolution.

BACKGROUND

One form of digital representation of images is a bitmap. In representing an image in a bitmap, the image is diviced into an array 0 of picture elements (pixels) and there is a one-to-one correspondence between pixels and digital storage. In its simplest form there is one I /S bit of storage for each pixel; this is a binary bitmap which

S.

represents an image where each pixel is one of two values (typically displayed as black and white, and.often 'referred to as "off" and If a bitmap includes a plurality of bits for each pixel, then pixels can be different colors or gray levels. For example, wvith four o bits per pixel, each pixel can have one of sixteen values; sixteen-valued pixels may be displayed as sixteen gray levels, sixteen different colors, or any sixteen combinations of intensity and color.

A bitmap representation of an image can be used in a variety of ways, such as: refreshing a video display, outputting on a printer, storing in RAM or in a disk file, image processing to enhance or combine images.

It is possible to represent in bitmap form an image that has more gray o3 levels than the bitmap has values per pixel. The simplest case is the use of a binary bitmap to represent images having gray scale. ;n this case, although each pixel will be either black or white, regions of the image encompassing pluralities of pixels will have apparent gray scale corresponding to the ratio of the number of black co the number of white pixels in the region.

1- -2- It is often desirable to convert the resolution of a bitmap image change the size of the bitmap array used to represent an image). This may be desirable in order to adjust for output devices of different' resolution that print different numbers of dots per inch) or to change the size of an image to fit a predetermined space (in which case the operation may be referred to as scaling).

One way to accomplish a reduction in resolution is to set each output pixel to the value of one of the input pixels, and ignore the other /o input pixels. This approach will lead to artifacts when the pattern of: input-to-output mapping correlates with dot patterns in the image: see* for example, if an image being subjected to a 2:1 reduction has a region where every other pixel is then that region (which appeared as 50% gray level in the input) will be either all "on" or all "off" in the output 0% or 100% gray level).

Another way to accomplish resolution conversion involve defining a mapping of input pixels to output pixels where al'l input pixels are used and where a plurality of input pixels are mapped to single output pixels. The value of an output pixel is determined by the average of the values of the mapped input pixels. This method has the limitation that, because the output pixels are represented by digital values, the output pixels will not in general be able to represent precisely the average of the corresponding input pixel values. A conversion by 2:1 Z5 horizontally and 2:1 vertically will serve as an example. In this case, there are four input piels for each output pixel, and therefore the average of the input pixels that correspond to a single output pixel can have one of five values (there can be 0, 1, 2, 3, or 4 pixels "on" at one time); yet eacn output pixel can have only one of two values. Output pixel values could be determined as follows: 0-2 input pixels "on" results in the output pixel being "off", and 3-4 input pixels being "on" results in the output pixel being If this method is used, then a region in the input image that had one quarter of the pixels "on" will result in the corresponding region of 3S the output image having none of the pixels and a region in the input image that had three quarters of the pixels "on" will result in

U

3 the corresponding region of the output image having all of the pixels This means that some of the gray scale representation will be lost.

When converting the resolution of an image having gray scale, it is desirable to maintain the gray scale in the converted image. It is particularly difficult to do so when gray scale is represented in a macroscopic way, in other words, by more than individual pixel values (for example, by the ratio of the numbers of "on" pixels to "off" pixels).

It is an object of the present invention to accomplish resolution conversion while maintaining gray scale, even when gray scale is represented macroscopically.

SUMMARY OF THE INVENTION According to the present invention an input bitmap is converted to an output bitmap having a different resolution from the input bitmap. In so doing, the cutput pixel values are determined not just on the basis of the ,o mapped input pixels, but also on the basis of an error S: 20 term that is carried from one or more preceding output pixel determinations.

The present invention provides a method of converting an input digital image to an output digital image by converting a set of input image pixels to a set of output image pixels, each pixel having a value with a predefined range, the method comprising: defining a mapping between input pixels and output pixels; providing for storage of an error term and storing an initial value of the error term; ior each pixel in the output image, determining a value for the output pixel as follows: determining a test value from a combination of the error term and the values of the input pixels mapped to the current output pixel; 3a (ii) determining the value of the output pixel from the test value by comparing the test value and a threshold value wherein the value of the output pixel is a first value when the test value exceeds the threshold value and is a second value when the test value does not exceed the threshold value; (iii) updating the error term by determining the error term to be the test value minus an offset value when the test value exceeds the threshold value and to be the current error term value when the test value does not exceed the threshold value.

A method of converting an input image or picture to an output image or picture is also provided.

The present invention further provides an image converter arranged to convert an input image to an output image, each of the input and output images comprising a set of pixels and each pixel having a value within a 20 predefined range, the sets of pixels being represented by an input bitmap and an output bitmap respectively, the image converter comprising: storage means arranged to save an error term; means for providing an initial error term; S 25 test value evaluation means arranged to determine a test value associated with a pixel in the output bitmap from a combination of the error term saved in said storage means and the value of a plurality of S" pixels in the input bitmap from which the pixel in the output bitmap is mapped by comparing the test value and a threshold value wherein the value of the output pixel is a first output value when the test value exceeds the threshold value and is a second output value when the test value does not exceed the threshold value; 3b output means arranged to evaluate and output a value for a pixel in the output bitmap from the test value for that output pixel and to update the saved error term by determining the error term to be the test value minus an offset value when the test value exceeds the threshold value and to be the current error term value when the test value does not exceed the threshold value.

In a preferred embodiment mapping is defined between input pixels and output pixels, which in the simplest case maps a plurality of input pixels to each output pixel.

The value of each output pixel is determined as follows: Adding the current value of an error term to a representation of the average of the values of the mapped input pixels, thereby determining a test value; if the test value is greater than a threshold, setting 0 e 0 0 0 0 0 *00.

o *oeo -4the output pixel to a value of 1 and subtracting an offset value from the error term; if the test value is less than the threshold, setting the output pixel to a value of 0 and updating the error term to be equal to the test value.

BRIEF DESCRIPTION OF THE DRAWING The invention is pointed out with particularity in the appended claims. The above -nd other advantages of the invention may be better /o understood by referring to the following detailed description in conjunction with the drawing, in which: Fig. 1 shows relationships between the logical components of an image conversion system using the present invention; Figs. 2A, 2C,'and 20 illustrate the calculations involved in a *conversion from an input bitmap to an output bitmap according to the present invention, while Fig. 2B shows an output bitmap that would result when not employing the present invention; a 0 Figs. 3A and 3B show a mapping from an input bit map (Fig. 2A) to an output bitmap (Fig. 28) for a resolution reduction of 2:1 horizontally and 4:1 vertically; *s t I 0- Figs. 4A, 48, 5A, 5B, 6A, and 6B show input bitmap to output bitmap mappings for other resolution conversion ratios; and Figs. 7A, 78, and 7C show, respectively, a section of an input bitmap, a section of an output bitmap, and the superimposition of the section 3o of the output bitmap on the section of the input bitmap.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT In Fig. 1, an image conversion system is shown having an image converter 10 for converting an image in an input bitmap 12 to an image in an output bitmap 14. The image converter 10 includes an error term 16, an error term initializer 20, a test value generator 22, a threshold comparator 24, an update means 26 for updating the value of the error term 16, and an output means 28 for setting a pixel value in ,o /0 the output bitmap 14.

a. The error term 16 stores a value so that the value generated by the update means 26 is available to be used by the test vaiue generator 22 to compute the next test value. There is not necessarily a memory /S location dedicated to storing the value of the error term. In fact, because of its central role, to, the extent possible it is kept in one or more internal CPU registers.

The error term initializer 20 is arranged to set the value of the Qo error term prior to the conversion of the first pixel of a bitmap.

Subsequently, the value of the error term is controlled by the update means 26, which adjusts the value of the error term 16 each time an o,.o.6 output pixel is set.

The test value generator 22 is arranged to define a mapping of pixels in the input bitmap 12 to pixels in the output bitmap 14. For each of the pixels in the output bitmap (in succession), the test value generator 22 adds to the current value of the error term the values of the pixels in the input bitmap that correspond to that output pixel.

3o This sum is the test value, which is passed to the threshold comparator 24.

The threshold comparator 24 determines whether the current test value is greater or less than a threshold value. Although there may in some 3s situation be some advantage in varying the threshold, in this illustrative embodiment the threshold is fixed. In order to make the

I

-6threshold comparison a simple operation, the threshold value is zero; this reduces the threshold comparison operation to that of testing the sign of the test value a minus sign indicates less than the threshold, a plus sign indicates greater than the threshold).

The result of the threshold comparison is used to control updating of the error term. If the threshold is exceeded the sign of the test value is positive), then the update means 26 arranges for the errc" term to be equal to the test value minus an offset value. If /0 the threshold is not exceeded, then the update means 26 arranges for the error term to be equal to the current test value; in fact, this case requires no specific action, because the test value is stored in the register that is used by the test value generator for the error term.

S 9 The offset value is equal to the maximum possible total of the values of the input pixels mapped to a single output pixel. Specifically, for a binary bitmap having a mapping where no input pixel maps to more than one output pixel, the offset value is equal to the number of o ao input pixels mapped to an output pixel.

S The result of the threshold comparison is also used to control the •setting of output pixel values. If the threshold is exceeded, then the output means 28 sets the value of the output pixel to be 1; 6 otherwise the value of the output pixel is 0.

The error term serves to link successive output pixel determinations.

This provides the advantage that the ratio of "on" pixels to "off" pixels in the output bitmap will more closely correspond to the ratio in the input bitmap than if each output pixel value was determined independent of the values of the other output pixels.

The above feature of the invention can be seen by the example illustrated in Figs. 2A, 2B, 2C, and 2D. Fig. 2A shows a series of input pixels in which three quarters of the pixels are The mapping of input pixels to output pixels for a conversion ratio of 3:1 -7i. indicated in Fig. 2A by heavier lines every three pixels. Fig. 28 shows the output pixels when not employing the present invention.

Fig. 2C shows the output pixels according to the present invention.

In Figs. 2A, 28, and 2C, "on" pixels are indicated by the presence of an and "off" pixels are indicated by the absence of the Fig. 2D shows values computed in converting from the input bitmap of Fig. 2A to the output bitmap of Fig. 2C, In Fig. 28, all of the pixels are "on" because for each output pixel /0 more than half of the input pixels that map to the output pixel are "on".

S

Fig. 2C illustrates the gray level preservation that can beaccomplished using the present invention: three quarters of the output pixels are the same ratio as for the input pixels.

Fig. 2D shows the values calculated in accomplishing the conversion from Fig. 2A to Fig.'2C. For this conversion, three' input pixels are mapped to each output pixel. Therefore, an offset value of 3 is .o subtracted each time an "on" output pixel is generated. And therefore, the error term is initialized to a value of -1.5 (one half S of the amount corresponding to an "on" pixel). Each test value is the sum of the number of "on" pixels and the preceding value of the error term. When the test value exceeds 0 (as is tile case for the first.

S' a second, and fourth output pixels), the output value is 1 and the error term is updated to be the test value minus 3. When the test value is less than 0 (as is the case for the third output pixel), the output value is 0 and the error term is upoated to be equal to the test value.

The above example started with an input image having a constant gray level for simplicity of illustration. In general the gray level will not be constant, but will vary across an image. The output bitmap produced by the present invention will not necessarily represent 3S precisely the same gray level as in the input bitmap. Nonetneless, the gray level in the output bitmap will track the gray level of the input bitmap on the average.

It is often desirable when using a digital computer to perform calculations to restrict the manipulated values to integers. The above example could be modified in two different ways to use integer calculations: the initial value cf the error term could be rounded to an integer value (this would have a small effect on the initial calculations, but no lasting effect; in fact, a convenient value such /0 as zero could be used as the initial value, resulting in less than qe ideal choices for the first few pixels, but without lasting effect; the degree of the non-ideal effect will depend an how far the initial value is from the ideal initial value, which is half of the offset); or all calculations could be doubled the initial value of S• /5 the error term would be the value of 2 would be added for every "on" pixel, and an offset value of 6 would be subtracted whenever an "on" output pixel is generated).

In an illustrative embodiment, the present invention is implemented 0o using a microcomputer system having various image manipulation so"ware, including in particular a resolution conversion subroutine written in 8086 assembly language and described in further detail below.

5 The resolution conversion subroutine includes an initialization portion followed by a series of conversion-ratio-specific routines.

The initialization portion loads input parameters into certain CPU registers and then branches to the conversion-ratio-specific routine designed to handle the conversion ratio requested. The input 3o parameters include pointers to each of typically several rows of an input bitmap and to plrces where one or more rows of an output bitmap are to be stored: for example, for a 3:1 x 3:1 conversion pointers are provided for three input rows and one output row; for a 3:2 x 3:2 conversion pointers are provided for three input rows and for two output rows.

-9- Each call to the resolution conversion subroutine does one conversion pass across an image. Each such pass iill typically "consume" some input lines and generate one or more output lines, the numbers of lines depending on the conversion ratio. This subroutine will generally be called repeatedly in order to convert an entire image.

Four of the conversion-ratio-specific routines are further described below. As will be seen in the following four examples, the desire to optimize for conversion speed and the different types of mappings 10 necessitated by different conversion ratios result in differences among the conversion-ratio-specific routines.

S

The mappings defined by the four exemplary conversion-ratio-specific routines are illustrated in Figs. 3A through 6B: Figs. 3A, 4A, S and 6A illustrate input bitmaps; Figs. 3B, 48, 5B, and 6B illustrate the corresponding output bitmaps. In :oth the input and output bitmaps, the individual pixels are delineated by fine lines. In the input bitmaps, heavier lines are used to delineate groups of pixels, each group corresponding to a single pixel in the output bitmap. Each 2o group includes an alphanumeric designation; the identical designation appears in the pixel in the output bitmap to which that group of input '.pixels is mapped. In the mappings of Figs. 5A and 6A, some of the input pixels are not mapped to any output pixel; these unmapped pixels are indic'ted by the designation The alphabetic order of the 2 designations corresponds to the order in which the output pixel values are generated B, C, D and so forth, and A1, A2, A3, A4, B1, B2, B3, B4, and so forth); this is the order in which the error term is propagated.

3o The following is a guide to the "structured English" used below to describe the four conversion-ratio-specific routines: Indented statements following an "if" statement indicate actions that are taken if the condition is true; Indented statements following a "for" statement are repeated as indicated in the "for" statement; Indented statements following a colon are an expanded description of the action described in the statement ending with the colon; Single letter or number labels on the left edge indicate points to which statements branch.

In the following descriptions, the term "block" refers to that rectangular group of input pixels that is the basic repeating pattern by which the conversion is accomplished. For simple mappings, the /O pixels in a block all map to a single output pixel. For more complex mappings, two or more output pixels are generated from a single input block.

S* The input bitmap is represented as N streams of bytes, where N depends /6 on the vertical conversion ratio. The output bitmap is represented as M streams of bytes where M depends on the vertical conversion ratio.

The output mask is a byte or word with a single bit set. This bit is shifted so as to be in the bit position corresponding to the current 10 output pixel. Prior to determining the values of any output pixels in a particular output byte, the byte is set to zero. When an output value is determined to be one, the output mask is ORed with the output byte; when an output value is determined to be zero, no action on the output byte is needed.

00 00 0 a 2:1 x 4:1 The mapping is shown n Figs. 3A and 38 for a 2:1 horizontal by 4:1 vertical rusolution reduction. Some features of the routine for this 3o conversion are the following: tests are made for the special cases of a byte having all 1s or all Os, in which cases processing of the individual bits of the byte is not necessary; adding of the values of the input pixels is done by shifting and testing.

-11- The 2:1 x 4:1 conversion is accomplished generally as indicated by the following structured English:

S

0

S.

S

OS.S

S

0* S *5

S

0 Initialize the error term to -4.

L Load next 16-bit word of each of 4 lines (2:1 horizo 1 input word will correspond to 1 output byte; 4:1 v that 4 input lines are needed to compute 1 output li If the 4 words are equal to each other, If the 4 words are equal to 0, Output a byte of all Os and branch to L (to load words) (the error term is unchanged).

If the 4 words are equal to all 1s, Output a byte of all is and branch to L (to load words) (the error term is unchanged).

15 Initialize the output mask and initialize (to zero) B Add the bits in the next block to the.error term, i.

For each of the four input words, Rotate the word and add carry to the error term.

Rotate the word again and add carry to the error If the error term is positive, Set the next output bit OR output mask with Subtract 8 from the error term.

Rotate the output mask.

f the output mask has not rotated all the way aroun bits have not yet been completed), Branch to B (to do next block).

Store the output byte.

If not at the end of the input data, Branch to L (to load next set of 4 input words).

3o Exit.

ntal means that ertical means ne).

next set of 4 next set of 4 the output byte.

e.: term.

output byte).

d 8 output Note that a 1:1 x 2:1 conversion benefits from a similar test for a special case: if a byte from the first line is equal to the corresponding byte from the second line, then that byte is output with 3. no change in the error term and without need to process the individual bits of the byte.

-12- 3:1 x 3:1 The mapping is shown in Figs. 4A and 4B for 3:1 horizontal by 3:1 vertical resolution reduction. Some features of the routine for this conversion are the following: adding of the values of the input pixels is done by "mask and lookup"; to use integer arithmetic, the initial value of the error term is rounded from the ideal value of and /0 a block can span byte boundaries.

.o Prior to any calls to the resolution conversion routines, various system initialization operations are performed including execution of a subroutine that generates a 256 entry lookup table by counting the 5" s in each of the single byte values 0-255. This lookup table is used by the below--described routine to count "on" pixels.

The 3:1 x 3:1 conversion is accomplished generally as follows: D.0 Initialize the output mask.

Initialize the output byte to zero.

Initialize count of input bits left to zero (the bits left to be processed in the current input word).

Initialize the error term to a L Add 8 to bits left.

For each of the 3 input words (one for each of 3 input lines), Put the 8 bits of the next input byte into the bit positions in °the input wor- following any bits left to be processed.

B For each of the 3 input words, Add the values of the 3 least significant bits to the error term, S.e.: Mask out all but all but the 3 least significant bits.

Use this as an index to a lookup table to retrieve a value from the table which is the number of 1s in the index to the table.

Add this number to the error term.

Shift the input word by 3 bits.

-13- If the error term is positive, Set the next output bit.

Subtract 9 from the error term.

Rotate the output mask.

If the out'put mask has rotated all the way around, Store the output byte.

Initialize the output byte to zero.

Subtract 3 from bits left.

If there are still more than 3 bits left (to be processed in the /0 current set of input words), Branch to B (process next block), If not at end of input data, Branch to L (load next 8 bits into each of the input words).

Exit.

3:2 x 3:1 The mapping is shown in Figs. 5A and 5B for 3:2 horizontal by 3'1 a< vertical resolution reduction. A feature of the routine for this S •conversion is that a complex mapping is used, in which: there are two output pixels per block of input pixels; the set of input pixels that maps to a single output pixel is not in the form of a rectangular array; and not all input pixels are mapped to output pixels.

S

°The 3:2 x 3:1 conversion is accomplished generally as follows: 0 Initialize the output mask.

3o Initialize the error term to -2.

Initialize the output byte to zero.

Initialize the pattern flag to 1 (processing pattern repeats every 3 input bits, after a new input byte is retrieved this indicates where in the processing pattern to continue; this flag has 3 possible 3S' values: 1, 2, or 3).

L Load next byte of each of 3 input lines.

-14- Set bit counter to 8 (8 input bits will be processed before another load is required).

Branch to 1, 2, or 3 depending on the value of the pattern flag.

1 Process the first third of the processing pattern, i.e.: E" Shift 1st byte and add carry to the error term.

Shift 2nd byte and add carry to the error term.

Shift 3nd byte and add carry to the error term.

Decrement the bit counter.

If the bit counter is nonzero, /0 Branch to 2.

Set the pattern flag to 2.

If there is more input data, Branch to L.

e Exit.

2 Process the second third of the processing pattern, i.e.: *0 Shift 1st byte and add carry to the error term.

If the error term is positive, Set the output bit.

Subtract 4 from the error term.

2.o Shift 2nd.byte (and ignore carry this input oit has no effect on the output because it is not mapped to any output pixel see Fig. Rotate the output mask.

Shift 3rd byte and add carry to error term.

*.26 s Decrement the bit counter.

If the bit counter is nonzero, Branch to 3.

o16 Set the pattern flag to 3.

If there is more input data, Branch to L.

Exit.

3 Process the last third of the processing pattern, i.e.: Shift 3rd byte and add carry to the error term.

Shift 2nd byte and add carry to the error term.

3S Shift 1st byte and add carry to the error term.

If the error term is positive, Set the output bit.

Subtract 4 from the error term.

Rotate the output mask.

If the output mask has rotated all the way around, Store the output byte.

Initialize the output byte to zero.

Decrement the bit counter.

Set the pattern flag to 1.

If there is more input data, Branch to L.

E i t.

6 3:2 x 3:2 /S The mapping is shown in Figs. 6A and 6B for 3:2 horizontal by 3:2 vertical resolution reduction. A feature of the routine for this conversion is that a complex mapping is used, in which: there are four output pixels per block of input pixels; the set of input pixels that maps to a single output pixel is not o .11 0 in the form of a rectangular array; not all input pixels are mapped to output pixels; and two lines of output pixels are gsnerated during one pass (each pass uses 3 lines of input pixels).

6 The 3:2 x 3:2 conversion is accomplished generally as follows: Initialize the output mask.

Initialize the error term to -1.

Initialize the output bytes to zero (in one processing pass output will be generated for 2 output lines).

Initialize the pattern flag to 1 (processing pattern repeats every 3 input bits, after a new input byte is retrieved this indicates where in the processing pattern to continue; this flag nas 3 possible values: 1, 2, or 3).

3 L L oad the next input byte of each of 3 lines.

I

-16- Set the bit counter to 8 (8 input bits will be processed before another load is required).

Branch to 1, 2, or 3 depending on the value of the pattern flag.

1 Process the first third of the processing pattern, i.e.: S- Shift 2nd byte and add carry to the error term.

Shift 3rd byte and add carry to the error term.

If the error term is positive, Set the output bit for the 2nd output line.

Subtract 2 from the error term.

/0 Shift 1st byte and add carry to the error term.

-'Decrement the bit counter.

If the bit counter is nonzero, Branch to 2.

S- Set the pattern flag to 2.

/5 If there is more input data, Branch to L.

S* Exit.

0000 2 Process the second third of the processing pattern, i.e.: Shift 1st byte and add carry to the error term.

If the error term is positive, Set the output bit for the 1st output line Subtract 2 from the error term.

Shift 2nd byte (and ignore carry this input bit has no effect on the output because it is not mapped to an output pixel).

25 Rotate the output mask.

Shift 3rd byte and store carry in a temporary location (so that the order of the output pixels in which the error term is propagated is as indicated in Fig. 6B).

Decrement the bit counter.

So If the bit counter is nonzero, Branch to 3.

Set the pattern flag to 3.

If there is more input data, Branch to L.

536- Exi t.

I -17- 3 Process the last thi Shift 1st byte and Shift 2nd byte and If the error term Set the output b Subtract 2 from Add the temporaril Shift 3rd byte and If the error term /0 Set the output b Subtract 2 from Rotate the output rd of tie processing pattern, i.e.: add carry to the error term.

add carry to the error term.

is positive, it in the 1st output line.

the error term.

y stored carry to the error term.

add carry to the error term.

is positive, it in the 2nd output line.

the error term.

C

0 o

C

0 *r 0 IocC e g.

S C

S

*0 C

C

C. Ce

C

nask.

I

If the output mask has rotated all the way around, Store the output bytes.

Initialize the two output bytes to zero.

Decrement the bit counter.

Set the pattern flag to 1.

If there is more input data, Branch to L.

Exit.

An alternative to the above-described approach to mapping involves the mapping of some input pixels to more than one output pixel and the use of a weighted average. Assume a conversion of the form N:Q by M:R, 21,Start by logically breaking the input bitmap into an array of rectangular sections each of dimension NxM pixels (one such section is shown in Fig. 7A for the case where also. logically break the output bitmap into an array of rectangular sections each of dimension QxR pixels (one such section is shown in Fig. 7B for the case where So The input pixels in each of the rectangular input sections map to the output pixels in the corresponding output section (so far, this is the same as the previously described mapping approach).

Superimpose a QxR array on an NxM array, as is shown in Fig. 7C for th, case of a 3:2 x 3:2 reduction. Input pixels map to those output pixels with which they overlap. Specifically, it can be seen from -18- Figs. 7A, 78, and 7C that input pixels a, b, d, and e all map to output pixel A. Note, however, that the input pixels overlap differing amounts, and note that while input pixel e maps to four output pixels 8, C, and input pixel a maps to a single output S pixel When the mapping described in the previous paragraph is used, it is desirable to adjust the way input pixel totals are calculated. In particular, when computing a total for a given output pixel, each /0 input oixel should contribute to the total to an extent proportional to the extent of that input pixels overlap with the output pixel.

When computing the total for output pixel A in the case shown in Figs.

7A, 7B, and 7C, input pixel a should be weighted twice as heavily as Sinput pixels b and d, and input pixel a should be weighted four times /$as heavily as input pixel e. In order to use integer arithmetic, the total for output pixel A could be computed as follows: *4Va 2Vb 2Vd Ve where Va, Vb, Vd, and Ve are the values of the corresponding input pixels. If the output pixels have binary values, then the offset to 2o be subtracted when an output pixel is set should be 9, and the initial value of the error term should be -4.5 (although to use integer "arithmetic -5 would be close enough).

o* Mappings whe're input pixels map to differing numbers of output pixels 2, can be used without the above-described weighting of pixels. This has the advantage of being computationally simpler, but has the S* disadvantage that it may degrade the quality of the output image.

As described in the examples above, the error t'rm is initialized once per row of the bitmap. Alternatively, the error term can be initialized more or less frequently. For example, the error term might be initialized once per bitmap.

In the above conve)sion examples all involve reduction in resolution, there are fewer pixels in the output bitmap than in the input bitmap. The present invention may also be useful in cases of -19increases in resolution. A 2:3 x 1:1 conversion is an example of an increase in resolution. The processing pattern repeats every three output pixels (which consumes two input pixels). A weighted mapping could be used such that the first input pixel maps to the first output S pixel with a weight of 2; the first input pixel and the second input pixel each map to the second output pixel with a weight of 1; and the second input pixel maps to the third output pixel with a weight of 2.

With such weighting, the error term would ideally be initialized to and an offset of 2 would be subtracted for each output pixel set /0 "on".

In the above examples, the error term is carried through a horizontal pass across a bitmap. One might alternatively carry the error term in two directions: vertically as well as horizontally. An error term can be initialized for each column in a bitmap. (As processing is done on a row-by-row basis, there is no need to create error terms for all the rows at once.) For each output pixel, the values of the mapped input pixels are added to the sum of the row error term and the appropriate column error term. When an updated error term is computed, half of it could be allocated to become the updated column error term and half could become the updated row error term.

In the above-e>amples there is one bit per pixel in both the input and S' output bitmaps. The invention may also be employed where each pixel S95 in either the input or output bitmaps is represented by more than one bit, including where th input and output bitmaps use differing numbers of bits per pixei.

While the above description is in terms of "gray level", the pixel 3o values could actually represent colors. Further, if used with color images, one might alternatively use a plurality of error terms, one for each color. This would be useful in maintaining the same relative proportions of the different colors in the output bitmap as in the input bitmap.

The foregoing description has been limited to specific embodiments of the invention. Additional advantages and modifications will be apparent to those skilled in the art. The invention is, therefore, not limited to the specific details, representative apparatus, and illustrative examples shown and described in this specification.

Rather, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope o.f the invention.

*C

a 0 0

II.

Claims

1. A method of converting an input digital image to an output digital image by converting a set of input image pixels to a set of output image pixels, each pixel having a value with a predefined range, the method comprising: defining a mapping between input pixels and output pixels; providing for storage of an error term and storing an initial value of the error term; for each pixel in the output image, determining a value for the output pixel as follows: determining a test value from a combination of the error term and the value of the input pixels mapped to the current output pixel; (ii) determining the value of the output pixel from the test value by comparing the test value and a threshold value wherein the value of the output pixel is a first value when the test value exceeds the threshold value and is a S 20 second value when the test value does not .:.exceed the threshold value; (iii) updating the error term by determining the L: error term to be the test value minus an offset value when the test value exceeds the S 25 threshold value and to be the current error term value when the test value does not exceed

2.the threshold value. 2. The method of ulaim 1 wherein the output image e differs irn resolution from the .Lnput image.

3. A method of converting an input image to an output image, each of the input and output images comprising a set of pixels and each pixel having a value with a predefined range, the sets of pixels being represented by an input bitmap and an output bitmap respectively, the method comprising: .B ti~ 22 *8 V V *D V V *e V. S defining a mapping between pixels in the input bitmap and pixels in the output bitmap; providing for storage of an error term and storing an initial value of the error terms; for each current pixel in the output bitmap, determining an output value as follows: determining a test value from a combination of the error term and the values of the input pixels mapped to the current output pixel; (ii) determining the output value from the test value by comparing the test value and a threshold value wherein the value of the output pixel is a first output value when the test value exceeds the threshold value and is a second output value when the test value does not exceed the threshold value; (iii) updating the error term by determining the error term to be the test value minus an offset value when the test value exceeds the 20 threshold value and to be the current error term value when the test value does not exceed the threshold value.

4. A method of reducing the size of an input picture having visually apparent gray scale to create an output 25 picture that also has visually apparent gray scale, the method comprising: storing the input picture by storing a value for each element of the picture in a storage medium; defining a mapping between picture elements in the input picture and picture elements in the output picture; providing storage for an error term and storing an initial value of the error term; for each picture element of the output picture, determining the picture element's value as follows: o3" p 23 determining a test value from a combination of the error term and the values of the input picture elements mapped to the output picture element; (ii) determining the value of the output picture element by comparing the test value and a threshold value wherein the value of the output picture element is a first output value when the test value exceeds the threshold value and is a second output value when the test value does not exceed the threshold value; (iii) updating the error term by determining the error term to be the test value minus an offset value when the test value exceeds the threshold value and to be the current error term value when the test value does not exceed the threshold value; storing the output picture by storing the values of the picture elements of the output picture in a 20 storage medium.

5. The method of claim 2 wherein input pixels are mapped to output pixels such that no input pixel is mapped to more than one output pixel and a plurality of input pixels are mapped to each output pixel, the offset ralue is equal to the number of input pixels that are mapped to that output pixel for which an output value is being determined, and the value representing a total is the count of the number of input pixels having values of I that are mapped to that output for which an output valae is being determined.

6. The method of claim 2 wherein the value of the input pixels mapped to a current output pixel for which a test value is being determined is a total representing is a weighted count of the input K;i~Z, n" p 3 24 pixels that are mapped to the current output pixel and that have values of i, where the weight of each input pixel mapped to the current output pixel and having a value of 1 is inversely related to the number of output pixels to which the input pixel is mapped.

7. The method of claims i, 2, 3 or 4 wherein the test value is a sum of the error term and a value representing a total of the values of the input pixels mapped to that output pixel for which an output value is being determined.

8. The method of claims i, 2, 3 or 4 wherein each pixel in the output bitmap is associated with one of a plurality of rows, and wherein for each row, the error term is initialized for generation of a first output pixel value of the row, and for each succeeding pixel in the row the error term is updated on the basis of the preceding output pixel value.

9. The method as claimed in any of claims 1 to 5 wherein the error term is initialized for generation of a first output value, and for each succeeding output value the 20 error term is updated on the basis of the preceding output value.

An image converter arranged to convert an input image an output image, each of the input and output images comprising a set of pixels and each pixel having a value a. 25 within a predefined range, the sets of pixels being represented by an input bitmap and an output bitmap respectively, the image converter comprising: e• storage means arranged to save an error term; means for providing an initial error term; test value evaluation means arranged to determine a test value associated with a pixel in the output bitmap from a combination of the error term saved in said storage means and the value of a plurality of pixnls in the input bitmap from which the pixel in the output bitmap is mapped by comparing the test j 7\ 5~ %f l.l 25 value and a threshold value wherein the value of the output pixel is a first output value when the test value exceeds the threshold value and is a second output value when the test value does not exceed the threshold value; output means arranged to evaluate and output a value for a pixel in the output bitmap from the test value for that output pixel and to update the saved error term by determining the error term to be the test value minus an offset value when the test value exceeds the threshold value and to be the current error term value when the test value does not exceed the threshold value.

11. The image converter of claim 10 wherein the output means comprises:- comparison means for determining if the test value is greater than a threshold; (ii) output evaluation means responsive to the comparison means and arranged to, 20 if the test value is greater than the threshold, determine the output value to be 1, and set the error term to the test value minus an offset value, and 0 9 0 *0 0 0 0a 0~ 0 0 0** 0 0 0e 0* 0 0 9009 0 0 Cee 0 I if the test value is not greater than the threshold, 25 determine the output value to be 0, and set the error term to the test value.

12, The image converter of claim 10 wherein the mapping of input pixels to output pixels is such that no input pixel is mapped to more than one output pixel and a plurality of input pixels ar.. mapped to each output pixel, the offset value is the number of input pixels that map onto the output pixel for which the test value is being determined, and a value of a plurality of pixels in the input bitmap 26 from which the pixel in the output bitmap is mapped and for which a test value is being determined is a total representing the number of input pixels that are mapped to the pixel in the output bitmap and that have a value of i.

13. The image converter of claim 11 wherein the mapping of input pixels to output pixels is such that at least some of the input pixels are each mapped to a plurality of output pixels, and a value of a plurality of pixels in the input bitmap from which the pixel in the output bitmap is mapped and for which a test value is being determined is a total representing a weighted count of the number of input pixels that are mapped to the pixel in the output bitmap, and that have a value of i, where the weight for each input pixel for which a test value is being determined is inversely related to the number of output pixels to which the input pixel is mapped.

14. The image converter of claims 10, 11, 12 or 13 wherein test value evaluation means comprises mapping :r 20 means defining a mapping between pixels in the input :bitmap and pixels in the output bitmap, and summation means arranged to compute a sum of the error term and a value representing a total of thR values of those pixels in the input bitmap that map onto the output pixel for S 25 which the test value is being determined.

15. The image converter of claims 10, 11, 12, 13 or 14 wherein each pixel in the output bitmap is associated with one of a plurality of rows, the image converter further comprising means for initializing the error term prior to the determination of a first output pixel value for that row, and wherein the means for updating the error term determines the value of the error term prior to the determination of output values of subsequent pixels in that row.

16. The image converter of claims 10, 11, 12, 13 or 14 d i 27 further comprising means for initializing the error term prior to the determination of the value of a first output pixel, and wherein the means for updating the error term determines the value of the error term prior to the determination of output values of subsequent pixels in the output bitmap. DATED this 18 day of November 1993 WANG LABORATORIES, INC. Patent Attorneys for the Applicant: F.B. RICE CO. *c a a a a a Ire