Đồ án Xây dựng chương trình tìm kiếm theo nội dung trong File Avi

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔN TIN ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành Công nghệ thông tin Đề tài: XÂY DỰNG CHƯƠNG TRÌNH TÌM KIẾM THEO NỘI DUNG TRONG FILE AVI Sinh viên thực hiện: BÙI MẠNH HÙNG Lớp K1B, hệ chính qui Giáo viên hướng dẫn: ThS. VŨ THÀNH VINH Thái Nguyên, 4 - 2007 LỜI CẢM ƠN Trước hết em xin gửi đến thấy giáo Thạc sĩ Vũ Thành Vinh lời cảm ơn chân thành và sâu sắc nhất. Bằng kinh nghiệm và lòng nhiệt huyết của mình, trong thời gian vừa qua, thầy đã tận tình chỉ bảo và hướng dẫn giúp em hoàn thành tốt đồ án của mình, kết quả đạt được của đồ án này cũng bao gồm một phần công lao rất lớn của thầy. Em xin cảm ơn thầy một lần nữa! Em cũng xin cảm ơn các thầy cô trong khoa Công nghệ thông tin Đại học Thái Nguyên, đặc biệt là những thầy cô đã trực tiếp giảng dạy em trong 5 năm học vừa qua, thầy cô là những người đã tạo nền tảng kiến thức cơ bản nhất, vững chắc nhất và đầy đủ nhất để em có thể nhận và hoàn thành đồ án này. Em xin cảm ơn! Sinh viên Bùi Mạnh Hùng LỜI CAM ĐOAN Tôi, sinh viên Bùi Mạnh Hùng, lớp K1B khoa Công nghệ thông tin, Đại học Thái Nguyên, xin cam đoan đồ án này là đồ án của tôi, không sao chép nội dung cơ bản từ bất kì đồ án nào khác, toàn bộ nội dung chính của đồ án là do nhưng nghiên cứu của bản thân tôi xây dựng lên. Chương trình kèm theo với các nội dung chính liên quan đến đồ án là do tôi tự viết ra, không sao chép từ bất kỳ nguồn nào và chương trình này chỉ sử dụng với mục đích demo cho nội dung đồ án không có bất kỳ một mục đích nào khác. Tôi xin cam đoan những gì tôi trình bày ở trên hoàn toàn là sự thật, nếu có nội dung nào sai sự thật tôi xin hoàn toàn chịu trách nhiệm. MỤC LỤC Mở đầu Chương 1: Tổng quan về ngôn ngữ lập trình Visual C++ 6.0 Chương 2: Tổng quan về xử lý ảnh 2.1 Tổng quan về một hệ thống xử lý ảnh 2.2 Các vấn đề cơ bản trong xử lý ảnh nâng cao 2.2.1 Histogram và biến đổi histogram 2.2.2 Các kỹ thuật tăng cường ảnh (Image Enhancement) 2.2.3 Khôi phục ảnh (Image Restauration) 2.2.4 Nhận dạng ảnh 2.2.5 Nén ảnh Chương 3: Tổng quan về video 3.1 Tổng quan về video 3.2.Một số thuộc tính đặc trưng của video 3.2.1.Color 3.2.2.Texture 3.2.3.Shape 3.2.4.Motion Chương 4: Các phương pháp xác định độ đo tương tự trong xử lý ảnh 4.1 Giới thiệu 4.2 Phương pháp Histogram dòng, cột 4.3 Mô hình Cognitive Visual Attention (CVA) 4.4 Độ đo tương tự có thể học (Trainable similarity measure) 4.5 Multivariate Two-sample problem Chương 5: Phân tích và thiết kế hệ thống 5.1.Phân tích 5.1.1.Đặt vấn đề 5.1.2.Phân tích bài toán 5.2.Kỹ thuật đề xuất 5.3.Thiết kế hệ thống Chương 6: Thực nghiệm 6.1 Giới thiệu chương trình 6.2 Các chức năng chính của chương trình 6.2.1 Giao diện chính 6.2.2 Chức năng mở file video, ảnh gốc 6.2.3 Thao tác với file video 6.2.4 Hiển thị Histogram 6.2.5 Xuất frame ra file bitmap 6.2.6 Khoanh vùng đối tượng cần tìm 6.2.7 Xác định độ đo tương tự 6.3 Kết quả đạt được KẾT LUẬN TÀI LIỆU THAM KHẢO PHỤ LỤC MỞ ĐẦU Ngày nay, thông tin hình ảnh đóng vai trò quan trọng trong trao đổi thông tin, bởi phần lớn các thông tin mà con người thu nhận được đều thông qua thị giác. Do vậy vấn đề xử lý ảnh nói chung và xử lý video nói riêng đã phát triển , nó liên quan đến nhiều ngành khác như: hệ thống tin học, lý thuyết thông tin, lý thuyết thống kê, trí tuệ nhân tạo, nhận dạng, v.v. Thực tế này đặt ra ba bài toán lớn. Thứ nhất, giảm dung lượng video và tăng tốc độ xử lý. Thứ hai, tổ chức lưu trữ, tìm kiếm video hiệu quả. Thứ ba, tiến đến việc hiểu nội dung video. Trong đợt làm đồ án tốt nghiệp này, em đã chọn đề tài là "Tìm kiếm theo nội dung trong file video" vì các lí dó sau. Đầu tiên, đây là đề tài đáp ứng được nguyện vọng vủa em là được nghiên cứu đề tài liên quan đến xử lý ảnh, một vấn đề mà em đã và đang rất qua tâm, thứ hai đây là một trong các bài toán nằm trong lớp bài toán thứ ba đề cập ở trên, một lớp bài toán có ý nghĩa đặc bệt quan trọng do vậy nó mang rất nhiều ý nghĩa thực tiễn, thứ ba đây là một cơ hội rất tốt giúp em có thể tự đánh giá được năng lực bản thân bởi vì đây là một đề tài khó và hiện tại vẫn chưa có nhiều nghiên cứu có kết quả cao và chưa được phổ biến rộng rãi. Chương 1: TỔNG QUAN VỀ NGÔN NGỮ LẬP TRÌNH VISUAL C++ 6.0 1.1 Giới thiệu Trước đây phần lớn các ứng dụng Windows được viết bằng ngôn ngữ C. Ngày nay các môi trường lập trình mới đã cho phép viết các chương trình thương mại có chất lượng cao bằng C, C++, Pascal, BASIC và các ngôn ngữ khác. Trong đó, ngôn ngữ C++ đã được các lập trình viên chuyên nghiệp chọn để sử dụng thay cho C. Kết hợp với thư viện lớp, C++ trừu tượng, giao diện lập trình ứng dụng (Application Programming Interface - API) của Windows nhờ các lớp cơ sở để biểu diễn các dối tượng chung như cửa sổ, thực đơn ... C++ làm giảm các khó khăn cho những người lập trình ít kinh nghiệm. Ở đây chúng ta sẽ mô tả các sử dụng MFC (Microsoft Foundation Class) để viết các ứng dụng Windows trên cơ sở thông điệp và các đặc tính cơ bản của C++ như lớp, thừa hưởng ... 1.2 Cơ bản về MFC MFC là tập hợp các lớp định nghĩa sẵn. Chúng biểu diễn cách tiếp cận hướng đối tượng đến lập trình Windows và chúng gói các Windows API. Rất nhiều lập trình viên C++ đã chọn thư viện MFC như là thư viện lớp để phát triển ứng dụng của mình. MFC cho phép lập trình viên dành nhiều thời gian hơn cho phát triển các thành phần cấu trúc chương trình và ít phải lo lắng về giao diện của Windows. Đặc biệt, MFC làm đơn giản tiến trình phát triển mã trình cho các loại máy có hệ điều hành khác nhau: Windows 16 bít, Windows 32 bít, Windows 64 bít. Hiện nay, MFC 6.0 (trong bộ Visual C++ 6.0) có hơn 130 lớp, trong đó một số lớp được trực tiếp sử dụng và một số khác làm lớp cơ sở cho lớp riêng của lập trình viên. Rất nhiều lớp khá đơn giản, chẳng hạn như lớp CPoint (chỉ chứa tọa độ x,y của một điểm). Một số lớp khác lại rất phức tạp, như lớp CWnd chứa cả cửa sổ mà ta quan sát thấy trên màn hình. Hình 1.1 - Mô tả rút gọn cấu trúc MFC Trong chương trình MFC, giao diện lập trình API rất ít khi được gọi trực tiếp. Thay vào đó là tạo ra các đối tượng của các lớp MFC và gọi các hàm thành phần của chúng. Rất nhiều hàm thành phần MFC là lớp vỏ bao bọc mỏng xung quanh API; rất nhiều hàm, thậm chí, có cùng tên với các hàm API. Điều này giúp cho lập trình viên C có thể chuyển nhanh sang MFC. Thí dụ, khi dịch chuyển cửa sổ, trong C ta gọi hàm API với tên SetWindowsPos. Khi tìm tên này trong MFC ta thấy MFC cũng trợ giúp chúng, đó là hàm thành phần của lớp CWnd khi cửa sổ được coi là đối tượng, còn SetWindowsPos là một hành động mà ta muốn thực hiện trên đối tượng đó. MFC còn là khung (framework) ứng dụng. MFC giúp định nghĩa cấu trúc của ứng dụng và quản lý rất nhiều công việc khác nữa. Bắt đầu với CWinApp, là lớp biểu diễn chính ứng dụng, MFC bao gồm hầu hết mọi thao tác chương trình. Khung ứng dụng cung cấp hàm WinMain, đến lượt WinMain gọi các hàm thành phần của đối tượng ứng dụng để làm cho chương trình chạy. Một trong các hàm thành phần của CWinApp mà WinMain gọi đến là hàm Run, nó chứa vòng lặp thông điệp và lệnh chạy chương trình. MFC còn trợ giúp các tài liệu (document) và quan sát (view), cho phép tách dữ liệu của chương trình khỏi biểu diễn đồ họa của chúng. MFC cũng đưa ra một số API riêng, độc lập với các lớp và được dùng chung. 1.3 CObject, cha của tất cả các lớp Khi quan sát biểu đồ phân cấp MFC ta sẽ thấy phần lớn các lớp MFC là lớp suy diễn trực tiếp hoặc gián tiếp từ CObject. CObject cũng cấp ba kiểu cơ bản để xây dựng các lớp thừa hưởng chúng: Vào/ra dữ liệu (Serialization) Thông tin về lớp khi chương trình đang chạy (Run - time) Thông báo kiếm tra lỗi Serialization (vào/ra) là tiến trình giúp các đối tượng tự truyền đến hoặc truyền đi từ phương tiện lưu trữ như đĩa từ, clipboard. CObject có hai hàm thành phần làm nhiệm vụ xử lý vào/ra: IsSerializable và Serialize. Chương trình có thể gọi hàm IsSerializable của đối tượng suy diễn từ CObject để xác định xem chúng có trợ giúp vào/ra hay không. Đặc trưng khác mà các lớp suy diễn từ CObject thừa hưởng là trợ giúp lấy thông tin về đối tượng của chương trình đang chạy. Cho trước con trỏ CObject đến lớp suy diễn từ chúng, tiện ích thông tin kiểm tra kiểu run - time cho phép chương trình biết được tên lớp của đối tượng cũng như các thông tin khác. CObject cung cấp hai hàm thành phần để làm việc này: IsKindOf và GetRuntimeClass. Đặc trưng thứ ba mà CObject thêm vào các lớp suy diễn của chúng là trợ giúp kiểm tra lỗi Hàm thành phần ảo AssertValid của CObject yêu cầu đối tượng thực hiện kiểm tra tính hợp lý trên chính nó (trạng thái bên trong của đối tượng) nhờ một dãy toán tử xen, tách ( >> hay << ). Hàm thành phần ảo Dump thực hiện quá trình kiểm tra các thành phần dữ liệu của đối tượng, có ích khi gỡ rối chương trình và kiểm tra các đối tượng mà nó sử dụng. 1.4 Các lớp kiến trúc ứng dụng Các lớp kiến trúc ứng dụng hình thành khuôn dạng và cấu trúc của các ứng dụng MF, CWinApp biểu diễn chính ứng dụng. Toàn bộ ứng dụng trên cơ sở MFC đều suy diễn lớp từ CWinApp và tạo các đối tượng ứng dụng từ các lớp suy diễn. Nhóm lớp này còn bao gồm CDocument, lớp cơ sở cho các tài liều (document) trong các ứng dụng sử dụng kiên trúc tài liệu/quan sát (document/view) của MFC. Hiểu đơn giản, một “tài liệu” là biểu diễn trừu tượng của các dữ liệu chương trình. CDocument cho phép ứng dụng bảo quản dữ liệu tách biệt khỏi các thành phần khác của chương trình, bao gồm các “quan sát” của dữ liệu được vẽ trên màn hình. Một lớp quan trọng khác là CWinThread. Một đối tượng CWinThread biểu diễn một luồng thực hiện Các hàm thành phần của chúng như CreateThread, SetThreadPriority và SuspendThread cung cấp các công cụ mà chương trình MFC sử dụng để tạo và xử lý các luồng thực hiện. 1.5 Các lớp đối tượng trực quan Các lớp đối tượng trực quan (visual object) bao gồm phần lớn các đối tượng quan sát được khi màn hình chương trình Windows chạy, bao gồm cửa sổ, hộp thoại, thực đơn, điều khiển và nhiều đối tượng khác. Chúng còn bao gồm cả ngữ cảnh thiết bị (Device Context - DC) của Windows và các đối tượng giao diện thiết bị đồ họa (Graphics Device Interface - GDI) như bitmaps, chổi tố (brushes) và bút vẽ (pens). Một trong những lớp trừu tượng nhất của loại này là CView, chúng là bản đối trọng của CDocument và là lớp cơ sở cho mọi quan sát dữ liệu của ứng dụng. Gốc của mọi lớp đối tượng trực quan là CWnd, chúng được sử dụng như lớp cơ sở cho mọi lớp cửa sổ. CWnd định nghĩa các chức năng cơ bản của cửa sổ và chứa hàng chục hàm thành phần để xử lý cho cửa sổ theo nhiều cách khác nhau CWnd còn định nghĩa các trả lời mặc định của cửa sổ cho hầu hết các thông điệp. CWnd đôi khi được sử dụng trực tiếp nhưng thường xuyên hơn là sử dụng các lớp suy diễn từ các lớp suy diễn của CWnd hay lập đối tượng từ các lớp mà MFC suy diễn từ CWnd. Lớp CGdiObject được sử dụng như lớp cơ sở của các đối tượng GDI như bút, chổi tô và cọ chữ, cùng với các lớp suy diễn từ CGdiObject như CPen, CBrush, và CFont biễu diễn chính các đối tượng. 1.6 Các lớp chức năng chung Không phải tất cả các lớp MFC được thiết kế để gói API của Windows. MFC còn có rất nhiều lớp khác thực hiện các công việc như quản lý các biến xâu và vào/ra tệp. Lớp cực kỳ hữu hiệu CString định nghĩa dữ liệu xâu có kiểu cơ sở với các toán tử chuẩn như =, +=, < và để thực hiện gán, ghép và so sánh. Lớp CFile và các suy diễn từ chúng thực hiện các hàm vào/ra chuẩn như Read và Write và cài đặt chúng trong ngữ cảnh đối tượng tệp. CException là lớp cơ sở trừu tượng để sử dụng cơ chế quản lý lỗi try/throw/catch của C++. 1.7 Các hàm AfxXxx Không phải tất cả các hàm mà MFC cũng cấp là hàm thành phần lớp. MFC còn cho API dưới dạng các hàm tổng thể với tên bắt đầu là Afx (A và f trong Afx là “application frameword”). Các hàm này được gọi bất kỳ đâu trong ứng dụng MFC, không như hàm thành phần là chúng phải có đối tượng hay con trỏ đối tượng. Bảng 1.1 liệt kê một vài hàm AfxXxx. Hàm Afx BeginThread thường được gọi thay cho hàm CWinThread::CreateThread vì chúng tạo và thực hiện luồng thực hiện trong một bước. Hàm AfxMessageBox tương đương với hàm MessageBox của Windows và không như CWnd::MessageBox, chúng có thể được gọi mà không cần con trỏ đến lớp suy diễn từ CWnd AfxFormatString1 thường được nối với AfxMessageBox để thực hiện tạo dạng xâu kiểu printf. AfxGetApp dùng để lấy về con trỏ đến đối tượng ứng dụng khai báo trong tệp khác, và AfxGetInstanceHandle lấy chỉ danh làm tham số của hàm API của Windows. Cuối cùng AfxRegisterWndClass được sử dụng khi MFC không thực hiện đăng ký lớp cửa sổ mặc định. Tên hàm Mô tả AfxAbort Kết thúc vô điều kiện ứng dụng. AfxBeginThread Lập luồng thực hiện mới và bắt đầu thực hiện chúng AfxEndThread Kết thúc luồng thực hiện đang thực hiện. AfxFormatString1 Thay thế xâu vào vị trí %1 trong xâu tài nguyên AfxMessageBox Hiển thị thông báo của Windows AfxGetApp Cho lại con trỏ đến đối tượng ứng dụng. AfxGetInstanceHandle Cho lại handle chỉ ra bản thân ứng dụng hiện hành AfxRegisterWndClass Đăng ký một lớp cửa sổ riêng cho ứng dụng MFC Bảng 1.1 - Một số hàm AfxXxx 1.8 Kiến truc tài liệu/quan sát Trong ứng dụng tài liệu/quan sát đối tượng tài liệu biểu diễn dữ liệu ứng dụng, còn một hay nhiều đối tượng quan sát sẽ biểu diễn quan sát dữ liệu đó. Các đối tượng dữ liệu và quan sát cùng xử lý đầu vào của người sử dụng, vẽ ký tự và biểu diễn đồ họa của dữ liệu kết quả. Lớp CDocument được sử dụng làm lớp cơ sở cho các đối tượng tài liệu, còn lớp CView và các lớp phái sinh của chùng làm cơ sở cho các đối tượng quan sát. Cửa sổ trên cùng suy diễn từ CFrameWnd hay CMDIFrameWnd không còn là tiểu điểm để xử lý các thông điệp, nhưng để làm cái “chứa” quan sát, thanh công cụ, thanh trạng thái, và các đối tượng khác. MFC trợ giúp hai loại ứng dụng tài liệu/quan sát Loại thứ nhất là ứng dụng ghép nối đơn tài liệu (Single-Document Interface - SDI), chúng chỉ cho phép mở một tài liệu một lần Loại thứ hai là ứng dụng ghép nối đa tài liệu (Multiple-Document Interface - MDI), cho phép mở hai hay nhiều tài liệu đồng thời. 1.8.1 Đối tượng tài liệu Trong ứng dụng tài liệu/quan sát, dữ liệu được lưu trong một đối tượng tài liệu của lớp phái sinh từ CDocument. Khái niệm “tài liệu” hay gây nhầm lẫn vì nó thường được hiểu dưới cái nhìn của các chương trình xử lý văn bản hay trang tính và các ứng dụng khác làm cho ta suy nghĩ đến tài liệu văn bản truyền thống. Trong thực tế, kiến trúc tài liệu/quan sát đề cập đến biểu diễn trừu tượng dữ liệu chương trình, vạch ra đường ngăn cách rõ ràng giữa việc lưu giữ dữ liệu và biểu diễn dữ liệu. Dữ liệu thường được lưu trong các biến thành phần đi theo lớp tài liệu phái sinh. Bảng 1.2 liệt kê một số hàm thành phần quan trọng mà đối tượng tài liệu thừa hưởng từ lớp CDocument. Hàm SetModifiedFlag được gọi mỗi khi dữ liệu tài liệu thay đổi. Hàm SetModifiedFlag sẽ lập cờ bên trong đối tượng tài liệu để cho khung ứng dụng biết rằng tài liệu có dữ liệu chưa được lưu trên đĩa. Ta có thể tự xác định xem tài liệu có chữa dữ liệu chưa lưu lại trên đĩa không nhờ gọi hàm IsModified của tài liệu. Hàm GetTitle và GetPathName lấy tên tệp của tài liệu và đường dẫn đầy đủ của tệp. Tên hàm Mô tả GetFirstViewPosition Cho lại giá trị POSITION để truyền cho GetNextView GetNextView Cho lại con trỏ CView trỏ đến quan sát tiếp theo trong danh sách GetPathName Lấy tên tệp và đường dẫn của tài liệu GetTitle Lấy tiêu đề tài liệu IsModified Cho lại giá trị khác 0 nếu tài liệu chưa lưu trên đĩa SetModifiedFlag Đặt hoặc xoá cờ cho biết tài liệu bị thay đổi UpdateAllViews Làm tươi toàn bộ các quan sát OnFileSendMail Cài đặt lệnh Send Mail trong thực đơn file Bảng 1.2 - Các thao tác cơ bản của CDocument CDocument còn cung cấp tập các hàm ảo để nạp chồng. Một số thường xuyên phải nạp chồng trong các lớp tài liệu phái sinh, một số khác rất ít khi nạp chồng. Bốn hàm thường xuyển hay được nạp chồng nhất được mô tả trong danh sách sau: Tên hàm Mô tả OnNewDocument Khởi động tài liều mới OnOpenDocument Mở một tài liệu đã được lưu lên đĩa DeleteContents Xóa dữ liệu của tài liệu Serialize Thực hiện vào/ra dữ liệu với thiết bị lưu trữ Bảng 1.3 - Các hàm nạp chồng của CDocument 1.8.2 Đối tượng quan sát Trong khi mục đích duy nhất của đối tượng tài liệu là lưu trữ dữ liệu ứng dụng, các đối tượng quan sát có hai mục đích: biểu diễn dữ liệu tài liệu trên màn hình và chuyển đổi đầu vào từ người sử dụng thành các lệnh thao tác tài liệu - trừ các thông điệp chuột và bàn phím, chúng chuyển đối đối tượng tài liệu như các thông điệp lệnh. Như vậy tài liệu và quan sát có quan hệ mật thiết và thông tin trao đổi giữa chúng là hai chiều. Đối tượng tài liệu có thể có số lượng bất kỳ các quan sát liên quan đến nó, những mỗi quan sát chỉ gắn với một loại tài liệu. Khung ứng dụng lưu con trỏ đến đối tượng tương ứng trong thành phần dữ liệu m_pDocument của quan sát và con trỏ này được thầm nhập qua hàm thành phần GetDocument. Lớp CView của MFC định nghĩa các tính chất của quan sát, và các lớp quan sát phái sinh chia sẻ chức năng phụ. Như lớp CDocument, CView và các lớp phái sinh của chúng bao gồm một số hàm thành phần ảo mà ta có thể nạp chổng để thực hiện các thao tác quan sát riêng. Hàm quan trọng nhất là hàm OnDraw, nó được gọi mỗi khi quan sát nhận thông điệp WM_PAINT. Trong ứng dụng không phải cấu trúc tài liệu/quan sát, các thông điệp WM_PAINT được xử lý nhờ hàm OnPaint, hàm này sử dụng đối tượng CPaintDC để vẽ. Trong ứng dụng tài liệu/quan sát, khung ứng dụng nhận thông điệp WM_PAINT và gọi hàm OnDraw của lớp quan sát, chuyển con trỏ CDC cho chúng để vẽ. Không cần ánh xạ thông điệp bởi vì OnDraw là ảo. Chương 2: TỔNG QUAN VỀ XỬ LÝ ẢNH 2.1 Tổng quan về một hệ thống xử lý ảnh Xử lý ảnh là một môn khoa học còn tương đối mới mẻ so với nhiều ngành khoa học khác, nhất là trên qui mô công nghiệp, song trong xử lý ảnh đã bắt đầu xuất hiện những máy tính chuyên dụng. Để có thể hình dung cấu hình một hệ thống xử lý ảnh chuyên dụng hay một hệ thống xử lý ảnh dùng trong nghiên cứu, đào tạo, trước hết chúng ta sẽ xem xét các bước cần thiết trong xử lý ảnh. Trước hết là quá trình thu nhận ảnh. Ảnh có thể thu nhận qua camera. Thường ảnh thu nhận qua camera là tín hiệu tương tự (loại camera ống kiểu CCIR), nhưng cũng có thể là tín hiệu số hoá (loại CCD - Charge Coupled Device). Hệ quyết định lưu trữ SENSOR Số hoá Thu nhận ảnh Nhận dạng CAMERA lưu trữ Phân tích ảnh Hình 2.1 - Các giai đoạn trong xử lý ảnh Ảnh cũng có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh, tranh được quét trên scanner. Tiếp theo là quá trình số hoá (Digitalizer) để biến đổi tín hiệu tương tự sang tín hiệu rời rạc (lấy mẫu) và số hoá bằng lượng hoá, trước khi chuyển sang giai đoạn xử lý, phân tích hay lưu trữ lại. Quá trình phân tích ảnh thực chất bao gồm nhiều công đoạn nhỏ. Trước hết là công việc tăng cường ảnh để nâng cao chất lượng ảnh. Do những nguyên nhân khác nhau: có thể do chất lượng thiết bị thu nhận ảnh, do nguồn sáng hay do nhiễu, ảnh có thể bị suy biến. Do vậy cần phải tăng cường và khôi phục lại ảnh để làm nổi bật một số đặc tính chính của ảnh, hay làm cho ảnh gần giống nhất với trạng thái gốc- trạng thái trước khi ảnh bị biến dạng.Giai đoạn tiếp theo là phát hiện các đặc tính như biên, phân vùng ảnh, trích chọn các đặc tính, v.v... Cuối cùng, tuỳ theo mục đích của ứng dụng, sẽ là giai đoạn nhận dạng, phân lớp hay các quyết định khác.Các giai đoạn chính của quá trình xử lý ảnh có thể mô tả ở hình 2.1. Với các giai đoạn trên, một hệ thống xử lý ảnh (cấu trúc phần cứng theo chức năng) gồm các thành phần tối thiểu như hình 2.2. Đối với một hệ thống xử lý ảnh thu nhận qua camera-camera như là con mắt của hệ thống.Có 2 loại camera: camera ống loại CCIR và camera CCD.Loại camera ứng với chuẩn CCIR quét ảnh với tần số 1/25 và mỗi ảnh gồm 625 dòng.Loại CCD gồm các photo điốt và làm tương ứng một cường độ sáng tại một điểm ảnh ứng với một phần tử ảnh (pixel).Như vậy, ảnh là tập hợp các điểm ảnh.Số pixel tạo nên một ảnh gọi là độ phân giải (resolution). Bộ xử lý tương tự (analog processor).Bộ phận này thực hiện các chức năng sau: Chọn camera thích hợp nếu hệ thống có nhiều camera. Chọn màn hình hiển thị tín hiệu Thu nhận tín hiệu video thu nhận bởi bộ số hoá(digitalizer).Thực hiện lấy mẫu và mã hoá. Tiền xử lý ảnh khi thu nhận: dùng kỹ thuật bảng tra (Look Up Table - LUT). Bộ xử lý ảnh số.Gồm nhiều bộ xử lý chuyên dụng: xử lý lọc, trích chọn đường bao, nhị phân hoá ảnh.Các bộ xử lý này làm việc với tốc độ 1/25 giây. Máy chủ.Đóng vai trò điều khiển các thành phần miêu tả ở trên. Bộ nhớ ngoài: Dữ liệu ảnh cũng như các kiểu dữ liệu khác, để có thể chuyển giao cho các quá trình khác, nó cần được lưu trữ.Để có một ước lượng, xét thí dụ sau: một ảnh đen trắng cỡ 512 x 512 với 256 mức xám chiếm 256K bytes.Với một ảnh màu cùng kích thước dung lượng sẽ tăng gấp 3 lần. Mành hình đồ họa camera Bộ xử lý tương tự Bộ nhớ ảnh Máy chủ Màn hình Bộ xử lý ảnh số Bộ nhớ ngoài Máy in Bàn phím Hình 2.2 - Các thành phần chính của hệ thống xử lý ảnh 2.2 Các vấn đề cơ bản trong xử lý ảnh nâng cao 2.2.1 Histogram và biến đổi histogram 2.2.1.1 Lược đồ xám (Histogram) Lược đồ mức xám của một ảnh là một hàm cung cấp tần suất xuất hiện của mỗi mức xám (grey level). Lược đồ xám được biểu diễn trong một hệ toạ độ vuông góc x,y. Trong hệ toạ độ này, trục hoành biểu diễn số mức xám từ 0 đến N, N là số mức xám (256 mức trong trường hợp chúng ta xét). Trục tung biểu diễn số điểm ảnh cho một mức xám (số điểm ảnh có cùng mức xám). Cũng có thể biểu diễn khác một chút: trục tung là tỷ lệ số điểm ảnh có cùng mức xám trên tổng số điểm ảnh mức xám mức xám số điểm ảnh số điểm ảnh ảnh đậm ảnh nhạt 2.3 - Lược đồ xám của ảnh Lược đồ xám cung cấp rất nhiều thông tin về phân bố mức xám của ảnh. Theo thuật ngữ của xử lý ảnh gọi là tính động của ảnh. Tính động của ảnh cho phép phân tích trong khoảng nào đó phân bố phần lớn các mức xám của ảnh: ảnh rất sáng hay ảnh rất đậm. Nếu ảnh sáng, lược đồ xám nằm bên phải (mức xám cao), còn ảnh đậm luợc đồ xám nằm bên trái(mức xám thấp). Theo định nghĩa của lược đồ xám, việc xây dựng nó là khá đơn giản. Thuật toán xây dựng lược đồ xám có thể mô tả như sau: Bắt đầu H là bảng chứa lược đồ xám (là vec tơ có N phần tử) a. Khởi tạo bảng Đặt tất cả các phần tử của bảng là 0 b. Tạo bảng Với mỗi điểm ảnh I(x,y) tính H[I(x,y)] = H[I(x,y)] + 1 c. Tính giá trị Max của bảng H. Sau đó hiện bảng trong khoảng từ 0 đến Max. Kết thúc Lược đồ xám là một công cụ hữu hiệu dùng trong nhiều công đoạn của xử lý ảnh như tăng cường ảnh ( xem chương Bốn). Dưới đây ta xem xét một số biến đổi lược đồ xám hay dùng. 2.2.1.2 Biến đổi histogram Trong tăng cường ảnh, các thao tác chủ yếu dựa vào phân tích lược đồ xám. Trước tiên ta xét bảng tra LUT(Look Up Table). Bảng tra LUT là một bảng chứa biến đổi một mức xám i sang mức xám j .Một cách toán học, LUT được định nghĩa như sau: - Cho GI là tập các mức xám ban đầu GI = {0, 1, ..., NI} - Cho GF là tập các mức xám kết quả GF = {0, 1, ..., NF} để cho tiện ta cho NI = NF = 255. - f là ánh xạ từ GI vào GF: "giÎGi sẽ $ gfÎGF mà gf = f(gi) Với mỗi giá trị của mức xám ban đầu ứng với một giá trị kết quả. Việc chuyển đổi một mức xám ban đầu về một mức xám kết quả tương ứng có thể dễ dàng thực hiện được nhờ một bảng tra. Khi đã xây dựng được bảng, việc sử dụng bảng là khá đơn giản. Người ta xem xét mức xám của mỗi điểm ảnh, nhờ bảng tra tính được mức xám kết quả. Gọi là bảng tra, thực ra là một véctơ có NI + 1 phần tử. Mỗi phần tử của bảng chứa một giá trị mức xám kết quả. Có hai kiểu bảng tra: bảng đồng nhất và bảng nghịch đảo. Với bảng đồng nhất, giá trị mức xám ban đầu cũng chính là giá trị mức xám kết quả; còn với bảng nghịch đảo, nếu giá trị mức xám ban đầ là gI thì giá trị mức xám kết quả là 255-gI. Một trong những ứng dụng phổ biến của LUT là viền khung động. Một số ảnh ban đầu hoặc có thể là rất đậm hay rất nhạt, hoặc độ tương phản thấp. Điều này có thể là do trong ảnh ban đầu, các mức xám có thể vượt lên cao hoặc xuống dưới tỷ lệ, hay tập trung lại trong một vùng rất hẹp (trên lược đồ xám thể hiện rõ điều này). Mục đích của LUT là phân bố lại mức xám để chúng có thể phủ trên toàn dải - đó chính là viền khung động. Việc chọn giá trị Min và Max là phụ thuộc vào từng ứng dụng. Một ứng dụng khác của LUT là làm nổi bật một số dải mức xám của ảnh. Điều này có thể thực hiện được nhờ viền khung động tại miền quan tâm, bên ngoài miền đặt giá trị là 0 hay nhị phân hoá ảnh (binarisation). Với một ảnh tự nhiên được lượng hoá một cách tuyến tính, phần lớn các điểm ảnh có giá trị thấp hơn độ sáng trung bình. Trong miền tối, ta khó có thể cảm nhận các chi tiết của ảnh. Thực tế cần phải khắc phục nhược điểm này bằng cách biến đổi luợc đồ xám. Người ta biến đổi lược đồ sao cho tiến gần tới lược đồ định trước. Có nhiều phương pháp, trong đó phương pháp phổ dụng là san bằng lược đồ (histogram equalisa-tion). Nếu ảnh có kích thước pxp và ảnh kết quả được mã hoá trên NF mức xám, thì số điểm ảnh cho 1 mức xám trong lược đồ cân bằng lý tưởng sẽ là hằng số và bằng p2/NF (NF là số mức xám đầu ra). Trên thực tế, NF thường nhỏ hơn NI (số mức xám ban đầu). Việc san bằng lược đồ được thực hiện theo thuật toán: /* Ima: ảnh gốc cần san bằng Histo: lược đồ xám của ảnh Transfo: bảng san bằng lược đồ BatDau, KetThuc : điểm bắt đầu và điểm kết thúc mỗi dải xét. Bande, CentreBande: độ rộng băng và trung điểm của dải Nl: Số mức xám của ảnh gốc Nf: Số mức xám của ảnh kết quả */ a. Khởi tạo TBLituong <-- pxp/NF; Bande <-- NI/NF; CentreBande <-- Bande/2; BatDau, KetThuc <-- 0; b. Tính và biến đổi lược đồ While KetThuc < Nl do Begin Tong <-- 0; While (Tong < TBLituong) and(KetThuc < NI ) do Begin Tong <-- Tong + Histo(KetThuc); Inc(KetThuc) End; For i := BatDau to KetThuc -1 do Trandfo[i] <-- CentreBande; CentreBande <- - CentreBande + Bande; Debut <-- KetThuc; End c. Tính ảnh kết quả For i := 1 to N do For j :=1 to N do Begin Pic <-- Ima[i,j]; Ima[i,j] <-- Transfo[Pic] End Lưu ý rằng, NF càng hạn chế thì việc tích hợp càng quan trọng vì giá trị p2/NF sẽ tăng. Trên thực tế, người ta hay dùng NF = NI/2 và lặp lại nhiều lần quá trình san bằng. Thí dụ với một ảnh 128 x 128 mã hoá trên 256 mức xám, nếu muốn lược đồ san bằng trên 64 mức xám, số lượng trung bình các điểm ảnh lý tưởng sẽ tiệm cận 1282/64 = 256. 2.2.2 Các kỹ thuật tăng cường ảnh (Image Enhancement) Nhiệm vụ của tăng cường ảnh không phải là làm tăng lượng thông tin vốn có trong ảnh mà làm nổi bật các đặc trưng đã chọn làm sao để có thể phát hiện tốt hơn, tạo thành quá trình tiền xử lý cho phân tích ảnh.Tăng cường ảnh bao gồm: điều khiển mức xám, dãn độ tương phản, giảm nhiễu, làm trơn ảnh, nội suy, phóng đại, nổi biên v...v. 2.2.2.1 Cải thiện ảnh dùng toán tử điểm Toán tử điểm là toán tử không bộ nhớ, ở đó một mức xám u Î[0,N] được ánh xạ sang một mức xám v Î[0,N]: v = f( u).Ánh xạ f tuỳ theo các ứng dụng khác nhau có dạng khác nhau và được liệt kê trong bảng sau: Tăng độ tương phản: Các độ dốc a, b, g xác định độ tương phản tương đối.L là số mức xám cực đại. Tách nhiễu và phân ngưỡng Khi a = b = t được gọi là phân ngưỡng. Biến đổi âm bản f(u) = L – u tạo âm bản Cắt theo mức Chính chọn bit với in = Int[it/2a-1], n = 1, 2, ..., B 2.2.2.2 Cải thiện ảnh dùng toán tử không gian Cải thiện ảnh là làm cho ảnh có chất lượng tốt hơn theo ý đồ sử dụng.Thường là ảnh thu nhận có nhiễu cần phải loại bỏ nhiễu hay ảnh không sắc nét bị mờ hoặc cần làm rõ các chi tiết như biên.Các toán tử không gian dùng trong kỹ thuật tăng cường ảnh được phân theo nhóm theo công dụng: làm trơn nhiễu, nổi biên.Để làm trơn nhiễu hay tách nhiễu người ta sử dụng các bộ lọc tuyến tính (lọc trung bình, thông thấp) hay lọc phi tuyến (trung vị, giả trung vị, lọc đồng hình).Do bản chất của nhiễu là ứng với tần số cao và cơ sở lý thuyết của lọc là bộ lọc chỉ cho tín hiệu có tần số nào đó thông qua (dải tần bộ lọc).Do vậy để lọc nhiễu ta dùng lọc thông thấp (theo quan điểm tần số không gian) hay lấy tổ hợp tuyến tính để san bằng (lọc trung bình). Để làm nổi cạnh (ứng với tần số cao), ngưòi ta dùng các bộ lọc thông cao, Laplace.Chi tiết và các cách áp dụng được trình bày dưới đây. Làm trơn nhiễu bằng lọc tuyến tính (lọc Trung bình và lọc dải thông thấp): vì có nhiều loại nhiễu can thiệp vào quá trình xử lý ảnh như: nhiễu cộng, nhiễu xung, nhiễu nhân nên cần có nhiều bộ lọc thích hợp.Với nhiễu cộng và nhiễu nhân ta dùng các bộ lọc thông thấp, trung bình và lọc đồng hình (homomorphie); với nhiễu xung ta dùng lọc trung vị , giả trung vị, lọc ngoài (outlier). Làm trơn nhiễu bằng lọc phi tuyến: người ta dùng bộ lọc trung vị (Median Filtering), giả trung vị (Pseudo Median Filtering), lọc ngoài (Outlier).Với lọc trung vị, điểm ảnh đầu vào sẽ được thay thế bởi trung vị các điểm ảnh.Còn lọc giả trung vị sẽ dùng trung bình cộng của 2 giá trị "trung vị" (trung bình cộng của max và min ). Mặt nạ gờ sai phân và làm nhăn (Unharp Masking and Crispering): mặt nạ gờ sai phân dùng khá phổ biến trong công nghệ in ảnh để làm đẹp ảnh.Với kỹ thuật này, tín hiệu đầu ra thu được bằng tín hiệu ra của bộ lọc gradient hay lọc dải cao bổ xung thêm đầu vào Khuyếch đại và nội suy ảnh: có nhiều ứng dụng cần thiết phải phóng đại một vùng của ảnh.Có nghĩa là lấy một vùng của ảnh đã cho và cho hiện lên như một ảnh lớn.Có 2 phương pháp được dùng là lặp (Replication) và nội suy tuyến tính (linear interpolation). 2.2.3 Khôi phục ảnh (Image Restauration) Khôi phục ảnh đề cập tới các kỹ thuật loại bỏ hay tối thiểu hoá các ảnh hưởng của môi trường bên ngoài hay các hệ thống thu nhận, phát hiện và lưu trữ ảnh đến ảnh thu nhận được.Ở đây, ta có thể liệt kê nguyên nhân các biến dạng (degradations): do nhiễu bộ cảm nhận tín hiệu, ảnh mờ do camera, nhiễu ngẫu nhiên của khí quyển, v...v.Khôi phục ảnh bao gồm nhiều quá trình như: lọc ảnh, khử nhiễu nhằm làm giảm các biến dạng để có thể khôi phục lại ảnh gần giống ảnh gốc tuỳ theo các nguyên nhân gây ra biến dạng.Một hệ thống khôi phục ảnh số có thể minh hoạ như hình 2.3. Về nguyên tắc, khôi phục ảnh nhằm xác định mô hình toán học của quá trình đã gây ra biến dạng, tiếp theo là dùng ánh xạ ngược để xác định lại ảnh.Việc xác định mô hình có thể thực hiện theo 2 hướng: trước và sau. Hệ thống ảnh Chuyển đổi AD Lọc ảnh Chuyển đổi DA Lưu trữ tín hiệu u(x,y) v(x,y) Hình 2.3 – Hệ thống khôi phục ảnh số Theo hướng thứ nhất, một mô hình sẽ được xây dựng từ các ảnh kiểm nghiệm để xác định đáp ứng xung của hệ thống nhiễu. Theo hướng thứ hai, người ta thực hiện các phép đo trên ảnh.Nói chung là mô hình không biết trước.Các mô hình toán học dùng cho cả hai phương pháp là rất phức tạp. 2.2.4 Nhận dạng ảnh Nhận dạng là quá trình phân loại các đối tượng được biểu diễn theo một mô hình nào đó và gán cho chúng vào một lớp (gán cho đối tượng một tên gọi) dựa theo những quy luật và các mẫu chuẩn.Quá trình nhận dạng dựa vào những mẫu học biết trước gọi là nhận dạng có thày hay học có thày (supervised learning); trong trường hợp ngược lại gọi là học không có thày (non supervised learning). 2.2.4.1 Mô hình Việc chọn lựa một quá trình nhận dạng có liên quan mật thiết đến kiểu mô tả mà người ta sử dụng để đặc tả đối tượng.Trong nhận dạng, người ta phân chia làm 2 họ lớn: - Họ mô tả theo tham số - Họ mô tả theo cấu trúc. Cách mô tả được lựa chọn sẽ xác định mô hình của đối tượng.Như vậy, chúng ta sẽ có 2 loại mô hình: mô hình theo tham số và mô hình cấu trúc. Mô hình tham số: sử dụng một véctơ để đặc tả đối tượng.Mỗi phần tử của véctơ mô tả một đặc tính của đối tượng.Thí dụ như trong các đặc trưng chức năng, người ta sử dụng các hàm cơ sở trực giao để biểu diễn.Và như vậy ảnh sẽ được biểu diễn bởi một chuỗi các hàm trực giao.Giả sử C là đường bao của ảnh và C(i,j) là điểm thứ i trên đường bao, i = 1, 2,..., N (đường bao gồm N điểm).Giả sử tiếp: là tọa độ tâm điểm.Như vậy momen trung tâm p, qua của đường bao là: vectơ tham số trong trường hợp này chính là các moment mij với i=1, 2,...,p và j=1, 2,...,q.Còn trong số các đặc trưng hình học, người ta hay sử dụng chu tuyến , đường bao, diện tích và tỉ lệ T = 4pS/p2, với S là diện tích, p là chu tuyến.Việc lựa chọn phương pháp biểu diễn sẽ làm đơn giản cách xây dựng.Tuy nhiên, việc lựa chọn đặc trưng nào là hoàn toàn phụ thuộc vào ứng dụng Mô hình cấu trúc: cách tiếp cận của mô hình này dựa vào việc mô tả đối tượng nhờ một số khái niệm biểu thị các đối tượng cơ sở trong ngôn ngữ tự nhiên.Để mô tả đối tượng, người ta dùng một số dạng nguyên thuỷ như đoạn thẳng, cung, v,...,v.Chẳng hạn một hình chữ nhật được định nghĩa gồm 4 đoạn thẳng vuông góc với nhau từng đôi một.Trong mô hình này người ta sử dụng một bộ kí hiệu kết thúc Vt, một bộ kí hiệu không kết thúc gọi là Vn.Ngoài ra có dùng một tập các luật sản xuất để mô tả cách xây dựng các đối tượng phù hợp dựa trên các đối tượng đơn giản hơn hoặc đối tượng nguyên thuỷ (tập Vt).Trong cách tiếp cận này, ta chấp nhận một khẳng đinh là: cấu trúc một dạng là kết quả của việc áp dụng luật sản xuất theo theo những nguyên tắc xác định bắt đầu từ một dạng gốc bắt đầu.Một cách hình thức, ta có thể coi mô hình này tương đương một văn phạm G = (Vt, Vn, P, S). 2.2.4.2 Bản chất của qua trình nhận dạng Quá trình gồm 3 giai đoạn chính: - Lựa chọn mô hình biểu diễn đối tượng. - Lựa chọn luật ra quyết định (phương pháp nhận dạng) và suy diễn quá trình học. - Học nhận dạng. Khi mô hình biểu diễn đối tượng đã được xác định, có thể là định lượng (mô hình tham số) hay định tính (mô hình cấu trúc), quá trình nhận dạng chuyển sang giai đoạn học.Học là giai đoạn rất quan trọng.Thao tác học nhằm cải thiện, điều chỉnh việc phân hoạch tập đối tượng thành các lớp. Việc nhận dạng chính là tìm ra quy luật và các thuật toán để có thể gán đối tượng vào một lớp hay nói một cách khác gán cho đối tượng một tên. Học có thày (supervised learning) Kỹ thuật phân loại nhờ kiến thức biết trước gọi là học có thày.Đặc điểm cơ bản của kỹ thuật này là người ta có một thư viện các mẫu chuẩn.Mẫu cần nhận dạng sẽ được đem sánh với mẫu chuẩn để xem nó thuộc loại nào.Thí dụ như trong một ảnh viễn thám, người ta muốn phân biệt một cánh đồng lúa, một cánh rừng hay một vùng đất hoang mà đã có các miêu tả về các đối tượng đó.Vấn đề chủ yếu là thiết kế một hệ thống để có thể đối sánh đối tượng trong ảnh với mẫu chuẩn và quyết định gán cho chúng vào một lớp.Việc đối sánh nhờ vào các thủ tục ra quyết định dựa trên một công cụ gọi là hàm phân lớp hay hàm ra quyết định. Học không có thày(unsupervised learning) Kỹ thuật học này phải tự định ra các lớp khác nhau và xác định các tham số đặc trưng cho từng lớp.Học không có thày đương nhiên là khó khăn hơn.Một mặt, do số lớp không được biết trước, mặt khác những đặc trưng của các lớp cũng không biết trước.Kỹ thuật này nhằm tiến hành mọi cách gộp nhóm có thể và chọn lựa cách tốt nhất.Bắt đầu từ tập dữ liệu, nhiều thủ tục xử lý khác nhau nhằm phân lớp và nâng cấp dần để đạt được một phương án phân loại. Nhìn chung, dù là mô hình nào và kỹ thuật nhận dạng ra sao, một hệ thống nhận dạng có thể tóm tắt theo sơ đồ sau: Trích chọn đặc tính biểu diễn đối tượng Phân lớp ra quyết định Đánh giá Quá trình tiền xử lý Khối nhận dạng trả lời Hình 2.4 - Sơ đồ tống quát một hệ thống nhận dạng ảnh 2.2.4.3 Nhận dạng dựa trên phân hoạch không gian Thực tế có nhiều thuật toán nhận dạng học không có thày.Ở đây, chúng ta xem xét 3 thuật toán hay được sử dụng: Thuật toán nhận dạng dựa vào khoảng cách lớn nhất, thuật toán K- trung bình (K - mean) và thuật toán ISODATA.Chúng ta lần lượt xem xét các thuật toán này vì chúng có bước tiếp nối, cải tiến từ thuật toán này qua thuật toán khác Thuật toán nhận dạng dựa vào khoảng cách lớn nhất Nguyên tắc: Cho một tập gồm m đối tượng.Ta xác định khoảng cách giữa các đối tượng và khoảng cách lớn nhất ứng với phần tử xa nhất tạo nên lớp mới.Sự phân lớp được hình thành dần dần dựa vào việc xác định khoảng cách giữa các đối tượng và các lớp. Thuật toán: Bước 1: - Chọn hạt nhân ban đầu: giả sử X1 Î C1 gọi là lớp g1.Gọi Z1 là phần tử trung tâm của g1. - Tính tất cả các khoảng cách Dj1 = X(Dj, Z1) với j = 1, 2, ..., m - Tìm Dk1 = maxj Dj1.Xk là phần tử xa nhất của nhóm g1.Như vậy Xk là phần tử trung tâm của lớp mới g2, ký hiệu Z2. - Tinh d1 = D12 = D(Z1,Z2) Bước 2: - Tính khoảng cách Dj1, Dj2. - Dj1 = D(Xj,Z1), Dj2 = D(Xj, Z2).Đặt Dk(2) = maxjDj Nguyên tắc chọn: - Nếu Dk(2) < qd1 kết thúc thuật toán, phân lớp xong. - Nếu không sẽ tạo lên nhóm thứ ba.Gọi Xk là phần tử trung tâm của g3, ký hiệu Z3. - Tính d3 = (D12 + D13 + D23)/3 với q là ngưỡng cho trước và D13 = D(Z1,Z3), D23 = D(Z2,Z3) Quá trình cứ lặp lại như vậy cho đến khi phân xong.Kết quả là ta thu được các lớp với các đại diện là Z1, Z2 ,..., Zm. Thuật toán K-trung bình Nguyên tắc: khác với thuật toán trên, ta xét K phần tử đầu tiên trong không gian đối tượng, hay nói một cách khác ta cố định K lớp.Hàm để đánh giá là hàm khoảng cách Euclide: (1) Jk làm chỉ tiêu với lớp Ck.Việc phân vùng cho k hạt nhân được tiến hành theo nguyên tắc khoảng cách cực tiểu.Ở đây, ta dùng phương pháp đạo hàm để tính cực tiểu. Xét với Zk là biến.Ta dễ dàng có Jk min khi: (2) Công thức trên là giá trị trung bình của lớp Ck và điều này lý giải tên của phương pháp Thuật toán: - Chọn Nc phần tử (giả thiết có Nc lớp) của tập T.Gọi các phần tử trung tâm của các lớp đó là: X1, X2,..., XNc và ký hiệu là Z1, Z2, ..., ZNc. - Thực hiện phân lớp: + X Ck nếu D(X,Zk) = Min D(X,Zj)(1), j =1,..., Nc là lần lặp thứ nhất. + Tính tất cả các Zk theo công thức (2) + X Gk(q-1) nếu D(X,Zk(q-1)) = min l D(X,Zl(q-1)) + Nếu Zk(q-1) = Zk(q) thuật toán kết thúc, nếu không ta tiếp tục thực hiện phân lớp Thuật toán ISODATA ISODATA là viết tắt của từ Iteractive Self Organizing Data Analysis.Nó là thuật toán khá mềm dẻo, không cần cố định các lớp trước. Các bước của thuật toán được mô tả như sau: - Lựa chọn một phân hoạch ban đầu dựa trên các tâm bất kỳ.Thực nghiệm đã chứng minh kết quả nhận dạng không phụ thuộc vào phân lớp ban đầu. - Phân vùng bằng cách sắp các điểm vào tâm gần nhất dựa vàp khoảng cách Euclide. - Tách đôi lớp ban đầu nếu khoảng cách lớn hơn ngưỡng t1. - Xác định phân hoạch mới trên cơ sở các tâm vừa xác định lại và tiếp tục xác định tâm mới. - Tính tất cả các khoảng cách đến tâm mới. - Nhóm các vùng với tâm theo ngưỡng t2. Lặp các thao tác tác trên cho đến khi thỏa mãn tiêu chuẩn phân hoạch. 2.2.4.4 Nhận dạng cấu trúc Các đối tượng cần nhận dạng theo phương pháp này được biểu diễn bởi một câu trong ngôn ngữ L(G).Khi đó thao tác phân lớp chính là xem xét một đối tượng có thuộc văn phạm L(G) không? Nói cách khác nó có được sinh ra bởi các luật của văn phạmG không? Như vậy sự phân lớp là theo cách tiếp cận cấu trúc đòi hỏ phải xác định: - Tập Vt chung cho mọi đối tượng. - Các quy tắc sinh P để sản sinh ra một câu và chúng khác nhau đối với mỗi lớp. - Quá trình học với các câu biểu diễn các đối tượng mẫu l nhằm xác định văn phạm G. - Quá trình ra quyết định: xác định một đối tượng X được biểu diễn bởi một câu lx.Nếu lx nhận biết bởi ngôn ngữ L(Gx) thì ta nói rằng X 'Ck. Nói cách khác, việc ra quyết định phân lớp là dựa vào phân tích cúGk biểu diễn lớp Ck.pháp của văn phạm.Cũng như trong phân tích cú pháp ngôn ngữ, có phân tích trên xuống, dưới lên, việc nhận dạng theo cấu trúc cũng có thể thực hiện theo cách tương tự. Việc nhận dạng dựa theo cấu trúc là một ý tưởng và dẫu sao cũng cần được nghiên cứu thêm 2.2.5 Nén ảnh 2.2.5.1 Tổng quan về nén dữ liệu ảnh Nén dữ liệu là quá trình làm giảm lượng thông tin "dư thừa" trong dữ liệu gốc và do vậy, lượng thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều.Với dữ liệu ảnh, kết quả thường là 10 : 1.Một số phương pháp còn cho kết quả cao hơn.Theo kết quả nghiên cứu được công bố gần đây tại viện kỹ thuật Georgie, kỹ thuật nén fractal cho tỉ số nén là 30 trên 1. 2.2.5.2 Các phương pháp nén thế hệ thứ nhất Mã hóa loạt dài RLC (Running Length Coding) Phương pháp mã hoá loạt dài lúc đầu được phát triển dành cho ảnh số 2 mức: mức đen (1) và mức trắng (0) như các văn bản trên nền trắng, trang in, các bức vẽ kỹ thuật. Nguyên tắc của phương pháp là phát hiện một loạt các bít lặp lại, thí dụ như một loạt các bit 0 nằm giữa hai bit 1, hay ngược lại, một loạt bit 1 nằm giữa hai bit 0.Phương pháp này chỉ có hiệu quả khi chiều dài dãy lặp lớn hơn một ngưỡng nào đó.Dãy các bit lặp gọi là loạt hay mạch (run).Tiếp theo, thay thế chuỗi đó bởi một chuỗi mới gồm 2 thông tin: chiều dài chuỗi và bit lặp (ký tự lặp).Như vậy, chuỗi thay thế sẽ có chiều dài ngắn hơn chuỗi cần thay. Phương pháp RLC có thể chia thành 2 phương pháp nhỏ: phương pháp dùng chiều dài từ mã cố định và phương pháp thích nghi như kiểu mã Huffman.Giả sử các mạch gồm M bits.Để tiện trình bày, đặt M =2m-1.Như vậy mạch cũ được thay bỏi mạch mới gồm m bits.Với cách thức này, mọi mạch đều được mã hoá bởi từ mã có cùng độ dài.Người ta cũng tính được, với M=15, p=0.9, ta sẽ có m=4 và tỷ số nén là 1,95. Với chiều dài cố định, việc cài đặt thuật toán là đơn giản.Tuy nhiên, tỷ lệ nén sẽ không tốt bằng dùng chiều dài biến đổi hay gọi là mã RLC thích nghi. Mã hóa Huffman Phương pháp mã hoá Huffman là phương pháp dựa vào mô hình thống kê.Dựa vào dữ liệu gốc, người ta tính tần suất xuất hiện của các ký tự.Việc tính tần xuất được thực hiện bằng cách duyệt tuần tự tệp gốc từ đầu đến cuối.Việc xử lý ở đây tính theo bit.Trong phương pháp này, ngưới ta gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự có tần xuất thấp từ mã dài.Nói một cách khác, các ký tự có tần xuất càng cao được gán mã càng ngắn và ngược lại.Rõ ràng với cách thức này, ta đã làm giảm chiều dài trung bình của từ mã hoá bằng cách dùng chiều dài biến đổi.Tuy nhiên, trong một số tình huống khi tần suất là rất thấp, ta có thể không được lợi một chút nào, thậm chí còn bị thiệt một ít bit Mã hóa LZW(Lempel Ziv - Wench Khái niệm nén từ điển được Jacob Lempel và Abraham Ziv đưa ra lần đầu tiên vào năm 1977, sau đó phát triển thành một họ giải thuật nén từ điển LZ.Năm 1984, Terry Welch đã cải tiến giải thuật LZ thành một giải thuật mới hiệu quả hơn và đặt tên là LZW.Phương pháp nén từ điển dựa trên việc xây dựng từ điển lưu các chuỗi kí tự có tần suất lặp lại cao và thay thế bằng từ mã tương ứng mỗi khi gặp lại chúng.Giải thuật LZW hay hơn các giải thuật trước nó ở kĩ thuật tổ chức từ điển cho phép nâng cao tỉ lệ nén. Giải thuật nén LZW được sử dụng cho tất cả các loại file nhị phân.Nó thường được dùng để nén các loại văn bản, ảnh đen trắng, ảnh màu, ảnh đa mức xám...và là chuẩn nén cho các dạng ảnh GIF và TIFF.Mức độ hiệu quả của LZW không phụ thuộc vào số bit màu của ảnh. Mã hóa khối (Block Coding) Phương pháp này lúc đầu được phát triển cho ảnh số 2 mức xám, sau đó hoàn thiện thêm bởi các phương pháp thích nghi và mở rộng cho ảnh số đa cấp xám. Cho một ảnh số I(x,y) kích thước M x N.Người ta chia nhỏ ảnh số thành các khối hình chữ nhật kích thước k x l, (k,l) là rất nhỏ so với M, N.Như vậy ảnh gốc coi như gồm các khối con xếp cạnh nhau và có N x M / (k x l) khối con. Ta có thể dùng phương pháp mã hoá Huffman cho từng khối của ảnh gốc, nghĩa là gán cho mỗi từ khối một từ mã nhị phân như ở phần trên.Một khó khăn gặp phải khi dùng mã hoá tối ưu Huffman đó là số lượng khối quá lớn.Giải pháp ở đây là dùng mã hoá gần tối ưu, đơn giản hơn để thực hiện mã hoá. 2.2.5.3 Phương pháp mã hóa dựa vào biến đổi thế hệ thứ nhất Thuật toán mã hóa dùng biến đổi hai chiều Các phương pháp mã hoá dùng biến đổi 2 chiều thường gồm 4 bước sau: Bước 1: chia ảnh thành khối Ảnh được chia thành các khối nhỏ kích thước k x l và biến đổi các khối đó một cách độc lập để thu được các khối Vi, i=0,1,...,B với B = N x M / (k x l). Bước 2: xác định phân phối bit cho từng khối Thường các hệ số hiệp biến của các biến đổi là khác nhau.Mỗi hệ số yêu cầu lượng hoá với một số lượng bit khác nhau. Bước 3: thiết kế bộ lượng hóa Với phần lớn các biến đổi, các hệ số v(0,0) là không âm.Các hệ số còn lại có trung bình 0.Để tính các hệ số, ta có thể dùng phân bố Gauss hay Laplace.Các hệ số được mã hoá bởi số bit khác nhau, thường từ 1 đến 8 bit.Do vậy cần thiết kế 8 bộ lượng hoá.Để dễ cài đặt, tín hiệu vào v1(k,l) được chuẩn hoá để có dạng: v1(k,l) = v1(k,l)/sk,l (k,l) ¹ (0,0) Trước khi thiết kế bộ lượng hoá, người ta tìm cách loại bỏ một số hệ số không cần thiết. Bước 4: mã hóa Tín hiệu đầu ra của bộ lượng hoá sẽ được mã hoá trên các từ bit để truyền đi hay lưu trữ lại.Quá trình mã hoá dựa vào biến đổi có thể được tóm tắt trên hình 8-3 dưới đây. Nếu ta chọn phép biến đổi KL cho phương pháp sẽ có một số nhược điểm: Khối lượng tính toán sẽ rất lớn vì phải tính ma trận hiệp biến, tiếp sau là phải giải phương trình tìm trị riêng và véc tơ riêng để xác định các hệ số. Vì lý do này, trên thực tế người ta thích dùng các biến đổi khác như Hadamard, Haar, Sin và Cosin. Trong số biến đổi này, biến đổi Cosin thường hay được dùng hơn Mã hóa dùng biến đổi Cosin và chuẩn JPEG Phép biến đổi Cosin rời rạc (DCT) được Ahmed đưa ra vào năm 1974.Kể từ đó đến nay nó được ứng dụng rất rộng rãi trong nhiều phương thức mã hoá ảnh khác nhau nhờ hiệu suất gần như tối ưu của nó đối với các ảnh có độ tương quan cao giữa các điểm ảnh lân cận.Biến đổi Cosin rời rạc được sử dụng trong chuẩn ảnh nén JPEG và định dạng phim MPEG. Phép biến đổi Cosine một chiều Phép biến đổi Cosin rời rạc một chiều được định nghĩa bởi: Trong đó: Phép biến đổi Cosin nhanh Phép biến đổi Cosin nhanh viết tắt là FCT (Fast Cosine Transform), dựa vào ý tưởng đưa bài toán ban đầu vể tổ hợp của các bài toán biến đổi FCT trên các dãy con.Việc tiến hành biến đổi trên các dãy con sẽ đơn giản hơn rất nhiều so với dãy gốc.Vì thế, người ta tiếp tục phân nhỏ dãy tín hiệu đến khi chỉ còn một phần tử. Phép biến đổi Cosin ngược Phép biến đổi Cosin ngược được định nghĩa bằng công thức: Trong đó: Phép biến đổi Cosin ngược sẽ được thực hiện theo chiều ngược lại với quy trình đã iến hành trong phép biến đổi nhanh.Tuy nhiên, công việc này không được thuận lợi như phép biến đổi FFT ngược. Chuẩn JPEG JPEG là viết tắt của Joint Photographic Expert Group ( nhóm các chuyên gia phát triển chuẩn ảnh này).Chuẩn JPEG được công nhận là chuẩn ảnh quốc tế năm 1990 phục vụ các ứng dụng truyền ảnh cho các lĩnh vực như y học, khoa học kĩ thuât, ảnh nghệ thuật... Chuẩn JPEG được sử dụng để mã hoá ảnh đa mức xám, ảnh màu.Nó không cho kết quả ổn định lắm với ảnh đen trắng.Chuẩn JPEG cung cấp giải thuật cho cả hai loại nén là nén không mất mát thông tin và nén mất mát thông tin. Ảnh gốc Phân đoạn 8x8 8x8 8x8 Lượng tử hóa Bảng lượng tử ...... Mã hóa Bảng mã Ảnh nén DCT Hình 2.5 - Sơ đồ thuật toán nén ảnh JPEG ẢNH GIẢI NÉN Lượng tử hóa Bảng lượng tử Giải mã Bảng mã ẢNH NÉN DCT ngược Hình 2.6 - Sơ đồ thuật toán giải nén ảnh JPEG 2.2.5.4 Phương pháp mã hóa thế hệ thứ hai Phương pháp Kim tự tháp Laplace (Pyramide Laplace) Phương pháp này là tổ hợp của 2 phương pháp: mã hoá thích nghi và biến đổi.Tỷ số nén là khá cao, thường là10 trên 1.Về nguyên tắc, phương pháp này dựa vào mô hình quan sát phân cấp của hệ thống quan sát của con người. Bắt đầu từ ảnh gốc x(m,n) qua bộ lọc dải thấp ta thu được tín hiệu x1(m,n).Bộ lọc này được thiết kế để tính trung bình cục bộ dựa vào đáp ứng xung 2 chiều gần với đường cong Gauss.Bộ lọc này đóng vai trò "dự đoán" với sai số e1(m,n) tính bởi: e1(m,n) = x(m,n) - x1(m,n) Như vậy là mã hoá của x1(m,n) và e1(m,n) là tương đương với mã hoá của x(m,n).Với cách biến đổi như trên, e1(m,n) thuộc loại dải cao.Vì mắt người ít cảm nhận được tín hiệu với tần số cao nên ta có thể dùng một lượng bit ít hơn để mã hoá cho nó.Mặt khác, tín hiệu x1(m,n) thuộc loại dải thấp, nên theo lý thuyết lấy mẫu số mẫu sẽ ít hơn. Quá trình này được lặp lại bằng cách dùng các bộ lọc thấp khác nhau và ta sẽ thu được các tín hiêụ xi(m,n), i =1, 2,...Với mỗi lần lặp, kích thước của ảnh sẽ giảm đi một lượng bằng fi/f i+1.Theo cách này, ta có một cấu trúc xếp chồng tựa như cấu trúc kim tự tháp mà kích thước giảm dần từ gốc đến đỉnh.Nhân chập Gauss được dùng ở đây có kích thước 5 x 5.Các tín hiệu ra sau đó được lượng hoá và mẫu hoá. Phương pháp mã hoá dựa vào biểu diễn ảnh Mã hoá dựa vào vùng gia tăng Kỹ thuật vùng gia tăng thực chất là hợp các vùng có cùng một số tính chất nào đó.Kết quả của nó là một ảnh được phân đoạn giống như một ô trong trò xếp chữ (puzzle).Tuy nhiên, cần lưu ý rằng tất cả các đường bao thu được không tạo nên một ảnh giống ảnh gốc. Việc xác định tính chất miền đồng nhất xác định độ phức tạp của phương pháp.Để đơn giản, tiêu chuẩn chọn ở đây là khoảng mức xám.Như vậy, miền đồng nhất là tập hợp các điểm ảnh có mức xám thuộc khoảng đã chọn.Cũng cần lưu ý thêm rằng, ảnh gốc có thể gồm có đường bao và các kết cấu (texture).Trong miền texture, độ xám biến đổi rất chậm.Do vậy, nếu không chú ý sẽ chia ảnh thành quá nhiều miền và gây nên các bao giả.Giải pháp để khắc phục hiện tượng này là dùng một bộ lọc thích hợp hay lọc trung vị. Sau giai đoạn này, ta thu được ảnh phân đoạn với các đường biên kín, độ rộng 1 pixel.Để loại bỏ các đường bao giả, ta có thể dùng phương pháp gradient .Sau khi đã thu được các đường bao đúng, người ta tiến hành mã hoá (xấp xỉ) đường bao bởi các đường cong hình học, thí dụ bởi các đoạn thẳng hay đường cong.Nếu ảnh gốc có độ phân giải không thích hợp, người ta dùng khoảng 1.3 bit cho một điểm biên. Phương pháp này thể hiện ưu điểm: đó là mô hình tham số.Các tham số ở đây là số vùng, độ chính xác mô tả.Tất nhiên tham số khoảng mức xám là quan trọng nhất vì nó có ảnh hưởng đến tỷ số nén.Một tham số cũng không kém phần quan trọng là số điểm của các đường bao bị coi là giả.Thường số điểm này không vượt quá 20 điểm. Phương pháp tách - hợp Cũng như đã chỉ ra trong chương Sáu, phương pháp tách-hợp khắc phục được một số nhược điểm của phương pháp phân vùng dựa vào tách vùng hay hợp vùng.Trong phương pháp mã hoá này, người ta thay tiêu chuẩn chọn vùng đơn giản ở trên bằng một tiêu chuẩn khác hiệu quả hơn. Nguyên tắc chung của phương pháp là theo mô hình biên - texture.Nhìn chung đường biên dễ nhạy cảm với mắt người, còn texture thì ít nhạy cảm hơn.Người ta mong muốn rằng đường phân ranh giữa các vùng là đồng nhất với các đường bao.Lưu ý rằng, cần quyết định phân vùng một phần của ảnh sao cho nó không được vắt chéo đường bao.Đây là một tiêu chuẩn kiểm tra quan trọng.Các đường bao thường nhận được bởi các bộ lọc thông cao, đẳng hướng. Để có thể quản lý các điểm thuộc một vùng một cách tốt hơn, tiêu chuẩn kiểm tra thứ hai cũng được xem xét đó là dấu: " các điểm nằm về một phía của đường bao có cùng dấu". Nhìn chung, phương pháp gồm 2 giai đoạn.Giai đoạn đầu thực hiện việc tách vùng.Giai đoạn sau thực hiện hợp vùng. Quá trình tách thực hiện trước.Người ta chia ảnh gốc thành các vùng nhỏ kích thước 9 x 9.Tiếp theo, tiến hành xấp xỉ các vùng ảnh đó bằng một đa thức có bậc nhỏ hơn 3.Sau quá trình tách, ta thu được trong một số vùng của ảnh, các hình vuông liên tiếp.Chúng sẽ tạo nên một miền gốc lớn và không nhất thiết vuông.Như vậy, trong trường hợp này phải xấp xỉ bằng rất nhiều các đa thức giống nhau.Rõ ràng là việc mã hoá riêng biệt các đa thức là điều kém hiệu quả và người ta nghĩ đến hợp các vùng để giảm độ dư thừa này. Quá trình hợp được tiến hành như sau: Nếu 2 vùng có thể xấp xỉ bởi 2 đa thức tương tự, người ta hợp chúng làm một và chỉ dùng một đa thức xấp xỉ.Nếu mức độ thay đổi là thấp, ta sẽ có nhiều cặp vùng tương tự.Để có thể nhận được kết quả không phụ thuộc vào lần hợp đầu, người ta xây dựng đồ thị "Vùng kế cận".Các nút của đồ thị này là các vùng và các liên hệ biểu diễn mối không tương đồng.Sự liên hệ với mức không tương đồng thấp chỉ ra rằng 2 vùng cần hợp lại. Sau bước hợp này, đồ thị được cập nhật lại và quá trình hợp được lặp lại cho đến khi tiêu chuẩn là thoả.Quá trình hợp dừng có thể quyết định bởi chất lượng ảnh nén hay một tiêu chuẩn nào khác. Ta có thể thấy rằng phương pháp này khá phức tạp song bù lại nó cho tỷ số nén khá cao: 60 trên 1 Chương 3: TỔNG QUAN VỀ VIDEO Dữ liệu video số bao gồm hình ảnh và âm thanh video được lưu trữ trong máy tính dưới dạng số.Cấu trúc phân cấp của video file như sau: Hình 3.1 - Cấu trúc phân cấp của Video 3.1 Tổng quan về video Video là tập hợp các khung hình, mỗi khung hình là một ảnh.Shot (lia) là cơ sở của video.Một lia là một đơn vị vật lý của dòng video, gồm các chuỗi các khung hình liên tiếp, không thể chia nhỏ hơn, ứng với một thao tác camera đơn. Scene (cảnh) là các đơn vị logic của dòng video, một cảnh gồm các lia liên quan về không gian và liền kề về thời gian, cùng mô tả một nội dung ngữ nghĩa hoặc một tình tiết. Khi phim được chiếu, các khung hình lần lượt được hiển thị ở tốc độ nhất định.Tốc độ thường thấy ở các định dạng video khác nhau là 30 và 25 hình/s.Như vậy một giờ video sẽ có số khung hình tương ứng là 108000 hoặc là 90000.Dù là video ở định dạng nào thì nó cũng có dung lượng rất lớn và nếu xử lý với tất cả các khung hình thì hiệu quả không cao. Phân đoạn là quá trình phân tích và chia nội dung hình ảnh video thành đơn vị cơ sở gọi là các lia (shot).Việc lấy mẫu chính là chọn gần đúng một khung video đại diện cho mỗi lia (hoặc nhiều hơn tùy theo mức độ phức tạp của nội dung hình ảnh của lia) và được gọi là khung-khóa. Khung-khóa là khung hình đại diện mô tả nội dung chính của shot. Quá trình phân đoạn dữ liệu video tiến hành phân tích, phát hiện sự chuyển đổi từ lia này sang lia khác hay chính là sự phát hiện danh giới giữa các lia (đó chính là đo sự khác nhau giữa các khung hình liền kề). 3.2 Một số thuộc tính đặc trưng của video Video có bốn đặc trưng chính: Color (màu), texture (kết cấu), shape (hình dáng), motion (chuyển động). 3.2.1 Color Màu là một thuộc tính quan trọng của ảnh.Biểu đồ màu, biểu diễn sự phân bố màu, là một đặc trưng màu phổ biến nhất hiện nay.Biểu đồ màu không phụ thuộc vào sự quay, dịch chuyển ảnh cũng như chiều nhìn ảnh.Tính hiệu quả của nó lại phụ thuộc vào hệ màu và phương pháp định lượng được dùng.Có một vấn đề với biểu đồ màu là nó không biểu diễn thông tin về không gian phân bố các điểm ảnh, do đó hai ảnh có cùng biểu đồ màu có thể có nội dung rất khác nhau. Hình 3.2 - Các ảnh rất khác nhau nhưng có cùng biểu đồ màu 3.2.2 Texture Đây là một đặc trưng quan trọng của bề mặt, nơi xảy ra việc lặp lại mẫu cơ bản.Có hai dạng biểu diễn texture phổ biển: biểu diễn dạng ma trận đồng thời và biểu diễn Tamura.Ma trận đồng thời mô tả hướng và khoảng cách giữa các điểm ảnh, nhờ đó các thống kê có nghĩa có thể được trích chọn.Ngược lại, người ta thấy rằng entropi và mô men chênh lệch nghịch đảo lại có khả năng phân biệt tốt nhất.Biểu diễn Tamura được thúc đẩy nhờ các nghiên cứu về tâm lý trong việc thu nhận trực giác của con người và nó bao gồm các đại lượng đo tính thô, độ tương phản, hướng, tính trơn, tính cân đối và độ ráp.Các đặc trưng Tamura rất hấp dẫn trong việc hiểu nội dung ảnh vì nó biểu đạt trực quan.Ngoài ra còn có một số các dạng biểu diễn khác như trường ngẫu nhiên Markov, biến đổi Gabor, biến đổi gợn sóng,… 3.2.3 Shape Các đặc trưng hình dáng có thể được biểu diễn sử dụng phân tích hình dáng truyền thống như bất biến mô men, mô tả Fourier, mô hình học tự động quay lui và các thuộc tính hình học.Các đặc trưng này có thể được phân chia thành đặc trưng toàn cục và đặc trưng cục bộ.Đặc trưng toàn cục là đặc trưng thuộc tính thu được từ toàn bộ hình dáng ảnh, chẳng hạn như chu vi, tính tròn, mô men trung tâm, hướng trục chính...Đặc trưng cục bộ là đặc trưng thu được từ việc thao tác với một phần của ảnh, không phụ thuộc vào toàn bộ ảnh. 3.2.4 Motion Hình 3.3 - Các thao tác camera Motion là thuộc tính quan trọng của video.Thông tin về chuyển động có thể được sinh ra bằng các kỹ thuật ghép khối hoặc luồng ánh sáng.Các đặc trưng chuyển động như mô men của trường chuyển động, biểu đồ chuyển động hoặc là các tham số chuyển động toàn cục có thể được trích chọn từ vectơ chuyển động.Các đặc trưng mức cao phản ánh di chuyển camera như quét camera (pan), nghiêng (tilt), phóng to (zoom in), thu nhỏ (zoom out) cũng có thể được chọn. Chương 4: CÁC PHƯƠNG PHÁP XÁC ĐỊNH ĐỘ ĐO TƯƠNG TỰ TRONG XỬ LÝ ẢNH 4.1 Giới thiệu Trong thời gian qua một số lượng rất lớn các thư viện số đã được xây dựng nhờ vào giá thấp của các thiết bị lưu trữ số và sự tăng trưởng mau lẹ của công nghệ thông tin.Để sử dụng hiệu quả hệ thống thư viện đồ sộ này cần thiết phải xây dưng các công cụ đủ mạnh để tìm kiếm và phân tích.Hệ thống tự động nhận về ảnh từ một cơ sở dữ liệu bằng việc sử dụng các miêu tả bằng văn bản đã được phát triển từ những năm 1970.Những hệ thống này sử dụng đặc trưng ảnh cấp thấp như màu sắc, hình dạng và texture để biểu diễn nội dung ảnh.Ngoài ra, chuẩn MPEG-7 định nghĩa một tập hợp các mô tả trực quan cho nội dung ảnh nhằm đáp ứng yêu cầu của các ứng dụng khác. Nhiều nghiên cứu đã được tiến hành trên cơ sở đặc trưng màu, ký thuật phổ biến nhất để biểu diễn các thông tin màu là histogram.Rất nhiều độ đo tương tự đã được đưa ra trong các tài liệu để so sánh phân bố màu sắc, giống như histogram intersection, L2-norm color histogram.Hơn nữa, nhiều đặc trưng màu khác cũng đã được sử dụng để mô tả màu sắc, bao bao gồm color moment và color sets. 4.2 Phương pháp Histogram dòng, cột Đây là một trong các phương pháp đơn giản nhất để xác định độ đo tương tự giữa hai ảnh mà sử dụng các đặc trưng về màu sắc. Phương pháp thực hiện như sau: trên từng dòng (cột) tương ứng của hai ảnh đầu vào, thực hiện xác định một hàm phân bố màu sắc cho dòng (cột) đó, tiếp theo tiến hành so sánh hai hàm đó với nhau kết quả thu được là một hệ số tương quan tương ứng cho dòng (cột).Trên cơ sở các hệ số tương quan của dòng (cột) thu được thực hiện phân tích và đánh giá để đi đến kết quả cuối cùng là rút ra được một độ đo tương tự cho hai ảnh đầu vào, phương pháp đơn giản nhất là lấy hai giá trị trung bình cộng tất cả các độ tương quan thu được trên dòng và cột sau đó xử lý theo một tỉ lệ xác định (thường là theo kích thước của ảnh) để thu về kết quả là độ đo tương tự cần tìm. Thuật toán để xác định Histogram theo dòng (cột): HisRow[ImageHeight][255] = [0]; //giả sử ảnh là ảnh xám. For ( i = 0; i < ImageHeight; i++) For ( j = 0; j < ImageWidth; j++) { HisRow[i][I(i,j)] ++; //I(i,j) là giá trị màu của pixel ở vị trí (i,j) } Đây là một phương pháp dựa trên đặc trưng hết sức cơ bản của ảnh số đó là đặc trưng màu, do đó nó đáp ứng được yêu cầu về độ chính xác trên phương diện màu sắc.Ưu điểm lớn nhất của phương pháp này là dễ cài đặt, dễ hiểu phù hợp cho các tìm hiểu ban đầu về vấn đề xác định độ đo tương tự giữa hai ảnh số.Tuy nhiên nó có một nhược điểm là có độ chính xác không cao mà trong nhiều trường hợp kết quả thu được không thể đánh giá được một các trực quan (đây là điều kiện tiên quyết trong thao tác với ảnh số) .Việc cài đặt phương pháp này trong các ứng dụng là hết sức dễ dàng, chính vì lẽ đó nên nó được được khai thác và sử dụng trong các ứng dụng xử lý ảnh từ rất lâu.Trong giai đoạn hiện nay với sự phát triển mạnh mẽ của xử lý ảnh cũng như sự hỗ trợ mạnh mẽ của các thiết bị tiên tiến phương pháp này đã trở nên ko còn phù hợp nữa, nó đòi hỏi phải có một phương pháp phức tạp hơn và đem lại độ chính xác cao hơn. 4.3 Mô hình Cognitive Visual Attention (CVA) Mô hình Cognitive Visual Attention (CVA) được mô tả ở đây là một cải tiến mới nhất của mô hình Visual Attention (được đưa ra bởi F.W.M.Stentiford) dựa vào độ tương tự của các cặp láng giềng của hai mẫu A và B.Phương pháp so sánh ở đây hết sức đơn giản và linh hoạt, không phụ thuộc vào một đặc trưng cụ thể nào do đó có thể áp dụng cho rất nhiều cơ sở dữ liệu ảnh khác nhau. Xét một tập hợp a trên mẫu A tương ứng với một vị trí x trong A trong không gian n chiều (x1,x2,x3,…,xn), trong đó: x = (x1,x2,x3,…,xn) và a = (a1,a2,a3,…,an) Định nghĩa một hàm F sao cho a = F(x) với mọi a.Điều đó có nghĩa là x chỉ tồn tại nếu a tồn tại. Xác định một tập láng giềng Nx của x sao cho: {x’ Î Nx nếu |xi – xi’| > e " i} Chọn một tập hợp m pixel ngẫu nhiên Sx trong Nx sao cho: SA = {x’1,x’2,x’3,…,x’m} và F(x’i) phải được định nghĩa Chọn một vị trí y tương tứng là tập b trên mẫu B mà hàm F đã được định nghĩa sao cho thỏa mãn điều kiện sau: |xi – yi| ≤ s Sau đó chọn ngẫu nhiên một tập hợp SB = {y’1, y’2,y’3,…,y’n} sao cho: x – x’i = y – y’i " i Khi đó gọi SA tương tự SB nếu |Fj(x) – Fj(y)| ≤ dj và |Fj(xi) – Fj(x’i)| ≤ dj " i,j Hình 4.1 - Tập hàng xóm ở vị trí x giống với vị trí y Như vậy, sẽ xác định một tương tự nếu tất cả các giá trị màu (giá trị j) của các pixel tương ứng trong SA và SB là gần nhau.Độ tương tự của một pixel x được tăng lên mỗi lần một trong M tập SA tương ứng với một tập SB của một vài điểm y trên mẫu B.Điều đó có nghĩa là độ tương tự này sẽ rất lớn nếu M được đặt giá trị lớn.Trong hình 1, m = 3 pixel x’ được chọn trong tập láng giềng của x trên mẫu A và tượng tự trên mẫu B cũng xác định được 3 pixel y’ là láng giềng của y trên mẫu B.Các pixel phải xử lý 3 tham số, mà F(x’) = a = (r, g, b) và hàng xóm của pixel thứ hai (y) tương ứng với pixel thứ nhất nếu các tham số màu của toàn bộ m + 1 pixel tương ứng có giá trị nhỏ hơn từng dj. Cuối cùng, gộp tất cả độ tương tự từ tất cả các điểm ảnh trong A được xác định là CAB giữa 2 ảnh A và B qua công thức: Một tham số s được đưa ra để giới hạn vùng trên B mà trong đó các vị trí của y được lựa chọn ngẫu nhiên. s = 3 định nghĩa vùng này ở ví dụ trên.Điều này đã làm cải thiện rất nhiều hiệu quả của thuật toán trong những trường hợp mà ta biết chắc rằng sự tương ứng giữa 2 vùng ảnh được dịch chuyển đi không nhiều hơn s pixel. Một vài kỹ thuật phân tích ảnh thực hiện các phép toán so sánh ảnh bằng việc sử dụng các “mảnh” (patche) đó là các láng giềng kề nhau trong đó các giá trị (values) của các pixel được tận dụng trong tính toán.Các “mảnh” là tương ứng khi độ tượng tự vượt qua một ngưỡng cho trước.Hướng tiếp cận này không thể đem lại độ chính xác cao trong trường hợp các chi tiết ảnh nhỏ hơn kích thước của các “mảnh”.Việc chọn lựa các láng giềng một cách ngẫu nhiên như trong phương pháp này có thể khắc phục được vấn đề này. 4.4 Độ đo tương tự có thể học (Trainable similarity measure) Đầu tiên, độ đo tương tự Sr(I, J) được xác định dựa trên việc tính toán hệ số tương quan giữa 2 ảnh cùng kích thước I và J: Trong đó, ký hiệu và biểu diễn cường độ của pixel thứ i tương ứng của các ảnh và và biểu diễn giá trị trung bình tương ứng của các cường độ của ảnh. Độ tương tự S(I, J, R) được đề nghị dựa trên sự tương xứng cục bộ của ảnh trong tập hợp các vùng ảnh R.Mỗi vùng ảnh r Î R được định nghĩa trong hệ tọa độ của ảnh I.Độ tương tự cục bộ s(I, J, r) giữa các vùng ảnh tương ứng r(I) và r(J) có thể được xác định, chẳng hạn, theo hệ số tương quan (3.1).Độ tương tự tổng thể S(I, J, R) la một hàm của tập hợp các độ tương tự cục bộ của các vùng r.Ở đây, để làm tăng tính chính xác của độ đo tương tự tổng thể trước các sai lệch cục bộ chúng ta sử dụng một điều kiện số học (arithmetic mean): Tập hợp các vùng R được xác định cụ thể đối với mỗi nguyên mẫu (prototype) trong suốt quá trịnh học tương ứng với tập dữ liệu Tr = {(I1, w(I1)), … , (IN, w(IN))} với N ảnh, với w(I) biểu diến một lớp của ảnh I. Quá trình học độ đo tương tự với đối với một ảnh nguyên mẫu (prototype image) Pr như sau: bắt đầu từ một tập hợp các vùng có thể chấp nhận Rinit , một tập con R được chọn tùy ý theo tính dễ phân tách (separability) của lớp (class) của đối tượng nguyễn mẫu (prototype object) w(Pr) từ tất cả các lớp liên quan trong tập Tr.Tính dễ phân tách tiêu chuẩn được chấp nhận là: Sự tách biệt giữa các đối tượng học (training object) mục tiêu (target) và không mục tiêu (non-target) dựa trên độ tương tự S(I, Pr, R).Các ký hiệu T và NT biể diễn tập hợp của đối tượng học mục tiêu và không mục tiêu: Ký hiệu và biểu diễn điều kiện mean và sự sai khác của giá trị tương tự S(Ii, Pr, R), Ii Î T (S(Ij, Pr, R), Ij Î NT). 4.5 Multivariate Two-sample problem Nghiên cứu này sử dụng một phương pháp kiểm tra không tham số kết hợp với “Multivariate Tow-Sampe Problem” để biểu diễn màu sắc ảnh tương tự.Phương pháp test cụ thể là phương pháp kiểm tra Wald-Wolfowitz và so sánh hai ảnh mẫu phân biệt dựa trên việc sử dụng MST (Minimal Spanning Tree) – cây khung nhỏ nhất. Định nghĩa: một đồ thị (graph) là một cấu trúc biểu diễn liện hệ dữa các dữ kiện với nhau.Bao gồm tập hợp các node V={Vi}i=1:N và tập hợp các liên kết E={Eij}i≠j giữa các node gọi là các cung, độ đo di của một node la số lượng các cung nối với node đó.Khi đó một trọng số eij được gán cho mỗi cung, trong trường hợp đồ thị vô hướng thì eij = eji .Một cây (tree) là một đồ thị không có kết nối vòng tròn.Một spanning tree T của một đồ thị trọng số G(V,E) được kết nối từ các đồ thị con G(V,E) sao cho: (i) chứa tất cả các node của G(V,E) và (ii) không chứa vòng.MST là một cây khung chứa (N-1) cung, sao cho tổng trọng số các cung là nhỏ nhất. Áp dụng định nghĩa trên để mô tả màu của một ảnh : N pixel được chọn và trêm cơ sở tương ứng với vector RGB những pixel này được biểu diễn bằng 1 điểm trong R3.Từng điểm này sau đó được thể hiện như là một node của đồ thì gốc (kết nối đầy đủ), và khoảng cách Euclidean được tính cho trọng số tướng ứng cho các cung. Cuối cùng, sử dụng một thuật toán chuẩn để xây dựng lên MST và dùng như một mô tả chính xác của biến đổi màu trong ảnh.Như vậy với 2 ảnh ban đầu, sự khác nhau về nội dung màu của chúng sẽ được biến đổi thành so sánh 2 đồ thị MST tương ứng.Quá trình so sánh sẽ đánh giá dựa trên một hằng số xác định.Phương pháp kiểm tra Walt-Wolfowitz (WW-test) đề xuất sử dụng một hằng số R như sau: trong đó : + m, n : kích thước của ảnh so sánh. + N = m + n + C : số các cung trong cây MST Hình 4.2 - WW-test sử dụng 15+15 pixel được chọn (a) hai ảnh bất tương tự với R = 4 (b) hai ảnh tương tự R = 11 Chương 5: PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG 5.1 Phân tích 5.1.1 Đặt vấn đề Bài toán “tìm kiếm theo nội trong file video” được mô tả như sau: cho trước một file video chứa đựng hình ảnh cũng như hoạt động của các đối tượng (bao gồm cả con người, đồ vật, phương tiện....), với một dữ liệu đầu vào là một đối tượng xác định, đối tượng có thể được mô tả bằng nhiều cách có thể là hình ảnh về đối tượng hay những mô tả về các đặc điểm của đối tượng bằng văn bản....Yêu cầu là phải tìm trong đoạn video đó đối tượng xuất hiện ở những frame nào với một độ chính xác (ngưỡng) cho trước. Bài toán có thể được mô hình hóa như sau: Đoạn Video đối tượng Tìm kiếm Frame đối tượng Hình 5.1 - Mô hình bài toán 5.1.2 Phân tích bài toán Nếu nhìn nhận bài toán ở khía cạnh con người thì có thể thấy đây là một bài toán không có gì là phức tạp, rõ ràng việc nhận biết một đối tượng trong các đoạn video đối với mắt người là hết sức đơn giản.Con người nhận biết đối tượng nhờ vào tri thức của họ về đối tượng đó, các định nghĩa được hình thành trong trí óc con người khi họ tiếp xúc với đối tượng lần đầu tiên và được củng cố trong những lần tiếp xúc sau. Khi có yêu cầu tìm kiếm đối tượng nào đó, con người sẽ hình dung trong đầu các đặc trưng của đối tượng (hình dáng, màu sắc, kích thước ...), cuối cùng khi duyệt qua nơi tìm kiếm họ chỉ việc tiến hành đối sánh các đối tượng thu được với đối tượng cần tìm (đã hình dung trong đầu) để đưa ra kết luận. Tương tự như vậy, hướng giải quyết bài toán cũng thực hiện theo quy trình: nhận thức đối tượng, tiến hành so sánh đối tượng đó với các đối tượng xác định được trong đoạn video (từng frame). Ở đây có hai vấn đề lớn cần giải quyết đó là nhận thức đối tượng và so sánh đối tượng.Nhận thức đối tượng quá trình tìm hiểu các thông tin về đối tượng bao gồm các đặc trưng về màu, về hình dáng, kết cấu v.v...để cuối cùng hình thành lên một định nghĩa chính xác về đối tượng đó giúp phân biệt với các đối tượng khác sao cho bảo đảm tính cá biết của đối tượng.Ví dụ như đối tượng là một bông hoa về mặt hình dáng thường bao gồm một đoạn dài (cuống) nằm trên là một vòng tròn (cánh hoa), kết hợp với đó là màu xanh của cuống và các màu đỏ, vàng của cánh hoa v..v...quá trình này phải được thực hiện hết sức cẩn thận vì rất dễ xảy ra hiện tượng nhầm lẫn hay hiểu sai về đối tượng, lý do là đối tượng thường được lồng ghép bởi rất nhiều chi tiết, đôi khi các đối tượng khác nhau lại chứa đựng các chi tiết giống nhau hoặc bản thân các chi tiết đó cũng không được phân biệt rõ ràng.Tiếp theo, sau khi đã nhận thức được đối tượng chúng ta tiến hành so sánh các đối tượng với nhau, chính vì lý do là đối tượng có rất nhiều thông tin nên vấn đề só sanh các đối tượng trở nên rất khó khăn. Nếu chỉ dựa vào một thông tin nào đó về đối tượng để so sánh rồi đưa ra đánh giá đối tượng đó có giống nhau hay không thì kết quả đem lại sẽ có tỉ lệ thất bại rất cao.Đối tượng tương tự nhau về thông tin này chưa chắc đã giống nhau về mặt thông tin khác đôi khi có thể khác nhau hoàn toàn.Ví dụ như sử dụng phương pháp so sánh dựa trên đặc trưng về màu sẽ đem lại một kết quả sai lệch hoàn toàn trong trường hợp hai đối tượng có hình dáng và kết cấu giống nhau trong khi phân bố màu sắc lại có nhiều nét tương đồng...Vì vậy, cần phải có một phương pháp so sánh sao cho kết hợp được tất cả các thông tin đó lại với nhau nhằm thu được những kết luận với sai số cho phép. Một vấn đề hết sức quan trọng khác trong bài toán này đó là vấn đề xác định ngưỡng.Đây là một yếu tố có ảnh hưởng trực tiếp đến hiệu quả của quá trình tìm kiếm.Nếu ngưỡng được chọn lựa phù hợp thì không những làm tăng hiệu suất của quá trình tìm kiếm mà còn giảm rất nhiều các chi phí không cần thiết phát sinh trong quá trình tìm kiếm.Ngưỡng ở đây không phải là một con số cố định, hoặc có thể rút ra chung cho tất cả các bài toán thuộc lớp này, ngưỡng phải được xác định tùy theo từng điều kiện cụ thể của mỗi bài toán, ngưỡng được quyết định bởi bản thân đối tượng tìm kiếm (về kích thước, màu sắc, phân bố kết cấu...) và bản thân đoạn video, nếu đoạn video có chất lượng cao đảm bảo khả năng tìm kiếm đối tượng với độ chính xác cao thì ngưỡng có thể được đẩy lên cao, nhưng ngược lại với các đoạn video chất lượng thấp hoặc chịu ảnh hưởng rất nhiều của nhiễu môi trường không thể kiểm soát thì ngưỡng cần phải được đẩy xuống. Như vậy lại có một vấn đề mới đặt ra trong trường hợp này là nếu ngưỡng bị đẩy xuống thấp quá rất dễ gây hiểu lầm, có nghĩa là quá trình tìm kiếm đã chở nên bớt khắt khe hơn, khi đó đối tượng được coi là giống nhau đã không được kiểm soát kỹ làm cho kết quả thu về có thể không theo được mong muốn, trường hợp nảy chỉ có thể đáp ứng được tính đủ của quá trình tìm kiếm nhưng lại gây lên sự dư thừa thông tin.Để giải quyết vấn đề này cần phải có thêm sự kết hợp của một số ký thuật hỗ trợ khác chẳng hạn như lọc nhiễu trước khi xử lý, hoặc phối hợp hỗ trợ của con người. 5.2 Kỹ thuật đề xuất Theo như các phân tích ở trên thì kỹ thuật để xử lý bài toán cần phải đáp ứng được các yếu tố: phải đảm bảo quá trình so sánh đối tượng phải được thực hiện trên toàn bộ các thông tin đặc trưng của đối tượng nhằm tránh hiểu sai, tìm thiếu đối tượng; phải có một phương pháp chọn ngưỡng phù hợp để làm tăng tính khả dụng của ngưỡng qua đó làm tăng hiệu suất của quá trình; ngoài ra còn phải phù hợp với điều kiện kỹ thuật hiện này về phần cứng cũng như các điều kiện về mặt thời gian. Có rất nhiều kỹ thuật đã được nghiên cứu, mỗi kỹ thuật lại phù hợp với từng bài toán cụ thể chẳng hạn như kỹ thuật dùng histogram, kỹ thuật phát hiện đối tượng trên cơ sở phát hiện biên, ký thuật sử dụng mạng noron, kỹ thuật trừ nền, kỹ thuật phân hoạch dựa vào không gian.... Trong khuôn khổ của đồ án tốt nghiệp này, em xin mạnh dạn đề xuất một kỹ thuật khá mới đó là kỹ thuật tìm kiềm đối tượng trên cơ sở xác định độ đo tương tự có tên là mô hình Cognitive Visual Attention (CVA) kết hợp với định hướng của kỹ thuật Histogram dòng, cột. Việc kết hợp giữa 2 phương pháp này nhằm tận dụng các ưu điểm của từng phương pháp nhằm hạn chế các nhược điểm nếu sử dụng từng kỹ thuật, trong đó mô hình CVA giữ vai trò chủ đạo, quyết định đến thành công của bài toán. Đây là một kỹ thuật được sử dụng khá nhiều trong giai đoạn gần đây đặc biệt đã được áp dụng trong lĩnh vực truy tìm dấu vân tay trong điều tra tội phạm. Kỹ thuật này có thể được môt tả ngắn gọn lại như sau: có hai vùng ảnh A, B cần đem so sánh với nhau.Với mỗi pixel x trên ảnh A chọn ra một tập ngẫu nhiên n láng giềng Sx nằm trong vùng láng giềng e, để so sánh với x trên B cũng chọn ngẫu nhiên các điểm y tương ứng cùng với vùng láng giềng của nó Sy sau tiến hành so sanh 2 vùng láng giềng này cho nhau theo một ngưỡng d nào đó.Kết quả của phép so sánh A, B thu được qua quá trình tính toán như trên với một số lượng đủ lớn pixel x trong A (chi tiết xin xem thêm phần 4.2). Kỹ thuật này có thể được coi là kỹ thuật dựa trên láng giềng, đây là một yếu tố hết sức quan trọng đảm bảo thành công của nó, lý do là việc sử dụng láng giềng đảm bảo việc nhìn nhận từng pixel trong mối quan hệ của nó với các pixel xung quanh. a) b) c) Hình 5.2 - pixel x và các tập láng giềng a) Láng giềng bốn b)Láng giềng c) Láng giềng xa (e = 2) Khái niệm láng giềng của một pixel x trong ảnh số được định nghĩa là: tập hợp các pixel nằm xung quanh pixel p theo một khoảng cách e nhất định.Trong đó tập láng giềng với e = 1 là được sử dụng nhiều nhất, đây là tập hợp chứa các láng giềng nằm ngay gần kề mang ý nghĩa quyết định nhất tới khả năng ảnh hưởng của láng giềng tới pixel trung tâm (pixel p).Trong xử lý ảnh cũng chia tập này thành 2 tập con là láng giềng 4 và láng giềng 8 được định nghĩa như sau: nếu pixel p có vị trí là (x,y) trong ảnh thì láng giềng 4 là tập hợp các pixel {(x-1,y-1), (x-1,y+1), (x+1,y+1), (x+1,y-1)} và láng giềng 8 là tập hợp các pixel {(x-1,y-1), (x-1,y), (x-1, y +1), (x,y-1), (x,y+1), (x+1,y-1),(x+1,y),(x+1,y+1)}. Trong kỹ thuật này để nâng cao hiệu suất của quá trình, tập láng giềng với e > 1 đã được đề xuất sử dụng, với e bất kỳ thì số lượng các pixel láng giềng trong tập láng giềng N sẽ là: ||N|| = (2*e + 1)2 Tuy nhiên, nếu sử dụng toàn bộ tập láng giềng N mà với e đủ lớn sẽ có thể làm tràn bộ nhớ trong quá trình tính toán gây lãng phí.Do vậy, kỹ thuật này đã đề xuất một cải tiến, đó các láng giềng cũng được lựa chọn ngẫu nhiên một tập hợp nào đó (chứ không phải toàn bộ tập các láng giềng bao xung quan pixel đang xét), tự quá trình này đã xây dựng lên một cấu trúc các pixel dùng cho so sánh một pixel mà lại rất riêng, ngâu nhiên và hết sức khách quan kết hợp với việc lựa chọn độ lớn của tập hợp các láng giềng này cũng giúp đẩy mạnh tính hiệu quả của kỹ thuật. Hình 5.3 - lựa chọn ngẫu nhiên một số các láng giềng trong tập láng giềng với e = 2 Hai pixel x và y khi đã có sự tương quan xác định về hai tập láng giềng Sx và Sy có nghĩa là chúng đã bao hàm được một phần cấu trúc của đối tượng đang so sánh như vậy giúp đảm bảo tính cấu trúc của đối tượng được so sánh, bên cạnh sự đảm bảo chính xác về giá trị màu. Image A Image B s Hình 5.4 - đối tượng ở ảnh A đã được dịch chuyển đi s pixel trong ảnh B Kỹ thuật này cũng đề suất việc sử dụng một tham số s, tham gia trong quá trình chọn lựa pixel y tương ứng cho pixel x.Tham số s thể hiện độ dịch chuyển của các pixel tương ứng có thể có giữa 2 vùng ảnh A, B, ở đây đã có một sự đoán nhận dựa trên kinh nghiệm nghĩa là bằng kinh nghiệm, trước khi sử dụng kỹ thuật này người ta đã dự đoán rằng đối tượng trong B sẽ chỉ có thể bị dịch chuyển đi s pixel, do vậy quá trình so sánh tiếp theo cần thiết chỉ lên tiến hành trong một độ lệch đề nghị là s pixel. Đây là một yếu tố có ý nghĩa cực kỳ quan trọng làm tăng rất nhiều hiệu quả cũng như tốc độ của quá trình tính toán mà thêm vào đó nó còn thể hiện tính tri thức của kỹ thuật.Để trợ giúp quá trình so sánh, nâng cao hiệu quả của ký thuật hằng số d đã được sử dụng khi thực hiện so sánh hai tập láng giềng Sx và Sy sao cho: |Sx – Sy| < d nghĩa hai tập láng giềng này để được coi là giống nhau thì từng pixel trong độ phải có độ khác biệt về màu sắc nhỏ hơn d (nếu là ảnh 24 bit thì từng giá trị r,g,b phải được so sánh riêng biệt và tương ứng có một giá trị d riêng). Dưới đây là một ví dụ của việc ứng dụng mô hình CVA trong lĩnh vực truy tìm vân tay, với các tham số là : e = 2 , M = 50, m = 3, s = 5, d = 20 Hình 5.5 - mẫu ảnh của 9 vân tay Kết quả tính toán của quá trình áp dụng mô hình CVA cho 9 mẫu trên được mô tả trên bảng sau: Hình 5.6 – độ đo tương tự giữa cá mẫu trong tập hợp 9 vân tay 5.3 Thiết kế hệ thống Với các phân tích như trên hệ thống “tìm kiếm đối tượng trong file video” sẽ được thiết kế như sau: Hoạt động: Input: file avi, đối tượng cần tìm kiếm, ngưỡng Output: các frame có chứa các đối tượng giống đối tượng cho trước Về cơ bản thuật toán của hệ thống sẽ được mô tả theo như lưu đồ sau: Bắt đầu Duyệt hết các frame Kết thúc yes yes no no - File video - Đối tượng cần tìm - Ngưỡng Duyệt lần lượt các frame trong đoạn video Thêm frame vào danh sách kết quả Phân tích histogram dòng cột Xác định độ đo tượng tự theo mô hình CVA So sánh với ngưỡng Các bước thực hiện thuật toán: Bước 1: - Đọc file video đầu vào. - Đọc ảnh chứa đối tượng. - Chọn đối tượng cần tìm kiếm. - Lựa chọn các tham số cho mô hình CVA. - Đề xuất ngưỡng. Bước 2: - Duyệt qua từng frame của file video. - Với mỗi frame thực hiện phân vùng, chọn vùng chứa đối tượng. Bước 3: - Tiến hành phân tích histogram, so sánh với đối tượng truy vấn. - Nếu đáp ứng được ngưỡng cho trước => đưa đối tượng vào tập đối tượng ứng viên và ngược lại. Bước 4: - Trong tập các đối tượng ứng viên thực hiện phân tích so sánh với ảnh truy vấn theo mô hình CVA. - Xác định độ đo tương tự và so sánh với ngưỡng. - Cơ chế điều chình ngưỡng . - Kết nạp frame hiện tại vào tập frame kết quả nếu đáp ứng được ngưỡng và ngược lại. Bước 5: - Thu được tập kết quả. - Kết hợp với đánh giá của người sử dụng để rút ra các điều chình cần thiết. Một số điều kiện tiền đề trong trường hợp của đồ án: + Dữ liệu đầu vào sẽ là một file video và một file ảnh, yêu cầu phải có kích thước giống nhau.File ảnh có thể chính là một frame trong file video, điều này đảm bảo chất lượng của file video và chất lượng ảnh đầu vào là như nhau, đáp ứng tính đồng nhất của dữ liệu đầu vào.Hơn nữa nó còn cho phép đảm bảo rằng ít nhất trong kết quả trả về của hệ thống phải chứa chính frame được trích ra đó, đây cũng là một cơ sở để tạo ngưỡng đề nghị. + Sau khi đã có một ảnh đầu vào, hệ thống phải cho phép người sử dụng chọn lựa các đối tượng trong đó một cách tùy ý, đương nhiên vùng mà ngưởi sử dụng chọn ra đó phải chứa ít nhất một đối tượng , hơn nữa phải chọn sao cho tầm ảnh hưởng của nền trong vùng đó là nhỏ nhất, nghĩa là đối tượng phải chiếm đa số trong vùng đó.Ngoài ra đối tượng cũng phải được chọn sao cho về màu sắc đối tượng phải đặc biệt nổi bật so với nền mà đối tượng nằm trên đó nghĩa là phải có được một sự phân biệt rõ ràng giữa các pixel trong ảnh thuộc về vật với các pixel thuộc về nền.Nếu không làm tốt vấn đề này có thể sẽ dẫn đến hậu quả là thay vì thực hiện tìm kiếm đối tượng hệ thông sẽ bị chuyển hướng lạm dụng sang thực hiện với nền.Điều này sẽ làm sụp đổ hoàn toàn hoạt động của hệ thống. Hình 5.7 – khoanh vùng đối tượng + Đặc thù của file video là một chuỗi các khung hình diễn ra liên tiếp có mối liên hệ với nhau về mặt nội dung theo các dòng sự kiện diễn biến theo thời gian.Mỗi dòng sự kiện đó sẽ ánh xạ thành một phân đoạn của file video.Trong từng phân đoạn đó, các đối tượng xuất hiện sẽ mang tính bảo toàn cao và xuất hiện theo một chuỗi diễn biến nào đó.Tận dụng điều này, việc tìm kiếm có thể thực hiện chia nhỏ cho từng phân đoạn nhất định, ứng với từng phân đoạn, hệ thống sẽ thực hiện tùy biến các tham số để có được một kết quả mong muốn trong từng trường hợp cụ thể. Nếu nhìn nhận kỹ thuật một cách khái quát, có thể hình dung quá trình so sánh là quá trình tìm kiếm các pixel tương ứng giữa hai ảnh của hai đối tượng được kỳ vọng là giống nhau.Đặc trưng cho pixel trong ảnh số, về mặt không gian, là vị trí của chúng (location) trong ảnh, được thể hiện bằng một cặp số (x,y) cho biết vị trí của pixel về chiều ngang và chiều dọc so với tọa độ gốc là góc trái trên của ảnh.Bởi vì đối tượng không phải là bất biến, cùng đối tượng nhưng ở từng thời điểm, từng vị trí lại có một sự sai khác nhất định.Cũng như vậy các pixel tương ứng của hai đối tượng giống nhau hầu như không nằm cùng vị trí mà nó đã có sự dịch chuyển sang một vị trí khác thậm chí còn có một sự sai khác nhất định về màu. Với những phân tích như trên, mô hình CVA ứng dụng trong đồ án này sẽ được thiết kế như sau: + Đối tượng tìm kiếm sẽ được khoanh vùng từ một ảnh cho trước (đề nghị được trích ra từ một frame của file video) + Tham số s được đặt bằng 5 nghĩa là dự đoán trước đối tượng đó sẽ được tìm kiếm trong các frame với độ dịch chuyển cho phép là 5 pixel.Hay nói cách khác mỗi pixel của đối tượng bạn đầu sẽ được tìm kiếm trong phạm vi bán kính 121 pixel. + Tham số e dùng trong chọn láng giềng được đặt là 2 như vậy tập láng giềng sẽ bao gồm 25 pixel bao quanh mỗi pixel được tìm kiếm. + Tham số m là số lượng các pixel láng giềng ngẫu nhiên được trích ra từ tập 121 láng giềng được đặt là 5.Đây là một con số đủ nhỏ để đẩy nhanh tốc đến tốc độ tính toán nhưng vẫn đảm bảo tính đầy đủ kết quả thu về. + Tham số d được đặt là 0 trong trường hợp thử nghiệm chương trình với một đoạn video lý tưởng (quay trực tiếp màn hình máy tính), và đặt bằng 12 trong trường hợp thử nghiệm với một đoạn video thực tế.Đây là con số đã được điều chỉnh trong quá trình thử nghiệm hệ thống. + Tham số M được đặt là 50, nghĩa là với mỗi pixel x sẽ thực hiện lựa chọn 50 lần ngẫu nhiên các láng giềng.Số lượng này đủ lớn để đáp ứng tính toàn vẹn về mặt cấu trúc của đối tượng. Chương 6: THỰC NGHIỆM 6.1 Giới thiệu chương trình Sau những tìm hiểu và phân tích nội dung đồ án như đã trình bày ở trên, em đã đưa ra được một chương trình demo với chức năng đáp ứng được các yêu cầu chính của đồ án. Chương trình được viết bằng ngôn ngữ lập trình Visual C++ 6.0, có giao diện chính như sau: Hình 6.1 - Giao diện chính của chương trình Luồng chức năng chính của chương trình là người sử dụng mở 1 file avi và 1 file ảnh từ thiết bị lưu trữ, sau đó chọn đối tượng trong ảnh đã mở, tiếp theo là có thể chỉnh sửa một số tham số cho phương pháp CVA, cuối cùng chương trình sẽ thực hiện duyệt qua toàn bộ file avi thực hiện tìm kiếm nội dung của từng frame và trả về các frame có chứa đối tượng cần tìm, kết quả sẽ được lưu trong một danh sách cho phép người sử dụng duyệt lại. Ngoài ra chương trình cũng cho phép người sử dụng playback file avi theo ý muốn. 6.2 Các chức năng chính của chương trình 6.2.1 Giao diện chính Chương trình có một giao diện chính duy nhất, được chia làm nhiều phần, mối phần giữ một chức năng riêng: đối tượng tìm kiếm Querry image frame kết quả danh sách kết quả tham số CVA menu chính AVI file Hình 6.2 - Các vùng trên giao diện chính AVI file: đây là phần sẽ hiển thị nội dung của file avi, cho phép playback file avi, duyệt qua từng frame. Phần này gồm có một button nằm ở phía trên bên phải, cho phép người sử dụng mở một file avi, nằm bên trái là hệ thống nút nhất cho phép playback file avi. Góc phải bên dưới làm nhiệm vụ hiển thị số thứ tự của frame hiện tại đang được hiển thị trên tổng số frame của file avi Đối tượng tìm kiếm : vùng này sẽ hiển thị đối tượng đã được người sử dụng chọn ra từ Querry image. Vùng hiển thị chỉ được giới hạn có kích thước là 40x40, đối tượng dù được chọn với kích thước bao nhiêu sẽ được set lại theo tỉ lệ nhất định để phù hợp với kích thước này. Querry image: vùng chứa ảnh nguồn mà từ đó sẽ chọn ra đối tượng để tìm kiếm. Nằm ở góc phải phía trên cũng có một button cho phép người sử dụng mở file ảnh bất kì Ở giữa vùng này sẽ hiển thị ảnh mà người dùng đã chọn, người sử dụng chỉ có thể chọn ra đối tượng khi di chuột ở đây. Frame kết quả: vùng này chịu trách nhiệm hiển thị frame kết quả sau khi đã thực hiện đo độ tương tự của đối tượng cần kiếm với các đối tượng trong các frame của file avi. Danh sách kết quả: đây là một listbox chứa danh sách các frame mà chương trình đã tìm được với kết quả phù hợp với đối tượng đã được chọn ở trên. Tham số CVA: vùng này chứa các textbox cho phép người sử dụng điều chỉnh các tham số trong mô hình CVA, là mô hình chính được sử dụng để đo đo độ tượng tự của chương trình. Menu chính: đây là hệ thống menu của chương trình, chứa đựng toàn bộ các thao tác của chương trình, , trên đó bao gồm 4 menu. Menu File: cho phép người sử dụng truy cập 3 chức năng : mở file AVI (Open AVI File), mở ảnh gốc (Open Querry Image), và kết thúc chương trình (Exit) Hình 6.3 - Menu File Menu Playback: cho phép người sử dụng thao tác chính với file avi, bao gồm chơi file avi (Play), tạm dừng (Pause), dừng hẳn (Stop), chơi ở tốc độ cao (High speed), chơi ở tốc độ thấp (Low speed), xem thuộc tính của file avi (Property) Hình 6.4 - Menu Playback Menu Process: menu này chứa đựng các thao tác quan trọng nhất của chương trình. Hình 6.5 - Menu Process Hiển thị histogram (Show histogram): bao gồm hiển thị histogram của frame hiện tại (From AVI), ảnh gốc (From Querry) và ảnh kết quả (From Result). Ghi frame thành ảnh (Save to bitmap) Xác định độ đo tương tự (Similarity Measurement) 6.2.2 Chức năng mở file AVI, ảnh gốc Hình dưới mô tả hộp thoại cho phép người sử dụng chọn mở file avi, thao tác này có thể được thực hiện thông qua bằng hai cách: sử dụng button trong vùng AVI file hoặc chọn submenu "Open AVI file..." trên menu File. Hiện tại chương trình mới chỉ cho phép người sử dụng thao tác với file avi nên hộp thoại này chỉ cho phép chọn các file có phần mở rộng là "avi". Hình 6.6 - Hộp thoại mở file AVI Để mở ảnh gốc (Querry Image) người sử dụng có thể thực hiện bằng cách click vòa button trong vùng Querry image hoặc thông qua submenu "Open Querry image..." trên menu File. Chương trình hiện tại đã cho phép người sử dụng thao tác với hầu hết các định dạnh cơ bản, dưới đây là hình ảnh của hộp thoại này: Hình 6.7 - Hộp thoại mở file ảnh nguồn 6.2.3 Thao tác với file AVI Chương trình cho phép playback file avi thông qua các thao tác : play, pause, stop, high speed, low speed, ngoài ra cũng cho phép người sử dụng xem các thông số kỹ thuật của file avi hiện đang được mở. Sau khi mở file avi người sử dụng có thể thực hiện chơi file avi ở tốc độ bình thường bằng cách chọn trong menu Playback® Play hoặc button trong vùng AVI file. Quá trình này có thể bị tạm dừng (pause) khi người dùng chọn (hay Playback® Play), hoặc dừng hẳn khi chọn (hay Playback®Stop). Ngoài ra, chương chình chọn cho phép người sử dụng chơi file ở tốc độ cao (Playback®High speed) hoặc chơi ở chế độ thấp (Playback®Slow speed). Cuối cùng người sử dụng có thể xem các thông số kỹ thuật của file avi đang được mở, bằng cách chọn trên menu Playback®Property: Hình 6.8 - Hộp thoại property 6.2.4 Hiển thị histogram Để người sử dụng có thể đánh giá hoạt động của chương trình một các trực quan hơn, chương trình có chức năng cho xem hist togram của các image hiển thị trên giao diện. Khi người sử dụng chọn xem histgram của một ảnh bất kỳ, hộp thoại sau sẽ hiện ra: Hình 6.9 - Hộp thoại Histogram Bên cạnh việc hiển thị histogram, hộp thoại này còn cung cấp cho người sử dụng một số lựa chọn, bao gồm: xem histogram theo các màu riêng biệt (Red, Green, Blue) thậm chí là histogram của ảnh ở dạng đa cấp xám (Gray), áp dụng toán tử logarit cho histogram nhằm đẩy cao đồ thị để quan sát. Người sử dụng có thể xem histogram của 3 image khác nhau hiển thị trên giao diện của chương trình: Xem histogram của Frame: để xem histogram của frame hiện tại người sử dụng thực hiện chọn trên menu Process®Show histogram®From Frame. Xem histogram của ảnh nguồn: sau khi chọn ảnh bất kì làm ảnh nguồn (Querry Image), để xem histogram của nó, người sử dụng có thể truy cập theo menu: Process®Show histogram®From Querry Image Xem histogram của ảnh kết quả: sau khi thực hiện xác định độ đo tương tự, kết quả trả về là các frame nằm trong danh sách kết quả, để xem histogram của một frame trong đó người sử dụng chọn một frame rồi chọn trên menu : Process®Show histgram®From Result. 6.2.5 Xuất frame ra file bitmap Như phân tích ở chương 5, để có được kết quả có độ chính xác cao hơn thì ảnh gốc nên là một frame chích ra từ file avi, chức năng này của chương trình cho phép thực hiện điều đó. Sau khi quan sát các frame của file avi, người sử dụng có thể thực hiện xuất frame ra file bitmap bằng cách lựa chọn trên menu Process®Save to bitmap, khi đó hộp thoại sau sẽ hiện ra: Hình 6.10 - Tùy chọn save frame Có 2 lựa chọn cho người sử dụng khi thực hiện thao tác này: Current frame: khi thực hiện lựa chọn này thì frame hiện tại (đang hiển thị trên giao diện) sẽ được save ra file bitmap. More frames: lựa chọn này cho phép ghi một chuỗi các frame ra file bitmap bằng cách nhập vào frame bắt đầu và rame kết thúc. Sau khi chọn một trong hai lựa chọn trên và nhấn OK một hộp thoại khác sẽ hiện ra cho phép người sử dụng chọn tên file bitmap sẽ đươc save: Hình 6.11 - Hộp thoại Save as frame 6.2.6 Khoanh vùng đối tượng cần tìm Hình 6.12 - Khoanh vùng đối tượng Chức năng này cho phép người sử dụng chọn lựa đối tượng cần tìm kiếm trong ảnh gốc. Để làm được điều này, người sử dụng thực hiện di chuột qua vùng chứa đối tượng mong muốn, một hình chữ nhật tạm thời sẽ được vẽ bao quanh đối tượng và khi chuột được thả ra thì hình chữ nhật sẽ biến mất và đối tượng được chấp nhận và hiển thị trên vùng Đối tượng tìm kiếm. 6.2.7 Xác định độ đo tương tự Đây là chức năng cuối cùng và cũng là chức năng quan trọng nhất của chương trình. Chức năng này thực hiện đo độ đo tương tự giữa đối tượng tìm kiếm với các đối tượng phát hiện trong các frame của file avi và rút ra các frame có độ tương tự phù hợp (đã được định trước theo ngưỡng). Người sử dụng có thể thực hiện chức năng này bằng hai cách: click chọn button trên giao diện hoặc chọn trên menu Process®Similarity Measurement. Sau khi quá trình tính toán được khởi động, chương trình sẽ thực hiện xác định độ đo tương tự và sắp xếp các frame kết quả vào listbox theo thứ tự từ cao xuống thấp, như sau: Hình 6.13 - Danh sách frame kết quả 6.3 Kết quả đạt được Chương trình đã giải quyết được vấn đề lớn nhất của đồ án đó là "tìm kiếm theo nội dung trong file avi". Chương trình đã thực hiện theo phương pháp CVA với tiền xử lý là kỹ thuật histogram dòng,cột để xác định độ tương tự giữa 2 ảnh thông qua đối tượng chọn trước và vị trí của đối tượng trong ảnh. Kết quả trả về được kết xuất thành một danh sách theo thứ tự giảm dần độ tương tự và nằm trong một ngưỡng cho trước. Kết quả này là khả quan trong trường hợp file avi và file ảnh đầu vào có chất lượng cao và tương đồng về dịnh dạng. Tuy nhiên, với các file có chất lượng tương đối thấp, chịu ảnh hưởng nhiều của nhiễu thì chương trình không đưa lại được kết quả như mong muốn thậm chí còn cho về kết quả không chính xác. Điều này đỏi hỏi phải có những điều chỉnh hợp lý hơn trong thời gian sắp tới. KẾT LUẬN Dữ liệu video số là một loại dữ liệu "cao cấp" trong các loại dữ liệu số của loài người. Nó không chỉ chứa đựng dữ liệu ảnh (mỗi frame) mà còn chứa đựng cả dữ liệu âm thanh (audio), nội dung chứa đựng trong video cũng chứa đựng nhiều giá trị và đáng tin cậy hơn so với các loại dữ liêu khác. Chính vì vậy việc phát triển các bài toán nhằm khai thác hợp lý nguồn dữ liệu này sẽ đem lại nhiều lợi ích vô cùng to lớn. Và bài toán "tìm kiếm theo nội dung trong file video" là một trong số đó. Trong khuôn khổ của một đồ án tốt nghiệp em đã thực hiện tìm hiểu được các vấn đề cơ bản nhất liên quan đến bài toàn này, đề xuất một phương án giải quyết dựa trên những nghiên cứu mới nhất và cuối cùng demo được một chương trình cho phép giải quyết bài toán ở mức độ trung bình. Hướng phát triển trong thời gian sắp tới sẽ là cải tiến phương pháp đã được đề xuất nhằm làm tăng hiểu quả của chương trình. Bên cạnh đó, nghiên cứu áp dụng thêm các phương pháp khác, chọn lọc ra phương pháp ưu việt nhất để giải quyết bài toán trong từng trường hợp cụ thể, cuối cùng là đưa ra được một chương trình mang ý nghĩa thực tiễn cao hơn. TÀI LIỆU THAM KHẢO Li Chen and F.W.Stentiford, An Attention Based Similarity Measure for Colour, University College London, 2005. F.W.Stentiford, An attention based similarity measure for fingerprint retrieval, UK IP5 3RE, 2004. ÉtienneBaudrier, GillesMillon, FredericNicolier, SuRuan, A new similarity measure using Hausdorff distance map, 10026 Troyes Cedex, 2005. Pavel Paclík , Jana Novovicova ,Robert P.W.Duin, A trainable similarity measure for image classification, Delft Universityof Technology, 2004. PTS Nguyễn Ngọc Kỷ, Bài Giảng môn Xử lý ảnh cho Cao học Tin học tại ĐHBK Hà Nội, ĐHBK Hà Nôi, 1997. Phạm Công Ngô, Lập trình windows bằng Visual C, NXB Giao thông vận tải, 2000. www.codeguru.com www.codeproject.com PHỤ LỤC 1. Xác định độ đo tương tự int i; RGBQUAD rgbX,rgbY; for (i = 0; i < COUNT_OF_NEIGHTBOUR; i++) { rgbX = m_imgSource->GetPixelColor(x.x + m_aNeightbourhood[i].x, x.y + m_aNeightbourhood[i].y); rgbY = m_imgTmpTmp->GetPixelColor(x.x + m_aNeightbourhood[i].x, x.y + m_aNeightbourhood[i].y); if (abs(rgbX.rgbBlue - rgbY.rgbBlue) > NGUONG_DO || abs(rgbX.rgbGreen - rgbY.rgbGreen) > NGUONG_DO || abs(rgbX.rgbRed - rgbY.rgbRed) > NGUONG_DO || abs(rgbX.rgbReserved - rgbY.rgbReserved) > NGUONG_DO) { return 0; } } return 1; 2. Sinh ngẫu nhiên tập láng giềng int i; bool *aFlag = NULL; long x,y; aFlag = (bool *)malloc(sizeof(bool) * 4 * cx * cy); if (NULL == aFlag) return false; for (i = 0; i < 4 * cx * cy; i++) { *(aFlag + i) = false; } srand((unsigned)time(NULL)); for (i = 0; i < nPoint; i++) { x = rand() % (2 * cx + 1); y = rand() % (2 * cy + 1); while (*(aFlag + y * cx + x) && (cx/2 == x) && (cy/2 == y)) { x = rand() % (2 * cx + 1); y = rand() % (2 * cy + 1); } m_aNeightbourhood[i].x = cx/2 - x; m_aNeightbourhood[i].y = y - cy/2; *(aFlag + y * cx + x) = true; } free(aFlag); 3. Hiển thị Histogram hMax = m_imgImage->Histogram(hRed, hGreen, hBlue, hGray); if (hMax) { int ybase = r.bottom-10; if (m_logen){ float yratio = (r.bottom - r.top - 50)/(float)log10((float)(hMax+1)); if (m_ren){ CPen redPen(PS_SOLID, 1, RGB(222, 0, 0)); pOldPen = dc.SelectObject(&redPen); dc.MoveTo(10, (int)(ybase-log10((float)(1+hRed[0]))*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-log10((float)(1+hRed[x]))*yratio)); } if (m_gen){ CPen greenPen(PS_SOLID, 1, RGB(0, 222, 0)); pOldPen = dc.SelectObject(&greenPen); dc.MoveTo(10, (int)(ybase-log10((float)(1+hGreen[0]))*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-log10((float)(1+hGreen[x]))*yratio)); } if (m_ben){ CPen bluePen(PS_SOLID, 1, RGB(0, 0, 222)); pOldPen = dc.SelectObject(&bluePen); dc.MoveTo(10, (int)(ybase-log10((float)(1+hBlue[0]))*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-log10((float)(1+hBlue[x]))*yratio)); } if (m_grayen){ CPen grayPen(PS_SOLID, 1, RGB(64, 64, 64)); pOldPen = dc.SelectObject(&grayPen); dc.MoveTo(10, (int)(ybase-log10((float)(1+hGray[0]))*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-log10((float)(1+hGray[x]))*yratio)); } dc.SelectObject(pOldPen); } else { float yratio = (r.bottom - r.top - 50)/(float)hMax; if (m_ren){ CPen redPen(PS_SOLID, 1, RGB(222, 0, 0)); pOldPen = dc.SelectObject(&redPen); dc.MoveTo(10, (int)(ybase-hRed[0]*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-hRed[x]*yratio)); } if (m_gen){ CPen greenPen(PS_SOLID, 1, RGB(0, 222, 0)); pOldPen = dc.SelectObject(&greenPen); dc.MoveTo(10, (int)(ybase-hGreen[0]*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-hGreen[x]*yratio)); } if (m_ben){ CPen bluePen(PS_SOLID, 1, RGB(0, 0, 222)); pOldPen = dc.SelectObject(&bluePen); dc.MoveTo(10, (int)(ybase-hBlue[0]*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-hBlue[x]*yratio)); } if (m_grayen){ CPen grayPen(PS_SOLID, 1, RGB(64, 64, 64)); pOldPen = dc.SelectObject(&grayPen); dc.MoveTo(10, (int)(ybase-hGray[0]*yratio)); for (int x=1; x<256; x++) dc.LineTo(x+10, (int)(ybase-hGray[x]*yratio)); } } }