›

Đồ án Phát hiện và hiệu chỉnh góc nghiêng trong văn bản - Lê Thành Long

pdf 60 trang huongle 2710
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Phát hiện và hiệu chỉnh góc nghiêng trong văn bản - Lê Thành Long", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_phat_hien_va_hieu_chinh_goc_nghieng_trong_van_ban_le_t.pdf

Nội dung text: Đồ án Phát hiện và hiệu chỉnh góc nghiêng trong văn bản - Lê Thành Long

  1. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Lời cảm ơn Em xin chân thành cảm ơn tất cả các thầy cô giáo trong khoa công nghệ thông tin - trường đại học dân lập Hải Phòng đã nhiệt tình giảng dạy và cung cấp cho em nhiều kiến thức quý báu. Em xin được bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Ngô Quốc Tạo, người đã tận tình hướng dẫn và tạo mọi điều thuận lợi để em hoàn thành đề tài. Xin cảm ơn các bạn trong khoa công nghệ thông tin - trường đại học dân lập Hải Phòng đã động viên, góp ý, trao đổi và hỗ trợ tôi trong suốt thời gian qua. Em xin chân thành cảm ơn! Hải Phòng, tháng 07 năm 2009 Sinh viên Lê Thành Long 1 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  2. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Lời mở đầu 4 Chương I : Tổng quan về xử lý ảnh và một số bài toán phát hiện góc nghiêng 6 1.1 Xử lý ảnh 6 1.2 Các quá trình của xử lý ảnh 7 1.3 Một số khái niệm liên quan 9 1.4 Ảnh PCX 10 1.4.1 Cấu trúc của ảnh PCX: 10 1.4.2 Kỹ thuật nén ảnh PCX 12 1.4.3 Giải thuật nén ảnh PCX 14 1.5 Một số bài toán phát hiện góc nghiêng 15 Chương II : Các phương pháp phát hiện góc nghiêng trong văn bản 17 2.1 Xác định góc nghiêng dựa vào thuật toán phân cụm láng giềng gần nhất: 17 2.1.1 Thuật toán ước lượng góc nghiêng 19 2.1.2 Kết quả thử nghiệm 23 2.1.3 Kết luận 24 2.2 Xác định góc nghiêng dựa vào các phép biến đổi Morphology 25 2.2.1 Bước tiền xử lý 27 2.2.2 Ước lượng thô 28 2.2.3 Áp dụng phép biến đổi Morphology 311 2.2.4 Ước lượng tinh 34 2.2.5 Kết quả thực nghiệm 37 2.3 Phương pháp ước lượng góc nghiêng dựa trên phép chiếu nghiêng 37 2.4 Ứng dụng phép biến đổi Hough để xác định độ nghiêng văn bản 40 2 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  3. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 2.4.1 Phép biến đổi Hough cho đường thẳng: 41 2.4.2 Thủ tục xác định độ nghiêng cho trang văn bản sử dụng phép biến đổi Hough: 48 2.4.3 Thủ tục xác định tâm cạnh dưới: 511 2.4.4 Thủ tục quay: 522 Chương III : Cài đặt chương trình 53 3.1 Sơ lược về chương trình cài đặt 53 3.2 Chương trình thực nghiệm 57 Kết Luận 59 Tài liệu tham khảo 60 3 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  4. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Lời mở đầu Trong số các thông tin con người thu nhận từ thế bên ngoài, cố đến hơn 79% đượ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 đã và đ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. 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ện vụ và là đối tượng chính của xử lý ảnh văn bản là tự động hoá công việc văn phòng. Một trong những vấn đề đầu tiên và kinh điể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 đẫ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. Do đặt ảnh vào bệ máy quét và máy in là một công đoạn được thực hiện bằng tay lên ảnh có thể bị lệch so với bệ máy một góc mà mắt thường không nhận thấy được, đẫn đến ảnh bị lệch đi một góc tương ứ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 trong đấu tiên trong xử lý ảnh văn bản. Từ hai thập kỷ gần đây, cùng với sự phát triển của xử lý ảnh văn bản, đã có nhiều phương pháp và thuật toán cho bài toán góc nghiêng văn bản. Một trong những cách tiếp cận phổ biến và dễ hiểu nhất là phương pháp hình chiếu. Phương pháp này tính histogram cho các góc khác nhau và góc lệch văn bản tương ứng là góc có histogram lớn nhất. Một thuật toàn khác phát hiện góc nghiêng văn bản là dùng biến đổi Hough. Biến đôi Hough là dụng cho một số điểm ảnh đại diện của các đối tượng và dùng một mảng tích luỹ để ước lượng góc nghiêng văn bản. Trong khi đó một số thuật toán xác định góc nghiêng văn bản bằng cách gom các nhóm đối tượng láng giềng trong 4 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  5. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản ảnh vào sử dụng một vector chỉ phương cho mỗi nhóm. Ngoài các phương pháp tiếp cận phổ biến trên bài toán góc nghiêng văn bản còn được giải quyết theo một số phương pháp khác như phương pháp dùng phép toán hình thái, phương pháp dùng logic mờ, phương pháp biến đổi Fourire v.v Khóa luận này trình bày một vài phương pháp phát hiện góc nghiêng phổ biến hiện nay. Cấu trúc của khóa luận như sau: Chương I: Tổng quan về xử lý ảnh và một số bài toán phát hiện góc nghiêng. Chương II: Trình bày các phương pháp phát hiện góc nghiêng. Chương III: Cài đặt chương trình. 5 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  6. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Chương I : Tổng quan về xử lý ảnh và một số bài toán phát hiện góc nghiêng 1.1 Xử lý ảnh Xử lý ảnh (XLA) là đối tượng nghiên cứu của lĩnh vực thị giác máy, là quá trình biến đổi từ một ảnh ban đầu sang một ảnh mới với các đặc tính và tuân theo ý muốn của người sử dụng. Xử lý ảnh có thể gồm quá trình phân tích, phân lớp các đối tượng, làm tăng chất lượng, phân đoạn và tách cạnh, gán nhãn cho vùng hay quá trình biên dịch các thông tin hình ảnh của ảnh. Cũng như xử lý dữ liệu bằng đồ hoạ, xử lý ảnh số là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ họa đề cập đến những ảnh nhân tạo, các ảnh này được xem xét như là một cấu trúc dữ liệu và được tạo bởi các chương trình. Xử lý ảnh số bao gồm các phương pháp và kỹ thuật biến đổi, để truyền tải hoặc mã hoá các ảnh tự nhiên. 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ác nội dung của ảnh là sự phân tích một hình ảnh thành những phần có ý nghĩa để phân biệt đối tượng này với đối tượng khác, dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu. Có thể liệt kê một số phương pháp nhận dạng cơ bản như nhận dạng ảnh của các đối tượng trên ảnh, tách cạnh, phân đoạn hình ảnh, Kỹ thuật này được dùng 6 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  7. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản nhiều trong y học (xử lý tế bào, nhiễm sắc thể), nhận dạng chữ trong văn bản. 1.2 Các quá trình của xử lý ảnh Thu nhận Tiền xử Phân Tách các Nhận dạng ảnh lý đoạn đặc tính và giải thích Hình 1.1: Các giai đoạn chính trong xử lý ảnh Thu nhận ảnh: Đây là công đoạn đầu tiên mang tính quyết định đối với quá trình XLA. Ảnh đầu vào sẽ được thu nhận qua các thiết bị như camera, sensor, máy scanner,v.v và sau đó các tín hiệu này sẽ được số hóa. Việc lựa chọn các thiết bị thu nhận ảnh sẽ phụ thuộc vào đặc tính của các đối tượng cần xử lý. Các thông số quan trọng ở bước này là độ phân giải, chất lượng màu, dung lượng bộ nhớ và tốc độ thu nhận ảnh của các thiết bị. Tiền xử lý: Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khử bóng, khử độ lệch,v.v với mục đích làm cho chất lượng ảnh trở lên tốt hơn nữa, chuẩn bị cho các bước xử lý phức tạp hơn về sau trong quá trình XLA. Quá trình này thường được thực hiện bởi các bộ lọc. Phân đoạn ảnh: phân đoạn ảnh là bước then chốt trong XLA. Giai đoạn này phân tích ảnh thành những thành phần có cùng tính chất nào đó dựa theo biên hay các vùng liên thông. Tiêu chuẩn để xác định các vùng liên thông có thể là cùng màu, cùng mức xám v.v Mục đích của phân đoạn ảnh là để có một miêu tả tổng hợp về nhiều phần tử khác nhau cấu tạo lên ảnh thô. Vì lượng thông tin chứa trong ảnh rất lớn, trong khi đa số các ứng dụng chúng ta chỉ cần trích một vài đặc trưng nào đó, do vậy cần có một quá trình 7 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  8. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản để giảm lượng thông tin khổng lồ đó. Quá trình này bao gồm phân vùng ảnh và trích chọn đặc tính chủ yếu. Tách các đặc tính: Kết quả của bước phân đoạn ảnh thường được cho dưới dạng dữ liệu điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh, hoặc tập hợp tất cả các điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trường hợp, sự chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý trong máy tính là rất cần thiết. Để chuyển đổi chúng, câu hỏi đầu tiên cần phải trả lời là nên biểu diễn một vùng ảnh dưới dạng biên hay dưới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh thuộc về nó. Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan tâm chủ yếu đến các đặc trưng hình dạng bên ngoài của đối tượng, ví dụ như các góc cạnh và điểm uốn trên biên chẳng hạn. Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính chất bên trong của đối tượng, ví dụ như vân ảnh hoặc cấu trúc xương của nó. Sự chọn lựa cách biểu diễn thích hợp cho một vùng ảnh chỉ mới là một phần trong việc chuyển đổi dữ liệu ảnh thô sang một dạng thích hợp hơn cho các xử lý về sau. Chúng ta còn phải đưa ra một phương pháp mô tả dữ liệu đã được chuyển đổi đó sao cho những tính chất cần quan tâm đến sẽ được làm nổi bật lên, thuận tiện cho việc xử lý chúng. Nhận dạng và giải thích: Đây là bước cuối cùng trong quá trình XLA. Nhận dạng ảnh có thể được nhìn nhận một cách đơn giản là việc gán nhãn cho các đối tượng trong ảnh. Ví dụ đối với nhận dạng chữ viết, các đối tượng trong ảnh cần nhận dạng là các mẫu chữ, ta cần tách riêng các mẫu chữ đó ra và tìm cách gán đúng các ký tự của bảng chữ cái tương ứng cho các mẫu chữ thu được trong ảnh. Giải thích là công đoạn gán nghĩa cho một tập các đối tượng đã được nhận biết. Chúng ta cũng có thể thấy rằng, không phải bất kỳ một ứng dụng XLA nào cũng bắt buộc phải tuân theo tất cả các bước xử lý đã nêu ở trên, ví dụ như các ứng dụng chỉnh sửa ảnh nghệ thuật chỉ dừng lại ở bước tiền xử lý. 8 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  9. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Một cách tổng quát thì những chức năng xử lý bao gồm cả nhận dạng và giải thích thường chỉ có mặt trong hệ thống phân tích ảnh tự động hoặc bán tự động, được dùng để rút trích ra những thông tin quan trọng từ ảnh, ví dụ như các ứng dụng nhận dạng ký tự quang học, nhận dạng chữ viết tay v.v 1.3 Một số khái niệm liên quan Ảnh và điểm ảnh: ảnh là một mảng số thực hai chiều (Ii j) có kích thước (m*n), trong đó mỗi phần tử Ii j (i=1 m, j=1 n) biểu thị mức xám của ảnh tại vị trí (i, j) tương ứng. Mức xám: là số các giá trị có thể có của các điểm ảnh của ảnh. Các điểm 4 và 8 láng giềng: giả sử (i, j) là một điểm ảnh, khi đó các điểm 4-láng giềng là : N4= {(i-1, j); (i+1, j); (i, j-1); (i, j+1)}, các điểm 8- láng giềng là : N8= N4 {(i-1, j-1); (i-1, j+1); (i+1, j -1); (i+1, j+1)}. P3 P2 P1 P4 P P0 P P P 5 6 7 Hình 1.2. Ma trận 8 láng giềng kề nhau Đối tượng ảnh: hai điểm P0 và Pn E , E tập các điểm vùng hoặc tập các điểm nền, được gọi là 8-liên thông (hoặc 4-liên thông) trong E nếu tồn tại tập các điểm được gọi là đường đi (i0, j0) (in, jn) sao cho (i0, j0) = P0 và (in, jn)= Pn, (ir, jr) E và (ir, jr) là 8-láng giềng (hoặc 4-láng giềng tương ứng) của (ir-1, jr-1) với r= 1,2, ,n. Quan hệ k-liên thông trong E (k=4,8) là một quan hệ phản xạ, đối xứng và bắc cầu. Bởi vậy đó là một quan hệ tương đương. Mỗi lớp tương đương được gọi là một thành phần k-liên thông của ảnh. Về sau ta sẽ gọi thành phần k-liên thông của ảnh là một đối tượng ảnh. 9 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  10. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 1.4 Ảnh PCX 1.4.1 Cấu trúc của ảnh PCX: Phần đầu với số bytes là 128 bắt đầu từ 0 đến 127. Khoảng này là cố định cho mọi file ảnh PCX. Thông tin của phần đầu có tác dụng là để cho những chương trình đọc file phát hiện ra các dấu hiệu đúng đắn đầu tiên của file ảnh PCX và đọc đúng các thông tin về ảnh cần đọc. Phần đầu của file định nghĩa nhiều thông số của ảnh như kích thước của ảnh, bảng màu (nếu không phải là ảnh nhị phân) và một số thông tin khác nữa. Đối với phần đầu của file PCX có tương đối nhiều khoảng trống mà không sử dụng. Cấu trúc phần đầu của file PCX gồm 16 thành phần chiếm 128 bytes. Tên thành phần Số bytes Mô tả (Hãng sản xuất )luôn manufacturer 1 luôn là A0h Vecsion 1 Số hiệu phiên bản Dấu hiệu nén ảnh (Luôn Encoding 1 là 1) Số bits để mã hoá một bits_per_pixel 1 pixel Toạ độ góc trên bên trái Xmin 2 theo chiều x Toạ độ góc trên bên trái Ymin 2 theo chiều y Toạ độ góc dưới bên Xmax 2 phải theo chiều x Toạ độ góc dưới bên Ymax 2 phải theo chiều y 10 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  11. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Bres 2 Độ phân giải ngang Vres 2 Độ phân giải dọc Pallette 48 Bảng màu n_server 1 Dự trữ color_planes 1 Số mặt phẳng màu Số bytes trên một dòng bytes_per_line 2 quét Sử dụng bảng màu hay pallett_type 2 mức xám Số bytes còn lại của Filler 58 header Hình 1.3 Sơ đồ cấu trúc phần đầu của file PCX Phần tiếp theo là lưu trữ các điểm ảnh: Phần này nằm ngay sau phần header. Vì ảnh PCX đựoc lưu trữ theo kiểu nén nên kích thước của ảnh phụ thuộc vào quá trình nén ảnh. Đối với các ảnh có cùng kích thước, cùng số bít mã hoá cho một điểm ảnh nhưng kích thước lưu trữ dữ liệu cho mỗi ảnh là tuỳ thuộc vào hiệu quả nén của từng ảnh. Phần bảng màu mở rộng: Vị trí của bảng màu hay bảng mức xám mở rộng nằm ở cuối tệp. Bảng này được sử dụng là bảng màu hay bảng mức xám là tuỳ thuộc vào trường (int)pallet_type trong phần PCXHEADER. Bảng này chỉ sử dụng cho loại file PCX đựơc mã hoá 8 bits/1 pixel.Vị trí của bảng màu mở rộng nằm ở cuối tệp, sau phần nén các điểm màu. Kích thước của phần này là 768 bytes. Dấu hiệu thứ nhất để nhận biết là có bảng màu mở rộng hay không là trường (char)version=5; dấu hiệu thứ hai là bytes 11 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  12. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản đứng ngay đằng trước bảng màu này phải là 0xC0. Hội đủ thì bảng màu mở rộng mới hoạt động được. HEADER (128 bytes) Image Extended color Patlette (768 Bytes) Hình 1.4 Sơ đồ phân bố các vùng thông tin trong ảnh PCX 1.4.2 Kỹ thuật nén ảnh PCX a) Kiểu nén: Thông tin về giá trị điểm xám cho mỗi điểm ảnh PCX được lưu trữ theo kiểu nén, khi được lưu trữ theo kiễu nén các file phải tuân theo quy luật nhất định: là một ma trận hai chiều để lưu trữ thông tin liên quan về các giá trị mức xám. Kỹ thuật dùng để nén ảnh PCX là kỹ thuật Run Length Encode (RLE), phần tử thông tin cần nén là 1 bytes. b) Tỷ số nén: Trong kỹ thuật nén ảnh người ta quan tâm nhiều đến tỷ số nén. Tỷ số nén của ảnh được tính bởi tỷ số giữa kích thước lưu trữ ảnh sau khi nén trên kích thước cần thiết để lưu trữ ảnh không nén. Giá trị của tỷ số này phụ thuộc vào mỗi file ảnh, ảnh pcx có thể là 1,4 hoặc 8 bits, nếu xét yếu tố này ảnh hưởng đến tỷ số nén ta thấy: Ảnh 1 bits (hay ảnh nhị phân) thì một bytes lưu trữ 8 bits khả năng xuất hiện mỗi mức xám là lớn (50% cho mỗi mức xám) làm cho tần xuất lặp bits là lớn, yếu tố này làm tăng khả năng nén. Nhưng phải ít nhất 3 bytes liên tiếp giống nhau trong một dòng quét thì mới có hiệu quả cho việc nén tức là tần xuất lặp ở đây không phải cho từng pixel mà là cả gói 8 pixel cùng lặp giống nhau, yếu tố này làm giảm khả 12 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  13. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản năng nén. Vậy việc nén ảnh nhị phân chỉ có ý nghĩa đối với ảnh có nền, còn đối với một số ảnh nhị phân khác việc nén không có ý nghĩa có khi càn làm tăng thêm kích thưóc của ảnh. Ảnh 4 bits (hay 16 màu) tương ứng với 4 bits mã hoá một pixel, ảnh này có 2 pixel được chứa trong một bytes. Khả năng xuất hiện cho mỗi mức màu là 1/16. Yếu tố này làm giảm đi khả năng nén so với ảnh nhị phân. Cần có ít nhất 3 bytes liên tiếp giống nhau cùng trong một dòng quét thì mới có hiệu quả nén, tần số lặp pixel ở đây là lặp gói gồm hai pixel, yếu tố này làm tăng khả năng nén hơn so với ảnh nhị phân. Ảnh 8 bits (hay ảnh 256 màu) tương ứng với 8 bits hay 1 bytes mã hoá một pixel. Khả năng xuất hiện cho mỗi mức màu là 1/256, yếu tố này làm giảm khả năng nén so với ảnh nhị phân và ảnh 4 bits. chỉ cần ít nhất 3 bytes (hay 3 pixel) liên tiếp giống nhau mà cùng nằm trong một dòng quét thì có hiệu quả nén. Như vậy đối với mỗi ảnh Pcx 1,4,8 bits màu thì mỗi loại đều có các yếu tăng hoặc giảm khả năng nén. nếu ảnh nào sử dụng nền hoặc chỉ dùng một số mức màu nhất định trong bảng màu thì có khả năng nén cao. c) Dấu hiệu nén trong file trong ảnh PCX: Cấu trúc nén trong một dòng ảnh bao gồm hai bytes, bytes đầu là dấu hiệu nén và số bytes được nén, bytes tiếp theo chứa chỉ số màu của các bytes đó. Bytes dùng làm dấu hiệu nén là một bytes đặc biệt nó được chia làm hai phần như hình vẽ sau: phần cố định 1 1 x x x x x x phần ghi số đếm Hỉnh 1.5 Cấu trúc của bytes dấu hiệu 13 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  14. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Phần cố định là C0h (1100 0000b), có 2 bits cao nhất là 1, số bits thấp hơn còn lại (gồm 6 bits) dùng để chỉ số bytes giống nhau liên tiếp. Như vậy mỗi cấu trúc chỉ có thể ghi được tối đa là 63 bytes giống nhau. Đọc một dòng ảnh vào mảng một chiều p t:=0; Gọi số bytes cho mỗi dòng quét là Bytes i = 0; ((P[t+i]=P[t+i+1]) Y and (t+i 0? P[t]>=C0h? t = t+1; Write(p[t]); N t = t+1; Write(C1h) Y t<Bytes Kết thúc 1 dòng Hình 1.6 Sơ đồ giải thuật nén một dòng ảnh cho file PCX 1.4.3 Giải thuật nén ảnh PCX Quá trình nén được tiến hành theo từng dòng như sau: + Thứ tự đầu tiên trong file ảnh PCX là dòng đầu tiên của ảnh. + Việc nén file ảnh PCX phải bắt đầu từ dòng đầu tiên của ảnh. + Kết thúc khi tất cả các dòng đều được nén. 14 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  15. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản + Mỗi một dòng nén phải tuân theo cùng một giải thuật nén của file PCX. 1.5 Một số bài toán phát hiện góc nghiêng 1) Phân cụm láng giềng gần nhất Ý tưởng chính của phương pháp này là dùng các kỹ thuật xác định biên cho các đối tượng riêng lẻ. Sau đó, với mỗi đối tượng xác định một số láng giềng gần nó nhất, dùng một vector định hướng với hai đầu là hai điểm được chọn từ hai trong số các đối tượng này để xác định góc nghiêng. Dùng một mảng tích lũy để lưu Histogram cho các góc lệch này. Nghĩa là, giá trị của mỗi phần tử mảng tích lũy sẽ cho biết nhóm láng giềng và vector định hướng cho góc bằng với chỉ số của phần tử mảng đó. Góc lệch của văn bản là góc tương ứng với phần tử Histogram lớn nhất. 2) Phương pháp dùng phép toán hình thái Một số thuật toán xác định góc nghiêng sử dụng các phép toán hình thái. Ý tưởng chủ đạo của phương pháp này xuất phát từ đặc điểm của phép đóng ảnh là có phả năng gắn các đối tượng gần nhau. Các thuật toán này thường dùng phép đóng nhiều lần với mục đích nối các dòng văn bản với nhau. Giai đoạn tiếp theo là dùng các vector chỉ phương của các dòng xác định góc nghiêng cho văn bản tương tự như trong phương pháp phân tích láng giềng. 3) Phân tích hình ảnh của phép chiếu Ý tưởng chính của phương pháp này là tính Histogram cho tất cả các góc lệch. Histogram của một góc là số điểm đen trong ảnh sao cho các điểm này nằm trên những đường thẳng có cùng một hướng tương ứng với góc đó. Sau đó, dùng một hàm chi phí áp dụng cho các giá trị Histogram này. Góc nghiêng văn bản tương ứng với góc có giá trị hàm chi phí cực đại. 15 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  16. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 4) Xác định góc nghiêng dựa vào biến đổi Hough Biến đổi Hough ánh xạ một đường thẳng trong mặt phẳng thành các cặp (r, ) trong không gian Hough với r là khoảng cách từ gốc tọa độ tới đường thẳng đó và là góc nghiêng của đường thẳng đó so với trục hoành. Góc nghiêng văn bản tương ứng là góc có tổng số điểm lớn nhất nằm trên những đường thẳng cùng lệch góc. 16 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  17. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Chương II : Các phương pháp phát hiện góc nghiêng trong văn bản 2.1 Xác định góc nghiêng dựa vào thuật toán phân cụm láng giềng gần nhất: Thuật toán láng giềng gần nhất dựa vào phương pháp phát hiện góc nghiêng tài liệu không yêu cầu sự hiện diện của một vùng văn bản nổi bật và không tùy thuộc vào hạn chế góc nghiêng. Tuy nhiên, nói chung sự chính xác của những phương pháp này không hoàn hảo. Yue Lu, Chew Lim Tan giới thiệu phương pháp láng giềng gần nhất cải tiến dựa theo cách tiếp cận thực hiện ước lượng chính xác góc nghiêng tài liệu. Kích thước hạn chế được giới thiệu với các phát hiện của những cặp láng giềng gần nhất. Sau đó lựa chọn những chuỗi với số lượng lớn nhất của các cặp láng giềng gần nhất và tính toán những độ dốc của chúng để đưa ra góc nghiêng của tài liệu ảnh. Kết quả thí nghiệm trên các loại tài liệu có chứa chữ viết khác nhau và bố trí đa dạng cho thấy hướng tiếp cận đưa ra đã đạt được tính chính xác cải thiện cho việc ước lượng góc nghiêng tài liệu ảnh và có lợi thế tồn tại ngôn ngữ độc lập. Hashizume đề xuất đầu tiên phương pháp hàng xóm gần nhất. Các thành phần kết nối được phát hiện lần đầu tiên. Véc tơ có hướng của tất cả các cặp láng giềng gần nhất của các thành phần kết nối được tích lũy trong một histogram, và đỉnh cao nhất trong histogram đưa cho ta góc nghiêng. Phương pháp này cũng được phổ biến bởi O'Gorman, cụm láng giềng gần nhất được mở rộng tới K láng giềng cho mỗi thành phần được nối. Bởi vì việc sử dụng kết nối K láng giềng có thể được thực hiện trên dòng văn bản, đỉnh kết quả histogram nói chung có thể không chính xác. 17 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  18. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Jiang đề xuất một phương pháp dựa trên biến hóa cụm láng giềng nhất, trong đó quá trình phân cụm cục bộ được tập trung vào một nhóm láng giềng đáng tin cậy. Phương pháp bình phương nhỏ nhất được thực hiện trên những láng giềng đáng tin cậy này, và góc nghiêng có liên hệ với đường thẳng được dùng để lập biểu đồ histogram. Đỉnh cao nhất trong histogram liên quan tới góc nghiêng của các tài liệu hình ảnh đầu vào. Các thuật toán đề xuất bởi Liolios cố gắng nhóm tất cả các thành phần thuộc vào cùng một dòng văn bản vào một nhóm. Vì chiều rộng và chiều cao trung bình của các thành phần được áp dụng trong quá trình đó, các phương pháp chỉ có thể đối phó với các tài liệu với một cỡ chữ khá đồng dạng. Mặc dù phương pháp láng giềng gần nhất không yêu cầu sự hiện diện của một vùng văn bản nổi bật hay không phải tùy thuộc vào hạn chế của góc nghiêng, nhưng tính chính xác của các phương pháp này không hoàn hảo. Một trong những lý do là kết quả của cặp láng giềng gần nhất có chứa một trong những phần ló đầu trên của chữ thường hoặc phần dưới của chữ thường mà dẫn tới những đường kết nối không song song đối với hướng văn bản. Lý do khác gây ra bởi khoảng cách nhỏ và những sự hỗn loạn vị trí của những cặp láng giềng gần nhất. Để thực hiện ước lượng góc nghiêng chính xác hơn, hướng tiếp cận dựa trên láng giềng gần nhất được đề xướng nghiên cứu này. Giới hạn cỡ chữ được giới thiệu nhằm dò tìm cặp láng giềng gần nhất. Sau đó lựa chọn những chuỗi với số lượng lớn nhất của các cặp láng giềng gần nhất và tính toán những độ dốc của chúng để đưa ra góc nghiêng của tài liệu ảnh. Những kết quả thực nghiệm trên những kiểu tài liệu khác nhau chứa những cách trình bày đa dạng cho thấy phương pháp được đề xuất đã đạt được tính chính xác cải thiện hơn để ước lượng góc nghiêng ảnh tài liệu. Phương pháp cải tiến này cũng chứng minh rằng cách tiếp cận được đề 18 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  19. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản xuất có khả năng độc lập về mặt ngôn ngữ , đặc biệt là nó có thể để xử lý các tài liệu với nhiều ngôn ngữ khác nhau và nhiều hướng văn bản khác nhau xuất hiện trên cùng một hình ảnh. 2.1.1 Thuật toán ước lượng góc nghiêng Định nghĩa 1: Khoảng cách trọng tâm giữa hai thành phần C1 và C2 được định nghĩa là: dc(C1,C2) = x y ở đó x xc1 xc2 y yc1 yc2 Định nghĩa 2: Khoảng cách trống giữa hai thành phần C1 và C2 được định nghĩa là: max( xl2 xr1, xl1 xr2 ) if x y d g (C1,C2 ) max( xt2 xb1, xt1 xb2 ) if y x Định nghĩa 3: Thành phần C2 là láng giềng gần nhất của thành phần C1 ([C1,C2] là 1 cặp láng giềng gần nhất), nếu: (1) hc1 hc2 với x y , hoặc wc1 wc2 với y x . (2) Cx2 > Cx1 với x y , hoặc Cy2 > Cy1 với y x . (3) dc (C1,C2 ) min dc (C1,Cm ). m (4) dg (C1,C2 ) .max(hc1,hc2 ). ở đó là không đổi, và được đặt là 1.2. Sau đó các cặp láng giềng gần nhất liền kề sẽ tạo thành một chuỗi láng giềng gần nhất nếu chúng có cùng chiều rộng hoặc chiều cao. Định nghĩa 4: chuỗi K láng giềng gần nhất (K-NNC) (NNC: Nearest neighbour chain) được định nghĩa là 1 chuỗi có chứa K thành phần 19 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  20. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản [C1,C2, ,CK], trong đó Ci+1 là láng giềng gần nhất của Ci với i= 1,2, ,K-1. Theo định nghĩa, một ảnh tài liệu có thể được chia thành một số mức độ khác nhau gồm các NNC với một hằng số K. Hình 2.1 cho hai ảnh tài liệu (một là tài liệu tiếng Anh Và một là tài liệu tiếng Trung), ở đó những thành phần được nối đã được bao trong những hình chữ nhật ngoại tiếp. Hình 2.2 (a-c) và hình 2.3 (a-c) minh họa các K-NNC với K = 2; K = 3, và K 4 tương ứng. Nói ngắn gọn quá trình các K - NNC với tất cả K 4 được đưa vào một hình ở đây. Hình 2.2 (d-f) và hình 2.3 (d-f) cho thấy đường kết nối NNC của hình 2.2 (a-c) và hình 2.3 (a-c) tương ứng. Chúng ta có thể thấy rằng các góc của những đường dốc này phản ánh độ góc nghiêng tài liệu nói chung, đặc biệt là đối với những tài liệu có K lớn hơn. (n) (n) (n) (n) Định nghĩa 5: Giả thiết S [C1 ,C2 , ,CK ] là K-NNC thứ n (n=1,2, ,N), độ dốc của nó được định nghĩa như sau: (x(n) x(n) )/(y(n) y(n) ) ck c1 ck c1 if x(n) x(n) y(n) y(n) (n) ck c1 ck c1 slopeK (y(n) y(n) )/(x(n) x(n) ) ck c1 ck c1 if y(n) y(n) x(n) x(n) ck c1 ck c1 Đối với một hằng số K, chúng ta có thể thu được giá trị trung bình hoặc trung tuyến các đường dốc của các NNC. Giá trị có thể được dùng để đại diện cho góc nghiêng tài liệu. Chúng ta sử dụng giá trị đối với một K lớn hơn như giá trị góc nghiêng tài liệu, tùy theo điều kiện số lượng các K-NNC được rút ra lớn hơn một ngưỡng đã định nghĩa từ trước. Ngưỡng sử dụng ở đây là để đảm bảo có đầy đủ các NNC cho K đặc biệt, với mục đích tránh ảnh hưởng của nhiễu. 20 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  21. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Hình 2.1: Những hình ảnh tài liệu mà ở đó các thành phần kết nối được giới hạn: (a) Tài liệu tiếng Anh, (b) Tài liệu tiếng Trung Hình 2.2: Các NNC của hình 2.1(a): (a)K=2 (b)K=3 (c)K 4 (d)đường kết nối với K=2 (e)đường kết nối với K=3 (f)đường kết nối với K 4. 21 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  22. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Hình 2.3: Các NNC của hình 2.1(b): (a)K=2 (b)K=3 (c)K 4 (d)đường kết nối với K=2 (e)đường kết nối với K=3 (f)đường kết nối với K 4. Thuật toán ước lượng góc nghiêng được tổng kết như sau: (1) Phát hiện tất cả các thành phần trong ảnh, và hợp nhất hai thành phần kết nối nếu một thành phần được bao quanh bởi một thành phần khác. (2) Phát hiện láng giềng gần nhất của mỗi thành phần, theo định nghĩa 3. Chú ý rằng một số thành phần không thể tìm được các láng giềng gần nhất như đã đề cập truớc đây. (3) Xác định chuỗi láng giềng gần nhất theo định nghĩa 4 (4) Khởi tạo K là số lượng các thành phần lớn nhất trong tất cả các NNC tạo ra từ bước 3. (5) Tính số (N) của các K-NNC. (6) Nếu N lớn hơn ngưỡng đã định nghĩa trước (nó được đặt theo 22 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  23. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản thực nghiệm 3), đến bước 7; nếu không thì K=K-1, đến bước 5. (n) (7) Tính mỗi đường dốc K-NNC slopeK (n 1,2, , N) theo định nghĩa 5. (8) Thu được đường dốc tài liệu SD bằng cách sử dụng giá trị trung bình hoặc trung tuyến của đường dốc từ bước 7. (9) Tính góc nghiêng arctan(SD ) *180/ . 2.1.2 Kết quả thử nghiệm Để xác minh tính hợp lệ của phương pháp tiếp cận được đề xuất trong nghiên cứu này để ước lượng góc nghiêng hình ảnh tài liệu, các thí nghiệm đã được tiến hành trên nhiều loại tài liệu có độ rộng khác nhau với bố trí đa dạng và mức độ góc nghiêng khác nhau. Những tài liệu này bao gồm không chỉ có văn bản, mà còn có đồ họa, bảng biểu, sơ đồ, công thức toán học. 280 hình ảnh tài liệu kiểm tra được sử dụng trong các thí nghiệm. Trong số này, 32 văn bản được lựa chọn từ cơ sở dữ liệu hình ảnh tài liệu Tiếng Anh UW, và 78 tài liệu được thu thập từ các tài liệu quét của học sinh (cơ sở dữ liệu NUSST) được cung cấp bởi các kỹ thuật Thư viện của trường đại học, 4 văn bản số là hình ảnh của máy fax. Góc nghiêng của các tài liệu này thường nhỏ, ví dụ trong khoảng [-100, +100]. Chúng tôi cũng quét 6 tài liệu từ báo tiếng Trung Quốc với kết quả 100 DPI, cũng có chứa một số bảng biểu hoặc đồ họa. Bên cạnh văn bản tiếng Trung Quốc, một số tài liệu cũng chứa văn bản Tiếng Anh. Các dòng văn bản ngang và dọc có thể xuất hiện trong phạm vi một tài liệu, và có thể là ký tự tiếng Trung Quốc được đơn giản hoá hoặc ký tự tiếng Trung Quốc truyền thống. Ngoài ra, còn quét 3 tài liệu tiếng Tamil để kiểm tra thêm khả năng xử lý các chữ viết khác nhau. Các hình ảnh tài liệu được quét này, cũng như một số lựa chọn từ các cơ sở dữ liệu UW và cơ sở dữ liệu NUSST, sau đó đã được cố xoay ở các góc khác nhau được 23 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  24. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản chọn từ trước theo cả hai hướng cùng chiều kim đồng hồ và ngược chiều kim đồng hồ, từ -450 đến +450, bằng cách sử dụng Adobe Photoshop. 166 hình ảnh tài liệu thu được thông qua cách này. Hình 2.4 Một số kết quả tiêu biểu về ước lượng góc nghiêng (trong tất cả các độ) (A: phương pháp của Hashizume, B: phương pháp của Jiang, C: phương pháp được đề xuất sử dụng giá trị trung bình). 2.1.3 Kết luận Phương pháp láng giềng gần nhất cải tiến được đưa ra để tự động ước lượng tính xiên góc độ trong ảnh tài liệu. Để phát triển một thuật toán với độ chính xác cao, giới hạn kích cỡ được giới thiệu trong việc phát hiện các cặp láng giềng gần nhất. Sau đó, các chuỗi với một số lượng lớn nhất có thể của các cặp láng giềng gần nhất được lựa chọn, và các độ dốc của chúng được tính cho để đưa các góc nghiêng của ảnh tài liệu. Kết quả thử nghiệm trên các loại tài liệu khác nhau có chứa các chữ viết với ngôn ngữ khác nhau và bố trí đa dạng cho thấy rằng phương pháp được đề xuất đã đạt được hiệu suất đầy triển vọng và độ chính xác cải thiện cho việc phát hiện góc nghiêng ảnh tài liệu. Phương pháp được đề xuất có thể phát hiện thành công các góc 24 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  25. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản nghiêng của các tài liệu khác nhau, mà không giới hạn góc nghiêng, và không có yêu cầu của vùng văn bản nổi bật. Nó có khả năng giải quyết với các tài liệu của các chữ viết khác nhau và thậm chí với các hướng văn bản khác nhau xuất hiện trên cùng một ảnh. Vì vậy, nó có khả năng giải quyết các vấn đề góc nghiêng trong hầu hết các chiều tổng quát. 2.2 Xác định góc nghiêng dựa vào các phép biến đổi Morphology Thuật toán này đặc biệt thích hợp cho các văn bản có dấu. Đối với loại văn bản này, việc xuất hiện của các dấu, phần phụ trên, phần phụ dưới của chữ cũng như nhiễu đã làm cho các dòng lân cận nhau có xu hướng dính lại với nhau. Chính điều này đã làm cho các phương pháp xác định góc nghiêng văn bản trước đây bị thất bại. Bằng cách sử dụng các phép biến đổi Morphology, dấu, nhiễu sẽ bị tách khỏi ảnh văn bản. Nó giúp cho việc xác định các dòng văn bản dễ dàng hơn. Quá trình loại bỏ nhiễu và dấu nhờ vào các phép biến đổi Morphology có thể làm mất một số thông tin của văn bản. Tuy nhiên, sự mất mát đó không quan trọng, vì góc nghiêng của văn bản được đặc trưng bởi các dòng văn bản ngay cả sau khi đã loại bỏ phần phụ trên và phụ dưới. Trong phương pháp của Chen và cộng sự, các phép đóng, mở với các phần tử cấu trúc khác nhau được sử dụng. Sau khi thực hiện các phép biến đổi này, các dòng văn bản sẽ biến thành các vệt thon dài rồi áp dụng một phương pháp khác để xác định hướng của các dòng văn bản. Trong quá trình áp dụng, có thể xuất hiện một số hướng sai lệch chúng được tạo ra bởi nhiễu và các thành phần liên thông không phải là text. Một thuật toán khác là “good lines selection” sẽ được sử dụng. Trong thuật toán này, các dòng có hướng gần giống với hướng cơ bản của toàn văn bản sẽ được chọn ra. Cuối cùng, góc nghiêng của toàn văn bản sẽ được ước lượng từ các hướng đã 25 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  26. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản chọn ra này. Tuy nhiên, phương pháp này chỉ áp dụng được cho các văn bản có độ nghiêng là ±5o và độ chính xác là 0.5o. Das và Chanda cũng dùng các phép đóng, mở trên các dòng văn bản với hai thành phần cấu trúc dạng đường thẳng và dạng hình vuông nhỏ. Ảnh văn bản đã được thực hiện phép mở sẽ được quét theo chiều dọc để ghi nhận các pixel có sự chuyển đổi từ 1 sang 0, đó cũng chính là base line của dòng văn bản. Các dòng có chiều dài lớn hơn một ngưỡng cho trước sẽ được chọn ra và góc của toàn bộ văn bản là trung vị của góc các dòng văn bản này. Giới hạn của phương pháp này là nó chỉ thực hiện tốt đối với các ảnh văn bản có góc nghiêng dưới 15o. Najman lại hiện thực các phép toán Morphology theo một cách khác. Ý tưởng chính là tìm ra góc quay tối ưu nhất của các phần tử cấu trúc bằng cách cực đại hóa diện tích của các vệt thẳng tạo ra từ các phép toán Morphology. Trong hướng tiếp cận này, thuật toán Run-Length Smoothing closing (RLSA) cũng được sử dụng để tối ưu hóa góc quay của phần tử cấu trúc. Góc quay này cũng chính là góc nghiêng của toàn bộ văn bản. Nhược điểm lớn nhất của cả ba phương pháp vừa trình bày ở trên là chúng phụ thuộc vào kích cỡ chữ, khoảng cách giữa các dòng, khoảng cách giữa các kí tự lân cận trong văn bản, .Do đó các thuật toán này rất phụ thuộc vào các tham số thực nghiệm và không thể xác định các tham số này một cách tự động. Nghiên cứu này cũng sử dụng các phép biến đổi Morphology để ước lượng góc nghiêng của ảnh văn bản. Tuy nhiên, khác với các phương pháp khác, phương pháp này có thể phù hợp với tất cả các loại văn bản với bất kì góc nghiêng. Hơn thế nữa, trong phương pháp này hầu hết tất cả các tham số 26 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  27. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản được tính toán dựa trên ảnh văn bản đầu vào. Do đó trong phương pháp này độc lập với tham số và chúng được tính toán tự động. Ý tưởng chính của phương pháp này có thể được tóm tắt như sau: trước hết là quá trình tiền xử lý, đây là quá trình dùng để lọc nhiễu, dấu và những thành phần liên thông lớn. Trong quá trình này các tham số như chiều cao và chiều rộng đặc trưng của chữ, sẽ được tự động xác định dựa trên văn bản đầu vào. Sau đó, thuật toán ước lượng thô sẽ xác định được khoảng mà góc nghiêng của văn bản rơi vào. Cuối cùng, với những tham số tìm thấy ở bước đầu tiên, sẽ thực hiện các phép đóng và mở cho các dòng văn bản để tạo thành các vệt tạo thuận lợi cho bước xác định góc nghiêng tiếp theo. Sau đó một thuật toán đơn giản sẽ được dùng để xác định góc của mỗi dòng văn bản và góc nghiêng của toàn bộ văn bản cũng sẽ được tìm thấy dựa trên góc nghiêng của các dòng văn bản. 2.2.1 Bước tiền xử lý Trong bước này, chúng ta sẽ lần lượt xác định các lược đồ về chiều cao và chiều rộng của tất cả các thành phần liên thông trong văn bản. Chiều cao và chiều rộng xuất hiện nhiều lần nhất của các thành phần liên thông, gọi là W và H, sẽ được xác định nhờ vào việc tìm ra đỉnh của những lược đồ này. Trong quá trình lọc dấu và nhiễu, các thành phần liên thông có chiều cao và chiều rộng nhỏ hơn T0 × min{W, H} được xem là nhiễu và dấu, có nghĩa là đối với mỗi thành phần liên thông c(w, h), trong đó w và h là chiều cao và chiều rộng của nó. Nếu max{w, h} ≤ T0 × min{W, H}, c sẽ bị loại khỏi văn bản chúng ta đang xem xét. Đối với việc loại bỏ các thành phần liên thông lớn, nếu một thành phần liên thông c(w, h) được gọi là thành phần liên thông lớn khi 27 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  28. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản min{w,h} 1/T0 max{W,H}, nó cũng sẽ bị loại ra khỏi ảnh văn bản. Thuật toán này đã kiểm nghiệm trên nhiều giá trị khác nhau của T0 trên nhiều ảnh văn bản và đã nhận thấy giá trị tối ưu nhất của T0 là 1/4. 2.2.2 Ước lượng thô Sau khi thực hiện bước tiền xử lý, chúng tôi sẽ có được hai ảnh gọi là bottom profile và left profile. Bottom profile được tạo ra bằng cách thay thế mỗi thành phần liên thông bằng một điểm bottom most left, tương tự left profile được tạo ra dựa trên các điểm left most bottom của các thành phần liên thông. Đối với các góc trong khoảng [-45o, 45o], các điểm bottom most left sẽ đặc trưng cho đường base lines của văn bản. Tuy nhiên trong trường hợp góc nghiêng văn bản lớn, các điểm left most bottom của thành phần liên thông sẽ biểu thị cho các base lines tốt. Hình 2.5 Các điểm left most bottom và bottom most left của thành phần liên thông Hình 2.6 Base Line (Đường cơ sở), ascender (Phần phụ trên), descender (Phần phụ dưới) 28 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  29. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Trong mỗi profile (bottom hay left), góc của mỗi cặp điểm lân cận được tính và thống kê vào trong lược đồ góc. Lân cận của một điểm p trong ảnh profile được xác định bằng cách quét tất cả các điểm (trừ p) trong một hình chữ nhật có kích thước (2W, 2H) với tâm là điểm p, trong đó W và H được lấy ở bước tiền xử lý. W và H là bao nhiêu sẽ tùy thuộc vào ảnh văn bản đầu vào. Do đó, phương pháp của chúng tôi chỉ dựa vào các tham số không đơn vị. Mục đích chính của ước lượng thô là tìm ra một khoảng 20o mà góc nghiêng thực của văn bản thuộc về. Lý do mà chúng tôi chọn 20o cho khoảng ước lượng góc nghiêng sẽ được giải thích rõ trong phần sau. Trong mỗi profile chúng ta sẽ tính diện tích phần đen của mỗi khoảng, khoảng nào có diện tích lớn nhất trong 9 khoảng của đồ thị tương ứng sẽ được chọn ra. Trong hai khoảng vừa tìm được, ta chọn khoảng có diện tích lớn hơn và đó cũng chính là khoảng mà góc nghiêng văn bản thuộc về. Trong hình 2.6, khoảng được chọn là khoảng tìm thấy từ left profile (hình 2.6(c)). (a) 29 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  30. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản (b) (c) (d) (e) Hình 2.7: Một ví dụ về ảnh văn bản và các profile của nó. (a) là ảnh văn bản gốc, (b) là bottom profile, (c) là left profile, (d) và (e) là các lược đồ phân bố góc của văn bản tìm được nhờ (b) và (c). 30 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  31. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 2.2.3 Áp dụng phép biến đổi Morphology Các phép giãn (dilation), co (erosion), mở (opening) và đóng (closing) của một ảnh nhị phân I bởi thành phần cấu trúc E được kí hiệu lần lượt là I E , I E , I E , I E và được định nghĩa như sau: (1) I E z Z 2 | z x y for somex I and y E (2) I E x Z 2 | x y I forevery y E (3) I E I E E (4) I E I E E Phép tự giãn (k-fold dilation) của tập hợp các thành phần cấu trúc E là: (5) ( k E) (E E E)/k,k 1 Trong bước này, chúng ta sẽ thực hiện các phép đóng và mở cho các dòng văn bản. Phép đóng dùng để nối các kí tự trong một từ, và các từ trong một dòng, phép mở để loại bỏ các thành phần liên thông rất nhỏ, cũng như các phần phụ trên hay phần phụ dưới của ký tự. Do đó các dòng văn bản sẽ trở thành các vệt thon dài. Tuy nhiên, để thực hiện các phép đóng, mở một cách hiệu quả nhất ta cần xác định kích cỡ và hình dạng của các phần tử cấu trúc thật chính xác. Trong thuật toán này, chúng tôi xin đề nghị một cách tính toán đơn giản được mô tả như sau: Trung điểm của khoảng mà góc nghiêng văn bản thuộc về tìm được trong bước ước lượng thô chính là góc quay của phần tử cấu trúc. Ví dụ khoảng mà góc nghiêng văn bản rơi vào [30o, 50o], thì góc quay của phần tử cấu trúc sẽ là 40o. Lý do mà chúng tôi chia góc quay của văn bản thành 9 phần và mỗi phần tương ứng với 20o là vì mỗi góc quay α của phần tử cấu trúc có thể phù hợp cho tất cả các văn bản có góc nghiêng trong khoảng [α – 10o, α + 10o], nghĩa là khoảng chênh lệch là 20o. Qua thực 31 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  32. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản nghiệm bằng cách quan sát và thử nghiệm trên một số lượng lớn các ảnh văn bản, cho thấy việc xác định góc quay cho các phần tử cấu trúc là rất quan trọng. Nó giúp cho kết quả của các phép đóng mở là đúng đắn nhất. Với một phần tử cấu trúc phù hợp, thì chỉ các từ trong cùng dòng mới kết hợp lại được với nhau trong khi đó từ trong các dòng khác nhau sẽ vẫn rời nhau. Hình 2.8 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. Gọi I là ảnh thu được sau khi khử nhiễu, dấu và những thành phần liên thông lớn. Ảnh Ico được tạo ra như sau: (6) Ico I m Ec n Eo Trong đó những phần tử cấu trúc 1×3 và 2×2 được chọn tương ứng với Ec và Eo; m và n được xác định bởi max{W/2z, H/z} và max{W/3z, H/2z}; với z là độ thu nhỏ thích hợp của ảnh, z được tính như sau: z = min{W / 4, H / 5} α được tính bằng thuật toán ước lượng thô; và m Ec và n Eo là những kết quả của phép quay những phần tử cấu trúc m Ec và n Eo bởi góc α (hình 3.5 là một minh họa của ảnh Ico). Một lần nữa, có thể thấy rõ ràng rằng kích thước và góc nghiêng của phần tử cấu trúc được xác định một cách tự động và chỉ dựa trên ảnh đưa vào ban đầu. Với việc tính toán tự động này, thuật toán mà chúng tôi đề nghị 32 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  33. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản có thể áp dụng để giải quyết vấn đề ước lượng góc nghiêng của những văn bản có góc nghiêng tùy ý. (a) (b) (c) Hình 2.9 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. Hình 2.9a là những ảnh đưa vào ban đầu. Hình 2.9b là kết quả của việc áp dụng bước tiền xử lý, ước lượng thô, và phép đóng tương ứng với hình 2.9a. Hình 2.9c là kết quả của việc áp dụng phép mở tương ứng với hình 2.9b. 33 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  34. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 2.2.4 Ước lượng tinh Sau khi áp dụng phép đóng và phép mở, những dòng văn bản của ảnh đã được bôi đen được xem như là những thành phần liên thông. Trong bước này, chúng tôi đề nghị một thuật toán đơn giản sử dụng để ước lượng hướng của tất cả những thành phần liên thông và của toàn văn bản. Gọi o là một thành phần liên thông, nghĩa là o = {(xi, yi), i = 1, , n}. * Gọi pi (xi, yi) là một điểm tùy ý thuộc o. Chúng ta cần tìm góc α của thành phần liên thông o (xem hình 2.9). Hình 2.10: Một thành phần liên thông dài với hệ tọa độ ảnh. Gọi p'i là kết quả của phép quay pi theo một góc với tâm c(xc,yc) của o, nghĩa là, p'i (x'i , y'i ) trong đó: x'i (xi xc ) cos (yc yi ) sin xc y'i (yi yc )cos (xi xc )sin yc . Gọi dyi là khoảng cách đại số giữa và pi. dyi có thể được tính như sau: (7) dyi y'i yc (yi yc )cos (xi xc )sin Gọi T( ) là tổng những bình phương của dyi, i=1,2, ,n n n 2 2 (8) T dyi yi yc cos xi xc sin i 1 i 1 34 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  35. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Trong đó c(xc, yc) là tâm của thành phần liên thông o. Góc * của một thành phần liên thông o (với trục x) được xác định: (9) * arg min T T( ) sẽ đạt cực trị nếu đạo hàm của nó bằng 0, nghĩa là T ' 0 . Chúng ta có: n 2 2 2 2 T [(yi yc ) cos (xi xc ) sin 2(xi xc )(yi yc )sin cos ] (10) i 1 Acos2 B sin2 2C sin cos Trong đó: n 2 (11) A = (yi yc ) i 1 n 2 (12) B = (xi xc ) i 1 n (13) C = (xi xc )(yi yc ) i 1 Cho nên: (14) T'( ) (B A) sin 2 2C cos2 arctan 2C A B 2 if A B (15) T ' 0 4 if A B Bởi vì phương trinh T'( ) có 2 nghiệm (sự khác nhau là π của hàm tan) mà: (16) 1 or 2 2 Vì vậy: * 1 if T 1 T 2 (17) 2 otherwise 35 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  36. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Vì phương trình có 2 nghiệm 1, 2 nên khi thay vào biểu thức T( ) ta sẽ có được hai giá trị T1( ) và T2( ), chọn ứng với biểu thức làm cho T( ) nhỏ hơn. Sau khi áp dụng thuật toán này, mỗi thành phần liên thông được đặc trưng bởi một cặp số (α*, T(α*)/n), trong đó n là số điểm thuộc thành phần liên thông đó. Một thành phần liên thông được xem là đáng tin cậy nếu như * tỷ lệ T(α )/n nhỏ hơn một ngưỡng được định nghĩa trước là T1. Trong quá trình thực nghiệm, chúng tôi đặt T1 là 0.007. Chỉ những thành phần liên thông đáng tin cậy mới được giữ lại cho quá trình xử lý kế tiếp trong khi những cái khác sẽ được loại bỏ. Từ kết quả của ước lượng thô, giả sử rằng khoảng góc tìm được là [β,γ]. Bởi vì ước lượng thô có thể đưa ra những kết quả không chính xác, nên chúng tôi mở rộng khoảng này với một giá trị cho trước là 2o, nghĩa là khoảng góc nghiêng của văn bản rơi vào sẽ là [β – , γ + ]. Trong quá trình trình thực nghiệm, ước lượng thô có thể cho kết quả sai khi góc nghiêng của văn bản gần với biên giữa hai khoảng gần kề nhau. Chúng tôi cũng quan sát thấy rằng độ lệch đối với đường biên của góc nghiêng thật sự không vượt quá 2o. Cho nên, được đặt là 2o. Những thành phần liên thông đáng tin cậy mà hướng của nó rơi ra ngoài khoảng [β – , γ + ] sẽ bị loại bỏ. Sau đó, khoảng [β – , γ + ] sẽ được chia thành nhiều khoảng nhỏ hơn, mỗi khoảng sẽ có độ rộng tương ứng là 0.1o, và đồ thị biểu diễn sự phân bố góc của tất cả những thành phần liên thông còn lại sẽ được tính với những khoảng nhỏ này. Cuối cùng, đỉnh của đồ thị này sẽ được chọn là góc nghiêng của toàn văn bản. 36 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  37. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 2.2.5 Kết quả thực nghiệm Trong phần so sánh, phương pháp của Chen sẽ được đem ra so sánh với phương pháp đã đề xuất này. Phương pháp Phương pháp Chen Phương pháp đề xuất Văn bản Tất cả văn Văn bản Tất cả văn Loại văn bản tiếng Latinh bản (1080 tiếng Latinh bản (1080 (900 ảnh) ảnh) (900 ảnh) ảnh) Độ chính xác 94.78% 89.26% 99.00% 96.67% Độ lệch góc 0.13o 0.15o 0.15o 0.15o Hình 2.11 Kết quả so sánh giữa phương pháp của Chen và phương pháp được đề xuất Tóm lại, những kết quả thực nghiệm trên đã chỉ ra rằng phương pháp này là độc lập với tham số, bởi vì hầu hết những tham số đều không có đơn vị, và chúng được tính một cách tự động. Thêm vào đó phương pháp này lại không phụ thuộc vào góc nghiêng cũng như độ phân giải của ảnh văn bản đầu vào. 2.3 Phương pháp ước lượng góc nghiêng dựa trên phép chiếu nghiêng Những phương pháp chiếu nghiêng rất phổ biến cho việc xác định độ lệch. Một hình chiếu nghiêng là một biểu đồ tần suất của số các giá trị điểm đen tích luỹ lại ứng với các dòng mẫu trên toàn bộ trang. Nghiêng có thể ở góc bất kỳ, nhưng thường thì nó được thực hiện theo hướng nằm ngang dọc theo các dòng hoặc theo hướng thẳng đứng vuông góc với các dòng; những độ nghiêng được gọi là các hình chiếu nghiêng theo các hướng nằm ngang hoặc thẳng đứng. Với một tài liệu mà các dòng văn bản của nó nằm ngang thì hình chiếu nghiêng theo hướng nằm ngang sẽ có đỉnh với độ rộng bằng chiều cao ký tự và các vùng trũng có độ rộng bằng khoảng cách giữa các 37 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  38. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản dòng. Với các tài liệu gồm nhiều cột, phương pháp chiếu nghiêng theo phương thẳng đứng sẽ thu được số khối tương ứng với số cột, các khối được phân chia bởi các vùng chũng tạo bởi các khoảng trống giữa các cột và lề giấy. Hình 2.12 Một phần của hai cột văn bản được thể hiện ở phía trên bên trái. Các hình chiếu nghiêng theo chiều thẳng đứng và nằm ngang của văn bản này cũng được trình bày: Đối với phép chiếu nghiêng theo chiều nằm ngang, mỗi cột ứng với một dòng văn bản; đối với phép chiếu nghiêng theo chiều thẳng đứng, mỗi khối ứng với một cột. Một cách sử dụng trực tiếp nhất đối với phương pháp chiếu mặt nghiêng trong việc xác định góc nghiêng là tính toán độ lệch của góc gần với hướng mong muốn (Postl). Với mỗi góc nghiêng, người ta đo chiều cao các hộp theo mặt nghiêng và hộp nào có chiều cao lớn nhất sẽ cho ta góc lệch 38 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  39. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản cần tìm. Tại góc lệch chuẩn, vì các dòng quét đã được sắp thẳng hàng theo các dòng văn bản, nên mặt cắt nghiêng sẽ có các đỉnh lồi với độ cao lớn nhất và các vùng trũng ứng với khoảng trống giữa các dòng văn bản. Đối với kỹ thuật chung này người ta có thể cải tiến và điều chỉnh để lặp lại một cách nhanh hơn đối với việc chuẩn hoá góc nghiêng và xác định góc nghiêng chính xác hơn. Baird tiến hành sửa đổi phương pháp mặt cắt nghiêng này để nâng cao tốc độ và độ chính xác trong xác định độ lệch. Trước hết, các phần kết nối được “xác định” và trung điểm cạnh dưới cũng được thể hiện. Người ta xác định tổng các độ lệch (như sự chênh lệch về chiều cao giữa các điểm lồi và lõm) đối với các góc nghiêng khác nhau. Giá trị thu được đối với mỗi góc sẽ được đo bởi số các điểm thuộc dòng cơ sở nằm trên đường chiếu theo góc ấy. Chiều cao của các cột càng lớn thì góc nghiêng càng tiến tới không. Giá trị đo được lớn nhất sẽ cho góc lệch thực sự. Độ chính xác của phương pháp này thường đạt trong phạm vi 0.5 độ so với hướng chuẩn. Do việc xác định được tiến hành bằng cách sử dụng các trung điểm cạnh đáy của mỗi hộp nên có một giả định rằng trang giấy được đặt gần vuông góc khi quét. Và một phần do giả thiết này nên phương pháp sẽ chỉ đạt độ chính xác cao nhất trong phạm vi góc lệch là dưới 10 độ. Thuật toán phát hiện góc nghiêng văn bản dựa vào hình chiếu có thể bao gồm các bước chính sau: Dùng hàm rút gọn F để chuyển ảnh đầu vào thành một tập các bộ ba (x,y,w) trong đó (x,y) là toạ độ của một điểm ảnh đại diện cho một đối tượng và w là trọng số của điểm đó. Ở đây, điểm đại diện được hiểu theo nghĩa là điểm biểu diễn các ký tự trong 39 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  40. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản các đối tượng của ảnh. Trọng số w sẽ được đề cập sau và thường phụ thuộc vào từng thuật toán. Một hàm P dùng để chiếu các điểm tìm được ở trên vào một mảng điểm A theo các góc chiếu khác nhau. Ứng với mỗi góc có một mảng A dùng lưu số điểm đại diện. Mảng A là mảng một chiều, phần tử A [r] sẽ cho biết số điểm đại diện nằm trên đường thẳng đó là r. Sau khi tính được mảng A [r], áp dụng một hàm tối ưu hóa cho các giá trị mảng này theo một tiêu chuẩn nào đó. Cuối cùng góc lệch của văn bản là góc tương ứng có giá trị hàm tối ưu hóa cực đại. 2.4 Ứng dụng phép biến đổi Hough để xác định độ nghiêng văn bản Thuật toán dùng biến đổi Hough thường xác định một số điểm đen và dùng biến đổi Hough tác động lên các điểm đó. Biến đổi Hough ánh xạ một đường thẳng trong mặt phẳng thành các cặp (r, ) trong không gian Hough với r là khoảng cách từ gốc tọa độ tới đường thẳng đó và là góc nghiêng của đường thẳng đó so với trục hoành. Góc nghiêng văn bản tương ứng là góc có tổng số điểm nằm trên những đường thẳng cùng lệch góc lớn nhất. Thông thường để đếm số các điểm đen này các thuật toán dùng một mảng tích lũy Histogram. Số các điểm đen được áp dụng biến đổi Hough tùy thuộc vào từng thuật toán, có thể là tất cả các điểm đen hoặc có thể chỉ là những điểm thỏa mãn một số ràng buộc nào đó hoặc chỉ là đáy của các đối tượng ảnh. Phương pháp của Srihari và Govidaraju là áp dụng biến đổi Hough cho tất cả các điểm đen của ảnh. Tất nhiên, việc áp dụng không có loại trừ một điểm nào dẫn đến chi phí tính toán rất lớn và ảnh hưởng tới độ chính 40 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  41. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản xác của thuật toán. Để giảm thời gian chạy và tăng một phần độ chính xác của thuật toán, Hinds chỉ áp dụng biến đổi Hough cho một số ít điểm hơn bằng phân tích chạy dài theo chiều dọc. Mục đích của nén chạy dài theo chiều dọc trong thuật toán này là lấy ra các điểm đáy của các dòng văn bản, loại bỏ đi những điểm đen khác kể cả chúng thuộc vào một ký tự dùng biến đổi Hough lên các điểm đen đó. Tuy nhiên, chi phí tính toán của thuật toán này vẫn còn lớn và việc áp dụng biến đổi Hough cho tất cả các điểm đen ở đáy có thể dẫn đến những kết quả sai trong trường hợp ảnh đầu vào còn nhiều đối tượng phi ký tự: nhiễu, bảng biểu hay ảnh. 2.4.1 Phép biến đổi Hough cho đường thẳng: Phép biến đổi Hough là một phương pháp tách các đường thẳng trong một ảnh. Bất kỳ điểm ảnh đen nào trong một ảnh cũng có thể có rất nhiều đường thẳng qua nó, mỗi đường thẳng với mọi góc nghiêng có thể. Mỗi đường thẳng này có thể được mô tả bằng dạng chắn nghiêng (slope- intercept) hoặc phương trình đường thẳng: Y= mX + b (1) với (X,Y) là toạ độ của điểm ảnh liên quan. Hệ số góc của đường thẳng là m, giao của đường thẳng với trục Y là tại điểm Y=b. Bây giờ, nếu phương trình (1) được hiểu theo cách khác, với X, Y là các hằng số và m, b là các toạ độ, phương trình có thể được viết lại: b = -Xm + Y (2) Là phương trình đường thẳng trong không gian (m,b). Khi đó, một điểm đơn trong không gian ảnh hai chiều (X,Y) tương ứng với một đường thẳng trong hệ toạ độ (m,b). Mỗi pixel trong một ảnh tương ứng một họ các đường thẳng, được biểu diễn trong không gian (m,b) như là một đường thẳng. Hơn nữa, những 41 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  42. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản vị trí trong không gian (m,b), bây giờ gọi là không gian Hough, nơi hai đường thẳng giao nhau tương ứng với những điểm đồng tuyến trong không gian ảnh. Từ đó dẫn đến nhận xét sau: “Nếu đường thẳng trong không gian Hough- tương ứng với N điểm ảnh đã cho trong không gian ảnh- giao nhau tại một điểm, thì N điểm ảnh đó nằm trên một đường thẳng trong hệ toạ độ ảnh. Các tham số của đường thẳng đó tương ứng với toạ độ Hough(m,b) của giao điểm”. Đây là cơ sở của phép biến đổi Hough, mọi pixel được đổi thành các đường thẳng trong không gian (m,b) và các giao điểm của nhiều đường thẳng được ghi nhận và được tập hợp vào các đoạn thẳng. Vì thật ra có rất nhiều đường thẳng, và rất nhiều điểm trên mỗi đường, sự bổ sung thực sự rất giống một histogram. Một mật độ lượng tử hoá trong toạ độ (m,b) được chọn ra từ trước và một ảnh Hough được tạo nên.Với mỗi pixel trong ảnh ban đầu, một đường trong không gian Hough được xác định, biểu đồ tần xuất (histogram) của mỗi pixel trên đường đó ở ảnh Hough được tăng lên một đơn vị. Sau khi mọi pixel đã được xử lý, các pixel trong ảnh Hough có giá trị lớn nhất tương ứng với số pixel lớn nhất đồng tuyến trong ảnh ban đầu. Phương trình đường thẳng (slope-intercept) có một tính chất không hay là nó không thể giải quyết những đường thẳng đứng: độ dốc (hệ số góc) là vô cùng. Có những dạng khác của phương trình đường thẳng mà không có nhược điểm này, trong đó có dạng: r = xcos(w) + ysin(w) Với r là khoảng vuông góc từ tâm tới đường thẳng, w là góc đo đường vuông đó hợp với trục x. Sử dụng phương trình này, hệ toạ độ trong không gian Hough là (r, w). 42 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  43. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Sự liên hệ giữa phép biến đổi Hough và việc xác định góc nghiêng đã rõ ràng. Những bước đầu của thuật toán xác định góc nghiêng Baird cho một ảnh với sự tập hợp các pixel đồng tuyến. Ảnh Hough của nó sẽ có đỉnh chính tại một góc tương ứng với góc nghiêng. Hình 2.13 Phép biến đổi Hough (a) họ đường thẳng qua một pixel (b) dạng đoạn chắn của một đường thẳng (c) dạng đoạn chắn thông thường của đường thẳng có thể biễu diễn qua ( ,r) ,(d) biễu diễn 3 điểm đồng tuyến trong không gian Hough. Dưới đây là thủ tục xấp xỉ tập các điểm bằng đường thẳng sử dụng phép biến đổi Hough cho đường thẳng: Thuộc tính (Attributes): Ảnh (Image): Các ảnh bilevel với các điểm ảnh cô lập hoặc các ảnh đa cấp xám với điểm ảnh được gán nhãn (ví dụ điểm cạnh, điểm xương). Đầu vào (Inputs): Tập tất cả các điểm ảnh cần được xấp xỉ bằng các đoạn thẳng có cấu trúc thích hợp. 43 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  44. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Các phần tử hình học đơn giản (ví dụ đường thẳng, đường tròn, đa giác) có thể được mô tả trong “miền không gian” (spatial domain) bằng các bộ tham số. Tuy nhiên, một bộ tham số có thể xem như một điểm trong không gian nhiều chiều, xác định bởi một bộ tham số được coi là toạ độ trong không gian này, và một “miền tham số” (prameter domain) như vậy được gọi là không gian Hough của các đơn vị hình học. Một điểm trong miền không gian có thể thuộc về nhiều hình khác nhau, ví dụ thuộc về mọi đường thẳng qua nó. Do đó một điểm trong miền không gian định ra nhiều bộ tham số trong không gian Hough, ví dụ các tham số của mọi đường thẳng qua điểm đó. Giả sử hai điểm trong miền không gian cùng có một đơn vị hình học. Đơn vị này có các tham số trong phần giao của các bộ tham số của hai điểm đã cho. Nói chung công việc có thể mô tả như sau: Cho một tập điểm (trong một ảnh), những điểm này cần được gộp lại trong không gian tham số để mỗi cụm “tương ứng” một đơn vị thuộc một lớp các đơn vị hình học cụ thể. Các giải pháp này cần một số bước: 1) Tìm các tập hợp bộ tham số cho mọi điểm ảnh đã cho trong một ảnh. Tách rời các tham số. 2) Xét phần giao của các tập hợp bộ tham số. Mỗi vị trí rời rạc trong không gian Hough được gán một giá trị đếm số bộ các đơn vị hình học khác chứa điểm này. 3) Gắn tất cả các điểm trong không gian Hough có giá trị được gán vượt quá một ngưỡng nào đó với một đơn vị nhận biết được trong miền không gian. 44 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  45. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Phần này xử lý những công việc cụ thể để nhận dạng đường thẳng. Ví dụ, giả sử các điểm biên cô lập cần được xấp xỉ nhờ một đoạn thẳng. Lớp các đơn vị hình học là các chương trình sử dụng không gian tham số (d, ) của Hessian norman form: d= x.cos + y.sin Để nhận dạng các điểm “đồng tuyến” (colinear) nhờ không gian (d, ), thuật toán thực hiện các bước sau: 1) Làm rời rạc các miền giá trị của d và , ví dụ từ 0 đến 180 với các bước 5 . Ước lượng giá trị cực đại dmax của d, đường chéo của ảnh sẽ xác định giá trị này, ví dụ dmax=724.08 với ảnh 512 x 512. Làm rời rạc d từ 0 đến dmax, ví dụ từ 0 đến 723 với bước bằng 3. Sau bước rời rạc hoá này, không gian tuyến tính có các hướng Hx=1, , Hx_max cho d và Hy=1, , Hy_max cho . Chương trình chiếu các “tập hợp điểm đầu vào” (input point set) lên không gian Hough này, với mức xám tại điểm (d, ) biểu diễn “trọng số” (score) của các điểm đã cho trong miền không gian, nằm trên đường thẳng: d= x.cos + y.sin 2) Chọn các điểm thích hợp trong ảnh vào f, ví dụ như kết quả của một phép tách cạnh hay tách xương. 3) Tuỳ chọn (Optional): Chọn một vùng quan tâm trong f (ảnh cần xử lý), ví dụ như một cửa sổ m x n, việc nhận dạng các điểm đồng tuyến trong vùng giao này. 4) Tăng giá trị đếm của mọi điểm của không gian Hough trên (hoặc gần) đường thẳng: d= p1.cos + p2.sin 45 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  46. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản cho mọi điểm vào (p1, p2). 5) Phân tích không gian Hough, tìm các điểm có giá trị đếm cao (mức xám cao) hoặc tìm các cụm có giá trị đếm cao. Tìm điểm trung tâm cho các cụm đó. Để cải tiến cách phân tích này, các đường thẳng tính được có thể được xét trong miền không gian, và bước (5) - chính bước này- có thể được lặp lại thường xuyên với các bộ tham số có thay đổi chút ít, ví dụ để tránh đạt được các dòng gần song song nếu nó là bắt buộc trong ứng dụng cụ thể. 6) Dừng hoặc quay lại bước (3). Cấu trúc điều khiển: Mảng dữ liệu đòi hỏi: Hough(1 Hx_max,1 Hy_max) với các trị nguyên. Nhập và khởi tạo không gian Hough: Nhập các tham số MAX_NUM và S_inkr (cp.below); _step := 5; d_step :=3; Hx_max:=dmax/d_step; Hy_max:=180/ _step; {Trong một số trường hợp phải thay 180 bằng 360, chẳng hạn như khi cần phân biệt phần trên với phần dưới của đường thẳng} array Hough(1 Hx_max, 1 Hy_max):integer; for Hx:=1 to Hx_max do for Hy:=1 to Hy_max do Hough(Hx, Hy):=0; Xếp tất cả các điểm ảnh (x,y) phù hợp vào không gian Hough: MAX:=0; {Đếm giá trị lớn nhất hiện thời trong không gian Hough} for (tất cả các điểm (x,y) phù hợp trong ảnh) do 46 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  47. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản for Hy:=1 to Hy_max do begin {Lần lượt với tất cả các giá trị của , d được tính theo } :=(Hy-1). _step;{ tính theo độ} d:=x.cos + y.sin ; {Nếu cần có thể đổi sang radian} Hx:=integer(d/d_step + 1.5); {d bắt đầu từ 0, Hx bắt đầu từ 1} if ((Hx >= 1) and (Hx <= Hx_max)) then begin Hough(Hx,Hy):=Hough(Hx,Hy) + 1; if MAX < Hough(Hx,Hy) then MAX:=Hough(Hx,Hy); end {then} else Tham số không nằm trong dãy khởi tạo của giá trị d (tăng dmax?) End; {for} Xác định các đường thẳng trong không gian Hough: Tiền xử lý của không gian Hough nhằm làm tăng cực đại địa phương nếu cần S:=MAX/2; {ví dụ về ngưỡng ban đầu trong không gian Hough} repeat NUM:=0; {số đường thẳng được xác định} S:=S+S_inkr; {S_inkr dùng để tăng ngưỡng lên trong từng bước} 47 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  48. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản for Hx:=1 to Hx_max do for Hy:=1 to Hy_max do if Hough(Hx,Hy) >= S then begin := (Hy-1). _step; d := (Hx-1).d _step; đường thẳng d:=x.cos + y.sin được xác định trong không gian x,y ( và d đã xác định) NUM:=NUM+1; End; {then} Until NUM <= MAX_NUM Một phương pháp xác định góc nghiêng khác, nó đòi hỏi các vùng liên thông được xác định trước, dựa trên sự quan sát thấy các ký tự trên một dòng nhỏ hơn khoảng cách giữa các đường (Hashizume). Như vậy, một đường được kẻ giữa các (centroids) của các cặp lân cận gần nhất sẽ nối các ký tự kề nhau, góc và đường thẳng sẽ gần góc nghiêng. Biểu đồ của các góc sẽ có đỉnh tại góc nghiêng xấp xỉ tốt nhất. 2.4.2 Thủ tục xác định độ nghiêng cho trang văn bản sử dụng phép biến đổi Hough: Bài toán “phát hiện độ nghiêng” có thể được thực hiện theo nhiều cách, và phương pháp mô tả ở đây chỉ tổng kết các khả năng. Trong trường hợp góc nghiêng xấp xỉ đã biết, phép tách ngang có thể được dùng. Nếu góc nghiêng lớn, sẽ không có các phần được tách ra tương ứng với các giải trắng hoàn toàn giữa các dòng. Tuy nhiên khi đã biết góc xấp xỉ, hình ảnh có thể được xoay theo góc đó, và các phép tính được theo các góc nhỏ cho đến khi 48 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  49. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản tìm thấy chiều cao dòng và vùng trắng lớn nhất giữa các dòng. Góc kết quả là góc nghiêng, mức nhiễu hợp lý. Với bất kỳ ký tự không có phần dưới (các ký tự khác g,j,p,q,y) chân các ký tự trên mỗi dòng là đồng tuyến (colinear). Do vậy nếu biết hợp biên (bounding box) của mỗi glyph, điểm giữa cạnh dưới của các hộp sẽ là colinear với mỗi dòng văn bản. Điều này gợi ý cho các thuật toán sau : (Baird) 1) Nhận dạng tất cả các vùng liên thông, coi như mỗi vùng miêu tả một ký tự, trừ khi nó vượt quá một vài ngưỡng kích thước. 2) Tìm hợp biên cho mỗi vùng, định vị tâm cạnh dưới của hợp biên. 3) Với góc cho trước, tính toán hình chiếu thu được của các điểm từ bước 2, tạo nên một mảng hình chiếu một chiều Baird sử dụng kích thước hộp (bin size) tương ứng với 1/3 kích thước một ký tự 6 điểm ở độ phân giải tiêu biểu, Pi(q) là giá trị của (bin) thứ i tìm được với góc . 4) Cực đại hoá hàm: n 2 A( ) Pi ( ) i 1 Với n là số hộp (bin) góc cho giá trị cực đại là góc nghiêng đúng. Một lần nữa sự ước lượng góc nghiêng là có ích, do nó giảm số phép tìm kiếm cần thiết để tìm giá trị cực đại. Nếu không có sẵn sự ước lượng, một sự tìm kiếm có thể được sử dụng, nhưng nó rất tốn thời gian. Tuy nhiên, mỗi khi ở một lân cận đúng, có thể dùng phép tìm kiếm thô đến mịn (coarse to fine). Phương pháp bình phương tối thiểu phi tuyến cũng được đề xuất. 49 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  50. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Sự chính xác thu được từ thuật toán này có thể đạt tới 1/30 độ, với 1/2 độ là điển hình. Sơ đồ 2.13 cung cấp một ví dụ của phương pháp này ứng dụng để quay ảnh- nó được thực hiện để nhận biết được góc nghiêng, và có thể so sánh với giá trị tìm được bởi thuật toán. Sơ đồ 2.13a là một phần của văn bản đã được quay 10 , sơ đồ 2.13b cho thấy phép quay 15 . Sau khi phân ngưỡng (sơ đồ 2.13c-d), hai bước đầu của thuật toán Baird được áp dụng, và các điểm tâm của các hợp biên được vẽ như những điểm ảnh đen (sơ đồ 2.13e-f) những đường thẳng khớp nhất (best-fit) qua các pixel đen sẽ nằm trong góc nghiêng của văn bản. Hình 2.14 Thuật toán Hough cho xác định độ nghiêng Tuy vậy, thay vì thực hiện hết thuật toán và xác định góc tốt nhất nhờ sử dụng phép chiếu, histogram và tính toán bình phương tối thiểu, người ta 50 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  51. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản đã thử một phương pháp khác để ước lượng góc. Sau cùng, tiêu chuẩn bình phương tối thiểu đã được dùng nhiều lần. Thuật toán Baird trình bày ở trên sử dụng phép biến đổi Hough cho đường thẳng để xác định góc nghiêng của trang ảnh tài liệu. Để cài đặt thuật toán cần phải thực hiện thêm thủ tục xác định tâm cạnh dưới của hình hộp bao quanh một ký tự. 2.4.3 Thủ tục xác định tâm cạnh dưới: Thủ tục này nhằm xác định một điểm đại diện cho một ký tự khi dùng thuật toán Baird sử dụng phép biến đổi Hough cho đường thẳng xác định góc nghiêng của ảnh văn bản. Thuộc tính: ảnh (Image): ảnh bilevel hoặc các ảnh đa cấp xám với các điểm ảnh được gán nhãn ( BACK-nền, OBJECT-thuộc ký tự). Đầu vào: File ảnh có các thuộc tính phù hợp. Thủ tục này nhằm xác định một điểm đại diện cho một ký tự khi dùng thuật toán Baird sử dụng phép biến đổi Hough cho đường thẳng xác định góc nghiêng của ảnh văn bản. Để xác định tâm cạnh dưới thủ tục thực hiện các bước sau: (a) Dò từ trên xuống từ trái qua phải để tìm điểm thuộc ký tự. (b) Đánh dấu các “điểm ký tự” liên thông với điểm tìm được trong (a). (c) Xác định hộp biên quanh vùng liên thông trong (b) (d) Xác định và đánh dấu tâm cạnh đáy của hộp biên trong (c). (e) Xoá thành nền vùng liên thông tìm được trong (b). (f)Thoát hoặc quay lại (a). 51 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  52. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản 2.4.4 Thủ tục quay: Trong luận văn này tôi có đưa ra một số thủ tục quay cho ảnh đen trắng, ảnh đa cấp xám. Nói chung các thủ tục quay dừng lại ở mức tham khảo, chủ yếu các thủ tục quay này dùng để quay lại ảnh văn bản đã được xác định góc nghiêng qua thủ tục trong phần 2.4.3. Đối với thủ tục quay các góc đặc biệt ( 90 , 180 ), tôi dùng các đặc điểm về quan hệ của ảnh trước và sau khi quay: - Quay 90 : I(x, y) I(y, width –x) - Quay -90 : I(x, y) I(height –y, x) - Quay 180 : I(x, y) I(height- x, width- y) Trong đó (height, width) là kích thước của ảnh sau khi quay. Do dùng các đặc điểm trên nên thủ tục có tốc độ tương đối nhanh, đồng thời phép quay cho ánh xạ một một nên độ mịn của ảnh quay là tuyệt đối. 52 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  53. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Chương III : Cài đặt chương trình 3.1 Sơ lược về chương trình cài đặt Ảnh đầu vào sau khi được đọc sẽ được xử lý qua giai đoạn tìm tâm cạnh đáy phục vụ cho giai đoạn xử lý góc nghiêng sau đó. Tạo buffer pbuff1[1 h_max][1 w_max] để lưu thông tin về một phần ảnh, các thao tác trên ảnh chuyển về buffer này. Tạo buffer pbuff2[1 h_max][1 w_max] lưu các tâm cạnh dưới đã được đánh dấu. Thủ tục Markcc đánh dấu tâm cạnh dưới của các hộp biên: int ulr, ulc, lrr, lrc; for i:=1 to h_max do for j=0 to w_max do {Dò từ trên xuống, từ trái qua phải các điểm ảnh thuộc ký tự} if (pBuff1[i][j] == OBJECT) { Mark(pBuff1, i, j, 2); {Đánh dấu các “điểm ký tự” liên thông với điểm (i,j)} bBox(pBuff1, i, j, 2, &ulr, &ulc, &lrr, &lrc); {Xác định hộp biên quanh một ký tự} pBuff2[lrr][(lrc + ulc)/2] = BACK; {Đánh dấu tâm cạnh đáy của hộp biên} UnMark(pBuff1, ulr, ulc, lrr, lrc, 2); {Xoá thành nền các “điểm ký tự” đẫ được đánh dấu} } return(pBuff2); /* */ 53 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  54. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Thủ tục Mark: Thủ tục đệ quy đánh dấu các “điểm ký tự” liên thông với điểm (i,j): pBuff1[row][col] = (BYTE)MARK ; {MARK: mầu đánh dấu} if (row-1>=1 and col-1>=1 and pBuff1[row-1][col-1]== OBJECT) Mark(pBuff1, row-1, col-1, MARK); if (row-1>=1 and pBuff1[row-1][col]==OBJECT) Mark(pBuff1, row-1, col, MARK); if (row-1>=1 and col+1 =1 and pBuff1[row][col-1]==OBJECT) Mark(pBuff1, row, col-1, MARK); if (col+1 =1 and pBuff1[row+1][col-1]== OBJECT) Mark(pBuff1, row+1, col-1, MARK); if (row+1 < h_max and pBuff1[row+1][col] == OBJECT) Mark(pBuff1, row+1, col, MARK); if (row+1<=h_max and col+1<w_max and pBuff1[row+1][col+1] == OBJECT) Mark(pBuff1, row+1, col+1, MARK) /* */ Thủ tục bBox: Thủ tục xác định hộp biên quanh một tập các “điểm ký tự” liên thông. int ip1 = 10000; int jp1 = 10000; int ip2 = -1; int jp2 = -1; int is, ie, js, je; 54 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  55. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản {Xác dịnh một cửa sổ tối đa cho hộp biên} if (I-SIZE h_max) ie = h_max; else ie = I+SIZE; if (J-SIZE w_max) je = w_max; else je = J+SIZE; {Tìm các toạ lớn nhất , nhỏ nhất theo cả hàng và cột} for i := is to ie do for j := js to je do if (pBuff1[i][j] == MARK) { if (i ip2) ip2=i; if (j jp2) jp2=j; } *ulr = ip1; {i min} *ulc = jp1; {j min} *lrr = ip2; {i max} *lrc = jp2; {j max} /* */ Thủ tục UnMark: Xoá vùng liên thông đã được xác định tâm cạnh đáy for i := is to ie do for j := js to je do {is, ie, js, je: cửa sổ được xác định trong bBox} 55 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  56. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản if (pBuff1[i][j] == MARK) pBuff1[i][j] = BACK; Thủ tục Hough: Xác định góc nghiêng dựa trên buffer pbuff2 lưu các tâm cạnh dưới. for (int omega=0; omega tmval) tmval = z[i][j] ; 56 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  57. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản tmax = i; double theta = 90-tmax ; return theta; 3.2 Chương trình thực nghiệm Ảnh văn bản bị nghiêng với góc 15o. 57 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  58. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Kết quả sau khi thực hiện hiệu chỉnh góc nghiêng Ảnh văn bản sẽ bị xê dịch so với văn bản ban đầu. Kết quả sau khi thực hiện hiệu chỉnh vị trí của ảnh văn bản đã được hiệu chỉnh nghiêng với ảnh văn bản gốc. 58 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  59. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Kết Luận Xử lý ảnh là một lĩnh vực rất rộng lớn gồm nhiều giai đoạn xử lý, trong mỗi giai đoạn có rất nhiều vấn đề để nghiên cứu. Với đề tài “ Tìm hiểu phương pháp phát hiện và hiệu chỉnh góc nghiêng trong văn bản” mới chỉ dừng lại ở việc nghiên cứu các phương pháp phát hiện và hiệu chỉnh góc nghiêng. Đề tài cũng áp dụng phương pháp đường thẳng Hough để hiệu chỉnh góc nghiêng. Chương trình được phát triển trên hệ điều hành Windows, lập trình bằng Visual C++ sử dụng MFC. Chương trình thực hiện được những chức năng sau: + Đọc và hiển thị ảnh. + Xoay ảnh văn bản một góc bất kỳ. + Phát hiện và hiệu chỉnh góc nghiêng văn bản. + Hiệu chỉnh lại vị trí văn bản so với bản gốc. + Ghi lại kết quả sau khi thực hiện. Tuy nhiên việc thực hiện đề tài vẫn còn nhiều hạn chế: + Chỉ dừng lại ở việc thực hiện trên ảnh văn bản nhị phân 1 bit. + Chỉ phát hiện được ảnh văn bản với góc [-15o,15o]. Hướng phát triển tiếp theo của đề tài: + Thực hiện phát hiện góc nghiêng trên mọi loại ảnh văn bản. + Áp dụng các phương pháp phát hiện góc nghiêng khác: Láng giềng gần nhất, Morphology, hình chiếu nghiêng. + Nghiên cứu thực hiện với ảnh văn bản có góc -15o và 15o. Em xin chân thành cảm thầy giáo PGS.TS Ngô Quốc Tạo đã tận tình hướng dẫn giúp đỡ em hoàn thành đề tài. Em cũng cám ơn sự giúp đỡ của các thầy cô giáo khoa Công Nghệ Thông Tin Trường Đại Học Dân Lập Hải Phòng đã tạo điều kiện tốt cho em trong thời gian làm khóa luận tốt nghiệp. 59 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin
  60. Phát hiện và hiệu chỉnh góc nghiêng trong văn bản Tài liệu tham khảo 1) Lương Mạnh Bá, Nguyễn Thanh Thủy, Nhập môn xử lý ảnh số, Nhà xuất bản Khoa Học và Kỹ Thuật. 2) Đỗ Năng Toàn, Phạm Việt Bình, Giáo trình môn học xử lý ảnh, Đại Học Thái Nguyên. 3) Yang Cao, Heng Li, Skew detection and correction in document images based on straight-line fitting, Building & Real Estate Department, the Hong Kong Polytechnic University, Hong Kong. 4) Yue Lu, Chew Lim Tan, Improved Nearest Neighbor Based Approach to Accurate Document Skew Estimation, Department of Computer Science, School of Computing National University of Singapore, Kent Ridge, Singapore 117543 {fluy,tanclg}@comp.nus.edu.sg. 5) L.Najman, Using Mathematical Morphology for Document Skew Estimation, Laboratoire A2SI, Groupe ESIEE Cité Descartes, BP99 93162 Noisy-le-Grand Cedex France l.najman@esiee.fr. 6) Kanai, J., Bagdanov, A.D, Projection Profile Based Skew Estimation Algorithm for JBIG Compressed Images, Int. J. Document Analysis and Recognition. 7) 60 Sinh viên thực hiện: Lê Thành Long Ngành Công Nghệ Thông Tin