BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC LẠC HỒNG
***
NGUYỄN MINH AN
NGHIÊN CỨU MỘT SỐ KỸ THUẬT
HIỆU CHỈNH FORM TÀI LIỆU
Luận văn Thạc sỹ Công nghệ Thông tin
ĐỒNG NAI, 2013
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC LẠC HỒNG
***
NGUYỄN MINH AN
NGHIÊN CỨU MỘT SỐ KỸ THUẬT
HIỆU CHỈNH FORM TÀI LIỆU
Chuyên ngành: Công nghệ Thông tin
Mã số: 60.48.02.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 ĐỖ NĂNG TOÀN
ĐỒNG NAI, 2013
LỜI CẢM ƠN
Trước hết tôi xin gởi lời cảm ơn chân thành tới thầy PGS.TS Đỗ Năng Toàn,
người thầy hướng dẫn khoa học, định hướng nghiên cứu và tận tình hướng dẫn cho tôi
trong suốt quá trình làm luận văn. Nếu không có thầy, tôi khó có thể hoàn thành luận
văn này.
Bên cạnh đó, tôi cũng muốn gửi lời cảm ơn đến các thầy cô đang làm việc tại
khoa Công nghệ Thông tin trường Đại học Lạc Hồng đã quan tâm chỉ bảo và trực
tiếp giảng dạy lớp cao học khóa 3.
Tôi xin chân thành cảm ơn Ban giám hiệu trường THCS Phú Mỹ Hưng đã tạo
điều kiện thuận lợi và hỗ trợ cho tôi trong việc thu thập số liệu của trường để phục vụ cho
nhu cầu luận văn.
Cuối cùng, tôi xin cảm ơn gia đình và bạn bè, đặc biệt là thành viên của lớp
CHK3 – Đại học Lạc Hồng - những người đã luôn ủng hộ và động viên để tôi yên tâm
nghiên cứu và hoàn thành luận văn.
Nguyễn Minh An
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn: “Nghiên cứu một số kỹ thuật hiệu chỉnh form tài
liệu” là kết quả quá trình học tập, nghiên cứu khoa học độc lập, nghiêm túc.
Các số liệu trong luận văn là trung thực, có nguồn gốc rõ ràng, được trích dẫn
và có tính kế thừa, phát triển từ các tài liệu, tạp chí, các công trình nghiên cứu đã được
công bố, các website, …
Các phương pháp nêu trong luận văn được rút ra từ những cơ sở lý luận và quá
trình nghiên cứu tìm hiểu của tác giả.
Đồng Nai, tháng 06 năm 2013
Tác giả
Nguyễn Minh An
TÓM TẮT LUẬN VĂN
Một tệp tin ảnh sau khi scan để nhận dạng thành văn bản số thì giai đoạn tiền
xử lí như lọc nhiễu, hiệu chỉnh độ nghiêng, hiệu chỉnh độ lệch là nhu cầu cần thiết.
Về kỹ thuật lọc nhiễu, luận văn giời thiệu các kỹ thuật lọc tuyến tính và phi tuyến
tính. Hiệu chỉnh độ dịch chuyển giới thiệu kỹ thuật so sánh histogram. Về phương
pháp khử nghiêng, luận văn tìm hiểu các phương pháp phân tích hình chiếu, biến
đổi Hough, phân tích láng giềng và phép toán hình thái. Các thuật toán nghiên cứu
trong luận văn được áp dụng vào hiệu chỉnh form điểm tại trường THCS Phú Mỹ
Hưng và bước đầu thu được những kết quả nhất định.
MỤC LỤC
LỜI CẢM ƠN
LỜI CAM ĐOAN
TÓM TẮT LUẬN VĂN
MỤC LỤC
PHẦN MỞ ĐẦU ............................................................................................................. - 1 Chƣơng 1: KHÁI QUÁT FORM TÀI LIỆU VÀ BÀI TOÁN HIỆU CHỈNH FORM
TÀI LIỆU ........................................................................................................................ - 4 1.1. Khái quát về Form tài liệu ............................................................................. - 4 1.1.1. Form tài liệu là gì? ................................................................................. - 4 1.1.2. Phân loại form tài liệu ............................................................................ - 4 1.1.2.1. Ảnh trắng, đen ............................................................................ - 4 1.1.2.2. Ảnh màu ..................................................................................... - 4 1.2. Thu nhận và biểu diễn form tài liệu .............................................................. - 5 1.2.1. Thu nhận form tài liệu ............................................................................ - 5 1.2.2. Cấu trúc Form tài liệu ............................................................................ - 5 1.2.2.1. Mào đầu tệp(Header) .................................................................. - 5 1.2.2.2. Dữ liệu nén (Data Compression) ................................................ - 5 1.2.2.3. Bảng màu (Palette color) ............................................................ - 5 1.2.3. Một số phương pháp biểu diễn Form tài liệu ......................................... - 5 1.2.3.1. Mã loạt dài (Run – Length code)................................................ - 5 1.2.3.2. Mã xích (Chain Code) ................................................................ - 6 1.2.3.3. Mã tứ phân (Quad Tree Code) ................................................... - 7 1.3. Bài toán hiệu chỉnh Form tài liệu .................................................................. - 7 1.3.1. Một số vấn đề trong hiệu chỉnh form tài liệu ......................................... - 7 1.3.2. Một số cách tiếp cận trong hiệu chỉnh form tài liệu ............................... - 7 1.3.2.1. Nhiễu form tài liệu ..................................................................... - 7 1.3.2.2. Khử nhiễu ................................................................................... - 8 -
Chƣơng 2: HIỆU CHỈNH FORM TÀI LIỆU ............................................................ - 15 2.1 Độ dịch chuyển của form tài liệu ................................................................. - 15 2.1.1 Giới thiệu.............................................................................................. - 15 2.1.2 Phát hiện độ dịch chuyển của form tài liệu .......................................... - 16 2.1.3 Hiệu chỉnh độ dịch chuyển form tài liệu .............................................. - 17 2.1.3.1 Phương pháp thứ nhất ............................................................... - 19 2.1.3.2 Phương pháp thứ hai ................................................................. - 20 2.2 Độ nghiêng của form tài liệu ........................................................................ - 22 2.2.1 Giới thiệu.............................................................................................. - 22 2.2.2 Một số thuật toán và phát hiện góc nghiêng văn bản ........................... - 23 2.2.2.1 Thuật toán dựa vào phân tích hình chiếu (Projection Profile) . - 23 2.2.2.2 Các thuật toán dựa vào biến đổi Hough (Hought Transform) .. - 28 2.2.2.3 Các thuật toán phân tích láng giềng (nearest Neighbour Clustering)
................................................................................................. - 35 2.2.2.4 Phương pháp dùng phép toán hình thái ..................................... - 41 Chƣơng 3: CHƢƠNG TRÌNH THỬ NGHIỆM ........................................................ - 48 3.1. Bài toán .......................................................................................................... - 48 3.2. Phân tích bài toán ......................................................................................... - 48 3.2.1. Module File .......................................................................................... - 49 3.2.2. Module Basic ....................................................................................... - 50 3.2.3. Module Filter ........................................................................................ - 51 3.2.4. Module Skew Detection ....................................................................... - 51 3.3. Một số kết quả hiệu chỉnh form tài liệu ...................................................... - 52 PHẦN KẾT LUẬN ....................................................................................................... - 60 TÀI LIỆU THAM KHẢO
PHỤ LỤC (Một số định dạng form tài liệu)
P.1. Định dạng ảnh IMG
P.2. Định dạng ảnh PCX
P.3. Định dạng ảnh TIFF
P.4. Định dạng ảnh GIF
P.5. Định dạng ảnh Bitmap
DANH MỤC HÌNH, BẢNG
Hình 1.1. Ảnh nhị phân và các biểu diễn mã loạt dài tương ứng. .................................. -6Hình 1.2: Minh hoạ mã xích ........................................................................................... -7Hình 1.3. Các toán tử gờ sai phân. ............................................................................... -12Hình 1.4. Sơ đồ bộ lọc thông cao. ................................................................................ -13Hình 1.5. Một số nhân chập trong lọc thông cao. ........................................................ -13Hình 1.6. Bảng điểm qua lọc thông cao ....................................................................... -14Hình 2.1. Bảng điểm bị dịch chuyển sau khi scan. ...................................................... -15Hình 2.2. Mô hình histogram dọc của bảng điểm mẫu. ................................................ -16Hình 2.3. Mô hình histogram dọc của bảng điểm cần nhận dạng. ................................ -16Hình 2.4. Mô hình histogram của bảng điểm mẫu và bảng điểm cần nhận dạng được xếp
trên cùng một trục tọa độ............................................................................. -17Hình 2.5. Ảnh mẫu và ảnh cần nhận dạng. ................................................................... -19Hình 2.6. Mô hình histogram dọc của bảng điểm mẫu. ................................................ -20Hình 2.7. Mô hình histogram ngang của bảng điểm cần nhận dạng. ............................ -20Hình 2.8. Mô hình histogram của bảng điểm mẫu và bảng bảng điểm cần nhận dạng được
xếp trên cùng một trục tọa độ. ..................................................................... -21Hình 2.9. Ảnh sau khi scan bị nghiêng......................................................................... -22Hình 2.10. Cấu trúc của dòng văn bản. ........................................................................ -23Hình 2.11. Phép chiếu ngang và chiếu dọc của trang tài liệu. ..................................... -24Hình 2.12. Phép chiếu dọc của dòng văn bản. ............................................................. -24Hình 2.13. Phép chiếu dọc của dòng văn bản. ............................................................. -24Hình 2.14. Đường thẳng Hough trong toạ độ cực. ...................................................... -33Hình 2.15. Biến đổi Hough phát hiện góc nghiêng. ..................................................... -34Hình 2.16. Các đối tượng trên ảnh. .............................................................................. -36Hình 2.17. Phân cụm các đối tượng. ............................................................................ -36Hình 2.18. NNC của hình có K=2, (b)K=3, (c)K 4. .................................................. -39Hình 2.19. Ảnh (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. ......................................................................................................... -39-
Hình 2.20. Các điểm left most bottom và bottom most left của thành phần liên thông.-42Hình 2.21. 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. ..................................................... -44Hình 2.22. Một thành phần liên thông dài với hệ tọa độ ảnh ....................................... -45Hình 3.1 Sơ đồ khối ...................................................................................................... -48Hình 3.2. Giao diện chương trình thử nghiệm ............................................................. -49Hình 3.3. Giao diện Module file................................................................................... -50Hình 3.4. Giao diện Module Basic ............................................................................... -50Hình 3.5. Giao diện Module Filter ............................................................................... -51Hình 3.6 Giao diện Module Skew Detection ............................................................... -52Hình 3.7. Bảng điểm sau khi scan chưa được xử lí ..................................................... -53Hình 3.8. Bảng điểm sau khi chuyển sang ảnh xám ................................................... -53Hình 3.9. Bảng điểm sau khi chuyển nhị phân............................................................. -54Hình 3.10. Bảng điểm sau khi được lọc trung bình không gian................................... -54Hình 3.11. Bảng điểm sau khi được lọc thông thấp ..................................................... -55Hình 3.12. Bảng điểm sau khi được lọc đồng hình ...................................................... -55Hình 3.13. Phát hiện độ nghiêng bảng điểm bằng Hough.......................................... -56Hình 3.14. Phát hiện độ nghiêng bảng điểm bằng phân tích láng giềng .................... -56Hình 3.15. Phát hiện độ nghiêng bảng điểm bằng phân tích hình chiếu .................... -57Hình 3.16. Hình sau khi thực hiện phép quay ............................................................. -57Hình 3.17. File hình được lưu lại sau khi thực hiện phép quay .................................. -58Bảng 1.1. Bảng so sánh kết quả áp dụng các thuật toán vào hiệu chỉnh độ nghiêng bảng
điểm .............................................................................................................................. -59-
-1-
PHẦN MỞ ĐẦU
1. Lý do thực hiện đề tài
Với sự phát triển như vũ bão của ngành công nghệ thông tin, hiện nay, hầu hết các
lĩnh vực đều có sự hiện diện của máy tính điện tử: từ việc tự động hóa các công việc văn
phòng đến việc điều khiển robot, thám hiểm vũ trụ,...
Cùng theo sự phát triển đó, nhận dạng và xử lí ảnh là một lĩnh vực ngày càng nhiều
các nhà khoa học quan tâm. Các công việc được lưu trữ theo lối cổ truyền như giấy, gỗ,
vải,… chứa đựng một lượng lớn tri thức của nhân loại lại không có độ bền vĩnh cửu, khó
xử lí và lưu trữ. Song song đó, các tài liệu như: sách, báo, văn bản, biểu mẫu,… khi lưu
trữ phải tốn nhiều thời gian và tiền bạc cho việc nhập các tài liệu đó. Vậy, sao chúng ta
không nghĩ đến việc dùng máy scan để quét các tài liệu đó vào máy tính và dùng các kỹ
thuật xử lí ảnh để chúng thành các văn bản một cách tự động?
Một giải pháp đó là xây dựng một hệ thống nhận dạng chữ, trong các tấm ảnh chứa
chữ và các đối tượng đồ họa cần tách và chuyển thành dạng trang văn bản, mở và xử lí
được trên các trình soạn thảo văn bản. Để hoạt động tốt, nhận dạng các tài liệu với độ
chính xác cao, thì hệ thống cần phải tự động nâng cao chất lượng hình ảnh của form tài
liệu, hiệu chỉnh góc nghiêng, hiệu chỉnh độ dịch chuyển, … của form tài liệu.
Thực tế bản thân em là một giáo viên tin học, em nhận thấy nhu cầu tại đơn vị rất
cần việc chuyển từ dữ liệu giấy sang dữ liệu số để lưu trữ các hồ sơ văn phòng tại đơn vị
là cần thiết. Song song đó, xuất phát từ ý tưởng: các bài kiểm tra, bài thi của học sinh nếu
được dùng máy scan để quét vào máy tính và thông qua một hệ thống nhận dạng và xử lý
chuyển các bài kiểm tra từ văn bản giấy sang văn bản số. Đồng thời, ta xây dựng một hệ
thống nhằm so sánh nội dung bài kiểm tra, bài thi với đáp án có sẵn và hệ thống sẽ đưa ra
các phương án chấm bài cho học sinh thì việc tự động hóa công việc chấm bài cho học
sinh sẽ giúp đỡ giáo viên một phần rất đáng kể.
Nhưng để làm được việc trên, một ảnh tài liệu sau khi đưa vào máy tính từ các thiết
bị như: scanner, camera,…sẽ bị nhiễu, bị nghiêng hay bị lệch do nhiều cách, có thể là do
để giấy vào máy quét hay máy fax không chính xác hay ảnh tài liệu có phương ngang có
thể bị quét theo phương dọc do kích thước máy quét không đủ,…
-2-
Do đó một ảnh tài liệu cần phải dùng một số kỹ thuật hiệu chỉnh ảnh như hiệu chỉnh
độ lệch, hiệu chỉnh độ nghiêng,… trước khi tiến hành nhận dạng và xử lý các ảnh tài liệu
này. Xuất phát từ ý tưởng trên, luận văn sẽ nghiên cứu một số kỹ thuật hiệu chỉnh form
tài liệu nhằm giúp cho việc nhận dạng các tài liệu đạt chất lượng cao. Sau khi hoàn thành
luận văn, em sẽ tiếp tục học tập và nghiên cứu để phát triển lên hệ thống chấm điểm các
bài kiểm tra dạng tự luận một cách tự động.
Tình hình nghiên cứu trong nƣớc liên quan đến đề tài:
-
Đề tài “Thiết kế và cài đặt hệ thống nhập liệu tự động -MarkRead dựa trên các
kỹ thuật nhận dạng và xử lý ảnh”, PGS.TS Đỗ Năng Toàn, Viện Công Nghệ Thông Tin,
năm 1999-2000.
-
Luận văn Thạc sĩ “Nghiên cứu bài toán phân trang dựa vào ảnh quét tiếng việt”,
Phạm Tuyết Trinh, ĐH KHTN TP.HCM, 1999.
Tình hình nghiên cứu ngoài nƣớc liên quan đến đề tài:
- “Using White Space for Automated Document Structuring”, Daniela Rus and
Kristen Summers, Department of Computer Science Cornell University, 1994.
- “Document image analysis: A primer”, RANGACHAR KASTURI, LAWRENCE
O’GORMAN
and VENU GOVINDARAJU, Department of Computer Science &
Engineering, The Pennsylvania State University, University Park, PA 16802, USA, 2002.
- “Document Structure and Layout Analysis”, Anoop M. Namboodiri and Anil K.
Jain, International Institute of Information Technology, Hyderabad, 500 019, India.
- A Knowledge-Based Approach to the Layout Analysis, Floriana Esposito, Donato
Malerba and Giovanni Semeraro, Dipartimento di Informatica - Universitd degli Studi via Orabona, 4 - 70126 Bari, Italy.
Nhận xét:
Mặc dù trong và ngoài nước hiện đang nghiên cứu nhiều lĩnh vực form tài liệu,
nhưng chưa có một công trình nghiên cứu nào phát triển chuyên sâu và đầy đủ các kỹ
thuật hiệu chỉnh form tài liệu để từ đó có thể giúp em phục vụ việc xây dựng hệ thống
chấm điểm các bài kiểm tra tự luận một cách tự động.
2. Mục tiêu đề tài:
Nghiên cứu một số kỹ thuật hiệu chỉnh độ dịch chuyển và độ nghiêng của phiếu
điểm, phục vụ cho quá trình nhập điểm thi tự động nhờ máy quét.
-3-
3. Nội dung thực hiện (Những công việc cần thực hiện để đạt mục tiêu):
Tìm hiểu khái quát về nhu cầu chuyển từ phiếu điểm văn bản giấy sang phiếu
điểm số.
Tìm hiểu tổng quan về xử lí ảnh và form tài liệu.
Nghiên cứu một số kỹ thuật hiệu chỉnh form tài liệu như hiệu chỉnh độ dịch
chuyển, hiệu chỉnh độ nghiêng,…
Thiết kế, phát triển chương trình thử nghiệm hiệu chỉnh độ dịch chuyển và độ
nghiêng của phiếu điểm thi.
Xây dựng báo cáo sơ bộ và hoàn chỉnh báo cáo.
4. Phƣơng pháp thực hiện
Khảo sát thực tế về các nhu cầu chuyển các văn bản, biểu mẫu giấy sang văn
bản, biểu mẫu số.
Tìm hiểu nghiên cứu tài liệu, tìm hiểu các thông tin trên Internet về các kỹ thuật
xử lý ảnh và form tài liệu.
Nghiên cứu phương pháp Histogram chỉnh độ dịch chuyển của form tài liệu.
Nghiên cứu thuật toán Hough hiệu chỉnh góc nghiêng của form tài liệu.
Thực nghiệm: sử dụng các thuật toán hiệu chỉnh form tài liệu để xây dựng
chương trình hiệu chỉnh độ dịch chuyển và độ nghiêng của phiếu điểm thi.
Sử dụng ngôn ngữ C# để xây dựng sản phẩm.
Luận văn được chia làm 3 chương:
Chƣơng 1: Khái quát form tài liệu và bài toán hiệu chỉnh form tài liệu: chương
này đề cập đến các khái niệm cơ bản về form tài liệu, cách thu nhận, biểu diễn form tài
liệu và một số phương pháp hiệu chỉnh form tài liệu.
Chƣơng 2: Hiệu chỉnh form tài liệu: trong chương này đề cập đến phương pháp
phát hiện và hiệu chỉnh độ lệch form tài liệu bằng thuật toán Histogram. Đồng thời còn
nêu phương pháp phát hiện và hiệu chỉnh độ nghiêng form tài liệu bằng các phương pháp
phân tích hình chiếu, biến đổi Hough, phân tích láng giềng, phép toán hình thái.
Chƣơng 3: Chƣơng trình thử nghiệm: tiến hành xây dựng chương trình thừ
nghiệm hiệu chỉnh độ lệch và độ nghiêng form tài liệu.
-4-
Chƣơng 1: KHÁI QUÁT FORM TÀI LIỆU VÀ BÀI TOÁN
HIỆU CHỈNH FORM TÀI LIỆU
1.1. Khái quát về Form tài liệu
1.1.1. Form tài liệu là gì?
Form tài liệu là các ảnh thu được của các tài liệu bằng giấy thông qua các thiết bị
như: camera, scanner, máy fax, …
Ảnh tài liệu gồm có các loại: ảnh đen trắng, ảnh màu, ảnh xám đa cấp, … với phần
mở rộng là GIF, JPG, TIF,…
1.1.2. Phân loại form tài liệu
1.1.2.1. Ảnh trắng, đen
Ảnh đen trắng chỉ bao gồm 2 màu: màu đen và màu trắng. Mức đen trắng được xác
định là L, nếu sử dụng số bit B=8 bit để mã hóa thì mức đen trắng (hay mức xám) thì L
được xác định: L=2B
Nếu L = 2 thì B = 1, nghĩa là chỉ có 2 mức: 0 và 1, còn gọi là ảnh nhị phân. Mức 1
ứng với màu sáng, còn mức 0 ứng với màu tối. Nếu L>2 ta có ảnh đa xám. Như vậy, với
ảnh nhị phân mỗi điểm ảnh được mã hóa trên 1 bit, còn với ảnh 256 mức, thì mỗi điểm
ảnh được mã hóa trên 8 bit. Với ảnh đen trắng: nếu dùng 8 bit để biểu diễn mức xám, số
các mức xám có thể được biểu diễn là 256. Mỗi mức xám được biểu diễn dưới dạng một
số nguyên nằm trong khoảng từ 0 đến 255, với mức 0 biểu diễn cho mức cường độ đen
nhất và với 255 biểu diễn cho mức cường độ sáng nhất.
1.1.2.2. Ảnh màu
Ảnh màu theo lý thuyết của Thomas là ảnh tổ hợp từ 3 màu cơ bản: đỏ (R), lục (G),
lam (B) và thường thu nhận trên các dải băng tần khác nhau. Với ảnh màu, cách biểu
diễn cũng tự như với ảnh đen trắng, chỉ khác là các số tại mỗi phần tử của ma trận biểu
diễn cho ba màu riêng lẻ gồm: đỏ (red), lục (green), lam (blue). Để biểu diễn cho một
ảnh màu gồm 24 bit và được chia thành 3 khoảng 8 bit. Mỗi màu cũng phân thành L cấp
màu khác nhau (thường L=256). Mỗi khoảng này biểu diễn cho cường độ sáng của một
trong các màu chính. Do đó để lưu trữ ành màu người ta có thể lưu trữ từng màu riêng
biệt, mỗi màu lưu trữ như một ảnh đa cấp xám. Nên không gian nhớ dành cho một ảnh
màu lớn gấp 3 lần một ảnh đa cấp xám cùng kích cỡ.
-5-
1.2. Thu nhận và biểu diễn form tài liệu
1.2.1. Thu nhận form tài liệu
Đây là công bước đầu tiên trong quá trình xử lí form tài liệu nhưng nó có tính quyết
định đến độ phân giải, chất lượng màu, dung lượng bộ nhớ của form tài liệu nên việc lựa
chọn các thiết bị thu nhận cần quan tâm đến khả năng thu nhận ảnh của chúng. Các thiết
bị thu nhận form tài liệu bao gồm camera, scanner,.. Các thiết bị thu nhận ảnh thông
thường Raster là camera, còn Vester là sensor hoặc bàn số hóa Digitalizer hoặc được
chuyển đổi từ ảnh Raster.
Tóm lại, hệ thống thu nhận ảnh được thực hiện như một quá trình:
Cảm biến: biến đổi năng lượng quang học thành năng lượng điện.
Tổng hợp năng lượng điện thành ảnh.
1.2.2. Cấu trúc Form tài liệu
1.2.2.1. Mào đầu tệp(Header)
Mào đầu tệp [2] là phần chứa các thông tin về kiểu ảnh, kích thước, độ phân giải, số
bit dùng cho 1 pixel, cách mã hóa, vị trí màu…
1.2.2.2. Dữ liệu nén (Data Compression)
Số liệu ảnh được mã hóa bởi kiểu mã hóa chỉ ra trong phần mào đầu tệp.
1.2.2.3. Bảng màu (Palette color)
Bảng màu cho biết số màu dùng trong ảnh và bảng màu được sử dụng để hiển thị
màu của ảnh
1.2.3. Một số phƣơng pháp biểu diễn Form tài liệu
1.2.3.1. Mã loạt dài (Run – Length code)
Phương pháp này hay dùng biểu diễn cho vùng ảnh hay ảnh nhị phân. Một vùng
ảnh R có thể biểu diễn đơn giản nhờ một ma trận nhị phân:
0 nếu (m,n) R
u(m,n) =
1 nếu không
Với cách biểu diễn trên, một vùng ảnh hay ảnh nhị phân được xem như gồm các
chuỗi 0 hay 1 đan xen. Các chuỗi này gọi là mạch (run). Theo phương pháp này, mỗi
mạch sẽ được biểu diễn bởi địa chỉ bắt đầu của mạch và chiều dài mạch theo dạng:
(, chiều dài)[3].
-6-
0
1
2
3
4
0
ảnh được biểu diễn
1
(1,1) 1, (1,3) 2
2
(2,0) 4, (3,1) 2
3
(nguồn [3])
Hình 1.1. Ảnh nhị phân và các biểu diễn mã loạt dài tƣơng ứng.
1.2.3.2. Mã xích (Chain Code)
Mã xích [3] thường được dùng để biểu diễn biên ảnh. Thay vì lưu toàn bộ ảnh,
người ta lưu trữ các dãy điểm ảnh như A, B, …, M. Theo phương pháp này, 8 hướng của
vector nối 2 điểm biên liên tục được mã hóa.
Khi đó ảnh được biểu diễn qua điểm ảnh bắt đầu A cùng với chuỗi các từ mã. Một
biến thể của phương pháp này là tăng số hướng. Điều này được minh họa như hình dưới
đây:
-7-
(nguồn [3])
Hình 1.2. Minh hoạ mã xích
1.2.3.3. Mã tứ phân (Quad Tree Code)
Theo phương pháp mã tứ phân[3], một vùng ảnh coi như bao kín một hình chữ
nhật. Vùng này được chia làm 4 vùng con (Quadrant). Nếu một vùng con gồm toàn điểm
đen (1) hay toàn điểm trắng (0) thì không chia tiếp. Trong trường hợp ngược lại, vùng
con gồm cả điểm đen và điểm trắng gọi là vùng không đồng nhất, ta tiếp tục chia thành 4
vùng con tiếp và kiểm tra tính đồng nhất của các vùng con đó. Quá trình chia dừng lại
khi mỗi vùng con chỉ chứa thuần nhất điểm đen hoặc điểm trắng. Quá trình đó tạo thành
một cây chia theo bốn phần gọi là cây tứ phân. Như vậy, cây biểu diễn ảnh gồm một
chuỗi các kí hiệu b (black), w (while) và g (grey) kèm theo ký hiệu mã hóa 4 vùng con.
Biểu diễn theo phương pháp này tốt hơn so với các phương pháp trên, nhất là so với mã
loạt dài. Tuy nhiên, để tính số đo các hình như chu vi, mô men là tương đối khó khăn.
1.3. Bài toán hiệu chỉnh Form tài liệu
1.3.1. Một số vấn đề trong hiệu chỉnh form tài liệu
Hiệu chỉnh form tài liệu là một bước quan trọng, là tiền đề cho quá trình nhận dạng
ảnh được chính xác. Khi scan form tài liệu thì có thể bị nhiễu, mờ không sắc nét hoặc cần
làm rõ các chi tiết như đường biên hay tài liệu bị nghiêng, bị lệch,…Mục đích chính của
việc hiệu chỉnh form tài liệu là làm nổi bật một số đặc tính như thay đổi độ tương phản,
lọc nhiễu, nổi biên, làm trơn, hiệu chỉnh độ lêch, hiệu chỉnh độ nghiêng,…
1.3.2. Một số cách tiếp cận trong hiệu chỉnh form tài liệu
1.3.2.1. Nhiễu form tài liệu
Nhiễu do nhiều nguyên nhân: quá trình quét form tài liệu, quá trình sao chép, sự
thoái hóa theo thời gian,.. Nhiễu sẽ làm ảnh hưởng lớn đến kết quả nhận dạng form tài
-8-
liệu. Thực tế có rất loại nhiễu nhưng thường người ta xét 3 loại nhiễu chính: nhiễu cộng,
nhiễu nhân và nhiễu xung [1]:
Nhiễu cộng
Nhiễu cộng thường phân bố khắp ảnh. Nếu gọi ảnh quan sát (ảnh thu được) là
Xqs, ảnh gốc là X gốc, nhiễu là η, ảnh thu được có thể biểu diễn bởi:
Xqs = Xgốc + η
Nhiễu nhân
Nhiễu nhân thường phân bố khắp ảnh và ảnh thu được sẽ biểu diễn với công thức:
Xqs = Xgốc * η
Nhiễu xung
Nhiễu xung thường gây đột biến tại một số điểm ảnh.
1.3.2.2. Khử nhiễu
a. Lọc tuyến tính
Trong quá trình hiệu chỉnh form tài liệu cần có nhiều bộ lọc vì form tài liệu sẽ có
nhiều loại nhiễu. Với nhiễu cộng và nhiễu nhân ta dùng bộ lọc thông thấp, trung bình và
lọc đồng hình (Homomorphie), với nhiễu xung ta dùng lọc trung vị, lọc ngoài (outlier)
Lọc trung bình không gian
Với lọc trung bình [3], mỗi điểm ảnh được thay thế bằng trung bình trọng số của
các điểm lân cận và được định nghĩa như sau:
v(m, n) = ∑ ∑a(k , l ) y(m − k , n − l )
( k ,l )∈ W
Nếu trong kỹ thuật lọc trên, ta dùng các trọng số như nhau, phương trình trên sẽ trở
thành:
1
v(m, n) = N ∑ ∑ y(m − k , n − l )
( k ,l )∈ W
với : y(m, n): ảnh đầu vào,
v(m, n): ảnh đầu ra,
a(k, l) : là cửa sổ lọc.
với a k ,l =
1
và Nw là số điểm ảnh trong cửa sổ lọc W.
NW
-9-
Lọc trung bình có trọng số chính là thực hiện chập ảnh đầu vào với nhân chập H.
Nhân chập H trong trường hợp này có dạng:
Trong lọc trung bình, thường người ta ưu tiên cho các hướng để bảo vệ biên của ảnh
khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng tùy theo các trường hợp
khác nhau. Các bộ lọc trên là bộ lọc tuyến tính theo nghĩa là điểm ảnh ở tâm của số sẽ
được thay bởi tổ hợp các điểm lân cận chập với mặt nạ.
Giả sử đầu vào biểu diễn bởi ma trận I:
Ảnh số thu được bởi lọc trung bình Y=H ⊗ I có dạng:
Một bộ lọc trung bình không gian khác cũng hay được sử dụng. Phương trình của
bộ lọc đó có dạng:
Ở đây, nhân chập H có kích thuớc 2x2 và mỗi điểm ảnh kết quả có giá trị bằng
- 10 -
trung bình cộng của nó với trung bình cộng của 4 lân cận gần nhất. Lọc trung bình trọng
số là một trường hợp riêng của lọc thông thấp.
Lọc thông thấp
Lọc thông thấp [1] thường được sử dụng để làm trơn nhiễu.Về nguyên lý của bộ
lọc thông thấp giống như đã trình bày trên. Trong kỹ thuật này người ta hay dùng một số
nhân chập có dạng sau:
Ta dễ dàng nhận thấy khi b =1, Hb chính là nhân chập Ht1 (lọc trung bình). Để
hiểu rõ hơn bản chất khử nhiễu cộng của các bộ lọc này, ta viết lại phương trình thu nhận
ảnh dưới dạng:
Xqs[m,n] = Xgốc[m,n] + η[m,n]
Trong đó η[m, n] là nhiễu cộng có phương nsai σ2. Như vậy, theo cách tính của
lọc trung bình ta có:
Như vậy, nhiễu cộng trong ảnh đã giảm đi Nw lần.
Lọc đồng hình (Homomorphie Filter)
Kỹ thuật lọc này [1] hiệu quả với ảnh có nhiễu nhân. Thực tế, ảnh quan sát được
gồm ảnh gốc nhân với một hệ số nhiễu. Gọi
và (m, n) là nhiễu, như vậy:
là ảnh thu được, X(m,n) là ảnh gốc
- 11 -
Lọc đồng hình thực hiện lấy logarit của ảnh quan sát. Do vậy ta có kết quả sau:
Log(X(m, n)) = log( X (m, n) ) + log( η(m, n))
Rõ ràng, nhiễu nhân có trong ảnh sẽ bị giảm. Sau quá trình lọc tuyến tính, ta
chuyển về ảnh cũ bằng phép biến đổi hàm e mũ.
b. Lọc phi tuyến tính
Với kỹ thuật lọc phi tuyến tính, ta dùng bộ lọc trung vị, giả trung vị, lọc ngoài. Với
lọc trung vị, điểm ảnh đầu vào sẽ được thay thế bởi trung vị các điểm ảnh còn lọc giả
trung vị sẽ là trung bình cộng của 2 giá trị “trung vị” (trung bình cộng của max và min)
Lọc trung vị
Trung vị được viết với công thức:
v(m, n) = Trungvi(y(m − k , n − l ))
với {k, l} W
Kỹ thuật này [2] đòi hỏi giá trị các điểm ảnh trong cửa sổ phải xếp theo thứ tự
tăng hay giảm dần so với giá trị trung vị. Kích thước cửa sổ thường được chọn sao cho
số điểm ảnh trong cửa sổ là lẻ. Các cửa sổ hay dùng là cửa sổ có kích thước 3x3, hay 5x5
hay 7x7. Ví dụ:
Nếu y(m) = {2, 3, 8, 4, 2} và cửa sổ W=(-1, 0, 1), ảnh thu được sau lọc trung vị là:
v(m) = (2, 3, 4, 4, 2).
do đó:
v[0]= 2 ;
v[1]=Trungvi(2,3,8)=3;
v[2]=Trungvi(3,4,8)=4
v[3]= Trungvi(8,4,2)=4;
v[4]= 2 .
;
Tính chất của lọc trung vị:
Lọc trung vị là loại lọc phi tuyến. Điều này dẽ nhận thấy từ:
Trungvi(x(m)+y(m)) ≠ Trungvi(x(m)) + Trungvi(y(m)).
Có lợi cho việc loại bỏ các điểm ảnh hay các hàng mà vẫn bảo toàn độ phân
giải.
Hiệu quả giảm khi số điểm trong cửa sổ lớn hay bằng một nửa số điểm
trong cửa sổ.
Điều này dễ giải thích vì trung vị là (Nw+1)/2 giá trị lớn nhất nếu Nw lẻ. Lọc
trung vị cho trường hợp 2 chiều coi như lọc trung vị tách được theo từng chiều.
Lọc ngoài (Outlier Filter)
Giả thiết có ngưỡng nào đó cho các mức nhiễu (có thể dựa vào lược đồ xám).
- Xem thêm -