1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
|
<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.13.1: http://docutils.sourceforge.net/" />
<title>GraphicsMagick Color Quantization</title>
<link rel="stylesheet" href="docutils-articles.css" type="text/css" />
</head>
<body>
<div class="banner">
<img src="images/gm-107x76.png" alt="GraphicMagick logo" width="107" height="76" />
<span class="title">GraphicsMagick</span>
<form action="http://www.google.com/search">
<input type="hidden" name="domains" value="www.graphicsmagick.org" />
<input type="hidden" name="sitesearch" value="www.graphicsmagick.org" />
<span class="nowrap"><input type="text" name="q" size="25" maxlength="255" /> <input type="submit" name="sa" value="Search" /></span>
</form>
</div>
<div class="navmenu">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="project.html">Project</a></li>
<li><a href="download.html">Download</a></li>
<li><a href="README.html">Install</a></li>
<li><a href="Hg.html">Source</a></li>
<li><a href="NEWS.html">News</a> </li>
<li><a href="utilities.html">Utilities</a></li>
<li><a href="programming.html">Programming</a></li>
<li><a href="reference.html">Reference</a></li>
</ul>
</div>
<div class="document" id="graphicsmagick-color-quantization">
<h1 class="title">GraphicsMagick Color Quantization</h1>
<!-- -*- mode: rst -*- -->
<!-- This text is in reStucturedText format, so it may look a bit odd. -->
<!-- See http://docutils.sourceforge.net/rst.html for details. -->
<blockquote>
This document describes how GraphicsMagick performs color
reduction on an image. To fully understand this document,
you should have a knowledge of basic imaging techniques and
the tree data structure and terminology.</blockquote>
<div class="section" id="description">
<h1>Description</h1>
<p>For purposes of color allocation, an image is a set of n pixels, where
each pixel is a point in RGB space. RGB space is a 3-dimensional vector
space, and each pixel, p(i), is defined by an ordered triple of red,
green, and blue coordinates, (r(i),g(i),b(i)).</p>
<p>Each primary color component (red, green, or blue) represents an
intensity which varies linearly from 0 to a maximum value, Cmax, which
corresponds to full saturation of that color. Color allocation is defined
over a domain consisting of the cube in RGB space with opposite vertices
at (0,0,0) and (Cmax ,Cmax,Cmax). GraphicsMagick requires Cmax= 255.</p>
<p>The algorithm maps this domain onto a tree in which each node represents
a cube within that domain. In the following discussion, these cubes are
defined by the coordinate of two opposite vertices: The vertex nearest
the origin in RGB space and the vertex farthest from the origin.</p>
<p>The tree's root node represents the the entire domain, (0,0,0) through
(Cmax, Cmax,Cmax). Each lower level in the tree is generated by
subdividing one node's cube into eight smaller cubes of equal size. This
corresponds to bisecting the parent cube with planes passing through the
midpoints of each edge.</p>
<p>The basic algorithm operates in three phases:</p>
<blockquote>
<ul class="simple">
<li>Classification,</li>
<li>Reduction, and</li>
<li>Assignment.</li>
</ul>
</blockquote>
<p>Classification builds a color description tree for the image. Reduction
collapses the tree until the number it represents, at most, is the number
of colors desired in the output image. Assignment defines the output
image's color map and sets each pixel's color by reclassification in the
reduced tree. Our goal is to minimize the numerical discrepancies between
the original colors and quantized colors. To learn more about
quantization error, see Measuring Color Reduction Error later in this
document.</p>
<p>Classification begins by initializing a color description tree of
sufficient depth to represent each possible input color in a leaf.
However, it is impractical to generate a fully-formed color description
tree in the classification phase for realistic values of Cmax. If color
components in the input image are quantized to k-bit precision, so that
Cmax = 2^k-1, the tree would need k levels below the root node to allow
representing each possible input color in a leaf. This becomes
prohibitive because the tree's:</p>
<pre class="literal-block">
total number of nodes = 1+Sum(8^i), i=1,k
For k=8,
Number of nodes= 1 + (8^1+8^2+....+8^8)
8^8 - 1
= 1 + 8.-----------
8 - 1
= 19,173,961
</pre>
<p>Therefore, to avoid building a fully populated tree, GraphicsMagick:</p>
<ol class="arabic simple">
<li>Initializes data structures for nodes only as they are needed;</li>
<li>Chooses a maximum depth for the tree as a function of the desired
number of colors in the output image (currently based-two logarithm
of Cmax).</li>
</ol>
<p>For Cmax=255,</p>
<pre class="literal-block">
Maximum tree depth = log (256)
2
= log (256) / log (2)
e e
= 8
</pre>
<p>A tree of this depth generally allows the best representation of the
source image with the fastest computational speed and the least amount of
memory. However, the default depth is inappropriate for some images.
Therefore, the caller can request a specific tree depth.</p>
<p>For each pixel in the input image, classification scans downward from the
root of the color description tree. At each level of the tree, it
identifies the single node which represents a cube in RGB space
containing the pixel's color. It updates the following data for each such
node:</p>
<blockquote>
<dl class="docutils">
<dt>n1:</dt>
<dd>Number of pixels whose color is contained in the RGB cube which
this node represents;</dd>
<dt>n2:</dt>
<dd>Number of pixels whose color is not represented in a node at lower
depth in the tree; initially, n2=0 for all nodes except leaves of
the tree.</dd>
<dt>Sr,Sg,Sb:</dt>
<dd>Sums of the red, green, and blue component values for all pixels
not classified at a lower depth. The combination of these sums and
n2 will ultimately characterize the mean color of a set of pixels
represented by this node.</dd>
<dt>E:</dt>
<dd>The distance squared in RGB space between each pixel contained
within a node and the nodes' center. This represents the
quantization error for a node.</dd>
</dl>
</blockquote>
<p>Reduction repeatedly prunes the tree until the number of nodes with n2 >
0 is less than or equal to the maximum number of colors allowed in the
output image. On any given iteration over the tree, it selects those
nodes whose E value is minimal for pruning and merges their color
statistics upward. It uses a pruning threshold, Ep, to govern node
selection as follows:</p>
<pre class="literal-block">
Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
prune all nodes such that E <= Ep
Set Ep to minimum E in remaining nodes
</pre>
<p>This has the effect of minimizing any quantization error when merging two
nodes together.</p>
<p>When a node to be pruned has offspring, the pruning procedure invokes
itself recursively in order to prune the tree from the leaves upward. The
values of n2 ,Sr, Sg and Sb in a node being pruned are always added to
the corresponding data in that node's parent. This retains the pruned
node's color characteristics for later averaging.</p>
<p>For each node, n2 pixels exist for which that node represents the
smallest volume in RGB space containing those pixel's colors. When n2 > 0
the node will uniquely define a color in the output image. At the
beginning of reduction, n2 = 0 for all nodes except the leaves of the
tree which represent colors present in the input image.</p>
<p>The other pixel count, n1, indicates the total number of colors within
the cubic volume which the node represents. This includes n1 - n2 pixels
whose colors should be defined by nodes at a lower level in the tree.</p>
<p>Assignment generates the output image from the pruned tree. The output
image consists of two parts:</p>
<ol class="arabic simple">
<li>A color map, which is an array of color descriptions (RGB triples)
for each color present in the output image.</li>
<li>A pixel array, which represents each pixel as an index into the
color map array.</li>
</ol>
<p>First, the assignment phase makes one pass over the pruned color
description tree to establish the image's color map. For each node with
n2 > 0, it divides Sr, Sg, and Sb by n2. This produces the mean color of
all pixels that classify no lower than this node. Each of these colors
becomes an entry in the color map.</p>
<p>Finally, the assignment phase reclassifies each pixel in the pruned tree
to identify the deepest node containing the pixel's color. The pixel's
value in the pixel array becomes the index of this node's mean color in
the color map.</p>
<p>Empirical evidence suggests that the distances in color spaces such as
YUV, or YIQ correspond to perceptual color differences more closely than
do distances in RGB space. These color spaces may give better results
when color reducing an image. Here the algorithm is as described except
each pixel is a point in the alternate color space. For convenience, the
color components are normalized to the range 0 to a maximum value, Cmax.
The color reduction can then proceed as described.</p>
</div>
<div class="section" id="measuring-color-reduction-error">
<h1>Measuring Color Reduction Error</h1>
<p>Depending on the image, the color reduction error may be obvious or
invisible. Images with high spatial frequencies (such as hair or grass)
will show error much less than pictures with large smoothly shaded areas
(such as faces). This is because the high-frequency contour edges
introduced by the color reduction process are masked by the high
frequencies in the image.</p>
<p>To measure the difference between the original and color reduced images
(the total color reduction error), GraphicsMagick sums over all pixels in
an image the distance squared in RGB space between each original pixel
value and its color reduced value. GraphicsMagick prints several error
measurements including the mean error per pixel, the normalized mean
error, and the normalized maximum error.</p>
<p>The normalized error measurement can be used to compare images. In
general, the closer the mean error is to zero the more the quantized
image resembles the source image. Ideally, the error should be
perceptually-based, since the human eye is the final judge of
quantization quality.</p>
<p>These errors are measured and printed when -verbose and -colorsare
specified on the command line:</p>
<blockquote>
<dl class="docutils">
<dt>mean error per pixel:</dt>
<dd>is the mean error for any single pixel in the image.</dd>
<dt>normalized mean square error:</dt>
<dd>is the normalized mean square quantization error for any single
pixel in the image.
This distance measure is normalized to a range between 0 and 1. It
is independent of the range of red, green, and blue values in the
image.</dd>
<dt>normalized maximum square error:</dt>
<dd>is the largest normalized square quantization error for any single
pixel in the image.
This distance measure is normalized to a range between and blue
values in the image.</dd>
</dl>
</blockquote>
</div>
<div class="section" id="authors">
<h1>Authors</h1>
<p>John Cristy, <a class="reference external" href="mailto:magick%40imagemagick.org">magick<span>@</span>imagemagick<span>.</span>org</a>, ImageMagick Studio.</p>
</div>
<div class="section" id="acknowledgements">
<h1>Acknowledgements</h1>
<p>Paul Raveling, USC Information Sciences Institute, for the original idea
of using space subdivision for the color reduction algorithm. With Paul's
permission, this document is an adaptation from a document he wrote.</p>
<hr class="docutils" />
<p>Copyright © GraphicsMagick Group 2002 - 2020</p>
</div>
</div>
</body>
</html>
|
