Add more dithering methods

[roshavagarga]

I would like to fix a few naming issues and add some more dithering matrices as a pull request, but I'm unable to find where they're actually located in your code, or are you using something external for the calculations?

[alexharris]

Hi, that'd be great.

The bayer matrix located is here: https://github.com/alexharris/ditherit-v2/blob/89f35deb9c620031fab0095934fecde112dc78d1/pages/index.vue#L742C1-L747C9

All of the error diffusion code is from a separate library called RGBQuant. The original is no longer maintained so I am using a forked version, which has a few of my own fixes, located here:

https://github.com/alexharris/RgbQuant.js/blob/master/src/rgbquant.js

Hope that is enough for you to go off of, let me know if you want to discuss anything further. Presumably additional options will need a UI change as well?

thanks, Alex

[roshavagarga]

Hm, the Bayer looks weird to my eyes, then again I'm not sure how that works - I've only worked with set Bayer matrices (2x2, 4x4, 8x8 for instance), so maybe that's why - I'm guessing yours just chooses how to 'grow' based on what it's handling?

As far as the error diffusion code - I will add new matrices and probably rearrange and add notes/links. I'm guessing I won't need to touch anything as far as the actual code and that it can handle any type of matrix, or does it have limitations?

Please treat me as a non-dev explanation-wise - I can figure out the simpler stuff by looking at examples or trial and error, but I can't code per say.

As far as ordered dithering - can new ones be added via matrices alone, or does the code require updating to accommodate anything non-Bayer?

Edit: As far as the UI - depends on what I add I guess? If I only add error diffusion, the only changes I'd like to make is to change the order, add new ones and have proper names (as in TwoSierra versus Sierra (Two-row)). If I can add ordered dithers, we would need the UI to match the one for error diffusion ones.

[alexharris]

I think that Bayer threshold map IS a 4x4 matrix? I suspect other size matrices could be used...I remember trying and then giving up. But I figure it could work. The maps on 807, 810, 813 will probably need to be updated to do %2 or %8 depending on the size of the matrix. That seems like something to try.

For error diffusion: that sounds good. The "kernels" are all here: https://github.com/alexharris/RgbQuant.js/blob/dd80ef94c2256eb0af4b8451b3f5c4e1b5a70988/src/rgbquant.js#L141

Yeah it sounds like the only UI change would be a need for a dropdown to select a matrix size, which would probably show in the "advanced options" panel when Bayer is selected.

Let me know if that is enough explanation or if you need more help getting to a point where you can test some of the above.

[roshavagarga]

Pull request for the error diffusion kernel is in - unfortunately, I'm not tech savvy enough to figure out how to extract that for a localhost of ditherit, so I was unable to test it, but it should work, though you may need to do some changes here too (index.vue would be my guess).

I arranged them based on when they were published/came into use and whether they were a derivation/modification of a previous matrix:

1. Floyd–Steinberg - 1976
2. Atkinson - Floyd–Steinberg modification, 1980s
3. Sierra2-4A - Floyd–Steinberg modification, 1990, a.k.a. Sierra (Filter Lite)
4. Fan - Floyd–Steinberg modification, 1993/1994
5. Shiau–Fan - Floyd–Steinberg modification, 1993/1994
6. Shiau–Fan 2 - Floyd-Steinberg modification, 1993/1994
7. Jarvis–Judice–Ninke - 1976
8. Stucki - Jarvis–Judice–Ninke modification, 1981
9. Burkes - Stucki modification, 1988
10. Sierra3 - Jarvis–Judice–Ninke modification, 1989, a.k.a. Sierra
11. Sierra2 - Sierra modification, 1990, a.k.a. Two-row Sierra

As far as the ordered ones, I have a number of matrices, but I don't think they will work without changes to the maps part and I'm pretty sure that is beyond me.

Specifically, the ones I'm thinking of adding are:

1. 4x4 and 8x8 cluster dot (the latter mimics halftoning).
2. Bayer matrices (2x2, 3x3, 4x4 and 8x8).
3. Void and cluster example matrix. All of the above are available as matrices here.

The Bayer matrices I'm not sure which ones you would find useful - the 3x3 gives different results from the others, the 2x2, 4x4 and 8x8 give similar results, albeit the larger it becomes the better the quality of the image, at least to what I've seen.

The void and cluster method is a bit beyond me - the example matrix in that study gives very interesting results, but after reading a lot about the subject, I'm not entirely sure whether a set matrix should be used, or if one is created per the input, although I'm guessing it's the former. Void and cluster is also known as blue noise dithering.

[roshavagarga]

Well, diffusion ones are out of the way - very happy with that, just tested them out on live.

By what little I can gather from the code, I don't think it will be easy to add the 3x3 Bayer matrix, or the Void and cluster example matrix - one is 3x3 and the other is 14x14, and the RGB part seems to need to get it down to 2, unless I'm reading it incorrect, which is impossible for either one of the above, without fairly big changes to that part?

The void and cluster method you can turn into a 4x4 - you'd have to basically create your own matrix, but that isn't horribly hard as far as I understood the process, the 3x3 would be a dead-end without changes.

The 2x2 and 8x8 are up to you I'd guess - 8x8 means more details are preserved, albeit marginally, while the 2x2 will sacrifice some details, in a minor way, but lower the file size a bit.

I will note, that out of all of the ordered ones, the void and cluster method will give you the best image quality, albeit I'm not sure how much it'll blow up the file size - I'd wager not that much, but I may be wrong.

[alexharris]

I am not sure what you are see that makes you think certain size matrixes wont work...but maybe you are right, I don't exactly remember the details of how I implemented this.

Since there will be a little bit of code scaffolding needed to allow for multiple ordered options (UI and some changes to the code that actually apply the algorithm), maybe it makes sense to keep it as simple as possible to start. I guess the 2x2 sounds good to start with..and then maybe either 8x8 just to test or else a 4x4 void and cluster sounds interesting as well if you want to make the matrix for it??

[roshavagarga]

My train of thought was that the since the RGB part of the code wants to divide things by 2, it would struggle with matrices that cannot be divided by 2 once or more than once? I may be entirely off on that. Example matrices can be found below.

Bayer 2x2:

[0, 2],
[3, 1]

Bayer 8x8:

[0, 32, 8, 40, 2, 34, 10, 42],
[48, 16, 56, 24, 50, 18, 58, 26],
[12, 44, 4, 36, 14, 46, 6, 38],
[60, 28, 52, 20, 62, 30, 54, 22],
[3, 35, 11, 43, 1, 33, 9, 41],
[51, 19, 59, 27, 49, 17, 57, 25],
[15, 47, 7, 39, 13, 45, 5, 37],
[63, 31, 55, 23, 61, 29, 53, 21]

Source for above - here. Libcaca study has the same, just mirrored/flipped on one side, you can do that and it will not change results or quality.

Cluster dot 4x4:

[12, 5, 6, 13],
[4, 0 , 1 ,7],
[11, 3, 2, 8],
[15, 10, 9, 14]

Cluster dot 8x8 (mimics halftoning):

[24, 10, 12, 26, 35, 47, 49, 37],
[8, 0 , 2, 14, 45, 59, 61, 51],
[22, 6, 4, 16, 43, 57, 63, 53],
[30, 20, 18, 28, 33, 41, 55, 39],
[34, 46, 48, 36, 25, 11, 13, 27],
[44, 58, 60, 50, 9, 1, 3, 15],
[42, 56, 62, 52, 23, 7, 5, 17],
[32, 40, 54, 38, 31, 21, 19, 29]

All of the above sourced from here.

I think the others can be dropped - void-and-cluster seems too taxing to recreate and it's only good for really really big images, so it would mean probably mean lost resources on computations. The 3x3 Bayer doesn't seem to add a lot, outside of a specific aesthetic. The above add quality options, without, to my mind, costing a lot of resources.

Feel free to ignore all of the above if they seem unnecessary.

[alexharris]

This all looks good, I will just focus on getting an mvp up of using multiple bayer matrixes, and then see what works to plug in

[alexharris]

OK, I got the basics of multiple bayer matrices working via selecting options in the "advanced" panel. These changes can be tested here: here. And the code changes are available in the "bayer" branch.

The matrices all seem to be working at least roughly as expected, the cluster dot ones are showing halftone-ish dots, etc, but something is definitely off in my implementation as the images seem to all be appearing too dark. Let me know if you notice what might be going wrong, and I will continue working on these as well. I can provide a more detailed explanation of what is happening in the code if that is helpful, but the relevant section starts here: https://github.com/alexharris/ditherit-v2/blob/99f2d74fe7e64a0e2950888fe27339ce55c02e0a/pages/index.vue#L857