Skip to main content

Visual Complexity Analysis: Smart Image Processing

Learn visual complexity analysis in deep learning - how neural networks measure entropy, edges, and saliency for adaptive image processing.

A vision transformer usually starts with a regular patch grid. If a limited budget lets it process only some patches, which ones should remain? Edge strength, frequency content and intensity entropy can suggest where the image varies. They cannot establish which regions matter to a task: a textured background may score highly while a small, low-contrast object scores poorly.

Following adaptive tiling, the next question is whether a fixed patch grid can spend a limited token budget on selected regions. This page builds a heuristic patch selector, not a trained token-pruning method. The explorer uses authored scores to make allocation decisions visible. The Python example computes related metrics from pixels. Neither runs a vision transformer or measures recognition accuracy or latency.

From complexity scores to a token budget

Choose a scene and compare the three allocation strategies at the same budget. Change the weights to inspect their effect on the score map, then lower the temperature to concentrate complexity-aware sampling. Each outlined cell represents one distinct kept patch. Use the patch inspector to read the underlying values without relying on color.

Spend a fixed patch budget

Which distinct patches survive when the budget shrinks? Compare the scene, its authored scores and the exact selection.

Scene
Allocation method

Sample distinct patches using softmax(score / T). Lower T concentrates the first-draw probabilities; the seed keeps comparisons repeatable.

0.40
0.30
0.30
0.40
96 / 196
Distinct patches kept
96 / 196
Tokens removed
51.0%
Attention pairs (k²)
9,216 / 38,416
Pair-count reduction
76.0%
Selected score mass
61.4%
Score map
Authored scene
Combined score and kept patches
Low scoreHigh scoreOutline: patch keptCenter dot: inspected
Row 1, column 1
Selection
Dropped
Edge score
0.10
Frequency score
0.00
Entropy score
0.12
Combined score
0.075
First-draw probability
0.3%
Authored 14 × 14 scene and score maps, not metrics computed from photographs or a ViT prediction. Score coverage measures this heuristic only. Attention pairs exclude special tokens, projections, MLPs and selection overhead; no accuracy or latency is measured.

The four scenes and their edge, frequency and entropy values are authored illustrations. Switching the displayed metric does not change the selected patches; it changes which score you inspect. Reset restores the scene, method, weights, budget and inspector together. A fixed random seed makes comparisons repeatable rather than changing the sample after every render.

The computer-vision lesson uses the same explorer and executable example. Both routes share those mechanics; this deep-learning route connects the heuristic to sequence length and attention cost.

How it works

The selector has four separate decisions: define the patch grid, score each patch, choose a fixed number of distinct patches, and pass their positions to the downstream model.

1. Distinguish patch size from grid size

With nonoverlapping 16 × 16 pixel patches, a 224 × 224 image produces a 14 × 14 grid: 196 patches. Using 14 × 14 pixel patches would instead produce a 16 × 16 grid: 256 patches. The example uses kernel_size=16 and stride=16 when unfolding the image. See PyTorch Unfold.

2. Score variation, not semantic importance

The three metrics answer different questions. Their scales must be defined before their weights can be meaningfully combined.

SignalWhat the example measuresWhat it can miss
Edge strengthMean Sobel gradient magnitude, scaled to a bound for intensities in [0, 1]Smooth objects and weak boundaries
Frequency fractionFraction of mean-centered FFT power above a chosen spatial frequencyWhether texture is useful or distracting
Histogram entropySpread of grayscale intensities across 32 bins, divided by its maximumSpatial arrangement and task relevance

The Sobel operator estimates intensity derivatives. Edge magnitude is not the same statistic as the fraction of pixels exceeding an edge threshold.

For frequency, the example removes the patch mean, then compares high-frequency power with total remaining power. A flat patch scores zero. The cutoff, 0.25 cycles per pixel by radial frequency, is an explicit teaching choice. The FFT frequency convention defines the frequency grid; this is a power fraction, not a semantic detail detector.

Histogram entropy ignores where pixels occur. Rearranging the same intensities leaves it unchanged. Noise can therefore have high entropy without contributing useful evidence for recognition.

3. Spend the budget once

The complexity-aware strategy samples without replacement from weighted probabilities. Once a patch is chosen, it cannot consume another slot. Uniform selection uses evenly spaced row-major indices; random selection samples distinct patches with equal probability. All three keep exactly kk patches.

The browser samples sequentially using a seeded random stream. The Python example uses torch.multinomial with replacement disabled. Their random-number implementations differ, so a seed is reproducible within each example rather than a promise of identical browser and Python selections.

4. Preserve position and model contracts

The selected indices identify each patch's original grid location. A downstream model must use the corresponding position embeddings, retain required special tokens and support the resulting sequence shape. Selecting image patches alone is not a drop-in modification for every pretrained ViT.

Token selection discards patches; token merging combines representations. This example performs selection only. It does not implement learned pruning, feature similarity matching or a guarantee that every region remains covered.

Mathematical Foundation

Let ei,fi,hie_i, f_i, h_i be the normalized edge, frequency and histogram-entropy scores for patch ii. With nonnegative weights:

ci=αei+βfi+γhiα+β+γ.c_i = \frac{\alpha e_i + \beta f_i + \gamma h_i}{\alpha + \beta + \gamma}.

If all weights are zero, this example sets every score to zero and uses equal sampling probabilities. Otherwise, the weights express a preference among the three signals; they do not calibrate task importance.

For complexity-aware selection, the first draw uses:

pi=exp⁡(ci/T)∑jexp⁡(cj/T),T>0.p_i = \frac{\exp(c_i / T)}{\sum_j \exp(c_j / T)}, \qquad T > 0.

Lower temperature sharpens this distribution. Each subsequent draw renormalizes over the remaining patches. Thus kpik p_i is not generally a patch's final inclusion probability when sampling without replacement, and clipping fractional allocations at one can silently waste the budget.

The explorer's selected score mass is:

R=∑i∈Sci∑ici,R = \frac{\sum_{i\in S} c_i}{\sum_i c_i},

where SS is the selected set. It is undefined when all scores are zero. This statistic rewards retaining the same scores that guide selection. It is a diagnostic of the heuristic, not retained information, predictive accuracy, or an independent evaluation of usefulness.

Implementation in PyTorch

The implementation processes every image in a batch, accepts finite float inputs in [0, 1], and returns distinct patch indices in row-major order. It computes metrics on grayscale patches with reflected borders for Sobel filtering. Using each patch independently is a simplification: cross-patch context and alternative border treatments can change the scores.

visual_complexity.py
import math

import torch
import torch.nn.functional as F


def select_patches(images, budget=96, patch_size=16, weights=(0.4, 0.3, 0.3),
                   temperature=0.4, generator=None):
    """Scores grayscale patches and samples without replacement per image.

    Args:
        images: Float tensor [batch, channels, height, width], values in [0, 1].
        budget: Number of distinct patches to retain per image.
        patch_size: Square patch side in pixels; must divide height and width.
        weights: Nonnegative weights for normalized edge, frequency and entropy.
        temperature: Positive softmax temperature; lower is more concentrated.
        generator: Optional torch.Generator on the same device as images.

    Returns:
        Selected patches [batch, budget, channels, patch_size, patch_size],
        row-major patch indices [batch, budget], and normalized scores [batch, n].

    Raises:
        ValueError: If the shape, input range or allocation parameters are invalid.
    """
    if images.ndim != 4 or not images.is_floating_point():
        raise ValueError("images must be a floating-point BCHW tensor")
    batch, channels, height, width = images.shape
    if min(images.shape) < 1 or not isinstance(patch_size, int) or patch_size < 2:
        raise ValueError("nonempty images and patch_size >= 2 are required")
    if height % patch_size or width % patch_size:
        raise ValueError("image dimensions must be divisible by patch_size")
    if not torch.isfinite(images).all() or images.min() < 0 or images.max() > 1:
        raise ValueError("images must contain finite values in [0, 1]")
    count = (height // patch_size) * (width // patch_size)
    if not isinstance(budget, int) or not 1 <= budget <= count:
        raise ValueError("budget must be between 1 and the patch count")
    if not math.isfinite(temperature) or temperature <= 0:
        raise ValueError("temperature must be positive")
    if len(weights) != 3 or any(not math.isfinite(w) or w < 0 for w in weights):
        raise ValueError("three finite nonnegative weights are required")

    # Float32 keeps FFT and convolution supported on CPU for half inputs.
    patches = F.unfold(images.float(), patch_size, stride=patch_size)
    patches = patches.transpose(1, 2).reshape(
        batch, count, channels, patch_size, patch_size)
    gray = patches.mean(dim=2).reshape(-1, 1, patch_size, patch_size)
    kernel_x = images.new_tensor(
        [[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]], dtype=torch.float32)
    kernels = torch.stack((kernel_x, kernel_x.T)).unsqueeze(1)
    gradients = F.conv2d(F.pad(gray, (1, 1, 1, 1), mode="reflect"), kernels)
    edge = gradients.square().sum(dim=1).sqrt().mean(dim=(-2, -1))
    edge = edge / (4 * math.sqrt(2))

    # Remove the mean. Measure the fraction of AC power above 0.25 cycles/pixel.
    centered = gray[:, 0] - gray[:, 0].mean(dim=(-2, -1), keepdim=True)
    power = torch.fft.fft2(centered).abs().square()
    frequencies = torch.fft.fftfreq(patch_size, device=images.device)
    fy, fx = torch.meshgrid(frequencies, frequencies, indexing="ij")
    high = fx.square() + fy.square() > 0.25 ** 2
    total_power = power.sum(dim=(-2, -1))
    frequency = power[:, high].sum(dim=-1) / total_power.clamp_min(1e-12)

    # Intensity histogram entropy: ignores spatial arrangement within a patch.
    bins = 32
    values = (gray.flatten(1) * bins).long().clamp(max=bins - 1)
    histogram = torch.zeros((batch * count, bins), device=images.device)
    histogram.scatter_add_(1, values, torch.ones_like(values, dtype=torch.float32))
    probabilities = histogram / (patch_size * patch_size)
    entropy = -(probabilities * probabilities.clamp_min(1e-12).log2()).sum(dim=1)
    entropy = entropy / math.log2(bins)

    metrics = torch.stack((edge, frequency, entropy), dim=-1)
    coefficients = metrics.new_tensor(weights)
    coefficients = coefficients / coefficients.sum().clamp_min(1e-12)
    scores = (metrics * coefficients).sum(dim=-1).reshape(batch, count)
    probabilities = torch.softmax((scores - scores.max(dim=1, keepdim=True).values)
                                  / temperature, dim=1)
    # Keep every index eligible under extreme temperatures despite underflow.
    probabilities = probabilities.clamp_min(torch.finfo(probabilities.dtype).tiny)
    indices = torch.multinomial(probabilities, budget, replacement=False,
                                generator=generator).sort(dim=1).values
    gather = indices[:, :, None, None, None].expand(
        -1, -1, channels, patch_size, patch_size)
    return patches.gather(1, gather), indices, scores


if __name__ == "__main__":
    torch.manual_seed(7)
    # Synthetic inputs for an executable shape check, not an accuracy benchmark.
    images = torch.rand(2, 3, 224, 224)
    selected, positions, scores = select_patches(images)
    assert selected.shape == (2, 96, 3, 16, 16)
    assert all(row.unique().numel() == 96 for row in positions)
    print(f"Selected {selected.shape[1]} distinct patches from {scores.shape[1]}")
    print(f"Returned positions for all {images.shape[0]} images")

Download the complete example and its Python requirements. Run python visual_complexity.py in an environment with PyTorch installed. The two synthetic inputs exercise batch shapes and unique selection; they are not benchmark images. Metric computation is included in this script but must also be counted when measuring an end-to-end implementation.

Performance Metrics

Reducing 196 patch tokens to 96 removes about 51.0% of patch tokens. A dense attention matrix over patch tokens alone has n2n^2 entries, so its pair count falls by about 76.0%. This is an analytical count, not a FLOP total or a measured speedup.

QuantityFull gridSelected patchesInterpretation
Patch tokens19696Exactly 100 removed
Patch-to-patch attention pairs38,4169,21676.0% fewer pairs
Pairs with one retained CLS token38,8099,409Uses 197² versus 97²
Model accuracyNot measuredNot measuredRequires a trained model and evaluation set
End-to-end latencyNot measuredNot measuredRequires timing the complete workload

Projection and MLP work also matter; so do preprocessing, gathering, padding and kernel efficiency. Dropping tokens late in a model does not save work already performed in earlier layers. Measure the model, dataset, hardware, precision, batch size and timing boundary before making speed or quality claims.

Use cases and failure modes

A selector is useful only if the saved work outweighs its overhead and the retained evidence is sufficient for the intended task.

Candidate useFailure to check
Documents with large marginsSmall or faint text receives low scores
Scenes with broad smooth backgroundsA small object appears in the smooth area
Images with repeated textureBackground texture outranks the object
Video with slowly changing contentCached scores become stale when something enters the frame

Use the explorer's Nature scene to see how a high frequency weight favors texture. That demonstrates the rule's preference, not that texture should receive the model's attention. Compare downstream quality at matched budgets, including an equal-probability baseline and a full-token model. Region coverage constraints are an additional design choice, not a property of this selector.

Key takeaways

  • Patch size determines grid size: 224 pixels divided by 16 gives 14 patches per side.
  • Normalized edge, frequency and entropy scores are heuristics for visual variation.
  • Distinct selection spends exactly one budget slot per kept patch and preserves original positions.
  • Score coverage and attention-pair counts do not establish model accuracy or measured speed.
  • Learned pruning and token merging require their own model integration and evaluation.

Further Reading

These methods use model representations or learned policies; their results do not validate the handcrafted selector on this page.

  • Token Merging: Your ViT but Faster combines similar token representations using a matching procedure.
  • DynamicViT learns token-importance predictors and progressively prunes tokens within the backbone.
  • AdaViT learns per-input decisions about patches, attention heads and transformer blocks.

If you found this explanation helpful, consider sharing it with others.

Mastodon