Welcome to Linux Knowledge Base and Tutorial
"The place where you learn linux"
The ONE Campaign to make poverty history

 Create an AccountHome | Submit News | Your Account  

Tutorial Menu
Linux Tutorial Home
Table of Contents

· Introduction to Operating Systems
· Linux Basics
· Working with the System
· Shells and Utilities
· Editing Files
· Basic Administration
· The Operating System
· The X Windowing System
· The Computer Itself
· Networking
· System Monitoring
· Solving Problems
· Security
· Installing and Upgrading
· Linux and Windows

Man Pages
Linux Topics
Test Your Knowledge

Site Menu
Site Map
Copyright Info
Terms of Use
Privacy Info
Masthead / Impressum
Your Account

Private Messages

News Archive
Submit News
User Articles
Web Links


The Web

Who's Online
There are currently, 152 guest(s) and 0 member(s) that are online.

You are an Anonymous user. You can register for free by clicking here




       #include <magick.h>


       This document describes how ImageMagick 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.

       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, pi,
       is defined by an ordered triple of red, green, and blue
       coordinates, (ri, gi, bi).

       Each primary color component (red, green, or blue) repre­
       sents an intensity which varies linearly from 0 to a maxi­
       mum 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).  ImageMagick requires
       cmax = 255.

       The algorithm maps this domain onto a tree in which each
       node represents a cube within that domain.  In the follow­
       ing 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.

       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.

       The basic algorithm operates in three phases:  Classifica­
       tion, Reduction, and Assignment.  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 origi­
       nal colors and quantized colors.  To learn more about
       quantization error, see MEASURING COLOR REDUCTION ERROR
       later in this document.

       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
       colors in the output image (currently log4(colormap
       size)+2).  A tree of this depth generally allows the best
       representation of the source image with the fastest compu­
       tational 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.

       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:

       n1:    Number of pixels whose color is contained in the
              RGB cube which this node represents;

       n2:    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.

       Sr, Sg, Sb:
              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 ulti­
              mately characterize the mean color of a set of pix­
              els represented by this node.

       E:     The distance squared in RGB space between each
              pixel contained within a node and the nodes' cen­
              ter.  This represents the quantization error for a

       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:

         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

       This has the effect of minimizing any quantization error
       when merging two nodes together.

       When a node to be pruned has offspring, the pruning proce­
       dure invokes itself recursively in order to prune the tree
       This includes n1 - n2 pixels whose colors should be
       defined by nodes at a lower level in the tree.

       Assignment generates the output image from the pruned
       tree.  The output image consists of two parts:  (1)  A
       color map, which is an array of color descriptions (RGB
       triples) for each color present in the output image; (2)
       A pixel array, which represents each pixel as an index
       into the color map array.

       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 clas­
       sify no lower than this node.  Each of these colors
       becomes an entry in the color map.

       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

       Empirical evidence suggests that distances in color spaces
       such as YUV, or YIQ correspond to perceptual color differ­
       ences 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 conve­
       nience, the color components are normalized to the range 0
       to a maximum value, cmax.  The color reduction can then
       proceed as described.


       Depending on the image, the color reduction error may be
       obvious or invisible.  Images with high spatial frequen­
       cies (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.

       To measure the difference between the original and color
       reduced images (the total color reduction error),
       ImageMagick sums over all pixels in an image the distance
       squared in RGB space between each original pixel value and
       its color reduced value. ImageMagick prints several error
       measurements including the mean error per pixel, the nor­
       malized mean error, and the normalized maximum error.

       The normalized error measurement can be used to compare
       images.  In general, the closer the mean error is to zero

              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.

       normalized maximum square error:
              is the largest normalized 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.


       display(1), animate(1), mogrify(1), import(1), miff(5)


       Copyright (C) 2003 ImageMagick Studio, a non-profit orga­
       nization dedicated to making software imaging solutions
       freely available.

       Permission is hereby granted, free of charge, to any per­
       son obtaining a copy of this software and associated docu­
       mentation files ("ImageMagick"), to deal in ImageMagick
       without restriction, including without limitation the
       rights to use, copy, modify, merge, publish, distribute,
       sublicense, and/or sell copies of ImageMagick, and to per­
       mit persons to whom the ImageMagick is furnished to do so,
       subject to the following conditions:

       The above copyright notice and this permission notice
       shall be included in all copies or substantial portions of

       The software is provided "as is", without warranty of any
       kind, express or implied, including but not limited to the
       warranties of merchantability, fitness for a particular
       purpose and noninfringement.  In no event shall ImageMag­
       ick Studio be liable for any claim, damages or other lia­
       bility, whether in an action of contract, tort or other­
       wise, arising from, out of or in connection with ImageMag­
       ick or the use or other dealings in ImageMagick.

       Except as contained in this notice, the name of the
       ImageMagick Studio shall not be used in advertising or
       otherwise to promote the sale, use or other dealings in
       ImageMagick without prior written authorization from the
       ImageMagick Studio.


       Paul Raveling, USC Information Sciences Institute, for the
       original idea of using space subdivision for the color



Security Code
Security Code
Type Security Code

Don't have an account yet? You can create one. As a registered user you have some advantages like theme manager, comments configuration and post comments with your name.

Help if you can!

Amazon Wish List

Did You Know?
You can get all the latest Site and Linux news by checking out our news page.


Tell a Friend About Us

Bookmark and Share

Web site powered by PHP-Nuke

Is this information useful? At the very least you can help by spreading the word to your favorite newsgroups, mailing lists and forums.
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters. Articles are the property of their respective owners. Unless otherwise stated in the body of the article, article content (C) 1994-2013 by James Mohr. All rights reserved. The stylized page/paper, as well as the terms "The Linux Tutorial", "The Linux Server Tutorial", "The Linux Knowledge Base and Tutorial" and "The place where you learn Linux" are service marks of James Mohr. All rights reserved.
The Linux Knowledge Base and Tutorial may contain links to sites on the Internet, which are owned and operated by third parties. The Linux Tutorial is not responsible for the content of any such third-party site. By viewing/utilizing this web site, you have agreed to our disclaimer, terms of use and privacy policy. Use of automated download software ("harvesters") such as wget, httrack, etc. causes the site to quickly exceed its bandwidth limitation and are therefore expressly prohibited. For more details on this, take a look here

PHP-Nuke Copyright © 2004 by Francisco Burzi. This is free software, and you may redistribute it under the GPL. PHP-Nuke comes with absolutely no warranty, for details, see the license.
Page Generation: 0.09 Seconds