More Itertools Techniques
This gives us some insight into how we can rearrange the data structure, calculate
the matching colors quickly, and then rebuild the image without doing a billion
comparisons.
We can apply mask values to the RGB bytes with the following piece of command:
masked_color= tuple(map(lambda x: x&0b11100000, c))
This will pick out the most significant 3 bits of red, green, and blue values. If we use
this instead of the original color to create a Counter object, we'll see that we have 214
distinct values.
Rearranging the problem
The naïve use of the product() function to compare all pixels and all colors was
a bad idea. There are 10 million pixels, but only 200,000 unique colors. When
mapping the source colors to target colors, we only have to save 200,000 values
in a simple map.
We'll approach it as follows:
- Compute the source to target color mapping. In this case, let's use 3-bit color
values as output. Each R, G, and B value comes from the eight values in the
range(0, 256, 32) method. We can use this expression to enumerate all
the output colors:
product(range(0,256,32), range(0,256,32), range(0,256,32)) - We can then compute the Euclidean distance to the nearest color in our
source palette, doing just 68,096 calculations. This takes about 0.14 seconds.
It's done one time only and computes the 200,000 mappings. - In one pass through the image, build a new image using the revised color
table. In some cases, we can exploit the truncation of integer values. We can
use an expression such as (0b11100000&r, 0b11100000&g, 0b11100000&b)
to remove the least significant bits of an image color. We'll look at this
additional reduction in computation later.
This will replace a billion Euclidean distance calculations with 10 million
dictionary lookups. This will replace 30 minutes of calculation with about
30 seconds of calculation.
Instead of doing color mapping for all pixels, we'll create a static mapping from
input to output values. We can build the image building using simple lookup
mapping from original color to new color.