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):

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

@Richard -- The code isn't commented, and even though it's fairly clean (not perfect as I've been messing with different ways to do this) it would take a while to understand. I can post the unfinished github if you're interested, but it's almost certainly easier to understand the issue from the above description — , Sep 09 '21 at 16:15
code for the renderer: https://github.com/VoiceNGO/seams/blob/main/src/renderer.ts — , Sep 09 '21 at 16:45
It might help if you completed the example. I assume that the final merged output has the numbers 1 thru 4 in each column, and the only thing to determine is the final unsorted order for each column. Assuming that column unsorting can be done in O(nlogn) time, the best you can hope for is 1024*1024*10 operations. — user3386109, Sep 09 '21 at 16:46
@user3386109 -- Not necessarily. It doesn't actually make sense to compute 100% of the seams as scaling down below a certain size just produces garbage. The purpose of this is to allow an image to fit a container cleanly, so you may only generate 50% of the seams, as in the example. In this case, the internal array fills all the `.`'s with `Infinity`, so that they're never removed. But you could also fill them with 1->N ... — , Sep 09 '21 at 17:04
I'm basically trying to figure out how to get the column generation to anywhere close to `N log N` — , Sep 09 '21 at 17:12
Some thoughts on how to unsort a column. First represent a seam by a 1D array of row numbers. So figure A becomes `{2,1,2,2,3,3,2,1,0,1}` and figure B becomes `{0,1,1,1,0,1,2,1,1,0}`. Those arrays are easy to compute from the data in the `.seam` file. Then my half-baked idea is that you may be able to use an [interval tree](https://en.wikipedia.org/wiki/Interval_tree) (with non-overlapping intervals) to assist unsorting a column. — user3386109, Sep 09 '21 at 17:26
For each column, you'd start the tree by adding the position for the 1. When adding the 2, first search for an existing interval that contains its position. If no such interval exists, 2 is added as a new interval. Otherwise the existing interval is extended, with the 2 added at the end. Then the problem is merging intervals, and I'm not sure if that can be solved efficiently. — user3386109, Sep 09 '21 at 17:28
The fundamental problem with representing it as a 1D array of row numbers is that it makes the seam sizes unwieldy. Currently each pixel takes up 1 or 1.67 bits of data in a seam (depending on settings), and the seam files are 60-100kb for a 1024x1024 image. If I were to store the entire column numbers each pixel would take 10 bits in this example and the files would be 600kb-1MB for the same image. And if you're talking about computing them on the fly, I don't see how to do that efficiently, do you? — , Sep 09 '21 at 17:33
It's actually one seam file, but it's all good. It's only for short time and then the intermediary seams are gc'd. But I don't see how to get `{ 0, 2, 1, 1, 0, 1, 3, 2, 2, 0 }` for the 2nd seam efficiently here, or the 400th seam where the previously removed pixels are very random — , Sep 09 '21 at 17:42
Let me check if I understand this: you have the whole image, calculate a seam, remove that seam from the image, calculate a new seam, remove that seam, and so on until there's no image left. Your seams are defined by movement directions from a starting position and it's hard to work in reverse because the backwards transformation from a small image to the larger image it came from is non-unique? — Richard, Sep 10 '21 at 04:52
Also: what kind of RAM constrains do you have? (For instance, if you have 5GB of RAM the problem might become easier.) — Richard, Sep 10 '21 at 05:30

score 0 · Answer 1 · answered Sep 10 '21 at 06:11

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.

This unfortunately isn't compressible, which makes it unsuitable for this. I need a format that I can transmit to a browser, which is why I took the approach I did as the compressed format is 1 bit per pixel, or less depending on settings — , Sep 10 '21 at 16:03
@Mark: Noted. I'll see if I can think of something else. But I'd expect the data to be decently compressible, much more so than the original image. Do you have numbers on running it through gzip or similar? — Richard, Sep 10 '21 at 19:07
It’s nearly 100% random data as far as gzip is concerned, so by definition it’s not compressible ;) (1.24mb->1.22mb, fwiw) — , Sep 11 '21 at 08:03

Speeding up a pre-computed seam carving algorithm

1 Answers1