Browse Prior Art Database

Algorithm for Rotating an Image in Run End Form

IP.com Disclosure Number: IPCOM000037143D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 4 page(s) / 67K

Publishing Venue

IBM

Related People

Anderson, KL: AUTHOR

Abstract

An algorithm is presented for rotating a binary image represented in run end form by 90 degrees in either a clockwise or counterclockwise direction, and with suitable modifications, it can be used to rotate images stored in similar run representation forms, such as run lengths. The original and rotated images are both represented in run end form.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 34% of the total text.

Page 1 of 4

Algorithm for Rotating an Image in Run End Form

An algorithm is presented for rotating a binary image represented in run end form by 90 degrees in either a clockwise or counterclockwise direction, and with suitable modifications, it can be used to rotate images stored in similar run representation forms, such as run lengths. The original and rotated images are both represented in run end form.

This rotation procedure is particularly useful in a system which stores binary images in compressed form using algorithms that create/compress images in run end form rather than requiring the target/source images to be in raster form. For a large class of images (including most line art and text, but excluding halftones), this mode of operation is faster than using raster form, and the run end form is more compact than the raster form, i.e., the image is represented using less space. In such a system, it will often be faster to rotate using the run representation form than to create a raster image, rotate it, and reconvert to run end form (using methods such as those described in U.S. Patents 4,596,039, 4,627,020, and 4,610,027 or 4,646,356, respectively) before encoding, or to create a raster-rotated image and then convert back to run end form (using the procedures described in U.S. Patents 4,658,430 and 4,610,027 or 4,646,356) for encoding.

The representation of a binary image in run end form will first be described. The run end representation used in this rotation procedure represents each row of an image as a series of halfwords. The 16 bits in a halfword are adequate to represent images with widths up to 32K as positive displacements. The first halfword in each line buffer gives the number of bytes of run end data plus two bytes for the count (i.e., the total number of bytes of data in the buffer); this is followed by three zero run ends, an arbitrary number of pairs of white/black run ends, and two additional copies of the last black run end. If the image row begins with a black run, the first white run end must be specified as zero. If the image row ends with a white run, the last black run end will be the same as the last white run end, so that, in fact, three additional copies of the last real run end will be used. For example, the following three-line bit image (where "0" represents a white pel and "1" a black pel) 11111111 11000000 00000000 00010000

00000000 00000000 00000000 00000000

10100000 10001111 11111111 11110001 row of all zero pels is compared to the last row in order to add the positions of the ends of black runs which extend to the edge of the rotated image to the set.

The collected transitions are then sorted according to column, since each column of the original image will become a row of the rotated image. The result of the sorting process is shown in Fig. 1 (b). Thus, we find that column "a" contains transitions after rows 4 and 6, column "b" contains transitions after rows 5 and 6, column "c" contains no transition...