Softmax Transition Probabilities

mediumPROVideo TexturesVideoCV: Image-Based Rendering

Convert frame similarities to transition probabilities using softmax.

For varied video texture playback, we use probabilistic transitions instead of always jumping to the best match. The transition probability from frame $i$ to frame $j$ is:

$P(j|i) = \frac{\exp(-D_{ij}/\sigma)}{\sum_k \exp(-D_{ik}/\sigma)}$

where:

$D_{ij}$ is the dissimilarity from $i$ to $j$
$\sigma$ is a temperature parameter
Lower dissimilarity = higher probability

This creates smooth random playback that prefers good transitions but allows variety.

Return the probabilities as a list in the same order as the input, with each probability rounded to 4 decimal places.

Example

Input

transition_probs([0, 10, 10], 10)

Output

[0.5761, 0.2119, 0.2119]

Reasoning

Inputs: similarities = [0, 10, 10] holds the dissimilarity $D_{ij}$ from the current frame to each of 3 candidate frames (0 means a perfect match), and sigma = 10 is the temperature.
Scale and negate: each score becomes $-D_{ij}/\sigma$ , giving $0, -1, -1$ . The negative sign is what makes a small dissimilarity produce a large weight.
Weights: $e^{0} = 1$ and $e^{-1} \approx 0.3679$ (twice), so the denominator is $1 + 2 \times 0.3679 \approx 1.7358$ .
Normalise: $P = 1 / 1.7358 \approx 0.5761$ for the matching frame and $0.3679 / 1.7358 \approx 0.2119$ for each of the other two, each rounded to 4 decimal places: [0.5761, 0.2119, 0.2119].
Notice: the two frames with equal dissimilarity get equal probability, and the rounded values add to $0.9999$ , not exactly 1. A larger $\sigma$ would shrink the gaps and push all three toward $1/3$ .

Constraints

similarities: list of similarity scores from current frame to all frames
sigma: temperature parameter (higher = more uniform)
Return probability distribution (sums to 1)

Learn this in

Image-Based RenderingCV Study Plan Mathematical FoundationsDiffusion Study Plan

More from CV: Image-Based Rendering

Differentiable Renderer Forwardhard Video Loop Findinghard Light Field Refocusinghard Depth-Based View Synthesishard Front-to-Back Splat Accumulationmedium

Concept primerPREVIEW

Background Knowledge

Video Textures and Frame Transitions

Video textures are short video clips that can be seamlessly looped or extended by intelligently stitching frames together. Rather than simply repeating a video or always jumping to the most similar frame, the key insight is to use probabilistic transitions—randomly selecting the next frame with probabilities weighted by how well it matches the current frame. This creates natural-looking, varied playback that avoids repetitive patterns while maintaining temporal coherence.

Softmax and Temperature Scaling

The softmax function converts raw similarity scores into a valid probability distribution. In this context, the dissimilarity scores $D_{ij}$ are first converted to similarities using the exponential function, then normalized so all probabilities sum to 1. The temperature parameter $\sigma$ controls how "sharp" or "smooth" the probability distribution is: a small $\sigma$ makes the distribution peaky (favoring the best matches strongly), while a large $\sigma$ flattens it (allowing more exploration of suboptimal transitions). This is crucial for balancing quality (preferring good transitions) with variety (allowing occasional less-optimal jumps).

Numerical Stability Considerations

When implementing softmax with exponentials, you'll encounter numerical challenges. Computing $\exp(-D_{ij}/$ \sigma $)$ directly can cause overflow (when values are very negative) or underflow (when values are very positive). The standard solution is the log-sum-exp trick: subtract the maximum dissimilarity value before computing exponentials, which doesn't change the final probabilities but keeps intermediate values in a safe numerical range.

Algorithm/Approach

The general pattern is:

Normalize dissimilarities by subtracting the minimum (or maximum) value for numerical stability
Apply exponential transformation with temperature scaling: $\exp(-D_{ij}/$ \sigma $)$
Compute the partition function (denominator): sum all exponential values
Normalize by dividing each exponential by the partition function to get probabilities

This transforms a raw distance metric into a proper probability distribution suitable for random sampling.

Step-by-Step Strategy

Step 1: Understand Your Input

You'll have a dissimilarity matrix $D$ where $D[i][j]$ represents how different frame $i$ is from frame $j$
You'll have a temperature parameter $\sigma$ (typically a small positive value like 0.1 or 1.0)

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results