Left: | ||
Right: |
OLD | NEW |
---|---|
(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 } | |
OLD | NEW |