Method for enlarging an image stored in run representation form

• US 4,885,786 A
• Filed: 05/24/1988
• Issued: 12/05/1989
• Est. Priority Date: 10/24/1984
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Anderson, Karen L., Pennebaker, William B., Pennington, Keith S.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/198,666
• Time in Patent Office: 560 Days
• Field of Search: 382/44, 382/47, 340/728, 340/731, 358/261, 358/283, 358/287
• US Class Current: 382/235
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403
• CPC Class Codes: H04N 1/3935 with modification of image resolution, i.e. determining the values of picture elements at new relative positions

Abstract

The method according to the present invention enlarges a binary digital image by a method comprising the steps of: storing the rows of the image as a plurality of run end representations, in which a row is represented as a sequence of values giving the white and black run ends; enlarging each row of the image along the horizontal axis by altering the value of each run end representation to achieve enlargement on the horizontal axis by a factor F1; enlarging the image along the vertical axis by interpolating rows between the lines of the partially enlarged image so as to produce enlargement along the vertical axis by a factor F2; storing the enlarged size image generated by the above steps in run end form. An image enlarged by the method of the present invention may be reduced by the simple technique of dividing the image into blocks of pixels and assigning one pixel in a reduced image for each block of pixels in the larger image. Each pixel in the reduced image may by set equal to a center pixel in each block.

Claims

1. A method for enlarging a binary digital image along first and second axes thereof by factors of F1 and F2, respectively, said binary image having rows of picture elements or pels, said rows arranged adjacently along said second axis and containing runs of white and black pels, comprising the steps of:

storing the rows of said image as a plurality of run ends with each row being represented as a sequence of values corresponding to the unnormalized white and black run ends;

partially enlarging said binary image along said first axis by altering the value of each unnormalized run end in the respective rows by a predetermined factor F1;

further enlarging said binary image along said second axis by creating additional rows interpolated between the rows of the partially enlarged image produced by the preceding step, using the corresponding run ends of the rows of the partially enlarged image adjacent the additional interpolated rows to determine the positions of the white and black run ends on the interpolated rows, the number and distribution of said interpolated rows being chosen so as to produce enlargement along said second axis by a predetermined factor F2; and

storing said enlarged size image generated by the above steps in said unnormalized run end form.

2. A method according to claim 1 in which said enlarging steps further comprise the step of:

compensating for output device characteristics which produce white and black pels of different sizes by adjusting characteristics of white and black runs.

3. A method according to claim 1 wherein said step of enlarging each row of said binary image along said first axis further comprises:

obtaining the run end values describing a current row of said image to be enlarged;

multiplying each run end value in said current row by F1 to enlarge each run and thereby said current row by a factor of F1;

detecting edge pel position changes in said image along said second axis by comparing run end locations from previous enlarged rows with those of said enlarged current row;

smoothing edges ending on the row preceding the current row by accordingly adding or removing pels from said edges; and

repeating said obtaining, multiplying, detecting, and smoothing steps until all rows of said binary image have been enlarged.

4. A method according to claim 1 in which F1 is equal to 3.

5. A method according to claim 1 in which F2 is equal to 3.

6. A method according to claim 1 in which said first axis is a horizontal axis.

7. A method according to claim 1 in which said second axis is a vertical axis.

8. A method for enlarging a binary digital image along one axis thereof by a predetermined factor F, said binary image having lines of picture elements or pels, said lines arranged adjacently along said one axis and containing runs of white and black pels, comprising the steps of:

initializing a buffer with unnormalized run end values corresponding to those of the runs of white and black pels in a number of adjacent lines selected from said image, said lines comprising two extreme lines disposed respectively at the two ends of sid buffer along said one axis;

discarding one of the extreme lines from one end of said buffer;

reading the unnormalized run end values describing a line of said image adjacent said other extreme line, and adding said run end values of said adjacent line to the other end of said buffer following the other extreme line;

interpolating zero or more lines between two selected lines of said buffer, in accordance with said predetermined enlargement factor F along said one axis, by creating respective run end values to describe each interpolated line;

selecting the run end locations for said interpolated lines being generated by examining the image lines in said buffer, in order to detect edge pel position changes along said axis and smoothing edges by accordingly adding or removing pels from said edges;

storing said zero or more interpolated lines and said selected line nearer said other end of said buffer in run end form; and

repeating said discarding, reading, adding, interpolating, selecting, and storing steps for all lines of said image.

9. A method for enlarging a binary digital image along first and second axes thereof by factors of F1 and F2, respectively, said original binary image having rows of picture elements or pels, said rows arranged adjacently along said second axis and containing runs of white and black pels, and then reducing the enlarged binary image to the original binary image size, such that the image that results upon reductiin after said original binary image has been enlarged is identical to said original binary image, comprising the steps of:

storing the rows of said original binary image as run end representations, in which each row is represented as a sequence of integer values corresponding to the unnormalized white and black run ends;

enlarging said original binary image by the steps of;

enlarging each row of said original binary image along said first axis by altering the integer value of each run end in the run end representation corresponding to each respective row by a predetermined factor F1, in such manner that for each pel represented in said each respective row there exists a pel at a known position in the produced enlarged image row having the same binary value as said pel represented in said each respective row;

further enlarging said original binary image along said second axis by creating run end representations representing rows interpolated between the rows of the partially enlarged image produced by the preceding step, using the run ends of the rows of the partially enlarged image adjacent each interpolated row to determine the positions of the white and black run ends in the interpolated rows, so as to produce enlargement of said original binary image along said second axis by a predetermined factor F2;

storing the enlarged image generated by the above steps in run end form; and

reducing said enlarged image to a reduced image identical to said original binary image and of said original size by the steps of;

dividing said enlarged image into a plurality of strips parallel to said first axis, each strip containing one row which was obtained by enlargement of an original image row and zero or more interpolated rows;

dividing each of said strips into blocks, each block corresponding to an original image pel and containing a pel of known position corresponding in binary value to said original image pel; and

creating said reduced image by providing a pel for each said block and assigning a binary value to said pel equal to the value of the pel of known position in the block corresponding to said pel.

10. A method according to claim 9 wherein each said block comprises 3 pels by 3 pels.

11. A method according to claim 10, wherein each said pel of known position is the center pel in said block.

12. A system for enlarging a binary digital image along first and second axes thereof by factors of F1 and F2, respectively, said binary image having rows of picture elements or pels, said rows arranged adjacently along said second axis and containing runs of white and black pels, comprising:

means for storing the rows of said binary image as a plurality of run end representations, in which each row is represented as a sequence of values corresponding to the unnormalized white and black run ends;

first means for partially enlarging said binary image by altering the value of each run end in the run end representations of the respective rows to achieve enlargement along said first axis by a predetermined factor F1;

second means for further enlarging said binary image along said second axis by creating run end representations representing rows interpolated between the rows of the partially enlarged image produced by said first means, using the run ends of the rows of the partially enlarged image adjacent each interpolated row to determine the positions of the white and black run ends on the interpolated rows, so as to produce enlargement along said second axis by a predetermined factor F2; and

means for storing said enlarged size image, generated by said foregoing means, in unnormalized run end form.

13. A system as in claim 12 wherein said first and second enlarging means comprise means for compensating for output device characteristics which produce white and black pels of different sizes by adjusting characteristics of white and black runs.

14. A system according to claim 13 wherein said first enlarging means comprises:

means for obtaining the run end values describing a current row of said image to be enlarged;

means for multiplying each run end value in said current row by F1 to enlarge each run and thereby said current row by a factor of F1;

means for storing run end locations from previous enlarged rows to detect edges in said image along said second axis;

means for detecting edge pel position changes in said image along said second axis by comparing run end locatiins from previous enlarged rows with those of said enlarged current row;

means for smoothing edges ending on the row preceding the current row by accordingly adding or removing pels from said edges; and

means for repeatedly actuating said obtaining, multiplying, detecting, and smoothing means until all the rows of said binary image have been enlarged.

15. A system according to claim 12 in which F1 is equal to 3.

16. A system according to claim 12 in which F2 is equal to 3.

17. A system according to claim 12 wherein said first axis is a horizontal axis and said second axis is a vertical axis.

18. A system for enlarging a binary digital image, in the form of a plurality of rows of picture elements or pels containing runs of white and black pels, along first and second axes thereof by factors of F1 and F2, respectively, and then reducing said binary image to its original size, such that the image that results upon reduction after said binary image has been enlarged is identical to said original binary image, comprising:

means for storing the rows of said original binary image as run end representations, in which each row is represented as a sequence of integer values corresponding to the unnormalized white and black run ends;

means for enlarging said original binary image comprising;

first means for enlarging each row of said original binary image along said first axis by altering the integer value of each run end in the run end representation corresponding to each respective row

by a predetermined factor F1, in such manner that for each pel represented in said each respective row there exists a pel at a known position in the produced enlarged image row having the same binary value as said pel represented in said each respective row;

second means for further enlarging said original binary image along said second axis by creating run end representations representing rows interpolated between the rows of the partially enlarged image produced by the preceding step, using the run ends of the rows of the partially enlarged image adjacent each interpolated row to determine the positions of the white and black run ends in the interpolated rows, so as to produce enlargement of said original binary image along said second axis by a predetermined factor F2;

means for storing the enlarged image generated by said first and second enlarging means in run end form; and

means for reducing said enlarged image to a reduced image identical to said original binary image and of said original size comprising;

first means for dividing said enlarged image into a plurality of strips parallel to said first axis, each strip containing one row which was obtained by enlargement of an original image row and zero or more interpolated rows;

second means for dividing each of said strips into blocks, each block corresponding to an original image pel and containing a pel of known position corresponding in binary value to said original image pel; and

means for creating said reduced image by providing a pel for each said block and assigning a binary value to said pel equal to the value of the pel of known position in the block corresponding to said pel.

19. A system according to claim 18 wherein each said block comprises 3 pels by 3 pels.

20. A system according to claim 19, wherein each said pel of known position is the center pel in said block.

21. A system for enlarging a binary digital image along one axis thereof by a predetermined factor F, said binary image having lines of picture elements or pels, said lines arranged adjacently along said one axis and containing runs of white and black pels, comprising:

means for initializing a buffer with unnormalized run end values corresponding to those of the runs of white and black pels in a number of adjacent lines selected from said image, said lines comprising two extreme lines disposed respectively at the two ends of said buffer along said one axis;

means for discarding one of the extreme lines from one end of said buffer;

means for reading the unnormalized run end values describing a line of said image adjacent said other extreme line, and adding said run end values of said adjacent line to the other end of said buffer following the other extreme line;

means for interpolating zero or more lines between two selected lines of said buffer, in accordance with said predetermined enlargement factor F along said one axis, by creating respective run end values to describe each interpolated line;

means for selecting the run end locations for said interpolated lines being generated by examining the image lines in said buffer, in order to detect edge pel position changes along said axis and smoothing edges by accordingly adding or removing pels from said edges;

means for storing said zero or more interpolated lines and said selected line nearer said other end of said buffer in run end form; and

means for repeatedlyactuating said discarding, reading, adding, interpolating, selecting, and storing means for all lines of said image.