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.


Abstract


There is a rich legacy of raster-based image file formats in the world today that contain raster operations. Given that each pixel's colour is represented by three 8-bit values representing red, green, and blue, these operations ignore the actual intensity values and instead combine individual bits of the representations using boolean arithmetic. The inputs to these operations are typically the current brush or pen colour and the background. One useful operation is XOR which inverts the background colour wherever a white object is drawn over it. For example, 0xFF69B4 (hot pink) XOR 0xFFFFFF equals 0x00964B (forest green).abcdef

Microsoft's Metafile formats, WMF and EMF, take raster operations to the extreme by offering all the possible boolean combinations of input values. Very few of these are actually useful, but many can create some very artistic effects. We were given the job to build a Metafile to SVG converter, and needed to somehow implement these arbitrary raster operations despite the fact that anything that manipulates individual pixel values doesn't fit in with vector-based SVG. The first idea was to implement a lookup table using the feComponentTransfer filter primitive with type=discrete. The two input values could somehow be combined to form the "index" into such a table. Unfortunately, as there are 256 possible values for each input, such a table would be very unwieldy with (256x256) 65536 entries. However, we discovered that if we use the four high-order bits of each eight-bit input value and combine these quantized values with raster operations, the results look very close to the original. This meant that we could use a 256-element lookup table and the solution becomes realistic. The input to the lookup table is formed by combining two quantized input values into one with a simple i+j>>4 operation.


Table of Contents


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:

Brush or Pen “P” 1 1 0 0 Name Boolean Equation (C style)
Background "D" 1 0 1 0
Result 0 0 0 0 R2_BLACK 0
0 0 0 1 R2_NOTMERGEPEN ~(D|P)
0 0 1 0 R2_MASKNOTPEN D&~P
0 0 1 1 R2_NOTCOPYPEN ~P
0 1 0 0 R2_MASKPENNOT P&~D
0 1 0 1 R2_NOT ~D
0 1 1 0 R2_XORPEN D^P
0 1 1 1 R2_NOTMASKPEN ~(D&P)
1 0 0 0 R2_MASKPEN D&P
1 0 0 1 R2_NOTXORPEN ~(P^D)
1 0 1 0 R2_NOP D
1 0 1 1 R2_MERGENOTPEN D|~P
1 1 0 0 R2_COPYPEN P
1 1 0 1 R2_MERGEPENNOT P|~D
1 1 1 0 R2_MERGEPEN D|P
1 1 1 1 R2_WHITE 1

Table 1

For example, consider R2_NOTXORPEN:

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:

Brush “P” 1 1 1 1 0 0 0 0 Code in Hex Name Boolean Equation (C style)
Source "S" 1 1 0 0 1 1 0 0
Background "D" 1 0 1 0 1 0 1 0
Result 0 0 0 0 0 0 0 0 00 BLACKNESS 0
0 0 0 1 0 0 0 1 11 NOTSRCERASE ~(D|S)
0 0 1 1 0 0 1 1 33 NOTSRCCOPY ~S
0 1 0 0 0 1 0 0 44 SRCERASE S&~D
0 1 0 1 0 1 0 1 55 DSTINVERT ~D
0 1 0 1 1 0 1 0 5A PATINVERT D^P
0 1 1 0 0 1 1 0 66 SRCINVERT D^S
1 0 0 0 1 0 0 0 88 SRCAND D&S
1 0 1 1 1 0 1 1 BB MERGEPAINT D|~S
1 1 0 0 0 0 0 0 C0 MERGECOPY P&S
1 1 0 0 1 1 0 0 CC SRCCOPY >S
1 1 1 0 1 1 1 0 EE SRCPAINT D|S
1 1 1 1 0 0 0 0 F0 PATCOPY P
1 1 1 1 1 0 1 1 FB PATPAINT D|P|~S
1 1 1 1 1 1 1 1 FF WHITENESS 1

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.gif

Figure 1: Transparent Cow

If a ROP was not used, the Metafile would look like this:

figure 2.gif

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.png

Figure 3: Original Metafile Image

Applying, for instance, the algorithm to the blue component of the tomato and the hot pink:

  1. 71. = 0x47, quantized = 0x40;
  2. 180. = 0xB4, quantized = 0xB0;
  3. ROP[0x40, 0xB0] = 0x0F (precalculated ~(0x40^0xB0)).

The correct value, ~(0x47^0xB4) = 0x0C.

Applying this algorithm to all intersection areas leads to the following image:

figure 4.png

Figure 4: Approximated Metafile Image

Implementing this apparently simple algorithm is SVG filter elements is a little complicated. For one thing, there are no two-dimensional lookup tables, just one-dimensional. This means the simple three-step algorithm given above becomes:

  1. Extract the high-order 4 bits of the background colour value;
  2. Extract the high-order 4 bits of the source graphic colour value;
  3. Concatenate these 4 bits into an 8-bit value with one set in the high order and the other, low (i + j<<4);
  4. Use this 8-bit value to look up a value in a table which contains pre-calculated ROP results.

Applying this SVG algorithm to the above example, we get:

  1. 71. = 0x47, 4 high-order bits = 0x04;
  2. 180. = 0xB4, 4 high-order bits = 0x0B;
  3. 0x4B = 75.;
  4. ROP[75] = 0x0F (precalculated ~(0x40^0xB0)).

Furthermore, the filter elements do not operate on integer values between 0 and 255, but instead work with floating point values between 0 and 1 which are gamma-corrected colour values.

To begin with, the same three circle image above in SVG would be (assuming the earlier definition of ROPFilter):

A ROPfilter consists of the following filter components:

  1. <feComposite in="BackgroundImage" in2="SourceGraphic" result="background" operator="in"/>
    This confines the filter's effect to the area occupied by the source graphic (the hot pink circle in the example above).
  2. <feComponentTransfer in="background">
    <feFuncR type="gamma" amplitude="1.055" exponent=".416666666" offset="-0.055"/>
    . . . (repeats for Green and Blue)
    This component undoes the gamma correction for the background image.
  3. <feComponentTransfer result="quantBack">
    <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)
    This quantizes the background colour values to multiples of 16/255 – this effectively removes the low-order 4 bits.
  4. <feComponentTransfer in="SourceGraphic">
    <feFuncR type="gamma" amplitude="1.055" exponent=".416666666" offset="-0.055"/>
    . . . (repeats for Green and Blue)
    This component undoes the gamma correction for the source graphic.
  5. <feComponentTransfer result="quantFore">
    <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)
    This quantizes the source graphic colour values to multiples of 16/255 – this effectively removes the low-order 4 bits.
  6. <feComposite in="quantFore" in2="quantBack" result="combined" operator="arithmetic" k2="0.0627" k3="1" />
    This does the equivalent of (i+j<<4) for the quantized background and source graphic components.
  7. <feComponentTransfer in="combined">
    <feFuncR type="discrete" tableValues="1.0 0.9372 0.8745 0.8117 0.7490 0.6862 0.6235 0.5607 0.4980 0.4352 0.3725 0.3098 0.2470 0.1843 0.1215 0.0588 ...
    . . . (repeats for Green and Blue)
    This is the 256-entry ROP look-up table for the XORNOT operation.
  8. <feComposite operator="arithmetic" k2="0.9479" k4="0.05213"/>
    This is part 1 of re-doing the gamma correction.
  9. <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 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.png

Figure 5: Original Source Bitmap

figure 6.png

Figure 6: Source Bitmap Negated (~S)

figure 7.png

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

figure 8.png

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)

Getting the current brush colour into a filter element can be done by including style="fill:..." in the image element which contains the bitmap itself. Within the filter element, this is available as the FillPaint input. For example:

<image x="0" y="0" width="203" height="195" xlink:href="ROP s_3001.png" style="fill:hotpink;filter:url(#Table)"/>

One thing we noticed: the FillPaint input is NOT gamma corrected like SourceGraphic and BackgroundImage so it must not be uncorrected before use in the rest of the filter.

Here are the PATPAINT filter components with commentary:

  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.png

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

The author acknowledges Dieter Shirley at Schemasoft as the originator of the ideas that formed the basis of this work.

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.