OCR (Optical Character Recognition)

Để tôi thử miêu tả một cách đơn giản phiên bản của thuật toán OCR. Thực sự, tất cả các triển khai của OCR “real” đều dựa trên phiên bản được đơn giản hóa này, và chắc chắn rằng một số bước sẽ phức tạp hơn một chút và cũng một số bước nhỏ khác được thêm vào.

Image result for ocr

Bước 1:

Phát hiện “direction” của văn bản. Một hình ảnh được scan không bao giờ được căn lề hoàn bảo 100%, vì thế hướng (direction) của văn bản không phải theo chiều ngang một cách chính xác, do đó bước đầu tiên này là bạn có thể hình dung là xoay nhẹ hình ảnh được scan để các dòng văn bản trở nên hoàn hảo theo chiều ngang

Bước 2:

Noise reduction: Xóa bỏ là điểm mờ, làm mượt ảnh

Despeckle image.

Bước 3

Tất nhiên định dạng pixel ở đây vẫn là đen/trắng/xám thuộc thang grayscale. Nếu không phải định dạng đen trắng (binary image) thì phải có một bước gọi là Binarisation.

Bước 4: Binarisation

Bước này chuyển ảnh từ định dạng RGB (8 bit) sang ảnh nhị phân (binary image – chỉ có 2 màu trắng và đen). Tại sao lại phải chuyển từ ảnh có mã màu 8bit sang ảnh nhị phân thì chúng ta cần đi qua một chút về cách hình ảnh được hiển thị. Hình ảnh có thể được hiển thị dưới rất nhiều cách nhưng có lẽ cách phổ biến nhất là lưới các ô vuông nhỏ gọi là pixel. Những bức ảnh đơn giản nhất chỉ có màu đen và màu trắng và chúng ta có thể nghĩ rằng mỗi pixel được biểu hiện bằng màu đen ( số 0) và màu trắng (số 1).

  • Hình ảnh này có thể lưu trữ bằng một chuỗi 36 bit: 111111101101111111101101100001111111 . Để có được hình ảnh trên từ chuỗi này, chúng ta sẽ phải bổ sung thêm thông tin như chiều của ảnh ( 6 hàng của 6 pixels thay vì 4 hàng của 9 pixels). Và đó chỉ là hình ảnh đen trắng. Vậy làm sao để biểu diễn một hình ảnh màu xám? Để làm được điều đó thì mỗi pixel phải lưu trữ được nhiều hơn 1 bit. Và với 2 bit dung lượng mỗi pixel thì có thể biễu diễn được 4 màu:
  • 00 đen
  • 01 xám tối
  • 10 xám nhạt
  • 11 trắng
2-bit grayscale circle

Và 1 pixel 8 bit(RGB) theo cách tương tự có thể biểu diễn 2^8^3 cách khác nhau (1 pixel chứa 3 sắc số green red blue, mỗi sắc tố có 2^8 cách biễu diễn khác nhau). Nhiệm vụ của bước này như là một cách đơn giản để tách text ra khỏi nền.

Bước 5:

Loại bỏ hàng, xóa những hàng và hộp mà không phải kí tự (non-glyph boxes and lines)

Bước 6:

Phân tích layout: Xác định các đoạn văn, cột, chú thích…điều này đặc biệt quan trọng trong layout nhiều cột và bảng, xác định các dòng chữ và phân tách ra thành các ký tự đơn.

Bước 7:

Sau khi ảnh đưa vào chỉ còn duy nhất những kí tự đơn thì bước tiếp theo là nhận dạng ký tự (Charater recognition). Bước này thì những tí tự sẽ được phân tách ra thành các “features” như đoạn thẳng, vòng lặp kín hay đoạn thẳng giao nhau …để so sánh với các ký tự nguyên mẫu (glyph prototypes), hoặc có thể so sánh khoảng cách giữa các phần nhỏ của một ký tự để xác định đó có phải là ký tự ở trong bảng chữ cái hay không…

Kernel Machine.svg

Bước 8: Xử lý hậu kỳ

Tất cả các bước trên chưa đủ để hoàn toàn đảm bảo độ chính xác nếu bước 7 chưa trả về tất cả những ký tự đơn hợp lệ (Tức là trả về một chuỗi xác xuất) . Độ chính xác OCR có thể được tăng lên nếu ouput bị ràng buộc bởi một bộ từ điển – danh sách những từ được cho phép xuất hiện trong văn bản. Chúng ta gọi đó là language model, và language model này chỉ áp dụng cho một đối tượng ngôn ngữ cụ thể (Bạn không thể sử dụng mô hình ngôn ngữ của tiếng việt cho tiếng anh). Đây là một bước mà nếu thiếu thì bạn sẽ tạo ra rất nhiều từ vô nghĩa (Tùy thuộc vào chất lượng của ảnh đầu vào), hihi. Vậy Language Model là cái con chị gì ??=))

A statistical language model is a probability distribution over sequences of words (Wikipedia)

Mô hình này cho biết một câu có “hợp lí” với ngôn ngữ xác định hay không, hoặc thêm một từ đằng sau một từ có đúng ngữ cảnh và ăn khớp với các từ trước đó hay không? Tỉ như Con chị … thì xác suất từ mày hay từ xuất hiện tiếp theo sau sẽ cao hơn xác suất của các từ khác.

Và google có sẵn cho chúng ta công cụ N-gram Viewer (N-gram: một dãy liên tiếp của n items của một văn bản hay lời nói):

Công cụ này có data của tất cả mọi cuốn sách được số hóa bởi Google Books từ những năm 1800. Chúng ta có thể thấy đường biểu diễn màu xanh – Albert Einstein xuất hiện lần đầu tiên trong sách năm 1915, năm ông đưa ra thuyết tương đối tổng quát.

Cùng thử một thí nghiệm khác, đó là 2 từ hello và hella. Chúng ta thấy rằng xác suất xuất hiện của từ hello cao hơn hẳn, từ hella gần như tiệm cận 0, vậy điều này được sảy ra như thế nào?

enter image description here

Chương trình N-gram sẽ phân tích chữ hello thành = {‘h’, ‘e’, ‘l’, ‘l’, ‘o’} với unigrams, {‘he’, ‘ll’, ‘o’} với bigrams và tương tự với N-gram khác. Qua đó sẽ có được xác suất phổ biến nhất của của các kí tự hoặc cụm ký tự đứng liên tiếp nhau và thực hiện việc dự đoán như một vị thần 😀 Superpower tool ! Ngôn ngữ học và xử lí ngôn ngữ tự nhiên (NLP) thực sự rất hay và thú vị.

Bonus nguyên nhân bài viết:

Reference: