IMAGE RETARGETING USING IMPORTANCE DIFFUSION
Sunghyun Cho1 , Hanul Choi1 , Yasuyuki Matsushita2 , and Seungyong Lee1
1POSTECH

2

Microsoft Research Asia

ABSTRACTThis paper presents a simple and effective image retargeting method that preserves visually important parts while
reducing unwanted distortions of an image. Our approach isbased on a novel importance diffusion scheme, which propagates importance of removed pixels to their neighbors for preserving visual contexts and avoiding over-shrinkage of unimportant parts. Importance diffusion enables even a simple
row/column removal method, which removes the least important rows/columns repeatedly, to produce visually pleasant results. It also provides control over the trade-off between uniform and non-uniform sampling for the row/column removal
and seam carving methods. Experimental results demonstratethat importance diffusion successfully improves the retargeting results of row/column removal and seam carving.
Index Terms— Image processing, image sampling, image retargeting
1. INTRODUCTION
With increasing diversity of display devices and availabilityof images, effective utilization of display space is becoming
more and more important. When viewing images on a smaller
display than originally intended, a naı̈ve scaling would notperform well because important parts in the image could become too small. Image retargeting methods aim at shrinking
the spatial size of an image while maintaining important parts
so that screen utilization is maximized.
For effective image retargeting, several approaches havebeen introduced. One major approach is based on image cropping that finds the region-of-interest (ROI) [1, 2]. The second
approach is based on image warping [3, 4, 5], which places
a grid mesh on an image and optimizes its geometry for adesired scale. The third is based on the seam carving operator [6, 7], which repeatedly carves out the least importantseams from an image.
Among these approaches, seam carving has many benefits. First, the implementation is simple, so several opensource codes are already available on internet. Second, it provides continuous changes between different scales, where theretargeted size of an image is determined by the number of removed seams. Third, the computation is not expensive, taking
time complexity of O(n) for finding the optimal seam, wheren is the number of pixels.
However, in spite of these benefits, the seam carving
method often produces distorted results, because it repeatedly
removes the least important seams while ignoring contextual
information carried by the removed parts afterwards. This
results in excessive removal of unimportant parts, and introduces distortions and loss of contextual information aroundimportant parts.
This paper presents a novel importance diffusion scheme,
which improves the seam carving method. In order to preserve the image context and avoid excessive removal of unimportant parts, importance diffusion elevates importance of theneighbors of removed pixels by propagating the importance ofremoved pixels to their neighbors after removing each seam.
As a result, images can be retargeted with less artifacts.
The importance diffusion scheme has several nice properties. With importance diffusion, as well as seam carving, evena simple method that repeatedly removes the least importantrows/columns from an image can produce visually pleasantretargeting results. Moreover, the simple method equippedwith importance diffusion often produces better results thanthe original seam carving, as we shall show in the discussion.
This simple row/column removal method can be very useful for environments with limited computing power such as
mobile devices with small displays. In addition, importancediffusion bridges the gap between uniform and non-uniform
sampling of image pixels and provides control over the tradeoff between maintained saliency and distortion in a retargeted
image.
2. RELATED WORKOne of major approachs for image retargeting is based on image cropping that finds the region-of-interest (ROI) to determine the optimal rectangular subimage to maintain. Suh etal. [1] used various features for determining salient parts forautomatic extraction of thumbnails from images. Chen etal. [2] also used a cropping based method with a more sophisticated feature for determining ROIs. These methods successfully achieve their goals, and results are shown to be superior
to simple image scaling. However, this approach loses information outside ROIs.
Another major approach is based on image warping. Liuand Gleicher [3] used a fisheye-view warping to magnify the(a) original image(b) R/C removal(c) R/C removalwith ID
Fig. 1: While simple row/column (R/C) removal results in discontinuous blocks of important parts, row/column removal with importance diffusion (ID) successfully retargets the image by avoiding excessive removal of unimportant parts.

ROI and de-empahsize less important image parts; however,their method cannot handle multiple ROIs. Wolf et al. [4]compute the optimal warping for image and video retargetingfrom pixel-wise importance values by solving linear systems.
Recently, Wang et al. [5] introduced another warping methodthat computes an optimal scaling factor for each image region,
instead of enforcing the size of important regions unchanged.
These warping methods need to solve linear systems, and they
can be time and storage demanding for devices with limited
computing power, which usually have small display sizes.
The seam carving method, which was introduced by Avidan and Shamir [6], finds the least significant seam crossing
the image vertically or horizontally. By removing or inserting
seams in a sequential manner, it successfully resizes an image while keeping important parts. Rubinstein et al. [7] further improved the seam carving method for reducing visualdistortions. They define forward energy of a seam as newly
introduced energy after removing the seam, instead of the energy of removed pixels. Our importance diffusion method
improves the quality of retargeting results by propagating importance of removed seams after each seam removal.
There have been other approaches. Setlur et al. [8] introduced a segmentation based approach that crops foregroundobjects from the background and scale the extracted foreground and background differently. But their method heavily
depends on the segmentation quality. Simakov et al. [9] introduced bidirectional similarity for measuring the similarity
between the original and the retargeted images, and retarget
an image by optimizing the similarity. Their method shows
excellent results that utilize redundancy of visual data, but it
suffers from the complicated and slow optimization process.
3. IMPORTANCE DIFFUSION
This section describes our importance diffusion scheme. For
better description, we first explain the scheme with the caseof row/column removal and extend it to seam carving.
3.1. Row/Column removal
One of the simplest idea for retargeting is to remove unimportant rows and columns from an image. Denoting a pixel

importance as v(x, y), the row and column importances vr (y)and vc (x) are computed by summing pixel importance along
the y and x directions, respectively. Pixel importances canbe computed in various ways, such as using image gradientsand using forward energy proposed by Rubinstein et al. [7].
Sequential removal of the least important rows and columns
leaves more important parts of the image.
However, repeated removal of unimportant rows andcolumns often produces unwanted artifacts, since excessive
removal of unimportant lines results in discontinuous blocksof important parts (Fig. 1(b)). This problem is caused by notpreserving the context of removed parts during row/column
removals. To resolve this problem, the neighbors of removed
parts should evidently carry the information about the removed parts as well as their own pixel information. In otherwords, the importance of the neighbors should increase reflecting the importance of the removed parts.
To realize this idea, our method updates importance ofthe neighbors of removed parts by diffusing importance ofthe removed rows and columns;
vr (y 0 ) ← vr (y 0 ) + w(y, y 0 )p(vr (y)),00(1)

0vc (x ) ← vc (x ) + w(x, x )p(vc (x)),
where x0 and y 0 are indices of neighbors of the removed column x and row y, w is a weighting function for diffusion, andp is the diffusion function. The weighting function w regulates the amount of importance passed to its neighbors. Weuse w(x, x0 ) = 1 if x0 is either x0 = x + 1 or x0 = x − 1,and w(x, x0 ) = 0 otherwise, which means only the immediateneighbors have increases of importance. The diffusion function p can be defined as any increasing function of v, such asp(v) = v/2.
Although the row/column removal approach is extremely
simple, when combined with importance diffusion, it effectively produces visually pleasing results (Fig. 1(c)). In theimplementation, finding the least important row/column canbe accelerated using a heap data structure. The simplicity andcomputational effeciency of this method can be very usefulin environments with low computing power such as mobiledevices, which usually have small display sizes.
3.2. Seam carving
The seam carving method [6, 7] is one of the most effective
image retargeting tools. In the method, a vertical seam is defined by
S = {(sy , y)},(2)where y = {1, ..., H}, sy = {1, ..., W }, and |sy − sy+1 | ≤1. A horizontal seam is defined in a similar manner. Thebackward energy function f of a vertical seam S, which wasintroduced in [6], is defined asXf (S) =v(sy , y),(3)y(a) original image(b) backward SC(c) backward SCwith ID(d) forward SC(e) forward SCwith IDFig. 2: Results of seam carving (SC) with importance diffusion show less artifacts, while the results of the original seam carving show severe
artifacts on the left part of the image. Forward/backward SC mean seam carving with the forward/backward energy, respectively.

(a) p(v) = 0(b) p(v) = v/4(c) p(v) = v/2(d) p(v) = v(e) uniform scaling
Fig. 3: Effect of importance diffusion with row/column removal. By changing the importance diffusion function p(v), the sampling ratio
between important and unimportant parts can be controlled. From (a) to (d), the retargeting result becomes more similar to uniform scaling.

and the forward energy of S, which was introduced in [7], isdefined by newly introduced pixel difference after removing
the seam S. The seam carving method repeatedly finds out
the least important seams from an image by a dynamic programming based optimization method and carves them out toretarget the image.
While the seam carving is very effective in retargeting images, it has the same problem with the simple row/columnremoval (Fig. 2(b) and (d)). It can excessively carve less important parts of an image and result in unwanted visual distortions. Similar to row/column removal, importance diffusion
can improve the seam carving method. After finding the least
important seam, we diffuse importance of every pixel on theseam to its neighboring pixels. For example, for a seam element (sy , y) of a vertical seam S, we diffuse its importanceto neighbors;v(x, y) ← v(x, y) + w(x, sy )p(v(sy , y)).

(4)With the importance diffusion, we can reduce discontinuity
artifacts and image deformation in seam carving (Fig. 2(c)and (e)).
3.3. Non-uniform and uniform sampling
The importance diffusion method enables to bride the gap
between uniform and non-uniform sampling by changing thediffusion function p(v) (Fig. 3). For example, p(v) = 0
makes the sampling process totally non-uniform, i.e., it sequentially removes the least important rows and columns

without importance diffusion. On the other hand, usingp(v) = M , where M is a value greater than the maximum
importance value, preserves neighbors of removed rows andcolumns, and the sampling process becomes similar to uniform sampling. When the function p lies within these twobounds, the sampling process becomes the midst of uniform
and non-uniform sampling. By controlling function p, we canbalance between uniform and non-uniform sampling.

4. RESULTS
We used diffusion functions p(v) = v/4 for Fig. 1, p(v) = v
for Fig. 5, and p(v) = v/2 for the others. For pixel importance values for row/column removal and backward seamcarving, we used |gx | + |gy |, where gx and gy are horizontal
and vertical gradient components for each pixel, respectively.
Fig. 4 shows a result of the simple row/column removal combined with importance diffusion. While the car
is shrunken too much in the result of simple scaling, theresult of row/column removal combined with importancediffusion preserves the car well without visual distortion.
Fig. 5 shows results of seam carving. The result of seam
carving without importance diffusion shows distorted features. Because of the amount of information in the original
image, unimportant regions are removed too much causing
the distortion. However, importance diffusion avoids excessive removal of unimportant regions, so the result of seam
carving with importance diffusion shows less artifacts.

(a) uniform scaling(c) R/C removalwith IDFig. 6: Comparison between the original seam carving androw/column removal with importance diffusion. Row/column removal with importance diffusion often preserves the image structure
better than seam carving without importance diffusion.

(a) original image(b) uniform(c) R/C removal
scalingwith ID
Fig. 4: Result of row/column removal. Row/column removal preserves the car better than uniform scaling.

(a) uniform scaling(b) forward SC(c) forward SC
with ID
Fig. 5: Result of seam carving with importance diffusion. Seamcarving with importance diffusion preserves the image context betterand produces less artifacts than the original seam carving.

(b) forward SC

Interestingly, when combined with importance diffusion,
the simple row/column removal often preserves the structureof the image content better than the original seam carving
method, especially when the image has much information.
The source image in Fig. 6 is very dense, and so the original seam carving removes unimportant seams too much andproduces a messy result (Fig. 6(b)). In this case, row/column
removal combined with importance diffusion gives a better
result (Fig. 6(c)). This is because row/column removal maintains the horizontal and vertical structures of an image, whileseam carving does not.
6. REFERENCES[1] Bongwon Suh, Haibin Ling, Benjamin B. Bederson, and David W. Jacobs, “Automatic thumbnail cropping and its effectiveness,” in Proc.
of UIST, 2003, pp. 95–104.

We also measured the processing time of row/column removal with importance diffusion to show the computational
efficiency of the method. We implemented the method inC++, and our testing environment is a PC running MS Windows XP 32bit version with Intel Core2 Quad CPU 2.66GHz.
The original sizes of Figs. 1, 4 and 6 are 1024 × 637, 334 ×500 and 500 × 377, respectively. Their retargeted sizes are750 × 637, 233 × 250 and 250 × 188, and their processingtimes were 3.91, 0.62 and 0.79 milliseconds, respectively.

[2] Li-Qun Chen, Xing Xie, Xin Fan, Wei-Ying Ma, Hong-Jiang Zhang,and He-Qin Zhou, “A visual attention model for adapting images on
small displays,” ACM Multimedia Systems Journal, pp. 353–364, 2003.

5. DISCUSSION[6] Shai Avidan and Ariel Shamir, “Seam carving for content-aware image
resizing,” ACM Trans. on Graphics, vol. 26, no. 3, pp. 10, 2007.

Similar ideas to the importance diffusion scheme have beenused in different contexts. Error diffusion based dithering
methods update attributes of neighbors of half-toned pixels tocompensate the quntization error [10]. Keeping unimportantparts for providing better understanding was also consideredin the image warping based method of Liu and Gleicher [11].
The reason why importance diffusion reduces distortions
is that importance diffusion makes non-uniform sampling ofpixels, which seam carving does, more uniformly. Uniform
sampling or scaling of an image does not break the image
structure, even though it does not preserve the original detailand scale of important parts. With importance diffusion, we
can take the advantage of uniform sampling as well as of nonuniform sampling.

[7] Michael Rubinstein, Ariel Shamir, and Shai Avidan, “Improved seam
carving for video retargeting,” ACM Trans. on Graphics, vol. 27, no. 3,2008.

[3] Feng Liu and Michael Gleicher, “Automatic image retargeting withfisheye-view warping,” in Proc. of UIST, 2005, pp. 153–162.
[4] Lior Wolf, Moshe Guttmann, and Daniel Cohen-Or,“Nonhomogeneous content-driven video retargeting,” in Proc. of Int’l Conf.
on Comp. Vis. (ICCV), 2007.
[5] Yu-Shuen Wang, Chiew-Lan Tai, Olga Sorkine, and Tong-Yee Lee,
“Optimized scale-and-stretch for image resizing,” ACM Trans. onGraphics, vol. 27, no. 5, 2008.

[8] Vidya Setlur, Saeko Takagi, Ramesh Raskar, Michael Gleicher, andBruce Gooch, “Automatic image retargeting,” in Proc. of Int’l Conf. on
Mobile and ubiquitous multimedia, 2005, pp. 59–68.
[9] Denis Simakov, Yaron Caspi, Eli Shechtman, and Michal Irani, “Summarizing visual data using bidirectional similarity,” in Proc. of Comp.
Vis. and Patt. Recog. (CVPR), 2008, pp. 1–8.
[10] Robert Ulichney, Digital Halftoning, MIT Press, 1987.
[11] Feng Liu and Michael Gleicher, “Video retargeting: automating panand scan,” in Proc. of ACM Multimedia, 2006, pp. 241–250.