pub fn find_vertical_seam<P>(image: &Image<P>) -> VerticalSeam
where
    P: Pixel<Subpixel = u8> + WithChannel<u16> + WithChannel<i16>,
    <P as WithChannel<u16>>::Pixel: HasBlack,
{
    let (width, height) = image.dimensions();
    assert!(
        image.width() >= 2,
        "Cannot find seams if image width is < 2"
    );

    let mut gradients = gradients(
        image,
        kernel::SOBEL_HORIZONTAL_3X3,
        kernel::SOBEL_VERTICAL_3X3,
        |p| {
            let gradient_sum: u16 = p.channels().iter().sum();
            let gradient_mean: u16 = gradient_sum / P::CHANNEL_COUNT as u16;
            Luma([gradient_mean as u32])
        },
    );

    // Find the least energy path through the gradient image.
    for y in 1..height {
        for x in 0..width {
            set_path_energy(&mut gradients, x, y);
        }
    }

    // Retrace our steps to find the vertical seam.
    let mut min_x = 0;
    let mut min_energy = gradients.get_pixel(0, height - 1)[0];

    for x in 1..width {
        let c = gradients.get_pixel(x, height - 1)[0];
        if c < min_energy {
            min_x = x;
            min_energy = c;
        }
    }

    let mut seam = Vec::with_capacity(height as usize);

    seam.push(min_x);

    let mut last_x = min_x;

    for y in (1..height).rev() {
        let above = gradients.get_pixel(last_x, y - 1)[0];
        if last_x > 0 {
            let left = gradients.get_pixel(last_x - 1, y - 1)[0];
            if left < above {
                min_x = last_x - 1;
                min_energy = left;
            }
        }
        if last_x < width - 1 {
            let right = gradients.get_pixel(last_x + 1, y - 1)[0];
            if right < min_energy {
                min_x = last_x + 1;
                min_energy = right;
            }
        }

        last_x = min_x;
        seam.push(min_x);
    }

    VerticalSeam(seam)
}
Computes an 8-connected path from the bottom of the image to the top whose sum of
gradient magnitudes is minimal.
src/seam_carving.rs