هدف از انجام این پروژه طراحی و پیاده سازی یک سیستم است که تصویر دو اثر انگشت ورودی که برای احراز هویت به آن داده میشود را با هم مقایسه کرده و عددی را به عنوان میزان تشابه آن برگرداند. سپس برای پذیرش احراز هویت، یک آستانه را برای میزان شباهت تعیین کند که اگر میزان شباهت از آن مقدار بیشتر بود، سیستم آن مقایسه را به عنوان تطبیق بپذیرد و در غیر اینصورت آن را رد کند. این حد آستانه باید به گونه ای باشد که خطا روی پایگاه داده آزمون، کمترین میزان باشد. منظور از خطا، جمع مقدار FAR[^False Accept Rate] و FRR[^False Reject Rate] می‌باشد.
* برای دریافت داده‌های آموزش و آزمون لطفا به آزمایشگاه دکتر آنالویی مراجعه نمایید.
# مقدمه
با توجه به افزایش روزافزونِ اهمیت و کاربرد تشخیص هویت در دنیای امروزه،اهمیت روش های تشخیص هویت نیز روز به روز افزایش پیدا می کند.یکی از روش های تشخیص هویت،علم بیومتریک یا زیست سنجشی[^Biometric] است.در این علم سعی می شود با توجه به مشخصات رفتاری یا فیزیولوژی انسان،هویت او تعیین شود.تشخیص هویت از روی وزن،قد، اثر انگشت،صورت،شبکیه یا عنبیه چشم و هندسه دست نمونه هایی از تشخیص فیزیولوژی و شناسایی از طریق امضا،صدا،،نحوه راه رفتن[^ gait] و میزان فشار بر روی کیبرد هنگام تایپ کردن[^Keystroke] نمونه هایی از تشخیص رفتاری انسان است.حال به بررسی معایب و مزایای هر کدام از روش های فوق می پردازیم
به طور کلی الگوهای اصلی اثر انگشت به سه دسته کمانی[^Arch]، حلقه ای[^Loop] و مارپیچی[^whorl] تقسیم می شوند که شکل زیر نشان دهنده آنهاست:
توسط این الگو ها می توان خصوصیاتی از قبیل مینوشیا را دریافت نمود که در قسمت آزمایش ها توضیح خواهیم داد.
# کارهای مرتبط
در مقاله انطباق اثر انگشت خانم جین(مرجع شماره [2])،کمی در مورد تاریخچه تشخیص اثر انگشت صحبت می شود که قسمت هایی از آن در قسمت مقدمه آورده شده است.سپس در مورد الگوریتم های انطباق اثر انگشت صحبت می شود و دلایل استفاده بیشتر از روش مبتنی بر مینوشیا را توضیح می دهد.در این روش از ساختار محلی مینوشیا برای یافتن سریع یک انطباق نسبی بین دو نمونه اثر انگشت استفاده و از انطباق کامل دو نمونه اطمینان حاصل می شود.این الگوریتم شامل 4 مرحله است که توضیح این مراحل در بحث ما نمی گنجد.همانطور که در اول مطلب بیان شد،در این سیستم ها با دو نوع خطا مواجه هستیم:
خطای نوع اول FAR یا FMR[^False Match rate] نامیده می شود.تشخیص مثبت اشتباه زمانی رخ می دهد که سیستم برای بررسی یک اثر انگشت ثبت نشده،نتیجه مثبت(انطباق)را بازمی گرداند.
خطای نوع دوم FNR یا FNMR[^False non match Rate]نامیده می شود.تشخیص منفی اشتباه زمانی رخ می دهد که سیستم برای یک اثر انگشت ثبت شده،نتیجه منفی(تطابق اشتباه یا عدم تطابق)را باز می گرداند.در سیستم هایی که امنیت زیادی نیاز ندارند و سرعت بیشتر از امنیت اهمیت دارد،در اولویت اول سعی می شود FNMR کمتری نسبت به FMR داشته باشند.مثلا سیستم های مبتنی بر اثر انگشت مجموعه دیزنی،با نرخ بسیار پایین FNMR کار می کنند،اما در عوض نرخ FMR بالایی دارند.از سوی دیگر،سیستم تشخیص اثر انگشت یک عابربانک به کمترین نرخ FMR نیاز دارد در نتیجه FNMR بالایی خواهد داشت.
در نتیجه کاهش هم زمان نرخ هر دوی این خطاها غیر ممکن است و کاهش یکی از این خطاها با افزایش دیگری اتفاق می افتد.
----------
در مقاله خانم آرنتس (مرجع شماره [3])از یک شبکه عصبی Neocognitron برای تشخیص هویت استفاده شده است.همانطور که می دانید استفاده اصلی شبکه عصبی Neocognitron برای تشخیص دستخط است ولی می توان از محاسن این شبکه عصبی برای تشخیص هویت نیز استفاده کرد.در این مقاله نیز از استخراج مینوشیا استفاده شده است و نرخ تشخیص برای یک مسئله 8 کلاسه که هر کلاس از 20 نمونه تشکیل شده بالای 90% است
----------
در مقاله جین (مرجع شماره [8])در مورد امکان وجود تعداد بالای نمونه ها برای بررسی صحبت شده است و در آن به 70 میلیون اثر انگشت موجود در پایگاه داده FBI اشاره شده است.به همین دلیل نیاز به یک سیستم چند کاناله برای بررسی تشخیص هویت توسط اثر انگشت را بررسی می کند[2]
به طور کلی الگوهای اصلی اثر انگشت به سه دسته کمانی[^Arch]، حلقه ای[^Loop] و مارپیچی[^whorl] تقسیم می شوند که شکل زیر نشان دهنده آنهاست[1]:
توسط این الگو ها می توان خصوصیاتی از قبیل مینوشیا را دریافت نمود.در این روش از ساختار محلی مینوشیا برای یافتن سریع یک انطباق نسبی بین دو نمونه اثر انگشت استفاده و از انطباق کامل دو نمونه اطمینان حاصل می شود.
در این سیستم ها با دو نوع خطا مواجه هستیم:
خطای نوع اول FAR یا FMR[^False Match rate] نامیده می شود.تشخیص مثبت اشتباه زمانی رخ می دهد که سیستم برای بررسی یک اثر انگشت ثبت نشده،نتیجه مثبت(انطباق)را بازمی گرداند.
خطای نوع دوم FNR یا FNMR[^False non match Rate]نامیده می شود.تشخیص منفی اشتباه زمانی رخ می دهد که سیستم برای یک اثر انگشت ثبت شده،نتیجه منفی(تطابق اشتباه یا عدم تطابق)را باز می گرداند.در سیستم هایی که امنیت زیادی نیاز ندارند و سرعت بیشتر از امنیت اهمیت دارد،در اولویت اول سعی می شود FNMR کمتری نسبت به FMR داشته باشند.مثلا سیستم های مبتنی بر اثر انگشت مجموعه دیزنی،با نرخ بسیار پایین FNMR کار می کنند،اما در عوض نرخ FMR بالایی دارند.از سوی دیگر،سیستم تشخیص اثر انگشت یک عابربانک به کمترین نرخ FMR نیاز دارد در نتیجه FNMR بالایی خواهد داشت.
در نتیجه کاهش هم زمان نرخ هر دوی این خطاها غیر ممکن است و کاهش یکی از این خطاها با افزایش دیگری اتفاق می افتد.
# کارهای مرتبط
در شکل زیر،شمای کلی یک سیستم تشخیص اثر انگشت را مشاهده می کنید[2]
در مرحله ثبت اثر انگشت،اثر انگشت کاربر توسط حسگر اسکن شده و تبدیل به یک تصویر دیجیتال می شود.جدا کننده ی مینوشیا،تصویر اثر انگشت را برای تعیین جزئیات خاصی که به اصطلاح نقاط مینوشیا [^Minutiae Points]نامیده می شوند پردازش می کند.نقاط مینوشیا محل هایی را که خطوط اصطکاکی ناگهان قطع شده یا به دو یا چند شاخه تقسیم شده اند را مشخص می کند.
در مرجله تشخیص کاربر دوباره همان حسگر را لمس می کند و تصویر جدیدی از اثر انگشت ایجاد می شود.به این تصویر جدید، Query Print گفته می شود.نقاط مینوشیای این تصویر نیز استخراج شده و با نقاط مینوشیای نمونه های داخل پایگاه داده مقایسه می شود تا تعداد نقاط مینوشیا مشترک بدست آید.بدلیل تفاوت در نحوه قرارگیری انگشتان و میزان فشار،تصویر Query و تصویر درون پایگاه داده باید پیش از مقایسه رجیستر شوند.منظور از رچیستر انطباق 2 تصویر بر روی یکدیگر برای تطبیق جفت های مینوشیا های یکسان است.سپس واحد تطبیق تعداد جفت های یکسان دو نمونه را محاسبه می کند.منظور از جفت های یکسان نقاطی هستند که هم محل و هم جهت یکسانی داشته باشند.پس از این مرحله،هویت کاربر از طریق محاسبه امتیاز تطابق و مقایسه آن با میزان آستانه ای که مشخص شده است تشخیص داده می شود.
**استخراج خصوصیات**
با توجه به شکل،به طور کلی استخراج خصوصیات به 3 سطح تقسیم می شود.
مرحله نخست-شکل چپ،برداشت جزئیات مقیاس بزرگ نظیر شکل جریان خطوط اصطکاکی،الگوی اصلی خطوط و نقاط تکی خواهد بود.مرحله دوم به دو شاخگی[^bifurcation] و انتهای لبه [^Ending Ridge]مربوط است و مرحله سوم شامل تمام خصوصیات ابعادی اثر انگشت مانند ضخامت خطوط،شکل آنها و آثار زخم و بریدگی است.
از خصوصیات به دست آمده در مرجله اول می توان برای تقسیم بندی آٍثار انگشت به دسته هایی با الگو های فرمی کمانی،حلقه ای و یا مارپیچی استفاده کرد.در مورد این الگو ها قبلا توضیح داده شده است.
شکل زیر یک الگوریتم استخراج مینوشیا را نشان می دهد
این الگوریتم نخست از روی شکل،جهت خطوط و میزان تکرار آنها را مشخص می کند.و توسط فیلتر براساس زمینه [^contextual filtering] کیفیت را بهبود داده و استخراج خطوط را آسان می کند. پس از بهبود تصویر،اسکلت های اصلی خطوط اصطکاکی استخراج شده و در نهایت الگوریتم برای شناسایی و حذف مینوشیا های اشتباه از یک هیوریستیگ استفاده می کند سپس فاز انطباق آغاز می شود .
**مرحله انطباق**
همانطور که توضیح داده شد،در این مرحله امتیازی برای تطبیق دو اثر انگشت محاسبه می شود.یکی از مشکل ترین قسمت های احراز هویت توسط اثر انگشت این قسمت است.زیرا تفاوت های درون کلاسی [^Interclass Variation] که تفاوت بین تصاویر مختلف یک اثر انگشت را نشان می دهد و شباهت های مابین کلاس ها [^Interclass Similarity] در اثر انگشت زیاد است.مثلا میزان فشار انگشت و نحوه قرار گیری و چرخش انگشت بر روی تفاوت های درون کلاسی تاثیر می گذارد همینطور وجود تنها 3 مدل کلی الگو های اثر انگشت(کمانی،حلقه ای و مارپیچ)باعث ایجاد شباهت میان گروه های مختلف می شود.در شکل زیر نحوه چگونگی انطباق توضیح داده شده است:
----------
یک روش دیگر برای تشخیص اثر انگشت،استفاده از شبکه های عصبی است[3].در مقاله خانم آرنتس از یک شبکه عصبی Neocognitron برای تشخیص هویت استفاده شده است.همانطور که می دانید استفاده اصلی شبکه عصبی Neocognitron برای تشخیص دستخط است ولی می توان از محاسن این شبکه عصبی برای تشخیص هویت نیز استفاده کرد.در این روش فقط از دو نوع انتهای لبه و دوشاخگی به عنوان مینوشیا استفاده می شود.شکل زیر مثالی از این نوع مینوشیا هاست
در این روش از 4 فاز زیر برای کلاسبندی مینوشیا استفاده می شود:
1. دریافت عکس[^Image Acquisition]
2. پیش پردازش عکس[^pre-processing]
3. استخراج مینوشیا [^minutiae Extractor]
4. تشخیص مینوشیا [^Minutiae Recognition]
پس از اجرای فاز اول که توسط سنسور ها انجام می پذیرد،نوبت به پیش پردازش عکس می رسد،این مرحله خود در 3 فاز اجرا می شود.شکل زیر نشان دهنده این 3 فاز است :
در اولین مرحله،پس از دریافت عکس حذف سایه ها اتفاق میافتد.سپس باینری کردن عکس ها انجام می شود.در این عکس با استفاده از تصویر خاکستری(در این نوع عکس هر پیکسل با عددی بین 0 تا 255 که نشان دهنده میزان خاکستری بودن پیکسل است نمایش داده می شود)،تصویری سیاه سفید(اصطلاحا تصویر باینری)بدست می آید.در این روش با قرار دادن مقدار 0 برای پیکسل هایی با مقدار خاکستری کمتر از 128 و 1 برای مقادیر خاکستری برابر یا بیشتر از 128 عکس خاکستری تبدیل به عکس سیاه سفید می شود.پس از بدست آمدن تصویر باینری،نوبت به نازک کردن[^thinning] لبه ها می رسد.شکل زیر تصویر پس از پیش پردازش را نمایش می دهد:
پس از اتمام پیش پردازش عکس ها،نوبت به استخراج مینوشیا می رسد.در این فاز، یک فضای 15*15 پیکسلی که حاوی یک مینوشیا است به 8 کلاس زیر تقسیم شده است:
فضای به دست آمده به عنوان ورودی پترن برای نئوکوگنیترون[^Neocognitron] استفاده می شود.لازم به ذکر است که در هر عکس مابین 40 تا 100 مینوشیا موجود است که تعداد آن به کیفیت عکس و سایز سنسور و... مربوط است.سپس نوبت به کلاس بندی می رسد،برای کلاس بندی از 2 شبکه به نام های شبکه کنترل[^Control network] و شبکه شناسایی[^Recognition Network] استفاده می شود.کنترل شبکه از چند مرحله تشکیل داده شده است که هر مرحله وظیفه تشخیص لبه، خط و نقطه پایانی را دارد. در شبکه کنترل به ازای هر کلاس مینوشیا 20 نمونه برای آموزش داده می شود.پس از آموزش، خروجی این شبکه،به عنوان ورودی برای شبکه شناسایی استفاده می شود.شبکه شناسایی از سه لایه تشکیل داده شده است: US3, UC3, US4, UC4, US5, UC5که شماره هر لایه به عنوان حرف سوم لایه بیان شده.پس از آموزش بدون ناظر،سلول های S ویژگی ها را استخراج می کند و سلول های C نتیجه نهایی تشخیص را می دهد.شکل زیر،ساختار این شبکه ها را نمایش می دهد.
شکل زیر نمای کلی پردازش نکوگنیترون را نمایش می دهد.در مرحله نخست عکس ورودی داده می شود،در مرحله دوم و سوم لبه ها تشخیص داده شده است.در مرحله 4 ،جهت خطوط و در مرحله 5 ،خطوط پایانی تشخیص داده می شود.در مرحله 6 ،ترکیب ویژگی ها شناسایی می شود و در مرحله آخر نیز کلاس مینوشیا مشخص می شود.این روال برای تمام بلوک های 15 در 15 پیکسلی سنسور ها که ابعاد 256 در 256پیکسلی دارند انجام می شود.اگر یک مینوشیا شناسایی شود،موقعیت x,y آن مینوشیا به همراه نوع مینوشیای آن ذخیره می شود.تمام مینوشیا های یک اثر انگشت در یک ساختمان داده ذخیره می شود و از این طریق می توان تشخیص هویت را انجام داد.
این فرآیند زمانبر است.به خصوص اگر سایز سنسور بزرگ باشد.
با توجه با مسائلی که مطرح شد،دو سوال مطرح می شود:
سوال اول- با توجه به اینکه روند تشخیص هویت بر اساس اثر انگشت روندی بسیار طولانی و زمانبری است،اگر تعداد اثر انگشت ها در پایگاه داده زیاد باشد،با روش های عادی هم زمان تشخیص بیش از حد طولانی خواهد شد و هم نیازمند دقت بسیار بالایی هستیم.آقای جین [8]روشی را برای آن ارائه داده است که در زیر به شرح آن خواهیم پرداخت:
در این حالت،به جای استفاده از یک دسته بند [^classifier]از 2 دسته بند استفاده می کنیم.دسته بند اول با سرعت زیاد و با دقت پایین تر عمل می کند.برای این منظور از یک دسته بند KNN[^K Nearest Neighborhood] استفاده می کنیم که در آن k=10 است.به این معنا که توسط 10 نزدیکترین همسایه،دسته بند به ما 2 دسته با بالاترین احتمال را می دهد.طبق مشاهدات به احتمال 85.4% دسته با بیشترین همسایه،دسته واقعی مورد نظر ماست و به احتمال 12.6 % دومین دسته با بیشترین همسایه،دسته واقعی ماست.در نتیجه KNN ما دو دسته که 98% دقت دارند را به ما اعلام می کند.وظیفه دسته بند دوم تشخیص اینکه کدام یک از دو دسته اعلام شده توسط KNN ،دسته درست است را برعهده دارد.دسته بند دوم از نوع شبکه عصبی با یک لایه مخفی 20 نرونی، و 192 نرون ورودی است و 5 نرون خروجی به عنوان 5 کلاس خروجی در نظر گرفته شده است. این روش بر روی پایگاه داده NIST-4 اجرا شده است .دقت 90 درصد برای 5 کلاس و دقت 94.5 درصد برای 4 کلاس به دست آمده است..با این حال،این الگوریتم باز هم نیاز به 10 ثانیه زمان دارد تا بتواند یک اثر انگشت اسکن شده را دسته بندی کند و از این نظر می تواند بهتر شود.
سوال دومی که ممکن است ایجاد شود این است که اگر تصویر اسکن شده اثرانگشتی که نیاز به دسته بندی دارد،کیفیت پایینی داشته باشد یا سنسور کیفیت مناسبی نداشته باشد یا فضای اسکن شده کم باشد چه کار می توان کرد؟
یکی از روش ها استفاده از ویژگی ترکیبی مبتنی بر مشخصه های اصلی [11]است.
در این روش به جای استفاده از مینوشیای اثر انگشت که نسبت به چرخش،خطای اسکنر،مکان قرارگیری انگشت بر روی اسکنر و نویز حساس است یا استفاده از ویژگی های سراسری مثل نقاط منفرد حلقه و دلتا[^delta] که ممکن است در بخش اسکن شده وجود نداشته باشد از ویژگی دیگری استفاده می شود:
روش پیشنهادی بر این اساس است که اگر حداقل قسمتی از تصویر اسکن شده با حداقل نویز باشد،در این قسمت مینوشیا ها را بدست آورده،سپس از تعداد رگه های بین دو مینوشیا و زاویه بین آن دو استفاده کنیم.این ویژگی ترکیبی در شکل زیر نمایش داده شده است:
در این روش اگه تعداد رگه های بین دو مینوشیا برابر RC باشد،RCزاویه خواهیم داشت (در شکل بالا 7 خط مشخص شده است پس 7 زاویه خواهیم داشت)پس به همراه خود مقدار RC تعداد ویژگی های ترکیبی برابر برابر RC+1 است.علاوه بر این مختصات دو مینوشیا نیز نیاز است پس برداری که ما به وسیله آن ویژگی ترکیبی را نشان می دهیم برابر است با:
حال سوال هایی که باقی می ماند چگونگی تخمین تعداد رگه و چگونگی پیدا کردن زاویه هاست
برای تخمین تعداد رگه بین دو نقطه A و Bاز 2 روش می توان استفاده کرد:
1. تخمین رگه توسط تعیین تعداد انتقال از صفر به یک در تصویر باینری
2. تعیین تعداد ماکسیموم های محلی بین A و B در تصویر خاکستری
در این روش از تصویر اسکلتی که از تصویر باینری به دست می آید استفاده می شود به این صورت که ناحیه بین a و b توسط یک ماسک 5*5 پیکسلی پیمایش می شود
برای تعیین زاویه نیز اگر o نقطه تلاقی رگهAB و خط m1m2 باشد با توجه به شکل زیر:
از فرمول زیر استفاده می شود:
برای تطبیق نیز فقط کافی است پس از هم تراز کردن تصویر نقاط مرجع شناسایی شده و سپس امتیاز شباهت حساب شود.
# آزمایش‌ها
# کارهای آینده
# مراجع
[1] Maltoni, Davide, et al. Handbook of fingerprint recognition. springer, 2009.
[2]Anil K. Jain, Jianjiang Feng, Karthik Nandakumar, "Fingerprint Matching", Computer, vol.43, February 2010
[3]Milene Arantes, Alessandro Noriaki Ide, Jose Hiroki Saito ,"A System For Fingerprint Minutiae Classification And Recognition"
[4]Tsai-Yang Jea, Venu Govindaraju,"A minutia-based partial fingerprint recognition system"
[5]Xudong Jiang*, Wei-Yun Yau, Wee Ser,"Detecting the fingerprint minutiae by adaptive tracing the gray-level ridge"
[6]Alessandro Farina, Zsolt M. Kovacss-vajna,Alberto Leone."Fingerprint minutiae extraction from skeletonized binary images"
[7]Andrew K . Hrechak and James A . McHugh,"Automated Fingerprint Recognition Using Structural Matching"
[8]Anil K. Jain,Salil Prabhakar, Lin Hong,"A Multichannel Approach to Fingerprint Classification"
[9]Anil K,Lin Hong."A personal Identification system using faces and fingerprints"
[10]D. K. Isenor and S. G. Zakyt."Fingerprint Identification Using Graph Matching"
[11]ناصر مزینی،منیره عبدوس"تطبیق بخشی از اثرانگشت با استفاده از ویژگی ترکیبی مبتنی بر مشخصه های اصلی"نشریه علمی پژوهشی انجمن کامپیوتر ایران،1387
# پیوندهای مفید
+ [Biometric System Laboratory](http://biolab.csr.unibo.it)
+ [Biometrics Research Group](http://biometrics.cse.msu.edu)