From Bitmap to Vector: Implementing K-Means Color Quantization and Contour Tracing#

I needed to convert some PNG icons to SVG for a project. Tried a few online tools—either poor quality or paywalled. So I built my own and dove into the core algorithms of image vectorization.

Bitmap vs Vector: The Fundamental Difference#

Bitmaps (PNG/JPG) store pixel color values. Scale them up, they blur. Vectors (SVG) store mathematical paths. Scale infinitely, stay sharp.

Vectorization in a nutshell:Extract color regions from pixel matrix, convert to geometric paths.

Three steps:

  1. Color Quantization - Reduce color count
  2. Region Labeling - Mark connected same-color regions
  3. Contour Tracing - Extract boundary paths

K-Means Color Quantization#

A photo might have tens of thousands of colors. Direct processing creates fragmented regions. K-Means reduces colors to a specified number (e.g., 8) while preserving visual quality.

The Algorithm#

K-Means minimizes squared color distance:

argmin Σ ||pixel - center(pixel)||²

I used K-Means++ initialization to avoid local optima:

function kMeans(pixels: [number,number,number][], k: number, maxIter: number): [number,number,number][] {
  if (pixels.length <= k) return pixels.map(p => [...p] as [number,number,number]);
  
  // K-Means++: First center random, subsequent centers pick farthest points
  const centers: [number,number,number][] = [pixels[Math.floor(Math.random() * pixels.length)]];
  
  for (let i = 1; i < k; i++) {
    let maxD = -1, best: [number,number,number] = pixels[0];
    for (const p of pixels) {
      // Distance to nearest center
      let minD = Infinity;
      for (const c of centers) {
        const d = (p[0]-c[0])**2 + (p[1]-c[1])**2 + (p[2]-c[2])**2;
        if (d < minD) minD = d;
      }
      // Pick farthest point as new center
      if (minD > maxD) { maxD = minD; best = p; }
    }
    centers.push(best);
  }
  
  // Iterative updates
  const assign = new Uint8Array(pixels.length);
  for (let it = 0; it < maxIter; it++) {
    let changed = false;
    
    // Assign pixels to nearest center
    for (let i = 0; i < pixels.length; i++) {
      let md = Infinity, b = 0;
      const p = pixels[i];
      for (let j = 0; j < k; j++) {
        const d = (p[0]-centers[j][0])**2 + (p[1]-centers[j][1])**2 + (p[2]-centers[j][2])**2;
        if (d < md) { md = d; b = j; }
      }
      if (assign[i] !== b) { changed = true; assign[i] = b; }
    }
    
    if (!changed) break;
    
    // Recalculate centers
    const sums: [number,number,number,number][] = Array.from({length: k}, () => [0,0,0,0]);
    for (let i = 0; i < pixels.length; i++) {
      const c = assign[i];
      sums[c][0] += pixels[i][0];
      sums[c][1] += pixels[i][1];
      sums[c][2] += pixels[i][2];
      sums[c][3]++;
    }
    
    for (let j = 0; j < k; j++) {
      if (sums[j][3] > 0) {
        centers[j] = [
          Math.round(sums[j][0] / sums[j][3]),
          Math.round(sums[j][1] / sums[j][3]),
          Math.round(sums[j][2] / sums[j][3])
        ];
      }
    }
  }
  
  return centers;
}

Key points:

  1. Distance metric uses squared Euclidean distance (skip the sqrt)
  2. K-Means++ initialization spreads centers more evenly
  3. Early termination if no pixels change assignment

Color Assignment#

After getting the palette, assign each pixel to the nearest color:

const indexed = new Uint8Array(n);
for (let i = 0; i < n; i++) {
  const idx = i * 4;
  if (d[idx+3] <= 128) { indexed[i] = 255; continue; } // Transparent pixels
  
  const r = d[idx], g = d[idx+1], b = d[idx+2];
  let md = Infinity, best = 0;
  
  for (let j = 0; j < palette.length; j++) {
    const dr = r - palette[j][0];
    const dg = g - palette[j][1];
    const db = b - palette[j][2];
    const dist = dr*dr + dg*dg + db*db;
    if (dist < md) { md = dist; best = j; }
  }
  
  indexed[i] = best;
}

Moore-Neighbor Contour Tracing#

After quantization, the image becomes several color regions. Now extract boundary paths for each region.

The Algorithm#

Moore-Neighbor is a classic boundary tracing algorithm. Core idea:“Walk around” the boundary pixels.

Start from a boundary pixel, search 8 neighbors clockwise, find the next boundary point, repeat until back to start.

function traceContours(indexed: Uint8Array, w: number, h: number, ci: number): Pt[][] {
  // Build binary image: current color=1, others=0
  const grid = new Uint8Array(w * h);
  for (let i = 0; i < w * h; i++) grid[i] = indexed[i] === ci ? 1 : 0;
  
  const visited = new Uint8Array(w * h);
  const contours: Pt[][] = [];
  
  // 8 directions: right, bottom-right, down, bottom-left, left, top-left, up, top-right
  const dirs = [[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1]];
  
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      const idx = y * w + x;
      if (grid[idx] !== 1 || visited[idx]) continue;
      
      // Check if boundary pixel (at least one neighbor is different color)
      const nb = [
        x > 0 ? grid[y*w+x-1] : 0,
        x < w-1 ? grid[y*w+x+1] : 0,
        y > 0 ? grid[(y-1)*w+x] : 0,
        y < h-1 ? grid[(y+1)*w+x] : 0
      ];
      if (nb.every(n => n === 1)) continue; // Interior point, skip
      
      // Moore-Neighbor tracing
      const contour: Pt[] = [{x, y}];
      visited[idx] = 1;
      let cx = x, cy = y, dir = 0;
      
      for (let step = 0; step < w * h * 4; step++) {
        let found = false;
        
        // Search counterclockwise from current direction
        for (let i = 0; i < 8; i++) {
          const d = (dir + 7 - i) % 8;
          const nx = cx + dirs[d][0], ny = cy + dirs[d][1];
          
          if (nx >= 0 && nx < w && ny >= 0 && ny < h && grid[ny*w+nx] === 1) {
            // Back to start with path length > 2, done
            if (nx === x && ny === y && contour.length > 2) { found = true; break; }
            
            cx = nx; cy = ny; dir = d;
            contour.push({x: nx, y: ny});
            visited[ny*w+nx] = 1;
            found = true;
            break;
          }
        }
        
        if (!found) break;
        if (cx === x && cy === y) break; // Loop closed
      }
      
      if (contour.length >= 4) contours.push(simplifyContour(contour, 1.5));
    }
  }
  
  return contours;
}

Key details:

  1. Starting direction searches counterclockwise from current direction to follow outer boundary
  2. Loop detection stops when coordinates return to start
  3. Boundary check only pixels with at least one different-colored neighbor are boundary points

Douglas-Peucker Path Simplification#

Contour tracing produces too many points. Direct SVG conversion creates huge files. Douglas-Peucker reduces points while preserving shape.

function simplifyContour(pts: Pt[], eps: number): Pt[] {
  if (pts.length <= 2) return pts;
  
  // Find point farthest from line connecting first and last
  let maxD = 0, maxI = 0;
  const f = pts[0], l = pts[pts.length - 1];
  
  for (let i = 1; i < pts.length - 1; i++) {
    const d = perpDist(pts[i], f, l);
    if (d > maxD) { maxD = d; maxI = i; }
  }
  
  // If max distance exceeds threshold, recursively simplify
  if (maxD > eps) {
    const left = simplifyContour(pts.slice(0, maxI + 1), eps);
    const right = simplifyContour(pts.slice(maxI), eps);
    return [...left.slice(0, -1), ...right];
  }
  
  // Otherwise replace with straight line
  return [f, l];
}

function perpDist(p: Pt, a: Pt, b: Pt): number {
  const dx = b.x - a.x, dy = b.y - a.y;
  if (dx === 0 && dy === 0) return Math.sqrt((p.x-a.x)**2 + (p.y-a.y)**2);
  return Math.abs(dy*p.x - dx*p.y + b.x*a.y - b.y*a.x) / Math.sqrt(dx*dx + dy*dy);
}

Generating SVG#

Finally, convert paths to SVG <path> elements:

const svgParts: string[] = [];
for (let ci = 0; ci < palette.length; ci++) {
  const contours = traceContours(indexed, sw, sh, ci);
  if (contours.length === 0) continue;
  
  const hex = toHex(palette[ci]);
  for (const contour of contours) {
    if (contour.length < 3) continue;
    
    // Build path's d attribute
    let d = `M${contour[0].x},${contour[0].y}`;
    for (let i = 1; i < contour.length; i++) {
      d += `L${contour[i].x},${contour[i].y}`;
    }
    d += 'Z'; // Close path
    
    svgParts.push(`<path d="${d}" fill="${hex}" stroke="${hex}" stroke-width="1"/>`);
  }
}

const svg = `<svg xmlns="http://www.w3.org/2000/svg" width="${img.width}" height="${img.height}" viewBox="0 0 ${sw} ${sh}">
<g transform="scale(${scaleX.toFixed(4)},${scaleY.toFixed(4)})">
<rect width="${sw}" height="${sh}" fill="#fff"/>
${svgParts.join('\n')}
</g>
</svg>`;

Performance Optimizations#

For large images:

1. Downscale Processing# 

const maxDim = 400;
let sw = img.width, sh = img.height;
const r = maxDim / Math.max(sw, sh);
if (r < 1) { sw = Math.floor(sw * r); sh = Math.floor(sh * r); }

Process at max 400px, then scale back to original size.

2. requestAnimationFrame to Avoid Blocking# 

setProcessing(true);
requestAnimationFrame(() => {
  // Heavy computation
  setProcessing(false);
});

3. Early Termination#

K-Means stops early if no pixels change assignment.

The Result#

Based on these algorithms, I built: Image to Vector

Features:

  • K-Means color quantization (2-32 colors)
  • Moore-Neighbor contour tracing
  • Douglas-Peucker path simplification
  • Paste to upload

Works well for icons, logos, simple illustrations. For complex photos, consider professional tools like Illustrator’s Image Trace.

Related: SVG Optimizer | Image Compress