Luận văn Truy tìm ảnh vân tay trên cơ sở dữ liệu được gom nhóm

- 33 - Chương 3 . TRÍCH CHỌN VECTOR ĐẶC TRƯNG CHO VIỆC GOM NHÓM ẢNH VÂN TAY 3.1 Giới thiệu Các thuật toán nhận dạng vân tay bền vững cần đảm bảo nhận dạng chính xác cho cả các trường hợp vân tay bị dịch chuyển hoặc bị xoay. Một giải pháp phổ biến hiện nay là phát hiện điểm tham chiếu và phương tham chiếu để sử dụng trong việc canh chỉnh, chuẩn hóa sự dịch chuyển và quay của vân tay. Đặt biệt, nhiều giải pháp xây dựng hệ thống truy tìm vân tay hiện nay sử dụng điểm tham chiếu và phương bất biến để rút ra vector đặc trưng phục vụ cho giai đoạn tìm kiếm ở mức thô. Do vậy, hoạt động nghiên cứu tìm ra thuật toán hiệu quả để phát hiện được điểm tham chiếu và phương bất biến một cách nhất quán là quan trọng và vẫn thu hút được sự quan tâm của nhiều nhà nghiên cứu. Các mục tiếp theo sẽ trình bày cách thức phát hiện điểm tham chiếu và phương bất biến như thế nào. Từ đó, việc rút trích các đặc trưng mà nó được sử dụng trong việc gom nhóm cơ sở dữ liệu được trình bày chi tiết. 3.2 Phát hiện điểm tham chiếu và phương pháp đề xuất Điểm tham chiếu đóng vai trò quan trọng trong các thuật toán nhận dạng vân tay. Nó được sử dụng rộng rãi trong việc phân lớp và so khớp vân tay. Có nhiều phương pháp đề xuất cho việc phát hiện điểm tham chiếu chẳng hạn như phương pháp Poincare Index, phương pháp dựa trên hình học vùng, phương pháp phát hiện đường cong, phương pháp dựa vào độ nhất quán hướng, … Tuy nhiên, kết quả thực nghiệm chỉ ra rằng các phương pháp hiện tại ít chính xác đối với cơ sở dữ liệu phần lớn ảnh vân tay chất lượng thấp (độ chính xác cao nhất của phương pháp hiện tại là 93% trên cơ sở dữ liệu chuẩn FVC2004, DB2, tập A). Công trình này đề xuất một thuật toán mới để xác định vị trí điểm tham chiếu duy nhất và nhất quán cho mọi - 34 - kiểu vân tay. Phương pháp này tính toán độ nhất quán hướng lồi mà nó miêu tả cả hướng đường cong và độ nhất quán hướng tại điểm đang xét. 3.2.1 Giới thiệu Vân tay được sử dụng rộng rãi việc nhận dạng con người trong các hệ thống thương mại và cơ quan hành pháp nhà nước. Nhìn chung, có hai loại đặc trưng để nhận dạng vân tay, đặc trưng toàn cục như hình dạng đường vân và đặc trưng cục bộ như minutiae. Nhìn mức độ toàn cục, có những vùng vân tay tại đó độ cong của các đường vân là rất cao. Chúng thường được gọi là những điểm nổi trội (singular) trong vân tay (điểm core và điểm delta xem Hình 3-1a). Chúng có vai trò quan trọng trong các hệ thống nhận dạng vân tay như phân lớp vân tay [9, 15, 25, 27] và so khớp vân tay [10]. (a) (b) ĐiểmCore Điểm Delta Điểm tham chiếu Hình 3-1. (a) Điểm Core và điểm Delta. (b) Điểm tham chiếu mà tại đó độ cong đường vân là lớn nhất. Tuy nhiên, một số vân tay, đặt biệt vân tay được thu nhận chỉ có một phần ảnh, với một phần điểm nổi trội nằm giáp lề bên ngoài vân tay. Thêm vào đó, số lượng điểm delta và điểm core là khác nhau trong các kiểu ảnh vân tay. Ví dụ ảnh vân tay kiểu plain arch không có điểm nổi trội rõ ràng, trong khi đó ảnh vân tay kiểu whorl có hai điểm core. Để xác định điểm duy nhất, nhất quán đối với mọi kiểu vân tay và ngay cả ảnh một phần, điểm tham chiếu được định nghĩa là điểm nằm trên đường vân cong lồi, cong nhất mà nó thường định vị ở tâm của vân tay (xem Hình 3-1b). - 35 - Nếu tồn tại nhiều điểm lõi thì điểm lõi nằm trên đường cong lồi chính là điểm tham chiếu. Đối với vân tay kiểu plain arch, điểm mà tại đó đường vân cong nhất là duy nhất. Có nhiều thuật toán được đề xuất để phát hiện điểm duy nhất và hầu hết chúng đều dựa vào trường hướng của vân tay. Phương pháp Poincare Index (PI) [4, 25] là một giải pháp thông dụng. Trong phương pháp này, PI của mỗi khối được tính toán bằng cách tính tổng sự thay đổi hướng xung quanh đường cong đóng của khối. Phương pháp này hiệu quả nhưng nhạy cảm đối với nhiễu, đặc biệt khi hướng thay đổi tiến tới π/2 hoặc −π/2. Hơn nữa, phương pháp này không thể xác định được điểm tham chiếu đối với vân tay kiểu Plain Arch. Các tác giả Koo và Kot [14] đề xuất phát hiện điểm duy nhất dựa vào việc tìm ra điểm có độ cong lớn nhất. Phương phát này không hiệu quả đối với ảnh chất lượng thấp bởi vì việc tính toán độ cong nhạy cảm với nhiễu. Tác giả Jain [10] đề xuất phương pháp dựa vào thành phần sin để xác định tham chiếu, là điểm có độ sai khác thành phần sin lớn nhất của hai vùng được định nghĩa trước. Phương pháp này tốt với cả trường hợp nhiễu nhưng việc định nghĩa hai vùng này nhạy cảm đối với ảnh vân tay bị quay. Hơn nữa, phương pháp này không hiệu quả trong việc định vị điểm tham chiếu đối với đối với ảnh vân tay kiểu Plain Arch. Tác giả Liu [16] đề xuất thuật toán hiệu quả phát hiện điểm tham chiếu bằng cách tính toán nhiều tỉ lệ độ nhất quán về hướng. Độ nhất quán này chỉ ra các hướng của các phần tử lân cận nhất quán như thế nào với hướng chính của nhóm. Phương pháp này có hạn chế trong việc loại bỏ điểm Delta. Nhiều trường hợp loại bỏ luôn điểm lõi thật sự, rồi chỉ phát hiện điểm tham chiếu là điểm có độ nhất quán nhỏ nhất gần đó. Tác giả Julasayvake [14] đề xuất phương pháp tối ưu lõi dựa vào việc kết hợp hai kĩ thuật. Kĩ thuật phát hiện đường cong để tìm ra điểm lõi thô, và kĩ thuật hình học được sử dụng để tìm ra điểm điểm lõi tinh. Phương pháp này vẫn không khắc phục hạn chế vốn có của phương pháp dựa vào hình học. Một hường tiếp cận hiệu quả được đề xuất để xác định điểm tham chiếu duy nhất và nhất quán đối với mọi kiểu vân tay. Phương pháp này cải tiến phương pháp của tác giả Liu trong việc lọc điểm delta bằng cách đề xuất một công thức mới - 36 - tính toán độ nhất quán hướng lồi của các điểm ứng viên. Độ nhất quán hướng lồi miêu tả cả hướng đường vân và các hướng đường vân trong vùng lân cận nhất quán với với hướng thống trị tốt như thế nào. Các mục tiếp theo trình bày chi tiết thuật toán dựa vào độ nhất quán hướng và thuật toán dựa vào độ nhất quán hướng lồi trong việc phát hiện điểm tham chiếu. 3.2.2 Phương pháp dựa vào độ nhất quán [16] Phương pháp dựa vào độ nhất quán hướng để chọn ra điểm tham chiếu là điểm mà tại đó trường hướng cong nhất là duy nhất và nằm trên đường hướng cong lồi. Độ nhất quán hướng này được tính toán bằng công thức (3-1). Đối với vùng có điểm core hoặc delta hoặc vùng nhiễu thì giá trị này nhỏ. Do vậy, cần có một phương pháp loại bỏ điểm nhiễu và điểm delta để chọn ra một điểm duy nhất đai diện cho vân tay làm điểu tham chiếu. Đối với vùng nhiễu, kính thước vùng lân cận lớn sẽ có độ nhất quán lớn, lớn hơn so với độ nhất quán của vùng lõi. Do vậy, độ nhất quán tại mỗi điểm được tính toán bằng mặt nạ lân cận với kích thước khác nhau từ lớn giảm tới nhỏ (xem Hình 3-2) để có thể loại bỏ nhiễu. Để loại bỏ điểm delta, phương pháp này sử dụng dụng phương pháp phát hiện đường cong. Trong phương pháp này, điểm tham chiếu có ( ) 0dx s > và ( ) 0dy s > . Các bước thực hiện định vị điểm tham chiếu bằng cách phân tích độ nhất quán dùng mặt nạ nhiều tỷ lệ (ví dụ là 4 mặt nạ) gồm các bước : 1) Tính toán trường hướng ( )' ,i jθ được trình bày trong mục 2.4 với mỗi khối có kích thước ϖ ϖ× , kích thước khối thường là nhỏ ϖ =5. 2) Tính toán độ nhất quán ( )Con s tại mỗi khối: ( ) ( )( )( )( )( ) ( )( )( )( )( ) 2 2 , , cos 2 ' , sin 2 ' , i j s i j s i j i j Con s M θ θ∈Ω ∈Ω+= ∑ ∑ (3−1) - 37 - trong đó: ( )sΩ là các khối viền ngoài 8 hướng trong của số lân cận có kích thước ( ) ( )2 1 2 1s s+ × + . ( ) ( )2 1 2 1s s− × − 3 3× ( ) ( )2 1 2 1s s+ × + Tỉ lệ từ lớn nhất Tỉ lệ nhỏ, tinh Hình 3-2. Hình biểu diễn các mặt nạ lân cận dùng cho việc tính độ nhất quán 3) Tìm khối có độ nhất quán nhỏ nhất ( )minCon s . Nếu ( )min 0.5Con s < thì ( )min 0.15T Con s= + ngoài ra ( )min 0.05T Con s= + . 4) Chọn các khối có ( )Con s T< . 5) Tính toán ( )dx s và ( )dy s cho các khối. Lựa chọn khối có ( ) 0dx s > và ( ) 0dy s > là ứng viên cho lần tính tiếp theo với bán kính lân cận giảm. ( ) ( )( ) ( )( ) ( ) ( )( ) ( )( ) cos 2 , cos 2 , sin 2 , sin 2 , s s j s j s s s j s j s dx s i s j i s j dy s i j s i j s θ θ θ θ =− =− =− =− = − − + = − − + ∑ ∑ ∑ ∑ (3−2) 6) Nếu không có ứng viên nào thì 0.01T T= + , lặp lại bước 3. 7) Lặp lại bước 2), 3), 4), 5), 6) và 7) cho các khối ứng viên với 1s s= − cho đến khi 1s = . - 38 - 8) Chọn khối có ( )1Con nhỏ nhất là điểm tham chiếu. Nhận thấy, phương pháp của tác giả Liu trong việc tính toán độ nhất quán hướng là rất hiệu quả. Công thức này cho phép phát hiện ra các điểm nổi bật trong vân tay. Để loại bỏ các điểm delta và điểm core nằm trên đường cong lõm, tác giả sử dụng phương pháp phát hiện đường cong. Điểm nổi bật thỏa mãn điều kiện ( )dx s và ( )dy s đều lớn hơn 0 được chọn làm điềm tham chiếu (những khối thỏa mãn điều kiện có màu đỏ xậm trong Hình 3-3b). (a) (b) Điểm tham chiếu sai (c) Điểm lõi Hình 3-3. (a) Trường nhất quán hướng. (b) Trường ngưỡng ( )dx s và ( )dy s . (c) Phát hiện sai điểm tham chiếu theo phương pháp của Liu. Theo phương pháp này, một số có điểm có giá trị nhất quán tối tiểu bị loại bỏ sai (xem Hình 3-2a, Hình 3-2c) bởi vì một số đặc điểm giống nhau của điểm này với điểm delta. Để khắc phục hạn chế này, phương pháp mới được đề xuất để lọc điểm delta và điểm core trên đường cong lõm bằng cách tính toán độ nhất quán hướng lồi. Phần tiếp theo trình bày chi tiết thuật toán được đề xuất. 3.2.3 Phương pháp phát hiện điểm tham chiếu Trong phương pháp này, công thức tính độ cong lồi tại mỗi khối ( ),CCE i j được đề xuất. Độ cong lồi tại khối ( ),i j được định nghĩa như sau. - 39 - ( ) ( ) ( ), ,, 12DX i j DY i jCCE i j += (3−3) (Hình 3-6b minh họa năng lượng cong lồi CCE -Convex Curvature Energy). trong đó, ( ),DX i j , và ( ),DY i j được tính toán với bán kính 3 3× các khối lân cận khối ( ),i j là. ( ) ( )( ) ( )( )1 1, cos 2 1, cos 2 1, , 1 1 DX i j i j s i j s s s θ θ= − + − + +∑ ∑=− =− (3−4) ( ) ( )( ) ( )( )1 1, sin 2 , 1 sin 2 , 1 . 1 1 DY i j i s j i s j s s θ θ= + − − + +∑ ∑=− =− (3−5) Giá trị năng lượng CCE này biểu diễn mức độ cong tại mỗi khối theo phương ngang và dọc. Nó đóng vai trong như một giá trị ngưỡng. Giá trị này kết hợp với giá trị nhất quán hướng để có được giá trị nhất quán hướng lồi cho mỗi khối. Sau đó, điểm tham chiếu có giá trị nhất quán lồi nhỏ nhất toàn cục được xác định nhất quán và chính xác. Công thức tính toán độ nhất quán hướng lồi (xem Hình 3-6) được định nghĩa như sau. ( ) ( ) ( ), , ,COCons i j ConsAV i j CCE i j= − (3−6) ( ) ( )' 1 1, S s ConsAV i j Cons s S = = ∑ (3−7) trong đó, S được thiết lập là 3 trong thực nghiệm của luận văn. ( )'Cons s là hướng được làm trơn tại khối ( ),i j với mặt nạ vùng lân cận là s . Trường giá trị độ nhất quán hướng được làm trơn bằng cách áp dụng phép lọc thông thấp trong miền không gian hai chiều với toán tử đơn vị G . Kích thước mặt nạ lọc là w wΦ Φ× . Gọi ( )' ,Cons i j là độ nhất quán hướng được làm trơn với các khối lân cận có bán kính ( ) ( )2 1 2 1s s+ × + . Công thức tính là ( ) ( ) ( )/2 /2' , , . , /2 /2 w w Cons i j G u v cons i u j v u w v w Φ Φ= − −∑ ∑=− =−Φ Φ (3−8) - 40 - trong đó, độ nhất quán hướng ( ),Cons i j với bán kính lân cận ( ) ( )2 1 2 1s s+ × + được tính toán bằng phương trình (3-1). Độ nhất quán hướng làm trơn trung bình là trung bình các giá trị độ nhất quán hướng được tính với nhiều tỉ lệ lân cận. Mục đích của việc tính toán ( )'Cons s và ( ),ConAV i j là để làm nổi bật điểm tham chiếu và loại bỏ vùng nhiễu (xem Hình 3-5). b)a) Loại bỏ nhiễu Hình 3-4. (a) Trường giá trị độ nhất quán hướng. (b) Trường giá trị độ nhất quán hướng được làm trơn. Các bước xử lý để xác định điểm tham chiếu có thể tổng kết như sau: 1) Tính toán ( ),DX i j , ( ),DY i j của mỗi khối ( ),i j bằng cách áp dụng phương trình (3-4), (3-5). 2) Tính toán năng lượng cong ( ),CCE i j tại mỗi khối ( ),i j . 3) Tính toán độ nhất quán hướng lồi ( ),COCons i j cho mỗi khối ( ),i j bằng cách áp dụng các phương trình (3-6), (3-7), (3-8). 4) Xác định khối ( ),ip jp có giá trị nhất quán hướng lồi nhỏ nhất là điểm tham chiếu duy nhất. + ( + (a) (b) (c) ) / 3= (d) Hình 3-5. Độ nhất quán hướng trung bình được tính toán trong (17). Trường nhất quán hướng được tính toán với mặt nạ lân cân 3 3× (a), 5 5× (b), 7 7× (c). (d) là trường nhất quán hướng làm trơn trung bình. - 41 - (b) (d) = Æ (c) (a) - Hình 3-6. Độ nhất quán hướng lồi được tinh toán trong (16). (a) Trường nhất quán hướng làm trơn trung bình. (b) Trường năng lương cong lồi. (c) Trường nhất quán hướng lồi. (d) phát hiện chính xác điểm tham chiếu. 3.3 Phát hiện phương bất biến Ảnh vân tay được thu nhận thường bị xoay. Do vậy để nhận dạng vân tay được chính xác, các thuật toán nhận dạng cần khắc phục được việc ảnh bị xoay. Một trong các giải pháp là sử dụng phương bất biến để chuẩn hóa ảnh vân tay khi bị xoay. Có một số bài báo đề xuất phương pháp phát hiện phương bất biến [4], [16]. Trong đó, phương pháp của tác giả Liu [16] đề xuất là rất hiệu quả. Phướng bất biến được phát hiện theo phương pháp này là duy nhất và nhất quán cho mọi kiểu ảnh vân tay. Trong phương pháp này, 16 hướng xuất phát từ tâm cách nhau / 8π (xem Hình 3-7a) được sử dụng để xem xét tính chất của hướng đường vân lân cận với phương này biến đổi như thế nào. Hướng có các đường vân cục bộ lân cận song song với nó nhiều nhất được chọn là hướng tham chiếu. Đối với ảnh plain arch có hai hướng ứng viên. Hướng tham khảo sẽ là giá trị trung bình của hai hướng này (xem Hình 3-7c). Giá trị để đánh giá mức độ các hướng cục bộ song song với hướng ứng viên đang xét như thế nào được tính toán theo công thức sau. ( ) ( )( ) ( ), 1 sin , , , 0,1,...,15, 8 k k i j k Var k i j M k k θ θ πθ ∈Ω = − = = ∑ (3−9) trong đó, kΩ là tập các hướng lân cận dọc theo hướng kθ , kích thước kΩ được điều chỉnh khi phân tích ( )Var k . Các hướng này nằm trong hình chữ nhật, chiều - 42 - rộng của nó vuông góc với hướng kθ , tâm đặt tại điểm tham chiếu. Hình chữ nhật gồm nhiều khối, Mỗi khối có kích thước 5 5× điểm ảnh. ( )Var k nằm trong phạm vi [ ]0,1 , ( ) 1Var k = khi kθ vuông góc với hầu hết các hướng của các khối nằm trong kΩ và bằng 0 khi kθ song song với hầu hết các hướng của các khối nằm trong kΩ . Thông thường, chúng ta tìm được ( )Var k nhỏ nhất để chọn hướng tham chiếu. Trường hợp đặt biệt là ảnh kiểu plain Arch, có hai hướng ứng viên, chúng ta chọn hướng ứng viên trung bình giữa chúng làm điểm tham chiếu. (a) (b) (c) π 3 / 2π 0 Điểm tham chiếu Phương tham chiếu Điểm tham chiếu Phương tham chiếu Hình 3-7. (a) 17 hướng xuất phát từ điểm tham chiếu. (b) Hướng tham chiếu. (c) Hướng tham chiếu đối với ảnh kiểu plain Arch. Thuật toán phát hiện hướng tham chiếu có thể trình bày tóm tắt như sau. 1) Ban đầu, kΩ được thiết lập gồm các khối trong hình chữ nhật 4 5× . 2) Tính ( )Var k cho 16 hướng dùng phương trình (3-9) và tìm ra giá trị ( )Var k nhỏ nhất là ( )minVar k . 3) Chọn các hướng kθ với ( )Var k < ( )minVar k +0.1 là các hướng ứng viên. 4) Nếu có nhiều hơn hai hướng ứng viên và độ rộng của kΩ nhỏ hơn giá trị T (trong thực nghiệm của luận văn 15T = ) thì mở rộng kích thước của kΩ và lặp lại bước 2. 5) Lựa chọn hướng có giá trị ( )Var k trung bình các lần lặp nhỏ nhất là hướng tham chiếu. Nếu có hai hay nhiều hướng ứng viên liên tiếp thì chọn - 43 - hướng trung bình của chúng làm hướng duy nhất. Hình 3-8. Biểu diễn giá trị độ lệch hướng so với hướng xem xét - một hướng ứng viên. Hình 3-9. Biểu diễn giá trị độ lệch hướng so với hướng xem xét - Hai hướng ứng viên 3.4 Trích chọn vector đặc trưng cho việc gom nhóm ảnh vân tay Ảnh vân tay bao gồm những đường vân và rãnh song song. Có hai đặc trưng cơ bản biểu diễn cho nó như: đặc trưng toàn cục miêu tả cấu trúc toàn cục và đặc trưng cục bộ miêu tả chi tiết minutiae của các đường vân. Các đặc trưng toàn cục (chẳng - 44 - hạn như điểm delta, core, hình dạng trường hướng) thường được sử dụng cho việc tìm kiếm (phân lớp) ảnh vân tay ở mức thô [15, 17, 25, 27], trong khi đó các đặc trưng cục bộ như minutiae được sử dụng cho việc so khớp ở mức tinh [6, 11, 13, 18, 21, 22]. Dưới đây, việc rút trích các đặc trưng toàn cục sử dụng trong giai đoạn truy tìm ảnh ở mức thô được trình bày chi tiết. 3.4.1 Trích chọn vector hướng Ảnh vân tay thường bị xoay và dịch chuyển. Do vậy, vector đặc trưng hướng được rút trích sao cho đảm bảo thể hiện đặc trưng hướng của ảnh mà không chịu tác động của việc xoay hoặc dịch chuyển của ảnh. Trường hướng đường vân được ước lượng bằng cách phân chia ảnh vân tay thành những khối đồng nhất và được sử dụng như là đặc trưng phân lớp trong [20]. Hướng đường vân thường biến đổi nhanh tại vùng xung quanh điểm lõi và chậm tại các vùng xa dần so với lõi. Do đó, việc sử dụng các khối không đều nhau là không hiệu quả cho việc đánh giá năng lượng biến đổi hướng của đường vân. Việc phân chia ảnh thành các phần không đều nhau bằng cách sử dụng khảm tròn được sử dụng rộng rãi [17]. Khảm tròn được sử dụng trong (xem Hình 3-10) [17] để tính toán hướng đường vân trong từng khối cục bộ và vector đặc trưng hướng của ảnh dùng cho việc tìm kiếm ở mức thô. Cụ thể việc tính toán vector hướng này như sau. Đặt ( ),I x y là giá trị xám của ảnh tại điểm ảnh ( ),x y kích thước là X Y× , ( ),r rx y là điểm tham chiếu. Khảm tròn chia ảnh thành những khối hình quạt (gọi là sector). Mỗi sector có bán kính r so với tâm ( ),x y và quay theo một góc ϕ so với rθ . Sector thứ j của vành thứ i ,i jS ( )1 ,1i E j F≤ ≤ ≤ ≤ , được tính toán như sau: ( ) ( ){ }, 0 0 1, | 1 . , ,1 , ,i j j jS x y i b b r i b b x X y Yϕ ϕ ϕ−= − + ≤ ≤ + ≤ ≤ ≤ ≤ ≤ (3−10) ( ) ( )2 2 ,r rr x x y y= − + − (3−11) 1tan mod 2 ,r r r y y x x ϕ θ π− ⎛ ⎞−= −⎜ ⎟−⎝ ⎠ (3−12) - 45 - trong đó, b là độ rộng của vành, 0b là độ rộng của vành bên trong nhất. Các tham số , , ,j b E Fϕ được xác định bằng thực nghiệm để nhận được kết quả tìm kiếm tốt nhất (thực nghiệm 13, 12, 9F E b= = = ). Các sector được phân chia thành các phần không đều nhau ( 13F = ) bắt đầu từ rθ các giá trị góc phân chia tương ứng là: / 8j jϕ π= , ( )2 5 / 8j π− và ( )3 / 8j π+ cho 1 5j≤ ≤ , 6 8j≤ ≤ , và 9 13j≤ ≤ . Dựa vào việc xác định các điểm ảnh thuộc sector ,i jS , chúng ta ước lượng hướng của sector này bằng phương pháp ước lượng hướng được trình bày trong phần 2.4. Kết quả vector hướng của ảnh vân tay q này là ( )1 2, ,..,q q q qM M E Fθ θ θ⎡ ⎤Θ = = ×⎣ ⎦ . Vì khảm tròn có thể có một số sector nằm ở ngoài vùng vân tay, nên vector { },1 ,2 , ,, ,..., , 0,1q q q q M q kS s s s s⎡ ⎤= ∈⎣ ⎦ được sử dụng kèm với vector hướng khi chúng được dùng trong việc so khớp. Thành phần , 1q ks = cho biết sector thứ k là thuộc vùng ảnh vân tay dùng cho nhận dạng. Hình 3-10. Hình minh họa khảm tròn. 3.4.2 Trích chọn vector khoảng cách Khoảng cách đường vân được định nghĩa là khoảng cách của điểm giữa hai đường vân kề nhau trong [24]. Với ảnh được thu với độ phân giải 500 dpi, khoảng cách đường vân thường giao động trong khoảng 3 đến 25 điểm ảnh [7]. Khoảng cách đường vân là phân biệt, do vậy nó có thể được sử dụng như là đặc trưng phụ - 46 - cho việc tìm kiếm ảnh ở mức thô. Khoảng cách đường vân cục bộ có thể ước lượng bằng cách được trình bày trong [7]. Cách tính khoảng cách đường vân được trình bày trong phần 2.5 được sử dụng. Trường khoảng cách đường vân này thường ít ổn định bởi vì ảnh vân tay thường được thu nhận ở những trạng thái khác nhau. Do vậy, khoảng cách đường vân trung bình của toàn ảnh thường ổn định hơn và được sử dụng như là đặc trưng toàn cục cho việc phân lớp ảnh. 3.4.3 Phương pháp trích chọn vector mật độ Nhận thấy: hai ảnh vân tay là khớp với nhau khi chúng có các tính chất sau là giống nhau: • Đặc điểm trường hướng đường vân giống nhau • Khoảng cách đường vân trung bình là giống nhau • Mật độ phân bố minutiae là giống nhau. Bên cạnh đó, nếu hai ảnh vân tay giống nhau trong việc so khớp minutiae thì mật độ phân bố minutiae là giống nhau. Do vậy, vector mật độ phân bố minutiae được đề xuất sử dụng như là đặc trưng toàn cục cho việc phân lớp vân tay. Các minutiae có vai trò như nhau trong việc so khớp ảnh vân tay, nên một khảm vuông (xem Hình 3-11) được sử dụng. Khảm vuông này chia ảnh thành những khối đều nhau kích thước E E× , tâm của khảm đặt tại điểm tham chiếu ( ),r rx y và có một cạnh vuông góc với phương bất biến rθ . Gọi M là số lượng minutiae của ảnh vân tay, D là vector mật độ. Thuật toán được tình bày tóm tắt như sau: 1) Thiết lập ( ) 0; 1,.., ;D i i n n E E= = = × và 1k = . 2) Xét minutiae thứ k . Tính toán khối ;l l i E j= × + mà minutiae thuộc nó. ( ),i j được xác định như sau. ( ) ( )/ , /i rCos w j rSin wϕ ϕ= = (3−13) ( ) ( )2 2 ,r rr x x y y= − + − (3−14) - 47 - 1tan mod 2 ,k r r k r y y x x ϕ θ π− ⎛ ⎞−= −⎜ ⎟−⎝ ⎠ (3−15) trong đó, ( ),k kx y là tọa độ của minutiae thứ k . 3) Tăng mật độ khối l lên 1: ( ) ( ) 1D l D l= + . 4) Nếu k M≤ thì 1k k= + và quay lại bước 2. Ngoài ra thì dừng lại. Hình 3-11. Hình minh họa khảm vuông và mật độ minutiae. Như vậy, chương này đã trình bày cách rút trích các vector đặc trưng được sử dụng trong việc gom nhóm cơ sở dữ liệu vân tay, và việc truy tìm theo nhiều cấp ảnh vân tay ở mức thô là dựa trên các đặc trưng này. Để tăng cường tốc độ tìm kiếm được tốt hơn, vector đặc trưng mật độ được đề xuất sử dụng. Phần tiếp theo trình bày chi tiết hóa việc truy tìm ảnh vân tay ở mức thô sử dụng những đặc trưng này.