i LỜI CẢM ƠN Trên thực tế thành công mà không gắn liền với hỗ trợ, giúp đỡ suốt thời gian từ bắt đầu học tập trường đến nay, em nhận nhiều quan tâm, giúp đỡ quý Thầy Cô Trường Đại học Công nghệ Thông tin Truyền thông - Đại học Thái Nguyên với tri thức tâm huyết để truyền đạt vốn kiến thức quý báu cho chúng em suốt thời gian học tập trường, luôn tạo điều kiện tốt cho chúng em suốt trình theo học trường Em xin chân thành cảm ơn quý Thầy Cô Ban lãnh đạo nhà trường! Với lòng biết ơn sâu sắc em xin gửi lời cảm ơn tới TS Đào Nam Anh, cán trực tiếp hướng dẫn khoa học cho em Thầy dành nhiều thời gian cho việc hướng dẫn em cách nghiên cứu, đọc tài liệu, cài đặt thuật toán giúp đỡ em việc xây dựng chương trình, em xin chân thành cảm ơn Thầy! Và cuối em xin bày tỏ lòng chân thành biết ơn tới lãnh đạo khoa Công nghệ Thông tin trường Cao đẳng Hoan Châu Nghệ An bạn bè đồng nghiệp bên cạnh lúc em khó khăn tạo điều kiện thuận lợi giúp em hoàn thành luận văn Hoàng Xuân Trung ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn kết nghiên cứu tôi, không chép Nội dung luận văn có tham khảo sử dụng tài liệu liên quan, thông tin tài liệu đăng tải tạp chí trang website theo danh mục tài liệu luận văn Tác giả luận văn Hoàng Xuân Trung iii MỤC LỤC LỜI CẢM ƠN i LỜI CAM ĐOAN ii DANH MỤC CÁC TỪ VIẾT TẮT v DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ vi MỞ ĐẦU CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN KHÔI PHỤC ẢNH 1.1 Một số khái niệm 1.1.1 Phần tử ảnh (Picture Element) 1.1.2 Mức xám (Gray level) 1.1.3 Quan hệ ảnh, điểm ảnh, mức xám 1.1.4 Lân cận điểm ảnh 1.1.5 Mối liên kết điểm ảnh 1.1.6 Đo khoảng cách điểm ảnh 1.2 Tổng quan khôi phục ảnh 1.2.1 Bài toán khôi phục ảnh 1.2.2 Ứng dụng khôi phục ảnh 1.3 Một số phương pháp khôi phục ảnh 10 1.3.1 Phương pháp khôi phục ảnh dùng kim tự tháp mờ Gaussian 10 1.3.2 Phương pháp khôi phục ảnh dùng lọc Median 12 1.3.3 Phương pháp khôi phục ảnh nhanh dựa vào lọc 13 1.3.4 Khôi phục ảnh dùng biến phân phần PDE 14 1.3.5 Khôi phục ảnh dùng phương trình Navier-Stokes 16 1.3.6 Khôi phục ảnh dùng tổng biến thể 17 1.4 Một số tiêu chí dùng để đánh giá chất khôi phục ảnh 18 1.4.1 Tổng quan tiêu chí đánh giá chất lượng ảnh 18 1.4.2 Sai số bình phương trung bình MSE 18 1.4.3.Tỷ lệ tín hiệu tín hiệu tạp PSNR 18 iv 1.4.4 Ứng dụng MSE PSNR 19 1.5 Kết luận chương 19 CHƯƠNG 2: KHÔI PHỤC ẢNH DÙNG BẢN VÁ VÀ TỐI ƯU ĐỊA PHƯƠNG 20 2.1 Khôi phục ảnh dùng vá 20 2.1.1 Khôi phục ảnh dùng vùng mẫu 20 2.1.2 Khôi phục ảnh dùng vá có kết cấu 23 2.1.3 Khôi phục ảnh dùng vá với độ thưa 26 2.1.4 Khôi phục ảnh dùng kết hợp vá biến phân phần PDE 29 2.1.5 Một số dạng khôi phục ảnh vá khác 32 2.2 Khôi phục ảnh dùng vá với điều kiện tối ưu địa phương 36 2.2.1 Bước tiền xử lý ảnh màu: Tách ảnh 36 2.2.2 Phát biểu toán phôi phục ảnh vá 37 2.2.3 Điều kiện tối ưu địa phương 37 2.2.4 Thuật toán 39 2.2.5 Đầu vào đầu thuật toán khôi phục ảnh dùng vá với điều kiện tối ưu địa phương 40 2.3 Kết luận chương 42 CHƯƠNG 3: CÀI ĐẶT THỬ NGHIỆM 43 3.1 Môi trường cài đặt 43 3.2 Kết thực nghiệm 43 3.3 So sánh với số phương pháp khác 53 3.4 Kết luận chương 54 TÀI LIỆU THAM KHẢO 56 PHỤ LỤC: TRÍCH MÃ NGUỒN 58 v DANH MỤC CÁC TỪ VIẾT TẮT Các thuật ngữ Ý nghĩa Wavelet Sóng nhỏ Inpainting Khôi phục ảnh Các từ viết tắt Ý nghĩa XLA Xử lý ảnh PDE Partial differential equation MSE Mean square error PSNR Peak Signal to Noise Ratio vi DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1: Mỗi điểm ảnh có tọa độ x, y, giá trị với ảnh xám Hình 2: Ảnh xám đồ thị theo mức xám Hình 3: Khôi phục tác phẩm hội họa Hình 4: Khôi phục ảnh đen trắng Hình 5: Khôi phục ảnh dùng kim tự tháp mờ Gaussian 11 Hình 6: Khôi phục ảnh dùng kim tự tháp mờ Gaussian 12 Hình 7: Khôi phục ảnh Median theo hướng 13 Hình 8: Khôi phục ảnh nhanh dựa vào lọc 14 Hình 9: Khôi phục ảnh biến phân phần PDE 16 Hình 10: Khôi phục ảnh dùng tổng biến thể 17 Hình 11: Ví dụ PSNR 19 Hình 12: Khôi phục ảnh dùng vùng mẫu: xác định mẫu p 21 Hình 13: Khôi phục ảnh dùng vùng mẫu: tìm miếng vá thích hợp cho p q’, q”, cuối tiến hành vá q’ cho p 21 Hình 14: Khôi phục ảnh dùng vùng mẫu 22 Hình 15: Khôi phục ảnh dùng vá có kết cấu: bên trái ảnh kết cấu, bên phải: dùng kết cấu để vá 23 Hình 16: Khôi phục ảnh dùng vá có kết cấu theo Efros Leung: 24 Hình 17: Khôi phục ảnh dùng vá có kết cấu theo Criminisi cộng sự: bên trái ảnh đầu vào, bên phải ảnh kết 25 Hình 18: Khôi phục ảnh dùng độ thưa: từ điển hình học từ điển kết cấu 28 Hình 19: Khôi phục ảnh dùng độ thưa: 28 Hình 20: Khôi phục ảnh dùng độ thưa: bên trái ảnh đầu vào bị nhiễu, bên phải ảnh kết 29 vii Hình 21: Một hình ảnh ban đầu, sau loại bỏ 15 x 15 hình vuông khôi phục lại với phương pháp giới thiệu Masnou Morel 30 Hình 22: Khôi phục dùng kết hợp vá biến phân phần PDE 31 Hình 23: Khôi phục ảnh dùng vá cho video 32 Hình 24: Khôi phục ảnh dùng vá từ ảnh khác: 35 Hình 25: Tách không gian Vector 37 Hình 26: Khôi phục ảnh dùng vá tối ưu địa phương 40 Hình 27: Khôi phục ảnh dùng vá tối ưu địa phương 41 Hình 28: Ảnh gốc mặt nạ 44 Hình 29: Kiểm tra phần biên mặt nạ 45 Hình 30: Kiểm tra phần biên mặt nạ 46 Hình 31: Khôi phục phần có kết cấu mạnh, có lỗi 47 Hình 32: Lỗi khôi phục phần có kết cấu phức tạp 48 Hình 33: Khôi phục kết cấu yếu, tốt 48 Hình 34: Khôi phục kết cấu yếu, có lỗi 49 Hình 35: Khôi phục kết cấu yếu, lỗi 49 Hình 36: Khôi phục kết cấu phức tạp, lỗi 50 Hình 37: Khôi phục kết cấu phức tạp, lỗi 51 Hình 38: Khôi phục kết cấu phức tạp, lỗi 52 Hình 39: Khôi phục kết cấu phức tạp, lỗi 52 MỞ ĐẦU Khôi phục ảnh (inpainting) trình xây dựng lại phận bị xuống cấp ảnh video Trong trường hợp tranh có giá trị, nhiệm vụ thực nghệ sĩ có tay nghề cao phục hồi tranh Trong giới công nghệ thông tin, khôi phục ảnh đề cập đến việc áp dụng thuật toán phức tạp để thay phận liệu ảnh bị bị hỏng Khôi phục ảnh có liên quan đến việc loại bỏ nhiễu, thuật toán sử dụng ý tưởng loại nhiễu, khôi phục ảnh vấn đề khác vấn đề loại nhiễu Vùng nhiễu thường có số thông tin ảnh gốc khôi phục ảnh, số vùng bị hoàn toàn liệu ảnh gốc Trọng tâm luận văn tìm hiểu vấn đề liên quan đến việc khôi phục ảnh, nghiên cứu số thuật toán khôi phục ảnh tập trung tìm hiểu thuật toán tổng hợp để tạo vùng ảnh lớn từ kết cấu mẫu, kỹ thuật lấp đầy khoảng trống ảnh nhỏ Trong giá trị màu sắc tính toán tổng hợp dựa mẫu Thuật toán thực nghiệm với chương trình sử dụng ngôn ngữ C++, MathLab Ngoài phần mở đầu kết luận, luận văn chia làm chương, luận văn có chương sau: Chương 1: Tổng quan toán khôi phục ảnh Trình bày vấn đề đặt cần giải toán khôi phục ảnh, hướng tiếp cận xử lý nhiễu ảnh khôi phục phần ảnh bị Trình bày số phương pháp Khôi phục ảnh dựa vào hàm Gaussian, khôi phục ảnh nhanh, khôi phục ảnh Bertalmio Một số phương pháp khôi phục ảnh khác Một số tiêu chí dùng để đánh giá kết khôi phục ảnh Chương 2: Khôi phục ảnh từ vá với điều kiện tối ưu địa phương Các thuật toán khôi phục ảnh vá trình bày mối liên hệ với thuật toán khôi phục ảnh vá với tối ưu địa phương Các thuật toán khôi phục ảnh vá có khả lấp khoảng trống ảnh cách tổng hợp vùng ảnh từ vùng khác Phương pháp gọi vá, lần điền thông tin, thuật toán điền mảng điểm ảnh, không điểm ảnh phương pháp dùng biến phân phần Chương 3: Thực nghiệm đánh giá Trình bày việc cài đặt chương trình, xây dựng liệu thực nghiệm với thuật toán khôi phục ảnh có khả lấp khoảng trống ảnh cách tổng hợp vùng ảnh từ vá, dựa vào độ tương tự cục bộ, trình thực nghiệm, kết CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN KHÔI PHỤC ẢNH 1.1 Một số khái niệm 1.1.1 Phần tử ảnh (Picture Element) Ảnh thực tế ảnh liên tục không gian giá trị độ sáng Để xử lý ảnh máy tính cần thiết phải tiến hành số hoá ảnh Trong trình số hoá, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua trình lấy mẫu (rời rạc hóa không gian) lượng hoá thành phần giá trị mà thể nguyên tắc mắt thường không phân biệt hai điểm kề Trong trình này, người ta sử dụng khái niệm Picture element mà ta quen gọi hay viết Pixel - phần tử ảnh, cần phân biệt khái niệm pixel hay đề cập đến hệ thống đồ hoạ máy tính Để tránh nhầm lẫn ta tạm gọi khái niệm pixel pixel thiết bị Khái niệm pixel thiết bị xem xét sau: ta quan sát hình (trong chế độ đồ hoạ), hình không liên tục mà gồm nhiều điểm nhỏ, gọi pixel Mỗi pixel gồm cặp toạ độ x, y màu [1] Hình 1: Mỗi điểm ảnh có tọa độ x, y, giá trị với ảnh xám 56 TÀI LIỆU THAM KHẢO [1] Lương Mạnh Bá, Nguyễn Thanh Thủy (1999) Nhập môn xử lý ảnh số, Nhà xuất Khoa học kỹ thuật, Hà Nội [2] Đỗ Năng Toàn, Phạm Việt Bình (2007) Giáo trình xử lý ảnh, Nhà xuất Đại học Hà nội [3] Võ Đức Khánh, Hoàng Kiếm (2007) Giáo trình xử lý ảnh Nhà xuất Đại học Quốc Gia TP Hồ Chí Minh [4] Nguyễn Kim Sách (1977) Xử lý ảnh video số, Nhà xuất Khoa học kỹ thuật, Hà Nội [5] Pablo Arias, Gabriele Facciolo, Vicent Caselles, Guillermo Sapiro, “A Variational Framework for Exemplar-Based Image Inpaiting“, Springer Science and Business Media, 2011 [6] Mahmoud Ghoniem, Youssef Chahir, Abderrahim Elmoataz, “Geometric And Texture Inpainting Based On Discrete Regularization On Graphs”, ICIP 2009 [7] Jun Zhou ; Canberra Res Lab., Robles-Kelly, A., Image Inpainting Based on Local Optimisation, Pattern Recognition (ICPR), 2010 [8] A Criminisi, P Perez, and K Toyama, "Region Filling and Object Removal by Exemplar-Based Image Khôi phục," IEEE Trans Image Processing, 13 (9), pp 1200-1212, September 2004 [9] J Sun, L Yuan, J Jia, and H.-Y Shum, “Image Completion with Structure Propagation,” SIGGRAPH, Vol 24, pp 861-868, 2005 [10] R Szeliski, R Zabih, D Scharstein, O Veksler, V Kolmogorov, A Agarwala, M Tappen, and C Rother, “A Comparative Study of Energy Minimization Methods for Markov Random Fields,” ECCV, volume 2, pages 16-29, Graz, Austria, May 2006 57 [11] Alexandru Telea, “An Image Inpainting Technique Based on the Fast Marching Method”, Journal of graphics tools, 2004 [12] A Efros and T Leung, “Texture synthesis by non-parametric sampling,” Proc IEEE International Conference Computer Vision, pp 1033-1038, Corfu, Greece, September 1999 [13] E Simoncelli and J Portilla Texture characterization via joint statistics of wavelet coefficient magnitudes 5th IEEE Int’l Conf on Image Processing, Chicago, IL Oct 4-7, 1998 [14] S Masnou and J.M Morel Level-lines based disocclusion 5th IEEE Int’l Conf on Image Processing, Chicago, IL Oct 4-7, 1998 [15] C Kenney and J Langan A new image processing primitive: reconstructing images from modified flow fields University of California Santa Barbara Preprint, 1999 58 PHỤ LỤC: TRÍCH MÃ NGUỒN Mục trích đoạn mã nguồn phân tích vá : #include "Exemplar.h" #include "Local.h" #include "Parallel.h" IplImage* exmpExtractPatch(IplImage *img, int r, int c, int size) { IplImage* ret = cvCreateImage(cvSize((size*2)+1,(size*2)+1),img>depth,img->nChannels); for(int a = -size; a height) row = img->height-1; if(row < 0) row = 0; if(col >= img->width) col = img->width-1; if(col < 0) col = 0; int x = row - (r - size), y = col - (c - size); cvSet2D(ret, x, y, cvGet2D(img, row, col)); } } return ret; } void exmpBorderFront(IplImage *msk, vector< pair >& borderPixels) { if(!msk) return; borderPixels.clear(); 59 for(int a = 0; a < msk->height; a++) { for(int b = 0; b < msk->width; b++) { if( iPixel(msk, a, b) < 128 ) continue; if( iPixel(msk, a+1, b) < 128 || iPixel(msk, a, b+1) < 128 || iPixel(msk, a-1, b) < 128 || iPixel(msk, a, b-1) < 128 ) { borderPixels.push_back(make_pair(a, b)); } } } return; } void exmpListSourcePatches(IplImage *msk, vector< pair >& sourcePatches, int patchSize, int stepSize) { if(!msk) return; sourcePatches.clear(); bool foundUncertain = false; for(int a = patchSize; a < msk->height - patchSize; a+=stepSize) { for(int b = patchSize; b < msk->width - patchSize; b+=stepSize) { foundUncertain = false; for(int a1 = a - patchSize; a1 width ) continue; if( cx2 < || cx2 >= img->height ) continue; if( cy2 < || cy2 >= img->width ) continue; if( iPixel(msk, cx1, cy1) > 128 ) continue; if( earlyExit >= 0.0 && dis > earlyExit ) return 1e50; for(int k = 0; k < img->nChannels; k++) { 61 dis += iSq( iPixel( img, cx1, cy1, k ) - iPixel( img, cx2, cy2, k ) ); } } } if( result != NULL ) (*result) = dis; return dis; } void exmpFillPatch( IplImage *img, IplImage *msk, int sx, int sy, int dx, int dy, int patchSize ) { for(int a = -patchSize; a height || cy1 >= img->width || cx2 >= img->height || cy2 >= img->width ) continue; iSixel( msk, cx2, cy2, 0.0 ); cvSet2D( img, cx2, cy2, cvGet2D( img, cx1, cy1 ) ); } } } double exmpGetConfidence( IplImage *cp, int x, int y, int patchSize ) { double thelta = 0; for(int a = x - patchSize; a 128 ) cdy = 0.0; dx = k * cdx; dy = k * cdy; d = sqrt(iSq(dx)+iSq(dy)); r++; if( r > EXMP_GRADIENT_MAX_RADIUS ) return Vector2D(0.0, 0.0); } return Vector2D( dx , dy ); } double exmpCalculateDatapoint( IplImage *img, IplImage *msk, int x, int y, int windowSize, int patchSize ) { if( patchSize height/2)+1, (mskdx>width/2)+1 ), iPixel( mskdy, (mskdy->height/2)+1, (mskdy->width/2)+1 ) ); normal.normalize(); double dataPointValue = fabs(isotope * normal) / EXMP_DATAPOINT_ALPHA; if( dataPointValue < 0.0 ) dataPointValue = 0.0; cvReleaseImage( &mskWindow ); cvReleaseImage( &mskdx ); cvReleaseImage( &mskdy ); return dataPointValue; } double exmpCalculatePriority( IplImage *img, IplImage *msk, IplImage *cp, int x, int y, int patchSize, double *result) { if( patchSize height; a++) { for(int b = 0; b < msk->width; b++) { if( iPixel(msk, a, b) < 128 ) iSixel( cp, a, b, 1.0 ); else iSixel( cp, a, b, 0.0 ); } } } void exmpSourceMask( IplImage *imsk, IplImage *smsk, int dis ) { cvDilate(smsk, smsk, 0, dis); for(int a = 0; a < smsk->height; a++) { for(int b = 0; b < smsk->width; b++) { if( iPixel(imsk, a, b) > 128 ) { iSixel(smsk, a, b, 0.0); } } } } void exmpInPaint(IplImage *img, IplImage *msk, int iter, int patchSize, int boundary, int skip, int method, bool GPU) { if(!img || !msk || iter sourcePatches; vector borderPriority; exmpSourceMask( iterMask, sourceMask, boundary ); exmpListSourcePatches( sourceMask, sourcePatches, patchSize, skip ); if( sourcePatches.size()