Golden section transform

An example of 2-Level DCT-Low Golden Section Transform(DCT-LGST).

The golden section transform was proposed and used in digital image multiresolution analysis in 2007 by Jun Li. The ratio of 1 level "Low" part length to "High" part length is the approximation of the golden ratio $\varphi$ (Type L) or ${\frac {1}{\varphi }}$ (Type H),

where

$\varphi ={\frac {1+{\sqrt {5}}}{2}}=1.618\ldots ;$

${\frac {1}{\varphi }}={\frac {-1+{\sqrt {5}}}{2}}=0.618\ldots$

DCT-golden section transform (DCT-GST)

It is well known that the Fibonacci sequence is:

$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;233,\;377,\;610,\;987\ldots \;$ (sequence A000045 in the OEIS)

$F_{0}=0,\;F_{1}=1,F_{n}=F_{n-1}+F_{n-2},$ make a golden section tree of the Fibonacci number 8:

The golden section tree of 8

Fibonacci number	DCT-LGST	Reverse order	Symmetrical form	DCT-HGST	Reverse order	symmetrical form
1	1	1	1	–	–	–
2	2	2	2	2	2	2
3	12	21	21	3	3	3
5	212	212	212	23	32	32
8	12212	21221	21212	323	323	323
13	21212212	21221212	21212212	23323	32332	32323
21	1221221212212	2122121221221	2121221221212	32323323	32332323	32323323

DCT-low golden section transform (DCT-LGST)

Take a sequence $(p_{0},p_{1},p_{2},p_{3},p_{4},p_{5},p_{6},p_{7})$ of 8 elements for example, we get the form of 8 is $12212$, 1-level DCT-LGST of the 8 elements is:

$p_{0},\;{\frac {p_{1}+p_{2}}{2}},\;{\frac {p_{3}+p_{4}}{2}},\;p_{5},\;{\frac {p_{6}+p_{7}}{2}},\;{\frac {p_{1}-p_{2}}{2}},\;{\frac {p_{3}-p_{4}}{2}},\;{\frac {p_{6}-p_{7}}{2}}$

the "low" part of the result is:

$p_{0},\;{\frac {p_{1}+p_{2}}{2}},\;{\frac {p_{3}+p_{4}}{2}},\;p_{5},\;{\frac {p_{6}+p_{7}}{2}}$

according to the form $212$ of 5, 2-level DCT-LGST of the 8 elements is:

${\frac {p_{0}+{\frac {p_{1}+p_{2}}{2}}}{2}},\;{\frac {p_{3}+p_{4}}{2}},\;{\frac {p_{5}+{\frac {p_{6}+p_{7}}{2}}}{2}},\;{\frac {p_{0}-{\frac {p_{1}+p_{2}}{2}}}{2}},\;{\frac {p_{5}-{\frac {p_{6}+p_{7}}{2}}}{2}},\;{\frac {p_{1}-p_{2}}{2}},\;{\frac {p_{3}-p_{4}}{2}},\;{\frac {p_{6}-p_{7}}{2}}$

An example of 1-Level DCT-Low Golden Section Transform(DCT-LGST).

Let $L_{N}$ be the $N\times N$ non-normalized DCT-LGST matrix, where $N=F_{k},(k\geq 3,k\in \mathbb {Z} )$

when $N=2$, 1-level non-normalized DCT-LGST matrix is:

$L_{2}={\frac {1}{2}}{\begin{bmatrix}1&1\\1&-1\\\end{bmatrix}}$

when $N=3$, 2-level non-normalized DCT-LGST matrix and the inverse matrix is:

$L_{3}={\frac {1}{4}}{\begin{bmatrix}2&1&1\\2&-1&-1\\0&2&-2\\\end{bmatrix}}$; $L_{3}^{-1}={\begin{bmatrix}1&1&0\\1&-1&1\\1&-1&-1\\\end{bmatrix}}$

when $N=5$, 3-level non-normalized DCT-LGST matrix and the inverse matrix is:

$L_{5}={\frac {1}{8}}{\begin{bmatrix}2&2&2&1&1\\2&2&-2&-1&-1\\0&0&4&-2&-2\\4&-4&0&0&0\\0&0&0&4&-4\\\end{bmatrix}}$; $L_{5}^{-1}={\begin{bmatrix}1&1&0&1&0\\1&1&0&-1&0\\1&-1&1&0&0\\1&-1&-1&0&1\\1&-1&-1&0&-1\\\end{bmatrix}}$

when $N=8$, 4-level non-normalized DCT-LGST matrix and the inverse matrix is:

$L_{8}={\frac {1}{16}}{\begin{bmatrix}4&2&2&2&2&2&1&1\\4&2&2&-2&-2&-2&-1&-1\\0&0&0&4&4&-4&-2&-2\\8&-4&-4&0&0&0&0&0\\0&0&0&0&0&8&-4&-4\\0&8&-8&0&0&0&0&0\\0&0&0&8&-8&0&0&0\\0&0&0&0&0&0&8&-8\end{bmatrix}}$;$L_{8}^{-1}={\begin{bmatrix}1&1&0&1&0&0&0&0\\1&1&0&-1&0&1&0&0\\1&1&0&-1&0&-1&0&0\\1&-1&1&0&0&0&1&0\\1&-1&1&0&0&0&-1&0\\1&-1&-1&0&1&0&0&0\\1&-1&-1&0&-1&0&0&1\\1&-1&-1&0&-1&0&0&-1\end{bmatrix}}$

when $N=8$, 4-level non-normalized reverse-order DCT-LGST matrix and the inverse matrix is:

$L_{8}={\frac {1}{16}}{\begin{bmatrix}1&1&2&2&2&2&2&4\\1&1&2&2&2&-2&-2&-4\\2&2&4&-4&-4&0&0&0\\4&4&-8&0&0&0&0&0\\0&0&0&0&0&4&4&-8\\8&-8&0&0&0&0&0&0\\0&0&0&8&-8&0&0&0\\0&0&0&0&0&8&-8&0\end{bmatrix}}$;$L_{8}^{-1}={\begin{bmatrix}1&1&1&1&0&1&0&0\\1&1&1&1&0&-1&0&0\\1&1&1&-1&0&0&0&0\\1&1&-1&0&0&0&1&0\\1&1&-1&0&0&0&-1&0\\1&-1&0&0&1&0&0&1\\1&-1&0&0&1&0&0&-1\\1&-1&0&0&-1&0&0&0\end{bmatrix}}$

also, when $N=8$, 4-level non-normalized symmetrical form DCT-LGST matrix and the inverse matrix is:

$L_{8}={\frac {1}{16}}{\begin{bmatrix}1&1&2&2&2&4&2&2\\1&1&2&2&2&-4&-2&-2\\2&2&4&-4&-4&0&0&0\\4&4&-8&0&0&0&0&0\\0&0&0&0&0&8&-4&-4\\8&-8&0&0&0&0&0&0\\0&0&0&8&-8&0&0&0\\0&0&0&0&0&0&8&-8\end{bmatrix}}$;$L_{8}^{-1}={\begin{bmatrix}1&1&1&1&0&1&0&0\\1&1&1&1&0&-1&0&0\\1&1&1&-1&0&0&0&0\\1&1&-1&0&0&0&1&0\\1&1&-1&0&0&0&-1&0\\1&-1&0&0&1&0&0&0\\1&-1&0&0&-1&0&0&1\\1&-1&0&0&-1&0&0&-1\end{bmatrix}}$

DCT-high golden section transform (DCT-HGST)

An example of 1-Level DCT-High Golden Section Transform(DCT-HGST).

Similar to DCT-LGST, 1-level DCT-HGST of the 8 elements by the form $323$ is:

${\frac {p_{0}+p_{1}+p_{2}}{3}},\;{\frac {p_{3}+p_{4}}{2}},\;{\frac {p_{5}+p_{6}+p_{7}}{3}},\;{\frac {\sqrt {6}}{6}}p_{0}-{\frac {\sqrt {6}}{6}}p_{2},\;{\frac {\sqrt {2}}{6}}p_{0}-{\frac {\sqrt {2}}{3}}p_{1}+{\frac {\sqrt {2}}{6}}p_{2},\;{\frac {p_{3}-p_{4}}{2}},\;$

${\frac {\sqrt {6}}{6}}p_{5}-{\frac {\sqrt {6}}{6}}p_{7},\;{\frac {\sqrt {2}}{6}}p_{5}-{\frac {\sqrt {2}}{3}}p_{6}+{\frac {\sqrt {2}}{6}}p_{7}$

DCT-HGST can be also defined by a $N\times N$ matrix $H_{N}$, where $N=F_{k},(k\geq 3,k\in \mathbb {Z} )$, it is known that the $3\times 3$ non-normalized DCT matrix is:

$W={\frac {1}{3}}{\begin{bmatrix}1&1&1\\{\frac {\sqrt {6}}{2}}&0&-{\frac {\sqrt {6}}{2}}\\{\frac {\sqrt {2}}{2}}&-{\sqrt {2}}&{\frac {\sqrt {2}}{2}}\end{bmatrix}}$

when $N=8$, 2-level non-normalized DCT-HGST matrix and the inverse matrix is:

$H_{8}={\frac {1}{18}}{\begin{bmatrix}2&2&2&3&3&2&2&2\\{\sqrt {6}}&{\sqrt {6}}&{\sqrt {6}}&0&0&-{\sqrt {6}}&-{\sqrt {6}}&-{\sqrt {6}}\\{\sqrt {2}}&{\sqrt {2}}&{\sqrt {2}}&-3{\sqrt {2}}&-3{\sqrt {2}}&{\sqrt {2}}&{\sqrt {2}}&{\sqrt {2}}\\3{\sqrt {6}}&0&-3{\sqrt {6}}&0&0&0&0&0\\3{\sqrt {2}}&-6{\sqrt {2}}&3{\sqrt {2}}&0&0&0&0&0\\0&0&0&9&-9&0&0&0\\0&0&0&0&0&3{\sqrt {6}}&0&-3{\sqrt {6}}\\0&0&0&0&0&3{\sqrt {2}}&-6{\sqrt {2}}&3{\sqrt {2}}\\\end{bmatrix}};$

$H_{8}^{-1}={\begin{bmatrix}1&{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&0&0&0\\1&{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&0&-{\sqrt {2}}&0&0&0\\1&{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&-{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&0&0&0\\1&0&-{\sqrt {2}}&0&0&1&0&0\\1&0&-{\sqrt {2}}&0&0&-1&0&0\\1&-{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&0&0&0&{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}\\1&-{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&0&0&0&0&-{\sqrt {2}}\\1&-{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}&0&0&0&-{\frac {\sqrt {6}}{2}}&{\frac {\sqrt {2}}{2}}\end{bmatrix}}$

DFT-golden section transform (DFT-GST)

Similarly, DFT-golden section transform can be defined as well, the $2\times 2$ DFT matrix is identical with $2\times 2$ DCT matrix, the $3\times 3$ non-normalized DFT matrix is:

$W={\frac {1}{3}}{\begin{bmatrix}1&1&1\\1&-{\frac {1}{2}}-{\frac {\sqrt {3}}{2}}i&-{\frac {1}{2}}+{\frac {\sqrt {3}}{2}}i\\1&-{\frac {1}{2}}+{\frac {\sqrt {3}}{2}}i&-{\frac {1}{2}}-{\frac {\sqrt {3}}{2}}i\end{bmatrix}}$

The lifting scheme of reverse-order DCT-LGST

Let $F_{0}=0,\;F_{1}=1,$ let $\{X_{u}\}\,\!$ be the original sequence, let $\{S_{v}\}\,\!$ be a sequence as the "Low" part of reverse-order DCT-LGST, let $\{D_{w}\}\,\!$ be a sequence as the "High" part of reverse-order DCT-LGST, we have

$\{X_{u}\}=X_{0},X_{1},X_{2},\ldots ,X_{u};\;$ $\{S_{v}\}=S_{0},S_{1},S_{2},\ldots ,S_{v};\;$ $\{D_{w}\}=D_{0},D_{1},D_{2},\ldots ,D_{w}\;$

where $u=F_{k}-1,\;v=F_{k-1}-1,\;w=F_{k-2}-1\;(k\geq 3,k\in \mathbb {Z} )$

The lifting scheme of normalized reverse-order DCT-LGST is:

${\begin{cases}S_{M_{n}}^{0}=X_{L_{n}-1},\;D_{n-1}^{0}=X_{L_{n}}\\D_{n-1}^{1}=S_{M_{n}}^{0}-D_{n-1}^{0},S_{M_{n}}^{1}=S_{M_{n}}^{0}-0.5D_{n-1}^{1}\\S_{M_{n}}={\sqrt {2}}S_{M_{n}}^{1},\;S_{L_{m}}=X_{H_{m}},\;D_{n-1}=D_{n-1}^{1}/{\sqrt {2}}\end{cases}}$

and the reconstruction algorithm is:

${\begin{cases}S_{M_{n}}^{1}=S_{M_{n}}/{\sqrt {2}},\;D_{n-1}^{1}={\sqrt {2}}D_{n-1}\\S_{M_{n}}^{0}=S_{M_{n}}^{1}+0.5D_{n-1}^{1},\;D_{n-1}^{0}=S_{M_{n}}^{0}-D_{n-1}^{1}\\X_{L_{n}-1}=S_{M_{n}}^{0},\;X_{H_{m}}=S_{L_{m}},\;X_{L_{n}}=D_{n-1}^{0}\end{cases}}$

where

$\{L_{n}\}=1,4,6,9,12,14,17,19,\ldots \;$ (sequence A003622 in the OEIS)

$\{M_{n}\}=0,2,3,5,7,8,10,11,\ldots \;$ (sequence A022342 in the OEIS)

$\{H_{n}\}=2,7,10,15,20,23,28,31,\ldots \;$ (sequence A035336 in the OEIS)

$L_{n}=\left\lfloor {\frac {3+{\sqrt {5}}}{2}}n\right\rfloor -1,M_{n}=\left\lfloor {\frac {1+{\sqrt {5}}}{2}}n\right\rfloor -1,H_{n}=2\left\lfloor {\frac {1+{\sqrt {5}}}{2}}n\right\rfloor +n-1$

where $m=1,2,3,4,\ldots \;F_{k-3};\;n=1,2,3,4,\ldots \;F_{k-2}\;(m,n\in \mathbb {N} ^{*})$

See also

• Fibonacci number
• Golden ratio
• Discrete cosine transform
• Discrete Fourier transform
• Wavelet transform
• List of Fourier-related transforms
• JPEG 2000

References

• Sun, Y.K.(2005). Wavelet Analysis and Its Applications. China Machine Press. ISBN 7111158768
• Jin, J.F.(2004). Visual C++ Wavelet Transform Technology and Engineering Practice. Posts & Telecommunications Press. ISBN 7115119597
• He, B.;Ma, T.Y.(2002). Visual C++ Digital Image Processing. Posts & Telecommunications Press. ISBN 7115109559
• Ingrid Daubechies(1992). Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics. ISBN 0-89871-274-2

External links

• "discrete cosine transform". PlanetMath.
• Sloane, N. J. A. (ed.). "Sequence A000045 (Fibonacci Numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
• Weisstein, Eric W. "Golden Ratio". MathWorld.

This article "Golden section transform" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Bloch wave – MoM method
• Sonnox
• Signal Metadata Format
• Frequency offsets least mean squares
• Winograd Fast Fourier Transform Algorithm
• Fast Fourier Transform Telescope

---