Tài liệu Nội suy ảnh dùng các ràng buộc hình học

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THÀNH TRUNG NỘI SUY ẢNH SỬ DỤNG CÁC RÀNG BUỘC HÌNH HỌC LUẬN VĂN THẠC SĨ HÀ NỘI 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THÀNH TRUNG NỘI SUY ẢNH SỬ DỤNG CÁC RÀNG BUỘC HÌNH HỌC Ngành: Công nghệ Điện tử -Viễn thông Chuyên ngành: Kỹ thuật Điện tử Mã số: 60 52 70 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.LÊ VŨ HÀ HÀ NỘI – 2011 3 LỜI MỞ ĐẦU Sự phát triển không ngừng của khoa học công nghệ đem lại cho con người cuộc sống ngày càng tốt hơn. Trong sự phát triển đó có thể dễ dàng nhận ra sự có mặt của các công trình khoa học liên quan đến lĩnh vực điện tử viễn thông và công nghệ thông tin. Công nghệ thông tin và truyền thông trong đó có lĩnh vực xử lý ảnh đã đóng góp một phần quan trọng, làm thay đổi căn bản, nâng cao chất lượng đời sống của con người. Chính vì lẽ đó có rất nhiều nhà khoa học dành thời gian để nghiên cứu về lĩnh vực này. Là học viên cao học đã được học một số môn liên quan và tôi cũng muốn thử sức mình trong lĩnh vực khoa học có nhiều ứng dụng này vì thế tôi lựa chọn đề tài:”Nội suy ảnh sử dụng các ràng buộc hình học” với mong muốn tiếp cận và dần dần có những công trình khoa học có giá trị phục vụ cuộc sống của con người. Mục tiêu của luận văn là: 1. Tìm hiểu một số phương pháp nội suy 2. Cài đặt thử nghiệm, đánh giá một giải thuật nội suy Tôi đã hoàn thành luận văn tốt nghiệp của mình với nội dung chính sau: Chương 1: Giới thiệu Chương 2: Cơ sở lý thuyết về một số phương pháp nội suy Chương 3: Thực nghiệm Mặc dù đã rất cố gắng để hoàn thành luận văn tốt nghiệp đặc biệt là giai đoạn hoàn thiện. Tuy nhiên tôi cũng không thể tránh khỏi những thiếu sót, sai sót. Kính mong nhận được sự góp ý chân thành của các Thày cô, anh chị, bè bạn để tôi khắc phục và hoàn thiện hơn luận văn tốt nghiệp của mình.. Hà nội ngày 26/09/2011 Học viên Nguyễn Thành Trung Formatted: Centered, Line spacing: Multiple 1,3 li 4 MỤC LỤC CHƯƠNG 1: GIỚI THIỆU ......................................................................................6 1.1. Tổng quan về xử lý ảnh ............................................................................................. 6 1.1.1 Lịch sử về xử lý ảnh................................................................................................ 6 1.1.2 Các bước cơ bản trong xử lý ảnh ............................................................................. 8 1.2. Vấn đề nội suy trong xử lý ảnh ............................................................................... 11 1.2.1 Sơ lược về một số phương pháp nội suy truyền thống .......................................... 12 1.2.2 Nội suy theo hướng ................................................................................................ 13 1.3. Cấu trúc của luận văn .............................................................................................. 15 CHƯƠNG 2 ..........................................................................................................16 CƠ SỞ LÝ THUYẾT VỀ CÁC PHƯƠNG PHÁP NỘI SUY ..................................16 2.1 Nội suy tuyến tính ........................................................................................................ 16 2.2 Nội suy song tuyến tính (bilinear) ................................................................................ 17 2.3 Nội suy spline ............................................................................................................... 20 2.4 Nội suy các điểm gần nhất............................................................................................ 23 2.5 Đánh giá và nhận xét về các phương pháp nội suy ở trên ........................................... 25 2.6. Nội suy ảnh theo hướng............................................................................................... 27 2.6.1 Đặt vấn đề .............................................................................................................. 27 2.6.2. Nội suy theo hướng và việc ước lượng thưa......................................................... 29 2.6.3 Phân giải ảnh trên từ điển có cấu trúc.................................................................... 30 5 CHƯƠNG 3: THỰC NGHIỆM ..............................................................................33 3.1 Giới thiệu chung ........................................................................................................... 33 3.2 Một số thực nghiệm đơn giản ....................................................................................... 34 3.2.1 Thực nghiệm phân tích phổ của một đường thẳng đơn ......................................... 34 3.2.2 Thực nghiệm phân tích phổ của đường thẳng đứt nét ........................................... 35 3.2.3 Phân tích ảnh của một đường thẳng dựa trên phép biến đổi wavlet ..................... 37 3.3 Xác định các hướng, các vị trí ở đó ảnh có tính chất đồng nhất .................................. 39 3.3.1. Xác định các hướng ở đó ảnh có tính chất đồng nhất........................................... 39 3.3.2. Xác định các khu vực tương ứng với các hướng ở đó ảnh có tính chất đồng nhất ......................................................................................................................................... 43 3.3 Nội suy theo hướng ...................................................................................................... 49 3.4 Triển khai cài đặt chương trình .................................................................................... 50 3.4.1 Mô tả về hoạt động của chương trình ................................................................... 50 3.4.2 Triển khai cài đặt ................................................................................................... 50 3.5.1 Thí nghiệm phóng to gấp đôi ảnh 64x64 ............................................................... 52 3.5.2 Thí nghiệm trên ảnh Lena 512x512 ....................................................................... 53 KẾT LUẬN ............................................................................................................55 TÀI LIỆU THAM KHẢO .........................................................................................56 6 CHƯƠNG 1: GIỚI THIỆU 1.1. Tổng quan về xử lý ảnh 1.1.1 Lịch sử về xử lý ảnh Các phương pháp xử lý ảnh bắt nguồn từ hai ứng dụng: nâng cao chất lượng thông tin hình ảnh đối với mắt người và xử lý số liệu cho máy tự động. Một trong những ứng dụng đầu tiên của xử lý ảnh là nâng cao chất lượng ảnh báo, truyền qua cáp giữa London và NewYork vào những năm 1920. Thiết bị đặc biệt mã hóa hình ảnh (báo), truyền qua cáp và khôi phục lại ở phía thu. Vấn đề nâng cao chất lượng hình ảnh (số) lúc đầu có liên quan đến việc lựa chọn quá trình in và phân bố các mức sáng. Hệ thống đầu tiên (Bartlane) có khả năng mã hóa hình ảnh với 5 mức sáng khả năng này tăng lên 15 mức vào năm 1929. Việc nâng cao chất lượng ảnh bằng các phương pháp xử lý để truyền ảnh được liên tục nghiên cứu 35 năm sau đó. Do kỹ thuật máy tính phát triển, nên xử lý hình ảnh ngày càng phát triển. Năm 1964, các bức ảnh chụp mặt trăng được vệ tinh Ranger 7 của Mỹ truyền tải về trái đất, được xử lý để sửa méo (gây ra do camera truyền hình đặt trên vệ tinh ở các góc độ khác nhau). Các kỹ thuật cơ bản cho phép nâng cao chất lượng hình ảnh như làm nổi đường biên và lưu hình ảnh. Từ năm 1964 đến nay, phạm vi xử lý ảnh và video(ảnh động) lớn mạnh không ngừng. Các kỹ thuật xử lý ảnh số (digital image processing) hiện nay được sử dụng để giải quyết hàng loạt vấn đề, nhằm nâng cao chất lượng thông tin hình ảnh. Trong y học, xử lý ảnh nhằm nâng cao độ tương phản, hoặc mã hóa các mức sáng thành các màu để nội suy ảnh X quang và các hình ảnh y sinh học dễ dàng.... Các nhà địa vật lý sử dụng kỹ thuật tương tự để nghiên cứu các mẫu vật chất từ ảnh vệ tinh. Các thuật toán làm nổi đường biên và khôi phục hình ảnh được sử dụng để xử lý hình ảnh bị giảm chất lượng. Trong thiên văn học, các phương pháp xử lý ảnh nhằm khôi phục hình ảnh bị nhiễu hoặc bị mất do bóng (antifacts) sau khi chụp. Trong vật lý và các lĩnh vực liên quan, kỹ thuật máy tính nâng cao được chất lượng hình ảnh trong các lĩnh vực như plasma và microcopy điện tử. Tương tự người ta đã ứng dụng xử lý ảnh có kết quả tốt trong viễn 7 thám, sinh học, y tế hạt nhân, quân sự, công nghiệp...Nâng cao chất lượng (làm nổi đường biên) và khôi phục ảnh bị nhiễu là quá trình xử lý ảnh dùng cho mục đích nội suy của mắt người. Lĩnh vực ứng dụng quan trọng thứ hai là xử lý ảnh số gắn liền với việc cảm nhận của máy. Trong lĩnh vực thứ hai, các cố gắng đều tập trung vào các quá trình trích thông tin ảnh và chuyển thành dạng thích hợp cho xử lý máy tính. Ví dụ như thông tin dùng cho máy tính là các moments thống kê, các hệ số biến đổi Fourier....... Những vấn đề tiêu biểu của kỹ thuật xử lý ảnh (tĩnh) và video (ảnh động) được ứng dụng nhiều trong thực tế, có thể kể như: tự động nhận dạng đặc trưng, máy nhìn công nghiệp để điều khiển và kiểm tra sản phẩm, nhận dạng mục tiêu quân sự, tự động xử lý vân tay, hiển thị lên màn hình ảnh X quang và các mẫu máu, xử lý bằng máy tính các hình ảnh chụp từ vệ tinh để dự báo thời tiết, nén ảnh (tĩnh) và video (ảnh động) để lưu và truyền được nhiều hơn tín hiệu ảnh và video số trong thông tin, máy tính, truyền hình thông thường và truyền hình có độ phân giải cao. HDTV/ATV. (Nguồn:[1] TS. Nguyễn Kim Sách, Xử lý ảnh và video số, Nhà xuất bản khoa học và kỹ thuật-tr 5,6) Có thể nói những công trình nghiên cứu về xử lý ảnh đã và đang góp phần không nhỏ vào sự phát triển của khoa học kỹ thuật, đời sống vật chất, tinh thần của con người đưa con người vươn xa ra ngoài vũ trụ. Cũng chính vì xử lý ảnh có nhiều ứng dụng và đem lại nhiều lợi ích như vậy nên em đã lựa chọn đề tài luận văn tốt nghiệp liên quan đến lĩnh vực này với mong muốn sau này có chút đóng góp nhỏ bé vào lĩnh vực này. 8 1.1.2 Các bước cơ bản trong xử lý ảnh Hình 1.1. Các bước cơ bản trong xử lý ảnh[2] 1.1.2.1 Thu nhận ảnh (Image Acquisition) Để thu nhận ảnh có thể sử dụng camera (màu hoặc đen trắng), máy quét hoặc các loại cảm biến khác. Thông thường ảnh nhận qua camera là ảnh tương tự (loại camera ống chuẩn CCIR với tần số 1/25, mỗi ảnh 25 dòng), cũng có loại camera đã số hoá (như loại CCD – Change Coupled Device) là loại dùng các điốt quang tạo cường độ sáng tại mỗi điểm ảnh. Camera thường dùng là loại quét dòng ; ảnh tạo ra có dạng hai chiều. Chất lượng một ảnh thu nhận được phụ thuộc vào thiết bị thu, vào môi trường (ánh sáng, phong cảnh) 1.1.2.2 Tiền xử lý (Image Processing) Sau bộ thu nhận, ảnh có thể nhiễu, độ tương phản thấp nên cần đưa vào bộ tiền xử lý để nâng cao chất lượng. Chức năng chính của bộ tiền xử lý là lọc nhiễu, nâng độ tương phản để làm ảnh rõ hơn, nét hơn. 1.1.2.3 Phân đoạn (Segmentation) hay phân vùng ảnh Phân vùng ảnh là tách một ảnh đầu vào thành các vùng thành phần để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận dạng chữ (hoặc mã vạch) trên phong bì thư cho mục đích phân loại bưu phẩm, cần chia các câu, chữ về địa chỉ hoặc tên người thành các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. Đây là phần phức tạp khó 9 khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này. 1.1.2.4 Biểu diễn ảnh (Image Representation) Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã phân đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trưng (Feature Selection) gắn với việc tách các đặc tính của ảnh dưới dạng các thông tin định lượng hoặc làm cơ sở để phân biệt lớp đối tượng này với đối tượng khác trong phạm vi ảnh nhận được. Ví dụ: trong nhận dạng ký tự trên phong bì thư, chúng ta miêu tả các đặc trưng của từng ký tự giúp phân biệt ký tự này với ký tự khác. 1.1.2.5 Nhận dạng và nội suy ảnh (Image Recognition and Interpretation) Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thường thu được bằng cách so sánh với mẫu chuẩn đã được học (hoặc lưu) từ trước. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ số và nét gạch ngang trên phong bì thư có thể được nội suy thành mã điện thoại. Có nhiều cách phân loai ảnh khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình toán học về ảnh được phân theo hai loại nhận dạng ảnh cơ bản: - Nhận dạng theo tham số. - Nhận dạng theo cấu trúc. Một số đối tượng nhận dạng khá phổ biến hiện nay đang được áp dụng trong khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay, chữ ký điện tử), nhận dạng văn bản (Text), nhận dạng vân tay, nhận dạng mã vạch, nhận dạng mặt người… 10 1.1.2.6 Cơ sở tri thức (Knowledge Base) Ảnh là một đối tượng khá phức tạp về đường nét, độ sáng tối, dung lượng điểm ảnh, môi trường để thu ảnh phong phú kéo theo nhiễu. Trong nhiều khâu xử lý và phân tích ảnh ngoài việc đơn giản hóa các phương pháp toán học đảm bảo tiện lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử lý ảnh theo cách của con người. Trong các bước xử lý đó, nhiều khâu hiện nay đã xử lý theo các phương pháp trí tuệ con người. Vì vậy, ở đây các cơ sở tri thức được phát huy. 1.1.2.7 Biểu diễn và mô tả Ảnh sau khi số hoá sẽ được lưu vào bộ nhớ, hoặc chuyển sang các khâu tiếp theo để phân tích. Nếu lưu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lượng bộ nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông thường, các ảnh thô đó được đặc tả (biểu diễn) lại (hay đơn giản là mã hoá) theo các đặc điểm của ảnh được gọi là các đặc trưng ảnh (Image Features) như: biên ảnh (Boundary), vùng ảnh (Region). Một số phương pháp biểu diễn thường dùng: • Biểu diễn bằng mã chạy (Run-Length Code) • Biểu diễn bằng mã xích (Chaine -Code) • Biểu diễn bằng mã tứ phân (Quad-Tree Code) Trên đây là các bước cơ bản trong xử lý ảnh trên thực tế không nhất thiết các ứng dụng liên quan đến xử lý ảnh phải trải qua tất cả các bước trên. Tùy vào yêu cầu của ứng dụng mà một số bước có thể bỏ qua. Hình vẽ dưới đây là một sơ đồ thể hiện khá chi tiết về phân tích, xử lý ảnh: (Nguồn[2] TS. Nguyễn Quang Hoan, Xử lý ảnh, Học viện công nghệ bưu chính viễn thông, 2006) 11 Hình 1.2. Sơ đồ phân tích và xử lý ảnh và lưu đồ thông tin giữa các khối[2] 1.2. Vấn đề nội suy trong xử lý ảnh Trong chế bản hay những công việc có liên quan đến hình ảnh đều gặp phải một trở ngại đó là việc phóng to ảnh sẽ dẫn đến tình trạng ảnh bị bể nên không thể in và chỉnh sửa được. Muốn phóng to ảnh người ta thường dùng phương pháp chụp rửa hình, dùng máy quét để quét ảnh với độ phân giải cao. Nhưng làm như thế rất mất thời gian lại không kinh tế. Hiện tại có rất nhiều nhà sản xuất phần mềm đã khắc phục vấn đề này bằng cách dùng các phương pháp nội suy ảnh và bù đắp sự tương quan của màu sắc trong quá trình biến đổi ảnh. Có thể dễ dàng nhận thấy sự có mặt của nội suy trong các máy ảnh kỹ thuật số, trong các phần mềm xem ảnh, trong các phần mềm chỉnh sửa hình ảnh. Một ví dụ cụ thể là trong phần mềm xem ảnh, khi chúng ta muốn phóng to/thu nhỏ hình ảnh thì là lúc cần dùng đến nội suy. Một ví dụ khác là khi chúng ta quay ảnh hoặc biến dạng hình ảnh thì cũng có thể dùng nội suy. Phần dưới đây trình bày về một số phương pháp nội suy hay được sử dụng. Những phương pháp nội suy này khi áp dụng vào nội suy ảnh thì “cư xử” như nhau đối với các ảnh tức là nội suy không thích nghi, không dựa vào thông tin hình ảnh. Formatted: DMC1 12 1.2.1 Sơ lược về một số phương pháp nội suy truyền thống Một số phương pháp nội suy hay được dùng trong xử lý ảnh: -Nội suy các điểm gần nhất -Nội suy song tuyến tính -Nội suy ghép trơn Nội suy các điểm gần nhất thực chất là không có tính toán gì chỉ đơn giản gán giá trị điểm ảnh cần nội suy với giá trị điểm ảnh gần nó nhất. Nội suy các điểm gần nhất có ưu điểm là đơn giản dễ cài đặt nhưng có nhiều nhược điểm cụ thể là nếu dùng nội suy các điểm gần nhất để phóng to ảnh có thể gây ra các đướng ziczac hoặc tạo những ô vuông lớn trong ảnh làm cho hình ảnh thô, không được mịn màng. Hình vẽ dưới đây minh họa việc phóng to một ảnh sử dụng nội suy các điểm gần nhất. Các ảnh được hiển thị dưới dạng ma trận số để thể hiện rõ bản chất của phương pháp nội suy: Hình 1.3. Ảnh ban đầu Hình 1.4. Ảnh phóng to sử dụng nội suy các điểm gần nhất Formatted: DMC2 13 Không giống như nội suy các điểm gần nhất trong nội suy song tuyến, điểm ảnh được nội suy có tính toán dựa trên một số điểm lân cận nó. Gọi là nội suy song tuyến tính nhưng thực chất nội suy song tuyến tính không phải là nội suy tuyến tính. Tính theo một biến thì nội suy song tuyến tính là tuyến tính song nếu tính trên tất cả các biến thì nội song tuyến tính không phải là nội suy tuyến tính. Nội suy song tuyến tính có quy luật nội suy phức tạp hơn nội suy các điểm gần nhất và do nó xét tới ảnh hưởng của 4 điểm gần nhất xung quanh nó nên có thể nói về cơ bản sử dụng nội suy song tuyến tính tuyến tính là lựa chọn tốt hơn so với nội suy các điểm gần nhất. So với nội suy song tuyến tính và nội suy các điểm gần nhất thì nội suy ghép trơn có quy luật phức tạp nhất trong nội suy ghép trơn (spline) điểm cần nội suy chịu ảnh hưởng của nhiều điểm xung quanh nó. Cài đặt nội suy ghép trơn khó hơn nhưng kết quả nội suy tốt hơn. 1.2.2 Nội suy theo hướng Formatted: DMC2 Nếu chỉ sử dụng đơn thuần các phương pháp nội suy đã trình bày ở trên trong việc nội suy ảnh thì ảnh sau nội suy xuất hiện những chi tiết lạ mà ảnh gốc không có điều này có thể làm giảm độ sắc nét của hình ảnh. Tìm cách hạn chế được tối đa các chi tiết lạ đó thì ảnh sau nội suy sẽ tốt hơn. Trong miền không gian ảnh xuất hiện các chi tiết lạ thì chắc chắn khi chuyển sang miền tần số thì cũng có những thành phần phổ lạ tương ứng. Có thể nhìn thầy một vấn đề là nếu những phổ lạ này được khử đi được hoặc hạn chế thì ảnh sau nội suy sẽ không còn xuất hiện hoặc hạn chế được sự xuất hiện của các chi tiết lạ. Nhưng không phải trong trường hợp nào cũng khử đi được thành phần phổ lạ. Thành phần phổ lạ chỉ khử được khi nó có sự tách biệt không chồng lấn với các phổ khác. Trường hợp đơn giản nhất là khi ta đem hạ mẫu một ảnh với hệ số hạ mẫu là 2, nếu    ảnh này chỉ có các thành phần tần số trong - ,  thì ảnh hạ mẫu xuất hiện các phổ lạ  2 2 2 nhưng các thành phần phổ lạ chắc chắn không đè lên các thành phần phổ của ảnh gốc vì vậy hoàn toàn có thể dùng bộ lọc thông thấp để loại bỏ thành phần phổ lạ từ ảnh hạ mẫu và ta lại thu được ảnh gốc ban đầu. 14 Vấn đề đặt ra là cũng trong trường hợp trên nhưng nếu ảnh đem hạ mẫu có các    thành phần tần số vượt ra ngoài - ,  thì thành phần phổ lạ nhiều khả năng bị đè lên  2 2 2 thành phổ giống phổ ảnh gốc điều này dẫn tới việc không thể dùng bộ lọc thông thấp như trên đề khôi phục. Nhưng nếu thành phần phổ lạ không chồng lấn lên thành phần phổ giống phổ của ảnh gốc thì có thể tách nó ra được. Liệu có ảnh nào có tính chất như vậy không? Guoshen Yu đã đưa ra một trường hợp đó là ảnh của một đường thẳng. Hình 1.5. a)Đường thẳng có độ phân giải cao và phổ của nó b)Đường thẳng có độ phân giải thấp và phổ của nó[5] Quan sát phổ của một đường thẳng có độ phân giải cao và phổ của đường thẳng hạ mẫu từ đường thẳng có độ phân giải cao ta thấy ngoài thành phần phổ giống với phổ của đường thẳng có độ phân giải cao (phổ gốc), trong phổ của đường thẳng có độ phân giải thấp còn xuất hiện các thành phần phổ lạ, điều đáng chú ý là có thành phần phổ lạ này tách rời so với phổ gốc. Nếu có một bộ lọc chỉ ưu tiên các thành phần phổ gốc không ưu tiên các thành phần tần số lạ thì có thể nội suy để thu được đường thẳng có độ phân giải cao từ đường thẳng có độ phân giải thấp bằng cách sử dụng bộ lọc này. Phương pháp nội suy này được đặt tên là nội suy theo hướng. Từ đây tôi thấy nếu có thể phân rã ảnh ra thành các đường thẳng thì trong nội suy có thể lợi dụng việc nội suy theo hướng từng đường thẳng vào việc nội suy ảnh và tôi đã triển khai ý tưởng này để cài đặt một chương trình nội suy ảnh có sử dụng ý tưởng nội suy theo hướng. Ý tưởng chính trong chương trình tôi đã cài đặt như sau: 15 -Phân tích ảnh cần nội suy để thu được thành phần ảnh tần số cao, thành phần ảnh tần số thấp -Nội suy theo phương pháp thông thường đối với thành phần ảnh tần số thấp -Nội suy theo hướng được áp dụng đối với thành phần ảnh tần số cao -Tổ hợp các ảnh để thu được ảnh đầu ra. 1.3. Cấu trúc của luận văn Formatted: DMC1 Sau một thời gian nghiên cứu tài liệu, cài đặt chương trình, chỉnh sửa tôi đã hoàn thành luận văn “Nội suy ảnh sử dụng các ràng buộc hình học”. Luận văn có cấu trúc 3 chương: Chương 1: Giới thiệu Chương 2: Cơ sở lý thuyết về các phương pháp nội suy Chương 3: Thực nghiệm Sau những lần chỉnh sửa tôi đã hoàn thành luận văn tốt nghiệp của mình các nội dung trong luận văn là do tôi tự viết theo suy nghĩ của mình dựa trên các tài liệu tham khảo mà tôi thu thập được. Ngoài ra tôi có một số nội dung lý thuyết từ các tài liệu khác tôi đã chỉ rõ nguồn trích dẫn. Formatted: mucchuong 16 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT VỀ CÁC PHƯƠNG PHÁP NỘI SUY Trong toán học việc nội suy với mục đích tìm ra những giá trị chưa biết của một hàm dựa trên những giá trị đã biết của hàm đó tại một số giá trị của biến số. Như ta đã biết một tín hiệu bất kì có thể được biểu diễn bởi một hàm của một hoặc nhiều biến độc lập. Vì vậy, rõ ràng ta có thể sử dụng các thuật toán nội suy trong toán học vào mục đích nội suy tín hiệu trong đó có nội suy ảnh. Chương 2 bắt đầu từ việc trình bày về một số thuật toán nội suy trong toán học và sử dụng chúng trong nội suy ảnh, tiếp theo là trình bày về nội suy theo hướng - phương pháp nội suy có khai thác thông tin hình ảnh cụ thể là có sử dụng ràng buộc hình học. Sử dụng phương pháp nội suy ảnh này cho kết quả tốt hơn đối với một số dạng ảnh. 2.1 Nội suy tuyến tính Trong nội suy tuyến tính thì hàm nội suy được tìm ra dựa trên việc coi mối quan hệ giữa hàm và biến là quan hệ tuyến tính. Formatted: DMC1 Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li Trường hợp đơn giản là cần tìm các giá trị của hàm f(x) tại các giá trị của x thuộc khoảng (x0,x1) khi biết f(x0) = y0 và f(x1) = y1 trong trường hợp này hàm nội suy chính là phương trình đường thẳng đi qua (x0,y0); (x1,y1) Formatted: Centered, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li Hình 2.1 Minh họa nội suy tuyến tính dựa trên 2 điểm đã biết[8] 17 Khi biết nhiều hơn hai giá trị của f(x) thì việc nội suy được thực hiện bằng cách nội suy tuyến tính trong từng cặp giá trị kề nhau của x. Cụ thể là nếu biết f(x) tại các giá Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li trị của x là x0, x1, x2, ...,xn thì hàm f(x) là tổ hợp của các phương trình đường thẳng đi qua Formatted: Font: 13 pt, Subscript các cặp điểm [(x0,y0) (x1,y1)]; [(x1,y1) (x2,y2)]; [(x2,y2) (x3,y3)],...,[(xn-1,yn-1),(xn,yn)] Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Hình 2.2 Minh họa nội suy tuyến tính[8] Thực chất nội suy tuyến tính khi biết giá trị của hàm tại nhiều điểm là nội suy tuyến tính từng khúc. Tức là sự tuyến tính chỉ xảy ra ở phạm vi cục bộ. Tập các giá trị đã biết của hàm có ảnh hưởng đến hàm nội suy. 2.2 Nội suy song tuyến tính (bilinear) Formatted: Font: 13 pt, Subscript Formatted: Font: 13 pt, Subscript Formatted: Centered, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li Formatted: Centered, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li Formatted: DMC1 Nếu như nội suy tuyến tính áp dụng với hàm một biến thì nội suy song tuyến tính được dùng trong việc nội suy hàm hai biến. Giả sử biết giá trị của hàm f tại các điểm Q11, Q12, Q21, Q22 cần tìm giá trị của hàm tại điểm P(x,y). Với P nằm trong hình vuông tạo bởi Q11, Q12, Q21, Q22 việc nội suy được thực hiện qua hai bước: Bước 1: Nội suy theo trục x để tìm ra f(R1), f(R2) Bước 2: Nội suy theo trục y để tìm ra f(P) Việc nội suy theo trục x trước hay nội suy theo trục y trước đều cho cùng một kết quả. Formatted: Justified, Line spacing: Multiple 1,3 li 18 Formatted: Centered, Line spacing: Multiple 1,3 li Hình 2.3 Minh họa nội suy song tuyến tính[10] Ta có thể áp dụng nội suy song tuyến tính vào việc nội suy ảnh vì nội suy song tuyến tính là nội suy cho hàm hai biến mà ảnh số cũng có thể biểu diễn dưới dạng hàm hai Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li biến. Thực hiện một thực nghiệm nhỏ trên matlab để quan sát kết quả của việc nội suy ảnh sử dụng nội suy song tuyến tính. Nội dung của thực nghiệm như sau: +Đọc ảnh Lena +Hạ mẫu với hệ số 2 +Nội suy phóng to ảnh hạ mẫu theo kiểu bilinear +Hiển thị ảnh gốc và ảnh nội suy +Quan sát và so sánh Thực nghiệm cho ta hai ảnh như hình vẽ dưới đây: Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li 19 Hình 2.4 Ảnh Lena nội suy bilinear Formatted: Centered, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li 20 Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li Hình 2.5 Ảnh Lena gốc Quan sát hai ảnh ta thấy độ sắc nét của ảnh nội suy không thể bằng so với ảnh gốc, ngoài ra trên ảnh nội suy xuất hiện những chi tiết lạ mà ảnh gốc không có. Điều này có Formatted: Line spacing: Multiple 1,3 li Formatted: Justified, Indent: First line: 1,27 cm, Line spacing: Multiple 1,3 li thể giải thích là do việc hạ mẫu đã làm xuất hiện những phổ lạ và chính những phổ lạ này phát sinh ra những chi tiết lạ mà ảnh gốc không có. 2.3 Nội suy spline Trong nội suy việc lựa chọn quy luật biến thiên của hàm nội suy theo biến ảnh hưởng tới kết quả nội suy. Người ta luôn cố gắng tìm ra các quy luật gần với tự nhiên. Nội suy spline (nội suy ghép trơn) phỏng theo quy luật uốn cong của thước đàn hồi khi ta ép nó chạy qua các điểm cố định. Formatted: Justified, Line spacing: Multiple 1,3 li Formatted: DMC1 Formatted: Justified, Line spacing: Multiple 1,3 li