Seam Carving — CUDA Parallel Optimisation

Technology Stack

C/C++, CUDA, GPU Parallel Programming, Profiling & Optimisation

Overview

Duration: 11/2022

Seam carving resizes an image by removing the least important paths through it rather than scaling uniformly, so faces, buildings, and text keep their proportions while empty sky and flat background absorb the change. It is the correct way to fit one image to many screen sizes without distortion.

It is also expensive. Nearly every stage is O(n²), and the naive implementation scales linearly with the number of seams removed — which makes it a genuinely good candidate for GPU parallelisation and a good subject for measuring what parallelisation actually buys you.

Input: an RGB image [W, H, 3] and a seam count N Output: an image [W-N, H, 3] with N low-energy seams removed and no distortion to important content

The Algorithm

• Energy computation per pixel — convert to greyscale, apply a Gaussian blur, run a Sobel filter to detect edges, then build an energy map from the horizontal and vertical gradients
• Seam identification — find the minimum-energy path from top to bottom using dynamic programming
• Seam removal — delete the identified path and repeat

The seam search is where the algorithmic work is. Let F[i][j] be the minimum cumulative energy of a seam ending at pixel (i, j):

F[i][j] = min(F[i+1][j-1], F[i+1][j], F[i+1][j+1]) + e[i][j]

A parallel trace matrix stores argmin at each step, so the optimal path can be reconstructed by backtracking once the table is complete.

Baseline Measurement

The sequential implementation was profiled first, because optimising without a baseline is guessing. The result was close to a straight line: doubling the seam count doubled the runtime, confirming that the cost is dominated by the per-pixel stages rather than by any single bottleneck.

Every major stage — greyscale conversion, the three convolutions, the DP table, and the removal pass — is O(n²) and operates on pixels largely independently. That is exactly the profile that justifies moving to the GPU.

Version 1 — Naive Parallelisation

Greyscale conversion, the convolution kernels, and the pixel-removal pass moved to the device; the dynamic programming and backtracking stayed on the host.

Result: a clear win at low seam counts, and no better than baseline at high ones. The cause was measurable rather than theoretical — host-to-device and device-to-host transfer per seam dominated once the seam count grew. Parallelising the work is not enough if the data crosses the bus on every iteration.

Version 2 — Shared Memory Convolution

The convolution stages were rewritten to stage their tile into shared memory before computing.

Shared memory sits on the streaming multiprocessor, with far lower access latency than global device memory. Because convolution reads each pixel repeatedly across neighbouring windows, loading the block once and having every thread read from shared memory removes the redundant global reads — the standard win for stencil operations, and it delivered.

Version 3 — Parallel Dynamic Programming

The remaining host-side bottleneck was the DP table. Version 3 parallelises it per row — every cell in a row is computed concurrently, with rows processed in sequence, since row i depends on row i+1.

Result: a significant improvement over both previous versions, and the largest single gain of the three. Notably, the algorithm's structure was not changed to achieve it — the same recurrence, mapped correctly onto the hardware.

Further Optimisation

• Bidirectional search — computing the DP table from both ends and combining at the midpoint, roughly halving the dependent-sequential depth
• Forward energy — the current backward-energy formulation can remove a seam that looks cheap but leaves a visible artefact where the newly adjacent pixels do not match. Forward energy scores a seam by the cost it creates after removal rather than the energy it currently occupies, which resolves that class of artefact and removes the need to recompute the energy map from scratch each iteration
• Batched removal — removing multiple seams per pass, since in practice the goal is maximising throughput rather than minimising single-run latency

This project is systems and performance work rather than application development: profile first, parallelise what the profile justifies, measure that the memory hierarchy is being used correctly, and know the difference between a change that looks faster and one that is.