BMP to Nametable + Sprites Layers

Is there a tool out there that could take a bitmap and generate a an "optimal" combination of background and sprite layers that could be used to construct that image? I've been trying to use NES Screen Tool and YY-CHR, but it only handles the background and in most cases it doesn't do color quantization well.

I've done it manually for a sprite, but it was very time consuming.

As part of the process of developing The Curse of Possum Hollow, I made a tool that takes a PNG image, a list of 3-color palettes, and a list of bounding rectangles for each cel, and breaks up each cel into multiple layers, converts each layer to 8x16-pixel tiles, removes duplicates, and produces metasprite data. It may be one of the artifacts that my manager and I agreed that I could release.

What kind of game are you making? That sprite looks like it almost takes up 8 sprites per line.

That sprite was used on an earlier project and shows what I had to do manually to create the color layers needed to approximate the image. It was close to 8 sprites per line, but didn't matter for that project.

For the project I'm trying to do now, I'm working on cut scenes (ex the title screen) where I can use the sprite palette to add up to 9 more colors to the scene. I've also been considering possible hblank palette changes to help but I've not explored that route much.

What I'd love to have is a tool that takes an image and returns the following:
1. CHR File for the backround
2. CHR File for the sprites
3. Nametable/Attribute for Background
4. Background Palette
5. Sprite Palette
6. Sprite Attributes (y, tile, atr, x)
7. Hblank Palette Changes (Optional)

Those are really hard to pull off on the NES, and several restrictions apply.

That's why I wouldn't even consider it unless there is a clear split in the graphics where I disable rendering for few lines to change (like parallax or sprite 0 hits)

This is quite similar to two of the modes of makechr, except that makechr doesn't support an image of combined background + sprites that it will decide to split up. I'm of the belief that it would be too difficult to define what "optimal" means, or to disambiguate what pixels should be in what layer.

For making Filthy Kitchen (open sourced on github) I created a small tool on top of makechr which takes compound pictures and splits it up into sprites and metadata describing how to piece the sprites back together to draw the original image on the NES. Typically, to do what you're describing, I would draw an image in Gimp, use the color select tool to cut pixels for the sprites, and paste them into another layer. Then, both layers can be exported as separate images, one can be run through bg mode, and the other through sprite mode. It's like, 80% of what you're asking, with the remaining 20% being manual work.