# Seam Carving (Presentation & Workshop)

Seam Carving is the task to remove empty room in a image. Have you ever wished to do ‘Content Aware Scaling’? Learn it now!
presentation
jvm
kotlin
workshop
Author

Hampus Londögård

Published

May 17, 2021

This is from a presentation I did last week (12th of May 2021). Notebook just under the slides!
Please note that this requires the Kotlin kernel to run as it’s Kotlin and not Python.

@file:DependsOn("org.boofcv:boofcv-core:0.37")
@file:DependsOn("org.boofcv:boofcv-kotlin:0.37")
%use lib-ext
import boofcv.abst.filter.derivative.ImageGradient_SB
import boofcv.kotlin.*
import boofcv.factory.feature.detect.edge.FactoryEdgeDetectors
import boofcv.io.image.ConvertBufferedImage
import boofcv.struct.image.*
import boofcv.io.image.UtilImageIO
import java.io.*
import javax.imageio.ImageIO
import java.nio.file.*
import java.awt.image.BufferedImage
val sobel: ImageGradient_SB.Sobel<GrayF32, GrayF32> by lazy {
}

fun BufferedImage.toByteArray(format: String): ByteArray {
val stream = ByteArrayOutputStream()
ImageIO.write(this, format, stream)
return stream.toByteArray()
}
fun FloatArray.removeIndices(toRemove: Set<Int>): FloatArray {
val result = FloatArray(size - toRemove.size)
var targetIndex = 0
for (sourceIndex in indices) {
if (sourceIndex !in toRemove) result[targetIndex++] = this[sourceIndex]
}
return result
}
fun ByteArray.removeIndices(toRemove: Set<Int>): ByteArray {
val result = ByteArray(size - toRemove.size)
var targetIndex = 0
for (sourceIndex in indices) {
if (sourceIndex !in toRemove) result[targetIndex++] = this[sourceIndex]
}
return result
}

Let’s load our first image using BoofCV. It’s simply done using UtilImageIO.loadImage("path/to/file").
The conversion to show an image in a notebook is a little awkward.

But I talked to Jetbrains through Slack - had a response & patch up within 20 minutes (waiting for the new release right now…) which simplifies this!

val img = UtilImageIO.loadImage("dali.jpg")
Image(img.toByteArray("jpg"), "jpg").withWidth("45%")

## Sobel Filters

Sobel is a very simple Edge Detector that runs the gradient in two directions

(18.S191 MIT Fall 2020 | Grant Sanderson) By applying this filter

val grayImg = img.asGrayF32()
Image(grayImg.asBufferedImage().toByteArray("jpg"), "jpg").withWidth("45%")
val grayDY = GrayF32(1,1)
val grayDX = GrayF32(1,1)
sobel.process(grayImg, grayDX, grayDY)
DISPLAY(Image(grayDY.asBufferedImage().toByteArray("jpg"), "jpg").withWidth(500))
Image(grayDX.asBufferedImage().toByteArray("jpg"), "jpg").withWidth(500)

Now we need to combine these two into one image, that’s done by taking the intensity, e.g.

$$\sqrt{D_x^2 + D_y^2}$$

Also called l2-norm, euclidean-norm or square-norm.

Where $$D_x$$ is the gradient in X direction (applying sobel-filter).

Luckily this exists in BoofCV (and most libraries), in the way of GGradientToEdgeFeatures.intensityE(grayDX, grayDY, intensity)

val intensity = GrayF32(1,1)
Image(intensity.asBufferedImage().toByteArray("jpg"), "jpg").withWidth("75%")

With the edges at hands (white) we can go ahead and try to create a graph of total intensity.
It is this graph we’ll use to traverse later, to find the cheapest path.

So how would we do this?
Trying all paths would prove expensive, but if we traverse the reverse we can speed things up by being clever.

Let’s take a look at how a subimage of the image looks.

intensity.subimage(10,10,20,20).printInt()
  5   9   2   7   6   6   4   4   5   6
3   7   4   7   4   3   3   7   3   5
9   7   5   6   6   1   5   5   3   6
10   6   7   4   4   4   5   4   6   3
7   7   6   4   5   2   5   8   5   2
4   3   2   2   3   1   3  11   3   1
3   1   7   6   3   3   4   9   4   2
3   5   4   4   7   7   1   6   6   5
10   6   1   4   3   8   4   6   7  10
4   7   3   3   4   5   6   7   7  10 

And now we’ll take a look at how this traversal works. These screens are taken from (18.S191 MIT Fall 2020 | Grant Sanderson) which is really good by the way.

val tmp = intensity.clone()
val width = tmp.width
val height = tmp.height

(height - 2 downTo 0).forEach { y ->
(0 until width).forEach { x ->
val range = (max(0, x-1)..min(x+1, width - 1))
val minimum = range.minOf { x2 -> tmp[x2, y + 1] }
tmp[x,y] += minimum
}
}

val max = (tmp.data.maxOrNull() ?: 0f) / 255f
tmp.data.forEachIndexed { i, _ -> tmp.data[i] /= max }
Image(tmp.asBufferedImage().toByteArray("jpg"), "jpg").withWidth("50%")

Through this image we can find the cheapest path by traversing the darkest path, where white is “expensive”.

This is simply done by taking the cheapest value at each row, forming a line. We’ve precalculated the whole matrix making this a walk in the park.

var previousX = 0 //int[]
val cheapestPath = IntArray(height) { y ->
val range = when(y) {
0 -> 0 until width
else -> (max(previousX - 1, 0)..min(previousX + 1, width - 1))
}
previousX = range.minByOrNull { x -> tmp[x,y] } ?: previousX

previousX + (y * width)
}
cheapestPath.take(10)
[1022, 2222, 3421, 4621, 5821, 7022, 8223, 9422, 10622, 11821]
val WHITE = 255f
cheapestPath.forEach { i -> grayImg.data[i] = WHITE }
Image(grayImg.asBufferedImage().toByteArray("jpg"), "jpg").withWidth("75%")
fun cheapestPath(image: GrayF32): Set<Int> {
val widthRange = 0 until image.width
for (y in image.height - 2 downTo 0) {
for (x in widthRange) {
val range = when (x) {
0 -> 0..1
widthRange.last -> x-1..x
else -> x-1..x+1
}
val cheapestPath = range.minOf { i -> image[i, y + 1] }

image[x, y] = image[x, y] + cheapestPath
}
}

var previousBest = 0
return IntArray(image.height) { i ->
val range =
if (i == 0) 0 until image.width
else max(previousBest - 1, 0)..min(previousBest + 1, image.width - 1)
previousBest = range.minByOrNull { j -> image.get(j, i) } ?: 0

previousBest + (i * image.width) // Raw Index
}.toSet()
}

fun seamCarve(img: GrayF32): Set<Int> {
sobel.process(img, grayDX, grayDY)
return cheapestPath(intensity)
}
val grayImg = img.asGrayF32()
(0..200).forEach { i ->
val indices = seamCarve(grayImg)

if (i % 25 == 0) {
indices.forEach { j -> grayImg.data[j] = WHITE }
UtilImageIO.saveImage(grayImg.asBufferedImage(), "step_\$i.jpg")
}
grayImg.apply {
setData(grayImg.data.removeIndices(indices))
reshape(width - 1, height)
}
}
DISPLAY(Image("step_0.jpg"))
Image("step_200.jpg")