Luận văn 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 Fourie f(x) có thể khai triển thành chuỗi fourie nh− sau: (1.1) (1.2) - 14 - Với chu kỳ T: 1.2.1.2. Sự hội tụ của chuỗi Fourier Nếu một hàm f(x) là tuần hoàn và nguyên trong chu kỳ của nó thì sẽ tồn tại chuỗi Fourie nh−ng không đảm bảo chắc chắn rằng chuỗi Fourie sẽ hội tụ tới f(x). Tuy nhiên theo điều kiện Fourie Dirichcle phần lớn hoặc các lớp chung của hàm có thể biểu diễn bằng chuỗi Fourie. Điều kiện chuỗi Fourie Dicrichcle nếu là một đoạn hàm f(x) liên tục : 1. Giới hạn số các điểm không liên tục 2. Giới hạn các điểm cực trị. Hàm này có thể mở rộng thành chuỗi Fourie hội tụ tại các điểm liên tục và ý nghĩa của điểm giới hạn thực và giới hạn ảo của hàm tại điểm giới hạn: Đối với tín hiệu số hoặc đối t−ợng số điều kiện Dirichcle đ−ợc chứng minh vì vậy nó có thể đ−ợc biểu diễn bởi chuỗi Fourie: 1.2.1.3. Biến đổi Fourier (1.3) (1.4) (1.5) (1.6) - 15 - Nếu hàm f(x) có thể biểu diễn bằng chuỗi Fourie của nó. Sau đó f(x) đ−ợc xác định duy nhất bởi hệ số Cn. Ng−ợc lại nếu hệ số Cn của chuỗi Fourie của hàm đã biết tr−ớc thì f(x) có thể đ−ợc xây dựng lại từ tập Cn. Chuỗi Fourie thiết lập mối quan hệ duy nhất giữa f(x) và hệ số Cn. Biểu diễn theo công thức : T−ơng ứng công thức: 1.2.1.4. Biến đổi Fourier rời rạc Biến đổi Fourie đặc biệt hữu ích đối với phân tích đối t−ợng số vì đối t−ợng số tồn tại ở dạng rời rạc. Để biến đổi công thức 1.7 và 1.8 thành dạng rời rạc, f(x) đ−ợc lấy N mẫu trong chu kỳ [0, T] f(x0); f(x0+∆x); f(x0+2∆x);… f(x0+(N-1)∆x) ∆x gọi là b−ớc lấy mẫu trong phạm vi không gian xem xét f(x) biểu diễn thành: B−ớc lấy mẫu ∆u trong miền tần số và b−ớc lấy mẫu ∆x trong miền không gian có quan hệ theo biểu thức : (1.7) (1.8) (1.9) (1.10) - 16 - Mối quan hệ này dễ thay đổi chỉ rõ sự chính xác của biểu diễn đối t−ợng trong miền không gian và trong miền tần số là ng−ợc với nhau. Chú ý, khi bố trí một tập dữ liệu khác thì chúng không thể biến đổi độc lập với nhau. Điều này cần l−u ý khi trích chọn đặc tr−ng trong miền không gian lấy mẫu đối t−ợng. 1.2.1.5. Biến đổi Fourier hai chiều Đối với hàm hai biến f(x,y) xác định 0 ≤ x, y ≤ N. Cặp biến đổi Fourie là: Mặc dù, số l−ợng F(u,v) từ biến đổi Fourie của biểu thức là rất lớn nh−ng số l−ợng F(u,v) có ích là rất bé. Đây là lý do biểu diễn đối t−ợng trong miền tần số tốt hơn (Hệ số có nghĩa ít). Điều này thực sự hữu ích trong nhiều ứng dụng đặc biệt trong việc phân tích hình dạng vì nó có thể xấp xỉ ý nghĩa của đối t−ợng gốc f(x,y) hoặc f(x) có thể xây dung từ F(u,v) nhỏ. Đây là vấn đề cơ bản của xử lý tín hiệu Fourie và phân tích đối t−ợng Fourie. 1.2.1.6. Phạm vi của biến đổi Fourier Biến đổi Fourie tuân theo phạm vi hữu ích của việc phân tích đối t−ợng • Sự riêng rẽ: Biến đổi Fourie rời rạc (1.11) có thể mô tả riêng rẽ nh− sau: • Lợi ích của việc riêng rẽ này đó là F(u,v) có thể thu đ−ợc trong 2 b−ớc bằng cách sử dụng liên tiếp biến đổi Fourie 1 chiều. FT 1 chiều có thể đ−ợc tính toán sử dụng biến đổi Fourie nhanh FFT. • Biến đổi: Biến đổi phạm vi của FT (1.11) (1.12) (1.13) (1.14) - 17 - • Điều này chỉ ra: 1 sự thay đổi trong miền không gian sẽ dẫn đến sự thay đổi trong miền tần số. • Phép quay: Nếu gắn vào hệ toạ độ cực Sau đó thay thế vào biểu thức có : Điều này có nghĩa việc quay f(x,y) trong miền không gian góc θ0 cũng t−ơng ứng việc quay F(u,v) một góc t−ơng tự trong miền tần số. • Độ chia: đối với hai hệ số a, b, phạm vi độ chia của FT đ−ợc viết nh− sau: Điều này chỉ ra rằng: độ chia của f(x,y) với a và b theo x,y trong miền không gian tỷ lệ nghịch với biên độ F(U,V) trong miền tần số. Điều này cũng giảm bớt hệ số F(u,v) bởi 1/a và 1/b theo u, v trong miền tần số. Tổng quát, phóng to một đối t−ợng ảnh trong miền tần số sẽ làm nổi mức tần số thấp trong miền không gian trong khi việc thu nhỏ đối t−ợng trong ảnh sẽ làm tăng vùng tần số cao trong miền không gian. 1.2.2. Không gian độ chia (Scale space) Đối với FT thì không gian độ chia là công cụ khá mới trong phân tích đối t−ợng. Nó đã đ−ợc phát triển trong các hệ thống tính toán. Phần này sẽ giới thiệu không gian độ chia tuyến tính và phạm vi quan trọng của nó. 1.2.2.1. Cơ sở Lý thuyết không gian độ chia giúp ta quan sát các đối t−ợng trong các độ chia khác nhau và các đối t−ợng chỉ có ý nghĩa duy nhất theo độ chia chính. Một ví dụ đơn giản nếu là ảnh một sự vật thì dù có là độ chia 1m hay 1cm thì ý nghĩa của sự vật không thay đổi. Trong vật lý các đối t−ợng tồn tại trong sự sắp xếp độ (1.15) (1.16) - 18 - chia. Các dụng cụ quan sát nh− camera các dụng cụ này có thể quan sát cũng là một sự sắp xếp độ chia. Để mở rộng các độ chia t−ơng ứng với sự phóng to hay thu nhỏ nhờ các dụng cụ quan sát. Độ chia của một dụng cụ luôn có hai giới hạn: độ chia giúp phân biệt chi tiết ảnh tốt nhất và kém nhất và khi quan sát sự vật thì độ chia nằm trong khoảng giới hạn hai phía này. Để tính toán bất kỳ dạng biểu diễn nào từ dữ liệu ảnh, thông tin cần đ−ợc trích chọn bằng cách sử dụng toán tử nào đó với dữ liệu. Các toán tử t−ơng tự nh− ống kính máy quay sử dụng để mô tả thế giới thực. Một vài vấn đề đặt ra khi đề cập tới các toán tử đó đ−ợc sử dụng nh− thế nào, thực hiện ở đâu và thực hiện công việc ra sao, độ lớn nh− thế nào. Nh− vậy thông tin thu đ−ợc xác định rất phong phú thông qua mối quan hệ của các cấu trúc thực tế trong dữ liệu và kích cỡ của toán tử. Độ chia gần đúng khi phân tích đối t−ợng có thể biết tr−ớc. Tuy nhiên trong phần lớn các vấn đề thì điều này không quan trọng. Lý do chính để xây dựng không gian độ chia đó là nếu có kiến thức biết tr−ớc về không gian độ chia thích hợp lấy từ tập CSDL có nhiều độ chia thì không gian độ chia sẽ đ−ợc áp dụng để thu gọn công thức tính toán thích hợp. Việc sử dụng các hàm làm trơn nhiễu Gauss tại các độ chia khác nhau đã đ−ợc áp dụng trong phân tích ảnh cho thấy mối liên hệ giữa các độ chia khác nhau với cấu trúc ảnh và không gian độ chia là có giới hạn. Tuy nhiên độ chia kích th−ớc hoàn toàn có thể thêm vào trong không gian miêu tả đối t−ợng vì các cấu trúc có thể đ−ợc nghiên cứu thông qua độ chia. Đặc biệt khi gắn vào tín hiệu f(x): RRN → và 1 tập liên tục ( ){ }0/, 〉ttxL làm mịn dần dần (có nghĩa là việc nhân chập tín hiệu f(x) với một hàm liên tục g(x,t)) ( ) ( ) ( ) )17.1(,, xftxgtxL ∗= ở đây g(x,t) là hàm làm mịn hoặc hàm mặt nạ, l(x,t) là tín hiệu đ−ợc làm mịn, * là phép nhân chập. Với tín hiệu liên tục thì f(x)đ−ợc khai triển nh− sau: (1.18) - 19 - 1.2.2.2. Không gian độ chia Gaussian Hàm Gausss là hàm mặt nạ hữu ích nhất cho không gian độ chia tổng quát nhất. Mang tới một tín biệu f(x): RRN → là mô tả độ chia L: RRR tN →ì đ−ợc định nghĩa nh− một mô tả tại độ chia 0 đối với tín hiệu gốc ( ) ( ) 19.10, xfxL = Và sự miêu tả độ chia kém hơn mang lại bằng phép nhân chập với mặt nạ Gauss khi đó kích th−ớc ảnh tăng lên: 1.2.2.3. Phạm vi của sự không tạo các đặc tr−ng mới Phạm vi quan trọng nhất trong không gian độ chia đó là sự không tạo các đặc tr−ng mới. Có nghĩa là sự biến đổi từ một độ chia tốt sang một độ chia xấu hơn sẽ thiết lập một tín hiệu đơn giản hơn, vì thế đặc tr−ng trong không gian độ chia mất tính đơn điệu khi độ chia gia tăng. Nó là nguyên nhân làm ảnh h−ởng tới tín hiệu và làm mờ ảnh h−ởng đối với tín hiệu hai chiều. (1.20) (1.21) (1.22) - 20 - Hình 1.3: Điểm qua 0 tại vị trí x và độ chia t của tín hiệu Các đặc tr−ng hữu ích đặc biệt tại điểm qua 0 của đạo hàm bậc thứ n. Thực tế đạo hàm bậc hai của tín hiệu đ−ợc sử dụng trong phân tích đối t−ợng, bởi đạo hàm bậc hai phản ánh điểm uốn cong của tín hiệu. Điểm cong (một đặc tr−ng hữu ích đối với phân tích đối t−ợng). Điểm qua 0 của đạo hàm bậc hai là điểm uốn cong đó là đặc tr−ng cho góc lồi ra của đối t−ợng. Với tín hiệu một chiều, điều đó đ−ợc áp dụng với không gian độ chia Gauss. Điểm qua 0 của tín hiệu tại tất cả các độ chia gọi là lấy dấu hoặc cây khoảng cách. (hình 1.3 b). Bởi phạm vi không sáng tạo của đặc tr−ng mới, việc làm mịn cuối cùng của tín hiệu đ−ợc bảo đảm. Vì vậy chiều cao của cây khoảng cách là có giới hạn. Witkin(Wit 83) giải thích cây khoảng cách này với kinh nghiệm quan sát, cành cây trong cây khoảng cách t−ơng ứng với vị trí lồi ra của đối t−ợng. ASA 84: đầu tiên trích chọn đỉnh từ cây khoảng cách thu đ−ợc và giải thích chúng nh− các đặc tr−ng vật lý( nh− góc, điểm nối, điểm kết thúc, điểm đặc biệt…) Mok96 cũng trích chọn đỉnh từ cây khoảng cách thu đ−ợc và đề nghị việc sử dụng các đặc tr−ng đỉnh thông th−ờng cho tìm kiếm hình dạng. Hoàn toàn có thể áp dụng không gian độ chia để biểu diễn hình dạng. 1.2.2.4. Không gian độ chia mâu thuẫn với việc đa quyết định Trong phân tích đối t−ợng hai ph−ơng pháp phân tích có thứ bậc th−ờng đ−ợc sử dụng: một là ph−ơng pháp không gian độ chia, ph−ơng pháp khác cây quyết định, ví dụ nh− ph−ơng pháp hình chóp và ph−ơng pháp sóng. Hai ph−ơng pháp này khác nhau: điểm khác biệt chính của hai công cụ thể hiện ở 3 khía cạnh: +Lấy mẫu không nhất quán, chống lại việc lấy mẫu các không gian khác. Biểu diễn không gian độ chia đ−ợc định nghĩa bằng việc làm mịn và l−u giữ các mẫu không gian giống nhau tại tất cả các độ chia. Trong khi lấy mẫu không gian đa quyết định tại các độ chia khác nhau là khác nhau. Đối t−ợng - 21 - chính của đa quyết định là giảm bớt lấy mẫu từ một độ chia tới các độ chia cao hơn, vì thế quá trình xử lý tín hiệu có thể hiệu quả hơn. +T−ơng quan độ chia đối nghịch với sự phân ly độ chia, ph−ơng pháp đa quyết định không khai thác điểm khác biệt của cấu trúc thông qua độ chia. Các kết quả tính toán tại mỗi một độ chia đ−ợc sử dụng duy nhất để h−ớng dẫn tính toán tại độ chia tiếp theo nhỏ hơn và đ−ợc loại bỏ một khi điều này đ−ợc hoàn thành. Chỉ thực hiện thuật toán tại một độ chia và tại một thời điểm. Ph−ơng pháp không gian độ chia chính là việc phân tích độ chia nh− một phần cần thiết của quá trình phân tích sự quan sát và nhận dạng. Phạm vi các phép đo tại các độ chia khác nhau có thể có cơ sở vững chắc phụ thuộc nhiệm vụ chứa trong nó. Bằng định nghĩa, giới thiệu không gian độ chia mang đến một giải pháp cho việc phổ biến l−ợng bù sai, điều đó có nghĩa các đặc tr−ng ở các độ chia khác nhau có thể liên quan tới những đặc tr−ng khác một cách rõ ràng. +Lấy mẫu độ chia liên tục chống lại việc lấy mẫu độ chia cố định. Giữa các ph−ơng pháp không gian độ chia và ph−ơng pháp đa quyết định đó là sự miêu tả đa quyết định chấp nhận một b−ớc lấy mẫu cố định trong độ chia hoặc quyết định đó không bị suy giảm, trong khi ph−ơng pháp độ chia phân tích tín hiệu tại độ chia liên tục. Vì vậy nhiệm vụ của việc tìm đặc tr−ng qua độ chia dễ dàng hơn trong không gian độ chia so với việc miêu tả đa quyết định. Sự tinh xảo của lấy mẫu độ chia có thể thực hiện khi có yêu cầu. Sự khác biệt các đặc tr−ng của hai loại ph−ơng pháp xác định ở cách ứng dụng của chúng. Ph−ơng pháp không gian độ chia th−ờng đ−ợc sử dụng cho phân tích và tìm hiểu tín hiệu, trong khi ph−ơng pháp đa quyết định th−ờng đ−ợc sử dụng cho mã hoá. Nó cũng cần thiết để kết hợp ph−ơng pháp không gian độ chia với ph−ơng pháp đa độ chia. Ph−ơng pháp đa độ chia đ−ợc chú ý hơn đa quyết định trong điều kiện phân tích hoặc miêu tả tín hiệu tại một độ chia tại một thời điểm. Nó không khai thác khái niệm phân tích, miêu tả tín hiệu ở độ chia liên - 22 - tục. Mối t−ơng quan tác động cấu trúc tín hiệu thông qua độ chia làm mất ý nghĩa của ph−ơng pháp đa độ chia. 1.2.3.Thảo luận ở phần trên, hai công cụ phân tích: Biến đổi Fourier và không gian độ chia đã đ−ợc mô tả và thảo luận. Phạm vi quan trọng của hai công cụ này đã đ−ợc phân tích và chọn lọc. Biến đổi Fourier miêu tả một đối t−ợng sử dụng các thành phần cơ bản của các tính chất khác nhau. Không gian độ chia quan sát một đối t−ợng với vector cơ bản có chiều khác nhau (các số chiều của vector khác nhau). Thông tin phổ thu đ−ợc từ biến đổi Fourier có thể đ−ợc sử dụng trực tiếp cho việc mô tả hoặc miêu tả đối t−ợng. Trong khi thông tin trong không gian đo đạc thu đ−ợc từ không gian độ chia cần thiết sự giải thích sâu xa hơn tr−ớc khi sử dụng mô tả đối t−ợng. Sự giải thích thông tin không gian độ chia vẫn còn là thách thức. Điều đó rất quan trọng để làm lẫn lộn giữa giải thích đối t−ợng và mô tả đối t−ợng tại đa độ chia với giải thích đối t−ợng và mô tả đối t−ợng trong không gian độ chia, đây là một vấn đề rất khó. Trong các dạng của thông tin thu đ−ợc, biến đổi Fourier thu đ−ợc thông tin đối t−ợng với hệ số tần số thấp, trong khi miêu tả thông tin đối t−ợng thu đ−ợc với hệ số rất cao. Đối với không gian độ chia, thông tin đối t−ợng chung có thể đ−ợc giải thích từ độ chia cao hơn, trong khi thông tin mô tả đối t−ợng có thể đ−ợc giải thích từ độ chia thấp hơn. Sức mạnh của hai công cụ cho phân tích đối t−ợng là rất rõ ràng. Nó đ−ợc biết đến đó là phân tích đối t−ợng hoặc trích chọn đặc tr−ng trong miền không gian là rất khó vì vấn đề nhiễu và các đối t−ợng thay đổi. Những vấn đề này có thể dễ dàng v−ợt qua bởi việc phân tích đối t−ợng trong miền phổ hoặc trong miền không gian độ chia. Cả hai ph−ơng pháp chấp nhận việc phân tích đối t−ợng tăng dần tính chi tiết. Bằng việc loại trừ hoặc bỏ qua những chi tiết tinh tế nhất trong một đối t−ợng. Đối t−ợng có thể đ−ợc biểu diễn và thể hiện hiệu quả hơn. - 23 - Từ cách nhìn nhận này, không gian độ chia xử lý t−ơng tự với biến đổi Fourier. Tuy nhiên trong không gian độ chia, những chi tiết của đối t−ợng đ−ợc dịch chuyển trong miền tần số. 1.3. Phép đo t−ơng đồng và thực hiện các phép đo Đối với việc tìm kiếm ảnh dựa trên hình dạng và các đặc tr−ng ảnh đ−ợc trích chọn th−ờng là vector đặc tr−ng N chiều, nó có thể đ−ợc đề cập tới nh− một điểm trong không gian N chiều. Một bức ảnh đ−ợc đánh chỉ mục trong cơ sở dữ liệu sử dụng các vector đặc tr−ng đ−ợc trích chọn. Việc tìm kiếm ảnh thực chất là việc xác định sự giống nhau giữa ảnh truy vấn và các ảnh mục tiêu trong cơ sở dữ liệu mà thực chất là sự xác định khoảng cách giữa các vector đặc tr−ng miêu tả hình ảnh. Sự đo đạc khoảng cách mong muốn cần phải tham chiếu với nhận thức của ng−ời. Vì vậy, đối với một đặc tr−ng hình dạng dẫn tới sự chính xác của việc tìm kiếm ảnh cao hơn, phép đo khoảng cách tốt hơn. Đối với việc tìm kiếm ảnh trực tuyến thì hiệu quả cần phải đ−ợc xem xét khi lựa chọn một phép đo khoảng cách. Nhiều phép đo khoảng cách khác đã đ−ợc khai thác trong việc tìm kiếm ảnh, chúng bao gồm khoảng cách các khối trung tâm (SWA91);(STR95); khoảng cách Ơcơlit (VOO88); khoảng cách Cosin(VOO 88), khoảng cách giao nhau của biểu đồ histoogram, hai khoảng cách thống kê(RUB99), khoảng cách bậc hai (NiB93, DEN99, WOL96, SEI97) và khoảng cách Mahalanobis…(TRE71, SMI97). Trong mục này, một vài phép đo khoảng cách sẽ đ−ợc mô tả và −ớc l−ợng. Mục đích của việc −ớc l−ợng này để tìm ra một phép đo t−ơng đồng sự mong đợi cho các bộ mô tả −ớc l−ợng hình dạng khác nhau. Để biết tìm kiếm ảnh tốt nh− thế nào, cần phải có một phép đo khả thi. Nói chung, thực hiện các phép đo đo đ−ợc sự chính xác của việc tìm kiếm ảnh. Tuy nhiên, phụ thuộc vào sự xác định độ chính xác khác nhau, có các phép đo sự thực hiện khác nhau. 1.3.1. Phép đo sự giống nhau - 24 - Một phép đo t−ơng đồng th−ờng đ−ợc định nghĩa nh− một phép đo khoảng cách. Trong phần này mô tả chi tiết các phép đo sự giống nhau khác nhau. 1.3.1.1. Không gian phép đo khoảng cách Một không gian RN là một không gian phép đo nếu cho bất kỳ hai phần tử X và Y của nó, ở đó tồn tại một số thực d(x,y) gọi là khoảng cách thoả mãn các thuộc tính sau: (1) d(x,y) ≥ 0 {Không phủ định} (2) d(x,y) = 0 nếu x = y {Tính đồng nhất} (3) d(x,y) = d(y,x) {Tính đối xứng} (4) d(x,z) < d(x,y) + d(y,z) {Bất đẳng thức trong tam giác} (1.23) 1.3.1.2. Khoảng cách dạng Minkowski Khoảng cách dạng Minkowski đ−ợc định nghĩa dựa trên tiêu chuẩn Lp: ( ) ( ) )24.1(, 1 1 0 pN i p iip TQTQd ⎟⎠ ⎞⎜⎝ ⎛ −= ∑− = ở đây Q = {Q0, Q1,…….QN-1} là vector đặc tr−ng truy vấn T = {T0, T1, …….TN-n} là vector đặc tính t−ơng ứng Khi p = 1; d1(Q,T) là khoảng cách khối trung tâm hoặc khoảng cách Manhattan (L1). ( ) ( ) )25.1(, 1 0 1 ∑− − −= N i ii TQTQd Khi p = 2; d2(Q,T) gọi là khoảng cách Ơcơlit (L2) ( ) ( ) )26.1(, 2 1 1 0 2 2 ⎟⎠ ⎞⎜⎝ ⎛ −= ∑− − N i ii TQTQd Khi p →∞ ta có L∞ L∞ (Q,T) = max {(Qi - Ti)} ; 0 ≤ i ≤ N (1.27) 1.3.1.3. Khoảng cách Cosin - 25 - Khoảng cách Cosin tính toán sự khác nhau về ph−ơng h−ớng mà không để ý tới chiều dài vector. Khoảng cách này thu đ−ợc từ việc đo góc giữa hai vector. Bằng qui tắc tích vô h−ớng: θcos.... TQTQTQ t == ( ) )28.1( . .1cos1,cos TQ TQTQd t −=−= θ Hình 1.4: (a) khoảng cách Ocolit, (b) khoảng cách Cosin, (c) khoảng cách L1 Nh− có thể thấy: khoảng cách Ơcơlit có đ−ợc tính đến cả góc lẫn chiều dài vector để tính toán. Trong khi khoảng cách Cosin chỉ tính đến góc đó khi tính toán. Nh− kết quả: Q1 và Q sẽ có khoảng cách giống nh− đối với T. dcos(Q, T) = dcos(Q1, T) . Khoảng cách tính toán d1 giữa mỗi kích th−ớc của vector đặc tr−ng (hình 1.4) 1.3.1.4. Thông tin thống kê 2χ 2χ (thông tin thống kê) đ−ợc định nghĩa nh− sau: ( ) ( ) )29.1(, 1 0 2 2 ∑− = −= N i i ii m mQTQd χ ; 2 ii i TQm += Chất l−ợng các phép đo này là việc phân bố không chắc chắn nh− từ các biểu diễn thông dụng bởi các kết quả khác (RMB 99). 1.3.1.5. Đ−ờng giao biểu đồ - 26 - Đ−ờng giao biểu đồ đ−ợc đề xuất bởi Swain và Ballard {Swa 91}. Tìm thấy những đối t−ợng bên trong các bức ảnh một cách khách quan bằng việc sử dụng biểu đồ màu sắc. Nó cũng có thể vận dụng đối sánh cục bộ. Khi kích th−ớc đối t−ợng( với đặc tr−ng Q) nhỏ hơn kích th−ớc ảnh( với đặc tr−ng trong T). Định nghĩa gốc của khoảng cách biểu đồ cho bởi công thức: ( ) ( ) )30.1( ,min 1, 1 0 Q TQ TQd N i ii hi ∑− =−= Mở rộng trong khoảng cách đo đ−ợc có công thức nh− {SMI 97}: ( ) ( ) ( ) )31.1(,min ,min 1, 1 0 TQ TQ TQd N i ii hi ∑− =−= 1.3.1.6. Khoảng cách bậc hai Những khoảng cách đ−ợc tính toán từ phép đo khoảng cách đ−ợc mô tả ở trên chỉ tính toán sự t−ơng ứng giữa mỗi kích th−ớc và không làm cho thông tin sử dụng thông qua các kích th−ớc. Vấn đề này nhận ra trong sự thích ứng của biểu đồ. Khoảng cách bậc hai đ−ợc đề xuất để tính toán đến sự giống nhau thông qua kích th−ớc (NIB93, SMI97). Nó cung cấp nhỉều kết quả hơn là sự đối sánh duy nhất giữa các biểu đồ mẫu. Khoảng cách mẫu bậc hai giữa hai vector đặc tr−ng Q và T đ−ợc tính: ( ) ( ) ( )[ ] )32.1(, 21TQATQTQd tqad −−= ở đây [ ]ijaA = ma trận N*N và aij là hệ số giống nhau giữa những chỉ số kích th−ớc i và j. aij đ−ợc tính: max 1 d d a ijij −= ; trong đó [ ]iiij TQd −= Để tính toán, khoảng cách mẫu bậc hai đ−ợc viết lại (DEN 99) - 27 - ( ) )33.1(, 2 1 1 0 1 0 1 0 1 0 1 0 1 0 ⎥⎦ ⎤⎢⎣ ⎡ ++= ∑∑ ∑∑ ∑∑− = − = − = − = − = − = N i N j N i N j N i N j jijiijjiijqad TQTTaQQaTQd 1.3.1.7. Khoảng cách Mahalanobis Khoảng cách Mahalanobis là một tr−ờng hợp đặc biệt của phép đo khoảng cách dạng bậc hai. ở đó ma trận chuyển đổi có đ−ợc nhờ ma trận hiệp ph−ợng sai thu đ−ợc từ một tập học của các vector đặc tr−ng đó là A = Σ - 1. Để áp dụng khoảng cách Mahalanobis, vector đặc tr−ng đ−ợc coi nh− không gian biến [ ]110 ,..., −= NxxxX . Sau đó ma trận hiệp ph−ơng sai lấy từ R, ở đây [ ]ijrR = với { } { }yEyxEr jiij .,= đ−ợc lấy từ không gian biến y. Sau đó ma trận hiệp ph−ơng sai là Σ ; [ ]2ijσ=Σ và { } { }jiijij xExEr −=2σ . Khoảng cách Mahalanobis giữa hai vector đặc tr−ng Q và T thu đ−ợc bằng XQ = Q và XT = T. ( ) ( )[ ] )34.1(. 211 TQTQmah XXXXd −Σ−= − Trong tr−ờng hợp đặc biệt khi xi độc lập thống kê nh−ng xác suất không bằng nhau, Σ là ma trân đ−ờng chéo: ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ =Σ − 2 1 2 1 2 0 0 Nσσ σ σ Trong tr−ờng hợp này, khoảng cách Mahalanobis đ−ợc tính lại có dạng t−ơng đ−ơng sau : ( ) ( ) )35.1(, 1 0 2 2∑− = −= N i i ii mah TQTQd σ Nó là một khoảng cách có trọng số L2 . Nó đem lại trọng số nhiều đối với kích th−ớc thay đổi ít hơn với sự thay đổi nhỏ hơn và trọng số ít hơn với kích th−ớc biến đổi nhiều hơn. 1.3.2.Thực hiện phép đo - 28 - Để định l−ợng các giải thuật khác nhau cho tìm kiếm ảnh, một phép đo hiệu quả thực hiện là cần thiết. Các phép đo hiệu quả thực hiện đã đ−ợc đề x−ớng [ ]99,98 BMILU , phép đo sự thực hiện th−ờng dựa trên việc thống kê các b−ớc thử chủ quan. Các phép đo sự thực hiện khác th−ờng sử dụng các phép thử chủ quan khác, dẫn đến các định nghĩa khác nhau về sự chính xác trong tìm kiếm ảnh. Các phép đo sự thực hiện khác nhau đ−ợc thảo luận trong phần này. 1.3.2.1. Độ nhạy và độ chính xác(RPP). RPP là phép đo sự thực hiện tìm kiếm ảnh đ−ợc sử dụng rộng rãi nhất trong các bài giảng. Về cơ bản nó dựa trên sự đối sánh tuyệt đối. Trong ph−ơng pháp này, CSDL đ−ợc chuyển thành tập nhị phân theo sự phù hợp hoặc không hợp với truy vấn dựa trên phép thử chủ quan. Trong các phép thử chủ quan, mỗi một đối t−ợng lựa chọn một tin tức t−ơng ứng với dạng truy vấn từ CSDL. Các mục đích đ−ợc lựa chọn cho mỗi truy vấn sát với các đối t−ợng có sẵn đ−ợc xem xét thích hợp tới truy vấn. Ng−ợc lại, chúng đ−ợc coi là không thích hợp. Độ chính xác và độ nhạy đ−ợc định nghĩa nh− sau: 1n rP = r : Số l−ợng các ảnh tìm kiếm phù hợp n1 : Số l−ợng ảnh đ−ợc tìm kiếm )36.1( 2n rR = n2 : Tổng số l−ợng các ảnh thích hợp trong CSDL Độ chính xác đo bằng tìm kiếm ảnh chính xác trong khi độ nhạy đo bằng khả năng tìm kiếm mục đích thích hợp từ CSDL. Độ chính xác và độ nhạy có mối hệ ng−ợc nhau. Sự chính xác thông th−ờng giảm t−ơng ứng sự gia tăng độ nhạy (cái này tăng thì cái kia giảm). 1.3.2.2. Tỷ lệ trọng số thành công (PWH- Percentage of Weighted Hits) - 29 - PWH t−ơng đ−ơng nh− phép đo độ nhạy ở RPP. Phép thử chủ quan giống nh− độ chính xác, đó là mỗi đối t−ợng lựa chọn một vài mục phù hợp với truy vấn từ CSDL. Tuy nhiên thay vì việc đo độ nhạy dựa trên giá trị nhị phân phù hợp nh− trong RPP, PWH gán một trọng số thích hợp wi cho mỗi Iterm wi t−ơng ứng. Vì vậy PWH đ−ợc định nghĩa nh− sau: ở đây, n là số iterm trả lại và N là tổng các iterm trong CSDL. Độ nhạy là tr−ờng hợp đặc biệt của PWH khi wi nhận các giá trị 0 và 1. 1.3.2.3. Phần trăm của thứ bậc giống nhau (PSR-Percentage of Similarity Ranking ) PSR đ−ợc đề xuất bởi Bimbo và Pala[bim 97], trong phép đo này mỗi đối t−ợng gán một dãy giống nhau cho mỗi iterm trong CSDL dựa trên sự t−ơng đồng của iterm với truy vấn. Điều này hơn hẳn việc gán sự thích hợp / không thích hợp nh− trong RPP và PWH. Kết quả cuối cùng của phép thử là ma trận Qj(i,k)- chỉ số thứ tự của iterm chủ đề I tại vị trí k cho câu hỏi j. Có nghĩa Pj(i) và σj(i) của mỗi hàng đã đ−ợc tính. Pj(i) và σj(i) giới thiệu thứ tự trung bình của bức ảnh thứ i cho truy vấn j và phép đo đ−ợc thoả thuận trong một thứ bậc khép kín t−ơng ứng với Pj(i). Nếu mỗi truy vấn j, một thuật toán tìm kiếm trở thành một iterm I tại thứ tự Pj(i) thì khi đó thoả thuận giữa thuật toán xếp hạng và sự xếp thứ bậc do con ng−ời thực hiện đ−ợc đo bởi PSR Sj(i): (1.37) - 30 - Đồ thị của Sj(i) nh− hàm của Pj(i) chỉ ra hiệu quả tìm kiếm của thuật toán t−ơng đối cao. Sj(i) cao chứng tỏ độ chính xác tìm kiếm cao. 1.3.2.4. Thảo luận Ba phép đo sự thực hiện đ−ợc giới thiệu, PWH chỉ ra trong tính toán số l−ợng các chủ đề khác nhau lựa chọn cho iterm t−ơng ứng. Nó đáp ứng sự sắp xếp của con ng−ời nhiều hơn trong recall ở RPP. Tuy nhiên PWH không đo khả năng loại bỏ các iterm không phù hợp trong danh sách hoàn lại. Sự bất lợi của PWH là nó lại giả thiết một số iterm cố định đ−ợc hoàn trả, điều này là không thực tế vì số iterm hoàn trả có thể khác nhau. Đối với PSR mang lại trong tính toán số l−ợng và thoả thuận của việc con ng−ời sắp xếp thứ bậc. Tuy nhiên với một truy vấn PSR mang lại một iterm chi tiết tại một thứ tự chi tiết là cao khi đó mâu thuẫn đối với truy vấn là nhỏ. Điều này dẫn đến kết quả PSR thấp nếu sự sắp xếp của thuật toán tìm kiếm khác với sự sắp xếp của con ng−ời. Mặt khác nếu mâu thuẫn lớn thì PSR có thể là cao thậm chí khi sự sắp xếp bằng thuật toán khác hẳn sắp xếp của chủ đề. Phép đo RPP có khả năng khôi phục iterm phù hợp và cả khả năng loại bỏ iterm không phù hợp. Sự bất lợi duy nhất của RPP là bỏ qua sự phù hợp của với truy vấn. Sự bất lợi này là không quan trọng nếu tập dữ liệu là một phân lớp. RPP là phép đo sự thực hiện −u việt hơn PWH và PSR. Đặc biệt thích hợp để đo sự thực hiện khôi phục dữ liệu trên tập dữ liệu lớn và đ−ợc phân lớp. 1.3.3. Trích chọn đặc tr−ng hình dạng. Trích chọn thông tin hình dạng từ dữ liệu ảnh tập trung ở đ−ờng viền và nhận thức về hình dạng là không thay đổi đối với thay đổi độ t−ơng phản( thay đổi trong độ chia màu sắc và độ chói) . Hình dạng hình học có đ−ợc mô hình nh− (1.38) - 31 - đ−ờng cong khép kín. Tuy nhiên trong một vài quan sát gần đây một phần đối t−ợng khi quan sát bị ẩn bởi các đối t−ợng khác, mặc dù vẫn còn giới hạn trong nhận thức của con ng−ời khi nhận dạng hình dạng trong ảnh.Vì vậy nhân tố hình dạng thực sự không trọn vẹn các cung t−ơng ứng của đ−ờng viền đối t−ợng, chỉ là một đoạn đối t−ợng. Trong luận văn này chấp nhận biểu diễn nhân tố hình dạng với bất kỳ đoạn cung nào. Thông tin về việc trích chọn nhân tố hình dạng từ ảnh nh− thế nào là không cần thiết cho moment, ta sẽ tính toán tập các nhân tố hình dạng đ−ợc trích chọn từ một ảnh đ−ợc giới thiệu phù hợp với biểu diễn ngữ nghĩa hình dạng của chúng. Khi hình dạng là đối t−ợng bị ảnh h−ởng của méo dạng xa gần, bằng nhận thức của mình con ng−ời vẫn có thể nhận dạng dạng đúng đối t−ợng. Để so sánh, biểu diễn hình dạng là không đổi với các phép biến đổi này và không đề cập tới các phép biến đổi trong đối sánh hình dạng, vì chúng cho phép vạch ra một lớp lớn các cung thành một đ−ờng tròn và vì thế vạch ra các cung tuỳ ý tạo thành cung tròn. Phép biến đổi trục đo có thể xấp xỉ cục bộ bằng phép biến đổi quan hệ. Hình 1:a ảnh ký tự,b) mức đ−ờng t−ơng ứng, c) Đoạn mức đ−ờng Từ nhân tố hình dạng khá cục bộ yêu cầu biểu diễn nhân tố hình dạng dạng hình học không thay đổi. Phần lớn các ứng dụng chỉ cần t−ơng đ−ơng không đổi là đủ. Vì vậy, Có thể biểu diễn mỗi nhân tố hình dạng S bằng danh sách của K bộ mô tả quan hệ hoặc sự t−ơng đồng không đổi, gọi là Code(mã) Hình 1 1.4. Thảo luận - 32 - Trong ch−ơng này một vài công cụ cơ bản sẽ đ−ợc sử dụng trong việc tìm kiếm, nhận dạng ảnh dựa vào hình dạng và trích chọn các đặc tr−ng đã đ−ợc nhắc lại. Những lý thuyết và thuộc tính quan trọng của hai công cụ trích chọn đặc tr−ng tức là biến đổi Fourier và không gian độ chia đã đ−ợc mô tả và bàn luận. Hai công cụ mà những đặc tr−ng hình dạng có đ−ợc từ những miền khác nhau. Với biến đổi Fourier có đ−ợc các đặc tính từ miền phổ và không gian độ chia có đ−ợc các đặc tr−ng từ miền không gian. Cả hai công cụ đều hữu ích cho phân tích hình dạng bởi chúng có khả năng thu đ−ợc đặc tr−ng tín hiệu của một hình dạng khi loại trừ bớt nh−ng chi tiết hình dạng tinh tế nhất. Các phép đo sự giống nhau khác và phép đo sự thực hiện cũng d−ợc thảo luận. Phép đo sự giống nhau khác đ−ợc −ớc l−ợng sử dụng các đặc tr−ng ảnh tổng quát và tập CSDL hình dạng tiêu chuẩn. Các kết quả thí nghiệm chỉ ra phép đo khoảng cách khối trung tâm là phù hợp cho khôi phục ảnh dựa trên hình dạng. Tuy nhiên nó sẽ đ−ợc sử dụng nh− phép đo t−ơng đ−ơng trong thí nghiệm khôi phục ảnh trong suốt luận văn. Một khi những tập CSDL sử dụng cho thí nghiệm trong luận văn đ−ợc phân lớp thành tất cả các nhóm giống nhau và không giống nhau, RPP sẽ đ−ợc sử dụng cho phép đo sự thực hiện. - 33 - Ch−ơng 2 Ph−ơng pháp tách contrario Ph−ơng pháp tách contrario nhằm giải quyết 3 vấn đề cơ bản trong phân tích nhóm: đầu tiên là −ớc l−ợng giá trị của nhóm, thứ hai là vấn đề nhóm có ý nghĩa này lại th−ờng chứa trong các nhóm có ý nghĩa khác, cần thiết phải định rõ nhóm có ý nghĩa nhất trong số các nhóm đó, thứ 3 là định rõ qui tắc kết hợp giữa các nhóm có ý nghĩa cho phép quyết định có sự riêng biệt giữa các nhóm hay chúng chỉ là một, nhằm mục đích nhận dạng hình dạng. Thuật toán đối sánh đ−ợc tính toán t−ơng ứng của các nhân tố hình dạng giữa hai ảnh đem so sánh và thiết lập mối quan hệ không gian giữa các đối sánh nhân tố hình dạng đ−a vào ảnh. Mỗi cặp đối sánh hình dạng dẫn tới 1 biến đổi xác định. Ch−ơng này giới thiệu lý thuyết lựa chọn nhóm đúng để nhóm các nhân tố hình dạng thành một hình dạng dựa vào việc tách nhóm trong không gian biến đổi. Thực hiện nhóm nhằm mục đích phát hiện ra các cấu trúc bằng cách phân chia điểm trong tập dữ liệu điểm thành các nhóm tự nhiên. Ph−ơng pháp này sử dụng cho vấn đề nhận dạng, đ−a vào hai ảnh, trả lời câu hỏi: hai ảnh có hình dạng nào chung. Thay vì phải phân tích nhiều nhân tố hình dạng và định rõ chúng trong mỗi cặp ảnh đ−ợc đề cập mỗi nhân tố hình dạng đ−ợc định nghĩa theo nhiều cách: nhân tố hình dạng t−ơng ứng nh− các đoạn mức đ−ờng đã đ−ợc mã hóa trong mối quan hệ xác định. B−ớc nhận dạng tiếp theo là đối sánh sự t−ơng đồng của các nhân tố hình dạng. Khi các nhân tố hình dạng là một đoạn của mức đ−ờng, mỗi thủ tục đối sánh với 1 phân tích tách biên đ−ợc mô tả chi tiết. Kết quả của thủ tục là một tập các cặp đối sánh nhân tố hình dạng. Do đối sánh cục bộ không tách hai nhân tố hình dạng của cùng 1 hình dạng đơn vì vậy các nhân tố hình dạng phải nhóm cùng nhau. Các nhóm tập các nhân tố hình - 34 - dạng đ−ợc biến đổi từ ảnh đầu tiên đến ảnh thứ hai bằng cùng phép biến đổi. Chính điều này dẫn tới việc tìm nhóm các nhân tố hình dạng có thể tính toán nh− tách nhóm thông th−ờng. Vấn đề của việc tìm ra nhóm trong tập cơ sở dữ liệu là một nghiên cứu thực sự. Nó bao gồm việc nhận dạng, phân lớp đối t−ợng trong CSDL. Tất cả các ph−ơng pháp phải đối mặt với ba vấn đề tổng quan đã nêu trên. Dubes và Miligan và Cooper đã giới thiệu giải pháp để lựa chọn số nhóm, mỗi nhóm chú ý đến qui tắc dừng trong ph−ơng thức thứ bậc. Ph−ơng pháp Contrario định nghĩa một ph−ơng pháp cơ sở cho các phép đo sự tập trung của các điểm. Trong ph−ơng pháp này, phân lớp sắp xếp tập các đoạn đ−ợc đề cập và nhóm có ý nghĩa đ−ợc tách. Sự thuận lợi của các thủ tục chính là tính hệ thống, và có thể tổng quát chung cho bất cứ chiều nào (mặc dù gánh nặng tính toán trở nên quá nặng). Tuy nhiên không giải quyết đ−ợc vấn đề ra quyết định, Grimson và Hutterloche giới thiệu một nghiên cứu trên Likelihood của điểm sai trong không gian tham số Hough. Công việc này làm cơ sở cho ph−ơng pháp tách đ−ợc giới thiệu. Các ph−ơng pháp nhận dạng tr−ớc đó kết hợp một ng−ỡng đơn với mỗi ảnh mục tiêu, độc lập với các cảnh phức tạp. Ng−ợc lại với các ph−ơng pháp trên, theo ph−ơng pháp này ng−ỡng nhóm để nhóm bị chia phải đáp ứng xác suất quan trọng. 2.1. Cluster có thứ bậc và đánh giá giá trị 2.1.1.Giá trị nhóm Contrario Định nghĩa một phép đo định l−ợng giá trị nhóm các điểm. Một nhóm sẽ đ−ợc đề cập nh− một vùng có ý nghĩa khi nó hàm chứa trong vùng có một vài điểm mong đợi nếu nh− dữ liệu đ−ợc xác định tại một không gian. Từ đó, một ph−ơng thức xác suất phải đ−ợc định nghĩa chính xác, thậm chí nó sẽ đ−ợc yêu cầu. 2.1.1.1. Cơ sở: - 35 - Trong tất cả các công thức sau, E lấy từ tập phụ RD, để lại với một phép đo xác suất π (nó sẽ đ−ợc gọi là luật cơ sở). Định nghĩa π(R) là xác suất tại một không gian điểm phụ thuộc R. Định nghĩa của π là một vấn đề cụ thể tổng quan đ−a ra một xác suất biết tr−ớc hoặc có thể −ớc l−ợng theo kinh nghiệm trên tập dữ liệu. Định nghĩa 2.1: Một xử lý nền là một xử lý các điểm có hạn (Xi) i= 1...M trong E từ các biến độc lập với nhau, định dạng phân bố theo luật π. Trình bày tập dữ liệu của M điểm (x1, x 2,... xM) trong E M , một tập phụ của tập dữ liệu sẽ là nhóm có nghĩa nếu các điểm quan trọng thuộc vào một vùng rất nhỏ, ở đó xác suất của những điểm này rất nhỏ. Vì vậy, cơ sở của ph−ơng thức Contrario là trái với giả thiết d−ới đây: (A): mô tả M ∈ Xi (i = 1,…. M) là một xử lý nền thực sự. Giả thiết cho khoảng cách E = (0,1)2 và π đồng dạng luật E. Đem M điểm trong E = (0,1)2; nó luôn có thể tìm một kết nối tập R với xác suất nhỏ tuỳ ý π(R) bao hàm trong mọi tập dữ liệu điểm. Trong thực tế, định nghĩa một nhóm có nghĩa sẽ bao hàm tổng có hạn các vùng phụ. 2.1.1.2. Nhóm có ý nghĩa. Đề cập một vùng R∈E bao gồm vùng gốc, giả thiết k điểm trong số x1...xM phụ thuộc vùng có dạng xj + R, cho 1≤ j ≤ M, nếu k đủ lớn, và π(xj + R) đủ nhỏ, chúng sẽ mô tả một tập hợp điểm trong vùng xj + R. Nhóm các điểm này sẽ đ−ợc tách trong xj + R, bằng ph−ơng pháp trái ng−ợc với ph−ơng pháp nền. Giả thiết các điểm thay đổi, nhóm có thể đ−ợc gộp lại quanh điểm xj bất kỳ và có hình dạng bất kỳ. Fix cứng xác suất cho tr−ớc, vùng R sẽ phải thuộc vào tập vùng gốc R có giới hạn, nó sẽ đ−ợc mô tả kỹ hơn. Giả thiết đơn giản hơn R giới hạn các dự tuyển #R và với mọi R∈R, O∈ R. k ≤ M ∈ N và 0 ≤ p ≤ 1 - 36 - Dạng luật nhị phân xử lý nền X1...X M và vùng R ∈ E với xác suất π (R), 1 có thể giải thích nh− xác suất tại điểm cuối k ngoài các điểm M của việc xử lý vào trong tập R. Mặc dù nghiên cứu dạng nhị thức và chúng sử dụng trong tách cấu trúc hình học có thể tìm thấy. Cho 1 ≤ j ≤ M và R' ∈ R Chú ý: X = (X1...XM): xử lý nền. Xj = (X1... XM): Xj thành phần bị thiếu. K (Xj, Xj, R '): số các điểm trong danh sách Xj phụ thuộc Xj + R '. Định nghĩa 2.2: Đặt R là một vùng dạng R = Xj + R ' j ∈ (1,...,M) và R' ∈ R. Gọi số cách báo sai của R = Xj + R' Gọi R = Xj + R ' là một vùng ε có nghĩa nếu NFAg(X, j, R') ≤ ε. Chú ý NFAg(X, j, R') cũng đ−ợc biểu thị bởi NFAg(R). Mục đích của chúng ta là giới thiệu mở rộng số l−ợng vùng có ý nghĩa ε là nhỏ hơn ε. Proposition 2.1 Nếu X1...XM là một xử lý nền, sự mở rộng số vùng có nghĩa ε nhỏ hơn ε. Để tính toán số các cảnh báo lỗi là phép đo sự giống nhau giữa các nhóm chứa trong vùng R nh− thế nào trong một tập dữ liệu điểm này ẩn chứa trong k điểm dữ liệu khác. Mức NFAg(R) thấp hơn, (Prop 2.1) thông số điều khiển tách là ε. Mệnh đề d−ới đây chỉ ra ảnh h−ởng của tham số #R và của thông số quyết định ε trong kết quả tách biên là rất ít. Mệnh đề 2.2: Đặt R là một vùng của R (2.1) (2.2) - 37 - Chú ý: k*(ε) là giá trị nhỏ nhất của điểm trong nhóm có nghĩa ε. Bằng kết quả dự đoán, quyết định ng−ỡng này chỉ có loga phụ thuộc #R và ε. Hình 2.2: Nhóm dữ liệu 950 điểm đồng dạng Hình 2.2 chỉ ra một ví dụ của nhóm dữ liệu bao gồm 950 điểm đồng dạng phân bố trong một đơn vị vuông và 50 điểm thêm vào xung quanh (0,4;0,4) và (0,7;0,7) xung quanh 950 điểm; phân bố đồng đều trong một đơn vị vuông. Trong ví dụ này #R= 2500 (50 kích cỡ khác cho mỗi chiều). Chính xác hai nhóm lớn nhất đ−ợc tách (hình 2.2) NFA của miền trái thấp hơn 10-8 trong khi NFA bên phải 107 2.1.2. Tiêu chuẩn kết hợp tốt nhất. Trong mục 2.2.1.2 đã giới thiệu hạn chế không gian của việc kiểm tra vùng từ Xi+R, Xi là mô tả dữ liệu và R∈ R , một tập hỗn hợp có giới hạn các vùng chứa vùng gốc trong RD. Độ d− thừa cao khi mỗi vùng có nghĩa lại liên quan tới tập mô tả biểu diễn các vùng có nghĩa khác. - 38 - Hai vùng R ⊂ R', câu hỏi này dễ dàng trả lời bằng việc so sánh NFAg(R) và NFAg(R'). Vùng có số l−ợng các cách báo sai nhỏ nhất là phù hợp hơn. Một cách hỏi khác khi 3 hoặc nhiều vùng liên kết với nhau, vì vậy phải yêu cầu một tiêu chuẩn hỗn hợp. Đầu tiên sẽ định nghĩa số cảnh báo sai cho một cặp vùng. Giá trị mới này đ−ợc so sánh với NFA của vùng hỗn hợp. Giới thiệu 3 hệ số danh nghĩa. Chú ý: Số này đ−ợc diễn dịch nh− sau: đặt R1 và R2 là hai vùng tách rời của E và π1= π (R1), π2 =π (R2) xác suất của chúng à(M, k1 , k2, π1 , π2) là xác suất tại giá trị nhỏ nhất k1 trong số M điểm và tại điểm thấp nhất k2 trong số M-k1 điểm, theo thứ tự là vùng R1 và R2. Mục tiêu là định nghĩa 1 NFA mới cho mỗi thành phần. Đặt 1<i ≠ j <M và R’, R”∈ R. Bây giờ 2 vùng thử Xi + R' và Xj + R'' có thể giao nhau và phải thực sự với xác suất này. Chú ý: đ−ợc mô tả bằng sự thay đổi hoàn toàn vai trò i và j: Định nghĩa 2.3: Gọi số cách báo sai của 2 cặp vùng bất kỳ (Ri, Rj) = (X i+ R', Xj + R '') (2.3) (2.4) - 39 - Cặp vùng bất kỳ(Ri,Rj) là có ý nghĩa ε nếu NFAgg(X,i,j,R',R'') < ε, NFAgg (X,i,j,R',R'') cũ sẽ đ−ợc chứa trong NFAgg (Ri,Rj). Mệnh đề 2.3: Số cặp vùng lý t−ởng nhỏ hơn ε Mệnh đề này dẫn tới 2 phép đo kém ý nghĩa: NFA của vùng và NFA của cặp vùng. Từ số l−ợng vùng có ý nghĩa ε trong ph−ơng thức nền ở trên đề cập tới biên độ t−ơng tự nhau đ−ợc so sánh để định nghĩa một tiêu chuẩn hỗn hợp Định nghĩa 2.4 (Vùng riêng biệt): Đặt R1 và R2 là hai vùng riêng biệt và R là một vùng chứa tất cả các dữ liệu điểm của R1 và R2. Nói rằng R là riêng biệt mối quan hệ với R1 và R2 nếu: Tập R là vùng thử và R là một nhân tố của R. R là riêng biệt trong R nếu nó độc lập quan hệ với mọi cặp vùng (R1, R2) chứa trong R; mỗi R chứa các điểm của vùng R1, R2 công thức (2.5) giới thiệu một phép thử chủ yếu cho kết cấu một tập hợp vùng Cluster. Nếu công thức 2.5 không xảy ra vùng thử đ−ợc coi nh− vùng không có giá trị, có nghĩa vùng thử có thể chia thành nhiều cặp vùng có nghĩa khác trong Cluster. Lenma tiếp theo sẽ cung cấp sự hữu ích trong việc gia tăng quyết định hỗn hợp. Lenma 2.1: Mỗi giá trị k1 và k2 trong (0,…., M). Mỗi k1, k2 ≤ M và mỗi π1 và π2 [0,1] sao cho π1 + π2 ≤ 1. Mệnh đề 2.4: Nếu R là riêng biệt với chú ý tới R1 và R2 Từ mệnh đề (2.4) và định nghĩa (2.4) (2.5) (2.6) - 40 - Bằng Lenma 2.1, với ( ) ( )pkMpkM ,,,,1 ββ ≤− cho mọi M, k, p công thức biểu diễn nh− sau: Mệnh đề 2.4 là hữu ích cho tính toán tổng quan, có thể tránh việc phải tính toán chi tiết 3 phân bố bằng bộ lọc các cluster đó . 2.1.3. Vấn đề tính toán 2.1.3.1. Lựa chọn vùng thử. Tập đúng của các vùng thử R nh− thế nào? Một vài lý do a > 0, r > 0 và n ∈N đề cập tới tất cả mọi vùng mà chiều dài đ−ờng biên thuộc vào tập {a, ar, ar2, arn}. Liên hệ với một số vùng thử có nhiều hình dạng kích cỡ khác nhau. Để đơn giản lựa chọn vùng thử có hình chữ nhật thích hợp với xác suất phân bố p đ−ợc định nghĩa trên miền chữ nhật E của RD là kết quả kéo căng một chiều t−ơng ứng. Định nghĩa 2.2: thừa nhận tính toán NFA của bất cứ vùng thử nào tại dữ liệu điểm. Từ số l−ợng các độ chia là n cho mỗi chiều có MnD vùng tại dữ liệu điểm. Từ số l−ợng các điểm quan sát khả thi. MnD sẽ rất lớn khi n tăng. Điều này giải thích tại sao phép thử không thể thực hiện theo cách này. Tốt hơn nên giải quyết cây cấu trúc của tập dữ liệu điểm mô tả bằng thuật toán tập trung thứ bậc. Tổ chức thứ bậc dữ liệu đ−ợc sử dụng để giới hạn các vùng thử, bằng thủ tục nh− sau: B−ớc 1: Bằng việc áp dụng ph−ơng pháp tập trung thứ bậc, ph−ơng pháp này cung cấp 1 tập hợp các tập con ẩn trong tập hợp điểm. Cấu trúc cây mà trong đó mỗi nút là một phần của tập dữ liệu và là một ứng viên Cluster. Cây này gọi là dendgrogram. Phần lớn các thủ tục đ−ợc thực hiện bởi việc lặp lại thủ tục nhị phân hỗn hợp. Vì vậy trực tiếp thiết lập cây nhị phân trong mỗi ph−ơng pháp, b−ớc khởi đầu: thiết lập nút là tập dữ liệu đơn {x1}...{xN}.Tại mỗi giai đoạn xây dựng 2 nút cha của - 41 - chúng. Khoảng cách nhóm, Cluster phải đ−ợc lựa chọn địa chỉ học. Trong tr−ờng hợp mật độ phân bố dữ liệu ít, b−ớc 1có thể khoảng cách nhỏ nhất d(xi, xj) tại xi phụ thuộc cluster đầu tiên và xj ở b−ớc 2. Các nút của cây đ−ợc tích hợp tất cả các phần tại tất cả các mức và lớp "cháu" của nút là 2 phần mà đã đ−ợc tích hợp từ đó. Tại sao mỗi một cấu trúc lại cần thiết, tr−ờng hợp tập các đoạn trong tập dữ liệu điểm lớn, thừa nhận một cấu trúc cây để giảm bớt việc khảo sát tỉ mỉ nhằm nghiên cứu một cây phụ tốt nhất đối với cấu trúc cây khởi tạo. Việc giảm bớt này dễ bị ảnh h−ởng nếu tập các nút của cây khởi tạo bao gồm tất cả các nhóm trong tập dữ liệu. Sự lựa chọn phép đo chính xác trên tập dữ liệu điểm và của khoảng cách cluster nguyên phải đ−ợc định rõ cẩn thận. Đem đến một dendrogram của tập cơ sở dữ liệu điểm, thuật toán d−ới đây chấp nhận khảo sát tỉ mỉ tất cả các vùng tại dữ liệu điểm và hàm chứa một nút của dendrogram. Thuật toán nhóm Mỗi nút G trong cây cluster hoặc dendrogram. 1- Mỗi điểm x thuộc nút: a) Tìm vùng nhỏ nhất x + R trung tâm tại điểm này, và chứa các dữ liệu điểm khác của nút. Gọi k+1 là số điểm dữ liệu mà nó chứa trong. b) Tính toán NFA của vùng nh− M.# R.B (M-1, k, p (x+R)) 2- Kết hợp với nút G của vùng R(G) với mức NFA đ−ợc tính toán thấp nhất, nó chứa điểm của nút G nh−ng cũng có thể chứa dữ liệu điểm khác. Từ thuật toán này đ−ợc tính toán, một vùng ứng cử đ−ợc kết hợp với mỗi nút bằng một chủ ý lạm dụng sự vô hại, chú ý NFAg(G) = NFAg(R(G)). Cách t−ơng tự, nếu G1 và G2 là một cặp nút và R(G1) và R(G2) là vùng của chúng. Chú ý NFAgg(G1,G2) = NFAgg(R(G1), R(G2)). Bằng cách này, cây cluster đ−ợc để lại cho NFAg và cho các cặp nút. Đặt R của vùng dạng R(G) thừa h−ởng từ cấu trúc ấy. - 42 - 2.1.3.2. Riêng rẽ và cực đại. Đối mặt vấn đề có thể có nhiều nhóm có nghĩa bởi ph−ơng pháp tr−ớc, NFA của chúng đã biết. Có thể cùng tính toán NFA của cặp cluster và so sánh thô với NFA hợp nhất của chúng. Định nghĩa tiếp theo giới thiệu một cách để lựa chọn cluster đúng, bằng việc sử dụng dendrogram cluster Định nghĩa 2.5 ( Cực đại nhóm có nghĩa ε) Một nút vùng R = R(G) trong R là ý nghĩa ε cực đại nếu và chỉ nếu: 1/ NFAg(R) ≤ ε 2/ R là riêng rẽ quan hệ với mọi cặp của sự xuống dốc. 3/ Mọi sự giảm độc lập R', NFAg(R') ≥ NFAg(R) 4/ Mọi sự tăng độc lập R', NFAg(R') >NFAg(R) hoặc tồn tại một sự giảm độc lập R'' của R khi NFAg(R'') < NFAg (R'). Ta nói rằng G là vùng ý nghĩa ε lớn nhất nếu là R(G). Điều kiện 4 bao hàm R có thể bị từ bỏ cho một vùng rộng hơn nếu vùng đó không bị áp đặt bởi một sự giảm. áp đặt điều kiện 3 và 4 chắc chắn 2 nhóm vùng ý nghĩa cực đại khác nhau là riêng rẽ. L−u ý rằng sự riêng biệt đ−ợc yêu cầu chỉ với mối liên hệ của cặp giảm. Định nghĩa 2.4 đáp ứng lý thuyết nh−ng không đáp ứng trong thực hành. 2.2. Kinh nghiệm có giá trị: Nhóm đối t−ợng dựa trên đặc tr−ng thành phần Hiện t−ợng nhóm là cần thiết trong nhận thức của con ng−ời từ đó chúng đáp ứng cho tổ chức thông tin. Mục tiêu của những kinh nghiệm này để trích chọn nhóm đối t−ợng trong ảnh, đó là hình dạng hình học mà một vài thành phần sở hữu. Đ−ờng viền đối t−ợng đ−ợc trích chọn nh− một vài đ−ờng mức t−ơng giảm trong ảnh, gọi là mức đ−ờng có ý nghĩa ([5] cho mô tả đầy đủ của thủ tục trích chọn này). Từ những đối t−ợng đ−ợc tách gọi là O1...OM, có thể tính toán cho chúng một mục D đặc tr−ng (độ chói, h−ớng, độ t−ơng phản...) Nếu k trong - 43 - số M đối t−ợng có một vài đặc tr−ng chung, liệu điều gì sẽ xảy ra khi thay đổi hoạc C nó có đủ để nhóm chúng. Mỗi dữ liệu điểm là một điểm trong tập đ−ờng viền của RD và ph−ơng pháp đã mô tả ở trên đ−ợc ứng dụng (thực tế, một vài các ngang cấp nh− góc phụ thuộc vào đơn vị tròn, từ tính chung kỳ phải đ−ợc đặt vào hàng đội, điều này có thể thực hiện với các cách t−ơng tự). 2.2.1. Nhiễu điểm Mỗi cái chứa 2 nhóm 25 điểm thêm vào 950 không đồng dạng trong một đơn vị vuông. Hai nhóm và 2 nhóm đ−ợc chọn với NFAg tốt (<10-7) kinh nghiệm trong hình 5 chỉ ra sự quan trọng của phân bố tr−ớc dữ liệu điểm. Hai phân bố khác nhau dẫn tới 2 vùng có ý nghĩa cực đại khác nhau. Nh−ng cả hai mối quan hệ đều đúng nh−ng lại phụ thuộc vào ngữ nghĩa. Hình 2.5: Vấn đề quan trọng của phân bố ph−ơng thức nền. Dữ liệu gốc là hình bên trái. Nó vị trí của 500 điểm trong 0,12 500iid điểm trong (0; 0,5) x (0; 1) và 25 điểm quanh (0,2; 0,3). Trong phần giữa; 1 phân bố tr−ớc trong ph−ơng thức nền mang lại đồng dạng. Sau đó, một vùng có ý nghĩa cực đại và độ rộng đơn đ−ợc tách, bao gồm 793 điểm và lg (NFAg)=44,9. Hình bên phải, phân bố đ−ợc định nghĩa nh− sản phẩm của phân bố lề theo kinh nghiệm trong tách dọc và tách ngang. Vùng có ý nghĩa cực đại đơn (- log10(NFAg) = 1,6) nh−ng bây giờ nó không phù hợp với nhóm nhỏ nhất. 2.2.2. Phân đoạn - 44 - Các nhóm đ−ợc nhận thức nh− 1 kết quả cộng tác giữa hai đại l−ợng trong khác nhau. Hình 2.6 chỉ ra 71 phân đoạn thẳng với h−ớng khác nhau; d−ờng nh− vị trí phân bố đồng dạng. Không cluster có ý nghĩa nào đ−ợc tách trong không gian sắp xếp vị trí của chúng. Trong tất cả các kinh nghiệm, số của kích ảnh hình chữ nhật trong mỗi lần tách là 50. Vì vậy #R= 50D. Hình 2.6: phân đoạn ảnh đã scan và 71 đ−ờng mức có mức ý nghĩa cực đại. Nếu h−ớng đ−ợc lựa chọn nh− một đặc tr−ng (D=1); 8 nhóm có ý nghĩa cực đại đ−ợc tách; t−ơng ứng với h−ớng đ−ợc biểu diễn rõ nhất. Không một cluster nào đ−ợc biểu diễn mức (trung tâm) NFAg thấp. Chỉ duy nhất một trong số các nhóm đó là riêng rẽ nh−ng h−ớng rõ ràng không phải là một nhân tố. Chú ý, nhóm này không bao gồm tất cả các phân đoạn trung tâm. H−ớng của chúng là khác nhau, và nhóm của 11phân đoạn không phải là cực đại. Tất cả các nhóm khác nhau thực sự không đ−ợc cảm nhận bởi vì chúng bị che phủ bởi sự lộn xộn tạo ra từ tất cả các đối t−ợng khác nhau. Tuy nhiên, một nhóm không thể có đối t−ợng chúng có một kết cấu phức tạp. Trong hình 2.7, có 8 nhóm có ý nghĩa cực đại. Thứ tự từ NFAg từ 10-1 đến 10-5 nhóm central không bao gồm tất cả các phân đoạn dọc, bởi vì h−ớng không chính xác. Từ đó nhóm cực đại bao gồm phân đoạn dọc không bao gồm tất cả các đối t−ợng centra. Điều có nghĩa một mình h−ớng không ảnh h−ởng tới tách nhóm - 45 - này. Nó cho phép tách nhóm tốt, nh−ng vị trí của chúng không đủ kết cấu để tạo thành kết cấu rõ ràng. Hình 2.7: Nhóm với mối quan hệ tới h−ớng. Xem xét khi đề cập tới hai đặc tr−ng (D =2; #R = 2500) trong không gian (sắp xếp, h−ớng). Hai cluster có ý nghĩa cực đại đ−ợc tìm thấy nh− mong đợi nhóm có ý nghĩa nhất là nhóm G, 11 phân đoạn dọc. NFAg của nó là 10-1,5 nó không thấp. Nhóm thứ 2 là chính xác nh−ng ý nghĩa NFAg =0,3 là rất khó khăn. Chúng khó t−ơng xứng NFAg = 0,3 trong không gian [ y...] sắp xếp va vị trí nhóm trung tâm G đ−ợc chia thành 2 cluster có ý nghĩa cực đại. Chúng t−ơng ứng với 2 hàng của phân đoạn sắp xếp G vai trò của tiêu chuẩn hỗn hợp là quyết định ở đây. Trong không gian (y - coordinate, h−ớng) sự kết hợp tiêu chuẩn cực đại và tiêu chuẩn hỗn hợp, điều đó có ý nghĩa hơn để mô tả tại cùng một thời điểm 2 hàng của 1 phân đoạn hơn ở trong một nhóm. Đây là trực quan, từ đó chúng ta thực sự thấy 2 hàng của các phân đoạn tại đây. Trái lại không gian (trong sự sắp xếp x, h−ớng) k tiêu chuẩn hỗn hợp chỉ ra mô tả G có ý nghĩa hơn mô tả hỗn hợp các lớp con của nó trong dendrogram. Quyết định này vẫn còn thích nghi với mô tả. Không một nhóm thực tế nào với G có thể là đặc biệt với chú ý tới sắp xếp x. Nhóm t−ơng tự - 46 - đ−ợc mô tả trong không gian (x coordinate, y, h−ớng) với mức thấp hơn NFAg =10-34. Hình 2.8: nhóm trong không gian(toạ độ x, h−ớng) Trong hình 2.8, có 2 nhóm có ý nghĩa lớn nhất thời gian này nhóm trung tâm đ−ợc tách (NFAg = 10-1,5) nh−ng có một nhóm khác (nhóm một phần nhóm thứ 7 trong hình 2.7). Tuy nhiên NFAg của nó = 0,3 có nghĩa nó là khó có ý nghĩa. Nếu nhóm đ−ợc thực hiện với mối quan hệ lắp đầy vị trí 2 chiều và h−ớng, chỉ nhóm trung tâm đ−ợc tách NFAg = 10-3,4. 2.3. Kết cấu nhóm không gian t−ơng ứng 2.3.1. Tại sao phải tách kết cấu không gian. Hình 2.9, có thể nhận dạng rõ ràng ở vùng trái phía d−ới của ảnh một bức tranh chi tiết của Picasso. Tuy nhiên, bức tranh đã không hoàn thành và phía d−ới ảnh bị che lại. Nó cũng bị biến dạng bởi điểm nhìn xa. Tuy nhiên, tốc độ nén là khác nhau. Nhận dạng hình dạng đ−ợc mô tả từ các điểm nhìn khác nhau và yêu cầu ngăn chặn cảm nhận trực quan. Bộ mô tả hình dạng đủ rõ ràng, cục bộ hoặc bán cục bộ. Mô tả hình dạng gọi là nhân tố hình dạng trong phần tiếp theo. Tính toán thí dụ của một truy vấn hình dạng đ−ợc biểu diễn trong một cảnh, ph−ơng pháp để nhận dạng nhân tố hình dạng t−ơng tự là có thể. Nó sẽ sẵn sàng cung cấp một vài cặp chính xác, những cung cấp sai, từ nhân tố hình dạng chỉ cung cấp thông tin cục bộ, hai đối t−ợng khác có những phần t−ơng tự có thể biểu diễn một - 47 - vài nhân tố hình dạng t−ơng ứng. Vì vậy nhận dạng yêu cầu tìm ra tập phù hợp các cặp, một tập các cặp trong hình dạng tự nhiên. 2.3.2. Đối sánh nhân tố hình dạng Lợi ích của việc hoàn thành, khái quát từng b−ớc chính của trích chọn đặc tr−ng hình dạng và thuật toán thích hợp đ−ợc mô tả và mô tả thủ tục nhóm. Mô tả đầu tiên là đ−ờng viền của đối t−ợng ở mức xám của ảnh rất hợp nhau, cuối cùng với đoạn các mức đ−ờng (hoặc) đoạn cover không phải luôn đúng: thực vậy, mức đ−ờng cung cấp một biểu diễn hoàn chỉnh của mức xám ảnh và chúng có nhiều mức trong kết cấu. Vì vậy b−ớc đầu tiên là lựa chọn một tập nhỏ trong tất cả các mức đ−ờng của ảnh. Ph−ơng pháp contrario đ−ợc giới thiệu và lựa chọn mức đ−ờng gọi là đ−ờng viền có ý nghĩa. Nó chấp nhập lựa chọn khoảng 1% mức đ−ờng của một bức ảnh không mất nội dung hình dạng. Mức đ−ờng này uốn cong và gặp đ−ờng viền ảnh ở điểm cuối cùng. Nhận dạng hình dạng là công cụ mạnh, vì thế đ−ờng viền có ý nghĩa phải chia cắt trong đoạn nhỏ hơn gọi là nhân tố hình dạng. Các hình dạng không đổi phải yêu cầu mã hóa nhân tố hình dạng không đổi; ph−ơng pháp mã hóa mối quan hệ không đổi đ−ợc giới thiệu. Chú ý trong một vài tr−ờng hợp, ph−ơng pháp không đổi t−ơng đ−ơng có thể đủ chính xác, phụ thuộc mức đ−ờng có ý nghĩa, các khung không đổi trong mối quan hệ cục bộ đ−ợc tính toán trực tiếp dựa trên mối quan hệ không đổi. Mỗi khung cục bộ định nghĩa một hệ thống tọa độ. Tọa độ của các điểm của một cung trong hệ thống, tọa độ này có thể không đổi. Hai đ−ờng cong có độ cong khác nhau trong một biến đổi quan hệ đ−ợc định nghĩa là hai khung cục bộ khác nhau. Tuy nhiên khi mô tả trong mối quan hệ của hệ thống tọa độ, chúng phải thiết lập cùng một vị trí. Từ đó chúng định nghĩa một đoạn cong thông th−ờng gọi là một nhân tố hình dạng có quan hệ không đổi. Một đ−ờng viền có ý nghĩa th−ờng chứa trong một vài nhân tố hình dạng lấy từ hai ảnh và hai tập nhân tố hình dạng, làm thế nào tìm thấy nhân tố hình dạng chung. - 48 - Từ nhân tố hình dạng đ−ợc chuẩn hoá thực hiện nhận dạng mối quan hệ tự nhiên bất biến. Một mô tả contrario đ−ợc giới thiệu để t−ơng ứng với nhân tố hình dạng. Một số l−ợng các cảnh báo sai của sự t−ơng đồng đ−ợc định nghĩa và t−ơng ứng với số các cảnh báo đ−ợc giữ lại. Đặt I và I’ là hai ảnh, tham khảo từ ảnh mục tiêu và cảnh. Mỗi cái t−ơng ứng giữa một nhân tố hình dạng S trong I và một nhân tố hình dạng S’ trong I’, biến đổi hình dạng( biến đổi mối quan hệ hoặc sự t−ơng đồng ) đ−ợc tính toán chấp nhận các tham số chứa trong nó nh− thế nào đ−ợc mô tả theo cách −ớc l−ợng đúng và cung cấp hình dạng t−ơng ứng với một hình dạng có thể thích hợp mối quan hệ tốt nhất. Phần này: cung cấp nhân tố hình dạng t−ơng ứng hình dạng đơn đ−ợc nhóm cùng nhau. Nhóm NFA của chúng nhỏ nên việc tách đáng tin cậy. Hình 2.9: Thử nghiệm Guernica Trong hình 2.9, thử nghiệm “ Guernica “. ảnh gốc và mức đ−ờng có ý nghĩa cực đại [5]. Tất cả các mức nhân tố hình dạng không đổi đ−ợc mã hóa và chuẩn hoá dựa trên sự phần đậm. Phía trên : ảnh mục tiêu; phía d−ới : ảnh và cảnh . - 49 - Hình 2.10: thử nghiệm “ Guernica “ quan hệ t−ơng ứng ý nghĩa không đổi Trong hình 2.10, thử nghiệm “ Guernica “ quan hệ t−ơng ứng ý nghĩa không đổi. Hình này cho thấy biểu diễn nhân tố hình dạng chung cho hai bức ảnh từ sự hạn chế tạo ra mối quan hệ bị bóp méo nhiều nhân tố hình dạng đ−ợc chuẩn hóa đ−ờng cong khá giống nhau. Một biến đổi quan hệ xác định t−ơng ứng với sự thích ứng giữa các nhân tố hình dạng. 2.3.3. Biến đổi mô tả 2.3.3.1. Tr−ờng hợp t−ơng đồng Đặt S và S’ là hai nhân tố hình dạng t−ơng đồng. Độ chính xác đó là một nhân tố hình dạng của một đoạn mức đ−ờng đ−ợc chuẩn hoá hóa đã đ−ợc mô tả trong frame cục bộ ( hình 2.11). Một khung không đổi t−ơng đ−ơng hoàn toàn đ−ợc xác định bởi hai điểm hoặc một điểm và một vectơ. Biểu diễn này đ−ợc chọn lựa. Một khung cục bộ mang lại bằng một cặp ( p, v ) p là khung gốc v là h−ớng và độ chia. Để tính S liên quan tới ( p, v ) và S’ liên quan ( p’, v’) từ S và S’ t−ơng ứng, chú ý các b−ớc biến đổi sự t−ơng đồng, bây giờ biểu đồ t−ơng đồng - 50 - khung cục bộ (p,v) trên (p’,v’) bằng việc hoàn thành các chú ý. Sự t−ơng đồng đ−ợc tính toán : Trong hình 2.11, hai đoạn của một mức đ−ờng và khung t−ơng tự của chúng. Biểu đồ T t−ơng đ−ơng từ R1 → R1’; R2→R2’. Tính toán khung cục bộ (R1 R2) có thể biểu diễn theo: Hình 2.11: Hai đoạn mức đ−ờng và khung t−ơng ứng 2.3.3.2. Tr−ờng hợp biến đổi mối quan hệ Đề cập tới tr−ờng hợp bình th−ờng mối quan hệ không đổi. Các đỉêm không thẳng hàng cần thiết để định nghĩa khung cục bộ. Mối quan hệ thông th−ờng của một đoạn cung đ−ợc thực hiện bằng bản đồ ba điểm ở đây (R1, R2, R3) trên bộ ba ((0,0), (0,1), (1,0)). Một bộ ba khác (R1’, R2’, R3’); đ−ợc chú ý lại bởi T. Tồn tại một ma trận M (2 x 2) và duy nhất (tx, ty) ∈R2: - 51 - Tính toán Sự phân tích này là duy nhất và hoàn toàn xác định (θ, ϕ, Sx, Sy) trong [(0,2π) ì Rì R+ ì R+]. Chú ý quan hệ ( xR1, xR2 ) và cặp ( xR1’ ,xR2’ ) của tọa độ R1 và R1’. Biến đổi tham số T = (θ, ϕ, Sx, Sy, tx, ty) đ−ợc xác định bằng tính toán đại số. Đặc tính vectơ T biến đổi thành T không mập mờ, có thể chọn một chủ tâm t−ơng tự hoặc biến đổi mối quan hệ thêm vào đó từ T đặc tr−ng T, cả hai có thể đ−ợc nhận dạng. Vì vậy viết lại X ∈ R2, T(x) thay thế T(x). Trong hình 2.12 : chỉ ra biến đổi 2-D điểm, Tk t−ơng ứng với quan hệ “ Guernica “ ý nghĩa không đổi ở hình 2.13. Hình 2.12 : thử nghiệm “ Guernica “. Mỗi biểu diễn một mối quan hệ biến đổi với một đối sánh mối quan hệ ý nghĩa không đổi mô tả bằng sáu tham số. Mỗi hình biểu diễn hai chiều cho các điểm, mối quan hệ tx và ty ( tọa độ), Biến đổi : θ (góc quay), ϕ (shear), ln(Sx) và ln(Sy) ( zoom vào x và y) trực tiếp (tọa độ). Nhiễu là do nhân tố hình dạng tổng quan đó rất giống với biến đổi mối quan hệ và nó không phụ thuộc một hình dạng thực tế. Cluster phần chính cũng đ−ợc mở rộng bởi ảnh h−ởng của việc nhìn xa. Hình 2.12: thử nghiệm “ Guernica “ - 52 - 2.3.4. Cluster có ý nghĩa của biến đổi Vấn đề của tách hình dạng đ−ợc giảm bớt vấn đề clustering trong không gian biến đổi. Nó là cần thiết để định nghĩa. 1. Một phép đo sự không t−ơng đ−ơng giữa các điểm trong không gian biến đổi. 2. Một xác suất trên không gian biến đổi. 3. Chiến l−ợc nhóm. 2.3.4.1. Phép đo sự không t−ơng đ−ơng giữa các biến đổi. Định nghĩa khoảng cách giữa các biến đổi là không đáng kể. Bởi hai lý do, đầu tiên : biên độ lớn của các tham số trong biến đổi không so sánh trực tiếp.. Thứ hai : biểu diễn về mối quan hệ t−ơng đồng hoặc biến đổi mối liên hệ không đổi không tốt nh− trong không gian vector. Nh− vậy khoảng cách là không cần thiết. Định nghĩa 2.4.1 ( tr−ờng hợp t−ơng đồng) đặt (P1, Q1) biểu diễn (P1’, Q1’) là điểm xác định khung cục bộ của S1 trong ảnh I (S1’ trong I’). Đặt T1 là t−ơng đồng duy nhất xác đinh bởi (P1, Q1) và (P1’, Q1’). Trong cách t−ơng tự T2 là t−ơng đồng xác định từ một sự t−ơng ứng giữa các hình dạng thành phần với khung (P2, Q2) và (P2’, Q2’) trong I và I’. Gọi phép đo không t−ơng đ−ơng giữa T1 và T2.Với sự hoàn thành định nghĩa một sự t−ơng đ−ơng giữa các biến đổi quan hệ. Định nghĩa 2.4.2 ( tr−ờng hợp quan hệ) : đặt T1 ( biểu diễn T2) là một biến đổi quan hệ xác định bởi hai thành phần hình dạng (S1, S1’) biểu diễn (S2, S2’). Dạng t−ơng đ−ơng từ I tới I’. Đặt (P1, Q1, R1) và (P1’, Q1’, R1’) biểu diễn (P2, Q2, R2) và (P2, Q2, R2’) xác định khung cục bộ của S1 và S1’ ( t−ơng tự S2 và S2’) đặt 2.3.4.2 Ph−ơng thức nền - 53 - Để ứng dụng tách khung, đầu tiên cần một luật cơ sở. Một dữ liệu điểm ở đây là một biến đổi t−ơng đ−ơng đ−ợc biểu diễn bởi một cặp các số (a, b) ∈ C2. Mục đích của phần này là ph−ơng pháp trên luật cơ sở, luật Π trên tập biến đổi t−ơng ứng. Với mục đích này, (a, b) đ−ợc xác định bởi hai khung cục bộ trong ảnh đ−ợc t−ơng ứng, mối quan hệ (p, v) và (p’, v’). Tính toán các mô tả này thực tế của không gian biến (p, v, p’, v’) ∈ C4. Nó tự nhiên tính toán vị trí, kích th−ớc và h−ớng của một đối t−ợng là độc lập. Đây là phần chính; ảnh h−ởng tới một vài đ−ờng viền. Thêm vào đó : hai ảnh không bao gồm các hình dạng chung cũng đ−ợc tính toán độc lập cho ph−ơng pháp nền. (A’) Đề cập một ph−ơng thức không gian ảnh I và cảnh I’. Từ không gian biến p, |v| arg v, p’, |v’| arg v’, liên hệ t−ơng ứng với nhau; giữa hai ảnh hoàn toàn độc lập. Luật giới hạn của 6 không gian biến tr−ớc đó có thể dễ dàng đ−ợc học từ hai ảnh. Từ đó luật của (P,V,P’,V’) đ−ợc tính toán. Định nghĩa không gian đối t−ợng t−ơng đồng đ−ợc chứng minh bởi (A, B), ở đây A biểu diễn góc quay và độ phóng đại, B là phép biến đổi. Luật cơ sở π không là gì nh−ng phân bố của (A, B). Biểu thức của (A, B) nh− một hàm (p, v, p’, v’) đ−ợc biểu diễn Luật cơ sở π là ảnh của luật (p, v, p’, v’) bởi ứng dụng này. Nó cũng chỉ rõ A và B không độc lập. Định nghĩa luật có điều kiện: π A là độ lớn của A và π B(b / A = a) là luật của B biết A = a. Từ |A| = |v’|/|v| và arg A = (arg v’ – arg v) mod 2π, hai biến này độc lập d−ới biểu thức A’. Vì vậy phân bố π A có thể dễ dàng đ−ợc tính toán. Tuy nhiên nó tạo ra A độc lập từ p và p’. - 54 - Từ đó luật của B = p’- Ap, điều kiện để A = a là luật của p’-ap, có thể dễ dàng tính toán. Thực tế tính toán của π giữa hai ảnh nh− sau : 1. Tính toán tất cả các hình dạng thành phần của ph−ơng thức và ảnh mục tiêu. 2. Tính toán kinh nghiệm luật của p, v, p’, v’ từ vị trí; độ chia và h−ớng của frame cục bộ liên quan tới thành phần hình dạng trong hai ảnh của biểu thức cơ sở (p, v, p’, v’) 3. D−ới biểu thức t−ơng tự, tính toán luật theo lối kinh nghiệm |A| = || |'| v v và arg A = (arg v’ – arg v) mod 2π 4. Với mỗi giá trị A của A với không tham số NULL, tính toán phân bố theo lối kinh nghiệm p’- Ap. Xác xuất của vùng R xấp xỉ : Một vài từ về −ớc l−ợng gần đúng của ph−ơng pháp nền: một sẽ là mong arg A phân bố đều trong [-π,π], mặc dù phân bố theo chiều dọc hoặc ngang đôi khi tập trung hơn. Phân bố của phần chính |A| đ−ợc thay thế từ một các đồng dạng, lý luận một xác suất phân bố thực tế tr−ớc cho |A| hoặc B lấy từ A. Phân bố ph−ơng pháp nền phải đ−ợc học từ cảnh và ảnh mục tiêu. Chú ý : ý t−ởng giới thiệu ở đây cũng giữ cho cluster biến đổi mối quan hệ. Cho tr−ờng hợp này θ, ϕ, Sx, Sy đ−ợc đề cập tới là độc lập với nhau. Phân bố của chúng có thể đ−ợc học từ kinh nghiệm nh− xác suất phân bố của (tx, ty) từ (θ, ϕ, Sx, Sy). Cấu trúc này, đáp ứng kinh nghiệm mặc dù không có lý thuyết nào chứng minh trực tiếp. 2.3.4.3. Kỹ thuật nhóm - 55 - Có một vài ph−ơng thức xây dựng một cây nhị phân từ tập dữ liệu và phép đo không t−ơng đồng. Trong phần này : Cây chiều dài cực tiểu đ−ợc sử dụng. Cấu trúc của nó đ−ợc sử dụng một thuật toán kết nối đơn làm việc nh− sau. Độ không t−ơng đồng nào giữa hai điểm dữ liệu đ−ợc mở rộng tới bất kỳ cặp nào cảu tập tách rời tập dữ liệu điểm A và B bằng : Một cây nhị phân đ−ợc cấu trúc bởi thủ tục lặp : mỗi dữ liệu điểm đ−ợc coi nh− là nút lá. Sau đó kết hợp cặp gần nhất của nút thành nút đơn. Lặp lại cho đến khi mọi nút đ−ợc tích hợp trong tập dữ liệu. Bằng việc thay thế min bởi max về phép tính trên, một cây chiều dài cực đại đ−ợc mô tả thay thế. Lựa chọn một cây hoặc cây còn lại có thể đ−ợc áp dụng nh−ng không có cách nào tổng quan hơn. 2.4. Thảo luận Phần này giới thiệu tổng quan việc tách và lựa chọn nhóm trong tập dữ liệu điểm. Nhóm có ý nghĩa không thể sinh ra bởi sự ngẫu nhiên. Chúng có thể đ−ợc địng nghĩa nh− độ lệch lớn từ một giả thiết độc lập của các điểm hàm chứa chúng. Điều này cho phép định nghĩa một phép đo của sự có ý nghĩa, số các cảnh báo sai( NFA). Trong tất cả các nhóm có ý nghĩa chỉ những nhóm không thể chia thành nhóm nhỏ hơn là thích hợp. Ph−ơng pháp t−ơng tự có thể dẫn tới việc lựa chọn các nhóm có ý nghĩa cực đại này. Ph−ơng pháp này phụ thuộc vào các b−ớc cluster mà cluster lại phụ thuộc rất nhiều vào ng−ời sử dụng và tính toán NFAg phải thích nghi với các nhóm phát sinh. Ph−ơng thức sử dụng để tìm ra đặc tính thực sự liên quan tới dạng nhóm trực quan trong tập đối t−ợng. Làm thế nào để lựa chọn đặc tính để mô tả nhóm có ý nghĩa và ở đây thủ tục cluster đ−ợc đề cập là phép phân tích vận động trực quanvà giới thiệu tách trong không gian thời gian t−ơng ứng. - 56 - Ch−ơng 3 Ph−ơng pháp ra quyết định Contrario Nhận dạng hình dạng là nhận biết ra hình dạng dựa trên các kiến thức biết tr−ớc, cụ thể ở đây là tìm ra có hay không hình dạng truy vấn trong CSDL hình dạng. Phần lớn các ph−ơng pháp nhận dạng dựa trên phép đo t−ơng đồng hoặc không t−ơng đồng. Quyết định cuối cùng trả lời rõ ràng có hay không hai hình dạng giống nhau. Phần này đ−a ra giải pháp nhận dạng chủ yếu dựa vào giới hạn số cảnh báo sai(NFA) của truy vấn hình dạng trong số hình dạng trong CSDL. Ph−ơng pháp ra quyết định với ít tham số hơn để quyết định có hay không hai ảnh bất kỳ chia sẻ một số hình dạng. Biểu diễn hình dạng đ−ợc đề cập với nguyên tắc là sự nhận biết. Xác định t−ơng ứng giữa các nhân tố hình dạng không chỉ là định nghĩa một khái niệm sự t−ơng đồng giữa chúng, nh−ng cũng có thể quyết định có hay không 2 thành phần hình dạng là một cặp. Phần này giới thiệu luật ra quyết định tự động, áp dụng ph−ơng pháp này để đối sánh hình dạng và mở rộng phạm vi của ph−ơng pháp so với lý thuyết. Đặc biệt, ý nghĩa luật tự động ra quyết định với đối sánh hình dạng trong một CSDL mà có thể dựa vào khoảng cách giữa các hình dạng. Từ hai hình dạng và một khoảng cách δ rất nhỏ giữa chúng có hai khả năng: 1- Cả hai hình dạng ở cùng một khoảng cách khi đối sánh 2- CSDL hình dạng đ−ợc trích chọn quá lớn, phải thay đổi một trong số những hình dạng này kết thúc S (Giữa chúng không có đối t−ợng giống nhau) - 57 - Giả thiết, mỗi δ có thể −ớc l−ợng, xác suất xảy ra khả năng thứ hai. Nếu số l−ợng này xảy ra rất nhỏ đối với hai hình dạng thì khả năng thứ nhất đ−ợc giải thích tốt hơn. Ph−ơng pháp này gọi là quyết định Contrario. Trong hệ thống quan sát tính toán, sự thử đầu tiên để có khả năng tách trong một ảnh Contrario tới một không gian tuần tự từ phân tích trực quan của David Lowe. Các đối t−ợng tìm kiếm đ−ợc mã hóa bằng h−ớng biên và so sánh bằng cách sử dụng một quan hệ khoảng cách Hausdory. Đ−a ra −ớc l−ợng xác xuất xuất hiện cảnh báo sai của bản thân ảnh; sử dụng xác suất này để ra một quyết định. Một ph−ơng pháp sử dụng −ớc l−ợng để thiết lập ng−ỡng đối sánh mỗi một xác suất của một cảnh báo sai d−ới mức của một vài xác suất xác định tr−ớc. Tuy nhiên, vấn đề trong khi Cluster ảnh đúng hay sai có thể có nguyên nhân từ ng−ỡng đã thiết lập. Grimson và Hutten giới thiệu ng−ỡng cố định trên tỷ lệ của các ph−ơng thức đặc tr−ng : “ Biên trong số đặc tr−ng của ảnh ( đề cập tới biến đổi không gian ) dựa trên việc tách chính xác. Chấp nhận phần lớn các đặc tr−ng phân bố đồng đều( ph−ơng pháp nền ), để hạn chế tính ngẫu nhiên thuật ngữ nàyphải định nghĩa. Ph−ơng pháp tính toán dựa vào một số giả thiết hạn chế( ph−ơng pháp hình dạng có sẵn; các đặc tr−ng phân bố đồng đều). Những giới hạn này là khó khăn cho từng tr−ờng hợp thực tế. Ví dụ trong ảnh y tế của não bộ, các điểm không phân bố đều trên ảnh nh−ng không quá ngẫu nhiên trên bề mặt vỏ não và sọ não. Mở rộng sẽ tính toán xác suất sai xác thực trực tuyến trong khi nhận dạng. Việc này cho phép chúng ta thống kê lại xác xuất phân bố đặc biệt của ph−ơng thức và đặc tr−ng cảnh. Đây là mục tiêu hoàn toàn chính xác. Ph−ơng pháp xác suất đáng tin cậy cho vấn đề hình dạng t−ơng ứng và đ−a ra một ph−ơng pháp để tính toán tự động mức ng−ỡng đối sánh đúng. Thay vì định nghĩa khoảng cách ng−ỡng cho mỗi truy vấn hình dạng, định nghĩa số cảnh báo sai NFA, có thể là ng−ỡng độc lập với truy vấn hình dạng. NFA có thể đ−ợc - 58 - giải thích nh− một số mong muốn các hình dạng ngẫu nhiên tại một vài khoảng cách từ một truy vấn hình dạng, thậm chí ng−ỡng NFA dẫn tới ng−ỡng đối sánh khoảng cách, chỉ ra khi thêm một thông tin vào đối sánh sự t−ơng đồng ta sẽ có đối sánh đúng đến mức nào. Đối sánh sẽ khắc phục vấn đề tổng quát của quyết định có hay không hai nhân tố hình dạng đ−ợc biểu diễn bởi một mã quan hệ không có sự giống nhau bất biến. Phần này giới thiệu khái niệm đối sánh có ý nghĩa, nó có thể sắp xếp các đối sánh với một nhân tố hình dạng chuẩn hoá với một ý nghĩa chính xác và thuận tiện: số các cảnh báo sai( NFA). Tuy nhiên, ng−ợc lại với phần lớn ph−ơng pháp đang có, không chỉ NFA mà ta có thể sắp xếp thứ tự các đối sánh từ thấp đến cao, nh−ng ng−ỡng tách thích hợp với truy vấn hình dạng và cơ sở dữ liệu cùng thu đ−ợc từ đ−ờng viền đồng dạng dựa trên NFA. Ph−ơng pháp quyết định trích chọn đ−ờng viền đ−ợc giới thiệu dựa trên việc chuẩn hoá cung tròn, nhân tố hình dạng đ−ợc trích chọn từ ảnh, rồi tính toán đối sánh và sau đó ra quyết định. 3.1. Một quyết định Contrario ở đây fix cứng mức ng−ỡng để chấp nhận hay loại bỏ ng−ỡng nhận dạng nhân tố hình dạng, tiến tới một phân lớp cố định. Mỗi nhân tố hình dạng đ−ợc mô tả bởi một mã( một danh sách các đặc tr−ng bất biến của một vài không gian đặc tr−ng). Nhận dạng là vấn đề khó: từ cách lựa chọn nhân tố hình dạng theo một phép đo t−ơng đ−ơng, một truy vấn nhân tố hình dạng phải trả lời câu hỏi “ có hay không có nhân tố hình dạng giống nh− nhân tố hình dạng truy vấn, trong tr−ờng hợp đó, cốt yếu ở tự động thiết lập ng−ỡng δ trên phép đo t−ơng đ−ơng và đem lại một mức thích hợp để ra quyết định. Đây là mục tiêu của ph−ơng pháp này. Xây dụng một ph−ơng pháp thống kê của CSDL nhân tố hình dạng và các đối sánh quan hệ đ−ợc tách Contrario. 3.1.1. Ph−ơng pháp hình dạng trái ng−ợc ph−ơng pháp nền - 59 - Đầu tiên phải định nghĩa chính xác biểu diễn nhân tố hình dạng và một vài khái niệm khác. Mục tiêu của ph−ơng pháp là so sánh truy vấn nhân tố hình dạng S với nhân tố hình dạng N của CSDL B. Giả thiết mỗi nhân tố hình dạng S đ−ợc biểu diễn bởi tập K đặc tr−ng X1(S), X2(S), …. , Xk(S) ; mỗi nhân tố hình dạng đều thuộc một không gian đo ( Ei , di ) i ∈ {1, … , k }. Định nghĩa khoảng cách giữa các nhân tố hình dạng nh− khoảng cách : E1 x E2 x … x Ek d( S , S’ ) = max di( xi(S), xi(S’) ) i = {1 … k} Một CSDL hình dạng S đ−ợc quan sát hoặc khoảng cách d(S,S’) chính xác hơn giữa hai truy vấn đ−ợc quan sát. Vấn đề là khoảng cách d(S,S’) có đủ nhỏ để ra quyết định cặp S,S’ tạo thành cảnh hay khoảng cách d(S,S’) quá lớn nên chúng không thể tạo thành bất cứ cảnh nào. Định nghĩa 3.1 : gọi ph−ơng pháp nền, bất kỳ ph−ơng pháp ngẫu nhiên (Ω, A, Pr ), mỗi tham số phụ thuộc công thức sau : đ−ợc tính toán độc lập, chú ý bởi Pi( S, δ ), Tỉ số theo kinh nghiệm: ở đây, # tập hữu hạn và N là các nhân tố hình dạngthuộc CSDL B, nh− một sự −ớc l−ợng của Pi( S, δ ) cho mỗi giá trịδ .Sử dụng trong thực tế Pi( S, δ ) = N 1 , # { S’∈B, di( xi(S), xi(S’) ) ≤ 0} 3.1.2. Ph−ơng thức quyết định Contrario Hàm khoảng cách giữa các nhân tố hình dạng, quyết định có hay không một đối sánh nhân tố hình dạng này với nhân tố hình dạng khác dựa vào tập mức - 60 - ng−ỡng khoảng cách δ . δ đ−ợc thiết lập tự động. Tìm cách thay thế giới hạn khoảng cách bằng giới hạn xác suất của cách báo sai. Một hình dạng S’ đ−ợc quan sát, lý thuyết: H0: “ S’ đ−ợc sinh ra từ ph−ơng thức của S “. Tuy nhiên, vận dụng lý thuyết này với sự thừa nhận( không một ph−ơng thức hình dạng nào có sẵn cho S ) là dễ dàng. Vì vậy dẫn tới tập trung thay đổi lý thuyết xen kẽ H1 :“ S’ đ−ợc phát sinh từ ph−ơng thức nền ”. Cho mỗi δ ; “tập nhân tố hình dạng đ−ợc chia thành hai tập con Ω0(δ), Ω1(δ)”, quan hệ từ nhân tố hình dạng với khoảng cách của chúng tới S thấp hơn δ thì lý thuyết H0 đ−ợc chấp nhận và khoảng cách S >δ (H0 bị từ chối). Định nghĩa 3.2: truy vấn nhân tố hình dạng S đ−a tới tập thử Tδ(S) đ−ợc định nghĩa nh− sau: - Nếu 1 tập CSDL nhân tố hình dạng S’ có d(S,S’)< δ thì lý thuyết H0 đ−ợc chấp nhận (S’ gần với S bởi 1 vài quan hệ) tr−ờng hợp này S’ đ−ợc phân lớp vào Ω0(δ) - Còn lại H0 bị loại trừ và thay đổi lý thuyết H1 đ−ợc chấp nhận(S’ gần S). Tr−ờng hợp này S’ đ−ợc phân lớp vào lớp Ω1(δ) Đặc tính của các phép thử thống kê là phép đo bởi xác suất quyết định sai, có thể có 2 loại lỗi, lỗi thứ nhất: loại bỏ H0 cho một quan sát S, H0 lại là có thực (dạng lỗi tách sai) và loại lỗi thứ hai: chấp nhận H0 cho S mặc dù H0 là sai (lỗi sai vị trí),vậy phép đo xác suất lỗi xác địng nh− sau: - Xác suất không tách hoặc 1 lỗi(liên quan loại lỗi 1) là: - Xác suất cảnh báo sai( liên quan loại lỗi 2) , là gần đúng lớn nhất của H0 t−ơng ứng H1 trên Ω. Rõ ràng là thấp hơn α và α’, phép thử tốt hơn α và α’ không thể đánh giá độc lập. Vấn đề để tìm ra sự thoả hiệp giữa 2 xác suất này. Mở rộng sử dụng kỹ thuật cho việc tìm tỷ lệ phép thử gần đúng nhất và phép thử Bayes. Tuy nhiên, lý thuyết là có giới - 61 - hạn. Việc gần đúng của lý thuyết H0 và H1 là khó thực hiện nếu mục tiêu nhận dạng là 1 truy vấn hình dạng xác định rõ( ph−ơng pháp chung thực sự cần thiết truy vấn hình dạng S để tính toán gần đúng 1 hình dạng S’ d−ới lý thuyết H0). Tuy nhiên, lý thuyết này cần các thông tin biết tr−ớc, còn các thông tin khác có thể bổ xung sau. 3.1.3. Ước l−ợng xác suất cảnh báo sai Tóm lại không thể tính toán xác suất của việc không tách Pr(Ω1(δ)/H0). Tính toán cung cấp giá trị xác suất cảnh báo sai của phép thử thống kê Tδ(S) chú ý PFA(S, δ)= Pr(Ω1(δ)/H1) từ S’∈ Ω0(δ) nếu d(S,S’) ≤δ nó phụ thuộc công thức sau: Định nghĩa: vì vậy: Tính toán lại ta có: Proposition 3.1: Xác suất cảnh báo sai cho phép thử thống kê Tδ(S) là : Đặt lại, theo kinh nghiệm sẽ sử dụng −ớc l−ợng cho Pi(S, δ) với i∈{1, k} 3.1.4. Luật ra quyết định Contrario B−ớc tiếp theo, để giới hạn PFA, xác suất cảnh báo sai PFA(S, δ) không suy giảm với δ, muốn giảm giới hạn của xác suất cảnh báo sai PFA phải bằng cách gia tăng khoảng cách δ* : - 62 - Do vậy nếu phép thử chấp nhận lý thuyết H0, nếu khoảng cách quan sát nhỏ hơn δ*(p) và để loại trừ lý thuyết bằng nhau, kết hợp xác suất cảnh báo sai đ−ợc giới hạn bởi p, luật này gọi là quyết định Contrario. PFA kết hợp với phép thử thống kê rất thấp vì vậy thay đổi nó là không hợp lý. ứng dụng cho nhận dạng hình dạng, chấp nhận lý thuyết 1 tập nhân tố hình dạng S’ t−ơng ứng với truy vấn hình dạng đối sánh S coi nh− S’ gần S. Chú ý, đối sánh nhân tố hình dạng giống nhau nh−ng không hẳn t−ơng ứng với các đối t−ợng nh− nhau. 3.2. Tự động thiết lập ng−ỡng khoảng cách 3.2.1. Số các cảnh báo sai NFA Quyết định contrario đ−ợc giới thiệu cốt yếu là cố định mức ng−ỡng của xác suất cảnh báo sai hơn là khoảng cách giữa các nhân tố hình dạng. Từ một xác suất ít ý nghĩa, giới thiệu số cảnh báo sai cùng độ chính xác đó, trong đó truy vấn nhân tố hình dạng đ−ợc so sánh với nhân tố hình dạng từ một tập CSDL kích th−ớc N. Định nghĩa 3.3 : số các cảnh báo sai của nhân tố hình dạng S tại khoảng cách d là : Từ kết quả cuối cùng của xác suất là xác suất cảnh báo sai khi thực hiện phép thử, nếu CSDL nhân tố hình dạng tại một khoảng cách( thấp hơn d) số các cảnh báo sai có thể thấy nh− trị trung bình số cảnh báo sai đ−ợc mong đợi khi thử, quyết định có hay không khoảng cách từ mỗi nhân tố hình dạng trong CSDL S là nhỏ hơn d. Chú ý: từ mỗi Pi là −ớc l−ợng theo kinh nghiệm trên tập CSDL B ; (NFA phụ thuộc B ). - 63 - Định nghĩa 3.4: số cảnh báo sai của truy vấn nhân tố hình dạng S là số cảnh báo sai của S tại một khoảng cách d(S, S’ ). Số các cảnh báo sai giữa S và S’, t−ơng ứng sự mong đợi của CSDL hình dạng nó là các cảnh báo sai và khoảng cách của nó tới S thấp hơn d(S,S’ ). Chú ý: chú thích t−ơng tự đ−ợc sử dụng cho cả dự đoán định nghĩa số các cách báo sai, cùng chú ý argument của NFA cuối cùng. 3.2.2. Đối sánh có ý nghĩa Thay vì giới hạn trực tiếp xác suất cảnh báo sai để giảm ng−ỡng khoảng cách nh− đã giải thích, giới hạn số các cảnh báo sai NFA giải thích cho tần suất xuất hiện nh− mong đợi. Định nghĩa 3.5: Nhân tố hình dạng S’ là một đối sánh có ý nghĩa ε của truy vấn nhân tố hình dạng S nếu số các cảnh báo sai của chúng đ−ợc giới hạn bởi ε: NFA(S,S’)≤ ε Chú ý từ hàm, không suy giảm, hàm có thể đảo ng−ợc chú ý tới khoảng cách d. Tồn tại một số thực xác định duy nhất δ*(ε/N) cũng phụ thuộc vào truy vấn hình dạng S: Tiên đề 3.2: 1 nhân tố hình dạng S’ là đối sánh có ý nghĩa ε của truy vấn nhân tố hình dạng t−ơng đ−ơng: d(S,S’)≤ δ*(ε/N) Đối sánh có ý nghĩa ε của S là các nhân tố hình dạng cho khoảng cách δ* < (ε/N). Xác suất cảnh báo sai của các phép thử lần l−ợt nhỏ hơn ε/N. Mặc dù, trị trung bình cảnh báo sai nhỏ hơn ε trong số tất cả các đối sánh có ý nghĩa ε trên N nhân tố hình dạng đ−ợc thử. Ph−ơng thức này không thể −ớc l−ợng số đối sánh có - 64 - ý nghĩa ε. Tuy nhiên, nếu mọi nhân tố hình dạng trong tập CSDL đ−ợc xuất phát bởi ph−ơng pháp nền, lý thuyết H0 không bao giờ đ−ợc chấp nhận và tách có ý nghĩa ε vì vậy sẽ đ−ợc đề cập nh− cảnh báo sai. Proposition 3.3: giả thiết CSDL nhân tố hình dạng chỉ rõ phân bố theo ph−ơng pháp nền; dự báo của số các đối sánh có ý nghĩa ε < ε. Đặt S’j=(1≤j≤N) chú ý nhân tố hình dạng trong tập CSDLvà χj là hàm của thành phần ej ( S’j là đối sánh của truy vấn S (giá trị của nó là 1 nếu S’j thực sự là đối sánh có ý nghĩa ε của S và là 0 với các giá trị khác). Đặt ∑ = = N j jR 1 χ là không gian biểu diễn hình dạng có ý nghĩa ε t−ơng ứng với S. Dự đoán của R là ( ) ( )∑ = = N j jERE 1 χ sử dụng tiên đề 3.2: Từ các nhân tố hình dạng trong CSDL đ−ợc giả thiết thỏa mãn giả thiết ph−ơng pháp nền: Tính tuyến tính của dự đoán t−ơng đ−ơng biểu thức: Bằng định nghĩa δ* có ( ) ∑ = −≤ N j NRE 1 1.ε vì vậy ( ) ε≤RE Điểm mấu chốt này là tính tuyến tính của dự đoán cho phép tính toán E(R). Từ sự phụ thuộc giữa các thành phần ej không đ−ợc biết, ta có thể −ớc l−ợng luật phân bố xác suất của R. 3.2.3. Ng−ỡng nhận dạng t−ơng ứng với ngữ cảnh Chú ý rằng xác suất thử nghiệm đem vào tính toán sự ngẫu nhiên hoặc tính phổ thông của đối sánh có thể: ng−ỡng δ* là hạn chế hơn trong tr−ờng hợp đầu tiên và khắt khe hơn trong các tr−ờng hợp khác. Nếu truy vấn hình dạng S1 hơn - 65 - một truy vấn S2 khác; CSDL hàm chứa nhiều hình dạng kết thúc S2 hơn S1, nhỏ hơn khoảng cách cố định d’ nào đó. Nếu truy vấn hình dạng S1 hiếm hơn S2 ta có : i∈{1, k} vad d < d’: Hiệu suất này *1 * 2 ss δδ ≤ ( cung cấp cả hai số l−ợng nhỏ hơn d’). Càng hiếm các hình dạng tìm kiếm thì ng−ỡng nhận dạng càng cao. Phép tính toán khác của giới hạn t−ơng tự nh−: nếu đem lại một truy vấn hình dạng trong số các hình dạng của CSDL B1 hiếm hơn là CSDL dạng cao hơn B2. Có i∈{1, k} và d đủ nhỏ: ở đây 1iP , 2 iP là −ớc l−ợng riêng trên B1 và B2, ( ) ( )SS *1*2 δδ ≤ . Kết quả là ng−ỡng đ−ợc giới thiệu bởi thuật toán tự động thích nghi liên quan đến sự biến thiên của truy vấn hình dạng trong CSDL hình dạng. Càng hiếm truy vấn hình dạng thì ng−ỡng khoảng cách t−ơng ứng càng tùy ý hơn và ng−ợc lại. 3.2.4. Tại sao quyết định Contrario Tiến bộ của quyết định Contrario dựa trên NFA đ−ợc so sánh với tập các ng−ỡng khoảng cách trực tiếp giữa các nhân tố hình dạng một cách rõ ràng. Ng−ỡng NFA là khá thuận lợi so với ng−ỡng khoảng cách. Thực vậy, đơn giản đặt ε = 1 và cho phép tại phần lớn cảnh báo sai trong các đối sánh có ý nghĩa hoặc ε = 10-1 nếu ta muốn lạm dụng sự tin cậy cao hơn trong đối sánh thu đ−ợc. Ng−ỡng tách ε đ−ợc đặt t−ơng đ−ơng dù truy vấn hình dạng là nh− thế nào và CSDL có thể là kết quả khoảng cách thích nghi tự động phụ thuộc vào chúng theo giải thích ở trên. Nói cách khác, ε thấp hơn, chắc chắn tách có ý nghĩa hơn. Tuy nhiên tính toán NFA không cần thiết cho bất cứ ph−ơng pháp hình dạng nào. Nó là tiến bộ chính của ph−ơng pháp giới thiệu, có một ph−ơng pháp - 66 - hình dạng có nghĩa là truy vấn hình dạng để nhận ra tr−ớc khi dùng cách này hay cách khác. Kết thúc với định nghĩa số cảnh báo sai khi so sánh mọi hình dạng trong CSDL với mọi hình dạng khác trong CSDL và không chỉ nhân tố hình dạng trong một CSDL. Điều này t−ơng ứng với thử nghiệm ở mục sau. Hai nội dung hình dạng của hai ảnh đ−ợc đối sánh. Khi tìm kiếm hình dạng phụ thuộc CSDL B1 tạo ra hình dạng N1; trong số các nhân tố hình dạng N2 phụ thuộc CSDL B2. Định nghĩa 3.6: Số các cảnh báo sai của một hình dạng tại khoảng cách d: ( ) ( )( ) ( ) ( )( )dkiSxSxdSNNdSNFA iii ≤∈ìì= ,1,',max,Pr, '21 Xác suất (phụ thuộc vào hình dạng S đ−ợc tìm kiếm) đ−ợc −ớc l−ợng nh− tr−ớc, nh− kết quả của K −ớc l−ợng thử nghiệm trên tập B2 trong số các truy vấn hình dạng đ−ợc tìm cho mỗi hình dạng trong B1, định nghĩa đối sánh có ý nghĩa ε. Mục tiêu, trị trung bình các cảnh báo sai ε trong số đối sánh có ý nghĩa trên N1, N2 cặp đ−ợc thử không thay đổi. 3.3. Xây dựng đặc tr−ng độc lập thống kê Khá quan trọng khi đề cập đặc tr−ng độc lập (cf(A)). Khi sử dụng đặc tr−ng độc lập là một cách để giảm kích th−ớc của CSDL. Bằng sự kết hợp một vài đặc tr−ng độc lập, có thể dễ dàng tìm số cảch báo sai rất thấp mà không cần CSDL lớn để −ớc l−ợng xác suất cảnh báo sai PFA. D Lowe giới thiệu tổng quan cho nhận dạng trực quan” bởi giới hạn sự chính xác của phép đo ảnh( và xác suất cũng thiếu các đoạn quan hệ trong thế giới tự nhiên)” Mối quan hệ đơn giản đ−ợc mô tả th−ờng bị lỗi so với mức xác suất xuất hiện ngẫu nhiên rất thấp, mối quan hệ này phải đủ mạnh để nhận dạng. Tuy nhiên, những kết quả hữu ích có thể gia tăng nh− kết quả tìm kiếm hỗn hợp tạo thành các quan hệ hỗn hợp mới, nó phải có xác suất xuất hiện mới thấp hơn. Xem xét một ví dụ bằng số. Nếu đề cập tới CSDL đ−ợc tạo ra từ N nhân tố hình dạng giá trị thấp nhất có thể tìm thấy bằng xác suất theo kinh nghiệm:# - 67 - ( ) ( ) ( )( ){ }dSxSx N dSP iii ≤∈ì= ,'1, id,S'# β Tại giá trị thấp nhất 1/N. Nếu ph−ơng pháp nền xây dựng trên k =1 đặc tr−ng và CSDL N =1000 hình dạng. Giá trị thấp nhất có thể tìm thấy số cảnh báo sai là 1000.1/1000=1. Điều này có nghĩa nếu hai nhân tố hình dạng S và S’ d−ờng nh− đ−ợc định dạng dựa trên NFA ta có thể chắc chắn đối sánh này không ngẫu nhiên. Thực vậy NFA =1 có nghĩa trị trung bình 1 hình dạng trong CSDL có thể đối sánh với S bằng sự thay đổi. Giả thiết ph−ơng pháp nền đ−ợc xây dựng trên 6 đặc tr−ng (N=1000) Số cảnh báo sai thấp nhất đ−ợc tìm thấy 1000.1/10006=10-15 Trong thực tế, quan sát số các cảnh báo sai giữa hai hình dạng t−ơng đ−ơng có thể thấp hơn 10-10. Điều này có nghĩa cần quan sát 1 trong CSDL 1010 không lớn hơn để đối sánh có ý nghĩa tại khoảng cách t−ơng tự là cảnh báo sai. Để tổng hợp, các khung của chúng ta để nhận dạng hình dạng, đặc tr−ng hình dạng đặt ra 3 yêu cầu sau: 1- Các đặc tr−ng hình dạng cung cấp mô tả hoàn thiện: 2 hình dạng với các đặc tr−ng t−ơng tự đ−ợc nhận dạng. 2- Các hình dạng độc lập thống kê (khá chính xác, khoảng cách giữa hai hình dạng là độc lập). 3- Số l−ợng các hình dạng lớn. Yêu cầu thứ nhất có nghĩa là mô tả đặc tr−ng hình dạng tốt. Yêu cầu thứ hai cơ sở cho thiết kế ph−ơng pháp nền và yêu cầu thứ ba cần thiết để tìm kiếm hình dạng với số cảnh báo sai thấp. Tìm các đặc tr−ng rất khó hội tụ cả ba yêu