What is rasterop?
What else can you do with rasterop?
How is rasterop implemented
efficiently?
What special cases have been implemented?
What is the calling sequence for rasterops?
One of the most useful operations in image composition, image transformation and image analysis is the rasterop. This is the low-level operation that your window system uses to paint bitmap characters to your frame buffer, and to paint and repaint windows when they are generated, resized, or moved.
This operation has a long and distinguished history, with the driving force being the desire to use bitmapped graphics terminals for realtime I/O. According to Eric Raymond's New Hacker's Dictionary (1991, MIT Press), the PDP-10 had a BLT (BLock Transfer) machine instruction to copy or move a contiguous block of data within memory. (This is not to be confused with the common BLT (Branch if Less Than zero) assembly instruction, or the BLT (Bacon Lettuce and Tomato) sandwich.) Suppose you have an image that is represented by a contiguous block of memory in line raster order, but you want to copy or move data between rectangular sub-blocks. In general, this data will be composed of disconnected fragments of the original block of data. One version of rasterop that worked on rectangular two-dimensional subimages of the display buffer was implemented at Xerox PARC in the early 1970s by Dan Ingalls. This utility was used to display character bitmaps on the Alto, a 16-bit computer derived from the Data General Nova minicomputer. At Xerox, the operation was called Bitblt, pronounced "bit blit", which is short for "Bit Block Transfer." (The Alto displays were 1 bit/pixel, monochrome.) Many implementations were subsequently written for other computers with bitmapped graphics displays, such as Sun's Unix workstations dating from the early 1980s that used Sun's proprietary Sunview window system.
For efficiency, some of the display bitblt operations need to work in place, so that the display buffer is both the source and the destination of the pixels. In such situations, bits have to be copied in a particular order so as not to overwrite bits that need to be moved later. Some bitblt (rasterop) operations do not use the display buffer as either the source or destination of the bits. Such memory-to-memory operations are used, for example, by imagers that compose page images for display or printing, or, as we shall see, for many image processing operations in general.
There are two well-tested versions of rasterop in open source that I know of: one with X windows and one with ghostscript. However, these are both complicated by internal reference to graphical display imaging, and they have a very large set of operators. They do not have a clean interface to the low-level bit manipulation routines, and they are encumbered by Gnu's GPL ``copyleft" (for X) and by Aladdin's own copyleft (for ghostscript). For these reasons, I have made a set of efficient low-level routines for rasterop, with a clean interface between the user's image data structure and low-level data. If you want to use a different image data structure, it is a simple matter to rewrite the interface shim to the low-level operations.
The general binary rasterop function replaces a rectangular part of a destination (dest) image with a bitwise combination of the pixels in the dest and those in an arbitrary rectangle of the same size in a source (src) image. The bitwise combination can be one of the following:
PIX_SRC s (replacement)
PIX_NOT(PIX_SRC) ~s (replacement with bit inversion)
PIX_SRC | PIX_DST s | d
PIX_SRC & PIX_DST s & d
PIX_SRC ^ PIX_DST s ^ d
PIX_NOT(PIX_SRC) | PIX_DST ~s | d
PIX_NOT(PIX_SRC) & PIX_DST ~s & d
PIX_NOT(PIX_SRC) ^ PIX_DST ~s ^ d
PIX_SRC | PIX_NOT(PIX_DST) s | ~d
PIX_SRC & PIX_NOT(PIX_DST) s & ~d
PIX_SRC ^ PIX_NOT(PIX_DST) s ^ ~d
PIX_NOT(PIX_SRC | PIX_DST) ~(s | d)
PIX_NOT(PIX_SRC & PIX_DST) ~(s & d)
PIX_NOT(PIX_SRC ^ PIX_DST) ~(s ^ d)
where the version on the left uses the macros that Sun
originally defined around 1981 for their Pixrect library,
and the version on the right is an obvious shorthand.
The first two are independent of the data in the dest,
but they are "binary" in the sense that the low-level
functions need to index into both the src and
dest arrays.
Of these 14 operations, only 12 are unique. The following
three operations are identical:
PIX_NOT(PIX_SRC) ^ PIX_DST ~s ^ d
PIX_SRC ^ PIX_NOT(PIX_DST) s ^ ~d
PIX_NOT(PIX_SRC ^ PIX_DST) ~(s ^ d)
In addition to the 12 unique binary operations, there are two
unary rasterop functions, that operate on the dest
and only depend on the the dest:
PIX_DST d (this is a no-op)
PIX_NOT(PIX_DST) ~d (bit inversion)
And finally there are two unary operations that operate on the
dest and are independent of both src and dest:
PIX_CLR (set all bits to 0)
PIX_SET (set all bits to 1)
In all, there are a total of 16 unique boolean operations.
The Sun definition of these macros, along with an analysis
of how they work properly in composition, is given in rop.c.
Before we go into any details, let me explain some of the
things besides image composition that rasterop can do.
Affine transforms are the set of linear geometrical transforms on a two-dimensional image that encompass translation, shear, rotation and scaling. Except for scaling, all of these operations can be implemented using rasterop! Translation is obvious: you choose entire image as the source block, and place it, appropriately translated, in the destination. Shear is implemented by translating blocks of image by different amounts. For example, you can imagine a horizontal "clockwise" shear about the center of the image where horizontal full width blocks are shoved to the right above the center and to the left below the center. Blocks near the top and bottom are pushed farther than blocks near the center; the distance a block moves horizontally increases linearly with the vertical distance of the block from the center of the image. Rotation is accomplished by three successive shears, alternating in horizontal and vertical directions; the details are given in the source code. (For small angles, a two-shear approximation to a rotation can be used. Th resulting rotation angle is correct, but the length-to-width ratio is altered by a fraction equal to the square of the angle. So for a 1 degree rotation angle, the two-shear rotation changes the length-to-width ratio by about 1/3000 -- about 1 pixel for a typical document image.) It should be noted that all these operations can be done in-place, by which we mean that the src and dest are the same image. In such situations when there is translation, care must be taken to clear those parts of the image that are not translated.
Binary morphology is most easily implemented by full-image rasterop. A dilation takes a (bit) union of various translates of the src image, whereas an erosion takes a (bit) intersection of translates. Dilation and erosion are dual operations, in that a dilation on the foreground is equivalent to an erosion of the background, and v.v. However, we typically visualize binary images non-symmetrically, with emphasis on the foreground (ON) pixels. Viewed this way, dilation has the effect of smearing out the foreground, whereas erosion thins the foreground and acts as a pattern matching operation for foreground patterns. The pattern that specifies the translations for a dilation or erosion is called a structuring element. If we view a morphological operation from the vantage point of each dest pixel, we see that the outcome (ON or OFF) depends on a set of pixels in the src image whose positions relative to the dest pixel are given by the structuring element.
The morphological opening and closing operations are derived from dilation and erosion: the opening is a sequence of erosion and dilation, using the same structuring element; the closing is a dilation/erosion sequence. Opening and closing have the particularly nice property of idempotence, so that repeated opening or dilation has no further effect. This is a filtering property that we we associate with ideal sieves or projection operators, and for this reason image morphology operations are often called morphological filters. For a further introduction, go to the section on binary morphology.
Grayscale morphology is a generalization of binary
morphology to images with more than one bit/pixel, with
dilation and erosion being defined as a max and
min, respectively, of a set of pixels.
Binary morphology occupies a central role in document
image analysis, because (particularly with multiscale
extensions) it is able to extract both shape and texture.
For an introduction to these methods, see
Multiresolution morphological
approach to document image analysis , published in
SPIE Conf. 1818, Boston, Nov. 1992.
Another set of special cases are unary rasterops that operate on a general rectangular region of a single image. There are only 3 non-trivial operations:
PIX_CLR, PIX_SET, and PIX_NOT(PIX_DST).These operations are implemented as special cases of word-aligned binary rasterops. When called with the high-level, 9 parameter pixRasterop() function, the last 3 arguments (src Pix and UL corner coordinates) are ignored. There is even a special case of unary rasterop where the left edge of the rectangle is aligned on a 32-bit word boundary.
Yet another special case of unary rasterops has been implemented to move pixels in-place within special rectangular regions. These two functions are
These horizontal and vertical in-place operations have been combined. By taking the block to be moved equal to the entire image, pixRasteropIP() is the high-level function that performs an arbitrary in-place shift of an image.
That's the big picture. We now look down at a few of the
internal details.
(9 args) pixRasterop(PIX *pixd, INT32 dx, INT32 dy, INT32 dw, INT32 dh, INT32 op, PIX *pixs, INT32 sx, INT32 sy);If the operation is unary, the last three arguments of pixRasterop() are ignored, and rasteropUniLow is called with 10 arguments. The width is scaled and the rectangle is clipped if necessary, and the remaining 7 arguments are passed to either rasteropUniWordAlignedLow() or to the more general function rasteropUniGeneralLow(). These does the work.
If the operation is binary, all the arguments in pixRasterop() are used, and rasteropLow() is called with 16 arguments:
(16 args) --> rasteropLow(UINT32 *datad,
INT32 dpixw, INT32 dpixh, INT32 depth, INT32 dwpl,
INT32 dx, INT32 dy, INT32 dw, INT32 dh,
INT32 op,
UINT32 *datas,
INT32 spixw, INT32 spixh, INT32 swpl,
INT32 sx, INT32 sy);
At this point, two simple operations are carried out immediately:
(11 args) --> rasteropGeneralLow(UINT32 *datad,
INT32 dwpl,
INT32 dx, INT32 dy, INT32 dw, INT32 dh,
INT32 op,
UINT32 *datas,
INT32 swpl,
INT32 sx, INT32 sy);
Due to the width adjustment and clipping that are
performed in rasteropLow(), the low-level function
that does all the work, rasteropGeneralLow(), does not need
five of the arguments passed to rasteropLow(); namely,
the width, height and depth of the dest and the width
and height of the src.
Note that because rasteropLow() does width adjustment and clipping, it is safe to call it directly with an arbitrary image depth and un-clipped rectangular regions. It also makes it easier to call these low-level functions using a different high-level shim that uses some other packed image data structure. This separation between high-level functions that use the Pix image data structure and low-level functions that use only built-in C data types makes it much easier to port the low-level functions to applications that use other image data structures.
