Skip to content

OCTREE.md

Latest commit

 

History

History
136 lines (92 loc) · 4.14 KB

OCTREE.md

File metadata and controls

136 lines (92 loc) · 4.14 KB
Raw

Octree Color Quantization

Overview

This program implements the Octree Color Quantization algorithm to reduce the number of colors in a 24-bit RGB bitmap image. The octree algorithm is an efficient method for color quantization that produces high-quality results by organizing colors in a tree structure based on their RGB values.

Algorithm Description

The octree color quantization algorithm works by:

  1. Building an Octree: Each color in the image is inserted into an octree where each level represents one bit of the RGB color values. The tree has a maximum depth of 8 levels (one for each bit in RGB channels).

  2. Color Representation: Each node in the octree represents a cube in the RGB color space. Leaf nodes accumulate color information (sum of RGB values and pixel count) for colors that map to that region.

  3. Tree Reduction: When the number of leaf nodes (colors) exceeds the target palette size, the algorithm merges nodes at the deepest level, combining similar colors together.

  4. Palette Generation: Once the tree is pruned to the desired number of colors, the final palette is generated by averaging the RGB values accumulated in each leaf node.

  5. Image Mapping: Each pixel in the original image is mapped to the closest color in the quantized palette by traversing the octree.

Features

  • Supports 24-bit RGB bitmap input images
  • Produces 8-bit indexed color output images
  • Configurable palette size (2-256 colors)
  • Efficient octree-based algorithm
  • High-quality color reduction

Usage

./octree <input.bmp> <output.bmp> [colors]

Parameters

  • input.bmp - Input 24-bit RGB bitmap file
  • output.bmp - Output 8-bit indexed bitmap file
  • colors - (Optional) Number of colors in output palette (default: 256, max: 256)

Examples

Reduce an image to 256 colors (default):

./octree photo.bmp photo_256.bmp

Reduce an image to 16 colors:

./octree photo.bmp photo_16.bmp 16

Reduce an image to 64 colors:

./octree landscape.bmp landscape_64.bmp 64

Building

The program can be built using the provided makefile:

make octree

Or manually:

gcc -Wall -O2 -std=c99 octree.c image.c bitmap.c -o octree

Dependencies

The program uses the following library files from the project:

  • image.h / image.c - Image data structures and bitmap management
  • bitmap.h / bitmap.c - Windows BMP file I/O operations

Technical Details

Octree Structure

  • Maximum Depth: 8 levels (matching 8 bits per RGB channel)
  • Children per Node: 8 (representing octants of RGB cube)
  • Node Types: Internal nodes and leaf nodes
  • Color Accumulation: Leaf nodes store sum of RGB values and pixel count

Memory Efficiency

The algorithm dynamically allocates nodes only as needed, and prunes the tree during construction to maintain the target color count, making it memory-efficient even for large images.

Color Quality

The octree algorithm produces high-quality quantization results because:

  • It adaptively partitions the color space based on actual image colors
  • Similar colors are naturally grouped together in the tree
  • The averaging process preserves color accuracy

Limitations

  • Input images must be 24-bit RGB format
  • Maximum palette size is 256 colors (8-bit indexed output)
  • Minimum palette size is 2 colors

Output Format

The output is an 8-bit indexed color bitmap (.bmp) file with:

  • A color palette containing the quantized colors
  • Indexed pixel data mapping to the palette

Example Output

Octree Color Quantization
=========================

Input file:  photo.bmp
Output file: photo_256.bmp
Max colors:  256

Loading input image...
Image loaded: 800x600, 24-bit
Building octree from image colors...
Octree built with 256 colors
Palette contains 256 colors
Mapping pixels to palette...
Quantization complete!
Saving output image...
Image saved successfully!

References

  • M. Gervautz and W. Purgathofer, "A Simple Method for Color Quantization: Octree Quantization," in Graphics Gems, Academic Press, 1990.

License

This program is part of the Color-Reduction project. See the LICENSE file in the project root for details.