Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams...
It's not besides the point at all. If you can reduce this linear-time algorithm to, say, amortized constant, then you'll handily beat parallelism.
After you remove a seam, you need to recompute the cones below every removed pixel -- which ends up being the cone below the topmost removed pixel (sadly, you can't just zip down the neighbors of the seam, but you can avoid expensive data moves with a 2d linked list). If the image is super wide, that gives you a speedup by approximately the aspect ratio. If it's square, you should be able to cut the runtime in half. If it's tall and skinny, neither this nor the author's approach are terribly helpful.
Because the seam is defined such that each pixel in the next row is within 1 column of the pixel in the preceding row, you can reuse all the calculations except for a pyramid shaped area around the last removed seam (in the worst case). However, that area is on the order of half the total number of pixels, so it doesn’t save _too_ much to reuse the other half.
> in the worst case
I wonder if typical data is more forgiving. If, for example, we cut an optimal seam down the column n=x, and the DP algorithm tells us that the best seams starting at (0,x-1) and at (0,x+1) are also column seams, the next iteration can happen in linear time in the number of rows. (Plus number of columns -- pessimistically -- if the next-optimal seam isn't "nearby".)
Basically, you're checking the things that crossed the old seam, and I'd guess that'd happen often enough, but I don't know how far the effects would typically spread. Maybe it would work worse in "sparse" images like blue sky, and better in "noisier" images like forests and crowds and dogs' fur.
I'm not sure how much cost that data-dependence would incur though. Might not be worthwhile.