Graph-Based Seam Optimization for Image Composition

24 concepts21 papers1 proposal

When combining multiple images—whether stitching a drone panorama, synthesizing a texture, or inserting a generated face into a video—we face a fundamental problem: how do we transition from one image to another?

Traditional approaches like linear or alpha blending average the pixel values in the overlapping region. While this sounds intuitive, it often results in "ghosting" or blurring because the underlying geometries rarely align perfectly. Alternatively, a straight cut creates a harsh, highly visible boundary.

The solution is energy-based seam optimization. Instead of forcing a rigid or blurry transition, we find a non-linear path (a seam) through the overlapping region where the source images are visually identical or highly similar. By switching from one image to the other exactly along this path, the transition becomes completely imperceptible.

Framing Seams as Graph Problems

To find this optimal path automatically, we can map the overlapping image region to a graph. Once formulated as a graph, finding the best visual boundary becomes an exact optimization problem.

Shortest Path and Dynamic Programming

For sequential or one-dimensional transitions—such as stitching adjacent vertical strips of an image mosaic—the problem can be solved using dynamic programming or shortest-path algorithms like Dijkstra's.

Wexler et al. et al. (Space-Time Scene Manifolds) demonstrated this by treating an image mosaic as a shortest-path search across thin vertical image strips, where edge costs represent visual compatibility. Similarly, Li et al. et al. (A STUDY ON AUTOMATIC UAV IMAGE MOSAIC METHOD FOR PAROXYSMAL DISASTER) and Huang et al. et al. (Optimal Region Gradated Fusion Based Automatic Image Stitching for Industrial Systems) utilized dynamic programming to let the seam line "snake" around complex structures in UAV and industrial panoramas, avoiding geometric discontinuities by selecting pixels with the highest color similarity.

Graph Cuts

When the overlap is more complex or involves arbitrary 2D patches, the problem is framed as a Graph Cut (min-cut/max-flow optimization). Here, pixels are nodes, and edges represent the cost of cutting between adjacent pixels.

Brostow et al. et al. (Semantic Photo Synthesis) used graph cuts to seamlessly stitch semantic photo patches based on user sketches or keywords. In texture synthesis, Hays et al. et al. (Quantitative Evaluation of Near Regular Texture Synthesis Algorithms) showed that explicitly optimizing seams over geometric lattices is crucial for synthesizing near-regular textures like brick walls. Paul et al. et al. (Optimized tile-based texture synthesis) also leveraged graph cuts to eliminate visible seams when merging optimized texture tiles.

Designing the Energy Function

The magic of seam optimization lies in how we define the "cost" or "energy" of a path. A low-energy path means a visually unnoticeable seam. By changing the energy function, we can force the seam to respect different types of visual constraints:

Expanding to Higher Dimensions

The power of graph-based seam optimization extends beyond flat 2D images into 3D volumes and temporal sequences.

In video editing, Kang et al. et al. (Space-Time Video Montage) treated video as a 3D space-time volume. To pack multiple video events into a single dense summary, they used graph-cut optimization to find optimal seams between overlapping volumetric layers, balancing color continuity with temporal smoothness.

┌─────────────────────────────────────────┐
│          Space-Time Volume              │
│  ┌───────────────────┐                  │
│  │  Video Blob A     │   Graph-Cut     │ ───> Seamless Video Montage
│  └─────────┬─────────┘   Seam Finding   │      (No temporal ghosting)
│            │ <-- Optimal Seam           │
│  ┌─────────┴─────────┐                  │
│  │  Video Blob B     │                  │
│  └───────────────────┘                  │
└─────────────────────────────────────────┘

For 3D urban modeling, Garcia-Dorado et al. et al. (Automatic urban modeling using volumetric reconstruction with surface graph cuts) applied graph cuts to a 3D surface graph. This allowed them to stitch multi-camera image fragments onto building proxies, automatically selecting the best camera view for each surface patch while minimizing visual transitions caused by occlusions or geometric inaccuracies.

The Modern Frontier: Integrating Deep Learning

While classical seam optimization relies entirely on hand-crafted pixel differences, modern approaches combine graph optimization with deep neural networks to solve complex reassembly and generative tasks.

Global Reassembly

When reassembling fragmented images or solving visual jigsaw puzzles, Picard et al. et al. (Image Reassembly Combining Deep Learning and Shortest Path Problem) and Paumard et al. et al. (Deepzzle: Solving Visual Jigsaw Puzzles With Deep Learning and Shortest Path Optimization) used convolutional neural networks to predict the relative positions of fragments. They then mapped these predictions to a directed graph, using shortest-path optimization to find the global configuration that maximizes the joint probability of the assembly.

Similarly, Cui et al. et al. (Dense Registration and Mosaicking of Fingerprints by Training an End-to-End Network) combined a deep Siamese network for dense fingerprint registration with a graph-search algorithm to find optimal seams that preserve linear ridge features across overlapping prints.

Blending Generative Models

Seam optimization also plays a vital role in blending generative models with real footage. Yamasaki et al. et al. (Real-Time Face Model Reconstruction and Synthesis Using an RGB-D Camera for Face Reorientation) used energy-based seam optimization to blend a synthesized 2.5D face model back into a live video frame, outperforming traditional alpha blending by maintaining sharpness along the boundary.

Likewise, the authors of Realistic Dynamic Facial Textures from a Single Image Using GANs combined graph-cut optimization with color blending to integrate GAN-generated facial regions into target videos, making the transition between synthesized content and the original background completely imperceptible.

Key Foundational Work

Semantic Photo Synthesis (2006) — contributed 2 concept elements to this direction.
Quantitative Evaluation of Near Regular Texture Synthesis Algorithms (2006) — contributed 1 concept elements to this direction.
Space-Time Scene Manifolds (2005) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 20 papers
  2. Version 1 · 2026-10-04 · 29 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_energy_based_seam_optimization_a550998b,
  title = {energy-based seam optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/energy-based-seam-optimization/rdr_a550998b9ff34f89afcbaa08b597ac88},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_energy_based_seam_optimization_a550998b_v2,
  title = {energy-based seam optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/energy-based-seam-optimization/rdr_a550998b9ff34f89afcbaa08b597ac88/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake