JAIST Repository
https://dspace.jaist.ac.jp/Title

デジタル著作物の適正流通を支援する電子指紋の超高速検出と実時間検索

Author(s)井口, 寧Citation

科学研究費補助金研究成果報告書: 1‑5

Issue Date

2012‑03‑31

TypeResearch Paper

Text version

publisher

URL

http://hdl.handle.net/10119/10597

RightsDescription

研究種目：基盤研究（Ｃ）, 研究期間：2008〜2010,
課題番号：20500049, 研究者番号：90293406, 研究分
野：並列処理, 科研費の分科・細目：情報学・計算機システム・ネットワーク

Japan Advanced Institute of Science and Technology

様式 C-19
科学研究費補助金研究成果報告書
平成２４年

３月３１日現在

機関番号：１３３０２
研究種目：基盤研究（Ｃ）
研究期間：2008～ 2010
課題番号：20500049
研究課題名（和文） デジタル著作物の適正流通を支援する電子指紋の超高速検出と実時
間検索
研究課題名（英文） High speed audio fingerprint detection to support fair trade ofdigital contents and real time search.
研究代表者
井口 寧（INOGUCHI YASUSHI）
北陸先端科学技術大学院大学・情報社会基盤研究センター・准教授
研究者番号：90293406

研究成果の概要（和文）：
本研究では，インターネットに流通する音楽ファイルをリアルタイムに検出し，楽曲を特定するために必要な，インターネットを流通する音楽ファイル(mp3)などの楽曲を特定するために必要な，超高速電子指紋検出技術 (音楽ファイルからの指紋生成)について研究を行った．ハードウェアに適合する Haar Waveet 変換 (HWT)を用いた新たなアルゴリズムを開発し，その検出速度は 21.86Gbps を得て，従来の FFT に基づいた手法の 1 万 8 千倍近い速度向上を達成した．
研究成果の概要（英文）：This research addressed to develop an ultra-high speed audio finger print detection
scheme to identify music from audio files such as mp3 which are exchanged throughinternet.
We developed a new algorithm to synthesize audio fingerprint based on
Haar-wavelet transform which is suitable for hardware implementation. Proposed
scheme reached to 21.86Gbps detection speed and this speed is almost 18 thousand times
faster than conventional FFT based method.
交付決定額（金額単位：円）2008 年度
2009 年度
2010 年度
年度
年度
総 計

直接経費
2,000,000
900,000
700,000

間接経費
600,000
270,000
210,000

3,600,000

1,080,000

合計
2,600,000
1,170,000
910,000

4,680,000

研究分野：並列処理
科研費の分科・細目：情報学・計算機システム・ネットワーク
キーワード：FPGA, リコンフィギャラブル，電子指紋，音楽ファイル，インターネット配信

１．研究開始当初の背景
近年，Winny や WinMX など，インターネッ
トでデジタル著作物を交換するソフトウェア(ファイル交換ソフト)が広く用いられ，デジタル著作物の著作権侵害が大きな社会問題となっている．このデジタル著作物を保護するための一手法として，電子指紋技術[1]が注目されている．電子指紋は，音楽や画像などのデジタル著作物の周波数帯域ごとのエネルギー遷移など，著作物ごとの特徴量を計量することによって著作物を特定する技術であり，著作物のコピーコントロールを成し得る重要な技術である．音楽などの著作物は，指紋によって楽曲が特定できるので，著作権者は流通しているデジタル化著作物の著作権の主張できるのである．ところで，電子指紋検出は従来ソフトウェアで行われており，検出速度が低速であるため，ネットワークを介して流通するデジタル著作物の電子指紋の実時間検出・特定は困難という問題があった．
一方で，ファイル交換ソフトを利用する理由
は，必ずしも著作権を侵害することが目的ではなく，音楽等の便利な入手ツールとして利用している要素が少なくない(例えば，米国Apple 社による音楽のダウンロードサービスの成功は良い傍証である)． つまり流通の利便性が確保できれば，ネットワークを介した著作物の公正な利用を大きく活性化できる可能性は大きいと考えられる．
これまで平成 17 年度～19 年度の若手研究(A)で，電子透かしを用いたデジタル著作物の超高速検出について研究を行った．その過程で電子透かしを用いた超高速音楽ファイル検出技術は確立されたが(特許出願済み)，実用化に際して次の点が解決すべき課題であることが分かった．
(1)音楽ファイルに透かしを挿入することは，小さいとは言え雑音の混入につながり，音楽関係者から強い抵抗感があること，および(2) 透かしを検出した後，何百万曲もの楽曲の中から検出した楽曲をリアルタイムに検索・特定する技術が必要なこと．

２．研究の目的
そこで本研究では，実用的にインターネット上で音楽を検出・特定するために必要な，次の研究課題に取り組む．
(1) 原音の音楽ファイルを改変せず楽曲を特定できる，電子指紋を用いた超高速電子指紋検出(2) 多数の楽曲から電子指紋に合致する曲を瞬時に特定する，リアルタイム指紋照合検索
本研究で目指すものは，単なる音楽の特定ではなく，誰もが手軽に音楽を交換できるシステムの構築にある．従来では，良い楽曲があっても，著作権法の制約のため直接その楽曲を伝えることはできず，アーティストや曲名を友達に伝え，伝えられた側は別途 CD 屋さんや iTunes 等からダウンロードする必要があった．もし音楽の電子指紋が高速に検出・検索できれば，誰が誰にどの楽曲を送ったか把握でき，許諾の付与や課金を容易に行うことができる．このような手軽で合理的な音楽共有のための手段を構築し，社会の豊かさに貢献することが，本研究の究極の目的である．

そこで本研究では，まず第一に (1) 電子指紋の検出をハードウェア回路で処理することによって，指紋検出処理の大幅な高速化を試みる．高速化の為のアイディアの骨子は次の通りである．
(i) VLSI チップ内の回路をユーザーが動的に構成可能な，FPGA や DRP 等のリコンフィギャラブル・デバイス(RC デバイス)を用いて，検出する指紋情報を回路内に埋め込む．この結果，比較器などが簡略化でき，回路の利用効率が向上する．さらに比較対象を外部メモリから読み込む必要が無いため，ピン・ボトルネックが半減する．(ii) 同時に複数の指紋を並列に検出する．ハードウェア回路では，各部分回路は独立して並列に動作するので，複数の指紋セグメントに対する検出回路を並列に実装することによって，処理速度の大幅な向上を目指す．
第二に，この超高速電子指紋検出システムをインターネットに適用する際に必要となる (2) リアルタイム指紋照合検索技術を開発する．たとえ著作物の指紋が超高速に検出できたとしても，市場にはおよそ百万曲の楽曲が流通し，これらの指紋情報は膨大なものとなる．一方で，インターネットの通信速度は年々向上し，音楽ファイルがネットワークを通過する時間は極めて短い．そこで，音楽の流行廃れに着眼し，次のような超高速照合
指紋データベースの階層化．膨大な検索機構を考える．
(i) 楽曲のうち，一部の電子指紋を RC デバイス内へ埋め込み，高速に検出する．検出に漏れた楽曲は，ソフトウェアで処理を行う．
(ii) どの楽曲を埋め込むか，オリコンヒッ
トチャートなどの楽曲流行に基づいて回路を入れ替えるアルゴリズムを明らかにする．
音楽流通では，一般のデータアクセスに比べて (a)少数のヒット曲が全体の流通の大部分を占める，(b) ヒット曲の入れ替わりは週単位で，しかも発売当初爆発的に流通し，徐々に減少する，といった特徴がある．そこで本研究では，楽曲のヒットチャートに基づく，音楽流通のための階層化検索アルゴリズ
ムを研究開発する．前述したように，検出対象の電子指紋を RC デバイスに埋め込む場合，チップ容量の制限から 100 万曲分全ての指紋検出回路を埋め込むことはできない．そこで，出現頻度が高い楽曲の指紋検出回路を RC デバイス内に動的に入れ替え，平均応答時間を大幅に短縮する，音楽向け電子指紋照合検索のための高速アルゴリズムを開発する．具体的には，ある電子指紋を検索キーとして，100万曲の中から 40 ミリ秒で照合検索できることが目標である．

３．研究の方法
最初に，インターネットに適用可能な，電子指紋高速検出システムの構築に取り組む．指紋検出のハードウェア・コアは，音楽ファイル向けの電子指紋検出回路を並列実装することによって，処理の高速化を達成する．並列に検出処理を行なう回路のブロック図を考える．システムに入力された音楽データは，一定の長さ(バイト数)にセグメント分割された後，セグメントごとに FFT および周波数バンドごとのエネルギー計算を行う．この時間推移がその音楽の電子指紋となる．
セグメントごとの FFT およびエネルギー計算は独立して行えるので，FFT およびエネルギー計算のための回路を並列に実装し，処理の高速化を図る．また，音楽向け電子指紋では，最終的に入力音楽の指紋と多くの楽曲の指紋データベース(指紋 DB)のエントリを比較する必要があるが，指紋の比較は周波数のバンドごとに独立して行うことができる．そこで，指紋のバンドごとにも比較回路を並列実装し，検出処理速度を更に向上させる．つまり，本研究では，検出回路をセグメントごと，およびバンドごとの 2 段階の並列化によって処理の大幅な高速化を目指す．設計した並列指紋検出回路を，VLSI 内の回路をユーザーが自由に書き変え可能な FPGA や DRP 等のリコンフィギャラブル・デバイス(RC デバイス)を用いて実装する．
指紋検出ハードウェア・コアのもう一つの特徴は，「ある特定の指紋を検出する回路」を複数並列化して，RC デバイス内に構築することである．指紋照合検索では，インターネ
ットを流通した音楽の電子指紋を指紋 DB から照合検索し，該当する楽曲を特定する．この時に必要なハミング距離比較器を並列化し，参照元となる指紋 DB の一部を回路内に埋め込めば，LSI のピン・ボトルネック(LSIの入出力ボトルネック)を解消し，ソフトウェアに比べて大幅な検索速度向上が期待できる．目標として，数百 Mbps 以上(理論性能1Gbps, 実効 500Mbps 以上)の検出・検索速度を目指すが，達成不可能な場合はシミュレーションで置き換え，この出力を次の第二段階の入力とする．

４．研究成果2008 年度は，電子指紋検出アルゴリズムの計算量、回路量、被検出楽曲に対する耐改変性などについて，既存アルゴリズムを MATLAB上に実装することによって詳しく検討した。
その結果，検出の基本的な要素は FFT による周波数ごとの時間遷移の差分であることが判明し，検出率などについての基本的なデータを得た．一方，ハードウェア化の障害となっている要因は，FFT の計算複雑さであり，この部分でハードウェア量や処理時間を大きく消費していることが分った．そこで，ハードウェア実装の観点から新しい電子指紋検出の実装法を研究し、実装時に問題となる回路量，クリティカルパス長など，ハードウェア実装における観点からアルゴリズムの評価を行った．新しいハードウェア向けアルゴリズムは，ハードウェア化の障害となった
FFT の代りに，Haar 基底の Wavelet 変換を用いるアルゴリズムである．時間シフトや差分の計算方法を変えて，提案アルゴリズムの検出精度を確認した． 128Mbps での WMA 及びmp3 による圧縮，また 22.05KHz でのサンプリ
ングレート変換を施した 10 曲の音楽について実験を行ったところ，ハードウェア実装された既存アルゴリズムが 315 ミリ秒要していた処理を，ソフトウェア実装の提案アルゴリ
ズムは 128 ミリ秒で処理可能なことが分った．
また，回路規模から試算したところ，ハードウェア実装された提案手法は，0.623 ミリ秒の処理時間が推測された．更に検出精度について正規分布に従うと仮定した場合，提案アルゴリズムの誤検出率は 10-30 となることが分った．
2009 年度は，楽曲から高速に FPID を生成するために，ハードウェアで FPID 生成を行う HiFP を提案し，HiFP のハードウェア実装性を評価した．既存のシステムは FPID生成に高速フーリエ変換を用いたが，今年度研究した HiFP ではハードウェア実装に適した高速な FPID 生成を行うために離散ウェーブレット変換のサブバンド分解を用いる．また，従来用いられてきたオーバーラップを用いないことで，精度を向上させている点が新しい．FPGA による評価の結果，HiFP は既存のシステムと比較してスループットを 25 倍向上させ，使用リソース数も削減可能であることが分かった．

2010 年度は，電子指紋検出アルゴリズムの計算量，回路量，被検出楽曲に対する耐改変性などについて，既存アルゴリズムをプログラムとして実装することによって詳しく検討した．前年度に引き続いて，ハードウェア実装向きの電子指紋検出アルゴリズムの改良を行った．今年度新たに提案したアルゴリ
ズムは，1/4 サンプルづつ間引きした上でHaar Waveet 変換 (HWT)を行うものであり，ハードウェア実装の障害となる浮動小数点演算や乗算を用いないながらも，高い検出精度と実行速度を有するアルゴリズムである．
提案アルゴリズムの実行時間をソフトウェ
アにて検証したところ，昨年のアルゴリズムの実行時間とスループットがそれぞれ 274m秒，7.63Gbps であった所，新アルゴリズムは95μ秒， 21.86Gbps が期待できることが分かった．従来の FFT ベースの Haitsma らのアルゴリズムは，同順で 1.7 秒および 0.01Gbpsである．
様々な圧縮率や精度で改変を行った楽曲に対して，検出精度の評価を行ったところ，同じ楽曲なのに別楽曲として誤認識したケースが，Haitsma らのアルゴリズムでは 32 万分の 8，我々の昨年のアルゴリズムは 32 万分の1 出会ったのに対し，新アルゴリズムは 32 万分の 3，一方で実際は違う楽曲なのに同じ楽曲だと誤認識ケースが，同順で 32 万分の 16，36，および新アルゴリズムは 0 であった．新アルゴリズムは，簡単で FPGA への効率良い実装が可能ながら，従来アルゴリズムに比べて，有為に高い検出精度を達成できた．

５．主な発表論文等（研究代表者、研究分担者及び連携研究者には下線）〔雑誌論文〕（計 5 件）① M.M. Hafizur Rahman, Yukinori Sato andYasushi Inoguchi, "On Nonuniform
Traffic
Patternof
Modified
Hierarchical 3D-Torus Network", IEICE
Transactions on Information andSystems, Vol. E94-D, No. 5, 1109-1112(letter), May, 2011 (査読付)② M.M. Hafizur Rahman, Yasushi Inoguchi,Faiz Al Faisal and Monz Kumar Kundu,"Symmetric and Folded Tori Connected
Torus Network", Journal of Networks,
Academy Publisher, Vol. 6, No. 1,
pp.26-35, Jan., 2011 (査読付)③ M.M. Hafizur Rahman, Yasushi Inoguchi,
Yukinori Sato, Yasuyuki Miura andSusumu
Horiguchi,"DynamicCommunication Performance of a TESH
network under the Nonuniform Traffic
Patterns.", Journal of Networks,
Academy Publisher, Vol. 4, No. 10,
pp.941-951, Dec., 2009 (査読付)④ 荒木 光一，佐藤 幸紀, 井口 寧, "動的リコンフィギャラブルプロセッサにおける並列タスクの データ転送を隠蔽するための効果的な処理法", 信学論 D,
Vol. J92-D, No. 12, pp.2137-2146, Dec.,
2009 (査読付)⑤ M.M. Hafizur Rahman, Yasushi Inoguchi,
Yukinori Sato and Susumu Horiguchi,"TTN: A High Performance HierarchicalInterconnection Network for Massively
ParallelComputers",
IEICE
Transactions on Information andSystems,Vol.
E92-D,
No.
5,pp.1062-1078, May., 2009 (査読付)〔学会発表〕（計 11 件）
① Koichi Araki, Yukinori Sato, Vijay
JainandYasushi
Inoguchi,"Performance Evaluation of Audio
Fingerprint Generation using Haar
Wavelet Transform", Proceedings ofthe 2011 International Workshop onNonlinear Circuits, Communications
and Signal Processing (NCSP11),
pp.380-383, Tianjin SaiXiang Hotel,Tianjin, China, Mar. 3, 2011 (査読付)② M.M. Hafizur Rahman, Yukinori Sato,
Yasuyuki Miura and Yasushi Inoguchi,"Dynamic Communication Performance of
Hierarchical
3D-Torus
Network",
IASTED,
In
10thInternational
Conference Parallel and Distributed
Computing and Networks (PDCN 2011),
pp.9-16, Innsbruck, Austria, Feb.
15-17, 2011 (査読付)③ M.M. Hafizur Rahman, Yukinori Sato andYasushi Inoguchi, "High Performance
Hierarchical Torus Network Under
Adverse Traffic Patterns", In 13th
International Conference on Computerand Information Technology (ICCIT2010), 6 pages, Ahsanullah Universityof Science and Technology, Dhaka,Bangladesh, Dec. 23-25, 2010 (査読付)④ M.M. Hafizur Rahman, Yukinori Sato andYasushi
Inoguchi,"DynamicCommunication
Performance
Enhancement in Hierarchical Torus
Network by Selection Algorithm", In
13th International Conference onComputer and Information Technology(ICCIT 2010), 6 pages, Ahsanullah
University of Science and Technology,Dhaka, Bangladesh, Dec. 23-25, 2010(査読付)⑤ Tan Yiyu, Yasushi Inoguchi, EikoSugawara, Yukinori Sato, Makoto Ohya,Yukio Iwaya, Hiroshi Matsuoka andTakaoTsuchiya,"AFPGA
Implementation of the Two-Dimensional
Digital Huygens' Model", TechnicalCo-sponsord by IEEE, The 2010
International
Conferenceon
Field-Programmable
Technology(FPT'10),
pp.304-307,
Tsinghua
University, Beijing, China, Dec. 8-10,
2010 (査読付)⑥ M.M. Hafizur Rahman, Yasushi Inoguchi
andYukinori
Sato,"Dynamic⑦⑧⑨⑩⑪

Communication Performance of a
Modified
Hierarchical
3D-Torus
Network under Non-uniform Traffic
Patterns", In 2nd Workshop on Ultra
PerformanceandDependable
Acceleration Systems (UPDAS) held inconjection
withTheFirstInternational
Conference
onNetworking and Computing (ICNC),
pp.167-172, Hiroshima, Japan, Nov. 19,
2010 (査読付)荒木 光一, 佐藤 幸紀, V.K. Jain, 井口 寧, "ハードウェアにおける高速なオーディオフィンガープリント 生成シス
テムの性能評価", 先進的計算基盤シス
テムシンポジウム SACSIS, pp.295-302,
奈良県, Jun. 27-28, 2010 (査読付)
M.M. Hafizur Rahman, Yasushi Inoguchi,
Yukinori Sato, Yasuyuki Miura andSusumuHoriguchi,"Dynamiccommunication performance of a TESH
network under the nonuniform trafficpatterns", In 11th International
ConferenceonComputerandInformation Technology (ICCIT 2008),
pp.365-370, Khulna, Bangladesh, Dec.
12, 2008 (査読付)
M.M. Hafizur Rahman, Yasushi Inoguchi,
Yukinori Sato, Yasuyuki Miura andSusumu Horiguchi, "On hot-spot
traffic pattern of TESH network", In
11th International Conference on
Computer and Information Technology(ICCIT 2008), pp.359-364, Khulna,Bangladesh, Dec. 12, 2008 (査読付)荒木 光一, 佐藤 幸紀, 井口 寧, "マル
チコンテキスト型リコンフィギャラブ
ルプロセッサに おけるデータ並列タス
クの処理法", 信学技法 RECONF2008-41,
Vol. 108, No. 300, pp.15-20, 北九州市, Nov. 20, 2008 (査読無)荒木 光一, 佐藤 幸紀, 井口 寧, "動的再構成デバイスにおけるデータ I/O と処理のオーバーラップを 用いた処理法",
先進的計算基盤システムシンポジウム
SACSIS, pp.55-56, 茨城県, Jun. 11-12,
2008 (査読付)〔図書〕（計 0 件）
〔産業財産権〕○出願状況（計 0 件）
名称：
発明者：
権利者：
種類：
番号：

出願年月日：
国内外の別：○取得状況（計 0 件）
名称：
発明者：
権利者：
種類：
番号：
取得年月日：
国内外の別：〔その他〕
ホームページ等

６．研究組織(1)研究代表者
井口 寧（INOGUCHI YASUSHI）
北陸先端科学技術大学院大学・情報社会基盤研究センター・准教授
研究者番号：90293406(2)研究分担者
佐藤 幸紀（YUKINORI SATO）
北陸先端科学技術大学院大学・情報科学センター・助教
研究者番号：30452113(3)連携研究者
福士 将（FUKUSHI MASARU）
東北大学・情報科学研究科・助教
研究者番号：50345659