Pages: 1 ... 5 6 [7]   Go Down

Author Topic: Is this Aliasing?  (Read 49859 times)

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #120 on: February 02, 2010, 02:16:07 pm »

Quote from: EsbenHR
Well, you do not appear to agree that "linear interpolation" means, by definition, connecting the original samples with straight lines.
I would say that the most common use of the term "interpolating" is that the interpolating function, f(x,y), satisfies f(x_i,y_i) = z_i for the sample set (i.e. the original samples).

Ignoring the terminology sideshow, what you want to do is quite different: you want to approximate the originally function (from which the samples are obtained) by approximating it with a function expressed as a sum of basis functions.

Hi, I think I tried to make my assumptions and definitions clear in my first message. I'm sorry if they were not fully clear. However, some of them are repeated below:

Quote from: joofa
Here is the intent of the interpolation in signal processing philosophy: If we are to reconstruct a continuous signal from its samples then how can the samples be obtained that the reconstructed signal using these samples is the "best" representation of that original possibly non-bandlimited function. The "best" part will be measured by error between original, possibly unknown, function and the reconstructed function.

Quote from: EsbenHR
When you say "linear interpolation", this means that the basis functions are triangular.

Yes, and that is linear interpolation.

Quote from: EsbenHR
Could we call this "reconstruction" to avoid the word war? Or is that too overloaded too in this context?

I have used the word "reconstructed signal" in my quoted text above.
« Last Edit: February 02, 2010, 02:21:39 pm by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

Jonathan Wienke

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 5829
    • http://visual-vacations.com/
Is this Aliasing?
« Reply #121 on: February 03, 2010, 08:26:07 am »

Quote from: joofa
Firstly, there is the correct interpretation of theory. Secondly, please don't put words in my mouth that I have not said or implied, just like you said above that I claimed something about gamma.

I'm not putting words in your mouth; "change the way we acquired the samples" is a direct quote from the last line of the first paragraph of YOUR post #117. In my universe, "acquiring the samples" is accomplished via an ADC chip taking some analog input signal and converting it to a series of numeric values. These original numeric values as output bu the ADC are "the samples". Values calculated by a reconstruction or interpolation algorithm are not "samples", they are educated guesses. Increasing the number of samples can increase the maximum amount of fine detail an image can contain, increasing the number of interpolated/reconstructed values cannot. The best they can do is aid us in more accurately interpreting the meaning of the samples we have.

Given that, the only way to "change the way we acquired the samples" in my world is to use a different ADC chip, or alter the mechanism feeding the analog signal to the ADC chip. This is obviously not practical in the context of processing images captured with whatever camera one has; it is unrealistic to expect someone to buy a new camera just so some flavor of "linear interpolation" will work better.

Similarly, when you claim "linear interpolation" can cause ringing, if you fail to define how your definition of "linear interpolation" differs from the most common definition of "linear interpolation", you risk looking like an idiot because the commonly-defined version of "linear interpolation" can never cause ringing, clipping, or overshoot.

I'm not trying to be a dick here; I'm trying to figure out exactly what you are saying. You seem to be a bit like Humpty Dumpty, taking the position that words mean whatever you say they mean, and I'm taking the position that words have specific, and generally well-established meanings, and using words contrary to those meanings causes confusion. What you call "linear interpolation" is very different from the notion of "linear interpolation" as commonly used in image processing, digital signal processing, and many other scientific fields. Your notion of a "sample" seems to similarly deviate from common usage.
Logged

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #122 on: February 03, 2010, 09:35:36 am »

Quote from: Jonathan Wienke
Given that, the only way to "change the way we acquired the samples" in my world is to use a different ADC chip, or alter the mechanism feeding the analog signal to the ADC chip. This is obviously not practical in the context of processing images captured with whatever camera one has; it is unrealistic to expect someone to buy a new camera just so some flavor of "linear interpolation" will work better.

I don't know why are you constantly ignoring what I have repeatedly said that there exist techniques to account for the fact that the samples were not acquired in the way mandated by the reconstructed kernel. I have said that a number of times but you keep on skipping  that. There  is NO need to use a different ADC.

I just worked an example for you where I took the samples as acquired by whatever "ADC" and still be able to accomplish the linear approximation in L2 sense. Please note that I have worked out this example very quickly, it is not the best, and there are certain hacks in there, and it can be made better, but it is just to illustrate that you don't need to change "ADC's".

Click here to see an actual image of Lena.

Click here to see image doubled in size with "straight" linear interpolation.

Click here to see image doubled in size with linear approximation in L2 sense.

The L2 approximated one looks sharper than straight linear interpolation with a lot of ringing artifacts. But as I said it was just done in a "shortcut" way and there is hope to make it better. But the point is that I did not change any ADCs.
« Last Edit: February 03, 2010, 09:36:05 am by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

Jonathan Wienke

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 5829
    • http://visual-vacations.com/
Is this Aliasing?
« Reply #123 on: February 03, 2010, 09:53:24 am »

Quote from: joofa
But the point is that I did not change any ADCs.

Nor did you acquire any "new" samples, you simply processed the same set of samples (the original Lena image) in different ways using different algorithms. You didn't change the way you acquired the samples, you changed the way you processed them. There's a big difference, kind of like the difference between lightning and a lightning bug.
« Last Edit: February 03, 2010, 09:56:16 am by Jonathan Wienke »
Logged

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #124 on: February 03, 2010, 11:07:28 am »

Quote from: Jonathan Wienke
Nor did you acquire any "new" samples, you simply processed the same set of samples (the original Lena image) in different ways using different algorithms. You didn't change the way you acquired the samples, you changed the way you processed them. There's a big difference, kind of like the difference between lightning and a lightning bug.

Are you nitpicking or really not following all of this stuff? Here is what was done: I have the regular samples, and know the reconstruction and sampling kernels so I derived a fast and somewhat crude approximation to what would have been the samples if they were acquired with the application of the right sampling kernel in the analog domain. With this new set of samples I did the standard linear interpolation.

However, one does not even need to do all of this. There are more sophisticated methods rooted in theory on how to deal with such situations.

Quote from: Jonathan Wienke
... you risk looking like an idiot ....  You seem to be a bit like Humpty Dumpty, taking the position that words mean whatever you say they mean, ...

I guess this conversation is over. As I mentioned before it takes a lot of time for me to research and prepare my responses for online forums. I wrote a small program only to illustrate my point to you. And, I can't continue doing this effort if we tread into issues of civility.
« Last Edit: February 03, 2010, 11:34:02 am by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #125 on: February 03, 2010, 11:25:12 am »

Deleted.
« Last Edit: February 03, 2010, 11:25:45 am by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

crames

  • Full Member
  • ***
  • Offline Offline
  • Posts: 210
    • http://sites.google.com/site/clifframes/
Is this Aliasing?
« Reply #126 on: February 03, 2010, 01:29:41 pm »

Quote from: joofa
I just worked an example for you where I took the samples as acquired by whatever "ADC" and still be able to accomplish the linear approximation in L2 sense. Please note that I have worked out this example very quickly, it is not the best, and there are certain hacks in there, and it can be made better, but it is just to illustrate that you don't need to change "ADC's".

Click here to see an actual image of Lena.

Click here to see image doubled in size with "straight" linear interpolation.

Click here to see image doubled in size with linear approximation in L2 sense.

The L2 approximated one looks sharper than straight linear interpolation with a lot of ringing artifacts. But as I said it was just done in a "shortcut" way and there is hope to make it better. But the point is that I did not change any ADCs.
Joofa,

The extra sharpness of the L2 version is interesting (although it looks like some jpeg artifacts got in the way).

Do you have a reference that describes that method?

Cliff
Logged
Cliff

Bart_van_der_Wolf

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 8913
Is this Aliasing?
« Reply #127 on: February 03, 2010, 02:48:21 pm »

Quote from: crames
The extra sharpness of the L2 version is interesting (although it looks like some jpeg artifacts got in the way).

Do you have a reference that describes that method?

I'm also a bit puzzled by the 'actual' Lena image (an image which I know as a larger color image) since it's smaller than any version I've seen used as a standard and there seem to be different versions around. Here are a few versions and we could adopt one as a relevant version. The lena512.bmp version could serve as one that could presumably be used by all who wish to experiment on something without introducing another variable, a different source image. Of course it becomes a lot bigger when it gets resized 2x linearly, 4x in number of pixels (to explain my use of the term linear  ), so one might prefer to compare crops.

Cheers,
Bart
« Last Edit: February 03, 2010, 07:17:59 pm by BartvanderWolf »
Logged
== If you do what you did, you'll get what you got. ==

ejmartin

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 575
Is this Aliasing?
« Reply #128 on: February 03, 2010, 04:40:16 pm »

Quote from: BartvanderWolf
I'm also a bit puzzled by the 'actual' Lena image [...] since it's smaller than any version I've seen

Obviously he changed the way the samples were acquired  
« Last Edit: February 03, 2010, 04:41:31 pm by ejmartin »
Logged
emil

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #129 on: February 03, 2010, 05:30:31 pm »

Quote from: crames
Joofa,

The extra sharpness of the L2 version is interesting (although it looks like some jpeg artifacts got in the way).

Do you have a reference that describes that method?

Cliff, I did not follow any published procedure. As I said I did a quick and dirty job at approximating the samples I wanted. Basically I took a cue from how the convergence coefficients are determined for Gabor expansions and derived a biorthogonal filter to the linear interpolation and used that with Lena image.

I also noticed the jpeg compression artifacts. I did not mess with quality parameters etc., as I was not aiming for anything fancy.

Quote from: ejmartin
Obviously he changed the way the samples were acquired  

Emil, that is very funny indeed!  
« Last Edit: February 03, 2010, 05:31:40 pm by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

crames

  • Full Member
  • ***
  • Offline Offline
  • Posts: 210
    • http://sites.google.com/site/clifframes/
Is this Aliasing?
« Reply #130 on: February 03, 2010, 06:36:30 pm »

Quote from: joofa
I also noticed the jpeg compression artifacts. I did not mess with quality parameters etc., as I was not aiming for anything fancy.
It seems that your Lena had the jpeg artifacts before going through your routine. I wonder how it would look on (a reduced version of) Bart's "clean" Lena?
Logged
Cliff

EsbenHR

  • Newbie
  • *
  • Offline Offline
  • Posts: 41
Is this Aliasing?
« Reply #131 on: February 03, 2010, 07:11:27 pm »

Quote from: joofa
I just worked an example for you where I took the samples as acquired by whatever "ADC" and still be able to accomplish the linear approximation in L2 sense. Please note that I have worked out this example very quickly, it is not the best, and there are certain hacks in there, and it can be made better, but it is just to illustrate that you don't need to change "ADC's".

The L2 approximated one looks sharper than straight linear interpolation with a lot of ringing artifacts. But as I said it was just done in a "shortcut" way and there is hope to make it better. But the point is that I did not change any ADCs.


OK, I'll bite!

So, let's forget the L2-norm and say, instead, that we assume the (continuous) image on the sensor (yeah, Lenna was scanned, work with me here) is piecewise linear and a remarkable piece of luck would have it that the pieces are all between the nearest pixel centers :-)

So, what would that look like, if we assume that the acquired pixels represents the average of the function? That is we assume pixels are noise-free, the fill-factor is 100% etc.?
As attached I would think. I hope you can see which is which ;-)


Here is the code which should work in Matlab or any halfway decent clone (the above was an ancient Octave):
% Load image.
img1 = double(imread('lena512.png'));

% Truncate an inverse (use a window to suck less).
F = 1024;
t = [zeros(1,100), [1, 6, 1]/8, zeros(1,F - 103)];
T = real(ifft(1./fft(t)));
m = F - 100;
f = T(m-5:m+5);

% Apply inverse.
img2 = conv2(img1, f,  'same');
img2 = conv2(img2, f', 'same');

% Upscale N times (original image in the example).
N = 4;
up = img1;
[H,W] = size(up);
up = reshape(up, [1, H, 1, W]);
up(N,1,N,1) = 0;
up = reshape(up, [H*N, W*N]);

% Filter using desired kernel (bilinear kernel in example).
k = [1, 2, 3, 4, 3, 2, 1]/4;   % Bilinear
%k = [1, 1, 1, 1];             % Nearest neigbour
up = conv2(up, k'*k, 'same');

% Write result back.
imwrite('lena-out1.png', uint8(up));
[attachment=19971:lena_test.png]
Logged

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #132 on: February 03, 2010, 07:21:50 pm »

Quote from: crames
It seems that your Lena had the jpeg artifacts before going through your routine. I wonder how it would look on (a reduced version of) Bart's "clean" Lena?

Hi Cliff,

You are right the Lena I was working with was apparently not very faithful.

I downloaded the Bart's "clean" Lena (thanks Bart). I had to convert the bmp to jpeg before I could do anything as I was working in jpeg. I upscaled from 512x512->1024x1024. Here are two crops out of the 1024x1024 ones:

Click here for regular linear interpolation.

Click here for L2 linear approximation.

The L2 ones seems sharper and those bad ringings are suppressed a lot.

Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

Jonathan Wienke

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 5829
    • http://visual-vacations.com/
Is this Aliasing?
« Reply #133 on: February 03, 2010, 07:40:50 pm »

Quote from: joofa
Are you nitpicking or really not following all of this stuff?

I suppose I'm nitpicking, in the interest of coming to a common definition of the meanings of terms. You can't have a meaningful discussion without having a common understanding of the meaning of the terms used in the conversation. As an example, your usage of the terms "linear interpolation" and "sample" are very different than their most common definitions, and as a result, it is sometimes difficult to to tell whether what you are saying is insightful or gibberish.
Logged

crames

  • Full Member
  • ***
  • Offline Offline
  • Posts: 210
    • http://sites.google.com/site/clifframes/
Is this Aliasing?
« Reply #134 on: February 04, 2010, 08:21:19 am »

Quote from: EsbenHR
OK, I'll bite!

So, let's forget the L2-norm and say, instead, that we assume the (continuous) image on the sensor (yeah, Lenna was scanned, work with me here) is piecewise linear and a remarkable piece of luck would have it that the pieces are all between the nearest pixel centers :-)

So, what would that look like, if we assume that the acquired pixels represents the average of the function? That is we assume pixels are noise-free, the fill-factor is 100% etc.?
As attached I would think. I hope you can see which is which ;-)
If I'm reading your code correctly, you're filtering with the inverse of a triangular psf ([1 6 1]/8), then interpolating?

It might be better to interpolate first, then inverse filter, to reduce the jaggies on the diagonal hat brim (as in my sharpening demo, above). Otherwise, the inverse filtering seems to help a lot.
Logged
Cliff

EsbenHR

  • Newbie
  • *
  • Offline Offline
  • Posts: 41
Is this Aliasing?
« Reply #135 on: February 05, 2010, 05:21:02 am »

Quote from: crames
If I'm reading your code correctly, you're filtering with the inverse of a triangular psf ([1 6 1]/8), then interpolating?

It might be better to interpolate first, then inverse filter, to reduce the jaggies on the diagonal hat brim (as in my sharpening demo, above). Otherwise, the inverse filtering seems to help a lot.
Yes, you are correct that is exactly what it does.
Certainly your suggestion would result in better images.

However, the job I set out to do was to create a continuous image which a sensor (ideal, no noise, 100% fill factor etc.) would return the values we were given in the file.

So it is not at attempt to create a good image; it is an attempt to create an image which would theoretically measure the image in the file.
The [1 6 1], which is inverted, express the fact that a triangular basis function has 1/8 of its mass on each of the neighbor pixels.

The point was to show that if we have an image model (in this case a very simple-minded model: "the image is piecewise linear") and a sensor model (here: each pixel measures the light exposed on its area) then we can construct a plausible image. If we accept those terms, then we get ringing.

[ Actually, I guess the sensor integral is in gamma 1.0 so actually we would need to transform the image before and after load. It would likely be even uglier but be more true to the stated assumptions.]
Logged

ejmartin

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 575
Is this Aliasing?
« Reply #136 on: February 05, 2010, 08:56:53 am »

It would seem that the image formation model one wants is that in a region of steep gradient, that the second derivative of the image does not change sign for a given distance from the steep gradient.  This would prevent or at least dampen ringing (which I for one find more objectionable than a little softness).
Logged
emil

EsbenHR

  • Newbie
  • *
  • Offline Offline
  • Posts: 41
Is this Aliasing?
« Reply #137 on: February 05, 2010, 12:03:21 pm »

Quote from: ejmartin
It would seem that the image formation model one wants is that in a region of steep gradient, that the second derivative of the image does not change sign for a given distance from the steep gradient.  This would prevent or at least dampen ringing (which I for one find more objectionable than a little softness).

Yes, I believe that is the kind of thinking we need. Ups, we just entered the non-linear territory :-)

Anyway, I personally lean towards the idea that we might not have a derivative everywhere.
Logged

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #138 on: February 05, 2010, 12:18:37 pm »

Quote from: Jonathan Wienke
... your usage of the terms "linear interpolation" and "sample" are very different than their most common definitions, and as a result, it is sometimes difficult to to tell whether what you are saying is insightful or gibberish.

In the signal processing literature there is a technical difference between interpolation and approximation. Interpolation means that the signal value at original location is kept the same while filling in-between detail. Approximation means that signal value at original locations is not necessarily kept the same.

I have tried to maintain this difference in my posts. I have talked about 2 sets of data we are going to interpolate. One is the actual samples and other a derived set of samples. When we fill in values in both of these separate sets I have been using linear interpolation, since at original locations in each set of samples I am keeping the data values intact.

However, once everything is done and when we compare the results of both sets then, of course, the interpolated values at the original locations in the derived set is going to differ from the first set, because the samples in the two sets were different to start with before any interpolation in each of them was done,  and in this sense it may be called approximation now.

If you notice I have used the words "linear approximation" in this final comparison phase in my posts #123 and #133 in those "Click here ..." sentences.
« Last Edit: February 05, 2010, 01:53:24 pm by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins

joofa

  • Sr. Member
  • ****
  • Offline Offline
  • Posts: 544
Is this Aliasing?
« Reply #139 on: February 05, 2010, 03:28:06 pm »

Quote from: EsbenHR
The point was to show that if we have an image model (in this case a very simple-minded model: "the image is piecewise linear") and a sensor model (here: each pixel measures the light exposed on its area) then we can construct a plausible image. If we accept those terms, then we get ringing.

It would appear to me that the joint effect of inverse-triangular-linear model may not be too simple. If I understood it correctly, here is the overall system response in this case:



It moves a little upwards around Nyquist, which causes the sharpening, but it is close to the ideal flat response. Below is the response of inverse-triangular-nearest-neighbor:



As expected, it has higher overshoots and would cause more of those nasty jaggies effect.
« Last Edit: February 05, 2010, 03:44:37 pm by joofa »
Logged
Joofa
http://www.djjoofa.com
Download Photoshop and After Effects plugins
Pages: 1 ... 5 6 [7]   Go Up