5 ms·

Seam Carving (2018)

70 points by maxwell 2y ago

Murky3515 2y ago
[flagged]
- _a_a_a_ 2y ago
  [flagged]
  - Murky3515 2y ago
    There aren't many useful applications. People who think otherwise are on par with delusional interviewers that feel compelled to ask problems with DP solutions. The vast majority of us will go our entire careers without needing to solve the Towers of Hanoi or the Egg Drop Puzzle.
    - JohnKemeny 2y ago
      Knapsack/subset sum, travelling salesman, longest common subsequence, dynamic time warp/edit distance/sequence alignment, Q-learning, line breaking/paragraph layout, ...
    - hinkley 2y ago
      I cut almost a minute off of our startup time by removing a recursive nightmare one of my coworkers inflicted on some code I wrote by replacing the whole thing with DP. But you’d have to look pretty close to see that’s what I did because unlike him I’m not obsessed with people thinking I’m clever. I’d rather be seen as wise. (I started fixing it because we had found a couple mystery bugs caused by his solution not being reentrant. By the time I had full code branch coverage, it was actually six separate bugs I fixed)
  - tejtm 2y ago
    Indeed. I would wager that over the last several decades BLAST (basic local alignment search tool) has done more to advance our knowledge of biology than any other algorithm. https://en.wikipedia.org/wiki/BLAST_(biotechnology) https://en.wikipedia.org/wiki/BLAST_(biotechnology)
    - Murky3515 2y ago
      BLAST isn't a dynamic programming algorithm. It's not guaranteed to find an optimal solution, unlike a DP algorithm. It has some elements of DP, but that's it.
      - _a_a_a_ 2y ago
        "BLAST is a heuristic method which means that it is a dynamic programming algorithm..." https://bioinformaticsreview.com/20210503/how-blast-works-concepts-types-methods-explained/ https://bioinformaticsreview.com/20210503/how-blast-works-co... "The heart of many well-known programs is a dynamic programming algorithm, or a fast approximation of one, including sequence database search programs like BLAST..." https://www.nature.com/articles/nbt0704-909 https://www.nature.com/articles/nbt0704-909
        Murky3515 2y ago
        All DP algorithms guarantee an optimal result. It's a defining characteristic of DP. BLAST doesn't. I'm really surprised that you're attempting to debate this.
        _a_a_a_ 2y ago
        DDG disagrees. https://html.duckduckgo.com/html?q=%22%20heuristic%20dynamic%20programming%22 https://html.duckduckgo.com/html?q=%22%20heuristic%20dynamic... I'm clearly not going to understand your motivation so I think I'll stop here. (edit: There is absolutely nothing stopping heuristics and DP being combined; in fact they have to be in eg. database optimisation. A pure DP solution to query optimisation will be optimal, but will take unbounded (lthough finite) time, which is unacceptable. DP and heuristics are combined to both guide the DP search and bound it after a strict time (usually a couple of seconds CPU) by when it is hopefully 'good enough').
        Murky3515 2y ago
        You're wrong, and I don't know why you're being stubborn about this. HDP is a different class of algorithms that uses DP, but it is not DP. A basic read of wikipedia of dynamic programming reveals the key pieces of DP: There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. ... Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. See the words optimal and optimization? https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming
  - deleted 2y ago
    [deleted]
  - dang 2y ago
    Please don't cross into name-calling, regardless of how wrong another comment is or you feel it is. That only makes the thread worse. This is in the site guidelines: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html.
JohnKemeny 2y ago
Related: Real-world dynamic programming: https://news.ycombinator.com/item?id=20285242 https://news.ycombinator.com/item?id=20285242 (66 comments) Parallel seam carving: https://news.ycombinator.com/item?id=24117330 https://news.ycombinator.com/item?id=24117330 (37 comments) Seam carving (2020) [video] https://news.ycombinator.com/item?id=26844121 https://news.ycombinator.com/item?id=26844121 (35 comments) Seam carving (Wikipedia) https://news.ycombinator.com/item?id=21192868 https://news.ycombinator.com/item?id=21192868 (11 comments)
worewood 2y ago
I bet that if this algorithm had come up today it would be called AI resizing
alexhwoods 2y ago
That's super cool. Love the visualizations!
londons_explore 2y ago
This is a very discrete 'pixel based' approach. I wonder if it could be generalized into the continuous image space, and if that would improve results.
nsjolj 2y ago
[dead]
mnjksd 2y ago
[dead]

Seam Carving (2018)

70 points by maxwell 2y ago

Murky3515 2y ago

[flagged]

_a_a_a_ 2y ago
[flagged]
- Murky3515 2y ago
  There aren't many useful applications. People who think otherwise are on par with delusional interviewers that feel compelled to ask problems with DP solutions. The vast majority of us will go our entire careers without needing to solve the Towers of Hanoi or the Egg Drop Puzzle.
  - JohnKemeny 2y ago
    Knapsack/subset sum, travelling salesman, longest common subsequence, dynamic time warp/edit distance/sequence alignment, Q-learning, line breaking/paragraph layout, ...
  - hinkley 2y ago
    I cut almost a minute off of our startup time by removing a recursive nightmare one of my coworkers inflicted on some code I wrote by replacing the whole thing with DP. But you’d have to look pretty close to see that’s what I did because unlike him I’m not obsessed with people thinking I’m clever. I’d rather be seen as wise. (I started fixing it because we had found a couple mystery bugs caused by his solution not being reentrant. By the time I had full code branch coverage, it was actually six separate bugs I fixed)
- tejtm 2y ago
  Indeed. I would wager that over the last several decades BLAST (basic local alignment search tool) has done more to advance our knowledge of biology than any other algorithm. https://en.wikipedia.org/wiki/BLAST_(biotechnology) https://en.wikipedia.org/wiki/BLAST_(biotechnology)
  - Murky3515 2y ago
    BLAST isn't a dynamic programming algorithm. It's not guaranteed to find an optimal solution, unlike a DP algorithm. It has some elements of DP, but that's it.
    - _a_a_a_ 2y ago
      "BLAST is a heuristic method which means that it is a dynamic programming algorithm..." https://bioinformaticsreview.com/20210503/how-blast-works-concepts-types-methods-explained/ https://bioinformaticsreview.com/20210503/how-blast-works-co... "The heart of many well-known programs is a dynamic programming algorithm, or a fast approximation of one, including sequence database search programs like BLAST..." https://www.nature.com/articles/nbt0704-909 https://www.nature.com/articles/nbt0704-909
      - Murky3515 2y ago
        All DP algorithms guarantee an optimal result. It's a defining characteristic of DP. BLAST doesn't. I'm really surprised that you're attempting to debate this.
        _a_a_a_ 2y ago
        DDG disagrees. https://html.duckduckgo.com/html?q=%22%20heuristic%20dynamic%20programming%22 https://html.duckduckgo.com/html?q=%22%20heuristic%20dynamic... I'm clearly not going to understand your motivation so I think I'll stop here. (edit: There is absolutely nothing stopping heuristics and DP being combined; in fact they have to be in eg. database optimisation. A pure DP solution to query optimisation will be optimal, but will take unbounded (lthough finite) time, which is unacceptable. DP and heuristics are combined to both guide the DP search and bound it after a strict time (usually a couple of seconds CPU) by when it is hopefully 'good enough').
        Murky3515 2y ago
        You're wrong, and I don't know why you're being stubborn about this. HDP is a different class of algorithms that uses DP, but it is not DP. A basic read of wikipedia of dynamic programming reveals the key pieces of DP: There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. ... Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. See the words optimal and optimization? https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming
- deleted 2y ago
  [deleted]
- dang 2y ago
  Please don't cross into name-calling, regardless of how wrong another comment is or you feel it is. That only makes the thread worse. This is in the site guidelines: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html.

JohnKemeny 2y ago

Related: Real-world dynamic programming: https://news.ycombinator.com/item?id=20285242 https://news.ycombinator.com/item?id=20285242 (66 comments) Parallel seam carving: https://news.ycombinator.com/item?id=24117330 https://news.ycombinator.com/item?id=24117330 (37 comments) Seam carving (2020) [video] https://news.ycombinator.com/item?id=26844121 https://news.ycombinator.com/item?id=26844121 (35 comments) Seam carving (Wikipedia) https://news.ycombinator.com/item?id=21192868 https://news.ycombinator.com/item?id=21192868 (11 comments)

worewood 2y ago

I bet that if this algorithm had come up today it would be called AI resizing

alexhwoods 2y ago

That's super cool. Love the visualizations!

londons_explore 2y ago

This is a very discrete 'pixel based' approach. I wonder if it could be generalized into the continuous image space, and if that would improve results.

nsjolj 2y ago

[dead]

mnjksd 2y ago

[dead]