One thing that I always wondered is how Photoshop managed to make it so fast that you can resize in real-time. If n is the width or height of the image, then the dynamic programming part is O(n^2) and needs to be recomputed after every seam removed. Since every seam is a single pixel wide, resizing the image by a non-trivial amount (say half) is O(n^3). There are other papers that remove multiple seams at a time but the quality isn't as good. GPU acceleration perhaps?
Another thing I learned while testing seam carving extensively is that it works nicely in certain scenes/situations, but tends to break down most of the time. The two most common scenarios are: 1) lines that are off by the horizontal by more than a few degrees get cutoff 2) objects loose their proportions and even when the manipulation is not directly obvious, it tends to feel off (in the uncanny valley sense).
I expect some interesting work to use deep learning for content-aware resizing, since neural nets could theoretically be more semantically and holistically aware of objects in the image.