The Mandelbrot set, step by step (4): colors

Posted on
Artistic interpretation. A mandelbrot set in the space is hit by a right of light and reflects a rainbow
2018 rmhdev. Image source

Welcome to the fourth post of the series where I develop an app that displays the Mandelbrot set using the Go programming language.

Objectives

In this post we will add the ability to use custom palettes to display colorized versions of the Mandelbrot set.

Requirements

Check the section about requirements in the second post of the series. If you want to see the code at this point of the history, browse the original repository or execute the next command to retrieve the code:

git checkout 49dfd1b

Color and distance

Until now, the images generated by the app follow a simplified coloring scheme: the pixels are white or black depending if they are outside or inside the Mandelbrot set. But, how can we add colors to these images?

A basic technique to colorize the Mandelbrot set is the “escape time” algorithm, which selects a color for a point using the number of iterations taken to check if the point is part of the set.

Detecting if a pixel is inside the set is not enough for this algorithm, that’s why we’ll need to update the Verifier struct to return a custom Verification object. It’s a simple change, but many things are going to break inside the app. Luckily, Golang’s type system and our tests will help us in this task!

// verifier.go
package main

import "math"

type Verifier struct {
  maxIterations int
}

type Verification struct {
  isInside   bool
  iterations int
  realZ      float64
  imagZ      float64
}

func (v Verifier) verify(realC float64, imagC float64) Verification {
  realZ, imagZ, modulusZ := 0.0, 0.0, 0.0
  for i := 0; i < v.maxIterations; i++ {
    modulusZ = math.Sqrt(realZ*realZ + imagZ*imagZ)
    if modulusZ > 2 {
      return Verification{false, i, realZ, imagZ}
    }
    realZ, imagZ = v.next(realZ, imagZ, realC, imagC)
  }
  return Verification{true, v.maxIterations, realZ, imagZ}
}
//...

Now take a look at the Representation of the set; you’ll notice that every pixel is represented with a boolean, which is not useful anymore. We will replace this boolean with our brand new Verification struct:

// representation.go
package main

type Representation struct {
  points [][]Verification
}

func CreateRepresentation(width int, height int) Representation {
  points := make([][]Verification, height)
  for i := range points {
    points[i] = make([]Verification, width)
  }
  return Representation{points}
}

// ...

func (r Representation) set(x int, y int, v Verification) {
  r.points[y][x] = v
}

// renamed from "isInside"
func (r Representation) get(x int, y int) Verification {
  return r.points[y][x]
}

Color palettes

To be fair, we are already using colors to represent the set: black and white. It’s the most basic palette, but this should give us a clue of how to handle different colors. Let’s create a new Palette struct that will be in charge of the colors used inside the image:

// palette.go
package main

import (
  "errors"
  "fmt"
  "image/color"
  "math"
)

type Palette interface {
  color(position int) color.Color
  length() int
}

func CreatePalette(name string) (Palette, error) {
  switch name {
  case "bw":
    return BlackWhitePalette{}, nil
  }
  return nil, errors.New("Undefined palette")
}

type BlackWhitePalette struct {
}

func (p BlackWhitePalette) length() int {
  return 2
}

func (p BlackWhitePalette) color(position int) color.Color {
  pos := int(math.Abs(float64(position))) % 2
  if 0 == pos {
    return color.RGBA{0, 0, 0, 255}
  }
  return color.RGBA{255, 255, 255, 255}
}

A palette should be responsible for returning colors, but the logic of choosing which color to use depending on the Verification object should be handled by a different struct. We will call it Coloring, and we will build it with a basic implementation of the “escape time” algorithm.

// coloring.go
package main

import (
  "errors"
  "fmt"
  "image/color"
)

type Coloring interface {
  color(v Verification) color.Color
}

func CreateColoring(name string, p Palette) (Coloring, error) {
  switch name {
  case "basic":
    return BasicColoring{p}, nil
  }
  return nil, errors.New("Undefined coloring")
}

type BasicColoring struct {
  palette Palette
}

func (c BasicColoring) color(v Verification) color.Color {
  if v.isInside {
    return c.palette.color(0)
  }
  pos := v.iterations % (c.palette.length())
  if 0 == pos {
    pos += 1
  }
  return c.palette.color(pos)
}

The “escape time” algorithm has more accurate coloring approaches, like histogram coloring or Continuous (smooth) coloring. For the sake of simplicity we will ignore them, but they can be added as new types inside coloring.go.

Now let’s edit the Exporter struct to make use of Coloring:

// exporter.go
package main
// ...

type Exporter interface {
  name() string
  export() (string, error)
}

func CreateExporter(
  name string,
  r Representation,
  folder string,
  filename string,
  coloring Coloring) (Exporter, error) {
  switch name {
  case "text":
    return TextExporter{r}, nil
  case "image":
    return ImageExporter{r, folder, filename, coloring}, nil
  }
  return nil, errors.New("Invalid Exporter")
}
// ...

type ImageExporter struct {
  representation Representation
  folder         string
  filename       string
  coloring       Coloring
}

func (e ImageExporter) name() string {
  return "image"
}

func (e ImageExporter) export() (string, error) {
  width := e.representation.width()
  height := e.representation.height()
  rect := image.Rect(0, 0, width, height)
  imageResult := image.NewRGBA(rect)
  for y := 0; y < height; y++ {
    for x := 0; x < width; x++ {
      v := e.representation.get(x, y)
      imageResult.Set(x, y, e.coloring.color(v))
    }
  }
  // ...
}

This change makes it simpler to separate the color election from “painting” the image. Now we can add as many color palettes as we want without the need of changing the exportation process. To put into practice this idea, we will add our first range of colors: the Bob Ross palette. In case you don’t know Mr Ross, he was an American painter that hosted The joy of painting, a widely famous TV show where he taught how to paint taking simple steps and using a limited palette of colors:

// palette.go
// ...

var BobRoss = []color.Color{
  color.RGBA{0x00, 0x00, 0x00, 0xff}, // Midnight black
  color.RGBA{0x02, 0x1e, 0x44, 0xff}, // Prussian blue
  color.RGBA{0x0a, 0x34, 0x10, 0xff}, // Sap green
  color.RGBA{0x0c, 0x00, 0x40, 0xff}, // Phthalo blue
  color.RGBA{0x10, 0x2e, 0x3c, 0xff}, // Phthalo green
  color.RGBA{0x22, 0x1b, 0x15, 0xff}, // Van Dyke brown
  color.RGBA{0x4e, 0x15, 0x00, 0xff}, // Alizarin crimson
  color.RGBA{0x5f, 0x2e, 0x1f, 0xff}, // Dark Sienna
  color.RGBA{0xc7, 0x9b, 0x00, 0xff}, // Yellow ochre
  color.RGBA{0xdb, 0x00, 0x00, 0xff}, // Bright red
  color.RGBA{0xff, 0x3c, 0x00, 0xff}, // Cadmium yellow
  color.RGBA{0xff, 0xb8, 0x00, 0xff}, // Indian yellow
  color.RGBA{0xff, 0xff, 0xff, 0xff}, // Titanium white
}

type BobRossPalette struct {
}

func (p BobRossPalette) color(v Verification) color.Color {
  if v.isInside {
    return BobRoss[0]
  }
  pos := (v.iterations) % (len(BobRoss) - 1)
  return BobRoss[pos+1]
}

I have also added a 256 color palette called “Plan 9” which is based on the one inside the official palette package (image/color/palette).

First colorized image

Now that everything is ready to generate our first colorized version of the Mandelbrot set, let’s improve the main method by letting the user select the palette and the coloring strategy:

// main.go
//..

func main() {
  //...
  paletteName := flag.String("palette", "bw", "color palette")
  coloringName := flag.String("coloring", "basic", "coloring")
  
  flag.Parse() // Don't forget this!
  
  palette, paletteErr := CreatePalette(*paletteName)
  if paletteErr != nil {
    fmt.Print(paletteErr)
    os.Exit(1)
  }
  coloring, coloringErr := CreateColoring(*coloringName, palette)
  if coloringErr != nil {
    fmt.Print(coloringErr)
    os.Exit(1)
  }
  //...
}

Ready! Get the refactored version of the app and test it by yourself:

git checkout 5b56d83
go build && ./mandelbrot-step-by-step -palette=bob_ross
The Mandelbrot set, colorized
First colorized version of the Mandelbrot set

As you can see in the image above, the “escape time” algorithm creates bands of color. Read more about how other algorithms deal with this problem. I tried to code the “continuous coloring” but gave up after failing to use it correctly :-(

Antialiasing

When looking with detail at the resulting images, you’ll easily notice pixel artifacts (aliasing) especially in dense areas like the one shown in the next image:

Detailed section of our colorized Mandelbrot set
Detailed section of our colorized Mandelbrot set

To fix this we can use sampling, which means selecting various random points inside every pixel and averaging the sum of the color values. This is equivalent to rendering the image at a higher resolution and scaling it down.

For example, if the size of the final image must be 200x200 and the chosen antialiasing value is 4, we will need to generate a 800x800 image and then resize it back to 200x200 while using an interpolation method (“linear”, “cubic”, “lanczos3”, …)

The new antialiasing parameter is going to affect the size of our representation. That’s why instead of working directly with width, height and antialiasing factor values, a new Size struct will handle all theses parameters:

// size.go
package main

import (
  "errors"
  "fmt"
)

const (
  MaxWidth  int = 5000
  MaxHeight int = 5000
  MaxFactor int = 16
)

type Size struct {
  width  int
  height int
  factor int
}

func CreateSize(width int, height int, factor int) (Size, error) {
  if 0 >= width || MaxWidth < width {
    return Size{1, 1, 1}, errors.New("Incorrect width")
  }
  if 0 >= height || MaxHeight < height {
    return Size{1, 1, 1}, errors.New("Incorrect height")
  }
  if 0 >= factor || MaxFactor < factor {
    return Size{1, 1, 1}, errors.New("Incorrect factor")
  }
  return Size{width, height, factor}, nil
}

func (s Size) rawWidth() int {
  return s.width * s.factor
}

func (s Size) rawHeight() int {
  return s.height * s.factor
}

This new Size struct is going to be used inside Config:

// config.go
package main

import (
  "errors"
  "fmt"
)

type Config struct {
  size    Size
  realMin float64
  realMax float64
  imagMin float64
  imagMax float64
}
// use Size instead of width and height...

It’s also going to affect the size of our Representation, because the size of the set needs to be multiplied by the antialiasing factor:

// representation.go
package main

type Representation struct {
  points [][]Verification
  size   Size
}

func CreateRepresentation(size Size) Representation {
  points := make([][]Verification, size.rawHeight())
  for i := range points {
    points[i] = make([]Verification, size.rawWidth())
  }
  
  return Representation{points, size}
}
//...

The final step of the antialiasing process is resizing the raw image to the original size using an interpolation function. To simplify this process we are going to use Resize; the “import” feature of Golang allows the use third party libraries very easily!

Note: we have defined Lanczos3 as the interpolation function because, even though not being the fastest method, it gives very good results.

// exporter.go
package main

import (
	//...

	"github.com/nfnt/resize"
)
// ...

func (e ImageExporter) export() (string, error) {
  cols := e.representation.cols()
  rows := e.representation.rows()
  rect := image.Rect(0, 0, cols, rows)
  rawImage := image.NewRGBA(rect)
  // ...
  
  finalWidth := uint(e.representation.size.width)
  resizedImage := resize.Resize(
    finalWidth, 0, rawImage, resize.Lanczos3)
  
  //...
  defer f.Close()
  png.Encode(f, resizedImage)
  
  return resultFilename, nil
}

Don’t forget to run the next command; it downloads all the external tools imported inside our source code:

go get

After adding the antialiasing parameter to the main method, the app will be ready to generate improved images; checkout the improved code and generate a new image:

git checkout 4017e2a
go build && ./mandelbrot-step-by-step -palette=bob_ross -aa=4

Thanks to the antialiasing (-aa=4), our resulting image has smoother colors than the previous version. Check the difference in a highly zoomed section:

Antialiasing difference in a detailed section of the Mandelbrot set.
Antialiasing difference in a zoomed section; top: aa=1, bottom: aa=4

Next

Our next goal is to generate multiple images while zooming to a custom point in the set. This will give us the content to generate animations in future posts, but before that we will need to improve the poor performance of our code. See you in the next posts!