Luận văn Nghiên cứu phương pháp xây dựng hệ thống tìm kiếm ảnh theo nội dung sử dụng biểu đồ màu mờ

ỤC LỤ

LỜI CAM ĐOAN . 1

LỜI CẢM ƠN. 2

DANH MỤC HÌNH ẢNH TRONG LUẬN VĂN. 5

MỤC LỤC. 7

PHẦN MỞ ĐẦU. 10

CHưƠNG 1. TỔNG QUAN VỀ HỆ THỐNG TÌM KIẾM ẢNH THEO

NỘI DUNG 12

1.1. Hệ thống tra cứu ảnh theo nội dung và những thành phần chính

của nó. 15

1.2. Các đặc trưng trong hệ thống tìm kiếm ảnh dựa trên nội dung . 16

1.2.1. Đặc trưng màu sắc . 16

Các đặc trưng về hình dạng của ảnh. 18

1.2.2. Đặc trưng kết cấu. 20

1.2.3. Biểu đồ màu. 21

1.3. Khả năng ứng dụng của hệ thống tìm kiếm ảnh theo nội dung . 24

1.3.1. Công cụ tìm kiếm Google Image Search. 25

1.3.2. Hệ thống QBIC (Query By ImageContent). 26

1.3.3. Hệ thống WebSEEK và VisualSEEK. 26

1.4. Tổng quan về Logic mờ . 27

1.4.1. Giới thiệu chung về Logic mờ. 27

1.4.2. Khái niệm tập hợp mờ. 29

1.4.3. Các đặc trưng của tập mờ. 29

1.4.4. Các phép toán trên tập mờ. 30

1.5. Kết luận chương. 34

pdf85 trang | Chia sẻ: honganh20 | Ngày: 04/03/2022 | Lượt xem: 60 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu phương pháp xây dựng hệ thống tìm kiếm ảnh theo nội dung sử dụng biểu đồ màu mờ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
nhiều hệ thống tra cứu ảnh được phát triển ra đời, Các chương trình tra cứu ảnh dựa theo nội dung được xây dựng cẩn thận bằng cách sử dụng chi tiết số liệu thống kê, logic mờ, nhận dạng khuôn mẫu, máy tính ,tính toán mềm và xử lý các dữ liệu. Cùng với đó các chương trình nghiên cứu và ứng dụng thương mại đã được xây dựng một cách bài bản và quy mô. Sau đây học viên sẽ giới thiệu một số hệ thống của tra cứu ảnh phổ biến hiện nay mà hầu như mọi người đều biết. 1.3.1. Công cụ tìm kiếm Google Image Search Một công cụ tìm kiếm mà hầu hết mọi người khi sử dụng internet đều biết đến đó là Google, trong các chương trình tìm kiếm của google thì google ảnh là một trong những thành công to lớn của họ, nó giúp người dùng tra cứu ảnh theo nôi dung hay bằng chính những hình ản sẵn có và trả về kết quả khá chính xác. Google Image Search hỗ trợ một số thuộc tính cơ bản như kích thước, hình dạng, để người dùng tra cứu chuẩn xác hơn. ` 26 Hình 2.3 : Công cụ tìm kiếm ảnh của Google 1.3.2. Hệ thống QBIC (Query By ImageContent) IBM một tập đoàn công nghệ máy tính đa quốc gia có trụ sở tại Armonk, New York, Mỹ. đã phát triển và đưa ra một hệ thống có tên gọi là Query By Image Content ( QBIC ) đó một hệ thống tìm kiếm ảnh thương mại được nhiều người biết đến trong số các hệ thống tra cứu ảnh dựa trên nội dung đã từng phát triển. Nó cho phép truy vấn các CSDL hình ảnh lớn bằng các thuộc tính trực quan ví dụ như: tỉ lệ màu sắc, màu sắc hay hình dạng, kết cấu, và từ các bức vẽ phác hoạ,cũng như các từ khóa. Thông thường bất kỳ thuộc tính trực quan nào cũng có thể được sử dụng trong truy vấn. Nhưng khi các thuộc tính trực quan đó có thể kết hợp với từ khoá để tạo thành một truy vấn tổng hợp sẽ cải tiến hiệu quả truy vấn. Phần mềm QBIC và trình diễn có tại [3]. 1.3.3. Hệ thống WebSEEK và VisualSEEK WebSEEK là một trong những hệ thống nguyên mẫu truy vấn ` 27 trực quan dựa trên nội dung được phát triển bởi Đại học Columbia. Nó được thiết kế đặc biệt để tìm kiếm hình ảnh và video trên WWW. Trong Web SEEK, các hình ảnh được phân tích trong hai quy trình tự động riêng biệt. - Quy trình đầu tiên là trích chọn và lập chỉ mục các đặc trưng trực quan như biểu đồ màu và kết cấu. - Quy trình thứ hai là phân tích văn bản liên quan và phân loại hình ảnh thành các lớp chủ đề theo một phân loại hình ảnh tùy chỉnh. Có trên 2000 lớp hình ảnh trong hệ thống phân loại. Ví dụ như các lớp chủ đề về thể thao, du lịch, cây cối và các lớp con của chúng. Một mẫu thử nghiệm nâng cao được gọi là Visual SEEK cũng được phát triển. Visual SEEK tăng cường khả năng tìm kiếm bằng cách tích hợp các truy vấn không gian (như những người sử dụng trong GIS) và các truy vấn đặc trưng trực quan hình ảnh. Người dùng yêu cầu hệ thống tìm kiếm ảnh bao gồm các vùng có các đặc trưng phù hợp và mối quan hệ không gian. Web SEEK có thể được truy cập từ [4] . 1.4. Tổng quan về Logic mờ 1.4.1. Giới thiệu chung về Logic mờ Logic mờ (tiếng Anh: Fuzzy logic) được nhà toán học Lotfali Askar Zadeh phát triển lên từ lý thuyết tập mờ từ 1965 ông đã cho ra đời hàng loạt các lý thuyết về tập mờ và được đăng trên báo và các tạp chí lớn tại Mỹ như “Information and Control” bài báo của ông đã mở đường cho hàng loạt của những nghiên cứu sau này, áp dụng phương pháp lập luận một cách tương đối thay vì lập luận chính xác theo các phương pháp logic vị từ cổ điển. Chứng minh của Lotfali Askar Zadeh cho phép chúng ta có thể khái quát hóa giá trị của các mệnh đề mờ, vì ` 28 thế mà ta có thể làm cho thiết bị máy móc hiểu được các thông tin mà ta truyền vào qua các ngôn ngữ tự nhiên,và một điều tuyệt vời là chúng có thể “hiểu” khá chính xác những nội dung mà ta truyển vào. Logic mờ đang được sử dụng trong nhiều ứng dụng liên quan đến nhận dạng, xử lý hình ảnh, xử lý ngôn ngữ, điểu khiển tự động, truy vấn bằng nội dung hình ảnh, phát hiện ranh rới, theo dõi đối tượng. Logic mờ là một công cụ tính toán dùng để sử dụng những kiến thức của con người vào các thuật toán khả thi. Ý tưởng về logic mờ được giới thiệu bởi tiến sỹ Lofti Zadeh của UC-Berkley vào năm 1960, là một cách thức của mô hình về sự không chắc chắn của ngôn ngữ tự nhiên. Logic mờ đã được áp dụng gần đây trong quá trình kiểm soát, mô hình hóa, ước tính, xác định, dự đoán thị trường chứng khoán, chẩn đoán, khoa học, quân sự, nông nghiệp , và nhiều lĩnh vực khác. Một trong những ứng dụng tiên phong trong logic mờ là trong các hệ thống điều khiển. Điều khiển dựa trên logic mờ được sử dụng trong các ứng dụng khác nhau. Suốt trong nhiều năm qua, kiểm soát dựa trên logic mờ đã xuất hiện như một trong những các lĩnh vực tích cực và hiệu quả nhất để nghiên cứu ứng dụng lý thuyết logic mờ, đặc biệt là trong phạm vi rộng của quá trình công nghiệp thiếu dữ liệu định lượng liên quan đến đầu vào - đầu ra. Không thể phủ nhận những thành công và những mặt tích cực mà logic mờ đem lại. Logic mờ đã được chấp nhận và sử dụng rộng rãi nhưng bên cạnh đó nó vẫn bị phê phán bởi những quan điểm bất đồng tại một vài trường phái nghiên cứu khác. ` 29 1.4.2. Khái niệm tập hợp mờ. Khái niệm Tập hợp mờ hay còn gọi là “Tập mờ” là mở rộng của khái niệm tập hợp cổ điển, dùng để đáp ứng nhu cầu biểu diễn những tri thức không chính xác. Để hiểu thế nào là logic mờ, trước hết cần hiểu thế nào là tập hợp mờ (fuzzy set) - Cho X là một không gian nền - A là tập mờ hoặc tập con mờ trên không gian nền X khi và chỉ khi A được xác định bởi hàm : μA được gọi là hàm thuộc hay hàm thành viên (Membership Function) để chỉ phụ thuộc của các phần tử trong tập X vào tập A. Nên μA(x) còn được gọi là mức độ phụ thuộc (membership degree hoặc degree of membership ) của phần tử x Î X lên tập A. 1.4.3. Các đặc trƣng của tập mờ Các đặc trưng của một tập mờ A trên X, được hiểu là những thông tin để mô tả về các phần tử liên quan đến tập mờ A, những đặc trưng này có thể chỉ rõ sự khác biệt của những tập con cổ điển khác của X với tập mờ A. Định nghĩa 1.4.3.1 Giá đỡ của tập mờ A (Support) là tập các phần tử có giá trị hàm thuộc lớn hơn 0 trong tập mờ A, được ký hiệu và xác định như sau: ` 30 supp(A) = {x | x ∈ X | μA(x) > 0} Định nghĩa 1.4.3.2 Chiều cao của tập mờ A (Hight) là giá trị lớn nhất mà hàm thuộc có thể lấy trong tập mờ A, được ký hiệu và xác định như sau: h(A) = sup{μA(x), x ∈ X} Như vậy, tập mờ A có nhân khác rỗng khi và chỉ khi A là tập mờ chuẩn hóa 1.4.4. Các phép toán trên tập mờ 1.4.4.1. Phép hợp ( U ) Trên tập vũ trụ U cho hai tập mờ A~ và B~. Hợp của hai tập mờ này là một tập mờ được ký hiệu là mà hàm thuộc của nó được định nghĩa theo điểm như sau : hay, trong trường hợp U là hữu hạn hay đếm được, Một cách tổng quát, cho ∈ F(U), i ∈ I, với I là tập chỉ số hữu hạn hay vô hạn nào đó. Khi đó, hợp của các tập mờ như vậy, ký hiệu là , được định nghĩa bằng hàm thuộc như sau: 1.4.4.2. Phép giao ∩ Phép giao của A và B được ký hiệu là: A ∩ B Phép giao sẽ có hàm thuộc một trong các định nghĩa sau: ` 31 1.4.4.3. Phép lấy phần bù ~ Cho A là tập mờ trong X có hàm thuộc µA. Phần bù ¬A của A trong X là một tập mờ có hàm thuộc xác định như sau: 𝜇¬A = 1 − 𝜇 , ∀x ∈ X Hình 2.4: Phần bù của một tập mờ 1.4.4.4. Phép mờ hóa (Fuzzification) . Fuzzification là quá trình chuyển đổi giá trị đầu vào rõ nét thành giá trị mờ được thực hiện bằng cách sử dụng thông tin trong cơ sở tri thức. Fuzzification bắt đầu với việc chọn các hàm thành viên phù hợp cho các tập mờ. Hình 2.4.1 cho thấy một lựa chọn điển hình, một loạt các đoạn thẳng. (Các lựa chọn khác là có thể, ví dụ: đường cong sigmoid.) Mỗi dấu có thể là một thành viên của ít nhất một tập mờ. Từ hình vẽ, chúng ta có thể thấy rằng khi ` 32 Hình 2.4.1 Chúng ta cũng cần định lượng các thuật ngữ 'rất' và 'đúng hơn'. Những hàng rào ngôn ngữ này có thể được hiểu như sau: Với những diễn giải này, một dấu ấn 80% có Tóm lại: phép mờ hóa là quá trình hình thành ánh xạ từ đầu vào đã cho sang đầu ra bằng logic mờ. Ánh xạ sau đó cung cấp một cơ sở mà từ đó các quyết định có thể được đưa ra, hoặc các mẫu được phân biệt. 1.4.4.5. Phép khử mờ Phương pháp chuyển đổi từ dữ liệu đầu vào là dữ liệu mờ và có đầu ra là giá trị thực được gọi là phép khử mờ. Nhưng trên thực tế về phương pháp hay cách thức khử mờ thì không có những ràng buộc hay định nghĩa cách thức chặt chẽ nào cả. Các hệ thống dựa trên quy tắc mờ đánh giá các quy luật ngôn ngữ If-then bằng cách sử dụng độ mờ, suy luận và các thủ tục thành phần. Chúng tạo ra kết quả mờ mà thường phải được chuyển đổi thành đầu ra rõ nét. Đến biến đổi các kết quả mờ thành sự sắc nét. Làm mờ ` 33 là quá trình chuyển đổi một đầu ra bị mờ thành một giá trị rõ nét duy nhất đối với một bộ mờ. Đầu ra từ công cụ suy luận ( loại Mamdani) là mờ và chúng cần được chuyển đổi thành đầu ra rõ nét trước khi gửi chúng đến thiết bị truyền động để kiểm soát quá trình, việc chuyển đổi số lượng mờ thành rõ nét , giá trị đó được gọi là khử mờ. Trong một khía cạnh nào đó, về trực quan chúng ta có thể lựa chọn một phương pháp khử mờ được xem là tối ưu nhất. Vào năm 1993 C.Thomas và Hellendoorn đã đưa ra 5 tiêu chuẩn trực quan như sau: • Tính không nhập nhằng (disambiguity), nghĩa là phương pháp chỉ sinh ra một giá trị đầu ra duy nhất • Tính liên tục, nghĩa là khi ta tạo một sự thay đổi bất kỳ của dữ liệu đầu vào thì kết quả của đầu ra cũng thay đổi theo nó. • Độ phức tạp tính đơn giản, một đòi hỏi tự nhiên • Tính hợp lý, với tính chất này nó yêu cầu giá trị đầu ra phải nằm ở khu vực trung tâm của tập mờ và độ thuộc hay giá trị hàm thuộc tại đó phải lớn. • Tính trọng số của phương pháp (weighting method) phương pháp này tính đến trọng số hay mức độ ưu tiên của tập mờ kết quả đầu ra. Như vậy có thể kết luận là các tiêu chuẩn cần bảo đảm giá trị khử mờ của tập mờ A~ là phần tử thực đại diện một cách hợp lý của A~. Ngoài ra chúng ta có thể tham khảo thêm một số phương pháp khử mờ sau: - Phương pháp khử mờ sử dụng cực đại trung bình có trọng số. - Phương pháp khử mờ sử dụng cực đại trung bình (average maximum). - Phương pháp trọng tâm. ` 34 1.5. Kết luận chƣơng Trong chương 1 này, luận văn đã trình bày về kiến trúc tổng quan hệ thống tìm kiếm ảnh theo nội dung, các đặc trưng cấp thấp của ảnh như màu sắc, kết cấu, hình dạng sử dụng trong tìm kiếm ảnh theo nội dung. Trong đó, biểu đồ màu là kỹ thuật được sử dụng. Ngoài ra, luận văn cũng trình bày khả năng ứng dụng của hệ thống CBIR trong nhiều lĩnh vực, giới thiệu một số hệ thống tìm kiếm ảnh theo nội dung tiêu biểu trên thế giới.Trình bày khái quát về logic mờ, tập hợp mờ, các đặc trưng, phép toán và các kiểu hàm thuộc của tập mờ. ` 35 CHƢƠNG 2. TÌM KIẾM ẢNH THEO NỘI DUNG TRÊN CƠ SỞ BIỀU ĐỒ MÀU MỜ 2.1. Đo khoảng cách giữa các biểu đồ màu Thông thường hệ thống tra cứu ảnh theo nội dung sẽ truy vấn hình ảnh bằng phương pháp đo tương tự dựa trên các đặc trưng, việc xác định nó có thể dưới nhiều hình thức như phát hiện biên, màu sắc, vị trí điểm ảnh... các phương pháp như histogram, màu sắc và phân tích histogram dòng cột sử dụng biểu đồ để xác định độ tương tự. Do đó, độ đo có ý nghĩa quan trọng trong tra cứu ảnh dựa theo nội dung. Độ đo mang ý nghĩa quyết định kết quả tìm kiếm sẽ như thế nào, mức độ chính xác ra sao. Nhiều phép đo khoảng cách đã được khai thác trong việc tra cứu ảnh chúng bao gồm: khoảng cách Euclide, khoảng cách Cosin, khoảng cách giao nhau của biểu đồ histogram, khoảng cách Minkowski 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 cho các bộ mô tả ước lượng hình dạng khác nhau. Trong hình ảnh của máy tính, khoảng cách Euclide thường được sử dụng để đo khoảng cách màu giữa hai màu. Và làm thế nào để đối phó với sự thay đổi chiếu sáng vẫn là một chủ đề nghiên cứu quan trọng. Tuy nhiên kết quả đánh giá đã chứng minh rằng khoảng cách Euclide không hoạt động tốt khi thay đổi ánh sáng vì mắt người có thể nhận ra các màu tương tự hoặc không liên quan dưới sự thay đổi chiếu sáng, nên một mô hình khoảng cách màu mới dựa trên nhận dạng hình ảnh được đề xuất. Đầu tiên, chúng ta thấy rằng các màu sắc khác nhau được phân phối phức tạp trong không gian màu. Ta mở rộng để phân chia không gian HSV thành 3 không gian con ít phức tạp hơn và nghiên cứu các mô hình khoảng cách cụ thể của chúng. Sau đó , một khoảng cách màu sắc mới được mô hình hóa dựa trên nhận dạng hình ảnh và mô hình khoảng cách màu sắc được đề xuất theo nguyên tắc khoảng ` 36 cách màu sắc hình ảnh. 2.1.1. Độ đo khoảng cách Minkowski(Lp) Độ đo khoảng cách Minkowski thích hợp để tính khoảng cách giữa hai ảnh có cùng chiều hoặc véc tơ đặc trưng của ảnh là độc lập và có số bin màu giống nhau (xem hình 2.5). Cho D(Q,I) là khoảng cách đo giữa hình ảnh truy vấn Q và hình ảnh I trong CSDL và fi(Q) là số lượng điểm ảnh trong bin thứ I của ảnh Q thì khoảng cách này được định nghĩa trong [6] là: D (Q,I) = (∑|fi (Q) – fi(I)| p ) 1/p (2-1) Trong đó p gọi là thành tố Minkowski (Minkowski Factor) Cho trước 2 véc tơ n chiều: Q = [q1, q2,, qn] T ; I = [i1, i2,, in] T - Nếu p = 1, độ đo là khoảng cách City block hay Manhattan có công thức tính: (2-2) - Nếu p = 2, độ đo là khoảng cách Euclide có công thức tính: (2-3) ` 37 Hình 2.5 Độ đo khoảng cách Minkowski Độ đo khoảng cách Minkowski là độ đo được sử dụng phổ biến cho việc tìm kiếm hình ảnh. Độ đo khoảng cách Euclide thường được sử dụng trong hệ thống tìm kiếm ảnh dựa trên nội dung. 2.1.2. Độ đo khoảng cách toàn phƣơng(Quaratic) Độ đo khoảng cách toàn phương ngoài việc dùng để so sánh các Bin màu giống nhau nó còn được dùng để so sánh nhiều bin màu giữa các biểu đồ màu. Nó được xác định bởi công thức: d(Q,I)=(HQ –HI) t A(HQ –HI) ( 2-4) ` 38 Hình 2.6: Độ đo khoảng cách Quadretic Với Q và I là 2 ảnh để so sánh, HQ là biểu đồ màu của ảnh Q và HI nó là biểu đồ màu của ảnh I, A =[ai,j] là một ma trận có kích thước n * n trong đó n là số bin trong các biểu đồ màu, và ai,j biểu diễn sự tương tự giữa màu i và màu j. Độ đo khoảng cách Quaratic đã được sử dụng trong nhiều hệ thống tìm kiếm hình ảnh dựa trên biểu đồ màu.Nó đã khắc phục được những thiếu sót của độ đo khoảng cách Euclide và biểu đồ màu giao nhau vì nó xem xét sự tương tự chéo giữa các màu sắc . ` 39 2.1.3. Độ đo khoảng cách biểu đồ giao nhau (Histogram Intersection Distance) Phương pháp này được thực hiện dựa trên ý tưởng lấy phần giao của hai biểu đồ màu cần so sánh, được định nghĩa như sau: (2-5) Trong đó,HA,HBlà biểu đồ màu của hai ảnh A và B với các bin i=0,1, ..,L-1 tương ứng; hA(i), hB(i) biểu thị giá trị biểu đồ của bin thứ I của HA và HB tương ứng. 2.2. Tìm kiếm ảnh theo nội dung trên cơ sở biểu đồ màu thông thƣờng Việc tìm kiếm ảnh theo nội dung trên cớ biểu đồ màu thông thường người ta thường sử dụng hai biểu đồ cơ bản đó là: “ Biểu đồ màu toàn bộ “ và “ Biểu đồ màu cục bộ ”. hai phương pháp này đều có những ưu nhược điểm riêng, sau đây chúng ta cùng tìm hiểu chi tiết về hai phương pháp này. 2.2.1. Biểu đồ màu toàn bộ (Global Color Histogram) Màu sắc là một trong những tính năng cấp thấp được sử dụng rộng rãi trong bối cảnh lập chỉ mục và truy xuất dựa trên nội dung hình ảnh. Nó khá mạnh mẽ để phức tạp hóa nền và độc lập với kích thước và định hướng hình ảnh. Thông thường, màu sắc của một hình ảnh được thể hiện thông qua một số mô hình màu . Một mô hình màu được chỉ định theo hệ tọa độ 3D và không gian con trong hệ thống đó , trong đó, mỗi màu được biểu thị bằng một điểm duy nhất. Các mô hình màu thường được sử dụng là : RGB( đỏ, xanh lá cây, xanh dương). Đối với một hình ảnh ba kênh, chúng ta sẽ có ba biểu đồ như vậy. Để truy xuất hình ảnh, biểu đồ của hình ảnh truy vấn sau đó được đối chiếu với biểu đồ của tất cả các hình ảnh trong cơ sở dữ liệu bằng cách sử dụng một số liệu tương tự. Có hai loại biểu đồ màu, biểu đồ màu toàn bộ ( GCH) và biểu ` 40 đổ màu cục bộ (LCH). Một GCH đại diện cho một hình ảnh toàn bộ với một biểu đồ màu duy nhất . Một LCH chia một hình ảnh thành các khối cố định và lấy biểu đồ màu của từng khối đó. LCH chứa nhiều thông tin hơn vè một hình ảnh nhưng lại rất đắt khi so sánh hình ảnh vector. Trong biểu đồ màu mẫu có 3 bin: Black, white and grey. Ta kí hiệu biểu đồ màu của ảnh ảnh A:{25%, 25%, 50%}; ảnh B: {18.75%, 37.5%, 43.75} ; ảnh C: {18.75%, 37.5%, 43.75}; Nếu sử dụng thước đo khoảng cách Euclidean để tính toán khoảng cách biểu đồ thì khoảng cách giữa hai ảnh A và B cho biểu đồ màu toàn bộ là: Sử dụng biểu đồ màu toàn bộ để tra cứu ảnh dựa trên màu sắc là một phương pháp đã có từ lâu. tuy nó không chứa các thông tin liên quan đến bố màu tại các phân vùng nên khoảng cách giữa các ảnh với nhau đôi khi không thể chỉ ra được tương quan giữa chúng. Ví dụ khoảng cách giữa ảnh Avà C khác so với khoảng cách giữa ảnh A và B nhưng nếu sử dụng biểu đồ màu toàn bộ để việc xây dựng thì chúng ta lại thu được khoảng cách tương tự giữa chúng. Ngoài ra còn có trường hợp hai ảnh khác nhau có GCH giống nhau như ví dụ trên ảnh B và C. và đây chính là hạn chế của biểu đồ màu toàn bộ. ` 41 Hình 2.7: Ảnh và biểu đồ màu của chúng 2.2.2. Biểu đồ màu cục bộ ( LCH ) Thuật toán cơ sở tìm kiếm ảnh dựa trên biểu đồ màu cục bộ ( viết tắt là LCH ) phương pháp này cho biết thông tin liên quan đến sự phân bố màu tại các vùng của ảnh. Để thực hiện phương pháp tra cứu này thì việc đầu tiên là ta phân đoạn bức ảnh thành nhiều khối và sau đó biểu diễn chúng như một biểu đồ màu cho mỗi khối. Bằng cách sử dụng biểu đồ của chúng khi đem so sánh hai ảnh này với nhau ta tính toán khoảng cách của chúng, giữa một vùng trong một ảnh và một vùng tương ứng trong ảnh khác. Khi ta cộng tổng tất cả các khoảng cách này thì sẽ cho kết quả là khoảng cách của 2 ảnh. Trong trường hợp sử dụng căn bậc 2 của khoảng cách Euclidean để tính toán khoảng cách biểu đồ thì khoảng cách giữa hai ảnh Q và I cho biểu đồ màu cục bộ là: Trong đó: • M được coi là số vùng được phân đoạn trong ảnh, • N là số bin trong biểu đồ màu. ` 42 • H[i] là giá trị của bin i trong biểu đồ màu đại diện cho vùng k của ảnh. Hình 2.7: Tính toán khoảng cách giữa ảnh A và B sử dụng LCH Áp dụng công thức tính khoảng cách Euclidean ta tính toán được khoảng cách giữa ảnh A và B như sau: ` 43 2.3. Tìm kiếm ảnh theo nội dung trên cơ sở biểu đồ màu mờ Trái ngược với biểu đồ màu thông thường (CCH) chỉ định mỗi pixel vào một bin màu, biểu đồ màu mờ (FCH) xem xét sự tương đồng màu bằng cách chia tổng giá trị thành viên của mỗi pixel vào tất cả các bin của biểu đồ màu. Vì vậy, FCH được đề xuất áp dụng cho việc lập chỉ mục và tìm kiếm hình ảnh theo nội dung, đặc biệt với những CSDL ảnh lớn [5]. 2.3.1. Định nghĩa biểu đồ màu mờ(FCH) Trong [5], FCH của ảnh màu I được biểu diễn dưới dạng F(I)={f1,f2,, fn),với: Pj là xác suất của một pixel chọn từ ảnh I ở pixel thứ j và Pj = 1/ N,𝜇𝑖𝑗 là giá trị thành viên của pixel thứ j trong bin màu thứ i. FCH không chỉ xem xét sự tương đồng của các màu sắc từ các bin màu khác nhau mà còn xem xét sự khác nhau của các màu trong cùng một bin màu. Do đó, FCH làm giảm sự nhạy cảm với nhiễu 2.3.2. Tính toán FCH và độ đo khoảng cách Để tính FCH của một ảnh màu, chúng ta cần phải tính các giá trị thành viên của mỗi pixel đối với tất cả các bin màu có trong ảnh. Cách tiếp cận trực tiếp này không thuận lợi vì thực hiện các phép tính toán lớn. Hơn nữa, để định lượng chính xác sự tương đồng về cảm nhận màu sắc giữa hai màu trong một không gian màu cụ thể, nên xem xét sự đồng nhất của không gian màu đó.Như trình bày ở mục trên về không gian màu, L*a*b hay CIELAB là một không gian màu độc lập với các thiết bị và có sự đồng nhất về cảm nhận màu sắc. Do đó, không gian ` 44 màu CIELAB hay L*a*b* đã được sử dụng trong một số giải pháp tính toán FCH. 2.3.3. Tính toán FCH trong không gian màu CIELAB sử dụng thuật toán phân cụm mờ Trong Ju Han và Kai-Kuang Ma đã giới thiệu thuật toán phân cụm mờ fuzzy C -means (FCM) để tính toán nhanh FCH mà không cần phải xử lý các hàm thành viên. Họ tìm thấy sự tương ứng giữa biểu đồ màu thông thường (CCH) và biểu đồ màu mờ (FCH). Sơ đồ thủ tục tính toán FCH được minh họa như hình 2.7.1 Hình 2.8: Sơ đồ thủ tục tính toán FCH (n’=163 = 4096) Trong không gian màu RGB, thực hiện lượng tử hóa đều các màu bằng cách ánh xạ tất cả các màu điểm ảnh vào n’ bin chứa biểu đồ. Ở đây, n’ bin được chọn đủ lớn để cho thấy sự khác biệt màu sắc giữa hai bin liền kề. Tiếp theo, chuyển đổi n’ màu từ không gian màu RGB sang không gian màu CIELAB. Cuối cùng, phân loại n’ màu trong CIELAB thành n cụm bằng cách sử dụng thuật toán phân cụm FCM, với mỗi cụm biểu diễn một bin FCH. Giá trị thành viên điểm ảnh của một bin FCH là đại diện giá trị thành viên bin màu tương ứng với bin màu thô. Ở đây, ` 45 giá trị thành viên chỉ cần tính một lần và chúng được biểu diễn qua ma trận thành viên M=[mij]n’xn, mỗi phần tử mij của M là giá trị thành viên của bin màu j phân phối cho bin màu i. Do đó FCH của một ảnh có thể tính trực tiếp từ CCH của nó mà không cần tính toán các giá Thành viên cho mỗi pixel.Ví dụ, chon ’bin CCH với Hn’x1 tương ứng n bin FCH với Fnx1 được tính như sau: Trong đó Mnxn’ chỉ cần tính một lần và được sử dụng để tính FCH cho mỗi ảnh trong CSDL. FCM là thuật toán nhằm tối thiểu hóa hàm mục tiêu Jm được M. R. Rezaee và cộng sự [21]1 định nghĩa như sau: Trong đó,V=[v1,v2,,vc] Tlà ma trận biểu diễn các giá trị đối tượng tâm của cụm, giá trị của uik đại diện cho các thành viên dữ liệu xk thuộc tập X={x1,x2,, xn} tương ứng với cụm thứ i. Tích vô hướng định nghĩa là một ma trận chuẩn A xác định phép đo độ tương tự giữa một điểm dữ liệu và các cụm nguyên mẫu tương ứng, U={uik} là ma trận phân hoạch mờ ngẫu nhiên của X trong c cụm,trọng số của số mũ m kiểm soát mức độ phân chia thành viên bởi các cụm c và gọi là tham số mờ. Bezdek (1981) đã đưa ra định lý: Nếu ||xk – vi||A> 0 với mọi i,k và m >1 thì Jm đạt tối thiểu trên (U,V) khi: ` 46 Ở đây,chúng ta cần phân loại n’ màu trong CCH thành n cụm trong FCH. Do tính đồng nhất về nhận thức của không gian màu CIELAB, tích vô hướng ||xk – vi|| 2 A có thể được thay thế bằng ||xk – vi|| 2. Đây chính là khoảng Thuật Toán FCM Input: số cụm c, số mũ m cho hàm mục tiêu J và dung sai ϵ Output: c cụm dữ liệu sao cho hàm mục tiêu trong (2-9) đạt giá trị cực tiểu. Begin Bước1:Nhập giá trị cho 2 tham số:số cụm c (1<c<N)và số mũ m (1 < m <+∞). Bước 2: Khởi tạo các trung tâm cụm vi, 1 ≤ i ≤ c. Bước 3: Nhập giá trị X={x1, x2,, xn} Bước4:Tính toán các trung tâm cụm {vi (l)} bằng công thức(2-10) Bước 5: Cập nhật U(l) bằng công thức(2-11) Bước6: Nếu||U(l)–U(l-1)||>ϵ,l=l+1thì quay lại Bước 4,ngược lại thuật toán dừng. End ` 47 cách Euclide giữa màu xk và trung tâm cụm vi. Kết quả phân cụm mờ của thuật toán FCM được biểu diễn bởi ma trận U=[uik]nxn’ và uik là bậc của thành viên của màu xk đối với trung tâm cụm vi. Như vậy, ma trận Unxn’ có thể xem là ma trận mong muốn Mnxn’ cho tính toán FCH, tức là Mnxn’= Unxn’. Số mũ m trong thuật toán FCM kiểm soát mức độ hoặc “lan truyền” của các thành viên phân chia trong các cụm mờ. Do đó, có thể dùng tham số này để kiểm soát mức độ phân chia tương tự giữa các bin khác nhau trong FCH. Ma trận thành viên có thể được điều chỉnh theo các ứng dụng tìm kiếm ảnh khác nhau. Kết quả phân cụm bị ảnh hưởng rất lớn trong việc chọn các tham số cụm, những tham số này thường được chọn ngẫu nhiên hoặc theo kinh nghiệm (Heuristic). Với m →1+ thì thuật toán FCM là thuật toán rõ. Vớ im→∞ thì thuật toán FCM là thuật toán phân cụm mờ với uik=1/c .Chưa có quy tắc nào lựa chọn tham số m đảm bảo cho việc phân cụm hiệu quả. [5] Trong JuHanand Kai-Kuang Ma cho thấy rằng lựa chọn trọng số mũ m =1.9 đạt được hiệu suất tìm kiếm tốt nhất trong các thử nghiệm của họ. Tóm lại, thuật toán FCM nhằm khám phá ra các cụm chồng lên nhau. Tuy nhiên, FCM vẫn còn chứa đựng các nhược điểm trong việc xử lý đối với các phần tử ngoại lai và nhiễu trong dữ liệu. 2.3.4. Phƣơng pháp tạo biểu đồ màu dựa vào hệ thống liên kết mờ trong không gian màu L*a*b* Có một số nghiên cứu đáng chú ý về biểu đồ màu mờ và ứng dụng của nó để tìm kiếm hình ảnh dựa trên nội dung. Konstantinidis và cộng sự (2005) [6] đã đề xuất một hệ thống liên kết mờ để tạo biểu đồ màu trong không gian màu L*a*b*. Hệ thống này liên kết các màu từ không gian màu L*a*b* đến các bin màu của FCH bằng cách sử dụng hệ thống suy lu

Các file đính kèm theo tài liệu này:

  • pdfluan_van_nghien_cuu_phuong_phap_xay_dung_he_thong_tim_kiem_a.pdf
Tài liệu liên quan