Coding Challenge #90: Floyd-Steinberg Dithering

hello welcome to today's coding challenge today's : challenge is to implement Floyd Steinberg dithering dithering dithering dithering and I'm going to do this dithering which is the thing that I actually spend most of my day just differing about I'm gonna do this dithering in processing which is a Java based programming environment works great for graphics I can load images I can relate pixels which is what I need to do now the reason why I'm doing this is because I'm interested in this overall topic of image stippling which is a way of making an image basically out of dots and just as one reference for this I'm going to show you the work of Robert Haugen did some interesting attempts to do image stippling using like particle systems moving around and forces between the particles and I'd love to think about that as a follow up but I'm going to in this video look at a particular dithering algorithm a way of quantizing an image and looking at errors and I'll kind of get to that as I go through it to get this type of look for an image but I do want to think of this for at least for you as a beginning step because if I could make this what if I consider all these dots to be particles that can move and experience physics and go and find another place for another image there's a lot of possibilities there so let's get started so I have a blank processing sketch and in the folder I have a data folder and I have this image of a kitten which is 512 by 512 pixels so the first thing that I want to do is I just want to write a simple sketch where I have ap image object called kitten and then I say kitten equals load image and the name of the file is kitten dot JPEG and I am going to make a window that is 1024 by 512 so that I can draw the image of the kitten at on the left hand side and if I run this there we go so what I want is I want to be able to look and see see it do you see the original kitten here and that I want to see the did kitten on the other side so how does this algorithm work fortunately for me among this Wikipedia page which explains it and it's got it right here but before I get to that let's talk a little bit about some of the things that have to happen for example in the pseudocode there's like this lancets find closest palette color what's that mean and then there's like this quant error thing so let's discuss sort of on the whiteboard what some of these pieces are so if I have an image an image is just a grid of pixels any given pixel having a column row location and I might think of that as X comma Y right it's in the X column 0 1 2 it's in the Y row 0 1 2 amazingly I picked the pixel 2 comma 2 and it has a color typically that color is going to be an RGB color meaning it's going to have some red value some green value and some blue value the idea of quantizing an image so typically speaking if I'm using the full range of digital color I have a lot of possibilities I have 0 to 255 256 possible Reds 256 possible greens and 256 possible blues but what if I wanted to reduce the number of possibilities what if there are only 4 Reds 0 1 2 & 3 4 greens I would have and I take an image of an original color take an image of that has the original full colors and I reduce it to a smaller subset of colors and this kind of process is applied to to make images most smaller file sizes and to do various kinds of effects so actually let's just do that first and actually what I'm going to do is quantize this image so that there's only two possible colors there's basically zero red or 255 red 0 green or 255 green and 0 blue or 255 blue so there's really two times two times two possible colors eight possible colors so instead of 256 to the third power colors I want to see what does this image look like with just eight possible colors let's make that happen first and we'll see later why that's part of this algorithm so the way I'm going to do that is I'm gonna operate on the same kitten image so I'm gonna do is load the original image and display the original image and set up then operate in on it and display the new image and draw you know there could be some animation stuff that I do or a different order but I'm gonna do that as a simple thing for right now okay so let's the first thing that I need to do is I need to look at all of the pixels and here's the thing even though I could just the pixels are stored in a one dimensional array so but I do want to say look at all the X values kitten and and based on that images with sorry I lost my what I was doing here for a second so I need a nested loop to look at every pixel for every X and for every Y so this is going to allow me to look at a given pixel from the kitten the problem is the pixels are actually stored into one dimensional array and I need and I want to think about the pixels as their XY positions come and need that later luckily for us there's a very simple formula X plus y times kitten dot with and I go through this formula in another video that I will link to from this video's description if you want to understand why this formula takes an X Y position and gives me the one dimensional location in the pixel already so here's the thing in order to quantize this image this color this color variable is actually just a big integer and I need to pull out the red value of the pixel the green value of the pixel and processing has these nice helper functions that if I just pass an RGB color to the red function I get the red value and the blue value of the pixel now how can i quantize the image basically what I want to say it's kind of like a threshold effect I want to say if if the range of college between 0 and 255 if I'm above 127 just make it 255 if I'm below 127 just make it zero and so I could use it if statement for that but there's actually kind of a fancy way I could do this let's say I take so I'm gonna say the new R is going to be equal to let's say I take the current R value and divide it by 255 what does that give me that gives me a number between 0 & 1 well what if I just round that number so if that number is 0.5 it'll be 1 if that number is 0 the low point 5 it'll be 0 so I can actually use the round function and then I could just multiply it by 255 so this is basically giving me two only two possible numbers no matter what R is I'm either gonna get 0 or 255 and I could do the same exact thing for G and the same exact thing for B and now what am I going to do I want to say kitten dot pixels index equals a new color with those values so this is me just saying pull the RGB values out quantize them to a smaller number of possibilities and make a new color and set it back to the pixels okay so and you know I've forgotten something kind of important which is that when I operate on an image in processing before app and operate on the pixels I should say kitten dot update pixels and then when I'm done I should say kitten dot no no update pixels is when I'm done and before I operate on the pixels I need to say load pixels like low picks are the same like hey hey you I want to work on the pixels right now update pixels thing done but I'm done I'm done so now image kitten 512 comma 0 so I should see the quantized version on the right and the original image on the left let's see this looks pretty good right this kind of makes sense like if I only have a certain number of possibilities this is what I'm left left over with we can you know let's well interestingly enough what happens if I already right before I do any of this make it grayscale so I can just quickly filter that image and make a grayscale with a filter function and processing we can run it again and we can see you can see how this is working now there's only two possibilities it's either white or black and so this is identical to a threshold effect and here whoops let's let's leave that in but comment it out because we'll come back to it later now interestingly enough what if I want to have more possibilities what if I actually want to have instead of just two possibilities for each color four possibilities for each color well I can do something similar for example what I could do I think this would work right what if I multiply this by 4 and then divide it by this and divide 255 by 4 let me just put this in here usually don't like to do this and then let me explain it think about this what I'm going to get now is if I'm multiplying this number that's a floating point number between 0 and 1 by 4 and I around it I'm gonna get a 0 1 2 or 3 right those are the only things I'm gonna get 0 1 2 or 3 now I want to scale that up to basically like what are 4 possible colors in between 0 and 255 so this also and this I was going to say I have to put floor here but luckily I don't and this is gonna really trip us up later if I'm not careful RGB our floats so this is going to turn into a float round will turn the result back into an integer 0 1 2 or 3 can I get 4 yeah I could get for this is actually giving me five possibilities right because if R is zero I'm gonna get zero so this is actually interesting enough giving me five possibilities zero one two three four four five possibilities just like multiplying it by one gave me two possibilities zero or one so I actually have five possibilities here and then I want to scale that up this though this is an integer this is an integer it's going to give me an integer back so and what I might like to do here just to be like protect myself here a little bit is I might want to say nu nu R and I want these to be sure that these are integers because I'm quantizing to just a few sets of possibilities so this is indeed an integer and so now so now I'm going to say a new r nu g newby newby so let's now run this and see what happens there you can see how now I have more color possibilities but still I've reduced the image to a smaller number of colors five five this was actually five times five times five so 125 possible colors I think not very many colors okay I should probably make this a variable I'll call it like factor and I'll set that equal to four and put this in here and the same number goes here if I've done this correctly and if we run this it looks like this if I set this to be one it looks like this so this makes her if I wouldn't do something interactive here I wouldn't want to operate on the original Khitan image I won't have a separate image so I could like change it on the fly but I don't need that for right now okay so we've done the quantizing part now the other thing that I need to understand is the quantization error is that the right way to say that I'm not entirely sure but what I mean by that is let's say the actual let's look at a particular example the actual color is 255 comma 100 ten what does one person this is an actual color or if I were to reduce this color with one with two levels with a factor of one two levels I would get to 5500 right because this would round up to 255 this would round down to zero and this would round down to zero so the error is the difference between these two this minus this is 0 this minus this is 100 and this minus this is 10 that's the actual error let's let's let's do this a little bit differently let's make this one 50 just so we can see so this would then be 10 but this would round up to 255 so the error would be negative 105 right so you can see this is calculating the error the reason why I need to work with this error and let's put this into the code real quick so I'm gonna say here err err err r equals nu r minus nu r error G equals G minus nu G and error B equals B minus newby newby okay so so the reason why I need this error is let's go back to that Wikipedia page basically this algorithm achieves dithering tillering using error diffusion meaning it pushes the residual quantization error of a pixel on to its neighboring pixels to be dealt with later so in other words it just keeps ah it's so different put it on it's kind of it keeps pushing the colors further further apart away from each other kind of based on the error and so the pixel indicated with a star indicate to the pixel currently being scanned and this is the amount of error it passes to its neighbors so in this case oh and what's kind of the order of matters here for each y from top to bottom for each X because I'm actually pushing the error based on pixels to the right so actually so the pixels that I'm using are pixels this is a pixel to the right this is a pixel to the left and down this is a pixel down it's kind of like the pixels on the bottom right of the image so let's check this out for each Y from top to bottom no I have X so I need to do Y first that's going to make a difference so right now let's just make sure this still works it still works but now I need to start doing this error thing so for each so now this is what I've done already right I've gotten the the quantized pixel like I've done this part I calculated the error so all I need to do is start like funneling the error off okay so how do I do that let's actually grab this and put it in our code right here and let's comment it out comment that out and let's put this up here right this in fact is that whole first part of the algorithm this whole first part of the algorithm matches exactly with these three lines of code right here right I look at the old pixel I get a new pixel and I set it and then I find the error so I've done that already now I just need to do this part so doing this part is hmm so first I need to say okay so here's the thing let's you know how I have this formula here X plus y times kitten dot with let's make that actually a function I'm going to call the function index and it just takes an int an integer éxito Y should probably take a whiff too but I'm gonna be sort of silly about it and it's just going to return because I'm going to need to do this a lot X plus y times kitten dot with Y oh and it's not a void function it returns an integer and then I'm gonna do this index X comma Y so what I'm going to do is like whenever I have an X Y I can just quickly get the index and we're and that will be the correct index into the pixels array I could have made this two lines of code but I think I think we can follow this I could follow this hopefully you can follow this because the reason why I just did that is because I need to say kitten dot pixels index X plus one comma Y right I am rewriting exactly this pseudo code right here and why okay so that's so I need to do this 2x plus one comma Y I need to do this 2x minus 1 y plus one I need to do this 2x y plus one and I'm sure I could do this in some kind of like loop or something but I'm just going to write it all out right now just to know that it works x plus 1 y plus 1 so and like if I just for a second put zeros here just so I don't have any syntax errors and put a semicolon here semicolon let's just see okay great so this is what I'm doing and I'm gonna be kind of anal retentive about this and add some extra spaces just so it all lines up so I know I need to operate on these 4 pixels that's what it's telling you down here and what do I need to do this is the important part ah so this gets the the if you can see that these are all getting parts of the error seven plus three plus five plus six is 16 so this is getting like you know almost half the error like forty high 40s percent this is getting like a little bit of around a little less than a quarter of the error so okay so this amount is important so for each one of these I actually need to make a new color so I need to say so I need to mmm-hmm I'm gonna have to do this with our I have to for everything have to do this with an R a G and a B so when this is going to be index XY here as well so now what I need to do is let's think about this I want to get a another new are I already used the variable name you are and I already called it an integer so ah let's okay let's say I'm gonna okay let's I'm gonna have a color called see I have an idea now I'm gonna rename just so I have different variable names I'd make this old are old G old be sorry for all this variable naming Oh old are old G old B and then old old old okay so the reason why I'm doing that is because this is what I want to do I'm gonna actually say int index equals this index then color is kitten dot pixels that index now kitten dot pixels that index should now equal R equals red see red of C G equals green of C B equals blue of see it should equal and that our shouldn't how equal that I got it I got it I got it r should equal itself plus error R times 7/16 times 7/16 do you see why this is so what I need to do is I need to do this for our G and B G B G B G B so what and I have a mistake here but for each one of these and now I set it back to the color I'm passing the error so let me look at that color get its RGB passed part of the error on to it and then set that new color okay so the thing that's wrong with this is 7 divided by 16 is what I said it was like almost 50% almost point five but it's actually zero because both of those are integers so I need to be very careful and say 16 points I need to at least explicitly in Java and JavaScript I wouldn't have this problem and you'd explicitly say point zero because I want that to be a float so now I just need to do this with every single one of these so I need to do this over and over again four times and each time I do it I'm going to just use the same variable names but not read eclair them I don't love this style but it will do so now I need the next one is X minus 1 y plus 1 and the next amount of error I want is 3 comma 16 3/16 so 3 so I'm going to do that then I'm going to do what the next one is X Y plus 1 X Y plus 1 and the amount of error is 5/16 X Y plus 1 is 5/16 then the last one and I can get rid of all my notes here from the pseudocode the last one is X plus 1 y plus 1 X plus 1 y plus 1 and 1/16 of the error okay I think yes yes I could make a function there's so many ways this could be cleaned up and I appreciate people who are watching this live do you see good feedback I'm gonna leave that as an exercise to the viewer I just want to run this right now ok so I have an array and there's Oh what is my problem here look at this I am looking at every single pixel but for every single pixel I'm dealing with neighboring pixels right I'm dealing with things like for this pixels XY I'm dealing with X plus 1 comma Y which is this pixel it's one over an X the same Y but when I do this there's no pixel over here so I need to deal with the edges and I could be thoughtful about this but just to get this algorithm to work let's look at these I am going to the right and the left but only to the right why only down why why's why wise so I can start x1 if I start at one I'll always have a neighbor to the left and I can go all the way up to minus one meaning I always have a neighbor to the right and four why I can I can start at zero because I never look up and I can go over this way so now let's run this and I really should I've learned my lesson so many times to not use this from roll effect so I usually have some mistakes but imma try it right now hey I think I kind of got this yeah look it's sort of hard to see cuz there's so much crazy detail in the outside here but I think did I leave the factor as one I think this is right you don't ease your way for me able to see if this is right is let's filter out let's juice the grayscale one and look at it yeah it's definitely right so you can see this image is now kind of dithered so to speak you could qu4 ask the question uses a lot of white dots is it a lot of white dots on a black background or is it a lot of black dots on a white background the truth of the matter it's neither all I've done is set every pixel to either white or black but I've made it have this appearance of being like a lot of dots next to each other and so the question here is how might I take this like if I used a lower resolution image drew the dots as ellipses and then blew it up what kind of other visual effects could I get here and we could see this we could kind of look you know if I change the factor to four and ran it again you know you can see that it's the same sort of thing is happening it's dithered but I'm only now I have I think five different gray possibilities it's a white white dark dark gray light gray medium gray no dark bright great gray I don't know what didn't you get the idea so I think a bit rate is an issue here so ah I think I've done something which is that this video is not going to work very well on YouTube because you're not really gonna be able to see this detail but I think if i zoom in right I think you can you can kind of see hopefully you can see see this detail alright so what could you do with this I'm gonna stop here I'm gonna go back to taking out gray let's look at it with mmm so you can see here this is dithered but now many different RGB colors maybe 125 RGB possibilities I think so what could you do with this I'm and I'm gonna actually leave the code with one and leave the grayscale in what I think could be interesting is number one work with a much lower resolution image but display it at much higher resolution and maybe draw ellipses or particles as each one of these dots whether it's a black dot or a white dot draw it with some texture some image or something what if those dots somehow are the seeds of a particle system and then I think eventually I want to come back maybe I'll do a follow up challenge like that but those would be some exercises that I would try you can read over a link also to Robert Hodgins description of this stippling you can see the particle checks the pixel array to see what shade of grey needs to represent if it shows blackness it grows smaller and it's magnetic charge diminishes if it's white it grows larger as it's charged so this is kind of like a force directed self-organizing physics based system that creates these white and black dots to represent an image you know and certainly I will try I will create or somebody will pull requests for me a JavaScript version of this so that you can also see a version that runs in the browser although the pixel array works differently in html5 canvas and in p5.js and pixel operations in the browser unless you're using shaders or some kind of advanced technique often are very very slow whereas in Java and processing that can operate quite quickly alright thank you everybody oh if I stop moving I'm told just to show this to you I'm told that if i zoom into it and then I stop moving it will resolve this will be the thumbnail let's get that mouse out of there this will be my thumbnail okay thanks for watching [Music]

Channel: The Coding Train

Views: 293,975

Keywords: live, programming, daniel shiffman, creative coding, coding challenge, tutorial, coding, challenges, coding train, the coding train, live stream, itp nyu, class, processing coding challenge, challenge, codingtrain, processing, code challenge, dithering, stippling, floyd-steinberg dithering, floyd-steinberg algorithm, dithering algorithm, dithering art

Id: 0L2n8Tg2FwI

Length: 28min 51sec (1731 seconds)

Published: Tue Jan 16 2018