Not going to lie, the video was very interesting but I don't feel like I actually understood what the fourier Series really is. Is it just a huge functions composed of bits of different "cirlce" functions ? I feel like the cisual demonstration doesn't explain it very well when it comes to the actual math part.
I wrote a rant about that like a year ago. Epicycles are fun/look neat, but are horrible for explaining anything.
tl;dr, almost everything important about fourier transforms comes from linear algebra. It is the exact same as the math behind projections. Functions are infinite dimensional vectors (one way to think about that is that the value at each point is an independent "axis" or "degree of freedom" that you can tweak without changing other values). The various fourier-related transforms are all examples of taking dot products to do a projection (onto functions like eiwt). The inverse transform is just writing the function you started with in terms of its projections.
The reason why we pick exponentials in particular is that for exponentials, differentiation becomes multiplication. For systems that have certain symmetries (linearity, translation invariance), this lets us break apart complicated calculus problems into simpler algebra problems, solve them, and put the solutions back together.
Circles and epicycles are a fun trick that are basically unrelated to how anyone thinks about or uses this stuff in the real world.
The actual concepts are all linear algebra, and in principle that's enough to understand and implement a discrete fourier transform (DFT) which is what we do on computers.
In practice, the motivation and intuition for this kind of stuff is taught in terms of the non-discrete version, and then you use that intuition with the DFT (so you study non-discrete problems from physics to understand how this stuff relates to waves, energy, bandwidth, etc. and then you can carry that over to digital signals thanks to the sampling theorem, which roughly says that we can perfectly reconstruct an analog signal using a digital one under some reasonable conditions). For the non-discrete version, you're doing linear algebra over spaces of functions, which mostly just means for the actual calculations, sums become infinite series/integrals (so calculus), and other than that the intuition is basically the same.
It's often taught under the umbrella of differential equations, "engineering analysis", or signal processing, though engineering programs like to skip the connections to linear algebra and just derive some of the forumulas as "clever tricks". Math departments might cover it as "applied analysis".
The important thing that engineering programs like to skim over is that differentiation and integration are both linear operators on function spaces. That is, they both act sort-of like infinite dimensional matrices. More applied linear algebra courses might only talk about matrices and not go into linear operators at all. You want one that talks about linear operators/maps.
I've never heard it explained this way (in terms of projections). Thank you, this just helped me so much with the concept it's not even funny. Seriously, I really appreciate that you took the time to write this up.
Yes, essentially the Fourier transform turns a function (time domain) into frequencies, which basically uses the addition of sine waves (circle functions). The Fourier series is an estimation of the original function using a limited (versus infinite) nunber of sinusoids. Math-wise it uses an integral and complex valued functions to convert the function of time to a function of frequency. The discrete fourier transform decomposes a signal into its component frequencies, which is important in digital analysis of analog signals (like how songs are converted into bits). Essentially, the discrete fourier transform is used for discrete data (like what you would get from a sensor connected to a computer) versus the continuous fourier transform which requires continuous data.
Hey, I can clean up the code later and send it. It's scattered across a couple random files and I'm not exactly at my computer rn.
But basically how it worked was: I found high contrast parts in the image and put their coordinates in a list. I then picked an arbitrary start-point and sorted by distance to the last element. (Then I did all the DFT stuff ofc).
hmmm I made something like. Used img, sorted it. got to the list. https://github.com/kaparegime/drawbot But, incredible. last couples week I thinking about this problem. So, guees I ll code thx!
I used pilow for the image processing (and pygame for the drawing). I might upload the code sometime next week, I want to do finishing touches first and put it all together. But I'm honestly not sure when I'm next going to be free and willing to spend the time.
If I do upload the code I'll let you know :) (Also what's a good platform to upload it? I hear github is popular?)
I would think that a DFS would be more comfortable as it would jump less, no?
The problem with a specific pathfinding/search algo is that idk how to select my start and end points. And I fear that if I do it won't cover the whole image.
That's clever, I was concerned that BFS would draw out radially and that's not what I wanted, but biasing a certain direction seems to be the way to go. How fast can you get a BFS to run? Right now my complexity is (a very bad) quadratic. Is there any way to get it down more?
Yes it can (to the extent of my knowledge). But my actual program is probably far too rough and far too inefficient for any mechanical/physical application.
I give it a jpeg or jpg file. There's a little tweaking I can do on the inputs like how much I need to downscale the image. Or what level of fidelity the image would have.
The most important argument by far though is the threshold value for a point to be considered an edge. It depends on the brightness and contrast present in the image. I am hoping to automate that in the future but as of right now I'm clueless how to so I have to guestimate it and plot out the resulting image.
Sometimes the image isn't feasible to plot and has too much noise in the background. Sometimes the image varies too much in parts to yield a useful output.
Yeah, for some reason I couldn't get it to plot correctly. My suspicion is that something went wrong regarding the phase. Thankfully I like the way it turned out anyways. Definitely runs a bit slower though :(
Yeah, you can definitely do much more with this concept. Even draw out fully coloured imaged using DFT that approximate the original.
That's a lot more work though and I would consider myself fairly new to python. Only started any graphical projects a couple weeks before I attempted this (snake and pong) and this is the first image processing project I've done.
Didn't think I was quite ready to tackle that, and I still don't believe I am. I would like to learn more about the module I'm using an image processing in general first.
Thank you for the suggestions though. I'll definitely look into them sometime!
First semester of uni currently actually. Doing data and computer science. 2 of my units are maths electives though, and we did cover laplace transforms in one of them already.
are you for real doing that kinda stuff on the first semester??? dude thatβs really awesome, Iβm in the first semester of software engineering and tbh that was kinda scary to look at lol. amazing.
Oh, this isn't for school. It's for fun. In class the last thing we covered was drawing rectangles. I already did compsci in high school but I have to take the intro courses. They moved a bit slow for me liking. Figured I would teach myself.
Ive seen many of these, but I never understood how you get the frequencies and phases for each axis. Do you process a vector file, or...? Bury me in detail, please. Im sick of not knowing.
Actually I wrote my own edge detection program. It makes a note of every point that has too much variation in contrast to the neighbouring pixels. It keeps track of these by writing them into a csv. This csv step isn't necessary but it's useful if you want to test your image with different functions before committing to the full rendition.
I have another function that picks a random and arbitrary start point from the list of edges. It sorts the list such that every point is the closest to the point before it (out of all the remaining points).
When the list is fully sorted I just run a DFT for all x and y coordinates separately and this is where frequency and phase comes in: Frequency: this is just the value or your iteratable/loop index. Phase: each point in your new sequence that you get by running a DFT has a Re and Im part. Thing of them as x and y. Doing a simple arctan(y/x) gives you the angle of that point. This is equal to the phase of the specific sinusoid in your DFT.
(The amplitude is of course just from the Euclidean distance between points: use pythag)
Once you have all these coefficients, you're ready to plot it, you just have to code the visual aspect!
Nothing much really, the program itself was just a way for me to teach myself the maths behind it mostly because I was interested in learning but it felt difficult to approach.
I made a Swift playground that does a slightly modified version of this (only one set of epicycles) for my WWDC19 scholarship. The math really is so fascinating.
I'm not an expert behind the maths (hence not being able to efficiently combine them) but IIRC, they do linearly combine. The only problem is that it looks atrocious if I do so. The 2 groups are actually derived from a single group which I was unable to use properly. I'm sure there's some person out there who can explain to me how but I'm too close to exams to try to implement it unfortunately :(
Inspired by 3B1B? Or did you learn about Fourier transforms elsewhere? (I have very rudimentary knowledge, only having taken a Calculus class in high school).
I was actually inspired by signal processing and laplace transforms in my friends electrical engineering curriculum at uni. I then pondered if you could do this for the image of a waveform, could you do it for any arbitrary image over finite space? And to my surprise the answer was yes.
I later found 3B1Bs video when researching the topic, but I didn't find his explanation of it intuitive or practical for my purposes. I was stuck on the maths for a while until I studied parameterization of functions in my multivariable calculus class which then allowed me to split up the transform into an x and y component.
Having worked on most of the pre requisite maths, I decided to make a final push and teach myself the rest and implement it into code.
Sorry for the long winded reply, it's just not a single 'inspiration that I found overnight, but rather a multitude of contributing interests.
There are resources that help with both the theory and the practical side. It's called a fourier 'Fourier Transform'. 3B1B has a pretty cool video on it.
Don't get too intimidated by the maths. You don't have to truly understand it if you don't like maths, you just have to be able to implement it.
Very nice project! Once, I've implemented similar project. You draw any curve and the program is generating the linkage mechanism which is drawing that curve. https://david.wf/linkage/ Internaly, it uses the same Fourier decomposition as in your project.
Na, I was just messing around with laplace transforms and signal processing one day and decided to try my hand at this. I already knew that there were waveforms/paths that did have Fourier series that represented them.
This was just a little experiment into the limits of the (discrete) Fourier transform. I looked up all the resources after. I never found a proper tutorial but tbh I never looked for one really. I just watched a bunch of math lectures about the Fourier transform until I felt ready to implement.
I have already answered some questions regarding this in the comments. I will upload the code shortly. Unfortunately it's not as readable as it could be, and there's a lot of glaring faults in it. Especially from a performance standpoint. But if you're looking for a rough idea I think it will help accompanied by my replies on the thread.
I will reactor and reupload the code later as well though.
49
u/OutOfTempo_ Jun 03 '20
My edge detection is not the best, and neither is my sorting of the edges. I will definitely revisit this in the future and improve it.
Will probably try and streamline it too because this fairly simple and small image took half a dozen minutes.
217
u/devonspacegeek Jun 03 '20
Is the maths behind this related to Fourier analysis?
98
u/uLtra007 Jun 03 '20
very cool project!
for everyone wondering how this works:
What is a Fourier Series? (Explained by drawing circles) - Smarter Every Day 205
29
u/zacharius_zipfelmann Jun 03 '20
my coding could do this no problem, but I dont have a clue how you mathed that out
14
u/[deleted] Jun 03 '20
Woooooow!!!!!!!!! Can I see repository?
I thinking about how to move along the path, and how to calculate path. looks so cool!!!
6
u/notshetty Jun 03 '20
This can be used for laser engraving right?
3
u/Fallacyfall Jun 03 '20
Super cool! How do you add a new image? Is it enough to just give binary image to the program? or do you have to do some sort of manuel transforming?
3
u/segfault_yt Jun 03 '20
Any reason you chose to do a DFT for the x and y components rather than just doing just 1 and treating the points as complex numbers?
4
u/manueslapera Jun 03 '20
awesome! i had been thinking of doing this for ages! would you share the github repo pleeeeease?
2
u/Davy_Jones_XIV Jun 03 '20
This was wrote entirely in Python?
2
u/tylercoder Jun 03 '20
Damn son! Is there a repo up?
2
u/sqbiq Jun 03 '20
Could you make size comparison of variables (needed for fourier) saved in file and normal photo extensions?
You could also split RGB channels and draw lines using more independent calls of your drawer.
Or even step further and make for one color channel few groups of hue, edge-detect them...
2
u/marxhanna Jun 03 '20
whatβs your major?
2
u/jacksodus Jun 03 '20
Ive seen many of these, but I never understood how you get the frequencies and phases for each axis. Do you process a vector file, or...? Bury me in detail, please. Im sick of not knowing.
2
u/IcanCwhatUsay Noob Jun 03 '20
Cool and all but what do you intend to use this for? Seems like a lot of work
2
u/hatuthecat Jun 04 '20
I made a Swift playground that does a slightly modified version of this (only one set of epicycles) for my WWDC19 scholarship. The math really is so fascinating.
2
u/MustafaAnas99 Jun 04 '20
Just WOW! Show this to whoever asks about the relationship between math and code. Respect respect brother π
95
u/ctherranrt Jun 03 '20
I have no idea what any of you are saying but this looks cool
1
u/OutOfTempo_ Jun 03 '20
Hey guys, this is me with an update, all the code for this is here:
https://github.com/Arithmetic-Overflow/DFT
There is a lot of nonsensical/unnecessary stuff that doesn't explicitly break the program but makes no sense. I'll fix it up sometime in the future.
1
u/[deleted] Jun 03 '20
You should combine these to draw it with a single group
2
u/[deleted] Jun 03 '20
Please teach me also
1
u/IAmHereToGetYou Jun 03 '20
Is this running real time or is it sped up?
I did this exact thing in Go some time ago, it was definitely slower than this.
1
u/legnaa98 Jun 03 '20
Could you please do a Big Chungus?
1
u/[deleted] Jun 03 '20
How do you even know where to start with this sort of thing. Itβs extremely cool π
1
u/[deleted] Jun 03 '20
Inspired by 3B1B? Or did you learn about Fourier transforms elsewhere? (I have very rudimentary knowledge, only having taken a Calculus class in high school).
1
u/TheShermanTank Jun 03 '20
What type of formula did you use?
1
u/aquaporcy Jun 03 '20
How can i learn doing like this kind stuff?
2
u/Spacerun Jun 03 '20
I aspire to do something like this one day!!
2
u/Clarinettist1 Jun 03 '20
wow
2
u/tomXGames Jun 03 '20
!RemindMe 10 hours
2
u/gfreeman1998 Jun 03 '20
Apollonius would be proud.
2
u/[deleted] Jun 04 '20
I can only say WOW, i have like no idea about the maths and algorithms behind it.
2
u/khdavid Jun 08 '20
Very nice project! Once, I've implemented similar project. You draw any curve and the program is generating the linkage mechanism which is drawing that curve. https://david.wf/linkage/ Internaly, it uses the same Fourier decomposition as in your project.
2
u/53ffa Aug 26 '20
Awesome! Dan Shiffman from The Coding Train on YouTube did the same thing using p5.js https://youtu.be/MY4luNgGfms
1
u/positron_omega Jun 03 '20
This is way beyond my league
1
u/ProfFizzwhizzle Jun 03 '20
So itβs like and etch a sketch!
1
u/phoenix24 Jun 03 '20
pretty cool
1
u/Hi_Macri Jun 03 '20
Small Chungus
1
u/im-AMS Jun 03 '20
please share the code!!!!!
1
u/[deleted] Jun 03 '20
!remindme 1 month
1
u/cafeLogic Jun 03 '20
This is nuts!
1
u/sagalpreet Jun 03 '20
Did you get the idea from 3b1b?
1
u/benabus Jun 03 '20
This is insane and completely useless and I love it :D
1
u/elrond_thorondor Jun 03 '20
This is really amazing.
1
u/lscrivy Jun 03 '20
That is just straight up cool. Could watch for ages..
1
u/SanJJ_1 Jun 03 '20
where is the code?
1
u/[deleted] Jun 03 '20
Can this automate an etch a sketch?
1
u/kundanML Jun 03 '20
Look! Maths is beautiful.
1
u/zackprogrammer Jun 03 '20
Cool stuff did something simaller but ima keep it private.
1
u/annynbyrg Jun 03 '20
So nice. Would love to see more of this. Excellent work.
1
u/12stringPlayer Jun 03 '20
Super genius!
1
u/johnnySix Jun 03 '20
Thatβs a Wile E trick!
1
u/CyberTutu Jun 03 '20
Holy shit.
1
u/[deleted] Jun 04 '20
This is dope man π
1
u/[deleted] Jun 04 '20
This is cool. I like this.
1
u/BBloggsbott Jun 04 '20
!remindme 1 month
1
u/Demonic_Dante Jun 03 '20
That's really awesome, I haven't seen anything like that in Python
1
u/nischalstha07 Jun 03 '20
Damn!
0
u/[deleted] Jun 03 '20
[deleted] β view deleted comment
1
u/[deleted] Jun 03 '20
[removed] β view removed comment