今学期には、「コンピューター情報を保護する方法と手段」という主題がスケジュールに登場しました。その一部は、生体認証、より具体的には指紋認識に関する実験室作業です。 また、最近、Habréでスキャン対象のデバイスに関する記事がありました。 ここで、認識アルゴリズムについて書くことにしました。
私の前に、学生として、かなり標準的なタスクがあります：指紋の検証（標準との比較）。 この研究室のものは今年だけ登場したので、方法論的なマニュアルはまだありません。 しかし、タスクの面白さを考慮して、Googleに行きました。
奇妙なことに、スキャナに関するトピックで示された記事の2番目の部分が最も有益であることが判明しました。 非常に理解しやすいように、いくつかのアルゴリズムについて説明しています。
1.相関の比較
このアプローチは、得られた結果に基づいて、異なるシフトと回転角度の2つの画像をピクセルごとに比較することで構成され、一致が判断されます。 （高度な複雑さのため、現代の条件では使用されません）
2.パターン比較
必要な精度に応じて、印刷の画像は領域に分割されます。 さらに、各領域のパターンは、パラメーターを使用して正弦波で記述されます。
- 初期位相シフト
- 波長
- 流通方向
このクラスのアルゴリズムは、スキャン時に高解像度を必要としません。
3.人のポイントによる比較
特徴点は、エンドポイントと分岐点です。 これらのポイントは両方の画像で強調表示され、その後、相関比較の方法によって、印刷物の一致に関する判定が発行されます。
比較的単純な実装と速度のため、これらのアルゴリズムはより一般的です。
私は、このタイプのアルゴリズムを実験室での実装に選択しました。 したがって、より詳細に説明します。
この記事では一般的なアイデアしか示していないため、引き続きGoogleを使用しました。 配信の3行目はこのプレゼンテーションでした。
選択したアプローチを実装するための手順をかなり詳細に説明しています。
だから、アクションプラン：
- 受信した画像の二値化
- 画像のスケルトン化
- ポイント選択
- ポイント比較
実装はPythonで行うことが決定されました。 したがって、 Python自体（バージョン2.7.1があります）に加えて、 PIL（Python Imaging Library）で画像をピクセルに解析する必要があります。
ステップ1.二値化
それから私は発明しなかったし、額で非常に簡単にすべてをした。
defバイナリ（ img ） ：
bImg = [ ]
範囲内の i （ img。size [ 0 ] ） ：
tmp = [ ]
範囲内の j （ img。size [ 1 ] ） ：
t = img。 getpixel （ （ i、j ） ）
p = t [ 0 ] * 0.3 + t [ 1 ] * 0.59 + t [ 2 ] * 0.11
p > 128の 場合 ：
p = 1
その他 ：
p = 0
tmp。 追加 （ p ）
bImg。 追加 （ tmp ）
戻り値
別の結果が必要な場合は、 「画像処理」ブログのトピックを参照してください。ここでは、2値化が頻繁に影響を受けます。
ステップ2.スケルトン化
グーグルのアルゴリズムが最も難しかったので、このステップは最大の困難を引き起こしました。 その結果、4つのアルゴリズムが見つかりました。
テンプレートの方法が選択されました。最初のセットは、テンプレートの2番目のセットとは異なり、画像のクロールが1回だけ必要なためです。 確かに、不正確さのレベルを下げるために、2番目のセットのテンプレートの一部が使用されます。
パターンは3 * 3マトリックスに対応します。ここで、中心要素はイメージトラバーサルの現在のピクセルです。
ここで、グレーは色が重要でないピクセルです
最初の8つのテンプレートが主要部分です。 「ノイズ」を除去するために下から4つ、これら4つは90、180、270度回転させることもでき、画像の2番目のバイパスで検索されます。
テンプレートに遭遇した場合、中央のピクセルは白く塗られます（スケルトンに属していません）。 削除オプションが残っている間、トラバーサルは続行します。
このアクションのコードは、いくつかの機能に分かれています。
def tmpDelete （ img ） ： ＃スケルトン化プロシージャの呼び出し、入力時にリストのリスト（2値化後）
w = len （ img ）
h = len （ img [ 0 ] ）
カウント= 1
カウントしながら ！ = 0 ： ＃少なくとも1つのピクセルが削除されたpokを繰り返します
カウント=削除（ img、w、h ）
カウントする場合 ：
delete2 （ img、w、h ）
def delete （ img、w、h ） ： ＃メインセットからピクセルを削除し、削除された数を返します
カウント= 0
範囲内の iの場合（ 1 、h- 1 ） ：
j が 範囲 （ 1 、w- 1 ）の場合 ：
if img [ j ] [ i ] == 0 ：
削除可能な場合 （ img、j、i ） ：
img [ j ] [ i ] = 1
カウント+ = 1
戻り回数
def delete2 （ img、w、h ） ： ＃ノイズセットからピクセルを削除
範囲内の iの場合（ 1 、h- 1 ） ：
j が 範囲 （ 1 、w- 1 ）の場合 ：
if img [ j ] [ i ] == 0 ：
deletable2 （ img、j、i ）の場合 ：
img [ j ] [ i ] = 1
def fringe （ a ） ： ＃3 * 3ノイズの定義
t = [ [ 1、1、1、1、0、1、1、1、1 ] 、
[ 1、1、1、1、0、1、1、0、0 ] 、
[1、1、1、0、0、1、0、1、1 ] 、
[ 0、0、1、1、0、1、1、1、1 ] 、
[1、1、0、1、0、0、1、1、1 ] 、
[1、1、1、1、0、1、0、0、1 ] 、
[ 0、1、1、0、0、1、1、1、1 ] 、
[1、0、0、1、0、1、1、1、1 ] 、
[ 1、1、1、1、0、0、1、1、0 ] 、
[ 1、1、1、1、0、1、0、0、0 ] 、
[ 0、1、1、0、0、1、0、1、1 ] 、
[ 0、0、0、1、0、1、1、1、1 ] 、
[ 1、1、0、1、0、0、1、1、0 ] ]
tのiの場合：
a == iの場合 ：
真を 返す
def check （ a ） ： ＃3 * 3がメインテンプレートに属するかどうかを判断する
t123457 = [ 1、1、0、0、1、0 ]
t013457 = [ 1、1、1、0、0、0 ]
t134567 = [ 0、1、0、0、1、1 ]
t134578 = [ 0、0、0、1、1、1 ]
t0123457 = [ 1、1、1、0、0、0、0 ]
t0134567 = [ 1、0、1、0、0、1、0 ]
t1345678 = [ 0、0、0、0、1、1、1 ]
t1234578 = [ 0、1、0、0、1、0、1 ]
t = [ a [ 1 ] 、a [ 2 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 7 ] ]
t == t123457の場合 ：
真を 返す
t = [ a [ 0 ] 、a [ 1 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 7 ] ]
t == t013457の場合 ：
真を 返す
t = [ a [ 1 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 6 ] 、a [ 7 ] ]
t == t134567の場合 ：
真を 返す
t = [ a [ 1 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 7 ] 、a [ 8 ] ]
t == t134578の場合 ：
真を 返す
t = [ a [ 0 ] 、a [ 1 ] 、a [ 2 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 7 ] ]
t == t0123457の場合 ：
真を 返す
t = [ a [ 1 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 6 ] 、a [ 7 ] 、a [ 8 ] ]
t == t1345678の場合 ：
真を 返す
t = [ a [ 0 ] 、a [ 1 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 6 ] 、a [ 7 ] ]
t == t0134567の場合 ：
真を 返す
t = [ a [ 1 ] 、a [ 2 ] 、a [ 3 ] 、a [ 4 ] 、a [ 5 ] 、a [ 7 ] 、a [ 8 ] ]
t == t1234578の場合 ：
真を 返す
def deletable （ img、x、y ） ： ＃受信3 * 3、メインの検証のために送信
a = [ ]
範囲内の iの場合（ y- 1 、y + 2 ） ：
j が 範囲 （ x- 1 、x + 2 ）の場合 ：
a。 追加 （ img [ j ] [ i ] ）
返却チェック（ a ）
def deletable2 （ img、x、y ） ： ＃3 * 3を受信し、ノイズのチェックのために送信します
a = [ ]
範囲内の iの場合（ y- 1 、y + 2 ） ：
j が 範囲 （ x- 1 、x + 2 ）の場合 ：
a。 追加 （ img [ j ] [ i ] ）
戻りフリンジ（ a ）
ステップ3.特異点を強調表示する
ここではすべてが簡単です。 8ポイントの近傍に黒が1つしかない場合、これが終点です。 それらが2つある場合、これは単なる行のポイントです。 3つは分岐点です。
def checkThisPoint （ img、x、y ） ： ＃近所の黒人を数える
c = 0
範囲 （ x- 1 、x + 2 ）の iの場合：
j が 範囲 （ y- 1 、y + 2 ）の場合 ：
if img [ i ] [ j ] == 0 ：
c + = 1
return c- 1
def findCheckPoint （ img ） ： ＃分岐点のリストと終了
x = len （ img ）
y = len （ img [ 0 ] ）
branchPoint = [ ]
endPoint = [ ]
範囲 （ x ）の iの場合：
範囲 （ y ）の jの場合：
if img [ i ] [ j ] == 0 ：
t = checkThisPoint （ img、i、j ）
t == 1の 場合 ：
エンドポイント。 追加 （ （ i、j ） ）
t == 3の 場合 ：
branchPoint。 追加 （ （ i、j ） ）
return （ branchPoint、endPoint ）
唯一の問題は、ノイズの完全な除去ではなく、特異点として認識されたプロセスの出現につながりました。 それらを考慮に入れないために、密接な（10 * 10）分岐点と終点の削除が行われました。
def __removeDouble （ x、y ） ： ＃別のリストに同じものがない要素のリストを返します
z = [ ]
xのiの場合：
c = true
yのjの場合：
i == jの場合 ：
c = False
cの場合 ：
z。 追加 （ i ）
yのiの場合：
c = true
xのjの場合：
i == jの場合 ：
c = False
cの場合 ：
z。 追加 （ i ）
zを返す
def delNoisePoint （ r ） ： ＃入力タプル（分岐、末尾）
tmp = [ ]
tmp2 = [ ]
for i in r [ 1 ] ：
x = 範囲 （ i [ 0 ] -5 、i [ 0 ] + 5 ）
y = 範囲 （ i [ 1 ] -5 、i [ 1 ] + 5 ）
r [ 0 ]の jの場合：
xのj [ 0 ] および yのj [ 1 ]の場合 ：
tmp。 追加 （ i ）
tmp2。 追加 （ j ）
return （ __removeDouble （ r [ 0 ] 、tmp2 ） 、__ removeDouble （ r [ 1 ] 、tmp ） ）
ステップ4.ポイントを比較する
30 * 30の近傍に入り、同じタイプのポイントであるポイントの簡単な検索。
def matchingPoint （ r、v ） ： #input：参照点のタプルとチェックされたもののタプル。 出力（一致、合計）
すべて = 0
一致= 0
v [ 0 ]の iの場合：
x = range （ i [ 0 ] -15 、i [ 0 ] + 15 ）
y = 範囲 （ i [ 1 ] -15 、i [ 1 ] + 15 ）
すべて + = 1
r [ 0 ]の jの場合：
xのj [ 0 ] および yのj [ 1 ]の場合 ：
マッチ+ = 1
破る
v [ 1 ]の iの場合：
x = range （ i [ 0 ] -15 、i [ 0 ] + 15 ）
y = 範囲 （ i [ 1 ] -15 、i [ 1 ] + 15 ）
すべて + = 1
r [ 1 ]の jの場合：
xのj [ 0 ] および yのj [ 1 ]の場合 ：
マッチ+ = 1
破る
リターン （一致、 すべて ）
オプション：
すべてのコードは、同じサイズの画像に対して有効です（ただし、異なる画像でも機能します）。
結論：
1.この実装は単純で不器用です。 たとえば、特定のポイントで線の角度を調べるなど、いくつかのチェックを追加することができます。 チェック時に、同じタイプの多くのポイントが近傍に落ちた場合に、すでに見つかったペアを破棄します。
2. Pythonでの実装はかなり遅いです。私のマシンでの実行速度は、人の往来が多いアイテムにはまったく適していません。 NumPyを使用するとパフォーマンスが向上する可能性があり、私も最高の実装者ではありません。
3. ここで完全なコードを取得します 。 このキットでテスト済み。
PS pythonの方がやや弱いので、コードについてコメントしたいと思います。 まあ、指紋採取に真剣に取り組んでいる人の意見。