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
@SubhadityaMukherjee4 жыл бұрын
agreed 100%
@jake_runs_the_world4 жыл бұрын
@@SubhadityaMukherjee ok baman
@JohnWick-xd5zu4 жыл бұрын
Go bears!
@SinnohStarly4 жыл бұрын
@@JohnWick-xd5zu who :o
@JohnWick-xd5zu4 жыл бұрын
@@SinnohStarly lol your were my TA at Cal
@ProjectPhysX4 жыл бұрын
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!
@henrmota3 жыл бұрын
Computer Science gives you the power to experiment at a low cost.
@ProjectPhysX3 жыл бұрын
@@henrmota I know!! That's why I'm doing it for a living :)
@yash11522 жыл бұрын
@Arid Sohan yeah, exactly what i was thinking
@ancbi4 жыл бұрын
"It picks up on the edginess of Mario" --- Grant Sanderson 2020
@kindoblue4 жыл бұрын
People waste time on Netflix when you have Grant around. Crazy.
@bessimaestro4 жыл бұрын
We need a petition to bring Grant to Netflix! Make Algebra Great Again!
@AndreasIndustriePro4 жыл бұрын
its crazy i had to go to bed half an hour ago
@JudahDaniels4 жыл бұрын
MIT are lucky to have you!
@NEMountainG4 жыл бұрын
I have my own classes, but I’m watching this series as well for Grant.
@nonhonome40804 жыл бұрын
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
@barrycavin4 жыл бұрын
How can he be very good at storytelling this kind of complicated and multilayered concepts/techniques. A genius.
@AV-br3bm4 жыл бұрын
Grant's lectures are always pure gold. We need to keep the activities in the comments so the KZfaq algorithms bless this video. It will help spread knowledge and will definitely make the world a better place.
@zinxys Жыл бұрын
i love the dynamic programming example.. changin from exponential order to multiplication just by reversing the way we do computation.. that is absolutely awesome..
@birdbrid93914 жыл бұрын
in this episode grant teaches us how to optimally get over your ex
@sprechchor3 жыл бұрын
This is Stalin's wet dream algorithm
@oghry4 жыл бұрын
This is the best explanation of magic of content aware shrinking. Thank you! Спасибо!
@SergioRMuniz4 жыл бұрын
Great presentation, Grant! So clear and concise, despite the depth. Makes it look easy and natural. Really good!
@usama579262 жыл бұрын
Grant you're great
@MrNightLifeLover3 жыл бұрын
Wow I've never seen anyone to explain dynamic programming simpler!
@abhchow4 жыл бұрын
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.
@shivamjalotra79194 жыл бұрын
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.;
@jjalag4 жыл бұрын
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
@harshmudhar963 жыл бұрын
Could always go bottom to top.
@Clashtoons3 жыл бұрын
That was so cool.
@VicenteSchmitt4 жыл бұрын
This is just amazing! Grant not only knows a lot but explains in a way that makes it very simple
@christophercrawford288311 ай бұрын
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].
@weinsim38564 жыл бұрын
I live in germany and im only in 10th grade but i still really enjoy watching these videos
@adityachk20024 жыл бұрын
This must be grants lowest views but thanks a lot for putting such content and making it accessible
@John_Chakder4 жыл бұрын
Everything about this video is great
@ManthaarJanyaro4 жыл бұрын
That's why I love algorithms, they are made by most genuine persons.
@kevinmathervideo Жыл бұрын
Brilliant explanation of a brilliant concept 😮
@maxmetpt3 жыл бұрын
This is awesome, thanks. Especially the bit at the end - great potential for mischief!
@user-zh2wf7qk9v Жыл бұрын
Getting rid of Ex's feature was just hilarious
@sorry4all2 жыл бұрын
What a simple clever algorithm. That should be on every photo editting tools
@aakashbakhle14584 жыл бұрын
Using dynamic programming to make lockscreen wallpapers would also be an apt title. I loved the teal gradients in starry night ❤️
@truefaceofevil4 жыл бұрын
These lectures are amazing. Thank you
@ancbi4 жыл бұрын
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.
@ShreyasRavibighero64 жыл бұрын
This guy sounds really similar to the talking pi at 3blue1brown
@unchaynd7266 Жыл бұрын
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!
@rineeshparai17803 жыл бұрын
Grant is a teaching genius.
@mr2octavio4 жыл бұрын
Instead of wasting my time watching a netflix show, I enjoyed learning about a fun way to make use of a triangle
@shivamjalotra79194 жыл бұрын
Not yet.
@enisten4 жыл бұрын
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
@enisten4 жыл бұрын
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.
@TheJuliaLanguage4 жыл бұрын
@@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.
@nxone99032 жыл бұрын
Fascinating
@oghry4 жыл бұрын
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
@64_bit802 жыл бұрын
i was like "hold on this guy sounds familiar" and then it clicked
@ShivaramakrishnaReddy4 жыл бұрын
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?
@alert.2723 жыл бұрын
Look at that fresh cut. Damn Grant.
@LeiosLabs4 жыл бұрын
"The great and one and only" Uh oh
@shzaizzhang44654 жыл бұрын
Wow , pretty like the exercises on Dynamic Programming in Introducton To Algorithms...
@amaurylerouxdupeyron4523 Жыл бұрын
So good 🎉
@TheBBmTV4 жыл бұрын
This is such incredibly good content, if the universities don't pick up their slack soon, youtube will just demolish them.
@TheMikebo4 жыл бұрын
You are aware that this is content from a university lecture at MIT?
@TheBBmTV3 жыл бұрын
@@TheMikebo In that case: Exceptional job MIT.
@rpavlik14 жыл бұрын
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.
@doodikun3183 жыл бұрын
thank you
@piyushsingh1784 жыл бұрын
At 22:48 why are we adding j==1 to dir while saving min item indices
@TheJuliaLanguage4 жыл бұрын
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).
@PhilBoswell4 жыл бұрын
@@TheJuliaLanguage so is the other special case, the other end of the row when there isn't a *south-east* element, handled automagically somehow?
@piyushsingh1784 жыл бұрын
@@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!!
@w1d3r754 жыл бұрын
Awesome
@joaopedrorocha56934 жыл бұрын
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.
@LOogt4 жыл бұрын
This is awesome. Thank you!
@ganeshkharad4 жыл бұрын
just awesome explanation...!!!
@eldattackkrossa98864 жыл бұрын
go grant go!
@dadireddysukumar2388 Жыл бұрын
Does solving the sub problems from top to bottom rather than from bottom top,would it give the same shortest energy path?
@ukaszszczyt49124 жыл бұрын
Thank you
@Pier_Py3 жыл бұрын
i translated your code in Python! it is great!!
@guiwenluo17744 жыл бұрын
wonderful lecture!!
@drakoumell6 ай бұрын
15:00 but dijkstra is faster, no?
@krisschobert44844 жыл бұрын
THIS IS SO DOPE!!!!!! thanks grant! cool hair too!
@danieladelodun95474 жыл бұрын
Edgy Mario looks like he's going through an emo phase.
@1e10014 жыл бұрын
yea thats why he's edgy
@arikfriedman44423 жыл бұрын
does anyone know where can I find the "original paper" he is referring to at 02:50?
@adityarjl65572 жыл бұрын
billions of people are busy watching despacito and only handful of thousand people are watching this interesting video. explains why the world is stupid.
@imranq92414 жыл бұрын
Has there been any study of seam carving with horizontal directions instead of just downward?
@SayanSamanta1234 жыл бұрын
Can you parallel this with the concept of value functions from reinforcement learning/marcov decision processes?
@gz66162 жыл бұрын
I got a question: do you re-compute energies after each seam removal?
@soejrd249783 жыл бұрын
Didn't know it was you Grant :)
@markcase9534 Жыл бұрын
Gold mine
@cicigg20454 жыл бұрын
Grant so handsome, lecture so amazing, using my whole attention to learn this material! Thanks~
@fburton84 жыл бұрын
Quality!
@skanda21862 жыл бұрын
No link to the notebook ?
@ohno55594 жыл бұрын
After removing a seam, is it best to recalculate the energy values or to continue using the original ones?
@0xDEAD_Inside3 жыл бұрын
Recalculation is the best.
@lucha62624 жыл бұрын
Where can I get started learning Julia?
@theadamabrams4 жыл бұрын
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?
@deinauge78944 жыл бұрын
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 ^^
@Dhanush-zj7mf4 жыл бұрын
Which programming did Grant used there not looks like python but almost similar to it.
@brandonbahret56324 жыл бұрын
This course uses the Julia programming language.
@keshavkasat94654 жыл бұрын
lol..read the name of the channel. I've heard this language is great for programming mathematical models.
4 жыл бұрын
Oh I missed the live class!
@shivamjalotra79193 жыл бұрын
12:56
@mirellahi51874 жыл бұрын
or a toilet brush to clean all of that yest thats been accumulating for years in the khukhus
@ahmadmoussa37714 жыл бұрын
Why hasn't this been used more as a preprocessing step for deep learning models?
@shivamjalotra79194 жыл бұрын
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.
@ahmadmoussa37714 жыл бұрын
@@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
@obi-wankenobi25914 жыл бұрын
This feature is alredy implemented in photoshop works both ways
@neve1772 жыл бұрын
It's the meme algorithm
@johnwaczak80284 жыл бұрын
Anyone catch the title of the seam-carving paper?
@franksonjohnson4 жыл бұрын
Found it: "Seam Carving for Content-Aware Image Resizing". graphics.cs.cmu.edu/courses/15-463/2012_fall/hw/proj3-seamcarving/imret.pdf
@andregn44834 жыл бұрын
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.
@microhoarray4 жыл бұрын
Is this a some kind of magic?🤏
@voxhominem4 жыл бұрын
what programming language is he using?
@henrmota3 жыл бұрын
Just one question. After eliminating one steam? We have to recalculate everything again? Because of steam pixel overlap.
@estivale81933 жыл бұрын
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.
@henrmota3 жыл бұрын
@@estivale8193 Thanks, because I am trying to implement this in the web with the gpu support. But this is a very particular calculation.
@Ganondurk4 жыл бұрын
Content aware scaaaaaalle
@echolee6014 жыл бұрын
Cool!
@mingshey3 ай бұрын
26:54 Creepy, he’s still holding the hand of his vanished ex-girl friend!
@DjNarda4 жыл бұрын
Is the full course getting uploaded?
@TheJuliaLanguage4 жыл бұрын
yes it will be. you can bookmark mitmath.github.io/18S191/Fall20/ to keep tabs. Schedule is on the front page
@luanmagioli81083 жыл бұрын
What is the animations software?
@bigmistqke2 жыл бұрын
Manim, 3b1b's custom software
@luanmagioli81082 жыл бұрын
Thanks!!!!! 🤝🏼
@silberlinie4 жыл бұрын
Photoshop can do it perfectly well. It’s called content preserving scaling
3 жыл бұрын
Probab photoshop does this way as well
@herohamp23 жыл бұрын
Where do I know his voice from?
@MusicEngineeer3 жыл бұрын
3blue1brown
@neoqueto4 жыл бұрын
I'm not a programmer but seam duplication with interpolation should also be easily doable?
@turtles-qt3ry4 жыл бұрын
Other profs: 200 views Grant: 1.6k views
@wacesferpit4 жыл бұрын
I mean, isn't this already a thing anyway? Content Aware Scaling
@aniksamiurrahman63654 жыл бұрын
But why did Julia drop OpenCL support?
@justforfun22384 жыл бұрын
Is he the 3b1b guy?
@Dezomm4 жыл бұрын
yes he is!
@noninvasive_rectal_probe89903 жыл бұрын
LOVE GRANT LOVE GRANT LOVE GRANT LOVE GRANT I AM DEEPLY DEPRESSED THAT HE WILL DIE