man.. these code or teletype tags are pretty useless...
a bit distorted, but I think you get what's displayed there ;)
[tt]
h(x,4):
^
| ****
** ** ** **
| * * * *
0----1----2----3----4----5----6----7->
* * * *
| ** ** ** **
| **** ****
h(x,5):
^
| *** ***
* ** * ** *
|* * * * *
0----1----2----3----4----5----6----7->
| * * * * *
| * * * * *
| *** ***
h(x,6):
^
| ** **
| * * * * *
|* * * * * *
0----1----2----3----4----5----6----7->
| * * * * * *
| * * * * * *
| ** ** **
h(x,7):
^
| * * *
| * * * * * *
|* * * * * * *
0----1----2----3----4----5----6----7->
| * * * * * * *
| * * * * * *
| * * *
[/tt]
hmm this looks really shitty in this forum.....
OT: hey candy [moved from "call gates"]
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
I hope you know what a basis is. A basis is a set of n linear independent vectors of a n-dimensional vectorspace.
Now we're going to define a basis {b[sub]0[/sub], b[sub]1[/sub],...b[sub]7[/sub]} for a 8dimensional vectorspace with our h(x,0),...h(x,7) functions:
b[sub]i[/sub] := ( h(0,i), h(1,i), ..., h(7,i) ) for i ? {0,..7}
This base has a special property - it's an orthonormalbase:
|| b[sub]i[/sub] || = 1 and <b[sub]i[/sub], b[sub]j[/sub]> = 0
Now what we want to do is a basetransformation of our sampledatavector f (8dimensional) from our standard base s...
s[sub]0[/sub] := (1,0,...,0)
s[sub]1[/sub] := (0,1,...,0)
...
s[sub]7[/sub] := (0,0,...,1)
...to this new base with 8 orthogonal projections:
c[sub]0[/sub] := <b[sub]0[/sub],f>
c[sub]1[/sub] := <b[sub]1[/sub],f>
...
c[sub]7[/sub] := <b[sub]7[/sub],f>
This gives us our transformed vector (c[sub]0[/sub],c[sub]1[/sub],...,c[sub]7[/sub]).
Written in matrix-style this looks like:
[ h(0,0) ... h(7,0) ] [ f[sub]0[/sub] ] [ c[sub]0[/sub] ]
[ .. .. ] * [ ... ] = [ ... ]
[ h(0,7) ... h(7,7) ] [ f[sub]7[/sub] ] [ c[sub]7[/sub] ]
This matrix is orthogonal, that is M*M[sup]-1[/sup] = I (Identity). This property can be used to our advance - calculating the inverse of a matrix sucks (slow), but for orthogonal matrices we have M[sup]-1[/sup] = M[sup]T[/sup]. Yippie, so to calculate the inverse DCT, all we have to do is transpose the matrix and do M[sup]T[/sup]*c = f, this means that DCT and IDCT is equal fast.
Now we're going to define a basis {b[sub]0[/sub], b[sub]1[/sub],...b[sub]7[/sub]} for a 8dimensional vectorspace with our h(x,0),...h(x,7) functions:
b[sub]i[/sub] := ( h(0,i), h(1,i), ..., h(7,i) ) for i ? {0,..7}
This base has a special property - it's an orthonormalbase:
|| b[sub]i[/sub] || = 1 and <b[sub]i[/sub], b[sub]j[/sub]> = 0
Now what we want to do is a basetransformation of our sampledatavector f (8dimensional) from our standard base s...
s[sub]0[/sub] := (1,0,...,0)
s[sub]1[/sub] := (0,1,...,0)
...
s[sub]7[/sub] := (0,0,...,1)
...to this new base with 8 orthogonal projections:
c[sub]0[/sub] := <b[sub]0[/sub],f>
c[sub]1[/sub] := <b[sub]1[/sub],f>
...
c[sub]7[/sub] := <b[sub]7[/sub],f>
This gives us our transformed vector (c[sub]0[/sub],c[sub]1[/sub],...,c[sub]7[/sub]).
Written in matrix-style this looks like:
[ h(0,0) ... h(7,0) ] [ f[sub]0[/sub] ] [ c[sub]0[/sub] ]
[ .. .. ] * [ ... ] = [ ... ]
[ h(0,7) ... h(7,7) ] [ f[sub]7[/sub] ] [ c[sub]7[/sub] ]
This matrix is orthogonal, that is M*M[sup]-1[/sup] = I (Identity). This property can be used to our advance - calculating the inverse of a matrix sucks (slow), but for orthogonal matrices we have M[sup]-1[/sup] = M[sup]T[/sup]. Yippie, so to calculate the inverse DCT, all we have to do is transpose the matrix and do M[sup]T[/sup]*c = f, this means that DCT and IDCT is equal fast.
Re: hey candy
You totally lost me. What is a basis?mpp.eox3 wrote: I hope you know what a basis is. A basis is a set of n linear independent vectors of a n-dimensional vectorspace.
Now we're going to define a basis {b[sub]0[/sub], b[sub]1[/sub],...b[sub]7[/sub]} for a 8dimensional vectorspace with our h(x,0),...h(x,7) functions:
b[sub]i[/sub] := ( h(0,i), h(1,i), ..., h(7,i) ) for i ? {0,..7}
I follow this, but not in the context of the basis. The idea represented does follow, and as soon as I figure out what a basis is I'll get this.This base has a special property - it's an orthonormalbase:
|| b[sub]i[/sub] || = 1 and <b[sub]i[/sub], b[sub]j[/sub]> = 0
I got that part. Except the references to basis, but all the same. I'm off to lookup what a transpose was again, I know inverse...Now what we want to do is a basetransformation of our sampledatavector f (8dimensional) from our standard base s...
s[sub]0[/sub] := (1,0,...,0)
s[sub]1[/sub] := (0,1,...,0)
...
s[sub]7[/sub] := (0,0,...,1)
...to this new base with 8 orthogonal projections:
c[sub]0[/sub] := <b[sub]0[/sub],f>
c[sub]1[/sub] := <b[sub]1[/sub],f>
...
c[sub]7[/sub] := <b[sub]7[/sub],f>
This gives us our transformed vector (c[sub]0[/sub],c[sub]1[/sub],...,c[sub]7[/sub]).
Written in matrix-style this looks like:
[ h(0,0) ... h(7,0) ] [ f[sub]0[/sub] ] [ c[sub]0[/sub] ]
[ .. .. ] * [ ... ] = [ ... ]
[ h(0,7) ... h(7,7) ] [ f[sub]7[/sub] ] [ c[sub]7[/sub] ]
This matrix is orthogonal, that is M*M[sup]-1[/sup] = I (Identity). This property can be used to our advance - calculating the inverse of a matrix sucks (slow), but for orthogonal matrices we have M[sup]-1[/sup] = M[sup]T[/sup]. Yippie, so to calculate the inverse DCT, all we have to do is transpose the matrix and do M[sup]T[/sup]*c = f, this means that DCT and IDCT is equal fast.
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
one sidenote - the ? means the element symbol and |R the real number symbol.
A set of vectors b[sub]1[/sub], b[sub]2[/sub], ... b[sub]n[/sub] ? V[sup]n[/sup] which are linear independent and span the vector space are called a basis.
This means that
[linear independent:]
x[sub]1[/sub]b[sub]1[/sub] + x[sub]2[/sub]b[sub]2[/sub] + ... + x[sub]n[/sub]b[sub]n[/sub] = 0 => x[sub]1[/sub] = x[sub]2[/sub] = ... = x[sub]n[/sub] = 0
or in other words the linear combination of the null-vector has only the trivial solution - all coefficients are zero.
and
[span the vectorspace:]
V[sup]n[/sup] = { c[sub]1[/sub]b[sub]1[/sub] + ... + c[sub]n[/sub]b[sub]n[/sub] : c[sub]1[/sub],...,c[sub]n[/sub] ? |R }
which means that every vector v ? V[sup]n[/sup] can be linear combined with those basis vectors
A set of vectors b[sub]1[/sub], b[sub]2[/sub], ... b[sub]n[/sub] ? V[sup]n[/sup] which are linear independent and span the vector space are called a basis.
This means that
[linear independent:]
x[sub]1[/sub]b[sub]1[/sub] + x[sub]2[/sub]b[sub]2[/sub] + ... + x[sub]n[/sub]b[sub]n[/sub] = 0 => x[sub]1[/sub] = x[sub]2[/sub] = ... = x[sub]n[/sub] = 0
or in other words the linear combination of the null-vector has only the trivial solution - all coefficients are zero.
and
[span the vectorspace:]
V[sup]n[/sup] = { c[sub]1[/sub]b[sub]1[/sub] + ... + c[sub]n[/sub]b[sub]n[/sub] : c[sub]1[/sub],...,c[sub]n[/sub] ? |R }
which means that every vector v ? V[sup]n[/sup] can be linear combined with those basis vectors
-
bkilgore
Re:OT: hey candy [moved from "call gates"]
This is a really interesting topic. I just finished some linear algebra classes so orthonormal bases and such are still words in my vocabulary, and its fun to see it actually used in practice instead of just theory.
So in this case, the DCT and IDCT are linear transformations to, and back from, the standard base, but why 8 dimensions? And what exactly is the transformation used for (why are we transforming to the standard base?) Thanks
So in this case, the DCT and IDCT are linear transformations to, and back from, the standard base, but why 8 dimensions? And what exactly is the transformation used for (why are we transforming to the standard base?) Thanks
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
I chose 8 dimensions because the DCT used in the JPEG is based on 8x8 blocks (note: 2 dimensional DCT).
You're free to use any dimension you want, you just have to set up some cosinus base vectors appropriately.
The transformation gives you amplitudes of cosinus frequencies, which when summed up form the original sample signal (vector in standard base).
Note that the DCT will give in mathematical theory the exact original signal, but due to precision limitations on our floating point processors we get a little error..
So what do we gain by transforming a vector (n-dimensional) into another base (again n-dimensional)?
- We still have to store the same amount of data to describe this vector: n coefficients.
Now the trick is to just throw away the higher frequency coefficients, as they don't have much impact on the signal if they're left away. Thus, we don't have to save that much information anymore and we achieve a lossy compression.
In JPEG, which frequencies are diminished by which factor is described by the quantization matrix. Here, each frequency coefficient is divided by some value, making it smaller - the coefficients for high frequencies will be mostly 0 (the entropy will sink -> better compressable).
A question I had myself might interest you too:
I wondered for what reason JPEG uses DCT, when FFT could be used as well.
The answer I found was that if you have a linear (I mean something like a straight increasing line, like f(x):=0.23*x) sample signal (it seemed to be common in picture data) and do some DCT on it, throw away the higher frequencies, then IDCT it again, the result will still look mostly linear like the original (with some error of course).
When the same is done with FFT, the original linear signal will look more wavy than the DCT processed signal, which is not wanted because the human eye might notice this error more.
This answer is based on a "quick" google search and I have to mention that I haven't found much information on why DCT is preferred over FFT in JPEG, so if somebody out there knows any better, please tell :)
You're free to use any dimension you want, you just have to set up some cosinus base vectors appropriately.
The transformation gives you amplitudes of cosinus frequencies, which when summed up form the original sample signal (vector in standard base).
Note that the DCT will give in mathematical theory the exact original signal, but due to precision limitations on our floating point processors we get a little error..
So what do we gain by transforming a vector (n-dimensional) into another base (again n-dimensional)?
- We still have to store the same amount of data to describe this vector: n coefficients.
Now the trick is to just throw away the higher frequency coefficients, as they don't have much impact on the signal if they're left away. Thus, we don't have to save that much information anymore and we achieve a lossy compression.
In JPEG, which frequencies are diminished by which factor is described by the quantization matrix. Here, each frequency coefficient is divided by some value, making it smaller - the coefficients for high frequencies will be mostly 0 (the entropy will sink -> better compressable).
A question I had myself might interest you too:
I wondered for what reason JPEG uses DCT, when FFT could be used as well.
The answer I found was that if you have a linear (I mean something like a straight increasing line, like f(x):=0.23*x) sample signal (it seemed to be common in picture data) and do some DCT on it, throw away the higher frequencies, then IDCT it again, the result will still look mostly linear like the original (with some error of course).
When the same is done with FFT, the original linear signal will look more wavy than the DCT processed signal, which is not wanted because the human eye might notice this error more.
This answer is based on a "quick" google search and I have to mention that I haven't found much information on why DCT is preferred over FFT in JPEG, so if somebody out there knows any better, please tell :)
Re:OT: hey candy [moved from "call gates"]
This I knowif somebody out there knows any better, please tell
The FFT makes use of the assumption that when you place the binary data after itself, it's a nice wave. DCT assumes that if you place itself time-inverted (or when drawn, horizontally inverted) after itself, and then see that as a wave it's appropriate. This way, FFT seems to round off the start & end values, where DCT is better for a subsection of a wave. FFT also performs badly on low-frequency waves where less than a full wave is available, since it rounds the ends down. This also explains why mp3 and the like are based on DCT or mDCT.
Now, anybody have a nice book on basis-things? I needed to buy Grimaldi's intro to maths for my study, does it have it somewhere?
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
ah, haven't thought of this periodicity thingy.
I googled if this Grimaldi book might be good, I've only found "Discrete and Combinatorial Mathematics".
If you meant this book I don't think this will be the right one.
Try to get something on "linear algebra" or visit the lecture :)
I googled if this Grimaldi book might be good, I've only found "Discrete and Combinatorial Mathematics".
If you meant this book I don't think this will be the right one.
Try to get something on "linear algebra" or visit the lecture :)
Re:OT: hey candy [moved from "call gates"]
hm... you have any hints on good books preferable below 50 euros, otherwise as cheap as possible?mpp.eox3 wrote: I googled if this Grimaldi book might be good, I've only found "Discrete and Combinatorial Mathematics".
If you meant this book I don't think this will be the right one.
Try to get something on "linear algebra" or visit the lecture
Am still a student without a big wallet.
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
hmm for Analysis I only bought these two books:
[url=http://www.amazon.de/exec/obidos/ASIN/3519622335]amazon.de-link1
[/url]
[url=http://www.amazon.de/exec/obidos/ASIN/3519522322]amazon.de-link2
[/url]
very good, but won't help you with your problem... (and they're in German..)
Concerning Linear Algebra, all I needed was the script of the lecture (actually two/three..). You might go and check out your "local script dealer", they sell them very cheap. Normally you should have something like that already - or don't you have to do math stuff when you study computer science in Holland?
[url=http://www.amazon.de/exec/obidos/ASIN/3519622335]amazon.de-link1
[/url]
[url=http://www.amazon.de/exec/obidos/ASIN/3519522322]amazon.de-link2
[/url]
very good, but won't help you with your problem... (and they're in German..)
Concerning Linear Algebra, all I needed was the script of the lecture (actually two/three..). You might go and check out your "local script dealer", they sell them very cheap. Normally you should have something like that already - or don't you have to do math stuff when you study computer science in Holland?
Re:OT: hey candy [moved from "call gates"]
Being born 10km from the german border, and now living in a different city 5km from the german border, I've been spoken to in german enough to comprehend, I guessmpp.eox3 wrote: very good, but won't help you with your problem... (and they're in German..)
Not this sort of math. In 4 or 5 years, it's hard enough to be able toConcerning Linear Algebra, all I needed was the script of the lecture (actually two/three..). You might go and check out your "local script dealer", they sell them very cheap. Normally you should have something like that already - or don't you have to do math stuff when you study computer science in Holland?
-program
-organize team work
-know algorithms
-know binary/computer organization/some detail
-get up to 2 years of experience (yes, they do bother)
so, I don't disagree with them valueing these higher, but I do miss that math. Don't know where to get it either, so I'm at a total blank.
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
ah your list looks a bit different with what I got stuffed into my brains. the only thing we did too was "program", "know algorithms" and "know binary/computer organization/some detail", though I can't really compare because they're not described very detailed.
here's a detailed list what it looks like here in germany (first 2 years):
If I knew that before I might have studied something different, something that the world doesn't need hehe. Luckily I'm almost done with maths ;)
here's a detailed list what it looks like here in germany (first 2 years):
- analysis 1: series, convergence, limits, differentials, taylor approximation, integrals, complex numbers, fourier series
- analysis 2: more-dimensional differentials&integrals, differential equations, fourier transformation, laplace transformation
- linear algebra 1: group+ring+field theory, vector spaces, base transformations, linear forms, multilinear forms, vector spaces of linear functions, eigenvectors, jordan normal form, determinants,
- linear algebra 2: orthonormal bases, cross product, normal endomorphisms, isometries (+ normal form),
- probability and statistics: veeery boring!! (don't try this at home kids ;)
- numerical mathematics: cholesky/LR reductions of matrices, linear equation systems + several solving algorithms, nonlinear systems (solved with newton approx, fixpoint iteration), polynom interpolation, splines & interpolation, beziers, discrete fourier transform, numerical integration
If I knew that before I might have studied something different, something that the world doesn't need hehe. Luckily I'm almost done with maths ;)
- informatik 1: algorithms, groups & relations, termalgebra, formal logic, functional programming & datastructures, number representation, graphs, grammar..
- informatik 2: imperative programming, system design, object oriented design, program verification & loop invariants, testing, algorithm design, scalability & complexity, data structures, dynamic programming, graph algorithms, databases & sql, processes & synchronisation, protocolls
- [theoretical] informatik 3: finite machines & regular expressions, turing&stack machines, complexity, grammar & chomsky, p/np proofs of problems, pumping lemma, normal forms of grammars,...
- informatik 4: efficient algorithms & proofs, indexing data/information retrieval (had to program a search engine, was the fastest of all of course ;), optimization of np-problemsolutions, neuronal nets, information theory, data compression
- linux internals seminar: had to do a speech on interrupts and DMA (see my homepage for it)
- technical informatik 1: CMOS, how to build circuits, minimizing logic expressions, realising automats with flipflops, ROMs, PLAs, hasards,..
- technical informatik 2: processor architecture, done some microcode programming, MIPS assembler, pipelining, caches, paging&segmentation (wohoo very hard for me ;), computer arithmetic,..
- physics 1+2: bah still hanging on this crap...
-
mpp.eox3
Re:OT: hey candy [moved from "call gates"]
Update, it just fell into my mind - now that I know that you read German books, here's a cool one on Linear Algebra for 19.90?:
[url=http://www.amazon.de/exec/obidos/ASIN/352856508X]amazon.de link: Lineare Algebra, Albrecht Beutelspacher
[/url]
This book is very lightweight and humourus written and you learn about everything I learned in my "Linear Algebra 1" course. If I remember correctly, there are also examples, excercises & solutions, so it might be ideal for you to study at home.
Sorry I didn't think of that yesterday so you could have ordered with your other orders.. (I don't own this book that's why I didn't think of it).
There are just 9 cent missing to get free delivery :/
[url=http://www.amazon.de/exec/obidos/ASIN/352856508X]amazon.de link: Lineare Algebra, Albrecht Beutelspacher
[/url]
This book is very lightweight and humourus written and you learn about everything I learned in my "Linear Algebra 1" course. If I remember correctly, there are also examples, excercises & solutions, so it might be ideal for you to study at home.
Sorry I didn't think of that yesterday so you could have ordered with your other orders.. (I don't own this book that's why I didn't think of it).
There are just 9 cent missing to get free delivery :/