Jump to content

Color Clearer Integer Math


MJW
 Share

Recommended Posts

I recently wrote the Color Clearer plugin, which is intended to increase the transparency of each pixel while producing the same color when alpha-blended against a background of a specified color. Pixels that match the selected color can be made completely transparent, while pixels that are very unlike the selected color must be mostly opaque.

 

I had two goals with the plugin: first I wanted it to work when the original pixels are partially transparent; second, I wanted the adjusted pixels to match the original pixels exactly when alpha blended to a background of the selected color. The first turned out to be very easy: all that needed to be done is to compute the alphas and colors to match the original colors alpha-blended with the selected color. The second is a bit trickier, since it must take into account the integer math used by PDN to blend layers. Because I think the same techniques might be useful for other plugins, I thought I'd explain them.
 
I wrote a brief comment called Integer Division and Inequalities. I later found the same information is contained (in a slightly different form)  in the rather thorough Wikipedia article on Floor and ceiling functions. Both explain how to find the largest or smallest integers that satisfy inequalities involving integer division.

 

----------

 

Definitions:

CF: One of the original RGB foreground color components. The foreground color is the color of the source pixel.

CF': One of the adjusted foreground RGB color components.

AF: The original foreground alpha.

AF': The adjusted foreground alpha.

CB: One of the background RGB color components. The background color is the color selected to be made transparent.

CC: One of the composited (alpha-blended) foreground and background RGB color components. The composite color is the color that would result if the actve layer were placed over an opaque layer filled with the background color.

 

We want to find new values for the foreground color and foreground alpha which will minimize alpha while still producing the same composite color when alpha blended to the background color.

 

Each of the RGB components will have its own minimum alpha. For instance, if the foreground and background red have the same value, alpha can be 0, while if the foreground green is 0 and the background green is 255, only an alpha near 255 will preserve the alpha-blended green value. Since we need an alpha that preserves all the components, alpha is the maximum of the three minimum component-alphas.

 

For PDN alpha blending,

CC = Truncate{ [255 * CB + AF * (CF - CB)] / 255 }

 

The Truncate function represents the fact that the computation is done using integer division. The result could be rounded by adding 127 or 128 to the numerator, prior to the integer division, but that's not what PDN does.

 

For each of the RGB components, we need to find new values CF' and AF' which minimize AF'.

 

----- The Adjusted Alpha -----

 

We need: CC = Truncate{ [255 * CB + AF' * (CF' - CB)] / 255 }

 

This requires,

255 * CC 255 * CB + AF' * (CF' - CB) < 255 * (CC + 1)

255 * (CC - CB) AF' * (CF' - CB) < 255 * (CC - CB + 1)

 

If CC = CB, then the minimum AF' that satisfies the inequality is AF' = 0.

 

If CC > CB, then the left side of the inequality is greater than zero. To minimize AF', (CF' - CB) must be made as large as possible; so CF' = 255. Thus,

255 * (CC - CB) + AF' * (255 - CB) < 255 * (CC - CB) + 255

255 * (CC - CB) / (255 - CB) AF' < [255 * (CC - CB) + 255] / (255 - CB)

 

The minimum value of AF' that satisfies the inequality is,

AF' = Truncate{ [255 * (CC - CB) - 1] / (255 - CB) } + 1

 

If CC < CB, then the left side of the inequality is less than zero, and the right side is less than or equal to 0. Multiplying by -1 gives:

255 * (CB - CC) + AF' * (CB - CF') > 255 * (CB - CC - 1)

255 * (CB - CC - 1) < AF' * (CB - CF') 255 * (CB - CC)

 

To minimize AF', (CB - CF') must be made as large as possible; so CF' = 0. Thus,

255 * (CB - CC - 1) < AF' * CB 255 * (CB - CC)

255 * (CB - CC - 1) / CB < AF' 255 * (CB - CC) / CB

 

The minimum value of AF' that satisfies the inequality is,

AF' = Truncate[ 255 * (CB - CC - 1) / CB ] + 1

 

Once the minimum adjusted alpha is computed for each of the RBG components, the alpha for the color is calculated as the maximum of the three values.

 

----- The Adjusted Color -----

 

The adjusted foreground color is computed for the adjusted alpha. In many cases, particularly for small alphas, there's a range of colors that will produce the desired composite color. If alpha is zero, any color will do. If alpha is some small non-zero value, the foreground color still makes little contribution to the composite color, so a wide range of colors can be used. The question becomes how to choose which color.

 

I think a good choice is to select each adjusted RGB component to be the value that's nearest to the original foreground color's component.

 

If alpha is zero, any color can be used, including the original color (which is obviously closest).

 

Assuming alpha is non-zero, then as previously shown:

255 * (CC - CB) AF' * (CF' - CB) < 255 * (CC - CB + 1)

 

255 * (CC - CB) AF' * [(CF' - CF) + (CF - CB)] < 255 * (CC - CB + 1)

255 * (CC - CB) - AF' * (CF - CB) AF' * (CF' - CF) < 255 * (CC - CB + 1) - AF' * (CF - CB)

or,

255 * (CC - CB) - AF' * (CF - CB) AF' * (CF' - CF) < 255 * (CC - CB) - AF' * (CF - CB) + 255

 

Let T = 255 * (CC - CB) - AF' * (CF - CB)

 

T AF' * (CF' - CF) < T + 255

T AF' * (CF' - CF) T + 254

 

If T -255, then AF' * (CF' - CF) is bounded between negative values, so it is negative. To minimize the magnitude, we must choose the largest value. This requires:

AF' * (CF' - CF) T + 254

CF' - CF (T + 254) / AF'

-(T + 254) / AF' CF - CF'

CF - CF' = Truncate{ [-(T + 254) - 1] / AF' } + 1

CF - CF' = Truncate[ -(T + 255) / AF' ] + 1

CF' = CF - 1 - Truncate[ -(T + 255) / AF' ]

 

Since for integer division, (-a)/b = -(a/b),

CF' = CF - 1 + Truncate[ (T + 255) / AF' ]

 

If -254 T ≤ 0, then AF' * (CF' - CF) is bounded between a negative and a non-negative, so the inequality is satisfied if CF' = CF.

 

If T > 0, then AF' * (CF' - CF) is positive, so to minimize the magnitude, we must choose the smallest value. This requires:

T AF' * (CF' - CF)

T / AF' CF' - CF

CF' - CF = Truncate[ (T - 1) / AF' ] + 1

CF' = CF + 1 + Truncate[ (T - 1) / AF' ]

 

----- Summarizing -----

 

For each of the three RGB color components, compute the minimum alpha (note the AF' in the alpha computation represents the minimum alpha for the particular color component. In the color computation, it represents the over-all alpha.)

 

CC = CB:   AF' = 0

CC > CB:   AF' = Truncate{ [255 * (CC - CB) - 1] / (255 - CB) } + 1

CC < CB:   AF' = Truncate[ 255 * (CB - CC - 1) / CB ] + 1

 

Once the three alphas are found (call them AR, AG, and AB) then the adjusted alpha is the maximum. That is:

AF' = Max(AR, AG, AB)

 

Now compute the three adjusted RGB color components using:

Let T = 255 * (CC - CB) - AF' * (CF - CB)

 

T -255:        CF' = CF - 1 - Truncate[ -(T + 255) / AF'  ]    (or CF' = CF - 1 + Truncate[  (T - 255) / AF' ])

-254 T ≤ 0:  CF' = CF

T > 0:             CF' = CF + 1 + Truncate[ (T - 1) / AF' ]

 

(Truncate indicates integer division is used.)

 

One thing worth noting is that while I chose to make the adjusted foreground color as near to the original foreground color as possible, nothing in the derivation depended on that particular choice. Therefore, if instead I wanted to make the adjusted color as near to the composite color (or any other color) as possible, I could just subtitute that color's components in place of CF

  • Upvote 3
Link to comment
Share on other sites

In case the forest was lost among the trees, I'll explain the basic steps involved.

 

1) Rewrite the integer computation as inequalities. This converts the problem into a continuous form, which is much easier to deal with.

2) Isolate the term you're interested in as far as possible. The term should normally be be one you wish to minimize or maximize. For example, in the color section, I use (CF' - CF), not CF', even though CF' is what I ultimately want to determine. More or less, solve for the term, but completely solving for it may involve division or multiplication by terms whose sign can change the direction of the inequalities. Which brings us to the next step.

3) If necessary (as it likely will be), divide the problem into several cases, which depend on the sign or magnitude of some of the terms. This is the step that requires the most ingenuity. If, as mentioned in the last step, a term can have different signs which can alter the direction of the inequalities, consider what values it can have. Each case should allow the variable of interest to be completely isolated.

4) For each case, isolate the variable of interest, then use the rules for integer division and inequalities to find the best solution. (There may be some situations where there's only one solution, or where any valid solution will do.)

 

I forgot rule 0), which is: Know what integer computation is done. I couldn't find anything showing exactly how PDN alpha blends pixels to an opaque background -- whether it truncates or rounds and so forth -- so I had to experiment a little to find out.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...