undo a composite -dissolve

[HugoRune]

I am looking for a way to "undo" this opperation:

Code: Select all

  composite -dissolve 50 -gravity South star.gif   dragon_sm.gif  combine.png

50% [over] =

50% star.gif + dragon.gif = combine.png



Given only star.gif and combine.png, how can I reconstruct the image dragon.gif?
i.e.
- = ?

combine.png - star.gif = dragon.gif (how???)

Looking at the image combine.png, all color information of the original dragon.gif is still there, it is merely "tinted" in certain places by the transparently overlayed star.gif. There might be some loss of accuracy because the colors below the star are forced into a smaller range, but aside from that, it should be possible to reconstruct dragon.gif with the information given.


--edit-- p.s.

I tried to express it as a "-compose mathematics" operation. inserting the values for black, white and grey and solving the resulting equations i got something like this:

Code: Select all

convert combine.png star.gif -compose Mathematics -define compose:args='0,2,-1,0' -composite dragon_orig.png

However first results where confusing; either I miscalculated, or there might be a bug here:

[HugoRune]

Eureka!
Apparently the single quotes ' do not work in the -define compose:args='0,-1,2,0' under windows. With double quotes it works as intended. This may be a bug with windows or with imagemagick, not sure

to undo a 50% dissolve (composite -dissolve 50 -gravity South star.gif dragon_sm.gif combine.png )
use :

Code: Select all

convert combine.png star.gif -compose Mathematics -define compose:args="0,-1,2,0" -gravity South -composite orig_dragon.png

- = !


Now to solve this for arbitrary parameters for -dissolve...

[Bonzo]

Good result Hugo and yes you have to use " not ' with windows.
http://www.imagemagick.org/Usage/windows/

[HugoRune]

Good result Hugo and yes you have to use " not ' with windows.
http://www.imagemagick.org/Usage/windows/

Thanks! I forgot about that.
There really should be a warning if there are unparseable options passed to imagemagick

Anyway, the general case:
to undo a composite -dissolve X fileA.png fileB.png Composite.png
with X < 100

Code: Select all

convert Composite.png fileA.gif -compose Mathematics -define compose:args="0,Y,Z,0" -composite fileB_new.png

where Y = - (X/100) / (1-X/100) and Z = 1/(1-X/100)

so a '-dissolve 80' can be undone by 'compose:args="0,-4,5,0"'
and '-dissolve 20' can be undone by 'compose:args="0,-0.25,1.25,0"'

[anthony]

Now this is a great discussion, and I'll look to add it to IM examples.

However I would like to point out that when you overlay (Over compose) one image on another, the amount of transparency in the overlay image is the dissolve amount.

That is, if the star was 50% transparent, and overlaid on the fully opaque dragon image, then you get the same result as the above.

So what if the image being overlaid was semi-transparent to begin with?

You have a image (with areas that are semi-transparent) overlaid (flattened) onto two different colors. Say black and white to make the problem easier. You have the two overlay images, but not the original! And you want the original.

For example this is the original

Which should be recoverable from these two images...


Remember if a pixel is semi-transparent black, then on the black background you will not see it.
Similarly a semi-transparent white pixel will not be visible on a white background. You need BOTH images to figure out how 'transparent' a pixel is.

Once you have the alpha transparency of each pixel, you can then determine the actual color of original pixel, just as HugoRune does in the previous problem.

[HugoRune]

That is, if the star was 50% transparent, and overlaid on the fully opaque dragon image, then you get the same result as the above.

So what if the image being overlaid was semi-transparent to begin with?

As far as I can tell, the method above works all right if the overlaid image contains semi-transparent areas; for example a logo with semi-transparent antialiased edges.
The formulas for calculating Z and Y however will not work if an entirely semi-transparent overlay image and a "dissolve 100%" (i.e. a simple overlay command) was used, I am unsure how to calculate the parameters for that case.

You have a image (with areas that are semi-transparent) overlaid (flattened) onto two different colors. Say black and white to make the problem easier. You have the two overlay images, but not the original! And you want the original.
...
Once you have the alpha transparency of each pixel, you can then determine the actual color of original pixel, just as HugoRune does in the previous problem.

That would be a problem I am interested in as well. How to get the original overlay image, given only a series of pictures that contain the overlay.

But I do not know how to do that. The original alpha channel is easily recovered by taking the difference of the two images, at least for the simple case of black and white. But how would I then apply the previous solution to this case?
I tried several combinations of the black and white image, but none produce the original RGB image.

[anthony]

My thinking is that if you can first get the 'alpha' values correct. Then the alpha can be used as the 'dissolve percentage' to recover the color values from just one of the images.

So lets first work on getting alpha...
First the alpha values that we what to get (for comparision) is

Code: Select all

convert match_burn.png -alpha extract  match_alpha_orig.png

that is our goal.

Attempt one - using difference...

Code: Select all

convert match_burn_black.png match_burn_white.png \
       -compose difference -composite -negate match_alpha.png

A perfect match to the goal!


I wonder however if it can fail if some of the original overlay image colors was a simple primary color?
Could you end up with one channel generating a different difference results than other channels?
What about if the two images did not use black and white but two random, but near complementary colors, say "skyblue" and "gold"?

It may be you need to get the 'maximum difference' of all the channels, and the normalize (-auto-level) the result so that minimum difference is transparent and maximum difference is opaque. That is assuming the original image has fully transparent and fully opaque areas.

Testing...

Code: Select all

  convert match_burn.png -background skyblue -flatten match_burn_skyblue.png
  convert match_burn.png -background gold    -flatten match_burn_gold.png

  convert match_burn_gold.png match_burn_skyblue.png \
          -compose difference -composite -separate -evaluate-sequence max \
          -auto-level -negate match_alpha_2.png

Yeap that seemed to work too.. But not perfectly, basically as the difference in the background colors are not covering the full range, the difference image needs to be stretched. That results is some rounding errors. But it appears to be minor.

I would think the errors would be larger if the background colors were closer together, or did not provide any reasonable different in one of the specific channels in the image. For example two shades of red backgrounds would not provide a good dual background color for this task.

So the next step is to recover the original color using the already recovered alpha value.
That should be the same as the previous problem, but performed on a pixel by pixel level.

[anthony]

Color recovery...

As a black background is a mathematical zero. and non-black color that is present much be dew to the overlay. the color on a overlaid image is thus color * alpha. that make color recovery from a background easy... Just divide the image by the recovered alpha value. Then re-add the alpha transparency!

Code: Select all

convert match_burn_black.png match_alpha.png \
   +swap -compose divide -composite \
   match_alpha.png -alpha off -compose CopyOpacity -composite \
   match_recovered.png

This was the equivalent to the 'Z' component in the previous general formula, as we did not need to subtract 'black'.

So the next problem is recovering the colors from a non-black background! That is a lot harder. And should be similar.

However the background is a solid color, and is easily extracted from some corner of the overlaid image. In actual fact you have the alpha channel to tell you want parts of the image is purely background! You don't even have to make a guess as to what pixel contains the unadulterated background color!


ASIDE: this is proving to be a most enlightening discussion.

[HugoRune]

This is an interesting problem.

My attempt below does not quite work, I have not found the error yet:
(edit: I think i found all errors)

-----
The goal is to recover an overlay (with varying transparency alpha) , given a background and composite

when the composite is white, and the background is white, the overlay must be white too.
When the background is white and the overlay black, the composite has a brightness of 1-alpha.
and so on:

Code: Select all

compo	backg	overl(alpha a)
1			1			1
1-a		1			0
a			0			1
0			0			0

Assuming that the relation can be expressed in the form
A*Sc*Dc + B*Sc + C*Dc + D

then

Code: Select all

A*Sc*Dc + B*Sc + C*Dc + D

(1)	A*1*1 + B*1 + C*1 + D =1
(2)	A*(1-a)*1 + B*(1-a) + C*1 + D =0
(3)	A*a*0 + B*a + C*0 + D =1
(4)	A*0*0 + B*0 + C*0 + D =0

(4)	D = 0
(3) B*a = 1; B = 1/a
(2) A*(1-a) + 1/a * (1-a) + C = 0; C = - A*(1-a) - 1/a * (1-a)
	A-Aa + 1/a -1 + C ; C = -A + Aa - 1/a + 1
(1) A + 1/a + C = 1 
	A + 1/a -A + Aa - 1/a + 1 = 1
	Aa = 0
	A = 0
	
A = 0
B = 1/a
C = -1/a (1-a)
D = 0

[/size]

Code: Select all

RESULT: 1/a *Sc   -  1/a (1-a) *Dc

so this should recover the overlay:

Code: Select all

convert match_burn_white.png xc:white match_alpha.png -fx " (u[2]==1||u[2]==0) ? u : 1/u[2] *u  -  1/u[2]*(1-u[2]) *v " match_alpha.png -alpha Off -compose Copy_Opacity   -composite recovered_from_white.png

convert match_burn_black.png xc:black match_alpha.png -fx " (u[2]==1||u[2]==0) ? u : 1/u[2] *u  -  1/u[2]*(1-u[2]) *v " match_alpha.png -alpha Off -compose Copy_Opacity   -composite recovered_from_black.png

It works! (the black version just a more complicated version of Anthonys command, I guess)

It should also work with inhomogenous backgrounds, as long as the transparency is known.

[anthony]

Very good. Nice demonstration of the mathematics involved.

The black recovery is simpler basically because in that case v = 0.
As such -fx " (u[2]==1||u[2]==0) ? u : 1/u[2] *u - 1/u[2]*(1-u[2]) *v "
devolves to -fx " (u[2]==1||u[2]==0) ? u : 1/u[2] *u "
or -fx " (u[2]==1||u[2]==0) ? u : u/u[2] "

The Composite divide is defined so that if u[2]==0 then the composition result is zero.
Of course the result in that case does not matter, as alpha is fully transparent in any case.
so the result is the same as a -compose divide

However doing the task with image composition may not work in the general case, unless HDRI is used.

[anthony]

Hmmm...

first the u[2]==1 exception is not needed as you don't actually divide by that figure!

The main FX expresion, ignoring the exceptions is...

Code: Select all

  1/u[2] *u  -  1/u[2]*(1-u[2]) *v

Doing a little simplification...

Code: Select all

  u/u[2]  -  v*(1-u[2])/u[2]
  u/u[2]  -  v/u[2] + v

So we get...

Code: Select all

convert match_burn_white.png xc:white match_alpha.png \
          -fx " u[2]==0 ? 0 : u/u[2] - v/u[2] + v " \
          match_alpha.png -alpha Off -compose Copy_Opacity -composite \
          match_recovered_white.png

WARNING; the above depends on the default -virtual-pixel edge setting for the xc:white background color mapping.

However as fx is restricted what it changes in the image by the channel setting, but can still read any channel. As such we can incorporate the alpha into main image first, without problems.

Code: Select all

convert match_burn_white.png match_alpha.png \
            -alpha Off -compose Copy_Opacity -composite \
            xc:white  -fx " u.a==0 ? 0 : u/u.a - v/u.a + v " \
            match_recovered_white.png

Now lets put it all together as a single program! using skyblue and gold overlays...

Code: Select all

convert match_burn_skyblue.png match_burn_gold.png -alpha off \
            \( -clone 0,1 -compose difference -composite \
               -separate -evaluate-sequence max -auto-level -negate \
             \) -delete 1  -compose Copy_Opacity -composite \
             xc:skyblue  -fx " u.a==0 ? 0 : u/u.a - v/u.a + v " \
            match_recovered_skyblue.png

ASIDE: this technique also a perfect 'green screen' color remover. As long as you can figure out exactly how much of the green screen is actually present in 'edge' pixels.

However if you photo an object in front of a green screen, then again in front of say a magenta screen, then you can
remove the background screens completely! There was a discussion about doing this type of thing to take photos of objects with lots of transparency, but I can't seem to find it.

[anthony]

I have verified that the function is correct.

color component for 'Over' composition.
http://www.w3.org/TR/2002/WD-SVG11-2002 ... ml#SrcOver
Dc' = Sc + Dc(1 - Sa)

where Dc' Sc Dc are all pre-multiplyed by there respective alpha values.
However Dc' (result or combined image) is opaque, as is the background Dc color
that is Da' = 1 and Da = 1

As such, by replacing Dc' with Rc to make it easier, and explicitly specifying the alpha components, the function becomes
Rc = Sc*Sa + Dc*(1-Sa)

now we are trying to recover Sc with a known Sa Rc and Dc so..
Sc*Sa = Rc - Dc + Dc*Sa
Sc = Rc/Sa - Dc/Sa + Dc

Which is exactly the simplified FX formula above.


I would never have thought to do that if it wasn't for the way you did your simultaneous equations!

Continuation...

While trying to sleep last night the above formula kept swirling roun din my mind, and I wondered if I could also verify that the Sa determination was really the negated difference of the two overlay images (Rc1 and Rc2).

Now as the same overlay image was used we have
Sc = Rc1/Sa - Dc1/Sa + Dc1
Sc = Rc2/Sa = Dc2/Sa + Dc2
So
Rc1/Sa - Dc1/Sa + Dc1 = Rc2/Sa - Dc2/Sa + Dc2
divide by Sa
Rc1 - Dc1 + Dc1*Sa = Rc2 - Dc2 + Dc2*Sa
(Dc1-Dc2)*Sa = (Rc2 - Rc1) + (Dc1-Dc2)
Sa = (Rc2 - Rc1)/(Dc1-Dc2) + 1
and a final result of
Sa = 1 - (Rc1 - Rc2)/(Dc1-Dc2)

And that is a negated difference of Rc1 and Rc2, with a normalization multiplier 1/(Dc1-Dc2) applied before the negation.
The multiplier would have been determined by the difference range between fully-transparent and fully-opaque pixels,
But as you can see you could also determine it more directly too.

For a pair of white and black and black backgrounds Dc1,Dc2 = 0,1 in any order that just becomes...
Sa = 1 - |Rc1 - Rc2|

So this verifies that the difference of the two overlay images does indeed generate a perfect alpha mask. However Dc1 and Dc2 should be as different as posible, and the Rc1 and Rc2 values should also be as different as posible.

Aside...

The formula also shows that it possible to recover the overlay from two images with known multi-colors backgrounds! Each pixel difference will then need to be normalized by dividing it by the difference between the original background used. Assuming of course that there is a good difference between all the pixels within the two original background images.

[anthony]

The background to transparency from two background color images is now online at...
http://www.imagemagick.org/Usage/maskin ... background

I will also look at adding the original problem of 'transparent overlay' removal shortly. I think it would be perfect for the removal of semi-transparent logos from multiple images. The two_background method itself can be used figure out the original logo that was added an is not to be removed.

In other words spam text/logo removal!

[HugoRune]

Great tutorial, Anthony!

Some random thoughts

---

Code: Select all

convert match_burn_skyblue.png match_burn_gold.png -alpha off \
            \( -clone 0,1 -compose difference -composite \
               -separate -evaluate-sequence max -auto-level -negate \
             \) -delete 1  -compose Copy_Opacity -composite \
             xc:skyblue  -fx " u.a==0 ? 0 : u/u.a - v/u.a + v " \
            match_recovered_skyblue.png

the -auto-level works if the overlay contains areas of total transparency and total opacity.

If the overlay is smaller than the background (or not shaped rectangular) then areas with total transparency are a save bet.
But the overlay might still have no totally opaque pixels.
So instead of -auto-level -negate
-fx "u/maxima" -negate
(this command takes rather long to execute, I think imagemagick is calculating maxima for every pixel.
perhaps -bordercolor white -border 1x1 -auto-level -shave 1x1 ?)

Alternatively, I just realized, with your formula:

Sa = 1 - (Rc1 - Rc2)/(Dc1-Dc2)

Code: Select all

convert match_burn_skyblue.png match_burn_gold.png -fx "1 - (u-v)/(u.p{0,0}-v.p{0,0}) match_alpha.png

If the background is noisy, or the source is a jpeg image, then some more contrast-stretch for black pixels in the mask would be desirable.

---

to recover an overlay from a series of images with mixed unknown backgrounds (img001.png-img999.png):

Code: Select all

convert img*.png -evaluate-sequence max maximage.png
convert img*.png -evaluate-sequence min minimage.png

check whether the background area is monochrome in both outputs, and then proceed as above using maximage and minimage as input.
If the background is not monochrome, then the series of images contains not enough information to recover the overlay, but might still suffice for a good aproximation. Maybe average the recovered overlay from the maximage and the minimage. not tested yet.

[HugoRune]

to recover an overlay from a series of images with mixed unknown backgrounds (img001.png-img999.png):

Code: Select all

convert img*.png -evaluate-sequence max maximage.png
convert img*.png -evaluate-sequence min minimage.png

check whether the background area is monochrome in both outputs, and then proceed as above using maximage and minimage as input.
If the background is not monochrome, then the series of images contains not enough information to recover the overlay, but might still suffice for a good aproximation. Maybe average the recovered overlay from the maximage and the minimage. not tested yet.

With the recovered overlay, it should be possible to recover the background images as well, as per the first post:

Code: Select all

convert  img001.png recovered_overlay.png -fx "v.a==1?u: (u - v*v.a)  /  (1 - v.a)" img001_recovered.png

(This will obviously not work for any part of the overlay that is fully opaque.)

Now, what if the overlay is in a different location for each image?
It might be possible to align the image and the overlay, but I am unsure what the best method for that would be.

Perhaps an edge-detect and then a subimage search?
Or is it possible to optimize the search with some assumptions?