They wanted some kind of rotoscope painting effect. So, after doing a few tests, we settled on a style and I started treating the footage. The first step was to chroma key all the shots, since I was planning to composite some together, then add particle effects in front and behind the various layers.
Once everyone was happy with the edit, I dropped it to 10 frames per second to get a stop-motion look and processed each frame with a proprietary image processing algorithm, to get the painted effect (After Effects plugins weren’t quite doing it for me). The result is rather pretty I think.