Iterative Closest Point (ICP)

Iterative Closest Point (ICP) - Computerphile

Рет қаралды 134,772

2 жыл бұрын

You've scanned a room or object and now you have lots of discrete scans you want to fit together. Dr Mike Pound explains how the Iterative Closest Point Algorithm is used.
this video was originally titled "Joining Point Cloud Scans" and was renamed for clarity Feb 2023
Stanford graphics resources: graphics.stanford.edu/data/3Ds...
Mesh Lab:
www.meshlab.net/
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

Пікірлер: 248

@tapiomakinen 5 ай бұрын

The problem I have with Dr Mike's videos is that whenever I come here to learn about a specific thing, I end up binge watching many more of his vids, and then forget the reason I came here in the first place.

@Tarsonis42 2 жыл бұрын

That video is rather unexpected - thought the next Mike Pound video would definitely be about Log4j.

@optimal284 2 жыл бұрын

He even said on Twitter he was working on it

@franziscoschmidt 2 жыл бұрын

That has to happen

@austinnar4494 2 жыл бұрын

Usually these videos are shot in advance - not sure about Sean but I know Brady will make a trip to Nottingham and film enough for a handful of videos and then dole them out over time

@ChrisDreher 2 жыл бұрын

Finally a video on the technical aspects of Insane Clown Posse (ICP).

@ShaunHusain 2 жыл бұрын

Magnets how do they work (more sixty symbols territory, perhaps a sociology channel as well ;) )

@davidgillies620 2 жыл бұрын

Fing LIDAR; how does that work?

@mattanimation 2 жыл бұрын

whoop whoop

@kellysmith7357 2 жыл бұрын

they got the dog beats

@CoughSyrup 2 жыл бұрын

I've always had Mike Pound pegged as a Juggalo, so it's nice to have my suspicions finally confirmed.

@renhansen1246 2 жыл бұрын

Very timely :) I have just finished stitching together several hundred lidar scans of a 2 km long road tunnel for a client. I relied pretty heavily on the auto-alignment software!

@tissuepaper9962 2 жыл бұрын

I was about to say "sheesh, couldn't you just pay somebody to do all that fiddly work" and then I realized that I'm a doofus and *you're* the one being paid to do fiddly work lol.

@surbhibarnwal8431 Жыл бұрын

how did you do that

@davidgillies620 2 жыл бұрын

Singular value decomposition is one of those things that translate extremely well to GPUs. In fact, Nvidia's CUDA library has purpose-built SVD support (the cusolverDnDgesvd function in its cuSolver package).

@vladusa 2 жыл бұрын

I used that for live feeds of a self-driving simulation.

@christophertralie9311 2 жыл бұрын

Sadly, SVD is by far not the bottleneck in this algorithm because it's only an SVD of a 3x3 matrix. Actually, the real thing that needs to be sped up on the GPU is nearest neighbors search, which is a bit tougher but doable

@christophertralie9311 2 жыл бұрын

You'd have to use a parallelizable KD Tree

@FranciscoNogueira 2 жыл бұрын

Mike's videos are always pretty engaging. This one is right there near the top. Pretty cool stuff.

@willmanjm 2 жыл бұрын

I am loving these recent videos on Computer Vision! Thanks!

@maxmusterman3371 2 жыл бұрын

Pleease more of this :3 great, interesting stuff perfectly presented as always

@salah6160 4 ай бұрын

It's inspiring how you explain different computer science topics and still explain them all exceptionally well.

@Kruglord 2 жыл бұрын

This is great, I've worked as a Lidar engineer for like a decade now, and ICP is one of those tools which will just tie everything together in a nice bow.

@QuintinMassey Жыл бұрын

I had no idea you could use meshlab like that. Thank you for making this.

@andrewharrison8436 2 жыл бұрын

Enjoyed - nicely explained. Love the enthusiasm. Seems to me that it works well for the scenery but there is a whole set of other problems if there are moving components. First level difficulty a moving rigid object - say a car. Even more tricky a flexible item - say a person walking. For a real time application then more frequent scans means closest point is more likely to be the corresponding point but you have less time to process each scan - interesting trade off.

@MrJacobegg 2 жыл бұрын

The goal of ICP is to reduce the amount of error, where "error" in this context would be defined (very roughly) as the sum of squared distances between the matched pairs of points. So movement in your scene would be handled (naively) the same way as the edges of the bunny scans in his example - the algorithm will minimize the error as much as possible but eventually get to a stopping point where most of the scene points overlap nicely but there are areas of large concentrated error, corresponding to the places where there was movement. (Hopefully that was clear enough.)

@DanielDoron-lightydo Жыл бұрын

Awesome explanation and demonstration!! Love it!

@DavidMorales-xz7fn 2 жыл бұрын

I'm a simple man. If I see Dr Mike Pound in a thumbnail, I click.

@CryTyped 2 жыл бұрын

I’m currently doing my dissertation on using lidar on iphones to create 3d meshes. I’ve been watching computerphile since its inception back when i was in high school, crazy to think how far i’ve come since then

@noahzuniga 2 жыл бұрын

the legend returns

@maxdoner4528 2 жыл бұрын

Love Dr Pound

@Veptis 2 жыл бұрын

I had this video in my watch later over 3 months now. My expectation was to learn something about photogrammetry and matching pairs to build a tree and then a point cloud. I had some ideas to how it might work with projection and interaction, but that seemed a little involved. Now with the topic of doing 2D or 3D tracking in video, I always assumed the 2D example would do an extrapolated spiral search pattern for points and just find the lowest difference in the search area. But it never occured to me to see matrix tricks like SVD show up. Such a crossover. I knew that a fourier transform on a matrix (like an image) would ignore any kind of translation or rotation, so you would use it for pattern matching for example. There was an actual optical application by Huygens Optics in a video a long while ago.

@ivarkrabol 2 жыл бұрын

Hope to see a video on log4shell, when you get around to it :)

@rachel_rexxx 2 жыл бұрын

Cheeky

@AndrewWhise 2 жыл бұрын

In astronomy we often need to map arbitrary images of the night's sky to Right Ascension and Declination coordinates (called plate solving). I wonder if this algorithm is involved, using stars as the points.

@konstantinkh 2 жыл бұрын

When your points have additional attributes, such as brightness, it's often helpful to treat them as an additional dimension. Besides that, what the matching program does is probably very similar. At least, as the final step. To improve convergence, it might, for example, start with just the brightest points, and add more as it gets closer to the solution.

@xl000 Жыл бұрын

Have a look at OpenCV + Homography.

@deepakrajendra8019 2 жыл бұрын

Mike Pound's back!

@joeab10 2 жыл бұрын

Very nice explanation! You could have also shown how bad it can get by doing the wrong initial point correspondence and hitting a local minimum.

@Richardincancale 2 жыл бұрын

I thought the Utah teapot was the archetypal 3D model, never heard of the Stanford bunny!

@ufffd 2 жыл бұрын

I think Utah teapot is the classic hard surface modeling and Stanford bunny is more relevant to photogrammetry

@renegibbetnich7883 Жыл бұрын

Thank you for this little tutorial. I wouldn't have found meshlab otherwise.

@larrybud 2 жыл бұрын

I think Mike is the best presenter on this channel.

@GorrathEUNE 2 жыл бұрын

Please add the subtitles! :) I love the other videos

@KarlssonF 2 жыл бұрын

now do one about SLAM (specifically with lidar maybe), would be a very cool topic

@intelinside3334 5 ай бұрын

Thank you for this interesting video

@drawn__9999 2 жыл бұрын

This was the clearest explanation of any algorithm I've ever heard in my life.

@elliotyu6573 2 жыл бұрын

13:15 The sound effect for ICP is brilliant.

@Alive6371 2 жыл бұрын

The videos are great. Can you kindly provide with captions ?

@blueguy5588 2 жыл бұрын

Very interesting. You can see the potential for some sort of memoization as well.

@murman100 2 жыл бұрын

Very good mike

@xsoggyeggroll4966 2 жыл бұрын

im taking classses in computer assisted surgery and this couldn't have come at a better time lol

@difflocktwo 2 жыл бұрын

are you a surgeon?

@xsoggyeggroll4966 2 жыл бұрын

@@difflocktwo nope too stressful haha, i'm in grad school for biomedical engineering. but I have talked with surgeons who use registration technology with robotic assistance and it's super cool to see these concepts work in real situations

@mertakyaz5359 2 жыл бұрын

@@xsoggyeggroll4966 Do you see those applications on practical?? That seems scary 😶

@xsoggyeggroll4966 2 жыл бұрын

@@mertakyaz5359 icp is generally used to match medical images with the robots workspace and also to track tools in the workspace

@mertakyaz5359 2 жыл бұрын

@@xsoggyeggroll4966 Liked the job there. I meant have you seen open surgery with these products been using or just simulations? I was talking about seeing a surgery 😄

@TheKrankgamer 2 жыл бұрын

Crazy, I am just doing a project in the next weeks on this for university

@Dandelion_Stitches 2 жыл бұрын

MMFCL in here for this video, spreading the word for ICP! WOOP WOOP!

@simeon136 2 жыл бұрын

Our biggest scan project was around 20 Billion points. Took a while to register even on a Threadripper-based workstation. Our scanner measures 976,000 pts/sec.

@videojeroki 2 жыл бұрын

Maybe you where busy counting your points, but if you listen carefully around ~10:00 he is answering your comment

@videojeroki 2 жыл бұрын

Btw: 20billion points would take more than 230 days of non stop laser scanning (with your ~1M pts/sec laser scanner). Did you just scan the all earth or what ?!!! :D

@simeon136 2 жыл бұрын

@@videojeroki, I know how it works, scanning is a large part of my job.

@simeon136 2 жыл бұрын

@@videojeroki a zoo with a castle in the grounds. We used multiple scanners. Terrestrial lidar scanners , UAV lidar and a wearable mobile mapping unit. We also took over 40,000 61MP full frame photos which are used to texture the mesh.

@Zahlenteufel1 2 жыл бұрын

Let's all take a moment to appreciate the existence of FOSS!

@johnlasky 2 жыл бұрын

Really interesting video! Are self driving cars doing this type of mesh stitching on the fly? And if so, would adding special reflective tape to the environment help with key point localization and reduce the amount of computation its doing? (Clearly I don't know anything about this stuff)

@calciumgoodness4073 2 жыл бұрын

Can we see a video on the TOR network compromise where a bad actor is running a bunch of relays?

@dustinjames1268 2 жыл бұрын

The bad actor you speak if us the US government

@gabrielgraf2521 Жыл бұрын

man, this was pretty clear. nice what you can do with one sheet of paper XD

@ofrench560 2 жыл бұрын

Mike has a home? I thought he just lived in his office, seen in this video behind him

@drooplug 2 жыл бұрын

He appears at home only when he is on loan from the university.

@ofrench560 2 жыл бұрын

@@drooplug I see Understandable

@GilesBathgate 2 жыл бұрын

Kd Trees, would make an interesting computerphile video.

@DJCloudPirate 2 жыл бұрын

KD trees are the underappreciated workhorse of machine vision. If done properly they can be blazingly fast compared to other spatial partitioning schemes. They don't provide some of the benefits of more complex structures but for nearest neighbor searches they're tough to beat. Interestingly enough the textbook implementation of KD trees (and the ones found in open source libraries like the PCL) are not optimal. They are "pure" but in practical terms there are tricks you can play to speed them up without much work.

@ahbushnell1 2 жыл бұрын

i assume this is what is done when they stack photo's say for astronomy. That would be an interesting video.

@giant3909 2 жыл бұрын

In astrophotography they can stack up to 100 hours of data to render a galaxy

@emmanueloluga9770 2 жыл бұрын

@@giant3909 omg wow..thats a lot of data

@kittenhat7266 2 жыл бұрын

Some programs might, but others use a method called RANSAC. For star fields, it’s not too much to ask of a computer to try to “brute force” match the brightest stars in 2 images.

@keksauraisks 2 жыл бұрын

Please do a video on Log4Shell!

@SteveMacSticky 2 жыл бұрын

very interesting

@ysahillioglu 2 жыл бұрын

Check out Scale-Adaptive ICP too :)

@Ogmobot 2 жыл бұрын

This was an Advent of Code puzzle this year

@BraedenSmith 2 жыл бұрын

Feels pretty similar to k means clustering. Basically both are gradient descent on a non convex function, involving distances in N dimensions.

@YensR 2 жыл бұрын

5:40 I understand the centre of mass of the points to shift the sample - but how do you decide the rotation? Do you just move it to centre of mass, then rotate and if it gets better, you rotate it some more , until it gets worse again? Or is there a better way to do it?

@alegian7934 2 жыл бұрын

rotations are simple enough that they can be expressed as matrix multiplication. the resulting matrix will not be completely solvable because its an approximation, but SVD gets you the best solution you can get with linear algebra

@YensR 2 жыл бұрын

@@alegian7934 yes he mentions SVD later but considering its 3 dimensions my mind still boggles how this can be done so quickly. Is there anything that helps a first guess?

@alegian7934 2 жыл бұрын

I could be wrong in any of the following. But: if matrix A describes the 3d rotation, X is the matrix that contains as columns all points in one group and Y is the matrix that contains all points in the other group, we have AX=Y (approximately, remember, these cant truly be equal) so ideally if they were equal we would invert matrix X and obtain A=YX' (we found the rotation matrix) In reality X is not invertible at all but we can find its SVD that gets us as close to its inverse as possible. so we get something like A*UΣV=Y and we solve for matrix Â (an approximation of the optimal rotation). And we apply Â to X

@YensR 2 жыл бұрын

@@alegian7934 I guess that's it! This is all new to me. We did cover 3d transformations back in my degree, but not inverse, only forward. At least that's what i remember! Very interesting, will have to do some more reading before I understand this enough.

@embeddor2230 2 жыл бұрын

@alegian Can't we just do the following: 1) build a vector A out of the selected points of the first shape in respect to their center of mass: A = Σ a_i - a_center 2) build a vector B out of the selected points of the second shape also in respect to their center of mass: B = Σ b_i - b_center 3) calculate angle between the vectors?

@U014B 2 жыл бұрын

The algorithm was originally going to be called Iterative Closest Union Point, but after an inexplicable outbreak of giggle fits, the name was changed.

@julianatlas5172 2 жыл бұрын

what's wrong with that name? I'm not a ntive english speaker so I think I'm missing the joke

@U014B 2 жыл бұрын

@@julianatlas5172 Say the initials out loud.

@FloydMaxwell 2 жыл бұрын

Facial recognition algorithms must be using this as well

2 жыл бұрын

I guess you can also do some calculations in other domain, for example distance(angle) instead of cartesian x(y). It can help.

@dixie_rekd9601 2 жыл бұрын

that would be my first idea to solve this issue I guess. create a set of data describing distance and angles of a bunch of points, then find the same results in the new data. although saying that point cloud data is usually very different from scan to scan.

@qztronic 2 жыл бұрын

Can you guys explain how those spinning lidar sensor are use to create a 2d map. (in term of how the raw data that lidar received get compute by the computers and then TADA we just have a map?)

@charliebaby7065 2 жыл бұрын

OMG YES! !! THANK YOU THANK YOU (I guess my pfp gives away my enthusiasm)

@booodan 2 жыл бұрын

Please do a video on the recent log4j exploit!!

@jwrush 2 жыл бұрын

"Maybe you have an artist sculpt something and then you scan it and get a nice mesh" well, a mesh anyway. point clouds don't yield clean topology, so one almost always has to retopo the mesh

@zxuiji 2 жыл бұрын

uh, I woulda just matched just compared the distances from the relative end points and worked my way inwards, if the distance stretches or contracts to much then it's not the same object, abort and try the next object, either way you need to identify the objects in the snapshot working with, might as well just compare the results to previous results to see what has the least difference in point distances **Edit:** the process could be further optimised by skipping objects that have to big a difference in the number of points also

@MrMysterious420 2 жыл бұрын

Whoop whoop!

@guoah9 2 жыл бұрын

I discuss my masters thesis in two days and this is something i used in it. nice timing 🤣

@dariuszmyczko7615 2 жыл бұрын

Good luck on that!

@emmanueloluga9770 2 жыл бұрын

Awesome. What's your master thesis on?

@guoah9 2 жыл бұрын

@@emmanueloluga9770 I discussed it this morning, it went very well. It is on an aerial point-cloud registration algorithm designed for urban scenarios. Basically it uses both image and point-clouds features to find an initial alignment as Mike does manually in the video and then applies ICP to refine it. I used an aerial Lidar scan of my uni city and ground clouds built with photogrammetry from a goPro(which stores a lot of position metadata) .

@emmanueloluga9770 2 жыл бұрын

@@guoah9 oh wow thats very interesting and exciting work. Congratulations on that accomplishment. Is there a paper out yet

@scheimong 2 жыл бұрын

You know the guy knows what he's doing when you see the MX master

@ashlandwithouttheshd 2 жыл бұрын

The missile knows where it is, because it knows where it isn’t

@fennecinspace 2 жыл бұрын

I started working on a project involving ICP and point clouds this month LOL.

@Ecolipsy 2 жыл бұрын

Yes

@drskelebone 2 жыл бұрын

Obligatory question that will probably be answered in the next minute: Are there any physics-based/momentum-like solvers? "We've been moving kind of left-ish at two meters per second. If we assume some points are close, and some are far, where would the last set of points fall?"

@lawrencedoliveiro9104 2 жыл бұрын

Instinctive physics-undergrad answer: represent each point in 6D, being 3 spatial coordinates and 3 momentum coordinates. Then do ICP in that space?

@micmacha Ай бұрын

You mention translation and rotation, but in 3D I'm also thinking about relative scaling and skewing. I presume a generic affine transform is assumed?

@MrWarlock616 2 жыл бұрын

Please request him to talk about log4j

@gloverelaxis 2 жыл бұрын

I assume the reason ICP isn't N^2 is because computing the "centre of mass" is the same as computing an mean/average? i.e., you can just **add** to the current average/accumulator then perform a single division at the end?

@kittenhat7266 2 жыл бұрын

Yep

@Chr0nalis 2 жыл бұрын

It's in NP

@braveshine2579 2 жыл бұрын

Please add subtitle. Love from oversea.

@jonathanmain9079 2 жыл бұрын

A long shot but how important is it for it to be accurate?? Would the fast inverse square root solution work well for this?

@Primalmoon 2 жыл бұрын

Dr Pound said there would be links in the description...?

@Computerphile 2 жыл бұрын

Oh yes, sorry, bear with me! -Sean

@kapils4113 2 жыл бұрын

Sir you played an amazing role in Spiderman no way home !

@ralfoide 2 жыл бұрын

Huh? Explanation?

@keenheat3335 2 жыл бұрын

the structure of the algorithm feels kind of similar to the face id algorithm that was shown in computerphile many years ago.

@420Travesty 2 жыл бұрын

whoop whoop!

@hymen0callis 2 жыл бұрын

12:09 Where is FPFH (from PCL) or multiview registration when you need it?

@To-mos 2 жыл бұрын

What is a situation where you would already have the geometry from a point cloud and need to overlap it like he's demonstrating. From what I've seen protogrammatry and point cloud to mesh software already aligns the points before even doing a geometry pass.

@antivanti 2 жыл бұрын

Whooo whoop

@10lauset 2 жыл бұрын

Is this somewhat like 'persistence of vision'?

@RobinHagg 2 жыл бұрын

Looks like this would be used in fingerprint Scan or qr code scan maybe.

@kas-lw7xz 2 жыл бұрын

Wait, you can get out of your office 0.0 awesome!

@MathTravels 2 жыл бұрын

Whoop Whoop!

@nyscersul42 2 жыл бұрын

Hehe i just figured out how to get a perfect pair to start :P

@MartinTowell 2 жыл бұрын

16:14 - "you can put the links in the description" -- is it possible to put the links in the description, please?

@pierreabbat6157 2 жыл бұрын

A couple of applications of this: 1. You have a lidar scan of terrain that includes woods, which has no color but has a few points on the forest floor, and a photogrammetric scan of the same terrain, which has color but no ground points. You align them and color the lidar points. (At least PerfectTIN, the program I wrote to make a TIN of point clouds, completely ignores color.) 2. You have a drone with a 32-head laser scanner. You fly it between two buildings over pavement and get 32 point clouds, one from each head. You align them and determine the calibration so that the point cloud you get from putting all 32 heads together is accurate.

@AlanCanon2222 2 жыл бұрын

Speaking as a grown up kid from the Commodore 64 days, may I just say, the kids are all right. You want self driving cars that save babies automatically? Let this up and coming generation design them.

@Ceelvain 2 жыл бұрын

This algorithm has a really strong taste of K-Means. Are they related in some way?

@Viniter 2 жыл бұрын

Are you going to make a video on the Log4j exploit?

@MoritzvonSchweinitz 2 жыл бұрын

But I think you are skipping over the main problem: how do the LIDAR scanners do the job of identifying common points that you did manually in an automated way?

@jonmackenzie 2 жыл бұрын

i would guess that because of the high scanning frequency the points are already going to be pretty well aligned. each consecutive scan will be pretty similar to the last

@TheNonXtreme 2 жыл бұрын

Probably with the help of other sensor data. For example, wheeled robot can take the encoder reading at the wheel to estimate the change in direction and position of the lidar sensor itself between each lidar scan. This data can be used to first align the point clouds closely together enough before doing the ICP.

@Meoiswa 2 жыл бұрын

If you know the exact location of your camera and lidar, you can map lidar points to camera pixels, then use strategies like edge detection or color feature isolation to tag points.

@tissuepaper9962 2 жыл бұрын

His input was a rough guess, in any real-world application you can use ubiquitous accelerometer or GPS data to get that guess. It's just not relevant to the algorithm itself, which is the focus of the video.

@TheAudioCGMan 2 жыл бұрын

yes to above answers. it's already close, but you can improve it with inertia measurements, feature detection in the point clouds, or feature detection from some color camera