勾配方向分布とマニューシャマッチングを用いた指紋照合

(1)

2010 年度修士論文

勾配方向分布とマニューシャマッチングを用いた指紋照合

Fingerprint Verification Using Gradient Distribution and Minutiae Matching

2011 年 1 月 28 日提出

指導教官若原徹教授

法政大学大学院情報科学研究科情報科学専攻

学籍番号 09T0011 坪井

^{ツボイ}

祐

^ユウ

輔

^スケ

(2)

ii

Abstract

High-accuracy fingerprint matching from poor-quality fingerprint images is important and the most challenging problem. This paper describes a new poor-quality fingerprint verification technique combining pattern matching and minutiae matching composed of the following four parts.

The first part is local FFT band-pass that passes only the dominant frequencies’ components representing the periodicity of ridge patterns and in each local area and raises the norms of all frequencies’ components to the power of a specified number. The second step is generation of a mask image that extracts fingerprint region by segmenting background region and part below the second joint of finger. The third step is pattern matching that is optimal block-wise shift using gradient distribution of input and enrolled fingerprints for absorbing rotation and translation. Finally， the fourth step is minutiae matching that are extraction of endpoints and bifurcations of fingerprint ridges called minutiae and one-to-one correspondence determination between input and enrolled minutiae. Experimental results using the public FVC2004 fingerprint image database demonstrate a fairly low equal error rate (EER) of 12.91% for false rejection and false acceptance as compared to those obtained by academic groups that participated in the FVC2004.

概要

低品質の劣化指紋画像から高精度な指紋照合は重要で最も挑戦的な課題となっている。

本論文では，以下の 4 つのステップで構成されたパターンマッチングとマニューシャマッチングを融合した劣化指紋画像に対する新しい指紋照合手法を提案する。第1ステップは，

局所領域ごとに指紋隆線方向の局所的周期性を表す周波数成分だけを通過させ，周波数成分をノルムの累乗で増幅する局所的FFTバンドパスフィルタを適用する。第2ステップは，

背景領域と指の第二関節部分から指紋領域を抽出する指紋マスク画像を生成する。第 3 ステップは，回転と平行移動成分を吸収するために，入力と登録指紋の勾配方向分布を使用する最適なブロック単位の位置ずらしを用いたパターンマッチングを行う。最終第 4 ステップは，指紋隆線の端点と分岐点であるマニューシャを抽出し，入力と登録マニューシャ間で1対1対応付けるマニューシャマッチングを行う。FVC2004公開指紋画像データベースを用いた評価実験より，FVC2004 に参加したアカデミックグループの結果と比べて，本人拒否率(FRR)と他人受理率(FAR)が等しくなるEERの値として，12.91%を達成することを示した。

(3)

iii

第 1 章序論

1.1 研究の背景および目的

近年，ネットワークを介しての商取引やサービスの利用により，ユーザーのセキュリティに対する認識が深まっており，情報の漏洩や不正アクセスへの対策として，バイオメトリクスを用いた個人認証が社会に浸透している。

バイオメトリクス認証を用いると，本人であることを証明するための物を携帯する必要がなくなる。また，パスワードや暗証番号を記憶する必要がなくなることなどの利点を得ることができる。さらに，本人だけしか持ち得ない情報をパスワードや鍵の代わりに使用することができるため，それらの盗難や偽造が困難である。そして，自身の一部を用いているため，紛失という概念が不要になり，管理の面でも負担が軽減されることなどの利点もある。例を挙げれば，銀行のATMなどで採用されている手指静脈認証がある。パスワードと違い，忘れることもなければ，盗まれることもない。

また，会社や家のドアにバイオメトリクス認証装置が設置されていると，鍵を持ち歩くことなく開錠・施錠することができ，部外者が建物や部屋へ不正に侵入することを防ぐことができる。

認証に使われる生体的特徴としては，指紋，顔，DNA，耳形状，顔や手の体温，歩き方，

掌形，手の甲の静脈，虹彩，キーストローク，臭気，網膜，署名，声紋などが代表的なものとして挙げられる。

図1.1にInternational Biometric Groupの調査による身体特徴別のバイオメトリクスマーケットシェア[1]を示す。

(6)

このしてい市場に Syste り，性

従来マッチマッチ当研て有効一方乾燥て照合抽出

本論ング法紋隆線景領域た回転登録指

のようなバイいるバイオメに出回ってお em)/Live-Scan

性能向上への来の代表的なチング法と，

チング法があ研究室では，

効性を報告し方，多くの実によるかすれ合精度に大きと照合処理が論文では，劣法を融合した線の周期性に域の分離によ転成分の吸収指紋マニュー

図1.1 身体

Cop

イオメトリクメトリクスでおり，図1.1か n(38.3%)と合の期待も大きな指紋照合法

，指紋を画像ある[4]。

，パターンマした[5]が，処実用化装置でれ，しわ，手きく影響するが，照合精度劣化指紋画像た照合手法をに着目して局よる指紋マス収と，勾配方ーシャ間での

体特徴別のバ Biometric Re pyright @ 200

クス認証の中である。指紋からFingerpr 合わせて66.7 きい[2], [3]。

法は，指紋隆像として取り

マッチング法処理量が多いで採用されて手荒れなどにる。そのため度の向上には

像を対象としを提案する。

局所的FFTバスク画像の生方向分布を用の1対1対応

2 バイオメトリ

evenues by Te 08 Internation

中でも，万人紋認証装置を rint(28.4%)と 7%を占めて

隆線の端点とり込み，画像

法の一つとしいという難点ているマニュによって劣化め，こうしたは必須となる

して，パター全体の処理バンドパスフ生成，(3)入力用いたブロッ

応付けによる

リクスマーケ echnology, 20 nal Biometric

人不同で終生を搭載したノとAFIS(Autom ている。さらな

と分岐点を捉像同士を重ね

して，摂動法点があった。

ューシャマッ化しているとた劣化画像のる。

ーンマッチン理は大きく 4

フィルタを用力－登録指紋ック単位のずるマニューシ

ケットシェア 009

c Group

生不変であるノートパソコ mated Finger なる市場拡大

捉えて判別すね合わせて照

法による指紋

ッチング法でと，偽マニュの修復，安定

ング法とマニ 4 つの部分で用いた劣化画紋間での複数ずらしマッチシャマッチン

ア：

る指紋は最もコンや携帯電 rprint Identifi 大も予想され

するマニュー照合するパタ

紋照合法を提

では，指紋画ューシャが発定なマニュー

ニューシャマで構成され，

画像の修復，

数回転画像をチング，(4) 入ング，となる

も普及電話も ication れてお

ーシャターン

提案し

画像が発生しーシャ

マッチ (1)指 (2)背を用い入力－

。

(7)

3

提案手法を，FVC2004で使用されて後に公開された指紋画像データベースDB1に適用して評価実験を行った。その結果，本人拒否率(False Rejection Rate; FRR)と他人受理率(False Acceptance Rate; FAR)が等しくなる値EER (Equal Error Rate)として，ブロック単位の位置ずらしによる前段のパターンマッチングの段階で 13.64%，後段のマニューシャマッチングと結合した最終段階で12.91%，を達成できることを示した。

1.2 論文の構成

本章では序論として，本研究がどのような背景および目的のもとに行われるか，提案手法の概要と結果について述べた。第2章では，本研究に用いたFVC2004指紋画像データベースについて紹介する。続いて，第3章では局所的FFTバンドパスフィルタ，第4章では指紋マスク領域の抽出，第 5章では位置ずらしマッチング，第 6 章ではマニューシャマッチング，の本研究における提案手法の各処理について述べる。そして，第 7 章では実験結果を示し，第8 章では実験結果に対しての考察を述べる。最後に，第 9章において結論を述べる。

(8)

第

本研ベース紹介す

2.1

本研コンペはDB を用い式スイされた

2 章

研究の提案手スFVC2004 する。

FVC2

研究で使用ペティション

B1からDB

いて収集されイープセンサたものである

(c) DB

FVC2

手法の有効性指紋データ

2004 指紋

した指紋デー

ン FVC2004

B4までの4つ

れたものであサ“FingerCh る。図2.1に

図2.1 FVC (a) DB1 3（感熱式ス

2004 指

性を確認するベースであ

紋データ

ータベースは 4 で使用されつのセクショある。同様に

hip FCD4B1 にそれぞれの

(a)

(c) C2004指紋デ

（光学式センスイープセン

4

指紋デー

る評価実験でる。本章で

ベースの

は，世界中のれ，後で公開ョンで構成さにDB2は光学

14CB”，DB

のセクション

データベースンサ） (b) D ンサ） (d) D

ータベー

で使用した指は，この指紋

の概略

の大学や企業開されたものされている。

学式センサ“

B4は指紋合成ンの指紋画像

スの指紋画像 DB2（光学式 DB4（指紋合

ース

指紋画像は，

紋画像データ

業が参加したのである[6]。

DB1は光学

“U.are.U 400 成ジェネレー像データを示

(b)

(d)

像データ例：

式センサ）

合成ジェネレ

公開指紋デタベースにつ

た世界的指紋本データベ学式センサ“V

00”，DB3は

ータを用いて示す。

レータ）

データついて

紋照合ベース V300”

は感熱て収集

(9)

5

それぞれのセクションには100人×1本×8種類，すなわち全部で800枚の指紋画像データが収録されている。また，全ての指紋画像データは階調値[0,255]，すなわち8ビットの濃淡画像として用意されており，各セクションによって画像サイズや解像度が異なる。これらの情報をまとめたものを表2.1に示す。

表2.1 FVC2004指紋データベースの各セクションの属性

DB センサの種類サイズ（横×縦）収録数（指×枚）解像度 DB1 光学式センサ 640×480 100×8 500dpi DB2 光学式センサ 328×364 100×8 500dpi DB3 感熱式スイープセンサ 300×480 100×8 512dpi DB4 指紋合成ジェネレータ 288×384 100×8 およそ500dpi

2.2 DB1 に収録されている指紋

今回の実験ではDB1に収録されている指紋画像を利用した。前節に記述したとおり，DB1 に収録されている指紋データは光学式センサ“V300”を用いて収集されたものであり，図2.2 に示すとおり収集状態も画像によりさまざまである。

例えば，(a)の示すような画像はとてもきれいに採取されているが，(b)は指紋領域が画像領域全体に対して少ない。他にも，(c)のように全体的に指紋がかすれていたり，(d)は潰れによって劣化したりしている。さらに，(e)は指の第二関節まで含まれている。そのため，

指紋照合をするにあたり不利になる要素も含まれている指紋画像データをどのように処理するかが重要な要素となってくる。

本研究では，第3章で述べるFFTを適用する際に画像サイズを2の累乗とする必要がある。このため，まず左右の背景部分を除いた480×480としてから，双一次線形補間法を用

いて256×256の画像サイズに変換して使用した。

(10)

(

図2.2 F a)

VC2004指紋 (a) 7_

(d)

紋データベー _6 (b) 10_2

6 (b)

ースDB1に収 (c) 11_7

(e) 収録されてい

(d) 14_8 (e

(c

いる指紋画像 e) 99_1

c)

像データ：

(11)

7

第 3 章局所的 FFT バンドパスフィルタ

指紋画像に潰れやかすれがあり，画像が劣化していると，マニューシャ抽出が困難となり，マニューシャマッチングの精度も著しく低下する。このため，指紋隆線を修復するためのフィルタリング処理を施す。

指紋画像を観察して主に指紋隆線の方向や周期性に着目すると，《指紋隆線方向の局所安定》と《指紋隆線の周期性》という性質を指摘することができる。本節では，《指紋隆線方向の局所安定》という性質を利用して，指紋画像を局所領域にブロック分割し，各ブロック領域にバンドパスによるパワー強調処理を施す。本処理により，局所領域では指紋隆線の方向・間隔がほぼ一定であるため，FFTパワースペクトラムにおいて特定の方向・周波数に鋭いピークが現れる，という利点が予想される。これらの利点は，いずれも信号とノイズの判別がより容易になり，画像修復に大きな成果を与える。また，本処理によりブロック境界で画像が不連続となることを防ぐため，パワーフィルタを施すブロックを互いに重なるようにして複数領域で行い，それらを重み付け加算し，滑らかな修復画像の作成を行う。

以下に処理の具体的な手順を示す。

1. 指紋画像全体をサイズM×Mの小領域単位にブロック分割する。ここで，サイズM は画像サイズN（= 256）より小さく，2のべき乗の値を取る。例えば，M = 16, 32, 64 となる。M = 16の場合，画像全体は256ブロックに分割される。さらに各ブロック位置でステップ幅をM / 4として上下左右の位置ずらしを行う。それら全ての位置でブロック単位にFFTを施し，フーリエ変換成分F(ω₁, ω₂)を求める。

2. 直流成分を含む低周波数領域をそのまま通過させるための上限周波数 R₀を次式で定める。ここでは，画像サイズNを定数16で割った値を用いる。

/16 (1)

3. フーリエ変換成分 F(ω₁, ω₂)を次式に従い，各成分のノルムの累乗を用いて成分の大 きさを増幅する。

, , | , |^γ (2)

ここで，累乗の指数バラメータγの値として，γ = 3.0を用いた。

4. 逆フーリエ変換IFFTを行い，ブロック毎に修復された指紋画像を得る。

5. ブロック毎に得られた修復画像に対して，そのブロックと部分的に重なる全てのブロックでの修復画像をガウス型の重み付けにより加算し，最終的な修復画像を作成する。この処理をM = 16，32の2種類のブロックサイズで行い，それらの平均画像を出力する。

(12)

式(

に強い図図とがわ

(2)から明らかい，周波数成 3.1に，提案 3.1より，かわかる。

かなように，

成分が強調さ案手法によるかすれや潰れ

図

F(ω₁, ω₂) される効果をる画像修復のれが修復され

(a)

図3.1 提案手上段：かす

(a)原画像

8 のノルムが大を持っているの例を示す。

れ，指紋隆線

手法による画すれ画像下

像 (b)指紋隆

大きいほど増る。

が強調された

(b) 画像修復の例下段：潰れ画像

隆線修復画像

増幅されるの

た指紋画像が

例：

像像

ので，局所領

が得られてい領域毎

いるこ

(13)

9

第 4 章指紋マスク領域の抽出

指紋画像には，指の第二関節の部分まで含まれている場合がある。また，指紋画像の修復処理を行うと，背景に雑音が発生する。そのため，指紋マスク画像を生成し，最適な指紋領域を抽出する。

具体的な手順を以下に説明する。

1. 指紋画像を局所平均に基づく動的2値化処理を行う。まず，指紋画像全体での平均濃

淡値total_meanを求める。次に，指紋画像の各画素に着目して，着目画素を中心とす

るサイズ(2n+1)×(2n+1)の正方ブロック内での平均濃淡値 local_mean を算出する。

total_meanとlocal_meanの値の小さい方を閾値として，着目画素を動的に2値化する。

本研究では，n = 10 を用いた。

2. モルフォロジ演算である太め処理（dilation）をN 回，穴埋めを行ってから細め処理

（erosion）を2N回，最後に太め処理をN回施す。こうして得られる黒領域のうち，

最も大きい黒領域のみ残す。本研究では，N = 20とした。

3. 黒領域の幅の最大値とその時のy座標を調べる。

4. 黒領域の幅の最大値をとるy座標より下の部分について黒領域の幅を調べていき，以下の2つの条件のうちどちらかに該当したら，その時のy座標以下の黒領域を取り除く。

(1) 最大値×0.7以下の場合

(2) 最大値×0.8以下かつ一列上の幅より大きい値をとる場合こうして得られる黒領域を指紋領域のマスク画像とする。

図4.1に，マスク画像を用いた指紋領域の抽出例を示す。

図4.1より，第二関節以下の部分のみが消去され，最適な指紋領域が抽出されていることがわかる。

(14)

(a))

図4.1 上段下段 (a)原画

マスク画像段：第二関節段：第二関節

画像 (b)マス

10 (b) 像を用いた指節の部分まで節の部分は含スク画像 (

指紋領域の抽で含まれてい含まれていな c)指紋領域抽

抽出例：

る画像い画像抽出画像

(c)

(15)

11

第 5 章位置ずらしマッチング

同一指の指紋画像の間でも，相互にかなりの回転や位置ずれを含む場合がある。本章では，マニューシャマッチングの前処理として，回転画像の使用による回転成分の吸収と，

勾配方向分布を用いたブロック単位の最適位置ずらしによる位置ずれ吸収，の 2 つの処理による入力－登録指紋画像間の位置ずらしマッチングについて述べる。使用する指紋画像は，登録および入力画像ともサイズは256×256で，第3章の強調処理を施してある。

5.1 回転による回転成分の吸収

回転成分の吸収には，単純に入力指紋画像を予め設定した複数の角度で回転した画像を生成してマッチングすることで対処した。具体的には，入力指紋画像を正立画像として，

－20度から＋20度の範囲で5度刻みに計9種類の回転角度を設定して，正立画像を含めて 9枚の回転画像を用意した。

この処理により，次節で述べるブロック単位の最適位置ずらしの処理量は，回転吸収のために9倍になることになる。

図5.1に回転画像の例を示す。

(16)

5.2

前節

(a)

(d

(g

ブロッ

節に続いて，

)

ック単位

，ブロック単

図5.

(a) －20度 (d) －5度 (g) ＋10度

位の最適位

単位の最適位

12 (b)

(e)

(h) 1 回転画像

(b) －15度度 (e) 0度

(h) ＋15度

位置ずら

位置ずらしに像の例：

度 (c) －10 (f) ＋5度度 (i) ＋20

らし

により，画像 0度

度

像間に生じた (c)

(f)

(i)

た平行移動ののずれ

(17)

を吸収位置グ尺度方ブ本研究像の特が，隆ロッ線の特

このずら

図ロック

収する。

置ずらしマ度の2点が重ロック（サイ究では，1ブ特徴としては隆線は端点やク単位で考え特徴を利用す

のブロック単し位置を求め

5.3に，ブロ

ク分割数を

入力指

登録

ッチングにお重要となってイズ M×M）

ブロックをM は，隆線が挙や分岐点などえると，各ブする。

図

単位での位置める。

ロック単位の

8×8とした

図5.3 指紋画像

録指紋画像

おいて，ずらてくる。ずら

に分割し，

M = 8とした挙げられる。

どが多くありブロック内で

図5.2 ブロ

置ずらしを行

のずらしマッた図となって

ブロック単

13 らし幅の設定らし幅につい

このブロッ

。分割ブロ

1つの指紋

り，複雑になで隆線はほぼ

ック内での指

行い，正規化

ッチングの概ている。実際

単位のずらし

定とマッチンいては，サイ

ック単位で位ック数は102

において，隆なっている。

ぼ一定の方向

指紋隆線方向

化相互相関値

概念図を示すの分割数は

しマッチング最終的

ングに用いるズN×Nの指位置ずらしを

24となる（N 隆線の幅や間しかし，図向となる。こ

向

値が最大とな

。わかりやす

32×32であ

グの概念図的に重なりが

る特徴・マッ指紋画像全体を行うことと

N = 256）。指間隔はほぼ一 5.2のようにこのような指

なる回転およ

すくするためある。

がよい位置をッチン体を正する。

指紋画一定だに，ブ指紋隆

よび，

め，ブ

を決定

(18)

14

5.3 勾配方向分布を用いた位置ずらしマッチング

上記の節5.1と節5.2を順に行い，回転・平行成分の吸収を行う。

具体的な手順を述べる。

1. 入力－登録指紋画像それぞれのマスク画像の重心が画像の中心になるように平行移動する。

2. 入力画像にアフィン変換を施し，回転画像を生成する。アフィン変換の式を以下に示す。伸縮・回転・せん断を表す2×2の行列A と平行移動を表すベクトルbで表現できる。さらに，このA, bを用いて，位置座標(i, j)は(i’, j’)に変換される。

(3)

3. Roberts交差勾配方向オペレータ[7]を用いて，濃淡指紋画像の各ピクセル位置(i, j)に

おける濃淡勾配を算出する。位置(i, j)での濃淡値g(i, j)と記すと，濃淡勾配の角度θ(i, j)は，2×2近傍マスクを用いて次式で計算される。なお，右水平方向を0度とし，濃淡勾配の角度θ(i, j)は，π / 16の間隔で32方向に量子化する。

∆ 1, 1 , ∆ 1, , 1

, ^∆_∆ (4)

4. 各ブロック内の8×8ピクセルがどの勾配方向であるか計数して，32方向別のヒストグラムを作成する。そして，ガウス型の重み[1 4 6 4 1]^Tを用いて32方向から16方向に圧縮し16次元の特徴ベクトルを抽出する。これを当該ブロックの勾配方向分布特徴ベクトルとする。

5. 入力画像を登録画像に対してブロック単位でずらしを施し，重なったブロック毎に勾配方向特徴ベクトル間の二乗距離を算出する。

① 入力画像の勾配方向特徴ベクトルを以下のように表現する。

, , ⋯ , (5)

② 登録画像の勾配方向特徴ベクトルを以下のように表現する。

, , ⋯ , (6)

③ ブロック当たりの平均二乗距離を当該ずらしΔによるマッチング尺度D(Δ)とし て次式で示す。Δをブロック単位での縦横ずらし，N(Δ)をずらしΔのときの入力画像と登録画像間の重なりブロック数を表す。

(19)

6.

7.

図図

ずらしの最うことにな最適位置ずここで得らいる。

5.4に，回転 5.4より，相

(a

∆ _∆

最大範囲を上なる。値D(Δ ずらしを与えられた最適な

転・平行移動相互の回転と

a)

図 (a)入

∆ ∑

上下左右にK Δ)が最小とな える。本研究な位置ずらし

動成分の吸収位置ずれが

図5.4 回転入力画像 (b)

15

∆

KブロックとなるずらしΔ 究では，K = しマッチング

収例を示す。

が吸収されて

(b)

・平行移動成 )マッチング

とすると，総 Δ^*を決定する

12と設定し

グの評価尺度

いることがわ

成分の吸収例グ画像 (c)登

総数(2K+1)²通ると，これがした。

度D(Δ^*)は指紋

わかる。

例：

登録画像

(7) 通りのずらしがブロック単

紋照合判定に

(c)

しを行単位の

にも用

(20)

第

前章実現

本章点と分づけ

6.1

まずには，

次い細線

1.

2.

3.

6 章

章までの処理している。

章では，この分岐点であるを行うマニュ

マニュ

ず，マニュー

，第4章でもいで，細線化線化パターン

細線化したとは，図

γ = 1であ候補とする抽出したす指紋隆線上除する。本これは，画生した端点指紋領域ともマニュー

マニュ

理により，回

の位置ずらしるマニューシューシャマッ

ューシャ

ーシャ抽出のも述べた局所化処理を施すンを用いてマ

た指紋隆線上 6.1のように

∑ る場合，中心る。これらがすべてのマニ上にある場合本研究では，

画像修復処理点を偽マニュと背景領域のーシャ候補点

ューシャ

回転成分の吸

しマッチングシャを抽出しッチングにつ

抽出

の前処理とし所平均に基づす。細線化処マニューシャ

上の各点を中に3×3近傍で

図

| 1

心画素は端点がマニューシニューシャ候合，それら2

Th_d＝8とし理後にも残っ

ューシャとしの境界部分に点から削除す

16

ャマッ

吸収と勾配方

グ後の入力おし，入力－登ついて述べる

して，入力おづく動的2値処理にはHild ャ抽出を行う

中心とする3 で中心画素を

6.1 3×3近

| 点の候補とすシャ候補点と候補点間の距候補点はとした。

ている画像して判定するに，指紋隆線する。

ッチング

方向分布を用

および登録指登録マニューる。

および登録指値化処理を用

ditchの方法が，具体的

3×3近傍で交

を囲む8画素

近傍の画素

する。γ > 2のとなる。

距離dを算出もに偽マニュ

のかすれによるものである線の端点や分

グ

用いた平行移

指紋画像からーシャ間で最

紋画像を2値用いた。

[7]を用いた的な手順を以

交差数γを算素を用いて次

の場合，中心

出し，一定距離ューシャとし

よる指紋隆線る。

岐点が発生す

移動成分の吸

ら，指紋隆線最適な 1 対 1

値化する。2

た。

下に述べる。

算出する。交次式で示す。

(8) 心画素は分岐

離Th_d以下でして候補点か

線の分断によ

するため，こ吸収が

線の端 1 対応

2値化

。交差数

岐点の

で同一から削

より発

これら

(21)

4.

5.

図

6.2

入力と分岐

まずマニの点間

最後に入力点を削除す以上の処理

6.2に，マニ

マニュ

力－登録マニ岐点の区別はず，入力－登

ューシャと登間距離行列が

力指紋と登録する。

理で残ったマ

ニューシャ抽

(a)画

ューシャ

ニューシャ間は行わないこ登録マニュー

登録マニューが作成される

録指紋のマス

マニューシャ

抽出例を示す

(a)

(c)

図6.2 マ画像修復後の

(c)細線化画

対応付け

間で1対1のこととする。

ーシャ間で全ーシャで点数る。この行列

17 スク領域の重

ャ候補点をマ

す。図中，○

マニューシャの濃淡指紋画

画像 (d)抽出

け

の最適なマニ

全てのマニュ数の多い方を列を用いて，点

重なり部分の

マニューシャ

が端点，□が

(b)

(d) ャ抽出例：

画像 (b)2値化出マニューシ

ニューシャ対

ーシャ対間

をP，少ない

点間距離和が

の外にあるマ

ャとして出力

が分岐点を表

化画像シャ

対応付けを行

の点間距離をい方をQと記

が最小となる

マニューシャ

力する。

表す。

行う。ただし，

を算出する。

記すと，P行るQ個の点対

ャ候補

端点

入力行Q列対を1

(22)

18

対1対応の条件下で求めることで，最適な対応付けとすることとした。

その際，対応マニューシャの点間距離に上限を設定した。今回の実験では上限値 = 14とした。この制限により，対応付けられる点対の総数はQ個以下となる。

この最適な組み合せ探索アルゴリズムとして，１対多の対応を解消する過剰対応解消法と Q 点側での未対応点を解消する不足対応解消法という 2 つの相補的な対応付け探索アルゴリズムの併用を用いた[8]。

最後に，相補的な両者の組み合わせ探索結果で照合点対数が多い方を採用し，最終的なマニューシャ対応付け結果として出力する。

6.2.1 過剰対応解消法

マニューシャが1対多の対応になったとき，それを解消するために行う手法である。

以下に具体的な説明を行う。

1. 入力画像のマニューシャをもっとも近い登録画像のマニューシャに対応付けさせる。

2. 1対1の対応付けであれば処理4へ進む。そうでなければ処理3へ進む。

3. 同一の登録画像のマニューシャに対応付いている入力画像のマニューシャ群の中で最も近い入力画像のマニューシャを対応相手として確定し，その他の入力画像のマニューシャはそれぞれ次に近い登録画像のマニューシャに対応付ける。処理2 に戻る。登録画像で未対応のマニューシャをそれぞれ入力画像でもっとも近いマニューシャに対応付けて，終了する。

4. 最後に，入力画像と登録画像の指紋領域で，重なっていない領域のマニューシャを削除する。

図6.3にアルゴリズムに対応する図を示す。●が入力画像のマニューシャであり，○が登録画像のマニューシャである。

(23)

19

図6.3 過剰対応解消法例

6.2.2 不足対応解消法

対応付かないマニューシャが存在するとき，それを解消するために行う手法である。

以下に具体的な説明を行う。

1. 登録画像のマニューシャを最も近い入力画像のマニューシャに対応付ける。

2. 対応相手のいない入力画像のマニューシャがあれば処理3 へ進む。そうでなければ処理4へ進む。

3. 対応相手のいない入力画像のマニューシャ群についてそれぞれ最も近い確定済みでない登録画像のマニューシャを選び，それらの中で最も遠く離れた対を確定とする。処理2へ戻る。

4. 複数の登録画像のマニューシャから対応付いている入力画像のマニューシャがあれば最も近い登録画像のマニューシャを対応相手として確定し，終了する。

図6.4にアルゴリズムに対応する図を示す。●が入力画像のマニューシャであり，○が登録画像のマニューシャである。

(24)

20

図6.4 不足対応解消法例

図6.3，図6.4を見てわかるとおり，過剰対応解消法と不足対応解消法では入力画像と登

録画像のマニューシャをマッチングさせる仕方が違うため，指紋によってはマッチング数が異なってくる。上記で述べたように，本研究ではよりマッチング数が多い方を対応付けの結果とした。

6.3 照合率の算出

前節の手順により，入力－登録マニューシャ間で1対1対応付けが決定される。この対応付けの評価尺度として，次式で定義する照合率κを用いた。

(9) ここで，入力指紋のマニューシャ数をM，登録指紋のマニューシャ数をN，入力－登録指 紋間で対応付いたマニューシャ対数を N_pairとする。式(3)より，照合率 κ は，0.0≦κ≦1.0 の値を取る。照合率κの値が大きいほど同一指の指紋である可能性が高いと考えられる。

(25)

第

提案枚の指録指わち，

7( = 5

7.1

指紋 N_pairおこの FRR)

まず示す。

図 ROC(

図ことが

7 章

案手法の評価指紋画像デーとして残り

，8-fold cros 5600)回，他

ROC

紋照合によるおよび照合率の 3種類の評 )と他人受理ず，3種類の

。

7.1に，D(Δ (Receiver ope 7.1より，単が分かる。

実験結

価実験には，

ータを用いた 7枚を本人指 ss-validation

人照合の総試

曲線

る本人・他人率κ，という

評価尺度のそ率(False Acc の評価尺度を

Δ^*)，N_pair，κ erating chara 単独では位置

図7

結果

FVC2004 指た。cross-vali

指の照合，そで評価を行っ試行数は10

人判定には，

う3種類の評それぞれに対 ceptance Rate を単独で用い

κについてそ acteristics)曲 置ずらしマッ

7.1 D(Δ^*)，

21 指紋画像デー

idation法[9]

その他の99 った。したが

0×8×99×8

第 5 章の D 評価尺度を使

対して閾値を e; FAR)の関係いた場合のFR

それぞれ閾値線[2]を示すチングでの評

N_pair，κ単

ータベースのに従い，各指枚×8枚を他がって，本人

8( = 712800)

D(Δ^*)，第 6 使用する。

を決め，本人係を調べた。

RRとFARの

値 Th1，Th2，

す。

評価尺度であ

単独でのROC

の DB1 に含指について1 他人指の照合人照合の総試

回となった。

6 章の照合マ

人拒否率(Fals の関係につい

，Th3を変化あるD(Δ^*)が

C曲線

含まれる全 1 1枚ずつ順次合に用いた。

試行数は100

。

マニューシャ

se Rejection

いての実験結

化させて得ら

が最も性能が 00×8 次に登すな

×8×

ャ対数

Rate;

結果を

られた

が良い

(26)

7.2

指紋 EER(

表

次にた。

それ討した

このよる性

図

EER の

紋照合システ (Equal Error R 7.1に，3種

に，3 種類の

れぞれの閾値た結果，次式

の EER値が性能評価の指

7.2に，式(1

の評価

テムの性能評 Rate)の値が種類の評価尺

の評価尺度 D

値 Th1，Th2 式の条件で本

が，位置ずら指標となる。

10)の条件を用

図7.2

評価には，本よく用いられ度を単独で用

表7.1 単評価 D(Δ N_pai κ

D(Δ^*)，N_pair

2，Th3 を用本人受理の判 2 ∩ ∆^∗ しマッチン

用いて各閾値

2 式(10)の

22 本人拒否率(F

れる[2]。

用いた場合の

単独の評価尺価尺度 EER Δ^*) 13

ir 31

23

r，κ の組み合

いた判定式定を行った場

1 ∪ グとマニュー

値を変化させ

条件を用いた

FRR)と他人

のEERの値

尺度でのEER R(%)

.64 .64 .86

合せによる本

を論理和と論場合に最小の

3

ーシャマッチ

せて得られた

た場合のRO

受理率(FAR を掲げる。

R

本人・他人判

論理積で組みのEER値12

チングを融合

たROC曲線

OC曲線

R)が等しくな

判定の実験を

み合せる方式 2.91%を達成

(10) 合した提案手

を示す。

なる値

を行っ

式を検した。

手法に

(27)

23

7.3 処理時間

表7.2に，提案手法の各段での処理時間を示す。入力指紋画像と登録指紋画像の1対当たりの照合に要する平均処理時間を表している。

ただし，開発はWindows上のVisual StudioでC言語を用いて行った。計算機環境はCPU がIntel Core 2 Duo P8600 2.4GHz，メモリが4GBである。

表7.2 提案手法の各段での処理時間

処理内容平均処理時間(s) 局所的FFTバンドパスフィルタによる画像修復 9.35

指紋マスク領域の抽出 1.94 位置ずらしマッチング 2.29 マニューシャマッチング 2.16

(28)

第

提案 FFTバ修復すとで，

影響図図の吸収る。特り，マング

EE

8 章

案手法では，

バンドパスフすることがで

，画像修復処を及ぼす部分 8.1に提案手 8.1より，局収，位置ず特に，図8.1

マニューシャと組み合わせ

(a)

ER = 12.91%

考察

，位置ずらしフィルタによできた。さ処理で発生分をきれいに手法の成功例

所的FFTバらしマッチン

下段(c)の画ャマッチングせることで救

)

(a)入

という結果は

しマッチングよる画像修復

らに，指紋マしてしまう雑に取り除くこ例を示す。

バンドパスフングによる平画像は，画像

グ単独では照救うことがで

図8.1 入力画像 (b)

は，FVC2004

24 グとマニュー復を行い，目視

マスク画像を雑音や指の第ことができ，

ィルタによ平行移動成分

修復が不十分照合率が良くできた。

(b) 提案手法の )重ね合わせ

4に参加した

ーシャマッチ視では確認すを生成して最第二関節の部 EER = 12.9

る画像修復や分の吸収が有分で最適なマくなかった。

の成功例：

せ画像 (c)登

たacademic g

チングの前処することも難最適な指紋領部分などマッ 1%という結

や回転画像を有効に働いてマニューシャしかし，位

登録画像 groupsが得た

処理として局難しい指紋隆領域を抽出すッチング精度結果を得られ

を用いた回転ていることがャ抽出が困難位置ずらしマ

(c)

た値[6]と比較局所的隆線をするこ度に悪れた。

転成分が分か難であマッチ

較する

(29)

と，中であり，良

8.1

回転るこッチいに重

まずこのつけ

これできチンチングチング

次にこのの値がング結

中位に相当する。また，in 良い結果とは

位置ず

転成分の吸収とで対応し，

ングを用いた重なっていなず，図8.2にの失敗例1は

ることができれを解決する

ると思われグしてしまいグ尺度D(Δ グをする必要

(a)

に，図8.3にの失敗例 2

が大きくなっ結果である。

する第5位の成 ndustryも含は言えない。

ずらしマ

収には－20度

，平行移動成た。しかし，

ないものがあに位置ずらし

は，入力画像きず，間違っるには，ずら

る。しかし，

い，他人受理 Δ^*)の最小値だ

要がある。

)

図8 (a)入

に位置ずらしは，指紋画像ってしまい，

。

成績である。

めた全参加4 以下では，

マッチング

度から＋20 成分の吸収に

マッチングあった。主にしマッチング像のずらし量った位置でマ

し範囲を広単純に広げ理率が高くなだけでなく，

8.2 位置ず入力画像 (b)

しマッチング像が非線形な

本人同士の

25

。ただし，aca

41機関の中

各マッチン

グの課題

度の範囲でには勾配方向グ結果を調べに2種類の失グの失敗例1 量が足りなか

マッチングしげることで正げてしまうとなってしまう重なってい

(b) ずらしマッチ

)重ね合わせ

グの失敗例2 な歪みを起この指紋である

ademic group 中では，提案手

グ処理の今後

題

5度刻みに計向分布を用いべてみると，

失敗例があっを示す。

かったためにしてしまった

正しく重なると少ない重なう可能性が考るブロック数

ングの失敗例せ画像 (c)登

を示す。

こしているたるにも関わら

での最高性能手法でのEE 後の課題につ

計9種類の回いたブロック入力－登録ったので考察

，正しく重なた。

るべき位置をなりブロック考えられる。

数を考慮して

例1：

登録画像

ためにマッチらず他人と判

能はEER = 4 ER値は32位ついて考察す

回転画像を生ク単位のずら録指紋画像が察する。

なるべき位置

を見つけるこク数の位置でそのため，

て位置ずらし

(c)

チング尺度 D 判定されたマ

4.37%

位であする。

生成すらしマがきれ

置を見

ことがでマッマッしマッ

D(Δ^*) マッチ

(30)

これいた量が増によ大す

位置るブされてく，指その

×480 イズにク画像を行っ類の評 ROC

れを解決するめ，非線形な増大する。そる悪影響を小る処理量を比

(a

置ずらしマロックのサイている指紋画指紋領域が画のため，解像 0サイズの原に変換して実像を生成し，

った。画像解評価尺度D(

曲線を図8.

るには，位置な画像歪みにそのため，位小さくするか比べながら検

a)

図8 (a)入

ッチングの精イズをより小画像を調べて画像全体の4 像度を上げた原画像を左右

実験を行ってマスク画像解像度以外の (Δ^*)，N_pair，

4に示す。さ

置ずらしマッに対処する必位置ずらしマか，新たに非検討する必要

8.3 位置ず入力画像 (b)

精度を上げる小さくするこ

てみると，画 4分の1に満た指紋画像を右80画素切り

ているのに対像の重心を中のその他の条 κについてそさらに，提案

26 ッチングでは必要がある。

マッチングの非線形な画像要があると考

(b) ずらしマッチ

)重ね合わせ

るには，回転ことが考えら

画像全体に対満たないようを用いて実験り取った後，

対して，検討中心に256×

条件は全て同それぞれ閾値案手法の結果

は回転と平行しかし，新の精度をさら像歪みに対処考えられる。

ングの失敗例せ画像 (c)登

転角の刻み幅られる。さら

対して指紋領うな画像も見験を行った。

双一次線形討案は640×

256サイズを

同じである。

値Th1，Th2 果と比較して

行移動の成分新たに処理をらに上げて非処する処理を

例2：

登録画像

幅やずらしマらに，FVC20

領域がかなり見られる。

具体的には形補間法を用

480サイズの

を原画像からこの検討案

，Th3を変化て表8.1に示す

分しか吸収でを追加すると非線形な画像を追加するか

(c)

マッチングに 004のDB1にり小さいもの

，提案手法が

用いて256×2

の原画像からら切り取っての実験結果，

化させて得らす。

できなと処理像歪みか，増

に用いに収録のが多

が640 256サらマスて実験

，3種られた

(31)

表ングのな部分したた勾配方向に圧る。まう前紋隆線

8.2

マニと考てい

8.1からもわの照合率κと分が解像度をためと考えら方向特徴の精圧縮していたまた，隣接すに，各ブロ線の修復が不

マニュ

ニューシャマえられる。偽るものがある

図8.4

表

わかる通り，

ともに精度がを上げたこられる。その精度を高めるた勾配方向特するブロックックについて不十分な部分

ューシャ

マッチングで偽マニューシる。

検討案のD

8.1 解像度評価尺度 D(Δ^*) N_pair κ

位置ずらしが低下してい

とによって，

のため，ブロることの方が特徴を32方

ク同士の隆線て近傍ブロッ分の影響を軽

マッチン

での課題としシャが全て削

27 D(Δ^*)，N_pair，

度の違いによ提案手法

13.64 31.64 23.86

マッチングいることがわ

より多数のックサイズが重要である

向のヒスト線方向は似てックの勾配方軽減すること

ングの課

しては，偽マ削除されず残

κ単独での

るEER(%)の検討案

15.92 27.11 26.30

の評価尺度わかる。これ

のブロックのを細かくしてると考えられ

グラムをそのているため，

方向特徴を比とができると

課題

マニューシャ残っているた

のROC曲線

の比較

D(Δ^*)とマニは，指紋隆線の勾配方向特てマッチングれる。解決案

のまま使用す位置ずらし比較して修正と考えられる

ャの削除に改ために照合率線

ニューシャマ線の修復が不特徴に影響をグすることよ案としては，

する案が挙げしマッチング正することでる。

改良の余地が率の低下に影

マッチ不十分を及ぼより，

16 方げられグを行で，指

がある影響し

(32)

図

偽マ点を削れる。

紋隆線

8.5に偽マニ

マニューシャ削除してい

。また，同一線が途中で合

ニューシャが

図8.

(c)

ャの削除ではるが，直線距一指紋隆線上

合流している

図8.6

が多く残って

(a)

(c)

5 偽マニュ (a)原画像 )細線化画像

は，点間の直距離だけでは上であるかを

ると同一指紋

2本の指紋

28 ている例を示

ューシャが多

像 (b)指紋隆

像 (d)マニュ

線距離を算は偽マニューを考慮してい

紋隆線と判断

紋隆線を同一

す。図中，○

(b)

(d) 多く残ってい隆線修復画像ューシャ抽出

出して指紋隆ーシャを検出いるが，図8.

断しているた

一と判断して

が端点，□が

いる例：

像画像

隆線の分断に出することは 6で示す例のため，正確で

しまう例

が分岐点を表

により発生しは難しいと考のように2本ではない。

表す。

した端考えら本の指

(33)

偽マを発生ター方向，

効と考

また化処理ーシいるがるとい他に偽マニ対1の

マニューシャ生させたり，

ンがある。そ

，2点間の隆考えられる。

た，局所的F 理の過程で修ャが多く発生が，局所的いう性質をに，マニュー

ニューシャのの対応付けに

ャは，図8.7 小さな輪をそのため，直隆線に沿った

。

FFTバンドパ

修復された指生する場合が

FFT バンド

2値化処理にーシャマッチ

の検出でも取にも用いるこ

で示すようを形成して分

直線距離に加た距離を用い

図8.7 偽マ

パスフィルタ指紋隆線が再がある。2値ドパスフィル

にも利用するングの精度を取り上げた，

ことは有効と

29 に指紋隆線分岐点を 2 点

加えて，端点て各パター

マニューシャ

タを用いて指再び失われて値化には，局所

タで用いた指るなどの改良

を向上させる端点や分岐と考えられる

から髭のよ点発生させた点や分岐点をンの偽マニュ

ャのパターン

指紋隆線を修ていることが

所平均に基づ指紋隆線方向良が必要であ

るには，1対岐点を延長し

る。

うに少し伸びたりと，いくを延長した場ューシャを検

ン

修復しているがあり，この

づく動的2値向が局所領域あると考えら

1の対応付けた場合の指紋

びて端点と分くつか決まっ場合の指紋隆検出すること

が，2値化，

のために偽マ値化処理を用域でほぼ一定られる。

けの強化があ紋隆線の方向

分岐点ったパ隆線のとが有

細線マニュ用いて定であ

ある。

向を1

(34)

30

第 9 章結論

身体特徴を用いて個人認証を行うバイオメトリクスの中でも指紋認証技術は，今後も市場拡大が予測されており，さらなる性能向上が期待されている。

本論文では，劣化指紋画像を対象として，パターンマッチング法とマニューシャマッチング法を融合した照合手法を提案し，FVC2004指紋画像データベースのDB1を用いて照合実験を行った。勾配方向分布を用いたブロック単位の位置ずらしで得られるマッチング尺度，

マニューシャマッチングで得られる照合数と照合率の 3 種類の評価尺度を併用した閾値判定を用いることにより，本人拒否率と他人受理率が等しくなる値としてEER = 12.91%を達成した。

しかし，FVC2004の全参加41機関の評価報告と比較すると，提案手法の性能は良い結果とは言えない。

今後の課題として，画像修復の改良，指紋隆線の勾配方向分布の特徴能力の向上，偽マニューシャの削除アルゴリズムの強化，がある。画像修復の改良は，フーリエ変換成分の大きさの増幅量やフィルタリングの上限周波数を変更して修復能力を向上させることが考えられる。指紋隆線の勾配方向分布の特徴能力の向上は，勾配方向特徴を細かく算出し，ずらし範囲を広げてマッチングことが挙げられる。偽マニューシャの削除アルゴリズムの強化は，マニューシャから伸びる隆線の方向を特徴に加えることで対処できると考えられる。

さらには，非線形な画像歪みに対処する必要があり，これをできるだけ少ない計算量で実現するアルゴリズム開発は挑戦的な課題である。

(35)

31

謝辞

本研究を行うにあたり，御指導いただいた若原徹教授に深い感謝の意を表します。的確な御助言により，本研究がこのような成果を得られたのだと思います。研究以外の面でも日頃から多数お世話になっており，感謝の念に絶えません。

また，手助けしてくださった若原研究室の皆様を初め，お世話になったすべての方々に深く感謝します。

2011年1月28日

(36)

32

参考文献

[1] http://www.biometricgroup.com/reports/public/market_report.php

[2] D. Maltoni, D. Mario, A. K. Jain, and S. Prabhakar, Handbook of Fingerprint Recognition, New York: Springer, 2002.

[3] A. K. Jain, “Biometric Recognition: Techniques, Applications and Challenges,” Tutorial-A, in 18^th Int. Conf. on Pattern Recognition, Hong Kong, China, Aug. 2006.

[4] 星野幸夫監修，指紋認証技術－バイオメトリクス・セキュリティ，画像電子学会編，

東京電機大学出版局，2005.

[5] S. Otaka, Y. Nishiyama, T. Hatano, and T. Wakahara, “Fingerprint verification using perturbation method,” Proc. of the IAPR Conf. on Machine Vision Applications 2007, pp.

424-427, Tokyo, Japan, May 2007.

[6] http://bias.csr.unibo.it/fvc2004/.

[7] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Third Edition, Prentice Hall, 2007.

[8] T. Wakahara, A. Suzuki, N. Nakajima, S. Miyahara, and K. Odaka, “On-line cursive Kanji character recognition as stroke correspondence problem,” Proc. of 3^rd Int. Conf. on Document Analysis and Recognition, vol. 2, pp. 1059-1064, Montreal, Canada, Aug. 1995.

[9] C. M. Bishop, Pattern Recognition and Machine Learning, New York: Springer, 2006.

勾配方向分布とマニューシャマッチングを 用いた指紋照合

2010 年度修士論文