I really appreciate how you included the "mistake + fix", rather than just the polished product (specifically the max total darkness vs max average darkness). Thanks for this video!
Using the Radon transform here would make chaining lines end-to-end pretty fast, computationally -- given a fixed starting point, the possible lines would form a 1-dimensional curve in that space that should be quite fast to scan for the next maximum.
I agree. In fact, what you could do is convert from radon space (alpha,s) to "nail space" (psi_1,psi_2). Then when searching for the next maximum don't bother searching the entire domain for the maximum, instead only search in a vertical line - since the psi_2 from a previous iteration becomes the psi_2 for the next iteration
Your old video popped into my recommendations, id already seen it so i checked if you had an update and was so pleasantly surprised that youd just made this video!
Thanks! I found one academic paper on the subject before I started which only focused on a simple least squares approach (similar to what I showed in my first video). There isn't any literature out there about using the radon transform to do string art :P
Hey Kevin, yeah, I'm trying out this new premiere feature on RUclips. Never tried it before, seemed like an interesting experiment. The video is currently available on my new Patreon if you really can't wait :)
Very cool. I suspect a good optimization for color would be to lay down the thread lines in order of lowest average darkness to highest average darkness. (instead of laying down all the red, then green, then etc, in which case the last color laid down would dominate the image). Of course, this would mean the robot would need to support multiple threads concurrently; not sure how much of a challenge that would be.
This is a very interesting idea. I'll be honest with you that I haven't fully solved the color issue. It's very complicated since order highly affects the outcome in a very nonlinear way. So far I found CMYK works quite well in a set order but I'm sure it can be improved.
@@virtually_passed The issue is string obscuring the string below it. You'd need to solve the top layer of string (in whatever colour - here, black is the top layer), subtract that from the image, and then solve the next colour layer down. ... actually, it's weirder than that. The issue is that areas obscured by the top layer are no longer 'interesting' to the layers below them - they can be anything.
Way Kewl. Occurred to me that you could take it to the next level by doing glowing "EL Wire" art, Assuming it would be an easy inversion, like just starting with a negative of the image or pattern. Controlling the point to point connections with a micro controller could generate lots of interesting visual effects. Scale might need to really large though given the added diameter of the wire.
Great video! I made my own string art last year with the help of your video and it turned out fantastic. Since then I couldn't stop thinking of extending the idea to 3 dimensions and turning a 3d model into a string cube with pins on each of the 12 edges. The idea of slicing the model into 2d planes and applying the algorithm would only have the strings as flat slices on a cube. I want the strings to be in all 3 dimensions. I would really appreciate some advice on how to go about this.
That's incredible! Great work! Ive also put some thought into 3D string art. The easiest way is to construct it out of multiple 2D layers, but I'm not a fan of this. I think you can generalize the radon transform into 3D and apply the same technique as shown in this video. The downside is that making this by hand would be very challenging, I also think a machine would struggle with this as well
Rather than the edges of a cube, maybe put a cross of nails on each face.This will give you many sets of skew lines, allowing you a number of options for string passing through the inner octahedron of the cube.
One think I like about most string art is that the endpoint of one line is the start of the next. I don't think this algorithm accounts for that right? Would be an interesting next video!
Great point! You're exactly right. To account for that you'll need a separate algorithm (that I didn't talk about yet) to get the order right. If the order doesn't match perfectly you can also wrap the string around the outskirts of the nails
@virtually_passed yeah that would work but I don't like that 'hack' haha. Maybe you could adjust the algorithm to pick the next line not as the max over the entire space but over a subspace where one of the endpoints is the same. That would work as a greedy algorithm!
@virtually_passed the algorithm should take into account both ends of the string (the beginning nail of the first line and the end nail of the last line) as possible appending positions, since there is no requirement that the lines are drawn in any particular order, it's just sufficient that they get drawn/placed at all, so they can be placed in either end.
I wonder if it is better to search the limited space for the best line starting from here, or to generate the global set of lines and then pick the order to place them. The ordering algorithm's objective function would be minimizing "wasted" movement along the outside.
past 5 month im working on same thing, I already build several different algorithm even self learning pixel/line weights during training like neural networks with different resoult. Now im wonder your approach ;p. You also metioned once about FFT method and Im very curious about that.
I also worked on this problem and was very surprised to find the first video of this series, since I had a pretty similar approach 😂 Btw, in the end I managed to make the least squares approach work (I've used non negative least squares)
@@virtually_passed its not a neaural network but its very similar i term of training session and weighting pixels/lines. For example I divide 3k strings into 20 layers (150 wire per layer, more layers mean more ram usage), each layer has its weights and after fully draw image then I decrease weights for invisible pixels so it might take another route of string. I also use defferent line score method, instead of measure average darkness then I calculate sum of difference between wire, source and destination colors and get lowest negative score (score += abs(source-wire) - abs(destination-wire)), the smaller negative score mean it will more improve the image score, any positive mean it will degrade image score, dividing it or not by pixel count of line make some different resoult, non divided preffer center image and divided preffer edges of image. I also noticed that its much better to score 'per pixel' instead of 'means' methods, 'means' methods are more blurred. I laso improve performance by precompute score for each possible line, and during draw line I update score for each line that correspond to each pixel on line (score += +abs(cdOld-cwOld) - abs(cdNew-cwNew); // it does not require to recompute whole line, just update single pixel score). Using greedy algorithm do not improve performance, but in case checking every possible line without continuity that its difference like 5s and several minutes to generate image - but it require somre pregenerate tables etc that consume more ram and generating them take some time each time I run program, its 5-7 sec but its annoing as I run it many times ;p.
This project is so cool.❤ Maybe you should run a optimization algorithm at the end to minimize the amount of string you are using. It is biginning to look a little comprehensive.
Interesting idea! String isn't an issue practically speaking (in my opinion at least). But even if you did want to minimize string, you can just terminate the iteration loop whenever a maximum number of lines have been plotted or if the difference between the radon transform of the image and the string representation is less than some threshold: p - sum of p_line < c
@@virtually_passed If I understand your method correctly, the string will sometimes go on the outside on the circle, right? Thus I was thinking to optimize the order you put down the strings suce to avoid unnecessary string on the outside. That would save string and make it faster to "print". But if you never have string on the "outside", then this makes no sense. 🙁I rewatched your older video and at ~8:50 you show that you do this in order (cause you only test lines from where you are), but in this video it seems like you pick from all possible lines and not only the lines from your courent point. But I might have misunderstood.🤷♂ Cause yes, if i understand your method correctly, you are already "optimizing" the number of crosses, by picking the strings that reduces the difference between the target and the line drawing as much as possible (per string length), as you explain at 5:20 and 6:30. Thus you are already using the optimal amount of string (on the inside) whit your given termination criteria. I would use stop if "p - sum of p_line < c or line length < maximum line length. Just to have a limit. But how to select t good value for c is probably difficult, it might change from image to image, some images might even look better with fewer strings, even though the threshold is larger. Some images might simplify very well and others not at all. In the old algorithm, it would be interesting to test if the starting point makes any difference, but I guess you could say that for all the following line too, if you start questioning if picking the best line when starting, will end up giving you the best image.
Next step - rectangular canvases. Not sure why the "radon transform' is needed if you are only interested in ψ. At a guess - it's used because there's an out-of-the-box engine to compute it in mathlab.
Nice work! After your first video i went down a similar rabbit hole and ended up with the exact same algorithm as you, but eventually realised that it essentially is the same algorithm as the greedy one. Ther must be a better solution than greedy!
You're right! My FFT algorithm avoids greedy and it's lightning fast. However the results are worse than the radon method in my opinion. I also have a sneaking suspicion that a modified inverse radon transformation could be used to solve this string art problem. That would be the holy grail. I've yet to crack that egg though :)
Yeah that would be ideal. I also thought about truncating the single line radon transforms to just the high intensity bow tie section and then solving it as a deconvolution, which would essentially be a faster approximated version of your initial optimisation algorithm, but ran in to the same binary problem. I wonder if there's a space in which the single strings are related by just a translation.
@@thisismy181 Wow!! I had the exact same idea originally. Indeed it only works if you leave it unconstrained. If you try and turn it into a constrained optimization problem it becomes too computationally heavy to be practical.
@@thisismy181 Thanks! yeah the calculations shown at 4:56 are a pretty heavy simplification. There's actually a few more steps that I didn't show for simplicity.
That's really amazing. Congratulations on explaining radon transform so smoothly. After the first video, I made research about it and had a lot of troubles understanding it. Juste wondering, how much quicker is the Radon Transform method ?
add a 3rd spatial dimension with virtual, translucent strings. then realize these could be sub-luminal laser emitters (like in the tilt-five device) in a flourescing gas instead of pins with strings.... where beams overlap they excite the gas to levels of luminosity then 🎉 you don't need a second pin, maybe see what it looks like with half a sphere, and boom, volumetric imagery baby!
You take the point of maximum rho/L of the 'normalized' Radon transform of the image because you assume that would be the line that best fits. I wonder if, for every line you wanted to add, you tried finding the next (alpha0, s0) of the line that maximizes its 'inner product' with the normalized Radon transform. In MATLAB it would be sum(rho_line .* normalized_radon). You could do that using gradient optimization taking the current maximum value of rho/L as the initial guess.
what an interesting idea! If the dot product is close to 0 then the line is orthogonal to the image (in other words, very different). I have not tried this, but you have peaked my interest! I suspect it'll be faster to do transpose(rho_line(:))*normalized_radon(:) Cool idea!
I am an undergraduate computer science student and I find this very interesting. I was wondering if you could help me to learn more about this in depth.
Thanks for your comment. I have the code available via my patreon if you want to see the finer details in MATLAB. Admittedly this video is a pretty heavy simplification
Hello, thanks for your wonderful video! I tried to create a python code using your algorithme. However, for each iteration I have to calculate the Radon Transform of the current line and it is problematic : first it is very slow, secondly if the line is drawn in diagonal, the result is not the same for a horizontal one. Is'nt it possible to calculte only one line and the extrapolate to other lines with other couple of (alpha, rho) parameters? Thanks a lot!
Hey great questions. How are you calculating p_line? Are you using an analytical formula? If so, are you calculating it using two for-loops? This can be a numerically slow way to go about it, I'd recommend array-wise multiplication and division. Then you'll be able to calculate p_line very quickly from a formula. Another thing I should confess is that the formula I showed in the video is a bit simplified. I actually used a slightly different formula which didn't make the assumption of an infinitely thin line. It's true that the lines should be rotationally invariant which means that a line which has the same s value as another line should have the same radon transform except shifted and alpha In case you're interested I have published my code on patreon :)
@virtually_passed Thanks for your answer! To calculate the Randon Transform I use a python library :p Honestly I didn't check how this fonction works, but I guess it might be optimized. Oh great for you code, I will watch it !
Hey sorry for the late reply. It's because CMYK is subtractive, meaning these colors absorb light, which is a crude but hopefully roughly accurate model of how the strings interact. I think it is possible to do it with RGB but it'll involve several tweaks to my algorithm. It turns out colour is very complicated and I'm still learning a lot about it
Question: doesn't this algorithm miss one important aspect of a physical contiguous string? I.e. the order of the points has to be such that they can be connected such that psi2 for any line is psi1 for another line except in the case of the endpoints? I imagine you could do this with a greedy search with no issues for a high enough number or lines, but it seems like it converges to some sort of assignment problem in low resolution cases or cases with highly non uniform density for various angles psi. And you'd end up with a systematically distorted image in these cases maybe?
Sorry for the late reply. Indeed in the video shown I do not specify that the nails need to be uniformly spaced. There are two approaches to solve this problem. 1) during the greedy algorithm only search for a maximum along a limited domain (this will be a sinusoid in radon space) or 2) do an interpolation afterwards. I personally prefer 2) because it's numerically easier
@@virtually_passed makes sense. I suppose if you imagine a sufficiently dense nail domain, interpolation would be great. But I mean more about the order of the lines under the assumption that the lines are one long contiguous string. So you've constrained the set of angles after interpolation to represent a graph with all nodes having even degree except the endpoints and all existing in 1 connected component, then you ask the question "what's the eulerian path from endpoint to endpoint?" And the answer (which may not be unique) defines how to wind the string IRL. If there is no eulerian path (assuming you're only allowed 1 contiguous string), I think it wouldn't be a physically possible set of lines, right?
Good question. You can model the line as a Dirac delta function. In which case, the radon transform of this yields 1/abs(sin). However, in reality the line will have some width. I've tried modelling the line with a box profile, triangular profile and oval profile, but all of the radon transforms of these profiles are very complicated and slow to implement numerically. In the end I used a mathematical hack to make the Dirac delta function have thicknesses. Does that answer your question
@@virtually_passed kind of. I was thinking that given a line, there's exactly one value for theta 1 and theta 2 where it overlaps, and for all the others values of thetas, the function in integral to compute the radon transform is 0 at almost every point Do you compute the radon transform numerically? Thanks for the video btw!
Isent this the same as calculating the intensity of all possibal line and choose the darkes possibal line to draw on? But the radon transformation is calculating it in a way that is fast insted of check all possibal lines for every line? 🤔🤔👍
@@PumpiPie With regards to your first question, yes, that is basically what i'm doing. With regards to your second question, i modelled each string as black with high transparency (you can prove that two highly transparent images overlapped on each other add in darkness). With regards to your third question, my previous video shows results using a different algorithm. But it might not be comparing apples and apples because the lines are defined slightly differently
@@virtually_passed 2 question) Compared to a real life version. Is it more realistic to add some transparency to the lines on the final piece? Or are it more realistic to use solid lines? 😀 Thanks for taking the time to answer. Will have a look on your patreon when i get vacation :) Keep up the good work :) Are there coming more videos soon?
@@PumpiPie That would depend on considerations. Mostly, how thin is your string in real life versus the size of the canvas and how high resolution is the image you are working with. If the pixels per inch isn't high enough, a solid line would not be representative, but if the resolution is too high, the it would take a really long time to calculate. He went over this issue in the first video.
So... I can find the brightest point on my transform but it doesn't correspond exactly to any possible thread. What do? I tried filtering my transform based on actually reachable threads, but then there's no need to calculate the radon of a single thread and subtract that (since the transform of the image is just a sparse matrix of points).
Once you have an ordered list of nails each described with (alpha,s) values, then you need to convert those values to Psi1,Psi2 values using the last formula I derived. Once you do that you'll find that your values will likely not correspond to a perfect equally spaced set of nails, so you'll have to do a linear interpolation. You'll also have to make an algorithm that converts all these individual disconnected lines, into something a single thread can reach. Another alternative is to perform the greedy algorithm in Psi1,Psi2 space.
I wonder what the result would be if you chose not the brightest spot in the Radon transform space, but the line which radon transform has the highest correlation to the Radon transform of the image.
great Video. Thank You. But i don't understand all of the equations completely. What did i need to run your code on my PC with my owne images? Yes i need Math lap but which version. On the web page from Math lap i can buy 1000+ different versions. Thank You
Hi! That's ok if you don't understand all the equations. My MATLAB script runs all of that for you so you don't need to know what's going on under the hood. You can download my MATLAB script on my patreon. It should run on any of the latest versions (2018b and up)
@@virtually_passed Hey I successful run your code to Create my own image. One side node Mathlab need 1 extension "Image Processing Toolbox" to run the Code. But I have one question. Where can I get the output as file? I tried to write all coordinates in to a File. The Problem that the End of Line are not the start from the next line. what did I wrong?
The FFT method that I alluded to last video was lightning fast, but the results (in my opinion) weren't as good as the results you can get using the radon method. I managed to use the FFT by boiling the problem into a convolution. More details are available at my Patreon if you like.
Some of these strings look out of place, like their contrast against surrounding areas is too high, like on the center of the face of the girl in the final image. Perhaps there's a way to combat this? Maybe something to do with the gradient of the image in a particular location, and if the string representation is similar within a certain range.
I dont think the colour version will work correctly with real strings, the colour at each point is (almost) entirely dominated by the topmost string. Unless you could choose the colour of each line section independently, rather than laying all C, then Y, etc then you could add dithering of some sort. Happy to be proven wrong though. Great video btw.
Great point! I've been struggling with modelling colored strings for a while now. Indeed order does matter. Ive found that even with CMYK and with interweaved threads there are still colours I can't perfectly recreate. The only solution is to use many more colours of thread. Not easy to implement in practice though!
Interesting example of possible extensions - non-CMYK color model, threads of different thickness, higher threads obscuring lower threads, non-circular frame - ruclips.net/video/JqnhM4iT2GU/видео.html
At the moment I model my lines as partially transparent. Although I'm still unsure if this is the best possible model for them. This is the most difficult frontier that I'm facing at the moment in string art haha
@@virtually_passed That should work for a black thread, as covering up a light background partially with black is equivalent to reducing the total brightness with some factor. But consider a white thread. In the CMYK model, it would be completely transparent - have no effect. In reality it would reduce the light passing through from the background just as much as a black thread, but then ADD it's own brightness,
@@virtually_passed What was the purpose of the partial transparency? Just antialiasing? Perhaps skip all that and compensate with higher resolution on the transformed space if it introduces aliasing? I’d model the thread as just fully opaque. I’m assuming that you can use any colorspace as long as it supports linear interpolation. That way you can use any number of colors really. And any color. But if you have multiple layers of different colors, each of them will cover the ones below. you should probably start the optimization with the top layer where they will be more relevant for the final image, and add more layers below. You could possibly use multiple layers of each color.
I really appreciate how you included the "mistake + fix", rather than just the polished product (specifically the max total darkness vs max average darkness). Thanks for this video!
Thanks for the feedback. I was really unsure about that design choice
Using the Radon transform here would make chaining lines end-to-end pretty fast, computationally -- given a fixed starting point, the possible lines would form a 1-dimensional curve in that space that should be quite fast to scan for the next maximum.
I agree. In fact, what you could do is convert from radon space (alpha,s) to "nail space" (psi_1,psi_2). Then when searching for the next maximum don't bother searching the entire domain for the maximum, instead only search in a vertical line - since the psi_2 from a previous iteration becomes the psi_2 for the next iteration
Your old video popped into my recommendations, id already seen it so i checked if you had an update and was so pleasantly surprised that youd just made this video!
Every time I see this, it blows my mind
:)
OMG, I HAVE WAITED SO LONG FOR THIS. FINALLY
same omg
I loved your previous video, pleased to see the followup showing up. I think you single handedly pushed this kind of art ahead by a huge step.
Thanks! I found one academic paper on the subject before I started which only focused on a simple least squares approach (similar to what I showed in my first video). There isn't any literature out there about using the radon transform to do string art :P
@@virtually_passedAny plans on publishing a paper on the more advanced method? Happy to take a crack at it. Super interesting concept!
Here from Another Roof, great video!
BRILLIANT!! Awesome video. I too am very hyped. Thank you for explaining string art in such an elegant way
Glad you liked it :)
I'M SO HYPED
I am super excited to watch this. I also thought it released just now... But it does so in another 24 hrs 😭
Hey Kevin, yeah, I'm trying out this new premiere feature on RUclips. Never tried it before, seemed like an interesting experiment. The video is currently available on my new Patreon if you really can't wait :)
This is REALLY cool.
thanks :)
Simply amazing.
Glad you think so!
That iterative process to place lines seems like the perfect use case for the Bend programming language.
Very cool. I suspect a good optimization for color would be to lay down the thread lines in order of lowest average darkness to highest average darkness. (instead of laying down all the red, then green, then etc, in which case the last color laid down would dominate the image). Of course, this would mean the robot would need to support multiple threads concurrently; not sure how much of a challenge that would be.
This is a very interesting idea. I'll be honest with you that I haven't fully solved the color issue. It's very complicated since order highly affects the outcome in a very nonlinear way. So far I found CMYK works quite well in a set order but I'm sure it can be improved.
@@virtually_passed The issue is string obscuring the string below it. You'd need to solve the top layer of string (in whatever colour - here, black is the top layer), subtract that from the image, and then solve the next colour layer down. ... actually, it's weirder than that. The issue is that areas obscured by the top layer are no longer 'interesting' to the layers below them - they can be anything.
Awesome!
😊
Way Kewl. Occurred to me that you could take it to the next level by doing glowing "EL Wire" art, Assuming it would be an easy inversion, like just starting with a negative of the image or pattern. Controlling the point to point connections with a micro controller could generate lots of interesting visual effects. Scale might need to really large though given the added diameter of the wire.
Great video! I made my own string art last year with the help of your video and it turned out fantastic. Since then I couldn't stop thinking of extending the idea to 3 dimensions and turning a 3d model into a string cube with pins on each of the 12 edges. The idea of slicing the model into 2d planes and applying the algorithm would only have the strings as flat slices on a cube. I want the strings to be in all 3 dimensions. I would really appreciate some advice on how to go about this.
That's incredible! Great work! Ive also put some thought into 3D string art. The easiest way is to construct it out of multiple 2D layers, but I'm not a fan of this. I think you can generalize the radon transform into 3D and apply the same technique as shown in this video. The downside is that making this by hand would be very challenging, I also think a machine would struggle with this as well
Rather than the edges of a cube, maybe put a cross of nails on each face.This will give you many sets of skew lines, allowing you a number of options for string passing through the inner octahedron of the cube.
One think I like about most string art is that the endpoint of one line is the start of the next. I don't think this algorithm accounts for that right? Would be an interesting next video!
Great point! You're exactly right. To account for that you'll need a separate algorithm (that I didn't talk about yet) to get the order right. If the order doesn't match perfectly you can also wrap the string around the outskirts of the nails
@virtually_passed yeah that would work but I don't like that 'hack' haha. Maybe you could adjust the algorithm to pick the next line not as the max over the entire space but over a subspace where one of the endpoints is the same. That would work as a greedy algorithm!
@@owendeheer5893 I like this idea :)
@virtually_passed the algorithm should take into account both ends of the string (the beginning nail of the first line and the end nail of the last line) as possible appending positions, since there is no requirement that the lines are drawn in any particular order, it's just sufficient that they get drawn/placed at all, so they can be placed in either end.
I wonder if it is better to search the limited space for the best line starting from here, or to generate the global set of lines and then pick the order to place them. The ordering algorithm's objective function would be minimizing "wasted" movement along the outside.
past 5 month im working on same thing, I already build several different algorithm even self learning pixel/line weights during training like neural networks with different resoult. Now im wonder your approach ;p. You also metioned once about FFT method and Im very curious about that.
wow that's incredible. How did the neural network method work out? I've been thinking of implementing that one myself too.
I also worked on this problem and was very surprised to find the first video of this series, since I had a pretty similar approach 😂
Btw, in the end I managed to make the least squares approach work (I've used non negative least squares)
@@virtually_passed its not a neaural network but its very similar i term of training session and weighting pixels/lines. For example I divide 3k strings into 20 layers (150 wire per layer, more layers mean more ram usage), each layer has its weights and after fully draw image then I decrease weights for invisible pixels so it might take another route of string. I also use defferent line score method, instead of measure average darkness then I calculate sum of difference between wire, source and destination colors and get lowest negative score (score += abs(source-wire) - abs(destination-wire)), the smaller negative score mean it will more improve the image score, any positive mean it will degrade image score, dividing it or not by pixel count of line make some different resoult, non divided preffer center image and divided preffer edges of image. I also noticed that its much better to score 'per pixel' instead of 'means' methods, 'means' methods are more blurred. I laso improve performance by precompute score for each possible line, and during draw line I update score for each line that correspond to each pixel on line (score += +abs(cdOld-cwOld) - abs(cdNew-cwNew); // it does not require to recompute whole line, just update single pixel score). Using greedy algorithm do not improve performance, but in case checking every possible line without continuity that its difference like 5s and several minutes to generate image - but it require somre pregenerate tables etc that consume more ram and generating them take some time each time I run program, its 5-7 sec but its annoing as I run it many times ;p.
@@virtually_passed its very strange, I wrote many things about my approaches but my comment disappear ;0
@@Dobijasek :o I'm unsure why, nothing has been flagged as spam on my end. Feel free to reply again or email me: virtuallypassed@gmail.com
:)
This project is so cool.❤
Maybe you should run a optimization algorithm at the end to minimize the amount of string you are using. It is biginning to look a little comprehensive.
Interesting idea! String isn't an issue practically speaking (in my opinion at least). But even if you did want to minimize string, you can just terminate the iteration loop whenever a maximum number of lines have been plotted or if the difference between the radon transform of the image and the string representation is less than some threshold: p - sum of p_line < c
@@virtually_passed If I understand your method correctly, the string will sometimes go on the outside on the circle, right?
Thus I was thinking to optimize the order you put down the strings suce to avoid unnecessary string on the outside. That would save string and make it faster to "print".
But if you never have string on the "outside", then this makes no sense. 🙁I rewatched your older video and at ~8:50 you show that you do this in order (cause you only test lines from where you are), but in this video it seems like you pick from all possible lines and not only the lines from your courent point. But I might have misunderstood.🤷♂
Cause yes, if i understand your method correctly, you are already "optimizing" the number of crosses, by picking the strings that reduces the difference between the target and the line drawing as much as possible (per string length), as you explain at 5:20 and 6:30. Thus you are already using the optimal amount of string (on the inside) whit your given termination criteria.
I would use stop if "p - sum of p_line < c or line length < maximum line length. Just to have a limit. But how to select t good value for c is probably difficult, it might change from image to image, some images might even look better with fewer strings, even though the threshold is larger. Some images might simplify very well and others not at all.
In the old algorithm, it would be interesting to test if the starting point makes any difference, but I guess you could say that for all the following line too, if you start questioning if picking the best line when starting, will end up giving you the best image.
Next step - rectangular canvases. Not sure why the "radon transform' is needed if you are only interested in ψ. At a guess - it's used because there's an out-of-the-box engine to compute it in mathlab.
It's because the radon transform can be calculated extremely quickly :) yep MATLAB has an inbuilt function for this.
Nice work! After your first video i went down a similar rabbit hole and ended up with the exact same algorithm as you, but eventually realised that it essentially is the same algorithm as the greedy one. Ther must be a better solution than greedy!
You're right! My FFT algorithm avoids greedy and it's lightning fast. However the results are worse than the radon method in my opinion.
I also have a sneaking suspicion that a modified inverse radon transformation could be used to solve this string art problem. That would be the holy grail. I've yet to crack that egg though :)
Yeah that would be ideal. I also thought about truncating the single line radon transforms to just the high intensity bow tie section and then solving it as a deconvolution, which would essentially be a faster approximated version of your initial optimisation algorithm, but ran in to the same binary problem. I wonder if there's a space in which the single strings are related by just a translation.
Also your images all look wayyy better than mine in general. I don't think the line profiling work you did can be understated!
@@thisismy181 Wow!! I had the exact same idea originally. Indeed it only works if you leave it unconstrained. If you try and turn it into a constrained optimization problem it becomes too computationally heavy to be practical.
@@thisismy181 Thanks! yeah the calculations shown at 4:56 are a pretty heavy simplification. There's actually a few more steps that I didn't show for simplicity.
That's really amazing. Congratulations on explaining radon transform so smoothly. After the first video, I made research about it and had a lot of troubles understanding it.
Juste wondering, how much quicker is the Radon Transform method ?
It's about 3x faster. Takes about 1 minute. Maybe a bit longer if you want a really refined image.
add a 3rd spatial dimension with virtual, translucent strings. then realize these could be sub-luminal laser emitters (like in the tilt-five device) in a flourescing gas instead of pins with strings.... where beams overlap they excite the gas to levels of luminosity then 🎉 you don't need a second pin, maybe see what it looks like with half a sphere, and boom, volumetric imagery baby!
You take the point of maximum rho/L of the 'normalized' Radon transform of the image because you assume that would be the line that best fits. I wonder if, for every line you wanted to add, you tried finding the next (alpha0, s0) of the line that maximizes its 'inner product' with the normalized Radon transform. In MATLAB it would be sum(rho_line .* normalized_radon). You could do that using gradient optimization taking the current maximum value of rho/L as the initial guess.
what an interesting idea! If the dot product is close to 0 then the line is orthogonal to the image (in other words, very different). I have not tried this, but you have peaked my interest!
I suspect it'll be faster to do transpose(rho_line(:))*normalized_radon(:)
Cool idea!
Hi this incredible well done !
I wonder how many pins were used for the harry potter example?
350 :)
@@virtually_passed Thanks ! - Wow that's a great amount.. And what width of thread did you take for consideration?
I am an undergraduate computer science student and I find this very interesting. I was wondering if you could help me to learn more about this in depth.
Thanks for your comment. I have the code available via my patreon if you want to see the finer details in MATLAB. Admittedly this video is a pretty heavy simplification
Hello, thanks for your wonderful video! I tried to create a python code using your algorithme. However, for each iteration I have to calculate the Radon Transform of the current line and it is problematic : first it is very slow, secondly if the line is drawn in diagonal, the result is not the same for a horizontal one. Is'nt it possible to calculte only one line and the extrapolate to other lines with other couple of (alpha, rho) parameters?
Thanks a lot!
Hey great questions. How are you calculating p_line? Are you using an analytical formula? If so, are you calculating it using two for-loops? This can be a numerically slow way to go about it, I'd recommend array-wise multiplication and division. Then you'll be able to calculate p_line very quickly from a formula.
Another thing I should confess is that the formula I showed in the video is a bit simplified. I actually used a slightly different formula which didn't make the assumption of an infinitely thin line.
It's true that the lines should be rotationally invariant which means that a line which has the same s value as another line should have the same radon transform except shifted and alpha
In case you're interested I have published my code on patreon :)
@virtually_passed Thanks for your answer! To calculate the Randon Transform I use a python library :p Honestly I didn't check how this fonction works, but I guess it might be optimized.
Oh great for you code, I will watch it !
This is great! Just out of curiousity, why'd you chose to use the CMY values and not the RGB? Wouldn't it work with Red, Green and Blue string?
Hey sorry for the late reply. It's because CMYK is subtractive, meaning these colors absorb light, which is a crude but hopefully roughly accurate model of how the strings interact.
I think it is possible to do it with RGB but it'll involve several tweaks to my algorithm. It turns out colour is very complicated and I'm still learning a lot about it
Question: doesn't this algorithm miss one important aspect of a physical contiguous string? I.e. the order of the points has to be such that they can be connected such that psi2 for any line is psi1 for another line except in the case of the endpoints? I imagine you could do this with a greedy search with no issues for a high enough number or lines, but it seems like it converges to some sort of assignment problem in low resolution cases or cases with highly non uniform density for various angles psi. And you'd end up with a systematically distorted image in these cases maybe?
Sorry for the late reply. Indeed in the video shown I do not specify that the nails need to be uniformly spaced. There are two approaches to solve this problem. 1) during the greedy algorithm only search for a maximum along a limited domain (this will be a sinusoid in radon space) or 2) do an interpolation afterwards. I personally prefer 2) because it's numerically easier
@@virtually_passed makes sense. I suppose if you imagine a sufficiently dense nail domain, interpolation would be great. But I mean more about the order of the lines under the assumption that the lines are one long contiguous string. So you've constrained the set of angles after interpolation to represent a graph with all nodes having even degree except the endpoints and all existing in 1 connected component, then you ask the question "what's the eulerian path from endpoint to endpoint?" And the answer (which may not be unique) defines how to wind the string IRL. If there is no eulerian path (assuming you're only allowed 1 contiguous string), I think it wouldn't be a physically possible set of lines, right?
Shouldn't the radon transform of a line be a delta distribution or something similar? Or do they have thickness?
Good question. You can model the line as a Dirac delta function. In which case, the radon transform of this yields 1/abs(sin). However, in reality the line will have some width. I've tried modelling the line with a box profile, triangular profile and oval profile, but all of the radon transforms of these profiles are very complicated and slow to implement numerically. In the end I used a mathematical hack to make the Dirac delta function have thicknesses. Does that answer your question
@@virtually_passed kind of. I was thinking that given a line, there's exactly one value for theta 1 and theta 2 where it overlaps, and for all the others values of thetas, the function in integral to compute the radon transform is 0 at almost every point
Do you compute the radon transform numerically?
Thanks for the video btw!
Isent this the same as calculating the intensity of all possibal line and choose the darkes possibal line to draw on? But the radon transformation is calculating it in a way that is fast insted of check all possibal lines for every line? 🤔🤔👍
And whan drawing the HP image. Did the lines have some transparency to it? Or are thay solid black?
Can you also post some image off results using the different algorithms on the same images? ❤
@@PumpiPie With regards to your first question, yes, that is basically what i'm doing. With regards to your second question, i modelled each string as black with high transparency (you can prove that two highly transparent images overlapped on each other add in darkness). With regards to your third question, my previous video shows results using a different algorithm. But it might not be comparing apples and apples because the lines are defined slightly differently
@@virtually_passed
2 question)
Compared to a real life version. Is it more realistic to add some transparency to the lines on the final piece? Or are it more realistic to use solid lines? 😀
Thanks for taking the time to answer. Will have a look on your patreon when i get vacation :)
Keep up the good work :)
Are there coming more videos soon?
@@PumpiPie That would depend on considerations. Mostly, how thin is your string in real life versus the size of the canvas and how high resolution is the image you are working with. If the pixels per inch isn't high enough, a solid line would not be representative, but if the resolution is too high, the it would take a really long time to calculate. He went over this issue in the first video.
the transformation between line-space and point-space reminds me the Hough transform, dont know if it's usfull here ...
So... I can find the brightest point on my transform but it doesn't correspond exactly to any possible thread. What do? I tried filtering my transform based on actually reachable threads, but then there's no need to calculate the radon of a single thread and subtract that (since the transform of the image is just a sparse matrix of points).
Once you have an ordered list of nails each described with (alpha,s) values, then you need to convert those values to Psi1,Psi2 values using the last formula I derived. Once you do that you'll find that your values will likely not correspond to a perfect equally spaced set of nails, so you'll have to do a linear interpolation. You'll also have to make an algorithm that converts all these individual disconnected lines, into something a single thread can reach.
Another alternative is to perform the greedy algorithm in Psi1,Psi2 space.
I wonder what the result would be if you chose not the brightest spot in the Radon transform space, but the line which radon transform has the highest correlation to the Radon transform of the image.
Interesting idea.
great Video. Thank You. But i don't understand all of the equations completely. What did i need to run your code on my PC with my owne images? Yes i need Math lap but which version. On the web page from Math lap i can buy 1000+ different versions.
Thank You
Hi! That's ok if you don't understand all the equations. My MATLAB script runs all of that for you so you don't need to know what's going on under the hood. You can download my MATLAB script on my patreon. It should run on any of the latest versions (2018b and up)
That means i only need the "Basic" math lab version, and i am good to go?
Is the script on your patron only for BW images or also for color ?
@@m10h20 yes. So far it's only for circular BW images. I'm currently working on perfecting my scripts for color string art and rectangular string art.
Thank you very much I will test it.
@@virtually_passed Hey I successful run your code to Create my own image. One side node Mathlab need 1 extension "Image Processing Toolbox" to run the Code.
But I have one question. Where can I get the output as file? I tried to write all coordinates in to a File. The Problem that the End of Line are not the start from the next line.
what did I wrong?
where is the fourier transform that u promised in last video ?
The FFT method that I alluded to last video was lightning fast, but the results (in my opinion) weren't as good as the results you can get using the radon method. I managed to use the FFT by boiling the problem into a convolution. More details are available at my Patreon if you like.
Some of these strings look out of place, like their contrast against surrounding areas is too high, like on the center of the face of the girl in the final image. Perhaps there's a way to combat this? Maybe something to do with the gradient of the image in a particular location, and if the string representation is similar within a certain range.
I dont think the colour version will work correctly with real strings, the colour at each point is (almost) entirely dominated by the topmost string. Unless you could choose the colour of each line section independently, rather than laying all C, then Y, etc then you could add dithering of some sort. Happy to be proven wrong though. Great video btw.
Great point! I've been struggling with modelling colored strings for a while now. Indeed order does matter. Ive found that even with CMYK and with interweaved threads there are still colours I can't perfectly recreate. The only solution is to use many more colours of thread. Not easy to implement in practice though!
Interesting example of possible extensions - non-CMYK color model, threads of different thickness, higher threads obscuring lower threads, non-circular frame - ruclips.net/video/JqnhM4iT2GU/видео.html
CMYK only works if the threads are transparent, like ink.
At the moment I model my lines as partially transparent. Although I'm still unsure if this is the best possible model for them. This is the most difficult frontier that I'm facing at the moment in string art haha
@@virtually_passed That should work for a black thread, as covering up a light background partially with black is equivalent to reducing the total brightness with some factor.
But consider a white thread. In the CMYK model, it would be completely transparent - have no effect. In reality it would reduce the light passing through from the background just as much as a black thread, but then ADD it's own brightness,
@@victorwidell9751 I really like the way you think about this. In your opinion, what do you think is the best way to model the thread?
@@virtually_passed What was the purpose of the partial transparency? Just antialiasing?
Perhaps skip all that and compensate with higher resolution on the transformed space if it introduces aliasing?
I’d model the thread as just fully opaque. I’m assuming that you can use any colorspace as long as it supports linear interpolation.
That way you can use any number of colors really. And any color.
But if you have multiple layers of different colors, each of them will cover the ones below. you should probably start the optimization with the top layer where they will be more relevant for the final image, and add more layers below.
You could possibly use multiple layers of each color.
Where is the machineeeee
I have details about that on my patreon page. Will provide more details in the near future too 🙂
8:35 WHOA, bro! We don’t use that word in this house!
Sorry I have a question about a topic (moment of inertia) you explained in a video
How to contact you?
Thanks @virtually_passed
Try emailing me: virtuallypassed@gmail.com