Speeding up a pre-computed seam carving algorithm

Question

I'm writing a JS seam carving library. It works great, I can rescale a 1024x1024 image very cleanly in real time as fast as I can drag it around. It looks great! But in order to get that performance I need to pre-compute a lot of data and it takes about 10 seconds. I'm trying to remove this bottleneck and am looking for ideas here.

Seam carving works by removing the lowest energy "squiggly" line of pixels from an image. e.g. If you have a 10x4 image a horizontal seam might look like this:

........x.
.x.....x.x
x.xx..x...
....xx....

So if you resize it to 10x3 you remove all the 'X' pixels. The general idea is that the seams go around the things that look visually important to you, so instead of just normal scaling where everything gets squished, you're mostly removing things that look like whitespace, and the important elements in a picture are unaffected.

The process of calculating energy levels, removing them, and re-calculating is rather expensive, so I pre-compute it in node.js and generate a .seam file.

Each seam in the .seam file is basically: starting position, direction, direction, direction, direction, .... So for the above example you'd have:

starting position: 2
seam direction: -1 1 0 1 0 -1 -1 -1 1

This is quite compact and allows me to generate .seam files in ~60-120kb for a 1024x1024 image depending on settings.

Now, in order to get fast rendering I generate a 2D grids that represents the order in which pixels should be removed. So:

(figure A):

........1.
.1.....1.1
1.11..1...
....11....

contains 1 seam of info, then we can add a 2nd seam:

(figure B):

2...2....2
.222.2.22.
......2...

and when merged you get:

2...2...12
.122.2.1.1
1211..122.
....112...

For completeness we can add seams 3 & 4:

(figures C & D):

33.3..3...
..3.33.333

4444444444

and merge them all into:

(figure E):

2343243412
3122424141
1211331224
4434112333

You'll notice that the 2s aren't all connected in this merged version, because the merged version is based on the original pixel positions, whereas the seam is based on the pixel positions at the moment the seam is calculated which, for this 2nd seam, is a 10x3px image.

This allows the front-end renderer to basically just loop over all the pixels in an image and filter them against this grid by number of desired pixels to remove. It runs at 100fps on my computer, meaning that it's perfectly suitable for single resizes on most devices. yay!

Now the problem that I'm trying to solve:

The decoding step from seams that go -1 1 0 1 0 -1 -1 -1 1 to the pre-computed grid of which pixels to remove is slow. The basic reason for this is that whenever one seam is removed, all the seams from there forward get shifted.

The way I'm currently calculating the "shifting" is by splicing each pixel of a seam out of a 1,048,576 element array (for a 1024x1024 px image, where each index is x * height + y for horizontal seams) that stores the original pixel positions. It's veeerrrrrryyyyy slow running .splice a million times...

This seems like a weird leetcode problem, in that perhaps there's a data structure that would allow me to know "how many pixels above this one have already been excluded by a seam" so that I know the "normalized index". But... I can't figure it out, anything I can think of requires too many re-writes to make this any faster.

Or perhaps there might be a better way to encode the seam data, but using 1-2 bits per pixel of the seam is very efficient, and anything else I can come up with would make those files huge.

Thanks for taking the time to read this!

[edit and tl;dr] -- How do I efficiently merge figures A-D into figure E? Alternatively, any ideas that yield figure E efficiently, from any compressed format

Answer 1

If I understand correct your current algorithm is:

while there are pixels in Image:
  seam = get_seam(Image)
  save(seam)
  Image = remove_seam_from_image(Image, seam)

You then want to construct an array containing the numbers of each seam.

To do so, you could make a 1024x1024 array where each value is the index of that element of the array (y*width+x). Call this Indices.

A modified algorithm then gives you what you want

Let Indices have the dimensions of Image and be initialized to [0, len(Image)0
Let SeamNum have the dimensions of Image and be initialized to -1
seam_num = 0
while there are pixels in Image:
  seam = get_seam(Image)
  Image = remove_seam_from_image(Image, seam)
  Indices = remove_seam_from_image_and_write_seam_num(Indices, seam, SeamNum, seam_num)
  seam_num++

remove_seam_from_image_and_write_seam_num is conceptually identical to remove_seam_from_image except that as it walks seam to remove each pixel from Indices it writes seam_num to the location in SeamNum indicated by the pixel's value in Indices.

The output is the SeamNum array you're looking for.