Coding Challenge #90: Floyd-Steinberg Dithering
Вставка
- Опубліковано 24 тра 2024
- In this coding challenge, I attempt to implement the Floyd-Steinberg Dithering algorithm and create a "image stippling" effect on an image (kitten, of course) using Processing. Code: thecodingtrain.com/challenges...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
🎥 Previous video: • Coding Challenge #89: ...
🎥 Next video: • Coding Challenge #91: ...
🎥 All videos: • Coding Challenges
References:
📓 DHALF.txt: github.com/SixLabors/ImageSha...
📚 Processing Tutorial on 2D Arrays: processing.org/tutorials/2dar...
🔗 Dither on Wikipedia: en.wikipedia.org/wiki/Dither
🔗 Floyd-Steinberg dithering on Wikipedia: en.wikipedia.org/wiki/Floyd%E...
Videos:
🚂 My Tutorial on Pixels in Processing: • 10.4: Pixels! (The Pix...
🚂 My Video on 2D Arrays: • 9.15: 2D Arrays in Jav...
🔴 Coding Train Live 114: • Coding Train Live 114:...
Related Coding Challenges:
🚂 #50 Circle Packing: • Coding Challenge #50.1...
🚂 #85 The Game of Life: • Coding Challenge #85: ...
🚂 #107 Sandpiles: • Coding Challenge #107:...
Timestamps:
0:00 Introducing today's topic
1:20 Let's start coding!
2:44 An image is a grid of pixels
3:25 Quantizing an image to reduce the number of possible colors
6:24 Pull the red, green, and blue values of the pixel
7:11 Quantize the r, g, b values
8:21 Add loadPixels() and updatePixels()
9:11 Filter the image to make it greyscale
11:01 Add more color possibilities
13:01 Quantization of the error
16:01 Funnel the error
17:10 Write an index function
21:08 Update r, g, b values
24:13 Deal with the edges
26:55 Conclusion and suggstions for variations
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: ua-cam.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#dithering #stippling #floydsteinbergdithering #processing
"Sorry I lost my.... What I was doing here for a second"
Pretty much sums up Dan's way of working. :-p
You Dutch?
and that's a good thing
Dude I'm not even a programmer but this was really interesting! Kept my attention the entire time.
Curb Your Enthusiasm for Coding. Loving the intensity and your videos. Thanks Dan(LD)!
I initially rewrote this in Python but it was S L O W. Re-rewrote it in C and not it's a very nice little utility that I use on a regular basis, thanks for the video dude. Keep up the great work! Love how you are making this stuff accessible to everyone.
wiki makes this stuff accessible
Python can be made to run more efficiently if you understand its idiosyncrasies.
@@DrSpooglemonbut never faster than efficient C
@@luigidabro Sure, but it can be faster than people think!
Just a note on this, if translating to another language the "r = r + errR * 7/16.0" parts can give you values 255 which will cause artefacts. your rgbs need to be clamped so if 255 =255.
Your videos are not only comprehensive but also FUN. Thank you.
Hey Daniel, it's always impressive when you show us stuff in 30min, I use in Photoshop since 20 Years. Really love your channel and challenges and dithering ;-) .
Thank you!
Hey man, just wanted to say that your videos are simply awesome. Cheers!
I like this guy. he is so enthusiastic and full of energy.
Someday when I'm bored I'm going to recreate all these in python
I have done so to a couple, and be warned, pixel manipulation is not as fast.
Carter Plasek I know, but it's still fun
Oh, of course, python is certain to grant a good time :D
legobudgie it's okay! I'm just a freshman in University, and just learning as well:) I know python and c++ the best, and any java or js I know is from that hunk on screen
Everybody started out like that. Even all those geniusses like Dan or Alan Turing or whoever.
Thanks for all the help, I was really struggling with this (this is part of my homework and I didn't catch the basics of the problem very much), but now I think I do understand a bit more. Thanks for all the work and effort you put in this.
Darn, I love these coding videos 🙌🙌 well done
I've known about Floyd-Steinberg Dithering, but never looked into the algorithm. I never knew it was so simple!
I'm not great at coding but just found this channel and loving it. I feel like this guy would really like Return of the Obra Dinn since that's basically a game made with dithering.
Wow.... this is actually helpful for my Shader Learning in GLSL :D Thank you!!!
I love those "algorithm" video's, where you are putting them into processing!
Just made a cool application where I can convert any image into a LEGO mosaic, and it looks really cool when looking at a distance! Thanks for the coding challenge!
Great the way you explain your thinking! So extremely helpful as i'm a beginner
Really teaches me how much of a newB I am at programming
3 years later. Are you an oldG yet?
Thanks for the wonderful performance!
I think it would be great if you did a challenge where you create an upscaling algorithm, similar to bilinear and linear upscaling you can find in programs like photoshop. There are some very advanced ones out there too that you can find in emulators for old pixel art games, although I don't know the names of them on the top of my head
like hq4x
I love these videos and think it a great introduction to algorithmic thinking. Your inspiration is contagious!
If anything I would love to see a refactoring exercise of each to see it improved in maintainability and quality.
Thanks a lot.
I love this guy. He is hilarious... And a programmer!? Xd
When mum asks you "what are you doing?" you answer "Watching quantized kittens" and she's going to be like "wow... he's learning some kind of a quantum physics..." :D
@LifE's UA-cam Channel
She can't prove that the cat is not alive if she can't see the screen
@@Skaggco Quantized schrodinger
goddamn nerd
@@FSFITA xDDDDDDDDD
InstaBlaster
Wow i've just discover your channel and it's awesomly pedagogically good and intertaining
Where do you get all these awesome ideas? I'd love to attempt something like this myself but I wouldn't know where to start
Интересно будет попробовать использовать фиксированные палитры или поменять распределение цветовой ошибки на картинке (распределить с другим соотношением или по большему количеству пикселей).
PS:
Классный канал, где программирование и творчество встречаются вместе.
Keep up the good work! My coding club is now doing a lesson on Processing :)
Loved the part where you posed for the thumbnail :D
wow... so this is the power of computer science... impressive...
Fascinating! Go Dan!
All of your coding challenges are great, they are so much entertaining and give tons of ideas to beginners wondering what to code.
Plus you really make them easy to follow..... but perhaps a little bit too easy. I definitely know you do that for the sake of clarity, but sometimes it makes your code choices really ugly and unseemly.
I honestly think it would be really important for your viewers to see you working more on the code rather than the ouput only, even though it doesn't make it more impressive.
Thanks for this feedback, I completely understand what you mean and will consider this in the future.
Thanks a lot for your reply and even more for your consideration, I'll look forward to it!!
I love watching his videos just for entertainment but I would love to see more practical approaches to some subject
Too Easy? AHAHAHAHAH
For another challenge, you could try using k-means to select an optimal set of palette colors, if you haven't done that in a video already.
k means sucks for photos, octree and median cut are better.
thanks for great tutuorial! I"m attending the 2022 Genuary challenge and found your dithering challenge!
Trying to translate the code from processing to P5js.
Dayum! I always wanted to make these.
Really interesting how the video compression on the dithered cat @25:40 is completely lossless when viewed at the original 1080p scale. The pixel perfect black and white detail is completely preserved!
YIPPI! Processing3 is used = +1000 points
A question Dan: why do that in the draw function? It's better do the loop once in the setup. Right?
Yeah, since this is generating a static image it makes sense for it all to happen one in setup!
I had the same question. Now I would like to see how the dithering behaves as we slowly introduce slight variations in the palette thresholds and definitions (or also mixing the RGB channels).
For what it's worth, you can also explicitly make a float by appending 'f' to the number: 7/16f
23:25 how I feel any time I finish writing in JavaScript and don't want to break it with missing closures again
Hmmm, this reminds me... have you ever seen Raven Kwok's work for Karma Fields? The videoclip for Greatness and the one for Skyline are just beautiful. Would love to see you try something like those. Anyway, thanks for the one more coding challenge!
24:51 when you reach the bitrate limit because of the noise
I like your videos! And I was wondering if you could make an hypercube animation on Processing...
for " r = round(r/255)*255", if you are in optimization, I think that an if statement is better, since you only do one test rather than a division, a test and a multiplication (the test come from the round function, i'm not sure how it's implemented in java, but the fastest way that I can think about comes with a test... and a few more number manipulations (I'd guess a truncation, a subtraction, a test and an addition)... In this case the optimization doesn't matter much since you only compute a relatively small image once on a powerful enough computer, but I had once a occasion where little optimizations like this helped a small computer do image processing much faster, reduced the time by a factor of at least 50...
Or you could do it with 'r = r/128' if r is an integer (which I think it is) to get only one line, I think it should be a bit slower than the if statement, though I'm not sure, not too too familiar with assembly yet
Thanks for the feedback!
You have to consider when you do branching, the processor have to do a branch-predication. Basically, when it can take two different code branches, it'll guess which path the program will take and load code for one of the branches. This is so it can do optimizations as *out of order execution*, and *parallelism*. However, guessing wrong branch means that everything it has loaded and calculated in advance must be discarded, and the correct code has to be loaded. This is **slow**!
So to know whether an if-statement is faster, you'll have to do what all optimization questions require; you have to measure it yourself!
If you're interested in image stippling, look up "poisson dart throwing" and "void-cluster method". A little trade secret, if you mean to apply relaxation to a stippled image, you might have to sharpen it a bit. Error diffusion will sharpen it a bit for you (that's partly why it's so popular), but other methods won't.
Thank you for these great tips!
this is nice for those who wants to show nice things on e-paper :)
I like processing. I've been playing with it for a bit, it's just that for some reason visual Studio doesn't like it. My apache server no prob. Thanks these videos are helping me get better.
Again super interesting and learned a lot, would have liked to see an example on the whiteboard to see what the formula of 7/16, 3/16, 5/16 and 1/16 on those surrounding dots was doing though
You can sort of imagine it, but visualizing it would have been cool
You're an eccentric genius!
22:00 Order of operations. errR gets multiplied by 7, and that float is divided by 16. It is all floating point in the end because the float comes first. I know this because I often get wrecked with integer division, but I know this is safe. Also, consider consolidating the definition of r and the addition on to one line.
Thanks for this correction!
"The times you have to see duplicate code before extracting it into a function is 1"
Hmmmm 🤔 23:00
Not gonna lie, I cried when I saw it xD
You need to keep a temporary row of floats to buffer error values for the next row (you only need one float for the pixel to the right, since it's always going to be the next one to be processed).
A pixel is made up of its own value, as well as the errors of 4 other pixels. With each partial error you're adding you're doing "max(0, min(255, round(current_value + error)));" .
Also, suppose a (for the sake of simplicity, assume grayscale) pixel has a value of 255, and its top left neighbour has an error of 16. This means that it would propagate 1 to the pixel in question, making the color (which can go from 0 to 255) into 256... this is a value that can't be stored in a value of type color, which only has 8 bits per color. Processing will do its clamping et voila: the error wasn't propagated at all.
It looks like it's working. It's not working right though. You need to add all the errors and *then* convert back to a color. Converting to a color after adding each partial error results in lost information
Yes a function is what I was thinking for that very similar block of code and repeated 3 times. And just pass the variations as parameters.
Would this have been more efficient if you converted the image to grayscale first, then operated on just brightness values?
It would be interesting to have a video on index mode of photoshop in processing. To get custom colors with dithering types in an image.
That awesome dithering effect at 14:44.
Lol... I just had a final exam from this topic
I wish I had final exams on topics like this
it's not as exiting when it's only theory and pseudocode :D :D
@@MrRys right
I love seeing the quality dropping at 25:02 because of the fixed bitrate and the crazy detail :D
Excellent video -- Love the style and simplicity !!! Congrats!!
Isn't there a hidden trick that each pixel is processed after it is changed?
If the pixels at X,Y is show as @ for where we are AT
then the four neighbors are ABCD the grid looks like
. @ A
B C D
The Pixels at A B C D will be processed again once X++ increments and Y++ increments
Can you explain this effect?
I saw dithering as an option in a Skyrim ENB and always wondered what it did
Oof! color pallete dithering? I didn't think of that genius artistry when I instantly came up with my own algorithm(s).
Great video
But how do we extract the resulted Image to be used in a different location.. Laser engraver for example
Thanks
In the p5 web editor, for some reason, even though you’re dithering it after displaying the original, it is showing the original dithered as well.
I like your beard
Would also love to see the curvy lines version that sort of looks like a maze... better yet... that is a maze.
"Dithering Dithering Dithering"
-- The coding train 2018
1:24 lands perfectly on the nose
How did you learn all this stuff? You're super awesome.
Awesome content!!
I have a question though..
If there would be 2 '(255,255,255)' pixels next to each other, when quantizing the first, wouldn't it try to add 7/16th of the red (255) (and also for the other channels) to the next pixel, extrapolating 255?
Is that being corrected by the library or did I get something wrong?
The fractions are of the INACCURACY between the original color and dithered color. So if you can use 255,255,255 in the dithered image, the difference will be 0. You should probably include that in the finished palette anyway, since if not, the difference could explode to infinity unless clamped.
Hi Dan (or other members of the coding train community), I was wondering how you choose which language to use ? whats the deciding factor between p5.js and processing for this project? and which projects are stereotypically best suited to which language ?
Hi! I often pick Processing for image processing applications b/c canvas can be quite slow (w/o the use of shaders), but otherwise it's often arbitrary. I like using p5js especially when I want to make sure I can run the result in the browser!
I did this years ago in highschool for a project, i didnt know it was a thing that actually existed. I used processing also, thats so weird
Hey Dan! Great video. I have a question: since I'm more acquainted with JS, I tried coding it in p5, following those instructions (and checking p5 ref to verify the commands exist). Even stippling alone doesn't seem to work at all. I then checked your GitHub source and saw that it was much quicker to code in .pde than in p5, what with all the long functions. I was wondering, is that because of the difference between JS and Java array structure? You can't simply grab a pixel from the array and get its blue value with one line of p5 code? Keep on being awesome ;)
check this video about pixel array in p5 ua-cam.com/video/nMUMZ5YRxHI/v-deo.html
Set that factor to 50, while using Greyscale. 50 shades of Gray!
My man Daniel looking like Luke Skywalker
Ese Brooks Luke or Chewbacca - I can’t make up my mind... ;-)
The beard is getting more and more majestic
Is this helpful when you have a beamer presentation but the resolution change makes your images look bad?
I had an idea, take a dithered image and reverse it back into a continuous image but make it so that new image is much smaller than the original but still approximates the dithered image so it could be recreated from the smaller data set. A sort of lossy compression.
The easiest way to achieve this effect? GameBoy Camera.
i feel like this would be a very handy method for increasing the resolution of an image (if you added pixels between each existing one to create a larger image)
there wouldnt be more detail tho
I can’t stop staring at the floating tuft of hair at the beginning...😅
I ran into a toolbar today, which is a plugin for atom to quickly setup a server and quickly create new P5 projects. Nothing special but kind of cool. I am not related to the project. just a quicktip - "p5js"or sth in atom package manager. And HEY I totally love your channel. :)
Two questions: when you round the color values, isn't that also a function which uses an if statement? If so, is round() not only more elegant to write, but also faster though? And by that I mean something that's going on under the hood in the implementation of processing.
You don't need to use an if statement in order to code your round function, for instance:
int round(float x){
return x+0.5;
}
Quentin Januel oh yes, I see. Cool trick. Thanks for The answer. :)
SellusionStar You are very welcome :)
Sir is the book "Grokking Algorithms" available in a pdf format? I saw it on your tweeter and then i rushed to Amazon but it really costs too much for me. $18.27 in my country amounts to more than Rupees 1000.
Sir???
„This is an integer, this is an integer. So it gives me an integer back“
But 255 divided by 4 is a float. I think it has to be 256 instead.
Wouldn't it be a rounded-down division instead?
Revi M Fadli sorry you‘re right. I disregarded the int cast.
I probably have bad programming habits ! i'm learning ! I use a lot of conditional branching like if (r > 200 ) {r = 255} . will this slow down my program if a check each pixel in an image?
i use about every 10th pixel to speed things up !
Could you use %amount of pixels in the index() function to get rid of out of bound errors, and make it rewind to the top?
Btw yes, rip bitrate
No, this wouldn't make any sense for several reasons.
First of all there is no point in having the error of a pixel on the right border to affect the pixel on the left border. The idea is to spread the error to the neighbor pixels and the left side is pretty far away from the right side ^^.
Next problem is this would completely mess up those pixels. The algorithm relies on the fact that a processed / quantized pixel is never touched again. The error of the current pixel is only spread onto pixels that hasn't been processed yet. So the error adding is actually a preparation step before you quantize the pixel.
The proper handling would be to not doing those steps when the x or y index is out of bounds. The easiest solution in his code would be to implement the bounds check inside the index method and when the index is out of bounds return "-1". Now we can simply check before each of those 4 steps if we got a valid index (index >= 0)
int index = index(x + 1, y);
if (index >= 0)
{
// ...
}
The index method could be changed into
float index(int x, int y)
{
if (x < 0 || y < 0 || x >= kitten.width || y >= kitten.height)
return -1;
return x + y * kitten.width;
}
How does this effect the size of the image? What percentage of reduction does this produce in overall file size?
Since you didn't go to the very right and the very bottom of the image, will those pixels still be quantized? I feel like they are not because those pixels are never checked, right?
Correct.
Best channel on UA-cam.
Sitting here bored @ 12:30am... sees an upload from this mint fella! I love your attitude and enthusiasm, actually makes me interested in Hungary.
Damn autocorrect, meant to say that it makes me interested in things I would otherwise not.
Checked your time zone you are off.
Mazeyar Moeini I'm not in Hungary. That was autocorrect, I decided to leave it in there for the giggles.
you could use PVectors to store the RGB colors
I need a clarification, actually I am in puzzled about p5.js and processing.js, what are the basic differences between them or what are the relationship between them, which one is better or which one should better to start learning ??
This video might help: ua-cam.com/video/AmlAiKsiy0o/v-deo.html
You: “pee-image”
My brain: “pie-mage”
21:56 Is this really a problem? It's not just 7 divided by 16, it's the error * 7 / 16. And it goes in that order from left to right, so it's first multiplied by 7. It will not be zero unless error is less than 3.
Don't you need a blank image to start with when you start accumulating the error distribution? It looks like you're adding to the original image over and over again ( you can see it change quite a few times 24:48 ). It should look much nicer than this.
Hey Dan, great video! This made me have an idea for an Android app, you'll be in credits if I do.
Dan is looking good with the beared
I think I learned more about coding concepts from this video than I did from my $70,000 master's degree education.
hey programmer can you make quiz page with timer in using p5 js
and using firebase
int MewR... your kitten has imprinted itself on your brain ;)