 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Can somebody who knows what they're talking about confirm this?
If I'm understanding this right, if I can find a complete set of
orthogonal functions, I should be able to construct any possible
function as a linear combination of them.
For example, the Fourier transform allows you to construct any function
from sine and cosine functions. (On the other hand, except in the
discrete case, you might need an infinite set of these functions to make
an exact reconstruction... but the discrete case is the one that really
interests me.)
If I'm not mistaken, "orthogonal" means that one function can't be
constructed from the others (so there's no duplication of
"information"), and "complete" just means you've got all the functions
you need.
So, like, how do you tell if two functions are orthogonal? And how do
you tell when a set of them is complete?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible a écrit :
> Can somebody who knows what they're talking about confirm this?
>
> If I'm understanding this right, if I can find a complete set of
> orthogonal functions, I should be able to construct any possible
> function as a linear combination of them.
>
That's just what being complete means. IIRC, orthogonal adds the
property that the linear combination is unique, i.e. you have a true
basis and not just a spanning set, as it seems to be called in English.
> If I'm not mistaken, "orthogonal" means that one function can't be
> constructed from the others (so there's no duplication of
> "information"), and "complete" just means you've got all the functions
> you need.
>
> So, like, how do you tell if two functions are orthogonal? And how do
> you tell when a set of them is complete?
Orthogonal means only one precise thing: their scalar product is 0.
Whether two functions are orthogonal really depends on the scalar
product you choose, and in turn on the set of functions you consider.
The common choice, for sufficiently well-behaved functions, is:
f.g = \sum{f g}, where . is the scalar product.
That's how you prove that the sine functions used in Fourier transform
are orthogonal.
Proving that a set is complete ordinarily means showing a way to build
the decomposition of any given element in the space you consider. When
you are in a finite dimension space it is easy enough, you check that
you have a number of vectors equal to the dimension of the space, and if
they are linearly independent (orthogonal to each other, for example)
you have a complete set...
--
Vincent
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>
> For example, the Fourier transform allows you to construct any function
> from sine and cosine functions.
>
This isn't quite true over the reals, even assuming you're only looking
for functions with a given period. For example the function which is
zero everywhere except being 1 at a single point will generate the same
Fourier representation as the constant zero function since it will have
the same integrals.
I think (no proof) that you can reconstruct any function up to the
addition of a function which is nonzero over an area of zero `volume'
though (assuming you don't count things like a delta functions). Not
that it matters for what you're doing of course, but you seem like the
sort of chap who might find it interesting.
>
> So, like, how do you tell if two functions are orthogonal? And how do
> you tell when a set of them is complete?
What are you using these function for? There may be better or worse
ways to do things depending on what you want.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Can somebody who knows what they're talking about confirm this?
That probably shouldn't include me, but I'll try.
> If I'm understanding this right, if I can find a complete set of
> orthogonal functions, I should be able to construct any possible
> function as a linear combination of them.
By definition, you can construct any possible piecewise continuous
function with them: In the domain that they are complete (which may only
be an interval on the real line).
See http://mathworld.wolfram.com/CompleteOrthogonalSystem.html
Now when they say that the limit of the error goes to 0, they mean in a
sort of "average" sense (see the Lebesgue integral?).
More concretely, this means that if you have your (usually infinite)
set of complete orthogonal functions, and a given function f, you can
construct something that's "almost" identical (if not identical) to f
using a linear combination of the orthogonal functions - BUT it may
disagree with f on a number of points (which constitutes a set of
measure 0).
For a concrete example, take your sines and cosines that you mentioned.
It can (easily) be shown that any linear combination of them (even an
infinite one), must be continuous. Hence, you cannot use them to
construct discontinuous functions (like a square wave) *exactly*.
However, you can construct something that looks a lot like it but
differs at only a "few" points. The square wave and your constructed
function will disagree at the points of discontinuity.
See Gibb's Phemonenon:
http://en.wikipedia.org/wiki/Gibbs_phenomenon
The "overshoot" at the point of discontinuity for a square wave is 9%
even when you take the infinite limit (the Wikipedia article, I believe,
is incorrect in claiming it goes away in that limit).
The reason sin and cos are labeled as "complete" even though they can't
replicate a simple square wave is that in the infinite limit, the sum is
identical to the square wave everywhere except at a finite number of
points.
> If I'm not mistaken, "orthogonal" means that one function can't be
> constructed from the others (so there's no duplication of
Not quite. You can have a function that cannot be obtained from the
others, but not be orthogonal to them.
In function spaces, a scalar (or inner) product is defined, akin to the
one that you get with vectors in space. You take two functions,
calculate their scalar product, and get a scalar. Two functions are
orthogonal if their scalar product is 0.
The analogy with vectors is a good one. Think in 3-D space: You can
easily get unit vectors from which you can construct any 3 dimensional
vector, but with none of these basis vectors being orthogonal. An
example would be:
A=[1 1 0], B=[0 1 1], C = [1 0 1]
(all divided by sqrt(2) for normalization). One wants orthogonality in
functions for the same reason you do with vectors: Computational
convenience.
There are a number of ways to define a scalar product of 2 functions,
but they usually have some properties:
http://mathworld.wolfram.com/InnerProduct.html
(For function spaces, things are often complex (vs real), and so you use
the "alternate" rule given further down the page in place of rule 3).
For systems I occasionally deal with, the inner product of 2 functions
is given by:
(f, g) = Integral(f*g') where g' is complex conjugation. Occasionally a
weighting function is included as well.
> So, like, how do you tell if two functions are orthogonal? And how do
> you tell when a set of them is complete?
To test for orthogonality, compute the scalar product. OR decompose it
into its components with respect to a known basis (e.g. sines and
cosines) and then take the inner product of those (hard to describe
here, but if you can do the decomposition, the inner product is trivial
as you know that the sines and cosines are orthogonal).
Forgot how to test for completeness...
I may not have described things well here, but once you "get" it, it's
quite illuminating. Basically an extension of how you dealt with vectors
in space. All concepts there have analogs in function spaces.
--
ASCII stupid question... get a stupid ANSI!
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawaz org<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> For example, the Fourier transform allows you to construct any
>> function from sine and cosine functions.
>>
>
> This isn't quite true over the reals, even assuming you're only looking
> for functions with a given period. For example the function which is
> zero everywhere except being 1 at a single point will generate the same
> Fourier representation as the constant zero function since it will have
> the same integrals.
O RLY?
My DSP textbook says the Fourier transform of the delta function yields
an amplitude of 1 for all frequencies. (Whereas the Fourier transform of
a zero signal would be a zero signal.)
> I think (no proof) that you can reconstruct any function up to the
> addition of a function which is nonzero over an area of zero `volume'
> though (assuming you don't count things like a delta functions). Not
> that it matters for what you're doing of course, but you seem like the
> sort of chap who might find it interesting.
>
>>
>> So, like, how do you tell if two functions are orthogonal? And how do
>> you tell when a set of them is complete?
>
> What are you using these function for? There may be better or worse
> ways to do things depending on what you want.
JPEG compression works by decomposing an image into a set of (2D) cosine
waves, and then quantinising the data. In my opinion, cosines are not
actually a particularly good choice for this. (Gibb's phenominon is very
ugly to look at.) So I'd like to try it with other functions - but first
I need to work out how...
(A similar thing could be said about most [lossy] audio codecs known to
man. Of course, here Gibb's isn't a problem at all. Here the problem
becomes time invariance...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> JPEG compression works by decomposing an image into a set of (2D) cosine
> waves, and then quantinising the data. In my opinion, cosines are not
> actually a particularly good choice for this. (Gibb's phenominon is very
> ugly to look at.) So I'd like to try it with other functions - but first
> I need to work out how...
So you are going to reinvent JPEG2000 then?-)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> This isn't quite true over the reals, even assuming you're only looking
>> for functions with a given period. For example the function which is
>> zero everywhere except being 1 at a single point will generate the same
>> Fourier representation as the constant zero function since it will have
>> the same integrals.
>
> O RLY?
>
> My DSP textbook says the Fourier transform of the delta function yields an
> amplitude of 1 for all frequencies. (Whereas the Fourier transform of a
> zero signal would be a zero signal.)
A function that is 0 everywhere except for f(0)=1 is not a delta funciton.
A delta function has f(0)=infinity and when integrated it gives a non-zero
value (ie it has area, unlike the function Kevin described).
> JPEG compression works by decomposing an image into a set of (2D) cosine
> waves, and then quantinising the data. In my opinion, cosines are not
> actually a particularly good choice for this. (Gibb's phenominon is very
> ugly to look at.) So I'd like to try it with other functions - but first I
> need to work out how...
Have you read:
http://en.wikipedia.org/wiki/Wavelet
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> JPEG compression works by decomposing an image into a set of (2D) cosine
>> waves, and then quantinising the data. In my opinion, cosines are not
>> actually a particularly good choice for this. (Gibb's phenominon is very
>> ugly to look at.) So I'd like to try it with other functions - but first
>> I need to work out how...
>
> So you are going to reinvent JPEG2000 then?-)
Nah. JPEG2000 uses wavelets - a technology I have repeatedly failed to
comprehend. I'm just using a decomposition with a different set of basis
functions. ;-)
[We casually overlook the fact that JPEG doesn't work in the RGB colour
space, it works in some weird custom space to better accomodate the
peculiarities of the human eye. There's also several layers of plain
ordinary lossless compression happening in addition to the lossy DCT
quantinisation step. And... basically JPEG is complicated. I'm only
trying to frobnicate one tiny step in the process.]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>>> This isn't quite true over the reals, even assuming you're only
>>> looking for functions with a given period. For example the function
>>> which is zero everywhere except being 1 at a single point will
>>> generate the same Fourier representation as the constant zero
>>> function since it will have the same integrals.
>>
>> O RLY?
>>
>> My DSP textbook says the Fourier transform of the delta function
>> yields an amplitude of 1 for all frequencies. (Whereas the Fourier
>> transform of a zero signal would be a zero signal.)
>
> A function that is 0 everywhere except for f(0)=1 is not a delta
> funciton. A delta function has f(0)=infinity and when integrated it
> gives a non-zero value (ie it has area, unlike the function Kevin
> described).
http://en.wikipedia.org/wiki/Kronecker_delta
http://en.wikipedia.org/wiki/Dirac_delta_function
So you see, we are in fact both right, for a suitable definition of
"delta function". (I'm going by a DSP textbook.)
The Dirac delta doesn't interest me - my signals won't ever contain
infinity.
> Have you read:
>
> http://en.wikipedia.org/wiki/Wavelet
I have. Multiple times. I still don't understand.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> [We casually overlook the fact that JPEG doesn't work in the RGB colour
> space, it works in some weird custom space to better accomodate the
> peculiarities of the human eye.
It's not a "custom space". It's the YCbCr color space, which has been
used in television and video for like 50 years.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> [We casually overlook the fact that JPEG doesn't work in the RGB colour
>> space, it works in some weird custom space to better accomodate the
>> peculiarities of the human eye.
>
> It's not a "custom space". It's the YCbCr color space, which has been
> used in television and video for like 50 years.
OK, I rephrase: It looks pretty exotic to me. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> A function that is 0 everywhere except for f(0)=1 is not a delta
>> funciton. A delta function has f(0)=infinity and when integrated it gives
>> a non-zero value (ie it has area, unlike the function Kevin described).
>
> http://en.wikipedia.org/wiki/Kronecker_delta
> http://en.wikipedia.org/wiki/Dirac_delta_function
>
> So you see, we are in fact both right, for a suitable definition of "delta
> function". (I'm going by a DSP textbook.)
>
> The Dirac delta doesn't interest me - my signals won't ever contain
> infinity.
Ok, well if you are dealing with discrete digital functions then the concept
of a function having "zero area" doesn't really make any sense, so yes, any
function can be made from a series of sine and cosines.
>> Have you read:
>>
>> http://en.wikipedia.org/wiki/Wavelet
>
> I have. Multiple times. I still don't understand.
Did you check out some of the links at the bottom? I just read this one and
it was ok to understand:
http://users.rowan.edu/~polikar/WAVELETS/WTtutorial.html
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> The Dirac delta doesn't interest me - my signals won't ever contain
>> infinity.
>
> Ok, well if you are dealing with discrete digital functions then the
> concept of a function having "zero area" doesn't really make any sense,
> so yes, any function can be made from a series of sine and cosines.
...and hopefully some other functions too? :-)
>>> Have you read:
>>>
>>> http://en.wikipedia.org/wiki/Wavelet
>>
>> I have. Multiple times. I still don't understand.
>
> Did you check out some of the links at the bottom? I just read this one
> and it was ok to understand:
>
> http://users.rowan.edu/~polikar/WAVELETS/WTtutorial.html
I read that back in 1997. (Yes, that's how old it is.) I had trouble
understanding it back then, and having reread it a few times since then,
I still have trouble comprehending it.
I think essentially wavelets are just too complicated to understand. So
I'll stick with my original approach...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> [We casually overlook the fact that JPEG doesn't work in the RGB colour
>>> space, it works in some weird custom space to better accomodate the
>>> peculiarities of the human eye.
>>
>> It's not a "custom space". It's the YCbCr color space, which has been
>> used in television and video for like 50 years.
>
> OK, I rephrase: It looks pretty exotic to me. ;-)
It's much better than RGB for two reasons.
1) The Y matches the high resolution bit of your eye, and the CbCr bits
match the lower resolution color detector bits of your eye. Thus they can
be compressed different amounts.
2) Equal distances in the CbCr space give a roughly equal difference in
colour perception.
If you tried to compress RGB channels separately the same amount as a YCbCr
signal it would look much worse.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> OK, I rephrase: It looks pretty exotic to me. ;-)
>
> It's much better than RGB for two reasons.
>
> 1) The Y matches the high resolution bit of your eye, and the CbCr bits
> match the lower resolution color detector bits of your eye. Thus they
> can be compressed different amounts.
>
> 2) Equal distances in the CbCr space give a roughly equal difference in
> colour perception.
>
> If you tried to compress RGB channels separately the same amount as a
> YCbCr signal it would look much worse.
Yes, I'm sure this is exactly why they use it. Still, it's not very easy
to comprehend...
(Similarly, almost all known audio codecs don't compress the left and
right stereo channels seperately; they compress "center and side"
instead, since usually the side channel will contain very much less
signal energy - and getting it wrong is far less serious sonically.)
PS. Is this why all MPEG-based algorithms utterly mutilate blue images?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I read that back in 1997. (Yes, that's how old it is.) I had trouble
> understanding it back then, and having reread it a few times since then, I
> still have trouble comprehending it.
>
> I think essentially wavelets are just too complicated to understand. So
> I'll stick with my original approach...
I don't claim to be anything like an expert on wavelets, but for someone who
apparently knows about fourier transforms it goes like this (roughly):
If you do a normal FT on a signal, you get a nice graph of amplitude against
frequency.
If you have a longer signal (eg a song) then you can split it up into chunks
and do FT on each chunk. You then get a nice 3D graph of how amplitude
against frequency changes over time.
The problem is that the shorter you make the chunks, the less accurate the
frequency information is. The longer you make the chunks, the less accurate
the time information is and the (more accurate) frequencies get blurred
together over time.
What wavelets do is allow you to use a different chunk size for different
frequencies. In a song you probably want a small chunk size for high
frequencies (the absolute frequency is not so important, just the timing),
and a large chunk size for low frequencies.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
> If you do a normal FT on a signal, you get a nice graph of amplitude
> against frequency.
But, sadly, only for a sationary siganl.
The problem, essentially, is that standard Fourier theory lets you look
at a signal purely in the time domain, or purely in the frequency domain
- but humans perceive sounds in *both* domains simultaneously.
> If you have a longer signal (eg a song) then you can split it up into
> chunks and do FT on each chunk. You then get a nice 3D graph of how
> amplitude against frequency changes over time.
>
> The problem is that the shorter you make the chunks, the less accurate
> the frequency information is. The longer you make the chunks, the less
> accurate the time information is and the (more accurate) frequencies get
> blurred together over time.
Or rather, the problem is that if the chunk bounderiess don't line up
nicely with wave cycles, you get spurious high-frequency components
being reported that don't actually exist in the original signal.
> What wavelets do is allow you to use a different chunk size for
> different frequencies. In a song you probably want a small chunk size
> for high frequencies (the absolute frequency is not so important, just
> the timing), and a large chunk size for low frequencies.
Yeah. I get all that. I just don't understand how the maths works.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Or rather, the problem is that if the chunk bounderiess don't line up
> nicely with wave cycles, you get spurious high-frequency components being
> reported that don't actually exist in the original signal.
Use a non-rectangular window function?
>> What wavelets do is allow you to use a different chunk size for different
>> frequencies. In a song you probably want a small chunk size for high
>> frequencies (the absolute frequency is not so important, just the
>> timing), and a large chunk size for low frequencies.
>
> Yeah. I get all that. I just don't understand how the maths works.
Maybe you should get a real book? I have no idea if it is valid or not, but
you could start off by doing repeated FTs with different chunk sizes for
different frequencies...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> Or rather, the problem is that if the chunk bounderiess don't line up
>> nicely with wave cycles, you get spurious high-frequency components
>> being reported that don't actually exist in the original signal.
>
> Use a non-rectangular window function?
Mmm, that's equivilent to a convolution in the frequency domain. ;-)
>>> What wavelets do is allow you to use a different chunk size for
>>> different frequencies. In a song you probably want a small chunk
>>> size for high frequencies (the absolute frequency is not so
>>> important, just the timing), and a large chunk size for low frequencies.
>>
>> Yeah. I get all that. I just don't understand how the maths works.
>
> Maybe you should get a real book?
Possibly, yes...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>> This isn't quite true over the reals, even assuming you're only
>> looking for functions with a given period. For example the function
>> which is zero everywhere except being 1 at a single point will
>> generate the same Fourier representation as the constant zero function
>> since it will have the same integrals.
>
> O RLY?
>
> My DSP textbook says the Fourier transform of the delta function yields
> an amplitude of 1 for all frequencies. (Whereas the Fourier transform of
> a zero signal would be a zero signal.)
Both your book and Kevin are correct. He was not talking about the
delta function (which never has a value of 1).
--
ASCII stupid question... get a stupid ANSI!
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> O RLY?
>
> My DSP textbook says the Fourier transform of the delta function yields
> an amplitude of 1 for all frequencies. (Whereas the Fourier transform of
> a zero signal would be a zero signal.)
>
As has been mentioned, a function which is zero everywhere except for
f(0)=1 is not what is meant by a delta function in this context. The
critical property of the delta function which your book is talking about
is that it has an integral of 1 over any interval containing the
`spike', whereas the function I described has an integral of zero
everywhere.
There's another argument that can lead you to the same conclusion that
you can't approximate any function over the reals with a Fourier
transform, and that's to note that the cardinality of the number of
possible Fourier representations is smaller than the cardinality of the
number of possible functions on the reals, so there have to be some
functions that you can't represent.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> There's another argument that can lead you to the same conclusion that
> you can't approximate any function over the reals with a Fourier
> transform, and that's to note that the cardinality of the number of
> possible Fourier representations is smaller than the cardinality of the
> number of possible functions on the reals, so there have to be some
> functions that you can't represent.
Sure. For example, you might have a partial function that isn't defined
at certain points.
None of this really interests me that much, because in the specific
instance I'm looking at [processing digital audio and video] there
aren't any such functions to worry about.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Sure. For example, you might have a partial function that isn't defined
> at certain points.
Even if you restrict yourself to functions which are defined everywhere
and are periodic with some given period the argument still applies. For
example, consider a really nasty function, like one which has a value of
one at all rational points and zero everywhere else.
> None of this really interests me that much, because in the specific
> instance I'm looking at [processing digital audio and video] there
> aren't any such functions to worry about.
Agreed. I hope that you find some interesting things with the audio and
video processing stuff! Is your goal to find some techniques which
improve on current methods or to fiddle around with some of the current
methods and understand them on a deeper level?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> [We casually overlook the fact that JPEG doesn't work in the RGB colour
>>> space, it works in some weird custom space to better accomodate the
>>> peculiarities of the human eye.
>>
>> It's not a "custom space". It's the YCbCr color space, which has been
>> used in television and video for like 50 years.
>
> OK, I rephrase: It looks pretty exotic to me. ;-)
Essentially the entire JPEG compression happens after an image
is split into grayscale channels though. The color space conversion
isn't used to increase compression.
The way I understand (wavelet?) compression, like that
in JPEG2000, is that it takes a somewhat recursive approach.
I think this part involves the wavelets... (digital wavelets being
somewhat different from analog wavelets with all the
complicated math)
The algorithm goes something like this...
1. Load the image to be compressed to memory
2. Produce an image that is the difference between
the current pixel and an average of the last few...
with a few small variations, like you can't use the pixel
above the current pixel on the top line, but you can elsewhere.
For most images this is similar to edge-detect, the resulting
image is mostly black, so highly compressible.
3. Save the difference image
4. Produce an image that is the error between the image constructed
in step 2 (when reconstructed) and the image in memory
5. replace the image in memory with the error image
6. reduce the size of the image in memory, resize,
by some fixed ratio
7. if the image in memory is larger than some size then repeat steps 2-7
8. perform some standardish compression on the saved images and
produce a file.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Essentially the entire JPEG compression happens after an image
> is split into grayscale channels though. The color space conversion
> isn't used to increase compression.
Yes it is. Usually, in the new colour space, two of the channels are scaled
by 50% as a first step that vastly decreases the file size. You would never
be able to get this much compression with RGB without the result looking
much worse.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
