Iterative Closest Point (ICP) - Computerphile 

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.

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

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).

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!

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

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

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.

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

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

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

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.

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.

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

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

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

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.

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

Awesome explanation and demonstration!! Love it!

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.

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

the legend returns

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

Love Dr Pound

Mike Pound's back!

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

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

13:15 The sound effect for ICP is brilliant.

Thank you for this interesting video

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

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

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

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

Very good mike

I think Mike is the best presenter on this channel.

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

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)

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

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

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

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.

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?)

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

Kd Trees, would make an interesting computerphile video.

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

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

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?

Please do a video on Log4Shell!

This was an Advent of Code puzzle this year

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

very interesting

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

Check out Scale-Adaptive ICP too :)

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

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?

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

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.

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.

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

Facial recognition algorithms must be using this as well

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

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

Please do a video on the recent log4j exploit!!

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

"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

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

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

Is this somewhat like 'persistence of vision'?

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?

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

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

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

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?"

how did u eliminate the unwanted points form depth camera

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

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

Please request him to talk about log4j

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

Please add subtitle. Love from oversea.

Whoop whoop!

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

is this also used for 3D dental scan technology?

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

Could we get some captions please? I'm finding it very hard to make out what Dr Mike is saying...

Yes

gradient descent?

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?

No 3d scans of Lenna?

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

Video on Log4?

Use thios quite alot for game art. Photogrammetry though, so dont know if it work the same.

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

Fricking point clouds, how do they work? -- ICP

What’s does he says at 9:46 ? Singularity composition ?

How does this relate to SLAM?

why not fit a curve to each set and rotate until those curves match. translation is automatically accounted for

I wish you ran ICP without first aligning the meshes just to see what it did

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.

whoop whoop!

Is it just the lighting or does Dr. Pound have blue and green eyes?

Is that a vivarium ?