Skip to content

Open source CapCut alternative.

TypeScript
17.2 KB
Raw Blame
/**
 * Measuring pictures and fitting grades to them: color statistics off a
 * frame, the auto grade, and reference matching. Every fit is expressed in
 * the grade's own parameters (exposure in stops, white balance as an
 * illuminant, contrast about grey), so the result is an ordinary ColorGrade
 * the user or the assistant refines afterward. Stats and the auto grade read
 * the base rendering — the picture after the source conversion — so a log
 * clip is measured as the display sees it; a match renders the clip's code
 * values through its real recipe for every grade it tries.
 */

import { type ColorGrade, GRADE_MAX, normalizeGrade } from "./colorGrade";
import { displayToLab } from "./colorDifference";
import { type ClipColorRecipe, createClipTransform } from "./colorPipeline";
import { bt1886Decode } from "./colorSpace";
import { CONTRAST_POWER_AT_MAX } from "./gradeMath";
import type { ParsedLut } from "./lutFile";

/** Quantile probes used by stats and matching. */
export const STAT_QUANTILES = [0.02, 0.1, 0.25, 0.5, 0.75, 0.9, 0.98] as const;

export interface ColorStats {
  /** Per-channel values 0..255 at each STAT_QUANTILES probe. */
  r: number[];
  g: number[];
  b: number[];
  luma: number[];
  /** Channel means 0..255. */
  meanR: number;
  meanG: number;
  meanB: number;
  /** Mean HSL saturation 0..1. */
  meanSat: number;
  /** Red/blue mean ratio in the midtones; >1 reads warm, <1 reads cool. */
  warmth: number;
  /** CIELAB lightness L* (0..100) at each STAT_QUANTILES probe. */
  lightness: number[];
  /** The color of the shadows, midtones and highlights (TONE_BANDS): the
   * share of pixels in the band, the mean a* and b* — its cast, green–magenta
   * and blue–yellow — and their spread, which saturation scales. */
  tones: ToneColor[];
}

export interface ToneColor {
  share: number;
  a: number;
  b: number;
  spreadA: number;
  spreadB: number;
}

/** Upper L* edge of each tonal band, darkest first. */
const TONE_BANDS = [35, 70, 100];

/** Lightness bins per L* unit: a tenth of the smallest step anyone sees. */
const L_BINS_PER_UNIT = 10;

export function colorStatsFromImageData(data: Uint8ClampedArray): ColorStats | undefined {
  const hist = [new Float64Array(256), new Float64Array(256), new Float64Array(256), new Float64Array(256)];
  const lightHist = new Float64Array(100 * L_BINS_PER_UNIT + 1);
  // Per band: count, Σa, Σb, Σa², Σb².
  const bands = TONE_BANDS.map(() => [0, 0, 0, 0, 0]);
  let count = 0;
  let sumR = 0;
  let sumG = 0;
  let sumB = 0;
  let sumSat = 0;
  let midR = 0;
  let midB = 0;
  let mids = 0;
  for (let i = 0; i < data.length; i += 4) {
    const r = data[i];
    const g = data[i + 1];
    const b = data[i + 2];
    const luma = 0.2126 * r + 0.7152 * g + 0.0722 * b;
    hist[0][r]++;
    hist[1][g]++;
    hist[2][b]++;
    hist[3][Math.min(255, Math.round(luma))]++;
    sumR += r;
    sumG += g;
    sumB += b;
    const max = Math.max(r, g, b);
    const min = Math.min(r, g, b);
    const l2 = max + min;
    sumSat += max === min ? 0 : (max - min) / (l2 <= 255 ? l2 : 510 - l2);
    if (luma >= 16 && luma <= 240) {
      midR += r;
      midB += b;
      mids++;
    }
    const [L, a, lb] = displayToLab(r, g, b);
    lightHist[Math.max(0, Math.min(lightHist.length - 1, Math.round(L * L_BINS_PER_UNIT)))]++;
    const band = bands[Math.max(0, TONE_BANDS.findIndex((top) => L <= top))];
    band[0]++;
    band[1] += a;
    band[2] += lb;
    band[3] += a * a;
    band[4] += lb * lb;
    count++;
  }
  if (!count) return undefined;
  const quantiles = (h: Float64Array, scale = 1) =>
    STAT_QUANTILES.map((p) => {
      let acc = 0;
      for (let v = 0; v < h.length; v++) {
        acc += h[v];
        if (acc >= count * p) return v / scale;
      }
      return (h.length - 1) / scale;
    });
  return {
    r: quantiles(hist[0]),
    g: quantiles(hist[1]),
    b: quantiles(hist[2]),
    luma: quantiles(hist[3]),
    meanR: sumR / count,
    meanG: sumG / count,
    meanB: sumB / count,
    meanSat: sumSat / count,
    warmth: mids ? midR / Math.max(1, midB) : 1,
    lightness: quantiles(lightHist, L_BINS_PER_UNIT),
    tones: bands.map(([n, sa, sb, saa, sbb]) => {
      if (!n) return { share: 0, a: 0, b: 0, spreadA: 0, spreadB: 0 };
      const a = sa / n;
      const b = sb / n;
      return {
        share: n / count,
        a,
        b,
        spreadA: Math.sqrt(Math.max(0, saa / n - a * a)),
        spreadB: Math.sqrt(Math.max(0, sbb / n - b * b)),
      };
    }),
  };
}

/* ------------------------------------------------------------------ */
/* Auto grade                                                          */
/* ------------------------------------------------------------------ */

/** Pixels of a frame rendered through its recipe with a candidate grade. */
type PixelRender = (grade: ColorGrade | undefined) => Uint8ClampedArray;

/** The most pixels a fit renders per try: enough for quantiles a tenth of
 * an L* apart, few enough that a few hundred tries take well under a second. */
const FIT_SAMPLE = 4096;

/** A PixelRender over a frame's code values (RGBA) and the recipe that draws
 * them, with the candidate grade as the manual layer: every try runs the
 * real pipeline, so a log clip is fitted in scene light exactly as the
 * preview renders it. The recipe grade's preset and LUT (`userLut` its
 * table) stay under every try, as they stay on the clip. At most FIT_SAMPLE
 * pixels, evenly spaced. */
function recipeRender(px: Uint8ClampedArray, recipe: ClipColorRecipe, userLut?: ParsedLut): PixelRender {
  const { preset, lut } = recipe.grade ?? {};
  const total = px.length >> 2;
  const stride = Math.max(1, Math.ceil(total / FIT_SAMPLE));
  const sample = new Float32Array(Math.ceil(total / stride) * 3);
  let n = 0;
  for (let i = 0; i < total; i += stride) {
    sample[n * 3] = px[i * 4] / 255;
    sample[n * 3 + 1] = px[i * 4 + 1] / 255;
    sample[n * 3 + 2] = px[i * 4 + 2] / 255;
    n++;
  }
  return (grade) => {
    const fn = createClipTransform({ ...recipe, grade: { ...grade, ...(preset ? { preset } : {}), ...(lut ? { lut } : {}) } }, userLut);
    const out = new Uint8ClampedArray(n * 4);
    for (let i = 0; i < n; i++) {
      const r = sample[i * 3];
      const g = sample[i * 3 + 1];
      const b = sample[i * 3 + 2];
      const v = fn ? fn(r, g, b) : [r, g, b];
      out[i * 4] = Math.round(v[0] * 255);
      out[i * 4 + 1] = Math.round(v[1] * 255);
      out[i * 4 + 2] = Math.round(v[2] * 255);
      out[i * 4 + 3] = 255;
    }
    return out;
  };
}

const lumaOf = (data: Uint8ClampedArray, i: number) => 0.2126 * data[i] + 0.7152 * data[i + 1] + 0.0722 * data[i + 2];

/** Geometric mean of display luminance: where the frame's exposure sits. */
function logAverage(data: Uint8ClampedArray): number {
  let sum = 0;
  for (let i = 0; i < data.length; i += 4) sum += Math.log(Math.max(1e-4, bt1886Decode(lumaOf(data, i) / 255)));
  return Math.exp(sum / Math.max(1, data.length >> 2));
}

/** Mean red minus mean blue of the midtones in display light — the cast
 * grey-world reads; darker and clipped pixels carry no reliable illuminant. */
function midtoneCast(data: Uint8ClampedArray): number {
  let gap = 0;
  let mids = 0;
  for (let i = 0; i < data.length; i += 4) {
    const luma = lumaOf(data, i);
    if (luma < 16 || luma > 240) continue;
    gap += bt1886Decode(data[i] / 255) - bt1886Decode(data[i + 2] / 255);
    mids++;
  }
  return mids ? gap / mids : 0;
}

/** The slider value in [-GRADE_MAX, GRADE_MAX] where a monotone `f` crosses
 * zero by bisection, or the end nearer zero when it never does. */
function sliderRoot(f: (v: number) => number): number {
  let lo = -GRADE_MAX;
  let hi = GRADE_MAX;
  let flo = f(lo);
  const fhi = f(hi);
  if (Math.sign(flo) === Math.sign(fhi)) return Math.abs(flo) < Math.abs(fhi) ? lo : hi;
  for (let i = 0; i < 14; i++) {
    const mid = (lo + hi) / 2;
    const fm = f(mid);
    if (Math.sign(fm) === Math.sign(flo)) {
      lo = mid;
      flo = fm;
    } else hi = mid;
  }
  return (lo + hi) / 2;
}

/** How much of each measured correction Auto applies: a starting point the
 * user refines, short of a full normalization. */
const AUTO_EXPOSURE_SHARE = 0.8;
const AUTO_CONTRAST_SHARE = 0.6;
const AUTO_WB_SHARE = 0.6;
const AUTO_CONTRAST_RANGE = [-10, 40] as const;
const AUTO_WB_MAX = 40;

/**
 * Auto grade from a frame's code values (RGBA) and the recipe that draws
 * them, the classic auto-tone pipeline measured through the real render:
 *
 * 1. Exposure — the slider that moves the rendered frame's log-average
 *    luminance AUTO_EXPOSURE_SHARE of the way to 18% middle grey.
 * 2. Contrast — auto-levels: clip 0.5% off each end of the rendered luma
 *    histogram and stretch what remains toward full range, expressed as the
 *    power about grey the contrast slider applies.
 * 3. White balance — grey-world: the temperature whose render brings the
 *    midtones' red and blue means together, applied in part.
 *
 * Saturation and hue are left alone. The recipe's grade carries the preset
 * and LUT the clip keeps, so the fit lands on the picture the clip shows.
 */
export function autoGrade(px: Uint8ClampedArray, recipe: ClipColorRecipe, userLut?: ParsedLut): ColorGrade | undefined {
  if (px.length < 4) return undefined;
  const render = recipeRender(px, recipe, userLut);
  const grade: ColorGrade = {};

  const start = Math.log(logAverage(render(undefined)));
  const target = start + AUTO_EXPOSURE_SHARE * (Math.log(0.18) - start);
  grade.exposure = Math.round(sliderRoot((e) => Math.log(logAverage(render({ exposure: e }))) - target));

  // Auto-levels on the exposed render. A near-flat histogram (solid color,
  // title card) carries no tonal-range signal: contrast stays.
  const exposed = render(normalizeGrade(grade));
  const hist = new Float64Array(256);
  for (let i = 0; i < exposed.length; i += 4) hist[Math.min(255, Math.round(lumaOf(exposed, i)))]++;
  const count = exposed.length >> 2;
  const percentile = (p: number) => {
    let acc = 0;
    for (let v = 0; v < 256; v++) {
      acc += hist[v];
      if (acc >= count * p) return v;
    }
    return 255;
  };
  const lo = percentile(0.005);
  const hi = percentile(0.995);
  if (hi - lo >= 16) {
    const power = 255 / (hi - lo);
    const [min, max] = AUTO_CONTRAST_RANGE;
    grade.contrast = Math.max(min, Math.min(max, Math.round(((power - 1) * AUTO_CONTRAST_SHARE * GRADE_MAX) / CONTRAST_POWER_AT_MAX)));
  }

  const toned = normalizeGrade(grade);
  const balanced = sliderRoot((t) => midtoneCast(render({ ...toned, temperature: t })));
  grade.temperature = Math.max(-AUTO_WB_MAX, Math.min(AUTO_WB_MAX, Math.round(balanced * AUTO_WB_SHARE)));
  return normalizeGrade(grade);
}

/* ------------------------------------------------------------------ */
/* Reference matching                                                  */
/* ------------------------------------------------------------------ */

/** The fields a match moves: exposure and contrast about grey, the two ends
 * of the range, white balance and saturation — the corrections that bring
 * one shot to another. Each is a slider the user reads afterward. */
const MATCH_FIELDS = ["exposure", "contrast", "highlights", "shadows", "temperature", "tint", "saturation"] as const;

/** Cost of a slider's distance from zero, in squared ΔL* units at full
 * throw: when two settings fit equally, the smaller one wins, so a field the
 * reference does not need stays at zero. */
const MATCH_PULL = 4;

/** Slider step of the finite differences the fit takes its slopes from. */
const MATCH_PROBE = 2;

/** The fit stops once no slider would move by more than this much. */
const MATCH_SETTLED = 0.25;
const MATCH_ITERATIONS = 40;

/** Longest stretch the fit works before it hands the thread back, so a match
 * in the tab never holds a preview frame. */
const FIT_SLICE_MS = 8;

/** Let the thread run other tasks. Headless runtimes have setImmediate,
 * which lets timers and I/O run first; a page posts a message, which runs
 * like a zero timer without the clamping a background tab applies to timers. */
function nextTask(): Promise<void> {
  return new Promise((resolve) => {
    if (typeof setImmediate === "function") {
      setImmediate(resolve);
      return;
    }
    const ch = new MessageChannel();
    ch.port1.onmessage = () => {
      ch.port1.close();
      resolve();
    };
    ch.port2.postMessage(null);
  });
}

/** The stats of a frame rendered with a candidate grade. */
export type StatsRender = (grade: ColorGrade | undefined) => ColorStats | undefined;

/** How far apart two frames read, as residuals in CIELAB units: the
 * lightness distribution probe by probe, and each tonal band's cast and
 * spread weighted by the share of the reference it holds — the moments a Lab
 * color transfer matches, read per band so a split tone counts too. */
function statsResiduals(a: ColorStats, b: ColorStats): number[] {
  const out = a.lightness.map((l, i) => l - b.lightness[i]);
  for (let i = 0; i < b.tones.length; i++) {
    const p = a.tones[i];
    const q = b.tones[i];
    const w = Math.sqrt(TONE_BANDS.length * q.share);
    out.push(w * (p.a - q.a), w * (p.b - q.b), w * (p.spreadA - q.spreadA), w * (p.spreadB - q.spreadB));
  }
  return out;
}

/** Solve A x = y for a small dense system by Gaussian elimination with
 * partial pivoting; null when A is singular. */
function solve(A: number[][], y: number[]): number[] | null {
  const n = y.length;
  const m = A.map((row, i) => [...row, y[i]]);
  for (let c = 0; c < n; c++) {
    let pivot = c;
    for (let r = c + 1; r < n; r++) if (Math.abs(m[r][c]) > Math.abs(m[pivot][c])) pivot = r;
    if (Math.abs(m[pivot][c]) < 1e-12) return null;
    [m[c], m[pivot]] = [m[pivot], m[c]];
    for (let r = c + 1; r < n; r++) {
      const f = m[r][c] / m[c][c];
      for (let k = c; k <= n; k++) m[r][k] -= f * m[c][k];
    }
  }
  const x = new Array<number>(n).fill(0);
  for (let r = n - 1; r >= 0; r--) {
    let v = m[r][n];
    for (let k = r + 1; k < n; k++) v -= m[r][k] * x[k];
    x[r] = v / m[r][r];
  }
  return x;
}

/** A StatsRender over a frame's code values (RGBA) and the recipe that
 * draws them: recipeRender, measured. */
export function recipeStatsRender(px: Uint8ClampedArray, recipe: ClipColorRecipe): StatsRender {
  const render = recipeRender(px, recipe);
  return (grade) => colorStatsFromImageData(render(grade));
}

/**
 * The grade that brings a frame to `reference`, fitted in the grade's own
 * sliders: Levenberg–Marquardt least squares over MATCH_FIELDS, every try
 * rendered through `render` and scored by statsResiduals in CIELAB, with a
 * light pull toward zero on each slider. `strength` (0..1) scales the fitted
 * sliders — for a reference whose content differs from the clip's (a bright
 * window for a dark room), where the full match lifts or crushes what the
 * reference never had. Returns undefined when the frames already agree.
 * The fit runs in slices of FIT_SLICE_MS between other tasks.
 */
export async function matchGrade(render: StatsRender, reference: ColorStats, strength = 1): Promise<ColorGrade | undefined> {
  const k = Math.max(0, Math.min(1, strength));
  if (k === 0) return undefined;
  const gradeOf = (p: number[]): ColorGrade => Object.fromEntries(MATCH_FIELDS.map((f, i) => [f, p[i]]));
  const pull = Math.sqrt(MATCH_PULL) / GRADE_MAX;
  let sliceStart = performance.now();
  const residuals = async (p: number[]): Promise<number[] | null> => {
    if (performance.now() - sliceStart > FIT_SLICE_MS) {
      await nextTask();
      sliceStart = performance.now();
    }
    const stats = render(normalizeGrade(gradeOf(p)));
    return stats ? [...statsResiduals(stats, reference), ...p.map((v) => pull * v)] : null;
  };
  const sumSq = (r: number[]) => r.reduce((a, v) => a + v * v, 0);
  const clampSlider = (v: number) => Math.max(-GRADE_MAX, Math.min(GRADE_MAX, v));

  // Levenberg–Marquardt: slopes by finite differences, a damped
  // Gauss–Newton step, damping eased after a step that helps and raised
  // after one that does not.
  let p = MATCH_FIELDS.map(() => 0);
  let r = await residuals(p);
  if (!r) return undefined;
  let damping = 1e-2;
  for (let it = 0; it < MATCH_ITERATIONS; it++) {
    const J: number[][] = [];
    for (let j = 0; j < p.length; j++) {
      const q = [...p];
      q[j] = p[j] + MATCH_PROBE <= GRADE_MAX ? p[j] + MATCH_PROBE : p[j] - MATCH_PROBE;
      const rq = (await residuals(q)) ?? r;
      J.push(rq.map((x, i) => (x - r![i]) / (q[j] - p[j])));
    }
    const A = J.map((ci) => J.map((cj) => ci.reduce((a, x, i) => a + x * cj[i], 0)));
    const g = J.map((ci) => ci.reduce((a, x, i) => a + x * r![i], 0));
    let stepped = false;
    let largest = 0;
    while (damping < 1e6) {
      const damped = A.map((row, i) => row.map((v, j) => (i === j ? v * (1 + damping) + 1e-9 : v)));
      const delta = solve(damped, g.map((v) => -v));
      if (!delta) break;
      const next = p.map((v, i) => clampSlider(v + delta[i]));
      largest = Math.max(...next.map((v, i) => Math.abs(v - p[i])));
      const rn = await residuals(next);
      if (rn && sumSq(rn) < sumSq(r)) {
        p = next;
        r = rn;
        damping = Math.max(1e-6, damping / 3);
        stepped = true;
        break;
      }
      damping *= 4;
    }
    if (!stepped || largest < MATCH_SETTLED) break;
  }

  const scaled: ColorGrade = {};
  MATCH_FIELDS.forEach((f, i) => {
    const v = Math.round(p[i] * k);
    if (v) scaled[f] = v;
  });
  return normalizeGrade(scaled);
}