9.2.1 Computing distances

A number of decision-making problems require that we find a close enough match. We might not be able to use a simple equality test. Instead, we have to use a distance metric and locate items with the shortest distance to our target. The k-Nearest Neighbors (k-NN) algorithm, for example, uses a training set of data and a distance measurement function. It locates the k nearest neighbors to an unknown sample, and uses the majority of those neighbors to classify the unknown sample.

To explore this concept of enumerating all possible matches, we’ll use a slightly simpler example. However, even though it’s superficially simpler, it doesn’t work out well if we approach it naively and exhaustively enumerate all potential matches.

When doing color matching, we won’t have a simple equality test. A color, C, for our purposes, is a triple ⟨r,g,b⟩. It’s a point in three-dimensional space. It’s often sensible to define a minimal distance function to determine whether two colors are close enough, without having the same three values of ⟨r₁,g₁,b₁⟩ = ⟨r₂,g₂,b₂⟩. We need a multi-dimensional distance computation, using the red, green, and blue axes of a color space. There are several common approaches to measuring distance, including the Euclidean distance, Manhattan distance, and other more complex weightings based on visual preferences.

Here are the Euclidean and Manhattan distance functions:

import math 
def euclidean(pixel: RGB, color: Color) -> float: 
    return math.sqrt( 
        sum(map( 
            lambda x_1, x_2: (x_1 - x_2) ** 2, 
            pixel, 
            color.rgb)) 
        ) 
 
def manhattan(pixel: RGB, color: Color) -> float: 
    return sum(map( 
        lambda x_1, x_2: abs(x_1 - x_2), 
        pixel, 
        color.rgb))

The Euclidean distance measures the hypotenuse of a right-angled triangle among the three points in an RGB space. Here’s the formal definition for three dimensions:

Here’s a two-dimensional sketch of the Euclidean distance between two points:

The Manhattan distance sums the edges of each leg of the right-angled triangle among the three points. It’s named after the gridded layout of the Borough of Manhattan in New York City. To get around, one is forced to travel only on the streets and avenues. Here’s the formal definition for three dimensions:

Here’s a two-dimensional sketch of the Manhattan distance between two points:

The Euclidean distance offers precision, while the Manhattan distance offers calculation speed.

Looking forward, we’re aiming for a structure that looks like this. For each individual pixel, we can compute the distance from that pixel’s color to the available colors in a limited color set. The results of this calculation for one individual pixel of an image might start like the following example:

[((0, 0), 
  (92, 139, 195), 
  Color(rgb=(239, 222, 205), name=’Almond’), 
  169.10943202553784), 
 ((0, 0), 
  (92, 139, 195), 
  Color(rgb=(255, 255, 153), name=’Canary’), 
  204.42357985320578), 
 ((0, 0), 
  (92, 139, 195), 
  Color(rgb=(28, 172, 120), name=’Green’), 
  103.97114984456024), 
 ((0, 0), 
  (92, 139, 195), 
  Color(rgb=(48, 186, 143), name=’Mountain Meadow’), 
  82.75868534480233),

We’ve shown a sequence of tuples; each tuple has four items:

• The pixel’s coordinates; for example, (0,0)

• The pixel’s original color; for example, (92, 139, 195)

• A Color object from a set of seven colors; for example, Color(rgb=(48, 186, 143), name=’Mountain Meadow’)

• The Euclidean distance between the original color and the given Color object; for example, 82.75868534480233

It can help to create a NamedTuple to encapsulate the four items in each tuple. We could call it an X-Y, Pixel, Color, Distance tuple, something like ”XYPCD.” This would make it slightly easier to identify the (x,y) coordinate, the original pixel’s color, the matching color, and the distance between the original color and the selected match.

The smallest Euclidean distance is a closest match color. For the four example colors, the Mountain Meadow is the closest match for this pixel. This kind of reduction is done with the min() function. If the overall four-tuple of (x,y), pixel, color, and distance is assigned to a variable name, choices, the pixel-level reduction would look like this:

min(choices, key=lambda xypcd: xypcd[3])

This expression will pick a single tuple as the optimal match between a pixel and color. It uses a lambda to select item 3 from the tuple, the distance metric.

9.2.2 Getting all pixels and all colors

How do we get to the structure that contains all pixels and all colors? One seemingly simple answer turns out to be less than optimal.

One way to map pixels to colors is to enumerate all pixels and all colors using the product() function:

from collections.abc import Iterable 
from itertools import groupby 
 
def matching_1( 
        pixels: Iterable[Pixel], 
        colors: Iterable[Color] 
    ) -> Iterator[tuple[Point, RGB, Color, float]]: 
 
    distances = ( 
        (pixel[0], pixel[1], color, euclidean(pixel[1], color)) 
        for pixel, color in product(pixels, colors) 
    ) 
    for _, choices in groupby(distances, key=lambda xy_p_c_d: xy_p_c_d[0]): 
        yield min(choices, key=lambda xypcd: xypcd[3])

The core of this is the product(pixel_iter(img), colors) expression that creates a sequence of all pixels combined with all colors. The overall expression then applies the euclidean() function to compute distances between pixels and Color objects. The result is a sequence of four-tuple objects with the original (x,y) coordinate, the original pixel, an available color, and the distance between the original pixel color and the available color.

The final selection of colors uses the groupby() function and the min(choices, ...) expression to locate the closest match.

The product() function applied to pixels and colors creates a long, flat iterable. We grouped the iterable into smaller collections where the coordinates match. This will break the big iterable into smaller iterables of only the pool of colors associated with a single pixel. We can then pick the minimal color distance for each available color for a pixel.

In a picture that’s 3,648×2,736 pixels with 133 Crayola colors, we have an iterable with 3,648 × 2,736 × 133 = 1,327,463,424 items to be evaluated. That is a billion combinations created by this distances expression. The number is not necessarily impractical; it’s well within the limits of what Python can do. However, it reveals an important flaw in the naive use of the product() function.

We can’t trivially do this kind of large-scale processing without first doing some analysis to see how large the intermediate data will be. Here are some timeit numbers for these two distance functions. This is the overall number of seconds to do each of these calculations only 1,000,000 times:

• Euclidean: 1.761

• Manhattan: 0.857

Scaling up by a factor of 1,000—from 1 million combinations to 1 billion—means the processing will take at least 1,800 seconds; that is, about half an hour for the Manhattan distance and 46 minutes to calculate the Euclidean distance. It appears this kind of naive bulk processing is ineffective for large datasets.

More importantly, we’re doing it wrong. This kind of width × height × color processing is simply a bad design. In many cases, we can do much better.

9.3.1 Rearranging the problem

The naive 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:

1. 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) expression. We can use this expression to enumerate all the output colors:

   product(range(0, 256, 32), range(0, 256, 32), range(0, 256, 32))

2. 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.

3. In one pass through the source image, we 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 distance calculations with 10 million dictionary lookups, transforming a potential 30 minutes of calculation into about 30 seconds.

Given a source palette of approximately 200,000 colors, we can apply a fast Manhattan distance to locate the nearest color in a target palette, such as the Crayola colors.

We’ll fold in yet another optimization—truncation. This will give us an even faster algorithm.

9.3.2 Combining two transformations

When combining multiple transformations, we can build a more complex mapping from the source through intermediate targets to the result. To illustrate this, we’ll truncate the colors as well as applying a mapping.

In some problem contexts, truncation can be difficult. In other cases, it’s often quite simple. For example, truncating US postal ZIP codes from nine to five characters is common. Postal codes can be further truncated to three characters to determine a regional facility that represents a larger geography.

For colors, we can use the bit-masking shown previously to truncate colors from three 8-bit values (24 bits, 16 million colors) to three 3-bit values (9 bits, 512 colors).

Here is a way to build a color map that combines distances to a given set of colors and truncation of the source colors:

from collections.abc import Sequence 
def make_color_map(colors: Sequence[Color]) -> dict[RGB, Color]: 
    bit3 = range(0, 256, 0b0010_0000) 
 
    best_iter = ( 
        min((euclidean(rgb, c), rgb, c) for c in colors) 
        for rgb in product(bit3, bit3, bit3) 
    ) 
    color_map = dict((b[1], b[2]) for b in best_iter) 
    return color_map

We created a range object, bit3, that will iterate through all eight of the 3-bit color values. The use of the binary value, 0b0010_0000, can help visualize the way the bits are being used. The least significant 5 bits will be ignored; only the upper 3 bits will be used.

For each truncated RGB color, we created a three-tuple that has (0) the distance from all crayon colors, (1) the RGB color, and (2) the crayon Color object. When we ask for the minimum value of this collection, we’ll get the closest crayon Color object to the truncated RGB color.

We built a dictionary that maps from the truncated RGB color to the closest crayon. In order to use this mapping, we’ll truncate a source color before looking up the nearest crayon in the mapping. This use of truncation coupled with the pre-computed mapping shows how we might need to combine mapping techniques.

The following function will build a new image from a color map:

def clone_picture( 
    color_map: dict[RGB, Color], 
    filename: str = "IMG_2705.jpg" 
) -> None: 
    mask = 0b1110_0000 
    img = Image.open(filename) 
    clone = img.copy() 
    for xy, rgb in pixel_iter(img): 
        r, g, b = rgb 
        repl = color_map[(mask & r, mask & g, mask & b)] 
        clone.putpixel(xy, repl.rgb) 
    clone.show()

This uses the PIL putpixel() function to replace all of the pixels in a picture with other pixels. The mask value preserves the upper-most three bits of each color, reducing the number of colors to a subset.

What we’ve seen is that the naive use of some functional programming tools can lead to algorithms that are expressive and succinct, but also inefficient. The essential tools to compute the complexity of a calculation (sometimes called Big-O analysis) is just as important for functional programming as it is for imperative programming.

The problem is not that the product() function is inefficient. The problem is that we can use the product() function to create an inefficient algorithm.

9.5.1 Combinations with replacement

The itertools library has two functions for generating combinations of items selected from some set of values. The combinations() function reflects our expectations when dealing hands from a deck of cards: each card will appear at most once. The combinations_with_ replacement() function reflects the idea of taking a card from a deck, writing it down, and then shuffling it back into the deck before selecting another card. This second procedure could potentially yield a five-card sample with five aces of spades.

We can see this more clearly by using the following kind of expression:

>>> import itertools 
>>> from pprint import pprint 
>>> pprint( 
... list(itertools.combinations([1,2,3,4,5,6], 2)) 
... ) 
[(1, 2), 
 (1, 3), 
 (1, 4), 
... 
 (4, 6), 
 (5, 6)] 
>>> pprint( 
... list(itertools.combinations_with_replacement([1,2,3,4,5,6], 2)) 
... ) 
[(1, 1), 
 (1, 2), 
 (1, 3), 
... 
 (5, 5), 
 (5, 6), 
 (6, 6)]

There are = 15 combinations of six things taken two at a time. There are 6² = 36 combinations when replacement is permitted, since any value is a possible member of the result.

9.8.1 Alternative distance computations

See Effects of Distance Measure Choice on KNN Classifier Performance - A Review. This is available at https://arxiv.org/pdf/1708.04321. In this paper, dozens of distance metrics are examined for their utility in implementing the k-Nearest Neighbors (k-NN) classifier.

Some of these are also suitable for the color-matching algorithm presented in this chapter. We defined a color, c, a three-tuple, (r,g,b), based on the Red, Green, and Blue components of the color. We can compute the distance between two colors, D(c₁,c₂), based on their RGB components:

We showed two: Euclidean and Manhattan distances. Here are some more formal definitions:

Some additional examples include these:

• The Chebyshev Distance (CD) is the maximum of the absolute values of each color difference:

  

• The Sorensen Distance (SD) is a modification of the Manhattan distance that tends to normalize the distance:

  

Redefine the make_color_map() function to be a higher-order function that will accept a distance function as a parameter. All of the distance functions should have a type hint of Callable[[RGB, Color], float]. Once the make_color_map() function has been changed, it becomes possible to create alternative color maps with alternative distance functions.

This function creates a mapping from ”masked” RGB values to a defined set of colors. Using a 3-bit mask defines a mapping from 2³ × 2³ × 2³ = 512 possible RGB values to the domain of 133 colors.

The function’s definition should look like this:

def make_color_map(colors: Sequence[Color], distance: Callable[[RGB, Color], float]) -> dict[RGB, Color]:

How much difference does the choice of distance function make? How can we characterize the mapping from the large collection of possible RGB values to the limited domain of subset colors? Is a histogram showing how many distinct RGB values map to a subset color sensible and informative?

9.8.2 Actual domain of pixel color values

When creating a color map, a mask was used to reduce the domain of possible colors from 2⁸ × 2⁸ × 2⁸ = 16,777,216 to a more manageable 2³ × 2³ × 2³ = 512 possible values.

Does it make sense to scan the original image using the mask value to determine the actual domain of available colors? A given image, may, for example, have only 210 distinct colors when a 3-bit mask is used. How much additional time is required to create this summary of colors actually in use?

Can the color summary be further optimized? Could we, for example, exclude rarely used colors? If we do exclude these rarely used colors, how do we replace a pixel’s color with more commonly used colors? What changes in an image if we use the color of the majority of the neighboring pixels to replace pixels with rarely used colors?

Consider an algorithm that makes the following two passes over an image’s pixels:

1. Create a Counter with the frequency of each color.

2. For colors with fewer than some threshold, ?, locate the neighboring pixels. In a corner, there may be as few as three. In the middle, there will be no more than eight. Find the color of the majority of those pixels and replace the outlier.

Before starting on this algorithm, it’s important to consider any ”edge” cases. Specifically, there is a potential complication when rarely used colors are adjacent.

Consider this case:

If the four pixels in the top-left corner, p_(0,0), p_(1,0), p_(0,1), and p_(1,1), all had rarely used colors, then it would be difficult to pick a majority color to replace p_(0,0).

In the case where there are no non-rare colors surrounding a pixel with a rare color, the algorithm would need to queue this up for later resolution after the neighbors have been processed. In this example, the color for pixel p_(1,0) can be computed using neighbors that are not rare colors. After p_(0,1) and p_(1,1) are also resolved, then p_(0,0) can be replaced with the majority color of the three neighbors.

Is this algorithmic complexity helpful for a picture with 10 million pixels? Choosing one or a few photos arbitrarily isn’t a sophisticated survey. However, it can help to avoid overthinking potential problems.

Survey the colors in a collection of images. How common is it to see a single pixel with a unique color? If you don’t have a private collection of images, visit kaggle.com to look for image datasets that can be examined.

9.8.3 Cribbage hand scoring

The card game of cribbage involves a phase where a player’s hand is evaluated. A player will use four cards that are dealt to them, plus a fifth card, called the starter.

To avoid overusing the word ”points,” we’ll consider each card to have a number of pips. Each face card is counted as having 10 pips; all other cards have a number of pips equal to their rank. Aces have a single pip.

The scoring involves the following combinations of cards:

• Any combination of cards that totals 15 pips adds 2 points to the score.

• Pairs – two cards of the same rank – add 2 points to the score.

• Any run of three, four, or five cards adds 3, 4, or 5 points to the score.

• A flush of four cards in a hand adds 4 points to the score. If the starter card is of the same suit, then the flush, as a whole, is 5 points.

• If a jack in a hand has the same suit as the starter card, this adds 1 point to the score.

If a hand contains three cards of the same rank, this is counted as three separate pairs, worth 6 points in aggregate.

An interesting hand involves runs with a pair. For example, a hand 7C, 7D, 8H, and 9S, with an irrelevant starter card of a Queen, has two runs—7C, 8H, 9S, and 7D, 8H, 9S—and a pair of 7’s. This is a total of 8 points. Furthermore, there are two combinations that add to 15: 7C, 8H and 7D, 8H, bringing the hand’s value to 12 points.

Note that a 4-card run is not counted as two overlapping 3-card runs. It’s only worth 4 points.

Another interesting example is holding 4C, 5D, 5H, 6S, and the starter card is 3C. There are two distinct runs of 4 cards: 3C, 4C, 5D, 6S, and 3C, 4C, 5H, 6S, as well a pair of 5s, leading to 10 points for this pattern. Additionally, there are two distinct ways to count 15 pips: 4C, 5D, 6S and 4C, 5H, 6S, adding 4 more points to the score.

A handy algorithm for this is to enumerate several combinations and permutations of cards to locate all the scoring. The following rules can be applied:

1. Iterate over the powerset of the cards. This is the set of all subsets: all of the singletons, all of the pairs, all of the triples, etc., up to the set of all five cards. Each of these is a distinct set, some of which will tally to 15 pips. For more information on generating the powerset, see the Itertools Recipes section of the Python Standard Library documentation.

2. Enumerate all pairs of cards to compute scores for any pairs. The combinations() function works well for this.

3. For sets of five cards, if they’re adjacent, ascending values, this is a run. If they’re not adjacent, ascending values, then enumerate the sets of four-card runs to see if either of these have adjacent numbers. Failing that test, enumerate all sets of three-card runs to see if any of these have adjacent numbers. The longest run applies to the score, and shorter runs are ignored.

4. Check the hand and starter for a five-flush. If there’s no five-flush, check the hand only for a four-flush. Only one of these two combinations is scored.

5. Also, check to see if the hand has a jack of the same suit as the starter.

Since there are only five cards involved in this, the number of permutations and combinations is rather small. Be prepared to summarize exactly how many combinations and permutations are required for a five-card hand.