"Good" FIRs with no negative parts

Hi Jerry,
Thanks for kind words; they mean a lot!
Regards,
Steve

SteveSmith wrote:
> Hi Michel,
> Let me suggest that you are thinking about this problem in a fundamentally
> wrong way.  You have image 1, and want to create image 2 that is a
> different size.  Further, you want image 2 to be similar to image 1 "in
> some sense."   In other words, the two images cannot be identical, so
> you need to define a criterion for measuring the "correctness" of
> image 2.  The method you are trying (frequency band filtering with
> decimation/interpolation) achieves this "in the sense" that the two
> images have similar frequency spectra.
>
> Here's the catch.  The information you are dealing with is encoded in
> the spatial domain, not the frequency domain.  That is, you are interested
> in the spatial patterns, their edges, their positions, their amplitudes,
> and so on. Accordingly, you want image 2 to be similar to image 1 in
> "some sense" that is related to the spatial domain.  This is in
> contrast to, for example, an audio signal that is primarily encoded in the
> frequency domain.
>
> The problems you are seeing are a direct result of trying to manipulate
> the data in the wrong domain. For instance, when you perform simple
> filtering in the frequency domain, you create unpredictable artifacts in
> the spatial domain.  Instead, ask yourself this, "how should a pixel in
> image 1 affect each pixel in image 2?"  For instance, should an isolated
> bright pixel in the original image be converted to a single bright pixel in
> the new image?

That's a very pertinent way to present the problem, and it seems to
tell me that the solution would be something like a convolution with a
Gaussian function, as to me that's what I'd expect to see a single
bright pixel to turn into in a either smaller or larger image. Only I
can't help but think about the implications in the frequency domain,
which imply that the image will look softer, as the single bright
point itself will look much blurrier, and that I'll get some aliasing..

Ron N. wrote:
> On these types of images, I would be tempted to try some form
> of non-linear interpolation, adaptive to the local content,
> maybe selection from a set of splines based on neighboring
> median criteria or something...

I thought about something like splines as a possible solution,
although I know little about the properties of such filtering
techniques, but what do you mean by adaptive to the local content? I'm
not quite familiar with any sort of adaptive processing I must admit.

Rune Allnor wrote:
> If your images resemple astro images, you might want to ask this
> question in an astronomy newsgroup. There ought to be a few
> established and tested algorithms for dealing with images with
> these caharacteristics.

Thanks, that's a great suggestion, I didn't even think about it.
Because after all I'm necessarily not the first one to encounter that
kind of problem.

Greg Berchin wrote:
> In your case I
> would recommend something like window-based FIR filter design

A window based FIR.. you mean a FIR that would be a window function,
like, using (for example) a Blackman function as a FIR?

> except that you're convolving the window with
> a rectangular kernel in the time-domain (well, actually spatial-
> domain) instead of in the frequency-domain.

So if my previous assumption about what you said is correct, it would
look like the anti-derivative of my windowing function, mirrored?
Would that have an awfully "sincy" frequency response?

> I wonder, though, since we're already discussing nonlinear solutions, if
> addition of a small global bias to your images might allow you to use
> filters with "negative values", so that all pixel values remain
> positive or zero after the convolution.

Well I could do that, but only temporarily, as what's black would
ultimately have to be black, and thus negative values would have to be
discarded.

Vladimir Vassilevsky wrote:
> That reminds me of the old problem of what conditions should satisfy the
> frequency response of a filter so the step response can be monotonic. I
> don't know if there is hard and fast answer to this question; I may be
> wrong however it seems like if you want a filter with the response
> better then gaussian, there will be ripple.

If I get it right, it all comes down to this, if I don't mind time-
domain ripples I should go with a windowed sinc, if I absolutely want
a filter that is monotonic in the time domain I'm better off using a
gaussian, right?

Michel Rouzic wrote:

> Here's the problem, due to the overwhelming presence of black areas in
> my pictures, it leaves FIRs with negative values (such as Lanczos/
> windowed sinc FIRs) out of the equation (well it at least makes them
> far-from-ideal choices), as most of the time the result would be
> equivalent to setting the negative values of the FIR to 0 in the first
> place. So what options do I have left? I've looked at the DFTs of
> Blackman and Gaussian functions, and they would make pretty awful
> FIRs, as they have a huge transition bandwidth, they have virtually no
> "full" passband area (if that makes any sense), and the Gaussian
> function has a relatively bad stop-band attenuation, plus an infinite
> length.

I would read:

http://www.amazon.com/Deconvolution-Images-Spectra-Peter-Jansson/dp/0123802229

> To sum up things, I'm looking for a FIR function with, if possible, no
> negative values (but let's not leave non-negative Lanczos FIRs out of
> our considerations), and as narrow a transition bandwidth as possible.

Much of the book is about non-linear deconvolution for problems that 
can't go negative.  Absorption and emission spectra are two examples.
The basic idea is that linear deconvolution gives unnatural results in
many cases.  As FIR are linear you might be stuck, but the book will
at least explain why.

I bought mine when it was cheaper, though.

-- glen

On Nov 29, 1:35 am, Michel Rouzic <Michel0...@yahoo.fr> wrote:

> A window based FIR.. you mean a FIR that would be a window function,
> like, using (for example) a Blackman function as a FIR?

In window-based FIR filter design, one typically starts with some sort
of ideal response, such as an ideal lowpass filter.  Of course, this
produces a sinc impulse response that is of infinite extent.  So one
multiplies the impulse response by a suitable window function, such as
Hann, not only to trim the length from infinity down to something
finite, but also to guarantee smooth transitions at each end of the
impulse response.  Of course, in the frequency domain the original
ideal lowpass filter has thereby been convolved with the frequency
response of the window.

I said, "... something like window-based FIR filter design ...", and
by "something like" I meant that you would start with a rectangle-
shaped time (space) domain response, probably the width of one pixel
prior to resizing the image, or thereabouts.  Realizing that the sharp
edges on that rectangle will cause havoc in your resizing, in order to
smooth the edges you would convolve the rectangle with some
appropriate window function, such as Hann, the width of which was
somehow related to the minimum width and the minimum separation (in
pixels) of the bright spots on your image.  The result of this
procedure, in the frequency (1/space) domain, would be the
multiplication of the sinc-shaped frequency response of the original
rectangle by the frequency response of the window.

This technique is not without precedent.  Most DSP texts devote at
least a paragraph or two to designing FIR filters by convolving a
rectangular frequency response with a suitable window to create
nonzero-width transition bands.  The technique that I described above
is just the dual of that.

Greg

Michel Rouzic wrote:
> SteveSmith wrote:
>> Hi Michel,
>> Let me suggest that you are thinking about this problem in a fundamentally
>> wrong way.  You have image 1, and want to create image 2 that is a
>> different size.  Further, you want image 2 to be similar to image 1 "in
>> some sense."   In other words, the two images cannot be identical, so
>> you need to define a criterion for measuring the "correctness" of
>> image 2.  The method you are trying (frequency band filtering with
>> decimation/interpolation) achieves this "in the sense" that the two
>> images have similar frequency spectra.
>>
>> Here's the catch.  The information you are dealing with is encoded in
>> the spatial domain, not the frequency domain.  That is, you are interested
>> in the spatial patterns, their edges, their positions, their amplitudes,
>> and so on. Accordingly, you want image 2 to be similar to image 1 in
>> "some sense" that is related to the spatial domain.  This is in
>> contrast to, for example, an audio signal that is primarily encoded in the
>> frequency domain.
>>
>> The problems you are seeing are a direct result of trying to manipulate
>> the data in the wrong domain. For instance, when you perform simple
>> filtering in the frequency domain, you create unpredictable artifacts in
>> the spatial domain.  Instead, ask yourself this, "how should a pixel in
>> image 1 affect each pixel in image 2?"  For instance, should an isolated
>> bright pixel in the original image be converted to a single bright pixel in
>> the new image?
> 
> That's a very pertinent way to present the problem, and it seems to
> tell me that the solution would be something like a convolution with a
> Gaussian function, as to me that's what I'd expect to see a single
> bright pixel to turn into in a either smaller or larger image. Only I
> can't help but think about the implications in the frequency domain,
> which imply that the image will look softer, as the single bright
> point itself will look much blurrier, and that I'll get some aliasing..

It's hard to make a concrete suggestion -- hard even to speculate -- 
without knowing more about what the image represents. For stars, there 
is an easy specification. Stars image ideally as points, so any bright 
regions larger than a pixel are artifacts either of the optics (sensor, 
diffraction and aberrations) or blooming (the spreading of an 
overexposed image). Reducing the scale of such an image is done by 
reducing the extent of black between the spots of white, while leaving 
those spots relatively unchanged. (Implementing the specification is not 
quite so easy.)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> It's hard to make a concrete suggestion -- hard even to speculate --
> without knowing more about what the image represents.

Well the thing is, I was asking that question for two different
applications (and possibly more if in the future I meet that problem
again, for example I intend on creating an anti-aliased vector
graphics rasterizer, and by anti-aliased I mean better than the linear
anti-aliasing commonly used), one for an anti-aliased star field in a
space simulation, and the other one (which is the one I really asked
this question for) which consists in resampling images such as seen in
the first 3 examples on that page http://arse.sourceforge.net/examples.shtml

The problem here being resizing horizontally only (no vertical
resizing is performed) the horizontal lines of such images. As you see
them the lines in the images you see have been resized using a
windowed sinc, and while artifacts are hardly seen, they're important
enough to go over the -48 dB threshold needed to appear faintly on the
8-bit images (the intensity of the spectrogram is represented linearly
here)

> For stars, there
> is an easy specification. Stars image ideally as points, so any bright
> regions larger than a pixel are artifacts either of the optics (sensor,
> diffraction and aberrations) or blooming (the spreading of an
> overexposed image).

Back to my space simulation thing, if stars are supposed to appear as
single pixels, then how do you make them smoothly scroll from a
position to another? ;-) Right now I'm using a Gaussian function, and
it looks very smooth but a bit blurry.

> Reducing the scale of such an image is done by
> reducing the extent of black between the spots of white, while leaving
> those spots relatively unchanged. (Implementing the specification is not
> quite so easy.)

Sounds a bit like that "content aware" technique used to resize images
http://www.youtube.com/watch?v=qadw0BRKeMk