I reverse engineered a work of art, and this is what I learned
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 131 | |
| Author | ||
| Contributors | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/69460 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
EuroPython 202474 / 131
1
10
12
13
16
19
22
33
48
51
54
56
70
71
84
92
93
95
99
107
111
117
123
00:00
View (database)MereologyThread (computing)AlgorithmGoogolProcess (computing)WebsiteBlogComputational physicsString (computer science)Greedy algorithmString (computer science)Medical imagingTwitterPoint (geometry)Projective planeAlgorithmMaxima and minimaThread (computing)Goodness of fitGraph coloringFunction (mathematics)QuicksortFigurate numberSet (mathematics)Library (computing)Matrix (mathematics)Greedy algorithmDisk read-and-write headRight angleDigital photographyRoundness (object)Commodore VIC-20IterationNumberNichtlineares GleichungssystemOpen sourceCASE <Informatik>BitBlogClosed setRevision controlInformationTerm (mathematics)Open setFamilyImage processingComputer animationLecture/Conference
05:32
Design of experimentsAreaIterationString (computer science)Right angleQuicksortWeightComputer animation
06:06
Design of experimentsConservation of energyGraph coloringString (computer science)AreaMedical imagingQuicksortComputer animation
06:48
QuicksortMedical imagingString (computer science)Sound effectBitComputer animation
07:10
Texture mappingMachine visionDisk read-and-write headNeuroinformatikAcoustic shadowExistential quantificationAlgorithmKonturfindung
07:42
View (database)QuicksortDifferent (Kate Ryan album)Line (geometry)DivisorKonturfindungGroup actionString (computer science)Right angleSoftwareComputer animation
08:38
Cue sportsFocus (optics)BitMedical imagingExpressionKonturfindungComputer animation
09:14
Focus (optics)Medical imagingQuicksortAverageString (computer science)DistancePixelComputer animation
09:40
Focus (optics)State diagramSuccessive over-relaxationMedical imagingString (computer science)Bit
10:10
Software repositoryCAN busBinomial coefficientGEDCOMRootAbsolute valueAlgorithmComputer programmingCausalitySound effectElectronic mailing listRight angleData dictionaryDebuggerLine (geometry)IterationObject (grammar)Semiconductor memorySoftware developerCalculationPixelProfil (magazine)Centralizer and normalizerKonturfindungArray data structureCodeNumberSocial classPoisson-KlammerLibrary (computing)Point (geometry)String (computer science)Graph coloringFunctional (mathematics)ImplementationCoprocessorMultiplication signPrototypeSinc functionMathematical optimizationBitMaxima and minimaMatrix (mathematics)MathematicsLevel (video gaming)Resource allocationModule (mathematics)Medical imaging2 (number)Computer animation
14:55
Set (mathematics)Graph coloringString (computer science)Order (biology)AlgorithmNoise (electronics)BitLevel (video gaming)Right angleComputer animation
15:54
DialectGraph coloringReverse engineeringOrder (biology)Numbering schemeDifferent (Kate Ryan album)Computer animation
16:22
Graph coloringPixelCubeSphereOrder (biology)Right angleNeuroinformatikColor spaceEndliche ModelltheorieAlgorithmVirtual machineDistanceTerm (mathematics)Image resolutionCASE <Informatik>MathematicsBitParameter (computer programming)Group actionSkewnessDimensional analysisMedical imagingPoint (geometry)Green's functionConditional-access moduleSelectivity (electronic)Doubling the cubeComputer animation
19:51
Ordinary differential equationGreedy algorithmString (computer science)Goodness of fitSoftware developerMaxima and minimaPhase transition1 (number)QuicksortOrder (biology)Multiplication signResultantAlgorithmData storage deviceGraph (mathematics)AreaComputer animation
21:32
NumberFunction (mathematics)SequenceThumbnailAlgorithmPredictabilityResultantComputer animation
22:31
Wide area networkComputer animationLecture/Conference
23:06
CASE <Informatik>String (computer science)Virtual machinePoint (geometry)Graph coloringColor spaceEndliche ModelltheorieCodeSlide ruleCubeShared memoryNumbering schemeNumberMedical imagingGroup actionComputer scienceMultiplication signRun time (program lifecycle phase)Parameter (computer programming)Drag (physics)Combinational logicJava appletDrop (liquid)Lattice (group)Expert systemRepository (publishing)Programming paradigmFilm editingLevel (video gaming)Existential quantificationRight angleComputer animationPanel paintingLecture/Conference
Transcript: English(auto-generated)
00:04
Okay, this talk is about how I reverse engineered a work of art. Quick about me, you can see from the Commodore I've been in tech for somewhere around the 80s, since the 80s. Done a bunch of roles, team lead architect and so on.
00:22
I'm based out of Israel. Most of the stuff I've done was in startups. I have a family. This is my daughter. This is sort of a preview of what we're going to talk about, because that's her in strings. Okay, this is an actual canvas with strings that are stretched. And in reality, her head is much more proportional to her body.
00:43
But I hope you get the idea. Yeah. All right, so what's this talk about? Why are we here? This is about a project that I started, which was going to take a weekend. And it was indeed a six-month-long weekend.
01:00
We're going to have fun with algorithms. And we're going to talk just a bit about performance too, and about colors, since obviously this algorithm deals with images and colors. All right, how did it start? I was scrolling on Instagram. I'm more of a Twitter guy, but I was on Instagram in this case. And I saw this post about an art piece made out of strings.
01:24
Now, I'm a geek. You know, I admired the art, but of course one of the first things I thought about was, okay, how did they get the algorithm to know how to stretch these strings? And that sent me down a rabbit hole. So it starts with this Google prompt.
01:41
This is before AI and, you know, perplexity or whatever. It's just Google. But anyway, I started reading blog posts, and there are even some academic papers on how to do this. I found algorithms for black and white threads. But I couldn't find a good, like, open source algorithm
02:00
of how to do it for color images. And so I figured, you know, let's start playing around and doing that. After a few false starts, I settled on Python. Python is, you know, ideal for this kind of project. It just has the set of libraries and capabilities that make it very easy to bootstrap this sort of project.
02:23
These are the main libraries I used, which is, you know, Pillow for, if you're familiar with that, for image processing, which helped me just load an image and make it into, you know, something mathematical, a matrix. NumPy for the number crunching. And there's also OpenCV for animations,
02:40
which you're going to see in this talk. Okay, so we're going to take an image to work on. So let's choose the image. I chose to take this image. The image is Afghan Girl, a well-known image. She's actually called Sharbat Ghoula. This was taken in Afghanistan in 1984 by a photographer called Steve McCurry.
03:03
And I encourage you to go Google this image. There's an interesting story behind it. But we won't get into that. Okay, so first thing, let's try and do it in black and white right before we go crazy with color. So we're going to take a round version of it.
03:21
And we want it in black and white. And what's the whole idea here? We want to select strings that will eventually give us the image using strings. Okay, how do we choose these strings? Okay, that's the big challenge here. So the algorithm we're going to use is a greedy algorithm.
03:42
Now, what is a greedy algorithm? A greedy algorithm is, to put it in plain terms, an algorithm that does the best it can at each point, okay, just like most of us, with the information it has. Okay, and so we have iterations. Each iteration, we choose a single string from a pool of candidate strings that I randomly select.
04:02
The one with the best score, which we'll talk about, is the one that I choose. And in the end, we arrive at this local maximum. What do I mean by local maximum? It is not the perfect solution. It's not the best solution, but it's good enough, okay? And just to be clear, what's this algorithm?
04:23
Because maybe you're not, you know, what's he talking about, strings and stuff? The output of the algorithm is instructions. I want plain, clear instructions of, you know, a bunch of points on, let's say, the periphery of the canvas, and how can I stretch strings from one point to the other?
04:40
So I want instructions. All right. So I already mentioned the algorithm is selecting a bunch of black strings in this case, because we're doing it in black and white, the canvas is white, the strings are black. And for each string, we want to sort of figure out what's the best string in this iteration to stretch.
05:06
And how do we do that? We look at how close this string is to the image underneath the string, okay? And basically, that's sort of a closeness to black. So I mean, the equation is a bit scary, but it's just how close is the image to the black string?
05:23
And the image with the best score wins. Simple, right? Do it 4,000 times, and we're done. So that was my talk. Not really. So naive approach. Let's see what happens.
05:43
Not so good. That's the first iteration. So we're doing something wrong, right? We are, I guess you could say, prioritizing the black, giving it too much weight, and then we're only catching like the dark areas. So we need to do something smarter. We need to add maybe some sort of penalty.
06:01
A string that we've already, an area that we've already covered should score lower. So what we're going to do is, if you can see on the color image, the strings that we selected are sort of scratched out of the original image. And that sort of reduces the score for areas that we've covered.
06:20
Okay? Is that going to solve our problem? Okay. At least we see a face, but it's like behind some sort of curtain. It's blurred. We de-prioritized those dark areas too much.
06:42
So, you know, we did too much of a good thing. So what can we do? Let's try and be gentler or less aggressive. So before that, we were erasing entirely the string from the original image. Let's de-prioritize it just a bit less.
07:01
Okay? So now you can see the blue becomes just brighter. It doesn't become entirely white. So we're sort of looking for a cumulative effect when we select it. Okay. Now we have, you know, light and shadow. We're getting there.
07:21
You can even see textures of the veil she has around her head, but it's not sharp. It's not really great. What else can we do? Well, when something's not sharp, what can we do? We sharpen it, right? But I'm not a computer vision guy. I don't know any, like, fancy computer vision algorithms
07:42
for edge detection and stuff like that. So I built some edge detection into this software, stupid detection, okay? Basically, I said, okay, what is an edge? Let's take a line, the red line in this case, and compare, look to the left, look to the right, and compare the scores of, like, an offset.
08:03
Now, if we're in a very bright area, like on the left side, everything is bright. It's going to score more or less the same. If we're crossing a transition and all the strings are transitioning, great. It's also going to score more or less the same. But if the line is right on the edge, then to the left,
08:24
we're going to have a dramatic difference, and to the right also, hopefully. And then take that difference and, you know, convert it into some sort of factor to the score. And so see what happens with that.
08:44
So you can definitely, I think, see, I hope, the edges here, right? You can see that this, like, simple, stupid edge detection works. You can even see one of her eyes, which really pops out. And that's what we want. I mean, we want to focus the whole, like,
09:03
special quality of the images is the expression. And so let's try and focus maybe just a bit more. We're almost done with black and white. So if I have the image, let's see if I can focus on the features that interest me. How do we do that?
09:21
Well, the score I'm calculating is just like I'm, you know, counting pixels on the string and taking some sort of average of the distance of the string from the original image. And so from an average, we go to a weighted average.
09:40
See what happens now? Okay. This is it. This is an image that I would actually take an actual canvas and, you know, start stretching the string. So we've done black and white. This was my first two weekends of the six months.
10:07
Okay. So let's talk a bit about small interlude, about performance. When I got to this stage, the calculations were sometimes taking, I don't know, hours. It, like, nothing, it didn't make sense.
10:22
And why? I mean, it's just an image, right? Well, if we look at the numbers, each string is about on average 1500 pixels. We have, I'm looking at 100 different random candidates for each iteration. The edge detection thing triples the number of calculations and then I have up to 8000 iterations depending on how many I want.
10:45
That's 3.6 billion points that I need to calculate and the calculation is a bit more complex than what I discussed so far. And that's just for one color. You know, when we're going towards many colors,
11:00
if it took me half an hour initially, now it's going to take, you know, hours for a lot of colors. So I figured, yeah, I need to start looking at, like, prototyping is nice but I need to get this program to run properly. And it turns out, and this was, you know,
11:20
Python has a pretty good debugger. There were other talks today talking about that. But it's really easy to actually debug your performance. All you need to do is, in whatever program you're running, add minus module C profile and C profile will give you this list of functions that ran and you can really see what's going on.
11:43
Okay, so let's see what's going on. All right, the library I used was NumPy, okay? If there are people here who haven't heard of NumPy or don't know what it is, it's a number-crunching library. It's great since it's written with C libraries.
12:02
There is various optimizations where it uses the processor where basically the syntax is Python but we're using low-level programming and it's much faster than working with, let's say, lists or dictionaries in Python.
12:23
So I thought I was doing great, you know, I'm using NumPy. So let's look at this line of code. This is a pretty central line of code in my algorithm. It doesn't do anything really complex. It takes a matrix, takes the absolute value of the values and takes the maximum of it.
12:42
Okay, when I profiled it, I noticed that this absolute method was taking most of the time of my algorithm. This is the built-in absolute value function of Python. And so I made one small change in my program, okay?
13:03
I changed absx to np.abs which is NumPy's implementation of absolute. Now it turns out that this is a really big deal. Let's see how it affected performance. Originally, 331 seconds, yeah.
13:24
What was going on here is that I was going from NumPy to Python and back to NumPy. So you really need, when you're writing code, you really need to notice that you're using the correct methods that you're not mixing things that may cause unexpected side effects
13:44
such as copying of arrays and memory and so on. Now I am a serious developer. And serious developers when they have an x and y point do not use
14:00
arrays, right? You want to do it object-oriented. You want to be correct. You want the benefits of having a class where you can reference .x and .y and not just, you know, square brackets zero and one because like that's dirty, you know. Let's do it correctly.
14:20
So I replaced the whole code base with this data class and I was very proud of myself for doing the right thing. And the right thing cost me a 12% penalty in performance because, and this is also another thing I learned, when you work with objects there's object allocation, deallocation and so on.
14:42
And so also not great. Lesson learned here, sometimes it's okay, you know, as long as you know what you're doing and you're doing it with your eyes open to not be absolutely correct. Okay. So we were in black and white, let's go for color.
15:00
Are you ready? Yeah. More or less noise. Okay. What was I doing wrong? The algorithm is greedy, right? It selects the best string first. Now in an actual, when you actually draw the strings you want the
15:28
best string to be on top. So you can't draw it in the order in which you find the string. If the best string is the one you find first you want that last. So, and with color, unlike black strings,
15:41
which is basically a bitmap, it's either white canvas or a black string, here the order matters. The last string is going to be covered by other strings. And so I figured out, and it took me way too long, that maybe let's try drawing it in the reverse order
16:02
in which we find it. And yeah, okay, now I have regions of color. Okay, I just need to get that, you know, RGB. That's the obvious color scheme that you would use. So I tried different color schemes and I won't go into them. Nothing was working and then I said, let's use AI.
16:23
Okay? And the non-commercial term for AI, which is machine learning, right? Let's use machine learning. There's an algorithm called k-means clustering, which basically you take an image, it outputs like the most dominant colors. It groups the colors into, in this case, six colors. And this is going to solve my problem, right?
16:43
Are you ready for it? Yeah. That is also, there's a machine learning term called overfitting. And this is one example of it. The k-means was too good. So I figured, okay, I need to just choose a bunch of colors
17:05
and let's see what sticks. But how do I choose a bunch of colors? And this is a small thing about colors. We're used to talking in red, green, blue, right? RGB. And that's how computers speak about colors, right? Each pixel is actually a red, green, and blue light that turns
17:24
on and off, but it's not really human, well, not readable, but you can't reason about RGB. If I tell someone I'm going to change the color from 50% blue to 75% blue, there's no way a human could tell you what color it is. Maybe a front-end engineer, but like not a human.
17:43
And so there's no way, okay? And the other thing is I'm calculating distances between colors, which is, think about it, what is the distance between color? That's also something really weird. And you get these strange things.
18:01
This is Euclidean distance, right? That's like what you would expect in distance. And so going from black to blue, that's 255. But from blue to white, it's 360. And from black to white, 441, almost double. I was getting color skews, like the colors were all wrong. And I ended up having to normalize this color cube
18:21
into a sphere in order to get a good score. Now, in the end, in order to generate my color space, I ended up using a color model called HSV, which if you don't know about, I recommend knowing and reading up a bit about it.
18:41
This is a human-friendly color space. Okay, what do I mean by human-friendly? You still have three parameters, hue, saturation and value in this case. But you can reason about the changes. Hue changes the color. Saturation changes the liveliness. Okay? And value just changes the brightness. So I can tell you, when I tell you I'm bumping up the saturation
19:02
or taking it down, it makes sense. And changing one dimension keeps others stationary. So you can reason about the colors. I ended up taking points on the circumference of this color space. And that gave me, in this case, 64 colors. And I ran my algorithm using 64 colors.
19:23
And the next morning, I got something. I ran it in low resolution. And I saw that it worked, so I did an overnight. And this is what I got. Okay, now we have the colors. And this is looking actually pretty good now.
19:42
I think I'm ready to actually do this like with an actual canvas. There's one problem, though. These are the colors that I ended up selecting. There's the path, right? This is 6,000 strings. Like tying 6,000 strings is going to take you, well, a long time.
20:02
So I need paths. I need to be able to draw the strings, like do 30 strings in a path and only then tie them. So the path, turns out, was also, I can do a separate talk about that, don't worry, I won't. So the idea originally, whenever the greedy algorithm was also determining the path,
20:21
each time I was choosing a string, the next bunch of candidates would start out from the string I chose. Turns out that this is not good, okay? And for various reasons, it generated a local maximum like you could never skip to a more correct area.
20:40
And it wasn't working. In the end, the breakthrough was I did it in two phases. First, just, you know, whatever, choose all the best strings. And in the second phase, if you sort of put it in a, store it in a graph when you remember the order, you can sort of do a walk and select the path.
21:00
But only after you've found the best strings. Okay. Are you ready? Okay. And this is the final result of the algorithm.
21:25
But, you know, I'm a developer and developers, like good ones, do QA, right? So here's the QA. I mentioned earlier, the algorithm does, the output is instructions.
21:43
So you number your nails and then you get this sequence of go from two to 12 to 19. And after a few black thumbs and so on, you're ready to do that. And this was the final result. If you look at the animation here, you'll see this is real world.
22:00
And you'll see that it actually follows the prediction that the animation predicted. And it only took 30 hours. But it's okay, it's a hobby, I mean, you know. And so we ended up with and quite happy that this,
22:23
it made it in one piece. Thank you. These are some other works that I've done.
22:50
All right. Thanks a lot for this awesome talk. I mean, I saw you unpack it below the desk and I was like, whoa, what is that? Okay, this is going to be interesting.
23:00
And I think I've never seen anything like this before. So thanks a lot for this. We have two, no, we actually have seven minutes left for Q&A if I see this correctly. So please feel free, we've got a microphone in the middle over there. If you have some questions, feel free to just queue up and ask some questions.
23:32
Yeah, so the question was, do I have the code? Yes, I do. I even use the, like, git, so I don't get everything deleted.
23:46
But the code right now is quite complex. The number of parameters that I needed to tweak, I mentioned that it took 30 hours to actually stretch these strings. Getting the parameters right, just right,
24:01
I think took at least as long. So unfortunately, it's not like, you know, it's not a drag and drop thing. I might put it, you know, open the repository in the future, but it's not, it would be difficult to use.
24:20
Let's, there's a guy. Yeah, very impressive work. I have a background in imaging and I got really impressed with what you did. I would be happy to talk to you afterwards. Sure, I'm here. Something's true. But a question regarding choosing color model, and this might be stepping on it too,
24:42
because it's always when you found a solution, it's, you found something. But did you look a lot at other color models than the HUE? Did you look at LAB and stuff like that? So, I had a slide there where I showed different like color schemes that I used.
25:04
So, I mean, there's obviously a lot that didn't go, that didn't make the cut here. I tried RGB, I tried CMY, various combinations, various combinations of colors. When I tried generating a color space like a group of colors
25:24
and tried doing it with RGB, I got a lot of grays because RGB in a 3D cube is basically a lattice, right? So, you're going to have points which are right in the middle and they tend up to be too greedy, like, and just like what we got
25:44
with the overfitting of the machine learning, you get things like in the end would work for me. And, you know, once I found something that worked, I stopped. I moved on to the next problem. So, it could be that there's a better solution. But using HSV and using HSV to generate the points
26:03
of color was what worked in the end. Thank you. Yes. Hi. Thank you. It was a wonderful talk. And I wanted to ask if you considered building a machine to stretch the strings? Okay. So, first of all, I'm, you know, I don't have a patent on the idea.
26:25
If you put string art in, like I said, it started with an Instagram account. If you go into that artist's Instagram, you'll see she does, her husband is also a computer scientist who wrote her code
26:40
or something like that. Like, she does the art and he does the code and, but, again, it's their code proprietary. And they don't share it. And that's why I decided to try and, you know, do it myself. And as for machines, if you Google or somewhere, you'll see that there are machines that can do that.
27:00
It's just that, you know, I haven't taken it to that level at this point. Hi. Very impressive work. Thanks. Did you try to, you hear me? Did you try to improve your run time by using Kupy instead of NumPy? By using what? Kupy. It's same syntax as NumPy, but it uses GPU.
27:26
No, I did try multithreading. My background, like, from before Python is like Java, Kotlin, and stuff like that. So, you know, multithreading was, I'm used to doing that. It did not work so well with Python,
27:44
but admittedly I'm not a performance expert in Python. I'm sure there are, you know, paradigms that would work and improve it. This was good enough. By the time I optimized it, I could get a run time of a few minutes depending on, you know, how quick I wanted it.
28:03
The final run where I wanted the instructions that I would actually do, then I would, you know, do a run that would take maybe 20 minutes because, you know, more candidates, so it's more correct, more precise, and so on. But, yeah, I'm sure it could be, the performance could improve.
28:21
Thank you. Toda. All right. Thanks a lot for the questions. Again, thanks a lot to Yair for the talk. Thank you.