To clear any possible misunderstandings, I am not working together with Fraggoso.
Anyway, I said I'll post some images but ehh, too lazy.
Here is a proof-of-concept patch instead.
Attention, this is nowhere near finished and nowhere near playable! All you can do is to look around starting Alexandria but not further than alley!
Most of the moving objects aren't replaced. Some of them partially processed, some no, but all of them look 5 times more ugly on new backgrounds. Most of the layer edges need work too. I did some, like on the main street where you 1st time meet Vivi and some other places, but mostly for testing.
For now it doesn't looks like consistent wysiwyg results with edges can be achieved so I decided not to touch them until (much) later.
If you are brave enough to try it, you absolutely must make a copy of your game files. There is no way to uninstall this!
I have no idea what effect on savedata this may have, if any. Backup it too.
Also only x64 version of the game is supported.