هدف از انجام این پروژه طراحی و پیاده سازی یک سیستم است که تصویر دو اثر انگشت ورودی که برای احراز هویت به آن داده میشود را با هم مقایسه کرده و عددی را به عنوان میزان تشابه آن برگرداند. سپس برای پذیرش احراز هویت، یک آستانه را برای میزان شباهت تعیین کند که اگر میزان شباهت از آن مقدار بیشتر بود، سیستم آن مقایسه را به عنوان تطبیق بپذیرد و در غیر اینصورت آن را رد کند. این حد آستانه باید به گونه ای باشد که خطا روی پایگاه داده آزمون، کمترین میزان باشد. منظور از خطا، جمع مقدار FAR[^False Accept Rate] و FRR[^False Reject Rate] می‌باشد.
* برای دریافت داده‌های آموزش و آزمون لطفا به آزمایشگاه دکتر آنالویی مراجعه نمایید.
# مقدمه
از دیر باز تشخیص هویت انسان امری حیاتی تلقی شده و بدین منظور راه کارهای مختلفی نظیر کارت شناسایی، پاسپورت و ... ارائه شده است که به علت جعل پذیری، گم شدن و سایر مشکلات آنها، از قابلیت اطمینان بالایی برخوردار نیستنید. بدین منظور در سالهای اخیر از تشخیص بیومتریک (زیست سنجی)[^Biometric] برای برطرف کردن نواقص راه حل های قدیمی استفاده شده است. بیومتریک به معنی تشخیص خودکار افراد براساس ویژگی های خاص رفتاری و بیولوژیک آنها نظیر چهره، اثر انگشت، عنبیه، صدا و مشخصات هندسی دست است که به آسانی قابل جعل نبوده و بنابراین میتوانند کارامدتر از روش های سنتی برای شناسایی افراد، افزایش امنیت، کاهش تخلفات و تسریع در امور روزمره به کار برده شوند.
به خطوط سر انگشتان رگه [^Ridge] گفته می شود. اثر انگشت افراد دارای الگوهایی از رگه هاست که در طول حیات فرد تغییرناپذیر بوده، مگر آنکه دچار سوختگی شدیدی شود. این امر، تشخیص هویت براساس اثر انگشت را به یکی از بیومتریک های رایج تبدیل کرده است که در این پروژه مشخصا به تشریح آن پرداخته خواهد شد.
در این حوزه مسائل با دو دیدگاه مطرح می شوند:
**• شناسایی هویت**:[^Identification] در این حالت تصویر ورودی با مجموعه ای از تصاویر ذخیره شده جهت جستجو، مقایسه شده و در صورت یافتن تصویر اثرانگشت مشابه، هویت آن را برمیگرداند.
**• تایید**:[^Verification] در این حالت دو تصویر ورودی به سیستم شناسایی اثر انگشت خودکار [^Automatic Fingerprint Identification Systems (AFIS)] داده می شود و با توجه میزان شباهت این دو تصویر عددی را برگردانده می شود . سپس براساس آستانه شباهت تعیین شده برای مسئله، سیستم پاسخ تایید تطبیق و یا رد در تطبیق را در خروجی نمایش می دهد.
مبنای کار در این پروژه، حل مسائل با دیدگاه دوم است. واضح است که با اندکی تغییر راه کار مورد استفاده در این پروژه برای دیدگاه اول نیز قابل اجرا خواهد بود، لذا در روند کار به منظور درک بهتر مسئله یا به کار گیری راه کار مناسبتر از مقالات حوزه اول نیز استفاده شده است.
# کارهای مرتبط
بررسی الگوی اثر انگشت در سطوح متفاوت، انواع مختلفی از ویژگی ها را نشان میدهد که به طور کلی به سه دسته تقسیم میشود [1]:
**ویژگی های سراسری**:[^Global Level] در بر گیرنده ساختار کلی تصویر می باشند. از آنجایی که اغلب پایگاه داده های اثرانگشت بسیار بزرگ است، بررسی تطبیق یک اثر انگشت خاص با تک تک آنها بسیار زمانبر و ناکار آمد است. در گذشته، هنری در [2] توانسته بود، دنباله کلی رگه های یک اثر انگشت را صرفا در چند کلاس طبقه بندی کند که مهم ترین و رایج ترین الگوها، نظیر حلقوی[^Left/Right loop]،مارپیچی[^Whorl]و کمانی [^Arch]در شکل زیر آمده است. با انجام این عمل در تصاویر خود دیگر نیازی به مقایسه با همه ی داده ها نمی باشد و صرفا به مجموعه ی داده های مربوط به یک کلاس خاص برای تطبیق مراجعه می شود.
چالش های زیادی در زمینه طبقه بندی تصاویر در این 5 کلاس وجود دارد که محققان را به ارائه روش هایی به منظور طبقه بندی هرچه بهتر تصاویر وا داشته است. لی و همکارانش در [3] به منظور کلاس بندی [^classifier]مناسبی از تصاویر براساس بردار ویژگی ها، از روشSVM [^Support Vector Machines] استفاده کرده اند که در کنار آن از الگوریتم های دیگر کلاس بندی برای بهبود پاسخ ها بهره گرفته شده است.
مشاهدات نشان داده است که در هر اثر انگشت یک یا دو ناحیه موجود است که در تصاویر، تراکم تکرار حلقوی رگه ها بیشتر است و این برجستگی ها در تصاویر به دو ویژگی سراسری به نام های نقاط منفرد حلقه [^loop] و دلتا[^Delta] (شکل زیر) تقسیم می شوند[2]. درحلقه، به شمالی ترین نقطه ی داخلی ترین رگه، هسته[^core]گفته می شود که در مسائل امروزی بر اساس محل قرار گیری هسته ی حلقه و دلتا میتوان به نوع کلاس هر اثر انگشت پی برد.
چالش هایی نظیر چرخش تصویر و جابه جایی آن در این سطح بررسی می شوند.
**ویژگی های محلی**:[^Local Level] در این سطح حدودا 150 ویژگی محلی، براساس اطلاعات محلی از الگوهای رگه ها استخراج می گردند که به آنها جزئیات کوچک [^Minute details]می گویند.مهمترین ویژگی های محلی، نقاط انشعابی(دوشاخه)[^bifurcation] و نقاط پایانی [^ending pioints]هستند که اصطلاحا به آنها مینوشیا[^Minutiae]گفته می شود که در شکل زیر نشان داده شده است.
ویژگی های محلی نسبت به تبدیلات سراسری، پایدار می باشند و در مواردی که اطلاعات مربوط به ساختار کلی اثرانگشت وجود ندارد، مناسب هستند. تطبیق صرفا مبتنی بر مشخصه های محلی، تأثیر رابطه های مکانی ساختار سراسری را که بسیار متمایز کننده می باشد، کاهش می دهند. جیا و همکارش در [4] به دلیل ناقص بودن تصاویر جزئی اثرانگشت، به منظور تطبیق بخشی از تصویر اثرانگشت از اطلاعات مینوشیاهای اثرانگشت استفاده کرده اند که مستقل از ساختار سراسری و نقاط منفرد[^Singular Points] می باشند.
بر طبق تحقیقات چمپاد و همکارانش در [5] تراکم مینوشیاها در نواحی نقاط منفرد بیشتر است و از لحاظ آماری به طور متوسط 0.49 تراکم مینوشیاها در داخل ناحیه نقاط منفرد و 0.18 آنها بیرون این نواحی قرار گرفته اند.
سطح سومی نیز وجود دارد که مربوط به جزئیات داخلی رگه ها نظیر پهنا و انحنا است که با وجود احتیاج به وضوح بالا در تصاویر اثر انگشت چندادن کاربردی نمی باشند.
# تطبیق اثرانگشت :
تطبیق اثر انگشت در دو روش کلی طبقه بندی میشود :
**تطبیق مبتنی بر مینوشیا**: اطلاعات مینوشیا(نقاط انشعابی و پایانی) از تصاویر استخراج می شود و به صورت مجموعه ای از نقاط دو بعدی به عنوان قالب [^template]ذخیره می شوند. سپس براساس مقایسه فاصله بین مجموعه مینوشیاهای تصویر ورودی و مینوشیاهای قالب های مختلف، بیشترین جفت تعداد مینوشیای مشابه یافت میشود و به عنوان نتیجه عملیات انطباق برگردانده می شود.
**تطبیق مبتنی بر ویژگی های غیر مینوشیا**: استخراج اطلاعات مینوشیا در تصاویر با کیفیت پایین دشوار است و یکی از چالش های عمده این روش به حساب می آید، در حالیکه ویژگی های دیگری که ارتباطی با نقاط مینوشیا ندارند، نظیر اطلاعات بافت، تعداد نوع و محل نقاط منفرد، شکل رگه ها و ویژگی های هندسی به آسانی و با قابلیت اطمینان بالایی از تصویر استخراج می شوند. این روش در حالت هایی که سطح سنسور اثرانگشت کوچک است، بهتر از الگوریتم های مبتنی بر مینوشیا عمل می کند، زیرا در این حالت صرفا 4-5 مینوشیا ممکن است در تصویر موجود باشد، بنابراین الگوریتم های میتنی بر مینوشیا عملکرد مناسبی نخواهند داشت. برای مثال ویلیس و میرز در مقاله خود [6]، روشی را براساس انتقال اطلاعات بافت کلی و محلی به حوزه فرکانس به منظور تشخیص اثر انگشت در تصاویر آسیب دیده معرفی می کنند. میدانیم که برخی اطلاعات در بافت کلی[^Global Texture] از بین می رود، بعلاوه بیشتر اطلاعات بافت محلی[^Local Texture] شامل جهت و فرکانس تصویر هستند. بنابراین [7][8] چندین رویه برای یافتن میزان تشابه براساس همبستگی بین جهت های رگه ها در دو تصویر مورد آزمایش پیشنهاد کرده اند.
دراین پروژه تصمیم برآن است که از روش مبتنی بر مینوشیا برای احراز هویت اثر انگشت استفاده شود. بدین منظور مراحل کلی روش انتخابی بدین شرح است :
1. دریافت تصاویر، تخمین جهت و استخراج رگه
2. باینری کردن تصویر
3. نازک سازی و تبدیل به تصویر اسکلتی
4. بهبود تصویر اسکلتی
5. استخراج مینوشیا
6. پس پردازش
7. تطبیق و محاسبه امتیاز شباهت
در ادامه به شرح مراحل و بررسی روش های مقالات مرتبط می پردازیم:
1) دریافت تصاویر، تخمین جهت و استخراج رگه:
به طور کلی تصاویر اثر انگشت به دو دسته off-line و Live-scan تقسیم میشوند که به تصویر اثرانگشت به روش سنتی یعنی جوهر و کاغذ، off-line و به تصویر حاصل از سنسورهای اثرانگشت، Live-scan گفته می شود. کلیات این بخش در قسمت های قبلی توضیح داده شد و جزئیات دیگر از حوزه کار ما خارج است [1].
2) باینری کردن تصویر
با استفاده از تصویر خاکستری[^Gray Scale] اثرانگشت مورد نظر، می توان آن را به یک تصویر باینری تبدیل کرد. در این قسمت می توان با استفاده از آستانه، پیکسل هایی که سطح خاکستری آنها از حد آستانه پایین تر است را به 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، جهت تعیین پیکسل های غیر مرزی تحت شرایط زیر انجام می گیرد:
الف) $$ 2<=N(P1)<=6$$
ب)$$ S(P1)=1$$
ج)$$P2,P4,P6=0 $$د)$$p2,p6,p8=0 $$
حذف پیکسل های تعیین شده، بعد از پردازش تمام پیکسل ها انجام می شود[10].
4) بهبود تصویر اسکلتی
تصویر اسکلتی حاصل ممکن است دارای نویز و یا شکستگی باشد. وجود پیکسل های منفرد در پیش زمینه و اتصالات کوتاه بین رگه ها، موسوم به پیکسل های متصل [12]H و رگه های کوتاه در تصویر اسکلتی اثرانگشت، منجر به ایجاد مینوشیای نادرست در تصویر (شکل زیر)می شوند، بنابراین باید حذف گردند.
در این پروژه برای حذف موارد ذکر شده و بهبود تصویر اسکلتی به دست آمده، از عملگرهای مورفولوژی بهره گیری خواهد شد.
5) استخراج مینوشیا
استخراج مینوشیا از تصویر اسکلتی، با استفاده از تحلیل پیکسل های همسایگی هر نقطه انجام می گیرد. اگر N8 همسایگی 8 پیکسل ها را نشان دهد، برای نقاط پایانی و انشعابی داریم :
نقاط پایانی: N8=1
نقاط انشعابی: N8>2
به این ترتیب مینوشیا از تصویر اسکلتی، استخراج می گردند. جهت مینوشیا با استفاده از اطلاعات پیکسل های مجاور تعیین می شود. هر مینوشیا به صورت بردار چهاری تایی زیر در نظر گرفته می شود که پارامترها به ترتیب بیانگر مختصات مکانی مشخصه، نوع مشخصه و جهت مینوشیا در تصویر را مشخص می کنند.
6) پس پردازش
پس پردازش عبارت است از تعیین مینوشیاهای درست و حذف مینوشیای نادرست اثرانگشت. بهبود تصویر اسکلتی تا حدودی از ایجاد مینوشیای نادرست جلوگیری می کند، با این وجود ممکن است در تصویر مینوشیای نادرست وجود داشته باشند.معروف ترین ساختار مینوشیای نادرست در یک تصویر اسکلتی در شکل زیر آورده شده است.
ژاو و تانگ در [11] به بحث این مسئله پرداختند که از آنجایی که بسیاری از مینوشیا نادرست[^False Minutiae] ها، دارای حداقل یکی از ساختارهای بالا هستند، کافی است نقاط 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 برابر تعداد مینوشیاهای انطباق داده شده و مخرج برابر متوسط مجموع مینوشیاهای دو تصویر است.
$$score=k/(n+m/2)$$
تطبیق اثرانگشت با استفاده از اطلاعات بخشی از اثرانگشت، امروزه یکی از مهم ترین چالش های اثرانگشت می باشد، به ویژه هنگامی که تصویر فاقد اطلاعات ساختاری نقاط منفرد حلقه و دلتا باشد. در [13]، روشی برای تطبیق بخشی از اثرانگشت و مستقل از نقاط منفرد حلقه و دلتا، معرفی شده است که در آن از ویژگی ترکیبی تعداد رگه ها و راستای آنها بین نقاط مینوشیا که با استفاده از اطلاعات مینوشیای تصویر حاصل می شود، استفاده می کند و در انتها از خطای FAR به منظور ارزیابی روش معرفی شده استفاده شده است.
در این بخش به بررسی اجمالی تحقیقاتی که با هدف بهبود تشخیص اثر انگشت ارائه شده اند، پرداختیم. جزئیات روش انتخابی در این پروژه، پس از به تایید رسیدن در آزمایشگاه دکتر آنالویی و در مرحله پیاده سازی و آزمایش شرح داده خواهد شد.
# آزمایش‌ها
# کارهای آینده
# مراجع
[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.
# پیوندهای مفید
1. [Biometric System Laboratory](http://biolab.csr.unibo.it)
2. [Biometrics Research Group](http://biometrics.cse.msu.edu)