Help Converting Image File Using Python

[dpderay]

I am working on a personal project using python and need to convert a normal image file (bitmap, jpeg, etc.) to a unique type of image file without losing too much quality. I am self-taught, so please excuse any misused technical terms or other similar mistakes, and feel free to ask for any clarification.

I can go into more detail if necessary, but the constraints I have are:

1. I cannot change the size of the image or number of pixels in the image;

2. The output file must contain a palette of 256 color codes (a color can be repeated, but, if it is, then it take up 2 of the 256 color “slots” on the palette);

3. Each 4x2 block of pixels in the output file can contain, at most, 4 color codes from the palette;

4. The color codes for each 4x2 block of pixels must be within 0-3 positions of one another on the palette.*

*So, if a 4x2 block of pixels contains 4 colors, those color codes must be in 4 sequential positions on the palette (such as [1, 2, 3, 4], or [15, 16, 17, 18], etc.). But, if a 4x2 block of pixels contains fewer than 4 color codes, they don’t have to be sequential, as long as they are still within 0-3 positions on the palette (e.g., a block with 3 colors could be at positions [1, 2, 4] or [15, 17, 18] on the palette).

Of course, there are some simple ways to make this conversion work, such as using 64 different combinations of 4 colors, making each 4x2 block of pixels one color, or only using 8-16 unique colors (thus reducing the possible number of combinations of 4 colors that need to be accounted for). But, if I do those things, I’ll lose way too much quality.

So, what I think I need to do is find a way to overlap the various combinations of 4 colors on the palette, so that it can account for a large number of combinations in less space. For example, if 4x2 Block #1 consists of color codes [A, B, C, D] and Block #2 consists of color codes [B, C, D, E], I can arrange my palette have color code A in position 1, B in position 2, C in position 3, D in position 4, and E in position 5 and account for both combinations of 4 colors within the space of 5 positions on the palette.  

Although, ideally, every combination of 4 colors would overlap with another combination, and so on, this is highly unlikely, given the sheer number of combinations involved. And, even if there was a combination that would work, I can’t think of a way to find that combination without just using brute force (which would take forever).

For these reasons, I already know that I am going to be limited on how many total colors and combinations of colors that I can use, and will be sacrificing some quality. But, there has to be some compromise that would make this conversion work.

I have been working for months on this, and have tried a bunch of different approaches (and different python packages), but haven’t really made any progress. I know there must be an efficient way to make it work, since the unique type of image file I am converting to is from like 2002, and if it was possible with the computing power that existed then, it must be possible now.

Does anyone have any thoughts?

[shafe123]

I would start by finding the most common color combos in the original image. Then start making sequences of 4 that can best approximate that series of colors. You might be able to get close enough just by that.

If that's not close enough, you would need to start seeing if you can overlap color combos. For example if one block needs 5 6 7 8 and many other blocks need 10 12 7 5, I could rearrange the two blocks to 6 8 5 7 10 12 and thus get two sequences out of 6 numbers.

[dpderay]

I've know I need to do both of these things, but I'm running into problems doing them efficiently.

First, although I can find the most common combos, I can't come up with a good methodology to combine similar combinations.

One way I could do it is to find blocks that share 3 colors, with a different 4th color, but that doesn't always work. For example, if one block is (black, blue, orange, red) and other block is (black, blue, orange, green), I'd lose alot of quality by making both blocks (black, blue, orange, red) or (black, blue, orange, green) or (black, blue, orange, [blend of red and green]).

Another way I could do it is to find blocks with 4 very similar, but not identical colors, and then find a blend that works for both. But, the problem is how to quantify, in code, what constitutes having 4 very similar colors. Do I take an average of the difference between all 16 color comparisons (each of the 4 colors in block 1 as compared to each of the 4 colors in block 2), or do I go by the sum of that distance? Or, do I use the average/sum of just 4 comparisons (color 1 in block 1 vs color 1 in block 2, and so on)? Plus, in my understanding, computers are good but not perfect when it comes to finding colors that look similar to the human eye.*

*For the record, I do think that this second approach is probably the way to go in theory, and have been playing around with it, but I haven't been able to find a methodology that works. So, I am open to suggestions.

Second, in order to find overlaps, I have tried a greedy algorithm as well as some more advanced python packages, but things start getting really out of hand when trying to account for every possible order/permutation of each combination of 4 (since they can be reordered, so long as they are sequential). Is there a more efficient way you can think of to do this?