Interesting thing about fractional binning

[vlaiv]

This one is still bugging me.

How come that SNR improvement in x1.5 bin is x2 instead of x1.8?

I created "simulation" of what happens. I've taken 4 subs consisting of gaussian noise with standard deviation of 1. Then I multiplied first sub with 4, second and third with 2 and did not touch the last one. Added those together and divided with 9.

As expected, result of this procedure is noise with stddev of 0.555 as per measurement:

To attest that algorithm is working, here is small image 9x9 pixels that consists of pixel values 0,1,2,3, ..., 8 and result of bin x1.5:

Just to verify that all is good, here are values of pixels in original and binned version:

Let's do first few pixels by hand and attest it's working.

(4*0 + 2*3 + 2*1 + 4)/9 = 12 / 9 = 1.3333

(2*3 + 4*6 + 2*7 + 4) / 9 = 5.33333

(2*1 + 2*5 + 4*2 + 4)  / 9 = 2.66666

(8*4 + 2*5+2*7+4) / 9 = 6.66666

Everything seems to be in order - resulting pixel values are correct.

However stddev of image binned x1.5 is lower by factor of x2 rather than by factor of x1.8, even if I remove correlation by splitting it.

This is sooo weird

[sharkmelley]

I'm very late to this thread but it looked interesting.  Did you find your problem?

In any case I simulated this in a spreadsheet and found that 1.5x binning leads to a SNR reduction of 1.8x, which is what you expected.

I generated 10,000 groups of 9 random values.  Each group of 9 values was binned down to 4 values using your algorithm.  This created 10,000 groups of 4 values.

The SNR of the resulting 40,000 values was 1.8x lower than the SNR of the original 90,000 values.

Mark

 

Edited November 16, 2019 by sharkmelley

[vlaiv]

1 hour ago, sharkmelley said:

I'm very late to this thread but it looked interesting.  Did you find your problem?

In any case I simulated this in a spreadsheet and found that 1.5x binning leads to a SNR reduction of 1.8x, which is what you expected.

I generated 10,000 groups of 9 random values.  Each group of 9 values was binned down to 4 values using your algorithm.  This created 10,000 groups of 4 values.

The SNR of the resulting 40,000 values was 1.8x lower than the SNR of the original 90,000 values.

Mark

 

No, I have not - I've done something similar to what you've done, only with images - created 4 images with gaussian noise and weighted added them in the same way one would create fractional binned pixel - and yes, that way it produces x1.8 SNR increase.

Still unable to figure out why there is x2 SNR increase once I fractionally bin and split result so there is no correlation between pixel values.

[sharkmelley]

1 hour ago, vlaiv said:

No, I have not - I've done something similar to what you've done, only with images - created 4 images with gaussian noise and weighted added them in the same way one would create fractional binned pixel - and yes, that way it produces x1.8 SNR increase.

Still unable to figure out why there is x2 SNR increase once I fractionally bin and split result so there is no correlation between pixel values.

If the fractionally binned image is split into 4 sub-images then you're right in saying that there is no correlation between them.  I'm seeing the same standard deviation (on average) in each of the 4 sub-images as I do in the fractionally binned image.

Mark

[vlaiv]

17 minutes ago, sharkmelley said:

If the fractionally binned image is split into 4 sub-images then you're right in saying that there is no correlation between them.  I'm seeing the same standard deviation (on average) in each of the 4 sub-images as I do in the fractionally binned image.

Mark

That one really bugs me. I simply can't figure out the difference. When we do fractional binning and split image - this should happen:

We take only red squares (not perfectly aligned to edges - but it should be seen as taking whole top left pixel and respective areas of other 3 pixels). That is exactly the same as taking 4 subs and weighted adding them in 1:1/2:1/2:1/4 ratio. Yet two approaches differ in resulting standard deviation.

[vlaiv]

Ok, it looks like I'm on to something in solving this puzzle.

For a moment I thought that there can't be any other reasonable solution except that maybe random generated numbers are not random in true sense. It occurred to me that computers use pseudo random number generators - and these tend to be cyclic in their nature (although for most purposes they are indeed random). Maybe it happened that by pure chance I tested my algorithm on configuration of data that somehow exploits cyclic nature of PRND.

To be sure I devised an experiment - it would consist of generating random noise image of 900x900 pixels and doing two approaches to generate same data set - one would be use of fractional binning and then splitting image in 4 sub sets and measuring one of them, while the other method would be to first split 900x900 image in 9 subsets (3x3 pattern) and then using sub sets (0,0), (0,1), (1,0) and (1,1) to do weighted summation. These should produce two identical image results (which could be verified by subtracting them and looking at the difference - which should be precisely 0 filled image if two are the same) - and in no way they should have different standard deviation. By examining difference I was hoping to get the idea what might be happening.

I started off by generating 900x900 gaussian noise image and I did x1.5 bin on it. To verify that it produces x2 SNR improvement I ran the stats on it and - Result was stddev of 0.555!

That is not the same thing that happened before! I repeated the test with another size just to make sure, and yes - again result of stddev was 0.555. How on earth did I get stddev of 0.5 last time I tried this?

Then I remembered my hypothesis about cyclic nature of random generator and sure enough, I remembered that I used 512x512 test image in previous case where I had stddev of 0.5. So I tried it again - result was also 0.5 - then I realized important fact - 512 side image aligns rather well with 16bit value (a WORD in computing terms), but also with 32bit value. In case that PRND is using base 16 or base 32bits - it could lead to cycling and values would not be acting as true random noise.

To repeat the findings, here are measurements of: 100x100, 200x200, 256x256 (again base 2 - 16 bit result), 400x400, 512x512, 800x800 and 1024x1024 all being binned x1.5 and measured for noise:

Not quite what I expected, but I think it will bring me closer to solution

100, 400 and 1024 sides "bin properly", while 200, 512 and 800 - don't. 900 side also bins properly.

It looks like those images that have side that has reminder of 2 when divided by 3 return wrong result. This points to implementation error rather than PRND issue I described above.

Issue solved! It is due to "feature" of algorithm that I implemented that tests show this behavior. Because binned result will not always match original sides I implemented "offset" which I totally forgot about

If for example we want to bin 7 pixels by x1.5, resulting image can have 4 pixels. One way it can be done is to use pixels 1,2,3 to produce first two pixels of output, and pixels 4,5,6 to produce next two and disregarding pixel 7 as extra. Or one could choose not to start at pixel boundary but half way "between" (starting at 1/3 of first pixel and finishing at 2/3 of last pixel) so that binned image is more centered on original image and no pixels are wasted .

It also means that above reasoning with aligned pixels is only viable in some cases while not in other (where there is that offset).

 

[sharkmelley]

17 hours ago, vlaiv said:

Issue solved! It is due to "feature" of algorithm that I implemented that tests show this behavior. Because binned result will not always match original sides I implemented "offset" which I totally forgot about

I'm glad you fixed it!