Đồ án Giải pháp xác thực cho Kiosk giao dịch và tra cứu thông tin cho Ngân Hàng Công Thương Việt Nam

ợc xác thực bởi hệ thống, còn khi người sử dụng không biết mình đang được xác thực bởi hệ thống thì hệ thống là bí mật. + Thường xuyên và không thường xuyên: chỉ mức độ thường xuyên mà người dùng sử dụng hệ thống sinh trắc. Ví dụ, ứng dụng đăng nhập máy tính là một hệ thống sinh trắc thường xuyên bởi vì ứng dụng này được sử dụng đều đặn, còn ứng dụng làm bằng lái xe là hệ thống không thường xuyên do mỗi bằng lái xe chỉ được làm mới sau vài năm. + Được thực hiện bởi con người và được thực hiện tự động: nếu được thực hiện bởi con người thì dữ liệu sinh trắc sẽ được thu thập khi có sự hướng dẫn, quản lý bởi một người. + Môi trường điều hành chuẩn hay phi chuẩn: Môi trường điều hành là chuẩn nếu hệ thống được hoạt động trong môi trường được điều khiển (các yếu tố nhiệt độ, độ ẩm). + Là ứng dụng công cộng hay ứng dụng kín: nếu là ứng dụng kín thì người sử dụng hệ thống sinh trắc là khách hàng hay nhân viên của tổ chức triển khai hệ thống. + Ứng dụng mở và ứng dụng đóng: Ứng dụng mở sử dụng chung các mẫu sinh trắc của một người với các ứng dụng khác, còn ứng dụng đóng phải sử dụng các mẫu sinh trắc thích hợp dành riêng. 2.3.4. So sánh các đặc trưng sinh trắc Một đặc tính sinh học hoặc hành vi của con người có thể được sử dụng như là một đặc trưng sinh trắc trong nhận dạng một người nếu nó có các yêu cầu sau: + Tính phổ biến: mọi người đều có đặc trưng sinh trắc này. + Tính phân biệt: hai người khác nhau thì đặc trưng sinh trắc này phải khác nhau. + Tính ổn định: đặc trưng sinh trắc này không thay đổi theo từng giai đoạn thời gian (tương ứng với hạng mục đối sánh nhất định). + Tính thu thập: nghĩa là đặc trưng này có thể đo được và lượng hóa. + Hiệu năng: khả năng nhận dạng chính xác, tốc độ nhận dạng; các tài nguyên cần thiết để đạt được tốc độ và độ chính xác mong muốn; các nhân tố môi trường và hoạt động ảnh hưởng đến tốc độ và độ chính xác trong nhận dạng. + Tính chấp nhận: mọi người vui lòng chấp nhận các đặc trưng sinh trắc trong đời sống hàng ngày của họ. + Khả năng phá hoại: là mức độ khó hay dễ để đánh lừa hệ thống bởi các phương pháp lừa dố. Sau đây là một số đặc trưng sinh trắc thông dụng: DNA, tai, mặt, dáng đi, đồ hình bàn tay và ngón tay, mống mắt. Hình 2.4: Một số đặc trưng sinh trắc: a) gương mặt, b) vân tay, c) đồ hình bàn tay, d) Mống mắt, e) võng mạc f) chữ kí, g) tiếng nói. Một số đặc tính của vân tay + Tính ổn định vĩnh viễn và tính cá thể của vân tay là những cơ sở nền tảng cho bộ môn khoa học nghiên cứu về sinh trắc nhận dạng vân tay. + Tính ổn định: Các vân tay (Fingerprint ridges) được hình thành khi thai nhi đạt tới tháng thứ ba hoặc thứ tư. Các vân tay bao gồm các đặc trưng cá nhân, trong đó bao gồm các điểm kết của các đường nổi (ridge endings), các điểm phân nhánh (bifurcations) và các chấm (dots). Sau khi sinh ra, các vân tay của trẻ sơ sinh phát triển dần đều về mọi hướng và vẫn giữ nguyên tỷ lệ quan hệ giữa các điểm đặc trưng cá nhân không đổi trong suốt cuộc đời. + Hầu như tất cả mọi người đều có vân tay: Về nguyên tắc thì tất cả mọi người đều có vân tay. Đôi khi do bệnh về da một số người có thể mất vân tay vĩnh viễn hoặc trong một thời gian (do kỳ xoá hoặc bị trày da) và bởi vậy có thể không nhận dạng được bằng vân tay. Tỷ lệ này thường chỉ ở mức từ khoảng 1-5% tổng số dân tuỳ thuộc vào thiết bị lấy vân tay, phần mềm phân tích nhận dạng vân tay và trình độ nghiệp vụ của cán bộ phân tích. Đặc trưng của vân tay (minutia) là các điểm kết và các điểm phân nhánh của các đường vân nổi (ridges) của vân tay. Đó là các đặc điểm biểu thị tính “riêng nhất cá thể” ("uniqueness"). 2.3.5. Các loại lỗi của hệ thống sinh trắc Đối sánh trong một hệ thống nhận dạng vân tay dựa vào điểm đối sánh s (không mất tính tổng quát, chúng ta giả sử giá trị của điểm này nằm trong [0, 1]). Điểm đối sánh được dùng để lượng hóa độ tương tự giữa biểu diễn của đầu vào và biểu diễn của mẫu cơ sở dữ liệu. Điểm này càng có giá trị gần 1 thì khả năng cả hai vân tay đều của cùng một ngón tay càng cao, ngược lại điểm này càng có giá trị gần 0 thì khả năng hai vân tay là của hai ngón tay khác nhau càng lớn. Quyết định của hệ thống được điều khiển bởi ngưỡng t. Với điểm s của hai vân tay: + nếu s t: kết luận là cặp so khớp (nghĩa là hai vân tay của cùng một ngón tay). + nếu s t: kết luận là cặp không so khớp (nghĩa là hai vân tay đến từ hai ngón tay khác nhau). Một hệ thống kiểm tra chấp nhận hai lỗi sau đây: + Kiểm tra các số đo sinh trắc từ hai ngón tay khác nhau với kết quả là của cùng một ngón tay (ta gọi là so khớp sai). + Kiểm tra các số đo sinh trắc của cùng một ngón tay với kết quả là của hai ngón tay khác nhau (ta gọi là không - so khớp sai). Hai lỗi trên tương ứng còn được gọi là chấp nhận sai và từ chối sa. Bởi vì kẻ giả mạo có thể được chấp nhận sử dụng thiết bị hay hệ thốngnếu có sự so khớp sai, và người có đủ thẩm quyền đăng nhập, sử dụng thiết bị hay hệ thống lại bị từ chối nếu xảy ra sự không so khớp sa. Chúng ta lượng hóa hai lỗi trên bằng các đại lượng: tỉ lệ chấp nhận sai và tỉ lệ từ chối sai. Chúng ta sẽ đi sâu hơn vào các lỗi trong những hệ thống kiểm tra và trong các hệ thống nhận dạng. 2.3.6. Các lỗi của hệ thống kiểm tra Kí hiệu T là mẫu sinh trắc của một người đã được lưu trữ, I là biểu diễn sinh trắc đầu vào cần được kiểm tra. Các giả thuyết đặt ra là: + H0: I T, đầu vào và mẫu không của cùng một người. + H1: I = T, đầu vào và mẫu của cùng một người. Tương ứng với các giả thuyết là các kết luận: + D0: người nay không có mẫu sinh trắc được lưu trữ trong hệ thống. + D1: người này đã có mẫu sinh trắc được lưu trữ trong cơ sở dữ liệu. Đối sánh trong kiểm tra T và I sử dụng độ tương tự s (T, I). Nếu s nhỏ hơn ngưỡng t thì kết quả là D0, nếu s lớn hơn hoặc bằng ngưỡng t thì cho kết luận D1. Từ các giả thuyết trên, chúng ta định nghĩa hai loại lỗi trong một hệ thống kiểm tra: + Dạng I: đối sánh sai (kết luận là D1 khi H0 đúng) + Dạng II: không-đối sánh sai (kết luận là D0 khi H1 đúng) Khi đó, tỉ lệ đối sánh sai (FMR) là xác suất của lỗi loại I, tỉ lệ không đối sánh sai (FNMR) là xác suất của lỗi loại II: + FMR = P (D1| H0 đúng). + FNMR = P (D0| H1 đúng). Để đánh giá tính chính xác của một hệ thống sinh trắc chúng ta phải thống kê các điểm đối sánh s của các cặp vân tay của cùng một ngón tay (phân bố p (s|H1 đúng)-thường được gọi là phân bố chân chính) và điểm đối sánh s của các cặp vân tay từ hai ngón tay khác nhau (phân bố p (s|H0 sai)-thường được gọi là phân bố giả mạo). + FNMR = p (s|H1 đúng)ds. + FMR = p (s | H0 đúng)ds. Hình 2.5: FMR và FNMR với một ngưỡng t thể hiện phân bố chân chính và phân bố giả mạo. Trong hình vẽ FMR là phần trăm các cặp giả mạo có điểm đối sánh lớn hơn hay bằng t và FNMR là phần trăm các cặp chân chính có điểm đối sánh nhỏ hơn t. Thực tế, cả FMR và FNMR đều là hàm của ngưỡng hệ thống t nên chúng ta có thể viết chúng là FMR (t) và FNMR (t). Nếu t giảm thì hệ thống sẽ bỏ qua nhiều lỗi và FMR (t) sẽ tăng, ngược lại khi tăng t để cho hệ thống an toàn hơn thì FNMR (t) sẽ tăng tương ứng. Người thiết kế hệ thống kiểm tra thường không biết trước hệ thống của mình sẽ ứng dụng ở lĩnh vực nào, vì vậy họ báo cáo hiệu năng hệ thống ở tất cả các điểm hoạt động (ngưỡng t) bằng cách xây dựng đường cong đặc tính hoạt động. Đường cong này biểu diễn các giá trị FNMR và FMR ở theo ngưỡng hệ thống t. Bên cạnh các phân bố và đồ thị trên, một vài chỉ số khác được dùng để đánh giá tính chính xác của một hệ thống kiểm tra. + Tỉ lệ lỗi cân bằng (EER): là tỉ lệ lỗi tại ngưỡng t mà FMR (t) = FNMR (t). Trong thực tế, do chúng ta có một số hữu hạn các cặp vân để so sánh và do sự lượng tự hóa giá trị nên EER không tồn tạ. Vì vậy thay vì đưa ra một giá trị đơn duy nhất, người ta đưa ra một khoảng. Mặc dù EER là một chỉ số quan trọng, nhưng các hệ thống kiểm tra vân tay ít khi hoạt động ở ngưỡng tương ứng với EER mà hoạt động ở các ngưỡng có FMR thấp. + ZeroFNMR là giá trị FMR nhỏ nhất mà tại đó không xảy ra không-đối sánh sai. + ZeroFMR là giá trị FNMR nhỏ nhất mà tại đó không xảy ra đối sánh sai. + Tỉ lệ thất bại trong thu thập (FTC): là tỉ lệ phần trăm mà thiết bị không thể tự động thu thập đặc trưng sinh trắc khi đặc trưng sinh trắc được đưa vào bộ cảm biến. + Tỉ lệ thất bại trong kiểm tra (FTE) là tỉ lệ phần trăm mà người dùng không được xử lý bởi hệ thống. + Tỉ lệ thất bại trong đối sánh (FTM) là tỉ lệ biểu diễn đầu vào không thể được xử lý hoặc đối sánh với một mẫu sinh trắc có giá trị, bởi các biểu diễn sinh trắc không đủ chất lượng. Hình 2.6: Đánh giá thuật toán kiểm tra vân tay trong cuộc thi nhận dạng vân tay 2002 (FVC2002) a) các phân bố chân chính và giả mạo được tính trên 2800 cặp chân chính và 4950 cặp giả mạo b)FMR (t) và FNMR (t) được tính từ các phân bố ở a. c) đường cong ROC dẫn xuất từ FMR (t) và FNMR (t) ở b). error FMR (t) FNMR (t) ZeroFNMR ZeroFMR EER Hình 2.7: Một ví dụ của đồ thị FMR (t) và FNMR (t), với các điểm tương ứng là EER, ZeroFNMR và ZeroFMR. 2.4. Đối sánh vân tay 2.4.1. Đặt vấn đề Một thuật toán đối sánh vân tay so sánh hai vân tay cho trước và trả về độ tương tự (không làm mất tính tổng quát, có giá trị giữa 0 và 1) hoặc một quyết định hai ngôi (khớp hoặc không khớp). Không làm mất tính tổng quát, từ đây về sau chúng ta kí hiệu biểu diễn của vân tay có được qua quá trình tuyển chọn như là mẫu (T) và biểu diễn của vân tay được đối sánh như là đầu vào (I). Trong trường hợp không có giai đoạn trích chọn đặc trưng, biểu diễn vân tay đồng nhất với chính ảnh cấp xám vân tay. Chúng ta kí hiệu cả ảnh vân tay và các vector đặc trưng ảnh (như các chi tiết) là T và I Trích chọn đặc trưng vân tay và các thuật toán đối sánh khá giống nhau cho các bài toán nhận dạng và kiểm tra vân tay. Bởi vì bài toán nhận dạng vân tay (tìm kiếm một vân tay đầu vào trong một cơ sở dữ liệu có N vân tay) có thể được thực hiện như là thực hiện tuần tự đối sánh một - một (kiểm tra) giữa các cặp vân tay. Sự phân loại vân tay và các kĩ thuật đánh chỉ số thường được sử dụng để tăng tốc độ tìm kiếm trong các bài toán nhận dạng vân tay. Đối sánh hai ảnh vân tay là một bài toán cực kì khó, chủ yếu do sự thay đổi dấu in của cùng một vân tay. Các yếu tố chính làm các dấu in khác nhau được tổng kết dưới đây: + Sự đổi chỗ: một ngón tay có thể đặt ở các vị trí khác nhau trên bộ cảm biến làm tịnh tiến ảnh vân tay. Một ngón tay thay đổi chỉ 2mm làm tịnh tiến khoảng 40 điểm ảnh trong cùng một vân tay được quét ở độ phân giải 500dpi + Sự quay: cùng một vân tay có thể quay ở các góc khác nhau trên bề mặt bộ cảm biến. Mặc dù bộ hướng dẫn ngón tay được gắn trên các máy quét thương mại, nhưng trong thực tế tồn tại sự quay không cố ý lên tới +-20 độ theo chiều dọc. + Sự chồng chéo từng phần: sự đổi chỗ và sự quay vân tay thường làm cho một phần vân tay bị đổ ra ngoài vùng nhìn thấy của bộ cảm biến, kết quả là xuất hiện sự chồng chéo giữa các vùng cận cạnh của mẫu vân và các vân tay đầu vào + Sự nhiễu phi tuyến: liên quan đến việc ánh xạ hình ảnh ba chiều sang hình ảnh hai chiều trên bề mặt bộ cảm biến. Ánh xạ này gây ra nhiễu phi tuyến trong việc đọc vân tay do sự mềm dẻo của ngón tay. Thông thường, các thuật toán đối sánh vân tay không quan tâm đến các đặc tính như ánh xạ, và xem một ảnh vân tay là không bị nhiễu bằng cách cho rằng: ảnh vân tay được cung cấp khi người dùng đặt đúng vị trí ngón tay: - Tiếp cận ngón tay vuông góc với bộ cảm biến. - Khi ngón tay chạm bề mặt bộ cảm biến, người dùng không ấn mạnh hay xoắn ngón tay. Do sự mềm dẻo của bề mặt da, các phần lực không vuông góc với bề mặt bộ cảm biến gây ra các nhiễu không tuyến tính (nén lại hay kéo dãn ra) trong quá trình lấy vân. Nhiễu làm mất khả năng đối sánh các vân tay như là các mẫu cứng. + Điều kiện áp lực và da: cấu trúc các vân của một vân tay có thể thu được chính xác nếu như phần ngón tay được lấy ảnh tiếp xúc đúng quy cách với bề mặt bộ cảm biến. Một số điều kiện như áp lực ngón tay, ngón tay khô, bệnh ngoài da, ướt, bẩn, độ ẩm không khí – gây ra sự tiếp xúc không đúng quy cách. Hệ quả là, ảnh vân tay lấy được rất nhiễu và mức độ các nhiễu này phụ thuộc vào mức độ các nguyên nhân nêu trên. Hình 2.8: Các dấu vân tay thu được của cùng một ngón tay không đối sánh được với nhau do nhiễu phi tuyến ở cặp đầu tiên và do các điều kiện da ở cặp thứ hai bên dưới. + Các lỗi trích chọn đặc trưng: các thuật toán trích chọn đặc trưng là không hoàn hảo và thường có các lỗi số đo. Các lỗi có thể tạo ra ở trong bất kì giai đoạn nào trong quá trình trích chọn đặc trưng (chẳng hạn: ước lượng ảnh hướng và tần suất, phát hiện số lượng, dạng, vị trí các vùng đơn, phân đoạn vùng vân tay từ nền). Cặp ảnh trong hình 2.8 thể hiện tính thay đổi cao có thể đặc tính hóa hai vết hằn khác nhau của cùng một ngón tay. Các ảnh vân tay từ các ngón tay khác nhau có thể xuất hiện khá giống nhau (tính thay đổi thấp), đặc biệt trong bối cảnh cấu trúc tổng thể (vị trí các vùng đơn, hướng vân cục bộ) Mặc dù khả năng một lượng lớn các chi tiết từ các vết ấn của hai vân tay khác nhau có thể so khớp là cực kì nhỏ, những người đối sánh vân tay hướng tới việc sử dụng các phép căn chỉnh tốt nhất. Họ thường xuyên có ý định khai báo các cặp chi tiết so khớp thậm chí ngay cả khi chúng không trùng khớp hoàn hảo. Một lượng lớn các thuật toán đối sánh vân tự động đã được đề nghị trong các tài liệu nhận dạng mẫu. Hầu hết các thuật toán này không gặp khó khăn trong đối sánh các ảnh vân tay chất lượng tốt. Nhưng trong đối sánh vân tay tồn tại thách thức ở các ảnh chất lượng thấp và vấn đề đối sánh từng vùng vân tay. Trong trường hợp hệ thống trợ giúp con người AFIS, một thuật toán kiểm tra chất lượng được sử dụng để chỉ lấy và chèn vào cơ sở dữ liệu các ảnh vân tay tốt. Hơn nữa, quá trình xử lý các mẫu vân khó có thể được quản lý. Dù sao, sự can thiệp là không thể trong các hệ thống nhận dạng trực tuyến tự động - những hệ thống này đang có nhu cầu ngày càng tăng trong các ứng dụng thương mại. Thống kê các lỗi không đối sánh sai xuất hiện nhiều trong các thuật toán đối sánh tham dự vào FVC2000 (Fingerprint verification competition csr. unibo. it/fvc2002) cho thấy hầu hết các lỗi được tạo ra trên 15-20% các ảnh vân tay chất lượng kém. Nói một cách khác, 20% mẫu trong cơ sở dữ liệu chịu trách nhiệm cho khoảng 80% các lỗi không - đối sánh sai. Vài cải tiến trong công nghệ nhận dạng vân tay được chứng minh sau đó hai năm ở FVC2002, nơi mà vài thuật toán được đưa ra đối sánh đúng nhiều ảnh vân tay chất lượng kém. Tuy vậy vẫn có nhu cầu tiếp tục phát triển các hệ thống mạnh có khả năng làm việc với các ảnh vân tay chất lượng kém. Các phương pháp đối sánh vân tay có thể được phân loại thô vào ba họ: + Đối sánh dựa độ tương quan: Hai ảnh vân tay được đặt chồng lên và độ tương quan giữa các điểm ảnh tương ứng được tính với sự căn chỉnh khác nhau (ví dụ với các vị trí và độ quay khác nhau). + Đối sánh dựa vào chi tiết: Đây là kĩ thuật phổ biến nhất và được sử dụng rộng rãi nhất. Chi tiết được trích chọn từ hai vân tay được lưu giữ như là tập các điểm trong một bề mặt hai chiều. Đối sánh dựa chi tiết cơ bản bao gồm tìm kiếm sự căn chỉnh giữa tập chi tiết mẫu và tập chi tiết đầu vào dẫn tới sự so khớp lớn nhất các cặp chi tiết. + Đối sánh dựa đặc tính vân: trong các ảnh vân tay chất lượng thấp, việc trích chọn chi tiết rất khó khăn. Khi các đặc trưng khác của mẫu vân tay (ví dụ: hướng và tần suất cục bộ, hình dạng vân, thông tin kết cấu) có thể được trích chọn một cách tin cậy hơn chi tiết, sự khác biệt của chúng là không cao. Các phương pháp thuộc họ này so sánh các vân tay với các đặc trưng được trích chọn từ các mẫu vân. Về nguyên lý, đối sánh dựa độ tương quan và đối sánh dựa vào chi tiết có thể xem như là một phần của đối sánh dựa đặc trưng vân, theo cách hiểu mật độ điểm ảnh, vị trí chi tiết là nhưng đặc trưng của mẫu vân ngón tay. Nhiều kĩ thuật khác cũng đã được đề nghị chính thức, về nguyên lý, có thể được xếp vào các họ trên theo các đặc trưng được sử dụng, nhưng chúng ta đề cập để phân loại chúng tách biệt trên cơ sở các kĩ thuật đối sánh. Chúng bao gồm các phương pháp dựa mạng thần kinh và các cố gắng thực hiện đối sánh vân sử dụng các bộ xử lý song song hoặc với các kiến trúc dành riêng khác. 2.4.2. Các kĩ thuật dựa độ tương quan Để T và I là hai ảnh vân tay tương ứng với vân tay mẫu và vân tay đầu vào. Một số đo trực quan về sự đa dạng (SSD) được tính bằng tổng các bình phương khác nhau của các cường độ các điểm ảnh tương ứng: SSD (T, I) = ||T-I||2 = (T-I)T (T-I) = ||T||2 + ||I||2 -2TTI (1) Trong đó chỉ số trên T kí hiệu sự hoán vị của một vector. Nếu ||T||2 và ||I||2 là hằng số, sự đa dạng giữa hai ảnh được tối thiểu khi độ tương quan (CC)) giữa T và I được cực đại: CC (T, I) = TTI. (2) Đại lượng -2. CC (T, I) xuất hiện như là đại lượng thứ ba của biểu thức (1). Độ tương quan chéo (hay gọi đơn giản độ tương quan) là độ đo tính tương tự giữa hai ảnh. Do sự đổi chỗ và sự quay là không thể tránh khỏi, đặc tính vết ấn của một ngón tay cho trước, tính tương tự giữa chúng không thể đơn giản được tính bằng cách đặt chồng T và I và áp dụng biểu thức (2). Kí hiệu I (∆x, ∆y, ) thể hiện một sự quay của ảnh đầu vào I bởi một góc quanh điểm đầu (thường là trung tâm ảnh) và dịch một đoạn ∆x, ∆y dọc theo trục x và y; khi đó độ tương tự giữa hai ảnh T và I có thể được đo như sau: S (T, I) = max CC (T, I (∆x, ∆y, )). (3) Ứng dụng trực tiếp của đẳng thức (3) hiếm khi dẫn tới các kết quả chấp nhận được chủ yếu là do các vấn đề sau: + Các nhiễu phi tuyến làm cho các vết ấn của cùng một ngón tay khác nhau trong cấu trúc toàn cục; Sự nhiễu mềm dẻo không thay thế mẫu vân tay ở các vị trí cục bộ, nhưng các hiệu ứng của nhiễu được tích hợp trong không gian ảnh, mẫu vân tay toàn cục không thể được tương quan một cách đáng tin cậy. + Điều kiện da và áp lực ngón tay làm cho độ sáng, độ tương phản, độ giày vân thay đổi trong các vết ấn khác nhau. Sử dụng các số đó độ tương quan phức tạp hơn như độ tương quan chéo được chuẩn hóa hay độ tương quan chéo được chuẩn hóa 0 - Trung bình có thể bỏ qua sự thay đổi độ sáng, độ tương phản để áp dụng các bước tăng cường ảnh, nhị phân hóa và làm mảnh (thực hiện trên cả ảnh T và I) có thể hạn chế độ dày vân. Hatano (2002) đã đưa ra giả thuyết sử dụng độ tương quan khác nhau, được tính như là độ tương quan lớn nhất trừ đi độ tương quan nhỏ nhất, trong một lân cận điểm nơi mà độ tương quan là lớn nhất. Trong thực tế, do tính chu kì của các mẫu vân tay, nếu hai phần tương ứng của cùng một vân tay không được căn chỉnh tương ứng với vị trí đối sánh tối ưu, giá trị độ tương quan hạ thấp trong khi hai vị trị không tương quan thể hiện một giá trị tương quan phẳng hơn trong lân cận của vị trí so khớp tối ưu. Hantano đã báo cáo một sự cải thiện độ chính xác tương ứng với phương pháp độ tương quan truyền thống Để ứng dụng trực tiếp biểu thức (3) đòi hỏi chi phí rất lớn. Ví dụ xem xét hai ảnh 400x400, sau đó sự tính toán độ tương quan ở đẳng thức (2) cho một giá trị đơn của (∆x, ∆y, ) yêu cầu 16000 phép nhân và 16000 phép cộng. Nếu ∆x, ∆y cả hai được lấy mẫu trong miền [-200, 200] và được lấy mẫu từng 1 độ trong miền [-30o, 30o] chúng ta phải tính 401x401x61 độ tương quan, kết quả là gần 1569 tỉ phép nhân và phép cộng (vậy là cần hơn 1h với máy tính 500MIPS). Vấn đề nhiễu ảnh vân tay (điểm 1 trong danh sách trên) thường được đặt ra khi tính độ tương quan cục bộ thay vì toàn cục: một tập các miền cục bộ (mà cỡ điển hình có thể là 24x24 hoặc 32x32) được trích chọn từ ảnh mẫu T và mỗi chúng được tương quan độc lập với toàn bộ ảnh đầu vào I (Bazen 2000). Các miền cục bộ có thể được x bằng vài cách: + Hợp của chúng hoàn toàn che phủ T và giao của chúng là rỗng. + Hợp của chúng hoàn toàn che phủ T và chúng cục bộ đè chồng. + Chỉ các vùng “thú vị” được lựa chọn từ T. Ví dụ, Yahagi, Igaki. . chọn các cửa sổ nhỏ quanh các chi tiết, trong khi Bazen (2000) xem xét các miền được chọn phân biệt cục bộ trên ảnh đầu vào (phù hợp ở vị trí bên phải, nhưng không phù hợp với các vị trí khác). Các hạng mục được đưa ra bởi Bazen để nhận dạng các vùng được chọn này trong ảnh mẫu: Các vùng quanh chi tiết, các vùng có các vân có độ cong cao, và các vùng thể hiện độ tương quan thấp ở các vị trí trong chính ảnh mẫu. Khi độ tương quan được tính một cách cục bộ, ước lượng độ tương quan ở các vùng khác có thể được tính bằng cách kết hợp để nhận được độ đo tính tương tự (ví dụ, số các ước lượng vượt qúa một ngưỡng cho trước được chia ra bởi tổng các ước lượng). Bổ sung vào giá trị của độ tương quan, sự đồng bộ của các điểm nơi mà mỗi vùng có độ tương quan lớn nhất có thể được sử dụng để tăng cường đối sánh: trong thực tế, mối liên hệ không gian (khoảng cách, góc) giữa các vùng trong mẫu và các vùng tương ứng trong ảnh đầu vào được giữ lại. Trong bất kì trường hợp nào, không có sử bảo đảm khi sử dụng bước hợp nhất là thực sự thuận lợi. Để tính độ phức tạp của kĩ thuật dựa độ tương quan, các phương pháp thông minh có thể được sử dụng để đạt được sự thi hành hiệu quả: + Định lý độ tương quan (Gonzales và Woods, 1992) phát biểu rằng: tính toán độ tương quan trên các miền không gian (toán tử ) là tương đương với thực hiện một phép nhân miền điểm trên miền Fourier, trong thực tế (4) + Trong đó F (.) là biến đổi fourier của một ảnh, F-1 (.) là biến đổi Fourier ngược, * kí hiệu liên hợp phức, và “x” kí hiệu nhân điểm với điểm của hai vector. Kết quả của đẳng thức (4) là ảnh độ tương quan mà các giá trị ở các điểm [x, y] thể hiện độ tương quan giữa T và I trong khi sự đổi chỗ là ∆x=x, ∆y=y. Đẳng thức (4) không xem xét sự quay, phải được giải quyết tách ra; trong bất kì trường hợp nào, tiết kiệm tính toán là rất cao trong khi độ tương quan được thực hiện một cách toàn cục (Coezteen và Botha, 1993) và khả năng xem xét khi nó được thực hiện một cách cục bộ bằng cách sử dụng các miền cỡ trung bình. + Tính toán độ tương quan lớn nhất không cần phải thực hiện tuần tự, theo cách vét cạn, các phương pháp đa phân giải, các kĩ thuật tìm kiếm không gian (Gradient Descent), và vài kinh nghiệm có thể được chấp nhận để làm giảm số các đánh giá. + Biến đổi Fourier-Mellin (Sujan và Mulqueen) có thể được sử dụng thay cho biến đổi Fourier để đánh giá được sự không thay đổi trong phép quay để bổ sung vào sự không thay đổi trong chuyển dịch; nói một cách khác, vài bước thêm vào (như chuyển đổi log) phải được thực hiện, nhưng chúng có thể làm giảm sự chính xác của giải pháp. + Phương pháp đưa ra bởi Wilson, Watson, và Paek (1997) phân hoạch cả T và I vào trong các miền cục bộ và tính toán độ tương quan lớn nhất (trong miền Fourier) giữa các cặp vùng. Phương pháp này bị ảnh hưởng bởi hiệu ứng viền do sự đè chồng không gian giữa các khối khác nhau, nhưng có thể được xem xét để tăng tốc độ của toàn bộ quá trình đối sánh. + Độ tương quan giữa hai tín hiệu có thể được tính bởi một hệ thống quan sử dụng thấu kính để dẫn xuất biến đổi Fourier của một ảnh và kết hợp các độ tương quan biến đổi cho sự đối sánh giữa chúng. Vài hệ thống đã được đưa ra trên thực tế cho đối sánh vân tay quang học. 2. 4. 3. Các phương pháp dựa chi tiết Đối sánh chi tiết là phương pháp nổi tiếng và được sử dụng rộng rãi nhất trong đối sánh vân tay, do các chuyên gia pháp lý so sánh các vân tay và chấp nhận phương pháp như là bằng chứng định danh trong các phiên tòa ở hầu hết các quốc gia. Đưa ra bài toán: Kí hiệu T và I là các biểu diễn của vân tay mẫu và vân tay đầu vào. Không như các kĩ thuật dựa độ tương quan, nơi mà các biểu diễn vân tay trùng khớp với ảnh vân tay, ở đây biểu diễn vân tay bởi một vector đặc trưng (của chiều dài biến thiên) mà các phần tử là các chi tiết vân tay. Mỗi chi tiết có thể được mô tả bằng một số các thuộc tính, bao gồm vị trí trong ảnh vân tay, hướng, kiểu (ví dụ điểm kết thúc vân hay điểm rẽ nhánh), một trọng số dựa trên chất lượng của ảnh vân tay trong một lân cận của chi tiếtHầu hết các thuật toán đối sánh chi tiết xem xét mỗi chi tiết như là một một nhóm bộ ba m = { x, y, ) thể hiện vị trí chi tiết ở vị trí x, y và góc chi tiết : T = { m1, m2, mm }; mI = { xi, yi, i }, i = 1m I = { m1’, m2’mn’ }; mj’ = { xj’, yj’, j’ } j = 1n Trong đó m và n là số các chi tiết trong T và I Một chi tiết mj’ trong I và một chi tiết mi trong T được xem là so khớp nếu khoảng cách không gian (sd) giữa chúng là nhỏ hơn mức dung sai cho trước ro và sự khác nhau về hướng (dd) giữa chúng là nhỏ hơn góc dung sai o: đẳng thức (6) lấy giá trị nhỏ nhất của | , và 360o - | bởi vì tính chu kì của góc (sự khác nhau giữa 2o và 358o chỉ là 4o). Chúng ta cần một hộp dung sai được định nghĩa qua ro và o để bù vào các lỗi không thể ngăn ngừa do các thuật toán trích chọn đặc trưng và các nhiễu mềm dẻo làm cho vị trí các chi tiết thay đổi Căn lề hai vân tay là bước bắt buộc để cực đại hóa số các chi tiết đối sánh. Căn lề chính xác hai vân tay yêu cầu phải tịnh tiến (theo x và y), quay (góc ) do vậy liên quan đến biến đổi hình học: + Phải co giãn ảnh vân tay khi độ phân giải của hai vân tay có sự khác nhau (ví dụ: hai ảnh vân tay được thu nhận bởi các máy quét hoạt động ở các độ phân giải khác nhau). + Các biến đổi h