9 ms·
Real-world dynamic programming: seam carving
- alleycat5000 7y agoThis was a homework assignment in Robert Sedgewick's Algorithms course on Coursera! https://www.coursera.org/learn/algorithms-part1 https://www.coursera.org/learn/algorithms-part1 Great class and fun assignment!
- fizwhiz 7y agoWasn't the first assignment about detecting percolation using the union find datastructure? IIRC, sedgwick's class doesn't cover dynamic programming directly at all.
- Chickenosaurus 7y agoSeam carving is the second assignment of Algorithms Part II. I also highly recommend Princeton's Algorithms course on Coursera.
- fizwhiz 7y agoAh, I haven't taken Part II of the course. Probably not a bad idea to start :)
- ttoinou 7y agoGreat. Now adapt this to video (:
- itronitron 7y agoI noticed they don't provide any images with human faces.
- roywiggins 7y ago"Human faces? You can't handle human faces!" https://www.youtube.com/watch?v=zqeIqJGdA58 https://www.youtube.com/watch?v=zqeIqJGdA58
- akdas 7y agoThe algorithm definitely has issues with faces. One part I didn't get into is artificial weights. The original paper discusses "painting" certain regions of the image as high energy, driving seams away from those regions. This ties into faces when the paper suggests face detection to automatically paint faces with high energy, avoiding these issues in the first place!
- shawnz 7y agoProbably intentional, the seam carving algorithm has a tendency to make faces look distorted: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15463-f10/www/proj2/www/gmethvin/Obamas_at_White_House_Easter_Egg_Roll_4-13-09_2_resized.jpg http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15463-f1...
- jeffreyrogers 7y agoThe basic algorithm doesn't work well with faces, but you can use facial recognition to add a large penalty to carving through regions with faces. So it can be extended pretty easily to handle this.
- a-priori 7y agoSince the human visual system is so highly sensitive to faces I think the best approach here would be to apply a facial detection algorithm, then boost the energy for the regions where faces are detected. Basically you'd apply a heuristic that because faces are so special to the human visual system, the perceived energy of a face is higher than the pixels would otherwise indicate. This would make seams avoid altering any faces in the scene.
- akdas 7y ago> apply a facial detection algorithm, then boost the energy for the regions where faces are detected. Great intuition! The original paper actually goes into this, and they come up with that solution. This solution is a special case of allowing the user to apply positive and negative penalties as they wish. The latter allows targeted object removal.
- gamegoblin 7y agoA friend and I once tried this at a hackathon. If you do it naively like we did, frame-by-frame, you will find that the optimal seam to carve shifts around a lot as the lighting changes subtly. This results in characters in frame apparently moonwalking around. It's a really cool effect, but not good for actually resizing a film. Might make for a cool bit of a music video.
- a-priori 7y agoThis same algorithm could be applied in three dimensions (X, Y, time) such that the seam connects along adjacent pixels through time as well as the Y axis. The seam here would be a 2D plane, rather than a 1D line as it is for a single image. If you visualize a video as a stack of frames, then the seam would cut through the stack, like cutting a cake with a knife, following the minimum-energy path through the stack. You'd do this by modifying the recurrence relation to add a term for the energy of pixels in the previous frame as well as the previous line in the current frame.
- gamegoblin 7y agoI don't think it's necessarily so simple, and I think the multi-frame case blows up the complexity of the algorithm. In the single frame case, each pixel is a 0 dimensional point, and for each pixel, you evaluate the 3 adjacent pixels in the row above. Then to find the seam you just pick the lowest energy pixel at the edge of the frame and follow the thread up. So the total runtime of this algorithm is O(pixels). In the multi-frame case, if you want the video to be totally smooth, you have to think higher-dimensionally. In the multi frame case, each seam is a 1 dimensional list of pixels, and for each seam, you evaluate the $HUGE_NUMBER of adjacent seams in the previous frame. That is, the 2D case's runtime is proportional to the image height times the number of adjacent pixels, which is a small constant (3). In the 3D case, the runtime is proportional to the number of frame times the number of adjacent seams, which is massive. I can imagine some heuristic optimizations that would allow you to guide your search, though. For instance, you could significantly downsample the video in both pixels and framerate and solve that, and then use that low-resolution solution to constrain and prune an approximate high-resolution search.
- dTal 7y agoI think this is the correct way to conceptualize generalizing this algorithm to moving video. I also think it's a fundamentally bad approach to resizing video. The problem is that humans watching the video will build a 3D mental model of the scene; any transform that modifies multiple frames must do so in such a way as to maintain global spatial consistency, or it will look odd. Seam carving is too primitive to do this. You will have shots where (for instance) someone is walking obliquely away from a building towards the camera, and yet making no headway because the algorithm is carving away the (low energy, yet perceptually indispensible) pixels that seperate them - the result will be that they appear to be walking in place (and growing).
- steventhedev 7y agoFor what it's worth, that was exactly what they did: http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html
- ausbah 7y agoIt has been done! http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf
- marvy 7y agoSee this comment in this thread: https://news.ycombinator.com/item?id=20285242#unv_20290891 https://news.ycombinator.com/item?id=20285242#unv_20290891 (HN really should make it easier to make "anchor" links, so people don't have to load a new page just to see a sub-thread. That probably took me almost 5 minutes, which is like a quarter of the "anti-procrastination" budget with the default settings. It should have taken 10 seconds.)
- xemoka 7y agoNon-medium version: https://avikdas.com/2019/05/14/real-world-dynamic-programming-seam-carving.html https://avikdas.com/2019/05/14/real-world-dynamic-programmin...
- sctb 7y agoThanks! We've updated the link from https://medium.com/@avik.das/real-world-dynamic-programming-seam-carving-9d11c5b0bfca https://medium.com/@avik.das/real-world-dynamic-programming-....
- milliams 7y agoIt feels like those images of the energy could have been improved by plotting the log of the energy. It would allow us to see changes at the low end where the decisions are being made.
- tylorr 7y agoI'm toying around learning the algorithm. Thought I might share a log plot of the energy. https://imgur.com/a/YlrS7aV https://imgur.com/a/YlrS7aV
- amelius 7y agoIsn't there a more generic deep-learning approach (i.e. with less assumptions) for this problem?
- madhadron 7y agoIt wouldn't really have fewer assumptions. In fact, it probably would have more. We just wouldn't know what they are. Classical image analysis is still interesting and valuable because you can construct an algorithm based on desired properties without having to have a large, labelled training set beforehand, and because it's computationally much less expensive.
- amelius 7y ago> It wouldn't really have fewer assumptions. In fact, it probably would have more. It depends on how you look at it. A deep learning approach is supposedly more generic. Therefore I suppose the assumptions would be dynamic instead of fixed.
- activatedgeek 7y agoAssumptions are NOT dynamic. Once we have chose a "loss" function or whatever fancy name you want to call the objective function by, you've already made a choice. There are never dynamic assumptions (a classic example would be the choice of use L2 loss in the pixel space essentially assumes a Gaussian likelihood, which is in principle kind of goofy but hey it works). Although, as alluded to earlier, it is hard to understand the space induced by the architectural assumptions (and many other moving parts) I like to think it this way - effectively, deep learning provides learned priors from data for a downstream task whereas the manual way comes from expert knowledge without the learning part.
- tagh 7y agoThere are plenty of fixed assumptions within deep learning. Off the top of my head: (1) Loss function (2) Pooling layers (which hard code invariances)
- slig 7y agoReally interesting, thanks for sharing! I believe there's a typo here: "the time complexity would still be 𝑂(𝑊)" should be "the space complexity would still be 𝑂(𝑊)".
- akdas 7y agoThanks so much for pointing that out! I've updated the article.
- GolDDranks 7y agoThis brings to mind the Viterbi algorithm that calculates the most likely sequence of events in a hidden Markov model (Markov model itself is just a state machine on a graph with weighed edges, where each weight on a state transition is represented as a probability of that transition). It's essentially bases to the same algorithm: you can eliminate sequences if they lead to the same event that is already part of a solution, but with lesser probability. The amount of paths would be exponential, but the ability to eliminate them keeps it polynomial. That really brings forth the beauty of dynamic programming.
- akdas 7y agoI just literally published an article on that yesterday :) https://avikdas.com/2019/06/24/dynamic-programming-for-machine-learning-hidden-markov-models.html https://avikdas.com/2019/06/24/dynamic-programming-for-machi... Agreed, it's basically the same algorithm.
- shaki-dora 7y agoA lot of problems on sequences are amendable to dynamic programming. Two other famous ones are Smith-Waterman and Needleman-Wunsch for finding optimal global and local alignments of sequences–a typical problem in genetics.
- marton78 7y agoThe Levenshtein distance, which finds the fewest edits to transform one string to another is also a classical example.
- n4r9 7y agoOne really nice application of the Viterbi algorithm is map-matching, i.e. taking a GPS trail and "snapping" it to the road network to determine the actual route taken. It's difficult because GPS trails are often sparse and noisy, so you can't do something simple like "project onto the closest road segment". If you take the "states" of the model to be road segments and derive the transition probabilities from the shortest route between segments, you can apply Viterbi and get a very accurate result most of the time. Of course, calculating shortest routes involves Dijkstra, another famous dynamic algorithm.
- matsemann 7y agoI held a workshop once where people implemented this (and other image algorithms). The end result can be seen here [0], and the tasks here [1] (but in Norwegian). Can click the "run seam carving" button to watch it unfold step by step. [0]: https://matsemann.github.io/image-workshop/ https://matsemann.github.io/image-workshop/ [1]: https://github.com/Matsemann/image-workshop https://github.com/Matsemann/image-workshop
- bitL 7y agoAny good set of super hard dynamic programming problems to practice? (I mean way harder than leetcode/hackerrank etc.)
- bouk 7y agoYou can look at competitive programming sites, they are a lot more serious than leetcode/hackerrank https://dmoj.ca/problems/?type=5&show_types=1&order=-points https://dmoj.ca/problems/?type=5&show_types=1&order=-points https://codeforces.com/problemset?order=BY_RATING_DESC&tags=dp https://codeforces.com/problemset?order=BY_RATING_DESC&tags=...
- kadoban 7y agoHackerrank has some fairly no-joke problems on it. Is https://www.hackerrank.com/challenges/decibinary-numbers/problem https://www.hackerrank.com/challenges/decibinary-numbers/pro... too easy? I enjoyed that one a while back. I think I have a list of curated DP problems bookmarked somewhere, I'll see if I can track it down.
- 6thaccount2 7y agoEnergy markets used to use Lagrangian Relaxation and Dynamic Programming to find the least cost dispatch. Some still do, but the larger ones (all the ones in the US) use Mixed-Integer Linear Programming and Linear Programming as the engines can handle a lot more and still solve. The problem is that you'd need to get your hands on a large dataset and none of the true ones are public. I think some of the national labs have synthetic models of various sizes to play with. Seriously cool field.
- jharger 7y agoI remember implementing this for a class years ago, and then the professor suggested doing the inverse to try to expand the image width. The idea was you would duplicate the lowest energy seam... but all that did was create a lot of repeats of the same seam. I never did finish that weird idea, but I probably needed to try something like increasing the energy of the chosen seam (and its duplicate)... I may try that again, just because I'm curious what would happen.
- Scaevolus 7y agoThe original seam carving paper discussed expanding too: https://youtu.be/6NcIJXTlugc?t=56 https://youtu.be/6NcIJXTlugc?t=56 http://www.faculty.idc.ac.il/arik/SCWeb/imret/imret.pdf http://www.faculty.idc.ac.il/arik/SCWeb/imret/imret.pdf > Figure 8: Seam insertion: finding and inserting the optimum seam on an enlarged image will most likely insert the same seam again and again as in (b). Inserting the seams in order of removal (c) achieves the desired 50% enlargement (d). Using two steps of seam insertions of 50% in (f) achieves better results than scaling (e). In (g), a close view of the seams inserted to expand figure 6 is shown.
- GBB 7y agoThe approach from the original paper is to remove seams like you are decreasing the size, which provides you with a set of exclusive seams that can be added to the original image (with some mapping logic). This produces an output without repeating the same seam repeatedly.
- feltarock 7y agoThat's actually done in the paper! You basically choose the lowest energy seam, duplicate it, then blacklist it and duplicate the next lowest energy seam (to prevent repeatedly duplicating the same seam). The results are quite good.
- gabeiscoding 7y agoCool to see this popping up again. It always impresses if you haven't seen it before and is a cool algorithm to work through. The original paper was discussed on slashdot and back at that time I was inspired to build a little GUI around an open source algorithm implementation to play with my Qt skills. It allows you to shrink, expand and "mask out" regions you don't want touch etc. Still available on Google Code archive: https://code.google.com/archive/p/seam-carving-gui/ https://code.google.com/archive/p/seam-carving-gui/
- petschge 7y agoThis is also known as "liquid rescale" and there is (was?) a gimpl plugin for it. It last updated in 2013 or so. After that the developer was hired by Adobe to work on Photoshop.
- BeetleB 7y agoYes, Gimp had it as a plugin first - before Photoshop.
- bcp2384 7y agoWhy are DP problems so popular for interviews? I am doing leetcode now and they seem to be everywhere.
- chii 7y agothey are a very good judge of whether the programmer can do complex problems (but still simple enough a solution to do in an interview setting).
- walrus1066 7y agoI'd honestly just walk out if a company asks this stuff, yet the actual work is maintaining a CRUD app.
- co0nsta 7y agoIf you like DP imaging applications like this, this old Microsoft Research technical report is neat: it uses DP to merge frames from two webcams placed left and right to synthesize a view in the middle, like having a webcam in the middle of your monitor. The DP is interesting because it has penalities set up assuming planar content because faces are pretty flat and in front of the cameras. Link: https://www.microsoft.com/en-us/research/publication/efficient-dense-stereo-and-novel-view-synthesis-for-gaze-manipulation-in-one-to-one-teleconferencing/ https://www.microsoft.com/en-us/research/publication/efficie...
- andreareina 7y agoThere's also the approach that calculates the energy of the resulting image as opposed to the seam being removed, which allows the seams to pass through objects where doing so will minimize artifacts. Paper: http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html GitHub: https://github.com/axu2/improved-seam-carving https://github.com/axu2/improved-seam-carving
- vanderZwan 7y agoThanks for sharing - it's kind of sad that nobody ever seems to know about the significantly better forward energy version. Especially since it's such a minor tweak.
- deleted 7y ago[deleted]
- trhway 7y agoTangential - the turbulent water looks for me like the large scale structure of the Universe.