Re: image/gif: add writer implementation with median cut qu... (issue 10896043)

[nige...@golang.org]

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go
File src/pkg/image/gif/mediancut.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode32
src/pkg/image/gif/mediancut.go:32: type point struct {
Or just

type point [numDimensions]uint32

Also, int would seem easier to work with than uint32.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode44
src/pkg/image/gif/mediancut.go:44: b := &block{points: p}
return &block{
minCorner: point{0x00, 0x00, 0x00},
maxCorner: point{0xFF, 0xFF, 0xFF},
points: p,
}

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode83
src/pkg/image/gif/mediancut.go:83: type By func(p1, p2 *point) bool
Why is this type exported?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode85
src/pkg/image/gif/mediancut.go:85: func (by By) Sort(points []point) {
Why is this method exported? We usually don't export methods unless we
have to, and we don't have to.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode86
src/pkg/image/gif/mediancut.go:86: ps := &pointSorter{
You can inline this into the next line:

sort.Sort(&pointSorter{
points: points,
by: by,
})

Or just inline the whole method in the one place it gets called below.
Then you wouldn't need to define a By type.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode98
src/pkg/image/gif/mediancut.go:98: func (ps *pointSorter) Len() int {
I'd change ps to just s.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode111
src/pkg/image/gif/mediancut.go:111: type PriorityQueue []*block
Why is this type exported?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode137
src/pkg/image/gif/mediancut.go:137: *pq = old[0 : n-1]
Drop the 0.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode149
src/pkg/image/gif/mediancut.go:149: type Quantizer interface {
This needs documentation comments.

I'd also move it to writer.go, near where the Options type is defined.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode150
src/pkg/image/gif/mediancut.go:150: Quantize(m image.Image)
(*image.Paletted, error)
Was this the API that we agreed on??

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode153
src/pkg/image/gif/mediancut.go:153: type MedianCutQuantizer struct {
This needs documentation comments.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode178
src/pkg/image/gif/mediancut.go:178: block1 := newBlock(points[0:median])
Drop the 0.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode190
src/pkg/image/gif/mediancut.go:190: sum := make([]uint32, numDimensions)
numDimensions is constant, use a (stack-allocated) array instead of a
slice.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode201
src/pkg/image/gif/mediancut.go:201: R: uint16(avgPoint.x[0]),
I wouldn't bother with an avgPoint variable, and just use
sum[0] / len(block.points)
directly here.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode215
src/pkg/image/gif/mediancut.go:215: colorSet :=
make(map[color.Color]bool, q.NumColor)
The color.Color implementation could be a func, which is not a valid map
key type.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode242
src/pkg/image/gif/mediancut.go:242: pm := image.NewPaletted(m.Bounds(),
palette)
m.Bounds() could be just bounds.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode243
src/pkg/image/gif/mediancut.go:243: pm.Stride = m.Bounds().Dx()
Huh?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode246
src/pkg/image/gif/mediancut.go:246: pm.Set(x, y, m.At(x, y))
Add a TODO to do this more efficiently.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go
File src/pkg/image/gif/writer.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode41
src/pkg/image/gif/writer.go:41: io.ByteWriter
Do you call writer.WriteByte anywhere? You probably should, as it should
be more efficient that calling Write with 1-byte slices.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode78
src/pkg/image/gif/writer.go:78: b.slice = b.tmp[1:256]
Why is b.slice a field? Just use b.tmp[1:256] on the next line.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode128
src/pkg/image/gif/writer.go:128: e.buf[0] = 0x21 // Extention
Introducer.
Typo in "Extension".

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode129
src/pkg/image/gif/writer.go:129: e.buf[1] = 0xff // Aplication Label.
Typo in "Application".

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode161
src/pkg/image/gif/writer.go:161: e.write(e.buf[:3])
Making 1 write of 768 bytes will be more efficient than 256 writes of 3
bytes.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode199
src/pkg/image/gif/writer.go:199: writeUint16(e.buf[1:3],
uint16(pm.Bounds().Min.X))
You should probably return an error if any of these bounds overflow a
uint16.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode205
src/pkg/image/gif/writer.go:205: if len(pm.Palette) > 0 {
I'd just return an error if pm has an empty palette.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode265
src/pkg/image/gif/writer.go:265: return e.err
If e.w was created above by bufio.NewWriter, then you may have unflushed
bytes here.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode282
src/pkg/image/gif/writer.go:282: pm, e.err = o.Quantizer.Quantize(m)
Quantization is unnecessary work if m is already an *image.Paletted:

pm, ok := m.(*image.Paletted)
if !ok {
// Quantize.
}

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode286
src/pkg/image/gif/writer.go:286: e.g = &GIF{Image:
[]*image.Paletted{pm}}
All this below should just be a call to EncodeAll.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go
File src/pkg/image/gif/writer_test.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go#newcode28
src/pkg/image/gif/writer_test.go:28: func readGif(filename string)
(*GIF, error) {
readGif should be readGIF.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go#newcode109
src/pkg/image/gif/writer_test.go:109: Delay: make([]int,
len(frames), 5),
Why the ", 5"?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go#newcode156
src/pkg/image/gif/writer_test.go:156: // Restrict to a 256-color palette
to avoid quantization path.
I'd also like a benchmark for the quantization path. Your current
implementation seems very allocation-heavy.

https://codereview.appspot.com/10896043/

[nige...@golang.org]

Also, please complete a Contributor License Agreement if you haven't
already done so:

http://golang.org/doc/contribute.html#copyright

https://codereview.appspot.com/10896043/

[nige...@golang.org]

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go
File src/pkg/image/gif/mediancut.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode150
src/pkg/image/gif/mediancut.go:150: Quantize(m image.Image)
(*image.Paletted, error)

On 2013/07/03 17:19:35, Andrew Bonventre wrote:
> In the above API, what do r and sp specify exactly? Is r the bounds of
the src
> image that the palette should be quantized from? What is sp?

They have the same meaning as the image/draw package.
http://golang.org/pkg/image/draw/
and
http://golang.org/doc/articles/image_draw.html

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode243
src/pkg/image/gif/mediancut.go:243: pm.Stride = m.Bounds().Dx()

On 2013/07/03 17:19:35, Andrew Bonventre wrote:
> Apologies if I’m missing something...?

image.NewPaletted already sets the stride to the correct value. You
shouldn't have to override it, and if you do, you're possibly setting it
to the wrong value. The stride is not necessarily the width of the image
rectangle, if the pixel buffer is part of a larger (wider) buffer. But
NewPaletted takes care of all of that.

http://play.golang.org/p/N0EA91shi_

https://codereview.appspot.com/10896043/

[nige...@golang.org]

It looks like the median cut algorithm isn't cheap. For a 1000x1000
pixel image, you're allocating a million points (even if the image only
contains e.g. 300 distinct colors) and repeatedly sorting them.

Encoding full-color image as a GIF involves several steps:
1. calculating an appropriate palette,
2. converting the source image to that palette,
3. writing the paletted image in GIF-specific format (headers, LZW
compression, blocks, etc.)

So far, I think we've treated 1 and 2 as a monolithic processs. On
second thoughts, it may be better to separate them out.

Specifically, step 1 isn't cheap, and step 1 can be avoided if you use a
pre-defined palette. The Netscape Color Cube is one such palette. The
Plan 9 palette (http://plan9.bell-labs.com/magic/man2html/6/color) is
another one, with the nice property that it contains 16 shades of gray,
so grayscale or mostly-grayscale images look pretty reasonable.

It may be better for package gif's default encoding method to use a
standard palette, while keeping the option to specify a custom quantizer
such as one that implements median-cut.

Rob and I need to do some more thinking about this, but I'm pretty busy
for the next few days. Can you hold off on this one for a bit?

https://codereview.appspot.com/10896043/

[andy...@chromium.org]

Thanks for the speedy response, Nigel.

Changes made with a question about the API inline.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go
File src/pkg/image/gif/mediancut.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode32
src/pkg/image/gif/mediancut.go:32: type point struct {

On 2013/07/03 03:27:25, nigeltao wrote:
> Or just

> type point [numDimensions]uint32

> Also, int would seem easier to work with than uint32.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode44
src/pkg/image/gif/mediancut.go:44: b := &block{points: p}

On 2013/07/03 03:27:25, nigeltao wrote:
> return &block{
> minCorner: point{0x00, 0x00, 0x00},
> maxCorner: point{0xFF, 0xFF, 0xFF},
> points: p,
> }

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode83
src/pkg/image/gif/mediancut.go:83: type By func(p1, p2 *point) bool

On 2013/07/03 03:27:25, nigeltao wrote:
> Why is this type exported?

Apologies. Lost track of what should be exported to satisfy
heap.Interface within this code.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode85
src/pkg/image/gif/mediancut.go:85: func (by By) Sort(points []point) {

On 2013/07/03 03:27:25, nigeltao wrote:
> Why is this method exported? We usually don't export methods unless we
have to,
> and we don't have to.

Brain fart syndrome?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode86
src/pkg/image/gif/mediancut.go:86: ps := &pointSorter{

On 2013/07/03 03:27:25, nigeltao wrote:
> You can inline this into the next line:

> sort.Sort(&pointSorter{
> points: points,
> by: by,
> })

> Or just inline the whole method in the one place it gets called below.
Then you
> wouldn't need to define a By type.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode98
src/pkg/image/gif/mediancut.go:98: func (ps *pointSorter) Len() int {

On 2013/07/03 03:27:25, nigeltao wrote:
> I'd change ps to just s.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode111
src/pkg/image/gif/mediancut.go:111: type PriorityQueue []*block

On 2013/07/03 03:27:25, nigeltao wrote:
> Why is this type exported?

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode137
src/pkg/image/gif/mediancut.go:137: *pq = old[0 : n-1]

On 2013/07/03 03:27:25, nigeltao wrote:
> Drop the 0.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode149
src/pkg/image/gif/mediancut.go:149: type Quantizer interface {

On 2013/07/03 03:27:25, nigeltao wrote:
> This needs documentation comments.

> I'd also move it to writer.go, near where the Options type is defined.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode150
src/pkg/image/gif/mediancut.go:150: Quantize(m image.Image)
(*image.Paletted, error)

On 2013/07/03 03:27:25, nigeltao wrote:
> Was this the API that we agreed on??

Nope. I should have gotten clarification earlier on the thread. Sorry
about that.

Within the API we had discussed, you had suggested:

type Quantizer interface {
// Quantize sets dst.Palette as well as dst's pixels.
// TODO: would we ever want to pass a color.Palette in as a hint?
// Is it feasible to use dst.Palette's initial value as that?
// TODO: should dst be a draw.Image (with a fast path for
image.Paletted)?
// Would Quantize then have to return a color.Palette?
Quantize(dst image.Paletted, r image.Rectangle, src image.Image, sp
image.Point)

}

In the above API, what do r and sp specify exactly? Is r the bounds of
the src image that the palette should be quantized from? What is sp?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode153
src/pkg/image/gif/mediancut.go:153: type MedianCutQuantizer struct {

On 2013/07/03 03:27:25, nigeltao wrote:
> This needs documentation comments.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode178
src/pkg/image/gif/mediancut.go:178: block1 := newBlock(points[0:median])

On 2013/07/03 03:27:25, nigeltao wrote:
> Drop the 0.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode190
src/pkg/image/gif/mediancut.go:190: sum := make([]uint32, numDimensions)

On 2013/07/03 03:27:25, nigeltao wrote:
> numDimensions is constant, use a (stack-allocated) array instead of a
slice.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode201
src/pkg/image/gif/mediancut.go:201: R: uint16(avgPoint.x[0]),

On 2013/07/03 03:27:25, nigeltao wrote:
> I wouldn't bother with an avgPoint variable, and just use
> sum[0] / len(block.points)
> directly here.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode215
src/pkg/image/gif/mediancut.go:215: colorSet :=
make(map[color.Color]bool, q.NumColor)

On 2013/07/03 03:27:25, nigeltao wrote:
> The color.Color implementation could be a func, which is not a valid
map key
> type.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode242
src/pkg/image/gif/mediancut.go:242: pm := image.NewPaletted(m.Bounds(),
palette)

On 2013/07/03 03:27:25, nigeltao wrote:
> m.Bounds() could be just bounds.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode243
src/pkg/image/gif/mediancut.go:243: pm.Stride = m.Bounds().Dx()

On 2013/07/03 03:27:25, nigeltao wrote:
> Huh?

Since each pixel within a palette is represented by a single byte, and
Stride represents the distance between vertically adjacent bytes, the
width of the image rectangle is used.

Apologies if I’m missing something...?

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode246
src/pkg/image/gif/mediancut.go:246: pm.Set(x, y, m.At(x, y))

On 2013/07/03 03:27:25, nigeltao wrote:
> Add a TODO to do this more efficiently.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go
File src/pkg/image/gif/writer.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode41
src/pkg/image/gif/writer.go:41: io.ByteWriter

On 2013/07/03 03:27:25, nigeltao wrote:
> Do you call writer.WriteByte anywhere? You probably should, as it
should be more
> efficient that calling Write with 1-byte slices.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode78
src/pkg/image/gif/writer.go:78: b.slice = b.tmp[1:256]

On 2013/07/03 03:27:25, nigeltao wrote:
> Why is b.slice a field? Just use b.tmp[1:256] on the next line.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode128
src/pkg/image/gif/writer.go:128: e.buf[0] = 0x21 // Extention
Introducer.

On 2013/07/03 03:27:25, nigeltao wrote:
> Typo in "Extension".

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode129
src/pkg/image/gif/writer.go:129: e.buf[1] = 0xff // Aplication Label.

On 2013/07/03 03:27:25, nigeltao wrote:
> Typo in "Application".

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode161
src/pkg/image/gif/writer.go:161: e.write(e.buf[:3])

On 2013/07/03 03:27:25, nigeltao wrote:
> Making 1 write of 768 bytes will be more efficient than 256 writes of
3 bytes.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode199
src/pkg/image/gif/writer.go:199: writeUint16(e.buf[1:3],
uint16(pm.Bounds().Min.X))

On 2013/07/03 03:27:25, nigeltao wrote:
> You should probably return an error if any of these bounds overflow a
uint16.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode205
src/pkg/image/gif/writer.go:205: if len(pm.Palette) > 0 {

On 2013/07/03 03:27:25, nigeltao wrote:
> I'd just return an error if pm has an empty palette.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode265
src/pkg/image/gif/writer.go:265: return e.err

On 2013/07/03 03:27:25, nigeltao wrote:
> If e.w was created above by bufio.NewWriter, then you may have
unflushed bytes
> here.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode282
src/pkg/image/gif/writer.go:282: pm, e.err = o.Quantizer.Quantize(m)

On 2013/07/03 03:27:25, nigeltao wrote:
> Quantization is unnecessary work if m is already an *image.Paletted:

> pm, ok := m.(*image.Paletted)
> if !ok {
> // Quantize.
> }

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer.go#newcode286
src/pkg/image/gif/writer.go:286: e.g = &GIF{Image:
[]*image.Paletted{pm}}

On 2013/07/03 03:27:25, nigeltao wrote:
> All this below should just be a call to EncodeAll.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go
File src/pkg/image/gif/writer_test.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go#newcode28
src/pkg/image/gif/writer_test.go:28: func readGif(filename string)
(*GIF, error) {

On 2013/07/03 03:27:25, nigeltao wrote:
> readGif should be readGIF.

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go#newcode109
src/pkg/image/gif/writer_test.go:109: Delay: make([]int,
len(frames), 5),

On 2013/07/03 03:27:25, nigeltao wrote:
> Why the ", 5"?

Oops. Removed.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_test.go#newcode156
src/pkg/image/gif/writer_test.go:156: // Restrict to a 256-color palette
to avoid quantization path.

On 2013/07/03 03:27:25, nigeltao wrote:
> I'd also like a benchmark for the quantization path. Your current
implementation
> seems very allocation-heavy.

Done.

https://codereview.appspot.com/10896043/

[andy...@chromium.org]

ptal

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go
File src/pkg/image/gif/mediancut.go (right):

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode150
src/pkg/image/gif/mediancut.go:150: Quantize(m image.Image)
(*image.Paletted, error)

On 2013/07/03 23:48:04, nigeltao wrote:
> On 2013/07/03 17:19:35, Andrew Bonventre wrote:

> > In the above API, what do r and sp specify exactly? Is r the bounds
of the src
> > image that the palette should be quantized from? What is sp?

> They have the same meaning as the image/draw package.
> http://golang.org/pkg/image/draw/
> and
> http://golang.org/doc/articles/image_draw.html

Done.

https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/mediancut.go#newcode243
src/pkg/image/gif/mediancut.go:243: pm.Stride = m.Bounds().Dx()

On 2013/07/03 23:48:04, nigeltao wrote:
> On 2013/07/03 17:19:35, Andrew Bonventre wrote:

> > Apologies if I’m missing something...?

> image.NewPaletted already sets the stride to the correct value. You
shouldn't
> have to override it, and if you do, you're possibly setting it to the
wrong
> value. The stride is not necessarily the width of the image rectangle,
if the
> pixel buffer is part of a larger (wider) buffer. But NewPaletted takes
care of
> all of that.

> http://play.golang.org/p/N0EA91shi_

Done.

https://codereview.appspot.com/10896043/

[andy...@chromium.org]

> Rob and I need to do some more thinking about this, but I'm pretty
busy for the
> next few days. Can you hold off on this one for a bit?

Sure. No worries.

https://codereview.appspot.com/10896043/

[Nigel Tao]

On Thu, Jul 4, 2013 at 5:30 PM, <nige...@golang.org> wrote:
> Encoding full-color image as a GIF involves several steps:
> 1. calculating an appropriate palette,
> 2. converting the source image to that palette,
> 3. writing the paletted image in GIF-specific format (headers, LZW
> compression, blocks, etc.)

I've had a go at implementing step 2. Please take a look at
https://codereview.appspot.com/10977043

[Nigel Tao]

Step 2 has been submitted. Step 1 should be covered by
https://codereview.appspot.com/11148043/ which adds a draw.Quantizer
interface:

// Quantizer produces a palette for an image.
type Quantizer interface {
// Quantize appends up to cap(p) - len(p) colors to p and returns the
// updated palette suitable for converting m to a paletted image.
Quantize(p color.Palette, m image.Image) color.Palette
}

I think that this CL should focus on step 3, and Options should be

type Options struct {
NumColors int
Quantizer draw.Quantizer
Drawer draw.Drawer
}

If NumColors is zero then use 256. If Quantizer is zero (nil), then
just use color.Plan9Palette as a standard palette. If Drawer is zero
then use draw.FloydSteinberg.

MedianCut will implement Quantizer but I don't think that it belongs
in the standard library yet. You are of course free to host it on
github, code.google.com, etc.