My 500-LED xmas tree got into Harvard.

Part II of everyone's favourite 500-LED xmas tree! Thanks to Jane Street. Check out their programs: janestreet.com/join-jane-stre...
Check out Ben Sparks’s campaign video on how the GeoGebra file was made! • Xmas Tree Interactive ...
And here is what you came for, the Harvard github with details on how to send me your effects as a CSV file. github.com/GSD6338/XmasTree
In short: each line of the CSV starts with a frame number and then R, G, B values (one 'column' each) for all of the LEDs in sequence. (You can see examples in the Harvard github.) Send them in by 09 January 2022 either directly on the standupmaths GitHub or email to [e-mail]
You can get my tree's coordinates in GIFT format as either a CSV:
www.dropbox.com/s/lmccfutftpl...
Or a TXT file in the old format from last year:
www.dropbox.com/s/xkb55tzdsxb...
Plus I've put my auto-correcting code from this video up on my github (along with the GIFT coordinates). github.com/standupmaths/xmast...
Thanks to all of my Patreon supporters who keep my LED habit alive. You too can help support me: / standupmaths
CORRECTIONS:
- Yes, I say "squared" twice instead of "cubed". But I was thinking "cubed". You know I was.
- Not actually "within 10%" but actually I was off by 11.8%. Close enough.
- Let me know if you spot anything else wrong!
Filming and editing by Alex Genn-Bash
Terrible code by Matt Parker
SUM Music by Howard Carter
Design by Simon Wright and Adam Robinson
MATT PARKER: Stand-up Mathematician
Website: standupmaths.com/
US book: www.penguinrandomhouse.com/bo...
UK book: mathsgear.co.uk/collections/b...

[@klam8765]

Matt is the embodiment of the motto "Why spend hours to fix it manually, when you can spend a year coding it."

[@Sauvenil]

Yeah but when you spend a year coding it, you can apply it to millions of lights on hundreds of trees and it won't take hundreds of man-hours measuring locations and entering them. (It doesn't matter if you ever actually need to do that or not.)

[@MushookieMan]

@@Sauvenil It always matters. Hard code everytime

[@vigilantcosmicpenguin8721]

@@Sauvenil But you still can't make money off of it, because it's already been patented.

[@2kevbob]

a true engineer.

[@Sauvenil]

@@MushookieMan Even with potentially millions of points and hundreds of man-hours creating them? I'd rather find a faster and more predictable way, like arranging a path for the lights to follow using CAD software so you always know the path of the lights and can figure out everything from that. Then you take that model and "map it to your tree." Kind of the opposite way to get the same results, and seems more likely if you're doing a hundred trees anyway.

[@Cyrathil]

"In theory, it cannot go wrong" The biggest clue that Matt is a mathematician and not a programmer. Bugs are the single constant in the universe.

[@onradioactivewaves]

He's well aware of "undocumented features" 🙂

[@ytbvdshrtnr]

If he's running these spreadsheets live I feel like he's opening himself to displaying a few risqué patterns, maybe some human anatomy, maybe a rickroll or two (tho that'd be hard with 500 pixels)

[@gramathy999]

I think that's the joke :P

[@joshyoung1440]

Maybe you didn't get the clear tongue-in-cheek tone of "in theory"

[@joshyoung1440]

Also weird supposition to make on a video wholly dedicated to Matt programming

[@Daryl5765]

For my own tree, I photographed in a dark room of course - but I made each LED light up pure blue, then had my code look for the reddest group of pixels. This worked out pretty well since the LED was bright enough to show up as white on the camera (So with a large red (and green) component), while all the reflections elsewhere were mostly blue (With small red components). I like your error correction technique and will definitely incorporate it into my own code - I'll happily convert to the GIFT format as well. I have mixed feelings on swapping to pre-rendered shows in CSV format: It's a great way to fix the compatibility issues you ran into with the code submitted last year, but it also means any particular CSV will only work completely as intended on the tree it was designed for. LibreOffice also can't display more than 1024 columns, while your tree requires 1501 - something I'm not sure counts as an issue since these will be programmatically generated anyways, but I'll bet *someone* out there (Without Excel) would have tried making one with spreadsheet formulas, especially considering this is *the* premier spreadsheet appreciation channel on KZbin.

[@Lodinn]

In all fairness, I wouldn't even attempt to work with such csv in an office program. Since you are coding something already to find coordinates, might as well just load it into pandas and go from there...

[@TheHuesSciTech]

Very clever, but just turning the shutter speed or gain or aperture on the camera would be a much more controllable and principled way of achieving the same thing.

[@natbroyles1814]

while a web-based application may not be ideal for working with this much data, I was able to make over 1501 columns in google sheets, so someone should still be able to make something with spreadsheet formulas w/o excel

[@Daryl5765]

@@natbroyles1814 That's encouraging to hear - given whose channel this is, I'll be very disappointed if literally nobody goes the route of making something with just spreadsheet formulas.

[@dancingfishfilms]

another downside of CSV format is it can't be dynamic (e.g., you couldn't have one that listened to the computer microphone and made a live visualisation, or one based on weather data)

[@nexaentertainment2764]

That patent notice was way more reasonable than I expected. Sounds like they're not saying you specifically infringed any patents, just that anyone who wants to maybe sell something that does this should be aware that whatever method they come up with /might/ be patented and /might/ get them into trouble. Still kinda silly to patent a method of measuring stuff, but again I was expecting some kind of patent troll, not a fairly 'innocuous' message.

[@fv9422]

It seems so vague that I am not sure it was worth it mentionning them...

[@tylisirn]

@@fv9422 It was vague because Matt chose not to list the patents or name the patent holder.

[@MorRobots]

Patent trolling isn't what it used to be. The courts have caught on to the practice and some times it's really difficult to pursue an infringement case when your patent isn't that strong and your biggest opertuntunity is an educational video creator who isn't actually selling or licensing an infringing product.

[@TheOneAndOnlyNeuromod]

Nope, given the demonstration basis of the application, the patent trolls were complete douches and should be beaten to death as being part of the problem blocking progress.

[@taliesine.8343]

@@TheOneAndOnlyNeuromod But they weren't blocking anything? How would you know they where part of the blocking progress? For all you know, this could be their first and only legal document they sent to anyone. Maybe they where wrong, but they also didn't do any harm.

[@mokapon_]

Matt: "it's not super obvious that they are out of sync with this effect" Me, who's been unable to take their eyes off that one contradictory LED in the middle since the start of the video: "oh good" :') Needless to say I am very happy that the video was all about addressing this issue! Looking forward to seeing what everyone can come up with this year! :D

[@pitchYellow2973]

same

[@SilverBullet27188]

314th like

[@namenamington]

IT'S DRIVING ME INSANE! Ooh, no, I hadn't even seen the second one, now I'm twice insane.

[@vigilantcosmicpenguin8721]

@Wotzinator I noticed 4. It was quite bothersome.

[@macblastoff7700]

Found the self-selecting group mildly on the spectrum. (Source: mildly on the spectrum)

[@AdroitConceptions]

instead of using the brightest pixel, use a base image, then look for the greatest increase in brightness, that would likely reduce the number of 'bad' pixel positions found.

[@martinm6368]

That's a good idea. It's also trivial and likely patented.

[@sillvvasensei]

And do it in a room with reduced light to reduce the amount of noise (false positives) around the tree.

[@Itsa_me_MC]

Could also predefine the shape of the tree so it ignores pixels outsides the bounds.

[@stylextv]

When you are doing this procedure in a completely dark room and your base image is basically completely black then these 2 methods will produce the same result, since the brightness of a pixel would correspond to the difference compared to the (black) base image.

[@oskarelmgren]

Reflections from obscured led's would not be resolved correctly though. Still need the distance based filtering to automatically correct stuff :)

[@trainchomp6184]

Love that this is Matt's idea of real world application of Pythagorean theorem as if this is something everyone does.

[@humanperson5122]

it’s not?

[@Loki-]

Longest gift I've ever waited for was the followup video to this.

[@KalebSmart]

When Matt turns on the colors for the wires in the graph, I was confused for a moment because everything was the same color until he said that they were red and green. Very fitting for a Christmas tree ;) curse my genes for not letting me enjoy this color combination. The idea for moving the out of bounds points was really interesting

[@kellymoses8566]

Wow, red and green are very different colors.

[@ComradeTiki]

@@kellymoses8566 But to some, when cones in the eyes are too eager, they might as well both appear yellow

[@asronome]

@@kellymoses8566 He's red/green color blind...

[@jursamaj]

You don't use one of the softwares that adjust colors for your problem?

[@divinebitter1638]

@@jursamaj how would sotware help distinguish between red and green on youtube?

[@markozagar]

Let me get this straight. The 'Organization' has developed a technology (for finding lights in 3D space or for turning them on) so incredibly good and magical and difficult, that if a few people were inspired to try their hand at the same thing, they might independently, accidentally arrive at that same, brilliant, patent-worthy solution?

[@talideon]

For better or worse, something doesn't need to be "incredibly good, magical and difficult" to get patent protection. It just has to be an invention, and for there to be no prior art in place. There are certain patentability criteria (including novelty, usefulness, and non-obviousness in the US), but the bar is surprisingly low. To be fair to the organisation in question, they were at least just alerting the existence of patents related to this, which is much better than what most such organisations would do. Also, there's nothing barring the discussion of the contents of a patent. Half the point of the things is to encourage the invention to be described, though the big problem there is that many patents are described so broadly as to be useless.

[@DEXTER3]

Is the 'organization' called twinkly?

[@clahey]

Welcome to software patents.

[@IgnatRemizov]

... El Psy Kongroo? (re: The Organization)

[@moomoocow526]

@@talideon but a patent needs to be non obvious. This method is the very first thing everyone would try to solve this problem

[@peabnuts123]

Oh no! I've just realised this video is a year old, and there's no follow-up video running the submissions on the new tree :( No pressure Matt, but I still hope to see this again some day.

[@HappyGardenOfLife]

There is. It's on his second channel. It's titled "I run untested viewer-submitted code on my 500-LED christmas tree"

[@peabnuts123]

@@HappyGardenOfLife no, that’s the original video he is referencing in this video, from Jan 2021

[@vesk4000]

Yeah I was searching for it and I never found it. Weird, I haven't seen anyone else mention that. I do hope to see it one day!

[@gama5942]

I'm so happy for your tree! mine got low grades, failed a bunch of classes, and hated being in school; he stays at Walmart during the holidays. Glad to see your tree has grown into the giant it is today!

[@Checkedbox]

I feel like the check using the brightest pixel might also be a fault with false positives from reflections. Perhaps each image needs to be compared with an all-off image, then you can subtract and select pixels with the greatest difference.

[@gizmoguyar]

Yeah, I was thinking that too. There are all sorts of checks that might help. Like making sure that the next light is not too far from the previous one.

[@akshaydalvi1534]

@@gizmoguyar he did that one

[@iminni3459]

Also, putting the tree against a dark background will probably help

[@matthewwhiteside4619]

@@akshaydalvi1534 he did that for fixing problems after the fact, but you could include a weighting while scanning the pixels, so that bright pixels a long distance away from the previous scanned light are valued less than bright pixels close to the previous light

[@dorixcraft]

Maybe take the average of the pixel coordinates in the possible zone (near the previous light) weighted by brightness ?

[@jacobwolfe3002]

10:02 Matt is giving off some big "You get a kid a present, and all they want to do is play with the box" energy

[@Anvilshock]

Matt is a cat confirmed.

[@sabastiankilgore781]

@@Anvilshock ...

[@davidfinch7418]

Inspired by this last year, I made my own, but being frustrated by the slowness of scanning, I was able to (nearly) triple the speed by setting 3 consecutive LEDs in each of Red, Green and Blue, so I was effectively scanning for 3 LED's at a time by finding the brightest point in each colour, rather than doing each individually.

[@Adskdnweotland]

Great idea

[@gorak9000]

If you also do some monte carlo runs, and just turn every pixel on, but choosing a random color from RGB CMY W for each of them, you could probably do all of the locating much faster, and all at "once", just by keeping track of which pixels were which colors in which frames. The same way you can use white noise to measure the audio response of a room, rather than doing a frequency sweep and taking a measurement at each frequency. Just take all the measurements at once, but in this case, do so with enough runs that the color sequence for each pixel is unique, so you can use that sequence to uniquely identify each pixel. If you use 7 primary colors (RGB CMY and white), how many runs do you have to do so that each pixel has like 95% chance of having a unique string of consecutive colors so that you can uniquely identify each one? That would make a good Math video!

[@kylebowles9820]

@@gorak9000 Take the number of distinguishable colors and use that as the base of the number system to flash the LEDs ID, similar to what he does in the video but not base 2, base 32 or higher hopefully. Probably just 2 pictures needed. Perhaps only 3 tree rotations and of course use "bundle adjustment" so LEDs seen in up to 6 total pictures get their locations optimized. Most importantly, turn the camera exposure way down so it doesn't get blown out!

[@hund4440]

With a binary search plus rgb it should only take sqrt( n/3) images from each camera

[@alexmcd378]

That legal document sounds like, we love your work, but we have patents vaguely related to this that we would be legally required to defend, so keep being awesome, just remind everyone to check existing patents so no one has to waste money on lawyers. Nicest legal document I've ever seen

[@mechadrake]

still has an air about it: "it would be a shame if your knecaps would burst" extrremely douchy patent trolling version sent to a man who is not even in a commercial scpace, thinly veiled as non threat. hope their coal hart will develop a crack just now

[@bmwiedemann]

I learned from a lawyer that checking out patents can be disadvanteous, because triple damages can be awarded for intentional infringement. Though, "unintentional infringement" sort of indicates that the patent is patenting something rather obvious that should not warrant a 20-year monopoly.

[@amylove1467]

Quack lawyers.

[@theaureliasys6362]

It doesn't matter how nice it is, patent law is a blight on humanity.

[@EmbeddedSorcery]

@@theaureliasys6362 There's absolutely nothing that Matt described, from the methodology of measurement, to the fact that he's working with lights in a tree, that could conceivably be *rightly* patented... This is very cordial, but also BS.

[@Crayphor]

Patent law (in the US) requires that the technology is non-obvious to someone in the associated industry. If picking the brightest pixel and using its position for the coordinates is not obvious, I don't know what is.

[@ch94086]

That doesn't mean a patent isn't issued, or it's easy to file a protest. It means you can go to court and try to convince people not in the industry it is obvious.

[@ribbonsofnight]

@@ch94086 imagine how convincing Matt Parker's videos would be if an unrelated third party were to use it as evidence.

[@KriLL325783]

Obviously the next step would be to put the tree on a rotating platform like laser scanners use, and use code to evaluate all the lights from more than 4 angles, could keep a light on and spin the tree 360 and check how far the light gets from the center of frame to tell how far it is from the center of the tree. Spinning something plugged into the mains seems like a brilliant idea to me.

[@masheroz]

Just need to oscillate +/- 180 deg.

[@sebastianjost]

You can also do this for three lights at a time by turning one on green, one red, one blue and analyse the color channels instead of just the brightness. That should speed up the process a lot.

[@Anvilshock]

Just use more cameras at once.

[@Codebreakerblue]

Using more than one camera is a problem because you'd need to either perfectly set each camera's position relative to each other, or perfectly measure each camera's position Could work though

[@KriLL325783]

@@masheroz That's no fun though, if you can get the tree spinning fast enough you could make a persistence of vision display out of it.

[@unconscious5630]

WHERES THE TREE VIDEO ;-;

[@pinionless]

YES. Where is the video. Please show us the submitions.

[@damiens4601]

Where is the video of running the new animations ?

[@alimanski7941]

An easy solution is to use the fact that each light has exactly two edges - one to each neighbour. So, the disorderly lights should be quite obvious when comparing the RGB values of each triple of lights as an outlier. The same fact can simplify locating the lights in the first stage.

[@sacwingedbatsatadbitsad4346]

That's also a good performance optimization. The lights are at a known fixed distance from each other, so you only need to check for the brightest pixel within a relatively small radius. Also reduces the maximum error quite significantly.

[@nicoberling668]

@@sacwingedbatsatadbitsad4346 This doesn't really work if you want everything to be automatic though, he used the original scan to determine the maximum distance in the first place, so you still need the "unbounded" scan to get started with your optimized scan... You could do some Bayesian stuff to start out with an unbounded distance and adjust it downwards as you go.

[@danieljensen2626]

@@sacwingedbatsatadbitsad4346 That only works if you start from a known good point though. If you start from a bad point the whole tree will be ruined.

[@607]

I can't find the January video, was it not done?

[@tagadvance]

"You can already see we've definitely got a Christmas tree." Me, being red-green colorblind: So we meet again...

[@vwem1237]

same lol

[@mausklick99]

When are you going to run the code?

[@Homoskedastic1]

You have a wonderful ability to entertain and inspire, simultaneously! I mean this is so silly from one perspective - just blinking lights on a plastic Christmas tree. But from another perspective, this is incredibly creative and ingenious! I am genuinely moved and inspired by you, Matt! Both as a lifelong student as well as an educator! Thank you for spreading and sharing your love of mathematics and learning 😊

[@JohnnieHougaardNielsen]

I'd most probably have had the leds blink when detecting the position. Looking for pulsating pixels is a lot more reliable than looking for the brightest. Camera noise and all that. Happy Yuletide!

[@1FatLittleMonkey]

IIRC from last year, he does the mapping in a dark room. The LEDs should be the only light-source and significantly brighter than genuine sensor noise. That means the false measurements are when the LED itself is obscured and a reflection _of that LED_ is visible. Hence blinking wouldn't help, since the reflection would also blink.

[@JohnnieHougaardNielsen]

@@1FatLittleMonkey Well, in this video you saw how a large part of the LEDs we just not detected anywhere close to a realistic location. This indicates that finding brightest pixel is just not a good method in practice. Reliability would likely be improved doing "quality control" of the data, like blinking and/or minimum level.

[@danieljensen2626]

I don't think camera noise is really a significant issue here, but that would help eliminate any persistent bright spots from any other light sources. You'd still have problems with possible reflections from the actual LED you're locating though.

[@__nog642]

Reflection can still cause other points to be detected if the LED is behind a small branch.

[@paulkennedy8701]

@@__nog642 In which case Johnnie's suggestion of blinking lights would not help. If the scan is done in a dark room, then the reflection would merely blink with the bulb that is blinking.

[@yaboku1686]

Really hope the follow up video happens at some point.

[@567secret]

Matt will we finally get the follow-up video?

[@IamCrusaderRUS]

12:45 Oh yes, now that you mention it, i can see some of the lights not following herd. Its not like they've been bothering me the first 12 and a half minutes of the video so much that i couldn't pay attention to whatever you've been talking about.

[@samuelzackrisson8865]

noticed it from the start

[@unvergebeneid]

Measuring active markers with multiple cameras in 3D space is an industry standard. Good luck enforcing those patents.

[@zakuraayame5091]

I have a patent on thinking; but the world stopped doing it ... I get nothing in royalties :(

[@skit555]

@@zakuraayame5091 I have patented Pi but none's paying (something about mathematicians and college students being poor)

[@charmio]

I have a patent on posting KZbin comments. The two of you owe me a thumb up in compensation.

[@Unsensitive]

Sounds like one of those overly broad patents that patent trolls love to pressure small people and organizations into settling. Or maybe it's a major corporation that has a patent on Christmas trees that do fancy light up things I've seen a lot of lately. They may have the patent, but I agree, it's probably not enforceable. What would be enforceable is a copyright on their code to do so, but to enforce that one would have to prove that they copied your code. Lighting up a Christmas tree, or 3D measurement of markers, is as you say an industry standard, and used broadly. I wish them luck should they try to enforce such a patent, and would enjoy a legal review of such a case. Also, I'm not a lawyer, nor do I play one on TV.

[@B3Band]

@@Unsensitive I doubt that very much, since Matt specifically stated that the company did not ask for the video to be taken down or for the project to stop. Without seeing the patents yourself, you can't possibly know what part of the process is patented. It's a bit small-minded to assume it's something like "tHeY pAtEnTed ChRiStMaS"

[@helanren]

What a fun project! And I love the way you explained it all, showing how much fun you have/had yourself!

[@kd7jhd]

There's something missing. A star (traditional tree topper) could be used as a reference point to set a limit on the Z coordinates for Christmas trees. I understand Matt was going for the ultimate generalization for any shape and any lights, but it seems like a missed opportunity for this theme. Awesome in so many ways! Thank you.

[@BackForwardPunch]

That untested code running on a tree video was the first of yours I saw! I’ve since read your book and bought another for a friend, and been watching the channel a while. Hoping to make some code for the tree this year! 🌲 Merry christmas

[@Sam-dn7jk]

Yes!!!! I loved every bit of watching this last year!!!

[@sadmanislam5111]

Thank You @Stand-up Maths for this great video. Love the LED lights. Merry Christmas Matt Parker. 🎄

[@randyhavard6084]

Great video, I love your enthusiasm and dedication you put into your videos. Whether it's flipping coins, rolling dance decorating a Christmas tree or calculating pi you always go to the extra mile to prove math can be fun.

[@RogueAstro85]

I watched your original tree light video when it first came out and popped up in my recommended. I never subscribed but didn't know why. A few weeks ago another video of yours popped up and I subscribed immediately and binged a good deal of your videos. I had no clue you were the same guy! You're awesome, man! Keep it up!

[@seangrand3885]

Was just rewatching the previous year's video! What a lovely gift this was Happy Christmas ☃️🌲

[@shayne7]

I watched it for the first time like last week. I ignored it the first time because I hadn't watched any other Matt videos yet

[@wiztwas]

I thought you were going to come up with a solution that found the 2 adjacent lights with the largest distance between them, the worst offenders, and calculated new "better" coordinates and updated the lights, gradually refining the model to match with observations. The initial model could have the lights randomly positioned in space as the process gradually nudges coordinates to match observations. You could keep on doing it from different angles until such time as you are happy with the model in 3d.

[@giggabiite4417]

When he had figured out which points were wrong, I thought he was going to run a re-calibration program which would light up specific lights around the tree to get the scale of the new camera POV and retake the photo's for the misaligned LED's and update the point

[@Sickdudenomnomnom]

But this way he doesn‘t have to observe the tree a million times

[@Aguila1138]

Matt, I am incredibly impressed that you managed to get all 500+ LEDs to function properly as intended on your very first try with zero mistakes. Brilliant.

[@thewhitefalcon8539]

They don't. Some of them are wrong, as you can see

[@ohno-wi1vb]

@@thewhitefalcon8539 watch the rest of the video

[@IshanPandit]

Merry Christmas Matt ❤ you're the best. Thanks for making me fall in love with mathematics again and again 💫

[@noahhorowitz2506]

This ☝️

[@TheInternetHelpdeskPlays]

Happy Christmas Matt. And thank you for all the awesome maths-ness

[@MarsCorporations]

The famous patent that allows you to "measure a distance". Its been there since ancient times. Everyone knows that.

[@BigBossBernie]

Euklidian distance or a different metric?

[@gwaptiva]

Unfortunately, the US Patent Office doesn't take "prior art" into account very much...

[@Sillimant_]

It's American, intelligence doesn't apply

[@DEtchells]

@@gwaptiva A lot of prior art does get missed; that’s where patent attorneys and IP consultants like me get to earn their money :-) In fairness to the USPTO, it can take a *lot* of effort to smoke out all the potentially relevant prior art. It’s not necessarily described in obviously related patents; you’ll often find it hiding in the background descriptions of inventions that are only tangentially related. A lot of times it’s not in patent filings at all, but rather found in products already on the market that may practice the claimed art, that neither the patent applicant nor the patent office were aware of. For selfish reasons, I’m glad that there are lots of prior art issues; I love digging through patents and the details of their claims and tracking down prior art. It’s interesting and always a great mental workout - and pays well too :-)

[@gwaptiva]

@@DEtchells I knew I should've listened to my parents and learnt a proper job 😁

[@ajsnarr8514]

Matt: *has whole tree full of physical christmas lights he could use* "I made a model" *takes out regular lightbulbs tied together on a string* I have really appreciated many of the models he's made. Ever since that colab with Steve Mould, I think Matt has really took the advice about models to heart. This one got me though, lol

[@StraveTube]

When he pulled out those two light bulbs, my first thought was "somehow this is Steve Mould's fault."

[@malt2380]

I love how you fixed this. This is brilliant.

[@azpcox]

Very fitting for the spreadsheet CSV format. Christmas Spectral Vector format, that is.

[@1up285]

Hei, considering that the differentiations between correct an incorrect led positions were done by comparing both neighbouring leds, you could afterwards add all the neighbours of the green ones back in the green set. This would work because the neighbours would always have one correct distance(otherwise the other neighbour would not be green) and one incorrect one. Using this you can decrease the length of the red dotted lines by 2 for each line. Anyway, great video, really enjoyed it.

[@evanhoffman7995]

Yes! I was going to comment something like this myself. To see why it works, consider a long line of correct points with one incorrect one in the middle, then the same string with two consecutive incorrect points, which are close enough to each other to look correct. The two edges leading to the incorrect points would be red, while the other edges would be green. With the "all-red" strategy, you correctly identify the incorrect point when there's only one, but it doesn't identify either problem point if there's two consecutive ones (because the links would be ...-green-red-green-red-green-... which doesn't have any points that are wrong on both sides). With the "any-red" strategy, you identify three incorrect points if there's only one, or four points if there's actually two, because you get all the incorrect points, plus the two correct points that happen to border any number of incorrect points. With the "any-red-minus-borders" strategy, you would first identify the incorrect points and their neighbors, even if two incorrect points were accidentally close enough to have a green link, but then reject those border points which are likely correct, leaving only the ones which are actually incorrect. This strategy would only generate a false negative if there were three or more incorrect points in a row, which all happened to be close enough together to give two consecutive green links. Which is unlikely if they're as random as they look, and I don't think we ever see that in our data. One other shortcoming of this strategy, which I think is actually the reason we see so many long lines of corrected points, is the rate of false positives. If there is only one correct point in a line of incorrect ones, that one will have red links in both sides and be labeled as incorrect. Same with two correct points, as they only have one green link between them, neither is identifiable as a border point. You need three consecutive correct points in order to interrupt a string of incorrect ones, and I suspect there are a lot of points in this data where that doesn't happen. I expect a lot of those long lines had one or two correct ones in the middle, maybe several that weren't consecutive, that were accidentally caught up in the correction method.

[@GastonCarrera]

brillant way to solve the problem. Thanks . i love your videos.

[@lolwu7718]

Never saw your videos before, then last year youtube suggested it.... I watched & roflmoa... and sent it to bunch of friends... can't wait for take 2!

[@MH_Binky]

An extra step you could do in verifying if a bulb is correctly placed, would be to check, for any bulb that is only adjecent to one proximal bulb, if its proximal bulb is itself proximal to both of its adjacent bulbs. It would only affect a few bulbs of course, but it would be a few extra bulbs that are more accurately positioned.

[@brgebrgsen724]

Merry Christmas Matt 😁

[@FensFirewood]

Hey Matt, what’s happening with the testing code video? On the edge of my seat waiting!

[@onepiecepedia]

12:45 Got so happy when you agnowledged the lights not following the pattern issue that I was focusing on for the first10 minutes of the videos!!! Haha!! Well done mate, can't wait to see what the viewers will come up with this year!! 🎄 Oh and Merry Christmas!!

[@PaulPaulPaulson]

You know it's math and not computer graphics when the pixels are counted from the bottom

[@thorvaldspear]

Still can't comprehend why the original software guys decided it was a good idea to count from the top

[@DeanCalhoun]

well of course GIFT goes from under the tree

[@altosack]

@@thorvaldspear - Because that’s the way CRTs scan over the screen (left to right, top to bottom).

[@thorvaldspear]

@@altosack I guess that does make sense; they didn't think about it in terms of a graph, but rather like reading text.

[@jj_...]

Even a binary tree starts at the top, so you know it's not computer science either.

[@WaitingForRevolution]

Early January? It's past halfway now Matt 😩

[@tristshapez]

Loved this! Merry Christmas everyone :)

[@Markyroson]

I’ve been waiting a whole year for this!!

[@tomvleeuwen]

This reminds me of a project I helped out on when I was a student. The organizers wanted to make a huge, 3D RGB display by having a 3D matrix of LEDs with very thin wires. Turned out that there was a patent covering a 3D RGB displays, so they went with red LEDs instead. In our case, the distance between the LEDs was indeed measured by a ruler, when cutting the wires to the correct length. I can't remember which company actually had that patent, but judging from this video I guess it was the same. It was already 15 years ago so it will probably expire soon.

[@CottidaeSEA]

That honestly seems like a patent that shouldn't be able to exist. For anyone who might read this and doesn't understand why; it is far too general of an idea.

[@thorvaldspear]

@@CottidaeSEA The tragic thing is, companies are forced to make as many useless patents as possible lest they be sued into nonexistence by another company who decided to make said useless patents instead. Even if the company is "good", they are forced into the system.

[@CottidaeSEA]

@@thorvaldspear Yeah, because if they don't, someone else will. Then they have to pay loads of money. The entire patent system is flawed as it is right now.

[@millwrightrick1]

Christmas trees are by their very nature 3d objects and the practice of stringing lights on them is as old as electric lights. Prior art invalidates any patent especially as flashing bulbs are older than me. Look at 3D neon sculptures as prior art also.

[@Sauvenil]

Challenge it and force them to defend it. Bet you'd win.

[@dan339dan]

The patent thing is ridiculous. Programming Christmas tree lights can literally be a Computer Vision assignment, even with "sophisticated" methods like lens distortion correction and pin hole camera model measurements. Not to mention object tracking is literally built into Blender.

[@danieljensen2626]

The only real requirement for patents is that no one has patented it before and it isn't complete bullshit (I.e. you can't patent perpetual motion machines because they aren't real). 🤷‍♂️ Besides, I'm sure Blender contains several patented tools, that's not really a reasonable benchmark.

[@scalesconfrey5739]

@@danieljensen2626 In fairness, it would be a bit weird if an open-source project like blender contained patented tools. Good god, imagine the legal nightmares that would cause.

[@sycration]

@@scalesconfrey5739 Blender contains Intel's Embree and Nvidia's OptiX, which I am fairly sure are patented.

[@varmituofm]

Finding lights in 3d space is patent used by video game manufacturers. It's the basis for all VR and motion capture tech. This is a very simple application of a multi-billion dollar industry

[@Lodinn]

It can be, until you realize people would buy some solution letting them to do that "easily". THEN it's patentable. You can patent literally taking two measurements with a ruler and adding them together if the end goal is not completely obvious. In this case, "we want to control Christmas lights programmatically, people would actually pay for this and here's one implementation doing that" is probably what's covered.

[@eric13hill]

You have an amazing mind. It is inspiring to learn from you. It also makes me more excited about math.

[@davidarcesolano8375]

So much beauty in this video

[@rupeshmahore]

I worked as an intern at Harvard this summer and created a code to find molecular knots based on similar idea.

[@SirHackaL0t.]

27 minutes in, and it would appear that your original way of finding the lbulb by looking for the brightest point was getting other light sources. Limiting it to the brightest light source within the sphere of the length of cable would stop those from being mis picked. Let’s see if I have any idea what I’m talking about. :)

[@scottcampbell96]

Was thinking the same thing. Limiting each bulb to a sphere during the initial scan might have made the secondary grouping algorithm unnecessary.

[@sebastianjost]

But how do you know the sphere size in advance?

[@azai.mp4]

@@sebastianjost You can scan twice. One time to find the average size, and then a second scan where you take advantage of the average size you deduced.

[@splodeyferret]

Or just turn the lights off

[@Majromax]

This could give rise to an entire series of videos, really. Using potentially noisy sensor data to learn things about the real world has... obvious applications. Matt could go so far as to talk about Kalman filters applied with the original pixel data.

[@harvestkitty]

I look forward to seeing this year's version!

[@Hyperboid]

Your running code video actually introduced me to this channel.

[@Hexcede]

A consistent way to scan the tree without nearly as much error would be to take a snapshot before any lights change. Then for each voxel you can cycle between full red, take a snapshot, full green, take a snapshot, and full blue, taking a snapshot one last time, giving you three samples, which lets you account for noise or color correction issues. Then you can do a weighted average (the weight being the change in color value, or 0 if it got darker) on every pixel's XY position for your three samples and you get three possible pixel positions. Then you can do one last weighted average on the three positions, the weight being the reciprocal of the distance to the last voxel's screen position, greatly eliminating any outliers, and biasing the pixel position to be closer to the previous one.

[@owensthethird]

As someone in the patent application process, the terms non-obviousness and natural law are very applicable here.

[@coolmonkey619]

Wat

[@blindleader42]

@@coolmonkey619 He's saying it's problematical (absurd is the word that comes to my mind) that someone claims a patent on measuring the 3D coordinates of an object (natural law). And if the patent is about using photography to do so, it comes under the subject of obviousness (equally absurd).

[@gizmoguyar]

They shouldn't have been issued patents maybe, but unfortunately this happens all the time, and they can still fight in court, and it could still cost a new company millions of dollars and years of time.

[@peterkelley6344]

Passing Suggestion: the US Patent Office (and England's) and Matt Parker ought to do a cross over video on this.

[@NathanTAK]

How does it feel to be part of the problem?

[@Codewow]

1 year ago today I was introduced to this channel because of this tree... I love this.

[@WarrenGarabrandt]

This is an excellent addition to the SCU (Stand-Up Cinematic Universe). I sincerely hope you continue this tradition every year for the foreseeable future.

[@suncrasher4168]

Question regarding brightness: Last time you recommended to not go above (50, 50, 50) for large amounts of LEDs because (a) that was bright enough already and (b) your power supplies didn't manage more. Does that still apply?

[@Necrotoxin44]

This is a very good point, and rather important to anyone looking to submit an animation! Hopefully this gets answered.

[@mattmar96]

He did mention he got a new power supply. Not sure what to make of that but thought I’d mention it

[@ConnorForbes25]

Asked this in Matt's github repo and got this response from Matt: "Yes, I was running the spinning effects with a max of 50 per value but you could push to 100 if you're only using one colour (for whole-tree effects). I might try to have some control to scale brightness up or down if people's CSV effects are too bright/dim."

[@jjweger]

I was inspired last year and did a 4 foot wreath this year. The brightest pixel method gave about 10% bad points so I switched to mouse clicks and coordinates. Worked well for 200, wouldn't want to do 500 x 2 rounds. Posted a video of the animation with code linked in the description. Thanks for the idea Mr Parker and Merry Christmas!

[@Necrotoxin44]

Very nice! It's cool to see when others have taken the idea, but implemented it in their own way.

[@gorak9000]

Use color to aid in your mapping. Simplest method, turn on 3 (RGB) or 6 (RGBCMY) or 7 (just add white) LEDs in a cluster, and then in one image, you can map 7 LEDs. You know the sequence of the colors, so if one is missing or obscured, just put it in the middle between the other 2 you can see. Or you can ramp up to a monte carlo simulation where you just pick a random color (from that set) for every LED in the whole string, and turn them all on at once. Figure out how many iterations you have to do so each pixel has a string of "random" colors that uniquiely identifies it (aka pixel 1 is R B Y C C G Y Y etc in consecutive frames, and that sequence is enough to uniquely locate that pixel compared to all the others). Flash up the sets of random values, take a quick video (30 frames / second), and you should be able to map all of the LEDs pretty quickly. You can use the same interpolation trick as in my simpler example to fill in obscured pixels when you can see other pixels on either side of them. I'm sure you could come up with even more elaborate methods that would work even better, and the scanning and mapping could be really fast - just a trade off with how much code you want to write and test, vs how short you want the mapping process to be

[@gorak9000]

Also, if you have the human identify where the first pixel is, or just map that pixel individually first, that would aid a lot in using the cluster or monte carlo type solutions to converge on the solution faster. Or use individual mapping to find every 10th or 20th pixel, and then use another method to fill in the rest like a string of known colors - the longer I think about it, the more ideas I come up with :)

[@jjweger]

Realistically, manually mapping 200 lights with the mouse took about 15 minutes. Unless you find the problem itself more interesting than codingbthe animations (I did not) it is a bad trade. My bad points, unlike Mr Parker's all clustered together near the originin a little cloud. I am kind of assuming random noise in the sensor feed or a bug in the python library. Sensor noise could be overcome with a high sample rate and an exclusion algorithm but again... 15 minutes.

[@sparkymccrystaldog3039]

Happy Merry Christmas Holidays!

[@slowgan1199]

I like the Escher lithograph print you have in th centre there. Also, the video is very pleasing to watch. Be well!

[@Verlisify]

That tree video you put on the other channel was what got me to rediscover then binge your channel

[@monika.alt197]

Same

[@thomasmcd]

And now I begin to wonder to myself... " *do these lights go backwards in Antarctica?* "

[@MarceldeJong]

That acronym is absolutely perfect!

[@camerondrew9402]

I love the overlap between the coordinate issues on the Christmas tree and the geometry of the Antartican eclipses.

[@Pfooh]

It looks like you can optimize your solution for the outliers by checking each of the 3 coordinates indepently. It looks like typically only x, or y, or z is wrong, but not often 2 or 3 at the same time (since you don't get a null island).. However, you choose to ignore that information when you interpolate. Suggested: for every red point adjacent to a green, check if changing only x, xor only y, xor only z brings it within distance of the green. If so, change that coordinate and color it green. Repeat until no new greens are found. Only then resort to interpolatio for all others.

[@1FatLittleMonkey]

Each measurements plots a position on a plane, four planes in a box. By running straight, perpendicular lines through the box to see where they intersect, you get the 3d coord. Large errors should be obvious. Lights with insufficient data could be indicated at the time at the time of scanning, allowing re-measurement with a blocking branch moved out of the way.

[@Priapos93]

This would also be a great method for generating a report which could detect a systematic measurement error

[@DukeBG]

A suggestion for better coordinates. After adjusting the "wrong" points into the arithmetic progressions between the "correct" points you should run another pass through them and if their original position was close enough to the new position (within a parameter), then adjust them back and the series of neighbors accordingly (adjust the parameter for this to "look good"). This is because your process would definitely consider some of the correct points wrong if their both neighbors were wrong (or they were a run of two correct amidst the wrong ones). Maybe I would also do several runs of this adjustment. It will produce an even better coordinates - definitely with less of those very long straight lines series.

[@mikefochtman7164]

I'd add that knowing the lights are joined by physical wiring, we can add a simple test for the location of a point in relation to the previous point. If you know that there is no more than say, 10 cm between successive lights, this can be used to validate.

[@ollie3x10_8]

@@mikefochtman7164 he does this?

[@DukeBG]

@@mikefochtman7164 have you watched the video?

[@mikefochtman7164]

@@ollie3x10_8 Yeah, I posted that while watching, then I saw that Matt did that very thing, only better. Sorry.

[@BK_Ben_FTW]

Loved the other video, it was super relaxing just to watch code work or not work with you. You were knowledgeable about it, you were fine with something working or not working. You weren't looking for views or like screaming to subscribe and check out your sponsors or buy your math branded pants. Just a casual night with a friendly person. That vibe is why people rewatch TV shows over and over. It was the second time I'd seen something you made. I'm a fan now.

[@Geofft-lp5hf]

Hi Matt, love your stuff and Happy New Year to you and yours, and everyone here. 28 minutes in and all I see is the same colour lines, no tree, just a cube of connections getting more dense to the centre. One of the few times since I was told I was red-green colour-blind 35 years ago that it's become apparent.

[@kriswillems5661]

Location of light sources with cameras is done by differential imaging, not by just looking for the brightest spot. You make one image with all lights off, then an image with one light on, and you make the mathematical difference of the pixel brightness values.

[@secr0]

Waiting for the 'I turned my Christmas tree into a spreadsheet' video

[@WindsorMason]

Ahaha, that's a great title! :D

[@JohnJosefUnger]

Can we see a follow up? Interesting to see if something was built out to advance this 😊

[@Shy--Tsunami]

Please make a video explaining what you were saying when you mentioned that when you “add up every conceivable distance in a ball” I sat and thought about it for a long time and I think an explanation would be super awesome

[@suncrasher4168]

I have a question regarding the eventual running of effects: What will the refresh rate of the tree be? (i.e. how many rows of the csv will be processed per second?)

[@9cool10]

that is a fantastic quesstion, both because an answer would be handy, and because it is a sentence that now exists.

[@RFC-3514]

@@9cool10 - Actually, Google shows two previous instances of "the refresh rate of the tree".

[@danieljensen2626]

An important question! I'm guessing he went with 25fps because that's the European standard, but it would be nice to know.

[@RFC-3514]

@@danieljensen2626 - The update speed of "neopixel" (programmable RGB LED) chains is limited by the length of the chain. Typically, you need at least 30 microseconds per LED, plus 50 microseconds at the end of the chain (that's assuming there's no other processing going on and you're just pushing raw data down the wire at 800 KHz). For a 500-LED chain, that would be a maximum of about 65 fps. But I expect Matt's code lets you add a controllable delay between updates, so you can vary the speed of the effect dynamically without changing the rest of the code.

[@HillClimbTV]

From the Harvard code linked to it is 60fps

[@JoeTaber]

Funny how Matt's video is probably the best evidence to invalidate the patents on novelty and obviousness grounds.

[@bevanward8787]

Nice - love your work. Family favourite :)

[@Tepalus]

Ah yes! March, the perfect month to rewatch your Christmas videos. :D

[@AlxM96]

I'd love to see a Bézier curve connecting all the plotted LEDs. Using that can even increase the accuracy of the correction compared to straight lines

[@asj3419]

I'm a years late to the party, but in a perfect world the hanging wire would make a catenary arch, (y = a*cosh(x/a), apparently) which you can compute for any length of wire. It would be interesting to see if this method is more or less accurate for long runs of wire. Maybe something clever could be done where the average hang distance a lamp sees is somehow used.

[@DerpMuse]

Happy Crimbo Matt! I celebrated mine on the 23rd though. I bought a "Parker Calendar" and all the holidays were quote, "nearly correct." Have a great holiday, and heres to a happy new years day on Jan 3rd!

[@CaraJoani]

There were four or five times in this video that I wanted to smash the like button. You and most others usually only have one point in the video where I guffaw and cackle and hit that button. Great work, Matt. Can't wait for the next video.

[@maxswisher5476]

Fantastic! Love to see the tree again. Friendly request to please add captions or make the auto captions available! 😀

[@Bozeman42]

When you started talking about the lights being close to their neighbors, it started to feel very "advent of code". It's a Christmas themed set of code challenges that become available each day in December (like an advent calendar, get it?)

[@Priapos93]

To me, the statistics looked like they revealed some systematic error in the mapping code. It seems like it would have been worthwhile to build the error detection into the mapping process. For each of those chains of red, the system could run a program to collect a second set of data from four more images.

[@risfutile]

I wonder if it's just integer overflow. It's unlikely since integers in python are huge... but it looks so much like what you would get when an integer overflows.

[@nolanhartwick7184]

@@risfutile I'm pretty sure integers in python are as big as your RAM

[@TheEpicEraser]

@@risfutile Unless you use some old Python 2 version, integers never overflow in Python.

[@gorak9000]

I think the problem lies with going for the "brightest" pixel - if the LED is obscured from the camera, the "brightest" pixel is just some random pixel in the background somewhere if you're doing this with regular room lights on (considering the tree itself is rather dark), which I think accounts for why most of the wrongly located pixels are way off the tree, and tend to be towards the edge of the field of view.

[@risfutile]

@@gorak9000 but why would that result in so many positions having one coordinate at max value? Why would there be so many on the outer most surfaces of the bounding box?

[@thermitebanana]

That's amazing!

[@michaelmuller4356]

If you have a distribution (of distances), or more accurately two distrubtions of a real distance plus a distribution of errorous distances between the lights, in order to find a separation threshold where real distances and errorous distances can be separated with smallest error, you could create bins and plot them as a histogram, and then use for instance the OTSU-Method to automatically find the best theshold or distance between the lights.

[@landonkryger]

I wonder if you can identify the location of the LEDs faster by taking a picture with all even LEDs on, then odds. Then do all where (LED #)/2 is even/odd. Repeat 9 times, and use bitmasks to correlate/identify each LED. You'd only need to take ~80 pictures instead of 2000.

[@Houdini111]

Someone else suggested using R and G and B simultaneously to speed it up. Perhaps doing both your suggestion and that at the same time count speed it up further.

[@savagesarethebest7251]

Look up gray coding, and if you are adventurous you should look up Stanfords camera / projector reversing (do not remember the names for the projects)

[@darealpoopster]

Didn’t he do the binary coding method last year?

[@landonkryger]

@@darealpoopster He did it to find and identify his LEDs with bad coordinates, but not to calculate the coordinates in the first place.

[@alexb2997]

You'll likely run into all kinds of fun with occlusion and disambiguation with bulbs that are behind others if trying to map simultaneously like this. It's not impossible to handle, and a fun computer vision problem, but I wonder that taking lots of photos is easier if the option is available.

[@Houshalter]

I would have taken many pictures of the lights from multiple angles and just taken the median of the observed coordinates for every light. Since some lights will be obscured from some angles you probably have to just ignore observations that don't pass some threshold for brightness.

[@txikitofandango]

I love the maverick stray Parker light in the middle

[@cece_marie]

Image at 28:03 could make a nice tshirt on mathsgear? It's lovely to see how much life your tree project has taken on, and how it has inspired learning and creativity in others. I'm beginning to think you know what you're doing as a maths communicator..... kidding of course. Thanks for another great video and a happy holiday!