A One-step Image Retargeing Algorithm Based on Conformal Energy

Chengyang Liu, Michael K. NgarXiv 2024 · DOI · arXiv

Abstract

Image retargeting aims to resize images to various aspect ratios while preserving important content and maintaining topological integrity. Traditional warping methods often suffer from self-intersections or "folds" that create visual artifacts. This paper presents a novel image retargeting algorithm based on conformal energy minimization. By formulating the problem on a simplicial mesh and employing a unique bijection correction step, the method guarantees a one-to-one mapping. Experimental results on the RetargetMe dataset demonstrate that the proposed approach eliminates flipped triangles and significantly reduces geometric distortion compared to existing state-of-the-art methods.

Introduction

Image retargeting is the process of resizing an image to fit different aspect ratios—such as adapting a widescreen image for a vertical mobile display—without the loss of context associated with cropping or the distortion of simple stretching.

The most effective approaches utilize warping, treating the image as a flexible sheet where "important" regions (e.g., faces, foreground objects) are preserved while "unimportant" regions (e.g., sky, water) absorb the majority of the deformation. However, a persistent challenge in warping is maintaining bijectivity. Without a mathematical guarantee of a one-to-one mapping, the image can "fold" over itself, leading to overlapping pixels and jarring visual artifacts. This research introduces a framework that ensures a bijective, orientation-preserving map through conformal energy optimization.

Methodology

Mathematical Modeling and Discretization

The algorithm begins by defining specific regions within the image that require different levels of preservation. These include Regions of Interest (ROIs), such as objects, and critical line structures. The image is then discretized into a simplicial mesh consisting of a grid of triangles. This allows the continuous warping problem to be solved as a discrete system of linear equations.

The image is discretized into a simplicial mesh where different regions are categorized: $\mathcal{O}(M)$ represents objects of interest, $\mathcal{L}(M)$ denotes line structures, $\mathcal{I}(M)$ is the background/interior, and $\mathcal{B}(M)$ defines the boundary.

Conformal Energy Minimization

The core objective is to minimize Conformal Energy, which measures how much local angles are distorted during the transformation. By minimizing the difference between the Dirichlet energy and the target area of the mesh, the algorithm finds a mapping that is as shape-preserving as possible.

A key mathematical insight provided by the authors is the connection to M-Matrices. They prove that if the mesh utilizes a Delaunay triangulation, the resulting system involves a Stieltjes matrix, ensuring the existence and uniqueness of a solution.

Bijection Correction

To prevent topological errors, the authors implement a "Bijection Correction Algorithm." If the initial optimization results in "flipped" triangles (indicating a fold), the algorithm iteratively identifies these regions and relaxes local constraints. This process prioritizes topological correctness over perfect rigidity, ensuring the final output is always a valid, non-overlapping image.

Experimental Results

The algorithm was evaluated using the RetargetMe dataset, comparing it against methods such as Seam Carving (SC), Non-homogeneous Warping (Warp), and Beltrami Representation (BR).

  • Topological Integrity: While the popular Beltrami Representation (BR) method exhibited flip rates as high as 21.08‰ under significant compression, the proposed method achieved a 0.00‰ flip rate across all tests.
  • Geometric Distortion: The average conformal energy—a direct measure of shape distortion—was significantly lower in the proposed method (e.g., 184,568) compared to the BR method (240,671) at a 0.5 resizing ratio.
  • Visual Quality: Qualitative analysis showed that the algorithm successfully prevented the "wavy" distortion of straight lines (like horizons or architectural features) and avoided the truncation of objects common in seam-carving approaches.

Conclusion

This research provides a robust mathematical framework for bijective image retargeting. By combining conformal geometry with a discrete mesh-based optimization, the algorithm guarantees artifact-free resizing. Future work will focus on extending this framework to video retargeting, where maintaining temporal consistency and preventing flickering between frames remains a significant challenge.

Summary updated

BibTeX
@misc{liu2024one,
  author = {Chengyang Liu and Michael K. Ng},
  title = {{A One-step Image Retargeing Algorithm Based on Conformal Energy}},
  year = {2024},
  eprint = {2402.18074},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.18074},
}
Figure