هدف از انجام این پروژه طراحی و پیاده سازی یک سیستم است که تصویر دو اثر انگشت ورودی که برای احراز هویت به آن داده میشود را با هم مقایسه کرده و عددی را به عنوان میزان تشابه آن برگرداند. سپس برای پذیرش احراز هویت، یک آستانه را برای میزان شباهت تعیین کند که اگر میزان شباهت از آن مقدار بیشتر بود، سیستم آن مقایسه را به عنوان تطبیق بپذیرد و در غیر اینصورت آن را رد کند. این حد آستانه باید به گونه ای باشد که خطا روی پایگاه داده آزمون، کمترین میزان باشد. منظور از خطا، جمع مقدار FAR¹ و FRR² می‌باشد.

• برای دریافت داده‌های آموزش و آزمون لطفا به آزمایشگاه دکتر آنالویی مراجعه نمایید.

مقدمه

از دیر باز تشخیص هویت انسان امری حیاتی تلقی شده و بدین منظور راه کارهای مختلفی نظیر کارت شناسایی، پاسپورت و ... ارائه شده است که به علت جعل پذیری، گم شدن و سایر مشکلات آنها، از قابلیت اطمینان بالایی برخوردار نیستنید. بدین منظور در سالهای اخیر از تشخیص بیومتریک (زیست سنجی)³ برای برطرف کردن نواقص راه حل های قدیمی استفاده شده است. بیومتریک به معنی تشخیص خودکار افراد براساس ویژگی های خاص رفتاری و بیولوژیک آنها نظیر چهره، اثر انگشت، عنبیه، صدا و مشخصات هندسی دست است که به آسانی قابل جعل نبوده و بنابراین میتوانند کارامدتر از روش های سنتی برای شناسایی افراد، افزایش امنیت، کاهش تخلفات و تسریع در امور روزمره به کار برده شوند.
به خطوط سر انگشتان رگه ⁴ گفته می شود. اثر انگشت افراد دارای الگوهایی از رگه هاست که در طول حیات فرد تغییرناپذیر بوده، مگر آنکه دچار سوختگی شدیدی شود. این امر، تشخیص هویت براساس اثر انگشت را به یکی از بیومتریک های رایج تبدیل کرده است که در این پروژه مشخصا به تشریح آن پرداخته خواهد شد.

در این حوزه مسائل با دو دیدگاه مطرح می شوند:
• شناسایی هویت:⁵ در این حالت تصویر ورودی با مجموعه ای از تصاویر ذخیره شده جهت جستجو، مقایسه شده و در صورت یافتن تصویر اثرانگشت مشابه، هویت آن را برمیگرداند.
• تایید:⁶ در این حالت دو تصویر ورودی به سیستم شناسایی اثر انگشت خودکار ⁷ داده می شود و با توجه میزان شباهت این دو تصویر عددی را برگردانده می شود . سپس براساس آستانه شباهت تعیین شده برای مسئله، سیستم پاسخ تایید تطبیق و یا رد در تطبیق را در خروجی نمایش می دهد.
مبنای کار در این پروژه، حل مسائل با دیدگاه دوم است. واضح است که با اندکی تغییر راه کار مورد استفاده در این پروژه برای دیدگاه اول نیز قابل اجرا خواهد بود، لذا در روند کار به منظور درک بهتر مسئله یا به کار گیری راه کار مناسبتر از مقالات حوزه اول نیز استفاده شده است.
بررسی الگوی اثر انگشت در سطوح متفاوت، انواع مختلفی از ویژگی ها را نشان میدهد که به طور کلی به سه دسته تقسیم میشود [1]:
ویژگی های سراسری:⁸ در بر گیرنده ساختار کلی تصویر می باشند. از آنجایی که اغلب پایگاه داده های اثرانگشت بسیار بزرگ است، بررسی تطبیق یک اثر انگشت خاص با تک تک آنها بسیار زمانبر و ناکار آمد است. در گذشته، هنری در [2] توانسته بود، دنباله کلی رگه های یک اثر انگشت را صرفا در چند کلاس طبقه بندی کند که مهم ترین و رایج ترین الگوها، نظیر حلقوی⁹،مارپیچی¹⁰و کمانی ¹¹در شکل زیر آمده است. با انجام این عمل در تصاویر خود دیگر نیازی به مقایسه با همه ی داده ها نمی باشد و صرفا به مجموعه ی داده های مربوط به یک کلاس خاص برای تطبیق مراجعه می شود.

چالش های زیادی در زمینه طبقه بندی تصاویر در این 5 کلاس وجود دارد که محققان را به ارائه روش هایی به منظور طبقه بندی هرچه بهتر تصاویر وا داشته است. لی و همکارانش در [3] به منظور کلاس بندی ¹²مناسبی از تصاویر براساس بردار ویژگی ها، از روشSVM ¹³ استفاده کرده اند که در کنار آن از الگوریتم های دیگر کلاس بندی برای بهبود پاسخ ها بهره گرفته شده است.
مشاهدات نشان داده است که در هر اثر انگشت یک یا دو ناحیه موجود است که در تصاویر، تراکم تکرار حلقوی رگه ها بیشتر است و این برجستگی ها در تصاویر به دو ویژگی سراسری به نام های نقاط منفرد حلقه ¹⁴ و دلتا¹⁵ (شکل زیر) تقسیم می شوند[2]. درحلقه، به شمالی ترین نقطه ی داخلی ترین رگه، هسته¹⁶گفته می شود که در مسائل امروزی بر اساس محل قرار گیری هسته ی حلقه و دلتا میتوان به نوع کلاس هر اثر انگشت پی برد.

چالش هایی نظیر چرخش تصویر و جابه جایی آن در این سطح بررسی می شوند.
ویژگی های محلی:¹⁷ در این سطح حدودا 150 ویژگی محلی، براساس اطلاعات محلی از الگوهای رگه ها استخراج می گردند که به آنها جزئیات کوچک ¹⁸می گویند.مهمترین ویژگی های محلی، نقاط انشعابی(دوشاخه)¹⁹ و نقاط پایانی ²⁰هستند که اصطلاحا به آنها مینوشیا²¹گفته می شود که در شکل زیر نشان داده شده است.

ویژگی های محلی نسبت به تبدیلات سراسری، پایدار می باشند و در مواردی که اطلاعات مربوط به ساختار کلی اثرانگشت وجود ندارد، مناسب هستند. تطبیق صرفا مبتنی بر مشخصه های محلی، تأثیر رابطه های مکانی ساختار سراسری را که بسیار متمایز کننده می باشد، کاهش می دهند. جیا و همکارش در [4] به دلیل ناقص بودن تصاویر جزئی اثرانگشت، به منظور تطبیق بخشی از تصویر اثرانگشت از اطلاعات مینوشیاهای اثرانگشت استفاده کرده اند که مستقل از ساختار سراسری و نقاط منفرد²² می باشند.
بر طبق تحقیقات چمپاد و همکارانش در [5] تراکم مینوشیاها در نواحی نقاط منفرد بیشتر است و از لحاظ آماری به طور متوسط 0.49 تراکم مینوشیاها در داخل ناحیه نقاط منفرد و 0.18 آنها بیرون این نواحی قرار گرفته اند.
سطح سومی نیز وجود دارد که مربوط به جزئیات داخلی رگه ها نظیر پهنا و انحنا است که با وجود احتیاج به وضوح بالا در تصاویر اثر انگشت چندادن کاربردی نمی باشند.

کارهای مرتبط

به منظور درک بیشتری از نتایج مقالات و تاثیرات آنها در بهبود تشخیص اثر انگشت، ابتدا توضیحات کوتاهی در مورد روند کلی کار داده می شود و سپس به بررسی روش های مقالات مرتبط می پردازیم.
تطبیق اثر انگشت در دو روش کلی طبقه بندی میشود :
تطبیق مبتنی بر مینوشیا: اطلاعات مینوشیا(نقاط انشعابی و پایانی) از تصاویر استخراج می شود و به صورت مجموعه ای از نقاط دو بعدی به عنوان قالب ²³ذخیره می شوند. سپس براساس مقایسه فاصله بین مجموعه مینوشیاهای تصویر ورودی و مینوشیاهای قالب های مختلف، بیشترین جفت تعداد مینوشیای مشابه یافت میشود و به عنوان نتیجه عملیات انطباق برگردانده می شود.
تطبیق مبتنی بر ویژگی های غیر مینوشیا: استخراج اطلاعات مینوشیا در تصاویر با کیفیت پایین دشوار است و یکی از چالش های عمده این روش به حساب می آید، در حالیکه ویژگی های دیگری که ارتباطی با نقاط مینوشیا ندارند، نظیر اطلاعات بافت، تعداد نوع و محل نقاط منفرد، شکل رگه ها و ویژگی های هندسی به آسانی و با قابلیت اطمینان بالایی از تصویر استخراج می شوند. این روش در حالت هایی که سطح سنسور اثرانگشت کوچک است، بهتر از الگوریتم های مبتنی بر مینوشیا عمل می کند، زیرا در این حالت صرفا 4-5 مینوشیا ممکن است در تصویر موجود باشد، بنابراین الگوریتم های میتنی بر مینوشیا عملکرد مناسبی نخواهند داشت. برای مثال ویلیس و میرز در مقاله خود [6]، روشی را براساس انتقال اطلاعات بافت کلی و محلی به حوزه فرکانس به منظور تشخیص اثر انگشت در تصاویر آسیب دیده معرفی می کنند. میدانیم که برخی اطلاعات در بافت کلی²⁴ از بین می رود، بعلاوه بیشتر اطلاعات بافت محلی²⁵ شامل جهت و فرکانس تصویر هستند. بنابراین [7][8] چندین رویه برای یافتن میزان تشابه براساس همبستگی بین جهت های رگه ها در دو تصویر مورد آزمایش پیشنهاد کرده اند.

دراین پروژه تصمیم برآن است که از یکی از روش های مبتنی بر مینوشیا برای احراز هویت اثر انگشت استفاده شود که غالبا تمامی روش ها روند زیر را دنبال می کنند:[13][1]:

1. دریافت تصاویر، تخمین جهت و استخراج رگه

2. باینری کردن تصویر²⁶

3. نازک سازی و تبدیل به تصویر اسکلتی²⁷

4. بهبود تصویر اسکلتی

5. استخراج مینوشیا

6. پس پردازش

7. تطبیق و محاسبه امتیاز شباهت

در ادامه به شرح مراحل و بررسی روش های مقالات مرتبط می پردازیم:
1) دریافت تصاویر، تخمین جهت و استخراج رگه:
به طور کلی تصاویر اثر انگشت به دو دسته off-line و Live-scan تقسیم میشوند که به تصویر اثرانگشت به روش سنتی یعنی جوهر و کاغذ، off-line و به تصویر حاصل از سنسورهای اثرانگشت، Live-scan گفته می شود. کلیات این بخش در قسمت های قبلی توضیح داده شد و جزئیات دیگر از حوزه کار ما خارج است [1].
2) باینری کردن تصویر
با استفاده از تصویر خاکستری²⁸ اثرانگشت مورد نظر، می توان آن را به یک تصویر باینری تبدیل کرد. در این قسمت می توان با استفاده از آستانه، پیکسل هایی که سطح خاکستری آنها از حد آستانه پایین تر است را به 0 و بزرگتر از آن را به 1 نظیر کرد [9].
3) نازک سازی و تبدیل به تصویر اسکلتی
به منظور کاهش پهنای رگه ها به یک پیکسل از الگوریتم های نازک سازی استفاده می شود. تصویر اسکلتی اثر انگشت با استفاده از الگوریتم نازک سازی حاصل می شود. این الگوریتم با روش تکراری تحت شرایط زیر، نقاط مرزی رگه های تصویر اثرانگشت را حذف می کند[10]:
الف) نقاط پایانی حذف نشوند.
ب) اتصالات قطع نشوند.
ج) باعث سایش بیش ازحد نشود.
تصویر باینری اثرانگشت دارای مقدار صفر برای شیارها و مقدار یک برای رگه های تصویر می باشد. نازک سازی شامل تکرار مراحل زیر می باشد:

1. تعیین نقاط مرزی جهت حذف

2. حذف نقاط تعیین شده

3. تعیین نقاط غیرمرزی جهت حذف

4. حذف نقاط تعیین شده
   تکرار تا جایی انجام می گیرد که دیگر نتوان نقطه ای را حذف کرد.
   مرحله 1: تعیین نقاط مرزی بر اساس همسایگی هشت گانه انجام می گیرد.هر نقطه P1 از تصویر که دارای شرایط زیر باشد، برای حذف شدن علامت می خورد:
   الف)

   2<=N(P1)<=6
   
   ب)
   S(P1)=1
   
   ج)
   P2,P4,P6=0
   د)
   p4,p6,p8=0

که N(P1) تعداد همسایه های غیر صفر p1 می باشد و S(P1) تعداد تغییر حالت از صفر به یک در دنباله مرتب P9,…P3,P2 می باشد.

مرحله یک در تمام پیشکل های مرزی تصویر اجرا می شود، اگر تمام شرایط الف تا د در پیکسلی از تصویر برقرار نباشد، آن پیکسل جهت حذف علامت میخورد، اما تا پایان پردازش تمام نقاط مرزی، حذف نمی شوند.
سپس مرحله 3، جهت تعیین پیکسل های غیر مرزی تحت شرایط زیر انجام می گیرد:

الف)

ب)
ج)د)
حذف پیکسل های تعیین شده، بعد از پردازش تمام پیکسل ها انجام می شود[10].
4) بهبود تصویر اسکلتی
تصویر اسکلتی حاصل ممکن است دارای نویز و یا شکستگی باشد. وجود پیکسل های منفرد در پیش زمینه و اتصالات کوتاه بین رگه ها، موسوم به پیکسل های متصل [12]H و رگه های کوتاه در تصویر اسکلتی اثرانگشت، منجر به ایجاد مینوشیای نادرست در تصویر (شکل زیر)می شوند، بنابراین باید حذف گردند.
در این پروژه برای حذف موارد ذکر شده و بهبود تصویر اسکلتی به دست آمده، از عملگرهای مورفولوژی بهره گیری خواهد شد.

5) استخراج مینوشیا
استخراج مینوشیا از تصویر اسکلتی، با استفاده از تحلیل پیکسل های همسایگی هر نقطه انجام می گیرد. اگر N8 همسایگی 8 پیکسل ها را نشان دهد، برای نقاط پایانی و انشعابی داریم :
نقاط پایانی: N8=1
نقاط انشعابی: N8>2
به این ترتیب مینوشیا از تصویر اسکلتی، استخراج می گردند. جهت مینوشیا با استفاده از اطلاعات پیکسل های مجاور تعیین می شود. هر مینوشیا به صورت بردار چهاری تایی زیر در نظر گرفته می شود که پارامترها به ترتیب بیانگر مختصات مکانی مشخصه، نوع مشخصه و جهت مینوشیا در تصویر را مشخص می کنند.
6) پس پردازش
پس پردازش عبارت است از تعیین مینوشیاهای درست و حذف مینوشیای نادرست اثرانگشت. بهبود تصویر اسکلتی تا حدودی از ایجاد مینوشیای نادرست جلوگیری می کند، با این وجود ممکن است در تصویر مینوشیای نادرست وجود داشته باشند.معروف ترین ساختار مینوشیای نادرست در یک تصویر اسکلتی در شکل زیر آورده شده است.

ژاو و تانگ در [11] به بحث این مسئله پرداختند که از آنجایی که بسیاری از مینوشیا نادرست²⁹ ها، دارای حداقل یکی از ساختارهای بالا هستند، کافی است نقاط H شناسایی و حذف شوند. در این صورت بسیاری از مینوشیا نادرست ها از بین می روند. بدین منظور در ابتدا به جای استفاده از رگه ها از خطوط سفید در تصویر اثرانگشت که اصطلاحا valley نامیده میشوند، به منظور نازک سازی برای استخراج مینوشیای اثر انگشت استفاده کردند. سپس الگوریتم معرفی شده با استفاده از Rutovitz Crossing Number حداکثر تعداد مینوشیای موجود در تصویر اسکلتی را شناسایی می کند. این شرایط به به حفظ مینوشیا درست ها و از بین بردن مینوشیا نادرست ها در مرحله پس پردازش کمک می کند. در انتها با استفاده از خاصیت دوگانگی ذاتی تصاویر اثرانگشت [1]، چندین تکنیک پس پردازش را معرفی نموده که به صورت قابل ملاحظه ای در پاک کردن مینوشیاهای جعلی موثر واقع شده است.
منسوخانی و همکارانش در [12] به ارائه روشی پرداختند که برای حذف مینوشیا نادرست ها از سیستم تطابق مبتنی بر SVM دو کلاسه استفاده می کند. در این روش از ویژگی های ترکیبی اثرانگشت استفاده شده است که بالقوه تعداد مینوشیا نادرست های تطبیق داده شده را 19% کاهش می دهد. البته در 5% موارد نیز این روش نمی تواند دو اثر انگشت یکسان را تطابق دهد. بعلاوه براساس طرحی دیگر به امتیاز دهی می پردازد و کارامدی الگوریتم خود را در کاهش نرخ خطا بررسی می کند.
روشی که توسط مینا عبدوس و ناصر مزینی در [13] برای تعیین مینوشیای نادرست بررسی شد، به این صورت است که ابتدا لیستی از دو مینوشیا که فاصله نسبی آنها از حد آستانه کمتر است، مشخص می گردد. این مینوشیاها علامت می خورند و با توجه به نوع آنها به یکی از سه گروه زیر تعلق می یابند:
1- مینوشیای پایانی-دوشاخه: یکی از مینوشیاها نقطه پایانی و دیگری نقطه دوشاخه باشد، در این صورت چنانچه هر دو متعلق به یک رگه باشند، حذف
می گردند .(شکل بالا.الف).
2- مینوشیای دوشاخه-دوشاخه: هر دو مشخصه نقاط دوشاخه باشند، در این صورت چنانچه هر دو متعلق به یک رگه باشند، حذف می گردند(شکل بالا. ب
و ج)
3- مینوشیای پایانی-پایانی: هر دو مشخصه نقاط پایانی باشند. در این صورت، دو حالت پیش می آید:
الف) هر دو مشخصه، متعلق به رگه باشند (شکل بالا.د). در این مورد، هر دومشخصه حذف می شوند.
ب) دو مشخصه، متعلق به رگه های متفاوت باشند (شکل بالا.ه). اگر این دو مشخصه باA و B نمایش داده شوند، در صورتی حذف می گردند که شرایط زیر برقرار باشد:

نقاط 'A و 'B به فاصله 5 پیکسل از A و B در نظر گرفته شده است. آلفا، عدد مثبت و کوچک در نظر گرفته شده است. این مینوشیاها حذف می گردند و در تصویر اسکلتی به یکدیگر متصل می گردند.

7) تطبیق
در تطبیق تصویر ورودی اول با دوم، با استفاده از اطلاعات جهت و اختلاف فاصله مکانی مینوشیا از دو مینوشیای مجاور[4][14]، تعدادی مینوشیای انطباق داده شده یافت می شود. سپس براساس فرمول زیر عددی به عنوان میزان تشابه دو تصویر به عنوان خروجی نمایش داده می شود. K برابر تعداد مینوشیاهای انطباق داده شده و مخرج برابر متوسط مجموع مینوشیاهای دو تصویر است.

تطبیق اثرانگشت با استفاده از اطلاعات بخشی از اثرانگشت، امروزه یکی از مهم ترین چالش های اثرانگشت می باشد، به ویژه هنگامی که تصویر فاقد اطلاعات ساختاری نقاط منفرد حلقه و دلتا باشد. در [13]، روشی برای تطبیق بخشی از اثرانگشت و مستقل از نقاط منفرد حلقه و دلتا، معرفی شده است که در آن از ویژگی ترکیبی تعداد رگه ها و راستای آنها بین نقاط مینوشیا که با استفاده از اطلاعات مینوشیای تصویر حاصل می شود، استفاده می کند و در انتها از خطای FAR به منظور ارزیابی روش معرفی شده استفاده شده است.
در این بخش به بررسی اجمالی تحقیقاتی که با هدف بهبود تشخیص اثر انگشت ارائه شده اند، پرداختیم. جزئیات روش انتخابی در این پروژه، پس از به تایید رسیدن در آزمایشگاه دکتر آنالویی و در مرحله پیاده سازی و آزمایش شرح داده خواهد شد.

آزمایش‌ها

استخراج مینوشیای قابل اعتماد و صحیح در تصاویر اثرانگشت از مسائل پراهمیت در تطبیق اثر انگشت میباشد بنابراین کیفیت تصاویر ورودی نقش مهمی را در میزان کارایی الگوریتم های تشخیص اتوماتیک اثر انگشت ایفا می کنند. در این پروژه الگوریتم سریعی برای بهبود تصویر و استخراج مینوشیا بر پایه جهت و فرکانس رگه های محلی پیاده سازی شده است که موجب بهبود وضوح ساختار رگه ها در تصاویر اثرانگشت ورودی شده و در نتیجه به استخراج مینوشیای درست کمک می کند.
روند کلی عملیات پیاده سازی به شرح زیر است :

1. پیش پردازش ³⁰
   1.1.بهبود تصویر³¹
   1.1.1. معادل سازی هیستوگرام³²
   1.1.2تبدیل فوریه ³³
   1.2.باینری کردن ³⁴
   1.3.بخش بندی تصویر³⁵
   1.3.1. تخمین جهت بلاک³⁶
   1.3.2. استخراج نواحی ROI براساس عملگرهای مورفولوژی³⁷

2. استخراج مینوشیا³⁸
   2.1.نازک سازی³⁹
   2.2.علامت گذاری مینوشیا⁴⁰

3. پس پردازش⁴¹
   3.1.حذف مینوشیاهای نادرست⁴²

4. تطبیق اطلاعات مینوشیای دو تصویر اثر انگشت⁴³

تصویر زیر فضای اولیه کاری را نشان میدهد که تمامی دکمه های آن به ترتیب مراحل مختلف بالا را انجام می دهند. دو ناحیه سفید هم به ترتیب از چپ به راست، وضعیت قبل و بعد از انجام هر مرحله از عملیات را نشان می دهند.

همانطور که در بخش قبلی گفته شد، پس از دریافت تصویر درابتدا، پیش پردازش انجام می شود که شامل زیربخش های بهبود کیفی تصویر و باینری کردن تصاویر می باشد. در اینجا از معادلسازی هیستوگرام و تبدیل فوریه به منظور بهبود کیفیت تصویر استفاده می شود. سپس با استفاده از رویه آستانه تطبیقی محلی ⁴⁴باینری می شود .[15]
معادلسازی هیستوگرام : توزیع مقداری پیکسل های تصویر را گسترش می دهد، بنابراین اطلاعات ادراکی از آن افزایش می یابد. در شکل زیر (1) هیستوگرام اصلی و (2) هیستوگرام معادلسازی شده را نشان می دهد.

در تصویر زیر، شکل سمت راست خروجی تصویر را بعد از اعمال معادلسازی هیستوگرام نشان می دهد.

تبدیل فوریه(FFT) : در ابتدا تصویر به بلاک های پردازشی کوچکی (3232 پیکسل) تقسیم شده و تبدیل فوریه اعمال می شود.
شکل زیر تصویر اثرانگشت را بعد از اعمال FFT نشان می دهد.

باینری کردن: تصاویر خاکستری موجود با 256 سطح را به تصویر 2 سطحی تبدیل می کند که حاوی همان اطلاعات اند و سپس بسته به برچسب هر پیکسل رنگ سیاه را برای 2فر و رنگ سفید را برای یک به طور معمول در نظر می گیرند.
از رویه باینری سازی تطبیقی محلی بدین منظور استفاده شده است. در این روش، تصویر به بلاک های 1616 تقسیم شده و یک مقدار متوسط شدت روشنایی برای هر بلاک محاسبه می شود. سپس مقدار هر پیکسلی که بیشتر از مقدار متوسط محاسبه شده در بلاک خودش باشد، به 1 تبدیل می شود و به ازای مقادیر کمتر از آن با 0 جایگزین می شود.

بخش بندی تصویر اثرانگشت: در حالت کلی، صرفا نواحی مورد علاقه (ROI) به تشخیص اثر انگشت کمک می کنند.ابتدا نواحی بدون رگه های موثر حذف می شوند زیر صرفا شامل اطلاعات پس زمینه و یا نویز می باشند. به منظور استخراج ROI، یک روش دو مرحله ای وجود دارد. قدم اول تخمین جهت بلاک هاست و قدم دوم اعمال برخی عملگرهای مورفولوژی است. [16]
تخمین حهت بلاک: الگوریتم تخمین جهت بلاک به صورت زیر انجام می شود:
• محاسبه مقدار گرادیان در طول محور افقی(gx)و محور عمودی برای هر پیکسل از بلاک(gy). از دو فیلتر سوبل ⁴⁵به منظور انجام این وظیفه استفاده شده است.
• در هر بلاک ، از فرمول زیر به منظور یافتن حداقل تقریبی از جهت بلاک استفاده می شود:
بنابراین به سادگی مقدار تانژانت جهت بلاک تقریبا مشابه فرمول زیر محاسبه می شود:

• بعد از تخمین جهت هر بلاک، بلاک هایی که حاوی اطلاعات مهمی نیستند (فاقد رگه می باشند) براساس فرمول زیر حذف می شوند:

برای هر بلاک، اگر مقدار E کمتر از حد آستانه باشد، آن بلاک به عنوان بلاک پس زمینه و بی اهمیت در نظر گرفته می شود.
شکل زیر، نقشه ی جهات را نشان می دهد.

استخراج نواحی ROI براساس عملگرهای مورفولوژی:
در اینجا از دو عملگر مورفولوژی به نام های باز⁴⁶ و بسته ⁴⁷استفاده شده است که به ترتیب اولی اتصالات باریک تصویر را حذف کرده و تصویری آرام تر می دهد و دومی نیز به منظور پر کردن حفره های تصویر استفاده می شود.
شکل زیر ناحیه ی ROI و حدود آن را نشان می دهد.

در مرحله استخراج مینوشیا، سه الگوریتم نازک سازی مورد آزمایش قرار گرفت [15][17] که در یک انتها الگوریتم نازک سازی موازی تکرار شونده به عنوان کارمدترین آنها انتخاب شد. الگوریتم، در هر بار اسکن کل تصویر، پیکسل های زائد را در هر پنجره کوچک 33 علامت می زند و نهایتا پس از چندین بار اسکن تمامی آن پیکسل های علامت خورده شده را حذف می کند.
سپس نقشه رگه های نازک شده ، با سایر عملگرهای مورفولوژی به منظور حذف شکستگی های H ⁴⁸، نقاط مجرد⁴⁹ و تیز⁵⁰فیلتر می شود. در این مرحله ، تمامی نقاط منفرد به عنوان نویز در نظرگرفته شده و حذف می شوند.

علامت گذاری مینوشیاهای تصویر: در حالت کلی، اگر در هر پنجره 33، پیکسل میانی یک و دقیقا سه همسایه با مقدار یک داشته باشد، بنابراین پیکسل میانی نقطه انشعابی است(شکل سمت چپ). اگر پیکسل میانی یک باشد و صرفا یک همسایه با مقدار یک داشته باشد، بنابراین پیکسل مرکزی نقطه پایانی خواهد بود(شکل سمت راست).

شکل زیر مینوشیاهای یافت شده را در خروجی نمایش می دهد.

در مرحله پس پردازش، از الگوریتم به کار رفته در [15] به منظور از بین بردن مینوشیاهای نادرست که نمونه های آن در بخش قبلی ذکر شده، استفاده شده است.
پردازش حذف مینوشیاهای نادرست به صورت زیر انجام می شود:

1. اگر فاصله ی بین یک نقطه انشعابی و یک نقطه ی پایانی کمتر از D باشد، بنابراین دو مینوشیا متعلق به یک رگه هستند. بنابراین هر دو حذف می شوند. D متوسط پهنای رگه داخلی است که متوسط فاصله بین دو رگه همسایه موازی را نشان می دهد.

2. اگر فاصله بین دو نقطه انشعابی کمتر از D باشد و هر دو در یک رگه باشند، هر دو انشعاب حذف می شوند.

3. اگر دو نقطه پایانی در یک رگه کوچک با طول کمتر از D باشد، هر دو نقطه پایانی حذف می شوند.

در انتهای این مرحله تعداد مینوشیاهای نادرست به صورت چشمگیری کاهش میابد .

حال صرفا ، اطلاعات مینوشیاهای استخراج شده در غالب فایل .dat ذخیره می شود. بنابراین به منظور تطبیق دو اثر انگشت کافی است مراحل قبلی را برای هر کدام انجام داده و با ذخیره اطلاعات مینوشیاها، از آنها در مرحله نهایی برای تطبیق استفاده می شود.

تطبیق اثرانگشت:
دکمه آخر موجود در برنامه، مربوط به عملیات تطبیق است. در این قسمت دو دسته مینوشیا از دو تصویر اثرانگشت که در مرحله قبل ذخیره شده است، دریافت می شود و سپس الگوریتم تطبیق مینوشیاها تصمیم میگیرد که آیا آن دو دسته مینوشیا مربوط به تصویر یکسانی از اثرانگشت هستند یا خیر.
در مرحله تطبیق مینوشیا، هر دو مینوشیا به عنوان جفت مینوشیای اصلی انتخاب شده و سپس لبه های همراه آنها انطباق داده می شود. اگر رگه ها به خوبی منطبق شوند، دو تصویر اثرانگشت معادلند و تطبیق برای همه ی مینوشیاهای باقیمانده انجام می شود.
1)مرحله ترازکردن: یک یمنوشیا به دلخواه در هر تصویر انتخاب می شود و به عنوان جفت مینوشیای اصلی انتخاب شده و سپس میزان شباهت دو رگه همراه آن نقاط محاسبه می شود.اگر میزان شباهت از حد آستانه بیشتر باشد، هر دسته مینوشیا به یک سیستم هماهنگ جدیدی تبدیل می شود که آن نقاط، نقاط مرجع آن هستند.
پس از دریافت دو دسته نقاط مینوشیا، از یک الگوریتم ارتجاعی تطبیق به منظور شمارش جفت مینوشیای منطبق استفاده شده است. ساختار این الگوریتم این گونه است که دو مینوشیایی که دارای مکان تقریبا مشابهی و جهت مشابهی هستند، یکسانند.
در نهایت ضریب تطبیقی برای دو تصویر اصرانگشت داده شده حاصل می شود که نسبت تعداد جفت مینوشیای تطبیق داده شده به کل مینوشیاهای تصویر است و در نهایت 100*ضریب به عنوان امتیاز که عددی بین 0 تا 100 می باشد نشان داده می شود.

اگر امتیاز کسب شده بیشتر از حد آستانه ی مشخص (که معمولا 80%است) باشد، دو اثرانگشت متعلق به یک انگشت خواهند بود و در نهایت تطابق یا عدم تطابق را به عنوان خروجی می دهد.
به منظور تست و بررسی کارایی پیاده سازی مذکور از پایگاه داده ی FVC2000 استفاده شده است.این پایگاه توسط مایو، مالتینو و سایر همکارانشان گرداوری شده است که شامل چندین تصویر اثر انگشت می شوند که آنهایی که دارای پیشوند یکسانی هستند متعلق به یک فرد می باشند. فرمت تمامی عکس ها tiff. می باشد.
کد در گیت هاب قرار داده شده است.

کارهای آینده

مراجع

[1] Maltoni, Davide et al. Handbook of fingerprint recognition. springer, 2009.
[2]Henry E., Classification and Uses of Finger Prints, Routledge, London, 1900.
[3]Li J., Yau W.Y. and Wang H., “Combining singular points and orientation image information for fingerprint classification,” Pattern Recognition, vol. 41, no. 1, pp. 353–366,2008
[4]T. Jea, and V. Govindaraju, "A Minutia-based partial fingerprint recognition system," Pattern Recognition, Vol.38, No. 10, pp. 1672-1684, 2005.
[5] Champod C., Lennard C.J., Margot P. and Stoilovic M., Fingerprints and Other Ridge Skin Impressions, CRC Press, Boca Raton, FL, 2004.
[6]Willis A.J. and Myers L., “A cost–-effective fingerprint recognition system for use with low-quality prints and damaged fingertips,” Pattern Recognition, vol. 34, no. 2, pp. 255–270, 2001
[7] Qi J. and Wang Y., “A robust fingerprint matching method,” Pattern Recognition,vol. 38, no. 10, pp. 1665–1671, 2005.
[8]Cheng J., Tian J. and Chen H., “Fingerprint Minutiae Matching with Orientation and Ridge,” in Proc. Int. Conf. on Biometric Authentication (1st), LNCS 3072, pp. 351–358, 2004
[9] Maio D. and Maltoni D., “Direct gray-scale minutiae detection in fingerprints,” IEEE Transactions on Pattern Analysis Machine Intelligence, vol. 19, no. 1, 1997.
[10]R. C. Gonzalez, and R. E. Woods, Digital Image Processing, Prentice Hall, Second Edition, 2002.
[11]Zhao F. and Tang X., “Preprocessing and postprocessing for skeleton-based fingerprint minutiae extraction,” Pattern Recognition, vol. 40, no. 4, pp. 1270–1281, 2007.
[12] Mansukhani P., Tulyakov S. and Govindaraju V.,“Using Support Vector Machines to Eliminate False Minutiae Matches During Fingerprint Verification,” in Proc. SPIE Conf. on Biometric Technology for Human Identification IV,2007
[13]م. عبدوس و ن. مزینی،" تطبیق بخشی از اثرانگشت با استفاده از ویژگی ترکیبی مبتنی بر مشخصه های اصلی"، نشریه علمی پژوهشی انجمن کامپیوتر ایران، مجلد 6،شماره 1 (الف)،1387
[14]T. Jea, and V. Govindaraju, "Partial FingerprintRecognition Based on Localized Features and Matching,"Proceedings of Biometric Consortium Conference, 2005.
[15] L.C. Jain, U.Halici, I. Hayashi, S.B. Lee and S.Tsutsui,' Intelligent biometric techniques in fingerprint and face recognition'. 1999, the CRC Press.
[16] N. Ratha, S. Chen and A.K. Jain, "Adaptive Flow Orientation Based Feature Extraction in Fingerprint Images", Pattern Recognition, Vol. 28, pp. 1657-1672, November 1995.
[17]D.Maio and D. Maltoni. Direct gray-scale minutiae detection in fingerprints. IEEE Trans. Pattern Anal. And Machine Intell., 19(1):27-40, 1997.

پیوندهای مفید

1. Biometric System Laboratory

2. Biometrics Research Group