Generic Dithering

Dithering Functions as Data

In order to implement all eight dithering functions that I was interested in, I split the dithering logic into DitherPattern objects and an extension onto a CGContext that applies the dithering function. I sacrificed a lot of the potential speed optimizations in doing it this way because I couldn't depend on tricks used to speed up the processing like only using modulo division when calculating the error as no all of the techniques used that, but it let me very quickly get some code working. This resulted in code that is very slow without compiler optimizations, but was acceptable with optimizations enabled.

The first of code to dig through is the CGContext extension:

public extension CGContext {

    public func dither(allowedColors: [RGBA], pattern: DitherPattern, using conversion: GrayscaleConversion) {
        guard let colors = data?.bindMemory(to: RGBA.self, capacity: width * height) else {
            fatalError()
        }
        let offsets = UnsafeMutablePointer<Int16>.allocate(capacity: width * height)
        // initialize and defer dealllocation
        let comparisons = allowedColors.map(AveragedColor.averager(using: conversion))
        let rowWidth = (bytesPerRow / (bitsPerPixel / 8))
        for y in 0..<height {
            let rowOffset = rowWidth * y
            let errorOffset = y * width
            for x in 0..<width {
                let position = x + rowOffset
                let average = conversion.averageFunction(colors[position])
                let averagedColor = AveragedColor(color: colors[position], average: average)
                let currentOffset = offsets[x + errorOffset]
                let results = comparisons.map(AveragedComparison.comparison(to: averagedColor, offsetBy: currentOffset))
                let sorted = results.sorted(by: AveragedComparison.sort)
                let error = sorted[0].difference
                let diffusion = pattern.diffused(error: Float(error), x: x, y: y, width: width, height: height)
                for point in diffusion {
                    let arrayPosition = point.xOff + (point.yOff * width)
                    let start = offsets[arrayPosition]
                    offsets[arrayPosition] = start &+ point.error
                }
                colors[position] = sorted[0].averagedColor.color
            }
        }
    }

}

This is binding the image data from the CGContext to memory, then created a block of memory to store all of the diffused offset data. The next thing that it does is converts the allowed colors list into grayscale averaged formulas using the supplied grayscale conversion to avoid recalculating those for every pixel in the image.

After this, there's an interesting and slightly maddening caveat when working with image data in memory, the data is aligned to memory word size, which will mean if you don't calculate the width of the row properly and just iterate through the array, the dead zone at the end of each row in some image means the data diffuses to the wrong pixels.

After this, we it's just brute forcing our way through the image data, comparing the available colors, finding the closest, then calculating the error and passing it to the surrounding pixels. Figuring out how to diffuse the error is where the dithering pattern enumeration comes into play. Each dithering function is just a different divisor and pattern so I'm stripping the code down to just the Floyd-Stienberg pattern:

private struct Point<Value> {
    let xOff: Int, yOff: Int, error: Value
}

public enum DitherPattern {
    case floydStienberg, jarvisJudiceNink, stucki, atkinson,
         burkes, sierraThree, sierraTwo, sierraLite
}

private extension DitherPattern {
    var divisor: Float {
        let divisor: Float
        switch self {
        case .floydStienberg: divisor = 16
        // Other divisors go here
        }
        return divisor
    }

    var pattern: [Point<Float>] {
        let points: [Point<Float>]
        switch self {
        case .floydStienberg:
            points = [
                Point(xOff: 1, yOff: 0, error: 7),
                Point(xOff: -1, yOff: 1, error: 3),
                Point(xOff: 0, yOff: 1, error: 5),
                Point(xOff: 1, yOff: 1, error: 1),
            ]
        // Other patterns go here
        }

        return points
    }

    func diffused(error: Float, x: Int, y: Int, width: Int, height: Int) -> [Point<Int16>] {
        let errorPoint = error / divisor
        return pattern.flatMap { initialPoint in
            let finalX = x + initialPoint.xOff
            let finalY = y + initialPoint.yOff
            guard finalX >= 0, finalY >= 0, finalX < width, finalY < height else {
                return nil
            }
            return Point(xOff: finalX, yOff: finalY, error: Int16(errorPoint * initialPoint.error))
        }
    }
}

Each pattern includes the divisor that the initial error is divided by, then the pattern used to copy the error to surrounding pixels, which includes the offset for the pixel of the image, and the multiplier to multiply the divided error by. The diffused function then generates an array of surrounding points to modify, with some convenience methods to check that the pixels being diffused to are within the bounds of the image.

Once I had one pattern working properly, implementing all of the other patterns became a matter of data entry copying the matrix code into the Point format. The next goal with this code is either to see how much I can improve performance by working with the Accelerate framework, or to add some fancy bells and whistles before I perform optimizations that will probably make the code harder to wrangle.