Tinh lọc trung vị trong xử lý ảnh

We’ve updated our privacy policy so that we are compliant with changing global privacy regulations and to provide you with insight into the limited ways in which we use your data.

You can read the details below. By accepting, you agree to the updated privacy policy.

Thank you!

View updated privacy policy

We've encountered a problem, please try again.

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

• Bộ lọc trung vị được dùng phổ biến, bởi vì một số loại nhiễu nhất định,

nó có thể lọc nhiễu rất tốt với độ mờ thấp so với bộ lọc tuyến tính cùng

kích thước.

Ý tưởng: Ý tưởng chính của thuật toán lọc trung vị như sau: Sử dụng

một cửa dổ lọc (ma trận 3 x 3) quét qua lần lượt từng điểm ảnh của ảnh

đầu vào input. Tại vị trí mỗi điểm ảnh lấy giá trị của các điểm ảnh tương

ứng trong vùng 3 x 3 của ảnh gốc “lấp” vào ma trận lọc. Sau đó sắp xếp

điểm ảnh nằm chính giữa (trung vị) của dãy giá trị điểm ảnh đã được sắp

xếp ở trên cho giá trị điểm ảnh đang xét của ảnh đầu ra input.

Các bước thực hiện:

• Trung vị E của một tập hợp là giá trị mà một nữa các giá trị trong tập

hợp nhỏ hơn hoặc bằng E, một nửa các giá trị trong tập hợp lớn hơn

hoặc bằng E.

• Chức năng cơ bản của bộ lọc trung vị là thiết lập trị của các điểm với

các mức xám khác nhau thành giá trị có ve như gần giống với giá trị của

điểm lân cận.

• Khi áp dụng bộ lọc trung vị có kích thước mxn, các điểm ảnh à có số

lượng các điểm lân cận cùng mức xám với nó nhỏ hơn m*n/2 sẽ không

bị ảnh hưởng, điều này khắc phục được nhược điểm làm mờ ảnh khi áp

dụng bộ lọc trung bình.

VD:

Có ma trận 3x3 như sau:

50

65

52

63

255

58

61

60

57

Các giá trị sau khi sắp xếp

50

52

57

58

60

61

63

65

255

20

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Kết quả là giá trị 255 sẽ được thay thế bằng giá trị 60.

• Hạn chế của lọc trung vị là chậm do mỗi lần tính giá trị mói phải thực hiện sắp

xếp lại nxn lần.

• Tính chất của lọc trung vị:

- Có lợi cho việc loại bỏ các điểm ảnh hay các hàng mà vẫn đảm bảo

an toàn độ phân giải

- Hiệu quả giảm khi số điểm trong ma trận lớn hay bằng một nửa số

điểm trong ma trận. Điều này dễ giải thích vì trung vị là (N w + 1)/2

giá trị lớn nhất nếu Nw lẻ. Lọc trung vị trường hợp hai chiều coi như

lọc trung vị tách được theo từng chiều.

• Một số bộ lọc thường dùng:

(1,

1,

1)

(1,

(1,

8,

1)

(2,

(1,

1,

1)

(1,

Kích thước của bộ lọc (2N – 1, 2M - 1), ví dụ 3x3, 5x5…

2,

4,

2,

1)

2)

1)

Đặt tâm của bộ lọc lên điểm ảnh cần xét, không xét những điểm nằm

trên biên vùng ảnh.

2.2.

Quá trình xử lý ảnh văn bản

2.2.1. Nhị phân hóa ảnh văn bản

Trong thực tế, ảnh văn bản mà chúng ta nhận vào ban đầu để xử lý là ảnh màu.

Vì vậy để có thể thực hiện được quá trình phân tích và nhận dạng, chúng ta cần phải

chuyển chúng thành ảnh nhị phân trong đó mỗi điểm ảnh (pixel) được biểu diễn bởi

một trong 2 giá trị là 0 hoặc 255. Đầu tiên, ảnh màu nhận vào sẽ được chuyển thành

ảnh 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

với một ngưỡng cho trước để quyết định điểm đó sẽ là 0 hoặc 255, giá trị 0 biểu diễn

cho màu đen và 255 biểu diễn cho màu trắng.

21

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Giới thiệu phương pháp OTSU:

Otsu là tên một nhà nghiên cứu người Nhật đã nghĩ ra ý tưởng cho việc tính

ngưỡng T một cách tự động (adaptive) dựa vào giá trị điểm ảnh của ảnh đầu vào

nhằm thay thế cho việc sử dụng ngưỡng cố định (fixed hay const). 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:

Bước 1: Chọn một giá trị khởi tạo cho T (nên 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).

Bước 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.

Bước 3: Tính trung bình (Average hay Mean) m1 và m2 của các điểm ảnh

thuộc G1 và G2.

Bước 4: Tính lại T dựa vào m1 và m2: T = (m1 + m2) / 2

Bước 5: 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 deltaT). 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ý. Trong trường hợp này T

được tính ở 4 sẽ có phép sai số là 1 / 2 * (giá trị đơn vị của điểm ảnh).

2.2.2. Tách khối văn bản

a)

Đặt vấn đề

Phân tích bố cục văn bản là một bước tiền xử lý đặc biệt quan trọng các hệ

thống OCR. Đây là quá trình chia nhỏ ảnh văn bản thành ảnh các khối thuần

nhất, có nghĩa là, các khối này chỉ chứa một loại thông tin, hoặc là text, hoặc là

22

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

ảnh, hoặc là bảng…Trong nhiều trường hợp, độ chính xác của quá trình phân

tích bố cục văn bản làm ảnh hưởng rất nhiều đến độ chính xác của hệ thống

OCR. Trong phạm vi đề tài này, tôi ưu tiên cho việc tách khối trong văn bản

công văn tiếng Việt. Các khối này được phân chia theo một số chuẩn cơ bản của

một văn bản công văn thông thường được sử dụng trong các cơ quan hành chính

tại Việt Nam.

Trên thực tế đã có nhiều phương pháp được đề xuất để phân tích bố cục

của một ảnh văn bản bất kì. Tuy nhiên, trong phạm vi của đồ án này, tôi chỉ

quan tâm đến việc phân tích bố cục của văn bản công văn hành chính tại Việt

Nam. Vì vậy, sau đây tôi đề nghị việc sử dụng một phương pháp đơn giản dựa

trên phương pháp của G. Nagy, S. Seth, and M. Viswanathan đồng thời được cải

tiến để phù hợp hơn đối với các văn bản hành chính tại nước ta.

Sau đây là một bố cục thường gặp của một văn bản công văn hành chính

tại nước ta. Thông thường nó bao gồm 8 phần chính :

b)

• Cơ quan gửi

• Quốc hiệu

• Ngày tháng năm lập công văn

• Tên công văn

• Kính gửi

• Nội dung công văn

• Cơ quan nhận

• Kí tên đóng dấu

Giới thiệu một số phương pháp tách khối hiện có

Hiện nay có hai hướng tiếp cận chính trong quá trình tách khối văn bản là:

thuật toán top-down , thuật toán này bắt đầu thực hiện từ toàn bộ văn bản sẽ tìm

ra các khối, sau đó dựa trên các khối để tìm ra dòng, từ rồi ký tự. Cách tiếp cận

thứ hai là bottom-up, ngược lại với cách tiếp cận đầu tiên, cách này đi từ các

23

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

thành phần liên thông nhỏ để tìm ra các ký tự, rồi tìm đến các từ sau đó là các

dòng, từ các dòng này sẽ tìm được các khối.

Mô tả phương pháp

Phương pháp tách khối được tóm tắt như sau: Bước thứ nhất tiến hành tách

khối theo phương ngang trong đó có sử dụng một số tham số đã được xác định

tại phần ước lượng góc nghiêng ảnh văn bản được trình bày ở trên. Bước thứ hai

chúng tôi tiến hành tách khối theo chiếu dọc bằng cách dựa vào các khối đã tách

theo chiếu ngang. Bước tiếp theo chúng tôi sẽ tiến hành chiếu ngang một lần

nữa trên các khối đã xác định được ở bước thứ hai. Sau khi đã tách được các

khối thì công đoạn lọc bỏ các khối có kích thước không phù hợp được tiến hành

và cho ra kết quả cuối cùng.

Tách theo chiều ngang:

Trên văn bản đã được lọc nhiễu, tiến hành duyệt theo chiều từ trên xuống

dưới từ trái qua phải, qua mỗi dòng pixel của văn bản ta sẽ cộng dồn số pixel

đen trên từng dòng. Số pixel đen trên từng dòng đó được biểu diễn thành một đồ

thị với trục nằm dọc là chiều cao của văn bản còn trục nằm ngang là số pixel

đen đếm được trên một dòng. Đồ thị vừa tìm được chính là biểu đồ biểu diễn sự

phân bố của các khối văn bản.

Tách theo chiều dọc

Trên mỗi khối ngang xác định ở bước trên ta sẽ duyệt chúng theo chiều

dọc. Ứng với mỗi cột ta sẽ đếm số pixel đen. Số lượng trên các cột sẽ được biểu

diễn thành một đồ thị, gọi là lược đồ chiếu dọc. Lược đồ này có trục Oy là số

lượng pixel đen trên mỗi cột và trục Ox là chiều rộng của ảnh văn bản.

Tách khối theo chiều ngang lần 2

24

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Do cấu trúc văn bản không thuần tuý mỗi khối chỉ có một khối cùng nằm

trên một hàng ngang nên sẽ có trường hợp sau khi tách khối, hai hoặc nhiều

khối bị gộp thành một (như hình 2.7(a)). Để khắc phục tình trạng trên, thông

thường người ta sẽ tiến hành tách khối cho đến khi không tách được nữa thì thôi,

nhưng cấu trúc của một văn bản công văn là khá đơn giản nên trong đề tài này

chỉ tìm hiều việc tách khối theo chiều ngang thêm một lần nữa thì tình trạng này

sẽ được khắc phục.

Sau khi thực hiện việc tìm và tách các khối, ta được một tập hợp các khối

văn bản riêng biệt. Tuy nhiên trong văn bản luôn có những khối nhiễu đặc thù

(như các kim bấm, các vết mực lem…) nên chúng cần được loại bỏ.

Khi quan sát ảnh quét ta dễ nhận ra, mỗi văn bản sẽ được chia thành các

đoạn khác nhau. Mỗi đoạn này có những đặc trưng khá tương đồng về cỡ chữ,

font chữ. Chính sự tương đồng đó sẽ tạo ra điều kiện thuận lợi, giảm bớt sự

phức tạp trong giai đoạn xử lý phía sau.

25

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Hình 2-7: Ví dụ mình họa cắt đoạn

Để tách thành các đoạn (hay các vùng ảnh) chúng ta sử dụng 2 đặc trưng:

Khoảng cách trắng giữa các đoạn sẽ lớn hơn khoảng cách trắng giữa các dòng,

lùi đầu dòng của dòng kế tiếp

2.2.3. Tách dòng văn bản

a)

Đặt vấn đề

Thuật toán xác định bố cục văn bản thực chất là tìm cách chia ảnh văn bản

ra thành nhiều khối mà mỗi khối sẽ đặc trưng cho một vùng văn bản. Sau đó

mỗi khối này sẽ được chia thành nhiều dòng, rồi mỗi dòng có thể được chia

thành một hoặc nhiều từ, tương tự mỗi từ sẽ được chia thành nhiều ký tự.

b) Giới thiệu phương pháp tách dòng dựa vào các đường kẻ ngang

Ta nhận thấy, với mỗi dòng văn bản chúng ta có thể chia làm 3 vùng dựa

vào bốn đường cơ bản là: Top Line, Bottom Line, Base Line.

Cha mẹ

26

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Hình 2-8: Các đường đặc trưng của một dòng văn bản

Bước 1: Ý tưởng chính của phương pháp này là dựa trên nhận xét các

điểm đen tập trung chủ yếu trong khoảng đường Base Line và X Line. Các

đường này có số điểm đen lớn hơn số điểm đen trung bình chính vì vậy chúng ta

có thể xác định được hai đường Base Line và X Line.

Bước 2: Sau khi xác định được Base Line và X Line chúng ta có thể tiến

hành xác định miền liên thông.

Bước 3: Tiếp theo là ta duyệt tất cả các miền liên thông. Nếu miền liên

thông nào có diện tích về dòng nào nhiều hơn thì thuộc về dòng đó.

Nhận xét: Phương pháp này sẽ gây ra lỗi nếu có xuất hiện các dòng ngắn.

Khi đó vì số ký tự trong dòng này quá ít, nên trong khoảng từ Base Line đến X

Line, só điểm đen trên mỗi đường vẫn nhỏ hơn giá trị trung bình. Có thể khắc

phục lỗi này bằng các gọi về đệ quy với các vùng chứa các dòng ngắn.

Phương pháp này cũng sẽ gây lỗi nếu gặp dòng toàn chữ in hoa (không tồn

tại 4 đường như trên) và khó áp dụng với văn bản tiếng Việt vì tiếng Việt có

thêm các dấu nên nhiều trường hợp giá trị X Line tìm được lại chính là Top

Line, kết quả sẽ ko chính xác nữa. Sau khi xác định được X Line, Base Line

cũng khó phân tách các dòng nếu chúng khá liền nhau hoặc dính vào nhau.

c)

Tách dòng dựa vào thành phần liên thông

Ý tưởng của phương pháp này là tìm tất cả các thành phần liên thông trong

ảnh và sắp xếp theo thứ tự tăng dần của tung độ của điểm trên nhất. Sau đó dựa

vào sự tương quan giữa tung độ của điểm trên nhất, tung độ của điểm dưới nhất

của mỗi thành phần liên thông để gộp các thành phần này vào một dòng văn

bản.

d)

Nhận xét:

27

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Ưu điểm của phương pháp này ta có thể tách được các dòng mà giữa

chúng có phần giao với nhau (không dính) và đường cắt giữa 2 dòng sẽ được đi

theo một đường cong, chứ không phải là một đường thẳng như những cách

khác.

Nhược điểm là phương pháp này tương đối chậm, do thời gian tính toán

thành phần liên thông, và phải duyệt lại thành phần liên thông nhiều lần.

e)

Tách ảnh dòng dựa vào các pixel đen của ảnh

• Thuật toán:

Bắt đầu từ điểm ảnh (x, y) đầu tiên của file ảnh (0, 0), gán số dòng đang

xét lines = 0;

Xác định giới hạn trên của dòng: Quét hết chiều rộng của ảnh, trên cùng

một giá trị y (chạy x <= chiều rộng ảnh, giữ nguyên y).

- Nếu gặp một pixel đen thì ghi nhận chính là tọa độ giới hạn trên của

dòng (top _ line). Dừng duyệt x.

- Nếu không, tiếp tục duyệt.

- Nếu khi quét hết chiều rộng của ảnh vấn không tìm thấy giá trị điểm

màu đen thì reset lại x = 0 và lại tiếp tục duyệt đến dòng tiếp theo

(tăng y = y + 1).

Xác định giới hạn dưới của dòng

- Bắt đầu duyệt từ giới hạn trên (đỉnh) vừa tìm thấy của dòng (0,

top_line).

- Tương tự như xác định giới hạn trên, ta duyệt hết chiều rộng của ảnh

trên cùng một giá trị y.

- Nếu duyệt hết dòng mà không tìm thấy ký tự pixel đen nào thì ghi

nhận y -1 là giới hạn dưới của dòng (bottom_line). Dừng duyệt. Tăng

số dòng lên (lines++).

28

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

- Nếu chưa tìm thấy bottom_line, tiếp tục duyệt đến dòng tiếp theo

(tăng y, reset x = 0).

Bắt đầu từ giới hạn dưới y (bottom_line) vừa tìm thấy sau cùng, lặp lại

các bước a, b để xác định giới hạn của các dòng tiếp theo, cho đến khi

duyệt hết chiều cao của ảnh thì dừng, quá trình xác định dòng ký tự hoàn

tất.

29

Tìm hiểu kỹ thuật xử lý ảnh và xây dựng ứng dụng tách ảnh ký tự từ ảnh văn bản

Hình 2- 9: Tách dòng văn bản

f)

Tách dòng dựa vào khoảng trắng giữa các dòng

Tách dòng dựa vào khoảng trắng và kết hợp Histogram ngang.

Ý tưởng của phương pháp này là dựa vào khoảng trắng giữa các dòng

cùng với nhau.. Khoảng trắng giữa các dòng chính là nơi ta đặt nhát cắt

các dòng với nhau.

Phương pháp này có ưu điểm là tốc độ rất nhanh. Nhưng nhược điểm

của phương pháp này là do sự xuất hiện của nhiễu. Nhiễu có thể làm mất

khoảng trắng giữa các dòng, dẫn đến hiện tượng tách sai dòng (Một dòng

thành hai hoặc ba dòng). Để giải quyết được nhược điểm của phương pháp

này ta kết hợp với Histogram ngang cho các trường hợp nghi ngờ tách hai

hay ba dòng. Ta tìm Histogram ngang của văn bản và xác định một

ngưỡng threshold nào đó, đối với các đường mà trên đó số điểm đen <

threshold thì sẽ được chọn làm phân cách giữa các dòng.

Các bước thực hiện:

Bước 1: Xác định khoảng trắng giữa các dòng và chọn làm vạch phân

cách hay là bị trí cắt các dòng. Quá trình được lặp lại cho đến khi nào hoàn

tất công việc tách dòng trong đoạn. Chiều cao của mỗi dòng phải lớn hơn

minHeightLine (tránh trường hợp tách nhiều dấu thành một dòng).

Bước 2: Xác định độ cao trung bình của các dòng trong một đoạn

(avgHeightLine). Thực nghiệm ta thấy ValueHistogram được tính:

valueHistogram = avgHeightLine x 1,2

Bước 3: Kiểm tra độ cao của các dòng đã tách. Nếu dòng nào có độ cao

lớn hơn valueHistogram thì thực hiện bước 4, 5.

30