#include <cassert>
#include "processing.h"
using namespace std;
// REQUIRES: img points to a valid Image
// MODIFIES: *img
// EFFECTS: The image is rotated 90 degrees to the left (counterclockwise).
void rotate_left(Image* img) {
// for convenience
int width = Image_width(img);
int height = Image_height(img);
// auxiliary image to temporarily store rotated image
Image *aux = new Image;
Image_init(aux, height, width); // width and height switched
// iterate through pixels and place each where it goes in temp
for (int r = 0; r < height; ++r) {
for (int c = 0; c < width; ++c) {
Image_set_pixel(aux, width - 1 - c, r, Image_get_pixel(img, r, c));
}
}
// Copy data back into original
*img = *aux;
delete aux;
}
// REQUIRES: img points to a valid Image.
// MODIFIES: *img
// EFFECTS: The image is rotated 90 degrees to the right (clockwise).
void rotate_right(Image* img){
// for convenience
int width = Image_width(img);
int height = Image_height(img);
// auxiliary image to temporarily store rotated image
Image *aux = new Image;
Image_init(aux, height, width); // width and height switched
// iterate through pixels and place each where it goes in temp
for (int r = 0; r < height; ++r) {
for (int c = 0; c < width; ++c) {
Image_set_pixel(aux, c, height - 1 - r, Image_get_pixel(img, r, c));
}
}
// Copy data back into original
*img = *aux;
delete aux;
}
static int squared_difference(Pixel p1, Pixel p2) {
int dr = p2.r - p1.r;
int dg = p2.g - p1.g;
int db = p2.b - p1.b;
// Divide by 100 is to avoid possible overflows
// later on in the algorithm.
return (dr*dr + dg*dg + db*db) / 100;
}
// REQUIRES: img points to a valid Image.
// energy points to a Matrix.
// MODIFIES: *energy
// EFFECTS: energy serves as an "output parameter".
// The Matrix pointed to by energy is initialized to be the same
// size as the given Image, and then the energy matrix for that
// image is computed and written into it.
void compute_energy_matrix(const Image* img, Matrix* energy) {
Matrix_init(energy, Image_width(img), Image_height(img));
Matrix_fill(energy, 0);
for (int r = 1; r < Matrix_height(energy) - 1; r++) {
for (int c = 1; c < Matrix_width(energy) - 1; c++) {
Pixel pn = Image_get_pixel(img, r - 1, c);
Pixel ps = Image_get_pixel(img, r + 1, c);
Pixel pw = Image_get_pixel(img, r, c - 1);
Pixel pe = Image_get_pixel(img, r, c + 1);
*Matrix_at(energy, r, c) =
squared_difference(pn, ps) + squared_difference(pw, pe);
}
}
Matrix_fill_border(energy, Matrix_max(energy));
}
// REQUIRES: energy points to a valid Matrix.
// cost points to a Matrix.
// energy and cost aren't pointing to the same Matrix
// MODIFIES: *cost
// EFFECTS: cost serves as an "output parameter".
// The Matrix pointed to by cost is initialized to be the same
// size as the given energy Matrix, and then the cost matrix is
// computed and written into it.
void compute_vertical_cost_matrix(const Matrix* energy, Matrix *cost) {
Matrix_init(cost, Matrix_width(energy), Matrix_height(energy));
for (int c = 0; c < Matrix_width(cost); c++) {
*Matrix_at(cost, 0, c) = *Matrix_at(energy, 0, c);
}
for (int r = 1; r < Matrix_height(cost); r++) {
for (int c = 0; c < Matrix_width(cost); c++) {
if (c == 0) {
*Matrix_at(cost, r, c) = *Matrix_at(energy, r, c)
+ Matrix_min_value_in_row(cost, r - 1, c, c + 2);
}
else if (c == Matrix_width(cost) - 1) {
*Matrix_at(cost, r, c) = *Matrix_at(energy, r, c)
+ Matrix_min_value_in_row(cost, r - 1, c - 1, c + 1);
}
else {
*Matrix_at(cost, r, c) = *Matrix_at(energy, r, c)
+ Matrix_min_value_in_row(cost, r - 1, c - 1, c + 2);
}
}
}
}
// REQUIRES: cost points to a valid Matrix
// seam points to an array
// the size of seam is >= Matrix_height(cost)
// MODIFIES: seam[0]...seam[Matrix_height(cost)-1]
// EFFECTS: seam serves as an "output parameter".
// The vertical seam with the minimal cost according to the given
// cost matrix is found and the seam array is filled with the column
// numbers for each pixel along the seam, with the pixel for each
// row r placed at seam[r]. While determining the seam, if any pixels
// tie for lowest cost, the leftmost one (i.e. with the lowest
// column number) is used.
void find_minimal_vertical_seam(const Matrix* cost, int seam[]) {
int i = Matrix_height(cost) - 1;
seam[i] = Matrix_column_of_min_value_in_row
(cost, Matrix_height(cost) - 1, 0, Matrix_width(cost) - 1);
i -= 1;
for (int r = Matrix_height(cost) - 2; r >= 0; r--) {
int c = seam[i + 1];
if (c == 0) {
seam[i] = Matrix_column_of_min_value_in_row(cost, r, c, c + 2);
i -= 1;
}
else if (c == Matrix_width(cost) - 1) {
seam[i] = Matrix_column_of_min_value_in_row(cost, r, c - 1, c + 1);
i -= 1;
}
else {
seam[i] = Matrix_column_of_min_value_in_row(cost, r, c - 1, c + 2);
i -= 1;
}
}
}
// REQUIRES: img points to a valid Image with width >= 2
// seam points to an array
// the size of seam is == Image_height(img)
// each element x in seam satisfies 0 <= x < Image_width(img)
// MODIFIES: *img
// EFFECTS: Removes the given vertical seam from the Image. That is, one
// pixel will be removed from every row in the image. The pixel
// removed from row r will be the one with column equal to seam[r].
// The width of the image will be one less than before.
/
void remove_vertical_seam(Image *img, const int seam[]) {
Image *aux_img = new Image;
Image_init(aux_img, Image_width(img) - 1, Image_height(img));
for (int r = 0; r < Image_height(aux_img); r++) {
for (int c = 0; c < Image_width(aux_img); c++) {
if (c < seam[r]) {
Image_set_pixel(aux_img, r, c, Image_get_pixel(img, r, c));
}
if (c >= seam[r]) {
Image_set_pixel(aux_img, r, c, Image_get_pixel(img, r, c + 1));
}
}
}
*img = *aux_img;
delete aux_img;
}
// REQUIRES: img points to a valid Image
// 0 < newWidth && newWidth <= Image_width(img)
// MODIFIES: *img
// EFFECTS: Reduces the width of the given Image to be newWidth by using
// the seam carving algorithm.
void seam_carve_width(Image *img, int newWidth) {
assert(0 < newWidth && newWidth <= Image_width(img));
Matrix *energy = new Matrix;
Matrix *cost = new Matrix;
int *seam = new int[Image_height(img)];
while (Image_width(img) > newWidth) {
compute_energy_matrix(img, energy);
compute_vertical_cost_matrix(energy, cost);
find_minimal_vertical_seam(cost, seam);
remove_vertical_seam(img, seam);
}
delete energy;
delete cost;
delete[] seam;
}
// REQUIRES: img points to a valid Image
// 0 < newHeight && newHeight <= Image_height(img)
// MODIFIES: *img
// EFFECTS: Reduces the height of the given Image to be newHeight.
void seam_carve_height(Image *img, int newHeight) {
assert(0 < newHeight && newHeight <= Image_height(img));
rotate_left(img);
seam_carve_width(img, newHeight);
rotate_right(img);
}
// REQUIRES: img points to a valid Image
// 0 < newWidth && newWidth <= Image_width(img)
// 0 < newHeight && newHeight <= Image_height(img)
// MODIFIES: *img
// EFFECTS: Reduces the width and height of the given Image to be newWidth
// and newHeight, respectively.
void seam_carve(Image *img, int newWidth, int newHeight) {
assert(0 < newWidth && newWidth <= Image_width(img));
assert(0 < newHeight && newHeight <= Image_height(img));
seam_carve_width(img, newWidth);
seam_carve_height(img, newHeight);
}