BBC BASIC for Windows
Programming >> Sound, Music and Video >> A first attempt at chroma keying
http://bb4w.conforums.com/index.cgi?board=multimedia&action=display&num=1242039548
A first attempt at chroma keying
Post by David Williams on May 11th, 2009, 10:59am

For my own amusement, I thought I'd have a go at home-made chroma keying. A BB4W program scans through the pixels of the source images and replaces blue pixels (within a specified range of 'blueness') with corresponding pixels from a (animated) background image. The end result isn't really so bad, although having done no research on how to implement a high quality colour keying algorithm, I think the way I've done it could make a certain person weep!

So here's a short (43-second) video of me -- or rather, my upper appendages -- making a noise in front of my makeshift blue screen (which consists of A2-sized pieces of blue card procured from my local craft shop). Actually, the original plan was to have my supremely talented guitarist friend do the honours, but unfortunately the plan fell through and so you've got me instead:

http://www.bb4w-games.com/fsb/fsb_640x480_divx.avi (DivX - recommended, best quality)

http://www.bb4w-games.com/fsb/fsb_640x480_wmv.wmv (WMV - inferior)


For completeness, here's the same again but without the chroma keying (DivX only):

http://www.bb4w-games.com/fsb/fsb_bluescreen_720x576_divx.avi (DivX)

And the animated background (FWIW):

http://www.bb4w-games.com/fsb/bg_720x576_divx.avi (DivX)


My (undoubtedly laughable) method is as follows:

1. Determine beforehand the minimum and maximum required fixed red/green, red/blue, and green/blue colour ratios (these are constants):

Code:
      minRG# = 0.4624
      maxRG# = 0.9189
      minGB# = 0.7087
      maxGB# = 0.9060
      minRB# = 0.3307
      maxRB# = 0.7718


2. Read the pixels of the source image with a 3x3 sampling matrix and obtain the average R, G and B values for the eight neighbouring pixels, plus the centre pixel.

3. Compute the red/green, red/blue and green/blue colour ratios based on the above calculated average R, G, B values.

4. If *all* of the just-calculated ratios lie within the range minRG to maxRG etc., then we've got a blue pixel, and it must be replaced by a corresponding background pixel.

5. Move on to the next pixel in the source image.

I'll tidy up the program and post it here shortly.


David.
Re: A first attempt at chroma keying
Post by admin on May 11th, 2009, 10:14pm

Quote:
I think the way I've done it could make a certain person weep!

Indeed. Can I ask why you did no research? I'm pretty sure there are patents and other published papers on CSO algorithms. You won't be surprised to learn that one of the very best was developed at my old place of work: BBC Research & Development.

Quote:
1. Determine beforehand the minimum and maximum required fixed red/green, red/blue, and green/blue colour ratios (these are constants):

It's usual to calculate hue and saturation (HSV) values from the RGB data, and derive the key signal from them; it's probably faster too. You need to think about what happens physically when areas of the 'blue' background (often green of course) are in shadow, or illuminated to a varying degree.

Quote:
2. Read the pixels of the source image with a 3x3 sampling matrix and obtain the average R, G and B values for the eight neighbouring pixels,

The last thing you want is any spatial filtering on the key signal; you want a wide bandwidth so that things like wispy strands of hair are keyed cleanly. If you need to perform spatial filtering to get a usable key signal, it's an indication that your underlying algorithm is poor.

Quote:
If *all* of the just-calculated ratios lie within the range minRG to maxRG etc., then we've got a blue pixel, and it must be replaced by a corresponding background pixel.

You'll never get good results if all you derive is a Boolean (1 bit-per-pixel) background/foreground 'switch' signal - aliasing will be a massive problem for a start. What you need to derive is a 'linear key', i.e. at least a 6-bit signal which determines in what proportion the background and foreground are combined.

I'm all in favour of reinventing the wheel, if the end result is a better wheel! However I'd be very surprised and impressed if you came up with a better CSO algorithm than those already used by the likes of Ultimatte.

Richard.
Re: A first attempt at chroma keying
Post by David Williams on May 11th, 2009, 11:14pm

on May 11th, 2009, 10:14pm, Richard Russell wrote:
Indeed. Can I ask why you did no research?

I had an inkling that whatever documentation I might find on this subject was just going to go straight over my head. I did actually glance at this document:

http://www.cs.utah.edu/~michael/chroma/

...and it went straight over my head!


on May 11th, 2009, 10:14pm, Richard Russell wrote:
I'm pretty sure there are patents and other published papers on CSO algorithms.

In any case, I'm pretty sure that I wouldn't have the skills to implement any such algorithms.


on May 11th, 2009, 10:14pm, Richard Russell wrote:
It's usual to calculate hue and saturation (HSV) values from the RGB data, ...

Ah... well I think I might be able to cope with that part.


on May 11th, 2009, 10:14pm, Richard Russell wrote:

(snip other interesting and useful information)



on May 11th, 2009, 10:14pm, Richard Russell wrote:
I'm all in favour of reinventing the wheel, if the end result is a better wheel!

Mine's an inferior wheel, but it didn't cost me anything and the results were more-or-less what I expected (namely, not terribly good), and it was quite fun doing it.


on May 11th, 2009, 10:14pm, Richard Russell wrote:
However I'd be very surprised and impressed if you came up with a better CSO algorithm than those already used by the likes of Ultimatte.

I couldn't even begin to aspire to that.


Anyway, thanks for the information and suggestions. The next video will hopefully be at least marginally better, but it will still, unfortunately, rely heavily on the CSO algo that I've devised (unless someone else feels charitable enough to donate a better one).


Regards,

David.
Re: A first attempt at chroma keying
Post by admin on May 12th, 2009, 08:33am

Quote:
In any case, I'm pretty sure that I wouldn't have the skills to implement any such algorithms

To the best of my recollection the BBC R&D algorithm, which is one of the better ones, is simpler than yours! The algorithm has to be relatively simple if it's to be implemented in hardware or real-time software. For example division operations, of which yours seems to require several, are best avoided or at least minimised. Division in hardware is a pain!

Richard.
Re: A first attempt at chroma keying
Post by admin on May 14th, 2009, 5:40pm

I have written, from scratch, my own Colour Separation Overlay (Chroma Key) software utility, to illustrate how a BB4W program can read video frames from an AVI file, and output video frames to another AVI file, without the need of a third-party conversion utility:

http://groups.yahoo.com/group/bb4w/files/WindowsAPI/csoavi.bbc
http://groups.yahoo.com/group/bb4w/files/WindowsAPI/csoavi.zip

The CSO algorithm used is not at all special; it is simplistic and has no advanced features such as hue supression or shadows. The program is intended to illustrate accessing AVI files, not keying! However adjustments are provided for key colour, acceptance angle and gain.

Here (with apologies to David Williams for stealing his bluescreen source material) is an example output file created using my program:

http://www.rtr.myzen.co.uk/cso_rtr_720x576_divx.avi

There's no sound (my utility doesn't copy sound to the output).

I've tried to write the program 'well', and it's quite a good example of my style of programming! All comments would be welcome.

Richard.