DSAA(B)2024 Project:Seam-Carving
DSAA(B)2024 Project:Seam-Carving
In this project,you are required to implement seam-carving algorithm to do resize on imagefiles.
To illustrate seam-carving,first see the above images.The left image is the original.The right image is the image shrinked by seam-carving. It is obvious that the algorithm isn't doing a simple resize as the shape of "important"objects in the image (surfing people)remains the
same.The seam-carving algorithm remove unimportant areas in the images while keeps the objects in the images unharmed.
Introduction of seam-carving Seam-carving
Seam-carving looks for seams in an image.By removing a vertical (horizontal)seam in the image,the width (height)of the image is reduced by one.Keep removing seams from image and the image will be resized to desired size.
The red line in the above image is a "seam"as we mentioned above.A vertical seam is a path containing many pixels.Along this path,each row in the image contains exactly one pixel (so that the image remains rectangle after this seam gets removed).If the coordinate of one of the pixels in this path is (x,y),then the possible coordinate of the pixel in the next line is (x-1,y+1),(x,y+1),(x+1,y+1).
This seam is carefully selected by algorithm so that it go through not so important area of the image.
Seam Selection
This section is how you can select seam usually.
An imagefile with M rows and N columns can be seen as an M by N matrix.The pixel on the siSth row and sjSth column in the image corresponds to the element on thesisth row and sj$th column of the matrix.Value 255 is white,and O is black.If this is a colored image, then the elements in the matrix each contains three values,the red,blue and green values,a.k.a rgb value.
With above description in mind,we can define the energy of a pixel:
√ △?(a,y)+△;(a,y)
where △2(x,y)=R(x,y)2+G7(x,y)2+Br(x,y)2.The variables R.,Ga,Br are the differences or "gradients"of red,green,bluechannel on the x-axis of position(x,y).Ra(x,y)can be defined asr(x+1,y)-r(x-1,y),where r(x,y)is the red value of the
pixel on(x,y).Other variables can be defined similarly.
Whenever we need to find a vertical seam,we find a vertical path on the image with minimal sum of energy.Then we can remove this seam from the image,shrink its width by one.Keep this process until the width of the image reach your goal.
The energy pixels on the border of the image (e.g.pixel on (0,1),(width-1,height-1))may be taken care of differently.You can assign their energy as 1000
The principle of finding a horizontal seam can be applied similarly.
Project Requirement
In this project,each team should finish the work as follows:
1.Implements basic seam-carving algorithm,which can help people to shrink the size of the image.
o Calculationofenergyfunction.
o Shrinking the imagesize, both vertically and horizontally, while the image should still remain rectangle.
2. Improve the algorithm so that the it can also expend the image. So that the image is larger than the original size.
3. Build operatable GUl for your program. Your program should be able to show the image and let user operate on the image.
4. User should be allowed to protect some part of the image so that the selected area are not removed by the algorithm. Also let the user to select some area so that these area easier to be removed by seam-carving algorithm.
Addtional Requirement
You can only use JAVA standard library and algs4. Other 3rd party libraries are not allowed.
