Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (481)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (547)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Bayer ordered dithering  (Read 2206 times)
0 Members and 1 Guest are viewing this topic.
Offline Porlus

Junior Member





« 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?

Just for reference, I've been consulting with this page: http://en.wikipedia.org/wiki/Ordered_dithering

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

Thanks,

Paul
Offline Porlus

Junior Member





« 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.
Offline delt0r

JGO Knight


Medals: 27
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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Porlus

Junior Member





« 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.
Offline delt0r

JGO Knight


Medals: 27
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
Offline delt0r

JGO Knight


Medals: 27
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
Offline Porlus

Junior Member





« 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.
Offline delt0r

JGO Knight


Medals: 27
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
Offline Porlus

Junior Member





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

Ah I see. Do you know how I would apply this to my algorithm?
Offline 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)
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Porlus

Junior Member





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

Thanks for the reply. That seems to work far better. Smiley It's just that it looks very bright. The image becomes saturated by light.
Offline 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)
Offline Porlus

Junior Member





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

Thanks for your help. Smiley I'll have a sit down and try and understand it.
Offline 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.
Offline Porlus

Junior Member





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

Thanks. Smiley I'll substitute it.
Offline theagentd
« 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.
Offline 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.
Offline 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.

atombrot (26 views)
2014-08-19 09:29:53

Tekkerue (24 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (13 views)
2014-08-16 06:20:21

Tekkerue (20 views)
2014-08-16 06:12:11

Rayexar (58 views)
2014-08-11 02:49:23

BurntPizza (38 views)
2014-08-09 21:09:32

BurntPizza (30 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!