Tài liệu Tìm hiểu một số kỹ thuật phát hiện góc nghiêng văn bản và ứng dụng

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN Hoàng Thị Vân Anh TÌM HIỂU MỘT SỐ KỸ THUẬT PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS NGÔ QUỐC TẠO Thái Nguyên - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CẢM ƠN Em xin trân trọng cảm ơn các thầy giáo, cô giáo trong Viện Công nghệ thông tin, Khoa Công nghệ thông tin Đại học Thái Nguyên đã nhiệt tình giảng dạy và hết lòng giúp đỡ em trong quá trình học tập và nghiên cứu đề tài. Luận văn được hoàn thành tại Khoa Công nghệ thông tin dưới sự hướng dẫn của PGS.TS Ngô Quốc Tạo. Em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy. Em cũng xin chân thành cảm ơn các bạn đồng nghiệp phòng Khảo thí & Đảm bảo chất lượng trường Đại học Hải Phòng đã tạo điều kiện giúp đỡ trong quá trình hoàn thành luận văn này. Sự quan tâm, giúp đỡ của gia đình và bạn bè, đặc biệt lớp Cao học K7 Khoa Công nghệ thông tin đã cổ vũ, động viên em trong suốt thời gian học tập và thực hiện đề tài. Mặc dù có nhiều cố gắng song luận văn không thể tránh khỏi những thiếu sót, tác giả mong nhận được sự đóng góp ý kiến của các thầy cô và các bạn. Xin chân thành cảm ơn! Thái Nguyên, tháng 11 năm 2010 Tác giả Hoàng Thị Vân Anh Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Tìm hiểu một số kỹ thuật phát hiện góc nghiêng văn bản và ứng dụng” là do tôi tự tìm hiểu và đƣợc hoàn thành dƣới sự hƣớng dẫn của thầy giáo PGS. TS Ngô Quốc Tạo. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i MỤC LỤC Trang Trang phụ bìa Lời cam đoan Mục lục ........................................................................................................ ..i Danh mục các bảng ...................................................................................... iv Danh mục các hình vẽ .................................................................................. iv MỞ ĐẦU ................................................................................................................ 1 CHƢƠNG I ............................................................................................................. 3 TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN PHÁT HIỆN.............................. 3 GÓC NGHIÊNG VĂN BẢN ................................................................................... 3 1.1. Xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh. .......................................3 1.1.1. Xử lý ảnh là gì? ............................................................................................... 3 Hình 1.2: Các giai đoạn trong xử lý ảnh .................................................................. 3 1.1.2. Các vấn đề cơ bản trong xử lý ảnh ............................................................... 4 1.1.2.1. Nắn chỉnh biến dạng......................................................................... 5 1.1.2.2. Khử nhiễu ........................................................................................ 5 1.1.2.3. Chỉnh mức xám ................................................................................ 5 1.1.2.4. Phân tích ảnh.................................................................................... 6 1.1.2.5. Nhận dạng ảnh ................................................................................. 6 1.1.2.6. Nén ảnh ............................................................................................ 6 1.2. Bài toán phát hiện góc nghiêng văn bản ....................................................7 1.2.1. Giới thiệu bài toán phát hiện góc nghiêng văn bản. .................................. 7 1.2.2. Biên và phƣơng pháp phát hiện biên ................................................................. 8 1.2.2.1 Biên của đối tƣợng ảnh ........................................................................... 8 1.2.2.2 Phƣơng pháp phát hiện biên trực tiếp ................................................ 9 1.2.2.3 Phƣơng pháp phát hiện biên gián tiếp .............................................. 11 1.2.2.4. Thuật toán dò biên tổng quát .......................................................... 12 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii CHƢƠNG II .......................................................................................................... 15 MỘT SỐ KỸ THUẬT PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN ....................... 15 2.1 Biến đổi Hough ....................................................................................... 15 2.1.1 Đƣờng thẳng Hough ...........................................................................................15 2.1.2 Áp dụng biến đổi Hough xác định góc nghiêng văn bản .............................19 2.1.3 Thuật toán phát hiện góc nghiêng văn bản......................................................20 2.1.4 Chỉnh sửa góc nghiêng văn bản ........................................................................22 2.2 Phƣơng pháp hình chiếu ............................................................................... 23 2.2.1 Thuật toán Postl....................................................................................................25 2.2.2 Thuật toán Baird ..................................................................................................25 2.2.3 Thuật toán Nakano ..............................................................................................26 2.3 Phép toán hình thái - Morphology ............................................................... 26 2.3.1 Phƣơng pháp.........................................................................................................26 2.3.2 Bƣớc tiền xử lý .....................................................................................................28 2.4 Phƣơng pháp phân tích láng giềng................................................................ 35 2.4.1 Phƣơng pháp.........................................................................................................35 2.4.2 Thuật toán Yue Lu và Chew Lim Tan ............................................................37 2.5 Phƣơng pháp đƣờng thẳng............................................................................ 38 2.5.1 Tƣ tƣởng thuật toán phát hiện góc nghiêng văn bản .....................................39 2.5.1.1 Chọn các miền xác định và các đối tƣợng ........................................ 39 2.5.1.2 Lựa chọn các đối tƣợng ................................................................... 40 2.5.2 Bó cụm điểm chủ đạo .........................................................................................41 2.5.2.1 Định nghĩa ...................................................................................... 41 2.5.2.2 Phân cụm các điểm chủ đạo ............................................................ 42 2.5.3 Lựa chọn đƣờng cơ sở ........................................................................................42 2.5.3.1 Phân loại điểm chủ đạo ................................................................... 42 2.5.3.2 Xác định đƣờng thẳng sử dụng phƣơng pháp bình phƣơng nhỏ nhất 44 2.5.4 Thuật toán phát hiện góc nghiêng .....................................................................45 2.5.4.1 Thuật toán định hƣớng góc nghiêng đơn giản .................................. 45 2.5.4.2 Thuật toán chính ............................................................................. 46 2.5.5. Thuật toán sửa góc nghiêng ..............................................................................47 2.5.5.1 Mô hình quét dòng văn bản ............................................................. 47 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii 2.5.5.2 Thuật toán chỉnh sửa góc nghiêng ................................................... 48 2.5.5.3 Kết quả thử nghiệm ......................................................................... 49 Bảng 1: Kết quả thực nghiệm của các phƣơng pháp phát hiện góc nghiêng ........... 49 2.6 Một vài phƣơng pháp khác.................................................................................. 50 CHƢƠNG 3............................................................................................................ 51 NÂNG CAO TỐC ĐỘ VÀ CHẤT LƢỢNG ............................................................... 51 PHÁT HIỆN GÓC NGHIÊNG.................................................................................. 51 3.1 Xử lý ảnh có độ phân giải thấp ........................................................................... 51 3.2 Tự động xác định ngƣỡng phân loại....................................................................52 3.2.1. Mục đích và ý nghĩa việc dùng ngƣỡng. ........................................................52 3.2.2 Ý tƣởng xuất phát ................................................................................................53 3.2.3 Phƣơng pháp thực hiện .......................................................................................53 3.3 Một vài trƣờng hợp ngoại lệ .............................................................................. 56 CHƢƠNG 4............................................................................................................ 59 CÀI ĐẶT THỬ NGHIỆM ........................................................................................ 59 4.1 Sơ đồ chức năng của chƣơng trình ............................................................... 59 4.2. Thiết kế Menu ............................................................................................. 60 4.3. Giao diện chính của chƣơng trình ................................................................ 61 KẾT LUẬN ............................................................................................................ 62 TÀI LIỆU THAM KHẢO ........................................................................................ 64 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv DANH MỤC BẢNG BIỂU Bảng 1: Kết quả thực nghiệm của các phƣơng pháp phát hiện góc nghiêng…………………………………………………………………........49 DANH MỤC HÌNH VẼ Hình 1.1 Quá trình xử lý ảnh ....................................................................... 3 Hình 1.2: Các giai đoạn trong xử lý ảnh ....................................................... 3 Hình 1.3a ..................................................................................................... 7 Hình 1.3b ..................................................................................................... 7 Hình 1.4a: Các 4- láng giềng của điểm ảnh P .............................................. 11 Hình 1.4b: Các 8- láng giềng của điểm ảnh P .............................................. 11 Hình 1.5a.Chu tuyến ngoài ........................................................................... 12 Hình 1.5b. Chu tuyến trong .......................................................................... 12 Hình 1.6: Chu tuyến trong và chu tuyến ngoài của một đối tƣợng ................ 12 Hình 1.7: Hƣớng các láng giềng của một điểm ảnh ...................................... 13 Hình 1.8a: Hƣớng xác định cặp vùng nền xuất phát .................................... 14 Hình 1.8b: Hƣớng xác định cặp vùng nền tiếp theo ..................................... 14 Hình 2.1: Biến đổi Hough cho đƣờng thẳng ................................................. 16 Hình 2.2: Tham số r – φ của đƣờng thẳng .................................................... 16 Hình 2.3: Biến đổi Hough trong không gian r-  .......................................... 17 Hình 2.4: Các hình chữ nhật ngoại tiếp......................................................... 18 Hình 2.5 : Áp dụng biến đổi Hough phát hiện góc nghiêng văn .................... 19 Hình 2.6 Quay một điểm ảnh quanh gốc tọa độ ............................................ 22 Hình 2.7 Hiện tƣợng rỗ ảnh sau khi quay ..................................................... 23 Hình 2.8 a Ảnh gốc ...................................................................................... 23 Hình 2.8b Ảnh bị nghiêng 50 ........................................................................ 23 Hình 2.8 Phƣơng pháp hình chiếu đƣợc tính từ ảnh trong hình 2.8a, 2.8b .... 24 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v Hình 2.9 Một ví dụ các dòng văn bản có xu hƣớng dính lại với nhau do ảnh hƣởng của dấu .............................................................................................. 27 Hình 2.10: Các điểm left most bottom và bottom most left .......................... 28 Hình 2.11: Những khoảng góc nghiêng khác nhau đƣợc sử dụng để ƣớc lƣợng góc nghiêng phù hợp cho phần tử cấu trúc ................................................... 31 Hình 2.12: Một vài ví dụ của việc sử dụng phép đóng và mở với những phần tử cấu trúc nghiêng ....................................................................................... 32 Hình 2.13: Một thành phần liên thông dài với hệ tọa độ ảnh......................... 33 Hình 2.14a. Định nghĩa điểm chủ đạo .......................................................... 41 Hình 2.14b. Định hƣớng góc nghiêng ........................................................... 41 Hình 2.15: Điểm chủ đạo trên dòng văn bản ................................................. 43 Hình 2.16: Quan hệ láng giềng giữa các điểm chủ đạo ................................. 43 Hình 2.17: Định hƣớng thuật toán phát hiện góc nghiêng ............................. 45 Hình 2.18: Mô hình quét dòng văn bản ........................................................ 47 Hình 3.1 Một ảnh văn bản nghiêng có độ phân giải thấp .............................. 51 Hình 3.2: Ví dụ về một ảnh văn bản nghiêng với nhiều đối tƣợng phức tạp và ít ký tự .......................................................................................................... 52 Hình 3.3: Sơ đồ phân bố histogram chu vi trƣớc khi gom ............................. 55 Hình 3.4: Sơ đồ phân bố histogram chu vi sau khi gom ................................ 56 Hình 3.5 Ví dụ về một ảnh nghiêng có ít ký tự chữ cái ................................. 56 Hình 3.6 : Ví dụ về văn bản nghiêng có các đối tƣợng bao nhau .................. 57 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU 1. Lý do chọn đề tài Thông tin con ngƣời thu nhận từ thế giới bên ngoài, đến hơn 80% đƣợc ghi nhận bằng mắt tức là ở dạng ảnh. Vì vậy xử lý ảnh là một ngành khoa học đã, đang và sẽ phát triển mạnh có ứng dụng rộng rãi trong khoa học và đời sống thực tiễn nhƣ vẽ bản đồ, trong lĩnh vực quảng cáo, siêu thị, trong quân sự…. Các hệ thống xử lý ảnh cho phép con ngƣời thu nhận lƣu trữ, phân tích và nhận dạng ảnh, một bộ phận quan trọng của xử lý ảnh là xử lý văn bản. Một trong những nhiệm vụ chính cũng là đối tƣợng của xử lý ảnh văn bản là tự động hóa công việc văn phòng. Hiện nay phần lớn lƣợng thông tin vẫn còn đƣợc lƣu trữ, trình bày và phân phối thông qua phƣơng tiện chủ yếu là giấy bởi con ngƣời tin tƣởng hơn khi nhận đƣợc văn bản giấy. Tuy nhiên có xu hƣớng đang phát triển để chia sẻ và trao đổi thông tin điện tử, vì thế sự cần thiết để chuyển đổi từ tài liệu giấy sang tài liệu điện tử để lƣu trữ, khôi phục và bảo trì ngày càng tăng lên. Để chuyển đổi từ tài liệu giấy sang dạng điện tử thì kỹ thuật thƣờng gồm ba bƣớc: quét và công nghệ kỹ thuật số, phân tích bố cục và nhận dạng ký tự. Khi văn bản đƣợc quét vào máy, văn bản bị nghiêng là không thể tránh khỏi do các yếu tố khác nhau khi đƣa ảnh vào. Hầu hết các thuật toán nhận dạng ký tự, phân tích bố cục là phổ biến nhƣng lại rất nhạy cảm đối với sự biến dạng của ảnh văn bản và văn bản bị nghiêng có thể gây ra lỗi nghiêm trọng cho việc phân tích văn bản. Do đó phát hiện và chỉnh sửa ảnh văn bản bị nghiêng là cần thiết ở giai đoạn tiền xử lý để tránh nhiễu trong quá trình xử lý nghiêng. Một trong những vấn đề đầu tiên trong xử lý ảnh văn bản là bài toán góc nghiêng văn bản. Nguyên nhân dẫn đến văn bản bị nghiêng một góc xuất phát từ quá trình quét ảnh hoặc copy ảnh, dẫn đến ảnh bị lệch đi một góc tƣơng Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 ứng. Văn bản bị lệch có ảnh hƣởng rất lớn đến các quá trình xử lý ảnh tiếp theo, vì vậy việc phát hiện và chỉnh sửa góc nghiêng văn bản là nhiệm vụ quan trọng đầu tiên trong xử lý ảnh văn bản. Với những lý do trên đây nên em đã chọn đề tài: “Tìm hiểu một số kỹ thuật phát hiện góc nghiêng văn bản và ứng dụng”. 2. Mục tiêu nghiên cứu Hiểu đƣợc các phƣơng pháp phát hiện góc nghiêng văn bản. Từ đó đƣa ra những nhận xét, so sánh giữa các phƣơng pháp. Lựa chọn công cụ phát triển phù hợp cài đặt ứng dụng. 3. Đối tƣợng và phạm vi nghiên cứu Tìm hiểu một vài kỹ thuật phát hiện góc nghiêng văn bản về mặt lý thuyết, từ đó lựa chọn phƣơng pháp cài đặt ứng dụng vào thực tế. Áp dụng đối với ảnh văn bản đen trắng. 4. Ý nghĩa khoa học và thực tiễn của đề tài Hệ thống hoá các kiến thức về kỹ thuật phát hiện góc nghiêng văn bản. Việc tìm hiểu và phát triển ứng dụng thành công giúp cho việc xử lý ảnh trở nên đơn giản và dễ dàng hơn đối với một số trƣờng hợp nhƣ: xử lý ảnh ban đầu để cho ra ảnh mới theo mong muốn của ngƣời dùng (ví dụ nhƣ ảnh bị nghiêng cần xử lý để thu đƣợc ảnh chính xác hơn…). 5. Phƣơng pháp nghiên cứu 5.1 Dựa trên các tài liệu - Tìm hiểu lý thuyết liên quan đến xử lý ảnh. - Tìm hiểu lý thuyết các kỹ thuật phát hiện góc nghiêng văn bản và chỉnh sửa. 5.2 Phương pháp toán học - Xử lý các số liệu thống kê Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 CHƢƠNG I TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN 1.1. Xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh. 1.1.1. Xử lý ảnh là gì? Quá trình xử lý ảnh đƣợc xem nhƣ là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh “tốt hơn” Ảnh Xử lý ảnh Kết luận Hình 1.1 Quá trình xử lý ảnh Mục đích của xử lý ảnh gồm: - Biến đổi ảnh, làm tăng chất lƣợng ảnh. - Tự động nhận dạng ảnh, đoán nhận ảnh, đánh giá các nội dung của ảnh. Nhận biết và đánh giá đƣợc nội dung của ảnh là để phân biệt đƣợc đối tƣợng này với đối tƣợng khác, từ đó ta có thể mô tả đƣợc ảnh ban đầu. Có một số phƣơng pháp nhận dạng nhƣ: nhận dạng cạnh của một số đối tƣợng trên ảnh, tách cạnh, phân đoạn hình ảnh …. Các kỹ thuật này đƣợc ứng dụng nhiều trong y học nhƣ: xử lý tế bào, nhiễm sắc thể; nhận dạng chữ viết trong văn bản… Thu nhận ảnh (Scanner, Camera, Senssor ) Tiền xử lý Trích chọn đặc điểm Hậu xử lý Hệ quyết định Lƣu trữ Đối sánh rút ra kết luận Hình 1.2: Các giai đoạn trong xử lý ảnh Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 1.1.2. Các vấn đề cơ bản trong xử lý ảnh * Ảnh và điểm ảnh: - Điểm ảnh đƣợc xem nhƣ là dấu hiệu hay cƣờng độ sáng tại một tọa độ trong không gian của đối tƣợng ảnh. - Ảnh đƣợc xem nhƣ là tập hợp các điểm ảnh. Ảnh đƣợc biểu diễn bởi một mảng số thực hai chiều (Ii j) có kích thƣớc (m x n), trong đó mỗi phần tử Ii j (i = 1…m; j = 1…n) biểu đồ mức xám của ảnh tại vị trí (i, j) tƣơng ứng. Ảnh đƣợc gọi là ảnh nhị phân nếu các giá trị chỉ nhận 0 hoặc 1. * Mức xám: Mức xám là kết quả sự mã hóa tƣơng ứng một cƣờng độ sáng của mỗi điểm ảnh với một giá trị số - kết quả của quá trình lƣợng hóa. Cách mã hóa thƣờng dùng là 16, 32 hay 64 mức, mã hóa 256 mức là phổ dụng nhất. * Đối tƣợng ảnh: Trong quá trình xử lý ảnh, một ảnh đƣợc thu nhận vào máy phải đƣợc mã hóa, vì vậy ảnh phải đƣợc lƣu trữ thế nào sao cho các ứng dụng khác nhau có thể thao tác trên các loại dữ liệu này. Một số dạng ảnh đã đƣợc chuẩn hóa nhƣ: GIF, BMP, PCX,...; mỗi kiểu lƣu trữ ảnh đều có điểm riêng. Tùy theo vùng các giá trị xám của điểm ảnh mà các ảnh đƣợc phân chia ra thành ảnh màu, ảnh xám, ảnh nhị phân. Khi trên một ảnh chỉ có giá trị 0 hoặc 1 thì ta nói đó là ảnh nhị phân hoặc ảnh đen trắng và các điểm ảnh của nó gọi là điểm ảnh nhị phân. Việc đếm các điểm ảnh trên ảnh nhị phân đã qua biến đổi tạo điều kiện thuận lợi cho việc tách ra các đặc tính. Để tạo ra một ảnh nhị phân từ ảnh đa cấp xám ta dùng phƣơng pháp tách ngƣỡng. Các giá trị nằm ở trên ngƣỡng đƣợc gán giá trị 1 còn ở bên dƣới ngƣỡng thì đƣợc gán giá trị 0. - Kỹ thuật tách ngƣỡng: Ngƣỡng  trong kỹ thuật tách ngƣỡng thƣờng đƣợc cho bởi ngƣời sử dụng. Kỹ thuật tìm, tách ngƣỡng tự động nhằm tìm ra Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 ngƣỡng  một cách tự động dựa vào Histogram theo nguyên lý trong vật lý là vật thể tách làm 2 phần nếu tổng độ lệch trong từng phần là tối thiểu. Giả sử ta có ảnh I ~ kích thƣớc m x n; G ~ số mức xám của ảnh kể cả khuyết thiếu; t(g) ~ số điểm ảnh có mức xám ≤ g. m( g )  1 g  i.h(i) ~ mômen quán tính trung bình có mức xám ≤ g t ( g ) i 0 g  f (g) Hàm f: f (g)  t(g) 2  m( g )  m(G  1) m  n  t(g) {f ( g )} Tìm  sao cho: f ( g )  0mg ax G 1 1.1.2.1. Nắn chỉnh biến dạng Ảnh thu nhận thƣờng bị biến dạng do các thiết bị quang học và điện tử. Để khắc phục, ngƣời ta sử dụng các phép chiếu, các phép chiếu thƣờng đƣợc xây dựng trên tập các điểm điều khiển. 1.1.2.2. Khử nhiễu Có hai loại nhiễu cơ bản trong quá trình thu nhận ảnh:  Nhiễu hệ thống: là nhiễu có quy luật có thể khử bằng các phép biến đổi.  Nhiễu ngẫu nhiên: là dạng vết bẩn không rõ nguyên nhân nên có thể khắc phục bằng các phép lọc. 1.1.2.3. Chỉnh mức xám Nhằm khắc phục tính không đồng đều của hệ thống gây ra, thông thƣờng có hai hƣớng tiếp cận:  Giảm số mức xám: thực hiện bằng cách nhóm các mức xám gần nhau thành một bó. Trƣờng hợp chỉ có hai mức xám thì chính là chuyển về ảnh đen trắng.  Tăng số mức xám: thực hiện nội suy ra các mức xám trung gian bằng kỹ thuật nội suy. Kỹ thuật này nhằm tăng độ mịn của ảnh. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 1.1.2.4. Phân tích ảnh Là khâu quan trọng trong quá trình xử lý ảnh để tiến tới hiểu ảnh. Trong phân tích ảnh việc trích chọn đặc điểm là một bƣớc quan trọng, các đặc điểm của đối tƣợng đƣợc trích chọn tùy theo mục đích nhận dạng trong quá trình xử lý ảnh. Một số đặc điểm của ảnh nhƣ: đặc điểm không gian, đặc điểm biến đổi, đặc điểm biên và đƣờng biên. 1.1.2.5. Nhận dạng ảnh Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tƣợng mà ngƣời ta muốn đặc tả nó. Quá trình nhận dạng thƣờng đi sau quá trình trích chọn các đặc tính chủ yếu của đối tƣợng. Nhận dạng tự động, mô tả đối tƣợng, phân loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy, đƣợc ứng dụng trong nhiều ngành khoa học khác nhau. Hệ thống nhận dạng tự động bao gồm ba khâu tƣơng ứng với ba giai đoạn chủ yếu sau: thu nhận dữ kiệu và tiền xử lý, biểu diễn dữ liệu, nhận dạng và ra quyết định. Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là: Đối sánh mẫu dựa trên các đặc trƣng đƣợc trích chọn, phân loại thống kê, đối sánh cấu trúc, phân loại dựa trên mạng nơron nhân tạo. 1.1.2.6. Nén ảnh Lƣợng thông tin để biểu diễn cho một ảnh là rất lớn, vì vậy nén ảnh nhằm giảm thiểu không gian lƣu trữ, thƣờng đƣợc tiến hành theo cả hai khuynh hƣớng là nén có bảo toàn và nén không bảo toàn thông tin. Nén không bảo toàn thì thƣờng có khả năng nén cao hơn nhƣng có khả năng phục hồi kém hơn. Các cách nén ảnh:  Nén ảnh thống kê: Dựa vào việc thống kê tần xuất xuất hiện của giá trị các điểm ảnh, trên cơ sở đó mà có chiến lƣợc mã hóa thích hợp. Ví dụ: mã nén *.TIF. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7  Nén ảnh không gian: Dựa vào vị trí không gian của các điểm ảnh để tiến hành mã hóa. Kỹ thuật này dựa vào sự giống nhau của các điểm ảnh trong các vùng gần nhau. Ví dụ: mã nén *.PCX.  Nén ảnh sử dụng phép biến đổi: Tiếp cận theo hƣớng nén không bảo toàn, kỹ thuật này thƣờng nén hiệu quả hơn. Ví dụ: nén *.JPG.  Nén ảnh Fractal: sử dụng tính chất Fractal của các đối tƣợng ảnh, thể hiện sự lặp lại của các chi tiết. Kỹ thuật nén sẽ tính toán để chỉ cần lƣu trữ phần gốc của ảnh và quy luật sinh ra ảnh theo nguyên tắc Fractal. 1.2. Bài toán phát hiện góc nghiêng văn bản 1.2.1. Giới thiệu bài toán phát hiện góc nghiêng văn bản. Một hệ thống xử lý văn bản thƣờng giải quyết bài toán góc nghiêng văn bản nhƣ bƣớc đầu tiên và tất yếu. Nguyên nhân dẫn đến ảnh văn bản có thể bị quay hoặc nghiêng một góc bất kỳ có thể do nó đƣợc đặt trên trục quay khi quét ảnh hoặc do sự cố đặt văn bản. Ảnh văn bản bị nghiêng đƣợc hiển thị nhƣ trong hình 1.3b. Hình 1.3a Hình 1.3b Ảnh văn bản bị nghiêng một góc tƣơng ứng là 50. Trong thực tế, có thể nhìn thấy văn bản bị nghiêng với độ nghiêng ít nhất là 0,10. Nhƣ vậy, một chức năng mong muốn trong máy Photo hoặc máy quét là phát hiện và chỉnh sửa góc nghiêng một cách tự động. Ví dụ đầu vào đƣợc thể hiện nhƣ hình Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 1.3b và đầu ra đƣợc thể hiện nhƣ hình 1.3a. Thuật toán phát hiện góc nghiêng đƣợc ứng dụng cho ảnh văn bản và xác định đƣợc góc nghiêng (có thể là 0) khi đã đƣợc số hóa. Một giải pháp đơn giản để phát hiện góc nghiêng là xác định vị trí của ít nhất hai góc của văn bản gốc và tính toán góc nghiêng từ chúng. Tuy nhiên điều này có thể gây ra lỗi vì xảy ra biến dạng phi tuyến khi các trang không phẳng trên trục lăn giấy. Ngoài ra, khi quét toàn bộ bề mặt văn bản có thể bị che khuất do lỗi đƣa văn bản đầu vào trong qúa trình quét. Cùng với sự phát triển của xử lý ảnh, đã có nhiều hƣớng tiếp cận áp dụng cho bài toán phát hiện góc nghiêng văn bản nhƣ biến đổi Hough, phép chiếu, các phép toán hình thái, phân tích láng giềng,... Các đặc trƣng của từng phƣơng pháp sẽ đƣợc trình bày ở chƣơng tiếp theo. Khi xem xét một văn bản, để kết luận văn bản có bị nghiêng hay không cách làm của con ngƣời là căn cứ vào một số đối tƣợng chủ đạo và góc nghiêng văn bản đƣợc ƣớc lƣợng dựa vào đƣờng nối các điểm giữa đáy của các đối tƣợng này. Xuất phát từ nhận xét trên, luận văn sẽ trình bày một phƣơng pháp phát hiện góc nghiêng văn bản từ kỹ thuật xác định chu tuyến một đối tƣợng ảnh và áp dụng biến đổi Hough lên điểm giữa đáy hình chữ nhật ngoại tiếp các đối tƣợng có kích thƣớc chủ đạo trong ảnh. Việc xác định các hình chữ nhật này dựa vào biên hay chu tuyến ngoài của các đối tƣợng. 1.2.2. Biên và phương pháp phát hiện biên 1.2.2.1 Biên của đối tượng ảnh Biên là một vấn đề chủ yếu trong phân tích ảnh vì các kỹ thuật phân đoạn ảnh chủ yếu dựa vào biên. Có thể thấy tầm quan trọng của biên khi ta theo dõi một họa sĩ làm việc. Giả sử anh ta muốn vẽ một quả bóng, nét đầu tiên đƣợc phác họa chính là đƣờng biên của quả bóng sau đó mới đến các chi tiết bên trong. Nhƣ vậy, mới chỉ nhìn biên của sự vật ta cũng đã hình dung ít nhiều về nó và có thể phân biệt đƣợc với các sự vật khác. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Một điểm ảnh đƣợc xem là biên nếu ở đó có sự thay đổi đột ngột về mức xám. Tập hợp các điểm biên tạo thành biên hay một đƣờng bao của ảnh (boundary). Trong ảnh nhị phân, một điểm ảnh thuộc biên nếu đó là một điểm đen và có ít nhất một điểm trắng lân cận. Ta thƣờng sử dụng hai phƣơng pháp phát hiện biên cơ bản: - Phát hiện biên trực tiếp: Phƣơng pháp này làm nổi biên dựa vào sự biến thiên mức xám của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên ở đây là dựa vào sự biến đổi theo hƣớng. Nếu lấy đạo hàm bậc nhất của ảnh ta có kỹ thuật Gradient, nếu lấy đạo hàm bậc hai của ảnh ta có kỹ thuật Laplace. - Phát hiện biên gián tiếp: Nếu bằng cách nào đó ta phân đƣợc ảnh thành các vùng thì ranh giới giữa các vùng đó gọi là biên. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu nhau vì dò biên để thực hiện phân lớp đối tƣợng. Khi đã phân lớp xong nghĩa là đã phân vùng đƣợc ảnh và ngƣợc lại, khi đã phân vùng ảnh xong là đã phân lớp thành các đối tƣợng, do đó có thể phát hiện đƣợc biên. 1.2.2.2 Phương pháp phát hiện biên trực tiếp a. Kỹ thuật phát hiện biên Gradient Phƣơng pháp gradient là phƣơng pháp dò biên cục bộ dựa vào cực đại của đạo hàm. Theo định nghĩa, gradient là một vector biểu thị tốc độ thay đổi giá trị của điểm ảnh theo 2 hƣớng x và y. Các thành phần của gradient đƣợc tính bởi: fx  f ( x, y) f ( x  dx, y)  f ( x, y)  x dx fy  f ( x, y ) f ( x, y  dy)  f ( x, y )  y dy Với dx, dy là khoảng cách giữa các điểm theo hƣớng x và y (đƣợc tính bằng số điểm ảnh). Trong hệ toạ độ cực ta có: f(x,y) = f(r.cos, r.sin) x = r.cos, y = r.sin. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 f f x f y    f x cos  f y sin  r x r y r f f x f y    rf x sin   rf y cos  x  y  Trong thực tế, khi ta nói lấy đạo hàm của ảnh thực ra chỉ là mô phỏng và xấp xỉ đạo hàm bằng các kỹ thuật nhân chập hay phép cuộn. Do ảnh số là tín hiệu rời rạc nên đạo hàm không tồn tại. Kỹ thuật PreWitt: Kỹ thuật này sử dụng 2 mặt nạ theo 2 hƣớng x và y: -1 0 1 -1 0 1 -1 0 1 Hx = Hy = -1 -1 -1 0 0 0 1 1 1 dx = dy = 2 Quá trình tính toán đƣợc thực hiện qua 2 bƣớc:  Bƣớc 1: Tính I Hx và I  Hy  Bƣớc 2: Tính (I Hx ) + (I  Hy) Kỹ thuật Sobel: Tƣơng tự nhƣ kỹ thuật PreWitt, kỹ thuật Sobel sử dụng 2 ma trận mặt nạ nhân chập là: Hx = -1 0 1 -2 0 2 -1 0 1 -1 -2 -1 0 0 0 1 2 1 Hy = b. Kỹ thuật Laplace: Các phƣơng pháp đánh giá Gradient ở trên làm việc rất tốt khi độ sáng thay đổi rõ nét. Tuy nhiên, khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phƣơng pháp Gradient lại kém hiệu quả so với phƣơng pháp đạo hàm bậc 2 Laplace. Theo định nghĩa , toán tử Laplace nhƣ sau: 2f = Ta có: 2 f 2 f  x 2 y 2 2 f ( f ( x  1, y )  f ( x, y ))  f  ( ) 2 x x x x Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11  [f(x+1,y) - f(x,y)] - [f(x,y) - f(x-1,y)] = f(x+1,y) – 2f(x,y) + f(x-1,y). Tƣơng tự: 2 f  f(x,y+1) - 2f(x,y) + f(x,y-1). y 2 Mặt nạ nhân chập: H = 0 1 0 1 -4 1 0 1 0 Trong thực tế, ngƣời ta thƣờng sử dụng một số biến dạng khác của toán tử Laplace bằng cách sử dụng một số mặt nạ sau: H1 = 0 -1 0 -1 4 -1 0 -1 0 H2 = -1 -1 -1 -1 8 -1 -1 -1 -1 1 -2 1 -2 4 -2 1 -2 1 H3 = 1.2.2.3 Phương pháp phát hiện biên gián tiếp a. Định nghĩa chu tuyến Chu tuyến của một đối tƣợng ảnh là dãy các điểm của đối tƣợng ảnh P1, P2,..., Pn sao cho Pi và Pi+1 là các 8-láng giềng của nhau (i = 1, …, n – 1) và P1 là 8-láng giềng của Pn , i  Q không thuộc đối tƣợng ảnh và Q là 4-láng giềng của Pi (hay nói cách khác i thì Pi là biên 4). Kí hiệu . Trong đó 4-láng giềng đƣợc định nghĩa là các điểm trực tiếp bên trên, dƣới, trái, phải của một điểm. Và 8-láng giềng là những điểm 4-láng giềng hoặc các điểm trên trái, trên phải, dƣới trái, dƣới phải trực tiếp của một điểm. P Hình 1.4a: Các 4- láng giềng của điểm ảnh P P Hình 1.4b: Các 8- láng giềng của điểm ảnh P Chu tuyến đối ngẫu Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Hai chu tuyến C = và C‟ = đƣợc gọi là hai chu tuyến đối ngẫu của nhau nếu và chỉ nếu i j sao cho:  Pi và Qj là 4 láng giềng của nhau.  Các điểm Pi là vùng thì Qj là nền và ngƣợc lại. Chu tuyến trong Chu tuyến C đƣợc gọi là chu tuyến trong nếu và chỉ nếu:  Chu tuyến đối ngẫu C‟ của nó là chu tuyến của các điểm nền.  Độ dài của chu tuyến C‟ nhỏ hơn độ dài của chu tuyến C. Chu tuyến ngoài Chu tuyến C đƣợc gọi là chu tuyến ngoài (hình 1.5a) nếu và chỉ nếu:  Chu tuyến đối ngẫu C‟ của C là chu tuyến các điểm nền.  Độ dài của chu tuyến C‟ lớn hơn độ dài chu tuyến C. Chu tuyến C Chu tuyến C’ Chu tuyến C’ Hình 1.5a.Chu tuyến ngoài Chu tuyến C Hình 1.5b. Chu tuyến trong Chu tuyến ngoài Chu tuyến trong Hình 1.6: Chu tuyến trong và chu tuyến ngoài của một đối tƣợng 1.2.2.4. Thuật toán dò biên tổng quát Về cơ bản, thuật toán xác định chu tuyến một đối tƣợng ảnh gồm các bƣớc sau: Bước 1: Xác định cặp vùng nền xuất phát P0. Bước 2: Xác định cặp vùng nền tiếp theo . Bước 3: Lựa chọn điểm biên vùng. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn