Algorithms

Image Inversion — KDTree Algorithm

C implementation comparing two image inversion methods: naive pixel-by-pixel color table vs. KD-Tree nearest-neighbor search in color space, with benchmarked performance and Gnuplot visualization.

2023/2024
Completed (2023/2024)
1 member
View Code

Technologies Used

CKD-TreeAlgorithmsMakefileGnuplotData Structures

Image inversion tools implemented in C comparing two algorithmic methods with different time complexities. Developed as a first-year algorithms project at ENSICAEN.

🔧 Methods Compared

Method 1 — Naive Color Table

  • Builds a lookup table mapping each source color to its inverted value
  • O(n) table construction, O(1) per pixel lookup
  • Simple but memory-bound for large color spaces

Method 2 — KD-Tree Nearest Neighbor

  • Constructs a K-D Tree over the color space
  • For each pixel, finds the nearest neighbor using KD-Tree search
  • O(n log n) construction, O(log n) per query
  • More complex but generalizable to arbitrary color transformations

🏗️ Architecture

  • test_table — Unit tests for color table method
  • test_kd_tree — Unit tests for KD-Tree method
  • Makefile — Build automation
  • Gnuplot scripts — Performance curve visualization

📚 Learning Outcomes

  • Implemented KD-Tree data structure from scratch in C
  • Compared algorithmic complexity empirically with benchmarked measurements
  • Applied Makefile build automation
  • Visualized performance results with Gnuplot

Challenges

  • Implementing KD-Tree from scratch in C with correct nearest-neighbor search
  • Managing memory correctly for tree construction and traversal

Solutions

  • Implemented recursive KD-Tree construction with alternating split dimensions
  • Used careful pointer management and valgrind testing to ensure no memory leaks

Outcomes

  • Two functional image inversion implementations with comparative benchmarks
  • KD-Tree implementation validated with unit tests
  • Performance comparison visualized with Gnuplot