Nghiên cứu phương pháp nhận dạng hình dạng

Bộ giáo dục và đào tạo Tr−ờng đại học bách khoa Hà nội --------------------------------------------- Luận văn thạc sĩ khoa học Nghiên cứu ph−ơng pháp nhận dạng hình dạng Ngành: xử lý thông tin và truyền thông M∙ số: 421 đinh thị kim ph−ợng Ng−ời h−ớng dẫn khoa học: T.S. Nguyễn kim anh Hà nội 2006 - 2 - Lời cam đoan Tôi xin cam đoan bản luận văn này là kết quả nghiên cứu của bản thân d−ới sự h−ớng dẫn của TS. Nguyễn Kim Anh. Nếu có gì sai phạm, tôi xin hoàn toàn chịu trách nhiệm. Ng−ời làm cam đoan Đinh Thị Kim Ph−ợng - 3 - Mục Lục Lời cam đoan..........................................................................................................2 Mục Lục .................................................................................................................3 Danh Mục Các từ viết tắt........................................................................................6 Danh mục hình vẽ...................................................................................................7 Lời nói đầu .............................................................................................................9 Ch−ơng 1:Tổng quan về tìm kiếm ảnh dựa trên hình dạng .Error! Bookmark not defined. 1.1. Giới thiệu...................................................................................................12 1.2. Trích chọn đặc tr−ng..................................................................................13 1.2.1.Biến đổi Fourier ...................................................................................12 1.2.1.1.Chuỗi Fourier....................................................................................13 1.2.1.2. Sự hội tụ của chuỗi Fourier..............................................................14 1.2.1.3. Biến đổi Fourier...............................................................................14 1.2.1.4. Biến đổi Fourier rời rạc ...................................................................15 1.2.1.5. Biến đổi Fourier hai chiều ...............................................................16 1.2.1.6. Phạm vi của biến đổi Fourier...........................................................16 1.2.2. Không gian độ chia (Scale space).......................................................17 1.2.2.1. Cơ sở ................................................................................................17 1.2.2.2. Không gian độ chia Gaussian..........................................................19 1.2.2.3. Phạm vi của sự không tạo các đặc tr−ng mới ..................................19 1.2.2.4. Không gian độ chia mâu thuẫn với việc đa quyết định ...................20 1.2.3.Thảo luận .............................................................................................22 1.3. Phép đo t−ơng đ−ơng và thực hiện phép đo...............................................22 1.3.1. Phép đo sự giống nhau........................................................................23 1.3.1.1. Không gian phép đo khoảng cách (Distance Metric Spaces) .........24 1.3.1.2. Khoảng cách dạng Minkowski ........................................................24 1.3.1.3. Khoảng cách Cosin..........................................................................24 1.3.1.4. Thông tin thống kê 2χ ...................................................................25 1.3.1.5. Đ−ờng giao biểu đồ .........................................................................25 - 4 - 1.3.1.6. Khoảng cách bậc hai........................................................................26 1.3.1.7. Khoảng cách Mahalanobis ..............................................................27 1.3.2.Thực hiện phép đo ...............................................................................27 1.3.2.1. Độ nhạy và độ chính xác(RPP). ......................................................28 1.3.2.2. Tỷ lệ trọng số thành công (PWH- Percentage of Weighted Hits) ...28 1.3.2.3. Phần trăm của thứ bậc giống nhau (PSR-Percentage of Similarity Ranking ) ......................................................................................................29 1.3.2.4. Thảo luận .........................................................................................30 1.3.3. Trích chọn đặc tr−ng hình dạng..........................................................30 1.4. Thảo luận...................................................................................................32 Ch−ơng 2 Ph−ơng pháp tách contrario .................................................................33 2.1. Cluster có thứ bậc và đánh giá giá trị........................................................34 2.1.1.Giá trị nhóm Contrario ........................................................................34 2.1.1.1. Cơ sở: ...............................................................................................34 2.1.1.2. Nhóm có ý nghĩa. ............................................................................35 2.1.2. Tiêu chuẩn kết hợp tốt nhất. ...............................................................37 2.1.3. Vấn đề tính toán .................................................................................40 2.1.3.1. Lựa chọn vùng thử. ..........................................................................40 2.1.3.2. Riêng rẽ và cực đại. .........................................................................42 2.2.1. Nhiễu điểm .........................................................................................43 2.2.2. Phân đoạn ...........................................................................................43 2.3. Kết cấu nhóm và không gian t−ơng ứng....................................................46 2.3.1. Tại sao phải tách kết cấu không gian. ................................................46 2.3.2. Đối sánh nhân tố hình dạng................................................................47 2.3.3. Biến đổi mô tả.....................................................................................49 2.3.3.1. Tr−ờng hợp t−ơng đồng ...................................................................49 2.3.3.2. Tr−ờng hợp biến đổi mối quan hệ ...................................................50 2.3.4. Cluster có ý nghĩa của biến đổi ..........................................................52 2.3.4.1. Phép đo sự không t−ơng đ−ơng giữa các biến đổi. ..........................52 2.3.4.2 Ph−ơng thức nền ...............................................................................52 2.3.4.3. Kỹ thuật nhóm .................................................................................54 2.4. Thảo luận...................................................................................................55 Ch−ơng 3:Ph−ơng pháp ra quyết định Contrario..................................................56 3.1. Một quyết định Contrario ......................................................................58 3.1.1. Ph−ơng pháp hình dạng trái ng−ợc ph−ơng pháp nền ........................58 3.1.2. Ph−ơng thức quyết định Contrario......................................................59 3.1.3. Ước l−ợng xác suất cảnh báo sai ........................................................61 - 5 - 3.1.4. Luật ra quyết định Contrario ..............................................................61 3.2. Tự động thiết lập ng−ỡng khoảng cách .................................................62 3.2.1. Số các cảnh báo sai NFA....................................................................62 3.2.2. Đối sánh có ý nghĩa ............................................................................63 3.2.3. Ng−ỡng nhận dạng t−ơng ứng với ngữ cảnh.......................................64 3.2.4. Tại sao quyết định Contrario ..............................................................65 3.3. Xây dựng đặc tr−ng độc lập thống kê....................................................66 3.4.Chuẩn hóa nhân tố hình dạng từ ảnh cho đặc tr−ng độc lập...................68 3.4.1. Biểu diễn hình dạng bằng các mức đ−ờng..........................................68 3.4.2.Tiêu chuẩn hóa và mã hóa bán cục bộ.................................................70 3.4.2.1. Mã hóa / Tiêu chuẩn hóa trị không đổi t−ơng đ−ơng ......................71 3.4.2.2. Mã hóa / Chuẩn hóa quan hệ bất biến .............................................73 3.4.3. Từ chuẩn hóa nhân tố hình dạng đến đặc tr−ng độc lập. ....................73 3.5. Thảo luận ...............................................................................................76 Ch−ơng 4Thử nghiệm...........................................................................................78 4.1. Thử nghiệm ph−ơng pháp nền...................................................................78 4.2. Thử nghiệm ph−ơng pháp Contrario..........................................................80 4.2.1. Hai ảnh không quan hệ với nhau ........................................................80 4.2.2. Méo dạng quan sát xa gần ..................................................................81 4.2.3. Quan hệ với sự nghẽn cục bộ và thay đổi độ t−ơng phản...................83 Kết luận ................................................................................................................88 Tài liệu tham khảo................................................................................................89 Tóm tắt luận văn...................................................................................................90 - 6 - Danh Mục Các từ viết tắt STT Từ viết tắt ý nghĩa 1 CBIR Content Based Image Retrieval 2 FD Fourie Descriptor 3 FFT Fast Fourie Transform 4 CSDL Cơ sở dữ liệu 5 NFA Number of Fasle Alarm 6 PFA Pridicion Fasle Alarm 7 FT Fourie Transform 8 NFAg NFA of region 9 NFAgg NFA of region-region 10 Pro Proposition 11 PFA Probability of False Alarm - 7 - Danh mục hình vẽ Hình 1.1: Đối t−ợng bị làm nhiễu bởi biến đổi phổ. ............................................13 Hình 1.2: ảnh và các biến đổi khác .....................................................................13 Hình 1.3: Điểm qua 0 tại vị trí x và độ chia t của tín hiệu ...................................20 Hình 1.4: (a) Khoảng cách Ocolit, .......................................................................25 (b) khoảng cách Cosin, (c) khoảng cách L1.........................................................25 Hình 1:a) ảnh ký tự,b) mức đ−ờng t−ơng ứng, c) Đoạn mức đ−ờng ...................31 Hình 2.2: Nhóm dữ liệu 950 điểm đồng dạng......................................................37 Hình 2.5: Vấn đề quan trọng của phân bố ph−ơng thức nền................................43 Hình 2.6: Phân đoạn ảnh đã scan và 71 đ−ờng mức có mức ý nghĩa cực đại. .....44 Hình 2.7: Nhóm với mối quan hệ tới h−ớng.........................................................45 Hình 2.8: Nhóm trong không gian(toạ độ x, h−ớng)............................................46 Hình 2.9: Thử nghiệm Guernica...........................................................................48 Hình 2.10: Thử nghiệm “ Guernica “ quan hệ t−ơng ứng ý nghĩa không đổi ......49 Hình 2.11: Hai đoạn mức đ−ờng và khung t−ơng ứng .........................................50 Hình 2.12: Thử nghiệm “ Guernica “ ...................................................................51 Hình 3.1: Trích chọn mức đ−ờng có ý nghĩa.......................................................70 Hình 3.3: Mã hoá sự không đổi t−ơng đ−ơng bán cục bộ ....................................73 Hình 3.4 : Mã hóa bán cục bộ mối quan hệ không đổi. . .....................................74 Hình 3.5 : Mã hóa hình dạng bán cục bộ quan hệ bất biến..................................75 - 8 - Hình 3.6: Mã hoá sự t−ơng đồng không đổi.........................................................76 Hình 4.1: ảnh và mức đ−ờng có ý nghĩa .............................................................80 Hình 4.2: Thử nghiệm hitchcook..........................................................................82 Hình 4.3: Ph−ơng pháp nhận dạng bán cục bộ quan hệ không đổi ......................83 Hình 4.4: Ph−ơng pháp nhận dạng quan hệ bán cục bộ không đổi ......................83 Hình 4.5 Ph−ơng pháp nhận dạng bán cục bộ .....................................................84 Hình 4.6: Tập các đoạn đ−ờng mức đối sánh với ảnh trong CSDL......................85 Hình 4.7: Ph−ơng pháp bán cục bộ t−ơng đồng không đổi ..................................85 Hình 4.8: ảnh gốc và mức đ−ờng có ý nghĩa.......................................................86 Hình 4.9: ảnh Menima và mức đ−ờng có ý nghĩa ...............................................86 - 9 - Lời nói đầu Ngày nay thông tin nói chung sử dụng trong ảnh là phổ biến. Rất nhiều lĩnh vực sử dụng ảnh nh− một công cụ để thực hiện công việc. Những năm gần đây, chứng kiến tốc độ gia tăng mạnh của ảnh số trên toàn thế giới, bởi sự gia tăng mạnh mẽ của các trạm làm việc tại mặt đất cũng nh− trạm vệ tinh, khó khăn trong l−u trữ, chi phí cao cho xử lý và internet. Sự đa dạng các ứng dụng của ảnh góp phần ra đời thế hệ ảnh số. Các ứng dụng của ảnh bao gồm: giải trí số, th− viện số, giáo dục và World Wide Web (www). Các ứng dụng ngày càng trở nên phụ thuộc vào việc sử dụng ảnh gốc. Lợi ích tr−ớc mắt của ảnh số gồm cả mặt xã hội và th−ơng mại. Sử dụng ảnh gốc giúp sáng tạo sản phẩm mới, tiết kiệm thời gian và tiền bạc. Tuy nhiên, độ lớn của kho l−u trữ ảnh số trên toàn thế giới có giới hạn, sự tận dụng ảnh số từ CSDL hiện tại khó hơn. Điều này là vì thiếu cách đánh chỉ mục và quản lý ảnh số chuẩn. Thông th−ờng các ảnh đ−ợc l−u trữ trong CSDL sử dụng d−ới dạng các thông tin thuộc tính. Thuận lợi của việc đánh chỉ mục thuộc tính ảnh: nó có thể cung cấp cho ng−ời sử dụng từ khoá tìm kiếm l−ớt qua mục lục, thậm chí thông qua giao diện truy vấn; ví dụ nh− ngôn ngữ truy vấn cấu trúc (SQL). Tuy nhiên, nhìn từ bên ngoài có hạn chế; một trong những hạn chế đó là thời gian tính toán khi CSDL lớn, nó d−ờng nh− không thể chú giải thủ công tất cả các ảnh. Mặt khác các đặc tr−ng thị giác của ảnh rất khó mô tả bằng từ ngữ một cách khách quan, có một tiêu điểm mới trên việc phát triển công nghệ đánh chỉ mục ảnh, đó là khả năng tìm kiếm ảnh dựa trên ngữ cảnh: nó có thể độc lập và có thể tự động hoá. Các công nghệ hiện tại đa phần qui về tìm kiếm ảnh dựa trên ngữ nghĩa (CBIR). CBIR đ−ợc giới thiệu nh− phần bổ xung cho việc tiến tới đánh chỉ mục thuộc tính truyền thống, nó là cần thiết để cấu thành CSDL multimedia. Vì những - 10 - tiềm năng ứng dụng rộng rãi của nó, CBIR đã thu hút đ−ợc số l−ợng lớn các chú ý trong những năm gần đây (KAT 92, NIB 93, YOS 99). Trong CBIR, ảnh trong CSDL là dữ liệu không cấu trúc, ảnh số hoàn toàn chỉ bao gồm mảng các pixel độ chói, không có ý nghĩ vốn có. Một trong những chìa khoá bắt nguồn CBIR là sự cần thiết để trích chọn thông tin hữu ích từ dữ liệu thô, để phản ánh ngữ nghĩa ảnh. Vì vậy việc trích chọn hiệu quả các đặc tr−ng ngữ nghĩa đó là điều cốt yếu sự thành công của CBIR. Nghiên cứu trên những yêu cầu của ng−ời sử dụng đối với ảnh từ bộ s−u tập ảnh biểu thị những đặc tr−ng nguyên thuỷ đó nh− màu sắc, kết cấu, hình dạng hoặc hỗn hợp của chúng là rất hữu ích đối với việc mô tả và khôi phục ảnh (EAK 99). Những đặc tr−ng này là khách quan và trực tiếp bắt nguồn từ tự bản thân ảnh mà không cần tham khảo bất kỳ một kiến thức cơ bản nào từ bên ngoài. Vì vậy đặc tr−ng nguyên thuỷ của ảnh ở mức thấp có thể đ−ợc bắt nguồn và khai thác để khuyến khích việc CBIR tự động hoá. *Đối t−ợng nghiên cứu Từ các thông tin cơ bản trên đây các ảnh trong CSDL có thể đ−ợc đánh chỉ mục bằng cách sử dụng thông tin thuộc tính hoặc thông tin ngữ nghĩa. Ngữ nghĩa của ảnh có thể đ−ợc mô tả sử dụng các đặc tr−ng nguyên thuỷ; ví dụ: màu sắc, cấu trúc, hình dạng hoặc tổ hợp của chúng. Kết quả nghiên cứu này chấp nhận tiến tới CBIR, đó là việc đánh chỉ mục và tìm kiếm ảnh bằng ngữ nghĩa của ảnh. Đặc biệt, việc tìm kiếm hội tụ ở việc đánh chỉ mục và tìm kiếm ảnh dựa trên hình dạng. Mục đích chủ yếu của cách tìm kiếm này là tìm kiếm và khai thác hình dạng rất khả thi để tìm kiếm và nhận dạng hình dạng. Điều tra các công nghệ và phát triển trong nghiên cứu này có thể là trực tiếp ứng dụng cho các ứng dụng đặc thù; ví dụ tìm kiếm nhãn mác, nhận dạng đối t−ợng… hoặc có thể hợp nhất trong bất cứ hệ thống CBIR nào để dễ dàng nhận dạng hình dạng sử dụng các đặc tr−ng hỗn hợp của ảnh. - 11 - Nhận dạng nói chung hội tụ các vấn đề của nhận dạng trực quan dựa trên thông tin hình dạng hình học. Ph−ơng pháp nhận dạng hình dạng th−ờng bao gồm 3 tiến trình: trích chọn đặc tr−ng, đối sánh (cốt lõi của tiến trình này là định nghĩa 1 khoảng cách hoặc phép đo sự t−ơng đồng giữa các đặc tr−ng hình dạng đ−ợc mô tả) và ra quyết định. Phần này chủ yếu nghiên cứu vấn đề ra quyết định cho đối sánh hình dạng, đặc biệt trong khung chung giữa hai hình dạng giống nhau để đối sánh, nó có thể đi tới quyết định nh− thế nào? Mục đích để định nghĩa tiêu chuẩn thống kê dẫn tới quyết định 2 hình dạng là giống hay không. Nghiên cứu các tiến trình thực hiệnnhận dạng hình dạng theo trình tự các công đoạn: từ công đoạn sơ khai biểu diễn ảnh, trích chọn đặc tr−ng, tách nhóm nhân tố hình dạng thành 1 hình dạng và chủ yếu là ph−ơng pháp ra quyết định Contrario cho nhận dạng hình dạng. *Cấu trúc luận văn Ch−ơng 1 : Tổng quan về tìm kiếm ảnh dựa trên hình dạng Ch−ơng 2: Tách nhóm Ch−ơng 3: Ph−ơng pháp Contrario cho nhận dạng hình dạng Ch−ơng 4: Thử nghiệm Do thời gian và khả năng có hạn nên luận văn này sẽ còn nhiều thiếu sót. Rất mong đ−ợc sự góp ý và thông cảm của các thầy giáo, cô giáo. Hà nội, ngày 6 tháng 11 năm 2006 Học viên Đinh Thị Kim Ph−ợng - 12 - Ch−ơng 1 Tổng quan tìm kiếm ảnh dựa trên hình dạng 1.1. Giới thiệu Vấn đề cơ bản của tìm kiếm ảnh dựa trên hình dạng là phép đo sự t−ơng đồng giữa các các hình dạng đ−ợc mô tả bởi các đặc tr−ng của chúng. Vì vậy, hai b−ớc cần thiết trong tìm kiếm và nhận dạng ảnh dựa trên hình dạng đó là trích chọn đặc tr−ng và phép đo t−ơng đ−ơng giữa các đặc tr−ng đã đ−ợc trích chọn. Hai công cụ cơ bản cần thiết đ−ợc sử dụng trong trích chọn đặc tr−ng hình dạng là biến đổi Fourier và không gian độ chia. Mặc dù trích chọn đặc tr−ng là mấu chốt để tìm kiếm ảnh dựa trên hình dạng và nhận dạng hình dạng, phép đo sự t−ơng đồng giữa các đặc tr−ng đ−ợc trích chọn cũng rất quan trọng. yêu cầu hiệu quả tìm kiếm ảnh đó là nhận biết nhanh các hình dạng t−ơng đồng - sự t−ơng đồng trong giới hạn của các đặc tr−ng đ−ợc trích chọn. 1.2. Công cụ trích chọn đặc tr−ng Biến đổi Fourie là một công cụ kinh điển. Nó đã đ−ợc sử dụng từ nhiều năm nay trong mọi hệ thống xử lý tín hiệu và hệ thống máy tính. Còn không gian độ chia là một công cụ mới đang đ−ợc chú ý gần đây. 1.2.1.Biến đổi Fourier Biến đổi Fourie là mấu chốt trong xử lý ảnh nó đ−ợc ứng dụng rộng rãi trong lý thuyết cũng nh− trong thực tế. Nguyên tắc cơ bản của biến đổi Fourie đó là một đối t−ợng đ−ợc coi nh− một tín hiệu và nh− vậy có thể biểu diễn đối t−ợng thành các thành phần cơ bản của tín hiệu. Biến đổi Fourie rất hữu ích cho phân tích các đối t−ợng khác nhau: có thể đối t−ợng bị làm nhiễu bởi biến đổi phổ - 13 - (Hình 1.1), trong khi các đối t−ợng t−ơng đ−ơng khác sẽ có biến đổi phổ t−ơng tự thậm chí cả khi chúng bị ảnh h−ởng bởi nhiễu và các biến đổi khác(hình 1.2). Hình 1.1: Đối t−ợng bị làm nhiễu bởi biến đổi phổ. Hình 1.2: ảnh và các biến đổi khác 1.2.1.1.Chuỗi Fourier Đặt f(x) là hàm tuần hoàn chu kỳ 2π và nguyên trong một chu kỳ, theo lý thuyết Four