Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (539) Games in Android Showcase (132) games submitted by our members Games in WIP (603) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Bayer ordered dithering  (Read 2676 times) 0 Members and 1 Guest are viewing this topic.
Porlus

Junior Devvie

 « Posted 2013-05-04 16:39:08 »

Hi all, I'm attempting to add a stylised order dithering effect on an image although I've been met with unexpected results. I have an 8 by 8 threshold matrix as follows:

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

I just found this on the wikipedia page for ordered dithering and have been following the explanation in order to produce this effect myself. The algorithm producing the effect from this matrix is as closely resemblant of that explained in the wikipedia page and is as follows:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17 `int w = image.getWidth();int h = image.getHeight();int bd = 64;for(int y = 0; y < h; y++) {   for(int x = 0; x < w; x++) {                  int c =  pixels[y * w + x];      int d = dither[(y & 7) * 8 + (x & 7)];                  int r = ((c >> 16) & 0xff) + d;      int g = ((c >> 8) & 0xff) + d;      int b = (c & 0xff) + d;                  newpix[y * w + x] = 0x000000 | closestCol(r, bd) << 16 | closestCol(g, bd) << 8 | closestCol(b, bd);               }}`

This is just the method that reduces the amount of colours available in each channel:
 1  2  3 `private int closestCol(int c, int b) {   return c / b * b;}`

The above code simply adds the corresponding value from the threshold matrix to the image data and then attempts to find the nearest colour to it after rounding. The issue is that the dither values are quite high and saturate the channel of the pixel. I've tried averaging the channel colour with the corresponding dither value but that makes the screen far darker than it should be. Is there a detail that I'm missing whereby it adds the effect without harshly altering the tone of the image?

Here's a before and after dither comparison so you can see the results: http://i.imgur.com/9SWukYS.png

Thanks,

Paul
Porlus

Junior Devvie

 « Reply #1 - Posted 2013-05-05 11:50:16 »

Just updated with a screenshot of the problem: http://i.imgur.com/9SWukYS.png
Posting this just so you guys can see how it's producing effectively the right results, just with slightly skewed channels.
delt0r

JGO Knight

Medals: 30
Exp: 18 years

Computers can do that?

 « Reply #2 - Posted 2013-05-06 05:40:59 »

You don't appear to finding the "closest" color correctly. Currently you are dividing by 64*64=4096. That seems way too high. Why to you square that bd?

Also i don't really follow how the wiki is normalizing the color values. The paper linked is too old and a bad scanned copy for me to bother reading it.

Note you can also do probabilistic dithering. Probably works about as bad as normal dithering tbh.

I have no special talents. I am only passionately curious.--Albert Einstein
Porlus

Junior Devvie

 « Reply #3 - Posted 2013-05-06 14:17:30 »

The closest colour rounding seems to actually be working before adding the threshold. As the colour's stored as an integer it performs the division first and rounds that result and then multiplies. So the end value is actually floored to the nearest 64 in this case. For example:

140 / 64 * 64
2 * 64
= 128

So 140 becomes 128 when floored to the nearest 64. Sorry if I'm teaching you how to suck eggs, I'm just making sure.
delt0r

JGO Knight

Medals: 30
Exp: 18 years

Computers can do that?

 « Reply #4 - Posted 2013-05-06 15:02:19 »

Oh right order of precedence. I never write code that way since you can't tell what you meant by it. ie a/b*b or did you mean a/(b*b). So i would write (a/b)*b.

Note that you get a different result from (b*a)/b too. So best be explicit. Brackets don't hurt anyone.

So yea I think the normalization in the wiki is the problem. Note the matrices they show are normalized to be less than 1. So its just not clear what range colors are suppose to take. Well not without more work.

I have no special talents. I am only passionately curious.--Albert Einstein
delt0r

JGO Knight

Medals: 30
Exp: 18 years

Computers can do that?

 « Reply #5 - Posted 2013-05-06 15:05:52 »

To sort of back that up. Note that if a value is overflowing before a call to closestCol, it can still be overflowing after. So it seems the dithering values should be a portion of between color range.

I have no special talents. I am only passionately curious.--Albert Einstein
Porlus

Junior Devvie

 « Reply #6 - Posted 2013-05-06 16:36:38 »

Yeah the threshold values range from 1-64, so presumably it breaches its respective channel fairly often which explains the artifacts, but I'm not entirely sure how to normalise the threshold value. I've tried dividing the value by 64, which is the highest value that is held in the matrix, although I'm working in whole numbers and only one instance would yield 1 and the rest would be 0.
delt0r

JGO Knight

Medals: 30
Exp: 18 years

Computers can do that?

 « Reply #7 - Posted 2013-05-06 17:13:09 »

I think you want to normalize by the range of a band. So for this matrix it would be 16/65 for 16 levels per channel. Or 4/65 for 64 levels per channel. I am assuming the range is 0-255.

I have no special talents. I am only passionately curious.--Albert Einstein
Porlus

Junior Devvie

 « Reply #8 - Posted 2013-05-06 17:23:01 »

Ah I see. Do you know how I would apply this to my algorithm?
pjt33
 « Reply #9 - Posted 2013-05-06 22:10:11 »

This is just the method that reduces the amount of colours available in each channel:
 1  2  3 `private int closestCol(int c, int b) {   return c / b * b;}`
That's not finding the nearest colour: it truncates rather than rounding.

As to the normalisation, the Wikipedia article says
Quote
The algorithm renders the image normally, but for each pixel, it adds a value from the threshold map, causing the pixel's value to be quantized one step higher if it exceeds the threshold.

So in your case with an 8x8 dither matrix you want to add bd * d / (8*8+1).

Putting that together,

 1  2  3  4  5  6  7  8  9 `      int c =  pixels[y * w + x];      int d = dither[(y & 7) * 8 + (x & 7)];      int l = dither.length;      int r = ((c >> 16) & 0xff);      int g = ((c >> 8) & 0xff);      int b = (c & 0xff);      newpix[y * w + x] = 0x000000 | closestCol(r, d, bd, l) << 16 | closestCol(g, d, bd, l) << 8 | closestCol(b, d, bd, l);`

and

(corrected below)
Porlus

Junior Devvie

 « Reply #10 - Posted 2013-05-06 22:20:10 »

Thanks for the reply. That seems to work far better. It's just that it looks very bright. The image becomes saturated by light.
pjt33
 « Reply #11 - Posted 2013-05-06 22:25:01 »

Yes, because there's a bias up but no bias down. Actually it seems to be preferable to counter the bias up from the threshold with an intentional bias down so that on average they cancel:

(Corrected below)
Porlus

Junior Devvie

 « Reply #12 - Posted 2013-05-06 22:32:23 »

Thanks for your help. I'll have a sit down and try and understand it.
pjt33
 « Reply #13 - Posted 2013-05-06 22:32:58 »

Actually I stupidly lost the quantisation. The corrected version is
 1  2  3  4 `   private static int closestCol(int col, int threshold, int quantum, int ditherSize) {      int quantised = quantum * (int)(col / quantum + threshold / (ditherSize + 1f) + 0.5);      return quantised > 255 ? 255 : quantised;   }`

And of course there's always the option of offsetting things so that you have a half interval at each end and both true black and true white are possible.
Porlus

Junior Devvie

 « Reply #14 - Posted 2013-05-06 22:43:25 »

Thanks. I'll substitute it.
theagentd

« JGO Bitwise Duke »

Medals: 366
Projects: 2
Exp: 8 years

 « Reply #15 - Posted 2013-05-06 22:59:31 »

(int)(quantised + 0.5f) = quantised since quantised is an int. That part does absolutely nothing.

Myomyomyo.
Roquen
 « Reply #16 - Posted 2013-05-07 04:48:27 »

Keep it simple.  Throw away some bottom bits, add (or sub) the dither, throw away some bottom bits.  Goof around with that...you'll need to clamp unless you account over or underflow (add vs. sub).

R = ((R & ~0xF)+D)&~0xF.
pjt33
 « Reply #17 - Posted 2013-05-07 07:18:06 »

(int)(quantised + 0.5f) = quantised since quantised is an int. That part does absolutely nothing.
This is why I shouldn't write code after midnight. I've edited to correct, because the number of versions is getting confusing. Thanks.
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 rwatson462 (31 views) 2014-12-15 09:26:44 Mr.CodeIt (23 views) 2014-12-14 19:50:38 BurntPizza (50 views) 2014-12-09 22:41:13 BurntPizza (84 views) 2014-12-08 04:46:31 JscottyBieshaar (45 views) 2014-12-05 12:39:02 SHC (59 views) 2014-12-03 16:27:13 CopyableCougar4 (57 views) 2014-11-29 21:32:03 toopeicgaming1999 (123 views) 2014-11-26 15:22:04 toopeicgaming1999 (114 views) 2014-11-26 15:20:36 toopeicgaming1999 (32 views) 2014-11-26 15:20:08
 Rayvolution 37x LiquidNitrogen 35x basil_ 31x HeroesGraveDev 27x BurntPizza 18x kevglass 17x appel 17x Gibbo3771 15x kpars 15x gouessej 14x princec 13x Riven 11x SHC 10x Ecumene 10x KevinWorkman 9x VIrtueeL 9x
 Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org