1 LỜI CẢM ƠN Trong lời đầu tiên của báo cáo Đồ án Tốt Nghiệp “Tìm hiểu phƣơng pháp trích chọn dấu hiệu của ảnh dựa vào đặc trƣng hình dạng” này, em muốn gửi những lời cám ơn và biết ơn chân thành nhất của mình tới tất cả những ngƣời đã hỗ trợ, giúp đỡ em về kiến thức, và tinh thần trong quá trình thực hiện Đồ án. Trƣớc hết, em chân thành cám ơn Thầy Giáo. Ths. Ngô Trƣờng Giang, Giảng viên Khoa Công Nghệ Thông Tin, Trƣờng ĐHDL Hải Phòng, ngƣời đã trực tiếp hƣớng dẫn, nhận xét, giúp đỡ em trong suốt quá trình thực hiện Đồ án. Em chân thành cảm ơn các Thầy Cô trong Khoa Công Nghệ Thông Tin và toàn Thầy Cô trong Trƣờng Đại Học Dân Lập Hải Phòng đã giúp đỡ em trong suốt quá trình học tập. Em cũng xin bày tỏ lòng biết ơn đến gia đình và những ngƣời bạn đã luôn giúp đỡ động viên em rất nhiều trong quá trình học tập và làm Đồ án Tốt Nghiệp. Do thời gian thực hiện có hạn, kiến thức còn nhiều hạn chế nên Đồ án thực hiện chắc chắn không tránh khỏi những thiếu sót nhất định. Em rất mong nhận đƣợc ý kiến đóng góp của Thầy Cô giáo và các bạn để em có thêm kinh nghiệm và tiếp tục hoàn thiện bài báo cáo của mình. Em xin chân thành Cám ơn! Hải Phòng, tháng 11/2011 Sinh viên Phùng Thị Lệ _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 2 MỤC LỤC MỤC LỤC ............................................................................................................................. 2 MỞ ĐẦU ............................................................................................................................... 4 DANH MỤC HÌNH VẼ ........................................................................................................ 5 CHƢƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA TRÊN NỘI DUNG. .............. 6 1.1 Tra cứu thông tin trực quan................................................................... 6 1.2 Các thành phần chính của một hệ thống CBIR..................................... 7 1.3 Các chức năng cơ bản của hệ thống CBIR. .......................................... 8 1.4 Một số phƣơng pháp tra cứu ảnh dựa trên nội dung. ............................ 9 1.5 Một số hệ thống tra cứu ảnh dựa trên nội dung. ................................. 10 1.5.1 Hệ thống QBIC (Query By Image Content). .............................. 11 1.5.2 Hệ thống Photobook.................................................................... 11 1.5.3 Hệ thống VisualSEEK và WebSEEK. ........................................ 11 1.5.4 Hệ thống RetrievalWare.............................................................. 12 1.5.5 Hệ thống Imatch. ......................................................................... 12 CHƢƠNG 2: CÁC PHƢƠNG PHÁP BIỂU DIỄN HÌNH DẠNG. ............................... 13 2.1 Giới thiệu. ........................................................................................... 13 2.2 Kỹ thuật biểu diễn hình dạng dựa trên biên. ....................................... 14 2.2.1 Phƣơng pháp toàn cục. ................................................................ 14 2.2.2 Phƣơng pháp cấu trúc. ................................................................. 16 2.3 Kỹ thuật biểu diễn hình dạng dựa trên vùng. ...................................... 18 2.3.1 Phƣơng pháp toàn cục. ................................................................ 19 2.3.2 Phƣơng pháp cấu trúc. ................................................................. 20 CHƢƠNG 3: MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN DẤU HIỆU CỦA ẢNH DỰA VÀO ĐẶC TRƢNG HÌNH DẠNG. .......................................................................... 22 3.1 Giới thiệu. ........................................................................................... 22 3.2 Phƣơng pháp trích chọn đặc trƣng dựa trên đƣờng biên. ................... 22 3.2.1 Mã xích (chain code)................................................................... 22 3.2.2 Shape number. ............................................................................. 24 3.2.3 Đối sánh các shape number. ........................................................ 25 _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 3 3.3 Phƣơng pháp trích chọn đặc trƣng dựa trên vùng............................... 27 3.3.1 Đồ thị xƣơng. .............................................................................. 29 3.3.2 Đối sánh đồ thị xƣơng. ................................................................ 29 3.3.3 Nhận xét ...................................................................................... 36 CHƢƠNG 4: THỰC NGHIỆM. .................................................................................... 37 4.1 Môi trƣờng thử nghiệm. ...................................................................... 37 4.2 Một số kết quả thu đƣợc. .................................................................... 37 4.2.1 Giao diện chƣơng trình: .............................................................. 37 4.2.2 Kết quả trên một số đối tƣợng khác nhau. .................................. 38 4.2.3 Một số nhận xét về chƣơng trình. ............................................... 40 KẾT LUẬN.......................................................................................................................... 41 TÀI LIỆU THAM KHẢO ................................................................................................... 42 _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 4 MỞ ĐẦU Trong thực tế, bài toán tra cứu ảnh có rất nhiều ứng dụng quan trọng, ví dụ nhƣ so sánh mẫu vân tay, tìm kiếm ảnh tội phạm... đƣợc áp dụng trong ngành khoa học hình sự, cơ sở dữ liệu ảnh về địa lý, y học.... làm cho lĩnh vực nghiên cứu này phát triển nhanh trong công nghệ thông tin. Tuy nhiên khi số lƣợng ảnh đƣợc lƣu trữ trở nên rất lớn thì vấn đề là phải có những phƣơng pháp tổ chức cơ sở dữ liệu ảnh tốt cùng với những kỹ thuật tìm kiếm, tra cứu ảnh hiệu quả, có độ chính xác cao và có hiệu năng tốt. Việc tìm kiếm đƣợc một bức ảnh mong muốn trong hàng triệu bức ảnh là rất khó khăn, đòi hỏi phải có những phƣơng pháp hiệu quả và chính xác. Một trong những phƣơng pháp đƣợc nhiều ngƣời quan tâm nghiên cứu hiện nay là phƣơng pháp “Tra cứu ảnh dựa theo nội dung” (Content-Based Image Retrieval). Ý tƣởng phƣơng pháp này là trích chọn các đặc điểm dựa vào nội dung trực quan của ảnh nhƣ màu sắc, kết cấu, hình dạng và bố cục không gian của ảnh để làm cơ sở cho việc tra cứu, sắp xếp, tổ chức cơ sở dữ liệu ảnh. Tra cứu ảnh dựa trên hình dạng sử dụng các đặc trƣng hình dạng của các ảnh mục tiêu để tìm kiếm, nó là một khía cạnh rất quan trọng của tra cứu ảnh dựa trên nội dung. Một phần quan trọng của tra cứu ảnh dựa trên hình dạng là nghiên cứu trích chọn dấu hiệu đặc trƣng. Cho đến nay vẫn chƣa có, định nghĩa toán học chính xác, bao gồm cả hình học, thống kê, hình thái học đo lƣờng về hình dạng, do đó việc mô tả hình dạng là vấn đề hết sức phức tạp. Đề tài này sẽ tìm hiểu một số phƣơng pháp mô tả và trích chọn dấu hiệu của ảnh dựa vào đặc trƣng hình dạng ứng dụng trong tra cứu ảnh dựa trên nội dung. Đồ án bao gồm 4 chƣơng: Chƣơng 1: Trình bày tổng quan về tra cứu ảnh dựa trên nội dung và giới thiệu một số hệ thống tra cứu ảnh dựa trên nội dung. Chƣơng 2: Trình bày một số phƣơng pháp biểu diễn hình dạng và cách phân loại các phƣơng pháp biểu diễn hình dạng. Chƣơng 3: Tìm hiểu hai phƣơng pháp trích chọn dấu hiệu của ảnh dựa vào đặc trƣng hình dạng: Mã xích và xƣơng. Chƣơng 4: Trình bày thực nghiệm và một số kết quả đạt đƣợc. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 5 DANH MỤC HÌNH VẼ Hình 1.1: Các thông tin sử dụng để mô tả hình ảnh....................................................7 Hình 1.2: Mô hình hệ thống tra cứu ảnh dựa trên nội dung. .......................................9 Hình 2.1: Phân loại các kỹ thuật mô tả hình dạng. ...................................................14 Hình 2.2: Minh họa độ lệch tâm và tuần hoàn của hình dạng. .................................15 Hình 2.3: Minh họa phƣơng pháp bề mặt lồi: (a) Bề mặt lồi và các thiếu hụt lồi của nó; (b) Cây lõm biểu diễn bề mặt lồi. ............................................................... 20 Hình 2.4: Trục trung vị (xƣơng) của hình chữ nhật. .................................................20 Hình3.1: Các hƣớng của đoạn thẳng đơn vị: (a): 4 hƣớng, (b): 8 hƣớng. ................23 Hình 3.2: Biểu diễn của một chuỗi mã ( theo 4 hƣớng và 8 hƣớng) ......................... 23 Hình 3.3: Biểu diễn hình dạng sử dụng shape number. ............................................24 Hình 3.4: Các bƣớc tính toán shape number. ............................................................ 25 Hình 3.5: Minh họa tìm kiếm hình dạng tƣơng tự sử dụng shape number: (a) hình dạng; (b) cây tƣơng tự; (c) ma trận tƣơng tự. ...................................................26 Hình 3.6: Hình dạng (a) và (b) tƣơng tự nhau nhƣng đồ thị khác nhau. ...................28 Hình 3.7: Hình dạng (a) và ( b) khác nhau nhƣng có đồ thị xƣơng (c) giống nhau. .28 Hình 3.8: Minh họa đƣờng dẫn xƣơng: (a) xƣơng của hình con ngựa, (b) đƣờng dẫn ngắn nhất giữa các cặp node cuối. ....................................................................30 Hình 3.9: Sự tƣơng ứng giữa các node cuối của hai đồ thị xƣơng............................ 32 Hình 3.10: Minh họa xƣơng đƣợc cắt tỉa bởi DCE. ..................................................33 Hình 3.11: Sự tƣơng ứng giữa các yếu tố. ................................................................ 35 Hình 4.1: Giao diện của chƣơng trình. ......................................................................37 Hình 4.2: Kết quả thu đƣợc với hình con ngựa ......................................................... 38 Hình 4.3: Kết quả thu đƣợc với hình con ngựa kéo xe. ............................................38 Hình 4.4: Kết quả thu đƣợc với hình cá heo. ............................................................ 39 Hình 4.5: Kết quả thu đƣợc với hình chữ nhật. ......................................................... 39 _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 6 CHƢƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA TRÊN NỘI DUNG. 1.1 Tra cứu thông tin trực quan. Nội dung của một bức ảnh gồm nội dung trực quan và nội dung ngữ nghĩa. Nội dung trực quan gồm có nội dung tổng quan và nội dung đặc tả. Nội dung ngữ nghĩa đƣợc phát hiện thông qua chú thích hoặc suy luận từ nội dung trực quan. Có hai phƣơng pháp chung để giải bài toán tra cứu thông tin trực quan dựa trên những thông tin trực quan: Phƣơng pháp dựa trên những thuộc tính (tổng quan) và phƣơng pháp dựa trên những đặc điểm (đặc tả). Phƣơng pháp dựa trên thuộc tính dựa vào tra cứu thông tin kết cấu truyền thống và những phƣơng pháp quản lý cơ sở dữ liệu dựa trên sự can thiệp của con ngƣời để trích chọn metadata về đối tƣợng trực quan và sự chú thích kết cấu. Nhƣng việc phân tích kết cấu mất nhiều thời gian và tốn nhiều công sức. Hơn nữa lời chú thích phụ thuộc rất nhiều vào cảm nhận chủ quan của con ngƣời, mà sự cảm nhận chủ quan và sự giải thích mơ hồ chính là nguyên nhân của sự ghép đôi không cân xứng trong quá trình xử lý. Vấn đề truy cập ảnh và video dựa trên từ khóa đã thúc đẩy quan tâm đến sự phát triển những giải pháp dựa trên đặc điểm. Đó là thay sự giải thích thủ công bằng những từ khoá dựa trên văn bản, ảnh có thể đƣợc trích chọn ra bằng cách sử dụng một số đặc điểm thị giác nhƣ là màu sắc, kết cấu, hình dạng và đƣợc đánh chỉ số dựa trên những đặc điểm trực quan này. Thuật ngữ tra cứu ảnh dựa trên nội dung (Content Based Image Retrieval - CBIR) đã đƣợc Kato sử dụng đầu tiên để mô tả những thí nghiệm của ông về lĩnh vực tra cứu tự động những hình ảnh từ một cơ sở dữ liệu dựa trên đặc điểm hình dạng và màu sắc. Từ đó nó đƣợc sử dụng rộng rãi để mô tả quá trình tra cứu những hình ảnh mong muốn từ một tập hợp lớn hình ảnh dựa trên những đặc điểm về màu sắc, kết cấu và hình dạng và những đặc điểm đó đƣợc trích rút một cách tự động từ chính các hình ảnh. Những đặc điểm sử dụng cho việc tra cứu có thể là những đặc điểm nguyên thủy hoặc là những đặc điểm ngữ nghĩa, tuy nhiên quá trình trích chọn chủ yếu phải đƣợc tự động [5]. Tra cứu ảnh dựa trên việc gán từ khóa (manually assigned keywords) không phải là tra cứu ảnh dựa trên nội dung bởi vì thuật ngữ đƣợc hiểu một cách chung chung ngay cả khi những từ khóa mô tả nội dung ảnh. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 7 Hình ảnh Văn bản Nội dung Kết hợp Hình Từ khóa Thể loại Màu sắc Kết cấu các đặc dạng trƣng Hình 1.1: Các thông tin sử dụng để mô tả hình ảnh. 1.2 Các thành phần chính của một hệ thống CBIR. Hiện nay, trọng tâm chính của CBIR là nghiên cứu chủ yếu trên 3 chủ đề chính: Trích chọn đặc trƣng, đánh chỉ số hiệu quả, giao diện ngƣời dùng. Trích chọn đặc trưng: Các đặc trƣng của hình ảnh bao gồm các đặc trƣng nguyên thủy và các đặc trƣng ngữ nghĩa /đặc trƣng logic. Đặc trƣng nguyên thủy nhƣ màu sắc, hình dạng, kết cấu và các mối quan hệ không gian đƣợc định lƣợng trong tự nhiên, chúng có thể đƣợc trích xuất tự động hoặc bán tự động. Đặc trƣng logic cung cấp mô tả trừu tƣợng của dữ liệu hình ảnh ở các cấp độ khác nhau.Thông thƣờng, các đặc trƣng logic đƣợc chiết xuất bằng tay hoặc bán tự động. Một hoặc nhiều đặc trƣng có thể đƣợc sử dụng trong một ứng dụng cụ thể. Ví dụ, trong một hệ thống thông tin vệ tinh, các đặc trƣng kết cấu là quan trọng, trong khi hình dạng và màu sắc là các đặc trƣng quan trọng hơn trong các hệ thống đăng ký nhãn hiệu hàng hoá.Một hoặc nhiềucác đặc trƣng đã đƣợc chiết xuất, tra cứu trở thành một nhiệm vụ đo độ giống nhau giữa các đặc trƣng hình ảnh. Lập chỉ số hiệu quả: Để tạo điều kiện truy vấn hiệu quả và xử lý tìm kiếm, các chỉ số hình ảnh cần thiết đƣợc tổ chức thành các cấu trúc dữ liệu hiệu quả. Đặc trƣng hình ảnh là sự hình dung miêu tả, chúng không thể nhúng chỉ thị và chúng có thể có các thuộc tính liên quan đến nhau. Vì vậy, cấu trúc dữ liệu linh hoạt nên đƣợc _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 8 sử dụng để tạo điều kiện thuận lợi cho lƣu trữ và truy xuất trong hệ thống phục hồi hình ảnh. Các cấu trúc nhƣ k-d-tree, R-tree family, R *- tree, quad-tree, và grid file (tập lƣới) thƣờng đƣợc sử dụng. Các cấu trúc trên có các ƣu điểm và nhƣợc điểm riêng vì vậy một số cấu trúc dữ liệu chỉ có thể sử dụng trong những lĩnh vực nhất định nhƣng một số cấu trúc dữ liệu có đƣợc sử dụng đồng thời trong nhiều lĩnh vực khác nhau. Giao diện người dùng: Trong các hệ thống thông tin trực quan, tƣơng tác ngƣời dùng đóng một vai trò quan trọng trong hầu nhƣ tất cả các chức năng. Giao diện ngƣời dùng bao gồm một bộ xử lý truy vấn và trình duyệt để cung cấp các công cụ đồ họa tƣơng tác, cơ chế truy vấn và truy cập cơ sở dữ liệu, theo thứ tự định sẵn. Các cơ chế truy vấn thông thƣờng đƣợc cung cấp bởi giao diện ngƣời dùng là: truy vấn bằng từ khóa, truy vấn bằng cách phác thảo, truy vấn bằng các ví dụ, duyệt theo thể loại, chọn lọc đặc trƣng và trọng số thu hồi, tinh chỉnh và phù hợp thông tin phản hồi. Ba tác vụ trên là ba thành phần chính của một hệ thống CBIR. Trong số ba tác vụ trên,trích chọn đặc trƣng (bao gồm cả đo độ giống nhau) là nhiệm vụ quan trọng và khó khăn nhất. Phần lớn các nghiên cứu CBIR đi vào nhiệm vụ đầy thách thức này. Nghiên cứu này tập trung vào khai thác các đặc trƣng hình dạng. 1.3 Các chức năng cơ bản của hệ thống CBIR. Một hệ thống tra cứu ảnh dựa trên nội dung không chỉ xử lý các nguồn thông tin trong những định dạng khác nhau (ví dụ nhƣ văn bản, ảnh, video) mà còn xử lý các nhu cầu của ngƣời sử dụng. Về cơ bản, hệ thống phân tích các nội dung của nguồn thông tin cũng nhƣ truy vấn của ngƣời sử dụng, rồi sau đó đối sánh chúng để tìm ra những tiêu chí có liên quan [5]. Những chức năng chính của một hệ thống bao gồm các nội dung sau: Phân tích nội dung của nguồn thông tin và biểu diễn nội dung của các nguồn thông tin sao cho phân tích phù hợp với sự so sánh các truy vấn của ngƣời sử dụng (không gian của thông tin nguồn đƣợc chuyển đổi thành không gian đặc điểm với mục đích đối sánh nhanh trong bƣớc tiếp theo). Bƣớc này thƣờng là mất nhiều thời gian cho việc xử lý tuần tự các thông tin nguồn (hình ảnh) trong cơ sở dữ liệu. Tuy nhiên, bƣớc này chỉ phải làm một lần và có thể làm độc lập. Phân tích các truy vấn của ngƣời dùng và biểu diễn chúng thành các dạng phù hợp với việc đối sánh với cơ sở sữ liệu nguồn. Nhiệm vụ của bƣớc này giống với bƣớc trƣớc nhƣng chỉ đƣợc áp dụng với những ảnh truy vấn. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 9 Xác định chiến lƣợc để đối sánh tìm kiếm truy vấn với thông tin đƣợc lƣu trữ trong cơ sở dữ liệu. Bƣớc này có thể thực hiện trực tuyến và thực hiện rất nhanh. Công nghệ đánh chỉ số hiện đại có thể đƣợc sử dụng để tổ chức lại không gian đặc điểm để tăng tốc độ xử lý đối sánh. Thực hiện các điều chỉnh cần thiết trong hệ thống (thƣờng là bằng cách đối chiếu các tham số trong công nghệ đối sánh) dựa trên phản hồi từ ngƣời sử dụng hoặc những hình ảnh đƣợc tra cứu. Từ sự trình bày ở trên ta thấy rằng một mặt hệ thống tra cứu ảnh dựa trên nội dung có các nguồn thông tin trực quan ở các dạng khác nhau, bên cạnh đó lại có cả các yêu cầu của ngƣời sử dụng. Mô hình một hệ thống tra cứu ảnh dựa trên nội dung [2] nhƣ hình 1.2: Hình 1.2: Mô hình hệ thống tra cứu ảnh dựa trên nội dung. 1.4 Một số phƣơng pháp tra cứu ảnh dựa trên nội dung. Một số phƣơng pháp của tra cứu ảnh dựa trên nội dung đƣợc đƣa ra từ lĩnh vực xử lý ảnh và đồ họa máy tính. Các phƣơng pháp này chủ yếu thông qua việc nhấn mạnh vào tra cứu ảnh với những đặc điểm mong muốn từ một tập hình ảnh lớn. Việc lựa chọn các đặc trƣng và độ đo thích hợp sẽ giúp tăng tốc độ thực hiện và _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 10 mức độ chính xác của hệ thống tra cứu ảnh. Vì vậy phải lựa chọn đƣợc một tập các đặc trƣng tốt nhất cho đầu vào của các hệ thống tìm kiếm ảnh. Nếu số lƣợng các đặc trƣng quá nhiều sẽ che khuất các tín hiệu, mặt khác, nếu số lƣợng các đặc trƣng quá ít sẽ khó nhận dạng đƣợc ảnh [1]. Sau đây, một số phƣơng pháp tra cứu ảnh dựa trên nội dung đƣợc giới thiệu: Tra cứu ảnh dựa trên màu sắc: màu sắc là một đặc trƣng nổi bật và đƣợc sử dụng phổ biến nhất trong tìm kiếm ảnh theo nội dung. Mỗi một điểm ảnh (thông tin màu sắc) có thể đƣợc biểu diễn nhƣ một điểm trong không gian màu sắc ba chiều. Các không gian màu thƣờng dùng là: RGB, Munsell, CIE, HSV. Tìm kiếm ảnh theo màu sắc tiến hành tính toán biểu đồ màu cho mỗi ảnh để xác định tỉ trọng các điểm ảnh chứa các giá trị đặc biệt (màu sắc). Các nghiên cứu gần đây đang tập trung vào phân vùng ảnh theo các màu khác nhau và tìm mối quan hệ giữa các vùng này. Tra cứu ảnh dựa trên kết cấu: Trích xuất nội dung ảnh theo kết cấu nhằm tìm ra mô hình trực quan của ảnh và cách thức chúng đƣợc xác định trong không gian. Kết cấu cung cấp thông tin về sự sắp xếp về mặt không gian của màu sắc và cƣờng độ của ảnh. Kết cấu đƣợc biểu diễn bởi các texel mà sau đó đƣợc đặt vào một số các tập phụ thuộc vào số kết cấu đƣợc phát hiện trong ảnh. Các tập này không chỉ xác định các kết cấu mà còn chỉ rõ vị trí các kết cấu trong ảnh. Việc xác định các kết cấu đặc biệt trong ảnh đạt đƣợc chủ yếu bằng cách mô hình các kết cấu nhƣ những biến thế xám hai chiều. Tra cứu ảnh dựa trên hình dạng: hình dạng của một ảnh hay một vùng là một đặc trƣng quan trọng trong việc xác định và phân biệt ảnh trong nhận dạng mẫu. Mục tiêu chính của biểu diễn hình dạng trong nhận dạng mẫu là đo thuộc tính hình học của một đối tƣợng đƣợc dùng trong phân lớp, so sánh và nhận dạng đối tƣợng. Hình dạng là đặc trƣng hình ảnh quan trọng và nó là một trong những đặc trƣng nguyên thủy để mô tả nội dung hình ảnh. Tuy nhiên, mô tả nội dung hình dạng là một nhiệm vụ rất khó khăn. Bởi vì, rất khó để định nghĩa các nhận thức về đặc trƣng hình dạng và đo lƣờng sự giống nhau giữa các hình dạng. 1.5 Một số hệ thống tra cứu ảnh dựa trên nội dung. Những năm gần đây, có nhiều hệ thống tra cứu ảnh đã đƣợc xây dựng và phát triển rất nhanh. Một số hệ thống của CBIR đƣợc biết tới: _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 11 1.5.1 Hệ thống QBIC (Query By Image Content). Hệ thống QBIC của hãng IBM là một hệ thống tra cứu ảnh thƣơng mại đầu tiên và nổi tiếng nhất trong số các hệ thống tra cứu ảnh dựa trên nội dung. Nó 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. QBIC cung cấp một số phƣơng pháp: Simple, Multi-feature, và Multi-pass. Trong phƣơng pháp truy vấn Simple chỉ sử dụng một đặc điểm. Truy vấn Multi-feature bao gồm nhiều hơn một đặc điểm và mọi đặc điểm đều có trọng số nhƣ nhau trong suốt quá trình tìm kiếm. Truy vấn Multi-pass sử dụng đầu ra của các truy vấn trƣớc làm cơ sở cho bƣớc tiếp theo. Ngƣời sử dụng có thể vẽ ra và chỉ định màu, kết cấu mẫu của hình ảnh yêu cầu. Trong hệ thống QBIC màu tƣơng tự đƣợc tính toán bằng thƣớc đo bình phƣơng sử dụng biểu đồ màu k phần tử (k-element) và màu trung bình đƣợc sử dụng nhƣ là bộ lọc để cải tiến hiệu quả của truy vấn. Bản demo của QBIC tại địa chỉ wwwqbic.almaden.ibm.com. 1.5.2 Hệ thống Photobook. Hệ thống này đƣợc phát triển ở Massachusetts Institute of Technology 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. Hệ thống này cung cấp một tập các thuật toán đối sánh gồm: Euclidean, mahalanobis, vector space angle, histogram, Fourier peak, và wavelet tree distance nhƣ là những đơn vị đo khoảng cách. Trong hầu hết các phiên bản đã có thể định nghĩa những thuật toán đối sánh của họ. Hệ thống nhƣ là một công cụ bán tự động và có thể sinh ra một mẫu truy vấn dựa vào những ảnh mãu đƣợc cung cấp bởi ngƣời sử dụng. Điều này cho phép ngƣời sử dụng trực tiếp đƣa những yêu cầu truy vấn của họ với những lĩnh vực khác nhau, và mỗi lĩnh vực họ có thể thu đƣợc những mẫu truy vấn tối ƣu. 1.5.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. Nó cho phép ngƣời sử dụng tra cứu ảnh dựa trên màu sắc, không gian miền và đặc điểm kết cấu. Tập màu và chuyển đổi wavelet dựa trên kết cấu đƣợc sử dụng để thực hiện những đặc điểm này. Thêm vào đó VisualSEEK còn cho phép ngƣời sử dụng tạo truy vấn bằng việc chỉ định vùng màu và những không gian vị trí của chúng. WebSEEK là một catalog ảnh và là công cụ tìm kiếm cho web. Hệ thống này cung cấp mẫu cho danh sách ảnh và video trên trang web sử dụng kết hợp xử lý dựa trên text và phân tích dựa trên nội dung. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 12 1.5.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. Ngƣời sử dụng có thể điều chỉnh tỷ trọng của những đặc điểm này trong suốt quá trình tìm kiếm. 1.5.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. Nó cung cấp một số phƣơng pháp để tra cứu ảnh tƣơng tự: Màu tƣơng tự, màu và hình dạng (Quick), màu và hình dạng (Fuzzy) và sự phân bố màu. Màu tƣơng tự truy vấn những ảnh tƣơng tự với ảnh mẫu dựa trên sự phân bố màu toàn cục. Màu và hình dạng (Quick) tìm hình ảnh tƣơng tự bởi việc kết hợp cả hình dạng, kết cấu và màu. Màu và hình dạng (Fuzzy) thực hiện thêm những bƣớc xác định đối tƣợng trong ảnh mẫu. Phân bố màu cho phép ngƣời sử dụng vẽ ra sự phân bố màu hoặc xác định tỷ lệ phần trăm của một màu trong hình ảnh mong muốn. Imatch cũng cung cấp những đặc điểm khác nội dung để xác định ảnh: ảnh nhị phân, ảnh co kích thƣớc, lƣu trữ trong những định dạng khác và những ảnh có tên tƣơng tự. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 13 CHƢƠNG 2: CÁC PHƢƠNG PHÁP BIỂU DIỄN HÌNH DẠNG. 2.1 Giới thiệu. Nghiên cứu về hình dạng đã hoạt động trong hơn 30 năm. Trƣớc đây, nghiên cứu hình dạng đƣợc thúc đẩy chủ yếu bởi sự nhận dạng đối tƣợng, các kỹ thuật mô tả và biểu diễn hình dạng này chủ yếu dựa vào các ứng dụng cụ thể. Trong đó, sự hiệu quả và chính xác là mối quan tâm chính của những kỹ thuật này. Khi các ứng dụng đa phƣơng tiện mới nổi lên, vấn đề quan trọng đặt ra là tra cứu trực tuyến. Trong sự phát triển của MPEG-7, sáu yêu cầu chính đƣợc thiết lập để đánh giá một mô tả hình dạng, đó là: trích chọn hiệu quả và chính xác, đặc trƣng cô đọng, ứng dụng rộng rãi, độ phức tạp thấp, hiệu suất cao và phân cấp mô tả tốt [5]. Việc phân loại các phƣơng pháp biểu diễn hình dạng phổ biến nhất là dựa trên việc sử dụng các điểm biên hình dạng và điểm vùng. Biểu diễn hình dạng cũng có thể đƣợc phân biệt giữa miền không gian và miền đặc trƣng. Phƣơng pháp trong miền không gian so sánh các hình dạng dựa trên điểm (hoặc điểm đặc trƣng) cơ sở, còn phƣơng pháp miền đặc trƣng so sánh các hình dạng dựa trên đặc trƣng (vector) cơ sở. Một cách phân loại các kỹ thuật biểu diễn hình dạng khác là dựa trên cơ sở bảo quản thông tin. Phƣơng pháp cho phép xây dựng lại chính xác một hình dạng từ mô tả của nó đƣợc gọi là lƣu trữ thông tin (Information preserving - IP), còn phƣơng pháp chỉ có khả năng xây dựng lại một phần hoặc mô tả không rõ ràng đƣợc gọi là sự không lƣu trữ thông tin (Non Information preserving - NIP). Các phƣơng pháp biểu diễn hình dạng đƣợc phân loại theo các cấp bậc, đầu tiên phƣơng pháp phân loại dựa trên đƣờng biên và phƣơng pháp phân loại dựa trên vùng căn cứ vào đặc trƣng hình dạng đƣợc trích chọn từ đƣờng biên hay toàn bộ các phân vùng hình dạng. Trong mỗi lớp, các phƣơng pháp khác nhau đƣợc tiếp tục phân biệt thành cấu trúc và toàn cục dựa vào việc hình dạng đƣợc biểu diễn theo toàn bộ hay theo các thành phần con [5]. Sau đó, tiếp tục phân ra các phƣơng pháp cụ thể nhƣ mô tả trong sơ đồ (2.1). _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 14 Hình dạng Dựa trên biên Dựa trên vùng Cấu trúc Toàn cục Toàn cục Cấu trúc Mã chuỗi. Mô tả đơn Bất biến Bề mặt lồi. Phân tích đa giản. momen hình Trục trung vị. giác. Dấu hiệu hình học Phƣơng pháp dạng. Bất biến tỉ lệ. Momen biên. momen đại số Phƣơng pháp lƣới Hình 2.1: Phân loại các kỹ thuật mô tả hình dạng. 2.2 Kỹ thuật biểu diễn hình dạng dựa trên biên. Kỹ thuật mô tả hình dạng dựa trên biên chỉ khai thác thông tin trên biên. Có hai loại phƣơng pháp tiếp cận rất khác nhau cho kỹ thuật dựa trên biên: phƣơng pháp tiếp cận liên tục (toàn cục) và phƣơng pháp tiếp cận rời rạc (cấu trúc). Phƣơng pháp tiếp cận liên tục không phân chia hình dạng thành các phần và một vector đặc trƣng có gốc từ đƣờng biên đƣợc sử dụng để mô tả hình dạng. Thƣớc đo sự giống nhau về hình dạng là dựa trên sự đối sánh các điểm đặc biệt hoặc dựa trên đặc trƣng. Phƣơng pháp tiếp cận rời rạc chia đƣờng biên thành các phân đoạn bằng cách sử dụng một tiêu chuẩn cụ thể. Biểu diễn cuối cùng thƣờng là một chuỗi hoặc một đồ thị (hoặc cây), các biện pháp tƣơng tự đƣợc thực hiện bằng cách kết hợp chuỗi hoặc đồ thị một cách phù hợp. 2.2.1 Phương pháp toàn cục. Kỹ thuật mô tả hình dạng dựa trên đƣờng biên toàn cục thƣờng tính toán vecto đặc trƣng từ thông tin đƣờng biên. Khi đối sánh giữa các hình dạng sử dụng _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 15 một khoảng cách theo quy tắc, chẳng hạn nhƣ khoảng cách Euclide hoặc khoảng cách City block. Phƣơng pháp mô tả biễu diễn hình dạng bằng đƣờng biên toàn cục là mô tả biểu diễn toàn bộ hình dạng có hệ thống cho một mô tả mẫu. Đối sánh giữa các hình dạng có thể thực hiện đƣợc trong miền không gian hoặc trong miền đặc trƣng. Đối với một mô tả hình dạng thì luôn cần sự cân bằng giữa độ chính xác và hiệu quả. Một mặt, hình dạng cần đƣợc mô tả chính xác, mặt khác, hình dạng mô tả nên càng nhỏ gọn càng tốt để đơn giản hóa quá trình đánh chỉ số và tra cứu. Bởi vậy chúng ta cần phải trích chọn đặc trƣng một cách hiệu quả. Mô tả hình dạng toàn cục đơn giản nhỏ gọn, tuy nhiên mô tả hình dạng không chính xác, nó chỉ có thể đƣợc kết hợp với mô tả hình dạng khác để tạo ra các mô tả hình dạng chính xác. 2.2.1.1 Mô tả hình dạng đơn giản. Mô tả toàn cục đơn giản có thể đƣợc biểu diễn thông qua: vùng, tuần hoàn (chu vi2/diện tích), độ lệch tâm (độ dài trục chính/độ dài trục nhỏ), hƣớng trục chính và khả năng uốn. Những mô tả đơn giản toàn cục thƣờng chỉ có thể phân biệt hình dạng với khác biệt lớn, do đó sẽ thƣờng sử dụng các bộ lọc để loại bỏ các truy cập sai hoặc kết hợp với mô tả hình dạng khác để phân biệt hình dạng. Phƣơng pháp không phù hợp với mô tả hình dạng độc lập. Ví dụ, lệch tâm của hình dạng trong hình 2.2(a) là gần tới 1 (a=b), nó không chính xác để mô tả hình dạng. Trong trƣờng hợp này, tuần hoàn là một mô tả tốt hơn. Hai hình dạng trong hình 2.2(b) và 2.2(c) có cùng tuần hoàn (a=2b), tuy nhiên, chúng là những hình dạng rất khác nhau.Trong trƣờng hợp này, độ lệch tâm là mô tả tốt hơn. (a) (b) (c) Hình 2.2: Minh họa độ lệch tâm và tuần hoàn của hình dạng. 2.2.1.2 Dấu hiệu hình dạng (Shape Signature). Dấu hiệu hình dạng (SS) mô tả hình dạng bởi hàm một chiều thu đƣợc từ điểm biên. SS bao gồm: tọa độ phức hợp, tọa độ cực, khoảng cách tâm, góc tiếp tuyến, góc quỹ tích, độ cong, diện tích và chiều dài dây cung. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 16 SS không bị tác động bởi dịch chuyển và co dãn hình dạng. Bên cạnh đó, SS có thể đƣợc lƣợng tử hóa thành một biểu đồ dấu hiệu, biểu đồ này bất biến với phép quay và có thể sử dụng cho đối sánh. SS thƣờng nhạy cảm với nhiễu, những thay đổi nhỏ trên biên có thể gây ra những lỗi lớn trong đối sánh. Vì vậy, SS không thực tế và không hiệu quả trong tra cứu hình dạng. 2.2.1.3 Momen biên (Boundary Moment). Momen biên (BM) có thể đƣợc dùng để giảm kích thƣớc của các biểu diễn biên. Giả sử biên đã đƣợc biểu diễn nhƣ một SS Z(i), momen thứ r là mr và momen tâm là µr, có công thức ƣớc tính: Và Trong đó, N là số các điểm biên. Chuẩn hóa các momen: Và Để mô tả bất biến với các phép dịch chuyển, phép quay và co dãn. 2.2.2 Phương pháp cấu trúc. Một phƣơng pháp khác trong phân tích hình dạng là biểu diễn hình dạng cấu trúc. Với cách tiếp cận cấu trúc, hình dạng đƣợc chia thành các phân đoạn biên đƣợc gọi là đối tƣợng ban đầu. Phƣơng pháp cấu trúc khác nhau trong việc lựa chọn đối tƣợng ban đầu và tổ chức các đối tƣợng này cho việc biểu diễn hình dạng. Phân tích biên thƣờng dựa trên xấp xỉ đa giác, phân tích đƣờng cong và đối sánh các đƣờng cong. Điều đạt đƣợc của tiếp cận cấu trúc đó là có khả năng giải quyết sự bế tắc trong chuỗi hoạt động liên tục và cho phép đối sánh từng phần, tuy nhiên, nó vẫn còn một vài điều hạn chế. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 17 2.2.2.1 Biểu diễn bằng mã xích (chain code). Mã xích mô tả đƣờng biên đối tƣợng bằng một chuỗi các đoạn thẳng đơn vị với các hƣớng đã đƣợc xác định. Nền tảng này đã đƣợc giới thiệu vào năm 1961 bởi Freeman, ông đã mô tả một phƣơng pháp cho phép mã hóa các cấu hình hình học theo ý muốn. Trong phƣơng pháp này, một đƣờng cong bất kỳ đƣợc biểu diễn bởi một chuỗi các vector đơn vị chiều dài và thiết lập một giới hạn các hƣớng cho phép, do đó gọi là phƣơng pháp vector đơn vị. Trong thực hiện, một hình ảnh đƣợc đặt chồng lên một lƣới, từ đó các điểm biên lấy xấp xỉ với điểm lƣới gần nhất, sau đó lấy mẫu của hình ảnh thu đƣợc. Từ một điểm khởi đầu đƣợc lựa chọn trên biên, một mã xích có thể đƣợc tạo ra bằng cách mã hóa các đoạn thẳng biểu diễn biên. Các đoạn thẳng đơn vị có thể định hƣớng theo 4 hƣớng, 8 hƣớng hoặc N hƣớng (với N> 8 và N = 2k), mã xích sử dụng đoạn thẳng đơn vị định hƣớng theo N hƣớng đƣợc gọi là mã xích tổng quát. Mã xích dùng để biểu diễn hình dạng phải không phụ thuộc vào sự lựa chọn điểm ảnh biên bắt đầu trong chuỗi. Một khả năng để chuẩn hóa chuỗi mã xích là tìm các điểm ảnh trong trình tự biên mà kết quả mô tả là các số nguyên tối thiểu, sau đó chúng đƣợc sử dụng nhƣ là các điểm ảnh bắt đầu. Ngoài ra, biên có thể đƣợc biểu diễn bởi sự khác biệt về các chỉ thị tiếp theo trong chuỗi mã thay vì biểu diễn cho biên theo chỉ số tƣơng đối. Sự chuẩn hóa sự khác biệt chuỗi mã đƣợc gọi là shape numbe, shape number sẽ đƣợc sử dụng để biểu diễn hình dạng đối tƣợng (phần này sẽ đƣợc trình bày cụ thể trong mục 3.2.2). Dùng mã xích biểu diễn hình dạng và đối sánh có nhiều hạn chế, mã xích bị ảnh hƣởng nhiễu đƣờng biên và biến dạng, thêm vào đó là kích thƣớc của chuỗi mã dài. Mã xích mà thƣờng đƣợc sử dụng là đầu vào của những phân tích ở mức độ cao, ví dụ nhƣ xấp xỉ đa giác và tìm điểm uốn. 2.2.2.2 Phân tích đa giác (Polygon Decompositon). Trong phƣơng pháp này, đƣờng biên đƣợc chia nhỏ thành các đoạn bởi xấp xỉ đa giác. Các đỉnh đa giác đƣợc sử dụng nhƣ một đối tƣợng ban đầu. Đặc trƣng của mỗi đối tƣợng ban đầu đƣợc mô tả nhƣ một chuỗi bao gồm 4 yếu tố: góc nội tiếp, khoảng cách đến đỉnh tiếp theo, các tọa độ x và y. Các đặc trƣng này đƣợc tổ chức thành một cây nhị phân hoặc m-arytree. Đối sánh hình dạng có hai bƣớc: Bƣớc đầu tiên đối sánh đặc trƣng với đặc trƣng, bƣớc thứ hai, đối sánh hình dạng với hình dạng. Trong bƣớc đầu tiên, chúng ta thu đƣợc dữ liệu đặc trƣng của các hình dạng truy vấn. Các đặc trƣng này đƣợc tìm kiếm thông qua chỉ số cây, nếu một mẫu đặc _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 18 trƣng cụ thể trong cơ sở dữ liệu đƣợc tìm thấy tƣơng tự nhƣ dữ liệu đặc trƣng thì danh sách các hình dạng liên quan đến mô hình đặc trƣng đƣợc lấy ra. Trong bƣớc thứ hai, đối sánh giữa hình dạng truy vấn và mẫu thu đƣợc, việc đối sánh đƣợc thực hiện dựa vàokhoảng cách biến đổi giữa hai chuỗi các đối tƣợng ban đầu. 2.2.2.3 Phương pháp không gian tỉ lệ (Scale Space method). Dudek và Tsotsos phân tích hình dạng trong không gian tỉ lệ và sử dụng sơ đồ đối sánh mô hình với mô hình. Trong phƣơng pháp này, trƣớc tiên hình dạng gốc (nguyên thủy) thu đƣợc từ kỹ thuật làm mịn đƣờng cong. Sau đó, thiết lập một mô tả đoạn bao gồm chiều dài phân đoạn, thứ tự vị trí và giá trị điều chỉnh độ cong đƣợc trích chọn từ mỗi hình dạng nguyên thủy. Cuối cùng, một chuỗi các mô tả đoạn đƣợc tạo ra để mô tả hình dạng. Ví dụ với hai hình dạng A và B đƣợc mô tả bởi hai chuỗi: A= ( và B= ), đối sánh mô hình với mô hình sử dụng lập trình động để thu đƣợc số điểm tƣơng đồng của hai hình dạng. Để làm tăng hiệu quả trong quá trình tính toán đối sánh, chúng ta đƣa các đặc trƣng hình dạng vào không gian có độ cong tỉ lệ để hình dạng có thể đƣợc đối sánh ở các tỉ lệ khác nhau. Tuy nhiên, do trong mô tả đoạn có bao gồm chiều dài phân đoạn nên mô tả này bất biến với co giãn. 2.3 Kỹ thuật biểu diễn hình dạng dựa trên vùng. Trong phƣơng pháp biểu diễn dựa trên vùng phải kể đến tất cả những pixel trong vùng hình dạng thu đƣợc trong biểu diễn hình dạng. Phƣơng pháp biểu diễn vùng thƣờng sử dụng các momen để mô tả hình dạng. Và một số phƣơng pháp khác thƣờng sử dụng gồm có: phƣơng pháp lƣới, bề mặt lồi và trục trung vị. Biểu diễn hình dạng dựa trên vùng xem xét đến toàn bộ vùng hình dạng và sử dụng hiệu quả thông tin của toàn bộ pixel chứa trong vùng. Những phƣơng pháp này đo sự phân phối pixel của vùng hình dạng, chúng ít có khả năng giả tạo bởi nhiễu và biến dạng. Phƣơng pháp vùng phổ biến là những phƣơng pháp moment. Ở mức thấp thứ tự moment hay bất biến momnet mang theo những ý nghĩa vật lý kết hợp với sự phân phối pixel. Tuy nhiên nó rất khó khăn để kết hợp thứ tự moment cao hơn với sự giải thích vật lý. Phƣơng pháp lƣới là dựa trên khả năng trực quan quan sát hình dạng, nó không phản ánh sự thống kê phân bổ của vùng hình dạng và bị ảnh hƣởng bởi nhiễu và không cô đọng nhƣ bất biến moment. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 19 2.3.1 Phương pháp toàn cục. Phƣơng pháp toàn cục xem xét đến toàn bộ hình dạng, kết quả của mô tả là vector số đặc trƣng (numeric feature vector), nó đƣợc sử dụng để biểu diễn hình dạng. 2.3.1.1 Bất biến momen hình học (Geometric Moment Invariant). Hu đã công bố bài nghiên cứu đầu tiên về việc sử dụng các momen bất biến cho ứng dụng nhận dạng mẫu hai chiều. Phƣơng pháp tiếp cận của ông dựa trên các nghiên cứu của các nhà toán học thế kỷ 19 và lý thuyết đại số: mpq = p, q = 0, 1, 2 … Sử dụng kết hợp phi tuyến các momen có thứ tự thấp, một tổ hợp các bất biến momen (thƣờng đƣợc gọi là momen hình học), trong đó các thuộc tính bất biến với co giãn và phép quay đƣợc rút ra. Việc sử dụng các momen có thứ tự cao cho phân tích mẫu không đƣợc áp dụng. Vấn đề chính với momen hình học là chỉ có một số bất biến đƣợc rút ra từ thứ tự thấp của momen, nhƣ vậy không đủ để mô tả chính xác hình dạng, nhƣng cũng rất khó để lấy đƣợc những bất biến thứ tự cao hơn. 2.3.1.2 Bất biến moment đại số (Algebraic Moment Invariant). Bất biến momen đại số (AMI) đƣợc Taubin và Cooper giới thiệu và sử dụng trong QBIC. Các AMI đƣợc tính toán cho từ m momen trung tâm đầu tiên và đƣợc đặt ra nhƣ là giá trị riêng của ma trận định trƣớc M[j,k], trong đó các phần tử tỉ lệ với các yếu tố của các momen trung tâm. Khác với phƣơng pháp bất biến momen hình học của Hu, các bất biến momen đại số có thể đƣợc xây dựng từ các thứ tự bất kỳ. AMI có xu hƣớng làm việc tốt trên các đối tƣợng có điểm ảnh đƣợc phân bổ và không phải là hình dạng phác thảo. 2.3.1.3 Phương pháp dựa trên lưới (Grid Based Method). Lƣới mô tả hình dạng đƣợc đề xuất bởi Lu và Sajjanhar, nó đã đƣợc sử dụng trong Mars và một số ứng dụng khác. Về cơ bản, hình dạng sẽ đƣợc chiếu lên một lƣới có kích thƣớc cố định, một chuỗi nhị phân mô tả hình dạng sẽ đƣợc tạo ra bằng cách quét lƣới này từ trái sang phải và từ trên xuống và cho kết quả là một bitmap. Các ô bao phủ hình dạng đƣợc chỉ định giá trị 1, và những ô không bao phủ hình dạng đƣợc chỉ định giá trị 0. Khoảng cách Hamming hoặc khoảng cách cityblock đƣợc sử dụng để đo lƣờng sự giống nhau giữa hai hình. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102 20 2.3.2 Phương pháp cấu trúc. Cũng giống nhƣ phƣơng pháp cấu trúc biên, cấu trúc vùng phân tích hình dạng vùng theo từng phần rồi sử dụng chúng cho mô tả và biểu diễn hình dạng. 2.3.2.1 Bề mặt lồi (Convex Hull). Một vùng R là lồi khi và chỉ khi với 2 điểm bất kỳ x1, x2 R thì toàn bộ đoạn x1x2 nằm bên trong vùng. Bề mặt lồi của một vùng là vùng lồi H nhỏ nhất đáp ứng điều kiện R H. Sự khác biệt của R-H đƣợc gọi là thiếu hụt lồi của vùng R (convex deficiency). Đầu tiên, bề mặt lồi của một đối tƣợng thu đƣợc với các thiếu hụt lồi của nó, sau đó lại tìm bề mặt lồi và thiếu hụt lồi của các thiếu hụt lồi đã tìm thấy ở bƣớc trƣớc, quá trình tiếp tục cho đến khi các thiếu hụt lồi đều là các vùng lồi. Hình 2.3(a) minh họa quá trình này, và hình dạng đƣợc mô tả nhƣ một cây lõm trong hình 2.3(b). Hình 2.3: Minh họa phƣơng pháp bề mặt lồi: (a) Bề mặt lồi và các thiếu hụt lồi của nó; (b) Cây lõm biểu diễn bề mặt lồi. 2.3.2.2 Trục trung vị (Media Axis) (hay còn gọi là xương). Cũng giống nhƣ bề mặt lồi, xƣơng cũng có thể đƣợc sử dụng để mô tả và biểu diễn hình dạng. Xƣơng (trục trung vị) là quỹ tích tâm của các đĩa cực đại của hình dạng nhƣ trong hình 2.4, đƣờng in đậm là xƣơng của hình chữ nhật. Hình 2.4: Trục trung vị (xƣơng) của hình chữ nhật. _____________________________________________________________ Sinh viên: Phùng Thị Lệ – CT1102