2024-09-20

改良型Hough変換について

Hough変換は通常、点群が、ある図形上に乗っているか、乗っていればその図形を表す方程式のパラメータを求める手法で、簡単なので直線上にのっている点群の直線がないとき、つまり点群の集合から、どういう方程式の直線上にのっているか、直線のパラメータを求めるための変換である。

引き続き直線で考える。

直線の方程式は、中学校で習う。y=ax+bとよく書かれる。この形式だとx=cのようなy軸に平行な直線はあらわせないのであるが、細かいことは気にしないで行く。

直線検出アルゴリズムとしてHough変換は使われる。パラメータが確実にぴたっと見つかるので反則なのだが、直線y=ax+b上の点(x0,Y0)、(x1,Y1)、・・・(x(N-1),y(N-1))を適当に決める。するとy=ax+bをa,bを変数、x,yを定数とみて、a、b平面の直線の式として見やすく変形することができる。

y=ax+b

b=-xa+y

bをyの代わり、aをxの代わりとして、a,b平面の直線の方程式としてみるのだ。

xi、yi(i=0～N-1)を代入すると、それぞれの直線は一点で交わる。交わった点が、それらの点群がのっているx,y平面の直線の方程式のパラメータa,bの値である。

というのがHough変換の直線検出アルゴリズムである。

改良型Hough変換は直線の交点としてではなく、パラメータ点そのものをa,b平面の点として表示させるものである。

これにはCTのラドン変換を使った断面投影定理を使うことで可能になる。

ラドン変換や、逆投影法、フィルター補正逆投影法、重畳積分法など、ネットをみれば、解説している論文が拾えるので解説はしない。

Hough変換のラドン変換表示は、

\begin{equation} g(s, \theta_{i} )= \delta (s-y_{i} \sin \theta_{i} ) \end{equation}

\begin{equation} \tan \theta_{i} = \frac {1}{x_{i}} \end{equation}

\begin{equation} \Delta \theta = \theta_{i} - \theta_{i-1} (i=1 to N) = const. \end{equation}

である。

$ \tan \theta $ の定義から $ \sin \theta $ および $ \cos \theta $ はもとめることができる。

さて、Hough変換は、2次元で完結するものだったが、3次元で考えよう。関数 $ f(a,b) $ を考える。a,b平面での直線 $ b=-x_{i} a + y_{i} $ に重みをもたせ $ f(a,b) $ とするのである。するとHough変換は、ラドン変換を逆投影したものに似ていることに気付くといいんだけど、気付いてね。 $ b=-x_{i} a + y_{i} $ に垂直な原点を通る直線 $ b = \frac{1}{x_{i}} $ これは、S軸である。これをS軸に垂直な方向に逆投影したものが、Hough変換である。よって、フィルター補正逆投影法でパラメータ a*,b*のインパルス関数 $ f(a,b) $ が求まるというのが、改良型Hough変換である。 $ f(a,b) $ は、パラメータ点 $ (a*,b*) $ のみ、無限大になり、他は0になる2次元δ関数 $ \delta (a-a*,b-b*) $ となる。

\begin{equation} f(a,b) = \int_{0}^{ \pi } (g(s, \theta ) \circledast h(s)) d \theta \end{equation}

\begin{equation} = \int_{0}^{ \pi } ( \delta (s-y_{i} \sin \theta ) \circledast h(s)) d \theta \end{equation}

\begin{equation} = \int_{0}^{ \pi } ( h(s-y_{i} \sin \theta ) ) d \theta \end{equation}

\begin{equation} = \int_{0}^{ \pi } ( h(a \cos \theta +b \sin \theta -y_{i} \sin \theta ) ) d \theta \end{equation}

\begin{equation} = \int_{0}^{ \pi } ( h( \frac {ax_{i}}{ \sqrt {x_{i}^{2} +1}} + \frac {b}{ \sqrt {x_{i}^{2} +1}} - \frac {y_{i}}{ \sqrt {x_{i}^{2} +1}} ) ) d \theta \end{equation}

\begin{equation} = \sum_{i=0}^{N-1} h( \frac {1}{ \sqrt {x_{i}^{2} +1}} (ax_{i} + b - y_{i}) ) \end{equation}

\begin{equation} h(s) = \int_{- \infty}^{ \infty } | \rho | \exp (2 \pi \rho s i) d \rho \end{equation}

　$ h(s) $は、アナログで式を書いたが、これをサンプリングし、格子状の点で考える。

サンプリング定理や補間の技術を使い、デジタル化してプログラミングすればよい。

面倒なら、shepp_logan , ram_lack等のデジタル化されたフィルターを使うのが良いと思う。

2022-08-03

修正離散コサイン逆変換とは？

まず、修正離散コサイン変換は

\begin{equation} S(r) = \sum_{k=0}^{N/2-1}p'(k){ \rm cos} ( \frac{2π}{N}(k+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

とDCTⅣで表せた。

よって逆変換が成立する。

\begin{equation} p'(k) = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}(k+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

ここで $ p'(k) $ は、変換対象数列の後半の偶対称数列部の後半を取り出し符号を反転したものの右に変換対象数列の前半の奇対称数列部の前半を並べたものであった。

したがってIMDCTでもとめるものは、変換対象数列の前半の奇対称数列部の右に変換対象数列の後半の偶対称数列部を並べたものをもとめることになる。

よって変換対象数列の前半の奇対称数列部の前半 $ p'(k+N/4) (k=0～N/4-1) $

変換対象数列の前半の奇対称数列部の後半 $ -p'(3N/4-1-k) (k=N/4～N/2-1) $

変換対象数列の後半の偶対称数列部の前半 $ -p'(3N/4-1-k) (k=N/2～3N/4-1) $

変換対象数列の後半の偶対称数列部の後半 $ -p'(k-3N/4) (k=3N/4～N-1) $

がIMDCTででてくることを証明すればいい。

ここ、ちょっとわかりにくいと思うけど、上の図3の波形（数列）がp'(k)としたとき

p'(k)から図1の数列をどうやってつくるかkに値をいれて図1と図3をにらめっこすれば

わかるんではないかと思います。分からない人は、文字に慣れてないだけだと思うので

Nに具体的な数字をいれてやってみてください。

そこで

\begin{equation} p'(k) = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}(k+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

であるから

\begin{equation} p'(k+ \frac{N}{4}) = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}(k+ \frac{N}{4}+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

\begin{equation} p'( \frac{3N}{4}-1-k) = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}( \frac{3N}{4}-1-k+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

\begin{equation} = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}( N- \frac{N}{4}-1-k+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

\begin{equation} = - \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}( k+ \frac{N}{4} + \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

\begin{equation} p'(k- \frac{3N}{4}) = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}( k- \frac{3N}{4}+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

\begin{equation} = \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}( -N+ \frac{N}{4}+k+ \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

\begin{equation} = - \sum_{r=0}^{N/2-1}S(r){ \rm cos}( \frac{2π}{N}( k+ \frac{N}{4} + \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

となり $ S(r) $ にIMDCTをかけると、図1の波形が再生されることがわかっていただける

のではないかと思います。すべてDCTⅣの式がIMDCTの定義式に変化してるでしょ。

MDCT結果S(r)にDCTⅣをかけると図3の波形が求まる。ところがIMDCTをかけると図1の

波形が求まるということを言っています。

フーリエ変換系の理論の奥深さに私はたまげました。

同時にまだ、実用的な応用変換が隠れてるような気がしてきました。

なお前の2つの記事、修正離散コサイン変換とは何か（まとめ）からみないと

わからないのはあしからず。

2022-06-07

修正離散コサイン変換とは何か２（まとめ）

前回の記事では詰めが甘い。

\begin{equation} S(r) = \frac{1}{2}{ \rm exp}(i \frac{πr}{N}) \sum_{k=N/4}^{3N/4-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N}) (s(k- \frac{N}{4})-s( \frac{3N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} kr) \end{equation}

\begin{equation} + \frac{1}{2}{ \rm exp}(i \frac{πr}{N}) \sum_{k=3N/4}^{N-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N}) (s(k- \frac{N}{4})+s( \frac{7N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} kr) \end{equation}

\begin{equation} - \frac{1}{2}{ \rm exp}(i \frac{πr}{N}) \sum_{k=0}^{N/4-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N}) (s(k+ \frac{3N}{4})+s( \frac{3N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} kr) \end{equation}

ここで

$ p(k) = s(k- \frac{N}{4})-s( \frac{3N}{4}-1-k) (k=N/4～3N/4-1) $

$ s(k- \frac{N}{4})+s( \frac{7N}{4}-1-k) (k=3N/4～N-1） $

$ -s(k+ \frac{3N}{4})-s( \frac{3N}{4}-1-k) (k=0～N/4-1) $

とおくと

\begin{equation} S(r) = \frac{1}{2}{ \rm exp}(i \frac{πr}{N}) \sum_{k=0}^{N-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N})p(k){ \rm exp}(i \frac{2π}{N}kr) \end{equation}

$ p(k) $ は、奇対称数列となる。

MDCTをかける数列の前半の奇対称数列部とMDCTをかける数列の後半の偶対称数列部

を並べて、4等分し、最後の1/4を前にもってきて、その前に持ってきたものだけ符号を

変えたものである。

\begin{equation} S(r) = \frac{1}{2} \sum_{k=0}^{N-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N})p(k){ \rm exp}(i \frac{2π}{N}(kr+ \frac{r}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N})p(k){ \rm exp}(i \frac{2π}{N}r(k+ \frac{1}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}p(k){ \rm exp}(i \frac{2π}{N}( \frac{1}{2}(k + \frac{1}{2})+r(k+ \frac{1}{2}))) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}p(k){ \rm exp}(i \frac{2π}{N} (k + \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

以前のDCTⅣの記事を参照すると

\begin{equation} \sum_{k=0}^{N-1}s'(k){ \rm cos}( \frac{2π}{2N} (k + \frac{1}{2})(r+ \frac{1}{2})) = \frac{1}{2} \sum_{k=0}^{2N-1}p'(k){ \rm exp}( \frac{i2π}{2N} (k + \frac{1}{2})(r+ \frac{1}{2}))\end{equation}

$ p'(k) = s'(k) (k=0～N-1) $

$　　　-s'(k) (k=N～2N-1) $

において、 $ N $ を $ \frac{N}{2} $ に書き換えると、$ k $ の範囲を考慮して $ s'(k) $ は

$ p'(k) $ に書き換えられる。よって

\begin{equation} \sum_{k=0}^{N/2-1}p'(k){ \rm cos}( \frac{2π}{N} (k + \frac{1}{2})(r+ \frac{1}{2})) = \frac{1}{2} \sum_{k=0}^{N-1}p'(k){ \rm exp}( \frac{i2π}{N} (k + \frac{1}{2})(r+ \frac{1}{2}))\end{equation}

$ p'(k) $ を $ p(k) $ におきかえて、結局

\begin{equation} S(r) = \sum_{k=0}^{N/2-1}p(k){ \rm cos}( \frac{2π}{N} (k + \frac{1}{2})(r+ \frac{1}{2})) \end{equation}

こうして、MDCTは、p(k)の前半部分のDCTⅣとなる。

2022-04-29

修正離散コサイン変換とは、何か？（まとめ）

\begin{equation} S(r) = \sum_{k=0}^{N-1} s(k) {\rm cos}( \frac{2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+ \frac{1}{2})) 　ただし(r = 0～N/2-1) \end{equation}

\begin{equation} = \frac{1}{2}( \sum_{k=0}^{N-1} s(k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2}))+\sum_{k=0}^{N-1} s(k) {\rm exp}(-i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2}))) \end{equation}

\begin{equation} =\frac{1}{2}( \sum_{k=0}^{N/2-1} s(k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2}))+\sum_{k=N/2}^{N-1} s(k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2})) \end{equation}

\begin{equation} +\sum_{k=0}^{N/2-1} s(k) {\rm exp}(-i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2})) + \sum_{k=N/2}^{N-1} s(k) {\rm exp}(-i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2})))\end{equation}

\begin{equation} +\sum_{k=0}^{N/2-1} s(\frac{N}{2}-1-k) {\rm exp}(-i \frac {2 \pi} {N} (\frac{N}{2}-1-k+ \frac{1}{2}+ \frac{N}{4})(r+\frac{1}{2})) \end{equation}

\begin{equation} + \sum_{k=N/2}^{N-1} s(\frac{3N}{2}-1-k) {\rm exp}(-i \frac {2 \pi} {N} (\frac{3N}{2}-1-k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2})))\end{equation}

\begin{equation} +\sum_{k=0}^{N/2-1} s(\frac{N}{2}-1-k) {\rm exp}(-i \frac {2 \pi} {N} (\frac{3N}{4}-k- \frac{1}{2})(r+\frac{1}{2})) \end{equation}

\begin{equation} + \sum_{k=N/2}^{N-1} s(\frac{3N}{2}-1-k) {\rm exp}(-i \frac {2 \pi} {N} (\frac{7N}{4}-k- \frac{1}{2})(r+\frac{1}{2})))\end{equation}

\begin{equation} +\sum_{k=0}^{N/2-1} s(\frac{N}{2}-1-k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2}-\frac{3N}{4})(r+\frac{1}{2})) \end{equation}

\begin{equation} + \sum_{k=N/2}^{N-1} s(\frac{3N}{2}-1-k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2}-\frac{7N}{4})(r+\frac{1}{2})))\end{equation}

\begin{equation} -\sum_{k=0}^{N/2-1} s(\frac{N}{2}-1-k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2}+\frac{N}{4})(r+\frac{1}{2})) \end{equation}

\begin{equation} + \sum_{k=N/2}^{N-1} s(\frac{3N}{2}-1-k) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2}+\frac{N}{4})(r+\frac{1}{2})))\end{equation}

\begin{equation} S(r)=\frac{1}{2}( \sum_{k=0}^{N/2-1} (s(k)-s(\frac{N}{2}-1-k)) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2}+ \frac{N}{4})(r+\frac{1}{2})) \end{equation}

\begin{equation} + \sum_{k=N/2}^{N-1} (s(k)+s(\frac{3N}{2}-1-k)) {\rm exp}(i \frac {2 \pi} {N} (k+ \frac{1}{2} + \frac{N}{4})(r+\frac{1}{2}))) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=N/4+1/2}^{3N/4-1/2}(s(k- \frac{N}{4}- \frac{1}{2})-s( \frac{3N}{4}- \frac{1}{2}-k)){\rm exp}(i \frac {2 \pi}{N}k(r+ \frac{1}{2})) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=3N/4+1/2}^{5N/4-1/2}(s(k- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}k(r+ \frac{1}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=N/4+1/2}^{3N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})-s( \frac{3N}{4}- \frac{1}{2}-k)){\rm exp}(i \frac {2 \pi}{N}kr ) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=3N/4+1/2}^{5N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}kr) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=N/4+1/2}^{3N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})-s( \frac{3N}{4}- \frac{1}{2}-k)){\rm exp}(i \frac {2 \pi}{N}kr ) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=3N/4+1/2}^{N-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}kr) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=N+1/2}^{5N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}kr) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=N/4+1/2}^{3N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})-s( \frac{3N}{4}- \frac{1}{2}-k)){\rm exp}(i \frac {2 \pi}{N}kr ) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=3N/4+1/2}^{N-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}kr) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=1/2}^{N/4-1/2}{ \rm exp}(i \frac{ \pi (k+N)}{N})(s(k+N- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-(k+N))){ \rm exp}(i \frac {2 \pi}{N}(k+N)r) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=N/4+1/2}^{3N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})-s( \frac{3N}{4}- \frac{1}{2}-k)){\rm exp}(i \frac {2 \pi}{N}kr ) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=3N/4+1/2}^{N-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k- \frac{N}{4}- \frac{1}{2})+s( \frac{7N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}kr) \end{equation}

\begin{equation} - \frac{1}{2} \sum_{k=1/2}^{N/4-1/2}{ \rm exp}(i \frac{ \pi k}{N})(s(k+ \frac{3N}{4}- \frac{1}{2})+s( \frac{3N}{4}- \frac{1}{2}-k)){ \rm exp}(i \frac {2 \pi}{N}kr) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=N/4}^{3N/4-1} { \rm exp}(iπ \frac{k+ \frac{1}{2}}{N}) (s(k- \frac{N}{4})-s( \frac{3N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} (k+ \frac{1}{2})r) \end{equation}

\begin{equation} + \frac{1}{2} \sum_{k=3N/4}^{N-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N})(s(k- \frac{N}{4})+s( \frac{7N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} (k+ \frac{1}{2})r) \end{equation}

\begin{equation} - \frac{1}{2} \sum_{k=0}^{N/4-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N})(s(k+ \frac{3N}{4})+s( \frac{3N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} (k+ \frac{1}{2})r) \end{equation}

\begin{equation} = \frac{1}{2}{ \rm exp}(i \frac{πr}{N}) \sum_{k=N/4}^{3N/4-1}{ \rm exp}(iπ \frac{k+ \frac{1}{2}}{N}) (s(k- \frac{N}{4})-s( \frac{3N}{4}-1-k)){ \rm exp}(i \frac{2π}{N} kr) \end{equation}

修正離散コサイン変換を離散フーリエ変換で表すと、上式のようになります。

$ 0～N/4-1 , N/4～3N/4-1 , 3N/4～N-1 $ の３つの範囲で項が３つの式になりますが

それぞれみていくと、 $ N/4～3N/4-1 $ の範囲には、数列の前半の奇対称数列成分

がきていて

$ 3N/4～N-1 $ の範囲には、数列の後半の偶対称数列成分の前半部分がきていて

$ 0～N/4-1 $ の範囲には、数列の後半の偶対称数列成分の後半部分に対して符号

を逆にしたものがきています。

意味を紐解いていくと、変換をかける数列 $ s(k) (k=0～N-1) $ の前半部分の奇対称数列

成分をとりだし、後半部分の偶対称数列成分をとりだし、並べて、4等分し、最後の1/4

部分を前にもってきて、そのもってきた部分のみ符号を反対にした数列

（この数列は奇対称数列になっています。）

に $ { \rm exp}(iπ \frac{k+ \frac{1}{2}}{N}) $

をかけたものを離散フーリエ変換し、しあげに $ \frac{1}{2}{ \rm exp}(i \frac{πr}{N}) $ を

かけたものとなります。 $ r $ の範囲は $ 0～N/2-1 $ なので、半分しか

とりだしません。フーリエ変換として見ると、 $ r = 0～N-1 $ で値を取り出せます。

しかし、 $ N/2～N-1 $ の残りの半分は同じもので冗長なのではぶくのが

修正離散コサイン変換です。

奇対称数列の離散フーリエ変換は、実部が０で、虚部が奇対称数列になります。虚部の

奇対称数列は、半分だけわかれば、もう半分はわかります。半分だけで実数として計算

するのが離散サイン変換です。

修正離散コサイン変換は、実は、変換をかける数列 $ s(k) (k=0～N-1) $ の前半部分の

奇対称数列成分の半分と後半部分の偶対称数列成分の半分をならべたものを変形

したものの離散サイン変換（実はDCTⅣ、このすぐ後の記事で導出しています。）

なのです。厳密な対称性とかを考慮するとちょっと

違いますが、本質的には、そう思っていいと思います。

2022-04-10

DCTⅠをDFTで表す。（今回のは、正しいと思います。）

DCTⅠの定義は、次の通りです。

\begin{equation} S(r) = \frac{1}{2} s(0)+ \frac{1}{2} s(N-1)(-1)^r+ \sum_{k=1}^{N-2}s(k) {\rm cos} \frac{2πkr}{2N-2} \end{equation}

本式を変形します。

\begin{equation} S(r) = \frac{1}{2} s(0)+ \frac{1}{2} s(N-1)(-1)^r+ \frac{1}{2} \sum_{k=1}^{N-2}s(k){\rm exp} \frac{i2πkr}{2N-2} + \frac{1}{2} \sum_{k=1}^{N-2}s(k){\rm exp} \frac{-i2πkr}{2N-2} \end{equation}

\begin{equation} = \frac{1}{2} s(0)+ \frac{1}{2} s(N-1)(-1)^r+ \frac{1}{2} \sum_{k=1}^{N-2}s(k){\rm exp} \frac{i2πkr}{2N-2} + \frac{1}{2} \sum_{k=N}^{2N-3}s(2N-2-k){\rm exp} \frac{-i2π(2N-2-k)r}{2N-2} \end{equation}

\begin{equation} = \frac{1}{2} s(N-1)(-1)^r+ \frac{1}{2} \sum_{k=0}^{N-2}s(k){\rm exp} \frac{i2πkr}{2N-2} + \frac{1}{2} \sum_{k=N}^{2N-3}s(2N-2-k){\rm exp} \frac{i2πkr}{2N-2} \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}s(k){\rm exp} \frac{i2πkr}{2N-2} + \frac{1}{2} \sum_{k=N}^{2N-3}s(2N-2-k){\rm exp} \frac{i2πkr}{2N-2} \end{equation}

ここで

$ p(k) = s(k) (k = 0 ～ N-1) $

　　　$ s(2N-2-k) (k= N ～ 2N-3) $

とおくと

\begin{equation} S(r) = \frac{1}{2} \sum_{k=0}^{2N-3}p(k){\rm exp} \frac{i2πkr}{2N-2} \end{equation}

となり、2N-2ポイントのDFTで表せました。

N-1の2倍は2(N-1) = 2N-2です。

N'=N-1で変数変換してみると、N'点の変換を偶対称に展開して2N'ポイントのDFTを

していることがわかります。

2022-03-17

DCTⅠをDFTで表す。

この記事は、DCTⅠ自身が逆変換になるDCTⅠの話ではありません。

本記事のDCTⅠの定義だと情報に不足が生じて、逆変換の本記事定義のDCTⅠでは

もとにもどりません。正しい定義はWIKIPEDIAの式になります。

その式については、改めて書きたいと思います。

以下の記事は、DCTⅡ～Ⅳと対称性をもたせたものが

成り立つと思っていた時代の記事です。

逆変換があるかわからないので、この記事は読まないほうがいいと思います。

情報が欠落するのでおそらく逆変換はないと思います。

DCTⅠの定義式は次の通りです。

\begin{equation} S(r)= \sum_{k=0}^{N-1} s(k) { \rm cos}( \frac{2π}{2N}kr) \end{equation}

この式を変形して

\begin{equation} S(r)= \frac{1}{2} \sum_{k=0}^{N-1} s(k) exp( \frac{i2π}{2N}kr) + \frac{1}{2} \sum_{k=0}^{N-1} s(k) exp( \frac{-i2π}{2N}kr) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1} s(k) exp( \frac{i2π}{2N}kr) + \frac{1}{2} \sum_{k=N+1}^{2N} s(2N-k) exp( \frac{-i2π}{2N}(2N-k)r) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1} s(k) exp( \frac{i2π}{2N}kr) + \frac{1}{2} \sum_{k=N+1}^{2N} s(2N-k) exp( \frac{-i2π}{2N}(-k)r) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1} s(k) exp( \frac{i2π}{2N}kr) + \frac{1}{2} \sum_{k=N+1}^{2N} s(2N-k) exp( \frac{i2π}{2N}kr) \end{equation}

$ k=0 $ と $ k=2N $ の場合を外に出すと

\begin{equation} S(r) = \frac{s(0)}{2} + \frac{s(0)}{2} + \frac{1}{2} \sum_{k=1}^{N-1}s(k)exp( \frac{i2π}{2N}kr) + \frac{1}{2} \sum_{k=N+1}^{2N-1}s(2N-k)exp( \frac{i2π}{2N}kr)\end{equation}

\begin{equation} = s(0) + \frac{1}{2} \sum_{k=1}^{N-1}s(k)exp( \frac{i2π}{2N}kr) + \frac{1}{2} \sum_{k=N+1}^{2N-1}s(2N-k)exp( \frac{i2π}{2N}kr)\end{equation}

ここで

$ p(k) = 　　　0 　(k=0,N) $

　　　　　　 $ s(k)　　(k=1～N-1) $

　　　　　 $ s(2N-k) 　　(k=N+1～2N-1) $

とおくと

\begin{equation} S(r) = s(0) + \frac{1}{2} \sum_{k=0}^{2N-1}p(k)exp( \frac{i2π}{2N}kr) \end{equation}

となり、 $ s(1)～s(N-1) $ を $ N $ 点で鏡像をとったものの離散フーリエ変換で各変換係数に $ s(0) $ をたしたものになる。

2022-03-12

DCTⅢをDFTで表す。

DCTⅢの定義式は、次の通りである。

\begin{equation} S(r) = \sum_{k=0}^{N-1}s(k){ \rm cos}( \frac{2π}{2N}k(r+ \frac{1}{2})) \end{equation}

この式を変形する。

\begin{equation} S(r) = \frac{1}{2} \sum_{k=0}^{N-1}s(k) exp( \frac{i2π}{2 N}k(r + \frac{1}{2})) + \frac{1}{2} \sum_{k=0}^{N-1}s(k) exp( \frac{-i2π}{2N}k(r + \frac{1}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}s(k) exp( \frac{i2π}{2 N}k(r + \frac{1}{2})) + \frac{1}{2} \sum_{k=N+1}^{2N}s(2N-k)exp( \frac{-i2π}{2N}(2N-k)(r+ \frac{1}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}s(k) exp( \frac{i2π}{2 N}k(r + \frac{1}{2})) - \frac{1}{2} \sum_{k=N+1}^{2N}s(2N-k)exp( \frac{-i2π}{2N}(-k)(r+ \frac{1}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}s(k) exp( \frac{i2π}{2 N}k(r + \frac{1}{2})) - \frac{1}{2} \sum_{k=N+1}^{2N}s(2N-k)exp( \frac{i2π}{2N}k(r+ \frac{1}{2})) \end{equation}

\begin{equation} = \frac{1}{2} \sum_{k=0}^{N-1}s(k)exp( \frac{iπk}{2N}) exp( \frac{i2π}{2 N}kr) - \frac{1}{2} \sum_{k=N+1}^{2N}s(2N-k)exp( \frac{iπk}{2N})exp( \frac{i2π}{2N}kr) \end{equation}

ここで $ \sum $ から $ k=0 $ と $ k=2N $ を分離すると

\begin{equation} S(r) = \frac{1}{2}s(0) + \frac{1}{2}s(0) + \frac{1}{2} \sum_{k=1}^{N-1}s(k)exp( \frac{iπk}{2N}) exp( \frac{i2π}{2 N}kr) - \frac{1}{2} \sum_{k=N+1}^{2N-1}s(2N-k)exp( \frac{iπk}{2N})exp( \frac{i2π}{2N}kr) \end{equation}

\begin{equation} = s(0) + \frac{1}{2} \sum_{k=1}^{N-1}s(k)exp( \frac{iπk}{2N}) exp( \frac{i2π}{2 N}kr) - \frac{1}{2} \sum_{k=N+1}^{2N-1}s(2N-k)exp( \frac{iπk}{2N})exp( \frac{i2π}{2N}kr) \end{equation}

ここで $ p(k) = 0 (k=0,N) $

　　　　 $ s(k) (k=1～N-1) $

　　　　　　$ -s(2N-k) (k=N+1～2N-1) $

とおくと

\begin{equation} S(r) = s(0) + \frac{1}{2} \sum_{k=0}^{2N-1}p(k)exp( \frac{iπk}{2N}) exp( \frac{i2π}{2 N}kr) \end{equation}

このように $ k=N $ を対称の中心とする奇対称数列に $ exp( \frac{iπk}{2N}) $

をかけたものを離散フーリエ変換したものにs(0)をたしたものがDCTⅢである。

$ s(0) $を分離することで、奇対称数列化ができ、$ exp( \frac{iπk}{2N}) $ をかけること

で実偶対称数列から０．５ずれたの変換結果が得られる。