Mục lục
Mục lục . i
Danh mục các hình ảnh . iv
MỞ ĐẦU . 1
I. Đặt vấn đề . 1
II. Nội dung nghiên cứu . 2
III. Bố cục của luận văn . 4
Chương I. TỔNG QUAN VỀ NHẬN DẠNG CHỮ VIẾT . 5
VÀ PHÂN TÍCH TRANG TÀI LIỆU . 5
I.1. Ảnh tài liệu và nhận dạng ảnh tài liệu . 5
I.1.1. Tổng quan về ảnh tài liệu . 5
I.1.2. Nhận dạng tài liệu và vai trò của phân tích ảnh tài liệu . 6
I.2. Cấu trúc của ảnh tài liệu . 7
I.2.1. Cấu trúc vật lý . 8
I.2.2. Cấu trúc logic . 10
I.3. Quá trình phân tích tài liệu . 10
I.3.1. Tiền xử lý(preprocessing): . 11
I.3.2. Phân tích cấu trúc vật lý . 12
I.3.3. Phân tích cấu trúc logic . 13
I.4. Một số hệ thống phân tích tài liệu hiện nay . 14
I.4.1. VnDOCR . 14
I.4.2. OminiPage . 18
I.4.3. Finereader . 20
I.5. Kết luận . 22
Chương II: CÁC PHưƠNG PHÁP TIẾP CẬN . 23
ĐỂ PHÂN TÍCH TRANG TÀI LIỆU . 23
II.1. Các phương pháp phân tích định dạng trang tài liệu . 23
II.1.1. Top-down . 23
II.1.2. Bottom-up . 30
II.1.3. Phương pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) . 32
II.1.4. Fractal Signature (FS) . 34
II.2. Lựa chọn giải pháp . 38
II.3. Thiết kế hệ thống. 39
II.3.1. Sơ đồ khối . 39
II.3.2. Ảnh đầu vào . 39
II.3.3. Module Tiền xử lý . 40
II.3.4. Phân tích sử dụng giả pháp Fractal Signature . 41
II.4. Kết luận . 45
Chương III: XÂY DỰNG CHưƠNG TRÌNH THỬ NGHIỆM . 46
III.1. Yêu cầu hệ thống . 46
III.2. Thiết kế chương trình . 46
III.2.1. Cấu trúc dữ liệu . 46
III.2.2. Module chuẩn hóa ảnh . 48
III.2.3. Module giao diện chính . 51
III.2.4. Module phân tích Top-down (TD) . 52
III.2.5. Module phân tích Fractal Signature . 55
III.2.6. Module lọc và làm trơn nhiễu . 57
III.2.7. Module mô phỏng thuật toán FS . 58
III.2.8. Các hàm chức năng chính của image processing tool trong matlab sử
dụng trong chương trình . 60
III.3. Kết luận và đánh giá kết quả . 62
Kết luận . 83
TÀI LIỆU THAM KHẢO . 84
Phục Lục . 85
A. Mã nguồn đầy đủ của chương trình . 85
A.1. Danh mục các chương trình con trong chương trình . 85
A.2. Sơ khối liên kết giữa các thủ tục trong chương trình. 86
A.3. Mã nguồn các module . 86
105 trang |
Chia sẻ: netpro | Lượt xem: 1952 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Luận văn Nhận dạng chữ viết và phân tích trang tài liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ếp tới khi mọi khối trên trang đƣợc xác định. Trong phạm vi luận văn này,
chỉ giới thiệu một số cách tiếp cận đƣợc coi là bottom-up nhƣng sử dụng những phƣơng
pháp trực tiếp rất khác nhau nhằm đạt cùng mục đích.
Môt giải pháp đƣợc mô tả với các bƣớc nhƣ sau:
1. Xác định góc nghiêng thông qua phép biến đổi Hough
2. Xác định khoảng cách giữa các dòng thông qua việc xác định khoảng cách
giữa các đỉnh của phép chiếu nghiêng cố định bằng góc nghiêng tìm đƣợc.
3. Làm trơn theo loạt (run-length-smothing), sau đó thực hiện tách các từ hoặc ký
tự dựa vào việc xác định các khoảng trắng trong dòng thông qua việc tìm đỉnh
trên biểu đồ chiếu nghiêng và các độ dài vùng đen (các từ).
4. Thực hiện phép nhóm bottom-up các phần văn bản nhờ một loạt thao tác làm
trơn theo loạt, theo các hƣớng. Kết quả thu đƣợc là các vùng ON và ta phân
tích các vùng liên thông trên đó. Tính toán một vài số liệu trên những vùng
liên thông này, ví dụ khoảng chiều cao và chiều dài các từ. Những thông tin
đặc trƣng này đƣợc dùng để phân biệt các khối văn bản và phân biệt phần văn
bản và phần đồ họa. Esposito6 đã dùng cách tiếp cận tƣơng tự, nhƣng trƣớc hết
xác định hợp biên của từng ký tự, sau đó thao tác trên hợp biên này, thay vì
trên từng pixel nhằm giảm lƣợng tính toán.
Một phƣơng pháp Dostrum bó cụm khác thực hiện với k lân cận gần nhất để nhóm
các ký tự và các dòng văn bản và các khối cấu trúc (Hình 26).
- Trƣớc tiên, với mỗi phần tài liệu, xác định các đƣờng nối k lân cận gần nhất
với các phần xung quanh. Khoảng cách và góc của các đƣờng nối này đƣợc vẽ
trên các biểu đồ. Vì hầu hết các đƣờng nối đƣợc tạo giữa các ký tự cùng dòng,
góc tối đa sẽ chỉ ra góc nghiêng và khoảng cách tối đa sẽ là khoảng cách giữa
các ký tự. Sử dụng các ƣớc lƣợng này, các dòng văn bản đƣợc xác định nhƣ
6 Floriana Esposito, Dipartimento di Informatica, Università degli Studi di Bari, Italy
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31 GVHD: PGS. TS. Ngô Quốc Tạo
nhóm các ký tự và các từ dọc theo hƣớng của trang. Các dòng văn bản đƣợc
nhóm thành các khối-sử dụng đặc tính của tài liệu là các dòng cùng khối
thƣờng gần nhau hơn các dòng khác khối.
b) Hạn chế
Phƣơng pháp phân tích Bottom-Up cũng tồn tại nhiều hạn chế nhƣ sau:
- Cần phải phân đoạn để xác định các thành phần cơ sở trƣớc khi có thể nhóm
lại.
Hình 26: Phƣơng pháp Dostrum cho phân tích định dạng trang từ dƣới lên. (a) Một
phần của nội dung văn bản gốc. (b) Các thành phần lân cận gần nhất đƣợc xác định.
(c) Các hình chữ nhật tối thiểu tạo nên nhóm láng giềng gần nhất từ đó xác định đƣợc
dòng văn bản.
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32 GVHD: PGS. TS. Ngô Quốc Tạo
- Tốc độ thực hiện chậm và phụ thuộc vào số thành phần trong trang tài liệu
- Cũng nhƣ Top-Down hiệu quả phục thuộc trực tiếp vào việc xác định đƣợc
góc nghiêng của tài liệu, vì khoảng cách dòng và từ chỉ xác định chính xác
đƣợc nếu góc nhiêng của tài liệu ≈00
- Kém hiệu quả với những trang tài liệu có cấu trúc phức tạp (nhiều bảng, tỷ lệ
đồ họa lớn hơn văn bản).
- Kém hiệu quả với loại trang tài liệu có nhiều loại Font chữ (chứa nhiều size
chữ khác nhau), vì với các trang chứa nhiều font có size khác nhau hoặc loại
font chữ nghiêng đặc biêt với chữ viết tay thì chƣơng trình rất khó có thể tính
đƣợc chiều cao chữ hay độ rộng giữa hai dòng thông qua biểu đồ chiếu
nghiêng.
II.1.3. Phƣơng pháp Tách và Nối thích nghi (Adaptive Split – and – Merge)
a) Tổng quan
Phƣơng pháp phân tích Adaptive Split – and – Merge đƣợc Lui, Tang và Suen
thiết kế với ý tƣởng chính từ một trang tài liệu ban đầu và coi đó nhƣ một vùng chƣa
đồng nhất, từ đó liên tiếp chia mỗi vùng thành các vùng nhỏ hơn, tại mỗi bƣớc chia thực
hiện nối các vùng đồng nhất và chia tiếp các vùng không đồng nhất.
Để có thể mô tả đƣợc thuật toán một cấu trúc cây tứ phân phân lớp đƣợc sử dụng
để biểu diễn quá trình tách và nối của thuật toán. Trong đó nút ở đỉnh tƣơng ứng với
trang tài liệu ban đầu và là gọi là lớp cao nhất, các nút con tiếp theo là các vùng con
tƣơng ứng với lớp thứ k của bƣớc chia thứ k các vùng không đồng nhất (mô tả ở hình).
Các bƣớc của thuật toán[7]:
B1: Tại lớp thứ K nếu tìm thấy một vùng không đồng nhất thì tiến hành
chia vùng đó thành 4 vùng nhỏ hơn
B2: Nếu thấy ít nhất 2 vùng trong 4 vùng vừa tách là đồng nhất thì tiến
hành nối chúng lại, còn các vùng không đồng nhất ta qua lại B1 và tách
chúng thành các vùng ở lớp thứ K+1.
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33 GVHD: PGS. TS. Ngô Quốc Tạo
Tiêu chuẩn xác định vùng đồng nhất để nối ghép[7]
Hai vùng tƣơng ứng rm và rn đƣợc coi là đồng nhất nếu chúng thảo mãn điều kiện
sau:
Trong đó:
Lớp 0
(Trang tài liệu)
Lớp 1
(Trang tài liệu được chia
thành 4 cùng nhỏ hơn)
(Nối 2 vùng đồng nhất)
Lớp 2
Tách vùng không
đồng nhất ở lớp 1
thành 4 vùng nhỏ hơn
Hình 27: Mô tả thuật toán Tách và Nối thích nghi
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34 GVHD: PGS. TS. Ngô Quốc Tạo
Trong đó: Nm và Nn biểu thị số vùng con trong mỗi vùng tƣơng ứng rm và rn. và
biểu thị giá trị trung bình của mỗi vùng tƣơng ứng rm và rn.
b) Ƣu điểm
- Có thể áp dụng với các loại trang tài liệu có cấu trúc phức tạp vì thuật toán này
không quan tâm đến việc phân đoạn các thành phần cơ sở, mà chỉ chia trang tài
liệu thành các vùng hình chữ nhật và xem xét giá trị trung bình của nó. Nhƣ
vậy các trang tài liệu có thể bỏ qua khâu xác định và hiệu chỉnh độ nghiêng
- Có thể áp dụng cho các loại trang tài liệu có nhiều loại font chữ khác nhau
- Tốc độ thực hiện nhanh hơn so với Top-down và Bottom-up
c) Hạn chế
- Hiệu quả của thuật toán phụ thuộc vào giá trị trung bình của vùng đƣợc xét,
trong một số tình huống thì giá trị trung bình của vùng văn bản và vùng đồ họa
là nhƣ nhau. Cho nên thuật toán này vẫn có thể phân đoạn nhầm.
- Không có một giá trị hằng số τ cho mọi trang tài liệu vì thế việc xác định giá τ
là một vấn đền khó.
II.1.4. Fractal Signature (FS)
a) Tổng quan
Ý tƣởng chính của thuật toán chia trang tài liệu A thành các vùng có kích thƣớc
bằng nhau Bk (k=1,..,n) sao cho Bk Є A. Sau đó tính FS cho mỗi vùng này, theo lý thuyết
FS thì nếu có 3 vùng B1(giả thiết là vùng nền), B2(giả thiết là vùng chữ), B3(giả thiết là
vùng đồ họa) thì luôn có FS(B1)<FS(B2)<FS(B3).
Quá trình thực hiện thuật toán có thể đƣợc mô tả nhƣ sau:
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35 GVHD: PGS. TS. Ngô Quốc Tạo
Cơ sở toán học tính Fractal Signature[1]
Cho F{Xi,j}, với i=0,1,…,K và j=0,1,…,L là một ảnh tài liệu đa cấp xám, trong đó
Xi,j là giá trị cấp xám của điểm ảnh thứ (i,j). Trong một dải đo nào đấy thì bề mặt tạo bởi
các độ xám của các điểm ảnh có thể xem nhƣ một phần tử hình học (Fractal). Vùng bề
mặt này có thể đƣợc dùng để xác định gần đúng hƣớng hình học của nó (Fractal
dimension). Cho một đơn vị đo , khi đó thể tích của một vùng A( ) có thể đƣợc tính
xấp xỉ nhƣ sau:
B1 B2 B3
B4 B5 B6
B7 B8 B9
…
… … Bn
FS1 FS2 FS3
FS4 FS5 FS6
FS7 FS8 FS9
…
… … FSn
B1: Trang tài liệu đƣợc
chia thành n block
B2: Tính FS cho từng Block
FS1 FS5
FS8
FS7 FS9 FSn …
FS3 …
Thuộc vùng Nền
FSthấp
Thuộc vùng Text
FStrung bình
Thuộc vùng Graphic
FSCao
B3: Phân đoạn dựa vào FS
Hình 28: Mô tả thuật toán FS
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36 GVHD: PGS. TS. Ngô Quốc Tạo
(1)
trong đó là một hằng số, D là fractal dimension có thể tính đƣợc từ A( ). Để
chính xác hơn ta logarithm hai vế của phƣơng trình (1) ta đƣợc:
Để tính fractal dimension, chúng ta cần đo đƣợc vùng bề mặt mức xám, trong giải
thuật này sử dụng đối tƣợng là một “lớp” (blanket) để tính. Ý tƣớng tƣởng của kỹ thuật
sử dụng “blanket” dựa theo định nghĩa về -parallel body Fδ” nhƣ sau:
Trong kỹ thuật “blanket” tất cả các điểm trong không gian 3 chiều trong phạm vi
tính từ bề mặt mức xám đƣợc xét đến. Các điểm này tạo thành một “blanket” (lớp) bao
bọc với độ dầy là của bề mặt đang xét. Một ảnh tài liệu đƣợc biểu thị qua một hàm
mức xám g(i,j). Khối “Blanket” bao bọc đƣợc định nghĩa chính là lớp phía trên uδ(i,j) và
lớp phía dƣới bδ(i,j) của g(i,j). Và thể tích Volδ của khối blanket đƣợc tính nhƣ sau:
Định nghĩa: Thể tích Volδ của một Blanket tính đƣợc quá bán kính δ, tứ đó ta có thể tính
đƣợc cho một vùng bề mặt hình học (area of a fractal surface) và chúng ta gọi nó là đặc
trƣng hình học (FS – Fractal Signature):
Theo công thức (1) ta có một vùng bề mặt hình học nhƣ sau:
Theo đó hƣớng hình học D có thể đƣợc tính, để xác định hƣớng ta chỉ cần đến 2 điểm vì
vậy ta sẽ phải dùng 2 giá trị δ để tính hƣớng hình học, khi đó ta cho δ = δ1 và δ2, sau đó
tính:
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37 GVHD: PGS. TS. Ngô Quốc Tạo
Ta lấy biểu thức (5) chia cho biểu thức (6) đƣợc:
Tiến hành logarithm hai vế ta đƣợc:
Vậy D đã đƣợc tính:
Ứng dụng phân tích tài liệu dựa vào FS[1]
FS đƣợc sử dụng để xác định cấu trúc hình học của một tài liệu. Một bề mặt thu
đƣợc từ việc ánh xạ hàm mức xám của một ảnh tài liệu, do đó FS phản ánh các đặc tính
chính cần một ảnh tài liệu.
Xét một trang tài liệu F, giải thiết nó có một số vùng với các nội dung nhƣ văn bản
(Texts), đò họa (Graphics) hay nền (Background).
Trong đó:
là tập các vùng văn bản
là tập các vùng đồ họa
tập các vùng nền
Các vùng khác nhau sẽ có hàm giá trị mức xám khác nhau
. Các hàm mức xám khác nhau sẽ dẫn đến các bề mặt khác nhau và tất nhiên
các bề mặt khác nhau thì sẽ có các FS khác nhau (A A ).
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38 GVHD: PGS. TS. Ngô Quốc Tạo
Định lý: Cho là một khối văn bản của một tài liệu, và , nếu cả hai khối này có
cùng một kích thƣớc hình học thì FS của vùng văn bản luôn lớn FS của vùng nền.
Đây là đặc tính rất quan trọng của FS va nó có thể đƣợc dùng để định dạng các
loại vùng khác nhau trong tài liệu.
b) Ƣu điểm
- Tốc độ thực hiện chỉ phụ thuộc vào kích thƣớc của ảnh mà không phụ thuộc
vào cấu trúc của tài liệu
- Hiệu quả cao với các loại tài liệu có cấu trúc phức tạp.
- Hiệu quả cao với các loại tài liệu có nhiều kiểu font, hay font chữ nghiêng, chữ
viết tay.
- Làm việc tốt với cả ảnh đa cấp xám và ảnh nhị phân
c) Nhƣợc điểm
- Không có một quy chuẩn để chọn đƣợc kích thƣớc Block là tốt nhất (thƣờng
dựa vào kinh nghiệm).
- Với mỗi loại trang tài liệu thì ngƣỡng để phân tách miền giá trị FS cho mỗi
vùng nền, văn bản và đồ họa là khác nhau.
- Với các loại tài liệu có cấu trúc đơn giản hoặc biết trƣớc thì tốc độ thực hiện
chậm hơn so với thuật toán Top-down và Bottom-up.
II.2. Lựa chọn giải pháp
Các phƣơng pháp phân tích Top-down và Bottom-up đã đƣợc một số nghiên cứu
trong nƣớc phát triển, vì thế trong đề tài này sẽ dừng ở mức độ giới thiệu để so sánh. Từ
phần II.1 dễ nhận thấy rằng thuật toán Fractal signature có nhiều ƣu điểm vƣợt trội với
các loại ảnh tài liệu có cấu trúc phức tạp. Đồng thời có thể làm việc với ảnh đa cấp xám
điều mà Top-down(TD) và Bottom-up(BU) không làm đƣợc. Vì thế trong phạm vi đề tài
này sẽ tập trung nghiên cứu và triển khai phƣơng pháp Fractal Signature (FS) với các
mục tiêu sau:
- Phân tích với ảnh đầu vào là đa cấp xám.
- Phát triển FS có hiệu quả cao với các loại trang tài liệu có cấu trúc phức tạp mà
TD và BU kém hiệu quả.
- Đầu ra của hệ thống là khoanh vùng đƣợc vùng ảnh và vùng văn bản.
- Phát triển thuật toán Top-down để so sánh với FS.
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39 GVHD: PGS. TS. Ngô Quốc Tạo
II.3. Thiết kế hệ thống
II.3.1. Sơ đồ khối
II.3.2. Ảnh đầu vào
- Ảnh đầu vào đƣợc chọn là ảnh đa cấp xám với định dạng “*.JPG”. Do thời gian có
hạn nên đề tài chỉ tập trung vào loại ảnh này, với anh màu cần phải chuyển sang
đa cấp xám trƣớc khi qua phân tích.
- Về kích thƣớc ảnh đầu vào về mặt thiết kế là không giới hạn.
- Với ảnh nhị phân là trƣờng hợp đặc biệt của ảnh đa cấp xám thì đã đƣợc các đề tài
trƣớc phân tích và trong thực tế thì thao tác với ảnh nhị phân đơn giản hơn so với
ảnh đa cấp xam (vì không cần phân ngƣỡng) nên đề tài không cài đặt cho loại ảnh
này.
Ảnh tài liệu
đa cấp xám
Tiền xử lý
Lọc và làm trơn nhiễu
Phân tích
Sử dụng Fractal signature
Ảnh đã đƣợc
khoanh vùng Văn
bản và Đồ họa
Hình 29: Sơ đồ khối hệ thống phân tích tài liệu trong phạm vi đề tài
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40 GVHD: PGS. TS. Ngô Quốc Tạo
- Về độ phức tạp của ảnh về mặt thiết kế là không giới hạn.
II.3.3. Module Tiền xử lý
Nhằm nâng cao hiệu quả cho quá trình phân tích, ảnh sẽ đƣợc qua khâu tiền xử lý
trƣớc khi qua khâu phân tích. Trong phạm vi đề tài này khâu tiền xử lý chỉ dừng ở mức
lọc và làm trơn nhiễu. Lý do là khâu phân tích sử dụng giải pháp FS không bị ảnh hƣởng
bởi góc nghiêng của tài liệu, tham số duy nhất ảnh hƣởng đến giá trị của FS là nhiễu.
Vì bản chất của FS là đi tính hiệu thể tích của hai lớp đƣợc tạo ra từ mỗi block ảnh
chuyển sang không gian 3D và dịch theo phƣơng z một khoảng ±Δ. Có thể so sánh quá
trình FS nhƣ đi tính thiết diện bề mặt của mỗi Block hay còn gọi là độ nhám từ đó đƣa ra
các miền giá trị FS đặc trƣng cho mỗi vùng (Text, Graphic,…) (Hình-30). Từ đó dễ nhận
ra rằng nếu tồn tại các nhiễu dạng muỗi thì có thể làm một vùng nền (độ nhám =0) trở
thành một vùng bề mặt cực nhám dẫn đến FS của nó có thể trùng vào miền Text hoặc
Graphic. Để khắc phục một giải pháp là khử và làm trơn nhiều nhằm làm giảm ảnh
hƣởng của vùng nhiễu muỗi lên vùng nền và ảnh.
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41 GVHD: PGS. TS. Ngô Quốc Tạo
Hình 30: Ví dụ một bolck chuyển sang dạng bề mặt trong không gian
3D
Hình 31: Ví dụ chuyển ảnh chữ "c" sang dạng bề mặt trong không gian 3D
II.3.4. Phân tích sử dụng giả pháp Fractal Signature
Chi tiết thuật toán FS[1]
Đầu vào: Ảnh đa cấp xám của một trang tài liệu F;
Đầu ra: Anh đã khoanh vùng vùng văn bản và đồ họa;
Thuật toán:
Trƣớc tiên ta chia F thành n vùng không trùng nhau có kích thƣớc NxN gọi là
Rk(x,y), trong đó k là vùng NxN thứ k của tài liệu và k=1,2,…,n
Bƣớc 1:
For x=1 to Xmax do
For y=1 to Ymax do
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42 GVHD: PGS. TS. Ngô Quốc Tạo
Tính hàm mức xám gk(x,y) cho F;
Bƣớc 2:
For x=1 to Xmax do
For y=1 to Ymax do
Bƣớc 2.1: Khởi tạo cho δ = 0 khi đó lớp trên và lớp dƣới
của Blanket đƣợc chọn bằng với hàm mức xám gk(x,y) nhƣ
sau:
;
Bƣớc 2.2 Cho δ = δ1
a) đƣợc tính theo công thức sau:
b) đƣợc tính theo công thức sau:
c) Thể tích của Blanket đƣợc tính theo công thức sau:
Bƣớc 2.3: Cho δ = δ2
a) đƣợc tính theo công thức sau:
b) đƣợc tính theo công thức sau:
c) Thể tích của Blanket đƣợc tính theo công thức sau:
Bƣớc 3:
Tính các FS cho mỗi Rk(x,y) là theo công thức sau:
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
43 GVHD: PGS. TS. Ngô Quốc Tạo
Bƣớc 4:
Tổ hợp các FS thành FS của tài liệu theo công thức sau:
Nhận xét: Dễ nhận thấy với một ảnh đầu vào có cùng kích thƣớc thì tốc độ thực hiện
thuật toán là không đổi và chỉ phải duyệt qua mỗi điểm ảnh một lần duy nhất.
Ví dụ:
Giả thiết ta có gk(x,y) là
Cho δ = 1, ta có:
Thu đƣợc kết quả là:
Ta có:
Thu đƣợc kết quả là:
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44 GVHD: PGS. TS. Ngô Quốc Tạo
Ví dụ về một kết quả áp dụng thuật toán này:
Hình 32: (a) Ảnh một tài liệu gốc, (b) kết quả sau khi áp dụng FS
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45 GVHD: PGS. TS. Ngô Quốc Tạo
II.4. Kết luận
Sau chƣơng 2 này, ta đã có đƣợc các module và công việc của mỗi module trong
hệ thống demo phân tích trang tài liệu sẽ đƣợc cài đặt, từ những cơ sở phân tích ở trên sẽ
làm cơ sở để triển khai cài đặt trên máy tính cho thuật toán Fractal Signature và các chức
năng của chƣơng trình demo.
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46 GVHD: PGS. TS. Ngô Quốc Tạo
Chƣơng III: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM
Chƣơng này tập trung vào việc xây dựng và cài đặt các chức năng của chƣơng
trình demo với mục đích chính là phân tich đƣa ra cấu trúc vật lý của ảnh đầu vào là ảnh
đa cấp xám có độ phức tạp cao sử dụng thuật toán Fractal Signature. Đồng thời triên khai
cả thuật toán Top-down nhằm so sánh vơi thuật toán Fractal Signature
III.1. Yêu cầu hệ thống
Theo nhƣ phần lựa chọn giải pháp (II.2) thì đề tài tập trung vào việc triển khai
phƣơng pháp phân tích Fractal Signature và để có thể so sánh hiệu quả của FS thì chƣơng
trình thử nghiệm sẽ cài đặt thêm phƣơng pháp Top-down. Với mục đích này thì những
yêu cầu cho chƣơng trình nhƣ sau:
- Cho phép chọn phân tích ảnh theo thuật toán FS hoặc Top-down
- Cho phép tùy chọn ảnh đa cấp xám đầu vào dạng *.jpg
- Ảnh kết quả đã khoanh vùng các vùng văn bản hoặc đồ họa
- Tự động lọc và làm trơn nhiễu ảnh đầu vào trƣớc khi phân tích
- Chƣơng trình đƣợc cài đặt trên MatLab v7.0
III.2. Thiết kế chƣơng trình
III.2.1. Cấu trúc dữ liệu
- Cấu trúc vùng nhớ lƣu ảnh:
Ảnh đầu vào là ảnh đa cấp xám dạng *.jpg, sau khi đƣợc tải vào bộ nhớ sẽ đƣợc
giải mã và chuyển sang dạng ma trận điểm ảnh (quá trình này đƣợc thực hiện tự động khi
sử dụng hàm đọc ảnh trong matlab).
*.jpg
Gray Image
Lọc và làm
trơn nhiễu
Phân tích cấu
trúc vật lý
Ảnh ra đã
khoanh
vùng vă bản
và đồ họa
Tùy chọn FS
hoặc Top-down
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47 GVHD: PGS. TS. Ngô Quốc Tạo
Nhƣ vậy về mặt logic thì cấu trúc vùng nhớ sử dụng để lƣu ảnh là một mảng hai
chiều Im x n có kích thƣớc (m x n) phần tử.
Image = { I[i,j], i = 1..m, j = 1..n}
Trong đó I[i,j] là giá trị độ xám của điểm ảnh tƣơng ứng với tọa độ (i,j) trong ảnh
Thông thƣờng với ảnh đa cấp xám thì giá trị độ xám của mỗi điểm ảnh nằm trong
khoảng [0..255], nhƣ vậy kích thƣớc tối thiểu cho mỗi I[i,j] là 1Byte.
Chƣơng trình sẽ sử dụng mảng có thuộc tính nhƣ sau để lƣu trữ ảnh:
- Mảng I hai chiều với I[i,j] kiểu Byte (Max(I[i,j])=255)
- Kích thƣớc của mảng là m x n với m là chiều cao của ảnh, n chiều rộng của ảnh và
m, n kiểu Double (max(m/n)=232)
36 26 80 60 90 15 14 53 81 65 16 49
85 65 73 18 8 68 71 27 28 35 93 39
7 12 96 1 29 10 35 64 85 22 68 91
69 33 44 52 63 80 30 89 18 93 60 58
97 98 89 11 40 17 15 8 15 22 42 98
34 92 87 79 72 44 35 39 39 24 86 50
56 45 87 92 19 27 46 53 11 94 52 54
83 71 98 7 72 64 27 41 58 31 26 60
37 18 4 56 4 91 86 79 11 73 14 96
19 7 13 75 2 21 50 38 57 91 19 3
22 50 65 97 81 50 30 7 76 86 87 74
82 18 81 81 60 21 88 59 92 8 66 49
71 95 72 76 61 26 33 55 25 80 91 72
Ảnh
Ma trận điểm ảnh
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48 GVHD: PGS. TS. Ngô Quốc Tạo
- Cấu trúc lƣu trữ lƣợc đồ xám (kết quả của các phép chiếu nghiêng).
Phép chiếu nghiêng là đi tính tổng các điểm đen theo phƣơng vuông góc với
hƣớng chiếu. Kết quả của phép chiếu sẽ đƣợc lƣu trữ vào một mảng một chiều H có kích
thƣớc d phần tử. Trong dó H[i] (với i = [1..d]) là tổng số điểm đen của cột thứ i theo
phƣơng chiếu.
III.2.2. Module chuẩn hóa ảnh
Thuật toán FS tính giá trị FS cho từng khối Block trong ảnh, vì thế cần phải chia
ảnh thành các block có kích thƣớc bằng nhau trƣớc khi thực hiện thuật toán. Giả thiết
kích thƣớc của mỗi Block là (k x q), để việc tính FS cho các block không gặp trƣờng hợp
đặc biệt (Kích thƣớc ảnh không bằng nguyên lần của Block) ta sẽ nối thêm vào chiều
ngang và dọc của ảnh vùng nền đủ để sao cho kích thƣớc ảnh mới bằng một số nguyên
lần của Block.
.. .. .. .. .. ..
1 Byte
m (Double)
n (Double)
Ảnh I
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49 GVHD: PGS. TS. Ngô Quốc Tạo
Giải thuật:
Input:
- Ảnh I có kích thƣớc m x n
- Block có kích thƣớc k x q (k,q<m,n)
Output: Ảnh I có kích thƣớc m’ x n’ sao cho m’ = i*k và n’ = j*q (với i,j € N)
Thuật toán:
B1: Tính m’
Nếu (m/k = nguyên (m/k)) thì m’=m;
Trái lại m’ = nguyên (m/k))*k + k;
B2: Tính n’
Nếu (n/q = nguyên (n/q)) thì n’=n;
Trái lại n’ = nguyên (n/q))*q + q;
Mã nguồn
(Mã nguồn cho module chuẩn hóa cài đặt trong Matlab)
Ảnh gốc
Phần dƣ không đủ 1 block
Phần nền bổ xung
cho đủ 1 block
Block
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50 GVHD: PGS. TS. Ngô Quốc Tạo
% chuan hoa kich thuoc anh the nguyen lan cua NxN
%chuan chieu cao anh
if (chieucao/N)>round(chieucao/N)
chieucao=round(chieucao/N)*N+N;
else
chieucao=round(chieucao/N)*N;
end
%chuan chieu rong anh
if (chieurong/N)>round(chieurong/N)
chieurong=round(chieurong/N)*N+N;
else
chieurong=round(chieurong/N)*N;
end
%%%%%%%%%%%%%%%%%%%%
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51 GVHD: PGS. TS. Ngô Quốc Tạo
III.2.3. Module giao diện chính
Giao diện chính đƣợc thiết kế đơn giản với một số chức năng chính nhƣ sau:
Vùng hiển thị ảnh gốc Vùng hiển thị ảnh kết quả
Chọn ảnh mới
Chọn phân tích
kiểu Top-down
Chọn phân tích
kiểu FS
Mô phỏng FS
Hình 33: Giao diện chính
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52 GVHD: PGS. TS. Ngô Quốc Tạo
Mã nguồn:
Một số mã nguồn sự kiện cho các Button chính trên giao diện chính (cài dặt trong
Matlab)
- Button chọn ảnh:
- Button Top-Down
- Button Fractal Signature
III.2.4. Module phân tích Top-down (TD)
Thuật toán phân tích TD đƣợc thiết kế theo kiểu đệ quy, và cần tham số chiều cao
của font chữ. Để tính chiều cao của font chữ có 2 giải pháp
- Một là cho phép ngƣời sử dụng nhập vào.
- Hai là tự động dò theo thuật toán sau:
B1: Tính lƣợc đồ chiếu nghiên theo phƣớc thẳng đứng
B2: Tìm độ rộng xuất hiện nhiều nhất của các “cột” trong lƣợc đồ chiếu nghiêng, đây xấp
xỉ bằng chiều cao của font chữ.
function pushbutton3_Callback(hObject, eventdata, handles)
imshow('anhmau\running.jpg')
pause(0.5)
filename=get(handles.path,'string');
Fsign % Gọi chương trình con Fractal signature
clear all
function pushbutton2_Callback(hObject, eventdata, handles)
imshow('anhmau\running.jpg')
pause(0.5)
filename=get(handles.path,'string');
topdown % Gọi chương trình con TOPDOWN
clear all
function pushbutton1_Callback(hObject, eventdata, handles)
% Hop thoai chon uong dan?
[fname,pname] = uigetfile('*.jpg','Hay chon mot anh da cap xam');
if fname~=0 % da chon 1 file
set(handles.path,'String',[pname,fname]); % hien thi duong dan cua file anh
axes(handles.anhgoc);
imshow([pname,fname]);
axes(handles.anhdich);
end
Luận văn tốt nghiệp cao học Học viên: Nguyễn Văn Huy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53 GVHD: PGS. TS. Ngô Quốc Tạo
Trong đề tài này việc xác định chiều cao đƣợc dò tự động theo phƣơng pháp trên.
Giải thuật Top-Down
Input: Ảnh đa cấp xám I kích thƣớc m x n, chiều cao font chữ k
Output: Ảnh đã đƣợc phân đoạn văn bản và đồ họa.
Thuật toán:
Proceduce Topdown (I,x,y,m,n,k) // I là ảnh đầu vào, m và n là kích thƣớc vùng ảnh
// k chiều cao font chữ
// x,y là tọa độ hàng và cột
// của điểm ảnh góc trái trên cùng
Begin
B1: Tính lƣợc đồ chiếu đứng cho ảnh I đƣợc kết quả là mảng A gồm m phần tử
B2: Xác định các “cột” trên lƣợc đồ A
For (mỗi cột(i) trong lƣợc đồ A) do
IF độ rộng cột(i) ≈ k then
Khoanh vùng trên ảnh tại vị trí của cột(i) chiều dài n là vùng văn bản;
Else
IF độ rộng côt(i) > k then
Thuật toán phân tích TD
đƣợc thiết kế theo kiểu đệ
quy, và cần tham số chièu
cao của font chữ.
Thuật toán phân tích TD
đƣợc thiết kế theo kiểu đệ
quy, và cần tham số chièu
cao của font chữ.
~k
~k
~k
~y
Thành phầ
Các file đính kèm theo tài liệu này:
- Nghiên cứu hệ thống nhận dạng chữ viết, cùng với một số phần mềm nhận dạng tiêu biểu hiện nay.pdf