EDIT: I'm not venting, I'm answering this! <_<;;
Sorry if someone has already been talking about this...but how have those darn m@d video creators been able to key out the backgrounds of their videos? 
It's not perfect so I assume it's some kind of program they're using...or something?
Definitely something algorithmic going there - likely using only color information. Probably a magic wand-like effect, as was mentioned earlier.
Idols are cel shaded (having a border) and generally well-lit, while the stage is neither, so this may be feasible. Can't do anything about the big window announcing what song you're doing, though. ^^;
Anyone interested can do a search for Laplacian Edge Detection - easy to do, and I'm betting it's what's been used here. So...
(1) Determine where your edges are, using whatever edge detection algorithm you want to use.
(2) Use some sort of fill algorithm to assign a bit to each pixel - 0 if outside an edge, 1 if inside. (A simple one: go row-by-row, start with 0's. Move horizontally across the row and switch to 1's when you hit an edge, since you're now inside an edge. When you hit an edge again, switch back to 0's. Keep doing this. Not perfect, but should be straightforward to understand.)
(3) Fill another picture with the same dimensions with your background of choice.
(4) Every pixel in the original image you masked with a 1, overlay that pixel from the original image to your destination image (the one in step 3).
That should be a basic idea of how I imagine the process should go. I could be wrong as always.
