Combine a few simple algorithms - in this case edge detection and minimum energy path search - and what you get is pure black magic. That is why I love computer science!
Grant's lectures are always pure gold. We need to keep the activities in the comments so the TH-cam algorithms bless this video. It will help spread knowledge and will definitely make the world a better place.
i love the dynamic programming example.. changin from exponential order to multiplication just by reversing the way we do computation.. that is absolutely awesome..
If you can, please do more of these computer science applied math on the main channel. They are really interesting, and way easier to remember thanks to your way of explaining. Also seeing your face while explaining, like you do here, I think it's better then just having the graphics full screen
After the first round of computing least energy to bottom for each cell, you can get the minimum energy path by just following the lowest energy cells from bottom to top. That is faster than starting from the top cells and performing least energy path computations.
Isn't the idea of using a seam at every step itself a greedy algorithm? Just based on my intuition, it should be possible to carve a seam that makes other future seams significantly less optimal, perhaps by cutting half of a seam that could be a future option. Of course, the greedy algorithm seems to work well enough, but perhaps there's a DP approach that could let us choose better seams by looking into potential future seams.
I don't think you can decide the behaviour of some (optimal) seam afterwards if you take the optimal one this time in linear complexity. So being greedy and taking the best I can get at some time (T) is the best option.;
Nice video. Here's an alternative justification of three rows in the Sobel filter. 1) taking a derivation requires at least two points per output, so the dimension of the convolution will be one less. 2) if you want a gradient matrix, each slice (partial derivative) should be the same size so you need to average neigboring pixels in every other dimension. 3) if you average the derivativesto reduce noise, you should also average the (averaged) dimensions for the same reasons above. This gives you the vertical weights of [1; 2; 1].
So, is this a good summary of what we are doing? 1. Convolve the image with a sobel kernel (vertical or horizontal), which contains some negative values 2. The resulting RGB object may have negative values in red, green, and/or blue channels 3. Take the L1 norm of each pixel (adding the absolute values of three color components), obtaining a non-negative number, possibly greater than 1 4. Repeat the same procedure with the other sobel kernel (horizontal or vertical) 5. Take the L2 norm of the two sobel results
Actually at 5:15, he seems to first convert the image into grayscale using a function called "brightness" _and then_ apply the sobel filter. So, the sobel filter was never applied to an RGB object. The result may still be negative at some pixels, but they go away when you take the L2 norm of the two sobel filter results. This seems to be a neater approach.
@@enisten that's right, brightness is actually mean of the images -- we use mean instead of sum to keep it between 0 and 1 so that we can simply call Gray.(means) to show it as an image. The scaling does not matter for the algorithm, and of course you can choose a different brightness function if you wanted to.
That's a great question. Very observant. It's because when j==1, your slice of the least_E array, i.e. least_E[j1:j2], does not have the south-west element, it only has two elements.. This needs a special case to handle -- if findmin says 1, the direction is actually 0 (go down), if it says 2, then the direction is 1 (go south-east).
@@PhilBoswell You're right that on the right side of the row, the array whose min we need again has only two elements. However (-1,0,1)[idx] will work fine because it can return either -1 or 0 , it'll never return 1. Similarly in the left side also the array has only two elements, but its problematic because -1 is invalid this time. Hence we need to handle left end specially by adding 1. That's what j==1 does (julia weirdly uses 1-indexed arrays instead of 0-indexed hence j==1 and not j==0) Thanks Grant!!
I wish I teach as well as Grant. Right now I'm blaming it on my lack of time to prepare as I teach online as a side job. But really, even if I have more time, the bar he sets is pretty high.
Why do we need to go only bottom to top? How does the algorithm care if we go from top to bottom in cumulative addition? Also, what if we want to reduce the image so as to keep the aspect ratio constant? Shouldn't we have two cumulative addition images one for top to bottom and another for left to right? If it's a 16:9 image, do we need to cut out top-bottom 16 times and then left-right 9 times and repeat?
Just had a crazy idea!! What if you could use this same concept to slow down a music file without distorting it?? That is a puzzle that I don't think we've solved yet!
Wow, this is great explanation of these algorithms, really awesome. Also, you managed to utter "picks up on the edginess of Mario", which wins the internet today.
billions of people are busy watching despacito and only handful of thousand people are watching this interesting video. explains why the world is stupid.
Great video! Quick question: your seams go top-to-bottom (for horizontal resizing), so why use √(vx²+vy²) instead of just |vx|, that is, only convolving with sx?
that would lead to shrinking of the objects, for example the horizontal tree branch or other horizontal lines. what concerns me about this energy function is, that is renders single pixels and one pixel wide lines as completely unimportant, even if they have the biggest contrast to their surroundings. the energy of the neighboring pixels would be considered very high though ^^
you can recalculate everything, or you can recalculate only parts that can be affected by the removal of a seam. Seam: X Original value: O for recalculation: Y OOOOOXOOO OOOOOXOOO OOOOXOOOO OOOOXOOOO OOOXOOOOO Then you recalulate these: YYYYYYYY YYYYYYYO OYYYYYOO OOYYYOOO OOOOOOOO bottom row should not be recalculated because it never changes.
I think the idea of preprocessing in DL models is to provide just enough knowledge to make the model generalise and not overfit. Here almost all the knowledge remains intact, so using it for preprocessing would not be beneficial.
@@shivamjalotra7919 I understand what you mean. I could see it useful for models that take as input images of a fixed resolution. Resizing images to fit this resolution can be detrimental sometimes, I would rather use this algorithm for that purpose. But I understand your point of view and I agree, I would use this step for pre-processing to make all the images the same size, but then still add rotation and translation pre-processing
I wonder what the results would be if you used some Machine Learning attention activation (like a GAM) instead of a simple edge detection. Maybe it could "understand" the important regions and perform better.
this is the best thing that has happened during the pandemic. I teach seam carving as a PhD student, but now I feel useless :D
agreed 100%
@@SubhadityaMukherjee ok baman
Go bears!
@@JohnWick-xd5zu who :o
@@SinnohStarly lol your were my TA at Cal
Combine a few simple algorithms - in this case edge detection and minimum energy path search - and what you get is pure black magic.
That is why I love computer science!
Computer Science gives you the power to experiment at a low cost.
@@henrmota I know!! That's why I'm doing it for a living :)
@Arid Sohan yeah, exactly what i was thinking
MIT are lucky to have you!
"It picks up on the edginess of Mario" --- Grant Sanderson 2020
I have my own classes, but I’m watching this series as well for Grant.
How can he be very good at storytelling this kind of complicated and multilayered concepts/techniques. A genius.
Grant's lectures are always pure gold. We need to keep the activities in the comments so the TH-cam algorithms bless this video. It will help spread knowledge and will definitely make the world a better place.
i love the dynamic programming example.. changin from exponential order to multiplication just by reversing the way we do computation.. that is absolutely awesome..
This is the best explanation of magic of content aware shrinking. Thank you! Спасибо!
People waste time on Netflix when you have Grant around. Crazy.
We need a petition to bring Grant to Netflix! Make Algebra Great Again!
its crazy i had to go to bed half an hour ago
in this episode grant teaches us how to optimally get over your ex
This is Stalin's wet dream algorithm
Great presentation, Grant! So clear and concise, despite the depth. Makes it look easy and natural. Really good!
If you can, please do more of these computer science applied math on the main channel. They are really interesting, and way easier to remember thanks to your way of explaining. Also seeing your face while explaining, like you do here, I think it's better then just having the graphics full screen
Wow I've never seen anyone to explain dynamic programming simpler!
After the first round of computing least energy to bottom for each cell, you can get the minimum energy path by just following the lowest energy cells from bottom to top. That is faster than starting from the top cells and performing least energy path computations.
Isn't the idea of using a seam at every step itself a greedy algorithm? Just based on my intuition, it should be possible to carve a seam that makes other future seams significantly less optimal, perhaps by cutting half of a seam that could be a future option.
Of course, the greedy algorithm seems to work well enough, but perhaps there's a DP approach that could let us choose better seams by looking into potential future seams.
I don't think you can decide the behaviour of some (optimal) seam afterwards if you take the optimal one this time in linear complexity. So being greedy and taking the best I can get at some time (T) is the best option.;
I was thinking the same as you. Maybe the best approach for this would be to know from the first how many paths you will want to shrink at total
Could always go bottom to top.
This is just amazing! Grant not only knows a lot but explains in a way that makes it very simple
That's why I love algorithms, they are made by most genuine persons.
Everything about this video is great
Nice video. Here's an alternative justification of three rows in the Sobel filter. 1) taking a derivation requires at least two points per output, so the dimension of the convolution will be one less. 2) if you want a gradient matrix, each slice (partial derivative) should be the same size so you need to average neigboring pixels in every other dimension. 3) if you average the derivativesto reduce noise, you should also average the (averaged) dimensions for the same reasons above. This gives you the vertical weights of [1; 2; 1].
This must be grants lowest views but thanks a lot for putting such content and making it accessible
I live in germany and im only in 10th grade but i still really enjoy watching these videos
That was so cool.
These lectures are amazing. Thank you
Grant is a teaching genius.
So, is this a good summary of what we are doing?
1. Convolve the image with a sobel kernel (vertical or horizontal), which contains some negative values
2. The resulting RGB object may have negative values in red, green, and/or blue channels
3. Take the L1 norm of each pixel (adding the absolute values of three color components), obtaining a non-negative number, possibly greater than 1
4. Repeat the same procedure with the other sobel kernel (horizontal or vertical)
5. Take the L2 norm of the two sobel results
Actually at 5:15, he seems to first convert the image into grayscale using a function called "brightness" _and then_ apply the sobel filter. So, the sobel filter was never applied to an RGB object. The result may still be negative at some pixels, but they go away when you take the L2 norm of the two sobel filter results. This seems to be a neater approach.
@@enisten that's right, brightness is actually mean of the images -- we use mean instead of sum to keep it between 0 and 1 so that we can simply call Gray.(means) to show it as an image. The scaling does not matter for the algorithm, and of course you can choose a different brightness function if you wanted to.
This is awesome, thanks. Especially the bit at the end - great potential for mischief!
What a simple clever algorithm. That should be on every photo editting tools
Brilliant explanation of a brilliant concept 😮
Using dynamic programming to make lockscreen wallpapers would also be an apt title. I loved the teal gradients in starry night ❤️
At 22:48 why are we adding j==1 to dir while saving min item indices
That's a great question. Very observant. It's because when j==1, your slice of the least_E array, i.e. least_E[j1:j2], does not have the south-west element, it only has two elements.. This needs a special case to handle -- if findmin says 1, the direction is actually 0 (go down), if it says 2, then the direction is 1 (go south-east).
@@TheJuliaLanguage so is the other special case, the other end of the row when there isn't a *south-east* element, handled automagically somehow?
@@PhilBoswell You're right that on the right side of the row, the array whose min we need again has only two elements. However (-1,0,1)[idx] will work fine because it can return either -1 or 0 , it'll never return 1. Similarly in the left side also the array has only two elements, but its problematic because -1 is invalid this time. Hence we need to handle left end specially by adding 1. That's what j==1 does (julia weirdly uses 1-indexed arrays instead of 0-indexed hence j==1 and not j==0)
Thanks Grant!!
I wish I teach as well as Grant. Right now I'm blaming it on my lack of time to prepare as I teach online as a side job. But really, even if I have more time, the bar he sets is pretty high.
26:54 Creepy, he’s still holding the hand of his vanished ex-girl friend!
Instead of wasting my time watching a netflix show, I enjoyed learning about a fun way to make use of a triangle
Not yet.
Why do we need to go only bottom to top? How does the algorithm care if we go from top to bottom in cumulative addition?
Also, what if we want to reduce the image so as to keep the aspect ratio constant? Shouldn't we have two cumulative addition images one for top to bottom and another for left to right?
If it's a 16:9 image, do we need to cut out top-bottom 16 times and then left-right 9 times and repeat?
does anyone know where can I find the "original paper" he is referring to at 02:50?
Grant you're great
There is also a cool looking glitch effect when you just remove N pixels with minimal entropy in each row without connection them in path
Getting rid of Ex's feature was just hilarious
"The great and one and only"
Uh oh
Just had a crazy idea!! What if you could use this same concept to slow down a music file without distorting it?? That is a puzzle that I don't think we've solved yet!
This guy sounds really similar to the talking pi at 3blue1brown
i was like "hold on this guy sounds familiar" and then it clicked
just awesome explanation...!!!
i translated your code in Python! it is great!!
This is awesome. Thank you!
15:00 but dijkstra is faster, no?
Wow , pretty like the exercises on Dynamic Programming in Introducton To Algorithms...
THIS IS SO DOPE!!!!!! thanks grant! cool hair too!
Edgy Mario looks like he's going through an emo phase.
yea thats why he's edgy
This is such incredibly good content, if the universities don't pick up their slack soon, youtube will just demolish them.
You are aware that this is content from a university lecture at MIT?
@@TheMikebo In that case: Exceptional job MIT.
Wow, this is great explanation of these algorithms, really awesome.
Also, you managed to utter "picks up on the edginess of Mario", which wins the internet today.
wonderful lecture!!
Thank you
go grant go!
billions of people are busy watching despacito and only handful of thousand people are watching this interesting video. explains why the world is stupid.
Does solving the sub problems from top to bottom rather than from bottom top,would it give the same shortest energy path?
Fascinating
Awesome
After removing a seam, is it best to recalculate the energy values or to continue using the original ones?
Recalculation is the best.
So good 🎉
I got a question: do you re-compute energies after each seam removal?
Talking in terms of energy it looks like a thunderbolt going down through the path of least energy :D
It could be called the thunderbolt algorithm.
Has there been any study of seam carving with horizontal directions instead of just downward?
Where can I get started learning Julia?
Which programming did Grant used there not looks like python but almost similar to it.
This course uses the Julia programming language.
lol..read the name of the channel. I've heard this language is great for programming mathematical models.
Can you parallel this with the concept of value functions from reinforcement learning/marcov decision processes?
Great video! Quick question: your seams go top-to-bottom (for horizontal resizing), so why use √(vx²+vy²) instead of just |vx|, that is, only convolving with sx?
that would lead to shrinking of the objects, for example the horizontal tree branch or other horizontal lines.
what concerns me about this energy function is, that is renders single pixels and one pixel wide lines as completely unimportant, even if they have the biggest contrast to their surroundings. the energy of the neighboring pixels would be considered very high though ^^
Didn't know it was you Grant :)
Quality!
No link to the notebook ?
Gold mine
Grant so handsome, lecture so amazing, using my whole attention to learn this material! Thanks~
Just one question. After eliminating one steam? We have to recalculate everything again? Because of steam pixel overlap.
you can recalculate everything, or you can recalculate only parts that can be affected by the removal of a seam.
Seam: X
Original value: O
for recalculation: Y
OOOOOXOOO
OOOOOXOOO
OOOOXOOOO
OOOOXOOOO
OOOXOOOOO
Then you recalulate these:
YYYYYYYY
YYYYYYYO
OYYYYYOO
OOYYYOOO
OOOOOOOO
bottom row should not be recalculated because it never changes.
@@estivale8193 Thanks, because I am trying to implement this in the web with the gpu support. But this is a very particular calculation.
Is the full course getting uploaded?
yes it will be. you can bookmark mitmath.github.io/18S191/Fall20/ to keep tabs. Schedule is on the front page
Why hasn't this been used more as a preprocessing step for deep learning models?
I think the idea of preprocessing in DL models is to provide just enough knowledge to make the model generalise and not overfit. Here almost all the knowledge remains intact, so using it for preprocessing would not be beneficial.
@@shivamjalotra7919 I understand what you mean. I could see it useful for models that take as input images of a fixed resolution. Resizing images to fit this resolution can be detrimental sometimes, I would rather use this algorithm for that purpose. But I understand your point of view and I agree, I would use this step for pre-processing to make all the images the same size, but then still add rotation and translation pre-processing
Oh I missed the live class!
Anyone catch the title of the seam-carving paper?
Found it: "Seam Carving for Content-Aware Image Resizing". graphics.cs.cmu.edu/courses/15-463/2012_fall/hw/proj3-seamcarving/imret.pdf
This feature is alredy implemented in photoshop works both ways
Other profs: 200 views
Grant: 1.6k views
what programming language is he using?
Photoshop can do it perfectly well.
It’s called content preserving scaling
Probab photoshop does this way as well
Content aware scaaaaaalle
12:56
What is the animations software?
Manim, 3b1b's custom software
Thanks!!!!! 🤝🏼
Is this a some kind of magic?🤏
I'm not a programmer but seam duplication with interpolation should also be easily doable?
I wonder what the results would be if you used some Machine Learning attention activation (like a GAM) instead of a simple edge detection. Maybe it could "understand" the important regions and perform better.
Cool！
or a toilet brush to clean all of that yest thats been accumulating for years in the khukhus
It's the meme algorithm
Where do I know his voice from?
3blue1brown
I mean, isn't this already a thing anyway? Content Aware Scaling
But why did Julia drop OpenCL support?
Is this Loopop lol
Is he the 3b1b guy?
yes he is!
yors mathas dripping khus khus.
LOVE GRANT LOVE GRANT LOVE GRANT LOVE GRANT
I AM DEEPLY DEPRESSED THAT HE WILL DIE
no squish? lol look at that pomegranate
You're 3Blue1Brown change my mind.