code review 10977043: image/draw: add Quantizer, NaiveQuantizer and FloydStei...

image/draw: add Drawer, FloydSteinberg and the op.Draw method.

[nigeltao, 2013-07-07 12:34:22]

Hello r@golang.org (cc: andybons@gmail.com, golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[nigeltao, 2013-07-07 12:41:14]

With https://codereview.appspot.com/10890045/ and the source image at
http://blog.golang.org/go-at-google-io-2011-videos_gopher.jpg the
program below produces the attached paletted PNG images.

--------
package main

import (
    "fmt"
    "image"
    "image/color"
    "image/draw"
    "image/jpeg"
    "image/png"
    "log"
    "os"
)

func main() {
    f, err := os.Open("gopher.jpeg")
    if err != nil {
        log.Fatal(err)
    }
    defer f.Close()
    src, err := jpeg.Decode(f)
    if err != nil {
        log.Fatal(err)
    }

    palettes := map[string]color.Palette{
        "bw":      color.Palette{color.Black, color.White},
        "plan9":   color.Plan9Palette,
        "websafe": color.WebSafePalette,
    }
    quantizers := map[string]draw.Quantizer{
        "naive": draw.NaiveQuantizer,
        "floyd": draw.FloydSteinberg,
    }
    for pName, p := range palettes {
        for qName, q := range quantizers {
            filename := fmt.Sprintf("out-%s-%s.png", pName, qName)
            fmt.Printf("Making %s\n", filename)
            dst := image.NewPaletted(src.Bounds(), p)
            q.Quantize(dst, dst.Bounds(), src, image.ZP)
            g, err := os.Create(filename)
            if err != nil {
                log.Fatal(err)
            }
            defer g.Close()
            err = png.Encode(g, dst)
            if err != nil {
                log.Fatal(err)
            }
        }
    }
}
--------

[Andrew Bonventre, 2013-07-07 20:15:26]

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize.go
File src/pkg/image/draw/quantize.go (right):

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:1: // Copyright 2013 The Go Authors.  All rights
reserved.
Nit: Some source files have one space after the period. Some have two.

[r, 2013-07-08 01:51:25]

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize.go
File src/pkg/image/draw/quantize.go (right):

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:78: bestIndex, bestSSD := 0, uint32(1<<32-1)
this is fine but it can be done more efficiently. you have a 32-bit color value
but the RGB in the palette is only 8 bits, which suggests some clever options.
caching can also help, but you need to watch out for bloat (again, remember the
8 bit rule).
maybe just a TODO for now.

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:81: ssd := delta * delta
if you're going to square it, why do you need a signed diff?

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
File src/pkg/image/draw/quantize_test.go (right):

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize_test.go:31: return
-s/Error/Fatal/
d

[r, 2013-07-08 01:52:23]

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize.go
File src/pkg/image/draw/quantize.go (right):

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:16: Quantize(dst *image.Paletted, r
image.Rectangle, src image.Image, sp image.Point)
if you made the dst an image.Image, this is a more general convert operation.
i'm not convinced (nor am i unconvinced) that we want to define this narrow
interface

[nigeltao, 2013-07-08 03:06:38]

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize.go
File src/pkg/image/draw/quantize.go (right):

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:16: Quantize(dst *image.Paletted, r
image.Rectangle, src image.Image, sp image.Point)
On 2013/07/08 01:52:23, r wrote:
> if you made the dst an image.Image, this is a more general convert operation.
> i'm not convinced (nor am i unconvinced) that we want to define this narrow
> interface

That would be more general in a sense, but the Palette information is then
implicit rather than explicit. I suppose this could instead be

type Drawer interface {
  Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point)
}

and Floyd-Steinberg had a fast-path if dst was an *image.Paletted. Does it make
sense to apply Floyd-Steinberg to an *image.Gray dst?? Hmm...

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:78: bestIndex, bestSSD := 0, uint32(1<<32-1)
On 2013/07/08 01:51:25, r wrote:
> this is fine but it can be done more efficiently. you have a 32-bit color
value
> but the RGB in the palette is only 8 bits, which suggests some clever options.
> caching can also help, but you need to watch out for bloat (again, remember
the
> 8 bit rule).

I'm curious what optimizations you had in mind (what's the 8-bit rule?). I guess
you could cache recent dst colors keyed by (er, eg, eb) although with
Floyd-Steinberg I wouldn't expect many cache hits.

Also, in theory, the colors in a color.Palette aren't restricted to 8 bits; they
could be color.RGBA64 values. In package color, it's
type Palette []Color
and not
type Palette []RGBA

[r, 2013-07-08 03:10:22]

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize.go
File src/pkg/image/draw/quantize.go (right):

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:16: Quantize(dst *image.Paletted, r
image.Rectangle, src image.Image, sp image.Point)
floyd-steinberg makes sense for any image type, and is genuinely useful on
low-pixel-depth grayscale images.

https://codereview.appspot.com/10977043/diff/6001/src/pkg/image/draw/quantize...
src/pkg/image/draw/quantize.go:78: bestIndex, bestSSD := 0, uint32(1<<32-1)
just put in a TODO to consider smarter algorithms.

[nigeltao, 2013-07-09 23:33:01]

PTAL.

FloydSteinberg now applies to any draw.Image, not just an
*image.Paletted. NaiveQuantizer was removed; use the Src Op instead.
The Quantizer interface was renamed Drawer, and now takes an arbitrary
draw.Image as a dst, not just *image.Paletted. The Quantizer name is
now free to use for the thing that derives a color.Palette from a
color.Image. That'll be a follow-up CL.

I've attached a couple more images, from ye olde CGA palette of my youth.

[r, 2013-07-10 03:10:43]

LGTM

[nigeltao, 2013-07-10 22:47:44]

*** Submitted as https://code.google.com/p/go/source/detail?r=ddb4f9feee8b ***

image/draw: add Drawer, FloydSteinberg and the op.Draw method.

R=r, andybons
CC=andybons, golang-dev
https://codereview.appspot.com/10977043

[srinathh_gmail.com, 2014-08-29 20:36:43]

Nigel,

Have you released any Quantizer implementation yet that produces an 
optimized color.Palette for an image?

I'm working on creating animated GIFs 
<https://github.com/srinathh/goanigiffy> from a series of frames extracted 
from a video & finding that the only way
 to get good dithering is to first save each image as a gif using 
gif.Encode() to a bytes.Buffer and reload the image
using gif.Decode() into a slice of image pointers to pass to the 
gif.EncodeAll()

if a Quantier were available, ideally we could create a image.Paletted with 
the optimized pallette in the first place
for draw.Draw() to operate on without going through an intermediate GIF 
encoding & decoding

Best Regards
Srinath

On Wednesday, July 10, 2013 5:03:00 AM UTC+5:30, Nigel Tao wrote:
>
> PTAL. 
>
> FloydSteinberg now applies to any draw.Image, not just an 
> *image.Paletted. NaiveQuantizer was removed; use the Src Op instead. 
> The Quantizer interface was renamed Drawer, and now takes an arbitrary 
> draw.Image as a dst, not just *image.Paletted. The Quantizer name is 
> now free to use for the thing that derives a color.Palette from a 
> color.Image. That'll be a follow-up CL. 
>
> I've attached a couple more images, from ye olde CGA palette of my youth. 
>

[nigeltao, 2014-09-01 06:37:51]

On Sat, Aug 30, 2014 at 6:36 AM,  <srinathh@gmail.com> wrote:
> Have you released any Quantizer implementation yet that produces an
> optimized color.Palette for an image?

No, but if you're not explicitly setting a Quantizer, then the
image/gif package is using the Plan 9 palette, so for each of your
source images, you could convert to a paletted image directly without
also needing to encode to and decode from GIF:

dst := image.NewPaletted(src.Bounds(), palette.Plan9)
draw.FloydSteinberg.Draw(dst, dst.Bounds(), src, image.ZP)

This is essentially the (default) implementation of gif.Encode:
http://golang.org/src/pkg/image/gif/writer.go?s=6476:6533#L281

[srinathh_gmail.com, 2014-09-01 07:57:41]

Hi Nigel,

Thanks - yes i also realized this yesterday night looking through the
sources for packages gif & draw. I think I've tracked down the issue of why
i was getting poor dithering. I was using draw.Draw() rather than using
draw.FloydSteinberg.Draw()

In the file draw.go in line 157, drawPaletted() is being called with the
last parameter for activating FloydSteinberg set to *false*.
http://golang.org/src/pkg/image/draw/draw.go?s=4522:4559#L157

If i understand this thread correctly, FloydSteinberg should now apply in
all cases & this parameter should be *true *instead right? Or alternatively
in case omitting dithering is a feature, I guess the documentation should
note it?

Best Regards
Srinath

Best Regards,
Srinath
*Blog:* Curiosity & the Geek <http://srinathh.github.io/>


On Mon, Sep 1, 2014 at 12:07 PM, Nigel Tao <nigeltao@golang.org> wrote:

> On Sat, Aug 30, 2014 at 6:36 AM,  <srinathh@gmail.com> wrote:
> > Have you released any Quantizer implementation yet that produces an
> > optimized color.Palette for an image?
>
> No, but if you're not explicitly setting a Quantizer, then the
> image/gif package is using the Plan 9 palette, so for each of your
> source images, you could convert to a paletted image directly without
> also needing to encode to and decode from GIF:
>
> dst := image.NewPaletted(src.Bounds(), palette.Plan9)
> draw.FloydSteinberg.Draw(dst, dst.Bounds(), src, image.ZP)
>
> This is essentially the (default) implementation of gif.Encode:
> http://golang.org/src/pkg/image/gif/writer.go?s=6476:6533#L281
>

[nigeltao, 2014-09-02 00:14:01]

On Mon, Sep 1, 2014 at 5:57 PM, Hariharan Srinath <srinathh@gmail.com> wrote:
> If i understand this thread correctly, FloydSteinberg should now apply in
> all cases & this parameter should be true instead right? Or alternatively in
> case omitting dithering is a feature, I guess the documentation should note
> it?

Floyd-Steinberg should not apply in all cases. Dithering results in
better quality images, but it's slower to compute, and the results
don't compress as well. There are also multiple ways to dither;
Floyd-Steinberg is only one algorithm of many. The default operation
for draw.Draw is not to dither.