Tài liệu Tra cứu ảnh dựa trên lưới và ứng dụng

Tra cứu ảnh dựa trên lưới và ứng dụng Lê Thị Lan Anh Trường Đại học Công nghệ Luận văn Thạc sĩ ngành: Hệ thống thông tin; Mã số: 60 48 05 Người hướng dẫn: PGS.TS. Ngô Quốc Tạo Năm bảo vệ: 2012 Abstract. Giới thiệu về tra cứu ảnh, các đặc trưng của ảnh, cấu trúc hệ thống tra cứu ảnh theo nội dung và một số lĩnh vực ứng dụng của tra cứu ảnh. Trình bày một số phương pháp trích chọn đặc trưng hình ảnh như màu sắc, kết cấu, hình dạng … Tập trung tìm hiểu kỹ thuật tra cứu ảnh dựa trên lưới. Giới thiệu phương pháp tra cứu ảnh kết hợp giữa đặc trưng màu sắc và hình dạng có sử dụng kỹ thuật lưới vùng. Từ cơ sở lý thuyết đã xây dựng ở chương 3 đưa ra ý tưởng, thuật toán xây dựng chương trình mô phỏng tra cứu ảnh dựa trên lưới. Keywords. Hệ thống thông tin; Kỹ thuật xử lý ảnh; Hình ảnh; Công nghệ thông tin Content MỞ ĐẦU Ngày nay, bên cạnh sự phong phú của kho dữ liệu văn bản thì kho dữ liệu ảnh cũng ngày càng trở nên khổng lồ vượt quá sự kiểm soát của con người. Khi có nhu cầu tra cứu một vài bức ảnh nào đó trong một cơ sở dữ liệu có hàng trăm ngàn ảnh, điều này khó có thể thực hiện được khi ta tìm kiếm bằng tay theo cách thông thường, nghĩa là xem lần lượt từng tấm ảnh một cho đến khi tìm thấy ảnh có nội dung cần tìm. Do đó, việc xây dựng các hệ thống tra cứu là rất cần thiết. Các công cụ tra cứu ảnh thường dựa vào hai đặc trưng chính là văn bản đi kèm ảnh hoặc nội dung ảnh. Tra cứu ảnh theo nội dung đã nhận được nhiều sự quan tâm của các nhà khoa học. Tra cứu ảnh dựa trên lưới là một hướng nghiên cứu mới. Một số phương pháp tra cứu ảnh dựa trên lưới có thể sử dụng lưới kết hợp với đặc trưng hình dạng hoặc đặc trưng màu sắc trong quá trình tra cứu. Nội dung luận văn giới thiệu một số vấn đề liên quan đến tra cứu ảnh, tra cứu ảnh theo nội dung và một số phương pháp trích chọn đặc trưng hình ảnh. Nghiên cứu phương pháp tra cứu ảnh dựa trên lưới và tìm hiểu phương pháp kết hợp đặc trưng màu sắc với đặc trưng hình dạng. Cuối cùng đi xây dựng chương trình ứng dụng mô phỏng phương pháp tra cứu ảnh dựa trên lưới. Nội dung luận văn gồm có bốn chương: Chƣơng 1: Tổng quan về tra cứu ảnh. Chƣơng 2: Một số phương pháp trích chọn đặc trưng hình ảnh. Chƣơng 3: Tra cứu ảnh dựa trên lưới. Chƣơng 4: Thiết kế và cài đặt chương trình tra cứu ảnh dựa trên lưới. Chƣơng 1: TỔNG QUAN VỀ TRA CỨU ẢNH 1.1 Giới thiệu chung Quá trình thực thi của hệ thống xử lý ảnh bao gồm: - Thu nhận ảnh. - Số hóa ảnh. - Phân tích ảnh. - Nhận dạng ảnh. Tra cứu ảnh là một quá trình tìm kiếm ảnh trong một cơ sở dữ liệu ảnh những ảnh thoả mãn một yêu cầu nào đó. Khi tra cứu ảnh người ta có thể sử dụng phương pháp tra cứu ảnh theo văn bản đi kèm hay theo nội dung ảnh. Tra cứu ảnh theo nội dung được thực hiện theo nguyên tắc sử dụng các đặc trưng mức thấp của ảnh như màu sắc, kết cấu, … để biểu diễn ảnh. Sau đó tính độ tương tự giữa ảnh cần tìm và ảnh trong cơ sở dữ liệu để đưa ra kết quả là bức ảnh có độ tương tự cao nhất. 1.2 Các đặc trƣng mức thấp của ảnh Đặc trưng mức thấp của ảnh là một vài đặc điểm thu nhận được từ một bức ảnh như: Hình dạng, màu sắc, kết cấu, và mối liên hệ không gian giữa các đối tượng. Đặc trưng màu sắc là đặc trưng được sử dụng phổ biến hơn cả do đặc trưng này cho phép con người nhận ra sự khác biệt rõ ràng nhất giữa các hình ảnh. Hình dạng của đối tượng có thể thu được bởi đường viền bao xung quanh. Có hai cách tiếp cận được sử dung để phân tích hình dạng, đó là dựa trên vùng hình dạng và biên. Hình 1.1: Đặc trưng hình dạng Kết cấu cũng là một đặc trưng quan trọng trong nhận dạng bản mẫu và tra cứu ảnh. Nó cung cấp bản mẫu trực quan về vùng của ảnh. Các thuộc tính quan trọng của đặc trưng kết cấu như: Độ tương phản, thuộc tính thô, hướng, tính quy luật, chu kỳ và tính ngẫu nhiên. Hình 1.2: Đặc trưng kết cấu Mối quan hệ không gian dùng để phân biệt các đối tượng khác nhau trong một ảnh. Hình 1.3: Biểu diễn hình dạng qua mối quan hệ không gian 1.3 Cấu trúc của hệ thống tra cứu ảnh theo nội dung Một hệ thống tra cứu ảnh có thể thực hiện qua nhiều công đoạn: Nhập ảnh truy vấn, nhập dữ liệu ảnh cho cơ sở dữ liệu, chuẩn hóa ảnh, trích chọn đặc trưng của ảnh truy vấn và ảnh trong cơ sở dữ liệu, tính toán độ tương tự và cách hiển thị kết quả lên màn hình, … Hình 1.4: Cấu trúc hệ thống tra cứu ảnh theo nội dung 1.4 Một số hệ thống tra cứu ảnh theo nội dung 1.4.1 Hệ thống QBIC Hệ thống QBIC của hãng IBM là một hệ thống tra cứu ảnh dựa trên nội dung cho phép người sử dụng tra cứu ảnh dựa vào màu sắc, hình dạng và kết cấu. 1.4.2 Hệ thống Photobook Hệ thống này được phát triển ở viện kỹ thuật Massachusetts cho phép người sử dụng tra cứu ảnh dựa trên màu sắc, hình dạng và kết cấu. 1.4.3 Hệ thống VisualSEEK và WebSEEK Cả hai hệ thống này đều được phát triển tại Trường Đại học Colombia. VisualSEEK là hệ thống cơ sở dữ liệu ảnh. WebSEEK là công cụ tìm kiếm trên website. 1.4.4 Hệ thống RetrievalWare Hệ thống này được phát triển bởi tập đoàn công nghệ Excalibur cho phép người sử dụng tra cứu ảnh bởi nội dung màu, hình dạng, kết cấu, độ sáng, kết cấu màu và hệ số co. 1.4.5 Hệ thống Imatch Hệ thống này cho phép người sử dụng tra cứu ảnh bởi nội dung màu, hình dạng, và kết cấu. 1.5 Một số ứng dụng cơ bản của tra cứu ảnh Tra cứu ảnh cùng với sự phát triển lớn mạnh của mình ngày càng được ứng dụng rộng rãi trong các lĩnh vực: Ngân hàng, sở hữu trí tuệ, ngăn chặn tội phạm, quân sự, giải trí … 1.6 Kết luận chƣơng Tra cứu ảnh theo nội dung (CBIR) là một lĩnh vực khoa học được phát triển dựa trên cơ sở lý thuyết và ứng dụng của xử lý ảnh. Hệ thống cho phép người dùng tra cứu các ảnh tương tự trong một cơ sở dữ liệu hình ảnh. Tra cứu ảnh theo nội dung được thực hiện thông qua việc tính độ tương tự giữa hai bức ảnh được biểu diễn bởi một trong số các đặc trưng mức thấp của ảnh như: Màu sắc, hình dạng, kết cấu… Kết quả đưa ra là tập các bức ảnh tương tự với ảnh truy vấn được xắp xếp theo thứ tự giảm dần độ tương tự. Chƣơng 2: MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG HÌNH ẢNH 2.1 Phƣơng pháp trích chọn đặc trƣng theo màu sắc 2.1.1 Không gian màu Không gian màu phổ biến: RGB, CMY, HSx, … Không gian màu RGB RGB là không gian màu được sử dụng phổ biến nhất để hiển thị ảnh. Không gian RGB bao gồm 3 thành phần màu là Đỏ (Red), Xanh lá cây (Green) và Xanh lam (Blue). Các thành phần này gọi là màu cộng bởi vì các màu sắc trong không gian RGB đều có thể thu được bằng cách cộng 3 thành phần màu này lại với nhau. Hình 2.1 Không gian màu RGB. Không gian màu CMY CMY là viết tắt của Cyan-Magenta-Yellow (màu lục lam, màu đỏ tươi, màu vàng), đó là ba màu chính tương ứng với ba màu mực in. Không gian màu HSx Hình 2.2 Mô tả không gian màu HSV. 2.1.2 Lượng tử hoá màu Lượng tử hóa màu là quá trình làm giảm số màu sắc được sử dụng để mô tả ảnh. Việc lượng tử hóa màu trong không gian màu RGB được thực hiện bằng cách chia khối hình lập phương lớn thành những khối nhỏ và mỗi khối nhỏ có thể đại diện cho một màu đơn. Khi giảm một màu {R, G ,B} 24 bit màu thành màu mới {R’, G’ ,B’} với n 3 màu ta đặt: R'  n*R 28 G'  n*G 28 B'  n*B 28 (2.1) Vì vậy, sau khi giảm số màu sẽ có n*n*n=n màu. 2.1.3 Các moment màu Công thức toán học để biểu diễn 3 moment : 3 i  i  si  3 1 N 1 N N f j 1 (2.2) N ( f 1 N ij j 1 ij  i ) 2 (2.3) N ( f j 1 ij  i )3 (2.4) Trong đó fij là giá trị của thành phần màu thứ i của điểm ảnh thứ j và N là số lượng điểm ảnh của ảnh đó. 2.1.4 Biểu đồ màu Biểu đồ màu (Color Histogram) để biểu diễn nội dung màu của một bức ảnh. Trong biểu đồ màu của ảnh, giá trị của mỗi mức sẽ là tổng số điểm ảnh có cùng màu tương ứng. Để so sánh những ảnh có kích cỡ khác nhau biểu đồ màu nên được chuẩn hóa và biểu đồ màu chuẩn hóa được định nghĩa: H’={H’[0], H’[1], H’[2], ..., H’[i], ...H’[N]} (2.5) H [i] H ' [i]  P Với (2.6) và P là tổng số các điểm trong ảnh. 2.2 Phƣơng pháp trích chọn đặc trƣng theo kết cấu 2.2.1 Các đặc trưng Tamura Độ thô Độ thô được dùng để đo tính chất hạt của kết cấu. Để tính toán độ thô, tại mỗi điểm ảnh (x,y) ta tính toán một trung bình động (average moving) Ak(x,y) sử dụng một cửa sổ kích thước 2k×2k (k = 0, 1, ..., 5): Ak ( x, y )  x  2 k 1 1 y  2 k 1 1   g (i, j ) / 2 i  x 2 k 1 j  y 2 2k k 1 (2.7) Trong đó g(i,j) là độ sáng của điểm ảnh ở vị trí (i,j). Độ thô được tính toán bằng cách lấy giá trị trung bình của Sbest trên phạm vi toàn bức ảnh, nghĩa là: Fcrs  1 m  m.n i 1 n S j 1 best (i, j ) (2.11) Độ tương phản Công thức tính độ tương phản như sau: Fcon  4  4 (2.12) Độ định hướng Độ lớn và góc pha của véc tơ này được định nghĩa: | G | |  H |  | V | 2 (2.13)     tan 1 ( V )  H 2 (2.14) Tính toán histogram tổng hợp của cả ảnh để xác định độ định hướng tổng thể dựa trên độ sắc của các đỉnh: np Fdir   p  (   w p p ) 2 H D ( ) (2.15) 2.2.2 Các đặc trưng Wold Một cách tiếp cận khác để biểu diễn kết cấu là sử dụng phân tích Wold. Phân tích Wold có 3 thành phần độ hài hoà, độ phai mờ và độ bất định tương ứng với các đặc điểm tính chu kỳ, tính định hướng và tính ngẫu nhiên của kết cấu. Trong miền tần số ta xây dựng được các công thức: Fy ( , )  Fu ( , )  Fd ( , )  Fu ( , )  Fh ( , )  Fe ( , ) (2.16) 2.2.3 Mô hình SAR Trong mô hình SAR, độ chói của các điểm ảnh được coi như các biến ngẫu nhiên. Độ chói g(x,y) của điểm ảnh (x,y) được coi như là một tổ hợp tuyến tính độ chói của điểm ảnh liền kề g(x’,y’) và mẫu nhiễu dương (x,y) tức là: g ( x, y)     ( x' , y' ) g ( x' , y' )   ( x, y) ( x ', y ')D (2.17) 2.2.4 Ma trận đồng khả năng Một số đặc trưng của kết cấu có thể tính được dựa vào phương pháp ma trận đồng khả năng là: Năng lượng: Entropy:  C i 2 (i, j ) j   C (i, j) log C (i, j) i j Độ tương phản:   (i  j) i 2 C (i, j ) j C (i, j )   1 | i  j | Tính đồng nhất: 2.2.5 Lọc Gabor Hàm lọc Gabor hai chiều g(x,y) được định nghĩa: i g ( x, y)  j 1 x2 y2 exp[  ( 2  2 )  2jWx 2 x y 2 x y 1 (2.18) 2.2.6 Biến đổi dạng sóng Biến đổi dạng sóng phân tích một tín hiệu thành một họ các hàm cơ sở mn(x) bằng cách dịch chuyển và co giãn một hàm gốc (x), tức là: mn(x) = 2-m/2(2-mx - n) (2.24) Trong đó m và n là tham số co giãn và tham số dịch chuyển. Một tín hiệu f(x) có thể được biểu diễn dưới dạng: f ( x)   cmn mn ( x) m,n (2.25) 2.3 Phƣơng pháp trích chọn đặc trƣng hình dạng Biểu diễn hình dạng của đối tượng ảnh có thể chia thành hai kiểu: Theo đường bao quanh (biên) và theo vùng. Hình 2.3 Biểu diễn hình dạng theo đường biên và theo vùng 2.3.1 Biên và các phương pháp phát hiện biên Phƣơng pháp phát hiện biên trực tiếp Phương pháp này làm nổi biên dựa vào sự biến thiên độ xám của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên là kỹ thuật đạo hàm. Phƣơng pháp phát hiện biên gián tiếp - Thuật toán dò biên tổng quát như sau: Bước 1: Xác định cặp nền-vùng xuất phát: cặp nền-vùng xuất phát được xác định bằng cách duyệt ảnh lần lượt từ trên xuống dưới, từ trái sang phải và kiểm tra theo định nghĩa cặp nền-vùng. Bước 2: Xác định cặp nền-vùng tiếp theo. Bước 3: Lựa chọn điểm biên Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2. 2.3.2 Xử lý ảnh trong miền tần số và biến đổi Fourier Để biểu diễn dữ liệu trong miền tần số cần phải thực hiện một số biến đổi thông qua các phép biến đổi: Fourier, ... Xét một ví dụ đơn giản: tín hiệu đầu vào có dạng hình cosin được biểu diễn trong miền thời gian và miền tần số: Hình 2.4 Biểu diễn hình dạng theo miền thời gian và miền tần số. Hình 2.5: Ảnh thực (a) và ảnh thu được sau biến đổi Fourier (b) 2.4 Thông tin không gian Thu thông tin không gian của các đối tượng trong một ảnh là một quá trình quan trọng đối với các hệ thống GIS. Quá trình này bao gồm việc biểu diễn vị trí không gian tuyệt đối và cũng bao gồm vị trí không gian tương đối của các đối tượng. Các thao tác như giao và chồng được sử dụng. Bố cục màu kết hợp thông tin không gian với thông tin màu xuất hiện trong ảnh và tạo ra một đặc trưng quan trọng trong quá trình tra cứu. 2.5 Phân đoạn Phân đoạn là quá trình phân ảnh ra thành các vùng mà về lý tưởng nó sẽ tương ứng với các đối tượng xuất hiện trong ảnh. Trong phân đoạn các yêu cầu chính xác phân đoạn là rất khác nhau cho các đặc trưng hình và các đặc trưng bố cục. 2.6 Kết luận Như vậy chương 2 đã tập trung giới thiệu một số phương pháp trích chọn đặc trưng hình ảnh trong tra cứu ảnh theo nội dung. Với mỗi phương pháp lại có các kỹ thuật tương ứng khác nhau. Tùy vào từng trường hợp cụ thể chúng ta có thể sử dụng phương pháp trích chọn nào đó cho phù hợp để trả về kết quả tra cứu là tốt nhất. Chƣơng 3: TRA CỨU ẢNH DỰA TRÊN LƢỚI 3.1 Định nghĩa lƣới Hình 3.1: Biểu diễn lưới. 3.2 Phƣơng pháp tra cứu ảnh dựa trên lƣới Tra cứu ảnh dựa trên lưới là phương pháp tra cứu dựa trên hình đại diện và độ đo tương tự. 3.2.1 Một số khái niệm cơ bản 3.2.1.1 Khái niệm về hình dạng Hình dạng không phải là một thuộc tính của ảnh, hình dạng chỉ là biên của đối tượng bất kỳ có trong ảnh. 3.2.1.2 Trục chính của hình dạng Trục chính của hình dạng là đoạn thẳng nối hai điểm thuộc đường bao của vùng hình dạng và có độ dài lớn nhất. 3.2.1.3 Trục phụ của hình dạng Trục phụ của hình dạng là đoạn thẳng vuông góc với tru ̣c chiń h, có đô ̣ dài đảm bảo để có thể vẽ một hình chữ nhật bao khít hình dạng có các cạnh song song và có độ dài b ằng với trục chính và trục phu ̣. 3.2.1.4 Độ lệch tâm Độ lệch tâm là tỉ lệ đô ̣ dài của tru ̣c chính trên tru ̣c phu .̣ 3.2.1.5 Độ đo tương tự Sự tương tự giữa hai hình ảnh p , q đươ ̣c xác đinh ̣ bằ ng đô ̣ đo tương tự s (p,q). Nế u s(p,q) = 1 có nghĩa là hai hình ảnh đượ c coi là giố ng nhau , ngươ ̣c l ại thì hai hình ảnh khác nhau. 3.2.2 Tra cứu ảnh dựa trên lưới 3.2.2.1 Tách vùng hình dạng của đối tượng Từ một ảnh ban đầu, chúng ta có thể thực hiện tách vùng hình dạng bằng cách sử dụng các phương pháp tách biên (nổi biên) hoặc biến đổi từ miền quan sát sang miền tần số. 3.2.2.2 Biể u diễn vùng hình dạng dựa trên lưới Đầu tiên ta vẽ đè mô ̣t lưới g ồm các ô có cùng kích thước lên vùng hình dạng. Quy ước rằng: - Số 1 tương ứng với ô có it́ nhấ t 15% số điể m ảnh của vùng hình dạng phủ lên ô lưới. - Số 0 ứng với mỗi ô còn la ̣i. Đọc l ần lượt các số trong lưới theo thứ tự từ trái sang phải , từ trên xuố ng dưới để được daỹ bit́ đa ̣i diê ̣n cho vùng hiǹ h da ̣ng. Ví dụ, 11100000 11111000 01111110 01111111. Hình 3.2: Tạo chuỗi bít biểu diễn vùng hình dạng 3.2.2.3 Chuầ n hóa xoay Mục đích của chuẩn hóa độ xoay là đặt vùng hình d ạng theo mô ̣t hướng cố đinh ̣ duy nhấ t, bằ ng cách xoay vùng hình d ạng sao cho tru ̣c chiń h của nó song song với tru ̣c hoành Ox (hoă ̣c trục tung Oy tùy theo từng chương triǹ h ). Khi đó vẫn có hai khả năng xảy ra đố i với vi ̣ trí của vùng hình dạng. Hình 3.3: Hai hướng của cùng một vùng hình dạng 3.2.2.4 Chuẩn hóa co dãn Thố ng nhấ t đưa vùng hiǹ h da ̣ng về kić h thướ c đồ ng da ̣ng mà ở đó tru ̣c chiń h của nó có cùng độ dài không đổi là 192 điể m ảnh (pixel). 3.2.2.5 Chỉ mục vùng hình dạng Sau khi chuẩ n hóa xoay , chuẩn hóa co dañ và cho ̣n kić h thước ô lưới phủ , chúng ta chỉ cần lưu trữ một chuỗi bit́ biể u diễn duy nhấ t cho mỗi vùng hiǹ h da ̣ng trong cơ sở dữ liê ̣u , với giả đinh ̣ rằ ng mỗi vùng chỉ có một tru ̣c chiń h. 3.2.2.6 Độ đo tương tự Giả sử: R và R’ là các véctơ hàng của hai ảnh, C và C’ là các véctơ cột của hai ảnh. Ta thực hiện: - Tính toán độ đo tương tự. - Tính toán các véctơ hàng và cột của mọi vùng hình dạng trong ảnh truy vấn. - Tìm khác biệt hàng và cột giữa các vùng hình dạng trong hai ảnh. - Ri và Ci là bit thứ i của các véctơ ảnh thứ nhất - Ri’ và Ci’ là bit thứ i của các véctơ ảnh thứ hai - Nếu (Rd+Cd) < T (ngưỡng) thì hai ảnh tương tự. 3.2.2.6 Các phép toán khác Ngoài ra chúng ta cần quan tâm tới phép đối xứng theo trục ngang và đối xứng theo trục thẳng đứng. Hình 3.4: Phép đối xứng 3.2.2.7 Xử lý trường hợp vùng hình dạng có hơn một trục chính Với những vùng hiǹ h da ̣ng có nhiề u hơn m ột tru ̣c, ta cầ n phải tim ̀ chuỗi bit́ chỉ mu ̣c của vùng hình d ạng đó theo từng tru ̣c chiń h của nó . Khi đó viê ̣c so sánh để tìm kiếm ảnh sẽ đươ ̣c thực hiê ̣n tố n kém hơn bằ ng cách so sánh từng că ̣p chuỗi bit́ trong tấ t cả các chuỗi bit́ biể u diễn vùng hình da ̣ng trong CSDL với 4 chuỗi bít phát sinh cho vùng hình da ̣ng truy vấ n . 3.2.2.8 Quy trình tạochỉ mục và tra cứu ảnh dựa trên lưới Xử lý các trích chọn đặc trưng để t ạo chỉ mu ̣c cho các hình da ̣ng trong cơ sở dữ liê ̣u , bao gồ m các bước: - Xác định trục chính, trục phụ, đô ̣ lê ̣ch tâm. - Chuẩ n hóa co dañ và chuẩ n hóa xoay. - Xác định kích thước lưới phủ, kích thước ô lưới và cố định kích thước đó để phủ lên vùng hình dạng. - Xác định chuỗi bít chỉ mục. - Chuỗi bit́ duy nhấ t, đô ̣ dài tru ̣c phu ̣ ta ̣o thành chỉ mu ̣c cho vùng hiǹ h da ̣ng và đươ ̣c lưu trữ trong cơ sở dữ liê ̣u. Như vậy trong quá trình tra cứu gồm các bước: 1. Vùng hình dạng trong ảnh truy vấn được mô tả bởi chiều dài trục phụ và chuỗi bít nhị phân. 2. Thực hiện so sánh bốn chuỗi bít nhị phân với các chuỗi trong cơ sở dữ liệu để tìm kiếm. 3. Khoảng cách giữa vùng hình dạng truy vấn với một vùng hình dạng trong cơ sở dữ liệu được tính toán bởi số lượng các vị trí bít bị sai khác. 4. Các vùng hình dạng tương tự được hiển thị hoặc lấy thứ tự tăng dần các khoảng cách. 3.3 Tra cứu ảnh dựa vào chỉ mục kết hợp màu sắc và hình dạng 3.3.1 Các đặc trưng màu sắc và hình dạng 3.3.1.1 Phương pháp lập chỉ mục màu sắc Không gian phân loại màu Toàn bộ không gian màu RGB được mô tả bằng cách sử dụng một tập con các màu như trong hình 3.5. Hình 3.5: Bảng tra cứu màu Kết hợp màu sắc và vùng lựa chọn Sử dụng giá trị màu tại điểm ảnh p và giá trị trong bảng màu tương ứng C, khoảng cách màu Cd được tính toán bằng cách sử dụng công thức tính khoảng cách Euclidean: 2 2 2 (3.1) Cd  MINi25 1 ( pr  Ci )  ( p g  Ci )  ( pb  Ci ) R G B Các bước thực hiện phân đoạn và dò biên: 1. Đọc ảnh và tạo một ma trận ảnh. 2. For mỗi điểm ảnh trong ảnh do D  (( I r  Cr ) 2  ( I g  Cg ) 2  ( I b  Cb ) 2 (3.2) - Gán các thành phần RGB trong bảng tra cứu màu cho một điểm ảnh có khoảng cách D nhỏ nhất. 3. Xác định sự xuất hiện đầu tiên của một điểm ảnh có giá trị RGB tương tự như bảng tần suất. 4. Gán vị trí điểm ảnh theo chiều ngang và chiều dọc. 5. Dựa vào iseed, jseed để đánh dấu toàn bộ vùng sử dụng thuật toán phát hiện biên gián tiếp (8 lân cận). 6. Kết hợp các (x,y) tạo thành biên của vùng. 7. Xác định kích thước r(R) của hình chữ nhật bao quanh: r ( R)  x1  x2 * y1  y 2 (3.3) Im age _ size 8. Lặp lại từ bước 3 đến bước 7 cho đến khi tìm được 3 vùng màu trội. Hình 3.6: Minh họa phân vùng màu. Hình 3.7: Ảnh đã tìm được biên. Tìm vị trí vùng màu trội Không gian ảnh được chia thành 9 khu vực nhỏ. Vị trí tương đối của vùng được xác định. Hình 3.8: Bản đồ khu vực Hình 3.9: Minh họa tìm khu vực. 3.3.1.2 Biểu diễn hình dạng Sau khi có được các vùng màu trội, ta có thể coi đó như là các vùng hình dạng cần tìm kiếm. 3.3.2 Quá trình lập chỉ mục và truy vấn 3.3.2.1 Chỉ mục màu sắc Cấu trúc chỉ mục chỉ mục đa chiều đa mức dựa trên việc phân đoạn và cấu trúc cây Rtree được sử dụng để lưu trữ hình ảnh. Cấu trúc này sử dụng kĩ thuật cắt tỉa để tăng tốc độ tìm kiếm. hình 3.10 mô tả cấu trúc hai mức đầy đủ như sau: Hình 3.10: Cấu trúc chỉ mục. Một chỉ số duy nhất được hình thành dựa trên 25 màu và được tính toán như sau: n (3.6) Index  i 1 Ci * 25 n1 Khi đó, chỉ số được đưa ra bởi công thức: Index  C1 * 25 2  C2 * 251  C3 * 250 (3.7) Hình 3.11: Ví dụ về bảng băm. 3.3.2.2 Chỉ mục hình dạng Với mỗi vùng màu được tìm thấy ở trên, ta thực hiện tính toán để có được chỉ mục cho vùng hình dạng gồm: Chuỗi bít và độ dài trục phụ. 3.3.2.3 Truy vấn Quy trình truy vấn được thực hiện qua các bước: 1. Ảnh truy vấn được xử lý để có được danh sách các ảnh phù hợp với đặc trưng màu sắc. 2. Với mỗi vùng màu trong ảnh truy vấn ta biểu diễn vùng hình dạng. Cần lưu lại chỉ mục của 4 ảnh tương ứng với vùng hình dạng khi thực hiện quay 180 độ và lật theo chiều ngang, lật theo chiều dọc. 3. So sánh chỉ mục vùng của ảnh truy vấn với danh sách các ảnh nhận được dựa vào màu sắc. 4. Chỉ các vùng có độ lệch tâm thỏa mãn ngưỡng T nào đó mới được so sánh độ tương tự hình dạng. 5. Các ảnh phù hợp được xếp thứ tự phụ thuộc vào độ khác biệt của tổng độ khác biệt trong các véc tơ hàng và cột giữa hình ảnh truy vấn và hình ảnh tương thích tìm được. 3.3.2.4 Độ đo tương tự Độ đo tương tự được tính toán như mục 3.2.2.6 của luận văn này. 3.4 Kết luận Tra cứu ảnh dựa trên lưới là một cách tiếp cận mới dựa trên hình dạng. Với ảnh đưa vào, chúng ta thực hiện trích chọn đặc trưng cho ảnh để được xâu bít nhị phân làm chỉ mục cho việc tra cứu. Tra cứu ảnh dựa trên lưới có thể kết hợp với đặc trưng màu sắc nhằm tăng hiệu quả tra cứu. Thực chất là tra cứu dựa trên chỉ mục kết hợp giữa màu sắc và hình dạng. Chƣơng 4: THIẾT KẾ VÀ CÀI ĐẶT CHƢƠNG TRÌNH MÔ PHỎNG TRA CỨU ẢNH DỰA TRÊN LƢỚI 4.1 Phát biểu bài toán Bài toán: Cho cơ sở dữ liệu ảnh, tìm kiếm ảnh tương tự với ảnh truy vấn về màu sắc và hình dạng. Giải quyết: - Trích chọn đặc trưng ảnh trong cơ sở dữ liệu lưu vào tệp đặc trưng. Tệp đặc trưng gồm các đặc trưng: chỉ số màu sắc, chuỗi bít nhị phân, chiều cao trục phụ (độ cao của ảnh), đường dẫn. - Trích chọn ảnh truy vấn bao gồm chỉ số màu sắc, chuỗi bít nhị phân và thực hiện so sánh với các đặc trưng được lưu trong tệp đặc trưng tìm ra ảnh có độ tương tự gần với ảnh truy vấn thỏa mãn một ngưỡng (T) cho trước nào đó. 4.2 Cài đặt sử dụng phƣơng pháp tra cứu ảnh dựa trên lƣới 4.2.1 Chuyển đổi ảnh về ảnh đen trắng Kiểm tra giá trị màu tại mỗi điểm ảnh nếu nhỏ hơn 128 thì đặt lại giá trị màu là 0, ngược lại đặt giá trị màu là 255. 4.2.2 Tìm hình chữ nhật cơ sở Lần lượt chiếu vùng hình dạng lên trục chính X và trục phụ Y để tìm giá trị Xmin, Xmax, Ymin, Ymax. 4.2.3 Chuẩn hóa vùng hình dạng Việc chuẩn hóa vùng hình dạng được thực hiện ở việc co dãn và xoay đối tượng. 4.2.3.1 Co dãn đối tượng Xét từng điểm ảnh rồi thực hiện làm tròn sau khi nhân tọa độ điểm ảnh với một hệ số nào đó sao cho kích thước của ảnh mới đúng bằng hình chữ nhật bao quanh đối tượng. 4.2.3.2 Tìm trục chính cho vùng hình dạng Trục chính của ảnh được xác định: đường nối giữa 2 điểm ảnh xa nhất (có độ dài lớn nhất). Với từng cặp điểm bất kỳ trong ảnh ta tính độ dài giữa chúng để tìm ra độ dài lớn nhất. Đường nối giữa hai cặp điểm có độ dài lớn nhất đó chính là trục chính cần tìm. 4.2.3.3 Xoay vùng hình dạng Thực hiện xoay vùng hình dạng theo góc quay nhất định. Góc quay được xác định thông qua công thức hệ thức lượng trong tam giác vuông. Để đảm bảo xoay hình theo hướng chính xác ta cần chú ý đến các trường hợp cụ thể. 4.2.4 Phủ lưới vùng hình dạng Ta thực hiện phủ lưới bằng cách chia tọa độ các ô trong ảnh, mặc định các ô lưới có kích thước 12 × 12. Dựa trên các ô lưới này, ta tính toán và tìm các ô có chứa ảnh theo tỷ lệ: thì ô lưới đó sẽ nhận giá trị 1, ngược lại là 0 (coi như không có ảnh trong ô lưới đó). Hình 4.1: Phủ lưới ảnh và tô màu đối tượng 4.2.5 Tính độ tương tự Với hai chuỗi bít nhị phân bất kỳ, ta kiểm tra nếu độ dài khác nhau không quá ngưỡng T cho phép thì ta sử dụng công thức tính khoảng cách Hamminh để tìm sự sai khác giữa các bít có trong dãy bít. 4.3 Giao diện chƣơng trình Chương trình được thiết kế có hai chức năng: Tra cứu dựa trên hình dạng, tra cứu kết hợp màu sắc và hình dạng. Hình 4.2: Tra cứu dựa trên hình dạng. Hình 4.3: Tra cứu kết hợp màu sắc và hình dạng. KẾT LUẬN Luận văn đã trình bày một cách tổng quan về tra cứu ảnh và một số phương pháp trích chọn đặc trưng hình ảnh, đồng thời tìm hiểu và nghiên cứu phương pháp tra cứu ảnh dựa trên lưới. Giới thiệu một số phương pháp trích chọn đặc trưng của ảnh trong tra cứu ảnh theo nội dung như: Trích chọn theo màu sắc, hình dạng, ... Sau đó đi vào nghiên cứu kỹ thuật tra cứu ảnh dựa trên lưới có sử dụng đặc trưng hình dạng, đồn thời kết hợp đặc trưng màu sắc với đặc trưng hình dạng. Việc nghiên cứu cài đặt phương pháp tra cứu ảnh dựa trên lưới là một bước đệm cho phép tra cứu ảnh kết hợp với các đặc trưng màu sắc để cho kết quả tra cứu tốt hơn nữa. Luận văn “Tra cứu ảnh dựa trên lưới và ứng dụng” đã đạt được những kết quả: 1. Nghiên cứu tổng quan về tra cứu ảnh, một số phương pháp trích chọn đặc trưng hình ảnh. 2. Nghiên cứu phương pháp tra cứu ảnh dựa trên lưới và tìm hiểu phương pháp tra cứu kết hợp đặc trưng màu sắc và hình dạng. 3. Xây dựng ứng dụng mô phỏng phương pháp tra cứu ảnh dựa vào đặc trưng mức thấp của ảnh. Tuy nhiên chương trình mới chỉ áp dụng cho tra cứu các ảnh đơn giản chứ chưa tra cứu được các ảnh phức tạp trong thực tế. References Tiếng Việt [1]. PGS.TS Đă ̣ng Văn Đức (2005), Bài giảng điện tử Cơ sở dữ liệu đa phương tiện , trường Đa ̣i ho ̣c Công Nghê ̣, Đa ̣i ho ̣c Quố c Gia Hà Nô ̣i. [2]. TS. Đỗ Năng Toàn - TS. Phạm Việt Bình (2008), Giáo trình xử lý ảnh, Nhà xuất bản Khoa học và Kỹ thuật. Tiếng Anh [3]. Guojun Lu (1999) Multimedia Database Management Systems, Artech House, Inc. [4]. Prof. Dr. H.-J. Schek, Supervisors: M. Mlivoncic, Dr. R. Weber (2002), Region Based Image Similarity Search, Silvan Andreas Saxer. [5]. Cheng Chang, Liu Wenyin, Hongjiang Zhang (2001), Image retrieval base on region shape similarity, Microsoft Research China. [6]. Atul Sajjanhar and Guojun Lu, A Grid Based Shape Indexing and Retrieval Method, Gippsland Shool of Computing and Information Technology, Monash University, Churchill, Victoria – 3842, Australia. [7]. B.G. Prasad, S.K. Gupta, K.K Biswas, Color and Shape Index for Region – Based Image Retrieval, Department of Computer Science and Engineering, P.E.S College of Engineering, Mandya, 571402, INDIA. [8]. Fuhui Long, Hongjiang Zhang, David Dagan Feng (2002), Fundamentals of Contentbased Image Retrieval, in Multimedia Information Retrieval and Management Technological Fundamentals and Applications. [9]. Colin C. Venteres and Dr. Matthew Cooper, A Review of Content-Based Image Retrieval Systems. [10]. Dengsheng Zhang, Aylwin Wong, Maria Indrawan, Guojun Lu, Content-based Image Retrieval Using Gabor Texture Features. [11]. Eva M.van Rikxoort (2005), “Content-based Image Retrieval Utilizing Color, Texture, and Shape”, Master’s thesis in AI Radbound University Nijmegen The Netherlands. [12]. Low (1991), A introductory Computer Vision and Image Processin, McGraw-hill, 244p. ISBN 0077074033 [13]. Sebe N, Lew (2001), “Texture Features for Content-based Retrieval”: Principles of visual Information Retrieval.