Open source CapCut alternative.
TypeScript
// How far a replica's frame is from the frame it copies, as numbers a model
// can act on. A picture of the two side by side shows that something is off;
// a score says how much, a grid says where, and a sweep of scores says when.
// Every score reads frames at the same small size, so a 4 in one call and a
// 4 in the next mean the same thing.
/** How compare_to_source reads: a few moments as pictures with their scores,
* or a sweep of scores over a span with no pictures. */
export const COMPARE_MODES = ["moments", "sweep"] as const;
/** The most moments one picture call reads: two frames drawn and one picture
* composed each, small enough to keep the reply readable. */
export const MAX_COMPARE = 8;
/** The score a replica aims for: under it, two frames read as the same
* picture to the eye. */
export const SWEEP_TARGET = 5;
/** Long side of the frame a score reads. Small enough to sweep a cut frame by
* frame, large enough that a title or a shape still moves the number. */
export const SCORE_LONG_SIDE = 96;
/** The grid's split per side: 4×4 cells, row 0 at the top. */
const GRID = 4;
/** How much better a neighbouring source frame has to match before the
* difference is called timing: under three quarters of the moment's own
* score, and at least this many points under it. */
const SHIFT_RATIO = 0.75;
const SHIFT_MIN_GAIN = 1;
/** A run of bad samples survives one good sample in its middle. */
const STRETCH_GAP = 1;
const round1 = (v: number) => Math.round(v * 10) / 10;
/** Mean absolute difference over R, G and B, 0 (identical) to 255. */
export function meanDiff(cut: Uint8ClampedArray, source: Uint8ClampedArray): number {
let sum = 0;
for (let i = 0; i < cut.length; i += 4) {
sum += Math.abs(cut[i] - source[i]) + Math.abs(cut[i + 1] - source[i + 1]) + Math.abs(cut[i + 2] - source[i + 2]);
}
return cut.length > 0 ? sum / ((cut.length / 4) * 3) : 0;
}
/** The score and where it comes from: `grid[row][col]` is each cell's own
* mean difference, rounded, so a title in the wrong place reads as two hot
* cells and a wrong background as a warm grid. */
export function diffPixels(
cut: Uint8ClampedArray,
source: Uint8ClampedArray,
width: number,
height: number
): { diff: number; grid: number[][] } {
const sums = new Float64Array(GRID * GRID);
const counts = new Float64Array(GRID * GRID);
let total = 0;
// One pass: every pixel adds to the total and to its cell.
for (let y = 0; y < height; y++) {
const row = Math.min(GRID - 1, Math.floor((y * GRID) / height));
for (let x = 0; x < width; x++) {
const i = (y * width + x) * 4;
const d =
Math.abs(cut[i] - source[i]) + Math.abs(cut[i + 1] - source[i + 1]) + Math.abs(cut[i + 2] - source[i + 2]);
const cell = row * GRID + Math.min(GRID - 1, Math.floor((x * GRID) / width));
sums[cell] += d;
counts[cell] += 3;
total += d;
}
}
const grid = Array.from({ length: GRID }, (_, r) =>
Array.from({ length: GRID }, (_, c) => {
const cell = r * GRID + c;
return counts[cell] > 0 ? Math.round(sums[cell] / counts[cell]) : 0;
})
);
return { diff: width * height > 0 ? total / (width * height * 3) : 0, grid };
}
/** The neighbouring source frame that matches clearly better than the moment
* itself, if one does. `shift` is how far from the moment that frame sits, so
* a positive shift means the cut shows early what the source shows later. */
export function bestShift(
base: number,
candidates: { shift: number; diff: number }[]
): { shift: number; diff: number } | undefined {
let best: { shift: number; diff: number } | undefined;
for (const c of candidates) {
if (!best || c.diff < best.diff) {
best = c;
}
}
if (!best || best.diff >= base * SHIFT_RATIO || base - best.diff < SHIFT_MIN_GAIN) {
return undefined;
}
return best;
}
/**
* Whether a run of sweep samples matches the source better a few steps away.
* `near` holds, per sample, its cut frame scored against the source sample k
* steps off for k in -reach..reach (NaN where there is none), so a stretch
* whose move lands a frame late reads as one shift for the whole stretch.
*/
export function runShift(
near: Float32Array,
reach: number,
first: number,
last: number,
step: number
): { shift: number; diff: number } | undefined {
const width = reach * 2 + 1;
// The run's mean score at each offset, over the samples that have one.
const meanAt = (k: number) => {
let sum = 0;
let n = 0;
for (let i = first; i <= last; i++) {
const v = near[i * width + k + reach];
if (Number.isNaN(v)) {
continue;
}
sum += v;
n++;
}
return n > 0 ? sum / n : NaN;
};
const base = meanAt(0);
const candidates: { shift: number; diff: number }[] = [];
for (let k = -reach; k <= reach; k++) {
const diff = meanAt(k);
if (k === 0 || Number.isNaN(diff)) {
continue;
}
candidates.push({ shift: Math.round(k * step * 1000) / 1000, diff: round1(diff) });
}
return Number.isNaN(base) ? undefined : bestShift(base, candidates);
}
/** Nearest-rank quantile of an ascending list. */
const quantile = (sorted: number[], p: number) => sorted[Math.max(0, Math.min(sorted.length - 1, Math.ceil(p * sorted.length) - 1))];
/** The shape of a sweep's scores: the typical frame, the bad tail, the worst. */
export function sweepStats(scores: number[]): { median: number; p95: number; max: number } {
const sorted = [...scores].sort((a, b) => a - b);
return {
median: round1(quantile(sorted, 0.5)),
p95: round1(quantile(sorted, 0.95)),
max: round1(sorted[sorted.length - 1] ?? 0),
};
}
/**
* The stretches of a sweep most worth a look, worst first.
*
* A sample is bad when it is over the target and at least as bad as the
* median, so a cut that is off by the same amount everywhere reads as one
* long stretch and a mostly good cut points at its outliers. Neighbouring bad
* samples join into one stretch, and stretches rank by how far over the floor
* they run in total: one frame far off and a long run a little off both
* surface. `to` is the end of the last bad sample's step.
*/
export function worstStretches(
samples: { at: number; diff: number }[],
step: number,
target: number,
limit: number
): {
from: number;
to: number;
diff: number;
peak: number;
peakAt: number;
peakIndex: number;
first: number;
last: number;
weight: number;
}[] {
const median = quantile(samples.map((s) => s.diff).sort((a, b) => a - b), 0.5) ?? 0;
const floor = Math.max(target, median);
const bad = (d: number) => d > target && d >= median;
// Runs of bad samples, bridging gaps of up to STRETCH_GAP good ones.
const runs: { first: number; last: number }[] = [];
for (let i = 0; i < samples.length; i++) {
if (!bad(samples[i].diff)) {
continue;
}
const open = runs[runs.length - 1];
if (open && i - open.last <= STRETCH_GAP + 1) {
open.last = i;
continue;
}
runs.push({ first: i, last: i });
}
// Each run measured over every sample inside it, the bridged ones too.
const stretches = runs.map(({ first, last }) => {
let sum = 0;
let weight = 0;
let peakIndex = first;
for (let i = first; i <= last; i++) {
sum += samples[i].diff;
weight += Math.max(0, samples[i].diff - floor);
if (samples[i].diff > samples[peakIndex].diff) {
peakIndex = i;
}
}
return {
from: samples[first].at,
to: samples[last].at + step,
diff: round1(sum / (last - first + 1)),
peak: round1(samples[peakIndex].diff),
peakAt: samples[peakIndex].at,
peakIndex,
first,
last,
weight,
};
});
return stretches.sort((a, b) => b.weight - a.weight).slice(0, limit);
}
export type Edge = "top" | "bottom" | "left" | "right";
/**
* The edges of a frame a difference runs the whole length of while its
* middle matches: a border, a band or a letterbox one picture has and the
* other lacks. Thin bars move a frame's mean little, so this reads the grid:
* every cell along the edge over the target, and the middle cells under a
* third of that edge's least. `diff` is the mean over those edges' cells.
*/
export function edgeBand(grid: number[][], target: number): { edges: Edge[]; diff: number } | null {
const n = grid.length;
if (n < 3 || grid.some((row) => row.length !== n)) return null;
const middle: number[] = [];
for (let r = 1; r < n - 1; r++) for (let c = 1; c < n - 1; c++) middle.push(grid[r][c]);
const calm = middle.reduce((a, b) => a + b, 0) / middle.length;
const lines: [Edge, number[]][] = [
["top", grid[0]],
["bottom", grid[n - 1]],
["left", grid.map((row) => row[0])],
["right", grid.map((row) => row[n - 1])],
];
const hot = lines.filter(([, cells]) => Math.min(...cells) > target && calm * 3 <= Math.min(...cells));
if (hot.length === 0) return null;
const cells = hot.flatMap(([, c]) => c);
return { edges: hot.map(([e]) => e), diff: round1(cells.reduce((a, b) => a + b, 0) / cells.length) };
}
/** How far a pixel stands off a title box's ground before it counts as ink. */
const INK_MIN = 30;
/** The share of a title box's pixels its ink is read from, the furthest off
* the ground: the cores of the strokes, not their soft edges. */
const INK_SHARE = 0.08;
/** How much of the way from its ground to the other's ink a read may sit:
* thinner or smaller letters read part way, never past the colour itself. */
const INK_BLEND = [0.3, 1.1] as const;
/** The ring around a title's box its ground is read from, as a share of the
* box's height, and never under 2 px: a small label fills most of its own
* box, so the box alone would read its letters as the ground. */
const GROUND_RING = 0.25;
/** How far apart the grounds under a title may be for its letters to be
* compared: past it the title sits on something else in one frame — a card's
* edge, another shape — which is the frame score's to find, not the ink's. */
const GROUND_SLACK = 48;
type Rgb3 = [number, number, number];
/** A title's letters as a frame shows them: their colour, null where none
* stand off the ground, and the ground's. */
export type Ink = { ink: Rgb3 | null; ground: Rgb3 };
/** How far apart two colours are: the largest of their channel differences. */
export function inkDiff(a: Rgb3, b: Rgb3): number {
return Math.max(Math.abs(a[0] - b[0]), Math.abs(a[1] - b[1]), Math.abs(a[2] - b[2]));
}
/**
* How far the source's letters are from ours in colour. Letters a little
* thinner, smaller or softer than ours read as our colour part way into their
* ground, so the source's ink is held against the nearest blend of ours into
* the source's ground: white letters read pale over purple are the same
* white, black ones where ours are white are not. Letters only one side
* shows are off by how far they stand off its ground. Null when the two sit
* on different grounds.
*/
export function inkOff(cut: Ink, source: Ink): number | null {
if (inkDiff(cut.ground, source.ground) > GROUND_SLACK) {
return null;
}
if (!cut.ink || !source.ink) {
const shown = cut.ink ? cut : source;
return shown.ink ? inkDiff(shown.ink, shown.ground) : 0;
}
const dir = cut.ink.map((v, c) => v - cut.ground[c]);
const seen = source.ink.map((v, c) => v - source.ground[c]);
const len = dir.reduce((a, v) => a + v * v, 0);
const k = len > 0 ? Math.min(INK_BLEND[1], Math.max(INK_BLEND[0], dir.reduce((a, v, c) => a + v * seen[c], 0) / len)) : 1;
return inkDiff(source.ground.map((v, c) => v + dir[c] * k) as Rgb3, source.ink);
}
/**
* The colour a title's letters are drawn in, read off a frame: the ground is
* the median colour of a ring around the box, and the ink the mean of the
* pixels inside it furthest from that. A title's box is mostly ground, so this holds on a flat
* card and on footage alike, and it reads the letters' colour where a frame
* score at a sweep's size barely moves for it. Null when the box is outside
* the frame.
*/
export function inkColor(
px: Uint8ClampedArray,
w: number,
h: number,
box: { x: number; y: number; w: number; h: number }
): Ink | null {
const x0 = Math.max(0, Math.floor(box.x));
const y0 = Math.max(0, Math.floor(box.y));
const x1 = Math.min(w, Math.ceil(box.x + box.w));
const y1 = Math.min(h, Math.ceil(box.y + box.h));
if (x1 <= x0 || y1 <= y0) {
return null;
}
const at: number[] = [];
const inside: number[][] = [[], [], []];
for (let y = y0; y < y1; y++) {
for (let x = x0; x < x1; x++) {
const i = (y * w + x) * 4;
at.push(i);
for (let c = 0; c < 3; c++) inside[c].push(px[i + c]);
}
}
const pad = Math.max(2, Math.round(box.h * GROUND_RING));
const ring: number[][] = [[], [], []];
for (let y = Math.max(0, y0 - pad); y < Math.min(h, y1 + pad); y++) {
for (let x = Math.max(0, x0 - pad); x < Math.min(w, x1 + pad); x++) {
if (x >= x0 && x < x1 && y >= y0 && y < y1) continue;
const i = (y * w + x) * 4;
for (let c = 0; c < 3; c++) ring[c].push(px[i + c]);
}
}
const median = (v: number[]) => v.sort((a, b) => a - b)[v.length >> 1];
const ground = (ring[0].length > 0 ? ring : inside).map(median) as Rgb3;
const off = at
.map((i) => ({ i, d: inkDiff([px[i], px[i + 1], px[i + 2]], ground) }))
.filter((p) => p.d > INK_MIN)
.sort((a, b) => b.d - a.d)
.slice(0, Math.max(1, Math.ceil(at.length * INK_SHARE)));
if (off.length === 0) {
return { ink: null, ground };
}
const sum = [0, 0, 0];
for (const { i } of off) for (let c = 0; c < 3; c++) sum[c] += px[i + c];
return { ink: sum.map((v) => Math.round(v / off.length)) as Rgb3, ground };
}