情報科学概論I 【第２回】実データの数理表現 ～音響信号と画像について～ 徳永隆治　（情報学類）.

Presentation on theme: "情報科学概論I 【第２回】実データの数理表現 ～音響信号と画像について～ 徳永隆治　（情報学類）."— Presentation transcript:

1 情報科学概論I 【第２回】実データの数理表現 ～音響信号と画像について～ 徳永隆治　（情報学類）

2 【音響信号；acoustic signals 】
アナログ表現からデジタル表現へ t s 【音響信号；acoustic signals 】 時間t上の粗密波の振幅を表す連続関数s(t) 【写真；photograph 】 2次元空間(h,v)上の明るさを表す連続関数s(h,v) v 【標本化；sampling】 連続関数の変域を離散化する処理 . s n m n s . 【量子化；quantization】 関数の値域を離散化する処理

3 デジタル画像 ピクセル R G B 色の三原色 0～255 (8 bit)

4 デジタル音響信号 音楽用ＣＤ：ＰＣＭフォーマット 標本化：44[kHz] = 44,000 [sample/sec]
　　　量子化：16 [bit/sample] ∈{0,1,.., 65535} 振幅 ． ． ． ． ． ． 1秒間に16[bit]精度の整数が44,000個 1秒 時間

5 【歪み圧縮；losy data compression】
データ圧縮とは？ 【歪み圧縮；losy data compression】 画像や音響信号の質(価値)を大幅に低下させず，可能な限りデータ量を削減する処理． (文書ファイル・プログラムファイル等には，無歪み(lossless)圧縮が適用される．) 生データ 生データ 符号化器 encoder 復号器 decoder 圧縮 ファイル ←小　データ量　大→ 【質問】身の回りの歪み圧縮の例をあげよ．また，その有効性について述べよ． 【例解】映像DVDおよびデジタルビデオに用いられる動画像用フォーマットMPEG２，　デジタルカメラに用いられる画像フォーマットJPEG．音楽ソフトに用いられる 　音響信号フォーマットADPCM，MP3等．データ転送に要する通信コストおよび 　記憶媒体に要するコストを削減できる．

6 認識とは？ 【認識；recognition 】 画像あるいは音響信号から特徴を抽出し，それが何であるか識別し，
それらと関連する“事物”を判定する自動処理． 生データ “あ” 認識系 recognizer “A氏” 【質問】すでに利用されている自動認識の例を挙げよ． 【例解】郵便局の集配システムにおける郵便番号の自動識別 (OCR) ． 【質問】近年，話題となっている生体認証に用いられる特徴を挙げよ． 【例解】声紋，眼底血管，こうさい，毛細血管，指紋等．

7 合成とは？ 【合成；synthesis 】 意味(価値) のある画像や音声・音響信号を自動生成する処理．
高度な合成技術によって超高効率な情報圧縮が可能となる． 合成結果 制御用 パラメータ ファイル 合成器 synthesizer 制御用 パラメータ ファイル ←極小　データ量　大→ 【質問】すでに合成を用いて，高効率のデータ圧縮を達成している製品がある． 　これは何か答えよ． 【例解】ゲーム機，通信カラオケ，着メロ等で用いられるMIDI符号(音楽スコア)． 　ADPCMあるいはMP3で音響信号を直接圧縮した場合と比べると良い．

8 解析学で学ぶ距離空間 【距離と距離空間】 集合X上の２つの元x,y∈Xを実数値に対応づける写像d(x,y)が，以下の条件を満足するとき，dを距離といい，集合Xを距離空間という． １．d(x,y)≧0 (非負性) ２．d(x,y) = d(y,x) 　(可換) ３．d(x,y) = 0 　⇔　x=y ４．d(x,y) ≦ d(x,z) + d(z,y) 　(三角不等式) 集合X 元x 元y R1 d 【例】人間関係の“親密”さは，距離の公理を満足しないあいまいなものである． 　２．他人から計った自分の距離と，自分から計った他人の距離は必ずしも一致しない． 　３．自分と自分の距離は，常に零とは限らない．(時として自分が分からなくなる．) 　４．第３者が介入することで２者の間の距離が近くなる場合がある．

9 情報圧縮における距離空間 符号化器 … … … … [Code Book] 64x3[B] → 1[B]
000:■, 001 :■, 002 :■, 003 :■, 004:■, 005 :■, 006 :■, 007 :■, 008:■, 009 :■, 010 :■, 011:■, 012:■, 013 :■, 014 :■, 015 :■, : 252:■, 253 :■, 254 :■, 255 :■, 【コードブック；code book】 類似したブロック群を代表する ブロックを記録したテーブル． [Data File] 8x8, 64x64 123,222,034,254,001,102,211,246, 123,222,034,253,001,102,211,246, : 123,222,034,254,001,006,211,246, 復号器 … … …

10 n画素からなる画像ブロックは，n次元実空間Rn上の元となる．
コードブックの作成 【画像空間；image space】 n画素からなる画像ブロックは，n次元実空間Rn上の元となる． 【距離で類似度を計る】 画像空間上で，位置の近い画像ブロック 同士は，類似している．したがって， 画像空間には類似度を測るための適当な 距離を定義する必要がある． 【群化；clustering】 　元を幾つかの代表点で近似するとき， 　できるだけ誤差を小さくする代表点 　を選択する処理をクラスタリングと 　いう．コードブックとは，群番号と 　代表点を記録したファイルである． 【LBG法】 全ての元を最寄の代表点で近似した場合の 距離の総量 (誤差関数，目的関数)が極小となるように代表点を移動させる最適化法

11 【特徴抽出；feature extraction】
認識における距離空間 あ お い (a1,b1,c1) (a3,b3,c3) (a4,b4,c4) (a2,b2,c2) (a5,b5,c5) (a6,b6,c6) 【特徴抽出；feature extraction】 対象データから特徴量を 数値として取り出す処理 【マッピング；mapping】 対象データを特徴空間に移す処理 【特徴空間；feature space】 いくつかの特徴量で張られる実空間 a → ↑ c b 【ラベリング；labeling】 名称や意味に基づき群化あるいは， 分割された領域に記名する処理． (a,b,c) お

12 ある集合X上の任意の要素xが，幾つかの特徴的要素（基底ベクトル）
距離だけでは足りない 距離だけでは，２つのパターンが“どれだけ似ているか”が分かるのみであり， “どこがどれぐらい似ているか”を知ることはできない． か お あ 【座標系と成分の重要性】 ある集合X上の任意の要素xが，幾つかの特徴的要素（基底ベクトル） 　　{a,b,c,….}の重ね合わせ x = a a + b b + g c + …….. 　　で表現されるとき，重なりの強さ(a,b,g, ….) はxと特徴的要素との 　　類似度（成分）を意味する．

13 【ベクトル空間；vector space 】
線形代数で学ぶベクトル空間 【ベクトル空間；vector space 】 集合Xには，任意の２元x,y ∈X間の和x+yと差x-yが定義され， 結合則の成立　　　：x+(y+z) = (x+y)+z 交換則の成立　　　：x+y = y+x 単位元・逆元の存在：x+0 = x, x+(-x) = 0 が成り立つとする．また，定数a∈R1との積axが定義されており， 定数の分配則の成立： (a+b)x = ax+bx 元の分配則の成立　： (x+y)a = ax+ay 単位元と逆元の存在：0x = 0, 1x = x が満たされて，線形結合ax + byもXの元となるとき，元をベクトルといい， Xをベクトル空間という． 上記の定義において最も重要な点は， 「何か“x”と何か“y”の線形結合ax+byで，別の何か“z”が作られる」 という特性にある．z は，“x”らしさと“y”らしさだけを持つことに注意する． 　ここで，線形結合・線形独立・線形従属・基底・次元の概念を熟知しよう．

14 実際に成分を計算するとき，“距離”の拡張概念である“内積”が重要となる．
座標を決める＝空間を張る C 直線A={ae1:a∈R1}は，ベクトルe1 で張られる１次元部分空間である． 　　　　　　　　　　 集合X B ce3 直線B ={be1:b∈R1}は，ベクトルe2 で張られる１次元部分空間である． be2 e3 A ae1 e2 e1 線形独立性：e1とe2が平行でない ならば，AとBは同一直線ではない． AとBは一つの平面を定める． 平面a={ae1+be2 : a, b∈R1}は，e1およびe2 で張られる２次元部分空間である． 集合X上の任意の点xが，線形独立なｎ個のベクトルの線形結合 X = a1e1+a2e2 +……. +anen で表現されるとき，集合Xはn次元ベクトル空間をなす．ここで，{e1,…,en}を基底系，{a1,…,an}を成分(あるいは係数) という． 実際に成分を計算するとき，“距離”の拡張概念である“内積”が重要となる．

15 コーシー・シュワルツの不等式：|<x,y>| = ||x||||y|| ⇔ xとyが平行(線形従属)である．
ベクトル空間から内積空間へ 【内積；inner product 】 ベクトル空間X上に，任意の2ベクトルx,y ∈Xを実数値<x,y>へ対応づける 写像が定義されており， 分配則の成立　　：<x+y,z> = <x,z> + <y,z> 交換則の成立　　： <x,y> = <y,x> 定数の括り出し　：<ax, y> = a<x.y> 非負性　　　　　：<x, x> ≧ 0, <x.x> =0 ⇔x = 0 を満たすとき，<x,y>を内積といい，Xを内積空間という． 距離の公理：<x,x>=||x||2は，距離である． 直交性：<x,y>=0　⇔　xとyが直交する. コーシー・シュワルツの不等式：|<x,y>| = ||x||||y|| ⇔ xとyが平行(線形従属)である． 【射影；projection 】 ベクトルxが正規化(||x||=1) されているとき， 内積<x,y>は，xの張る部分空間へ落ちるY の影の長さとなる． y x <x,y>

16 認識と内積空間 . . sn デジタル信号S(1) S(1) = (s1,s2,s3,….,sD) ∈ RD sn デジタル信号S(2)
デジタル信号S(k) . n sn デジタル信号S(2) S(2) = (s1,s2,s3,….,sD) ∈ RD S(k) = (s1,s2,s3,….,sD) ∈ RD . これらのベクトルは，D次元空間全体を 本当に占めているのだろうか？ RD マッピングの結果がd(<D)次元部分空間のみを 占めているならば，この特徴空間は冗長である． この部分空間の次元をどうやって計るのか？

17 射影と主成分分析 座標回転 分散の最大方向 座標回転 データの零平均化 最大方向と直交する 次の最大方向
【主成分；principal component】 データの分散の順に並んだ正規直交座標系の成分を主成分という． 後方に現れる成分は，データを含まない分散が零の部分空間に対応する．

18 情報圧縮における内積空間 D画素ブロック D成分 画素順に並べられた成分には， 昇順あるいは降順という特徴はない． D次元空間
主成分分析と同様に，適当に座標系を回転させることで， 分散の順に成分を並べかえることができる．

19 降順に成分を並べかえることで末尾に零を集中させる．
スカラー量子化との併用 量 子 化 量 子 化 直交変換 整数除算を用いることで， 割り当てるビット数を減らす． 降順に成分を並べかえることで末尾に零を集中させる．

20 レポート問題 【問題１】4つの整数値{0,1,2,3}からなる記号列
　は，2ビットの2進符号 0 → 00, 1 → 01 , 2 → 10 , 3 → 11 　を用いて，2×40=80ビットのデータ量で表現できる． 　ここで，2進符号 0 → 1, 1 → 01 , 2 → 001 , 3 → 0001 　を用いるとき，記号列のデータ量を計算し，総データ量がそのように 　変化した理由を考察せよ． 【レポートの提出方法】 　次回終了の後，２回と３回に出題された２問に回答して， 　レポートを提出せよ．提出場所および期限は，次週に告知する．