(57)【要約】皮膚の模様、および特に指紋における線を符号化する方法において、１度に１つの線が複数の頂点を用いて符号化され、複数頂点は開始点と終了点を含み、この場合に隣接する頂点の間の接続線の部分は、この線から離れて予め設定された間隔より短い。
2005535957.tif 000002
【特許請求の範囲】
【請求項１】
皮膚表面の模様、特に指紋における線を符号化する方法であって、
開始点および終了点を含み、１つの線上に位置を定められた複数の頂点を用いて、隣接する頂点の間を結ぶ線分が、その線から離れる所定の間隔よりも大きくないようにして、一度に１つの線が符号化されることを特徴とする方法。
【請求項２】
開始点および終了点が決定された後に、前記開始点および前記終了点との間の接続線から最大の間隔で離れている線の上の点について探索が行なわれ、前記最大の間隔で離れている前記点が第１の頂点として記憶され、前記第１の頂点と前記開始点および前記終了点との間で、他の複数の点であってそれらを補助的に接続する線分から最大の間隔で離れている複数の点について、第２および第３の頂点を構成するものと考えられるこれらの点と前記開始点、前記終了点、前記第１の頂点との間で、最大の間隔でそれぞれ離れている更なる複数の点についての探索が行なわれ、これらの複数の点が更なる頂点を形成し、このような種類の探索が、前記所定の間隔よりも大きい間隔である点が発見されることが無くなるようなそのときまで続けられることを特徴とする請求項１に記載の方法。
【請求項３】
前記所定の間隔は、複数の線の間の間隔の第３の間隔よりも小さいことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記分岐から離れて分岐線が分かれていることを特徴とする請求項１ないし３の何れかに記載の方法。
【請求項５】
閉じられた線が分岐されていることを特徴とする請求項１ないし４の何れかに記載の方法。
【請求項６】
接続する線分からの間隔を決定する際に、所定の点から前記接続する線分を含む直線までの垂線が計算されることを特徴とする請求項１ないし５の何れかに記載の方法。
【請求項７】
一度に１つの点と接続線分との間の間隔は、所定の点から前記接続する線分を含む直線までの垂線が、前記接続する線分の上に位置されていないならば、前記接続する線分の開始と終了の間隔として計算されることを特徴とする請求項１ないし５の何れかに記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、皮膚から紋［表面の模様］内の線を符号化する方法に関し、特に、指紋の線を符号化する方法に関する。
【背景技術】
【０００２】
指紋を用いて身元を確認するために、指紋の画像が解析され、これは、特に皮膚における末端や分岐などの特徴的な特性を抽出し、それらを蓄えて保持されている特性と比較することにより行なわれている。
【０００３】
特徴的な特性が抽出されることを可能にするため、画像が前処理されて、この前処理することにより生成された詳細が前処理されて蓄積されていることが必要である。この前処理の一部分として頻繁に取り出されるステップが、いわゆる骸骨化［skeletonization］であり、ここでは、複数の画像要素（画素）の幅を有する、隆線［ridge］が僅かに１画素幅の線へと低減される。これが行なわれる前に、輝度レベルが２値の値へと換えられる。この種の線を蓄積するために、結果としては線を作り上げるところまでいく、ラスタドット［raster dots―一定の軌跡の点―］の全てがそれらの共通の縦座標と共にメモリ内に蓄積されるべきである。多数の線が存在していることから判断すると、これは、メモリ内におけるかなりの量の空きを取り上げている。
【０００４】
それゆえに、この発明の目的は、構造的な解析のために必要とされる情報の如何なる損失もなしに、データを低減させるようにして線を符号化することにある。
【発明の概要】
【０００５】
この目的は、開始点および終了点を含んで、１つの線上に位置を定められた、複数の頂点を用いて、隣接する頂点の間を結ぶ線分が、その線から離れる所定の間隔よりも大きくないようにして、一度に１つの線が符号化される、この発明にしたがって達成される。
【０００６】
この発明に係る方法により可能となることは、記憶スペースの節約だけではない。連続的な構造解析や特に特徴的な特性の抽出が、骸骨化された隆線を備える２値の画像によるよりも、より速く、より容易に行なえる。この目的のために用いられる方法によれば、接続線の線分の上に位置される他の点を計算することにより復号化されなくてはならないような線を用いることなく、カバーされるため、複数の頂点のみで充分である。
【０００７】
この発明による方法の１つの実施形態は、複数の頂点のために、特に有利な方法で決定されることを可能にしており、開始点および終了点が決定された後に、前記開始点および前記終了点との間の接続線から最大の間隔で離れている線の上の点について探索が行なわれ、前記最大の間隔で離れている前記点が第１の頂点として記憶され、前記第１の頂点と前記開始点および前記終了点との間で、他の複数の点であってそれらを補助的に接続する線分から最大の間隔で離れている複数の点について、第２および第３の頂点を構成するものと考えられるこれらの点と前記開始点、前記終了点、前記第１の頂点との間で、最大の間隔でそれぞれ離れている更なる複数の点についての探索が行なわれ、これらの複数の点が更なる頂点を形成し、このような種類の探索が、予め設定された間隔よりも大きい間隔である点が発見されることが無くなるようなそのときまで続けられる。
【０００８】
予め設定された間隔は、皮膚からの模様［プリント］の種々の属性、例えば複数の線の間の間隔や後の方の最大曲率に、依存するであろう。実際に、もしも予め設定された間隔が複数の線の間の第３の間隔よりも狭いならば、それは有利であることが分かる。
【０００９】
皮膚からの模様の中に生じる隆線の分岐は、この発明による方法においては、分岐で離れるように分岐線を分けることにより許容可能となる。これが行なわれたとき、分岐における全部で３つの枝［limb］はそれぞれ１つの線として処理されるならば、これは有利であることが分かる。したがって、離れて分かれることはまた、これらの線のそれぞれのために定義されるべき開始点と終了点の原因となる。
【００１０】
皮膚からの模様内にさらに生じるより近い線がある場合、この発明による方法によりより近い線が破壊されて開かれる対策が為されても良い。開始点および終了点は、このときに破壊されて開かれた線のためにまた定義される。
【００１１】
この発明による有利な実施形態において、接続線を備える直線に対する所定の点からの縦軸は、接続線からの間隔を決定するときに計算される。しかしながら、目立った曲率の場合、この実施形態は、一定の状況のもとで、エラーを生成するが、計算という点では相対的に小さな負担のみを強いるだけである。
【００１２】
この発明による方法の他の実施形態は、間隔が目立った曲率の場合であっても正確に決定されると共に、一度の１つの点との間の距離を含んでおり、接続線またはその部分は、もしも、所定の点から接続線またはその部分を含む直線までの縦軸が、その接続線またはその部分の上に配置されていないならば、接続線またはその部分の開始点または終了点との間隔として計算されている。
【発明を実施するための最良の形態】
【００１３】
この発明のこれらおよび他のアスペクトは、以下に説明される実施形態から明らかであり、また明らかとされるであろう。
【００１４】
図１は、それぞれが０または１（黒か白か）の値を前提としても良い、例えば、２５０×３５０画素から形成された２値の形式のラスター画像へと前処理した後の、指紋を示している。この画像は、種々の線１を含み、この線１は開始点２、終了点３，分岐部４を有する。
【００１５】
図２は、複数の骸骨化された線の１つの線図であり、それぞれは１つの画素幅のみである。骸骨化された線を作り上げている複数の画素の中心を接続する線は、この発明の方法ではなく、個別の点がそれらの共通軸と共に記憶されていなければならない線の続きを示している。
【００１６】
線１が個別に符号化させられるために、この方法の第１のステップで、終了点と分岐点とが骸骨化された画像の中に発見される。これは、周知の方法により行なわれる。この目的を達成するために、探索が、例えば、同じ２値に隣接する１つの画素のみを有する１つの線（図では黒）を示す２値を有する複数の点について行なわれる。分岐の場合、探索は例えば、２つの隣接する点よりも多数の点について行なわれる。
【００１７】
これは、それぞれが開始点と終了点とを有する複数の線を生成する。追跡プロセスにより、これらの線はそれぞれ点の配列へと変換され、一度に一続きとなった複数の点の共通軸は、それらが追跡プロセス内で見出されるように連続してメモリ内に蓄積されている。
【００１８】
必要な記憶スペースを低減させるようにするために、チェックはまさに、予め設定された精度の基準の範囲内で、線を表示するために求められる（すなわち“必要な”）点をそれぞれの線に沿った内部の点の中から見つけ出すためにこの時点で行なわれる。この目的のために設けられる基準は、線の本来の一続きにおける点が、線の低減された一続きの点から離れて予め設定された間隔よりも、より多くなるべきものは全く無いことである。この方法が適当であることを考慮する前に、線ＡＢの一続きの２つの端部の間の接続線とある点との間の間隔を決定する２つの方法が、図３を参照することにより説明されるであろう。
【００１９】
図３ａに示された変形例において、為される全てのことは、端部ＡおよびＢを介して延長する直線への間隔を決定することである。これは、直線からのその間隔が予め設定された間隔ｈの最大である何れかの点のために、接続線との間隔が同じように最大でｈであるときはいつでも充分である。
【００２０】
図３ａにおいて、等距離の複数の直線がＡとＢとを通過する直線に平行して示されている。この方法は、図３ｂに示された方法の場合は避けられる、非常に目立つ曲率を有する曲線の場合にエラーを導く可能性がある。この場合、これは、決定されるＡとＢとの間の接続線からの実際の距離であり、その点からその直線までの垂線がＡおよびＢの内側の直線と一致するか、または外側の直線と一致するかを確立されなければならないと言うことを目的としている。第１の場合において、それは点ＡとＢのより近いものが間隔であり、第２の場合には、それは、接続線との間隔、すなわち垂線の下端が間隔となる。図３ｂに示される間隔の決定方法の使用が為されるとき、基礎とされる２値の画像は何れかの所望の構造を含んでいても良い。
【００２１】
図３ｃは再び、点Ｃのために間隔がどのようにして決定されるかにつき明らかにする。図３ａに示された方法については、ｈよりも狭い間隔が決定されるであろうし、これは明らかにこの場合ではない。しかしながら、図３ｂに示された方法については、間隔は、ＣとＢの間の間隔に等しくなるように決定される。
【００２２】
図４は、一例として線１を取り上げることにより、この発明に係る方法における個別のステップを示している。まず、図４ａに示すように、接続線５が線１の終了点ｘ１とｘ９との間に形成され、このうち後者は、例えば、最初におよそ３００点で作り上げられる。次に、接続線５から最も大きな間隔で離れた線上のその点が、すなわちこの実施例においては点ｘ５が計算される。接続線の線分６，７は、点ｘ５から点ｘ１およびｘ９に対して順々にそれぞれ形成される（図４ｂ）。図４ｃに示された図において、接続線（図４ｂ）の線分６，７から離れて最大の間隔である点ｘ３およびｘ７が示されており、この点ｘ３およびｘ７は順々に接続線の更なる線分８，９，１０，１１のための開始点を順々と形成し、そのプロセスは順々と中間の点ｘ２，ｘ４，ｘ６，ｘ８を生成する（図４ｄ）。
【００２３】
接続線の線分５ないし１９のそれぞれの計算の後に、接続線の所定の線分を定義する点ｘ１からｘ９の間で、接続線（図３）の線分からｈよりも大きく離れた間隔である線１の上の点が無いことを理解するためにチェックが行なわれる。もしもそれらの点が無いのならば、新たな頂点は線の関連する部分の上に形成されない。ひとたび、接続線の対応する線分よりもさらに離れた線の全体に沿って点が無いのならば、その後、全ての頂点が決定され、その後、要求された精度の基準の範囲内で、線を完全に定義する列の中に入れられる。示された例において、図４ｄに示された９つの点ｘ１ないしｘ９は全て本来の３００点よりもむしろ必要とされるものである。
【００２４】
８８０の指紋の研究において、この発明に係る方法により、２７５点の平均数が１つの完全な指紋を表現または符号化するために必要とされたことが分かった。全てのケースの２％よりも少ないケースにおいて、４００点よりも多い点が要求された。もしも点の位置が２バイト内に格納可能であるものと仮定し、さらにおよそ１００バイトのその他の点が最終点によりメモリ内で線の個別の一続きを互いに分離するために必要とされているものと仮定すると、そのとき、指紋はこの発明による方法と共に１キロバイトよりも少ない値で蓄積可能となる。圧縮されておらず、もしもビット毎に蓄積されているのならば、他方で２５６×３８４画素を計測する２値画像は、１２キロバイトを必要とする。
【００２５】
記憶スペースの低減に加えて、この発明は他の長所もまた有しており、すなわち、ベクトル的な表現が詳細な構造解析の実行されることを許容するという長所である。複数の隆線にとってはそれらの長さと方向のために調査されることは、より容易である。細目が共通の隆線上に位置されていること、または、所定の場合に、如何に多くの隆線が２つの些細な点の間に位置しているのかということを見つけることはより容易である。指紋を処理するために為される作業の大部分を構成する、人為的な影響（橋渡し、蹴爪、島状）の部分の除去は、より容易に為される。
【００２６】
図５はフローチャートの形態でこの発明による方法を実行するためのプログラムを示している。２１での開始の後に、既に骸骨化された画像（図１）は、２２で読み出され、また予め設定された許容値ｈのようになる。これは２３に続けられて、骸骨化された画像は個別の線に分離される。２４では、線が追跡されて、これにより線を形成する複数の点の列を生成する。２３で得られた線のそれぞれのために実行される、プログラムの次のステップ２５で、複数の頂点が図４に示されるように決定される。ここに含まれているプログラムにおけるステップは、図６と関連づけて、詳細に説明されるであろう。ひとたび複数の頂点が全ての線のために見出されたならば、プログラムは２６で終了となる。
【００２７】
図６に示されたプログラムは、複数の線のそれぞれのための一続きである。始めは、第１の頂点のインデックス、すなわち所定の線の開始点が３１で第１のスタック１の上に押しつけられ、最後の頂点のインデックス、すなわち終了点が第２のスタック２の上に押しつけられる。次に、開始点および終了点が“必要なもの”としてマークされる。３３で分岐の後に、２つのインデックスｉｄｘ１とｉｄｘ２が、３４でそれらのそれぞれのスタックから跳ね上げられて、スタックは空ではないものとして提供される。図４との関係で説明したように、３５で点ｘ１とｘ２との間で調査が行なわれ、接続線の一続きからのその点の間隔が最大となる。
【００２８】
もしもこの種の点が見つけられたならば、間隔が許容範囲ｈよりも大きいか否かを見つけるために３６でチェックがなされる。もしもこれが、この線の進路に沿って配置された第１の頂点が計算された場合であったとしたならば、その後この頂点は、含まれるものがこの許容範囲ｈ内の直線であるので、“必要な”ものではなくなる。このプログラムのステップ３７で“必要な”頂点から配列［アレイ］を再構築することにより、換言すれば、開始点および終了点以外の線上の全ての点を削除することにより３３でのブランチの後にプログラムは終了させられる。
【００２９】
しかしながら、もしも間隔ｄｍａｘがｈよりも大きくなったならば、その後、３８でインデックスｉｄｘ１がスタック１の上に押しつけられ、最大の間隔での点のためのインデックスｉｄｘｍａｘがスタック２の上に押しつけられ、その上で、３９で、最大の間隔での点のためのインデックスｉｄｘｍａｘはスタック１の上に押しつけられ、最終点のためのインデックスｉｄｘ２はスタック２の上に押しつけられる。このようにして、必要条件は点ｘ１，ｘ５およびｘ９の間の更なる点の探索を許容するように合致しており、最大の間隔での点（プログラムループにおける点ｘ５）はまず、プログラムのステップ４０における“必要な”ものとしてマークされている。
【００３０】
この後で、スタックが空であるか否かを発見するために、３３で再びチェックがなされる。しかしながら、これは、新たな頂点が３５で見出されていた場合ではないであろう。次のプログラムループはその後、点ｘ３とｘ７を生成する。この後、点ｘ２，ｘ４，ｘ６およびｘ８が発見される。図４に関連されて説明された例においては、ｄｍａｘは更なるループ内でｈよりも大きくはならないであろうし、そのときすぐに、このスタックは空であり、“必要な”頂点は３７で配列が為されるであろうことが、３３で分かる。
【図面の簡単な説明】
【００３１】
【図１】骸骨化された指紋を示す説明図。
【図２】線の続きとして骸骨化された皮膚の隆線の線図。
【図３】接続線からのある点の間隔の決定に関連する説明図。
【図４】この発明に係る方法により符号化された線を示す説明図。
【図５】この発明に係る方法を実行するためのプログラムを示すフローチャート。
【図６】図５に示されたフローチャート一部分をより詳細に示すフローチャート。
【図１】
2005535957.tif 000003
【図２】
2005535957.tif 000004
2005535957.tif 000005
2005535957.tif 000006
【図５】
2005535957.tif 000007
【図６】
2005535957.tif 000008
【国際調査報告】
2005535957.tif 000009