1 of 53

� Computer Graphics Meets CVGIP

李同益

​

Image Resizing Using Seam Carving (SC)

2 of 53

Image/Video Retargeting

  • Adapt image/video content to different display devices
    • Resolution
    • Aspect ratio

​

​

​

16 : 9

? : ?

2.39 : 1

4 : 3

Direct scale

along x axis

Distorted

along x axis

3 of 53

Image Resizing

  • Need to fit images to various display media (wide-screen TV, PDA, thumbnail...) but with less distortion !!

4:3

16:9

1:1

4 of 53

Resizing – Standard Solutions

  • Linear scaling
    • everything is distorted
  • Letterboxing
    • screen not fully utilized
  • Cropping
    • objects close to boundary are removed

© Blender Foundation

5 of 53

Resizing – Standard Solutions

  • Linear scaling
    • everything is distorted
  • Letterboxing
    • screen not fully utilized
  • Cropping
    • objects close to boundary are removed

© Blender Foundation

6 of 53

Resizing – Standard Solutions

  • Linear scaling
    • everything is distorted
  • Letterboxing
    • screen not fully utilized
    • Uniformly scaled, i.e. no distortion but with non-appealing empty space!!!
  • Cropping
    • Lobjects close to boundary are removed

© Blender Foundation

7 of 53

Resizing – Standard Solutions

  • Linear scaling
    • everything is distorted
  • Letterboxing
    • screen not fully utilized
  • Cropping
    • objects close to boundary are removed
    • May lose important objects

© Blender Foundation

8 of 53

Resizing – Content-Aware Solutions

Seam-carving

[Avidan+Shamir 2007]

i.e., cut unimportant

seams

Non-homo. warping

[Wolf et al. 2007], i.e.,

deform non-important

objects only

​

Optimized scale&stretch

[Wang et al. 2008], i.e.

allowing uniform scale

for important objects

and non-uniform scale

for non-important

objects

Determine ‘important’ regions

Apply operator

[Visual Media Retargeting, SIGGRAPH Asia 09 Course]

9 of 53

Seam carving: nonlinear cropping�[Avidan and Shamir 2007; Rubinstein et al. 2008]

  • Define an importance map (for example: gradients)

​

​

​

​

​

  • Remove lowest-energy 1D seams (one by one)

i.e., Gray = R*0.299 + G*0.587 + B*0.114

An image gradient is a directional change in the intensity or color in an image. 

    • A seam is a connected path of low energy pixels crossing the image from top to bottom, or from left to right

(x,y)

(x,y)

10 of 53

10

Original image to be made narrower

Scaling is undesirable because the castle is distorted.

Cropping is undesirable

because part of the castle is removed.

Seam carving

11 of 53

Image reduction & Image enlarging

  • For image reduction, seam selection ensures that while preserving the image structure, we remove more of the low energy pixels and fewer of the high energy ones.
  • For image enlarging, the order of seam insertion ensures a balance between the original image content and the artificially inserted pixels.

​

11

Image enlarging n seams

i.e., select n highest seams and duplicate n seams

Image reducing n seams, i.e., select n lowest seams and delete n seams

12 of 53

Seam Carving

  • A seam is a connected path of low energy pixels crossing the image from top to bottom, or from left to right.
  • Seam-carving is a simple image operator that can change the size of an image.
  • Image enlarging n seams i.e., select n highest seams and duplicate n seams

​

​

​

​

12

13 of 53

Image reduction

  • Results of 4 different strategies for reducing the width of an image.
  • (b)有最高能量的子視窗 (crop)
  • (c)移除每行有最低能量
  • (d)Seam removal
  • (e)每行移除相同數的低能量

​

13

14 of 53

Image reduction (conti.)

14

12.8

15 of 53

Image reduction (conti.)

15

12.8

12.8

16 of 53

Image reduction (conti.)

16

12.8

12.8

13.4

17 of 53

Image reduction (conti.)

17

12.8

12.8

13.4

13.1

18 of 53

Image reduction (conti.)

18

12.8

12.8

13.4

13.1

13.5

19 of 53

Image reduction (conti.)

19

12.8

12.8

13.4

13.1

13.5

12

20 of 53

Image reduction (conti.)

20

12.8

12.8

13.4

13.1

13.5

12

21 of 53

Image reduction

  • Results of 5 different strategies for reducing the width of an image.
  • (b)有最高能量的子視窗
  • (c)移除每行有最低能量
  • (d)Seam removal
  • (e)每行移除相同數的低能量

21

22 of 53

Image reduction (conti.)

22

2

23 of 53

Image reduction (conti.)

23

2

2.6

24 of 53

Image reduction (conti.)

24

2

2.6

3.2

25 of 53

Image reduction (conti.)

25

2

2.6

3.2

26 of 53

Image reduction (conti.)

26

2

2.6

3.2

2

3

2

3.2

2.9

2.4

1.5

27 of 53

Image reduction (conti.)

27

2

2.6

3.2

2

3

2

3.2

2.9

2.4

1.5

The disadvantage is to lose some important pixels on some deleted lines

such as 2nd line (with 2.4)

28 of 53

Image reduction

  • Results of 5 different strategies for reducing the width of an image.
  • (b)有最高能量的子視窗
  • (c)移除每行有最低能量
  • (d)Seam removal
  • (e)每行移除相同數的低能量

28

29 of 53

Image reduction (conti.)

29

1.6

30 of 53

Image reduction (conti.)

30

1.6

1.5

31 of 53

Image reduction (conti.)

31

1.6

1.5

1.9

32 of 53

Image reduction (conti.)

32

1.6

1.5

1.9

33 of 53

Image reduction (conti.)

33

1.6

1.5

1.9

1.3

1.9

1.7

2.2

1.7

1.6

1.0

34 of 53

Image reduction (conti.)

34

1.6

1.5

1.9

1.3

1.9

1.7

2.2

1.7

1.6

1.0

35 of 53

Image reduction

  • Results of 5 different strategies for reducing the width of an image.
  • (b)有最高能量的子視窗
  • (c)移除每行有最低能量
  • (d)Seam removal
  • (e)每行移除相同數的低能量

35

36 of 53

Image reduction (conti.)

36

37 of 53

Image reduction (conti.)

37

V

V

V

V

V

38 of 53

Image reduction (conti.)

38

V

V

V

V

V

This pixel is not selected for

this line,

So, breaking continuity

​

39 of 53

Aspect Ratio Change(1/2)

  • 影像縮減：
  • Left:

Seam removals

  • Center:

Scaling

  • Right:

Cropping

39

40 of 53

Aspect Ratio Change(2/2)

  • 影像拉寬：
  • In both examples the original

image is widened by seam

insertion.

​

​

40

(a) To add a line, 1) choose a seam with

largest value, and then 2) repeat a same seam

​

(b) To add n line, 1) choose n seams first

and then 2) repeat n seams

41 of 53

Object Removal

  • The system can automatically calculate the smaller of the vertical or horizontal diameters (in pixels) of the target removal region and perform vertical or horizontal removals accordingly .
  • 用簡單的UI讓使用者

描繪出要移除的物件

​

​

41

42 of 53

Limitations

  • Combined with a face detector we get much better results.
  • Detected pixels will be important, so their seams are avoided to be deleted as possibly as they could be

42

Without detection

With detection

43 of 53

Limitations

  • 若影像太過單調，且不包含不太重要的部分，則不太適用此方法，用傳統的scaling 反而會比較好。

43

44 of 53

影片Demo

44

45 of 53

Reference

  • Seam carving for content aware image resizing: MATLAB

http://danluong.com/2007/12/21/seam-carving-matlab-implementation-tutorial/

  • liquid-resize

http://www.thegedanken.com/retarget/

  • CAIR code

http://code.google.com/p/seam-carving-gui/

  • Rsizr線上

http://cn.rsizr.com/

  • 簡單小程式

http://swieskowski.net/carve/

45

46 of 53

OPTIMIZED SCALE-AND-STRETCH FOR IMAGE RESIZING

published in ACM Siggraph Asia 2008

47 of 53

Importance map

saliency map

[Itti et al. 98]

x

=

importance map

gradients only

importance map

48 of 53

The warping mechanism

quads with high importance:�uniform scaling

quads with low importance:

allowed non-uniform scaling

Optimize the location of mesh vertices, interpolate image

49 of 53

The warping mechanism

  • Grid mesh, preserve the shape of the important quads

​

​

​

​

​

​

​

  • Optimize the location of mesh vertices, interpolate image

50 of 53

Results

original

SC (Seam carving)

ours

http://graphics.csie.ncku.edu.tw/Image_Resizing/data/ImageResizing08.mp4

​

51 of 53

51

Motion-Aware Temporal Coherence for Video Resizing

Yu-Shuen Wang1, Hongbo Fu2, Olga Sorkine3, Tong-Yee Lee1, Hans-Peter Seidel4

ACM Transaction on Graphics (Proceedings of SIGGRAPH 2009 Asia)

1National Cheng Kung University, Taiwan, 2City University of Hong Kong, 3New York University, 4MPI Informatik

http://graphics.csie.ncku.edu.tw/VideoResizing/data/videoResizing.mp4

​

52 of 53

52

Non-homogeneous Resizing of Complex Models

53 of 53

53

http://graphics.csie.ncku.edu.tw/Vis2008/vis-1013_final_video.mp4

​