BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
NGUYỄN THỊ HỒNG HÀ
BIẾN ĐỔI HOUGH VÀ ỨNG DỤNG PHÁT HIỆN GÓC
NGHIÊNG VĂN BẢN
Chuyên ngành: Khoa học máy tính
LUẬN VĂN THẠC SĨ KỸ THUẬT
Hà Nội - năm 2011
bộ Giáo dục và đào tạo Bộ Quốc phòng
Học viện Kỹ thuật Quân sự
Nguyễn thị hồng hà
Biến đổi hough và ứng dụng phát hiện góc
nghiêng văn bản
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
luận văn thạc sĩ kỹ thuật
Hà Nội - Năm 2011
công trình đợc hoàn thành tại
học viện kỹ thuật quân sự
Cán bộ hớng dẫn chính: TS. Trần Nguyên Ngọc
Cỏn b chm phn bin 1:..................................................................
Cỏn b chm phn bin 2:..................................................................
Luận văn thạc sĩ đợc bảo vệ tại:
hội đồng chấm luận văn thạc sĩ
học viện kỹ thuật quân sự
Ngày ... tháng ... năm 2011
HC VIN K THUT QUN S CNG HềA X HI CH NGHA VIT NAM
PHềNG SAU I HC c lp T do Hnh phỳc
H Ni, ngy thỏng nm 2011
NHIệM Vụ LUậN VĂN THạC Sĩ
Họ tên học viên: Nguyễn Thị Hồng Hà Giới tính: Nữ

nhau tính toán góc ban đầu sử dụng phương pháp Scanline. …………………………26
DANH MỤC CÁC HÌNH VẼ
Hình 1.1: Các giai đoạn chính trong xử lý ảnh
5
Hình 2.1: Hộp bao quanh và điểm cơ sở của một ký tự.
12
Hình 2.2: Quét tài liệu từ sách với phương pháp Base – poin.
14
Hình 2.3: Ảnh quét từ bài thi với phương pháp Base – point.
15
Hình 2.4: Ảnh quét từ danh mục điện thoại với phương pháp Base – point.
16
Hình 2.5: Ảnh quét từ danh mục điện thoại với phương pháp Base – point
17
Hình 2.6: Quét tài liệu từ sách với phương pháp scanline
22
Hình 2.7: Ảnh quét từ bài thi với phương pháp scanline
23
Hình 2.8: Ảnh quét từ danh mục điện thoại với phương pháp scanline
24
Hình 2.9: Ảnh quét từ danh mục điện thoại với phương pháp scanline
25
Hình 2.10: Đại diện dòng bình thường
28
Hình 3.1: Đường thẳng Hough trong tọa độ cực
38
Hình 4.1: Biến đổi Hough phát hiện góc nghiêng
41
Hình 4.2: Giao diện chính chương trình
42

Bước thứ 2 là dựa trên biến đổi Hough. Biến đổi Hough là thực hiện trên
ảnh văn bản đã quét và phương sai trong các giá trị
ρ
là tính toán cho
mỗi giá trị của
θ
. Góc mà cho giá trị phương sai lớn nhất là góc
nghiêng.
Bước thứ 3 là dựa trên phương thức base-point. Sau khi Base-point liên
tiếp trong từng dòng văn bản trong khoảng thời gian thích hợp như một vùng
đã được chọn làm mẫu cho khớp đường thẳng .Tỷ lệ trung bình của đường cơ
bản được tính toán, tương ứng với mức độ nghiêng của toàn bộ văn bản hình
ảnh.
Chương trình được viết bằng ngôn ngữ Matlab trên bộ công cụ Image
Processing Toolbox để xây dựng, mẫu nhận dạng được thu thập từ các văn
bản in, viết tay và quét vào bằng máy quét ảnh với các kích cỡ và định dạng
khác nhau, thiết kế chương trình theo thuật toán đã nghiên cứu.
Chương 1
ĐẶT VẤN ĐỀ
1.1. Bài toán xử lý văn bản và các ứng dụng trong thực tế
Con người thu nhận thông tin qua các giác quan, trong đó thị giác đóng
vai trò quan trọng nhất. Con người sử dụng hệ thống thị giác để xem hoặc có
được thông tin mà thị giác thu được, cảm nhận... xử lý và hiểu nó sau đó suy
ra kết luận từ việc cảm nhận thông tin. Các lĩnh vực xử lý ảnh tập trung vào tự
động hoá quá trình thu tập và xử lý thông tin thị giác. Quá trình tiếp nhận và
phân tích thông tin thị giác của máy tính kỹ thuật số được gọi là xử lý ảnh kỹ
thuật số.
Một bức ảnh có thể được mô tả như là một hàm 2 chiểu I:
I = f ( x , y)
(1.1)

văn bản, … Những yếu tố này có thể được giải quyết trong giai đoạn tiền xử
lý. Tuy nhiên, những kết quả trung gian trong giai đoạn tiền xử lý có ảnh
hưởng quan trọng đến độ chính xác của kết quả cuối cùng của những hệ thống
OCR. Một trong những bước tiền xử lý quan trọng là phân trang ảnh văn bản,
nghĩa là, xác định cấu trúc vật lý của một văn bản là bao gồm nhiều khối,
những khối này có thể là vùng văn bản (text), hình ảnh hay bảng biểu; ở đây
chúng tôi chỉ quan tâm đến những vùng text
Phương pháp được tạo ra và lưu trữ liên tục của văn bản đã tồn tại từ
Lưỡng Hà dạng viên đất sét, các tác phẩm Trung Quốc về tre và tơ lụa cũng
như Ai Cập viết trên giấy cói. Đối với việc tìm kiếm và phục hồi, phương
pháp để lưu trữ có hệ thống tài liệu hoàn chỉnh trọng một thư viên được phát
triển bởi các nhà sư, những người chuyên ghi chép sổ sách cho các vị vua,
hoàng đế trong nhiều nền văn hoá. Lưu truyền theo thời gian nó không còn
nguyên vẹn. Việc chỉnh sửa các văn bản gặp không ít vấn đề. Tuy nhiên, phần
mền xử lý văn bản sẽ chỉ đối phó với một số hữu hạn các định dạng văn bản
kỹ thuật số. Các chuyển đổi hình ảnh của một tài liệu giấy hiện có – mà
không mất nội dung hoặc bố cục – thành một định dạng số mà nó có thể được
xử lý nguyên vẹn là điều khó khăn và thường không thể. Người sử dụng của
chúng tôi cố gắng phá vỡ các vấn đề bằng cách sử dụng một số phần mền
đóng gói Nhận dạng ký tự quang học (optical character recognition - OCR).
Hiện nay phần mềm đóng gói OCR sẽ làm công việc hợp lý giúp người sử
dụng chuyển đổi hình ảnh sang một dạng tài liệu mà có thể được xử lý bởi hệ
thống xử lý văn bản thường xuyên cung cấp cho nó có những điều kiện tối ưu
với:
• Chất lượng hình ảnh
• Phân chia các văn bản từ hình nền của nó
• Sự hiện diện của các font ký tự
• Không có kịch bản viết tay được connected-cursive và bố cục trang đơn giản
Mô hình quá trình xử lý ảnh được mô tả như sau:
Hình 1.1: Các giai đoạn chính trong xử lý ảnh

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 xử lý
ảnh. 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 xử lý
ảnh 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ý.
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…
Quả thực, trong mỗi trường hợp hạn chế nghiêm ngặt về nội dung, hình
dạng ký tự và bố cụ hiện tại, phương pháp hiện tại thậm chí là công việc khá
tốt trong việc chuyển đổi chính xác hình ảnh ký tự để các chuỗi tương ứng
của các ký tự số trong bảng mã ASCII hay Unicode. Ví dụ về các ứng dụng
như vậy là bưu điện đọc địa chỉ hoặc chữ số để xác nhận kiểm tra ngân hàng.

triển của xử lý ảnh nói chung và xử lý ảnh văn bản nói riêng, bài toán góc
nghiêng văn bản cũng được quan tâm ngày càng nhiều và dưới nhiều góc độ
khác nhau. Có rất nhiều hướng tiếp cận cho bài toán góc nghiêng văn bản từ
trước tới nay. Các thuật toán phát hiện góc nghiêng thường được xây dựng
cho các hệ thống phân tích ảnh văn bản khác nhau nên chỉ giải quyết cho
những loại ảnh văn bản cụ thể. Có thể chia ra một số hướng tiếp cận cơ bản
cho bài toán góc nghiêng văn bản như sau:
- Các thuật toán dựa vào phương pháp Base - point
- Các thuật toán dựa vào biến đổi Hough (Hough Transform)
- Các thuật toán dựa vào biến đổi Fourier (Fourier Transform)
- Các thuật toán phân tích láng giềng (Nearest Neighbour Clustering)
- Các thuật toán dựa vào phương pháp scanline…
Dựa vào tính chất mỗi đối tượng ảnh có duy nhất một chu tuyến ngoài và
quan niệm con người nhận ra độ nghiêng của văn bản dựa vào cỡ chữ chiếm
chủ đạo trong văn bản. Mục này đề cập đến việc tính toán kích thước chủ đạo
của các đối tượng ảnh trong văn bản thông qua kỹ thuật tính biểu đồ tần xuất
kích thước hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh. Việc xác định
góc nghiêng văn bản sẽ được xác định nhờ phép biến đổi Hough cho những
điểm giữa đáy của hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh cho các
đối tượng ảnh có kích thước chủ đạo.
Kết luận
Nội dung chương 1 đã giới thiệu tổng quan các bước tiền xử lý văn bản,
vai trò của nó trong việc nhận dạng văn bản. Bước đầu tiếp cận với bài toán
phát hiện góc nghiêng văn bản.
Qua nghiên cứu có rất nhiều cách tiếp cận khác nhau đối với bài toán
phát hiện góc nghiêng văn bản. Một số thuật toán tiêu biểu sẽ được trình bày
chi tiết hơn trong chương 2.
Chương 2
CÁC THUẬT TOÁN PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN
Có nhiều phương pháp khác nhau để phát hiện góc nghiêng hình ảnh văn

,h
1
≤ y ≤ h
2
,(w
1
−w
2
)≥ W
c
,(h
1
−h
2
)≥T
h
(2.1)
Ở đây
W
c
là trung bình chiều rộng của các ký tự chữ và số, và
T
h
là khoảng ngưỡng giữa những dòng kế tiếp. Cho độ rộng của văn bản
hình ảnh là W và chiều cao là H, đường biên trái của vùng nên là
w
1
=W /3
,
đường biên phải

i
∨W (C
i
)≥ D
w
V H (C
i
)≥ D
h
,1≤ x≤ k
(2.2)
Ở đây C là tập hợp các ứng viên cho các thuật toán phát hiện góc
nghiêng,
W (C
i
)
và
H (C
i
)
có chiều rộng và chiều cao của hộp ranh giới của
đối tượng
C
i
, tương ứng
D
w
là ngưỡng của độ rộng,
D
h

P
i

vào nhóm mới
G(k)
.
Bước 3: Trong phạm vi hình chữ nhật
(x
i
, y
i
−T
h
/ 2) ,(w2 , y
i
+T
h
/2)
, nếu điểm cơ sở trái nhất
P
j
(x
j
, y
j
)
không tìm thấy trong bất kỳ nhóm cơ sở nào, đưa
P
j
vào

Hình 2.3 (a)
Hình 2.3 (c)
Hình 2.4 (a)
Hình 2.4 (c)
Hình 2.5 (a)
Hình 2.5 (c)
-4
-2
-1
-1
-4
-3
-8
6
-7
15
16
-18
Bước 4: quay lại bước 2 cho đến khi tất cả các điểm cơ sở trong vùng R
đã được đưa vào trong các nhóm cơ sở khác nhau.
Áp dụng cho đường thẳng phù hợp, sử dụng phương pháp tối ưu, đối với
mỗi nhóm thu được ở cuối bước 4 để có được độ nghiêng của đường đó phù
hợp nhất cho mỗi nhóm. Lấy giá trung bình tất cả các giá trị độ nghiêng thu
được trong bước trước đó. Đây là góc nghiêng của chúng tôi.
2.1.3. Độ phức tạp
Cho số điểm ảnh trong vùng R là
N
R
. Sau thuật toán các điểm cơ sở
thì cho độ phức tạp thời gian