Introduction

No background required. This book assumes you know nothing about programming, AI, or math beyond high-school basics. Every concept, line of code, and symbol is explained, and every code example is followed by the exact output it produces. If you've never written Python, read the 5-minute primer first.

The one-sentence idea

Kernel Temporal Segmentation (KTS) automatically chops a video into a small number of consistent pieces ("shots" or "scenes") by finding the moments where the picture changes a lot.

An everyday analogy

Imagine flipping through a photo album. Pages 1 to 10 are a beach trip, pages 11 to 18 are a birthday party, pages 19 to 25 are a hike. You can instantly spot the boundaries, the points where the photos suddenly start looking different. KTS does exactly this, automatically, for the frames of a video. The boundaries it finds are called change points.

Where it's used

KTS was introduced by Potapov, Douze, Harchaoui & Schmid in "Category-Specific Video Summarization" (ECCV 2014). It became a standard first step in video summarization: before a computer decides which parts of a video are worth keeping, it first splits the video into shots, and KTS is the tool that does the splitting. It's used to prepare well-known datasets like TVSum and SumMe.

How a video becomes numbers

A computer can't "see" a picture the way we do: it works with numbers. So each video frame is turned into a list of numbers called a feature vector: a numeric fingerprint of that frame. Similar-looking frames get similar fingerprints.

So our input is a sequence of feature vectors, one per frame:

$$ x_1, x_2, \dots, x_n \in \mathbb{R}^d $$

Read that line as: "there are $n$ frames; each frame $x_t$ is a list of $d$ numbers." (The symbol $\mathbb{R}^d$ just means "a list of $d$ real numbers.") Frames within the same shot have similar fingerprints; at a shot boundary the fingerprint changes sharply. KTS finds those sharp changes.

What KTS actually does

Given those fingerprints, KTS finds the change points so that:

• frames inside a segment are as similar to each other as possible, and
• the number of segments stays small (we don't want one segment per frame).

It does this with two ideas, which are the two halves of this book:

1. Measure how "spread out" a segment is using a kernel, a flexible similarity measure (Chapters 1 to 2).
2. Find the cut points that minimize the total spread using dynamic programming, a technique that is guaranteed to find the best possible answer, not just a good guess (Chapters 3 to 6).

What you'll build

By the end you'll have one short, fully-understood Python file, kts.py, and you'll watch it recover hidden boundaries in test data exactly.

What you need

• Python 3.8+ (the primer shows how code/output is presented)
• NumPy (a number-crunching library, also covered in the primer)
• (optional) Matplotlib, only for one picture in the final demo

Let's start with the two background ideas: kernels and change points. 👉

A 5-minute Python & NumPy primer

This book assumes no prior experience with Python, AI, or any library. This page gives you just enough to read every code example. If you already know Python and NumPy, skip ahead.

What is Python?

Python is a programming language, a way to write step-by-step instructions for a computer. You write text in a file ending in .py and run it. Throughout this book, grey boxes contain Python code, and the box right after shows what it prints when you run it:

print("hello")
print(2 + 3)

Output:

hello
5

print(...) displays a value on the screen. That's how we'll inspect results.

Variables, functions, lists

x = 10                 # a variable: the name x now refers to the number 10
name = "video"         # text (a "string") goes in quotes
nums = [4, 1, 7]       # a list: an ordered collection of values

A function is a reusable recipe. You "call" it with inputs (called arguments) in parentheses, and it gives back a result:

def double(value):     # define a function named "double"
    return value * 2   # "return" hands a result back to the caller

print(double(21))      # call it

Output:

42

What is NumPy?

NumPy is a Python library (a bundle of pre-written code you can reuse) for working with arrays of numbers efficiently. We load it once at the top of a file and, by convention, nickname it np:

import numpy as np

Arrays: 1-D (a list of numbers) and 2-D (a grid/matrix)

import numpy as np

v = np.array([1.0, 2.0, 3.0])          # a 1-D array (a "vector")
M = np.array([[1.0, 2.0],              # a 2-D array (a "matrix" / grid)
              [3.0, 4.0]])
print(v)
print(M)
print("shape of M:", M.shape)          # (rows, columns)

Output:

[1. 2. 3.]
[[1. 2.]
 [3. 4.]]
shape of M: (2, 2)

• A vector is just a row of numbers. In this book, each video frame is described by a vector of numbers (its "features", think of it as a numeric fingerprint of the image).
• A matrix is a grid of numbers (rows × columns). M.shape tells you its size as (rows, columns).

The handful of NumPy operations we use

You don't need to memorize these, each is explained again the first time it appears.

One more idea: the dot product

The dot product of two vectors multiplies them position-by-position and adds up the results. It's the basic "how aligned are these two things?" measurement, and it's the seed of everything in this book:

import numpy as np
a = np.array([1.0, 0.0])
b = np.array([0.9, 0.1])
print(np.dot(a, b))     # 1*0.9 + 0*0.1

Output:

0.9

A big dot product means the two vectors point in a similar direction (the frames look alike); a small one means they're different. Hold onto that intuition, the next chapter builds the whole method on it. 👉

Background: kernels & change points

Two ideas power KTS: change-point detection and kernels. We'll build both from scratch, with numbers you can check by hand.

Change-point detection

We have an ordered sequence of frame fingerprints $x_1,\dots,x_n$. A change point is a position where the sequence suddenly starts behaving differently, the boundary between two shots.

If we mark change points at positions $t_1 < t_2 < \dots < t_m$, they cut the sequence into $m+1$ segments (the stretches between consecutive cuts). For example, with 10 frames and cuts after frame 3 and frame 7, we get three segments: frames 1 to 3, 4 to 7, 8 to 10.

How do we know a segmentation is good? We use within-segment variance, a measure of how spread out the frames inside a segment are. A tight, consistent segment (all frames similar) has low variance; a segment that mixes a beach and a party has high variance. The total cost of a segmentation is the sum of its segments' variances, and lower is better.

⚠️ One catch: if you're allowed unlimited cuts, the cheapest answer is to put every frame in its own segment (variance = 0). That's useless. So KTS either fixes the number of segments (Chapter 5) or adds a penalty for having too many (Chapter 6).

Why a "kernel"?

To measure variance we need to measure similarity between frames. The simplest similarity is the dot product (from the primer): multiply two fingerprints position-by-position and add up. Big result = similar.

But a plain dot product assumes the "natural" way to compare frames is a straight line in number-space. Often that's too rigid. A kernel is just a more flexible similarity function $k(x, y)$, give it two fingerprints, it returns a number saying how alike they are. Different kernels encode different notions of "alike".

The beauty of kernels: we collect every pairwise similarity into one grid called the kernel matrix (or Gram matrix) $K$, where the entry in row $i$, column $j$ is

$$ K_{ij} = k(x_i, x_j) = \text{similarity between frame } i \text{ and frame } j. $$

Everything KTS does is read numbers out of this one grid.

Three common kernels

(Here $x^\top y$ is the dot product, and $\lVert x\rVert$ means the length of vector $x$.)

A concrete kernel matrix

Take three 2-number frames. Frames 0 and 1 point "right"; frame 2 points "up":

import numpy as np

X = np.array([[1.0, 0.0],     # frame 0: points right
              [0.9, 0.1],     # frame 1: almost the same as frame 0
              [0.1, 1.0]])    # frame 2: points up (different)

Using the cosine kernel (direction similarity), the kernel matrix is:

[[1.    0.994 0.1  ]
 [0.994 1.    0.209]
 [0.1   0.209 1.   ]]

Read it like a similarity table:

• The diagonal is all 1.0: every frame is perfectly similar to itself.
• Row 0, column 1 = 0.994: frames 0 and 1 are almost identical (both point right). High number → same shot.
• Row 0, column 2 = 0.1: frames 0 and 2 are very different. Low number → a boundary lives between them.

That single grid already "knows" frame 2 belongs to a different shot. The next chapter turns this intuition into the exact cost formula KTS minimizes. 👉

The math behind KTS

This is the only heavily mathematical chapter. We'll go slowly and explain every symbol. The payoff is one simple formula that scores how "tight" a segment is, using only the kernel matrix from the previous chapter.

Reading the notation

A few symbols appear a lot:

• $\sum_{t=i}^{j}$ means "add up, for every $t$ from $i$ to $j$." For example $\sum_{t=1}^{3} t = 1 + 2 + 3 = 6$. The big $\Sigma$ is just shorthand for "sum".
• $\phi_t$ (the Greek letter phi) is frame $t$'s fingerprint after the kernel's similarity transformation. You never compute it directly: it's a thinking tool.
• $\mu$ (mu) is the average (mean) of a group of fingerprints.
• $\lVert a \rVert^2$ is the squared length of vector $a$, a measure of "how big" it is. $\lVert a - b \rVert^2$ is then the squared distance between $a$ and $b$: small when they're close, large when far apart.
• $\langle a, b \rangle$ is the dot product of $a$ and $b$ (the similarity measure from before). Crucially, $\langle \phi_s, \phi_t \rangle = K_{st}$, the dot product of two fingerprints is exactly the kernel-matrix entry.

Step 1: what "spread out" means

Take one segment covering frames $i, i+1, \dots, j$. Call its length $L = j - i + 1$ (the number of frames in it). Its average fingerprint is

$$ \mu = \frac{1}{L} \sum_{t=i}^{j} \phi_t. $$

(Add up the fingerprints in the segment, divide by how many there are, an ordinary average.)

The scatter of the segment is the total squared distance from each frame to that average:

$$ v(i, j) = \sum_{t=i}^{j} \lVert \phi_t - \mu \rVert^2. $$

In words: how far is each frame from the segment's "typical" frame, added up. A consistent segment → every frame near the average → small $v$. A jumbled segment → frames far from the average → large $v$. This single number is what KTS uses to grade a segment.

Step 2: rewrite it using only the kernel matrix

The problem: $\mu$ and $\phi_t$ live in an abstract space we can't compute in directly. The fix: expand the formula until only dot products $\langle \phi_s, \phi_t \rangle = K_{st}$ remain.

Expanding the squared distance (using $\lVert a-b\rVert^2 = \langle a,a\rangle - 2\langle a,b\rangle + \langle b,b\rangle$):

$$ v(i,j) = \sum_{t=i}^{j} \Big( \langle \phi_t, \phi_t \rangle - 2\langle \phi_t, \mu \rangle + \langle \mu, \mu \rangle \Big). $$

Now substitute $\mu = \frac{1}{L}\sum_s \phi_s$ and replace every $\langle \phi_s, \phi_t \rangle$ with $K_{st}$. The three pieces become:

• $\displaystyle \sum_{t=i}^{j} \langle \phi_t, \phi_t \rangle = \sum_{t=i}^{j} K_{tt}$, the diagonal entries summed.
• $\displaystyle \sum_{t=i}^{j} 2\langle \phi_t, \mu \rangle = \frac{2}{L}\sum_{t=i}^{j}\sum_{s=i}^{j} K_{st}$, twice the sum of the whole block, divided by $L$.
• $\displaystyle \sum_{t=i}^{j} \langle \mu, \mu \rangle = \frac{1}{L}\sum_{s,t} K_{st}$, the block sum divided by $L$.

The last two combine, leaving the key formula:

$$ \boxed{\,v(i,j) = \sum_{t=i}^{j} K_{tt} \;-\; \frac{1}{L} \sum_{s=i}^{j}\sum_{t=i}^{j} K_{st}\,} $$

In plain words:

scatter = (sum of the diagonal entries for the segment) − (sum of the whole square block of $K$ for the segment, divided by its length).

No averages, no abstract fingerprints, just sums of numbers we already have in the grid $K$. That's the whole trick.

A worked example you can check by hand

Take two frames that are each a single number: $x_1 = 0$ and $x_2 = 0.2$, with the linear kernel (so this is just ordinary distance). The segment containing both has length $L = 2$ and average $\mu = (0 + 0.2)/2 = 0.1$.

Directly from the definition:

$$ v = (0 - 0.1)^2 + (0.2 - 0.1)^2 = 0.01 + 0.01 = 0.02. $$

In Chapter 4 we compute this segment's scatter with code and get the matching value 0.02. Two completely different routes (by hand and by computer), agree.

The total objective

A full segmentation with change points $t_1 < \dots < t_m$ (giving $m+1$ segments) is scored by adding up every segment's scatter:

$$ J = \sum_{r=0}^{m} v\big(t_r,\ t_{r+1}-1\big). $$

KTS chooses the cut positions that make $J$ as small as possible. Two cases:

• You know how many segments you want → minimize $J$ directly with dynamic programming (Chapter 5).
• You don't → add a penalty for extra cuts and let the computer pick (Chapter 6).

Why we'll precompute sums

Each $v(i,j)$ needs a sum over a block of $K$. Done naively for every possible segment, that's far too slow. The next chapter shows a trick (cumulative sums) that makes each scatter an instant lookup. First, let's write the code to build $K$. 👉

Step 1: The kernel matrix

Everything in KTS reads from the kernel matrix $K$: a grid where the entry in row $i$, column $j$ is the similarity between frame $i$ and frame $j$. Step one is to turn our table of frame fingerprints into this similarity grid.

Our input is an array X with one row per frame and one column per feature number. So X has shape (n, d): n frames, each described by d numbers. The output K has shape (n, n): a similarity for every pair of frames.

The code

import numpy as np


def linear_kernel(X):
    """K[i, j] = dot product of frame i and frame j. Plain variance."""
    return X @ X.T


def cosine_kernel(X, eps=1e-8):
    """Similarity by direction only (length-normalized). A good default."""
    norms = np.linalg.norm(X, axis=1, keepdims=True)   # length of each frame vector
    Xn = X / np.maximum(norms, eps)                    # rescale each to length 1
    return Xn @ Xn.T


def rbf_kernel(X, sigma=None):
    """Gaussian similarity: 1 when identical, fading to 0 as frames differ."""
    sq = np.sum(X**2, axis=1)                          # squared length of each frame
    # squared distance between every pair: ||a-b||^2 = ||a||^2 + ||b||^2 - 2 a.b
    d2 = sq[:, None] + sq[None, :] - 2.0 * (X @ X.T)
    d2 = np.maximum(d2, 0.0)                            # clip tiny negatives (rounding)
    if sigma is None:
        med = np.median(d2[d2 > 0]) if np.any(d2 > 0) else 1.0
        sigma = np.sqrt(0.5 * med) if med > 0 else 1.0  # auto bandwidth
    return np.exp(-d2 / (2.0 * sigma**2))


def build_kernel(X, kind="cosine", **kwargs):
    """Pick a kernel by name and build the matrix."""
    X = np.asarray(X, dtype=np.float64)
    kernels = {"linear": linear_kernel, "cosine": cosine_kernel, "rbf": rbf_kernel}
    if kind not in kernels:
        raise ValueError(f"unknown kernel {kind!r}; pick one of {list(kernels)}")
    return kernels[kind](X, **kwargs) if kind == "rbf" else kernels[kind](X)

Reading the code, line by line

• X @ X.T, @ is matrix multiplication and .T is the transpose (rows ↔ columns). Multiplying X by its own transpose computes the dot product of every pair of rows at once. That grid of dot products is the linear kernel.
• np.linalg.norm(X, axis=1, keepdims=True), the length of each frame vector. axis=1 means "do it per row" (one length per frame).
• X / norms, divide each frame by its own length, so every frame becomes length 1. After this, the dot product measures direction only: that's the cosine kernel. np.maximum(norms, eps) just avoids dividing by zero.
• In rbf_kernel, sq[:, None] + sq[None, :] - 2 * (X @ X.T) is the algebra identity for squared distance between every pair, computed in one shot.
• np.exp(...) raises $e$ to a power elementwise; here it turns "distance" into "similarity" (distance 0 → similarity 1; large distance → similarity ~0).

Try it: input and output

import numpy as np

X = np.array([[1.0, 0.0],     # frame 0: points right
              [0.9, 0.1],     # frame 1: nearly the same as frame 0
              [0.1, 1.0]])    # frame 2: points up (different)

K = build_kernel(X, kind="cosine")
print(np.round(K, 3))         # round to 3 decimals for readability

Output:

[[1.    0.994 0.1  ]
 [0.994 1.    0.209]
 [0.1   0.209 1.   ]]

How to read this 3×3 grid:

• Diagonal is all 1.0: each frame is identical to itself.
• K[0,1] = 0.994: frames 0 and 1 are nearly identical (same shot).
• K[0,2] = 0.1: frames 0 and 2 are very different (a boundary sits between them).

The same three frames with the other two kernels:

print("linear:\n", np.round(build_kernel(X, "linear"), 3))
print("rbf:\n",    np.round(build_kernel(X, "rbf"), 3))

Output:

linear:
 [[1.   0.9  0.1 ]
 [0.9  0.82 0.19]
 [0.1  0.19 1.01]]
rbf:
 [[1.    0.986 0.287]
 [0.986 1.    0.368]
 [0.287 0.368 1.   ]]

All three agree on the story, frames 0 and 1 are similar, frame 2 is the odd one out: they just put the numbers on different scales.

Which kernel should I use?

• cosine: the safe default for AI "deep" features; it ignores brightness/ scale and compares content.
• linear: reproduces ordinary variance; simplest.
• rbf: adds non-linear sensitivity, at the cost of a sigma knob (how fast similarity fades with distance). The code picks a reasonable sigma automatically.

Two practical notes

• Memory. K has n × n entries. A 1-hour video has too many frames, so in practice you keep one frame per second, run KTS, then map the change points back to real time.
• Sanity check. A valid kernel matrix is symmetric (K[i,j] == K[j,i]), and for the cosine kernel the diagonal is exactly 1:

Xr = np.random.randn(6, 4)            # 6 random frames, 4 features each
Kc = build_kernel(Xr, "cosine")
print("symmetric:", np.allclose(Kc, Kc.T))
print("diagonal all 1:", np.allclose(np.diag(Kc), 1.0))

Output:

symmetric: True
diagonal all 1: True

With $K$ in hand we can score any segment. Let's make that fast. 👉

Step 2: The scatter (cost) matrix

Recall the per-segment cost from the math chapter: the scatter $v(i,j)$ of frames $i$ through $j$ is

$$ v(i,j) = \sum_{t=i}^{j} K_{tt} \;-\; \frac{1}{L} \sum_{s=i}^{j}\sum_{t=i}^{j} K_{st}, \qquad L = j - i + 1. $$

We want this number for every possible segment, and we want each one to be instant to look up. The trick that makes it instant is cumulative sums.

What is a cumulative sum?

A cumulative (running) sum replaces each number with the total of everything up to it: [5, 2, 4] becomes [5, 7, 11]. Why bother? Because once you have running totals, the sum of any stretch is a single subtraction. The sum of items 1 to 2 above is 11 − 5 = 6, no re-adding. We use the same idea in two dimensions.

The code

import numpy as np


def calc_scatters(K):
    """
    Return J, an n x n table where J[i, j] is the scatter v(i, j) of frames
    i..j. Building it costs O(n^2); each entry is then an O(1) lookup.
    """
    n = K.shape[0]

    # running total of the diagonal: dcum[t] = sum of K[0,0] .. K[t-1,t-1]
    dcum = np.concatenate(([0.0], np.cumsum(np.diag(K))))

    # 2-D running total: Kcum[a, b] = sum of the top-left a x b block of K
    Kcum = np.zeros((n + 1, n + 1))
    Kcum[1:, 1:] = np.cumsum(np.cumsum(K, axis=0), axis=1)

    J = np.zeros((n, n))
    for i in range(n):
        for j in range(i, n):
            L = j - i + 1
            diag_sum = dcum[j + 1] - dcum[i]                 # diagonal part
            block = (Kcum[j + 1, j + 1] - Kcum[i, j + 1]     # block sum via
                     - Kcum[j + 1, i] + Kcum[i, i])          # 4 corner lookups
            J[i, j] = diag_sum - block / L
    return J

Reading the code

• np.diag(K) pulls out the diagonal (each frame's self-similarity). np.cumsum(...) makes its running total, so dcum[j+1] - dcum[i] instantly gives the diagonal sum for frames $i..j$.
• np.cumsum(np.cumsum(K, axis=0), axis=1) does the running total down then across, giving a 2-D running total Kcum. After that, the sum of any rectangular block of K is four corner lookups added/subtracted (see below).
• The two for loops fill in J[i, j] for every segment using those instant lookups.

Why the four corners work

For a 2-D running total, the sum inside a rectangle equals (big rectangle) − (strip above) − (strip left) + (overlap added back):

sum = Kcum[j+1, j+1]   # everything from the origin down to (j, j)
    - Kcum[i,   j+1]   # subtract the strip above the block
    - Kcum[j+1, i  ]   # subtract the strip to the left
    + Kcum[i,   i  ]   # the top-left corner got subtracted twice; add it back

This is the standard "inclusion-exclusion" pattern for rectangle sums.

Try it: input and output

Four frames that are single numbers, two near 0, two near 5 (so clearly two groups). We use the linear kernel:

import numpy as np

X = np.array([[0.0], [0.2], [5.0], [5.1]])
K = X @ X.T               # linear kernel
J = calc_scatters(K)
print(np.round(J, 3))

Output:

[[ 0.     0.02  16.027 24.527]
 [ 0.     0.    11.52  15.687]
 [ 0.     0.     0.     0.005]
 [ 0.     0.     0.     0.   ]]

How to read J[i, j] (only the upper triangle is filled; j ≥ i):

• J[0,1] = 0.02: frames 0 to 1 (both near 0) form a tight segment. Tiny scatter = good segment. (This is the exact number we computed by hand in Chapter 2! ✔)
• J[2,3] = 0.005: frames 2 to 3 (both near 5) are also tight.
• J[0,3] = 24.527: lumping all four frames into one segment mixes the two groups, so the scatter is huge. Bad segment.

The table already tells us the right split: keep 0–1 together, keep 2–3 together, and don't merge across the gap. Dynamic programming (next chapter) makes that decision automatically.

Speed

Both the running totals and filling J cost on the order of $n^2$ operations, the same as just storing $K$. So we get every segment's cost cheaply.

Sanity check against the definition

We can confirm calc_scatters matches the original "distance to the average" definition by brute force:

def brute_scatter(X, i, j):
    seg = X[i:j + 1]
    mu = seg.mean(axis=0)              # the segment average
    return float(((seg - mu) ** 2).sum())

X = np.random.randn(8, 3)             # 8 random frames, 3 features
J = calc_scatters(X @ X.T)
ok = all(abs(J[i, j] - brute_scatter(X, i, j)) < 1e-8
         for i in range(8) for j in range(i, 8))
print("scatter matrix matches the definition:", ok)

Output:

scatter matrix matches the definition: True

Now every segment has a cost. Time to find the best combination of segments. 👉

Step 3: Dynamic programming

We can now score any single segment instantly. The remaining problem: out of the enormous number of ways to place the cuts, find the one combination with the smallest total scatter

$$ J = \sum_{r=0}^{m} v\big(t_r,\ t_{r+1}-1\big). $$

Trying every possibility is hopeless, for $n$ frames and $m$ cuts there are $\binom{n-1}{m}$ combinations, which explodes. Dynamic programming (DP) finds the guaranteed-best answer without trying them all.

The idea, in plain words

DP is "solve small pieces, reuse the answers." Here's the intuition:

Suppose you already knew the best way to split the first part of the video into a few segments. Then to split a slightly longer part, you only need to decide where the last segment starts, everything before it is a smaller problem you've already solved.

So we build up the answer for longer and longer prefixes of the video, reusing the best answers to the shorter prefixes. Because every sub-answer is optimal, the final answer is optimal too.

The recurrence

Let $C[k, \ell]$ be the smallest possible total scatter when splitting the first $\ell$ frames into exactly $k+1$ segments (that's $k$ cuts). The last segment must start somewhere (call it $t$), and run to frame $\ell-1$. Everything before $t$ is the best $k$-segment split of the first $t$ frames. So we just try every possible start $t$ and keep the cheapest:

$$ C[k, \ell] \;=\; \min_{t} \Big( C[k-1,\ t] \;+\; v(t,\ \ell-1) \Big). $$

• Base case: $C[0, \ell] = v(0, \ell-1)$, with zero cuts there's one segment covering everything.
• Answer: $C[m, n]$ is the best total scatter for the whole video with $m$ cuts.

To recover where the cuts are (not just the cost), we remember, for each cell, which start $t$ won. Walking those choices backward is called backtracking.

The code

import numpy as np


def cpd_nonlin(K, ncp, lmin=1, lmax=None):
    """
    Globally optimal segmentation given the kernel matrix K.

    K    : (n, n) kernel matrix.
    ncp  : number of change points m  (=> m + 1 segments).
    lmin : smallest allowed segment length.
    lmax : largest allowed segment length (defaults to n).

    Returns (cps, cost):
      cps  : the m change-point positions (start frame of each new segment).
      cost : the total scatter of that optimal segmentation.
    """
    n = K.shape[0]
    m = int(ncp)
    if lmax is None:
        lmax = n
    if (m + 1) * lmin > n:
        raise ValueError("sequence too short for this many change points")

    J = calc_scatters(K)                 # from Step 2: every segment's cost

    INF = 1e18
    C = np.full((m + 1, n + 1), INF)     # C[k, l]: best cost, first l frames, k+1 segs
    back = np.zeros((m + 1, n + 1), dtype=int)   # remembers the winning start t

    # base row: a single segment [0 .. l-1]
    for l in range(lmin, min(lmax, n) + 1):
        C[0, l] = J[0, l - 1]

    # fill rows k = 1 .. m
    for k in range(1, m + 1):
        for l in range((k + 1) * lmin, n + 1):
            t_lo = max(k * lmin, l - lmax)
            t_hi = l - lmin              # last segment must be at least lmin long
            if t_lo > t_hi:
                continue
            for t in range(t_lo, t_hi + 1):
                cost = C[k - 1, t] + J[t, l - 1]
                if cost < C[k, l]:
                    C[k, l] = cost
                    back[k, l] = t

    # backtrack from the full problem to read off the cuts
    cps = np.zeros(m, dtype=int)
    l = n
    for k in range(m, 0, -1):
        t = back[k, l]
        cps[k - 1] = t
        l = t
    return cps, C[m, n]

Reading the code

• C is the table of best costs; C[k, l] is "first l frames, k+1 segments."
• np.full((m+1, n+1), INF) fills the table with a huge number (INF) meaning "not computed / impossible yet"; real costs will be smaller and overwrite it.
• The three nested loops implement the recurrence: for each number of cuts k and each prefix length l, try every start t for the last segment and keep the cheapest, recording the winner in back.
• lmin/lmax (min/max segment length) shrink the search and prevent silly one-frame segments.
• The final loop reads back from the whole-video cell backward to list the cuts.

Try it: input and output

Six frames: the first three point "right", the last three point "up", two obvious shots, so the boundary should be at frame 3.

import numpy as np
from kts import build_kernel, cpd_nonlin

X = np.array([[1.0, 0.0], [0.95, 0.10], [0.90, 0.05],   # shot A (frames 0,1,2)
              [0.10, 0.90], [0.05, 0.95], [0.00, 1.00]]) # shot B (frames 3,4,5)
K = build_kernel(X, "cosine")

cps, cost = cpd_nonlin(K, ncp=1, lmin=1)    # ask for exactly 1 cut
print("1 cut :", cps.tolist(), " cost:", round(cost, 4))

cps2, cost2 = cpd_nonlin(K, ncp=2, lmin=1)  # ask for exactly 2 cuts
print("2 cuts:", cps2.tolist(), " cost:", round(cost2, 4))

Output:

1 cut : [3]  cost: 0.0116
2 cuts: [3, 4]  cost: 0.0069

• With 1 cut, KTS puts it at frame 3, exactly the true boundary between the two shots. 🎯
• With 2 cuts, it keeps the real boundary at 3 and adds a second cut at 4. Notice the cost barely drops (0.0116 → 0.0069): the first cut explains almost all the structure; the second is just splitting hairs. That tiny extra gain is the clue we'll use in the next chapter to decide the right number of cuts automatically.

How backtracking recovers the cuts

back[k, l] stored the best start of the last segment for each sub-problem. Starting from the whole video (m, n), we read that start, jump to the smaller sub-problem, and repeat, collecting one cut each step. Those starts are the change points.

Speed

The loops run on the order of $m \times n \times n$ steps in the worst case, polynomial and fast, versus the impossible "try everything" count. (The full implementation in Chapter 7 replaces the inner for t loop with a single NumPy operation for extra speed; the logic is identical.)

This solves the problem when you already know how many cuts you want. Usually you don't, so next we let KTS choose. 👉

Step 4: Choosing the number of segments

cpd_nonlin makes you specify $m$, the number of cuts. But in real life you don't know how many shots a video has. This chapter makes KTS decide for you.

The trade-off

More cuts always lower the total scatter. (In the extreme, one frame per segment gives a scatter of zero, perfectly "tight" but completely useless.) So we can't just minimize scatter; that would always choose the maximum number of cuts.

We need to charge a fee for every cut, then pick the number of cuts that minimizes scatter + fees:

$$ m^\star = \arg\min_m \Big( J_m + \text{penalty}(m) \Big). $$

($\arg\min$ means "the $m$ that gives the smallest value".) This is the same spirit as not over-fitting in statistics: a new cut is only worth it if it lowers the scatter by more than its fee.

The penalty (and a bug to avoid)

A natural-but-wrong idea is to make the fee proportional to the scatter. That fails: as scatter shrinks toward zero, the fee shrinks too, so cuts become free and KTS never stops splitting. (We actually hit this and fixed it.)

The correct penalty grows with the number of cuts, independent of the scatter. For $m$ cuts over $n$ frames:

$$ \text{penalty}(m) = \frac{m}{2n},\Big( \log\!\big(\tfrac{n}{m}\big) + 1 \Big), \qquad \text{score}(m) = \frac{J_m}{n} + v_{\max}\cdot\text{penalty}(m). $$

The fee rises steadily with each extra cut, so the score goes down while cuts are explaining real structure, then up once they're just splitting hairs. The lowest point is the answer. The weight $v_{\max}$ is your one knob: larger → fewer segments.

The code

import numpy as np


def cpd_auto(K, ncp_max, vmax=1.0, lmin=1, lmax=None):
    """
    Automatically choose the number of change points.

    K       : (n, n) kernel matrix.
    ncp_max : largest number of cuts to consider.
    vmax    : penalty weight. Larger -> fewer segments. (try 0.5 .. 2.0)
    lmin    : minimum segment length.

    Returns (cps, scores):
      cps    : change points of the chosen segmentation.
      scores : dict {m: score} so you can see/plot the trade-off.
    """
    n = K.shape[0]
    ncp_max = min(ncp_max, n - 1)
    J = calc_scatters(K)                     # compute once, reuse for every m

    best_score = np.inf
    best_cps = np.array([], dtype=int)
    scores = {}

    for m in range(0, ncp_max + 1):
        if (m + 1) * lmin > n:
            break
        cps, J_m = cpd_nonlin(K, m, lmin=lmin, lmax=lmax, J=J)
        penalty = 0.0 if m == 0 else (m / (2.0 * n)) * (np.log(n / m) + 1.0)
        score = J_m / n + vmax * penalty
        scores[m] = score
        if score < best_score:
            best_score = score
            best_cps = cps
    return best_cps, scores

Reading the code

• It runs the Chapter-5 solver once for each candidate number of cuts m, from 0 up to ncp_max.
• For each, it adds the penalty fee and keeps the m with the lowest total score.
• best_cps ends up holding the cuts of the winning segmentation.

Try it: input and output

A small but realistic test: 30 frames, the first 15 around one center and the next 15 around another (with random noise). The true boundary is at frame 15.

import numpy as np
from kts import build_kernel, cpd_auto

rng = np.random.default_rng(0)
A = np.array([3, 3, 0, 0, 0, 0, 0, 0.0])
B = np.array([0, 0, 0, 0, 3, 3, 0, 0.0])
X = np.vstack([A + rng.normal(scale=0.5, size=(15, 8)),    # frames 0..14
               B + rng.normal(scale=0.5, size=(15, 8))])   # frames 15..29
K = build_kernel(X, "cosine")

cps, scores = cpd_auto(K, ncp_max=8, vmax=1.0, lmin=2)
print("chosen change points:", cps.tolist(), "=>", len(cps) + 1, "segments")
for m, s in scores.items():
    print(f"   m={m}: score={s:.3f}")

Output:

chosen change points: [15] => 2 segments
   m=0: score=0.538
   m=1: score=0.159
   m=2: score=0.202
   m=3: score=0.237
   m=4: score=0.269
   m=5: score=0.298
   m=6: score=0.323
   m=7: score=0.345
   m=8: score=0.366

KTS picks one cut at frame 15 (exactly the real boundary), without being told there were two groups. 🎯 Look at the scores: they plunge from m=0 (0.538) to m=1 (0.159), then climb steadily. That "valley" at m=1 is the penalty doing its job, the first cut pays for itself; further cuts don't. Plotting score vs m shows the same valley as a classic elbow.

Tuning, in practice

• vmax is the main dial. Too many tiny segments → raise it. Too few → lower it. (1.0 is a sensible start.)
• ncp_max caps how many cuts to even consider, set it comfortably above what you expect.
• lmin (minimum segment length) is a cheap way to forbid spurious one- or two-frame segments, e.g. "at least 1 second of frames".

We now have all four pieces. Next: the polished, all-in-one implementation. 👉

The full implementation

Here is the consolidated module that ties Steps 1 to 4 together. It's the same logic from the previous chapters, with the DP inner loops vectorized with NumPy for speed (the for t loop becomes a slice + argmin), and calc_scatters computed once and reused across every candidate $m$ in cpd_auto.

The runnable file lives at code/kts.py in this book's folder. It is reproduced below in full.

"""
Kernel Temporal Segmentation (KTS) — from scratch in NumPy.

Reference:
    Potapov, Douze, Harchaoui, Schmid.
    "Category-Specific Video Summarization." ECCV 2014.

This module is the consolidated, vectorized version of the step-by-step
derivation in the accompanying mdBook. Public functions:

    build_kernel(X, kind="cosine")  -> kernel/Gram matrix K
    calc_scatters(K)                -> n x n scatter (cost) table J
    cpd_nonlin(K, ncp, ...)         -> optimal segmentation for fixed m
    cpd_auto(K, ncp_max, ...)       -> auto-select the number of segments

All functions use only NumPy.
"""

from __future__ import annotations

import numpy as np


# --------------------------------------------------------------------------- #
# Step 1 — kernels
# --------------------------------------------------------------------------- #
def linear_kernel(X):
    """K[i, j] = <x_i, x_j>; reproduces ordinary Euclidean variance."""
    return X @ X.T


def cosine_kernel(X, eps=1e-8):
    """Scale-invariant kernel; a robust default for deep features."""
    norms = np.linalg.norm(X, axis=1, keepdims=True)
    Xn = X / np.maximum(norms, eps)
    return Xn @ Xn.T


def rbf_kernel(X, sigma=None):
    """Gaussian kernel exp(-||x_i - x_j||^2 / (2 sigma^2))."""
    sq = np.sum(X ** 2, axis=1)
    d2 = sq[:, None] + sq[None, :] - 2.0 * (X @ X.T)
    d2 = np.maximum(d2, 0.0)
    if sigma is None:
        pos = d2[d2 > 0]
        med = np.median(pos) if pos.size else 1.0
        sigma = np.sqrt(0.5 * med) if med > 0 else 1.0
    return np.exp(-d2 / (2.0 * sigma ** 2))


def build_kernel(X, kind="cosine", **kwargs):
    """Build a kernel matrix from an (n, d) feature array."""
    X = np.asarray(X, dtype=np.float64)
    if kind == "linear":
        return linear_kernel(X)
    if kind == "cosine":
        return cosine_kernel(X)
    if kind == "rbf":
        return rbf_kernel(X, **kwargs)
    raise ValueError(f"unknown kernel {kind!r}; use 'linear', 'cosine' or 'rbf'")


# --------------------------------------------------------------------------- #
# Step 2 — scatter (cost) matrix via cumulative sums
# --------------------------------------------------------------------------- #
def calc_scatters(K):
    """
    J[i, j] = within-segment scatter of frames i..j (inclusive):

        v(i, j) = sum_t K[t, t]  -  (1 / L) * sum_{s,t in [i, j]} K[s, t]

    where L = j - i + 1. Built in O(n^2) with prefix sums; entries with
    j < i are left at 0.
    """
    K = np.asarray(K, dtype=np.float64)
    n = K.shape[0]

    dcum = np.concatenate(([0.0], np.cumsum(np.diag(K))))        # diagonal prefix
    Kcum = np.zeros((n + 1, n + 1))
    Kcum[1:, 1:] = np.cumsum(np.cumsum(K, axis=0), axis=1)       # 2-D prefix

    J = np.zeros((n, n))
    for i in range(n):
        # vectorized over j = i .. n-1
        js = np.arange(i, n)
        L = js - i + 1
        diag_sum = dcum[js + 1] - dcum[i]
        block = (Kcum[js + 1, js + 1] - Kcum[i, js + 1]
                 - Kcum[js + 1, i] + Kcum[i, i])
        J[i, i:] = diag_sum - block / L
    return J


# --------------------------------------------------------------------------- #
# Step 3 — dynamic programming for a fixed number of change points
# --------------------------------------------------------------------------- #
def cpd_nonlin(K, ncp, lmin=1, lmax=None, J=None):
    """
    Globally optimal segmentation with exactly `ncp` change points.

    Returns
    -------
    cps  : (ncp,) int array of change points (start frame of each new segment).
    cost : total scatter of the optimal segmentation.
    """
    n = K.shape[0]
    m = int(ncp)
    if lmax is None:
        lmax = n
    if (m + 1) * lmin > n:
        raise ValueError("sequence too short for this many change points")

    if J is None:
        J = calc_scatters(K)

    INF = 1e18
    C = np.full((m + 1, n + 1), INF)         # C[k, l]: best cost, first l frames, k+1 segs
    back = np.zeros((m + 1, n + 1), dtype=int)

    # base row: single segment [0 .. l-1]
    for l in range(lmin, min(lmax, n) + 1):
        C[0, l] = J[0, l - 1]

    for k in range(1, m + 1):
        for l in range((k + 1) * lmin, n + 1):
            t_lo = max(k * lmin, l - lmax)
            t_hi = l - lmin                  # last segment length >= lmin
            if t_lo > t_hi:
                continue
            ts = np.arange(t_lo, t_hi + 1)
            cand = C[k - 1, ts] + J[ts, l - 1]
            idx = int(np.argmin(cand))
            C[k, l] = cand[idx]
            back[k, l] = ts[idx]

    # backtrack
    cps = np.zeros(m, dtype=int)
    l = n
    for k in range(m, 0, -1):
        t = back[k, l]
        cps[k - 1] = t
        l = t
    return cps, float(C[m, n])


# --------------------------------------------------------------------------- #
# Step 4 — automatic selection of the number of segments
# --------------------------------------------------------------------------- #
def cpd_auto(K, ncp_max, vmax=1.0, lmin=1, lmax=None):
    """
    Pick the number of change points by penalized model selection.

    Returns
    -------
    cps    : change points of the selected segmentation.
    scores : dict {m: penalized score} for inspection.
    """
    n = K.shape[0]
    ncp_max = min(ncp_max, n - 1)
    J = calc_scatters(K)                     # compute once, reuse for every m

    best_score = np.inf
    best_cps = np.array([], dtype=int)
    scores = {}

    for m in range(0, ncp_max + 1):
        if (m + 1) * lmin > n:
            break
        cps, J_m = cpd_nonlin(K, m, lmin=lmin, lmax=lmax, J=J)
        # Penalty grows with the *number of change points* m, independent of the
        # scatter. (A scatter-proportional penalty would vanish as J_m -> 0 and
        # never stop adding cuts.) This is the KTS model-selection criterion.
        penalty = 0.0 if m == 0 else (m / (2.0 * n)) * (np.log(n / m) + 1.0)
        score = J_m / n + vmax * penalty
        scores[m] = score
        if score < best_score:
            best_score = score
            best_cps = cps
    return best_cps, scores


__all__ = [
    "build_kernel", "linear_kernel", "cosine_kernel", "rbf_kernel",
    "calc_scatters", "cpd_nonlin", "cpd_auto",
]

The {{#include}} directive above is an mdBook feature: when the book is built, it splices in the real code/kts.py, so the documentation can never drift from the actual implementation.

API at a glance

Typical usage

import numpy as np
from kts import build_kernel, cpd_auto

features = np.load("frame_features.npy")   # shape (n_frames, d)
K = build_kernel(features, kind="cosine")

# Let KTS decide how many shots there are:
change_points, scores = cpd_auto(K, ncp_max=30, vmax=1.0, lmin=5)

# change_points are start-frame indices of each new segment.
segments = np.split(np.arange(len(features)), change_points)
print(f"{len(segments)} segments")

A complete run, start to finish

This single example uses every function in order, build features, build the kernel, auto-segment, and list the resulting segments:

import numpy as np
from kts import build_kernel, cpd_auto

# 1. Fake "video": 12 frames in 3 groups of 4 (groups differ in direction).
rng = np.random.default_rng(1)
g1 = np.array([1, 0, 0, 0.0]) + rng.normal(scale=0.05, size=(4, 4))
g2 = np.array([0, 1, 0, 0.0]) + rng.normal(scale=0.05, size=(4, 4))
g3 = np.array([0, 0, 1, 0.0]) + rng.normal(scale=0.05, size=(4, 4))
X = np.vstack([g1, g2, g3])                 # shape (12, 4)

# 2. Similarity grid.
K = build_kernel(X, kind="cosine")

# 3. Let KTS choose the cuts.
cps, _ = cpd_auto(K, ncp_max=6, vmax=1.0, lmin=2)

# 4. Turn cuts into actual frame ranges.
segments = np.split(np.arange(len(X)), cps)
print("change points :", cps.tolist())
print("segments       :", [s.tolist() for s in segments])

Output:

change points : [4, 8]
segments       : [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11]]

KTS recovers the three groups exactly, cuts at frames 4 and 8, splitting the 12 frames into 0–3, 4–7, 8–11. 🎯

In the final chapter we run the larger bundled demo and measure accuracy. 👉

A worked demo

Let's confirm KTS actually works. We build a synthetic "video" whose true structure we know, run KTS, and check it recovers the planted boundaries.

The full script is code/demo.py; here's how it's built.

A fake video with known change points

To test KTS we need data where we already know the right answer. So we manufacture a fake video: we pick a few random "centers" (each stands for a shot), and for each shot we generate a block of frames that are that center plus a little random noise. Frames in the same block look alike; frames in different blocks look different. The boundaries between blocks are the true change points we hope KTS will rediscover.

def make_synthetic_sequence(seed=0):
    """Return (X, true_change_points)."""
    rng = np.random.default_rng(seed)
    d = 8
    block_lengths = [40, 25, 35, 20, 30]   # 5 segments
    centers = rng.normal(scale=3.0, size=(len(block_lengths), d))

    chunks, true_cps, cursor = [], [], 0
    for i, L in enumerate(block_lengths):
        chunks.append(centers[i] + rng.normal(scale=0.4, size=(L, d)))
        cursor += L
        if i < len(block_lengths) - 1:
            true_cps.append(cursor)        # boundary = start of next block
    X = np.vstack(chunks)
    return X, np.array(true_cps)

A couple of unfamiliar bits:

• np.random.default_rng(seed) creates a reproducible source of random numbers, using the same seed gives the same "random" data every run, so the results in this book are repeatable.
• rng.normal(scale=0.4, size=(L, d)) draws L × d small random numbers (the per-frame noise). A bigger scale = noisier frames = harder problem.
• np.vstack([...]) stacks the blocks on top of each other into one big (n_frames, d) array.

We use 5 blocks of lengths [40, 25, 35, 20, 30], so the true change points are at frames [40, 65, 100, 120] (4 cuts → 5 segments).

Running KTS

from kts import build_kernel, cpd_auto, cpd_nonlin

K = build_kernel(X, kind="cosine")

# automatic number of segments
cps_auto, scores = cpd_auto(K, ncp_max=12, vmax=1.0, lmin=5)

# or, if we already knew there were 5 segments:
cps_fixed, cost = cpd_nonlin(K, ncp=4, lmin=5)

What you get

Running python demo.py produces:

sequence length n = 150
true change points = [40, 65, 100, 120]  (5 segments)

[cpd_auto]   change points = [40, 65, 100, 120]  (5 segments)
[cpd_nonlin] change points = [40, 65, 100, 120]  (fixed m=4, total scatter=4.04)

fixed-m boundary errors (frames): [0, 0, 0, 0]  (mean 0.00)

🎯 Both modes recover all four true change points exactly, and cpd_auto independently figures out that there are 5 segments, without being told.

If Matplotlib is installed, the demo also saves kts_demo.png showing the feature heatmap with true boundaries (white dashed) and detected boundaries (red) overlaid.

Things to try next

• Make it harder. Increase the per-cluster noise (scale=0.4) until segmentation starts to fail: that's the signal-to-noise limit.
• Change the kernel. Swap "cosine" for "rbf" and watch how the bandwidth $\sigma$ changes sensitivity.
• Tune vmax. Lower it toward 0 to over-segment; raise it to merge.
• Plot the scores. scores from cpd_auto vs $m$ reveals the elbow that the penalty is exploiting.
• Real features. Replace X with CNN features extracted one-per-second from a real video, then map change points back to timestamps.

That's KTS, from the math all the way to a working segmenter. 🎉

Finally, let's step back and look at the research paper this all came from, how to read it, how to reproduce a paper like it, and where KTS is used. 👉

The original paper: understand & reproduce

So far we built KTS as if from thin air. In reality, KTS comes from a research paper, and the previous chapters are a reproduction of one piece of it. This chapter steps back and tells that story: what the paper actually says, how to read a paper like it, the general process of turning any paper into working code, and an honest reflection on what we built versus what the paper specifies.

The paper

Danila Potapov, Matthijs Douze, Zaid Harchaoui, Cordelia Schmid. Category-Specific Video Summarization. ECCV 2014.

The paper's main goal is video summarization: given a long video and a known category (e.g. "changing a tire", "making a sandwich"), produce a short summary that keeps the important moments for that category. KTS, "Kernel Temporal Segmentation", is one component of that system, not the whole thing.

The paper's pipeline, roughly:

1. Describe each frame with features (visual descriptors).
2. Segment the video into shots: this is KTS, the part we reproduced.
3. Score each segment for importance using a category-specific model.
4. Select the highest-scoring segments under a length budget to form the summary.

We rebuilt step 2. It's a clean, self-contained algorithm with a precise objective, which makes it an ideal target for a "from scratch" reproduction.

Where the idea comes from

KTS didn't appear out of nowhere either: it adapts kernel change-point detection from the statistics/machine-learning literature (notably Harchaoui & Cappé, Retrospective Multiple Change-Point Estimation with Kernels, 2007, and related work on penalized model selection by Arlot, Celisse and others). The paper's contribution here is applying that machinery to video frames and wiring it into a summarization system. Recognizing this lineage is useful: when the paper is terse about a detail, the cited prior work usually spells it out.

How to read a paper like this

Research papers are dense and are not meant to be read top-to-bottom like a tutorial. A practical recipe (a version of Keshav's well-known "three-pass" method):

Pass 1, the 5-minute skim. Read the title, abstract, figures, and section headings. Goal: What problem? What's the key idea? Is this even the part I need? For us, the realization is "the summarization framing is interesting, but the reusable algorithm is the temporal segmentation."

Pass 2, the method, carefully. Read the algorithm/method section and its math, but skip proofs and most experiments. Write down, in your own words:

• the inputs and outputs (in: per-frame features; out: change points),
• the objective (minimize total within-segment kernel variance),
• the algorithm (dynamic programming),
• the hyperparameters (kernel choice, number of segments / penalty weight),
• the complexity (so you know if it'll scale).

Pass 3, reproduce. Re-derive the key equations and implement them. This is the only pass that truly tests understanding, and it's the rest of this book.

Tip: keep a one-page "notation sheet" as you read. Papers reuse symbols heavily ($K$, $\phi$, $\mu$, $n$, $m$…); a glossary you write yourself prevents most confusion. Our math chapter literally opens with one.

From paper to code: the general process

Reproducing a paper is a repeatable craft. The steps we followed, and that transfer to almost any algorithmic paper:

1. Isolate the algorithm. Separate the reusable core (objective + DP) from the surrounding system (the summarization pipeline) you don't need.
2. Translate math into data structures. Each mathematical object becomes a concrete array:
   • kernel $K_{ij}$ → an n × n NumPy matrix (Chapter 3),
   • segment scatter $v(i,j)$ → a precomputed cost table (Chapter 4),
   • the DP recurrence $C[k,\ell]$ → a 2-D table filled bottom-up (Chapter 5).
3. Make the slow thing fast. The naive scatter is too slow, so we used the cumulative-sum trick. Papers often state the efficient form without derivation; reconstructing it is part of the work.
4. Fill the gaps. Papers omit details for space. The biggest gap here is the exact model-selection penalty for choosing the number of segments. We reconstructed it from the algorithm's intent and the companion reference code (more below).
5. Validate against ground truth. Build synthetic data where you know the answer and check the code recovers it (Chapter 8), plus internal sanity checks (kernel symmetry; scatter matching its definition).
6. Reflect on the differences. Document where your version diverges and why the next section does exactly that.

What the paper specifies vs. what we filled in

Being honest about the boundary between "from the paper" and "our choices" is part of a good reproduction.

A reflection on the penalty (and a real bug we hit)

The trickiest "gap" was the penalty that decides how many segments to keep. Our first attempt made the penalty proportional to the scatter: which seems reasonable but is wrong: as the scatter shrinks toward zero, the penalty vanishes, so extra cuts become free and the algorithm never stops splitting. We caught this because our auto-selection demo returned absurdly many segments.

The fix matches the widely-used KTS reference implementation: a penalty that grows with the number of change points, independent of the scatter:

$$ \text{penalty}(m) = \frac{m}{2n}\,\Big(\log\!\big(\tfrac{n}{m}\big) + 1\Big). $$

This is the lesson of step 4 above in miniature: the paper tells you a penalty exists and what it must accomplish; getting the exact form right takes a careful read of the criterion (and, when available, the authors' released code). It's also a reminder that validation catches reproduction bugs that "it compiles and looks plausible" never would.

How KTS is used: general use cases

KTS solves a generic problem, split an ordered sequence into homogeneous segments, so it's useful well beyond the original paper:

• Video summarization (its home turf). Standard preprocessing for benchmarks like TVSum and SumMe: segment first, score segments, then select.
• Shot / scene boundary detection. Find where one shot ends and the next begins, for indexing, editing, or thumbnail selection.
• Generic change-point detection. Any sequential signal where the distribution shifts in blocks: sensor streams, financial/time-series data, audio segmentation, EEG, activity logs. Swap in a kernel appropriate to the data and KTS works unchanged.
• A preprocessing step for downstream models. Whenever you want to classify or score segments rather than individual samples, KTS gives you the segments.

When KTS is a good fit, and when it isn't

Good fit when:

• the signal is genuinely piecewise-homogeneous (blocks that are internally consistent), and
• you can compute, or already have, per-item features and a sensible kernel.

Reach for something else when:

• the sequence is very long, the kernel matrix is $n \times n$, so you must subsample (e.g. one feature per second) and map results back;
• you need online/streaming detection, KTS is retrospective (it looks at the whole sequence at once), not real-time;
• segments aren't well modeled as "constant-ish then a jump" (e.g. slow drifts).

A reusable checklist for reproducing any paper

1. Skim for the one idea and locate the part you actually need.
2. Write your own notation sheet and a plain-English statement of inputs, outputs, objective, and algorithm.
3. Map each math object to a concrete data structure.
4. Implement the naive version first; optimize only once it's correct.
5. Identify gaps the paper leaves; fill them from cited work or released code, and record your assumptions.
6. Validate on data with known answers, plus internal invariants.
7. Document the deltas between your version and the paper.

That's the full arc: from a dense ECCV paper to a small, correct, well-understood implementation you can read, run, and reuse. 🎓

See the References for the paper and its intellectual roots.

One-file CLI: KTS on a real video

Everything in this book, distilled into one self-contained script that runs on an actual video file and does a useful job: automatic shot detection + storyboard extraction (one keyframe per shot). The KTS core is plain NumPy, written from scratch; only video decoding uses OpenCV.

The steps

1. Sample frames. Decode the video and keep ~1 frame per second.
2. Describe each frame. Compute an HSV color histogram, a model-free numeric fingerprint of the frame.
3. Build the kernel. Make the n × n similarity matrix K between frames (cosine by default).
4. Cost table. Precompute every segment's within-segment scatter J[i,j] using cumulative sums (instant lookups).
5. Segment. Dynamic programming (cpd_nonlin) finds the optimal cuts for a given count; cpd_auto adds a penalty and chooses the count for you.
6. Map back & report. Convert sampled-frame cuts to real timestamps, print a shot table, and save one keyframe per shot.

Install & run

pip install numpy opencv-python

# auto-detect shots and save a keyframe per shot into ./keyframes/
python kts_video.py myvideo.mp4

# sample 2 fps, fewer shots (higher penalty), custom output dir
python kts_video.py myvideo.mp4 --fps 2 --vmax 1.5 --outdir shots

# force an exact number of shots
python kts_video.py myvideo.mp4 --num-shots 8

# just print the shot table, no images
python kts_video.py myvideo.mp4 --no-keyframes

What it prints

[1/4] decoding & sampling myvideo.mp4 at 1.0 fps ...
      183 frames sampled (4575 total, 25.00 fps source)
[2/4] building cosine kernel matrix (183x183) ...
[3/4] auto-selecting shots (vmax=1.0) ...
[4/4] found 7 shots:

  shot       start         end      dur
  --------------------------------------
     0     0:00:00.0     0:00:21.0    21.0s
     1     0:00:21.0     0:00:48.0    27.0s
     2     0:00:48.0     0:01:33.0    45.0s
     ...
saved 7 keyframes to ./keyframes/

You get a timestamped shot list plus keyframes/shot_000.jpg, shot_001.jpg, … a ready-made storyboard, and exactly the preprocessing step video-summarization pipelines need.

The exact numbers above are illustrative (they depend on your video). The shot count adapts to content via the penalty; tune it with --vmax (higher → fewer shots) or pin it with --num-shots.

The complete script

#!/usr/bin/env python3
"""
kts_video.py — Kernel Temporal Segmentation on a real video, from scratch.

A single-file command-line tool that:
  1. decodes a video and samples frames (e.g. 1 per second),
  2. describes each sampled frame with a color histogram (no deep model needed),
  3. builds a kernel (similarity) matrix between frames,
  4. runs Kernel Temporal Segmentation to find shot boundaries,
  5. prints a shot table (start/end timestamps) and saves one keyframe per shot
     — i.e. an automatic storyboard / video-summary preprocessing step.

The KTS core (scatter table + dynamic programming + auto model selection) is
implemented here in plain NumPy. Only video decoding uses OpenCV.

Usage:
    python kts_video.py path/to/video.mp4
    python kts_video.py video.mp4 --fps 2 --vmax 1.0 --outdir shots
    python kts_video.py video.mp4 --num-shots 8        # force exactly 8 shots

Requirements:
    pip install numpy opencv-python
"""

from __future__ import annotations

import argparse
import os
import sys

import numpy as np


# ===========================================================================
# 1. Feature extraction — turn each sampled frame into a number vector
# ===========================================================================
def color_histogram(frame_bgr, bins=8):
    """
    Describe a frame by an HSV color histogram (a robust, model-free fingerprint).

    Returns a 1-D feature vector of length 3*bins, normalized to sum to 1.
    """
    import cv2

    hsv = cv2.cvtColor(frame_bgr, cv2.COLOR_BGR2HSV)
    h = np.histogram(hsv[:, :, 0], bins=bins, range=(0, 180))[0]
    s = np.histogram(hsv[:, :, 1], bins=bins, range=(0, 256))[0]
    v = np.histogram(hsv[:, :, 2], bins=bins, range=(0, 256))[0]
    feat = np.concatenate([h, s, v]).astype(np.float64)
    total = feat.sum()
    return feat / total if total > 0 else feat


def extract_features(path, target_fps=1.0, bins=8):
    """
    Decode `path`, sample ~target_fps frames per second, and return:
        X            : (n_sampled, 3*bins) feature matrix
        frame_index  : original frame number of each sampled frame
        src_fps      : the video's real frame rate
        n_total      : total number of frames in the video
    """
    import cv2

    cap = cv2.VideoCapture(path)
    if not cap.isOpened():
        raise SystemExit(f"error: could not open video {path!r}")

    src_fps = cap.get(cv2.CAP_PROP_FPS) or 25.0
    n_total = int(cap.get(cv2.CAP_PROP_FRAME_COUNT) or 0)
    step = max(1, int(round(src_fps / max(target_fps, 1e-6))))

    feats, frame_index = [], []
    i = 0
    while True:
        ok, frame = cap.read()
        if not ok:
            break
        if i % step == 0:
            feats.append(color_histogram(frame, bins=bins))
            frame_index.append(i)
        i += 1
    cap.release()

    if len(feats) < 2:
        raise SystemExit("error: video too short / too few sampled frames")
    return np.array(feats), np.array(frame_index), src_fps, (n_total or i)


# ===========================================================================
# 2. Kernel (similarity) matrix
# ===========================================================================
def build_kernel(X, kind="cosine", eps=1e-8):
    """Similarity grid K[i, j] between every pair of frame fingerprints."""
    X = np.asarray(X, dtype=np.float64)
    if kind == "linear":
        return X @ X.T
    if kind == "cosine":
        norms = np.linalg.norm(X, axis=1, keepdims=True)
        Xn = X / np.maximum(norms, eps)
        return Xn @ Xn.T
    if kind == "rbf":
        sq = np.sum(X ** 2, axis=1)
        d2 = np.maximum(sq[:, None] + sq[None, :] - 2.0 * (X @ X.T), 0.0)
        pos = d2[d2 > 0]
        sigma = np.sqrt(0.5 * np.median(pos)) if pos.size else 1.0
        return np.exp(-d2 / (2.0 * max(sigma, eps) ** 2))
    raise ValueError(f"unknown kernel {kind!r}")


# ===========================================================================
# 3. Scatter (cost) table — within-segment variance for every segment, fast
# ===========================================================================
def calc_scatters(K):
    """J[i, j] = within-segment scatter of frames i..j, via prefix sums."""
    K = np.asarray(K, dtype=np.float64)
    n = K.shape[0]
    dcum = np.concatenate(([0.0], np.cumsum(np.diag(K))))
    Kcum = np.zeros((n + 1, n + 1))
    Kcum[1:, 1:] = np.cumsum(np.cumsum(K, axis=0), axis=1)

    J = np.zeros((n, n))
    for i in range(n):
        js = np.arange(i, n)
        L = js - i + 1
        diag_sum = dcum[js + 1] - dcum[i]
        block = (Kcum[js + 1, js + 1] - Kcum[i, js + 1]
                 - Kcum[js + 1, i] + Kcum[i, i])
        J[i, i:] = diag_sum - block / L
    return J


# ===========================================================================
# 4. Dynamic programming — optimal cuts for a fixed number of change points
# ===========================================================================
def cpd_nonlin(K, ncp, lmin=1, lmax=None, J=None):
    """Globally optimal segmentation with exactly `ncp` change points."""
    n = K.shape[0]
    m = int(ncp)
    if lmax is None:
        lmax = n
    if (m + 1) * lmin > n:
        raise ValueError("sequence too short for this many change points")
    if J is None:
        J = calc_scatters(K)

    INF = 1e18
    C = np.full((m + 1, n + 1), INF)
    back = np.zeros((m + 1, n + 1), dtype=int)
    for l in range(lmin, min(lmax, n) + 1):
        C[0, l] = J[0, l - 1]
    for k in range(1, m + 1):
        for l in range((k + 1) * lmin, n + 1):
            t_lo = max(k * lmin, l - lmax)
            t_hi = l - lmin
            if t_lo > t_hi:
                continue
            ts = np.arange(t_lo, t_hi + 1)
            cand = C[k - 1, ts] + J[ts, l - 1]
            idx = int(np.argmin(cand))
            C[k, l] = cand[idx]
            back[k, l] = ts[idx]

    cps = np.zeros(m, dtype=int)
    l = n
    for k in range(m, 0, -1):
        t = back[k, l]
        cps[k - 1] = t
        l = t
    return cps, float(C[m, n])


# ===========================================================================
# 5. Automatic model selection — let KTS choose the number of shots
# ===========================================================================
def cpd_auto(K, ncp_max, vmax=1.0, lmin=1, lmax=None):
    """Pick the number of change points by a penalized score; return cuts."""
    n = K.shape[0]
    ncp_max = min(ncp_max, n - 1)
    J = calc_scatters(K)
    best_score, best_cps = np.inf, np.array([], dtype=int)
    for m in range(0, ncp_max + 1):
        if (m + 1) * lmin > n:
            break
        cps, J_m = cpd_nonlin(K, m, lmin=lmin, lmax=lmax, J=J)
        penalty = 0.0 if m == 0 else (m / (2.0 * n)) * (np.log(n / m) + 1.0)
        score = J_m / n + vmax * penalty
        if score < best_score:
            best_score, best_cps = score, cps
    return best_cps


# ===========================================================================
# Helpers: segments, timestamps, keyframes
# ===========================================================================
def segments_from_cps(cps, n):
    """Turn change points into (start, end) index pairs covering 0..n-1."""
    bounds = [0] + list(cps) + [n]
    return [(bounds[i], bounds[i + 1] - 1) for i in range(len(bounds) - 1)]


def fmt_time(seconds):
    """Seconds -> H:MM:SS.s timestamp string."""
    h = int(seconds // 3600)
    m = int((seconds % 3600) // 60)
    s = seconds % 60
    return f"{h}:{m:02d}:{s:04.1f}"


def save_keyframes(path, segments, frame_index, outdir, max_side=480):
    """Save one representative frame (segment midpoint) per shot into outdir."""
    import cv2

    os.makedirs(outdir, exist_ok=True)
    cap = cv2.VideoCapture(path)
    saved = []
    for k, (a, b) in enumerate(segments):
        mid_sampled = (a + b) // 2
        src_frame = int(frame_index[mid_sampled])
        cap.set(cv2.CAP_PROP_POS_FRAMES, src_frame)
        ok, frame = cap.read()
        if not ok:
            continue
        h, w = frame.shape[:2]
        if max(h, w) > max_side:
            scale = max_side / max(h, w)
            frame = cv2.resize(frame, (int(w * scale), int(h * scale)))
        out = os.path.join(outdir, f"shot_{k:03d}.jpg")
        cv2.imwrite(out, frame)
        saved.append(out)
    cap.release()
    return saved


# ===========================================================================
# Command-line interface
# ===========================================================================
def main(argv=None):
    p = argparse.ArgumentParser(
        description="Detect shots in a video with Kernel Temporal Segmentation "
                    "and save one keyframe per shot (a storyboard).")
    p.add_argument("video", help="path to the input video file")
    p.add_argument("--fps", type=float, default=1.0,
                   help="frames sampled per second (default: 1)")
    p.add_argument("--vmax", type=float, default=1.0,
                   help="penalty weight; larger = fewer shots (default: 1.0)")
    p.add_argument("--num-shots", type=int, default=None,
                   help="force an exact number of shots (skips auto-selection)")
    p.add_argument("--max-shots", type=int, default=100,
                   help="upper bound for auto-selection (default: 100)")
    p.add_argument("--min-shot-sec", type=float, default=1.0,
                   help="minimum shot length in seconds (default: 1.0)")
    p.add_argument("--kernel", choices=["cosine", "linear", "rbf"],
                   default="cosine", help="similarity kernel (default: cosine)")
    p.add_argument("--bins", type=int, default=8,
                   help="histogram bins per channel (default: 8)")
    p.add_argument("--outdir", default="keyframes",
                   help="directory for keyframe images (default: keyframes)")
    p.add_argument("--no-keyframes", action="store_true",
                   help="only print the shot table; do not save images")
    args = p.parse_args(argv)

    # Step 1–2: features + kernel
    print(f"[1/4] decoding & sampling {args.video} at {args.fps} fps ...")
    X, frame_index, src_fps, n_total = extract_features(
        args.video, target_fps=args.fps, bins=args.bins)
    print(f"      {len(X)} frames sampled ({n_total} total, {src_fps:.2f} fps source)")

    print(f"[2/4] building {args.kernel} kernel matrix ({len(X)}x{len(X)}) ...")
    K = build_kernel(X, kind=args.kernel)

    # Step 3–5: segmentation
    sample_dt = (frame_index[1] - frame_index[0]) / src_fps if len(frame_index) > 1 else 1.0
    lmin = max(1, int(round(args.min_shot_sec / max(sample_dt, 1e-6))))
    if args.num_shots:
        print(f"[3/4] segmenting into exactly {args.num_shots} shots ...")
        cps, _ = cpd_nonlin(K, args.num_shots - 1, lmin=lmin)
    else:
        print(f"[3/4] auto-selecting shots (vmax={args.vmax}) ...")
        cps = cpd_auto(K, args.max_shots, vmax=args.vmax, lmin=lmin)

    segments = segments_from_cps(cps, len(X))

    # Report
    print(f"[4/4] found {len(segments)} shots:\n")
    print(f"  {'shot':>4}  {'start':>10}  {'end':>10}  {'dur':>7}")
    print("  " + "-" * 38)
    for k, (a, b) in enumerate(segments):
        t0 = frame_index[a] / src_fps
        t1 = (frame_index[b] / src_fps) + sample_dt
        print(f"  {k:>4}  {fmt_time(t0):>10}  {fmt_time(t1):>10}  {t1 - t0:>6.1f}s")

    if not args.no_keyframes:
        saved = save_keyframes(args.video, segments, frame_index, args.outdir)
        print(f"\nsaved {len(saved)} keyframes to ./{args.outdir}/")


if __name__ == "__main__":
    main()

That's the whole tool: decode → fingerprint → kernel → DP → timestamps, in one file you can read top to bottom.

What is a sound bite? (and why segmentation finds it)

So far this book has cut video into shots. The same machine cuts audio into pieces, and once you can cut audio you can pull out its most quotable moments: sound bites. This short section (Chapters 11 to 15) is the audio counterpart of everything you have already built.

The one-sentence idea

A sound bite is a short, self-contained excerpt of audio that stands on its own: a quotable sentence from an interview, the chorus of a song, the punch line of a podcast. Finding sound bites means two things. First, decide where the audio naturally breaks. Then decide which pieces are worth keeping.

An everyday analogy

You have listened to a 40-minute interview and a producer says: "give me the three best 8-second clips for social media." In your head you do two things. You mentally chop the recording where the sound changes (host talking, guest talking, laughter, a musical sting, silence), then you skim those chunks and keep the few that are loud, clear, and complete. A computer follows the same two steps, and step one is change-point detection, which is what KTS already does.

Why is it needed?

Raw audio is a long, undifferentiated stream of numbers. Almost anything useful you want to do with it first needs it sliced into meaningful pieces:

• Social and marketing clips. Auto-cut the ten most shareable seconds from a podcast or speech.
• Search and navigation. "Jump to the part where they talk about pricing" needs the audio indexed by segment.
• Captioning and transcription. Speech recognizers work far better on short, homogeneous chunks than on a 60-minute blob.
• Highlight reels. Sports commentary, lecture recaps, trailer audio.
• Data prep for ML. Just as KTS prepares video for summarization datasets, audio segmentation prepares clips for training and evaluation.

Don't be confused: sound bite vs. shot vs. utterance. A shot is a visual segment, which was KTS's original job. An utterance is one continuous bit of speech from one speaker. A sound bite is a curated excerpt, usually one utterance or a few, chosen because it stands on its own. All three are temporal segments. They differ only in what makes a boundary and what makes a piece worth keeping.

How does it work? (the two-step view)

   raw waveform                                      ranked sound bites
   ~~~~~~~~~~~~~                                      ~~~~~~~~~~~~~~~~~~~
   ░░▒▓██▓▒░░▒▓██▓▒  ──▶  features  ──▶  KTS cuts  ──▶  score each  ──▶  🏆 0:21-0:25
   (440k samples)        (one vector       (where the     segment        🥈 0:03-0:09
                          per frame)        sound          for "bite-      …
                                            changes)        worthiness")

1. Where does the sound change? Turn the waveform into a sequence of feature vectors, one per short frame, then find the change points. This is the same thing KTS does on video. Only the feature vectors come from audio instead of pixels (Chapter 12).
2. Which pieces are worth keeping? Score each resulting segment (loud enough? clear speech, not noise or silence? right length?) and rank (Chapter 15).

Why KTS is a natural fit

KTS never assumed its input was video. Re-read its contract: it takes a sequence of feature vectors $x_1,\dots,x_n \in \mathbb{R}^d$ and finds boundaries so that each segment is internally consistent (Introduction). It does not care whether each $x_t$ describes a video frame or a 50-millisecond slice of sound.

Everything in the middle stays the same: the kernel (Ch. 1 to 3), the scatter cost (Ch. 4), and the dynamic program (Ch. 5 to 6) are all reused without changes. In Chapter 15 we literally import kts.py and feed it audio.

A concrete teaser

Chapter 15's lab builds a 25-second clip with six known regions (silence, speech, silence, music, applause, speech) and asks KTS to find the boundaries blind. It recovers all five exactly, then ranks the speech segments as the best bites:

KTS found 5 cut points at: 0:03.0, 0:09.0, 0:12.0, 0:18.0, 0:21.0

top bite: 0:21.0 - 0:25.0 (4.0s, score 0.81)

That is the whole story in miniature: the same KTS you already understand, cutting sound instead of pictures, with a small scoring step on top.

Next: how a waveform becomes the feature vectors KTS expects. 👉

From frames to audio features

KTS eats feature vectors. A video gave us one vector per image; audio has no images, so we build the vectors from the raw sound. This chapter shows, in phases, how a waveform becomes the (n, d) array KTS expects, and why the features we pick make speech, music, silence, and noise look obviously different.

Phase 0: what a waveform actually is

Recorded sound is air pressure measured many thousands of times per second. Each measurement is one number (a sample); the sample rate sr is how many we take per second (16,000 Hz is plenty for speech). A 25-second clip at 16 kHz is just an array of $25 \times 16000 = 400{,}000$ numbers.

amplitude
   +1 ┤      ╭╮        ╭─╮
    0 ┤─╮╭╮╭─╯╰╮╭──╮╭─╯ ╰╮╭─   ...  (400,000 of these)
   -1 ┤  ╰╯╰╯  ╰╯  ╰╯    ╰╯
      └────────────────── time →

That raw array is too long and too low-level to hand to KTS directly (400k "frames" of one number each). We compress it into a shorter sequence of richer descriptors.

Phase 1: framing, chop the stream into short frames

Sound changes slowly compared to its sample rate, so we analyse it in short frames, typically 20 to 50 ms, that overlap by a fixed hop so we do not miss events on a boundary. With a 50 ms window and a 25 ms hop, our 25-second clip becomes about 1000 frames.

def frame_signal(wave, sr, win_ms=50.0, hop_ms=25.0):
    win = int(sr * win_ms / 1000)        # 800 samples
    hop = int(sr * hop_ms / 1000)        # 400 samples
    n = 1 + (wave.size - win) // hop
    idx = np.arange(win)[None, :] + hop * np.arange(n)[:, None]
    return wave[idx], win, hop            # (n_frames, win)

Don't be confused: "frame" here vs. in the video book. In the video chapters a frame was one whole image. In audio a frame is one short time window of the waveform. Same word, same role for KTS (it is the unit we describe with a vector and segment between), different physical thing.

Phase 2: describe each frame with a few numbers

Each frame is still hundreds of raw samples. We summarise it with a handful of features that capture how it sounds. Five classic, model-free ones are enough to tell our four content types apart:

The frequency-domain features come from the FFT, a standard transform that tells you which pitches are present in a frame. We do not derive the FFT here; NumPy gives it to us as np.fft.rfft. The point is that energy, ZCR, and three spectral numbers form a 5-dimensional description of each frame:

spec   = np.abs(np.fft.rfft(frame * np.hanning(win)))   # magnitude spectrum
power  = spec ** 2
freqs  = np.fft.rfftfreq(win, d=1.0 / sr)
centroid = (freqs * power).sum() / power.sum()           # one of the five

So our audio is now exactly what KTS wants:

$$ x_1, x_2, \dots, x_n \in \mathbb{R}^5 \qquad (\text{one 5-vector per frame}). $$

Phase 3: do the features really separate the content?

This is the test that matters: if speech, music, silence, and noise produce visibly different feature vectors, KTS will find the boundaries between them. Averaging each feature over each known region of the lab clip (Chapter 15) gives:

per-region mean features:
region     log_energy        zcr   centroid  bandwidth   flatness
silence        -6.178      0.498   3978.086   2297.462      0.558
speech         -2.212      0.173   1006.251    878.143      0.127
silence        -6.172      0.504   3980.467   2290.049      0.557
music          -1.409      0.037    279.154    106.577      0.001
applause       -2.446      0.499   3973.502   2304.736      0.560
speech         -2.210      0.175   1053.582    892.559      0.126

Read it as a table of signatures. Every content type has its own:

• silence is by far the quietest (log_energy ≈ -6.2); its "spectrum" is just faint hiss, so flatness is high and the centroid is bright but meaningless.
• speech has moderate energy, low ZCR (0.17), and low flatness (0.13): voiced and tonal. This is the bite-worthy signature.
• music is loudest, with near-zero ZCR and flatness near 0 (a purely tonal chord).
• applause is about as loud as speech but has flatness ≈ 0.56 and ZCR ≈ 0.50, the clear noise signature.

Notice that the two speech regions (rows 2 and 6) have almost identical signatures even though one is pitched higher. That is what we want: same content type means same signature, so KTS keeps each one as a coherent segment.

Phase 4: one last step, standardize

The five features live on very different scales (energy near -6, centroid near 4000). A kernel would let the centroid drown out everything else. So before building the kernel we z-score each column (subtract its mean, divide by its standard deviation) so all five count equally:

def zscore(features):
    mu = features.mean(axis=0, keepdims=True)
    sd = features.std(axis=0, keepdims=True)
    return (features - mu) / np.maximum(sd, 1e-8)

Don't be confused: standardizing vs. the cosine kernel. The cosine kernel rescales each frame vector to unit length (direction only). Z-scoring rescales each feature column so no single feature dominates. They solve different problems; for these mixed-scale audio features, z-scoring first is what makes the kernel behave.

That is the whole front end: waveform, then frames, then five features, then standardize. The output is a clean (n, 5) array, and from here on it is just KTS. Next we survey the common ways people turn these segments into sound bites. 👉

Common ways of handling sound bites

There is more than one way to chop audio and pick the good parts. KTS is one member of a family. This chapter is the map: the main approaches, what each is good and bad at, and where KTS sits among them. Knowing the alternatives is what lets you choose KTS on purpose instead of by default.

Recall the two sub-problems from Chapter 11: where are the boundaries, and which segments are bites? Most methods specialise in one of the two; a real system combines them.

A. Finding the boundaries

1. Silence / energy thresholding

Cut wherever the volume drops below a threshold for long enough. This is how "split on pauses" works in most editors. It is trivial, instant, and needs no model, which makes it a good first pass for clearly-spaced speech. It is also easily fooled by background noise and by speakers who do not pause, and it ignores what the sound is, so it will not split speech from music when both are loud.

2. Voice Activity Detection (VAD)

A smarter "is this speech?" classifier (energy and spectral cues, or a small neural net) marks speech vs. non-speech regions, and boundaries fall at the transitions. It is robust to noise and is the standard first step in speech pipelines. Its weakness is that it only knows speech from non-speech: it will not separate two speakers or tell speech from music, and it gives no sense of which segment is best.

3. Change-point detection on features (this is KTS)

Describe each frame with features (Chapter 12), then find the boundaries that make each segment internally consistent. KTS does this optimally with a kernel and dynamic programming. Because it reacts to any change in the fingerprint rather than just volume, it splits speech, music, applause, and silence in one pass. The dynamic program is globally optimal, and you can fix the number of cuts or let the penalty choose it (Ch. 6). The costs: it needs good features, and it runs in $O(n^2)$ in the number of frames, so very long audio wants coarse frames or a windowed approach.

4. Speaker diarization ("who spoke when")

Cluster frames by speaker identity using voice embeddings; boundaries fall where the speaker changes. This is exactly right when a bite is "one clean quote from one person." It is also heavier (it needs an embedding model plus clustering) and is overkill when you do not care who is talking.

5. Transcript / NLP boundaries

Run speech-to-text first, then cut on sentence boundaries from the text. Bites then land on grammatically complete sentences, which is ideal for quotes and captions. The catch is that it depends on transcription quality and does nothing for music or other non-speech audio.

Don't be confused: these are layers, not rivals. A production pipeline often stacks them: VAD to drop silence, then KTS (or diarization) to segment, then a transcript to snap cuts onto sentence edges. KTS is the general segmenter that works without a transcript or a speaker model.

B. Choosing which segments are bites

Once you have segments, you rank them. Common signals:

The lab in Chapter 15 uses the first three (energy, voicedness, length) straight from the features, with no extra model, and that already ranks speech above music, applause, and silence. The richer signals (semantic salience, supervised scoring) are what Chapter 14 adds with modern tools.

Where KTS fits: a decision cheat-sheet

The throughline: KTS is the boundary engine. It gives you clean, optimal, content-aware segments without a transcript, a speaker model, or labelled training data, and every other technique either feeds it (VAD, features) or builds on its output (scoring, NLP). Next we look at the specific tools and algorithms people use to build each layer. 👉

Trending tools & algorithms

Chapter 13 mapped the approaches; this chapter names the tools people actually reach for in 2024 and 2025 to build each layer, with minimal follow-along snippets. Our from-scratch NumPy pipeline (Chapter 15) is the spine; these are the production-grade parts you would swap in.

Follow-along, not run-here. These libraries (librosa, whisper, pyannote, ruptures, and the rest) are not installed in this book's verification environment, so the outputs below are illustrative. They show the shape of what you will see, not a value captured on this machine. The pure-NumPy code in Chapter 15 is run and verified. Install with the pip line shown above each block.

Layer 1: better features

librosa, the standard audio-feature toolkit

It covers everything we hand-rolled in Chapter 12 (framing, FFT, centroid, ZCR) plus the feature the field uses most: MFCCs (mel-frequency cepstral coefficients), a compact, perceptually-tuned fingerprint.

pip install librosa

import librosa
y, sr = librosa.load("clip.wav", sr=16000)          # waveform
mfcc  = librosa.feature.mfcc(y=y, sr=sr, n_mfcc=20)  # (20, n_frames)
feats = mfcc.T                                        # (n_frames, 20) -> feed to KTS
print(feats.shape)

(1003, 20)         # ~1000 frames, 20-D each, drop straight into build_kernel(...)

Why this matters for KTS: swapping our five hand-features for feats above changes nothing downstream. build_kernel(feats) and cpd_auto work as-is. Better features give cleaner boundaries from the same engine.

Learned embeddings: wav2vec2, CLAP

For state-of-the-art fingerprints, use a pretrained audio encoder. wav2vec 2.0 (speech) and CLAP (general audio and text) turn each frame or clip into a rich vector. These are the audio analog of the CNN embeddings the video book mentions, and again they are just a different X into KTS.

Layer 2: boundaries

ruptures, change-point detection as a library

This is the closest published cousin of KTS. ruptures implements the same penalized dynamic-programming idea (Ch. 5 to 6), including kernel cost functions and PELT, a faster, pruned dynamic program for when you do not fix the number of cuts.

pip install ruptures

import ruptures as rpt
algo = rpt.KernelCPD(kernel="rbf").fit(feats)   # same kernel idea as this book
bkps = algo.predict(pen=10)                      # penalty replaces our vmax
print(bkps)

[120, 360, 480, 720, 840, 1003]   # change points (frame indices), like our cps

Don't be confused: ruptures vs. kts.py. They optimise the same objective. KTS in this book is the from-scratch, fixed-or-auto-count version built for video; ruptures is the general-purpose, well-optimised library with extra cost functions and PELT pruning. Understand kts.py, then reach for ruptures in production.

Silero VAD and webrtcvad, voice activity detection

Fast, tiny speech vs. non-speech gates. Use them to drop silence before KTS so the $O(n^2)$ cost is spent only on real content.

pip install silero-vad

from silero_vad import load_silero_vad, get_speech_timestamps, read_audio
model = load_silero_vad()
wav   = read_audio("clip.wav", sampling_rate=16000)
speech = get_speech_timestamps(wav, model, return_seconds=True)
print(speech[:2])

[{'start': 3.0, 'end': 9.0}, {'start': 21.0, 'end': 25.0}]   # speech-only spans

pyannote.audio, speaker diarization

The de-facto open-source diarizer ("who spoke when"). When bites are "one clean quote per speaker," its boundaries are the cuts you want.

pip install pyannote.audio

from pyannote.audio import Pipeline
pipe = Pipeline.from_pretrained("pyannote/speaker-diarization-3.1")
for turn, _, spk in pipe("clip.wav").itertracks(yield_label=True):
    print(f"{turn.start:5.1f}-{turn.end:5.1f}  {spk}")

  3.0-  9.0  SPEAKER_00
 21.0- 25.0  SPEAKER_01

Layer 3: transcript and sentence boundaries

faster-whisper, speech-to-text with timestamps

Whisper (and the speed-optimised faster-whisper) transcribes audio with per-segment timestamps, letting you snap bite edges onto complete sentences.

pip install faster-whisper

from faster_whisper import WhisperModel
model = WhisperModel("base")
segments, _ = model.transcribe("clip.wav")
for s in segments:
    print(f"[{s.start:5.1f}-{s.end:5.1f}] {s.text}")

[ 3.0-  9.0]  The single most important thing we learned this year ...
[21.0- 25.0]  ... and that's why it completely changed our roadmap.

Layer 4: choosing the best bite (semantic)

Boundaries get you candidates; ranking by meaning gets you the best bite. Two trending routes:

Embedding similarity with sentence-transformers

Embed each candidate's transcript and score it against a query ("the most surprising claim") or against the whole talk's centroid (most representative).

pip install sentence-transformers

from sentence_transformers import SentenceTransformer, util
enc = SentenceTransformer("all-MiniLM-L6-v2")
emb = enc.encode([c.text for c in candidates])
query = enc.encode("the most surprising, quotable claim")
ranked = util.cos_sim(query, emb)[0].argsort(descending=True)

LLM-as-judge: pick bites with Claude

The most flexible recent approach: hand a model the timestamped transcript and ask it to choose and justify the best clips. Using the Anthropic SDK with the current model id claude-opus-4-8:

pip install anthropic

import anthropic
client = anthropic.Anthropic()
transcript = "\n".join(f"[{c.start:.1f}-{c.end:.1f}] {c.text}" for c in candidates)
msg = client.messages.create(
    model="claude-opus-4-8",
    max_tokens=400,
    messages=[{"role": "user", "content":
        "Here is a timestamped transcript. Pick the 3 best 8-second sound bites "
        "for social media. Return start/end timestamps and a one-line reason.\n\n"
        + transcript}],
)
print(msg.content[0].text)

1. 0:21-0:25  : punchy payoff line; complete sentence; strong verb ("changed").
2. 0:03-0:09  : sets up the year's key lesson; self-contained.
3. ...

The pattern: KTS, ruptures, or diarization produce candidate segments; the LLM or embedding step ranks them by meaning. The acoustic layer decides where, the semantic layer decides which, which is the same two-step split from Chapter 11.

How it all stacks

A modern, robust sound-bite pipeline is these layers composed:

  audio
    │  Silero VAD            drop silence (Layer 2)
    ▼
  speech spans
    │  librosa / wav2vec2    features (Layer 1)
    ▼
  feature vectors
    │  KTS  (this book!)     content-aware boundaries (Layer 2)   ◀── you built this
    ▼  └ or ruptures / pyannote
  candidate segments
    │  faster-whisper        snap to sentences (Layer 3)
    │  sentence-transformers / Claude   rank by meaning (Layer 4)
    ▼
  ranked sound bites

You now know every box. The next chapter is the hands-on lab that builds the core of this stack, with no VAD and no transcript, in pure NumPy, so you can watch KTS turn a waveform into ranked bites end to end. 👉

Lab: extract sound bites with KTS

Time to build the thing. This lab takes a waveform and produces ranked sound bites, reusing kts.py without changes: the same kernel and dynamic program from the rest of the book. It runs in pure NumPy, with no audio files and no extra libraries, so every number below is real output you can reproduce.

Run it any time with:

cd books/kts/code
python3 soundbites.py

We will go phase by phase, then list the whole file.

Phase 1: make a clip with known answers

To prove the pipeline works we need ground truth. synthesize_audio builds a 25-second waveform from six labelled regions (silence, speech, silence, music, applause, speech), so we know exactly where the boundaries should be:

wave, sr, regions = synthesize_audio(sr=16000, seed=0)

clip: 25.0s @ 16000 Hz  (400000 samples)
ground-truth regions:
    silence   0:00.0 - 0:03.0
    speech    0:03.0 - 0:09.0
    silence   0:09.0 - 0:12.0
    music     0:12.0 - 0:18.0
    applause  0:18.0 - 0:21.0
    speech    0:21.0 - 0:25.0

Each region is synthesised to sound like its label: speech is voiced harmonics with a 4 Hz syllable envelope, music is a steady three-note chord, applause is broadband noise bursts, and silence is faint hiss. The details are in the file at the end.

Why fake audio? The same reason the video demo uses synthetic data: with known boundaries we can check KTS is correct, not just that it runs. Swap synthesize_audio for librosa.load("clip.wav") (Ch. 14) and the rest is identical.

Phase 2: turn the waveform into features

This is the front end from Chapter 12: frame the signal (50 ms window, 25 ms hop) and describe each frame with five features.

feats, hop_sec = frame_features(wave, sr, win_ms=50.0, hop_ms=25.0)

framed: 999 frames x 5 features (hop 25 ms)

That is 999 frames, each a 5-vector: our $x_1,\dots,x_n \in \mathbb{R}^5$.

Phase 3: segment with KTS (the reused engine)

Standardize the features, build a kernel, and let cpd_auto choose the cuts. This is the point of the lab: the next three lines are imported from kts.py, so the audio never touches new segmentation code.

from kts import build_kernel, cpd_auto          # <-- the book's core, unchanged
fz = zscore(feats)
K  = build_kernel(fz, kind="rbf")
cps, _ = cpd_auto(K, ncp_max=12, vmax=1.0, lmin=8)

KTS found 5 cut points at: 0:03.0, 0:09.0, 0:12.0, 0:18.0, 0:21.0

It nailed all five. Compare to Phase 1's ground truth (3.0, 9.0, 12.0, 18.0, 21.0): every boundary recovered exactly, and the count (5) was chosen automatically by the penalty, not handed to it. The same cpd_auto that found video shots just found audio scene changes.

Phase 4: score and rank the segments

Boundaries give six segments; now we rank them as sound bites with the simple, feature-only heuristic from Chapter 13: reward loud, voiced (low flatness), speech-band ZCR, and the right length.

segs   = cuts_to_segments(cps, feats.shape[0])
ranked = score_bites(feats, segs, hop_sec)

6 segments, ranked as sound-bite candidates:
  rank   start      end     dur   energy    zcr   flat   score
  ------------------------------------------------------------
     0   0:21.0   0:25.0    4.0   -2.21   0.18   0.13   0.81
     1   0:03.0   0:09.0    6.0   -2.21   0.17   0.13   0.81
     2   0:12.0   0:18.0    6.0   -1.41   0.04   0.00   0.80
     3   0:18.0   0:21.0    3.0   -2.45   0.50   0.56   0.41
     4   0:09.0   0:12.0    3.0   -6.21   0.51   0.56   0.10
     5   0:00.0   0:03.0    3.0   -6.21   0.50   0.56   0.10

top bite: 0:21.0 - 0:25.0 (4.0s, score 0.81)

Read the ranking against what we know is in the clip:

• Ranks 0 and 1 are the two speech segments: loud, voiced (flat ≈ 0.13), with speech-band ZCR. These are the bites a producer wants.
• Rank 2 is the music: just as loud, but it is a chord, not a quote, so the speech-ZCR term keeps it a hair below the speech bites.
• Rank 3 is applause: loud-ish but noisy (flat 0.56), correctly demoted.
• Ranks 4 and 5 are the silences: quietest (energy -6.21), correctly last.

The pipeline went from raw samples to "your best clip is 0:21 to 0:25" with no labels, no transcript, and no model: just features, KTS, and a scoring rule.

Phase 5: take it to real audio

To run this on an actual recording, change only Phase 1:

import librosa                                   # see Chapter 14
wave, sr = librosa.load("interview.wav", sr=16000)
feats, hop_sec = frame_features(wave, sr)        # Phase 2 unchanged
# ... Phases 3 and 4 unchanged ...

For longer or higher-quality results, swap layers in from Chapter 14 without touching the KTS core:

• Trim silence first with Silero VAD, so fewer frames keep the $O(n^2)$ cost down.
• Richer features: replace frame_features with librosa MFCCs or wav2vec2 embeddings. build_kernel accepts any (n, d) array.
• Smarter ranking: feed the candidate timestamps plus a Whisper transcript to claude-opus-4-8 to pick the most quotable bites (Ch. 14, Layer 4).
• Tune the cut count: raise vmax for fewer, longer bites, lower it for more, or pin an exact number with cpd_nonlin (Ch. 5).

The complete script

"""
Sound bites with KTS — from scratch in NumPy.

A "sound bite" is a short, self-contained, salient excerpt of audio (a quotable
sentence, a chorus, a punch line). Finding them is the *audio* sibling of video
shot detection: instead of cutting where the *picture* changes, we cut where the
*sound* changes, then keep the segments that are most "bite-worthy".

The cut-finding is exactly KTS — the same kernel + dynamic-programming machinery
from this book — so this module imports the core straight from ``kts.py``:

    build_kernel, calc_scatters, cpd_auto

Pipeline (see the "Lab: extract sound bites with KTS" chapter):

    waveform  ->  frame features  ->  kernel  ->  KTS cut points
              ->  score each segment  ->  rank the top bites

Everything is pure NumPy and CPU-only. ``synthesize_audio`` fakes a clip with
known regions (silence / speech / music / applause) so the whole pipeline runs
and verifies with no audio files and no extra libraries.
"""

from __future__ import annotations

import numpy as np

from kts import build_kernel, calc_scatters, cpd_auto


# --------------------------------------------------------------------------- #
# 0 — a synthetic clip with known regions (stand-in for a real .wav)
# --------------------------------------------------------------------------- #
def synthesize_audio(sr=16000, seed=0):
    """
    Build a 25-second mono waveform made of labelled regions:

        0- 3s  silence       (near-zero, faint hiss)
        3- 9s  speech-like    (voiced harmonics, syllable-rate modulation)
        9-12s  silence
       12-18s  music-like     (steady tonal chord)
       18-21s  applause-like  (broadband noise bursts)
       21-25s  speech-like

    Returns (wave, sr, regions) where regions is a list of
    (label, start_sec, end_sec).
    """
    rng = np.random.default_rng(seed)

    def t(seconds):
        return np.arange(int(seconds * sr)) / sr

    def silence(sec):
        return 0.002 * rng.standard_normal(int(sec * sr))

    def speech(sec, f0=120.0):
        x = t(sec)
        # a few harmonics = "voiced"; 4 Hz envelope = syllable rate
        tone = sum((1.0 / k) * np.sin(2 * np.pi * f0 * k * x) for k in (1, 2, 3, 4))
        env = 0.5 * (1 + np.sin(2 * np.pi * 4.0 * x)) ** 2
        return 0.3 * env * tone + 0.01 * rng.standard_normal(x.size)

    def music(sec):
        x = t(sec)
        chord = (np.sin(2 * np.pi * 220.0 * x)
                 + np.sin(2 * np.pi * 277.18 * x)
                 + np.sin(2 * np.pi * 329.63 * x))
        return 0.2 * chord + 0.005 * rng.standard_normal(x.size)

    def applause(sec):
        x = silence(sec) * 0 + 0.25 * rng.standard_normal(int(sec * sr))
        # crackle: random amplitude bursts
        burst = (rng.random(x.size) < 0.02).astype(float)
        return x * (0.3 + burst)

    plan = [
        ("silence", 3, silence(3)),
        ("speech", 6, speech(6, f0=120.0)),
        ("silence", 3, silence(3)),
        ("music", 6, music(6)),
        ("applause", 3, applause(3)),
        ("speech", 4, speech(4, f0=160.0)),
    ]

    wave = np.concatenate([seg for _, _, seg in plan])
    regions, cursor = [], 0.0
    for label, dur, _ in plan:
        regions.append((label, cursor, cursor + dur))
        cursor += dur
    return wave.astype(np.float64), sr, regions


# --------------------------------------------------------------------------- #
# 1 — frame the waveform and describe each frame with a few features
# --------------------------------------------------------------------------- #
def frame_signal(wave, sr, win_ms=50.0, hop_ms=25.0):
    """Slice the waveform into overlapping frames -> (n_frames, win) array."""
    win = int(sr * win_ms / 1000)
    hop = int(sr * hop_ms / 1000)
    if wave.size < win:
        return np.empty((0, win)), win, hop
    n = 1 + (wave.size - win) // hop
    idx = np.arange(win)[None, :] + hop * np.arange(n)[:, None]
    return wave[idx], win, hop


def frame_features(wave, sr, win_ms=50.0, hop_ms=25.0):
    """
    Turn audio into KTS-ready feature vectors: one row per frame.

    Five classic, model-free descriptors per frame:
        log_energy        loudness (log RMS)
        zcr               zero-crossing rate (noisiness / pitch proxy)
        centroid          spectral centroid in Hz (brightness)
        bandwidth         spectral spread in Hz
        flatness          spectral flatness (tonal ~0  vs  noisy ~1)

    Returns (features (n, 5), hop_sec).
    """
    frames, win, hop = frame_signal(wave, sr, win_ms, hop_ms)
    if frames.shape[0] == 0:
        return np.empty((0, 5)), hop / sr

    # window to reduce spectral leakage
    window = np.hanning(win)
    fw = frames * window

    # time-domain features
    rms = np.sqrt(np.mean(frames ** 2, axis=1) + 1e-12)
    log_energy = np.log(rms + 1e-8)
    signs = np.sign(frames)
    signs[signs == 0] = 1
    zcr = np.mean(np.abs(np.diff(signs, axis=1)) > 0, axis=1)

    # frequency-domain features
    spec = np.abs(np.fft.rfft(fw, axis=1)) + 1e-12
    power = spec ** 2
    freqs = np.fft.rfftfreq(win, d=1.0 / sr)
    psum = np.sum(power, axis=1, keepdims=True)
    centroid = np.sum(freqs[None, :] * power, axis=1) / psum[:, 0]
    bandwidth = np.sqrt(
        np.sum(((freqs[None, :] - centroid[:, None]) ** 2) * power, axis=1) / psum[:, 0]
    )
    geo = np.exp(np.mean(np.log(power), axis=1))
    arith = np.mean(power, axis=1)
    flatness = geo / arith

    feats = np.stack([log_energy, zcr, centroid, bandwidth, flatness], axis=1)
    return feats, hop / sr


def zscore(features):
    """Standardize each column to mean 0, std 1 (so no feature dominates)."""
    mu = features.mean(axis=0, keepdims=True)
    sd = features.std(axis=0, keepdims=True)
    return (features - mu) / np.maximum(sd, 1e-8)


# --------------------------------------------------------------------------- #
# 2 — segment with KTS, then score each segment for "bite-worthiness"
# --------------------------------------------------------------------------- #
def segment(features, kind="rbf", ncp_max=12, vmax=1.0, lmin=4):
    """Run KTS on the features. Returns cut points (start frame of each seg)."""
    K = build_kernel(features, kind=kind)
    cps, scores = cpd_auto(K, ncp_max=ncp_max, vmax=vmax, lmin=lmin)
    return cps, scores


def cuts_to_segments(cps, n):
    """Turn change points into [start, end) frame ranges covering 0..n."""
    bounds = [0, *list(cps), n]
    return [(bounds[i], bounds[i + 1]) for i in range(len(bounds) - 1)]


def score_bites(features, segments, hop_sec, want=(2.0, 12.0)):
    """
    Rank segments by how good a *speech* sound bite each one is.

    Heuristic score (all from the raw features):
        + loud        : high mean energy
        + voiced      : low spectral flatness (tonal, not hiss/applause)
        + speechy ZCR : mid-range zero-crossing rate
        + right length: duration inside the wanted window (seconds)

    Returns a list of dicts sorted best-first.
    """
    log_energy, zcr, _, _, flatness = features.T
    e_lo, e_hi = np.percentile(log_energy, [5, 95])

    out = []
    for (a, b) in segments:
        dur = (b - a) * hop_sec
        e = log_energy[a:b].mean()
        z = zcr[a:b].mean()
        fl = flatness[a:b].mean()

        loud = (e - e_lo) / max(e_hi - e_lo, 1e-8)        # 0..1-ish
        voiced = 1.0 - min(fl / 0.5, 1.0)                  # tonal -> ~1
        speechy = float(0.05 <= z <= 0.25)                 # speech ZCR band
        lo, hi = want
        fit = 1.0 if lo <= dur <= hi else max(0.0, 1 - abs(dur - np.clip(dur, lo, hi)) / hi)

        score = 0.45 * np.clip(loud, 0, 1) + 0.30 * voiced + 0.15 * speechy + 0.10 * fit
        out.append({
            "start_sec": a * hop_sec, "end_sec": b * hop_sec, "dur": dur,
            "energy": e, "zcr": z, "flatness": fl, "score": float(score),
        })
    return sorted(out, key=lambda d: d["score"], reverse=True)


# --------------------------------------------------------------------------- #
# 3 — end-to-end demo / report
# --------------------------------------------------------------------------- #
def fmt_ts(sec):
    m, s = divmod(sec, 60)
    return f"{int(m):d}:{s:04.1f}"


def main():
    wave, sr, regions = synthesize_audio(sr=16000, seed=0)
    print(f"clip: {wave.size/sr:.1f}s @ {sr} Hz  ({wave.size} samples)")
    print("ground-truth regions:")
    for label, s, e in regions:
        print(f"    {label:9s} {fmt_ts(s)} - {fmt_ts(e)}")

    feats, hop_sec = frame_features(wave, sr, win_ms=50.0, hop_ms=25.0)
    print(f"\nframed: {feats.shape[0]} frames x {feats.shape[1]} features "
          f"(hop {hop_sec*1000:.0f} ms)")

    fz = zscore(feats)
    cps, _ = segment(fz, kind="rbf", ncp_max=12, vmax=1.0, lmin=8)
    cut_times = [c * hop_sec for c in cps]
    print(f"KTS found {len(cps)} cut points at: "
          + ", ".join(fmt_ts(t) for t in cut_times))

    segs = cuts_to_segments(cps, feats.shape[0])
    ranked = score_bites(feats, segs, hop_sec)

    print(f"\n{len(segs)} segments, ranked as sound-bite candidates:")
    print("  rank   start      end     dur   energy    zcr   flat   score")
    print("  " + "-" * 60)
    for r, b in enumerate(ranked):
        print(f"  {r:>4d}  {fmt_ts(b['start_sec']):>7s}  {fmt_ts(b['end_sec']):>7s}"
              f"  {b['dur']:5.1f}  {b['energy']:6.2f}  {b['zcr']:5.2f}"
              f"  {b['flatness']:5.2f}  {b['score']:5.2f}")

    best = ranked[0]
    print(f"\ntop bite: {fmt_ts(best['start_sec'])} - {fmt_ts(best['end_sec'])} "
          f"({best['dur']:.1f}s, score {best['score']:.2f})")


if __name__ == "__main__":
    main()

That is the entire sound-bite tool: synthesize, features, KTS, score, in one file that imports the book's core and runs top to bottom. You have now used the same Kernel Temporal Segmentation engine to cut both pictures and sound. 👉

References

1. Danila Potapov, Matthijs Douze, Zaid Harchaoui, Cordelia Schmid. Category-Specific Video Summarization. ECCV 2014. The paper that introduced KTS.

2. Zaid Harchaoui, Olivier Cappé. Retrospective Multiple Change-Point Estimation with Kernels. IEEE/SP SSP 2007. The kernel change-point framework KTS builds on.

3. Ke Zhang, Wei-Lun Chao, Fei Sha, Kristen Grauman. Video Summarization with Long Short-Term Memory. ECCV 2016. Popularized KTS as preprocessing for the TVSum / SumMe benchmarks.

Related ideas

• Dynamic programming for change-point detection: the same optimal-substructure recurrence appears in PELT, segmented regression, and ruptures-style libraries.
• The kernel trick: writing variance/distance purely through a Gram matrix is the same move behind kernel PCA and kernel k-means.

Sound bites & audio segmentation (Chapters 11 to 15)

• Charles Truong, Laurent Oudre, Nicolas Vayatis. Selective review of offline change point detection methods. Signal Processing, 2020. Survey behind the ruptures library; PELT and kernel change-point cost functions.
• Hervé Bredin et al. pyannote.audio: neural building blocks for speaker diarization. ICASSP 2020. The open-source diarization toolkit.
• Alec Radford et al. Robust Speech Recognition via Large-Scale Weak Supervision (Whisper). 2022. Timestamped transcription for sentence-level cuts.
• Alexei Baevski et al. wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations. NeurIPS 2020. Learned audio embeddings as KTS features.
• librosa: https://librosa.org, standard audio feature extraction (MFCCs, spectral features) referenced in Chapter 14.

This book's code

• code/kts.py, the full implementation.
• code/demo.py, the synthetic-data demo.
• code/kts_video.py, one-file CLI tool for real videos.
• code/soundbites.py, sound-bite extraction lab; imports the KTS core and applies it to audio.

All depend only on NumPy (Matplotlib optional, for the demo plot).