Next to text, digital images are the most common element found on the internet. However, the internet would feel much slower if every advertisement-sized image required 196,560 bytes of memory. Instead, a banner ad image requires only 14,246 bytes, just 7.2% of what it could take. Where do these numbers come from? How is such a phenomenal savings achieved? The answers to these questions are the topic of this section.
Subsection8.5.1A Quick Review of Digital Images
A digital image is composed of thousands of individual components called pixels. The pixels are arranged as a rectangle that forms the image. Each pixel in an image represents a particular color in the image. On a computer, the color of each pixel is determined by a mixture of three primary colors: red, green, and blue. A simple example of how pixels are arranged to form a picture is shown in Figure 8.5.1.
Figure8.5.1.A Simple Image Composed of Pixels
In the physical world colors are not discrete quantities. The colors in our physical world have an infinite amount of variation to them. Just as computers must approximate floating point numbers, they also must approximate the colors in an image. The human eye can distinguish between 200 different levels in each of the three primary colors, or a total of about 8 million individual colors. In practice we use one byte (8 bits) of memory for each color component of a pixel. Eight bits gives us 256 different levels for each of the red, green, and blue components, for a total of 16.7 million different possible colors for each pixel. While the huge number of colors allows artists and graphic designers to create wonderfully detailed images, the downside of all of these color possibilities is that image size grows very rapidly. For example, a single image from a one-megapixel camera would take 3 megabytes of memory.
In Python we might represent an image using a list of a list of tuples, where the tuples consist of three numbers between 0 and 255, one for each of the red, green, and blue components. In other languages, such as C++ and Java, an image could be represented as a two-dimensional array. The list of lists representation of the first two rows of the image in Figure 8.5.1 is shown below:
im = [[(255,255,255),(255,255,255),(255,255,255),(12,28,255),
(12,28,255),(255,255,255),(255,255,255),(255,255,255),],
[(255,255,255),(255,255,255),(12,28,255),(255,255,255),
(255,255,255),(12,28,255),(255,255,255),(255,255,255)],
... ]
The color white is represented by the tuple \((255, 255, 255)\text{.}\) A bluish color is represented by the tuple \((12, 28, 255)\text{.}\) You can obtain the color value for any pixel in the image by simply using list indices, for example:
>>> im[3][2]
(255, 18, 39)
With this representation for an image in mind, you can imagine that it would be easy to store an image to a file just by writing a tuple for each pixel. You might start by writing the number of rows and columns in the image and then by writing three integer values per line. In practice, the Python package Pillow provides us with some powerful classes. Using the Image class we can get and set pixels using getpixel((col, row)) and putpixel((col, row), color). Note that the parameters for the image methods are in the traditional \(x, y\) order but many people forget and think in terms of row, column order.
Subsection8.5.2Quantizing an Image
There are many ways of reducing the storage requirements for an image. One of the easiest ways is to use fewer colors. Fewer color choices means fewer bits for each red, green, and blue component, which means reduced memory requirements. In fact, one of the most popular image formats used for images on the World Wide Web uses only 256 colors for an image. Using 256 colors reduces the storage requirements from three bytes per pixel to one byte per pixel.
Right now you are probably asking yourself how to take an image that may have as many as 16 million colors and reduce it to just 256? The answer is a process called quantization. To understand the process of quantization, let’s think about colors as a three-dimensional space. Each color can be represented by a point in space where the red component is the x axis, the green component is the y axis, and the blue component is the z axis. We can think of the space of all possible colors as a \(256 \times 256 \times 256\) cube. The colors closest to the vertex at \((0, 0, 0)\) are going to be black and dark color shades. The colors closest to the vertex at \((255, 255, 255)\) are bright and close to white. The colors closest to \((255, 0, 0)\) are red and so forth.
The simplest way to think about quantizing an image is to imagine taking the \(256 \times 256 \times 256\) cube and turning it into an \(8 \times 8 \times 8\) cube. The overall size of the cube stays the same, but now many colors in the old cube are represented by a single color in the new cube. Figure 8.5.2 shows an example of the quantization just described.
Figure8.5.2.Color Quantization
We can turn this simple idea of color quantization into the Java program shown in Listing 8.5.3. The simpleQuuant algorithm works by mapping the color components for each pixel represented by its full 256 bits to the color at the center of the cube in its area. This is easy to do using integer division in Java. In the simpleQuant algorithm there are seven distinct values in the red dimension and six distinct values in the green and blue dimensions.
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.WindowConstants;
import java.util.Scanner;
public class SimpleQuantize {
public static void simpleQuant(BufferedImage img) {
int w = img.getWidth();
int h = img.getHeight();
for (int row = 0; row < h; row++) {
for (int col = 0; col < w; col++) {
int argb = img.getRGB(col,row);
int r = (argb >> 16) & 0xff;
int g = (argb >> 8) & 0xff;
int b = argb & 0xff;
r = r / 36 * 36;
g = g / 42 * 42;
b = b / 42 * 42;
img.setRGB(col, row, (r << 16 | g << 8 | b));
}
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String filename = "";
do {
System.out.print("File name: ");
filename = input.nextLine();
if (!filename.equals("")) {
JFrame f = new JFrame("Simple Quantize");
f.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
ImageComponent img = new ImageComponent(filename);
simpleQuant(img.getImage());
f.add(img);
f.pack();
f.setVisible(true);
}
} while (!filename.equals(""));
}
}
Listing8.5.3.Simple Quantization
Lines 14–17 use bit manipulation to extract the red, green, and blue values. The >> operator is the right shift operation. The & is bitwise and, and | is bitwise or. The bitwise or and bitwise and operations work just like the logical operations used in conditionals, except that they work on the individual bits of a number. The shift operation moves the bits \(n\) places to the right, filling in with zeros on the left and dropping the bits as they go off the right.
In line 21, << shifts the revised values left. This fills in with zeros on the right an drops bits as they move go off the left. The bitwise or operator | puts the new color value back together.
The main method prompts you for file names until you press ENTER without giving a file name. Line 36 creates a new ImageComponent, given a file name. This is a class we have also written. It is listed in Listing 8.5.4 for your reference:
import java.awt.Graphics;
import java.awt.Dimension;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import javax.swing.JComponent;
class ImageComponent extends JComponent {
BufferedImage image;
public ImageComponent(String filename) {
try {
this.image = ImageIO.read(new File(filename));
} catch (IOException e) {
System.out.println("Unable to open file.");
this.image = new BufferedImage(400, 100,
BufferedImage.TYPE_INT_ARGB);
}
}
public void paint(Graphics g) {
g.drawImage(image, 0, 0, null);
}
public Dimension getPreferredSize() {
if (image == null) {
return new Dimension(100,100);
} else {
return new Dimension(image.getWidth(null),
image.getHeight(null));
}
}
public BufferedImage getImage() {
return this.image;
}
}
Listing8.5.4.The ImageComponent Class
After numerous import statements, the constructor reads the file into a BufferedImage object. If the file cannot be read, we create a 400 by 100 empty image (lines 12–20). Lines 22–33 provide methods that the Java graphics system will call when it needs to display the component and find how large it is.
Figure 8.5.5 shows a before and after comparison of original and quantized images of a crystal. You can use any JPEG color image from your collection and run the program to see the differences. Notice how much detail is lost in the quantized picture.
Figure8.5.5.Comparison of Original and Quantized Image
Subsection8.5.3An Improved Quantization Algorithm Using Octrees
The problem with the simple method of quantization just described is that the colors in most pictures are not evenly distributed throughout the color cube. Many colors may not appear in the image, so parts of the cube may go completely unused. Allocating an unused color to the quantized image is a waste. Figure 8.5.6 shows the distribution of the colors that are used in the example image. Notice how little of the color cube space is actually used.
Figure8.5.6.Plot of Colors Used in Image as Points in Color Cube
To make a better quantized image we need to find a way to do a better job of selecting the set of colors we want to use to represent our image. There are several algorithms for dividing the color cube in different ways to allow for the better use of colors. In this section we are going to look at a tree-based solution. The tree solution we will use makes use of an octree. An octree is similar to a binary tree; however, each node in an octree has eight children. Here is the interface we will implement for our octree abstract data type:
Octree() creates a new empty octree.
insert(r, g, b) adds a new node to the octree using the red, green, and blue color values as the key.
find(r, g, b) finds an existing node, or the closest approximation, using the red, green, and blue color values as the search key.
reduce(n) reduces the size of the octree so that there are \(n\) or fewer leaf nodes.
Here is how an octree is used to divide the color cube:
The root of the octree represents the entire cube.
The second level of the octree represents a single slice through each dimension (\(x\text{,}\)\(y\text{,}\) and \(z\)) that evenly divides the cube into eight pieces.
The next level of the tree divides each of the eight sub-cubes into eight additional cubes for a total of 64 cubes. Notice that the cube represented by the parent node totally contains all of the sub-cubes represented by the children. As we follow any path down the tree we are staying within the boundary of the parent, but getting progressively more specific about the portion of the cube.
The eighth level of the tree represents the full resolution of 16.7 million colors in our color cube.
Now that you know how we can represent the color cube using an octree, you may be thinking that the octree is just another way to divide up the color cube into even parts. You are correct. However, because the octree is hierarchical, we can take advantage of the hierarchy to use larger cubes to represent unused portions of the color cube and smaller cubes to represent the popular colors. Here is an overview of how we will use an octree to do a better job of selecting a subset of the colors in an image:
For each pixel in the image:
Search for the color of this pixel in the octree. The color will be a leaf node at the eighth level.
If the color is not found create a new leaf node at the eighth level (and possibly some internal nodes above the leaf).
If the color is already present in the tree increment the counter in the leaf node to keep track of how many pixels are this color.
Repeat until the number of leaf nodes is less than or equal to the target number of colors.
Find the deepest leaf node with the smallest number of uses.
Merge the leaf node and all of its siblings together to form a new leaf node.
The remaining leaf nodes form the color set for this image.
To map an original color to its quantized value, search down the tree until you get to a leaf node. Return the color values stored in the leaf.
The ideas outlined above are encoded as a Java method to quantize an image octreeQuant() in Listing 8.5.7.
public static void octreeQuant(BufferedImage img) {
int w = img.getWidth();
int h = img.getHeight();
Octree ot = new Octree();
for (int row = 0; row < h; row++) {
for (int col = 0; col < w; col++) {
int argb = img.getRGB(col,row);
int r = (argb >> 16) & 0xff;
int g = (argb >> 8) & 0xff;
int b = argb & 0xff;
ot.insert(r, g, b);
}
}
ot.reduce(256);
for (int row = 0; row < h; row++) {
for (int col = 0; col < w; col++) {
int argb = img.getRGB(col,row);
int r = (argb >> 16) & 0xff;
int g = (argb >> 8) & 0xff;
int b = argb & 0xff;
int[] newRgb = ot.find(r, g, b);
img.setRGB(col, row, (newRgb[0] << 16 |
newRgb[1] << 8 | newRgb[2]));
}
}
}
Listing8.5.7.Octree Quantizing
The octreeQuant method implements the basic process just described. First, the loops in lines 6–14 Listing 8.5.7 read each pixel and add it to the octree. Second, the number of leaf nodes is reduced by the reduce method on line 16. Finally, the image is updated by searching for a color, using find, in the reduced octree on line 25.
Let us now turn our attention to the definition of the Octree class (Listing 8.5.8), which is where all the magic happens.
import java.util.ArrayList;
public class Octree {
OTNode root;
int numLeaves;
int maxLevel;
ArrayList<OTNode> allLeaves;
public Octree() {
this.root = null;
this.maxLevel = 5;
this.numLeaves = 0;
this.allLeaves = new ArrayList<OTNode>();
}
public void insert(int r, int g, int b) {
if (this.root == null) {
this.root = new OTNode(null, 0, this);
}
this.root.insert(r, g, b, 0, this);
}
public int[] find(int r, int g, int b) {
if (this.root != null) {
return this.root.find(r, g, b, 0);
} else {
return null;
}
}
public void reduce(int maxCubes) {
System.err.printf("Reducing %d to %d%n",
this.allLeaves.size(), maxCubes);
while (this.allLeaves.size() > maxCubes) {
OTNode smallest = this.findMinCube();
smallest.parent.merge();
this.allLeaves.add(smallest.parent);
this.numLeaves += 1;
}
}
public OTNode findMinCube() {
int minCount = Integer.MAX_VALUE;
int maxLevel = 0;
OTNode minCube = null;
for (OTNode node: allLeaves) {
if (node.count <= minCount && node.level >= maxLevel) {
minCube = node;
minCount = node.count;
maxLevel = node.level;
}
}
return minCube;
}
}
Listing8.5.8.The Octree Class
First notice that the constructor for an Octree initializes the root node to null. Then it sets up three important attributes that all the nodes of an octree may need to access. Those attributes are maxLevel, numLeaves, and allLeaves. The maxLevel attribute limits the total depth of the tree. Notice that in our implementation we have initialized maxLevel to five. This is a small optimization that allows us to ignore the two least significant bits of color information. It keeps the overall size of the tree much smaller and doesn’t hurt the quality of the final image at all. The numLeaves and allLeaves attributes allow us to keep track of the number of leaf nodes and allow us direct access to the leaves without traversing all the way down the tree. We will see why this is important shortly.
The insert and find methods behave exactly like their cousins in chapter Chapter 6. They each check to see if a root node exists, and then call the corresponding method in the root node. Notice that insert and find both use the red, green, and blue components ((r, g, b)) to identify a node in the tree.
The reduce method is defined on line 31 of Listing 8.5.8. This method loops until the number of leaves in the leaf list is less than the total number of colors we want to have in the final image (defined by the parameter maxCubes). reduce makes use of a helper method findMinCube to find the node in the octree with the smallest reference count. Once the node with the smallest reference count is found, that node is merged into a single node with all of its siblings (see line 36 of Listing 8.5.8).
The findMinCube method is implemented using the allLeaves and a simple find minimum loop pattern. When the number of leaf nodes is large, and it could be as large is 16.7 million, this approach is not very efficient. In one of the exercises you are asked to modify the Octree class and improve the efficiency of findMinCube.
One of the things to mention about the Octree class is that it uses an instance of the class OTNode which is defined inside the the Octree class. A class that is defined inside another class is called an inner class. We define OTNode inside Octree because each node of an octree needs to have access to some information that is stored in an instance of the Octree class. Another reason for making OTNode an inner class is that there is no reason for any code outside of the Octree class to use it. The way that an octree node is implemented is really a private detail that nobody else needs to know about. This is a good software engineering practice known as information hiding.
Now let’s look at the class definition for the nodes in an octree (Listing 8.5.9). The constructor for the OTNode class has three parameters: parent, level, and outer. These parameters allow the Octree methods to construct new nodes under a variety of circumstances. As we did with binary search trees, we will keep track of the parent of a node explicitly. The level of the node simply indicates its depth in the tree. The most interesting of these three parameters is the outer parameter, which is a reference to the instance of the octree class that created this node. outer will function like this in that it will allow the instances of OTNode to access attributes of an instance of Octree.
The other attributes that we want to remember about each node in an octree include the reference count and the red, green, and blue components of the color represented by this tree. As you will note in the insert method, only a leaf node of the tree will have values for red, green, blue, and count. Also note that since each node can have up to eight children we initialize a list of eight references to keep track of them all. Rather than a left and right child as in binary trees, an octree has 0–7 children.
public class OTNode {
public int red;
public int green;
public int blue;
public int count;
public OTNode parent;
public int level;
public Octree oTree;
public OTNode[] children;
public OTNode() {
this(null, 0, null);
}
public OTNode(OTNode parent, int level, Octree outer) {
this.red = 0;
this.green = 0;
this.blue = 0;
this.parent = parent;
this.level = level;
this.oTree = outer;
this.children = new OTNode[8];
}
Listing8.5.9.Defining an OTNode
Now we get into the really interesting parts of the octree implementation. The Java code for inserting a new node into an octree is shown in Listing 8.5.10. The first problem we need to solve is how to figure out where to place a new node in the tree. In a binary search tree we used the rule that a new node with a key less than its parent went in the left subtree, and a new node with a key greater than its parent went in the right subtree. But with eight possible children for each node it is not that simple. In addition, when indexing colors it is not obvious what the key for each node should be. In an octree we will use the information from the three color components. Figure 8.5.11 shows how we can use the red, green, and blue color values to compute an index for the position of the new node at each level of the tree. The corresponding Java code for computing the index is on lines 20–26 of Listing 8.5.10.
public void insert(int r, int g, int b, int level, Octree outer) {
if (level < oTree.maxLevel) {
int index = computeIndex(r, g, b, level);
if (this.children[index] == null) {
this.children[index] = new OTNode(this, level + 1, outer);
}
this.children[index].insert(r, g, b, level + 1, outer);
} else {
if (this.count == 0) {
this.oTree.numLeaves = this.oTree.numLeaves + 1;
this.oTree.allLeaves.add(this);
}
this.red += r;
this.green += g;
this.blue += b;
this.count += 1;
}
}
public int computeIndex(int r, int g, int b, int level) {
int nShift = 8 - level;
int rBits = (r >> (nShift - 2)) & 0x04;
int gBits = (g >> (nShift - 1)) & 0x02;
int bBits = (b >> nShift) & 0x01;
return rBits | gBits | bBits;
}
Listing8.5.10.Insert into OCtree
The computation of the index combines bits from each of the red, green, and blue color components, starting at the top of the tree with the highest order bits. Figure 8.5.11 shows the binary representation of the red, green, and blue components of 163, 98, 231. At the root of the tree we start with the most significant bit from each of the three color components; in this case the three bits are 1, 0, and 1. Putting these bits together we get binary 101 or decimal 5.
The operators used in the compute_index may be unfamiliar to you. The >> operator is the right shift operation. The & is bitwise and, and | is logical or. The bitwise or and bitwise and operations work just like the logical operations used in conditionals, except that they work on the individual bits of a number. The shift operation moves the bits \(n\) places to the right, filling in with zeros on the left and dropping the bits as they go off the right.
Once we have computed the index appropriate for the current level of the tree, we traverse down into the subtree. In the example in Figure 8.5.11 we follow the link at position 5 in the children array. If there is no node at position 5, we create one. We keep traversing down the tree until we get to maxLevel. At maxLevel we stop searching and store the data. Notice that we do not overwrite the data in the leaf node, but rather we add the color components to any existing components and increment the reference counter. This allows us to compute the average of any color below the current node in the color cube. In this way, a leaf node in the octree may represent a number of similar colors in the color cube.
Figure8.5.11.Computing an Index to Insert a Node in an octree
The find method, shown in Listing 8.5.12, uses the same method of index computation as the insert method to traverse the tree in search of a node matching the red, green, and blue components.
public int[] find(int r, int g, int b, int level) {
if (level < this.oTree.maxLevel) {
int index = computeIndex(r, g, b, level);
if (this.children[index] != null) {
return this.children[index].find(r, g, b, level + 1);
} else if (this.count > 0) {
return new int[] {this.red / this.count,
this.green / this.count, this.blue / this.count};
} else {
System.err.printf(
"No leaf node to represent RGB(%d, %d, %d)%n",
r, g, b);
return null;
}
} else {
return new int[] {this.red / this.count,
this.green / this.count, this.blue / this.count};
}
}
Listing8.5.12.The find Method
The find method has three exit conditions:
We have reached the maximum level of the tree and so we return the average of the color information stored in this leaf node (see lines 6–0).
We have found a leaf node at a height less than maxLevel (see lines 4–5). This is possible only after the tree has been reduced. See below.
We try to follow a path into a nonexistent subtree, which is an error.
Note8.5.13.Java Note.
We are writing the error to System.err instead of System.out. Doing this permits users to direct the error output to a file separate from any normal console output when running the program from the terminal.
The final aspect of the OTNode class is the merge method. It allows a parent to subsume all of its children and become a leaf node itself. If you remember back to the structure of the octree where each parent cube fully encloses all the cubes represented by the children, you will see why this makes sense. When we merge a group of siblings we are effectively taking a weighted average of the colors represented by each of those siblings. Since all the siblings are relatively close to each other in color space, the average is a good representation of all of them. Figure 8.5.14 illustrates the merge process for some sibling nodes.
Figure8.5.14.Merging Four Leaf Nodes of an octree
Figure 8.5.14 shows the red, green, and blue components represented by the four leaf nodes whose identifying color values are (101, 122, 167), (100, 122, 183), (123, 108, 163), and (126, 113, 166). As you can see in Listing 8.5.12, the identifying values are calculated by dividing the color values by the count. Notice how close they are in the overall color space. The leaf node that gets created from all of these has an ID of (112, 115, 168). This is close to the average of the four, but weighted more towards the third color tuple due to the fact that it had a reference count of 12.
public void merge() {
for (OTNode child: this.children) {
if (child != null) {
if (child.count > 0) {
boolean removed = this.oTree.allLeaves.remove(child);
this.oTree.numLeaves -= 1;
} else {
System.err.println("Recursively merging non-leaf");
System.exit(0);
child.merge();
}
this.count += child.count;
this.red += child.red;
this.green += child.green;
this.blue += child.blue;
}
}
for (int i = 0; i < 8; i++) {
this.children[i] = null;
}
}
Listing8.5.15.The merge method
Because the octree uses only colors that are really present in the image and faithfully preserves colors that are often used, the final quantized image from the octree is much higher quality than the simple method we used to start this section. Figure 8.5.16 shows a comparison of the original image with the quantized image.
Figure8.5.16.Comparison of Original and Octree-Quantized Image
There are many additional ways to compress images using techniques such as run-length encoding, discrete cosine transform, and Huffman coding. Any of these algorithms are within your grasp, and we encourage you to look them up and read about them. In addition, quantized images can be improved by using a technique known as dithering. Dithering is a process by which different colors are placed near each other so that the eye blends the colors together, forming a more realistic image. This is an old trick used by newspapers for doing color printing using just black plus three different colors of ink. Again, you can research dithering and try to apply it to some images on your own.
