Seam Carving

Definition

Definition

Seam Carving Algorithm is a content-aware image resizing technique that intelligently removes or adds pixels from an image's least noticeable areas, rather than simply scaling it. This allows for resizing without distorting important features in the image

Explanation

Iteratively finding and removing or adding seams, which are connected paths of pixels with the least energy in the image. Energy is a measure of pixel importance, typically calculated based on gradients or contrast. Initially, the algorithm calculates the energy of each pixel in the image. Then, it identifies the lowest-energy seam, which represents the path of pixels that contributes the least to the overall image content. This seam is removed or duplicated, depending on whether the image needs to be reduced or enlarged. This process is repeated iteratively until the desired image size is achieved

Guidance

• Calculate the energy of each pixel in the image based on gradients or other relevant measures
  • compute the cumulative minimum energy map, which represents the minimum energy path from the top to each pixel in the image
  • identify the seam with the lowest energy by tracing back from the bottom row of the cumulative energy map
  • remove or duplicate the identified seam from the image
  • update the energy values of the pixels affected by the removal or addition of the seam
  • repeat steps until the desired image size is reached

Tips

• consider parallelization techniques for faster processing, especially for large images
• experiment with different energy functions and seam removal strategies to achieve desired resizing results
• handle boundary cases carefully to ensure seamless resizing without artifacts

Practice

Practice

seam_carving(image, new_width, new_height):
  while image.width > new_width:
    energy_map = calculate_energy_map(image)
    cumulative_energy_map = calculate_cumulative_energy_map(energy_map)
    seam = find_vertical_seam(cumulative_energy_map)
    image = remove_vertical_seam(image, seam)

  while image.height > new_height:
    energy_map = calculate_energy_map(image)
    cumulative_energy_map = calculate_cumulative_energy_map(energy_map)
    seam = find_horizontal_seam(cumulative_energy_map)
    image = remove_horizontal_seam(image, seam)

  return image

remove_vertical_seam(image, seam):
  new_image = create_new_image(image.width - 1, image.height)
  for row from 0 to image.height:
    for col from 0 to image.width:
      if col < seam[row]:
        new_image[row][col] = image[row][col]
      else if col > seam[row]:
        new_image[row][col - 1] = image[row][col]
  return new_image

remove_horizontal_seam(image, seam):
  new_image = create_new_image(image.width, image.height - 1)
  for col from 0 to image.width:
    for row from 0 to image.height:
      if row < seam[col]:
        new_image[row][col] = image[row][col]
      else if row > seam[col]:
        new_image[row - 1][col] = image[row][col]
  return new_image

Solution

package main

import (
    "image"
    "image/color"
    "image/jpeg"
    "os"
)

type energyMatrix [][]float64

func computeEnergy(img image.Image) energyMatrix {
    bounds := img.Bounds()
    width, height := bounds.Max.X, bounds.Max.Y

    energy := make(energyMatrix, height)
    for y := range energy {
        energy[y] = make([]float64, width)
    }

    for y := 0; y < height; y++ {
        for x := 0; x < width; x++ {
            dx := getColorDelta(bounds, img, x-1, y, x+1, y)
            dy := getColorDelta(bounds, img, x, y-1, x, y+1)
            energy[y][x] = dx*dx + dy*dy
        }
    }

    return energy
}

func getColorDelta(bounds image.Rectangle, img image.Image, x1, y1, x2, y2 int) float64 {
    x1 = clamp(x1, 0, bounds.Max.X-1)
    y1 = clamp(y1, 0, bounds.Max.Y-1)
    x2 = clamp(x2, 0, bounds.Max.X-1)
    y2 = clamp(y2, 0, bounds.Max.Y-1)

    c1 := img.At(x1, y1)
    r1, g1, b1, _ := c1.RGBA()
    c2 := img.At(x2, y2)
    r2, g2, b2, _ := c2.RGBA()

    dr := float64(r1 - r2)
    dg := float64(g1 - g2)
    db := float64(b1 - b2)

    return (dr*dr + dg*dg + db*db) / 3.0 // taking average of the color differences
}

func clamp(x, min, max int) int {
    if x < min {
        return min
    }
    if x > max {
        return max
    }
    return x
}

func findVerticalSeam(energy energyMatrix) []int {
    height, width := len(energy), len(energy[0])

    distTo := make([][]float64, height)
    edgeTo := make([][]int, height)
    for i := range distTo {
        distTo[i] = make([]float64, width)
        edgeTo[i] = make([]int, width)
    }

    for y := range energy[0] {
        distTo[0][y] = energy[0][y]
    }

    for y := 1; y < height; y++ {
        for x := 0; x < width; x++ {
            minIdx := x
            minEnergy := distTo[y-1][x]
            if x > 0 && distTo[y-1][x-1] < minEnergy {
                minIdx = x - 1
                minEnergy = distTo[y-1][x-1]
            }
            if x < width-1 && distTo[y-1][x+1] < minEnergy {
                minIdx = x + 1
                minEnergy = distTo[y-1][x+1]
            }
            distTo[y][x] = energy[y][x] + minEnergy
            edgeTo[y][x] = minIdx
        }
    }

    minEnergyIdx := 0
    minEnergy := distTo[height-1][0]
    for x := 1; x < width; x++ {
        if distTo[height-1][x] < minEnergy {
            minEnergy = distTo[height-1][x]
            minEnergyIdx = x
        }
    }

    seam := make([]int, height)
    seam[height-1] = minEnergyIdx
    for y := height - 2; y >= 0; y-- {
        seam[y] = edgeTo[y+1][minEnergyIdx]
        minEnergyIdx = seam[y]
    }

    return seam
}

func removeVerticalSeam(img *image.RGBA, seam []int) {
    bounds := img.Bounds()
    height, width := bounds.Max.Y, bounds.Max.X-1

    for y := 0; y < height; y++ {
        copy(img.Pix[y*width+y:], img.Pix[y*width+seam[y]+1:])
    }

    img.Rect.Max.X -= 1
}

func resizeImage(img image.Image, newWidth int) image.Image {
    bounds := img.Bounds()
    width := bounds.Max.X

    for width > newWidth {
        energy := computeEnergy(img)
        seam := findVerticalSeam(energy)
        removeVerticalSeam(img.(*image.RGBA), seam)
        width--
    }

    return img
}

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;

public class SeamCarving {

  static class EnergyMatrix {
    double[][] energy;

    public EnergyMatrix(int height, int width) {
      energy = new double[height][width];
    }
  }

  public static BufferedImage resizeImage(BufferedImage image, int newWidth) {
    int width = image.getWidth();
    int height = image.getHeight();

    while (width > newWidth) {
      EnergyMatrix energyMatrix = computeEnergy(image);
      int[] seam = findVerticalSeam(energyMatrix);

      removeVerticalSeam(image, seam);

      width--;
    }

    return image;
  }

  public static EnergyMatrix computeEnergy(BufferedImage image) {
    int width = image.getWidth();
    int height = image.getHeight();
    EnergyMatrix energyMatrix = new EnergyMatrix(height, width);

    for (int y = 0; y < height; y++) {
      for (int x = 0; x < width; x++) {
        double dx = getColorDelta(image, x - 1, y, x + 1, y);
        double dy = getColorDelta(image, x, y - 1, x, y + 1);
        energyMatrix.energy[y][x] = dx * dx + dy * dy;
      }
    }

    return energyMatrix;
  }

  public static double getColorDelta(BufferedImage image, int x1, int y1, int x2, int y2) {
    x1 = clamp(x1, 0, image.getWidth() - 1);
    y1 = clamp(y1, 0, image.getHeight() - 1);
    x2 = clamp(x2, 0, image.getWidth() - 1);
    y2 = clamp(y2, 0, image.getHeight() - 1);

    Color c1 = new Color(image.getRGB(x1, y1));
    Color c2 = new Color(image.getRGB(x2, y2));

    double dr = c1.getRed() - c2.getRed();
    double dg = c1.getGreen() - c2.getGreen();
    double db = c1.getBlue() - c2.getBlue();

    return (dr * dr + dg * dg + db * db) / 3.0; // Taking average of the color differences
  }

  public static int clamp(int x, int min, int max) {
    return Math.min(Math.max(x, min), max);
  }

  public static int[] findVerticalSeam(EnergyMatrix energyMatrix) {
    int height = energyMatrix.energy.length;
    int width = energyMatrix.energy[0].length;

    double[][] distTo = new double[height][width];
    int[][] edgeTo = new int[height][width];

    for (int y = 0; y < height; y++) {
      for (int x = 0; x < width; x++) {
        distTo[y][x] = y == 0 ? energyMatrix.energy[y][x] : Double.MAX_VALUE;
      }
    }

    for (int y = 0; y < height - 1; y++) {
      for (int x = 0; x < width; x++) {
        if (x > 0 && distTo[y + 1][x - 1] > distTo[y][x] + energyMatrix.energy[y + 1][x - 1]) {
          distTo[y + 1][x - 1] = distTo[y][x] + energyMatrix.energy[y + 1][x - 1];
          edgeTo[y + 1][x - 1] = x;
        }
        if (distTo[y + 1][x] > distTo[y][x] + energyMatrix.energy[y + 1][x]) {
          distTo[y + 1][x] = distTo[y][x] + energyMatrix.energy[y + 1][x];
          edgeTo[y + 1][x] = x;
        }
        if (x < width - 1 && distTo[y + 1][x + 1] > distTo[y][x] + energyMatrix.energy[y + 1][x + 1]) {
          distTo[y + 1][x + 1] = distTo[y][x] + energyMatrix.energy[y + 1][x + 1];
          edgeTo[y + 1][x + 1] = x;
        }
      }
    }

    int minEnergyIdx = 0;
    double minEnergy = distTo[height - 1][0];
    for (int x = 1; x < width; x++) {
      if (distTo[height - 1][x] < minEnergy) {
        minEnergy = distTo[height - 1][x];
        minEnergyIdx = x;
      }
    }

    int[] seam = new int[height];
    seam[height - 1] = minEnergyIdx;
    for (int y = height - 2; y >= 0; y--) {
      seam[y] = edgeTo[y + 1][minEnergyIdx];
      minEnergyIdx = seam[y];
    }

    return seam;
  }

  public static void removeVerticalSeam(BufferedImage image, int[] seam) {
    int width = image.getWidth();
    int height = image.getHeight();

    for (int y = 0; y < height; y++) {
      System.arraycopy(image.getRGB(seam[y] + 1, y, width - seam[y] - 1, 1, image.getRGB(seam[y], y, 1, 1),
          0, width - seam[y] - 1);
    }
    image.getRaster().setWidth(width - 1);
  }
}

const fs = require("fs");
const { createCanvas, loadImage } = require("canvas");

function getColorDelta(imgData, width, x1, y1, x2, y2) {
  x1 = clamp(x1, 0, width - 1);
  y1 = clamp(y1, 0, imgData.height - 1);
  x2 = clamp(x2, 0, width - 1);
  y2 = clamp(y2, 0, imgData.height - 1);

  const idx1 = (y1 * width + x1) * 4;
  const idx2 = (y2 * width + x2) * 4;

  const dr = imgData.data[idx1] - imgData.data[idx2];
  const dg = imgData.data[idx1 + 1] - imgData.data[idx2 + 1];
  const db = imgData.data[idx1 + 2] - imgData.data[idx2 + 2];

  return (dr * dr + dg * dg + db * db) / 3.0; // Taking average of the color differences
}

function computeEnergy(imgData, width) {
  const energy = [];

  for (let y = 0; y < imgData.height; y++) {
    energy.push([]);
    for (let x = 0; x < width; x++) {
      const dx = getColorDelta(imgData, width, x - 1, y, x + 1, y);
      const dy = getColorDelta(imgData, width, x, y - 1, x, y + 1);
      energy[y].push(dx * dx + dy * dy);
    }
  }

  return energy;
}

function findVerticalSeam(energy) {
  const height = energy.length;
  const width = energy[0].length;

  const distTo = new Array(height)
    .fill(null)
    .map(() => new Array(width).fill(0));
  const edgeTo = new Array(height)
    .fill(null)
    .map(() => new Array(width).fill(0));

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      distTo[y][x] = y === 0 ? energy[y][x] : Infinity;
    }
  }

  for (let y = 0; y < height - 1; y++) {
    for (let x = 0; x < width; x++) {
      if (x > 0 && distTo[y + 1][x - 1] > distTo[y][x] + energy[y + 1][x - 1]) {
        distTo[y + 1][x - 1] = distTo[y][x] + energy[y + 1][x - 1];
        edgeTo[y + 1][x - 1] = x;
      }
      if (distTo[y + 1][x] > distTo[y][x] + energy[y + 1][x]) {
        distTo[y + 1][x] = distTo[y][x] + energy[y + 1][x];
        edgeTo[y + 1][x] = x;
      }
      if (
        x < width - 1 &&
        distTo[y + 1][x + 1] > distTo[y][x] + energy[y + 1][x + 1]
      ) {
        distTo[y + 1][x + 1] = distTo[y][x] + energy[y + 1][x + 1];
        edgeTo[y + 1][x + 1] = x;
      }
    }
  }

  let minEnergyIdx = 0;
  let minEnergy = distTo[height - 1][0];
  for (let x = 1; x < width; x++) {
    if (distTo[height - 1][x] < minEnergy) {
      minEnergy = distTo[height - 1][x];
      minEnergyIdx = x;
    }
  }

  const seam = new Array(height).fill(0);
  seam[height - 1] = minEnergyIdx;
  for (let y = height - 2; y >= 0; y--) {
    seam[y] = edgeTo[y + 1][minEnergyIdx];
    minEnergyIdx = seam[y];
  }

  return seam;
}

function removeVerticalSeam(imageData, seam, width) {
  const height = imageData.height;

  for (let y = 0; y < height; y++) {
    const idx = (y * width + seam[y]) * 4;
    imageData.data.copyWithin(idx, idx + 4, idx + width * 4);
  }

  imageData.width = width;
}

function seamCarving(imagePath, outputPath, newWidth) {
  loadImage(imagePath)
    .then((image) => {
      const canvas = createCanvas(image.width, image.height);
      const ctx = canvas.getContext("2d");
      ctx.drawImage(image, 0, 0);
      const imageData = ctx.getImageData(0, 0, image.width, image.height);

      while (image.width > newWidth) {
        const energy = computeEnergy(imageData, image.width);
        const seam = findVerticalSeam(energy);
        removeVerticalSeam(imageData, seam, image.width - 1);
      }

      canvas.width = imageData.width;
      canvas.height = imageData.height;
      const newCtx = canvas.getContext("2d");
      newCtx.putImageData(imageData, 0, 0);

      const out = fs.createWriteStream(outputPath);
      const stream = canvas.createJPEGStream();
      stream.pipe(out);
      out.on("finish", () => console.log("Image resized successfully!"));
    })
    .catch((err) => console.error(err));
}

import java.awt.Color
import java.awt.image.BufferedImage
import java.io.File
import javax.imageio.ImageIO

class EnergyMatrix(val energy: Array<DoubleArray>)

fun resizeImage(image: BufferedImage, newWidth: Int): BufferedImage {
    var img = image
    var width = img.width
    var height = img.height

    while (width > newWidth) {
        val energyMatrix = computeEnergy(img)
        val seam = findVerticalSeam(energyMatrix)
        img = removeVerticalSeam(img, seam)
        width--
    }

    return img
}

fun computeEnergy(image: BufferedImage): EnergyMatrix {
    val width = image.width
    val height = image.height
    val energy = Array(height) { DoubleArray(width) }

    for (y in 0 until height) {
        for (x in 0 until width) {
            val dx = getColorDelta(image, x - 1, y, x + 1, y)
            val dy = getColorDelta(image, x, y - 1, x, y + 1)
            energy[y][x] = dx * dx + dy * dy
        }
    }

    return EnergyMatrix(energy)
}

fun getColorDelta(image: BufferedImage, x1: Int, y1: Int, x2: Int, y2: Int): Double {
    val x1Clamped = x1.coerceIn(0 until image.width)
    val y1Clamped = y1.coerceIn(0 until image.height)
    val x2Clamped = x2.coerceIn(0 until image.width)
    val y2Clamped = y2.coerceIn(0 until image.height)

    val c1 = Color(image.getRGB(x1Clamped, y1Clamped))
    val c2 = Color(image.getRGB(x2Clamped, y2Clamped))

    val dr = c1.red - c2.red
    val dg = c1.green - c2.green
    val db = c1.blue - c2.blue

    return (dr * dr + dg * dg + db * db) / 3.0 // Taking average of the color differences
}

fun findVerticalSeam(energyMatrix: EnergyMatrix): IntArray {
    val height = energyMatrix.energy.size
    val width = energyMatrix.energy[0].size

    val distTo = Array(height) { DoubleArray(width) }
    val edgeTo = Array(height) { IntArray(width) }

    for (y in 0 until height) {
        for (x in 0 until width) {
            distTo[y][x] = if (y == 0) energyMatrix.energy[y][x] else Double.POSITIVE_INFINITY
        }
    }

    for (y in 0 until height - 1) {
        for (x in 0 until width) {
            if (x > 0 && distTo[y + 1][x - 1] > distTo[y][x] + energyMatrix.energy[y + 1][x - 1]) {
                distTo[y + 1][x - 1] = distTo[y][x] + energyMatrix.energy[y + 1][x - 1]
                edgeTo[y + 1][x - 1] = x
            }
            if (distTo[y + 1][x] > distTo[y][x] + energyMatrix.energy[y + 1][x]) {
                distTo[y + 1][x] = distTo[y][x] + energyMatrix.energy[y + 1][x]
                edgeTo[y + 1][x] = x
            }
            if (x < width - 1 && distTo[y + 1][x + 1] > distTo[y][x] + energyMatrix.energy[y + 1][x + 1]) {
                distTo[y + 1][x + 1] = distTo[y][x] + energyMatrix.energy[y + 1][x + 1]
                edgeTo[y + 1][x + 1] = x
            }
        }
    }

    var minEnergyIdx = 0
    var minEnergy = distTo[height - 1][0]
    for (x in 1 until width) {
        if (distTo[height - 1][x] < minEnergy) {
            minEnergy = distTo[height - 1][x]
            minEnergyIdx = x
        }
    }

    val seam = IntArray(height)
    seam[height - 1] = minEnergyIdx
    for (y in height - 2 downTo 0) {
        seam[y] = edgeTo[y + 1][minEnergyIdx]
        minEnergyIdx = seam[y]
    }

    return seam
}

fun removeVerticalSeam(image: BufferedImage, seam: IntArray): BufferedImage {
    val width = image.width
    val height = image.height
    val resizedImage = BufferedImage(width - 1, height, BufferedImage.TYPE_INT_RGB)

    for (y in 0 until height) {
        var destIndex = 0
        for (x in 0 until width) {
            if (x != seam[y]) {
                resizedImage.setRGB(destIndex++, y, image.getRGB(x, y))
            }
        }
    }

    return resizedImage
}

import numpy as np
from PIL import Image

def compute_energy(image):
    grayscale_image = image.convert("L")
    grayscale_array = np.array(grayscale_image)

    sobel_x = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]])
    sobel_y = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]])

    dx = signal.convolve2d(grayscale_array, sobel_x, mode="same", boundary="symm")
    dy = signal.convolve2d(grayscale_array, sobel_y, mode="same", boundary="symm")

    energy = np.sqrt(dx**2 + dy**2)
    return energy

def find_vertical_seam(energy):
    height, width = energy.shape
    cumulative_energy = energy.copy()

    for i in range(1, height):
        for j in range(width):
            if j == 0:
                cumulative_energy[i, j] += min(cumulative_energy[i-1, j], cumulative_energy[i-1, j+1])
            elif j == width - 1:
                cumulative_energy[i, j] += min(cumulative_energy[i-1, j-1], cumulative_energy[i-1, j])
            else:
                cumulative_energy[i, j] += min(cumulative_energy[i-1, j-1], cumulative_energy[i-1, j], cumulative_energy[i-1, j+1])

    seam = []
    j = np.argmin(cumulative_energy[-1])
    seam.append(j)

    for i in range(height - 2, -1, -1):
        if j == 0:
            j = np.argmin(cumulative_energy[i, j:j+2])
        elif j == width - 1:
            j = np.argmin(cumulative_energy[i, j-1:j+1]) + j - 1
        else:
            j = np.argmin(cumulative_energy[i, j-1:j+2]) + j - 1
        seam.append(j)

    seam.reverse()
    return seam

def remove_vertical_seam(image, seam):
    height, width = image.shape[:2]
    new_image = np.zeros((height, width - 1, 3), dtype=np.uint8)

    for i in range(height):
        j = seam[i]
        new_image[i, :, 0] = np.delete(image[i, :, 0], j)
        new_image[i, :, 1] = np.delete(image[i, :, 1], j)
        new_image[i, :, 2] = np.delete(image[i, :, 2], j)

    return new_image

def seam_carving(input_image_path, output_image_path, new_width):
    image = np.array(Image.open(input_image_path))

    for _ in range(image.shape[1] - new_width):
        energy = compute_energy(Image.fromarray(image))
        seam = find_vertical_seam(energy)
        image = remove_vertical_seam(image, seam)

    Image.fromarray(image).save(output_image_path)
    print("Image resized successfully!")

use image::{GenericImageView, DynamicImage, ImageBuffer, Rgba};
use std::cmp;

fn compute_energy(image: &ImageBuffer<Rgba<u8>, Vec<u8>>) -> ImageBuffer<Rgba<u8>, Vec<u8>> {
    let width = image.width() as usize;
    let height = image.height() as usize;

    let mut energy = ImageBuffer::new(width as u32, height as u32);

    for y in 0..height {
        for x in 0..width {
            let dx = get_color_delta(image, x.saturating_sub(1), y, x.saturating_add(1), y);
            let dy = get_color_delta(image, x, y.saturating_sub(1), x, y.saturating_add(1));
            let energy_val = (dx * dx + dy * dy).sqrt() as u8;
            energy.put_pixel(x as u32, y as u32, Rgba([energy_val, energy_val, energy_val, 255]));
        }
    }

    energy
}

fn get_color_delta(image: &ImageBuffer<Rgba<u8>, Vec<u8>>, x1: usize, y1: usize, x2: usize, y2: usize) -> f64 {
    let x1_clamped = cmp::min(cmp::max(x1, 0), image.width() as usize - 1);
    let y1_clamped = cmp::min(cmp::max(y1, 0), image.height() as usize - 1);
    let x2_clamped = cmp::min(cmp::max(x2, 0), image.width() as usize - 1);
    let y2_clamped = cmp::min(cmp::max(y2, 0), image.height() as usize - 1);

    let c1 = image.get_pixel(x1_clamped as u32, y1_clamped as u32);
    let c2 = image.get_pixel(x2_clamped as u32, y2_clamped as u32);

    let dr = (c1[0] as f64 - c2[0] as f64).powi(2);
    let dg = (c1[1] as f64 - c2[1] as f64).powi(2);
    let db = (c1[2] as f64 - c2[2] as f64).powi(2);

    (dr + dg + db) / 3.0
}

fn find_vertical_seam(energy: &ImageBuffer<Rgba<u8>, Vec<u8>>) -> Vec<usize> {
    let width = energy.width() as usize;
    let height = energy.height() as usize;
    let mut dist_to = vec![vec![0.0; width]; height];
    let mut edge_to = vec![vec![0; width]; height];

    for y in 0..height {
        for x in 0..width {
            dist_to[y][x] = if y == 0 {
                energy.get_pixel(x as u32, y as u32)[0] as f64
            } else {
                std::f64::INFINITY
            };
        }
    }

    for y in 0..height - 1 {
        for x in 0..width {
            if x > 0 && dist_to[y + 1][x - 1] > dist_to[y][x] + energy.get_pixel(x as u32, (y + 1) as u32)[0] as f64 {
                dist_to[y + 1][x - 1] = dist_to[y][x] + energy.get_pixel(x as u32, (y + 1) as u32)[0] as f64;
                edge_to[y + 1][x - 1] = x;
            }
            if dist_to[y + 1][x] > dist_to[y][x] + energy.get_pixel(x as u32, (y + 1) as u32)[0] as f64 {
                dist_to[y + 1][x] = dist_to[y][x] + energy.get_pixel(x as u32, (y + 1) as u32)[0] as f64;
                edge_to[y + 1][x] = x;
            }
            if x < width - 1 && dist_to[y + 1][x + 1] > dist_to[y][x] + energy.get_pixel(x as u32, (y + 1) as u32)[0] as f64 {
                dist_to[y + 1][x + 1] = dist_to[y][x] + energy.get_pixel(x as u32, (y + 1) as u32)[0] as f64;
                edge_to[y + 1][x + 1] = x;
            }
        }
    }

    let mut min_energy_idx = 0;
    let mut min_energy = dist_to[height - 1][0];
    for x in 1..width {
        if dist_to[height - 1][x] < min_energy {
            min_energy = dist_to[height - 1][x];
            min_energy_idx = x;
        }
    }

    let mut seam = Vec::with_capacity(height);
    seam.push(min_energy_idx);

    for y in (0..height - 1).rev() {
        min_energy_idx = edge_to[y + 1][min_energy_idx];
        seam.push(min_energy_idx);
    }

    seam.reverse();
    seam
}

fn remove_vertical_seam(image: &mut ImageBuffer<Rgba<u8>, Vec<u8>>, seam: &[usize]) {
    let height = image.height() as usize;
    let width = image.width() as usize;
    for y in 0..height {
        let mut x = seam[y];
        while x < width - 1 {
            image.put_pixel(x as u32, y as u32, *image.get_pixel((x + 1) as u32, y as u32));
            x += 1;
        }
    }
    image.resize(width as u32 - 1, height as u32, image::imageops::FilterType::Lanczos3);
}

import { createCanvas, ImageData, loadImage } from "canvas";

function getColorDelta(
  imageData: ImageData,
  width: number,
  x1: number,
  y1: number,
  x2: number,
  y2: number,
): number {
  x1 = Math.min(Math.max(x1, 0), width - 1);
  y1 = Math.min(Math.max(y1, 0), imageData.height - 1);
  x2 = Math.min(Math.max(x2, 0), width - 1);
  y2 = Math.min(Math.max(y2, 0), imageData.height - 1);

  const idx1 = (y1 * width + x1) * 4;
  const idx2 = (y2 * width + x2) * 4;

  const dr = imageData.data[idx1] - imageData.data[idx2];
  const dg = imageData.data[idx1 + 1] - imageData.data[idx2 + 1];
  const db = imageData.data[idx1 + 2] - imageData.data[idx2 + 2];

  return (dr * dr + dg * dg + db * db) / 3.0; // Taking average of the color differences
}

function computeEnergy(imageData: ImageData, width: number): number[][] {
  const energy: number[][] = [];

  for (let y = 0; y < imageData.height; y++) {
    energy.push([]);
    for (let x = 0; x < width; x++) {
      const dx = getColorDelta(imageData, width, x - 1, y, x + 1, y);
      const dy = getColorDelta(imageData, width, x, y - 1, x, y + 1);
      energy[y].push(dx * dx + dy * dy);
    }
  }

  return energy;
}

function findVerticalSeam(energy: number[][]): number[] {
  const height = energy.length;
  const width = energy[0].length;

  const distTo: number[][] = Array.from({ length: height }, () =>
    Array(width).fill(0),
  );
  const edgeTo: number[][] = Array.from({ length: height }, () =>
    Array(width).fill(0),
  );

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      distTo[y][x] = y === 0 ? energy[y][x] : Infinity;
    }
  }

  for (let y = 0; y < height - 1; y++) {
    for (let x = 0; x < width; x++) {
      if (x > 0 && distTo[y + 1][x - 1] > distTo[y][x] + energy[y + 1][x - 1]) {
        distTo[y + 1][x - 1] = distTo[y][x] + energy[y + 1][x - 1];
        edgeTo[y + 1][x - 1] = x;
      }
      if (distTo[y + 1][x] > distTo[y][x] + energy[y + 1][x]) {
        distTo[y + 1][x] = distTo[y][x] + energy[y + 1][x];
        edgeTo[y + 1][x] = x;
      }
      if (
        x < width - 1 &&
        distTo[y + 1][x + 1] > distTo[y][x] + energy[y + 1][x + 1]
      ) {
        distTo[y + 1][x + 1] = distTo[y][x] + energy[y + 1][x + 1];
        edgeTo[y + 1][x + 1] = x;
      }
    }
  }

  let minEnergyIdx = 0;
  let minEnergy = distTo[height - 1][0];
  for (let x = 1; x < width; x++) {
    if (distTo[height - 1][x] < minEnergy) {
      minEnergy = distTo[height - 1][x];
      minEnergyIdx = x;
    }
  }

  const seam: number[] = [];
  seam[height - 1] = minEnergyIdx;
  for (let y = height - 2; y >= 0; y--) {
    seam[y] = edgeTo[y + 1][minEnergyIdx];
    minEnergyIdx = seam[y];
  }

  return seam;
}

function removeVerticalSeam(imageData: ImageData, seam: number[]): ImageData {
  const width = imageData.width;
  const height = imageData.height;
  const newImageData = new ImageData(width - 1, height);

  for (let y = 0; y < height; y++) {
    let destIndex = 0;
    for (let x = 0; x < width; x++) {
      if (x !== seam[y]) {
        newImageData.data[destIndex++] = imageData.data[y * width * 4 + x * 4];
        newImageData.data[destIndex++] =
          imageData.data[y * width * 4 + x * 4 + 1];
        newImageData.data[destIndex++] =
          imageData.data[y * width * 4 + x * 4 + 2];
        newImageData.data[destIndex++] =
          imageData.data[y * width * 4 + x * 4 + 3];
      }
    }
  }

  return newImageData;
}

async function seamCarving(
  inputImagePath: string,
  outputImagePath: string,
  newWidth: number,
) {
  const image = await loadImage(inputImagePath);
  const canvas = createCanvas(image.width, image.height);
  const ctx = canvas.getContext("2d");
  ctx.drawImage(image, 0, 0);
  const imageData = ctx.getImageData(0, 0, image.width, image.height);

  while (imageData.width > newWidth) {
    const energy = computeEnergy(imageData, imageData.width);
    const seam = findVerticalSeam(energy);
    imageData.width -= 1;
    imageData.data = removeVerticalSeam(imageData, seam).data;
  }

  canvas.width = imageData.width;
  const newCtx = canvas.getContext("2d");
  newCtx.putImageData(imageData, 0, 0);

  const buffer = canvas.toBuffer("image/jpeg");
  require("fs").writeFileSync(outputImagePath, buffer);
  console.log("Image resized successfully!");
}