|
|
Created:
11 years, 5 months ago by Andrew Bonventre Modified:
11 years, 4 months ago Reviewers:
nigeltao CC:
r, nigeltao, golang-dev Visibility:
Public. |
Descriptionimage/gif: add writer implementation
Patch Set 1 #Patch Set 2 : diff -r 09e39a9ce38e https://code.google.com/p/go #
Total comments: 66
Patch Set 3 : diff -r e334347476c4 https://code.google.com/p/go #Patch Set 4 : diff -r e334347476c4 https://code.google.com/p/go #Patch Set 5 : diff -r 84917868ef43 https://code.google.com/p/go #Patch Set 6 : diff -r fc06b300732a https://code.google.com/p/go #Patch Set 7 : diff -r c1301713bae7 https://code.google.com/p/go #Patch Set 8 : diff -r c1301713bae7 https://code.google.com/p/go #Patch Set 9 : diff -r c1301713bae7 https://code.google.com/p/go #Patch Set 10 : diff -r c1301713bae7 https://code.google.com/p/go #Patch Set 11 : diff -r c1301713bae7 https://code.google.com/p/go #Patch Set 12 : diff -r c1301713bae7 https://code.google.com/p/go #
Total comments: 18
Patch Set 13 : diff -r 26f441a1f78b https://code.google.com/p/go/ #
Total comments: 14
Patch Set 14 : diff -r 26f441a1f78b https://code.google.com/p/go/ #
MessagesTotal messages: 18
I’ve noticed some hot spots when I benchmarked that I plan to address. The two notable ones are both within the Quantizer. lines 172 and 246 are the most obvious areas where performance should be improved before submission.
Sign in to reply to this message.
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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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_te... File src/pkg/image/gif/writer_test.go (right): https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_te... 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_te... 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_te... 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.
Sign in to reply to this message.
Also, please complete a Contributor License Agreement if you haven't already done so: http://golang.org/doc/contribute.html#copyright
Sign in to reply to this message.
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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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... 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_te... File src/pkg/image/gif/writer_test.go (right): https://codereview.appspot.com/10896043/diff/3001/src/pkg/image/gif/writer_te... 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_te... 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_te... 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.
Sign in to reply to this message.
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... 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... 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_
Sign in to reply to this message.
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... 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... 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.
Sign in to reply to this message.
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?
Sign in to reply to this message.
> 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.
Sign in to reply to this message.
On Thu, Jul 4, 2013 at 5:30 PM, <nigeltao@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
Sign in to reply to this message.
On Sun, Jul 7, 2013 at 10:35 PM, Nigel Tao <nigeltao@golang.org> wrote: > On Thu, Jul 4, 2013 at 5:30 PM, <nigeltao@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 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.
Sign in to reply to this message.
ptal Removed mediancut.go. What is the purpose of returning a color.Palette from Quantize in addition to potentially altering the one passed in? Would there be a difference between the two at return time?
Sign in to reply to this message.
On Fri, Jul 12, 2013 at 4:37 AM, <andybons@chromium.org> wrote: > What is the purpose of returning a color.Palette from Quantize in > addition to potentially altering the one passed in? Would there be a > difference between the two at return time? Call the argument palette p and the returned one q. len(p) should be less than cap(p), and len(q) should be greater than len(p). // 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
Sign in to reply to this message.
On 2013/07/11 22:29:16, nigeltao wrote: > On Fri, Jul 12, 2013 at 4:37 AM, <mailto:andybons@chromium.org> wrote: > > What is the purpose of returning a color.Palette from Quantize in > > addition to potentially altering the one passed in? Would there be a > > difference between the two at return time? > > Call the argument palette p and the returned one q. len(p) should be > less than cap(p), and len(q) should be greater than len(p). Got it. I believe I’m doing what I should be, then. Let me know if that’s not the case.
Sign in to reply to this message.
https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.go File src/pkg/image/gif/writer.go (right): https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:25: func log2Int256(x int) int { Just call the function log2. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:129: // TODO: GIF87a could be valid depending on the features that I wouldn't bother. Just assume GIF89a. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:179: e.buf[3*i] = uint8(r >> 8) I'd add a +0 for symmetry. The compiler should take it back out. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:203: if b.Dx() >= 1<<16 || b.Dy() >= 1<<16 || b.Min.X >= 1<<16 || b.Min.Y >= 1<<16 { You should also check b.Min.X < 0 and likewise for Y. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:256: bw := &blockWriter{w: e.w} You shouldn't need to allocate a blockWriter for each call to writeImageBlock. In fact, you could probably re-use the encoder's tmp buffer: type blockWriter struct { e *encoder } func (b blockWriter) Write(data []byte) (int, error) { if b.e.err != nil { return 0, b.e.err } etc } https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:268: const DefaultNumColors = 256 I'm not sure that this constant is worth exporting, or even defining. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:299: e := newEncoder(w) It doesn't seem worth defining a newEncoder function. Just inline it: e := encoder{ g: g } if ww, ok := w.(writer); ok { e.w = ww } else { e.w = bufio.NewWriter(w) } https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:322: o.NumColors = DefaultNumColors I'd prefer not to modify the o argument's fields. Instead: opts := *o if opts.NumColors <= 0 || 256 < opts.NumColors { opts.NumColors = 256 } etc. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:330: pm = image.NewPaletted(b, color.Plan9Palette) Strictly speaking, I think that color.Plan9Palette should be color.Plan9Palette[:opts.NumColors] and add a TODO to pick a better sub-sample of the Plan 9 palette.
Sign in to reply to this message.
PTAL https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.go File src/pkg/image/gif/writer.go (right): https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:25: func log2Int256(x int) int { On 2013/07/12 00:47:17, nigeltao wrote: > Just call the function log2. Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:129: // TODO: GIF87a could be valid depending on the features that On 2013/07/12 00:47:17, nigeltao wrote: > I wouldn't bother. Just assume GIF89a. Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:179: e.buf[3*i] = uint8(r >> 8) On 2013/07/12 00:47:17, nigeltao wrote: > I'd add a +0 for symmetry. The compiler should take it back out. Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:203: if b.Dx() >= 1<<16 || b.Dy() >= 1<<16 || b.Min.X >= 1<<16 || b.Min.Y >= 1<<16 { On 2013/07/12 00:47:17, nigeltao wrote: > You should also check b.Min.X < 0 and likewise for Y. Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:256: bw := &blockWriter{w: e.w} On 2013/07/12 00:47:17, nigeltao wrote: > You shouldn't need to allocate a blockWriter for each call to writeImageBlock. > In fact, you could probably re-use the encoder's tmp buffer: > > type blockWriter struct { > e *encoder > } > > func (b blockWriter) Write(data []byte) (int, error) { > if b.e.err != nil { > return 0, b.e.err > } > etc > } Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:268: const DefaultNumColors = 256 On 2013/07/12 00:47:17, nigeltao wrote: > I'm not sure that this constant is worth exporting, or even defining. Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:299: e := newEncoder(w) On 2013/07/12 00:47:17, nigeltao wrote: > It doesn't seem worth defining a newEncoder function. Just inline it: > > e := encoder{ g: g } > if ww, ok := w.(writer); ok { > e.w = ww > } else { > e.w = bufio.NewWriter(w) > } Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:322: o.NumColors = DefaultNumColors On 2013/07/12 00:47:17, nigeltao wrote: > I'd prefer not to modify the o argument's fields. Instead: > > opts := *o > if opts.NumColors <= 0 || 256 < opts.NumColors { > opts.NumColors = 256 > } > etc. Done. https://codereview.appspot.com/10896043/diff/55003/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:330: pm = image.NewPaletted(b, color.Plan9Palette) On 2013/07/12 00:47:17, nigeltao wrote: > Strictly speaking, I think that > color.Plan9Palette > should be > color.Plan9Palette[:opts.NumColors] > and add a TODO to pick a better sub-sample of the Plan 9 palette. Done.
Sign in to reply to this message.
LGTM. I'll make the minor edits and submit. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.go File src/pkg/image/gif/writer.go (right): https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:70: func (b *blockWriter) Write(data []byte) (int, error) { Drop the *. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:125: writeUint16(e.buf[:2], uint16(pm.Bounds().Dx())) I'd change :2 to 0:2, for symmetry. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:169: e.buf[3*i] = 0x00 +0. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:241: bw := &blockWriter{e: e} Drop the &, and just inline this variable into the next line. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:305: if o == nil { Ah, there's no need to allocate here. Instead: opts := Options{} if o != nil { opts = *o } https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer_t... File src/pkg/image/gif/writer_test.go (right): https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer_t... src/pkg/image/gif/writer_test.go:78: t.Error(tc.filename, err) Add continue after this. Similarly below. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer_t... src/pkg/image/gif/writer_test.go:121: t.Error("EncodeAll:", err) Change Error to Fatal, as there's not much point continuing if the EncodeAll fails.
Sign in to reply to this message.
https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.go File src/pkg/image/gif/writer.go (right): https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:70: func (b *blockWriter) Write(data []byte) (int, error) { On 2013/07/12 04:51:04, nigeltao wrote: > Drop the *. Done. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:125: writeUint16(e.buf[:2], uint16(pm.Bounds().Dx())) On 2013/07/12 04:51:04, nigeltao wrote: > I'd change :2 to 0:2, for symmetry. Done. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:169: e.buf[3*i] = 0x00 On 2013/07/12 04:51:04, nigeltao wrote: > +0. Done. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:241: bw := &blockWriter{e: e} On 2013/07/12 04:51:04, nigeltao wrote: > Drop the &, and just inline this variable into the next line. Done. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer.g... src/pkg/image/gif/writer.go:305: if o == nil { On 2013/07/12 04:51:04, nigeltao wrote: > Ah, there's no need to allocate here. Instead: > > opts := Options{} > if o != nil { > opts = *o > } Done. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer_t... File src/pkg/image/gif/writer_test.go (right): https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer_t... src/pkg/image/gif/writer_test.go:78: t.Error(tc.filename, err) On 2013/07/12 04:51:04, nigeltao wrote: > Add > continue > after this. > > Similarly below. Done. https://codereview.appspot.com/10896043/diff/74001/src/pkg/image/gif/writer_t... src/pkg/image/gif/writer_test.go:121: t.Error("EncodeAll:", err) On 2013/07/12 04:51:04, nigeltao wrote: > Change Error to Fatal, as there's not much point continuing if the EncodeAll > fails. Done.
Sign in to reply to this message.
*** Submitted as https://code.google.com/p/go/source/detail?r=58ee92a528da *** image/gif: add writer implementation R=r, nigeltao CC=golang-dev https://codereview.appspot.com/10896043 Committer: Nigel Tao <nigeltao@golang.org>
Sign in to reply to this message.
|