Raster Operations using Filter Elements

Keywords: Metafiles, Raster Operations, Filters

Brian J. Wing
Senior Software Engineer
SchemaSoft
Vancouver
British Columbia
Canada
brianw@schemasoft.com
http://www.schemasoft.com

Biography

Brian graduated from the University of British Columbia in 1979 with a degree in Electrical Engineering, but fortunately various summer jobs programming at UBC convinced him software was much more fun. Since then he's been involved in software development and support on a wide variety of platforms and products from antique supervisory and control systems used on oil pipelines through early office automation software to file format converters. About three years ago, he joined up with Schema Software to get even more varied experience on things like, well, SVG. Other interests include his five year-old son, bicycle-commuting, maintaining and renovating a 90 year-old house, playing the harmonica (poorly), and learning to drive a small airplane.

1. Introduction
2. Two-Input ROPs as SVG Filters
3. Three-Input ROPs as SVG Filters
4. Comments
Acknowledgements
Bibliography

1. Introduction

Microsoft’s Metafile file format has been around for many years and there is a rich legacy of clip art and other images in this file format. Metafiles basically contain Windows graphics commands in a binary format; these commands are for both vector and raster graphics. They are documented in various places such as [MSDN] , [ORA] , and [Petzold] . Converting Metafiles to SVG is relatively straightforward with a few noteworthy exceptions. One of these exceptions is the Raster Operation (“ROP”). Generally, a ROP combines pixels in a bit-wise manner to get various special effects. ROPs which combine a pen or brush with current background pixels are called ROP2 since they combine 2 operands. These are used in the simple drawing and filling functions such as LineTo and Ellipse. ROPs which combine background pixels, a brush and new pixels from a bitmap are called ROP3 since they combine 3 operands. These operators are used in functions which deal with bitmaps such as BitBlt and StretchBlt. A ROP indicates the desired output bit for each possible permutation of input bits. For ROP2, the following table shows these relationships:

Table 1

For example, consider R2_NOTXORPEN:

• If a bit in the brush or pen colour value is 1 and in the background colour value it is 1, the resulting bit is to be 1;
• If a bit in the brush or pen colour is 1 and the background is 0, the result is to be 0;
• If a bit in the brush or pen colour is 0 and the background is 1, the result is to be 0;
• If a bit in the brush or pen colour is 0 and the background is 0, the result is to be 1;

So, if a brush or pen colour was represented by the RGB triplet (0xFF, 0x69, 0xB4) (hot pink), the background was (0xFF, 0x63, 0x47) (tomato), and the ROP was R2_NOTXORPEN, whatever that brush or pen drew would be rendered as (0xFF, 0xF5, 0x0C) (yellow).

For ROP3, there are 256 possible combinations of background, current brush, and bitmap pixel values ("Source"). Microsoft has deemed 15 of these combinations important enough to assign names to:

Table 2

A bitmap-related Metafile can contain any ROP3 code as well as those shown above. In our Metafile test suite, there are examples of B8, 9A, and 6A.

In the following simple example, a Metafile uses a ROP to render a black and white pixelmap of a cow over a purple background. Black pixels appear as black, while the purple background shows through white pixels:

Figure 1: Transparent Cow

Figure 2: Opaque Cow

2. Two-Input ROPs as SVG Filters

We first thought that ROPs could be done by SVG’s discrete feComponentTransfer filter element by combining two input arguments in some manner and using the results as an index into the table values in the filter element. The most obvious combination of input argument was to concatentate their values together bit-wise.

From the above R2_NOTXORPEN example, the blue components of hot pink and tomato are 0xB4 and 0x47 respectively. Concatenating them together yields 0xB447 = 46151. The 46151th value in this theoretical filter element’s table would be ~(0xB4^0x47) = 0x0C.

However, a 65536-element table is too large and unwieldy. Fortunately, we discovered that concatenating just the highest order 4 bits of component values was good enough to fool the eye. In other words, for example, ~(0xB0^0x40)can be used to approximate the result of ~(i^j) for any value of i from 0xB0 to 0xBF combined with any value of j from 0x40 to 0x4f. Applying this idea to 8-bit primary colour values, the algorithm is basically:

1. Zero the low-order 4 bits of the background colour value;
2. Zero the low-order 4 bits of the source graphic colour value;
3. Use these two "quantized" values to look up a value in a table which contains pre-calculated ROP results.

For example, the following image starts out with a circle coloured tomato rgb(255, 99, 71)and another mocassin rgb(255, 228, 181). A hot pink rgb(255, 105, 180) circle is placed over these two background circles using the ROP R2_NOTXORPEN:

Figure 3: Original Metafile Image

Figure 4: Approximated Metafile Image

The result of all this work was actually used to produce Figure 4 above. There is one small improvement especially for ROP results which should be pure white (0xFFFFFF): The output from the quantized lookup table always ends in 0. As a final touch up, multiply colours by 17/16 (1.0625). This will convert 0x10 to 0x11, 0x20 to 0x22, 0x30 to 0x33, ... 0xF0 to 0xFF. This can be done with a simple linear arithmetic Composite element, and can be combined with step 8. above which would change it to:

8. <feComposite operator="arithmetic" k2="1.007" k4="0.05213"/>

3. Three-Input ROPs as SVG Filters

Bitmap ROPs which take all three inputs can be approximated by cascading two-input ROP filters. For instance, the steps to implement PATPAINT are:

1. Invert the source bitmap;
2. OR the result of step 1 with the current brush;
3. OR the result of step 2 with the background.

The following images show the results of each step applied to a bitmap image as it is rendered using the PATPAINT ROP:

Figure 5: Original Source Bitmap

Figure 6: Source Bitmap Negated (~S)

Figure 7: Source Bitmap Negated and OR’d with Hot Pink Paint (P|~S)

Figure 8: Source Bitmap Negated and OR’d with Hot Pink Paint OR'd with a Background Containing Black-Outlined Oval Filled with Mocassin (D|P|~S)

1. <feComposite in="FillPaint" in2="SourceGraphic" operator="in"/>
   Confines the action of filter on the fill paint to the area covered by the source bitmap.
2. <feComponentTransfer result="P">
<feFuncR type="discrete" tableValues="0.0 0.0627 0.1254 0.1882 0.2509 0.3137 0.3764 0.4392 0.5019 0.5647 0.6274 0.6901 0.7529 0.8156 0.8784 0.9411"/>
   . . . (repeats for Green and Blue)
   Quantizes the fill paint to 16 values.
3. <feComponentTransfer in="SourceGraphic">
<feFuncR type="gamma" amplitude="1.055" exponent=".416666666" offset="-0.055"/>
   . . . (repeats for Green and Blue)
   Undoes gamma correction for the source bitmap.
4. <feComponentTransfer result="S">
<feFuncR type="discrete" tableValues="0.0 0.0627 0.1254 0.1882 0.2509 0.3137 0.3764 0.4392 0.5019 0.5647 0.6274 0.6901 0.7529 0.8156 0.8784 0.9411"/>
   . . . (repeats for Green and Blue)
   Quantizes inverted source graphic to 16 values.
5. <feComposite in="BackgroundImage" in2="SourceGraphic" operator="in"/>
   Confines the action of filter on the fill paint to the area covered by the source bitmap.
6. <feComponentTransfer>
<feFuncR type="gamma" amplitude="1.055" exponent=".416666666" offset="-0.055"/>
   . . . (repeats for Green and Blue)
   Undoes gamma correction for the background.
7. <feComponentTransfer result="D">
<feFuncR type="discrete" tableValues="0.0 0.0627 0.1254 0.1882 0.2509 0.3137 0.3764 0.4392 0.5019 0.5647 0.6274 0.6901 0.7529 0.8156 0.8784 0.9411"/>
   . . . (repeats for Green and Blue)
   Quantizes background to 16 values.
8. <feComponentTransfer in="S" result="Sn>
<feFuncR type="discrete" tableValues="0.9411 0.8784 0.8156 0.7529 0.6901 0.6274 0.5647 0.5019 0.4392 0.3764 0.3137 0.2509 0.1882 0.1254 0.06279 0.0"/>
   . . . (repeats for Green and Blue)
   Inverts source graphic resulting in an image which approximates Figure 6 above.
9. <feComposite in="P" in2="Sn" operator="arithmetic" k2="0.0627" k3="1" />
   Combines fill paint and inverted source graphic values to form index into OR lookup table.
10. <feComponentTransfer result="PSno">
<feFuncR type="discrete" tableValues=" 0.0 0.0627 0.1255 0.1882 0.251 0.3137 0.3765 0.4392 0.502 0.5647 0.6275 0.6902 ...
    . . . (repeats for Green and Blue)
    This is the 256-entry look-up table for OR in use. Produces an image which approximates Figure 7 above.
11. <feComposite in="PSno" in2="D" operator="arithmetic" k2="0.0627" k3="1" />
    Combines result of previous operation (OR) with quantized background to form index into another OR lookup table.
12. <feComponentTransfer result="DPSnoo">
<feFuncR type="discrete" tableValues=" 0.0 0.0627 0.1255 0.1882 0.251 0.3137 0.3765 0.4392 0.502 0.5647 0.6275 0.6902 ...
    . . . (repeats for Green and Blue)
    Another 256-entry look-up table for OR resulting an image which approximates Figure 8 above.
13. <feComposite operator="arithmetic" k2="0.9479" k4="0.05213"/>
    This is part 1 of re-doing the gamma correction.
14. <feComponentTransfer>
<feFuncR type="gamma" amplitude="1" exponent="2.4" offset="0"/>
    . . . (repeats for Green and Blue)
    This is part 2 of re-doing the gamma correction.

The resulting SVG rendered:

Figure 9: PATPAINT Example Approximated in SVG

4. Comments

While most results of this ROP approximation filter are difficult to tell apart from the original Metafile, there are some situations where the results are not as good. This is especially true if a resulting colour is very close to a quantization boundary.

If a source bitmap is large or there are a large number of ROPs applied throughout a Metafile, SVG renderers can take a very long time to work through the output of our Metafile converter. For one or two of the more elaborate Metafiles in our test suite, we felt compelled to halt the rendering process after half an hour or so and remove that file from our testing program.

Acknowledgements

Bibliography

[MSDN]

Microsoft Developer’s Network, Microsoft, October, 2000.

[ORA]

Microsoft Windows Metafile, O’Reilly & Associates, found in a number of places in the WWW as ora-wmf.html.

[Petzold]

Programming Windows 3.1, Charles Petzold, Microsoft Press, 1992.

XHTML rendition created by gcapaper Web Publisher v2.0, © 2001-3 Schema Software Inc.