image: PalettedColor added.

image: PalettedColor added.

Motivation: image.Image interface is very abstract and useful not only to access in-memory images, but also on-disk images (think tiled geotiff and images to big to load them into memory)
Currently the only way to access color indices of paletted image is in-memory image.Paletted.
As a consequence, the present png.Encode() can encode paletted image only from this in-memory source, but not from any Image whose ColorModel() is image.PalettedColorModel

Introduced image.PalettedColor encapsulates color index and palette slice.
This allows to calc RGBA color quickly and also does not loose its color index in the palette.

Storing color index is useful for operations which preserve palette, such as taking image slice or converting image from one file format to another.

Also, PNG Writer changed to be more generic and to work with on-disk paletted images as the source.

[rsc, 2011-08-28 15:55:24]

Can you benchmark paletted image encoding
before and after this change?  I think you will
find that the new code, while certainly cleaner,
is significantly slower.

Russ

[jp, 2011-08-28 17:01:24]

On 2011/08/28 15:55:24, rsc wrote:
> Can you benchmark paletted image encoding
> before and after this change?  I think you will
> find that the new code, while certainly cleaner,
> is significantly slower.

Well, benchmarking depends on the pattern of usage.

The only case which could be slower is encoding in-memory image.Paletted. 
image.Paletted cannot be huge due to its in-memory nature.

Work with other image sources (besides that in-memory array whose internal
structure png.Writer aware of), such as 
* on-disk tiled tiff; 
* Image interface which represents a few smaller Images as a single Image;
* Image interface which zooms another Image;
* Image interface which makes the palette of another Image smaller;
is definetely faster.
Before they had been encoding as RGB24 (3 bytes per pixel) and in two passes.
First pass is straightforward full scan of the whole image for opaque pixels
(which implies full read of src image if it is on-disk) and the actual encoding
on the second.

Also, in order to make a paletted image back from the Image which has lost its
palette and color indices, it is necessary to use very slow function "func (p
PalettedColorModel) Index(c Color) int".

[jp, 2011-08-28 17:32:18]

Also, please have a look at the code png/writer.go around my patch.
using copy() there was not a speed optimization but a kludge to gen access to
color indices.
Other color models use per-pixel interface conversion (as P8 after my patch) and
can be optimized by checking if the source image is a known in-memory one in
order to use fast per-line copy.

This patch makes the work with all the color models uniform.

Then, if necessary, png/writer can be profiled and speed optimized so  all the
color models will work faster.

On 2011/08/28 17:01:24, jp wrote:
> On 2011/08/28 15:55:24, rsc wrote:
> > Can you benchmark paletted image encoding
> > before and after this change?  I think you will
> > find that the new code, while certainly cleaner,
> > is significantly slower.
> 
> Well, benchmarking depends on the pattern of usage.
> 
> The only case which could be slower is encoding in-memory image.Paletted. 
> image.Paletted cannot be huge due to its in-memory nature.
> 
> Work with other image sources (besides that in-memory array whose internal
> structure png.Writer aware of), such as 
> * on-disk tiled tiff; 
> * Image interface which represents a few smaller Images as a single Image;
> * Image interface which zooms another Image;
> * Image interface which makes the palette of another Image smaller;
> is definetely faster.
> Before they had been encoding as RGB24 (3 bytes per pixel) and in two passes.
> First pass is straightforward full scan of the whole image for opaque pixels
> (which implies full read of src image if it is on-disk) and the actual
encoding
> on the second.
> 
> Also, in order to make a paletted image back from the Image which has lost its
> palette and color indices, it is necessary to use very slow function "func (p
> PalettedColorModel) Index(c Color) int".

[bradfitz, 2011-08-28 20:33:47]

So is it faster or slower now?

There are plenty of existing benchmarks you copy/paste from in the image
directory.


On Sun, Aug 28, 2011 at 9:32 PM, <jp@webmaster.ms> wrote:

> Also, please have a look at the code png/writer.go around my patch.
> using copy() there was not a speed optimization but a kludge to gen
> access to color indices.
> Other color models use per-pixel interface conversion (as P8 after my
> patch) and can be optimized by checking if the source image is a known
> in-memory one in order to use fast per-line copy.
>
> This patch makes the work with all the color models uniform.
>
> Then, if necessary, png/writer can be profiled and speed optimized so
> all the color models will work faster.
>
>
> On 2011/08/28 17:01:24, jp wrote:
>
>> On 2011/08/28 15:55:24, rsc wrote:
>> > Can you benchmark paletted image encoding
>> > before and after this change?  I think you will
>> > find that the new code, while certainly cleaner,
>> > is significantly slower.
>>
>
>  Well, benchmarking depends on the pattern of usage.
>>
>
>  The only case which could be slower is encoding in-memory
>>
> image.Paletted.
>
>> image.Paletted cannot be huge due to its in-memory nature.
>>
>
>  Work with other image sources (besides that in-memory array whose
>>
> internal
>
>> structure png.Writer aware of), such as
>> * on-disk tiled tiff;
>> * Image interface which represents a few smaller Images as a single
>>
> Image;
>
>> * Image interface which zooms another Image;
>> * Image interface which makes the palette of another Image smaller;
>> is definetely faster.
>> Before they had been encoding as RGB24 (3 bytes per pixel) and in two
>>
> passes.
>
>> First pass is straightforward full scan of the whole image for opaque
>>
> pixels
>
>> (which implies full read of src image if it is on-disk) and the actual
>>
> encoding
>
>> on the second.
>>
>
>  Also, in order to make a paletted image back from the Image which has
>>
> lost its
>
>> palette and color indices, it is necessary to use very slow function
>>
> "func (p
>
>> PalettedColorModel) Index(c Color) int".
>>
>
>
>
>
http://codereview.appspot.com/**4956046/<http://codereview.appspot.com/4956046/>
>

[jp, 2011-08-28 21:30:11]

On 2011/08/28 20:33:47, bradfitz wrote:
Slower, about 7x.
I made the change in order not to affect the performance in case of in-memory
source.
Perhaps it worth to do the same for the other ColorModels, as all they use
slower code.

> So is it faster or slower now?
> 
> There are plenty of existing benchmarks you copy/paste from in the image
> directory.

[nigeltao, 2011-08-29 00:31:12]

On 28 August 2011 12:39,  <jp@webmaster.ms> wrote:
> Description:
> image: PalettedColor added.

I'm happy to broaden the types of images which a png Writer thinks are
Paletted. I'm not happy with adding a PalettedColor type.

Instead, I'd add the following interface to package image:

type PalettedImage interface {
  Image
  ColorIndexAt(x, y int) uint8
  PalettedColorModel() PalettedColorModel
}

and make png.Writer work with that.

[jp, 2011-08-29 01:28:53]

On 2011/08/29 00:31:12, nigeltao wrote:
> On 28 August 2011 12:39,  <mailto:jp@webmaster.ms> wrote:
> > Description:
> > image: PalettedColor added.
> 
> I'm happy to broaden the types of images which a png Writer thinks are
> Paletted. I'm not happy with adding a PalettedColor type.

Can you explain why?
It is just color index and slice (can be changed to pointer to slice).
Not much heavier than RGBAColor or RGBA48Color which is used at the moment to
represent colors.

> Instead, I'd add the following interface to package image:
> 
> type PalettedImage interface {
>   Image
>   ColorIndexAt(x, y int) uint8
>   PalettedColorModel() PalettedColorModel
> }
> 
> and make png.Writer work with that.

That would make another things diffucult.
It is easy for png.Reader to return a struct with or without image.PalettedImage
interface for it returns a very own structure for each in-memory format.

But, for example, I have a struct which incorporates big tiff image on disk.
Should it implement image.PalettedImage interface? Or should I declare 2
structs?

Also, having single Image interface make simpler thinks like Image converters,
like "func ZoomedImage(img imake.Image) imake.Image", "func BlackWhiteImage(img
imake.Image) imake.Image".
With introducing PalettedImage all of them will have to check for PalettedImage
inside and threat it specially.

[jp, 2011-08-29 01:49:35]

I meant zerocopy image converters, like below
With PalettedImage they will lose color index information unless they have
special support to pass it. Do they have to be aware of palettes?

============
type BiggerImage struct {
  image image.Image
  rate  int
}

func (si* BiggerImage) ColorModel() image.ColorModel {
  return si.image.ColorModel()
}

func (si* BiggerImage) Bounds() image.Rectangle {
  r := si.image.Bounds()
  r.Min.X = r.Min.X*si.rate
  r.Min.Y = r.Min.Y*si.rate
  r.Max.X = r.Max.X*si.rate
  r.Max.Y = r.Max.Y*si.rate
  return r
}

func (si* BiggerImage) At(x, y int) image.Color {
  return si.image.At(x/si.rate, y/si.rate)
}

func NewBiggerImage(img image.Image, rate int) image.Image {
  return &BiggerImage{img, rate}
}
============

On 2011/08/29 01:28:53, jp wrote:
> On 2011/08/29 00:31:12, nigeltao wrote:
> > On 28 August 2011 12:39,  <mailto:jp@webmaster.ms> wrote:
> > > Description:
> > > image: PalettedColor added.
> > 
> > I'm happy to broaden the types of images which a png Writer thinks are
> > Paletted. I'm not happy with adding a PalettedColor type.
> 
> Can you explain why?
> It is just color index and slice (can be changed to pointer to slice).
> Not much heavier than RGBAColor or RGBA48Color which is used at the moment to
> represent colors.
> 
> > Instead, I'd add the following interface to package image:
> > 
> > type PalettedImage interface {
> >   Image
> >   ColorIndexAt(x, y int) uint8
> >   PalettedColorModel() PalettedColorModel
> > }
> > 
> > and make png.Writer work with that.
> 
> That would make another things diffucult.
> It is easy for png.Reader to return a struct with or without
image.PalettedImage
> interface for it returns a very own structure for each in-memory format.
> 
> But, for example, I have a struct which incorporates big tiff image on disk.
> Should it implement image.PalettedImage interface? Or should I declare 2
> structs?
> 
> Also, having single Image interface make simpler thinks like Image converters,
> like "func ZoomedImage(img imake.Image) imake.Image", "func
BlackWhiteImage(img
> imake.Image) imake.Image".
> With introducing PalettedImage all of them will have to check for
PalettedImage
> inside and threat it specially.

[nigeltao, 2011-08-29 04:35:08]

On 29 August 2011 11:28,  <jp@webmaster.ms> wrote:
>> I'm happy to broaden the types of images which a png Writer thinks are
>> Paletted. I'm not happy with adding a PalettedColor type.
>
> Can you explain why?
> It is just color index and slice (can be changed to pointer to slice).
> Not much heavier than RGBAColor or RGBA48Color which is used at the
> moment to represent colors.

It is qualitatively heaver than RGBAColor or RGBA64Color: your
PalettedColor struct is larger than the size of a pointer, and hence
as a Color (an interface value) the data needs to live on the heap.
See http://research.swtch.com/2009/12/go-data-structures-interfaces.html
for an explanation of memory layout.

In comparison, RGBAColor is 4 bytes and RGBA64Color is 8 bytes. The
former is <= the size of a pointer on both 32-bit and 64-bit GOARCHes,
the latter is on 64-bit.


> But, for example, I have a struct which incorporates big tiff image on
> disk. Should it implement image.PalettedImage interface? Or should I
> declare 2 structs?
>
> Also, having single Image interface make simpler thinks like Image
> converters, like "func ZoomedImage(img imake.Image) imake.Image", "func
> BlackWhiteImage(img imake.Image) imake.Image".
> With introducing PalettedImage all of them will have to check for
> PalettedImage inside and threat it specially.

I would have your ZoomedImage function return an image.Image, whose
concrete type also implements the image.PalettedImage interface (and
Opaque would help, too). When zooming a non-paletted image, the
ColorIndexAt and PalettedColorModel methods should return zeroes.
png.Writer should switch on both m.ColorModel returning a
PalettedColorModel and m implementing image.PalettedImage.

On second thoughts, I don't think that a PalettedColorModel method is
necessary. But I would still have a PalettedImage interface with a
ColorIndexAt method. The fact that adding this interface will require
no changes to the image.Paletted type is a good sign.

[jp, 2011-08-29 05:28:15]

It results in almost every code which works with image.Image will check it for
image.PalettedImage. 

Encoders - yes, decoders - yes, transformers - yes.
The only exception I see is the code that displays images.

But we have ColorModel() in Image interface which displayers do not use as well.
All the code which use ColorModel() will check for image.PalettedImage and then
use ColorIndexAt().

I mean, if we have to split the interface {
Bounds()
At(x, y int)
ColorModel()
ColorIndexAt(x, y int)
}
into 'simple' (for displayers) and 'advanced' (for readers, writers and
transformers), there will be Bounds() and At(x, y int) in the former and
ColorModel() and ColorIndexAt(x, y int) in the latter 

What would be the reason to have ColorModel() and ColorIndexAt(x, y int) in
separate interfaces ?

Wouldn't it simpler to add "ColorIndexAt(x, y) int" into image.Image, returning
zero for non-paletted images?


On 2011/08/29 04:35:08, nigeltao wrote:
> I would have your ZoomedImage function return an image.Image, whose
> concrete type also implements the image.PalettedImage interface (and
> Opaque would help, too). When zooming a non-paletted image, the
> ColorIndexAt and PalettedColorModel methods should return zeroes.
> png.Writer should switch on both m.ColorModel returning a
> PalettedColorModel and m implementing image.PalettedImage.
> 
> On second thoughts, I don't think that a PalettedColorModel method is
> necessary. But I would still have a PalettedImage interface with a
> ColorIndexAt method. The fact that adding this interface will require
> no changes to the image.Paletted type is a good sign.

[jp, 2011-08-30 06:07:24]

PTAL

On 2011/08/29 05:28:15, jp wrote:
> It results in almost every code which works with image.Image will check it for
> image.PalettedImage. 
> 
> Encoders - yes, decoders - yes, transformers - yes.
> The only exception I see is the code that displays images.
> 
> But we have ColorModel() in Image interface which displayers do not use as
well.
> All the code which use ColorModel() will check for image.PalettedImage and
then
> use ColorIndexAt().
> 
> I mean, if we have to split the interface {
> Bounds()
> At(x, y int)
> ColorModel()
> ColorIndexAt(x, y int)
> }
> into 'simple' (for displayers) and 'advanced' (for readers, writers and
> transformers), there will be Bounds() and At(x, y int) in the former and
> ColorModel() and ColorIndexAt(x, y int) in the latter 
> 
> What would be the reason to have ColorModel() and ColorIndexAt(x, y int) in
> separate interfaces ?
> 
> Wouldn't it simpler to add "ColorIndexAt(x, y) int" into image.Image,
returning
> zero for non-paletted images?
> 
> 
> On 2011/08/29 04:35:08, nigeltao wrote:
> > I would have your ZoomedImage function return an image.Image, whose
> > concrete type also implements the image.PalettedImage interface (and
> > Opaque would help, too). When zooming a non-paletted image, the
> > ColorIndexAt and PalettedColorModel methods should return zeroes.
> > png.Writer should switch on both m.ColorModel returning a
> > PalettedColorModel and m implementing image.PalettedImage.
> > 
> > On second thoughts, I don't think that a PalettedColorModel method is
> > necessary. But I would still have a PalettedImage interface with a
> > ColorIndexAt method. The fact that adding this interface will require
> > no changes to the image.Paletted type is a good sign.

[nigeltao, 2011-08-30 07:52:03]

http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/image.go
File src/pkg/image/image.go (right):

http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/image.go#newco...
src/pkg/image/image.go:27: // Image is PalettedImage iff its ColorModel() is
PalettedColorModel
It's not an "if and only if". A ZoomedImage can implement PalettedImage but a
ZoomedImage of an RGBA will not have a PalettedColorModel color model.

Instead, I would write:

// PalettedImage is an image whose colors may come from a limited palette.
// If m is a PalettedImage and m.ColorModel() returns a PalettedColorModel p,
// then m.At(x, y) should be equivalent to p[m.ColorIndexAt(x, y)]. If m's
// color model is not a PalettedColorModel, then ColorIndexAt's behavior is
// undefined.

and I would delete the "Invariant" line below.

http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/image.go#newco...
src/pkg/image/image.go:29: // At returns palette index of the pixel at (x, y).
s/At/ColorIndexAt/ and s/returns/returns the/.

http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/png/writer.go
File src/pkg/image/png/writer.go (right):

http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/png/writer.go#...
src/pkg/image/png/writer.go:442: pal, _ :=
m.ColorModel().(image.PalettedColorModel)
I'd prefer to require both m implementing image.PalettedImage and the ColorModel
being an image.PalettedColorModel. Thus:

var pal image.PalettedColorModel
if _, ok := m.(image.PalettedImage); ok {
  pal, _ = m.ColorModel().(image.PalettedColorModel)
}

[jp, 2011-08-30 20:47:38]

PTAL
On 2011/08/30 07:52:03, nigeltao wrote:
> http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/image.go
> File src/pkg/image/image.go (right):
> 
>
http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/image.go#newco...
> src/pkg/image/image.go:27: // Image is PalettedImage iff its ColorModel() is
> PalettedColorModel
> It's not an "if and only if". A ZoomedImage can implement PalettedImage but a
> ZoomedImage of an RGBA will not have a PalettedColorModel color model.
> 
> Instead, I would write:
> 
> // PalettedImage is an image whose colors may come from a limited palette.
> // If m is a PalettedImage and m.ColorModel() returns a PalettedColorModel p,
> // then m.At(x, y) should be equivalent to p[m.ColorIndexAt(x, y)]. If m's
> // color model is not a PalettedColorModel, then ColorIndexAt's behavior is
> // undefined.
> 
> and I would delete the "Invariant" line below.
> 
>
http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/image.go#newco...
> src/pkg/image/image.go:29: // At returns palette index of the pixel at (x, y).
> s/At/ColorIndexAt/ and s/returns/returns the/.
> 
> http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/png/writer.go
> File src/pkg/image/png/writer.go (right):
> 
>
http://codereview.appspot.com/4956046/diff/15001/src/pkg/image/png/writer.go#...
> src/pkg/image/png/writer.go:442: pal, _ :=
> m.ColorModel().(image.PalettedColorModel)
> I'd prefer to require both m implementing image.PalettedImage and the
ColorModel
> being an image.PalettedColorModel. Thus:
> 
> var pal image.PalettedColorModel
> if _, ok := m.(image.PalettedImage); ok {
>   pal, _ = m.ColorModel().(image.PalettedColorModel)
> }

[nigeltao, 2011-08-30 22:26:54]

On 31 August 2011 06:47,  <jp@webmaster.ms> wrote:
> PTAL

LGTM, thanks.

[nigeltao, 2011-08-30 22:27:09]

*** Submitted as http://code.google.com/p/go/source/detail?r=070b7cc84e48 ***

image: add PalettedImage interface, and make image/png recognize it.

R=golang-dev, rsc, bradfitz, nigeltao
CC=golang-dev
http://codereview.appspot.com/4956046

Committer: Nigel Tao <nigeltao@golang.org>