01-Overview

# LPGS Algorithm Overview

> **Doc Version**: v1.0.0 · **Algorithm Version**: LPGS v1.0 · **Last Updated**: 2026-06-01

## Full Name

**LPGS** — **L**uMKFs **P**rism **G**auss **S**plat

## One-Line Definition

LPGS is an **error-driven stochastic greedy search** algorithm for geometric image approximation: it iteratively overlays semi-transparent geometric primitives (circles, ellipses, lines) onto a canvas, progressively approaching the target image by continuously reducing the pixel-level SSD (Sum of Squared Differences) error between the current canvas and the target.

## Algorithm Positioning

| Dimension | Description |
|-----------|-------------|
| Problem Domain | Image → ordered geometric primitive sequence (inverse decomposition) |
| Optimization Objective | Minimize SSD(I_target, I_current) |
| Search Strategy | Random sampling + greedy selection + local mutation |
| Convergence Guarantee | Monotonically decreasing — a new shape is accepted only when total error decreases |
| Output Format | Ordered list of geometric primitives (with position, size, rotation, color, opacity) |

## Core Ideas

The core philosophy of LPGS can be summarized as **"Splat"**:

1. **Splat**: Each iteration "splats" a geometric shape onto the canvas, covering a portion of the canvas pixels
2. **Prism**: Each shape acts like a prism, "refracting" the canvas colors closer to the target direction
3. **Gauss**: The color solving process uses least squares (equivalent to maximum likelihood estimation under Gaussian distribution), finding the globally optimal color and opacity for given shape parameters

The algorithm does not pursue a perfect solution in one step; instead, it approaches the target image from coarse to fine through the cumulative effect of many "small splats."

## Relationship to Related Algorithms

LPGS shares its algorithmic framework with the [Geometrize](https://www.geometrize.co.uk/) / [Primitive](https://github.com/fogleman/primitive) family, but differs fundamentally in the following aspects:

| Feature | Geometrize/Primitive | LPGS |
|----------|---------------------|------|
| Error-driven sampling | None/simple | 16×16 error grid weighted sampling |
| Color solving | Single-pass least squares | Two-pass iterative least squares |
| Edge awareness | None | Distance transform + shape overflow detection |
| Transparency handling | Not supported | Alpha pre-multiplication + threshold filtering |
| Precision mode | None | ROI selection + auto-detection of high-error regions |
| Multi-threading | None | Parallel candidate evaluation |
| Primitive types | Various (triangles, rectangles, etc.) | Circle, ellipse, line |

## Overall Algorithm Flow

```
┌─────────────────────────────────────────────────────────┐
│                  Image Loading & Preprocessing            │
│  Scale to MAX_DIM=500 → Edge padding 3% → Alpha premul   │
└────────────────────────┬────────────────────────────────┘
                         ▼
┌─────────────────────────────────────────────────────────┐
│                  Build Initial Error State                │
│  Compute initial SSD → Build error grid → Build edge map │
└────────────────────────┬────────────────────────────────┘
                         ▼
              ┌──────────────────────┐
              │   Main Loop RunLoop()│◄──────────────────┐
              │  Add Speed shapes/frame│                   │
              └──────────┬───────────┘                    │
                         ▼                                │
              ┌──────────────────────┐                    │
              │   TryOneShape()       │                    │
              │  Generate→Eval→Mutate │                    │
              └──────────┬───────────┘                    │
                         ▼                                │
              ┌──────────────────────┐                    │
              │  shapeCount < MaxShapes?│─── Yes ─────────┘
              └──────────┬───────────┘
                         │ No
                         ▼
              ┌──────────────────────┐
              │  Fitting done /       │
              │  Precision mode → ROI │
              └──────────────────────┘
```

## Key Design Principles

1. **Monotonicity**: Each step only accepts shapes that reduce the total SSD, guaranteeing a monotonically decreasing error curve
2. **Error-driven**: New shape positions are determined by the error distribution — regions with higher error are prioritized
3. **Coarse-to-fine**: Shape sizes decrease with progress (`sizeMult = 1.0 - progress * 0.55`) — large shapes lay the base early, small shapes fill details later
4. **Separation of concerns**: Shape parameters (geometry) are determined by random search, color parameters by analytical solving — the two are decoupled
5. **Incremental**: Each new shape is evaluated against the current canvas state, naturally supporting pause/resume/precision refinement