intTypePromotion=1

Tiểu luận: Đề tài Nhận dạng tổng thể đối tượng - Xử lý ảnh số với thuật toán SIFT

Chia sẻ: Pham Luong Son Phi | Ngày: | Loại File: DOC | Số trang:20

0
322
lượt xem
91
download

Tiểu luận: Đề tài Nhận dạng tổng thể đối tượng - Xử lý ảnh số với thuật toán SIFT

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo Đề tài Nhận dạng tổng thể đối tượng - Xử lý ảnh số với thuật toán SIFT sẽ giúp các bạn tìm hiểu, nắm rõ các thuật toán SIFT và kĩ thật dò tìm đặc trưng bất biến. Cài đặt từng phần của thuật toán và viết tài liệu tiếng Việt cùng mã nguồn nêu những hiểu biết đầy đủ về giải thuật SIFT.

Chủ đề:
Lưu

Nội dung Text: Tiểu luận: Đề tài Nhận dạng tổng thể đối tượng - Xử lý ảnh số với thuật toán SIFT

  1. Đề tài NCKH sinh viên 1 Nhận dạng đối tượng THÔNG TIN CHUNG VỀ ĐỀ TÀI 1. Tên đề tài: Nhận dạng tổng thể đối tượng 2. Cấp dự thi: Cấp Bộ 3. Nhóm sinh viên thực hiện: STT Họ tên sinh viên Lớp, khoa Vai trò 1 Lê Đình Trường ĐH Tin K10B, Khoa CNTT-TT Nhóm trưởng 2 Lê Văn Hào ĐH Tin K10B, Khoa CNTT-TT Nhóm viên 3 Lê Ngọc Thanh ĐH Tin K10B, Khoa CNTT-TT Nhóm viên 4. Giáo viên hướng dẫn: - ThS. Trương Thế Chuyên, Trưởng bộ môn khoa học máy tính, khoa CNTT-TT. - Đồng hướng dẫn: ThS. Phạm Thế Anh, ThS. Lê Đình Danh, khoa CNTT-TT. 5. Thời gian thực hiện: 6 tháng (từ tháng 11/2010 đến tháng 5/2011). 6. Cơ quan quản lý đề tài: Trường Đại học Hồng Đức. 7. Đơn vị chủ trì đề tài: Khoa công nghệ thông tin và truyền thông BẢNG CÁC KÍ HIỆU, CHỮ VIẾT TẮT DÙNG TRONG BÁO CÁO Kí hiệu, chữ viết tắt Được hiểu là CSDL Cơ sở dữ liệu SIFT Scale-invariant feature transform DoG Diffirence of Gaussian NC Nghiên cứu Object Recoginition
  2. Đề tài NCKH sinh viên 2 Nhận dạng đối tượng MỤC LỤC Mụ Tên chương, mục và tiểu mục Trang c Thông tin chung về đề tài 01 Mục lục 02 Mở đầu 03 I Sự cần thiết của đề tài 04 II Mục tiêu của đề tài 04 III Ý nghĩa khoa học, tính thực tiễn và khả năng ứng 04 dụng IV Nội dung nghiên cứu 04 1 Tổng quan về SIFT 05 2 Nội dung Giải thuật 07 2.1 Dò tìm cực trị cục bộ 07 2.2 Trích xuất keypoint 10 2.3 Gắn hướng cho các keypoint 12 2.4 Tạo bộ mô tả cục bộ 13 3 Kĩ thuật đối sánh 14 4 Những đề xuất cải tiến, phát triển giải thuật SIFT 14 V Kết quả 15 VI Kết luận 18 VII Tài liệu tham khảo 18 Object Recoginition
  3. Đề tài NCKH sinh viên 3 Nhận dạng đối tượng MỞ ĐẦU Xử lí ảnh số (DIP - Digital Image Processing) nói chung và nhận dạng đối tượng (Object Recognition) nói riêng, đã và đang được ứng dụng rất nhiều. Nó trải rộng trên mọi mặt trong cuộc sống từ xử lí các bản in ấn, báo, bìa t ạp chí đ ến vấn đề về năng lực nhìn trong máy học, đôi khi nó rất gần gũi trong cuộc sống hàng ngày mà nhiều người không nhận ra như chức năng nhận dạng khuôn mặt, đối tượng chuyển động trong các máy ảnh, máy quay phim hay đơn giản là chức năng camera của điện thoại đi động cũng được tích hợp các công cụ xử lí ảnh và nhận dạng đối tượng. Đề cập sâu hơn vào vấn đề nhận dạng đối tượng là các bài toán cụ thể như nhận dạng dấu vân tay, nhận dạng khuôn mặt, nhận dạng chữ viết. Các bài toán này được ứng dụng rất nhiều trong nhận dạng đối tượng hình sự, phục vụ điều tra, kiểm chứng. Từ những ứng dụng rộng rãi như vậy mà tại các tổ chức, các trung tâm nghiên cứu của các trường đại học trên thế giới, các đề tài về xử lí ảnh luôn được đầu tư nhiều về vật chất lẫn thời gian. Tuy trong nước, ở các năm gần đây mặc dù các nghiên cứu về xử lí ảnh và nhận dạng đối tượng phát triển mạnh nhưng thông qua các cuộc hội thảo quốc gia thì vấn đề này chưa nhận được nhiều kết quả như mong đợi và cần đầu tư nhiều hơn nữa. Trong vấn đề cụ thể nhận dạng đối tượng thì ngày nay hướng nghiên cứu phổ biến trên thế giới là việc sử dụng các điểm bất biến (Invarian Feature) trong ảnh làm đặc trưng (Keypoint) để nhận dạng. Tiêu biểu nhất trong các thuật toán đối sánh sử dụng keypoint dạng này là thuật toán SIFT (Scale-Invarian Feature Transform, David Lowe 1999 và 2004), SIFT có thể coi là thuật toán tiền đ ề cho các ứng dụng cũng như giải thuật khác về biến đổi đặc trưng bất biến trong ảnh. Các giải thuật đang ứng dụng trong thực tế khác đều dựa trên hay phát triển theo các nhánh riêng của SIFT. Các đặc trưng trong SIFT không phụ thuộc vào các phép biến đổi ảnh cơ bản như xoay, thu phóng, thay đổi độ sáng... nên có thể xem tập các đặc trưng của một ảnh là thể hiện cho nội dung của ảnh đó. Vì vậy kết quả của việc nhận dạng Object Recoginition
  4. Đề tài NCKH sinh viên 4 Nhận dạng đối tượng sẽ có độ chính xác rất cao và thậm chí có thể khôi phục đ ược đối tượng b ị che khuất trong ảnh. Tuy nhiên giải thuật SIFT rất phức tạp trong cài đặt, đòi hỏi thời gian nghiên cứu và am hiểu nhiều thuật toán thành phần. Trong phạm vi đề tài, em đã tìm hiểu sâu từng bước của giải thuật SIFT và thực hiện cài đặt thành công giải thuật và ứng dụng vào nhận dạng đối tượng tùy biến trong cơ sở dữ liệu đặc trưng được trích chọn từ ảnh. I. Sự cần thiết của đề tài Mặc dù được ứng dụng nhiều trên thế giới nhưng trong nước việc tìm hiểu và cài đặt các thuật toán nhận dạng sử dụng keypoint đang còn hạn chế, hiện tại rất hiếm các đề tài, công trình nghiên cứu, tài liệu tiếng Việt về vấn đề này. Vì vậy việc tìm hiểu, hoàn thành cài đặt cơ bản thuật toán là cần thiết. II. Mục tiêu nghiên cứu Chúng em thực hiện đề tài với mục tiêu chính là tìm hiểu, nắm rõ thuật toán SIFT và kĩ thuật dò tìm đặc trưng bất biến. Sau đó, dựa theo những điều tìm hiểu được, chúng em sẽ cài đặt từng phần của thuật toán và viết tài liệu tiếng Việt cùng mã nguồn nêu những hiểu biết đầy đủ về giải thuật SIFT. III. ý nghĩa khoa học, tính thực tiễn và khả năng ứng dụng Hiện nay trên thế giới đã và đang có những bước tiến nhanh trong lĩnh vực tra cứu ảnh dựa trên nội dung, tuy nhiên việc nghiên cứu, ứng dụng các thành quả này ở trong nước còn rất khiêm tốn. Về ý nghĩa khoa học thì đề tài tìm hiểu về những thuật toán mạnh nhất hiện nay về trích chọn đặc trưng và từ những bước tìm hiểu đó để đề xuất giải pháp cải thiện chi phí tính toán nhưng vẫn giữ đ ược độ chính xác cần thiết. Từ việc hiểu và cài đặt những thuật toán mạnh trên, sẽ thực hiện xây dựng một chương trình hoàn chỉnh để có thể đối sánh tính tương đồng các đối tượng trong các ảnh khác nhau hoặc tìm kiếm đối tượng trong CSDL lớn các ảnh. IV. Nội dung nghiên cứu Nội dung nghiên cứu của đề tài bao gồm: Object Recoginition
  5. Đề tài NCKH sinh viên 5 Nhận dạng đối tượng - Tìm hiểu các thuật toán nhận dạng đối tượng sử dụng đặc trưng bất biến, trong đó trọng tâm là thuật toán SIFT. - Thực hiện cài đặt thuật toán SIFT và xây dựng chương trình nhận dạng đối tượng sử dụng SIFT. Sau đây chúng em xin trình bày cụ thể nội dung nghiên cứu của đề tài. 1. Tổng quan về SIFT Một thuật toán tiêu biểu và có hiệu quả khá cao là dựa theo các đặc trưng cục bộ bất biến trong ảnh: SIFT (Scale-invariant Feature Transform) do David Lowe đưa ra từ năm 2004 và đến nay đã có nhiều cải tiến trong thuật toán. Đ ặc trưng được trích chọn trong SIFT là các điểm đặc biệt (keypoint), các điểm này kèm theo các mô tả về nó và một véc tơ có lấy keypoint làm điểm gốc. Có bốn giai đoạn chính được thực hiện trong thuật toán để trích xuất các điểm đặc biệt và các đặc trưng của nó bao gồm: a. Dò tìm cực trị trong không gian đo (Scale-space Extrema Detection) : Bước đầu tiên này sẽ áp dụng hàm sai khác Gaussian (DoG - Deffirence of Gaussisan) để tìm ra các điểm có khả năng làm điểm đặc trưng tiềm năng (candidate keypoints), đó là những đểm rất ít phụ thuộc (bất biến) vào s ự thu phóng ảnh và xoay ảnh. b. Lọc và trích xuất các điểm đặc biệt (Keypoint localization): Từ những điểm tiềm năng ở trên sẽ lọc và lấy ra tập các điểm đặc trưng tốt nhất (keypoints). c. Gán hướng cho các điểm đặc trưng (Oriented Assignment) : Mỗi điểm đặc trưng sẽ được gán cho một hoặc nhiều hướng dựa trên hướng gradient của ảnh. Mọi phép toán xử lý ở các bước sau này sẽ được thực hiện trên những dữ liệu ảnh mà đã được biến đổi tương đối so với hướng đã gán, kích cỡ và vị trí của mỗi điểm đặc trưng. Nhờ đó, tạo ra một sự bất biến trong các phép xử lý này. d. Bộ mô tả điểm đặc trưng (Keypoint Description) : Các hướng gradient cục bộ được đo trong ảnh có kích cỡ cụ thể nào đó trong vùng lân cận với mỗi Object Recoginition
  6. Đề tài NCKH sinh viên 6 Nhận dạng đối tượng điểm đặc trưng. Sau đó, chúng sẽ được biễu diễn thành một dạng mà cho phép mô tả các tầng quan trọng của quá trình bóp méo hình dạng cục bộ và sự thay đổi về độ sáng. Tập các điểm đặc biệt thu được thường phụ thuộc rất ít vào các phép biến đổi cơ bản như xoay, phóng to, thu nhỏ, tăng giảm cường độ sáng, vì vậy có thể xem đây là các đặc trưng mang tính cục bộ của ảnh. Để đối sánh và nhận dạng hai ảnh thì ta tìm tập keypoint giống nhau trong hai ảnh, dựa vào hướng và tỉ lệ để có thể biết đối tượng trong ảnh gốc đã xoay, thu phóng bao nhiêu so với ảnh đem đối sánh. Cách tiếp cận của thuật toán này dựa vào điểm bất biến cục bộ của ảnh, chúng được trích xuất ra, được định hướng và mô tả sao cho hai keypoint ở hai vùng khác nhau thì khác nhau. Tuy nhiên một yếu tố ảnh hưởng không nhỏ đ ến tốc độ thuật toán là số lượng các keypoint được lấy ra là không nhỏ. Trung bình một ảnh kích thước 500 x 500 pixels thì sẽ trích xuất được khoảng 1000 điểm (số lượng điểm này phụ thuộc vào tùy từng ảnh và tham số lọc khác nhau). Số lượng các điểm đặc trưng có một tầm quan trọng trong vấn đề nhận dạng đối tượng, để nhận dạng một đối tượng nhỏ trong một ảnh chứa tập hợp các đối tượng hỗn độn thì cần ít nhất 3 điểm đặc trưng giống nhau để phát hiện và và bóc tách đ ối tượng. Đối với vấn đề xây dựng một cơ sở dữ liệu ảnh và thực hiện nhận dạng đối tượng bất kì thì ban đầu thường sử dụng SIFT để tạo một hệ dữ liệu các đặc trưng (keypoints) được trích xuất từ dữ liệu ảnh gốc. Sau đó với mỗi ảnh đối tượng đem nhận dạng ta dùng giải thuật SIFT trích xuất tập đặc trưng từ ảnh và đem đối sánh với hệ dữ liệu đặc trưng để tìm ra tập keypoint giống nhau, từ đó nhận dạng đối tượng trong cơ sở dữ liệu ảnh ban đầu. Tuy nhiên việc đối sánh này cần chi phí đối sánh rất lớn đối với cơ sở dữ liệu ảnh có số lượng lớn do số lượng các đặc trưng ở mỗi ảnh là lớn. Object Recoginition
  7. Đề tài NCKH sinh viên 7 Nhận dạng đối tượng Hình 1: Minh họa các bước chính trong giải thuật SIFT 2. Nội dung giải thuật 2.1. Dò tìm cực trị cục bộ Như đã nêu ở trên, bước đầu tiên sẽ tìm các điểm tiềm năng có thể trở thành điểm đặc trưng bằng phương pháp lọc theo tầng dựa vào việc thay đ ổi tham s ố bộ lọc Gaussisan. Trong bước này, ta cần dò tìm các vị trí và các số đo (kích cỡ) mà chúng bất biến trong các khung nhìn khác nhau của cùng một đối tượng. Các vị trí đó bất biến về số đo có thể được dò tìm bằng cách tìm kiềm các đ ặc tr ưng ổn định trên toàn bộ các số đo có thể, sử dụng một hàm liên tục về số đo vốn rất nổi tiếng có tên là hàm không gian đo (Witkin 1983). Theo các công bố của Koenderink (1984) và Lindeberg(1994) thì hàm Gaussian là hàm tốt nhất để biễu diễn không gian đo của ảnh 2 chiều. Vì vậy, không gian đo của một ảnh sẽ được định nghĩa như là một làm L(x,y,ó) được tạo ra bằng cách nhân chập ảnh gốc I(x,y) với môt hàm Gaussian G(x,y,ó) có tham số về số đo ó thay đổi. L(x,y,ó) = G(x,y, ó) * I(x,y) (2.1.1) Trong đó toán hạng * là phép nhân chập các ma trận 2 chiều x,y. Và G(x,y, ó) hàm Gaussian : Object Recoginition
  8. Đề tài NCKH sinh viên 8 Nhận dạng đối tượng G(x,y,ó) = (2.1.2) Để tìm những điểm đặc trưng có tính bất biến cao, thuật toán được sử dụng là tìm cực trị cục bộ của hàm sai khác DoG (Difference-of-Gaussian), kí hiệu là D(x,y,ó ). Hàm này được tính toán từ sự sai khác giữa 2 không gian đo cạnh nhau của một ảnh với tham số đo lệch nhau một hằng số k. D(x,y,ó) = L(x,y,kó) – L(x,y,ó) = (G(x,y,kó) – G(x,y, ó)) * I(x,y) (2.1.3) Các lý do lựa chọn hàm Gaussian là vì nó là kỹ thuật rất hiệu quả đ ể tính toán L (cũng như làm tăng độ mịn của ảnh), mà L thì luôn phải được tính rất nhiều để mô tả đặc trưng trong không gian đo, và sau đó, D sẽ đ ược tính một cách đ ơn giản chỉ với phép trừ ma trận điểm ảnh với chi phí thực hiện thấp. Hình 2. Quá trình tính không gian đo (L) và hàm sai khác D Hơn nữa, hàm sai khác DoG có thể được sử dụng để tạo ra một sự xấp xỉ gần với đạo hàm bậc hai Laplace có kích thước chuẩn của hàm Gaussian (ó 2∇ 2G) do tác giả Lindeberg đề xuất năm 1994. Ông đã chỉ ra rằng việc chuẩn hóa đ ạo hàm bậc hai với hệ số ó2 là cần thiết cho bất biến đo trở nên đúng. Cụ thể, ông đã Object Recoginition
  9. Đề tài NCKH sinh viên 9 Nhận dạng đối tượng công bố rằng các giá trị cực đại và cực tiểu của ó 2∇ 2G chính là những giá trị có tính ổn định nhất (bất biến cao) so với một loạt các hàm đánh giá khác như : gradient, Hessian hay Harris. Mối quan hệ giữa D và ó2∇ 2G được biễu diễn như sau : (2.1.4) Như vậy, ∇ 2G có thể được tính thông qua việc xấp xỉ sự sai khác hữu hạn tại các tham số đo gần nhau kó và ó : (2.1.5) Do đó : (2.1.6) Từ công thức này, ta thấy khi mà hàm sai khác DoG được tính toán tại các tham số đo lệch nhau một hằng số k, thì ta có thể sử dụng DoG đ ể xấp xỉ đ ạo hàm bậc hai Laplace của Gaussian. Vì hệ số (k-1) trong phương trình trên là hằng số trong mọi không gian đo nên nó sẽ không ảnh hưởng đến việc tìm các vị trí cực trị. Sai số trong việc xấp xỉ đạo hàm bậc 2 tiến về 0 khi k gần với 1. Tuy nhiên, các kết quả thử nghiệm của tác giả cho thấy quá trình xấp xỉ đạo hàm không ảnh hưởng đến việc dò tìm các vị trí cực trị thậm chí ngay cả khi chọn k khá xa, ví dụ k= 2 . Sau khi áp dụng hàm DoG ta thu được các lớp kết quả khác nhau (scale) từ ảnh gốc, bước tiếp theo là tìm các cực trị trong các lớp kết quả theo từng mi ền cục bộ. Cụ thể là tại mỗi điểm trên các lớp kết quả sẽ được so sánh với 8 điểm lân cận trên cùng lớp và 9 điểm lân cận trên mỗi lớp khác (hình dưới). Object Recoginition
  10. Đề tài NCKH sinh viên 10 Nhận dạng đối tượng Hình 3. Quá trình tìm điểm cực trị trong các hàm sai khác DoG Trong hình trên: điểm đánh dẫu x sẽ được so sánh với 26 điểm lân cận (đánh dấu vòng tròn xanh). Điểm này sẽ được lấy làm điểm tiềm năng (điểm có thể làm điểm đặc biệt – candidate keypoint) nếu nó có giá trị lớn nhất hoặc nhỏ nhất so với 26 điểm lân cận như trên. Giải pháp cho việc tìm các điểm tiềm năng này là sử dụng thuật toán blob detection (dò tìm điểm) do Lindeberg đề xuất. Vì số lượng các cực trị là rất lớn, vì vậy để tăng sự hiệu quả khi dò tìm các điểm cực trị (dò các điểm cực trị tốt nhất thay vì phải dò hết), ta cần xác định tần số lấy mẫu trong không gian đo và tần số lấy mẫu trong không gian quan sát (không gian ảnh). Thật không may là ta không thể xác định cả 2 loại tần số này một cách động trong mỗi tiến trình dò tìm. Thay vì vậy, các tần số này sẽ đ ược xác định offline thông qua phương pháp thử nghiệm. Sau khi thử nghiệm với nhiều nguồn dữ liệu ảnh khác nhau, tác giả đã chỉ ra tần số lấy mẫu trong không gian đo tốt nhất là 3 (giữ lại 3 lớp trong mỗi bộ 8 lớp), và tần số lấy mẫu ó = 1.6. 2.2. Trích xuất keypoint Sau bước 1 sẽ thu được rất nhiều điểm tiềm năng có thể làm điểm đ ặc biệt, tuy nhiên một số trong chúng là không cần thiết. ở bước tiếp theo này sẽ loại bỏ các điểm có độ tương phản kém (nhạy cảm với nhiễu) hoặc tính đặc trưng cục bộ ít hơn các điểm khác hoặc có xu hướng là đường biên đ ối t ượng. Bước thực hiện này gồm 3 công đoạn : a. Phép nội suy lân cận cho vị trí đúng của điểm tiềm năng: Object Recoginition
  11. Đề tài NCKH sinh viên 11 Nhận dạng đối tượng Phép nội suy lân cận () sử dụng mở rộng Taylor (Taylor expansion) cho hàm Difference-of-Gaussian D(x,y,ó) : (2.2.1) Trong đó : D và đạo hàm của nó được tính tại một điểm tiềm năng và X = (x,y,ó) là khoảng cách từ điểm đó. Vị trí của điểm cực trị được xác định bằng cách lấy đạo hàm của hàm trên với đối số X và tiến dần đến 0 : Hình 4 : Mô phỏng sử dụng công thức mở rộng của Taylor cho hàm DoG (2.2.2) Nếu > 0.5 theo một chiều nào đó thì nó có chỉ số cực trị không gần với các điểm tiềm năng khác, nó sẽ bị thay đổi và phép nội suy sẽ thay thế vai trò của nó bằng điểm khác gần nó. Object Recoginition
  12. Đề tài NCKH sinh viên 12 Nhận dạng đối tượng Hình 5. Minh họa các bước của quá trình lựa chọn các điểm keypoints. (a) là ảnh gốc. (b) mô tả 832 điểm keypoints tìm được, các điểm keypoints được vẽ ở dạng một vector thể hiện 3 thông tin : vị trí, hướng và độ dài. (c) sau khi đặt ngưỡng tương phản tổi thiểu, ta giữ lại được 729 điểm. (d) Giữ lại 536 điểm sau khi áp một ngưỡng nữa về hệ số độ cong. b. Loại trừ các điểm có tính tương phản kém: Các điểm nhạy cảm với độ sáng và nhiễu thì không được trở thành điểm đặc biệt và cần loại bỏ khỏi danh sách điểm tiềm năng. Trong khai triển Taylor mở rộng ở trên, nếu điểm tiềm năng nào có giá trị < 0.03 thì điểm đó sẽ bị loại, ngược lại thì nó được giữ lại theo vị trí mới (y+ ) và tùy biến ó, với y là vị trí cũ của nó cùng giá trị biến ó. c. Loại bỏ các điểm dư thừa theo biên : Object Recoginition
  13. Đề tài NCKH sinh viên 13 Nhận dạng đối tượng Sử dụng hàm DoG sẽ cho tác động mạnh đến biên khi vị trí của biên là khó xác định và vì vậy các điểm tiềm năng trên biên sẽ không bất biến và bị nhiễu. Và để tăng sự ổn định cho các điểm sẽ được chọn làm điểm đặc biệt ta sẽ loại trừ các điểm tiềm năng khó định vị (tức là vị trí dễ thay đổi khi có nhiễu do nằm ở biên). Sau khi áp dụng hàm DoG sẽ làm đường biên ảnh không rõ ràng và độ cong chính sẽ có giá trị lớn hơn nhiều so với độ cong dọc theo biên vì vậy cần loại bỏ bớt các điểm đặc biệt dọc theo cùng một biên. Giải pháp cho việc này là sử dụng giá trị của ma trận Hessian cấp 2 : (2.2.3) Các giá trị riêng của H tỉ lệ thuận với độ cong của D, các giá trị riêng â (giá trị nhỏ) và á (giá trị lớn) có tỉ lệ r = á/â sẽ được sử dụng. Các phần tử của H là Dxx và Dyy 2.3. Gắn hướng cho các keypoint Bằng việc gán một hướng cho mỗi điểm đặc trưng keypoint dựa vào các thuộc tính ảnh cục bộ, bộ mô tả keypoint có thể được biễu diễn tương đối so với hướng này và do đó đặt được tính bất biến đối với các hiện tượng quay ảnh. Cách tiếp cận này ngược lại với các bộ mô tả bất biến hướng của Schmid (1997) ở chỗ mỗi thuộc tính ảnh sẽ dựa vào một độ đo bất biến về hướng. Nhược điểm của cách tiếp cận này đó là nó giới hạn số lượng các bộ mô tả được sử dụng và bỏ qua các thông tin về ảnh bởi vì nó không yêu cầu mọi độ đo đ ều phải dựa trên một hướng nhất quán. Sau đây là kỹ thuật gán hướng cục bộ cho các điểm đặc trưng. Độ đo của các điểm đặc trưng được sử dụng để tìm ra một ảnh đã lọc Gaussian L với kích thước gần nhất sao cho mọi tính toán sẽ được thực hiện trong cùng một cách b ất biến về độ đo. Với mỗi mẫu ảnh L(x,y) này, gọi m(x,y) là biên độ gradient, θ (x,y) là hướng. Hai giá trị cuối được tính toán như sau : Object Recoginition
  14. Đề tài NCKH sinh viên 14 Nhận dạng đối tượng (2.3.1) 2.4. Tạo bộ mô tả cục bộ Các phép xử lý trên đây đã thực hiện dò tìm và gán tọa độ, kích thước, và hướng cho mỗi điểm đặc trưng keypoint. Các tham số đó yêu cầu một hệ thống tọa độ địa phương 2D có thể lặp lại được để mô tả vùng ảnh địa phương và nhờ vậy tạo ra sự bất biến đối với các tham số đó. Bước tiếp theo đây sẽ tính toán một bộ mô tả cho môt vùng ảnh địa phương mà có tính đặc trưng cao (bất biến với các thay đổi khác nhau về độ sáng, thu – phóng ảnh, xoay). Một cách tiếp cận đơn giản đó là lấy mẫu mật độ ảnh cục bộ lân cận điểm đặc trưng ở một độ đo thích hợp, và đối sánh các mật độ này sử dụng độ đo tương quan chuẩn. Tuy nhiên, hê số tương quan đơn giản thì lại rất nhạy cảm với sự thay đổi mà gây ra sự đăng ký nhầm các mẫu, chẳng hạn như các biến đổi Affine, phối cảnh 3D, hoặc bóp méo mềm. Cách tiếp cận tốt hơn nhiều được đưa ra bởi Edelman, Intrator và Poggio (1997). Cách tiếp cận này dựa trên một mô hình thị giác sinh học, cụ thể là mô hình noron phức tạp trong hệ thống não bộ. Các noron sẽ tương ứng với một gradient tại một hướng và tần số không gian c ụ thể, nhưng vị trí của gradient trên võng mạc được phép trượt trên một phạm vi nhỏ của khung nhìn. Dựa trên cách tiếp cận này, tác giả đã cài đặt bộ mô tả mới trong đó cho phép việc trượt vị trí sử dụng một cách tính toán khác. Hình sau mô phỏng quá trình tính toán các bộ mô tả theo cách tiếp cận mới. Object Recoginition
  15. Đề tài NCKH sinh viên 15 Nhận dạng đối tượng Hình 6 : Mô tả tạo bộ mô tả cục bộ Ảnh trái là mô phỏng biên độ gradient và hướng tại mỗi mẫu ảnh trong một vùng lân cận với điểm keypoint. Các giá trị đó tập trung trong một cửa sổ gaussian (nằm bên trong vòng tròn). Các mẫu này sau đó được gom lại thành một lược đồ hướng mô tả vắn tắt nội dung trong 4x4 vùng con như được mô tả ở bên phải với độ dài của mỗi hàng tương ứng với tổng biên độ gradient gần hướng đó bên trong một vùng. 3. Kĩ thuật đối sánh Trước hết để đối sánh các ảnh với nhau thì cần trích xuất tập keypoint tương ứng từ mỗi ảnh bằng các bước đã chỉ ra ở trên. Sau đó việc đối sánh sẽ thực hiện trên các tập keypoint này. Bước chính trong kĩ thuật đ ối sánh s ẽ thực hiện tìm tập con keypoint so khớp nhau ở hai ảnh, để thực hiện việc này sẽ tìm các cặp keypoint trùng nhau lần lượt ở hai ảnh. Tập con các keypoint so khớp chính là vùng ảnh tương đồng. Các bước đối sánh trên là gần giống vét cạn, đối với việc đối sánh trong CSDL lớn các ảnh sẽ gặp rất nhiều khó khăn do chi phí thực hiện đối sánh là rất lớn. Giải pháp cho vấn đề này là tạo chỉ mục (index) cho các tập keypoint, cụ thể là các keypoint được sắp xếp sẵn theo một tiêu chí dựa trên các giá tr ị c ủa bộ mô tả và hướng của nó. Để thêm một tập keypoint mới sẽ tự động sắp xếp và tạo chỉ mục cho nó. Việc thực hiện tìm kiếm một keypoint so khớp trên CSDL sẽ áp dụng tìm kiếm nhị phân trên các tập keypoint đã được sắp xếp và đánh chỉ mục. Việc tìm kiếm tập keypoint so khớp sẽ trở nên đơn giản hơn với chi phí tính toán th ấp hơn nhiều. 4. Những đề xuất cải tiến, phát triển thuật toán SIFT a. Giảm số lượng keypoint trích xuất ở mỗi ảnh Một trong những hạn chế lớn của SIFT là chi phí đối sánh tập keypoint khá lớn do số lượng keypoint trích xuất được khá lớn. Để khắc phục nhược điểm này ngoài cải thiến thuật toán đối sánh thì nên giảm số lượng các điểm keypoint trích xuất được. Cụ thể sẽ tối giản tập keypoint theo các bước: Object Recoginition
  16. Đề tài NCKH sinh viên 16 Nhận dạng đối tượng - Hạn chế các điểm keypoint mà tại đó biên độ Gradient biến đổi không rõ rệt, tức là tại đó độ biến thiên màu sắc là nhỏ, các điểm lân cận có mức xám gần tương tự nhau. Hạn chế những điểm này không làm giảm tính đặc trưng của tập keypoint do một trong số các điểm lân cận của nó có biên độ Gradient biến đổi rõ rệt hơn và được chọn làm keypoint sẽ đại diện tính đặc trưng cục bộ cho điểm bị loại bỏ và điểm được chọn sẽ đồng thời tăng tính đặc trưng cục bộ - Kết hợp với việc dò biên ảnh để hạn chế các điểm keypoint nằm gần biên do càng gần biên sẽ càng dễ bị ảnh hưởng bởi nhiễu và các phép biến đổi thông thường. Việc dò biên sẽ áp dụng kỹ thuật dò biên Candy cho đường biên mảnh và hiệu quả. b. Dùng lượt đồ màu loại trừ trước các ảnh ít khả năng tương đồng: Trước khi thực hiện tìm kiếm trong CSDL ảnh ta sẽ dùng lượt đồ màu để loại các ảnh có màu sắc quá khác nhau, tức là tính tương tự nhau là r ất ít. Các ảnh này sẽ bị bỏ qua trong quá trình tìm kiếm để giảm chi phí đối sánh, tìm kiếm ảnh tương đồng c. Trích xuất đối tượng ra khỏi ảnh theo đối tượng mẫu Sau khi nhận dạng đối tượng trong ảnh theo một đối tượng mẫu ta có thể trích xuất đối tượng đó ra khỏi ảnh nhờ việc điều chỉnh hướng cho từng c ặp keypoint so khớp cho chúng đồng bộ nhau và thực hiện dò vết theo các chốt là các keypoint so khớp để lần theo biên đối tượng và thực hiện trích xuất được đối tượng ra khỏi ảnh. V. Kết quả Chúng em đã cài đặt thuật toán SIFT và xây dựng chương trình nhận dạng ảnh tương đồng trong một CSDL ảnh được thu thập và dò tìm đặc trưng trước đó. Do đây chỉ là thử nghiệm nên chỉ tìm trên số lượng ảnh nhỏ gồm 50 ảnh kích thước từ 100x100 đến 1024x1024. Để tìm tổ chức lưu trữ keypoint và tìm kiếm keypoint tương đồng, chương trình được thiêt kế riêng bộ học sử dụng cấu trúc lưu trữ KDTree (cây đa chiều) Object Recoginition
  17. Đề tài NCKH sinh viên 17 Nhận dạng đối tượng và tìm keypoint tương đồng bằng thuật toán Nearest-Neighbor (tìm hàm xóm gần nhất). Sau đây là minh họa kết quả của chương trình: Hình 7: Ảnh bên phải (ảnh b) đã có trong CSDL và ảnh bên trái (ảnh a) là ảnh đầu vào. Chương trình đã nhận ra chính xác cặp ảnh tương đồng này với độ chính xác cao (49 keypoint so khớp). Điều này cho thấy SIFT bất biến với phép xoay, thu phóng và không yêu cầu tính toàn vẹn của ảnh. Object Recoginition
  18. Đề tài NCKH sinh viên 18 Nhận dạng đối tượng Hình 8: Lần này chương trình thử nghiệm với ảnh đầu vào là một khuôn mặt đối tượng cụ thể trong một ảnh từ CSDL có chứa đối tượng. Chương trình nhận diện chính xác và khoanh vùng đối tượng nhận diện như trong hình. Hình 9: Đây là thử nghiệm nhận dạng địa điểm qua ảnh vệ tinh. Hình bên phải là ảnh đầu vào, ảnh chụp từ trên vệ tinh cảnh khuôn viên cơ sở 1 trường ĐH Hồng Đức, năm 2003 và khu vực lân cận (bởi Google Maps). Ảnh đầu vào là chụp nhà đa năng của trường và bị xoay một hướng khác với góc nhìn thay đổi. Chương trình đã tìm ra với độ chính xác rất cao, với 135 keypoint so khớp. Object Recoginition
  19. Đề tài NCKH sinh viên 19 Nhận dạng đối tượng Hình 10: Đây là thử nghiệm chương trình nhận dạng một đối tượng cụ thể trong ảnh, hình bên trái là đối tượng mẫu, hình phải là bối cảnh chứa đ ối tượng mẫu, kết quả chương trình đã nhận ra đối tượng với 69 keypoint so khớp VI. Kết luận SIFT được xem là thuật toán rất mạnh và thuộc loại phức tạp nhất trong nhận dạng đối tượng. Vì vậy, trong phạm vi đề tài chúng em chỉ tìm hiểu và cài đặt thuật toán với đầy đủ các bước ở mức cơ bản, sau đó xây dựng ứng dụng mô phỏng việc nhận dạng đối tượng tương đồng sử dụng SIFT. Để cải tiến và phát triển thành một ứng dụng đầy đủ cần phải đầu tư thời gian và có phương pháp nghiên cứu ở mức cao hơn. Trong thời gian tới, chúng em sẽ tìm hiểu thêm các cải tiến của SIFT và xây dựng ứng dụng hoàn chỉnh bao gồm cả giao diện người dùng và CSDL đặc trưng một cách đầy đủ, hệ thống. VII. Tài liệu tham khảo 1/ Lowe, D. “Distinctive image features from scale-invariant keypoints” International Journal of Computer Vision, 60, 2 (2004). 2/ Lee, David. Object Recognition from Local Scale-Invariant Features (SIFT). O319.Sift.ppt. 3/ Basri, R., andJacobs, D.W.1997. Recognition using region correspondences. International Journal ofComputerVision, 25(2). 4/ Brown, M. And Lowe, D.G. 2002. Invariant features from interest point groups. In British Machine Vision Conference, Cardiff, Wales. 5/ Vedrana Andersen, LarsPellarin, RenéeAnderson. Scale-Invariant Feature Transform (SIFT): Performance and Application. In The IT University of Copenhagen. 6/ Piotr Indyk. Algorithms for Nearest Neighbor Search Slide. In MIT. Object Recoginition
  20. Đề tài NCKH sinh viên 20 Nhận dạng đối tượng 7/ RobHess. An Open-Source SIFT Library. In School of EECS, Oregon State University Corvallis, Oregon, USA. Object Recoginition
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2