Skip to content

Open source CapCut alternative.

TypeScript
19.6 KB
Raw Blame
/** The camera's move over a stretch of a source: each frame's zoom, shift and
 * turn against the stretch's first frame, found by warping that frame until
 * it lands on this one. A punch-in, a beat zoom, a shake or a slow push in a
 * reference keys as a clip's pose track (set_clip_keyframes) from these
 * numbers, and holdsStill tells a picture that holds under the move — a
 * freeze the template zooms and shakes — from a live one.
 * Pure data in, pure data out; sourceMeasure.ts feeds it decoded frames. */

import type { Pixels } from "./color";

/** A frame as luma, one float a pixel. */
export interface Gray {
  width: number;
  height: number;
  data: Float32Array;
}

/** How a frame sits against the reference frame: `scale` > 1 is zoomed in,
 * `dx`/`dy` move the picture's centre (frame fractions, + is right and
 * down), `rotation` turns it clockwise in degrees, and `residual` is the mean
 * per-pixel difference left after the warp, 0..255. */
export interface CameraPose {
  scale: number;
  dx: number;
  dy: number;
  rotation: number;
  residual: number;
  /** A second layer moving its own way: a cutout held over a background
   * that shakes, or one pulsing over a still. Its pose is read at half size,
   * and `share` is the part of the matched patches it holds. */
  second?: { scale: number; dx: number; dy: number; rotation: number; share: number };
}

/** The long side frames are read at for the camera: a pixel is half a
 * percent of it, and a patch match lands to a tenth of one. */
export const CAMERA_LONG_SIDE = 192;

export function grayOf(px: Pixels): Gray {
  const data = new Float32Array(px.width * px.height);
  for (let i = 0; i < data.length; i++) {
    data[i] = 0.2126 * px.data[i * 4] + 0.7152 * px.data[i * 4 + 1] + 0.0722 * px.data[i * 4 + 2];
  }
  return { width: px.width, height: px.height, data };
}

/** Patches across the frame, cols × rows; the camera is fitted to the ones
 * that agree, so a subject crossing some of them is outvoted. */
const GRID = { cols: 10, rows: 6 };
/** A patch's half side, and how far it is searched each way past where a
 * pose puts it: wide on the half-size pass that catches a shake's jump, close
 * on the full-size one that places it to a tenth of a pixel. */
const PATCH_R = 6;
const COARSE_R = 8;
const FINE_R = 3;
/** A patch flatter than this (high-passed std) has nothing to match: sky,
 * snow, a blown-out flash. */
const MIN_TEXTURE = 3;
/** Frames the fit needs this many agreeing patches to trust. */
const MIN_PATCHES = 6;

/** The frame minus its own blur: edges and texture without the light over
 * them, so a vignette fixed to the screen, a sky's gradient and a beat's
 * exposure pulse do not pull the fit. */
function highPass(g: Gray, r = 4): Gray {
  const { width: w, height: h } = g;
  const integral = new Float64Array((w + 1) * (h + 1));
  for (let y = 0; y < h; y++) {
    let row = 0;
    for (let x = 0; x < w; x++) {
      row += g.data[y * w + x];
      integral[(y + 1) * (w + 1) + x + 1] = integral[y * (w + 1) + x + 1] + row;
    }
  }
  const data = new Float32Array(w * h);
  for (let y = 0; y < h; y++) {
    const y0 = Math.max(0, y - r);
    const y1 = Math.min(h, y + r + 1);
    for (let x = 0; x < w; x++) {
      const x0 = Math.max(0, x - r);
      const x1 = Math.min(w, x + r + 1);
      const sum = integral[y1 * (w + 1) + x1] - integral[y0 * (w + 1) + x1] - integral[y1 * (w + 1) + x0] + integral[y0 * (w + 1) + x0];
      data[y * w + x] = g.data[y * w + x] - sum / ((x1 - x0) * (y1 - y0));
    }
  }
  return { width: w, height: h, data };
}

/** Half the size, each pixel the mean of four. */
function halve(g: Gray): Gray {
  const w = Math.max(1, Math.floor(g.width / 2));
  const h = Math.max(1, Math.floor(g.height / 2));
  const data = new Float32Array(w * h);
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      const i = 2 * y * g.width + 2 * x;
      data[y * w + x] = (g.data[i] + g.data[i + 1] + g.data[i + g.width] + g.data[i + g.width + 1]) / 4;
    }
  }
  return { width: w, height: h, data };
}

function sample(g: Gray, x: number, y: number): number {
  if (x < 0 || y < 0 || x > g.width - 1.001 || y > g.height - 1.001) return NaN;
  const x0 = Math.floor(x);
  const y0 = Math.floor(y);
  const fx = x - x0;
  const fy = y - y0;
  const i = y0 * g.width + x0;
  return (
    (g.data[i] * (1 - fx) + g.data[i + 1] * fx) * (1 - fy) + (g.data[i + g.width] * (1 - fx) + g.data[i + g.width + 1] * fx) * fy
  );
}

/** Mean absolute difference between `cur` and `ref` warped by the pose (shift
 * in pixels of these frames), over the pixels whose source lies inside `ref`.
 * Infinity when too little overlaps. */
function cost(ref: Gray, cur: Gray, s: number, dxPx: number, dyPx: number, rotDeg: number, step: number): number {
  const { width: w, height: h } = cur;
  const cx = (w - 1) / 2;
  const cy = (h - 1) / 2;
  const th = (rotDeg * Math.PI) / 180;
  const cos = Math.cos(th) / s;
  const sin = Math.sin(th) / s;
  let sum = 0;
  let n = 0;
  for (let y = 0; y < h; y += step) {
    for (let x = 0; x < w; x += step) {
      // The reference point that lands on (x, y): undo the shift, the turn
      // and the zoom about the centre.
      const px = x - cx - dxPx;
      const py = y - cy - dyPx;
      const v = sample(ref, cx + cos * px + sin * py, cy - sin * px + cos * py);
      if (Number.isNaN(v)) continue;
      sum += Math.abs(v - cur.data[y * w + x]);
      n++;
    }
  }
  // A warp that leaves less than a third of the frame overlapping proves nothing.
  return n * step * step < (w * h) / 3 ? Infinity : sum / n;
}

interface Pose {
  s: number;
  rot: number;
  tx: number;
  ty: number;
}

/** Where a point of the reference (from the centre) lands under a pose. */
function place(p: Pose, x: number, y: number): [number, number] {
  const th = (p.rot * Math.PI) / 180;
  const a = p.s * Math.cos(th);
  const b = p.s * Math.sin(th);
  return [a * x - b * y + p.tx, b * x + a * y + p.ty];
}

/** A match within this many pixels of where a pose puts it agrees with it. */
const AGREE_PX = 1;

/** The least-squares zoom, turn and shift over the pairs `idx`:
 * q = [a -b; b a] p + t, solved with the means taken out. */
function solvePose(from: [number, number][], to: [number, number][], idx: number[]): Pose | null {
  let mpx = 0, mpy = 0, mqx = 0, mqy = 0;
  for (const i of idx) {
    mpx += from[i][0]; mpy += from[i][1]; mqx += to[i][0]; mqy += to[i][1];
  }
  mpx /= idx.length; mpy /= idx.length; mqx /= idx.length; mqy /= idx.length;
  let saa = 0, sab = 0, spp = 0;
  for (const i of idx) {
    const px = from[i][0] - mpx, py = from[i][1] - mpy;
    const qx = to[i][0] - mqx, qy = to[i][1] - mqy;
    saa += px * qx + py * qy;
    sab += px * qy - py * qx;
    spp += px * px + py * py;
  }
  if (spp <= 0) return null;
  const a = saa / spp;
  const b = sab / spp;
  return { s: Math.hypot(a, b), rot: (Math.atan2(b, a) * 180) / Math.PI, tx: mqx - (a * mpx - b * mpy), ty: mqy - (b * mpx + a * mpy) };
}

/** The pairs a pose agrees with. */
function agreeing(pose: Pose, from: [number, number][], to: [number, number][], px: number): number[] {
  return from.flatMap((p, i) => {
    const [x, y] = place(pose, p[0], p[1]);
    return Math.hypot(x - to[i][0], y - to[i][1]) <= px ? [i] : [];
  });
}

/** The zoom, turn and shift that carry `from` onto `to` (points from the
 * centre) by consensus: every two pairs propose a pose, the one most pairs
 * agree with wins, and it is refitted over them. Snow, sky and a subject
 * moving through mismatch at random and agree with nothing. Null with fewer
 * than MIN_PATCHES agreeing. */
function fitPose(from: [number, number][], to: [number, number][], px = AGREE_PX): { pose: Pose; kept: number; agree: number[] } | null {
  if (from.length < MIN_PATCHES) return null;
  let best: number[] = [];
  for (let i = 0; i < from.length; i++) {
    for (let j = i + 1; j < from.length; j++) {
      // Two points too close together cannot tell a zoom or a turn.
      if (Math.hypot(from[i][0] - from[j][0], from[i][1] - from[j][1]) < 8 * px) continue;
      const pose = solvePose(from, to, [i, j]);
      if (!pose || pose.s < 0.5 || pose.s > 2) continue;
      const agree = agreeing(pose, from, to, px);
      if (agree.length > best.length) best = agree;
    }
  }
  if (best.length < MIN_PATCHES) return null;
  let pose = solvePose(from, to, best)!;
  let agree = agreeing(pose, from, to, px);
  if (agree.length >= MIN_PATCHES) pose = solvePose(from, to, agree)!;
  else agree = best;
  return { pose, kept: agree.length, agree };
}

interface Patch {
  /** Its centre from the frame's centre. */
  x: number;
  y: number;
  pixels: Float32Array;
}

/** The textured patches of the reference frame, on the grid. */
function patchesOf(g: Gray): Patch[] {
  const margin = PATCH_R + 2;
  const cx = (g.width - 1) / 2;
  const cy = (g.height - 1) / 2;
  const out: Patch[] = [];
  for (let r = 0; r < GRID.rows; r++) {
    for (let c = 0; c < GRID.cols; c++) {
      const x = Math.round(margin + ((g.width - 2 * margin) * (c + 0.5)) / GRID.cols);
      const y = Math.round(margin + ((g.height - 2 * margin) * (r + 0.5)) / GRID.rows);
      const pixels = new Float32Array((2 * PATCH_R + 1) ** 2);
      let k = 0, sum = 0, sq = 0;
      for (let v = -PATCH_R; v <= PATCH_R; v++) {
        for (let u = -PATCH_R; u <= PATCH_R; u++) {
          const p = g.data[(y + v) * g.width + x + u];
          pixels[k++] = p;
          sum += p;
          sq += p * p;
        }
      }
      const std = Math.sqrt(Math.max(0, sq / k - (sum / k) ** 2));
      if (std >= MIN_TEXTURE) out.push({ x: x - cx, y: y - cy, pixels });
    }
  }
  return out;
}

/** Where a reference patch sits in `cur`, searched around where `pose` puts
 * it, with the patch zoomed and turned as the pose has it; null when it runs
 * off the frame or its best match is no better than its neighbours'. */
function matchPatch(cur: Gray, patch: Patch, pose: Pose, SEARCH_R: number): [number, number] | null {
  const cx = (cur.width - 1) / 2;
  const cy = (cur.height - 1) / 2;
  const [px, py] = place(pose, patch.x, patch.y);
  const th = (pose.rot * Math.PI) / 180;
  const a = pose.s * Math.cos(th);
  const b = pose.s * Math.sin(th);
  const n = 2 * SEARCH_R + 1;
  const costs = new Float32Array(n * n).fill(Infinity);
  let best = Infinity;
  let bi = -1;
  for (let oy = -SEARCH_R; oy <= SEARCH_R; oy++) {
    for (let ox = -SEARCH_R; ox <= SEARCH_R; ox++) {
      let sum = 0;
      let k = 0;
      let off = false;
      for (let v = -PATCH_R; v <= PATCH_R && !off; v++) {
        for (let u = -PATCH_R; u <= PATCH_R; u++) {
          const val = sample(cur, cx + px + ox + a * u - b * v, cy + py + oy + b * u + a * v);
          if (Number.isNaN(val)) {
            off = true;
            break;
          }
          sum += Math.abs(val - patch.pixels[k++]);
        }
      }
      if (off) continue;
      const i = (oy + SEARCH_R) * n + ox + SEARCH_R;
      costs[i] = sum;
      if (sum < best) {
        best = sum;
        bi = i;
      }
    }
  }
  if (bi < 0) return null;
  const bx = (bi % n) - SEARCH_R;
  const by = Math.floor(bi / n) - SEARCH_R;
  // A best on the search's edge may lie past it.
  if (Math.abs(bx) === SEARCH_R || Math.abs(by) === SEARCH_R) return null;
  // The parabola through the best and its neighbours puts it between pixels.
  const sub = (l: number, c: number, r: number) => {
    const d = l - 2 * c + r;
    return d > 0 && Number.isFinite(d) ? Math.max(-0.5, Math.min(0.5, (l - r) / (2 * d))) : 0;
  };
  const at = (x: number, y: number) => costs[(y + SEARCH_R) * n + x + SEARCH_R];
  return [
    px + bx + sub(at(bx - 1, by), best, at(bx + 1, by)),
    py + by + sub(at(bx, by - 1), best, at(bx, by + 1)),
  ];
}

/** The pose that carries `patches` of the reference onto `cur`, searched
 * `reach` pixels around where `start` puts each one. */
function matchAll(cur: Gray, patches: Patch[], start: Pose, reach: number) {
  const from: [number, number][] = [];
  const to: [number, number][] = [];
  for (const p of patches) {
    const hit = matchPatch(cur, p, start, reach);
    if (hit) {
      from.push([p.x, p.y]);
      to.push(hit);
    }
  }
  return { from, to };
}

function fitFrom(cur: Gray, patches: Patch[], start: Pose, reach: number, px = AGREE_PX) {
  const { from, to } = matchAll(cur, patches, start, reach);
  return fitPose(from, to, px);
}

/** The layers the matches split into: the pose most of them agree with, and
 * the pose most of the rest agree with, when enough do. */
function layersOf(cur: Gray, patches: Patch[], start: Pose, reach: number, px: number) {
  const { from, to } = matchAll(cur, patches, start, reach);
  const first = fitPose(from, to, px);
  if (!first) return [];
  const taken = new Set(first.agree);
  const rest = from.flatMap((_, i) => (taken.has(i) ? [] : [i]));
  const second = fitPose(rest.map((i) => from[i]), rest.map((i) => to[i]), px);
  const share = (n: number) => n / from.length;
  return second && apart(first.pose, second.pose, cur, 2 * px)
    ? [{ pose: first.pose, share: share(first.kept) }, { pose: second.pose, share: share(second.kept) }]
    : [{ pose: first.pose, share: share(first.kept) }];
}

/** Whether two poses put some corner of the frame more than `px` apart. */
function apart(a: Pose, b: Pose, g: Gray, px: number): boolean {
  const hw = g.width / 2;
  const hh = g.height / 2;
  return [[-hw, -hh], [hw, -hh], [-hw, hh], [hw, hh], [0, 0]].some(([x, y]) => {
    const [ax, ay] = place(a, x, y);
    const [bx, by] = place(b, x, y);
    return Math.hypot(ax - bx, ay - by) > px;
  });
}

/** How far apart two poses put the frame's corners, at most. */
function gap(a: Pose, b: Pose, g: Gray): number {
  const hw = g.width / 2;
  const hh = g.height / 2;
  return Math.max(
    ...[[-hw, -hh], [hw, -hh], [-hw, hh], [hw, hh]].map(([x, y]) => {
      const [ax, ay] = place(a, x, y);
      const [bx, by] = place(b, x, y);
      return Math.hypot(ax - bx, ay - by);
    })
  );
}

/** Layers holding shares this close are near even. */
const EVEN_SHARE = 0.1;
/** A second layer holds at least this share of the matched patches in a
 * frame, and shows in at least SECOND_FRAMES of the stretch's frames: less
 * is a few patches mismatching together, not a layer. */
const SECOND_SHARE = 0.25;
const SECOND_FRAMES = 0.25;

const half = (p: Pose): Pose => ({ ...p, tx: p.tx / 2, ty: p.ty / 2 });
const REST: Pose = { s: 1, rot: 0, tx: 0, ty: 0 };

/** Each frame's pose against `frames[0]`, read at CAMERA_LONG_SIDE: the
 * reference frame's textured patches are found again in each frame and one
 * zoom, turn and shift is fitted to the patches that agree. A half-size pass
 * from the frame before's pose, and from rest, catches a jump; the better
 * fit is placed at full size. A frame too blurred or too changed to fit
 * keeps the pose before it, with residual Infinity. */
export function cameraPath(frames: Gray[]): CameraPose[] {
  if (frames.length === 0) return [];
  const ref = highPass(frames[0]);
  const refHalf = highPass(halve(frames[0]), 2);
  const patches = patchesOf(ref);
  const patchesHalf = patchesOf(refHalf);
  const out: CameraPose[] = [{ scale: 1, dx: 0, dy: 0, rotation: 0, residual: 0 }];
  let prev: Pose = REST;
  for (let i = 1; i < frames.length; i++) {
    const cur = highPass(frames[i]);
    const curHalf = highPass(halve(frames[i]), 2);
    // The layers seen from the frame before and from rest. The camera is the
    // one holding most of the picture — of two near even, the one carrying
    // on from the frame before — and another holding a fair share of its
    // own is the second layer.
    const layers = [...layersOf(curHalf, patchesHalf, half(prev), COARSE_R, AGREE_PX * 0.75), ...layersOf(curHalf, patchesHalf, REST, COARSE_R, AGREE_PX * 0.75)]
      .sort((a, b) => b.share - a.share);
    const main = layers
      .filter((l) => l.share >= layers[0].share - EVEN_SHARE)
      .sort((a, b) => gap(a.pose, half(prev), curHalf) - gap(b.pose, half(prev), curHalf))[0];
    const other = main && layers.find((l) => l.share >= SECOND_SHARE && apart(l.pose, main.pose, curHalf, 1.5));
    const start = main ? { ...main.pose, tx: main.pose.tx * 2, ty: main.pose.ty * 2 } : prev;
    const fit = fitFrom(cur, patches, start, FINE_R);
    if (!fit) {
      out.push({ ...out[out.length - 1], residual: Infinity });
      continue;
    }
    prev = fit.pose;
    out.push({
      scale: fit.pose.s,
      dx: fit.pose.tx / cur.width,
      dy: fit.pose.ty / cur.height,
      rotation: fit.pose.rot,
      residual: cost(ref, cur, fit.pose.s, fit.pose.tx, fit.pose.ty, fit.pose.rot, 2),
      ...(other
        ? {
            second: {
              scale: other.pose.s,
              dx: other.pose.tx / curHalf.width,
              dy: other.pose.ty / curHalf.height,
              rotation: other.pose.rot,
              share: other.share,
            },
          }
        : {}),
    });
  }
  const layered = out.filter((p) => p.second).length;
  if (layered < SECOND_FRAMES * (out.length - 1)) for (const p of out) delete p.second;
  return out;
}

/** Two frames the camera holds the same way differ by less than this a pixel
 * when the picture under it is one frame: a returning live shot has moved on. */
export const STILL_RESIDUAL = 2;

/** Poses this close show the same part of the picture the same way. */
const SAME_POSE = { scale: 0.004, d: 0.003, rotation: 0.2 };

/** Whether one picture holds under the whole move — a freeze the template
 * zooms or shakes — by the frames where the camera comes back to a pose it
 * held at least two frames before: a frozen picture is the same frame again,
 * a live one has moved on. The warp's own residual cannot tell, since a
 * screen-fixed vignette or grain over a zoomed freeze leaves one too. Null
 * when the camera never returns, as in a steady push. */
export function holdsStill(frames: Gray[], path: CameraPose[]): boolean | null {
  const diffs: number[] = [];
  for (let i = 2; i < frames.length; i++) {
    for (let j = 0; j <= i - 2; j++) {
      const a = path[i];
      const b = path[j];
      if (
        Math.abs(a.scale - b.scale) < SAME_POSE.scale &&
        Math.abs(a.dx - b.dx) < SAME_POSE.d &&
        Math.abs(a.dy - b.dy) < SAME_POSE.d &&
        Math.abs(a.rotation - b.rotation) < SAME_POSE.rotation
      ) {
        diffs.push(cost(frames[j], frames[i], 1, 0, 0, 0, 1));
        break;
      }
    }
  }
  if (diffs.length < 2) return null;
  diffs.sort((x, y) => x - y);
  return diffs[Math.floor(diffs.length / 2)] < STILL_RESIDUAL;
}

/** The least a zoom must change the scale by before the point it holds still
 * is told: a 5% punch-in moves the picture too little to place it. */
const ANCHOR_ZOOM = 0.2;
/** How far, frame fractions, the moves may stray from a zoom about one point
 * on average: past it the camera slides as well and holds no point. */
const ANCHOR_FIT = 0.02;

/**
 * The frame point a zoom holds still, in frame fractions, or null when the
 * path zooms too little or slides too. A zoom about `a` carries the
 * picture's centre to a + s·(½ − a), so each frame's shift is (a − ½)·(1 − s)
 * and `a` falls out of a least-squares fit over every frame read.
 */
export function zoomAnchor(path: CameraPose[]): { x: number; y: number } | null {
  const read = path.filter((p) => Number.isFinite(p.residual));
  const scales = read.map((p) => p.scale);
  if (read.length < 3 || Math.max(...scales) / Math.min(...scales) < 1 + ANCHOR_ZOOM) return null;
  let kk = 0;
  let kx = 0;
  let ky = 0;
  for (const p of read) {
    const k = 1 - p.scale;
    kk += k * k;
    kx += k * p.dx;
    ky += k * p.dy;
  }
  const ox = kx / kk;
  const oy = ky / kk;
  let miss = 0;
  for (const p of read) miss += Math.hypot(p.dx - ox * (1 - p.scale), p.dy - oy * (1 - p.scale));
  if (miss / read.length > ANCHOR_FIT) return null;
  return { x: 0.5 + ox, y: 0.5 + oy };
}