Tuesday, September 25, 2012

SOCIS - part 7

After POT is applied to an input image we obtain a transformed image in which the value of each pixel no longer corresponds to a light intensity at a specific wavelength. We can still however plot bands from the transformed image and see what they look like. To that end, I initially plotted the transformed bands for: original POT, POT with the simple smoothing formula, POT in which for each we've faked a 0 mean result. These plots can be found here [1]. Let's inspect bands 13, 19 and 37. These are the bands, I have used in all previous example images, to represent the blue, green and red wavelengths.
I will only add here the plot for band 13, in the 3 cases. The rest can be found at [1].

This band is particularly interesting because, unlike the other 2, we can clearly see discontinuities in the original POT plot. These discontinuities in the transform domain seem to correspond to the discontinuities we've seen on the image after lossy compression, such as here [2].

What's important to note is that, in the smoothed image, the discontinuities are gone. As we know, the smooth image doesn't have discontinuities either, but there's still the problem of blurriness. Where does that come from? Maybe, like in the case of the discontinuities, it is present in just one of the 3 bands chosen for red, green and blue and affects the entire image when constructing the composite image. But what can we do to solve this problem? In order to answer this, we have to plot another case.

A while back I tested the case of applying POT to the image as if it were a single line. This just means that if the image has dimensions Z, Y, X (Z = number of bands, Y = number of lines, X = number of columns), then we consider it of dimensions Z, 1, X * Y. In that case, we obtained the following:

Looks better than our blurry image, but why is that? Well, I plotted the transformed single line case [3], just like the others and compared it to the smooth case to see what was different. What I noticed was that both were free of discontinuities but there was a better contrast in the single line case (e.g. the difference in intensities between a lake and it's surroundings was greater than in the simple smoothing case). I was thinking that the mean in the single line case is for all lines. So then I thought that maybe for each line I could use a mean which is an average of all previous means. I tried that (rots were still smoothed with the original formula) and didn't get a better result. The image was still blurry. However, a plot of the means showed that they were very nicely smoothed. I then decided to try the same thing for the rots as well and it seems to have worked. The result looks very similar to the single line case:

The plots for the means and the rotations can be found here [4][5]. As can be seen, they are much smoother than anything previously obtained.
To explain in a bit more detail what I did exactly: at each step we compute a rotation parameter tCurrent and a mean mCurrent. The POT uses exactly these values which were computed. In this "averaged smoothing" the actual values that are used, let's call them tNew and mNew, are averages over all previous tCurrent or mCurrent values of the same band. Updating the average after each line can be done in constant time (keep current sum of elements and current element count), so there is no increase in either memory or time requirements.

A SNR plot will show how well this method behaves with respect to the original POT, the simple smoothing approach and the single line attempt. I made a mistake when making the SNR plots as I used the SNR values for the original POT and PSNR for the others. The next post will contain the correct plots. We can still look at one of the plots, just substitute SNR with PSNR:

We can see how the "averaged smoothing" approach performs better than both simple smoothing and single line. This PSNR plot is for reverse-waterfill rate allocation, not BIFR.

Tuesday, September 18, 2012

SOCIS - part 6

Picking up where the last post left off, I mentioned the idea of using a selective smoothing approach.

Since the variance of differences is already computed after each line (as mentioned in the previous post), this quantity can be used to implement selective smoothing. We've noticed that after smoothing an image, the variance of differences decreases. Therefore, when implementing selective smoothing I attempt to reduce the current variance. The condition for smoothing is that the relative difference between the current variance and the variance updated with |tCurrent - tPrev| be less than some threshold value.

Applying selective smoothing directly did not yield better results (discontinuities vanish, but the image is still blurry). I've proceeded to run some more tests to better determine the sources of both discontinuities and the blurriness. While discontinuities seem to originate from both t values and means, the blurriness seems to be mostly due to means.

Faking a 0 mean for each line in the transform yield this:

What's interesting to note is that even though discontinuities are present, the image is not as blurry as it is after smoothing the means as well (in this image the t values were smoothed).

To sum up, this week was mostly concerned with implementing the selective smoothing and testing various approaches to see how they affect the image. I will now try study the transformed image (right after applying POT) to see, in each band, what discontinuities appear and where in each case (without faking a 0 mean, with 0 mean).

Tuesday, September 11, 2012

SOCIS - part 5

Continuing from part 4 we discuss about smoothing and the methods employed to achieve this.

Last time we saw that certain anomalies appeared in the transformed image after the final smoothing attempt. The anomalies disappear when we do not take into account -1 to +1 (and viceversa) transitions of the t parameter and just use the simple smoothing formula tNew = 0.98 * tPrev + 0.02 * tCurrent.
The problem with this attempt is that the resulting image, while being free of discontinuities, becomes very blurry.

For my next attempt I've been testing a smoothing formula which is a weighted sum of previous t values (same for means). The weights of each previous t value grows exponentially as you approach the current line (so the previous line has the largest weight). For example: tNew = (tCurrent + 2 * t(j - 3) + 4 * t(j - 2) + 8 * t(j - 1)) / 15
This method yields slightly better results than the simple smoothing formula with just the previous t value, when the number of previous values used is 4. When I say 'slightly' I mean barely noticeable... the bifr images for 0.2 bpppb look identical, however for 0.15 bpppb this method gives a slightly better smoothing. 
You can see a comparison of the 2 cases below:

I've compared the metrics of this case with those from the simple smoothing formula and what I've noticed is that the variances and -1 to +1 jumps are roughly the same, while metric 3 is much larger in the weighted sum implementation, so for lossy compression it doesn't have much influence. I've also tested for 2, 3 and 4 previous values and what I've noticed is that metrics 1 and 2 decrease and discontinuities disappear. However, the image becomes blurry so it's clear that this method is not good enough (not to mention the memory requirements associated with retaining previous values).

When considering how to eliminate discontinuities, the variances of differences is clearly a factor, reducing it is important. Also reducing the number of -1 to +1 (and viceversa) jumps is also important. To that end, I have incorporated an online variance computing implementation into the POT code for use in smoothing. The implementation relies on the algorithm found here [1]. 

The next thing worth exploring is perhaps a selective smoothing, which might solve both the discontinuities and the blurring problems. The idea is to smooth only component for which the t differences exceed a given threshold or change the variance significantly, while leaving the other values the way the are.

Monday, September 3, 2012

SOCIS - part 4

This post is concerned with a first attempted smoothing implementation incorporated into the POT software.

As mentioned in the beginning, the purpose of this project was to eliminate discontinuities which arose from using the pairwise orthogonal transform. In the previous post we saw how we can have strong variations of the rotation parameter. One approach at solving the discontinuity problem would be to 'smoothen' this parameter. A simple way of doing this is with the formula tNew = 0.875 * tPrev + 0.125 * tCurrent. In this formula we see that the new value for the rotation parameter is biased mostly towards the previous value thus decreasing large variations.

Let's see some comparative images. First without any smoothening:

We've seen this before. The left-most image is the original, the middle image is after applying POT and BIFR (non optimal rate allocation) and the right-most is after applying POT and waterfill. The discontinuities are clearly visible.
Now we have a look at how things improve by using the previous formula:

It's somewhat better, but the discontinuities are still very much there. "VERT" comes from vertical, because the smoothening is vertical, that is the rotation parameters are smoothened according to previous values from the same band.
Notice the variation of the t parameter after smoothing:

Clearly we can do better. For starters, let's see what happens if we increase the smoothing, that is, we change the formula so that we have more bias towards the previous value, to something like: tNew = 0.98 * tPrev + 0.02 * tCurrent.
In this case the images look like this:

Even better, but we still have discontinuities. And what about the t parameter?

We haven't taken into account something, which is the fact that the t parameter is periodic on the interval [-1,1]. This means that if we have a current t value of -0.98 and a previous value of 0.8, then when applying the formula, the actual value we should use for tCurrent should be 1.02 because of the periodicity, to obtain a final result slightly greater than 0.8. Care should be taken so that when situations like this arise the final result is within the [-1, 1] interval. If we correct the formula to take into account this periodicity we obtain the following:


In the BIFR image the discontinuities are still noticeable. There is one more thing we can do and that is to smoothen the means as well. Initially the means for the image looked like this:

After we apply the same smoothing formula (no worries about periodicity this time) we get this:

And our result for the image is:

This time we can say that no discontinuities are visible in either image.

There is still one thing to be fixed in this case and that is an anomaly which can be seen in the image, discontinuities which appear in the northern part. They seem to have appeared after adapting the formula to take into account t's periodicity.

Correcting this shouldn't be a problem.

What comes next is to incorporate the metrics computations into the POT software and adjust the smoothing method accordingly. For now, the formula is fixed/constant. In terms of implementation, the correction can be easily achieved by having a class which specifically handles this sort of things and passing along a references of an instance of this class to all other methods.