Senior 2
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Senior 2 as PDF for free.
More details
- Words: 1,764
- Pages: 71
produced by: Mr. Visanu Upatumphan ID. 4788244 Mr. Yingpong Vimugtipant ID. 4788247 Miss. Sompak Boonwong ID. 4788263
Advisor: Dr. Rawesak Tanawongsuwan
1
SEAM CARVING • An image resizing algorithm developed by Shai Avidan and Ariel Shamir in Siggraph 2007 • Not by scaling or cropping • Removing pixels from the area of an image or adding pixels to the area of an image that are least important
2
TEASER
3
IMAGE SCALING Result of extending in one dimension and reducing in the other, compared to standard scaling on the bottom right
The original image with one horizontal and one vertical seam
The energy function shown the magnitude of the gradient
4
MOTIVATION • New idea in image scaling algorithm • Learn how researchers do research in CG and image processing • Learn Matlab to develop a prototype
5
SCOPE • Image resizing software implemented in Matlab • Allowing vertical & horizontal stretch • Software to load image, do resizing and save
6
PROBLEM STATEMENT
Input Image
Remove or Add pixels for both Vertical and Horizontal
Show the output and save
7
IMAGE RESIZING IN GENERAL There are two simple concepts in image resizing:
• image scaling • image cropping
8
SCALING AND CROPPING
9
CROPPING
10
SCALING
11
SCALING AND CROPPING Scaling causes • changing in shape of image
Cropping causes • losing some contents which have been deleted
12
REGION-OF-INTEREST (ROI)
•To select samples for a particular purpose •Need more memory and a lot of processes 13
VERTICAL SCALING
14
USING ENERGY
15
USING ENERGY
16
OVERVIEW OF THE ALGORITHM Finding a seam includes 5 steps 1. Read Image 2. Find energy: energy of the picture 3. Find the best seam 4. Delete seam or add seam 5. Show result
17
THE FLOW OF THE ALGORITHM Read Image
Find Energy Find the best seam
Show Result
Delete or Duplicate seam
18
FIND ENERGY Use to calculate the importance:
Suppose we want to find the energy at pixel of position (i,j) 19
FIND ENERGY Example: 12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
20
FIND ENERGY
Find energy of this pixel
12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
21
FIND ENERGY
Use this 4 pixels to calculate e=
12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
= 7
22
FIND ENERGY
Energy of this pixel
7
23
FIND ENERGY
To find energy of the edge pixel, we have to expand the image one pixel outward
12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
24
FIND ENERGY 12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
25
FIND ENERGY 12
12
17
33
37
19
19
12
12
17
33
37
19
19
18
18
28
8
25
33
33
15
15
11
13
22
24
24
17
17
11
11
21
27
27
20
20
10
14
26
27
27
20
20
10
14
26
27
27 26
FIND ENERGY • Matrix of energy 5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
27
DYNAMIC PROGRAMMING Dynamic programming is a method of solving problems exhibiting the properties of:
– overlapping sub-problems Break and reuse ex. Fibonacci sequence – optimal substructure Break and Use optimal solutions
28
FIND THE BEST SEAM
Find M values: values prepared to find a seam • Start with Second row • Follow M equation for the individual
• Keep track the minimal M values
1
2
M
3 29
COMPUTING M VALUES
Energy
e(i,j) M(i,j) M Matrix 30
FIND THE BEST SEAM • Example: energy matrix 29.5 5.5
40 16
47.5 22.5
57 13
54 16
36.5 6.5
27 8
49.5 11.5
50 20
50.5 6.5
30.5 2.5
33.5 9.5
26 7
41.5 7.5
53 4
31.5 5.5
24.5 3.5
29.5 5.5
43 10
49.5 4.5
33.5 6.5
27.5 3.5
30.5 9.5
44 9
53.5 0.5
31
FIND THE BEST SEAM
To find M, Start with the second row. In the first row we can use energy
5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
32
FIND THE BEST SEAM Find M value of this pixel 5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
33
FIND THE BEST SEAM Use 2 values to compare the minimum one
0
Keep track
5.5
16
22.5
13
0
0
2
16
12
6.5+5.5 = 12
1
2
M
3 34
FIND THE BEST SEAM Find M value of this pixel
5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
35
FIND THE BEST SEAM Use 3 values to compare the minimum one 5.5
16
12
8
22.5
13
16
0
0
2
1
0
Keep track
8+5.5 = 13.5
1
2
M
3 36
FIND THE BEST SEAM
5.5
16
22.5
12
13.5
11.5
11.5+13 = 24.5
13
16
0
0
0
2
1
3
Keep track
1
2
M
3 37
FIND THE BEST SEAM
5.5
16
22.5
13
16
12
13.5
24.5
20
6.5
0
0
0
0
2
1
3
2
Keep track
20+13 = 33 1
2
M
3 38
FIND THE BEST SEAM 5.5
16
22.5
13
12
13.5
11.5
33
0
0
0
0
0
2
16 1
3
2
1
6.5
Keep track
6.5+13 = 19.5
1
2
M
3 39
FIND THE BEST SEAM • Matrix of M 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5
40
FIND THE BEST SEAM • Matrix of Keeping track 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
41
BACKTRACK – This process will produce the seam - Find the least M value of the last row - Follow the track that we keep from the previous process
42
BACKTRACK
0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
16 3
2
1
1
2
• Example B a c k t r a c k
5.5
16
22.5
13
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5
1
2
3
M
43
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
1
2
M
3
Least M at the last row 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5
44
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
1
2
3
M 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 45
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2 12
1
2
3
M 5.5
16
22.5
13
16
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 46
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2 12
1
2
3
M 5.5
16
22.5
13
16
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 47
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
1
2
3
M 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 48
DELETE SEAM In order to reduce the image size, we can do by delete Seam: • remove that seam directly • shift the rest to fill the blanks
49
DELETE SEAM • Example 5.5
16
22.5
13
16
12
13.5
24.5
33
16 19.5
22.5
13
16
14.5
21.5
20.5
27
13.5 23.5
24.5
33
19.5
20
18
26
30.5
21.5 28
20.5
27
23.5
24.5
21.5
27.5
35
20 28.5
26
30.5
28
24.5
27.5
35
28.5 50
DELETE SEAM
51
SHRINK VS STRETCH To Shrink • Remove and Shift To Stretch • Shift the rest to make blanks • Find the average the beside pixels • Put in the Blanks 52
VERTICAL VS HORIZONTAL To compute Horizontal seam is similar to Vertical by inversing • Column to row • Row to Column With the same processes
53
IMPLEMENTATION • Operating System and Utilities Application – Microsoft Window XP with service pack 2
• Programming and Scripting Tools – Matlab R2007a with Image Processing Toolbox – main language in implementation
54
INTERFACE DESIGN There will be two main components: - Controller - Display
55
INTERFACE DESIGN(CONT) The overall of interface 5 windows: 4 display 1 controller
56
INTERFACE DESIGN(CONT) Controller
57
BROWSE AND SAVE
58
DISPLAY ORIGINAL IMAGE
MODIFIED IMAGE
SEAM IMAGE ENERGY IMAGE 59
EXAMPLE RESULT
60
EXAMPLE RESULT
Removing Vertical Seam 61
EXAMPLE RESULT
Removing Horizontal Seam 62
EXAMPLE RESULT
63
EXAMPLE RESULT
64
COMPARING RESULT
Our Result
Scaled
Cropped
100 Height Remove 65
EXAMPLE RESULT
Stretch Vertical Seam 66
CONCLUSION After the implementation, we • Understand seam carving algorithm • Can using Matlab
67
PROBLEM AND LIMITATIONS • Losing quality after increasing size • Speed
• Support only JPEG
68
FUTURE WORK • Improve speed • Combine to other application
69
• Let’s see our demo!!
70
71
Advisor: Dr. Rawesak Tanawongsuwan
1
SEAM CARVING • An image resizing algorithm developed by Shai Avidan and Ariel Shamir in Siggraph 2007 • Not by scaling or cropping • Removing pixels from the area of an image or adding pixels to the area of an image that are least important
2
TEASER
3
IMAGE SCALING Result of extending in one dimension and reducing in the other, compared to standard scaling on the bottom right
The original image with one horizontal and one vertical seam
The energy function shown the magnitude of the gradient
4
MOTIVATION • New idea in image scaling algorithm • Learn how researchers do research in CG and image processing • Learn Matlab to develop a prototype
5
SCOPE • Image resizing software implemented in Matlab • Allowing vertical & horizontal stretch • Software to load image, do resizing and save
6
PROBLEM STATEMENT
Input Image
Remove or Add pixels for both Vertical and Horizontal
Show the output and save
7
IMAGE RESIZING IN GENERAL There are two simple concepts in image resizing:
• image scaling • image cropping
8
SCALING AND CROPPING
9
CROPPING
10
SCALING
11
SCALING AND CROPPING Scaling causes • changing in shape of image
Cropping causes • losing some contents which have been deleted
12
REGION-OF-INTEREST (ROI)
•To select samples for a particular purpose •Need more memory and a lot of processes 13
VERTICAL SCALING
14
USING ENERGY
15
USING ENERGY
16
OVERVIEW OF THE ALGORITHM Finding a seam includes 5 steps 1. Read Image 2. Find energy: energy of the picture 3. Find the best seam 4. Delete seam or add seam 5. Show result
17
THE FLOW OF THE ALGORITHM Read Image
Find Energy Find the best seam
Show Result
Delete or Duplicate seam
18
FIND ENERGY Use to calculate the importance:
Suppose we want to find the energy at pixel of position (i,j) 19
FIND ENERGY Example: 12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
20
FIND ENERGY
Find energy of this pixel
12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
21
FIND ENERGY
Use this 4 pixels to calculate e=
12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
= 7
22
FIND ENERGY
Energy of this pixel
7
23
FIND ENERGY
To find energy of the edge pixel, we have to expand the image one pixel outward
12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
24
FIND ENERGY 12
17
33
37
19
18
28
8
25
33
15
11
13
22
24
17
11
11
21
27
20
10
14
26
27
25
FIND ENERGY 12
12
17
33
37
19
19
12
12
17
33
37
19
19
18
18
28
8
25
33
33
15
15
11
13
22
24
24
17
17
11
11
21
27
27
20
20
10
14
26
27
27
20
20
10
14
26
27
27 26
FIND ENERGY • Matrix of energy 5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
27
DYNAMIC PROGRAMMING Dynamic programming is a method of solving problems exhibiting the properties of:
– overlapping sub-problems Break and reuse ex. Fibonacci sequence – optimal substructure Break and Use optimal solutions
28
FIND THE BEST SEAM
Find M values: values prepared to find a seam • Start with Second row • Follow M equation for the individual
• Keep track the minimal M values
1
2
M
3 29
COMPUTING M VALUES
Energy
e(i,j) M(i,j) M Matrix 30
FIND THE BEST SEAM • Example: energy matrix 29.5 5.5
40 16
47.5 22.5
57 13
54 16
36.5 6.5
27 8
49.5 11.5
50 20
50.5 6.5
30.5 2.5
33.5 9.5
26 7
41.5 7.5
53 4
31.5 5.5
24.5 3.5
29.5 5.5
43 10
49.5 4.5
33.5 6.5
27.5 3.5
30.5 9.5
44 9
53.5 0.5
31
FIND THE BEST SEAM
To find M, Start with the second row. In the first row we can use energy
5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
32
FIND THE BEST SEAM Find M value of this pixel 5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
33
FIND THE BEST SEAM Use 2 values to compare the minimum one
0
Keep track
5.5
16
22.5
13
0
0
2
16
12
6.5+5.5 = 12
1
2
M
3 34
FIND THE BEST SEAM Find M value of this pixel
5.5
16
22.5
13
16
6.5
8
11.5
20
6.5
2.5
9.5
7
7.5
4
5.5
3.5
5.5
10
4.5
6.5
3.5
9.5
9
0.5
35
FIND THE BEST SEAM Use 3 values to compare the minimum one 5.5
16
12
8
22.5
13
16
0
0
2
1
0
Keep track
8+5.5 = 13.5
1
2
M
3 36
FIND THE BEST SEAM
5.5
16
22.5
12
13.5
11.5
11.5+13 = 24.5
13
16
0
0
0
2
1
3
Keep track
1
2
M
3 37
FIND THE BEST SEAM
5.5
16
22.5
13
16
12
13.5
24.5
20
6.5
0
0
0
0
2
1
3
2
Keep track
20+13 = 33 1
2
M
3 38
FIND THE BEST SEAM 5.5
16
22.5
13
12
13.5
11.5
33
0
0
0
0
0
2
16 1
3
2
1
6.5
Keep track
6.5+13 = 19.5
1
2
M
3 39
FIND THE BEST SEAM • Matrix of M 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5
40
FIND THE BEST SEAM • Matrix of Keeping track 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
41
BACKTRACK – This process will produce the seam - Find the least M value of the last row - Follow the track that we keep from the previous process
42
BACKTRACK
0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
16 3
2
1
1
2
• Example B a c k t r a c k
5.5
16
22.5
13
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5
1
2
3
M
43
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
1
2
M
3
Least M at the last row 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5
44
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
1
2
3
M 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 45
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2 12
1
2
3
M 5.5
16
22.5
13
16
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 46
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2 12
1
2
3
M 5.5
16
22.5
13
16
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 47
BACKTRACK 0
0
0
0
0
2
1
3
2
1
2
1
1
3
2
2
1
2
1
2
3
2
1
1
2
1
2
3
M 5.5
16
22.5
13
16
12
13.5
24.5
33
19.5
14.5
21.5
20.5
27
23.5
20
18
26
30.5
28
24.5
21.5
27.5
35
28.5 48
DELETE SEAM In order to reduce the image size, we can do by delete Seam: • remove that seam directly • shift the rest to fill the blanks
49
DELETE SEAM • Example 5.5
16
22.5
13
16
12
13.5
24.5
33
16 19.5
22.5
13
16
14.5
21.5
20.5
27
13.5 23.5
24.5
33
19.5
20
18
26
30.5
21.5 28
20.5
27
23.5
24.5
21.5
27.5
35
20 28.5
26
30.5
28
24.5
27.5
35
28.5 50
DELETE SEAM
51
SHRINK VS STRETCH To Shrink • Remove and Shift To Stretch • Shift the rest to make blanks • Find the average the beside pixels • Put in the Blanks 52
VERTICAL VS HORIZONTAL To compute Horizontal seam is similar to Vertical by inversing • Column to row • Row to Column With the same processes
53
IMPLEMENTATION • Operating System and Utilities Application – Microsoft Window XP with service pack 2
• Programming and Scripting Tools – Matlab R2007a with Image Processing Toolbox – main language in implementation
54
INTERFACE DESIGN There will be two main components: - Controller - Display
55
INTERFACE DESIGN(CONT) The overall of interface 5 windows: 4 display 1 controller
56
INTERFACE DESIGN(CONT) Controller
57
BROWSE AND SAVE
58
DISPLAY ORIGINAL IMAGE
MODIFIED IMAGE
SEAM IMAGE ENERGY IMAGE 59
EXAMPLE RESULT
60
EXAMPLE RESULT
Removing Vertical Seam 61
EXAMPLE RESULT
Removing Horizontal Seam 62
EXAMPLE RESULT
63
EXAMPLE RESULT
64
COMPARING RESULT
Our Result
Scaled
Cropped
100 Height Remove 65
EXAMPLE RESULT
Stretch Vertical Seam 66
CONCLUSION After the implementation, we • Understand seam carving algorithm • Can using Matlab
67
PROBLEM AND LIMITATIONS • Losing quality after increasing size • Speed
• Support only JPEG
68
FUTURE WORK • Improve speed • Combine to other application
69
• Let’s see our demo!!
70
71
Related Documents
Senior 2
November 2019 22
Senior
April 2020 38
Senior Ad 2
December 2019 10
Senior Letter (2)
April 2020 5
Senior 2 Elections Dialogue
October 2019 13