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.
> In this paper, we present a more efficient algorithm for seam based content-aware image resizing, which searches seams through establishing the matching relation between adjacent rows or columns. We give a linear algorithm to find the optimal matches within a weighted bipartite graph composed of the pixels in adjacent rows or columns.
I wonder if you could do a kind of quad-tree version where you hone in on the precise seam and minimise recalculations to bubbling new energy up the tree. That might also give a way to weigh global-to-local structure.
For example, if you consider an image of a roof, the roof pixels will all be semantically similar, but if you remove any of them just based on that, the regular structure will be distorted. Do you have an idea how to solve this?
I know little about deep learning though, so I can't really comment on it.
For situations like the roof problem you describe, I think PatchMatch is more likely to work out well. The downside is that it's considerably harder to implement correctly than seam carving. http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/patchmatch....
So, for a landscape-oriented image of aspect ratio 2:1 that would mean re-calculating up to 50% of its pixels. For narrower ones, that percentage is even higher, so not too much to gain.
(Licensed by Adobe for noncommercial research use only.)
Surely this is true in journalism. I find it hard to believe it's true in ad work.
Not as fancy as photoshop I'm sure, but does have the ability to paint a mask of regions to keep / remove to aid the algorithm and get the desired result. Multi-threaded too!
Didn’t expect image expanding... was blown away.
Mix in temporal energy plus a ML objects DB, put that in a chip, and turn decades of 4:3 TV into widescreen!
2008: Original Assignee Abode Systems Incorporated
2009: Original Assignee Eastman Kodak Company
Where is the creator located?
The cause of these artefacts are mainly that the original algorithm did not look at energy that was introduced by removing a seam: each time this happens, the pixels adjacent to this seam become neighbours, which creates a new energy gradient. So sometimes removing the least-energy seam would produce a net increase in energy.
The original authors of the seam carving paper realised this, which lead to the obvious fix for it: instead of only looking at the current energy of a picture, and removing the least-energy seam, look how much of a net energy difference the removal of a seam would make, aka "forward energy".
A few years later another paper came out that used "forward gradient difference maps" which supposedly work even better, but to be honest the formulas described in that paper are too complex for me to understand. Conceptually though, I think they just extended the original energy function (a simple Sobel operator) with a few other ones that include orientation and others:
> The energy function measures the curvature inconsistency between the pixels that become adjacent after seam removal, and involves the difference of gradient orientation and magnitude of the pixels. Our objective is to minimize the differences induced by the removed seam, and the optimization is performed by dynamic programming based on multiple cumulative energy maps, each of which corresponds to the seam pattern associated with a pixel. The proposed technique preserves straight lines and regular shapes better than the original and improved seam carving, and can be easily combined with other types of energy functions within the seam carving framework
With that in mind, it shouldn't be that complicated to come up with more improvements to seam-carving: just stack on different energy functions (either forward or current energy), and compute the ideal seam based on the (weighted) sum of them.
The algorithm itself looks like it needs face (and body) detection to be really useful, though.
Example: My girlfriend and I on holiday in Australia.
It will be more complicated than it seems, though, because I just tried the GUI version from gabeiscoding above, and got the following result:
With my tongue somewhat-in-cheek, I wanted to point you that you may want to be careful with that sample pic of the Eiffel Tower at night!
It's similar to the effect that changing focal length on a camera has. eg. Wider angle lenses seem to squish far away objects and enlarge closer objects. However, this affects the entire image in a consistent way whereas changing focal length does not.
I wonder if this could be used to simulate focal length changes?
These days it's a popular algorithm to be implemented as a midterm project in computational photography courses at top schools.
Anyways, neat! Nice contribution.