離散コサイン変換でRuby練習

　前回離散フーリエ変換でRuby練習した勢いで、今回は、離散コサイン変換(DCT:Discrete Cosine Transform)を実装しデータ圧縮の雰囲気を味わいたいと思います。

◆DCTの特徴

　WEBの世界では普段からお世話になっているJPEGファイルですが、JPEGは画像を圧縮するときにDCTの性質を巧みに利用しています。JPEGが画像を圧縮する手順は、

ファイルの読み込み　→　DCT　→　量子化と符号化　→　ファイル保存

　こんな感じになります。

　画像が小さくなる発想の原点はDCTにあると言ってもいいでしょう。理屈によるとDCTは入力信号を対照的に折り返した連続的な信号として変換することになっています。一方でDFTは入力信号の羅列を変換します。例えば、以下のような周期の信号が入力された場合に、

　DFTの場合は単純な繰り返しになりますので以下のようになります。

　DCTの場合は対照的に繰り返しますので以下のようになります。両方を比較すると、DFTの方は波の継ぎ目が鋭く切り立っているのに対して、DCTの方が滑らかにつながっていることが分かります。

　DCTはこの滑らかなつながりのお陰でDFTに比較して変換後の係数に含まれる高周波成分が少ないことが特徴です。

◆Rubyで実装

　一般的にDCTの式は4種類知られていますが、今回はよく使われるDCT-IIの式を使います。DCTをequ.1に、逆DCT(IDCT:Inverse DCT)をequ.2に示します。

　equ.1

equ.2

equ.3

　この通りRubyの関数として実装します。

def dct(dat)
  ret=[]
  a=2*dat.length
  d=Math.sqrt(2.0 / dat.length)
  dat.length.times{|k|
    b=k*Math::PI
    ret[k]=0.0
    dat.length.times{|n|
      ret[k] += dat[n] * Math.cos(((2*n+1)*b)/a)
    }
    ret[k] *= d
    ret[k] /= Math.sqrt(2) if k==0
  }
  return ret
end

def idct(dat)
  ret=[]
  a=2*dat.length
  d=Math.sqrt(2.0 / dat.length)
  dat.length.times{|n|
    b=2*n+1
    ret[n]=0.0
    dat.length.times{|k|
      ret[n] += dat[k] * Math.cos((k*Math::PI*b)/a)
      ret[n] /= Math.sqrt(2) if k==0
    }
    ret[n] *= d
  }
  return ret
end

◆ちょっとだけデータ圧縮してみる

　では実行してみましょう。実行用のコードを以下に示します。変換と逆変換をするたけでなく、DCTしたデータの後半4つをゼロに置き換えて(ret.fill(0,4..7)の部分)逆変換しています。後半をゼロに置き換えることによってデータを半分に圧縮したことになります。

　ここで注目することは変換係数の前半ではなく後半をゼロにしたことです。高周波成分が少なめに出るDCTの特徴を利用しているわけです。値が少なく出るのであれば思い切ってゼロにしてしまっても大きな影響は無いと推測できます。

dat=[10,15,20,30,40,35,25,10]

ret=dct(dat)
ret.each{|v|
  printf("%.3f ",v)
}
puts

ret.fill(0,4..7)

ret.each{|v|
  printf("%.3f ",v)
}
puts

ret=idct(ret)
ret.each{|v|
  printf("%.3f ",v)
}
puts

　結果はこんな感じです。

65.407 -9.300 -25.967 11.109 -1.768 -0.717 -2.638 1.446
65.407 -9.300 -25.967 11.109 0.000 0.000 0.000 0.000 
11.188 13.207 20.062 31.127 39.113 36.125 23.106 11.072

　入力と似たような数字が出力されていることが分かります。今回試した方法は、データを復元したときに入力と同じになりませんので非可逆圧縮ということになります。同じ原理を利用しているJPEGも非可逆圧縮です。

◆最後に

　今回の内容はRubyを使う必然性がまったく無かったような気もしますが、

　

　

　
Latest update at 2007/11/06