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 |