TRƯỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN
--------
BÁO CÁO
NGHIÊN CỨU KHOA HỌC
ĐỀ TÀI:
NGHIÊN CỨU GIẢI PHÁP VÀ XÂY DỰNG
PHẦN MỀM THỬ NGHIỆM CHUYỂN CÁC
DÒNG VĂN BẢN TIẾNG VIỆT TRONG HÌNH
ẢNH SANG VĂN BẢN DẠNG TEXT
VÕ HOÀNG MINH
BIÊN HÒA,THÁNG 06/2012
MỤC LỤC
Trang
Chƣơng 1 - GIỚI THIỆU ĐỀ TÀI
1.1
1.2
1.3
1.4
Đặt vấn đề ........................................................................................................ 1
Mô hình giải quyết bài toán ............................................................................. 2
Mức độ phức tạp của bài toán.......................................................................... 3
Phạm vi luận văn ............................................................................................. 4
Chƣơng 2 – PHÂN ĐOẠN ẢNH VĂN BẢN
Nhị phân hoa ảnh số ........................................................................................ 5
Thành phần liên thông ..................................................................................... 7
2.2.1 Khái niệm điểm lân cận ........................................................................ 7
2.2.2 Thành phần liên thông .......................................................................... 7
2.3 Phép chiếu và các profile ................................................................................. 8
2.4 Đồ thị kề khối ................................................................................................ 10
2.5 Lọc nhiễu ....................................................................................................... 16
2.6 Tách đoạn....................................................................................................... 18
2.6.1 Tách liên thông bằng kỹ thuật đệ quy................................................. 19
2.6.2 Giải thuật cải tiến ................................................................................ 20
2.7 Xử lý nghiên .................................................................................................. 21
2.8 Tách dòng ...................................................................................................... 13
2.8.1 Tách dòng dựa vào thành phần liên thông .......................................... 23
2.9 Tách từ ........................................................................................................... 24
2.10 Tách ký tự ...................................................................................................... 25
2.11 Chuần kích thước ........................................................................................... 26
2.11.1 Lắp khoảng trống ảnh bằng phép đóng morphology .......................... 26
2.1
2.2
Chƣơng 3 - TRÍCH CHỌN ĐẶC TRƢNG VÀ NHẬN DẠNG
3.1
3.2
Trích chọn đặc trưng ...................................................................................... 28
3.1.1 Trích chọn đặc trưng theo cấu trúc ..................................................... 28
3.1.2 Trích chọn đặc trưng theo hướng hình học......................................... 31
Tổng quan về xây dựng và huấn luyện mạng neural ..................................... 33
3.2.1 Mô hình của một neural nhân tạo ....................................................... 33
3.2.2 Các kiểu hoc với mạng neural ............................................................ 48
3.2.3 Tổng quan về các thuật toán học ........................................................ 37
Chƣơng 4 – XÂY DỰNG PHẦN MỀM
4.1
4.2
Sơ đồ xử lý của chương trình ........................................................................ 40
Xây dựng chương trình .................................................................................. 41
4.2.1 Môi trường phát triển .......................................................................... 41
4.2.2 Sơ đồ thiết kế ...................................................................................... 41
4.2.3 Các engine xử dụng trong chương trình ............................................. 42
4.2.4 Danh sách các class chính .................................................................. 42
Chƣơng 5 – THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ
5.1 Thử nghiệm ...................................................................................................... 43
5.2
Đánh giá kết quả ............................................................................................ 46
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
Kết luận..................................................................................................................... 47
Hướng phát triển ....................................................................................................... 47
Tài liệu tham khảo .................................................................................................... 48
DANH MỤC CÁC HÌNH VẺ, SƠ ĐỒ
Hình 1.1 Sơ đồ hệ nhận dạng văn bản tiếng việt ........................................................ 2
Hình 1.2 Ảnh hưởng của chất lượng văn bản đến kết quả nhận dạng........................ 4
Hình 2.1 Ví dụ điểm ảnh ............................................................................................ 5
Hình 2.2 Ví dụ chuyển ảnh đa mức xám sang ảnh nhị phân ...................................... 5
Hình 2.3 Ví dụ về lân cận 4 và lân cận 8 .................................................................... 7
Hình 2.4 Ví dụ về thành phần liên thông 4 ................................................................ 8
Hình 2.5 Ví dụ về thành phần liên thông 8 ................................................................ 8
Hình 2.6 Profile phép chiếu ngang ............................................................................. 9
Hình 2.7 Các Profile chiếu ngang và dọc của một ảnh văn bản ............................... 10
Hình 2.8 Đồ thị BAG ................................................................................................ 11
Hình 2.9 Hình bao liên thông .................................................................................. 12
Hình 2.10 Quy trình tách văn bản đã được chuẩn hóa ............................................. 13
Hình 2.11 Khoảng cách theo chiều ngang và theo chiều dọc................................... 15
Hình 2.12 Một ảnh văn bản trước và sau khi được lọc nhiễu muối tiêu .................. 16
Hình 2.13Mô hình nhiễu cộng .................................................................................. 17
Hình 2.14 Phân tích top-down .................................................................................. 19
Hình 2.15Gán nhãn cho thành phần liên thông ........................................................ 21
Hình 2.16 Đường thẳng Hough trong tọa độ cực ..................................................... 22
Hình 2.17 Biến đổi Hough phát hiện góc ngiêng ..................................................... 23
Hình 2.18 Biểu đồ phân cách của ngưỡng................................................................ 24
Hình 2.19 Các vị trí chính xác, vị trí cắt nhập nhằng ............................................... 25
Hình 3.1 Ảnh ban đầu và ảnh sau khi được bao ....................................................... 32
Hình 3.2 Mặt na Sobel theo hai hướng X và Y ........................................................ 32
Hình 3.3 Mô hình neural sinh học ............................................................................ 35
Hình 4.1 Sơ đồ xử lý của chương trình .................................................................... 40
Hình 4.2 Sơ đồ thiết kế của chương trình ................................................................. 41
Hình 5.1 Ảnh văn bản đầu vào đơn cột, kiểu font: Arial, Cambria, Times New
Roman, Tahoma, cỡ font: 16 cho kết quả nhận dạng chính xác 100% .................... 43
Hình 5.2 Chương trình cho phép lựa chọn vùng ảnh cần nhận dạng ....................... 44
Hình 5.3 Chương trình nhận dạng tốt đối với các ảnh văn bản có chèn hình .......... 44
DANH MỤC CÁC BẢNG
Bảng 3.1 Các luật về đặc trưng cấu trúc ................................................................... 29
Bảng 4.1 Danh sách các class chính trong chương trình .......................................... 42
Bảng 5.1 Thử nghiệm chương trình với font Times New Roman ........................... 45
Bảng 5.2 Thử nghiệm chương trình với font Arial .................................................. 46
LỜI MỞ ĐẦU
Những năm gần đây, nhu cầu số hóa tài liệu ngày càng bùng nổ. Hiện nay ở nước
ta, tất cả các yêu cầu về lưu trữ tài liệu, dịch thuật tự động…đều có thể thực hiện tốt nếu
có một phần mệm nhận dạng chữ in tiếng Việt hiệu quả, có độ chính xác cao và độ thực
thi nhanh. Hiện tại trên thị trường đã có một số phần mềm nhận dạng chữ in tiếng Việt,
tuy nhiên kết quả nhận được còn có nhiều hạn chế. Do đó việc nghiên cứu phương pháp
để xây dựng một hệ nhận dạng văn bản tiếng Việt là vấn đề hết sức quan trọng và có ý
nghĩa cao trong thực tiễn. Dó là lý do tôi chọn đề tài” Nghiên cứu giải pháp và xây dựng
phần mềm thử nghiệm chuyển các dòng văn bản tiếng việt trong hình ảnh sang văn bản
dạng text” để làm đề tài nghiên cứu khoa học, đề tài chia thành 5 chương với các nội dung
sau:
Chƣơng 1 – Giới thiệu đề tài: đặt vấn đề, giới thiệu những công trình liên quang, đưa ra
mô hình đã giải quyết bài toán, và những khó khăn cần phải giải quyết, phạm vi của đề
tài.
Chuong 2 – Phân đoạn ảnh văn bản: trình bài các khái niệm cơ sở của ảnh văn bản.
Nêu ra các bước tiến hành để lọc nhiểu, chình nghiên, tách lấy phần văn bản từ ảnh và
phân thành các đoạn, các dòng, các ký tự.
Chƣơng 3 – Trích chọn đặc trƣng và nhận dạng: trình bài thuật toán trích chọn lấy
những phần tiêu biểu, đặc trưng trong một ký tự để làm đầu vào của một mô hình học
máy. Trình vài cách thức dùng mạng Neural để huấn luyện nhận dạng các ký tự.
Chƣơng 4 – Xây dựng phần mềm: trình bài sơ đồ xây dựng và quy trình xử lý của
chương trình, liệt kê môt số class chính.
Chƣơng 5 – Thử nghiệm và đánh giá kết quả: thử nghiệm chương trình trên nhiều dữ
liệu khác nhau, có so sách với các chương trình khác.
Luận văn đã tập trung nghiên cứu lý thuyết về bài toán nhận dạng chữ in tiếng việt
và đã cài đặt chương trình với độ chính xác khá cao và tốc độ tương đối nhanh đối với các
văn bản tiếng Việt trên nhiều kiểu font và cỡ font khác nhau. Trong tương lai, tôi sẽ cố
gắng hoàn thiện và phát triển thêm các chức năng của chương trình để xây dựng một
phiên bản có thể thực thi trên các nền tảng điện thoại di động.
Chương 1
GIỚI THIỆU ĐỀ TÀI
1.1 Đặt vấn đề
Ngày nay công nghệ thông tin là ngành khoa học mới nhưng tốc độ phát triển rất
nhanh trên toàn thế giới. Những ứng dụng của công nghệ thông tin cũng rộng khắp trong
tất cả các lỉnh vực khoa học như: giáo dục, y tế, kinh tế, văn hóa,… nó góp phần giúp đời
sống con người ngày càng hiện đại giảm đi những công việc nặng nhọc trong đời sống
hằng ngày. Nhận dạng và xử lý ảnh cũng là một trong những chuyên ngành của tin học có
tầm ứng dụng to lớn. Có thể kể ra hàng loạt các lĩnh vực áp dụng kỹ thuật nhận dạng ảnh
như: xử lý ảnh chụp vệ tinh, dự báo thời tiết, điều khiển giao thông công cộng, nhận dạng
vân tay, nhận dạng mặt người,….Hiện nay các đề tài và công trình nghiên cứu về chuyển
đổi văn bản tiếng việt từ hình ảnh vẫn còn hạn chế và chưa đạt được kết quả như mong
muốn mặc dù đây là một hướng được nhà nước ưu tiên phát triển. Đề tài này nhằm đáp
ứng các nhu cầu hiện nay về xử lý , nhận dạng ngôn ngữ tiếng Việt và tập trung nghiên
cứu các phương pháp tách văn bản tiếng Việt từ hình ảnh chứa văn bản ( những tấm ảnh
này có thể được thu thông qua máy scanner), từ đó xây dựng chương trình thử nghiệm.
1
1.2 Mô hình giải quyết bài toán
Bài toán nhận dạng văn bản tiếng Việt được thực hiện qua ba giai đoạn chính: phân
đoạn ảnh, nhận dạng kí tự và hậu xử lý. Được thể hiện qua sơ đồ dưới đây:
Hình 1 1 Sơ đồ hệ nhận dạng văn bản tiếng Việt
2
Đầu vào hệ thống nhận dạng của chúng ta là một hình ảnh scan từ một văn bản
tiếng Việt hoặc một tập tin hình ảnh chứa văn bản tiếng Việt bất kì. Đầu ra là một văn bản
đã được nhận dạng. Để xử lý được điều này hệ thống nhận dạng của chúng ta sẽ trải qua
giai đoạn cụ thể như sau:
1. Phân đoạn ảnh: Giai đoạn này có nhiệm vụ loại bỏ nhiễu nhằm nâng cao chất lượng
hình ảnh đầu vào. Sau đó thực hiện việc nhị phân hóa, chỉnh nghiêng, tách đoạn, tách
dòng, tách từ, tách kí tự.
2. Nhận dạng kí tự: Đầu vào của giai đoạn này là ảnh của một kí tự, đầu ra là kí tự nhận
dạng được. Thông thường trong phần này sử dụng một thuật toán máy học (dùng
mạng Neural, mô hình Markov ẩn hoặc máy SVM) hoặc một bộ đối sánh mẫu.
3. Hậu xử lý: Tổng hợp các kí tự nhận dạng được và hiển thị lên giao diện người dùng.
Điều chỉnh nhận dạng sai dùng từ điển hoặc mô hình ngôn ngữ.
1.3 Mức độ phức tạp của bài toán
Nếu phân chia quá trình đọc văn bản thành các tác vụ cơ bản thì các hệ nhận dạng
hiện nay thực hiện các tác vụ đó khá chật vật và không phải khi nào cũng mang lại kết
quả mong muốn. Nhiều hệ thống nhận dạng đã làm việc khá tốt với các trang văn bản rõ
nét, nhưng xét tổng thể thì vẫn còn khoảng cách khá lớn giữa tính năng của các hệ nhận
dạng và đòi hỏi thực tế.
Thực tế các trang văn bản không bao giờ đạt được mức độ sạch sẽ, chuẩn mực
hoàn toàn. Nhiễu bẩn hiện tại là một vấn đề lớn đối với các hệ OCR, bởi vì chỉ cần một
vài chấm mực nhỏ chữ c có thể biến thành chữ o, hoặc chữ j thành chữ i... Nếu tài liệu đã
qua photocopy thì các nét mảnh có thể trở thành đứt đoạn, khi đó lỗi sẽ rất nhiều vì nhiều
hệ OCR sẽ chuyển mỗi ô liền nét thành một chữ cái riêng.
Nếu văn bản có rất sạch sẽ đi chăng nữa thì sự phong phú của các kiểu font chữ
cũng là một thách thức lớn với các hệ thống nhận dạng. Các kiểu font chữ mang tính nghệ
thuật ngày càng nhiều. Ngoài sự phức tạp về font chữ và nhiễu ra, các hệ OCR cũng phải
giải quyết các vấn đề về kích cỡ chữ khác nhau, góc nghiêng, bố cục văn bản, hệ thống
dấu thanh…Vì thế các thuật toán nhận dạng phải đủ mềm dẻo để xử lý các khía cạnh
phức tạp này. Nếu không đủ mềm dẻo thì một khác biệt rất bé của kiểu chữ cũng đòi hỏi
quản lý và xử lý riêng. Ngược lại, quá mềm dẻo thì lỗi có thể rất nhiều, chẳng hạn chữ b
và chữ h khác nhau không nhiều có thể bị đồng nhất làm một.
3
Hình 1 2 Ảnh hưởng của chất lượng văn bản đến kết quả nhận dạng
1.4 Phạm vi đề tài:
Đề tài “Nghiên cứu giải pháp và xây dựng phần mềm thử nghiệm chuyển các dòng
văn bản tiếng việt trong hình ảnh sang văn bản dạng text” tập trung vào việc trình
bày một quy trình tổng quát để giải quyết bài toán nhận dạng văn bản in tiếng Việt
và làm rõ phương pháp để giải quyết từng phần trong quy trình. Có sự phân tích, so
sánh, đánh giá giữa các phương pháp với nhau nhằm tìm ra phương pháp tối ưu để
giải quyết bài toán.
Xây dựng một chương trình nhận dạng văn bản in tiếng Việt với độ chính xác cao
(khoảng 80%) với các văn bản scan có chất lượng tốt. Tốc độ nhận dạng cao (thời
gian nhận dạng trung bình 3-5 giây trên mỗi trang).
4
Chương 2
PHÂN ĐOẠN ẢNH VĂN BẢN
2 1 Nhị phân hóa ảnh số
Ảnh số được tạo nên từ hàng trăm ngàn cho đến hàng triệu ô vuông rất nhỏ được coi
là những thành tố của bức ảnh gọi là điểm ảnh (pixel). Giá trị mỗi điểm ảnh được gán cho
một số nguyên biểu diễn màu sắc tại điểm ảnh đó.
Hình 2 1 Ví dụ điểm ảnh
Đầu vào của hệ thống là một ảnh có màu bất kì, nhưng để thực hiện được việc phân
đoạn ảnh thì bắt buộc phải thực hiện trên ảnh nhị phân. Về cơ bản quá trình này sẽ thực
hiện chuyển ảnh màu thành ảnh đa mức xám với các mức xám có giá trị từ 0 đến 255 dựa
trên ba giá trị Red, Green, Blue của ảnh đầu vào. Từ ảnh xám này, chúng ta sẽ so sánh
mức xám của từng điểm ảnh với một ngưỡng cho trước để quyết định điểm ảnh đó sẽ là 0
hoặc 1.
Hình 2 2 Ví dụ chuyển ảnh đa mức xám sang ảnh nhị phân
5
Quá trình chuyển ảnh đa mức xám sang ảnh nhị phân nhằm phân hoạch một bức ảnh
ra làm 2 phần, một phần chứa các đối tượng (object hay foreground) trong bức ảnh và
phần kia chứa nền ảnh. Quá trình này gọi là phân hoạch ngưỡng (thresholding
segmentation) được thực hiện nhờ vào hàm phân ngưỡng, trong trường hợp phân hoạch
đơn ngưỡng thì công thức được sử dụng như sau:
Dest (x,y) =
Trong đó, Source(x,y) là giá trị điểm ảnh ở vị trí (x,y) của ảnh nguồn, Dest(x,y) là
giá trị điểm ảnh tương ứng ở vị trí (x,y) của ảnh đích và T là giá trị ngưỡng. Nếu sử dụng
một T duy nhất cho toàn bộ bức ảnh, có nghĩa là công thức trên áp dụng cho toàn ảnh
trong quá trình phân hoạch thì ta gọi đó là cách dùng ngưỡng toàn cục (global
thresholding). Ngược lại nếu sử dụng ngưỡng khác nhau tùy theo từng vùng trong ảnh, T
biến thiên theo từng vị trí khác nhau và được tính toán lại tại từng vùng ảnh, có nghĩa là
công thức trên áp dụng cho từng vùng cục bộ của ảnh với T thay đổi thì đó gọi là phương
pháp dùng ngưỡng cục bộ (local thresholding).
Trong Đề tài này sử dụng phương pháp phân ngưỡng thích nghi (adaptive
thresholding) theo phương pháp Otsu. Ý tưởng chính của phương pháp này là tính
ngưỡng T một cách tự động dựa vào giá trị điểm ảnh của ảnh đầu vào. Phương pháp này
cho kết quả là mỗi ảnh khác nhau có một ngưỡng tương ứng khác nhau bằng các bước xử
lý như sau:
1. Chọn một giá trị khởi tạo cho T: Thường chọn giá trị mang tính công thức, ví dụ T =
(min + max) / 2, T = giá trị trung bình, ... tránh dùng các giá trị mang tính định lượng
thiết lập cứng).
2. Phân hoạch ảnh sử dụng T: Kết quả của bước này sẽ tạo ra 2 nhóm điểm ảnh: G1
chứa tất cả các điểm ảnh với giá trị (intensity) > T và G2 chứa các điểm ảnh với giá trị
(intensity) <= T.
3. Tính trung bình: Tính trung bình m1 và m2 của các điểm ảnh thuộc G1 và G2.
4. Tính lại T dựa vào m1 và m2: T = (m1 + m2) / 2
5. Bước lặp: Lặp lại bước 2 đến 4 cho tới khi nào giá trị chênh lệch giữa T cũ và T mới
là không đáng kể (nhỏ hơn một giá trị cho trước Delta T). Delta T thường được sử
dụng là sai số từ các phép tính toán trong quá trình xử lý.
6
2 2 Thành phần liên thông
2 2 1 Khái niệm điểm lân cận
Cho một điểm P với tọa độ (x, y), khi đó bốn điểm
N1 (x + 1, y), N2 (x – 1, y), N3 (x, y + 1), N4 (x, y – 1)
được gọi là lân cận 4 của điểm P.
Các điểm :
N1 (x + 1, y), N2 (x – 1, y), N3 (x, y + 1), N4 (x, y – 1)
N5 (x - 1, y - 1), N6 (x – 1, y + 1), N7 (x + 1, y - 1), N8 (x + 1, y + 1)
Tám điểm N1 đến N8 được gọi là lân cận 8 của điểm P.
Hình 2.3 Ví dụ về lân cận 4 và lân cận 8
2 2 2 Thành phần liên thông: liên thông bốn và liên thông tám
Hai điểm P1, P2 được gọi là liên thông bốn với nhau nếu thỏa mãn một trong hai điều
kiện:
P2 là lân cận bốn của P1 (hoặc P1 là lân cận bốn với P2)
Tồn tại điểm P3 mà P3 là lân cận bốn của P2 và P3 là lân cận bốn của P1.
7
Hình 2.4 Ví dụ về thành phần liên thông 4
Hai điểm P1, P2 được gọi là liên thông tám với nhau nếu thỏa mãn một trong hai điều
kiện:
P2 là lân cận tám của P1 (hoặc P1 là lân cận tám với P2)
Tồn tại điểm P3 mà P3 là lân cận tám của P2 và P3 là lân cận tám của P1.
Hình 2.5 Ví dụ về thành phần liên thông 8
2 3 Phép chiếu và các profile
Để thực hiện phân đoạn trong nhận dạng, người ta thường sử dụng phép chiếu hình chữ
nhật bao. Dưới đây là một số khái niệm cơ sở:
Hình chiếu trên trục đứng (vertical projection profile)
Là tổng các điểm đen của hàng thứ i trên ảnh, được kí hiệu bằng vector đặc trưng V[i]
8
Với:
V[i]: Tổng các điểm đen của hàng thứ i trên ảnh.
S[i,j]: Giá trị của điểm ảnh tại hàng i cột j (giá trị này bằng 1 nếu là điểm đen trong ảnh
nhị phân).
m: Số dòng ảnh quét
Hình chiếu trên trục ngang (horizontal projection profile)
Là tổng các điểm đen của một cột j, được kí hiệu bằng vector đặc trưng H[j]
Với:
H[j]: Tổng các điểm đen của cột thứ j trên ảnh.
S[i,j]: Giá trị của điểm ảnh tại hàng i cột j (giá trị này bằng 1 nếu là điểm đen trong ảnh
nhị phân).
m: Số cột ảnh quét
Hình 2.6 Profile phép chiếu ngang, có được bằng cách tích lũy các hình chữ nhật bao
lên đường thẳng dọc
9
Hình 2.7 Các profile chiếu ngang và dọc của một ảnh văn bản
2 4 Đồ thị kề khối
Một trang ảnh nhị phân P được biểu diễn bởi đồ thị kề khối BAG (Block Adjacent
Graph), kí hiệu B = (N, E) với:
N = {ni}: tập các nút
E = {e(ni, nj) | ni, nj
N}: tập các cạnh nối nút ni và nj
Mỗi nút ni là một khối gồm một hay nhiều đường chạy (run length) xếp chồng lên nhau
với các biên trái, phải tương đối thẳng hàng (lệnh khác một đơn vị điểm ảnh).
Mỗi nút (khối) được đặc tả bởi các tọa độ hình chữ nhật biên (góc trên bên trái (Xu, Yu) và
góc dưới bên phải (Xe, Ye)).
10
Các khái niệm cơ sở:
Đường chạy (Run length): Các điểm ảnh nằm liên tục nhau theo chiều ngang tạo thành
một đường chạy.
Khối (Block): Nhóm các đường chạy nằm kề nhau có điểm bắt đầu và kết thúc tương đối
thẳng hàng (lệch không quá 1 điểm ảnh) được gọi là một khối. Mỗi khối được đặc tả bởi
các tọa độ của hình chữ nhật.
Khối kề: Hai khối được gọi là kề nhau nếu các hình chữ nhật biên của chúng có chung
nhau một số điểm.
Liên thông: tập các khối kề nhau trên ảnh được gọi là liên thông nhau trên đồ thị khối
tương ứng.
Ảnh nguồn
Đồ thị kề khối
Hình 2.8 Đồ thị BAG
Cho trước biểu diễn đồ thị kề khối BAG, một thành phần liên thông ci = {nj} là tập
các nút BAG thỏa các điều kiện sau:
(i) ci
(ii)
B
nj, nk
ci, có một đường chạy (nj, nj1, nj2,…,njp, njk) sao cho njl ci, l = 1,2,..p
và e(nj, nj1), e(nj1, nj2)…e(njp-1, njp), e(njp, nk) E
(iii)
Nếu
e(nj, nk)
và nj
ci thì nk
11
ci
Các tọa độ góc trên bên trái và góc dưới bên phải của một thành phần liên thông ci = {nj}
là:
Xu(ci) = min{Xu(nj)}, nj ci
Yu(ci) = min{Yu(nj)}, nj ci
Xl(ci) = min{Xl(nj)}, nj ci
Yl(ci) = min{Yl(nj)}, nj ci
Dựa vào biểu diễn đồ thị kề khối BAG, ta trích chọn mỗi thành phần liên thông bằng cách
tìm kiếm các nút BAG trong một đồ thị liên thông và mỗi nút khối trong B được truy cập
O(|E|), thấp hơn hầu hết các phương pháp tuần tự (O(NlogN)) với một ảnh bitmap kích
thước N*N.
Hình bao liên thông: là hình chữ nhật có cạnh song song với hai trục tọa độ, có
diện tích bé nhất bao phủ toàn bộ miền liên thông. Hình bao được đặc tả bởi tọa độ
góc bên trái và dưới phải.
Kích thước của liên thông: là kích thước của hình chữ nhật bao.
Khoảng cách liên thông:
Khoảng cách ngang: hiệu tọa độ x giữa hai tâm hai hình bao của hai liên thông.
Khoảng cách dọc: hiệu tọa độ y giữa hai tâm hai hình bao của hai liên thông.
Phần giao của hai liên thông:
Phần giao ngang: hiệu tọa độ x giữa cạnh trên của hình bao liên thông phải và cạnh
phải của hình bao trái.
Phần giao dọc: hiệu tọa độ y giữa cạnh trên của hình bao liên thông dưới và cạnh
dưới của hình bao trên.
Hình 2.9 Hình bao liên thông
12
Như vậy, một vùng các điểm đen kề nhau trên ảnh văn bản sẽ là một miền liên thông các
khối tương ứng. Trong trường hợp các kí tự không bị rạn nứt, đứt nét thì mỗi chữ hay dấu
sẽ là một miền liên thông.
Nguyên tắc tạo từ và tạo dòng trong tiếng Việt là các kí tự được thể hiện liên tiếp nhau từ
trái sang phải và từ trên xuống dưới, những phần tử cơ bản của một hàng chính là các
thành phần liên thông.
Như vậy các công đoạn của quy trình tách ảnh văn bản đã được chuẩn hóa ra thành các kí
tự riêng lẻ có thể được thực hiện theo sơ đồ:
Hình 2.10 Quy trình tách văn bản đã được chuẩn hóa
Một ảnh văn bản P bao gồm các vùng văn bản X (gọi là vùng văn bản hay vùng text) và
các vùng không văn bản (vùng nontext). Các vùng không văn bản bao gồm vùng ảnh I,
vùng vẽ D, thước ngang H, thước dọc V và vùng bảng T.
P = (X, T, I, D, R)
Nhiệm vụ của thuật toán phân trang là lấy được các vùng văn bản X = {Xi}, các thước R
= {Hi, Vj} và các vùng không văn bản.
13
Vùng văn bản và vùng ảnh có cùng các thành phần logic, và được định nghĩa một
cách phân cấp như sau:
Xi = {tj} và Ij = {tj}
Trong đó tj = {ck } là một dòng cơ sở các thành phần liên thông gần nhau theo chiều
ngang.
Vùng bảng và vùng hình vẽ có cùng các thành phần logic và được định nghĩa như
sau:
Ti = ({tj}, {lk})
Di = ({tj}, {lk})
Trong đó, lk = {ne} biểu diễn một đường ngang hay dọc chứa các nút BAG liên thông.
Thước (ngang hay dọc) bao gồm một tập các thành phần liên thông:
Hi = {cj}, Vi = {cj}
Định nghĩa một đối tượng tổng quát Oi, trong đó Oi có thể là một nút BAG nj, một
thành phần liên thông ci, một dòng cơ sở ti hay một khối vùng bi, trong đó, b
{X,
T, I, D}; dưới dạng hình chữ nhật bao với các tọa độ góc bên trên trái và góc dưới
bên phải (Xu(Oi), Xe(Oi), Yu(Oi), Ye(Oi)). Ta có:
Chiều rộng: W = Xl – Xu
Chiều dài: H = Yl – Yu
Các khoảng cách theo chiều ngang và chiều dọc của hai đối tượng được định nghĩa
như sau:
Dx(Oi, Oj) = max(Xu(Oi), Xu(Oj)) – min(Xl(Oi), Xl(Oj))
Dy(Oi, Oj) = max(Yu(Oi), Yu(Oj)) – min(Yl(Oi), Yl(Oj))
14
- Xem thêm -