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

ị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._.h 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 cầu. Thực vậy phải có đủ đặc tr−ng để yêu cầu thứ nhất có giá trị nh−ng yêu cầu thứ 2 có thể bị lỗi. Khung quyết định, phải mô tả khá xa so với thực tế nói chung. Phải ứng dụng để tìm ra sự t−ơng đồng giữa bất kỳ loại cấu trúc nào trong cảnh, với k đặc tr−ng độc lập thống kê có thể đ−ợc trích chọn trong phần tiếp theo, đề cập vấn đề - 68 - trích chọn đặc tr−ng độc lập từ đoạn cung Jordan (nhân tố hình dạng). Nhân tố hình dạng đ−ợc chuẩn hóa tr−ớc khi đối sánh để yêu cầu nhận dạng hình học cố định. Vì vậy nhân tố hình dạng phải đ−ợc chuẩn hóa và trích chọn đặc tr−ng độc lập thống kê từ các nhân tố hình dạng đã đ−ợc chuẩn hoá nhằm đáp ứng ba yêu cầu này. 3.4.Chuẩn hóa nhân tố hình dạng từ ảnh cho đặc tr−ng độc lập 3.4.1. Biểu diễn hình dạng bằng các mức đ−ờng Các thử nghiệm ph−ơng pháp ra quyết định đ−ợc sử dụng trong hệ thống nhận dạng thực nh− thế nào. Một thuật toán trích chọn đoạn cung Jordan t−ơng ứng với biểu diễn hình dạng cục bộ không đổi trong ảnh đ−ợc giới thiệu tiến hành theo các b−ớc sau: 1- Trích chọn mức đ−ờng có ý nghĩa 2- Làm mịn các mối quan hệ không đổi của mức đ−ờng đ−ợc trích chọn 3- Mã hóa cục bộ đoạn mức đ−ờng sau khi chuẩn hóa các mối quan hệ t−ơng đồng. Chi tiết hơn, đề cập tới tập các mức đ−ờng trong ảnh (đ−ờng viền của các thành phần). Sự biểu diễn này có một số tiến bộ, mặc dù nó không cố định ở một vài sự thay đổi độ chói của cảnh ( Trong tr−ờng hợp này các ảnh tự nó thay đổi). Chú ý,mức đ−ờng không đổi khi thay đổi độ t−ơng phản. Đảm bảo việc học chính xác các thông tin hình dạng yêu cầu đ−ợc biểu diễn ở mức đ−ờng. Tuy nhiên, đ−ờng viền đối t−ợng nằm trong ảnh đ−ợc biểu diễn bởi tổ hợp một số đoạn các mức đ−ờng. Vì vậy, các mức đ−ờng có thể đ−ợc quan sát nh− một dãy các đoạn đ−ờng viền đối t−ợng, vì vậy phải mã hóa mọi thông tin hình dạng. Tuy nhiên, biểu diễn hình dạng bằng mức đ−ờng là không cần thiết và cũng có thể chứa thông tin vô ích. Đó là tại sao, Desolneux giới thiệu ph−ơng pháp để trích chọn mức đ−ờng có ý nghĩa từ ảnh, điều này đ−ợc hoàn thiện bởi Cao. - 69 - Qua thực nghiệm, những đ−ờng này cung cấp để trùng khớp cục bộ với đ−ờng viền trực quan của đối t−ợng trong ảnh. Thuật toán không cần sự điều chỉnh tham số, từ các tham số tự động thiết lập dựa trên số liệu thống kê thu đ−ợc từ nguyên tắc trực quan. Mức đ−ờng có ý nghĩa là độ t−ơng phản không đổi, từ các phát hiện của chúng dựa trên phân bố sự t−ơng phản của ảnh. Hình 3.1 minh họa việc mất thông tin, có nghĩa là bằng việc sử dụng mức đ−ờng có ý nghĩa đ−ợc so sánh với tăng độ chính xác của thông tin. Sự giảm bớt các mức đ−ờng nhằm mục đích đối sánh hình dạng sau mã hóa. Mặt khác, ngăn chặn yếu tố ph−ơng pháp không đ−ợc ứng dụng của, Ví dụ nh− tìm kiếm ảnh từ CSDL. Từ một mức đ−ờng có ý nghĩa đ−ợc trích chọn, cần làm nhẵn chúng để hạn chế nhiễu và ảnh h−ởng của nhiễu. Không gian độ chia quan hệ hình học (Geometric Affine) phải thích hợp (từ mỗi sự làm nhẵn thay thế với biến đổi quan hệ riêng và từ đó quan tâm tới quan hệ không đổi: ở đây x là điểm trên mức đ−ờng, Curv(x) là độ cong và n (x) th−ờng là độ cong, h−ớng về phía lõm, sử dụng thực hiện nhanh bởi Moisan. Độ chia tại điểm làm nhẵn đ−ợc ứng dụng để cố định kích th−ớc pixel. Fix cứng độ chia tại điểm làm nhẵn để mở rộng chi tiết của hình dạng ảnh ở điểm trên cung đ−ợc trích chọn. Mục đích là giảm bớt sự phức tạp của các mức đ−ờng có ý nghĩa hoàn thiện bằng cách chuẩn hoá chúng. Mục tiêu còn lại cũng nhằm mục đích tạo các đối sánh hình dạng chắc chắn. Thực vậy, làm mịn là hạn chế số đ−ờng mảnh bitangents (màu sẫm) trên mức đ−ờng để hạn chế các nhiễu; kết quả tất nhiên nó cũng hạn chế số nhân tố hình dạng đ−ợc mã hóa và nh− vậy mức đ−ờng sẽ trở lên rõ ràng hơn. Cuối cùng, thuật toán mã hóa hình dạng không đổi thực hiện chuẩn hóa cục bộ và mã hóa. Để xây dựng biểu diễn không đổi ( biến đổi quan hệ hoặc - 70 - t−ơng đồng), định nghĩa khung cục bộ cho mỗi mức đ−ờng, dựa trên h−ớng mạnh lên (robust, chú ý đ−ờng sẫm tại đoạn béo, hoặc đ−ờng mảnh). Mỗi biểu diễn thu đ−ợc bằng lấy mẫu đồng dạng một đoạn đ−ờng cong trong khung tiêu chuẩn hóa này. Sự liên kết của ba sự xắp xếp này đ−ợc giới thiệu đầu tiên bởi Lisani. Cách thứ ba dụa trên bài báo của Lamdan cho phép công việc của Reths trên đánh chỉ mục không đổi và gần đây hơn là Orrite. Phần sau giới thiệu thuật toán cải tiến của Lisani. Hình 3.1: trích chọn mức đ−ờng có ý nghĩa a-ảnh gốc “ La Conpouaille “. b-Mức đ−ợc giới thiệu biểu diễn với chất l−ợng mức xám cao từng b−ớc t−ơng ứng 10 (54 790 mức đ−ờng). Mức đ−ờng có ý nghĩa M’ (296 detetion). 3.4.2.Tiêu chuẩn hóa và mã hóa bán cục bộ Giới thiệu tiêu chuẩn hóa mức đ−ờng bán cục bộ, tổng quan hơnchính là cung Jordan dựa trên h−ớng cực đại. Việc tách này đ−ợc cung cấp bằng đ−ờng mảnh hoặc đ−ờng đậm tại đoạn nhẵn. (Một đoạn là vế trái của cung không tiến tới phân đoạn điểm điểm, mối quan hệ với ph−ơng pháp nền. Trong khi đ−ờng mảnh là một khả năng quan hệ không đổi; nó không phải là đoạn bằng phẳng. Tuy nhiên, hai đối số cho sự đề cập của nó; đầu tiên, d−ới lý do nhân tố zoom, đoạn bằng phẳng đ−ợc duy trì, lý do thứ hai là điểm cong, tất yếu cũng đ−ợc duy trì bởi biến đổi quan hệ. Nếu không phải tr−ờng hợp này, tại điểm cong sẽ không - 71 - phải là h−ớng mạnh. Trong cảnh, điểm đậm tại đoạn bằng phẳng có thể đ−ợc đề cập nh− version mạnh của độ đậm tại điểm cong (sử dụng thuật toán gốc của Lisani ) cùng với đ−ờng mảnh và version không mạnh của phần bằng phẳng. Chi tiết thủ tục sử dụng để thực hiện t−ơng tự và mối quan hệ không đổi cho mã hóa / tiêu chuẩn hóa cục bộ đ−ờng cong Jordan. Tiếp theo, đề cập trực tiếp tham số Euclidean cho mức đ−ờng. 3.4.2.1. Mã hóa / Tiêu chuẩn hóa trị không đổi t−ơng đ−ơng Chi tiết ở hình 3.2, hai tham số thực hiện, F và N bao gồm trong thủ tục tiêu chuẩn hóa này. Giá trị của F xác định chiều dài chuẩn hóa của nhân tố hình dạng, và nó đ−ợc lựa chọn: nếu F quá lớn, nhân tố hình dạng sẽ không đ−ợc chấp nhận tốt với thực tế, trong khi nếu F quá nhỏ nhân tố hình dạng không đủ để phân biệt. Mặt khác, một vấn đề cơ bản trong phân tích hình dạng: tính cục bộ trái ng−ợc với tính chung trong biểu diễn hình dạng. Từ t−ơng quan biểu diễn hình dạng thì việc lựa chọn N ít khó khăn hơn, vì vậy các tham số t−ơng đối chính xác. Giá trị của nó đ−ợc lựa chọn nh− một sự thỏa thuận giữa biểu diễn hình dạng chính xác với việc đảm bảo tính toán nhanh. Hình 3.3 : Chỉ ra một vài tiêu chuẩn hình dạng đ−ợc trích chọn từ đ−ờng đơn. Nhiệm vụ tính toán với F=5 và N=45. Chú ý : Biểu diễn có d− thừa. Trong khi biểu diễn chắc chắn không phải là tối −u vì có d− thừa, nó gia tăng xác suất tìm nhân tố hình dạng chung khi hình dạng t−ơng ứng đ−ợc giới thiệu trong ảnh, thậm chí chúng bị suy giảm hoặc tùy thuộc vào một phần sự nghẽn. Tất cả các thử nghiệm đ−ợc giới thiệu ở mục 5 đề cập tới đối sánh dựa trên mã hóa cục bộ sử dụng F=5, N=45, theo đó các kết quả thỏa mãn tốt nhất. Tiến hành tại một các tham số tổng quan này đ−ợc cố định cho tất cả các thử nghiệm và không cần xác định lại bởi ng−ời dùng. - 72 - Để giới thiệu một mức đ−ờng L1; mỗi đoạn bằng phẳng và mỗi cặp điểm trên đ−ờng thẳng t−ơng tự và đậm với cung tròn. Hình 3.2 : Mã hóa bán cục bộ sự không đổi t−ơng tự. Phía trái : một minh họa dựa trên đ−ờng mảnh. a) đặt P1 và P2 cả các điểm đậm khi thực sự với mảnh hoặc điểm cuối cùng cho segment đ−ợc tách khi thực sự với đoạn bằng phẳng. Để cặp đoạn đậm D với những điểm này. b) Bắt đầu chậm tiến từ P … P1 với Dgọi P1 là đoạn đậm của L hoặc Thogonoil tới D. Bắt đầu từ P2 gọi P2 đoạn đậm tiếp theo của L hoặc Thogonal tới D. c) Tìm điểm giao điểm giữa P1 và D và giữa P2 và D. Gọi là R1 , R2. d) Chuẩn hóa tọa độ của phân bố điểm N trên ảnh của chuẩn hóa chiều dài F; trung tâm tại C. Giao diện điểm của L với đ−ờng phân giác (R1,R2) bằng tọa độ chuẩn hóa có nghĩa là tọa độ trong khoảng t−ơng đ−ơng định nghĩa bởi điểm R1, R2 trên bản đồ chạy từ (- 2 1 ,0),( 2 1 ,0) t−ơng ứng. Là mã hóa F=5. Khi chiều dài của chúng quá nhỏ với thừa nhận chiều dài của đ−ờng phân đoạn (R1,R2), kết quả nhân tố hình dạng tự nó gối lên nhau(có sự chồng lấn giữa các kết quả thu đ−ợc). Hình 3.3 : mã hóa sự không đổi t−ơng đ−ơng bán cục bộ. Đ−ờng phải : tổng quan 19 nhân tố (F=5, N=45) 12 trong số chúng dựa trên đ−ờng mảnh, còn - 73 - lại là đ−ờng đậm. Biểu diễn khá thừa. ở đây chỉ biểu diễn ba nhân tố hình dạng chuẩn hóa, hai nhân tố hình dạng thu đ−ợc từ đ−ờng mảnh một nhân tố hình dạng từ đ−ờng đậm. Hình 3.3: Mã hoá sự không đổi t−ơng đ−ơng bán cục bộ 3.4.2.2. Mã hóa / Chuẩn hóa quan hệ bất biến Minh họa trong hình 3.4. Nh− đã thực hiện ở việc chuẩn hóa sự t−ơng đồng không đổi, tham số thi hành đ−ợc sửa từ F=5 N=45. Hình 3.5 chỉ ra một vài hình dạng đ−ợc trích chọn từ đ−ờng đơn giản cho các tham số lựa chọn này. Mã hóa thực tế giảm d− thừa so với thủ tục mã hóa t−ơng đồng. Bởi vì thực tế cấu trúc của khung cục bộ quan hệ không đổi lạm dụng nhiều sự miễn c−ỡng trên khung hơn là khung t−ơng đồng không đổi. 3.4.3. Từ chuẩn hóa nhân tố hình dạng đến đặc tr−ng độc lập. Giải thích thủ tục ứng dụng để trích chọn vài đặc tr−ng từ các nhân tố hình dạng. Theo kinh nghiệm thu đ−ợc đồng thời ba yêu cầu đặc tr−ng (minh họa ở hình 3.6). Mỗi đoạn cung Jordan C đ−ợc chia thành 5 đoạn con chiều dài bằng nhau. Mỗi đoạn đ−ợc chuẩn hóa bằng bản đồ dây cung giữa điểm đầu và điểm cuối trên trục ngang. Điểm đầu là điểm gốc : kết quả “ Đoạn cung nhỏ đ−ợc chuẩn hóa “ là 5 đặc tr−ng C1, C2, …, C5 ( mỗi các t−ơng ứng Ci có 9 điểm riêng biệt. Các đặc tr−ng này là độc lập; tuy nhiên C1 … C5 đem lại : nó có thể tái thiết lại hình dạng gốc của chúng : mục đích của sự trọn vẹn đặc tr−ng tổng quan thứ 6. C6 đ−ợc tạo ra từ điểm cuối của 5 đoạn trên, trong khung chuẩn hóa. Cho - 74 - mỗi đoạn của mức đ−ờng. Đặc tr−ng hình dạng đã giới thiệu tạo ra từ ba đặc tr−ng này C1 … C6. Để thu đ−ợc một biểu diễn quan hệ không đổi của các mức đ−ờng L, mỗi đoạn bằng, mỗi cặp điểm trên cùng đ−ờng thẳng là đậm đối với cung thực hiện. Hình 3.4 : Mã hóa bán cục bộ mối quan hệ không đổi. Nhân tố hình dạng đ−ợc mã hóa dựa trên đ−ờng mảnh D. a) Đặt P1, P2 là điểm đậm khi thực tế với mảnh hoặc điểm kết thúc cho tách đoạn khi thực tế với đoạn bằng. Đề cập đ−ờng đậm D với các điểm này. b) Bắt đầu từ P2 trừ đoạn đậm tiếp theo với L, đó là song song với D. Gọi là D’. c) Để cặp đ−ờng thẳng song song D và đặt tại 3 1 và 3 2 , của khoảng cách từ D tới D’. Gọi là D1 và D2 t−ơng ứng. d) Bắt đầu từ P2 tìm điểm giao nhau tiếp theo giữa L và D1, L và D2. Xem xét đoạn thẳng T1 định nghĩa bởi hai điểm này. e) Bắt đầu ng−ợc lại từ P1, tìm điểm đậm tr−ớc đó song song L và T1 gọi là T2. f) Định nghĩa điểm R1, R2 và R3 là điểm cắt giữa D và T2, D và T1, D’ và T2 t−ơng ứng. Hình 3.4: - 75 - g) Điểm R1, R2, R3 định nghĩa nh− một quan hệ cơ bản. Chuẩn hóa quan hệ đ−ợc sửa t−ơng ứng bằng bản đồ {R1, R2, R3} và {(0,0), (1,0), (0,1)} nếu {R1, R2, R3} là một khung trực tiếp và {(0,0), (1,0), (0,-1)} nếu không phải. h) Mã hóa : xem xét điểm giao nhau giữa L và đ−ờng thẳng cách đều từ D và D’ ( điểm đầu bắt đầu P2). Gọi nó là chuẩn hóa C của L chiều dài 2 F tại cả hai ảnh của C. L−u trữ phân bố điểm N trên dạng chuẩn hóa đ−ờng cong. Hình 3.5 : mã hóa hình dạng bán cục bộ quan hệ bất biến. Đ−ờng trên phía phải phát sinh từ 7 nhân tố hình dạng (F=5, N=45); 3 trong số chúng đ−ợc biểu diễn ở đây.Tr−ớc có xi(S) = Ci ( i ∈ (1, …, 6) mỗi i ∈ {1, …, 5}, Ei = (R 2)9. E6= (R 2)6 và khoảng cách di giữa chúng là L ∞ Trong hình 3.6, mã hóa sự t−ơng đồng không đổi. Phác họa a) Hình dạng gốc nh− cung Jordan trong khoảng đ−ợc chuẩn hóa dựa trên đ−ờng mảnh. Cả giới hạn của cung Jordan đ−ợc đề cập đ−ợc rõ ràng với đ−ờng đậm : biểu diễn này đ−ợc chia thành 5 đoạn C1, C2, C3, C4, C5. - 76 - Phác họa b) Mỗi một hình đ−ợc chuẩn hóa và đặc tr−ng số 6 tạo ra điểm cuối của những đoạn này đ−ợc xây dựng. Hình 3.6: mã hoá sự t−ơng đồng không đổi Khả năng khác, điều tra việc sử dụng phân tích thành phần cơ bản PCA [28]. Mặc dù PCA không cung cấp đặc tr−ng độc lập nh−ng nó cũng không phải là chính xác nhất. Khi này, tính toán số cảnh báo sai xuất hiện vẫn có giá trị. Tuy nhiên, kết quả không tốt nh−ng chúng vẫn có PCA thực tế cho phép từ một giới hạn vốn có: nó là thừa nhận bền vững không gian đặc tr−ng tuyến tính. Điều này rõ ràng không đúng với không gian hình dạng. 3.5. Thảo luận Trong phần này đề cập tới nhân tố hình dạng nh− một đoạn của mức đ−ờng đủ độ t−ơng phản. Định nghĩa này theo một phân tích yêu cầu nhận dạng hình dạng. Thay đổi độ t−ơng phản ít và sự tập trung trong tính toán( vùng, thay đổi mức chói ở đâu) là thiết thực. Mục đích để giới thiệu ph−ơng pháp để tính toán NFA của đối sánh của một vài nhân tố hình dạng tiến tới phân lớp không đổi. Tính toán số l−ợng này rất hữu ích bởi nó tiến tới tới chấp nhận hay phủ định ng−ỡng cho đối sánh nhân tố hình dạng. Luật ra quyết định để dựa trên sự cân nhắc các đối sánh với NFA < 1(hoặc 10-1 nếu đ−ợc đề cập tới việc tách chính - 77 - xác), việc tự động mức ng−ỡng khoảng cách phụ thuộc vào CSDL và phụ thuộc vào truy vấn. Dĩ nhiên, với đoạn mức đ−ờng không đủ để quyết định có hay không 1 đối t−ợng trích ra từ ảnh. Tuy nhiên, biên đối t−ợng trùng khớp tốt nhất với các đoạn mức đ−ờng, vì thế có thể đánh giá để tính toán. B−ớc tiếp theo là kết hợp các đối sánh bằng cách tính toán kết cấu không gian của chúng. Thật vậy, có thể thấy trong các thử nghiệm đ−ợc giới thiệu, đối sánh sai(đối sánh không t−ơng ứng với các đối t−ợng giống nhau) không đ−ợc phân bố rõ ràng trên một ảnh, ng−ợc lại hoàn toàn với nh− đối sánh chính xác. Mỗi cặp đối sánh nhân tố hình dạng tiến tới 1 biến đổi xác định giữa các ảnh, t−ơng ứng nh− một đối t−ợng trong biến đổi không gian. Từ đó các đối sánh có ý nghĩa không gian chặt chẽ phải t−ơng ứng nh− cluster trong không gian biến đổi, việc tách các đối sánh có ý nghĩa có thể tính toán nh− việc thực hiện cluster. Hoàn thành nhiệm vụ này chính là phát triển thuật toán cluster không giám sát mà vẫn dựa trên ph−ơng pháp cotrario. Đồng thời, kết hợp thông tin không gian có sẵn bằng đối sánh nhân tố hình dạng sẽ củng cố cho nhận dạng nhân tố hình dạng của ph−ơng pháp ra quyết định Contrario. - 78 - Ch−ơng 4 Thử nghiệm 4.1. Thử nghiệm ph−ơng pháp nền Tính toán xác suất PFA(S, δ) của một nhân tố hình dạng bằng cách thay đổi tại một khoảng cách thấp hơn δ để một truy vấn hình dạng S là đúng với giả thuyết (A) độc lập dựa trên khoảng cách giữa các thuộc tính. Dĩ nhiên dựa vào độ chính xác có thể mang tới giá trị NFA(S, δ) đủ lớn phụ thuộc giá trị của giả thuyết độc lập (A). Số các cảnh báo sai mong muốn trong số tất cả các đối sánh có ý nghĩa ε với truy vấn hình dạng ở mức thấp hơn của ε. Tuy nhiên không thể cảnh báo riêng và đối sánh thực tế : chúng chỉ tách khi quan sát. Hiện tại, nguyên tắc Helinholtz nói rõ không thực hiện tách các đối t−ợng lẫn “nhiễu”. Mọi đối sánh ý nghĩa ε mà có nhiễu sẽ coi nh− cảnh báo sai. Trong mỗi tr−ờng hợp, sau khi kiểm tra yêu cầu trị trung bình ε của nhiễu, chỉ ra rằng tr−ờng hợp này NFA là dự báo khá tốt số hình dạng đ−ợc tách. Giả thuyết độc lập đủ giá trị, vì vậy yêu cầu phụ thuộc trị trung bình cảnh báo sai ε trong số ε đối sánh có ý nghĩa còn lại. Thử nghiệm đầu tiên, kiểm tra ng−ỡng tách trên mọi ph−ơng thức đơn giản. Xem xét CSDL và truy vấn một vài không gian với việc gia tăng số l−ợng đặc tr−ng độc lập (thay thế cho hình dạng đã chuẩn hóa). Mặc dù trong tr−ờng hợp này, nhân tố hình dạng không lấy từ đ−ờng cong Jordan, ph−ơng thức nền là có khả năng thực hiện. Trong cảnh, các nhân tố hình dạng đ−ợc đề cập hoàn toàn thích hợp giả thuyết đặc tr−ng độc lập. Bảng 4.1 chỉ ra số các cảnh báo sai dự báo chính xác cho CSDL có kích th−ớc khác nhau : số tách với NFA thấp hơn ε là khoảng cách thực tế ε . - 79 - Bảng 4.1 : Trung bình lớn hơn 10 mẫu. Số tách có ý nghĩa ε = 1 mâu thuẫn ε. Hàng đầu tiên : CSDL có 100 hình dạng, thứ 2 có 50 hình dạng, thứ 3 có 10 hình dạng. Dĩ nhiên, ph−ơng pháp này không thực tế với nhân tố hình dạng xuất hiện ngẫu nhiên. Nói cách khác, nhân tố hình dạng t−ơng ứng với đoạn cung Jordan và bởi vậy nó bị phân chia c−ỡng bức. Đặc tr−ng nhân tố hình dạng thu đ−ợc từ thủ tục chuẩn hóa, giới thiệu một vài cấu trúc t−ơng đ−ơng (ví dụ : nhân tố hình dạng kết hợp từ các điểm mảnh với cấu trúc chung) để số l−ợng “ trọng số sự phụ thuộc ” giảm bớt bởi vì những cái này có hai mặt. ảnh nhiễu, bảng 2 chỉ ra số tách không là dự đoán chính xác nh− trong kinh nghiệm dự đoán, cuối cùng mỗi giá trị ε nhỏ. Tuy nhiên, để biên độ là đúng, không phụ thuộc vào kích th−ớc của CSDL cần phải thiết lập ng−ỡng số cảnh báo sai trên nguyên tắc Helrholtz. Ph−ơng pháp d−ới đây, một đối sánh là đ−ợc coi nh− một quan hệ mật thiết nếu nó không xuất hiện trong ảnh có nhiễu. Phụ thuộc bảng 2, đối sánh với mức thấp hơn 0,1 để chắc chắn không có nhiễu trắng. Bảng 2 đối sánh với NFA < 0,1 đ−ợc chắc chắn để khá giống với trong nhiễu trắng. Nếu muốn chắc chắn sự tin cậy cao trong đối sánh để tách, chúng ta tiến tới đối sánh có ý nghĩa 0,1 theo kinh nghiệm thực tế. Bảng 4.2 : Đoạn chuẩn hóa của đ−ờng mức có nhiễu trắng. - 80 - 4.2. Thử nghiệm Contrario 4.2.1. Hai ảnh không quan hệ với nhau Mục tiêu của thử nghiệm này là để kiểm tra phạm vi chính của ph−ơng pháp đề xuất: số các cảnh báo sai NFA là một −ớc l−ợng số các đối sánh thay đổi. Hình 4.1 có thể thấy 2 kết quả biểu diễn đ−ợc mô tả nh− thế nào khi đề cập tới các ảnh khác. Nhân tố hình dạng đ−ợc chuẩn hoá sự t−ơng đồng bất biến của mức đ−ờng có ý nghĩa từ những cái đ−ợc tìm kiếm đầu tiên trong số các nhân tố hình dạng đ−ợc chuản hoá từ bức ảnh thứ 2. Chỉ những đối sánh có ý nghĩa 1 đ−ợc khôi phục(NFA của đối sánh này <1) nh− ở Pro 3. 1 là mong đợi nhất của một đối sánh có ý nghĩa. Mặc dù ph−ơng pháp không làm xáo trộn giữa đối sánh tốt và đối sánh sai, NFA mang lại 1 −ớc l−ợng tốt” đối sánh tốt nh− thế nào” Trong hình 4.1, hai ảnh không liên quan. ảnh gốc (bên trái), mức đ−ờng có ý nghĩa (ở giữa), 846 hình dạng đ−ợc chuẩn hoá ở trên đ−ợc tìm kiếm trong số 281 hình dạng đ−ợc chuẩn hoá từ bức ảnh thứ 2. Chỉ đối sánh có ý nghĩa 1 đ−ợc tách (bên phải) NFA bằng 0.2. Đối sánh này t−ơng ứng đoạn mức đ−ờng khá thô đ−ợc lấy ngẫu nhiên. Hình 4.1: ảnh và mức đ−ờng có ý nghĩa - 81 - 4.2.2. Méo dạng quan sát xa gần Không ngẫu nhiên khi thực hiện ph−ơng pháp quan hệ tốt hơn ph−ơng pháp t−ơng đồng. Khi phân chia với ảnh liên hệ dù chỉ có 1 thay đổi mối quan hệ. Trong thử nghiệm thứ hai, chỉ ra ph−ơng pháp quan hệ thực hiện tốt hơn(với chú ý NFA thấp nhất có thể tìm kiếm). So với ph−ơng pháp t−ơng đồng, khi ứng dụng vào ảnh thực liên quan vừa phải tới biến đổi xa gần ít. Hai ảnh đ−ợc đề cập trong thử nghiệm này(thử nghiệm Hitchcock) là hai ảnh chụp của cùng một cảnh. Chỉ ra ở hình 4.2 với đ−ờng mức t−ơng ứng của chúng. Đối với ph−ơng pháp quan hệ bán cục bộ không đổi, 1150 và 853 nhân tố hình dạng đ−ợc trích chọn từ ảnh mục tiêu và từ CSDL t−ơng ứng. Số các đối sánh ý nghĩa 1 đ−ợc tách là 16. 16 nhân tố hình dạng đ−ợc đối sánh này đ−ợc chỉ ra trên ảnh, trong hình 4.3. Không đối sánh sai nào bị tách, và mọi đối sánh NFA của chúng <0.1. Đối sánh tốt nhất chỉ ra trong hình 4.2, NFA nghiên cứu bằng 6,5. 10-11. Giá trị này rõ ràng rất thấp, đề cập tới ý t−ởng đối sánh hoàn hảo trong thử nghiệm với số cảnh báo sai: 26 105.2853 8531150 −ì=ì Khi phân bố theo kinh nghiệm của khoảng cách ảnh đích đ−ợc học sử dụng duy nhất CSDL ảnh đã đề cập. Hình 4.2: chỉ ra đối sánh có ý nghĩa đ−ợc tách sử dụng ph−ơng pháp nhận dạng bán cục bộ bất biến. Trong tr−ờng hợp này 2.33 và 1463 nhân tố hình dạng đ−ợc trích chọn từ annhr và CSDL t−ơng ứng. ph−ơng pháp t−ơng đồng dẫn tới trích chọn nhiều nhân tố hình dạng hơn ph−ơbng pháp quan hệ, đó là lý do tại sao nhiều đối sánh có ý nghĩa 1 đ−ợc tách, trong tr−ờng hợp này đối sánh có ý nghĩa cho ph−ơng pháp t−ơng đồng đ−ợc chỉ ra ở hình 4.5. Mức NFA thấp nhất tìm they với ph−ơng pháp t−ơgn đồng là 3.8*10-8 và t−ơgn ứng các nhân tố hình dạng đ−ợc tách biểu diễn ở hình 4.3. Trong hình 11b,c t−ơgn ứng đối sánh nhân tố hình dạng tại ε<0.1 và cho NFA là: 0.1<NFA<1. Chú ý : không có danh sách có - 82 - ý nghĩa 10-1 nào là đối sánh sai và các nhân tố hình dạng theo tổng quan cục bộ hơn so với đối sánh hình 4.5c. Các nhân tố hình dạng tổng quan kém chính xác t−ơng đ−ơng nh− biến đổi phép chiếu. Trong hình 4.2, thử nghiệm hitchcook: ảnh gốc (t−ơng ứng 2 ảnh chụp cùng 1 cảnh và mức đ−ờng t−ơng ứng của chúng đ−ợc mã hoá. ảnh phía trên là ảnh đích. Trong ảnh đích 307 mức đ−ờng có ý nghĩa đ−ợc tách và 266 mức đ−ờng có ý nghĩa đ−ợc tách trong CSDL ảnh.). NFA thấp nhất tìm kiếm với ph−ơng pháp t−ơng đồng (3,8*10-8) lớn hơn so với mức NFA thấp nhất ở ph−ơng pháp quan hệ (6,5*10-11). NFA khá thấp trong ph−ơng pháp quan hệ so với ph−ơng pháp t−ơng đồng, t−ơng ứng nh− phép biến đổi phép chiếu áp dụng ở đây xấp xỉ cục bộ bằng biến đổi quan hệ tốt hơn biến đổi t−ơng đồng. Hai đối sánh sai, NFA >0.1 thấy ở hình 4.5c. Hình 4. chỉ ra nhân tố hình dạng của các đối sánh sai này, khi thêm vào nhân tố hình dạng đ−ợc chuẩn hoá biểu diễn ở khung đ−ợc chuẩn hoá. Chú ý ng−ỡng khoảng cách t−ơng ứng với mỗi NFA là đủ lớn vì vậy không có đối sánh tốt nào bị lỗi. Mặc dù ph−ơng pháp đ−ợc giới thiệu không xác định xác suất này rất thấp. Hình 4.2: thử nghiệm hitchcook - 83 - Trong hình 4.3 có 16 đối sánh có ý nghĩa giữa các nhân tố hình dạng theo ph−ơng pháp nhận dạng bán cục bộ quan hệ không đổi. Không đối sánh sai nào đ−ợc tách (trong ảnh mọi đối sánh có ý nghĩa t−ơng ứng đoạn giống nhau của đối t−ợng) mọi phép tách chỉ ra NFA <0.1. NFA thấp nhất NFA =6,5 10-11 Hình 4.3: Ph−ơng pháp nhận dạng bán cục bộ quan hệ không đổi Hình 4.4: ph−ơng pháp nhận dạng quan hệ bán cục bộ không đổi Trong hình 4.4, đối sánh chỉ ra mức NFA thấp nhất 6.5 10-11 4.2.3. Quan hệ với sự nghẽn cục bộ và thay đổi độ t−ơng phản Thử nghiệm sau cốt yếu so sánh mã hoá trích chọn từ hai điểm quan ssát của bức hoạ Monalisa( hình 4.5). Mã đ−ợc trích chọn từ truy vấn (11332 mã) đ−ợc tìm thấy trong số các mã đ−ợc trích chọn từ CSDL ảnh (11833 mã). Nhân tố hình dạng đ−ợc chuẩn hoá chú ý biến đổi t−ơng đ−ơng. Chú ý ảnh gốc là ảnh chụp từ bảo tàng. - 84 - Hình 4.5 ph−ơng pháp nhận dạng bán cục bộ : sự t−ơng đồng không đổi: các đối sánh sai(2) có thể thấy ở hình c NFA > 0.1 a: 26 đối sánh NFA< 1, b: 12 đối sánh NFA< 0.1, c:14đốisánhNFA∈(0.1ữ1) Ph−ơng pháp nhận dạng cục bộ sự t−ơng đồng không đổi: đối sánh chỉ ra mức NFA thấp nhất (3.8 10-8). Trong hình 4.6 chỉ ra bên trái: tập các đoạn đ−ờng mức trong ảnh gốc đ−ợc đối sánh 1 đoạn mức đ−ờng trong CSDL ảnh t−ơng ứng. NFA <1 và phía phải là tập các nhân tố hình dạng từ CSDL ảnh t−ơng ứng tại ảnh cuối cùng trong truy vấn ảnh. Thuật toán nhận ra 55 đối sánh có ý nghĩa. Chỉ 5 đối sánh sai có thể thấy trong số chúng. Có NFA∈(1, 10-1) sự thật, 36 đối sánh chỉ ra 1 NFA <10-1 Hình 11 Hình 4.5 nhận dạng bán cục bộ - 85 - Hình 4.6: Tập các đoạn đ−ờng mức đối sánh với ảnh trong CSDL Trong hình 4.7, 2 đối sánh sai NFA>0,1 ph−ơng pháp bán cục bộ t−ơng đồng không đổi. Mỗi NFA từ đ−ờng cong chỉ ra sự biến đổi cục bộ. Nh−ng hình dạng chung gióng nhau, nh− ảnh gốc thể có thể dựa vào nhân tố hình dạng đ−ợc chuẩn hoá. Hình 4.7: ph−ơng pháp bán cục bộ t−ơng đồng không đổi a- Đối sánh sai NFA= 0,64; b- Đối sánh sai N=0.68 Trong hình 4.8, ảnh gốc bên trái và mức đ−ờng có ý nghĩa bên phải. ảnh trên ảnh d−ới :truy vấn ảnh và mức đ−ờng của nó.Mã hoá từ truy vấn hình dạng đ−ợc tìm kiếm trong số mã từ CSDL ảnh. Chuẩn hoá ở đay phải chú ý đến biến đổi t−ơng đ−ơng. - 86 - Hình 4.8: ảnh gốc và mức đ−ờng có ý nghĩa Trong hình 4.9, ảnh Menima 55 đối sánh có ý nghĩa, một nửa trong số chúng có NFA < 10-3, đối sánh tốt nhất có NFA=4*10-4. để mỗi đoạn đậm của mức bên phải t−ơng ứng đoạn đậm phía trái . Hình 4.9: ảnh Menima và mức đ−ờng có ý nghĩa Trích trọn đặc tr−ng độc lập đ−ợc giới thiệu khá thực tế và cung cấp khá nhiều kết quả kinh nghiệm. ( Trong sense có nghĩa là đối sánh t−ơng ứng với nhân tố hình dạng thành đối t−ơng t−ơng ứng). - 87 - 4.3. Thảo luận Phần này đ−a ra một vài thử nghiệm minh hoạ cho ph−ơng pháp Contraio để chuẩn hoá mức đ−ờng. Mặc dù ảnh và đoạn mức đ−ờng thêm vào ảnh đ−ợc chỉ ra, ng−ời đọc có thể giữ luật ra quyết định thực tế với nhân tố hình dạng đã đ−ợc chuẩn hóa. Tuy nhiên kết quả t−ơng ứng với đoạn mức đ−ờng (không chuẩn hóa hình dạng trong một vài cảnh) đ−ợc chỉ ra ở đây rõ ràng. Gọi đối sánh sai trong là đối sánh thực sự nó có t−ơng ứng với đối t−ợng t−ơng tự nh− thế nào. Rồi đ−a đối sánh ngữ nghĩa chính xác. Tách các đối sánh không giống nh− xuất hiện bởi thay đổi hoặc chứng tỏ chính xác, đối sánh không chắc rằng đ−ợc phát sinh nhiễu hơn từ ph−ơng pháp nền ( sửa ứng với NFA ng−ỡng 1). Đối sách sai phát sinh từ NFA lớn hơn 10-1. Đơn giản đặt ng−ỡng NFA = 10-1. - 88 - Kết luận Sau thời gian nghiên cứu và tìm hiểu về ph−ơng pháp contrario cho nhận dạng nhân tố hình dạng tôi đã đạt đ−ợc một số kết quả sau: - Nắm đ−ợc ph−ơng pháp tách nhóm trong thủ tục với nhận dạng và tìm kiếm hình dạng. - Nắm đ−ợc ph−ơng pháp ra quyết định dựa vào việc đối sánh hình dạng truy vấn với hình dạng trong CSDL và số các cảnh báo sai NFA. - Tìm hiểu, phân tích đ−ợc phần thử nghiệm của ph−ơng pháp. Với mục đích nghiên cứu tìm hiểu để áp dụng ph−ơng pháp ra quyết định Contrario cho nhận dạng hình dạng tiến tới là nhận dạng đối t−ợng trong các ảnh phức tạp. Với những kết quả đã đạt đ−ợc trong thời gian nghiên cứu vừa qua, tôi nhận thấy mình có thể tiếp tục nghiên cứu để hoàn thiện ph−ơng pháp này hơn nữa. Hy vọng luận văn này sẽ giúp ích phần nào cho những ng−ời bắt đầu tìm hiểu về lĩnh vực mới này. Tôi xin chân thành cảm ơn: TS Nguyễn Kim Anh, ng−ời đã trực tiếp h−ớng dẫn và giúp đỡ tôi trong thời gian làm luận văn. Trung tâm Đào tạo và Bồi d−ỡng Sau Đại học - Tr−ờng Đại học Bách khoa Hà Nội; các thầy cô giáo trong Khoa Điện tử, tr−ờng ĐHCN Hà Nội, đã giúp đỡ tôi về mặt thời gian cũng nh− sự động viên rất lớn của bạn bè ng−ời thân về mặt tinh thần trong thời gian thực hiện đề tài. - 89 - Tài liệu tham khảo 1. F. Cao, J. Delon, A. Desolneux, P. Musé, F.Sur (2005), “A unified framework for detecting and application to shape recognition”, 2. Dengsheng Zhang,(2002), Image Retrieval Based on Shape, Monash University. 3. [ZHA01] D.S. Zhang and G.Lu. Segmentation of Moving Objects in Image Sequence: A revieww. Circuits, Systems and Signal Processing( Special Issue on multimedia) 4. Frédéric Cao, “An a contrario decision method for shape elemet recognition” 5. Anil K.Jain(2002), Fundamentals of Digital Image Processing, 6. G.Dudek, J.k.Tsotsos (1997). Shape Representation and Recognition from multiscale Curvature - 90 - Tóm tắt luận văn Đề tài: “Nghiên cứu ph−ơng pháp nhận dạng hình dạng” với mục đích nghiên cứu ph−ơng pháp Contrario cho nhận dạng nhân tố hình dạng từ các công đoạn cơ bản của quá trình nhận dạng nh− biểu diễn hình dạng, tách nhóm các nhân tố hình dạng thành hình dạng và đặc biệt là ra quyết định dựa vào NFA( số cảnh báo sai) Nội dung của đề tài bao gồm: - Nghiên cứu ph−ơng pháp biểu diễn hình dạng. - Nghiên cứu ph−ơng pháp thực hiện Cluster chính xác. - Nghiên cứu ph−ơng pháp ra quyết định Contrario cho nhận dạng nhân tố hình dạng. - Thử nghiệm ph−ơng pháp ra quyết định Contrario cho nhận dạng hình dạng Trong luận văn tác giả giới thiệu về ph−ơng pháp Contrario. Qua việc nghiên cứu này tác giả đãgiới thiệu ph−ơng pháp nhận dạng dựa trên số cảnh báo sai tiến bộ hơn so với một số ph−ơng pháp đã có mà thực hiện nhận dạng dựa trên đối sánh về khoảng cách. Nội dung của luận văn đ−ợc thể hiện qua 4 ch−ơng: Ch−ơng 1: Tổng quan về hệ thống điều khiển giám sát Ch−ơng 2: Tách nhóm Ch−ơng 3: Ph−ơng pháp ra quyết định Contrario Ch−ơng 4: Thử nghiệm • Từ khoá chính của luận văn: ” nhận dạng, tách nhóm, ra quyết định, nhân tố hình dạng” ._.