Indexing

Key terms

image palette

A table of colors that an indexed image references. The palette is stored in the PNG file’s internal representation, and is used to map the indices in the image to colors.

palette aggregate

A color tuple in the image palette.

indexing function

A function that maps a color to a palette index.

deindexing function

A function that maps a palette index to a color.

Worked example

In this tutorial, we will use the library’s indexing APIs to colorize the following grayscale image:

We already saw in the Basic decoding tutorial how to read grayscale samples from an input PNG.

import PNG

let path:String = "Sources/PNG/docs.docc/Indexing/Indexing"

guard
let image:PNG.Image = try .decompress(path: "\(path).png")
else
{
    fatalError("failed to open file '\(path).png'")
}

let v:[UInt8] = image.unpack(as: UInt8.self)

What we want to do is map the grayscale UInt8 values to some color gradient, where gray value 0 gets the color at the bottom of the gradient, and gray value 255 gets the color at the top of the gradient. We will do this by creating a new, indexed image where the gray values in the original image are the indices in the new image, and where each index references a gradient value stored in the image palette.

We define a simple, six-stop gradient function with the following code. It generates a gradient that is black at the bottom, red in the middle, and yellow at the top.

func lerp(
    _ a:(r:Double, g:Double, b:Double),
    _ b:(r:Double, g:Double, b:Double),
    t:Double) -> (r:Double, g:Double, b:Double)
{
    (
        a.r * (1.0 - t) + b.r * t,
        a.g * (1.0 - t) + b.g * t,
        a.b * (1.0 - t) + b.b * t
    )
}
func gradient<T>(_ x:T) -> (r:UInt8, g:UInt8, b:UInt8, a:UInt8)
    where T:FixedWidthInteger
{
    let stops:
    (
        (r:Double, g:Double, b:Double),
        (r:Double, g:Double, b:Double),
        (r:Double, g:Double, b:Double),
        (r:Double, g:Double, b:Double),
        (r:Double, g:Double, b:Double),
        (r:Double, g:Double, b:Double)
    )
    =
    (
        (0.0, 0.0, 0.0),
        (0.1, 0.1, 0.1),
        (1.0, 0.2, 0.3),
        (1.0, 0.3, 0.2),
        (1.0, 0.4, 0.3),
        (1.0, 0.8, 0.4)
    )
    let t:Double = (.init(x) - .init(T.min)) / (.init(T.max) - .init(T.min))
    let y:(r:Double, g:Double, b:Double)
    switch t
    {
    case         ..<0.0:    y = stops.0
    case    0.0 ..< 0.2:    y = lerp(stops.0, stops.1, t: (t      ) / 0.2)
    case    0.2 ..< 0.4:    y = lerp(stops.1, stops.2, t: (t - 0.2) / 0.2)
    case    0.4 ..< 0.6:    y = lerp(stops.2, stops.3, t: (t - 0.4) / 0.2)
    case    0.6 ..< 0.8:    y = lerp(stops.3, stops.4, t: (t - 0.6) / 0.2)
    case    0.8...     :    y = lerp(stops.4, stops.5, t: (t - 0.8) / 0.2)
    default            :    y = stops.5
    }
    return
        (
        r: .init(max(0, min(y.r * 255, 255))),
        g: .init(max(0, min(y.g * 255, 255))),
        b: .init(max(0, min(y.b * 255, 255))),
        a: .max
        )
}

Of course, we can’t encode a gradient function directly in a PNG file, since PNG viewers can’t execute Swift code. So we have to tabularize it as a 256-element array.

let gradient:[(r:UInt8, g:UInt8, b:UInt8, a:UInt8)] =
    (UInt8.min ... UInt8.max).map(gradient(_:))

We can visualize the gradient using the same APIs we used in the Basic encoding tutorial.

let swatch:[PNG.RGBA<UInt8>] = (0 ..< 16).flatMap
{
    _ -> [PNG.RGBA<UInt8>] in
    (0 ..< 256).map
    {
        let (r, g, b, a):(UInt8, UInt8, UInt8, UInt8) = gradient[$0]
        return .init(r, g, b, a)
    }
}
let visualization:PNG.Image = .init(packing: swatch, size: (256, 16),
    layout: .init(format: .rgb8(palette: [], fill: nil, key: nil)))
try visualization.compress(path: "\(path)-gradient.png")

We can create an indexed image by defining an indexed layout, and passing the grayscale samples we obtained earlier to one of the pixel-packing APIs. The init(packing:size:layout:metadata:) initializer will treat the grayscale samples as pixel colors, not indices, and will try to match the pixel colors to entries in the given palette. This is not what we want, so we need to use a variant of that function, init(packing:size:layout:metadata:indexer:), and pass it a custom indexing function.

let indexed:PNG.Image = .init(packing: v, size: image.size,
    layout:  .init(format: .indexed8(palette: gradient, fill: nil)),
    metadata: image.metadata)
{
    _ in Int.init(_:)
}

The best way to understand the indexing function is to compare it with the behavior of the init(packing:size:layout:metadata:) initializer. Calling that initializer is equivalent to calling init(packing:size:layout:metadata:indexer:) with the following indexing function.

{
    (palette:[(r:UInt8, g:UInt8, b:UInt8, a:UInt8)]) -> (UInt8) -> Int in

    let lookup:[(r:UInt8, g:UInt8, b:UInt8, a:UInt8): Int] = .init(
        uniqueKeysWithValues: zip(palette, palette.indices))
    return { (v:UInt8) -> Int in lookup[(v, v, v, .max), default: 0] }
}

Its type is ([(r:UInt8, g:UInt8, b:UInt8, a:UInt8)]) -> (UInt8) -> Int. This construct can be a little confusing, especially if you aren’t familiar with functional programming, so let’s walk through it.

The outer function is a pure function that takes a palette argument of type [(r:UInt8, g:UInt8, b:UInt8, a:UInt8)]. This palette comes from the palette field of the image’s color format, if the format is one of the indexed color formats. (If the image layout has a non-indexed color format, the indexing function never gets invoked in the first place.)

The default implementation of the outer function then constructs a dictionary mapping the palette entries to their array indices, using init(uniqueKeysWithValues:).

The return value of the outer function is an inner function of type (UInt8) -> Int. As its signature suggests, the inner function takes an argument of type UInt8, and returns an Int index. The UInt8 is a grayscale sample from the given pixel array. The inner function is not generic. If you pass a [UInt16] array to the packing initializer, the 16-bit grayscale samples will get rescaled to the range of a UInt8 before getting passed to the inner function.

Its default implementation encloses the dictionary variable, and uses it to look up the palette index of the function’s grayscale sample argument, expanded to RGBA form. If there is no matching palette entry, it returns index 0. As you might expect, this can be inefficient for some use cases (though not terribly so), so the custom indexing APIs are useful if you want to manipulate indices without re-indexing the entire image.

Depending on the color target, the inner function may take a tuple argument instead of a scalar. For the PNG.VA<T> color target, the inner function recieves (UInt8, UInt8) tuples. For the PNG.RGBA<T> color target, it receives (UInt8, UInt8, UInt8, UInt8) tuples. (The return type is always Int.) In this library, the inner function argument is called a palette aggregate.

Let’s go back to the custom indexing function:

{
    _ in Int.init(_:)
}

Since we just want to cast the grayscale samples directly to index values, we don’t need the palette parameter, so we discard it with the _ binding. We then return the Int.init(_:) initializer, which casts the grayscale samples to Ints.

On appropriate platforms, we can encode the image to a file with the compress(path:level:hint:) method.

try indexed.compress(path: "\(path)-indexed.png")

To read back the index values from the indexed image, we can use a custom deindexing function, which we pass to unpack(as:deindexer:).

let indices:[UInt8] = indexed.unpack(as: UInt8.self)
{
    _ in UInt8.init(_:)
}

For the scalar pixel packing API, deindexing functions have the type ([(r:UInt8, g:UInt8, b:UInt8, a:UInt8)]) -> (Int) -> UInt8. Its return type, (Int) -> UInt8 is exactly the opposite of that of an indexing function. Its default behavior is equivalent to the following implementation, which should be self-explanatory.

{
    (palette:[(r:UInt8, g:UInt8, b:UInt8, a:UInt8)]) -> (Int) -> UInt8 in
    {
        (i:Int) -> UInt8 in palette[i].r
    }
}

We can verify that the indices we read back with our custom deindexing function are identical to the grayscale samples we originally passed to the packing initializer.

print(indices == v)

true