I haven't watched the movie clip you linked to but this effect is surprisingly simple. It get's complicated depending on how complicated the mask needs to be.
Place your orginal clip (with the person walking by) on layer two and you second clip (that are transitioning to) on layer one.
At the time the peorson walks past the scene you simply need to add a garbage matt so that the bit of image that they have walked past is ignored, showing the other layer through it.
You can easily do this in Premiere Pro but the masking options available are not so hot and you'll only get a good result if you can mask using straight lines using the 4, 8 or 16 point garbage matts.
You'll get the best result using AE where you can mask anything in whatever shape you want using spline curves etc. Also, you can feather the mask in AE which you can't in Premiere.
Hope this is clear. Ask if you need more.