Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN Hoàng Thị Vân Anh TÌM HIỂU MỘT SỐ KỸ THUẬT
PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC

Thái Nguyên, tháng 11 năm 2010
Tác giả Hoàng Thị Vân Anh Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn “Tìm hiểu một số kỹ thuật phát hiện góc
nghiêng văn bản và ứng dụng” là do tôi tự tìm hiểu và đƣợc hoàn thành
dƣới sự hƣớng dẫn của thầy giáo PGS. TS Ngô Quốc Tạo.


Xử lý ảnh là gì? 3

Hình 1.2: Các giai đoạn trong xử lý ảnh 3
1.1.2.

Các vấn đề cơ bản trong xử lý ảnh 4

1.1.2.1. Nắn chỉnh biến dạng 5
1.1.2.2. Khử nhiễu 5
1.1.2.3. Chỉnh mức xám 5
1.1.2.4. Phân tích ảnh 6
1.1.2.5. Nhận dạng ảnh 6
1.1.2.6. Nén ảnh 6
1.2. Bài toán phát hiện góc nghiêng văn bản 7
1.2.1.

Giới thiệu bài toán phát hiện góc nghiêng văn bản. 7

1.2.2. Biên và phƣơng pháp phát hiện biên 8

1.2.2.1 Biên của đối tƣợng ảnh 8
1.2.2.2 Phƣơng pháp phát hiện biên trực tiếp 9
1.2.2.3 Phƣơng pháp phát hiện biên gián tiếp 11
1.2.2.4. Thuật toán dò biên tổng quát 12

ii Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên



2.5.1.1 Chọn các miền xác định và các đối tƣợng 39
2.5.1.2 Lựa chọn các đối tƣợng 40
2.5.2 Bó cụm điểm chủ đạo 41

2.5.2.1 Định nghĩa 41
2.5.2.2 Phân cụm các điểm chủ đạo 42
2.5.3 Lựa chọn đƣờng cơ sở 42

2.5.3.1 Phân loại điểm chủ đạo 42
2.5.3.2 Xác định đƣờng thẳng sử dụng phƣơng pháp bình phƣơng nhỏ nhất 44
2.5.4 Thuật toán phát hiện góc nghiêng 45

2.5.4.1 Thuật toán định hƣớng góc nghiêng đơn giản 45
2.5.4.2 Thuật toán chính 46
2.5.5. Thuật toán sửa góc nghiêng 47

2.5.5.1 Mô hình quét dòng văn bản 47

iii Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

2.5.5.2 Thuật toán chỉnh sửa góc nghiêng 48
2.5.5.3 Kết quả thử nghiệm 49
Bảng 1: Kết quả thực nghiệm của các phƣơng pháp phát hiện góc nghiêng 49
2.6 Một vài phƣơng pháp khác 50
CHƢƠNG 3 51
NÂNG CAO TỐC ĐỘ VÀ CHẤT LƢỢNG 51


DANH MỤC BẢNG BIỂU
Bảng 1: Kết quả thực nghiệm của các phƣơng pháp phát hiện góc
nghiêng………………………………………………………………… 49
DANH MỤC HÌNH VẼ
Hình 1.1 Quá trình xử lý ảnh 3
Hình 1.2: Các giai đoạn trong xử lý ảnh 3
Hình 1.3a 7
Hình 1.3b 7
Hình 1.4a: Các 4- láng giềng của điểm ảnh P 11
Hình 1.4b: Các 8- láng giềng của điểm ảnh P 11
Hình 1.5a.Chu tuyến ngoài 12
Hình 1.5b. Chu tuyến trong 12
Hình 1.6: Chu tuyến trong và chu tuyến ngoài của một đối tƣợng 12
Hình 1.7: Hƣớng các láng giềng của một điểm ảnh 13
Hình 1.8a: Hƣớng xác định cặp vùng nền xuất phát 14
Hình 1.8b: Hƣớng xác định cặp vùng nền tiếp theo 14
Hình 2.1: Biến đổi Hough cho đƣờng thẳng 16
Hình 2.2: Tham số r – φ của đƣờng thẳng 16
Hình 2.3: Biến đổi Hough trong không gian r-

17
Hình 2.4: Các hình chữ nhật ngoại tiếp 18
Hình 2.5 : Áp dụng biến đổi Hough phát hiện góc nghiêng văn 19
Hình 2.6 Quay một điểm ảnh quanh gốc tọa độ 22
Hình 2.7 Hiện tƣợng rỗ ảnh sau khi quay 23
Hình 2.8 a Ảnh gốc 23
Hình 2.8b Ảnh bị nghiêng 5
0
23
1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

MỞ ĐẦU

1. Lý do chọn đề tài
Thông tin con ngƣời thu nhận từ thế giới bên ngoài, đến hơn 80% đƣợc
ghi nhận bằng mắt tức là ở dạng ảnh. Vì vậy xử lý ảnh là một ngành khoa học
đã, đang và sẽ phát triển mạnh có ứng dụng rộng rãi trong khoa học và đời
sống thực tiễn nhƣ vẽ bản đồ, trong lĩnh vực quảng cáo, siêu thị, trong quân
sự…. Các hệ thống xử lý ảnh cho phép con ngƣời thu nhận lƣu trữ, phân tích
và nhận dạng ảnh, một bộ phận quan trọng của xử lý ảnh là xử lý văn bản.
Một trong những nhiệm vụ chính cũng là đối tƣợng của xử lý ảnh văn bản là
tự động hóa công việc văn phòng.
Hiện nay phần lớn lƣợng thông tin vẫn còn đƣợc lƣu trữ, trình bày và
phân phối thông qua phƣơng tiện chủ yếu là giấy bởi con ngƣời tin tƣởng hơn
khi nhận đƣợc văn bản giấy. Tuy nhiên có xu hƣớng đang phát triển để chia sẻ
và trao đổi thông tin điện tử, vì thế sự cần thiết để chuyển đổi từ tài liệu giấy
sang tài liệu điện tử để lƣu trữ, khôi phục và bảo trì ngày càng tăng lên. Để
chuyển đổi từ tài liệu giấy sang dạng điện tử thì kỹ thuật thƣờng gồm ba
bƣớc: quét và công nghệ kỹ thuật số, phân tích bố cục và nhận dạng ký tự.
Khi văn bản đƣợc quét vào máy, văn bản bị nghiêng là không thể tránh khỏi
do các yếu tố khác nhau khi đƣa ảnh vào. Hầu hết các thuật toán nhận dạng ký

ban đầu để cho ra ảnh mới theo mong muốn của ngƣời dùng (ví dụ nhƣ ảnh bị
nghiêng cần xử lý để thu đƣợc ảnh chính xác hơn…).
5. Phƣơng pháp nghiên cứu
5.1 Dựa trên các tài liệu
- Tìm hiểu lý thuyết liên quan đến xử lý ảnh.
- Tìm hiểu lý thuyết các kỹ thuật phát hiện góc nghiêng văn bản và
chỉnh sửa.
5.2 Phương pháp toán học
- Xử lý các số liệu thống kê 3 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

CHƢƠNG I
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN PHÁT HIỆN
GÓC NGHIÊNG VĂN BẢN

1.1. Xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh.
1.1.1. Xử lý ảnh là gì?
Quá trình xử lý ảnh đƣợc xem nhƣ là quá trình thao tác ảnh đầu vào
nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh
có thể là một ảnh “tốt hơn” hoặc một kết luận.
Hình 1.1 Quá trình xử lý ảnh
Mục đích của xử lý ảnh gồm:

Hậu xử lý
Đối sánh rút
ra kết luận

4 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

1.1.2. Các vấn đề cơ bản trong xử lý ảnh
* Ảnh và điểm ảnh:
- Điểm ảnh đƣợc xem nhƣ là dấu hiệu hay cƣờng độ sáng tại một tọa độ
trong không gian của đối tƣợng ảnh.
- Ảnh đƣợc xem nhƣ là tập hợp các điểm ảnh. Ảnh đƣợc biểu diễn bởi
một mảng số thực hai chiều (I
i j
) có kích thƣớc (m x n), trong đó mỗi phần tử
I
i j
(i = 1…m; j = 1…n) biểu đồ mức xám của ảnh tại vị trí (i, j) tƣơng ứng.
Ảnh đƣợc gọi là ảnh nhị phân nếu các giá trị chỉ nhận 0 hoặc 1.
* Mức xám: Mức xám là kết quả sự mã hóa tƣơng ứng một cƣờng độ
sáng của mỗi điểm ảnh với một giá trị số - kết quả của quá trình lƣợng hóa.
Cách mã hóa thƣờng dùng là 16, 32 hay 64 mức, mã hóa 256 mức là phổ
dụng nhất.
*
Đối tƣợng ảnh: Trong quá trình xử lý ảnh, một ảnh đƣợc thu nhận vào
máy phải đƣợc mã hóa, vì vậy ảnh phải đƣợc lƣu trữ thế nào sao cho các ứng
dụng khác nhau có thể thao tác trên các loại dữ liệu này. Một số dạng ảnh đã
đƣợc chuẩn hóa nhƣ: GIF, BMP, PCX, ; mỗi kiểu lƣu trữ ảnh đều có điểm

m g i h i
tg



mômen quán tính trung bình có mức xám ≤ g
Hàm f:
 
2
()
()
( ) ( ) ( 1)
()
g f g
tg
f g m g m G
m n t g
  



Tìm

sao cho:
01
( ) ax { ( )}
gG
f g m f g
  


1.1.2.5. Nhận dạng ảnh
Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tƣợng mà ngƣời
ta muốn đặc tả nó. Quá trình nhận dạng thƣờng đi sau quá trình trích chọn các
đặc tính chủ yếu của đối tƣợng. Nhận dạng tự động, mô tả đối tƣợng, phân
loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy,
đƣợc ứng dụng trong nhiều ngành khoa học khác nhau.
Hệ thống nhận dạng tự động bao gồm ba khâu tƣơng ứng với ba giai
đoạn chủ yếu sau: thu nhận dữ kiệu và tiền xử lý, biểu diễn dữ liệu, nhận dạng
và ra quyết định. Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là:
Đối sánh mẫu dựa trên các đặc trƣng đƣợc trích chọn, phân loại thống kê, đối
sánh cấu trúc, phân loại dựa trên mạng nơron nhân tạo.
1.1.2.6. Nén ảnh
Lƣợng thông tin để biểu diễn cho một ảnh là rất lớn, vì vậy nén ảnh
nhằm giảm thiểu không gian lƣu trữ, thƣờng đƣợc tiến hành theo cả hai
khuynh hƣớng là nén có bảo toàn và nén không bảo toàn thông tin. Nén
không bảo toàn thì thƣờng có khả năng nén cao hơn nhƣng có khả năng phục
hồi kém hơn. Các cách nén ảnh:
 Nén ảnh thống kê: Dựa vào việc thống kê tần xuất xuất hiện của giá trị các
điểm ảnh, trên cơ sở đó mà có chiến lƣợc mã hóa thích hợp. Ví dụ: mã nén
*.TIF.

7 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

 Nén ảnh không gian: Dựa vào vị trí không gian của các điểm ảnh để tiến
hành mã hóa. Kỹ thuật này dựa vào sự giống nhau của các điểm ảnh trong các
vùng gần nhau. Ví dụ: mã nén *.PCX.
 Nén ảnh sử dụng phép biến đổi: Tiếp cận theo hƣớng nén không bảo toàn,

các trang không phẳng trên trục lăn giấy. Ngoài ra, khi quét toàn bộ bề mặt
văn bản có thể bị che khuất do lỗi đƣa văn bản đầu vào trong qúa trình quét.
Cùng với sự phát triển của xử lý ảnh, đã có nhiều hƣớng tiếp cận áp dụng cho
bài toán phát hiện góc nghiêng văn bản nhƣ biến đổi Hough, phép chiếu, các
phép toán hình thái, phân tích láng giềng, Các đặc trƣng của từng phƣơng
pháp sẽ đƣợc trình bày ở chƣơng tiếp theo.
Khi xem xét một văn bản, để kết luận văn bản có bị nghiêng hay không
cách làm của con ngƣời là căn cứ vào một số đối tƣợng chủ đạo và góc
nghiêng văn bản đƣợc ƣớc lƣợng dựa vào đƣờng nối các điểm giữa đáy của
các đối tƣợng này. Xuất phát từ nhận xét trên, luận văn sẽ trình bày một
phƣơng pháp phát hiện góc nghiêng văn bản từ kỹ thuật xác định chu tuyến
một đối tƣợng ảnh và áp dụng biến đổi Hough lên điểm giữa đáy hình chữ
nhật ngoại tiếp các đối tƣợng có kích thƣớc chủ đạo trong ảnh. Việc xác định
các hình chữ nhật này dựa vào biên hay chu tuyến ngoài của các đối tƣợng.
1.2.2. Biên và phương pháp phát hiện biên
1.2.2.1 Biên của đối tượng ảnh
Biên là một vấn đề chủ yếu trong phân tích ảnh vì các kỹ thuật phân đoạn ảnh
chủ yếu dựa vào biên. Có thể thấy tầm quan trọng của biên khi ta theo dõi một họa sĩ
làm việc. Giả sử anh ta muốn vẽ một quả bóng, nét đầu tiên đƣợc phác họa chính là
đƣờng biên của quả bóng sau đó mới đến các chi tiết bên trong. Nhƣ vậy, mới chỉ nhìn
biên của sự vật ta cũng đã hình dung ít nhiều về nó và có thể phân biệt đƣợc với các sự
vật khác.

9 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

Một điểm ảnh đƣợc xem là biên nếu ở đó có sự thay đổi đột ngột về mức xám.
Tập hợp các điểm biên tạo thành biên hay một đƣờng bao của ảnh (boundary). Trong

yxfdyyxf
y
yxf
fy
),(),(),( 





Với dx, dy là khoảng cách giữa các điểm theo hƣớng x và y (đƣợc tính bằng số
điểm ảnh). Trong hệ toạ độ cực ta có:
f(x,y) = f(r.cos, r.sin)
x = r.cos, y = r.sin.

10 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

cos sin
xy
f f x f y
ff
r x r y r

    
   
    


Kỹ thuật Sobel: Tƣơng tự nhƣ kỹ thuật PreWitt, kỹ thuật Sobel sử dụng 2 ma trận mặt
nạ nhân chập là:
b. Kỹ thuật Laplace:
Các phƣơng pháp đánh giá Gradient ở trên làm việc rất tốt khi độ sáng thay đổi
rõ nét. Tuy nhiên, khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phƣơng
pháp Gradient lại kém hiệu quả so với phƣơng pháp đạo hàm bậc 2 Laplace. Theo định
nghĩa , toán tử Laplace nhƣ sau:

2
f =
2
2
2
2
y
f
x
f






Ta có:
x
yxfyxf
x
f
x

x
= -2 0 2
-1 0 1
-1 -2 -1
H
y
= 0 0 0
1 2 1

11 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

 [f(x+1,y) - f(x,y)] - [f(x,y) - f(x-1,y)]
= f(x+1,y) – 2f(x,y) + f(x-1,y).
Tƣơng tự:



2
2
y
f
f(x,y+1) - 2f(x,y) + f(x,y-1).
Mặt nạ nhân chập:

Trong thực tế, ngƣời ta thƣờng sử dụng một số biến dạng khác của toán tử
Laplace bằng cách sử dụng một số mặt nạ sau:


n
>. Trong đó 4-láng giềng đƣợc định nghĩa
là các điểm trực tiếp bên trên, dƣới, trái, phải của một điểm. Và 8-láng giềng là những
điểm 4-láng giềng hoặc các điểm trên trái, trên phải, dƣới trái, dƣới phải trực tiếp của
một điểm.
Chu tuyến đối ngẫu
0 1 0
H

= 1 -4 1
0 1 0
0 -1 0
H
1
= -1 4 -1
0 -1 0
-1 -1 -1
H
2
= -1 8 -1
-1 -1 -1
1 -2 1
H
3
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

Hai chu tuyến C = <P
1
, P
2
, P
n
> và C‟ = <Q
1
, Q
2
, , Q
n
> đƣợc gọi là hai chu
tuyến đối ngẫu của nhau nếu và chỉ nếu i j sao cho:
 P
i
và Q
j
là 4 láng giềng của nhau.
 Các điểm P
i
là vùng thì Q
j
là nền và ngƣợc lại.
Chu tuyến trong
Chu tuyến C đƣợc gọi là chu tuyến trong nếu và chỉ nếu:

Chu tuyến ngoài
Hình 1.5a.Chu tuyến ngoài
Hình 1.5b. Chu tuyến trong

13 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

Bước 4: Nếu gặp lại cặp nền vùng xuất phát thì dừng, ngƣợc lại quay lại bƣớc 2.
Khái niệm cặp vùng nền đƣợc định nghĩa gồm một điểm vùng và một điểm
nền, trong đó nếu điểm vùng đi đƣợc một vòng chu tuyến thì điểm nền cũng đi đƣợc
một vòng chu tuyến đối ngẫu.
a. Xác định cặp vùng nền xuất phát.
Để xây dựng các hàm xác định cặp vùng nền xuất phát và tiếp theo, ta định
nghĩa các hƣớng tƣơng ứng với 8-láng giềng của một điểm ảnh. Gọi Orient []là mảng
dùng lƣu các hƣớng trên, mỗi phần tử tƣơng ứng là độ lệch hàng và cột của một láng
giềng so với điểm đang xét.

Với một điểm P(x,y) của ảnh Image có màu c và hƣớng đi hiện tại là dir, hàm
tìm cặp vùng nền xuất phát Inverse sẽ xác định một hƣớng đi xuất phát cho P.
Phƣơng pháp: Từ hƣớng đi hiện tại quay theo chiều ngƣợc kim đồng hồ cho
đến khi gặp một điểm cùng màu với điểm ảnh đang xét. Nếu thành công hàm trả về
hƣớng đi trƣớc đó, ngƣợc lại hàm trả về 8 (một giá trị không thuộc mảng Orient[]).

6
3
7
Hình 1.8a: Hƣớng xác định cặp
vùng nền xuất phát.
2
1
0
4

5
6
3
7
Hình 1.8b: Hƣớng xác định cặp
vùng nền tiếp theo.

14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên Tƣơng tự nhƣ hàm xác định cặp vùng nền xuất phát, để tìm một hƣớng đi cho
bƣớc kế tiếp từ hƣớng đi hiện tại ta quay theo chiều kim đồng cho tới khi gặp điểm có
cùng màu với điểm hiện tại và hàm trả về hƣớng đi đó. Hàm Next dùng để xác định
hƣớng đi tiếp theo. Hàm hàm trả về -1 (giá trị không thuộc Orient[]) nếu không thành
công.
c. Thuật toán dò biên.
Sau khi đã xây dựng đƣợc hai hàm Inverse và hàm Next xác định cặp vùng nền

Một phƣơng pháp cơ bản mà chúng ta có thể mô tả các đối tƣợng bởi các hàm
toán học mà các hàm này miêu tả biên đƣờng thẳng, đó là biến đổi Hough; đƣợc phát
hiện vào năm 1962 do Paul Hough phát minh. Mặc dù về mặt lý thuyết các công thức
toán học phức tạp có thể sử dụng đƣợc nhƣng lại đặt ra những yêu cầu tính toán có
thực hiện đƣợc hay không.
2.1.1 Đường thẳng Hough
Với biến đổi Hough, phần lớn các thông tin trên cạnh ảnh không đƣợc sử dụng
và để chuyển sang một hình thức khác thì bƣớc đầu tiên là sử dụng kỹ thuật chọn
ngƣỡng. Bất kỳ điểm nào mà Gradient ở trên ngƣỡng này thuộc về biên, các điểm ảnh
đó gọi là điểm cạnh. Kỹ thuật này là tốt cho hình ảnh có độ tƣơng phản cao nhƣng làm
giảm tính ứng dụng của nó. Biến đổi Hough là á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 tung. Xét
đƣờng thẳng trong mặt phẳng tọa độ có phƣơng trình:
y – m*x – c = 0 (2.1)
Trong đó m và c là 2 hằng số, nếu ta chọn một điểm trên mặt phẳng tọa độ
Đêcac (X, Y) nó có thể thuộc họ các đƣờng đƣợc xác định bởi các giá trị khác nhau
của m và c. Một điểm (x
i
, y
i
) trong không gian Đêcac sẽ tƣơng ứng với hằng số m – c
đƣợc cho bởi phƣơng trình: y
i
– m*x
i


r

φ
X
cos( ) ysin( )rx



Y
Hình 2.2: Tham số r – φ của đƣờng thẳng

[x
1
,y
1
]

[x
1
,y
1
]
v

[x
1
,y
1
]

,y
1
]
v

[x
1
,y
1
]

[x
2
,y
2
]
[x
3
,y
3
]
[x
4
,y
4
]
[x
5
,y
5

ii
xy
MM



Ta đƣa phƣơng trình (2) về dạng:
cos( )cos( ) sin( )sin( )r M M
   


cos( )M



Trong đó φ là hằng số không đổi. Vì vậy một điểm trong không gian
tọa độ cực tƣơng ứng với hình sin trong không gian r-

, và ta tìm điểm mà
đa số các đƣờng sin này giao nhau (hình 2.3)
Phƣơng trình (2.2) có thể đƣợc xem là mối quan hệ giữa các tọa độ (x,
y) của một số điểm trên cạnh ảnh, và giá trị của các tham số [r, q] xác định
trên đƣờng thẳng. Do đó ta phải lƣợng tử hóa các thông số vào các giá trị
Biến đổi các điểm sang
đƣờng hình sin trong không
gian r-
