Golden section transform

From Deletionpedia.org: a home for articles deleted from Wikipedia
Jump to: navigation, search


This article was considered for deletion at Wikipedia on December 22 2013. This is a backup of Wikipedia:Golden section transform. All of its AfDs can be found with PrefixIndex, the first at Wikipedia:Wikipedia:Articles for deletion/Golden section transform. If the page name here has changed, please see these three pages instead. Purge
Wikipedia editors had multiple issues with this page:
The topic of this article may not meet Wikipedia's general notability guideline. But, that doesn't mean someone has to… establish notability by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond its mere trivial mention. (November 2013)

Template:Confusing Template:Lead rewrite Template:Technical oooh, orphan

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.[1] The ratio of 1 level "Low" part length to "High" part length is the approximation of the golden ratio <math>\varphi</math> (Type L) or <math>\frac{1}{\varphi}</math> (Type H),

where

<math>\varphi = \frac{1+\sqrt{5}}{2} = 1.618\ldots ;</math>
<math>\frac{1}{\varphi}= \frac{-1+\sqrt{5}}{2} = 0.618\ldots</math>

DCT-golden section transform (DCT-GST)

It is well known that the Fibonacci sequence is:

<math>0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;233,\;377,\;610,\;987\ldots\;</math> Template:OEIS
<math>F_0 = 0,\; F_1= 1,F_n = F_{n-1} + F_{n-2},</math> 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 <math>(p_0,p_1,p_2,p_3,p_4,p_5,p_6,p_7)</math> of 8 elements for example, we get the form of 8 is <math>12212</math>, 1-level DCT-LGST of the 8 elements is:

<math>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}</math>

the "low" part of the result is:

<math>p_0,\;\frac{p_1 + p_2}{2},\;\frac{p_3 + p_4}{2},\;p_5,\;\frac{p_6 + p_7}{2}</math>

according to the form <math>212</math> of 5, 2-level DCT-LGST of the 8 elements is:

<math>\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}</math>
An example of 1-Level DCT-Low Golden Section Transform(DCT-LGST).

Let <math>L_{N}</math> be the <math>N\times N</math> non-normalized DCT-LGST matrix, where <math>N=F_k, (k\ge3,k \in \mathbb{Z})</math>

when <math>N=2</math>, 1-level non-normalized DCT-LGST matrix is:

<math>L_{2}=\frac{1}{2}\begin{bmatrix}

1 & 1\\1 & -1\\ \end{bmatrix}</math>

when <math>N=3</math>, 2-level non-normalized DCT-LGST matrix and the inverse matrix is:

<math>L_{3}=\frac{1}{4}\begin{bmatrix}

2 & 1 & 1\\2 & -1 & -1\\0 & 2 & -2\\ \end{bmatrix}</math>; <math>L_{3}^{-1}=\begin{bmatrix} 1 & 1 & 0\\1 & -1 & 1\\1 & -1 & -1\\ \end{bmatrix}</math>

when <math>N=5</math>, 3-level non-normalized DCT-LGST matrix and the inverse matrix is:

<math>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}</math>; <math>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}</math>

when <math>N=8</math>, 4-level non-normalized DCT-LGST matrix and the inverse matrix is:

<math>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}</math>;<math>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}</math>

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

<math>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}</math>;<math>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}</math>

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

<math>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}</math>;<math>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}</math>

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 <math>323</math> is:

<math>\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} ,\;</math>

<math>\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</math>

DCT-HGST can be also defined by a <math>N\times N</math> matrix <math>H_{N}</math>, where <math>N=F_k, (k\ge3,k \in \mathbb{Z})</math>, it is known that the <math>3\times 3</math> non-normalized DCT matrix is:

<math>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} </math>

when <math>N=8</math>, 2-level non-normalized DCT-HGST matrix and the inverse matrix is:

<math>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};</math>

<math>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}</math>

DFT-golden section transform (DFT-GST)

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

<math>

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} </math>

The lifting scheme of reverse-order DCT-LGST

Let <math>F_0 = 0,\; F_1= 1,</math> let <math>\{X_u\}\,\!</math> be the original sequence, let <math>\{S_v\}\,\!</math> be a sequence as the "Low" part of reverse-order DCT-LGST, let <math>\{D_w\}\,\!</math> be a sequence as the "High" part of reverse-order DCT-LGST, we have

<math>\{X_u\}=X_0, X_1, X_2, \ldots, X_u;\;</math> <math>\{S_v\}=S_0, S_1, S_2, \ldots, S_v;\;</math> <math>\{D_w\}=D_0, D_1, D_2, \ldots, D_w\;</math>

where <math>u=F_k-1,\;v=F_{k-1}-1,\;w=F_{k-2}-1\;(k\ge3,k \in \mathbb{Z})</math>

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

<math>\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}</math>

and the reconstruction algorithm is:

<math>\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}</math>

where

<math>\{L_n\}=1, 4, 6, 9, 12, 14, 17, 19, \ldots\;</math> Template:OEIS
<math>\{M_n\}=0, 2, 3, 5, 7, 8, 10, 11, \ldots\;</math> Template:OEIS
<math>\{H_n\}=2, 7, 10, 15, 20, 23, 28, 31, \ldots\;</math> Template:OEIS
<math>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</math>

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

See also

References

  1. ↑ Jun. Li (2007). "Golden Section Method Used in Digital Image Multi-resolution Analysis" (in zh-cn). Application Research of Computers 24 (Suppl.): 1880–1882. ISSN 1001-3695. 
  • 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

Retrieved from "https://deletionpedia.org/w/index.php?title=Golden_section_transform&oldid=368"