Seam carving.

// Opaque RGB pixels in row order. No image decoder or encoder is required.
export type Raster = { width: number; height: number; pixels: number[] };
export type Seam = { columns: number[]; total: number; costs: number[][]; parents: number[][] };
const MAX_SIDE = 512;

function dimension(value: number): boolean {
	return Number.isInteger(value) && value >= 1 && value <= MAX_SIDE;
}
function validateImage(image: Raster): void {
	if (
		!dimension(image.width) ||
		!dimension(image.height) ||
		image.pixels.length !== image.width * image.height * 3
	) {
		throw new Error('Expected a nonempty RGB image, at most 512 × 512.');
	}
	for (const channel of image.pixels) {
		if (!Number.isInteger(channel) || channel < 0 || channel > 255)
			throw new Error('RGB channels must be integers from 0 to 255.');
	}
}
function validateGrid(grid: number[][]): void {
	if (!dimension(grid.length) || !dimension(grid[0]?.length))
		throw new Error('Expected a nonempty energy grid, at most 512 × 512.');
	for (const row of grid) {
		if (row.length !== grid[0].length) throw new Error('Energy rows must have equal width.');
		for (const value of row) {
			if (!Number.isInteger(value) || value < 0 || value > 1_000_000)
				throw new Error('Energy must be an integer from 0 to 1,000,000.');
		}
	}
}

export function energy(image: Raster): number[][] {
	validateImage(image);
	const { width, height, pixels } = image;
	return Array.from({ length: height }, (_, y) =>
		Array.from({ length: width }, (_, x) => {
			const left = (y * width + Math.max(0, x - 1)) * 3;
			const right = (y * width + Math.min(width - 1, x + 1)) * 3;
			const above = (Math.max(0, y - 1) * width + x) * 3;
			const below = (Math.min(height - 1, y + 1) * width + x) * 3;
			let value = 0;
			for (let channel = 0; channel < 3; channel++) {
				value += Math.abs(pixels[left + channel] - pixels[right + channel]);
				value += Math.abs(pixels[above + channel] - pixels[below + channel]);
			}
			return value;
		})
	);
}

export function findSeam(grid: number[][]): Seam {
	validateGrid(grid);
	const height = grid.length,
		width = grid[0].length;
	const costs = grid.map((row) => [...row]);
	const parents = grid.map((row) => row.map(() => -1));
	for (let y = 1; y < height; y++) {
		for (let x = 0; x < width; x++) {
			let best = Math.max(0, x - 1);
			for (let p = best + 1; p <= Math.min(width - 1, x + 1); p++) {
				if (costs[y - 1][p] < costs[y - 1][best]) best = p;
			}
			costs[y][x] += costs[y - 1][best];
			parents[y][x] = best;
		}
	}
	let end = 0;
	for (let x = 1; x < width; x++) {
		if (costs[height - 1][x] < costs[height - 1][end]) end = x;
	}
	const total = costs[height - 1][end];
	const columns = Array<number>(height);
	for (let y = height - 1; y >= 0; y--) {
		columns[y] = end;
		end = parents[y][end];
	}
	return { columns, total, costs, parents };
}

export function removeSeam(image: Raster, columns: number[]): Raster {
	validateImage(image);
	const { width, height, pixels } = image;
	if (width <= 1 || columns.length !== height)
		throw new Error('Removal needs width > 1 and one column per row.');
	for (let y = 0; y < height; y++) {
		const x = columns[y];
		if (
			!Number.isInteger(x) ||
			x < 0 ||
			x >= width ||
			(y > 0 && Math.abs(x - columns[y - 1]) > 1)
		) {
			throw new Error('Seam columns must be in bounds and connected.');
		}
	}
	const result: number[] = [];
	for (let y = 0; y < height; y++) {
		for (let x = 0; x < width; x++) {
			if (x === columns[y]) continue;
			const offset = (y * width + x) * 3;
			result.push(pixels[offset], pixels[offset + 1], pixels[offset + 2]);
		}
	}
	return { width: width - 1, height, pixels: result };
}

export function carve(image: Raster, targetWidth: number): Raster {
	validateImage(image);
	if (!Number.isInteger(targetWidth) || targetWidth < 1 || targetWidth > image.width) {
		throw new Error('Target width must be between 1 and the original width.');
	}
	let preview: Raster = { ...image, pixels: [...image.pixels] };
	while (preview.width > targetWidth) {
		const seam = findSeam(energy(preview));
		preview = removeSeam(preview, seam.columns);
	}
	return preview;
}

export function runExample(): void {
	// A tiny decoded image: each number becomes a grayscale RGB pixel.
	const values = [10, 10, 200, 10, 10, 200, 10, 10, 200];
	const original: Raster = { width: 3, height: 3, pixels: values.flatMap((v) => [v, v, v]) };
	const first = findSeam(energy(original));
	const preview = carve(original, 2);
	console.log(`seam: ${first.columns.join(',')}; energy: ${first.total}`);
	console.log(
		`preview: ${preview.width}x${preview.height}; original: ${original.width}x${original.height}`
	);
	// The editor displays the preview; the original remains available for another size.
}

runExample();

package main

import (
	"fmt"
	"strings"
)

type Raster struct {
	Width, Height int
	Pixels        []int
}
type Seam struct {
	Columns        []int
	Total          int
	Costs, Parents [][]int
}

func dimension(value int) bool { return value >= 1 && value <= 512 }
func validateImage(image Raster) error {
	if !dimension(image.Width) || !dimension(image.Height) || len(image.Pixels) != image.Width*image.Height*3 {
		return fmt.Errorf("expected a nonempty RGB image, at most 512 x 512")
	}
	for _, channel := range image.Pixels {
		if channel < 0 || channel > 255 {
			return fmt.Errorf("RGB channels must be integers from 0 to 255")
		}
	}
	return nil
}
func validateGrid(grid [][]int) error {
	if !dimension(len(grid)) || !dimension(len(grid[0])) {
		return fmt.Errorf("expected a nonempty energy grid, at most 512 x 512")
	}
	for _, row := range grid {
		if len(row) != len(grid[0]) {
			return fmt.Errorf("energy rows must have equal width")
		}
		for _, value := range row {
			if value < 0 || value > 1000000 {
				return fmt.Errorf("energy must be from 0 to 1,000,000")
			}
		}
	}
	return nil
}
func abs(value int) int {
	if value < 0 {
		return -value
	}
	return value
}

func Energy(image Raster) ([][]int, error) {
	if err := validateImage(image); err != nil {
		return nil, err
	}
	width, height, pixels := image.Width, image.Height, image.Pixels
	grid := make([][]int, height)
	for y := 0; y < height; y++ {
		grid[y] = make([]int, width)
		for x := 0; x < width; x++ {
			left := (y*width + max(0, x-1)) * 3
			right := (y*width + min(width-1, x+1)) * 3
			above := (max(0, y-1)*width + x) * 3
			below := (min(height-1, y+1)*width + x) * 3
			for channel := 0; channel < 3; channel++ {
				grid[y][x] += abs(pixels[left+channel] - pixels[right+channel])
				grid[y][x] += abs(pixels[above+channel] - pixels[below+channel])
			}
		}
	}
	return grid, nil
}


func FindSeam(grid [][]int) (Seam, error) {
	if err := validateGrid(grid); err != nil {
		return Seam{}, err
	}
	height, width := len(grid), len(grid[0])
	costs, parents := make([][]int, height), make([][]int, height)
	for y, row := range grid {
		costs[y] = append([]int(nil), row...)
		parents[y] = make([]int, width)
		for x := range parents[y] {
			parents[y][x] = -1
		}
	}
	for y := 1; y < height; y++ {
		for x := 0; x < width; x++ {
			best := max(0, x-1)
			for p := best + 1; p <= min(width-1, x+1); p++ {
				if costs[y-1][p] < costs[y-1][best] {
					best = p
				}
			}
			costs[y][x] += costs[y-1][best]
			parents[y][x] = best
		}
	}
	end := 0
	for x := 1; x < width; x++ {
		if costs[height-1][x] < costs[height-1][end] {
			end = x
		}
	}
	total := costs[height-1][end]
	columns := make([]int, height)
	for y := height - 1; y >= 0; y-- {
		columns[y] = end
		end = parents[y][end]
	}
	return Seam{columns, total, costs, parents}, nil
}


func RemoveSeam(image Raster, columns []int) (Raster, error) {
	if err := validateImage(image); err != nil {
		return Raster{}, err
	}
	width, height, pixels := image.Width, image.Height, image.Pixels
	if width <= 1 || len(columns) != height {
		return Raster{}, fmt.Errorf("removal needs width > 1 and one column per row")
	}
	for y, x := range columns {
		if x < 0 || x >= width || (y > 0 && abs(x-columns[y-1]) > 1) {
			return Raster{}, fmt.Errorf("seam columns must be in bounds and connected")
		}
	}
	result := make([]int, 0, (width-1)*height*3)
	for y := 0; y < height; y++ {
		for x := 0; x < width; x++ {
			if x == columns[y] {
				continue
			}
			offset := (y*width + x) * 3
			result = append(result, pixels[offset:offset+3]...)
		}
	}
	return Raster{width - 1, height, result}, nil
}


func Carve(image Raster, targetWidth int) (Raster, error) {
	if err := validateImage(image); err != nil {
		return Raster{}, err
	}
	if targetWidth < 1 || targetWidth > image.Width {
		return Raster{}, fmt.Errorf("target width must be between 1 and the original width")
	}
	preview := Raster{image.Width, image.Height, append([]int(nil), image.Pixels...)}
	for preview.Width > targetWidth {
		grid, err := Energy(preview)
		if err != nil {
			return Raster{}, err
		}
		seam, err := FindSeam(grid)
		if err != nil {
			return Raster{}, err
		}
		preview, err = RemoveSeam(preview, seam.Columns)
		if err != nil {
			return Raster{}, err
		}
	}
	return preview, nil
}


func runExample() error {
	values := []int{10, 10, 200, 10, 10, 200, 10, 10, 200}
	original := Raster{Width: 3, Height: 3}
	for _, value := range values {
		original.Pixels = append(original.Pixels, value, value, value)
	}
	grid, err := Energy(original)
	if err != nil {
		return err
	}
	first, err := FindSeam(grid)
	if err != nil {
		return err
	}
	preview, err := Carve(original, 2)
	if err != nil {
		return err
	}
	columns := make([]string, len(first.Columns))
	for y, x := range first.Columns {
		columns[y] = fmt.Sprint(x)
	}
	fmt.Printf("seam: %s; energy: %d\n", strings.Join(columns, ","), first.Total)
	fmt.Printf("preview: %dx%d; original: %dx%d\n", preview.Width, preview.Height, original.Width, original.Height)
	return nil
}

func main() {
	if err := runExample(); err != nil {
		panic(err)
	}
}