Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(622)

Side by Side Diff: src/pkg/image/gif/mediancut.go

Issue 10896043: image/gif: add writer implementation (Closed)
Patch Set: diff -r 09e39a9ce38e https://code.google.com/p/go Created 10 years, 9 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1 // Copyright 2013 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package gif
6
7 import (
8 "container/heap"
9 "image"
10 "image/color"
11 "sort"
12 )
13
14 const (
15 numDimensions = 3
16 )
17
18 func min(x, y uint32) uint32 {
19 if x < y {
20 return x
21 }
22 return y
23 }
24
25 func max(x, y uint32) uint32 {
26 if x > y {
27 return x
28 }
29 return y
30 }
31
32 type point struct {
nigeltao 2013/07/03 03:27:25 Or just type point [numDimensions]uint32 Also, i
Andrew Bonventre 2013/07/03 17:19:35 Done.
33 x [numDimensions]uint32
34 }
35
36 type block struct {
37 minCorner, maxCorner point
38 points []point
39 // The index is needed by update and is maintained by the heap.Interface methods.
40 index int // The index of the item in the heap.
41 }
42
43 func newBlock(p []point) *block {
44 b := &block{points: p}
nigeltao 2013/07/03 03:27:25 return &block{ minCorner: point{0x00, 0x00, 0x00
Andrew Bonventre 2013/07/03 17:19:35 Done.
45 for i := 0; i < numDimensions; i++ {
46 b.minCorner.x[i] = 0
47 b.maxCorner.x[i] = 0xFF
48 }
49 return b
50 }
51
52 func (b *block) longestSideIndex() int {
53 m := b.maxCorner.x[0] - b.minCorner.x[0]
54 maxIndex := 0
55 for i := 1; i < numDimensions; i++ {
56 diff := b.maxCorner.x[i] - b.minCorner.x[i]
57 if diff > m {
58 m = diff
59 maxIndex = i
60 }
61 }
62 return maxIndex
63 }
64
65 func (b *block) longestSideLength() uint32 {
66 i := b.longestSideIndex()
67 return b.maxCorner.x[i] - b.minCorner.x[i]
68 }
69
70 func (b *block) shrink() {
71 for j := 0; j < numDimensions; j++ {
72 b.minCorner.x[j] = b.points[0].x[j]
73 b.maxCorner.x[j] = b.points[0].x[j]
74 }
75 for i := 1; i < len(b.points); i++ {
76 for j := 0; j < numDimensions; j++ {
77 b.minCorner.x[j] = min(b.minCorner.x[j], b.points[i].x[j ])
78 b.maxCorner.x[j] = max(b.maxCorner.x[j], b.points[i].x[j ])
79 }
80 }
81 }
82
83 type By func(p1, p2 *point) bool
nigeltao 2013/07/03 03:27:25 Why is this type exported?
Andrew Bonventre 2013/07/03 17:19:35 Apologies. Lost track of what should be exported t
84
85 func (by By) Sort(points []point) {
nigeltao 2013/07/03 03:27:25 Why is this method exported? We usually don't expo
Andrew Bonventre 2013/07/03 17:19:35 Brain fart syndrome?
86 ps := &pointSorter{
nigeltao 2013/07/03 03:27:25 You can inline this into the next line: sort.Sort
Andrew Bonventre 2013/07/03 17:19:35 Done.
87 points: points,
88 by: by,
89 }
90 sort.Sort(ps)
91 }
92
93 type pointSorter struct {
94 points []point
95 by func(p1, p2 *point) bool
96 }
97
98 func (ps *pointSorter) Len() int {
nigeltao 2013/07/03 03:27:25 I'd change ps to just s.
Andrew Bonventre 2013/07/03 17:19:35 Done.
99 return len(ps.points)
100 }
101
102 func (ps *pointSorter) Swap(i, j int) {
103 ps.points[i], ps.points[j] = ps.points[j], ps.points[i]
104 }
105
106 func (ps *pointSorter) Less(i, j int) bool {
107 return ps.by(&ps.points[i], &ps.points[j])
108 }
109
110 // A PriorityQueue implements heap.Interface and holds blocks.
111 type PriorityQueue []*block
nigeltao 2013/07/03 03:27:25 Why is this type exported?
Andrew Bonventre 2013/07/03 17:19:35 Done.
112
113 func (pq PriorityQueue) Len() int { return len(pq) }
114
115 func (pq PriorityQueue) Less(i, j int) bool {
116 return pq[i].longestSideLength() > pq[j].longestSideLength()
117 }
118
119 func (pq PriorityQueue) Swap(i, j int) {
120 pq[i], pq[j] = pq[j], pq[i]
121 pq[i].index = i
122 pq[j].index = j
123 }
124
125 func (pq *PriorityQueue) Push(x interface{}) {
126 n := len(*pq)
127 item := x.(*block)
128 item.index = n
129 *pq = append(*pq, item)
130 }
131
132 func (pq *PriorityQueue) Pop() interface{} {
133 old := *pq
134 n := len(old)
135 item := old[n-1]
136 item.index = -1 // for safety
137 *pq = old[0 : n-1]
nigeltao 2013/07/03 03:27:25 Drop the 0.
Andrew Bonventre 2013/07/03 17:19:35 Done.
138 return item
139 }
140
141 func (pq *PriorityQueue) Top() interface{} {
142 n := len(*pq)
143 if n == 0 {
144 return nil
145 }
146 return (*pq)[n-1]
147 }
148
149 type Quantizer interface {
nigeltao 2013/07/03 03:27:25 This needs documentation comments. I'd also move
Andrew Bonventre 2013/07/03 17:19:35 Done.
150 Quantize(m image.Image) (*image.Paletted, error)
nigeltao 2013/07/03 03:27:25 Was this the API that we agreed on??
Andrew Bonventre 2013/07/03 17:19:35 Nope. I should have gotten clarification earlier o
nigeltao 2013/07/03 23:48:04 They have the same meaning as the image/draw packa
Andrew Bonventre 2013/07/04 04:31:31 Done.
151 }
152
153 type MedianCutQuantizer struct {
nigeltao 2013/07/03 03:27:25 This needs documentation comments.
Andrew Bonventre 2013/07/03 17:19:35 Done.
154 NumColor int
155 }
156
157 func (q *MedianCutQuantizer) medianCut(points []point) color.Palette {
158 if q.NumColor == 0 {
159 return color.Palette{}
160 }
161
162 initialBlock := newBlock(points)
163 initialBlock.shrink()
164 pq := &PriorityQueue{}
165 heap.Init(pq)
166 heap.Push(pq, initialBlock)
167
168 for pq.Len() < q.NumColor && len(pq.Top().(*block).points) > 1 {
169 longestBlock := heap.Pop(pq).(*block)
170 points := longestBlock.points
171
172 // TODO: Instead of sorting the entire slice, finding the median using an
173 // algorithm like introselect would give much better performance .
174 func(li int) {
175 By(func(p1, p2 *point) bool { return p1.x[li] < p2.x[li] }).Sort(points)
176 }(longestBlock.longestSideIndex())
177 median := len(points) / 2
178 block1 := newBlock(points[0:median])
nigeltao 2013/07/03 03:27:25 Drop the 0.
Andrew Bonventre 2013/07/03 17:19:35 Done.
179 block2 := newBlock(points[median:])
180 block1.shrink()
181 block2.shrink()
182 heap.Push(pq, block1)
183 heap.Push(pq, block2)
184 }
185
186 palette := make(color.Palette, q.NumColor)
187 var n int
188 for n = 0; pq.Len() > 0; n++ {
189 block := heap.Pop(pq).(*block)
190 sum := make([]uint32, numDimensions)
nigeltao 2013/07/03 03:27:25 numDimensions is constant, use a (stack-allocated)
Andrew Bonventre 2013/07/03 17:19:35 Done.
191 for i := 0; i < len(block.points); i++ {
192 for j := 0; j < numDimensions; j++ {
193 sum[j] += block.points[i].x[j]
194 }
195 }
196 var avgPoint point
197 for j := 0; j < numDimensions; j++ {
198 avgPoint.x[j] = sum[j] / uint32(len(block.points))
199 }
200 palette[n] = color.RGBA64{
201 R: uint16(avgPoint.x[0]),
nigeltao 2013/07/03 03:27:25 I wouldn't bother with an avgPoint variable, and j
Andrew Bonventre 2013/07/03 17:19:35 Done.
202 G: uint16(avgPoint.x[1]),
203 B: uint16(avgPoint.x[2]),
204 A: 0xFFFF,
205 }
206 }
207 // Trim to only the colors present in the image, which
208 // could be less than NumColor.
209 return palette[:n]
210 }
211
212 func (q *MedianCutQuantizer) Quantize(m image.Image) (*image.Paletted, error) {
213 bounds := m.Bounds()
214 points := make([]point, bounds.Dx()*bounds.Dy())
215 colorSet := make(map[color.Color]bool, q.NumColor)
nigeltao 2013/07/03 03:27:25 The color.Color implementation could be a func, wh
Andrew Bonventre 2013/07/03 17:19:35 Done.
216 i := 0
217 for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
218 for x := bounds.Min.X; x < bounds.Max.X; x++ {
219 c := m.At(x, y)
220 r, g, b, _ := c.RGBA()
221 colorSet[c] = true
222 points[i].x[0] = r
223 points[i].x[1] = g
224 points[i].x[2] = b
225 i++
226 }
227 }
228 var palette color.Palette
229 if len(colorSet) <= q.NumColor {
230 // No need to quantize since the total number of colors
231 // fits within the palette.
232 palette = make(color.Palette, len(colorSet))
233 i := 0
234 for c, _ := range colorSet {
235 palette[i] = c
236 i++
237 }
238 } else {
239 palette = q.medianCut(points)
240 }
241
242 pm := image.NewPaletted(m.Bounds(), palette)
nigeltao 2013/07/03 03:27:25 m.Bounds() could be just bounds.
Andrew Bonventre 2013/07/03 17:19:35 Done.
243 pm.Stride = m.Bounds().Dx()
nigeltao 2013/07/03 03:27:25 Huh?
Andrew Bonventre 2013/07/03 17:19:35 Since each pixel within a palette is represented b
nigeltao 2013/07/03 23:48:04 image.NewPaletted already sets the stride to the c
Andrew Bonventre 2013/07/04 04:31:31 Done.
244 for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
245 for x := bounds.Min.X; x < bounds.Max.X; x++ {
246 pm.Set(x, y, m.At(x, y))
nigeltao 2013/07/03 03:27:25 Add a TODO to do this more efficiently.
Andrew Bonventre 2013/07/03 17:19:35 Done.
247 }
248 }
249
250 return pm, nil
251 }
OLDNEW

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b