@ dlfrsilver: There's a lot of wastage in the original graphics! It almost looks as if different people where working on different elements with different palette's.
@ fishyfish: Thanks for the links, I'm hopefull this CPS1 emulator will help!
For the colour reduction:
There is only one palette now of 32 colours. Obviously it's a good idea to have separate palette's for your characters/backgrounds but they are one and the same here. I wanted to have all/most colours available for both.
The first stage BKG uses 24 colours, the characters are made using similar tones for the flesh and some key colours for their outfits. This palette is the starting point.
The palette changes from stage to stage, but the change so far has not been drastic. It does not matter too much if a character's clothing has to change from pastel blue to pastel green in order to make a larger section of the background appear nicer. This is not the best way of creating clear guidelines as to the colour reduction, there is plenty of room for artistic freedom here! I think that after re-colouring several stages the palette will become more finalised, and I think it will be worth it in the end.
The goal is to reduce the colours to the 32 colour 'stock' palette while retaining as much depth and detail as possible.
I start by trying a reduction to 64 colours. Usually it doesn't work, so I edit out some of the obvious colours by hand, by matching close colour hues, checking the detail has not reduced (significantly - you can't always help it as you get nearer to 32) counting the colours used on screen, and reducing again to that amount.
As the amount colours becomes reduced, I start matching the colours of the image to those of the stock palette. Here is where compromises may have to be made, either to the palette or the image. At this stage I check the image against those of the characters by pasting them in (- it's safer if you don't put them over the background unless you're careful with saving).