画像検索を用いたディジタルアーカイブのインデクシング

05-01045
画像検索を用いたディジタルアーカイブのインデクシング
川 嶋 稔 夫
公立はこだて未来大学教授
1 はじめに
貴重な文化財や歴史的文書などをディジタルアーカイブとして蓄積保存する取り組みが盛んである．しか
しディジタルアーカイブは単なる保存技術にとどまるものでなく，広く世界に公開して一般の活用を促すこ
とによってこそ知財としての有効利用が活性化され，その進化が発揮されるものである．このことは学術的
文化的観点からのみならず経済的観点からも極めて有益なものであり，従ってこれを研究開発することは電
気通信技術による社会貢献という観点からも意義深いものであると言える．
このようにディジタルアーカイブの知財としての有効活用を考える場合，ディジタル化して保存された文
書画像への文字認識，文字検索，解読支援，頻出語抽出などを行う手段を提供することが非常に重要となる．
こうした手段の一方法として文字認識手法（OCR）により文書画像をテキスト形式に変換して取り扱うことが
考えられるが，古文書画像を対象とする場合，文字認識は通常の硬筆文字に対する場合と比べて格段に難し
い．そのため，それより近い到達目標として，文字認識によらずに類似文字画像を探すこと，すなわちワー
ドスポッティングを行う研究が近年行われている．文字列検索が可能になることにより，文書画像中から特
定のキーワードを含む部分を抽出することができるほか，インデックス作成の作業支援や，あるいは翻刻者
が解読できない文字列に遭遇した際にそれと同一の文字列が現れる別の文脈を提示することによる解読支援
なども可能となる．
以前より我々は，文字列画像をスリット状に切り出して各スリット画像に対して特徴量を記述することで，
文字切出しが困難な文書に対してもワードスポッティングを可能とする方法の開発に取り組んできた．この
方法は完全にデータ主導の方法であるため，特定の言語に依存せず，あらゆる言語に対して適用することが
可能であるという特長を持っている．本論文ではこれまでの研究の結果得られた成果の中から，スライディ
ングウインドウによって画像を切り出す方法と，切り出した画像から検索に適した特徴量を記述する方法に
ついて述べる．今回特徴量として採用した「勾配分布特徴量（GDF 特徴量）」は，従来の特徴量が画像の画素
値に基づいて特徴記述を行っていたのに対し，画素値の勾配に基づいて特徴を記述することで，文字のスト
ローク方向を取り込むことが可能であるという利点を持っている．
また，分布の集約方法を工夫することで，
位置ずれに対する頑健性も獲得している．このようにして勾配分布に基づいて特徴記述をする方法は，画像
検索や物体抽出の分野で用いられている方法（Lowe1999,Lowe2004）にインスパイアされたものであり，本論
文の提案手法はそれらを文字検索に適用可能なように拡張したものとなっている．
1-1 関連研究
本論文で扱うような文字認識によらない文字列検索の研究としては，英語の手書き文書を対象に頻出する
単語を抽出した Manmatha らの研究（Manmatha1996）があり，“ワードスポッティング”（word spotting）と
名づけられている．Rath and Manmatha は，ワードスポッティングに適した 4 つの特徴量を提案し
（Rath2003ICDAR），またこれに DTW（dynamic time warping）を適用することにより精度の向上を図ってい
る（Rath2003CVPR）．また，Marinai らは主に活字で印刷された古文書を対象に，自己組織化マップを用いて
連結成分を符号化し，符号列エディット距離を用いて単語間の対応を定める方法を提唱している
（Marinai2003）．これらの研究はいずれも英語の文書を対象としているため，単語単位の切出しが比較的容
易に行われることを前提に，単語間の対応付けを行っている．
一方で，日本語や中国語のような言語では単語単位に切り出すことが難しい．こうした言語を対象とした
研究としては Yue Lu and Chew Lim Tan が中国語の新聞記事を対象とした文字列検索の手法を提案している
ものがある（Lu2002）が，これは活字で印刷されたものを対象としており，文字単位に切出しを行うことが
前提となっている．崩し字やつづけ字などにより文字切出しが困難な文書に対する文字切出しを前提としな
い研究としては，探索範囲を単一文字に限定せずに切り出すこととした近藤らの研究があり（近藤ら 2003）
，
ここでは文字幅に着目して探索範囲を切り出し，切り出した範囲と正規化した文字パターンとの間でテンプ
486
レートマッチングを行うという方法がとられている．
2 スリット切出しによるワードスポッティング
この章では，文書画像をスリット状に切り出すことによって，ある文字列画像からそれに類似した文字列
画像を検索する方法の手順について述べる．
2-1 前処理
はじめに，入力画像に対して前処理を施す．前処理は，「しきい値処理により，背景を消去」
「文字行の切
出し」
「文字行の中心位置の正規化」の 3 段階で行う．
しきい値処理は，画素値が一定のしきい値以下の（すなわち黒に近い）ピクセルのみを有効成分として抽
出し，それ以外の部分は背景とみなすという形で行う．この処理で得られる画像は単純な二値化画像とは異
なって文字部分の画素の濃淡情報はそのまま残されており，この後の解析もすべてグレースケールの領域で
行う．このような方法を採用したのは，毛筆文書画像においてはペン字画像と異なり，画素値の濃淡に文字
識別のために有益な情報が含まれている可能性があるためである．
次に，文字行の切出しを行う．文字行とは文字が読み書きされる方向，すなわち縦書きの文書であれば垂
直方向，横書きの文書であれば水平方向に連続する文字列の改行までの 1 単位である．本手法は縦書き横書
きいずれの文書に対しても適用可能であるが，以下では縦書きの文書を前提に説明する．すなわち，垂直方
向を文字行方向とする．なお横書きの文書を取り扱う場合ははじめに x,y 座標を入れ替えればよい．日本語
の文書は英語の文書と異なり単語の切出しが容易でないことはすでに述べたが，文字行に切り出すことは比
較的容易である．文字行方向の黒画素値の射影ヒストグラム H(x) を作成し， H(x) が極小となる x 座標を
文字行と文字行との境界位置と定めることにより，文書画像を文字行単位に切り出すことができる．なお，
このようにして切り出された文字行は幅が一定しないため，幅が狭い画像について左右に余白を追加するこ
とで，文字行の幅を一定にそろえておく．
最後に，切り出された各文字行について中心位置の正規化（センタリング処理）を行う．罫線のない紙に
書かれた文書は文字位置が左右に揺れる場合がしばしば見られる．この影響を除くため，移動平均法によっ
て文字行の中心位置を推定し，これを中心にそろえる．ここで移動平均を取る範囲 n は大きすぎると補正に
よる効果が小さくなる一方で，小さすぎると文字形状自体を崩してしまう過補正が発生するため，文書画像
の性質に応じて個別に定める必要がある．予備実験を行った結果，今回対象とする文書画像については， n を
1 文字程度の長さに設定すると良好な結果が得られたため，以下の実験でもこの値を採用する．
ここまでの処理結果を図 1(a)～(d)に示した．
2-2 平滑化及びスリット切出し
前処理済みの画像に対し，ノイズに対する頑健性を付与するためにガウシアンフィルタによる平滑化を行
った後，これをスリット状に切り出す（図 1(e)及び(f)）
．このようにして画像を切り出すことにより，文字
列画像をスリット画像のシーケンス（画像列）としてとらえることができるようになる．ここでガウシアン
フィルタによる平滑化を行う際のパラメータ σ の値及びスリット状に切り出す際の切り出し幅については
実験により最適な値を求めた．実験の詳細については割愛するが，結果としては（文字行幅≒文字解像度が
487
80 ピクセル程度の場合） σ=3.0～4.0 ，切り出し幅＝8 ピクセル程度とした場合に良好な結果を示した．以
下での実験はこれらのパラメータを採用する．
2-3 特徴量ベクトルの記述－勾配分布特徴量
切り出した画像列に対し，各スリット画像を低次元の特徴量ベクトルで記述することを考える．著者らの
以前の研究では主成分分析（固有空間法）を用いた特徴量構成法を用いていたが，その後の研究の結果，画
像の勾配分布に基づいた特徴量がより高い記述性能を示したため，ここではそちらを紹介する．
画像のある領域を記述するための特徴量として画素値の勾配ベクトルの分布を用いるという方法は，Lowe
による SIFT（Scale-Invariant Feature Transform）でよく知られている（Lowe1999,Lowe2004）．SIFT アル
ゴリズムは局所的特徴量に基づいて画像検索を行うものであり，類似のアルゴリズムと比べて最も安定した
結果を出力すると Mikolajczyk and Schmid により報告されている（Mikolajczyk2003）．局所特徴量に基づく
画像検索は一般的に，画像から特徴点を抽出し，次いで特徴点近傍を特徴量ベクトルで記述するというプロ
セスを踏む．SIFT アルゴリズムもその例に違わず，
(1) DoG を用いて画像中から特徴点（keypoint）を探す．
(2) 特徴点の位置を正確に定める．
(3) 特徴点近傍領域の主方向を推定し，正規化する．
(4) 正規化された近傍領域を特徴量ベクトル（descriptor）で記述する．
という 4 段階の手続きから構成されている．ただしこのうち，(1)～(3)の段階については本研究のような目
的にはなじまない．なぜなら，文字検索の課題において文字の大きさや方向を推定しようとする場合，文書
内においてこれらがばらばらに変動することは考えづらいため，SIFT のような局所的性質に基づく方法で推
定するよりも，むしろ大局的な方法を用いて推定したほうが良好な結果が得られると考えられるからである．
したがってここでは(4)の特徴点近傍領域の記述に関する部分についてのみ述べる．
(1)～(3)の手続きにより，すでに位置・大きさ・方向について正規化がなされた近傍領域（正規化領域）
というものが得られている．またすでに適切なガウシアンフィルタによって平滑化がなされている．SIFT ア
ルゴリズムは，この正規化領域を 4×4 の部分領域に分割して，各領域内で画素値の勾配ベクトルを方向別に
（8 方向に）集約することにより 128 次元特徴量を構成するものである．具体的な計算方法を図 2 に示した．
構成される特徴ベクトル f(xi,yj,θk) は， i, j がそれぞれ 4 通り， k が 8 通りなので，合計 4×4×8 = 128
次元となる．なお図では説明を簡単にするため x,y,θについて Nearest Neighbor 法で区分するように書い
た が ， 実 際 に は 線 形 補 間 （ tri-linear
interpolation）で重みをつけながら計算する．ま
た，極端な値の影響を抑制するためにベクトルの
各成分の上限を 0.2 に制限するなどの工夫も行わ
れるが，詳細は割愛する．このようにして構成さ
れた 128 次元特徴ベクトル f を用い，ベクトル間
のユークリッド距離により近傍領域の類似性を判
488
定するというのが SIFT アルゴリズムの概要である．
さてこの SIFT アルゴリズムを文字列画像の特徴記述に導入するにはどうすればよいだろうか．すでに述べ
たように，SIFT アルゴリズムの特徴点抽出法や近傍領域正規化法(1)～(3)は文字検索にはなじまない．そこ
でまず，前章で述べた方法によって文字列画像をスリット状に切り出すこととする．したがって，正規化領
域もオリジナルの SIFT のような正方形状ではなくスリット状の細長い長方形となる．また，領域区分も SIFT
のように 4 × 4 の正方領域に区切るのではなく，スリット状の長方形を横方向のみに n 分割することとし
た．そして，この領域分割に従って，SIFT と同様に画素値の勾配ベクトルを求め，その勾配ベクトルを方向
別に集約し， n×8 次元ベクトルを構成する．なお，集約の際には横方向および角度方向，すなわち特徴量
f(xi, yj, θk) の i および k に関しては線形補間で重み付けをした．縦方向に関しては分割を行わないた
め，補間を行わなかった．もっともこの段階では分割しないとはいえ，そもそもスリット画像自体が原画像
を分割することにより得られたものであるため，原理的には縦方向にも補間による重み付けを行うことは可
能である．しかし今回は簡単のためこれを省略し，縦方向については補間を行わないこととした．このよう
に構成された n × 8 次元ベクトルに対し，最後にこれを単位ベクトルに正規化する処理を行って，特徴量
とする．本論文ではこの特徴量を勾配分布特徴量（GDF 特徴量）と呼び，これを用いた検索法を勾配分布法
（GDF 法）と呼ぶことにする．図 3 に勾配分布特徴量構成法の概念図を示した．
2-4 ベクトル列を用いたパターンマッチングの方法
前節により，文字列画像を特徴量ベクトルの系列に変換する手法が得られた．この節では，これを用いて
文書画像中からクエリー部分と類似度の高い部分を検出する方法について述べる．
スリット画像列の特徴量ベクトルの系列を y(t)（t はスリット番号）とし，クエリー画像は a1≦t≦a1+τ
の範囲に含まれているものとする．このとき，クエリー画像列 A ={y(t) | a1 ≦ t ≦ a1+τ}と，b1 を起点
とする同じ長さの画像列 B ={y(t) | b1 ≦ t ≦ b1+τ}との間のマッチングコストを D(A,B)=Σ 0≦t≦τ
d(y(a1+t) ,y(b1+t) ) で定め，小さい D(A,B)を与える B をクエリー画像と類似度の高い画像と定義する．
ここで d(y(a1+t) ,y(b1+t) ) は各スリットにおける特徴量ベクトル間の距離を表し，本研究では最も一般的
な L2-ノルム（ユークリッド距離）d(y(a1+t) ,y(b1+t) )= (Σi |yi (a1+t) - yi (b1+t)|2 )1/2（yi はベクトル
y の第 i 成分を表すものとする）を採用することとした．B の始点 b1 を変化させながら D(A,B)を計算し，最
も類似度の高い画像を第 1 位検出画像，以下第 2 位検出画像，第 3 位検出画像，……として出力することと
する．
これにより，文書画像から，クエリーとする部分と類似度の高い部分を検出する方法が得られた．
2-5 Dynamic Time Warping
前節までで文字画像列から類似画像を検出する方法が得られ
たが，ここでは更にそれを拡張し，文字列の縦方向の伸縮変形
に対応するために DTW（dynamic time warping）を導入するこ
とを考える．DTW は主に音声認識の分野で発達した手法で，2
つの時系列信号が入力されたときに，それぞれの時間軸を非線
形に変形させながら最も良い対応が取れる時間対応を探し，そ
の時間対応の下での類似度を出力するものである．本研究で取
り扱う文書画像検索においても，文字行方向の軸（縦軸）を時
間軸とみなすことによりスリットに分割された文字画像を時系
列信号とみなすことができ，DTW を適用することが可能となる．
図 3 に DTW のイメージ図を示した．図内のグレーで着色され
た部分の中で，左下の原点を起点として，
「右上，上，右」の 3
方向に動ける Path（経路）を考える．あらゆる Path について
前節で定めたマッチングコストを計算し，その中で最小のもの
を出力する．可能な経路数は区間の長さに応じて O(2n) オーダ
ーで増加するが，DTW においては動的計画法で最小値を求める
ことにより，計算量は O(n2) オーダーにおさえられている．詳
細については文献（寺沢ら 2006）などを参考とされたい．
489
3 実験結果
実験素材には「亜国来使記」
（図 3）を用いた．
「亜
国来使記」は安政元年（1854 年）に書かれた松前藩
家老・松前勘解由の日記であり，その全文は 182 ペ
ージ，1553 行，25148 文字からなる．これから，文
中に 25 回以上登場する人名（表 1）を対象に，平均
適合率（average precision）を評価する．各特徴量
に共通の操作として，まず前処理（背景除去，文字
行抽出，中心位置補正）を行った後，ガウス関数で
平滑化し，さらにスリット状に切り出して，文字列
をスリット画像のシーケンスに変換する．次いで各
スリット画像をそれぞれの方法で特徴量ベクトルに
変換し，ベクトル列のマッチング問題に帰着させる．
ベクトル列のマッチング問題を解く際は，非線形伸
縮を許容するため，DTW を用いる．精度評価を行う
ために必要な人名の出現位置の正解データは手作
業で事前に作成しておいたものを用いる．実験対
象としたキーワードの各クエリー画像に対し平均
適合率を算出し，それを更にキーワードごとに平
均値をまとめて評価基準とした．
実験結果を表 2 に示す．なお表中，画素値 PCA
法，こう配 PCA 法，とは，我々が GDF 特徴量を開
発する以前に導入していた特徴量である．この表
から，勾配分布法（GDF 法）は従来法に比べて検
索精度が大きく向上していることが見て取れる．
また，4 種類のキーワードに対する検索結果の
うち，キーワード「又左衛門」に対する再現率－
適合率曲線を示したものが図 5 である．この図か
らも，勾配分布法が他の方法に比べて高い精度を
示していることがわかる．
本手法の出力結果の一例として，クエリー文字
列「吉岡元平」に対する検索結果を図 7 に示した．
「吉岡元平」は全文中に 7 回出現するが，そのすべ
てが上位（1,2,3,4,5,7 位）に検出されていること
が確認できるであろう．
4 おわりに
本論文では毛筆手書き文字を対象に文字検索を行
うための方法を提案した．新たな特徴量として導入
した勾配分布特徴量は線幅の変化や微細な位置ずれ
490
に対して頑健であるなどという特長を持ち，実際の古文書画像を用いた実験においても，従来法に比べて相
当程度の精度の向上が見られることが確認された．
本研究の結果をふまえた今後の予定としては，まず方向線素特徴量や Gabor 特徴量との定量的な精度比較
検証を行ってみたいと考えている．勾配分布特徴量のアイデアは毛筆に限らず硬筆文字に対しても適用可能
であるため，硬筆手書き文字データベースに対してこれを適用し，従来法との精度の比較を行いたい．また
それと同時に，本手法の他言語への適用も予定している．本手法は画像類似度に基づく文字検索であるため，
原理的にはあらゆる言語に対して適用可能である．したがって，これを日本語以外の文献に対しても適用し，
その性能を評価することは有益であろう．また，今回の実験では同一著者の文献内での検索実験のみを行っ
たが，これを筆跡の異なる文献間での検索が可能であるかどうかについても検証したい．それに加えて，前
処理段階の改善でさらなる精度の向上が得られるかどうかについても引き続き検討を行っていく予定である．
【参考文献】
R. Manmatha, C. Han, and E.M. Riseman, ``Word spotting: a new approach to indexing
handwriting,'' Proc. IEEE Conf. on Computer Vision and Pattern Recognition,pp.631--637, 1996.
T.M. Rath and R. Manmatha, ``Features for word spotting in historical manuscripts,'' Proc. Int.
Conf. on Document Analysis and Recognition, pp.218--222, 2003.
T.M. Rath and R. Manmatha, ``Word image matching using dynamic time warping,'' Proc. IEEE
Conf. on Computer Vision and Pattern Recognition, pp.521--527, 2003.
S. Marinai, E. Marino, and G. Soda, ``Indexing and retrieval of words in old documents'', Proc. Int.
Conf. on Document Analysis and Recognition, pp.223--227, 2003.
Yue Lu and Chew Lim Tan, ``Word spotting in Chinese document images without layout analysis,''
Proc. IEEE Int. Conf. on Pattern Recognition, pp.30057--30060, 2002.
近藤博人，松本隆一，柴山守，山田奨治，荒木義彦，“文字切出しを前提としない古文書標題認識”,情報処理
学会研究報告，no.2003-CH-57，2003.
D.G. Lowe, ``Object recognition from local scale-invariant features,'' Proc. 7th Int. Conf. on
Computer Vision, ICCV'99, vol.2, pp.1150--1157, 1999.
D.G. Lowe, ``Distinctive image features from scale-invariant keypoints,'' Int. Journal of Computer
Vision, vol.60, no.2, pp.91--110, 2004.
寺沢憲吾，長崎健，川嶋稔夫，“固有空間法と DTW による古文書ワードスポッティング”,電子情報通信学会論
文誌，vol.J89-D, no.8, pp.1829-1839, 2006.
寺沢憲吾，長崎健，川嶋稔夫，“勾配分布特徴量による高精度手書き文字検索”，画像の認識・理解シンポジウ
ム(MIRU)2006 講演論文集，pp.1325-1330, 2006.
〈発
題
名
固有空間法と DTW による古文書ワードス
ポッティング
勾配分布特徴量による高精度手書き文字
検索
表
資
料〉
掲載誌・学会名等
電子情報通信学会論文誌Ｄ
画像の認識・理解シンポジウム
(MIRU)2006
491
発表年月
2006 年 8 月
2006 年 7 月