GIỚI THIỆU
Nhận dạng ký tự, đặc biệt là ký tự viết tay, là một bài toán có nhiều ứng dụng thực tiễn Công nghệ này cho phép máy tính tự động xử lý và nhận dạng các biểu mẫu, phiếu điều tra, giúp tiết kiệm thời gian, công sức và chi phí cho việc nhập dữ liệu.
Hiện nay, có nhiều phương pháp giải quyết bài toán nhận dạng ký tự, bao gồm nhận dạng dựa trên cấu trúc, logic mờ, thuật toán di truyền, mô hình xác suất thống kê và mạng nơ-ron Tuy nhiên, tất cả các hệ thống nhận dạng chữ viết đều phải trải qua các giai đoạn cơ bản trong sơ đồ tổng quát.
Hình 1 Sơ đồ tổng quát hệ thống nhận dạng chữ viết
Cơ sở lý thuyết giai đoạn tiền xử lý ảnh ký tự
Đánh nhãn thành phần liên thông
Khái niệm liên thông trong ký tự được hiểu là tập hợp các điểm ảnh liền kề nhau tạo thành ký tự Mục tiêu của thuật toán này là lọc ra các ký tự có trong hình ảnh.
1 Tách liên thông bằng kĩ thuật đệ quy: Để tách liên thông ta nghĩ ngay đến kỹ thuật đệ quy cấp 8 (tại mỗi bước chúng ta có tối đa 8 lựa chọn tiếp theo)
Quy ước: Điểm (x, y): cho biết giá trị điểm tại toạ độ (x, y)
=1 màu chữ =0 màu nền Height: Chiều cao ảnh Width: Chiều rộng ảnh
Ta có giải thuật như sau:
// Đưa tất cả các điểm liên thông với Điểm(x,y) vào liên thông t Procedure Chonvao((x,y) :điểm, t :liênthông)
If (Điểm(x, y)=1) AND (NOT đã_xét[x,y]) then Begin
Them_vao_lien_thong(t,(x, y)); Đã_xét[x, y] :=True ; For i :=x-1 to x+1 do For j:= y-1 to y+1 do
End ; // Ta có thủ tục tách liên thông đệ quy như sau : Procedure TáchLiênThôngĐQ(VAR LT: Danh_Sách_Liên_Thông) Begin
T:= t:=
For j:=1 to Height do For i:=1 to Width do đã_xét[i, j]:se;
If (Điểm(x, y)=1) AND( NOT Đã_xét[i, j]) then Begin
Thêm _liên_thông_vào_Danh_Sách(T, t) ; t := ; End ;
Thuật toán này chỉ minh họa bản chất của việc tách liên thông, nhưng không được lựa chọn để cài đặt do chi phí đệ quy quá cao và tốc độ thực hiện không hiệu quả.
2 Giải thuật cải tiến: Để gán nhãn cho thành phần liên thông ta có thể duyệt theo từng đường chạy.Kỹ thuật này gán cho mỗi thành phần liên thông của ảnh nhị phân một nhãn riêng biệt Nhãn thường là các số tự nhiên bắt đầu từ một đến tổng số các thành phần liên thông trong ảnh input
Giải thuật phát biểu như sau:
Quét ảnh từ trái sang phải và từ trên xuống dưới, bắt đầu từ dòng đầu tiên với pixel đen, mỗi đường chạy liên tục được gán một nhãn duy nhất Trong quá trình quét, với mỗi pixel đen ở dòng tiếp theo, các pixel lân cận từ dòng trước và pixel bên trái được xem xét Nếu có pixel lân cận đã được gán nhãn, pixel đen hiện tại sẽ nhận nhãn tương tự; nếu không, một nhãn mới chưa được sử dụng sẽ được chọn Thủ tục này tiếp tục cho đến khi hoàn thành toàn bộ ảnh Kết quả cuối cùng có thể tạo thành một thành phần liên thông, trong đó các pixel có thể mang các nhãn khác nhau do sự xem xét lân cận của các pixel đen.
Trong quá trình xử lý ảnh, pixel trong hình c có thể được gán nhãn riêng biệt cho lân cận trái và các lân cận trong dòng trước Việc xác định và ghi lại các tình huống này là rất quan trọng Sau khi quét ảnh, quá trình gán nhãn được hoàn tất bằng cách thống nhất các mâu thuẫn và gán lại các nhãn chưa được sử dụng Các hình biểu diễn sau đây sẽ minh họa cho quy trình này.
Hình a lân cận của “?” P= dòng trước; L=lân cận trái
* * * * * * * * * * * * * * * * * * * * Hình b Ảnh ban đầu Hình c Tiến trình gán nhãn
Hình d Sau khi quét đầy đủ Hình e Kết quả sau cùng
Chuẩn kích thước
Chuẩn kích thước ảnh kí tự về một kích thước cố định và phóng sát bốn biên của ảnh
Phóng ảnh là thực hiện phép biến đổi sau: f s (x , y) = f (x / s x , y / s y)
Điểm ảnh sau khi phóng được xác định bởi tọa độ (x, y), trong đó sx và sy là tỷ lệ phóng theo trục x và y tương ứng Giá trị điểm ảnh kết quả ứng với tọa độ (x, y) được ký hiệu là fx(x, y).
Sau khi phóng to ảnh, hình ảnh có thể xuất hiện tình trạng rời rạc và răng cưa ở các biên Để khắc phục vấn đề này, chúng ta cần thực hiện một số xử lý bằng phương pháp đóng morphology.
Lấp khoảng trống ảnh bằng phép đóng morphology
Giả sử A và B là hai tập trong không gian Z2 , a A thì a = (a1 , a2) Phép dịch chuyển của tập A đối với x = (x1, x2) ký hiệu(A)x , được định nghĩa
(A)x = {c|c = a + x , với a A } Phép phản chiếu của tập B, ký hiệu B*, được định nghĩa:
Phép bù của một tập A, ký hiệu Ac, được định nghĩa:
Hiệu của hai tập hợp A và B, ký hiệu A-B, được định nghĩa:
Giả sử A, B là hai tập hợp thuộc Z2 , ỉ là tập rỗng , phộp gión của A đối với B , ký hiệu A B , được định nghĩa :
Tập B được gọi là thành phần cấu trúc
Giả sử A, B là hai tập thuộc Z2, phép co của A đối với B, ký hiệu A B được định nghĩa:
Giả sử A, B là hai tập thuộc Z2, phép đóng của A đối với B, ký hiệu A • B được định nghĩa:
Tức phép đóng là phép do thực hiện phép giãn rồi thực hiện phép co lên kết quả vừa có
Phép đóng có tác dụng làm đầy những khoảng nhỏ (tuỳ thuộc vào thành phần cấu trúc B) thường xảy ra trên đường biên
Thành phần cấu trúc thường được sử dụng là thành phần cấu trúc đối xứng có gốc (0, 0) là ở tâm như hình:
Khi ảnh được quét với độ phân giải 300 dpi, những chữ có bụng viết nghiêng gặp khó khăn khi phóng lớn do phép giãn làm cho phần bụng dính lại Để hạn chế tình trạng này, ta sử dụng hai thành phần cấu trúc không đối xứng và thực hiện phép đóng hai lần trên các thành phần này, giúp giãn chỉ về một phía.
Các thành phần cấu trúc không đối xứng
Lấy đường biên và làm trơn đường biên
Biên của ảnh được thiết lập bằng cách nhân chập ảnh với phần tử có cấu trúc:
2 Dò biên và mã hóa đường biên:
Ta có giải thuật dò tìm biên như sau:
Bước 1: Quét ảnh đến khi gặp điểm ảnh đen Gọi nó là pixel 1 Bước 2: Lặp
Nếu “điểm ảnh hiện thời là đen” thì “dò ngược”
Ngược lại “sang phải” đến khi “gặp pixel 1”
3 Xác định hướng của điểm biên (Freeman code):
Các hướng được quy ước như sau:
Với hướng quy ước trên, đường biên được mã hóa như sau:
Làm trơn đường biên là quá trình điều chỉnh đường biên sao cho hiệu số hướng giữa hai điểm liên tiếp không vượt quá 1 Nếu phát hiện hai điểm trên đường biên có hiệu số hướng lớn hơn 1, cần thực hiện hiệu chỉnh để đảm bảo rằng hiệu số hướng giữa các điểm liên tiếp sẽ bằng 1.
Theo mã hướng Freeman, hiệu số hướng của 2 điểm liên tiếp nhau trên đường biên được định nghĩa :
Goi ci là mã hướng tại điểm biên đang xét pi , ci+1 là mã hướng của điểm kế tiếp trên đường biên pi+1 Đặt d=ci+1-ci và Dabs=|d| nếu |d|4
Ta có các trường hợp sau: a dabs1 : Điểm biên trơn b dabs=2 và ci chẵn, ci+1 chẵn : bỏ pi+1 và thay hướng pi như sau:
Dabs có các trường hợp khác nhau: khi dabs = 2 và ci chẵn, ci+1 cũng chẵn; khi dabs = 2 và ci lẻ, ci+1 lẻ thì bỏ pi+1 và thay đổi hướng pi Ngoài ra, khi dabs = 3 với ci chẵn và ci+1 lẻ, hoặc khi ci lẻ và ci+1 chẵn cũng có những quy tắc riêng.
Minh hoạ ảnh kí tự sau quá trình tiền xử lý ảnh ban đầu ảnh sau khi xử lý
Phương pháp chuyển đổi ảnh RGB sang ảnh đa cấp xám sử dụng điểm ảnh (pixel) làm đơn vị cơ bản, với mỗi pixel được biểu diễn bằng n bytes trong các hệ màu khác nhau Việc chuyển đổi giữa các hệ màu thường được thực hiện thông qua các phép biến đổi ma trận Bài viết này sẽ giới thiệu cách chuyển đổi từ ảnh 24 bits RGB sang ảnh 8 bits đa mức xám, áp dụng các công thức cụ thể cho từng điểm ảnh [x,y].
Lx,y = 0.3086 * Redx,y + 0.6094 * Greenx,y + 0.0820 * Bluex,y Lx,y = 0.299 * Redx,y + 0.587 * Greenx,y + 0.114 * Bluex,y
Giá trị mỗi điểm ảnh Lx,y, hay cường độ sáng (Luminance Intensity) trong ảnh đa mức xám được tính bằng tổng trọng số khác nhau của các thành phần màu trong hệ màu RGB Việc sử dụng cùng trọng số như (R + G + B) / 3 sẽ dẫn đến việc màu đỏ, màu xanh nước biển và màu xanh da trời có cùng mức xám sau khi chuyển đổi Tuy nhiên, nghiên cứu cho thấy mắt người nhạy cảm hơn với các thành phần màu xanh lá cây và màu đỏ so với màu xanh da trời.
Triển khai công thức chuyển đổi màu sắc trong C/C++ cho ảnh định dạng RGBRGB rất đơn giản Đoạn mã dưới đây thực hiện phép tính để chuyển đổi từng pixel: ```cfor (i = 0; i < imgSize; i += 3) { out[i] = (unsigned char)(0.299 * in[i] + 0.587 * in[i + 1] + 0.114 * in[i + 2] + 0.5);}```Cách này giúp chuyển đổi ảnh màu sang ảnh đen trắng hiệu quả.
Việc thực hiện phép nhân trong miền số nguyên diễn ra nhanh hơn so với miền số thực, vì vậy công thức trên được điều chỉnh để áp dụng trong miền số nguyên.
Việc thay thế các phép chia và nhân bằng toán tử shift giúp tăng tốc độ tính toán hiệu quả Dưới đây là mã nguồn cho quá trình nâng cấp: ```cint iTmp; for (i = 0; i < imgSize; i += 3) { iTmp = in[i] 3); }```
} Lưu ý: trong thực hành, không phải lúc nào thứ tự của 3 bytes trong 1 điểm ảnh cũng là R - G - B, đôi khi thứ tự này có thể là B - G - R
VIII Phân đoạn ảnh và lấy ngƣỡng ảnh
1 Phân đoạn (hay phân vùng)
Phân vùng ảnh là quá trình tách một ảnh đầu vào thành các vùng thành phần để phục vụ cho phân tích và nhận dạng ảnh Ví dụ, trong việc nhận dạng chữ hoặc mã vạch trên phong bì thư để phân loại bưu phẩm, cần chia các câu, chữ và số thành các phần riêng biệt Đây là giai đoạn phức tạp và dễ gây lỗi, ảnh hưởng đến độ chính xác của quá trình nhận dạng Kết quả cuối cùng của nhận dạng ảnh phụ thuộc nhiều vào bước phân vùng này.
2 Các hướng tiếp cận phân đoạn ảnh
Phân đoạn ảnh là quá trình chia ảnh thành các vùng không trùng lặp, mỗi vùng bao gồm một nhóm pixel liên thông và đồng nhất theo tiêu chí nhất định, như màu sắc, mức xám, kết cấu, hoặc độ sâu của các lớp Sau khi phân đoạn, mỗi pixel sẽ thuộc về một vùng duy nhất Đánh giá chất lượng phân đoạn rất khó khăn, do đó, việc xác định rõ mục tiêu của quá trình phân đoạn là rất quan trọng Tổng quan, có thể chia các phương pháp phân đoạn ảnh thành ba nhóm chính.
Các kỹ thuật phân đoạn ảnh dựa trên không gian đặc trưng
Các kỹ thuật dựa trên không gian ảnh
Các kỹ thuật dựa trên các mô hình vật lý
3 Một số phương pháp phân đoạn cụ thể
Phương pháp phân đoạn của B.G Prasad được áp dụng trong hệ thống truy vấn ảnh dựa trên chỉ mục màu sắc, hình dạng và vị trí Phương pháp này sử dụng sự lượng tử hóa màu trong không gian màu RGB với 25 màu phân biệt để phân đoạn ảnh, dựa vào những màu trội Số lượng 25 màu này đủ để phân biệt rõ ràng tất cả các vùng màu trong cơ sở dữ liệu hình ảnh mà tác giả đã chọn.
3.2) Phương pháp phân đoạn dựa trên ngưỡng cục bộ thích nghi
Số ngưỡng cục bộ và giá trị của chúng được xác định thông qua việc kiểm tra thông tin cục bộ Quá trình này bao gồm các bước tuần tự, bắt đầu bằng việc áp dụng giải thuật Watershed để chia ảnh thành nhiều vùng con khác nhau.
Trộn các vùng và đồng thời phát hiện ngưỡng cục bộ Ngưỡng được tính từ thông tin cục bộ của vùng và các vùng lân cận
Giải thuật này cho kết quả tương đối tin cậy trên nhiều loại ảnh khác nhau
3.3) Phân đoạn sơ khởi bằng Watershed
Giải thuật Watershed sử dụng ảnh xám làm dữ liệu đầu vào Do đó, bước đầu tiên là chuyển đổi ảnh đầu vào I thành ảnh xám Tiếp theo, chúng ta áp dụng giải thuật tìm cạnh Canny để xử lý ảnh.
Để xác định cường độ gradient (IG), ta phân tích ảnh gradient như một lược đồ địa hình Các khu vực có độ xám cao hơn thường biểu thị cho vùng trũng, trong khi các khu vực có độ xám thấp hơn cho thấy vùng cao Đánh giá tại mỗi pixel sẽ dựa trên giá trị mức xám của pixel đó.
Kỹ thuật này thiết lập ngưỡng để hiển thị các tông màu liên tục trong ảnh Các điểm ảnh sẽ được so sánh với ngưỡng đã định trước, và giá trị của ngưỡng sẽ quyết định xem điểm đó có được hiển thị hay không.
Do vậy ảnh kết quả sẽ mất đi một số chi tiết Có nhiều kỹ thuật chọn ngưỡng áp dụng cho các đối tượng khác nhau:
Phương pháp hiển thị 2 màu chỉ sử dụng ảnh đen trắng với 256 mức xám, trong đó ngưỡng được xác định dựa trên lược đồ mức xám của ảnh Để đơn giản hóa, có thể chọn ngưỡng với giá trị là 127.
1 khi h(m,n)1) để không làm mất tính liên thông
Các điểm ảnh có thể xóa được thường được gọi là điểm ảnh đơn Một điểm ảnh biên không bị cô lập p được coi là đơn nếu N(p) chỉ có một thành phần đen, tương đương với việc XH(p) bằng 1.
Các điểm ảnh có số liên thông Nc 8(p) lớn hơn 1 được phân loại là điểm ảnh bội, bao gồm các điểm cuối của các nhánh, các nét vẽ dày 2 điểm ảnh, và các điểm ảnh được xác định cho xương theo tiêu chuẩn liên thông.
To determine the neighbors of a pixel, we need to identify points that have more than three neighbors, which helps in locating junction points The following demo code illustrates how to find the neighbors of a pixel: ```cppvoid IMAGE::LangGieng(char*pCot, struct LangGieng_8 *pixel, int type) { unsigned char next; pixel->nhomBienDen_8 = 0; pixel->nhomBien_4 = 0; pixel->nhomBienDen_4 = 0; pixel->langGieng_8 = 0; pixel->langGiengDen_8 = 0; pixel->langGieng_4 = 0; pixel->langGiengDen_4 = 0; for(unsigned char i = 0; i < 8; i++) ```This code initializes various neighbor counts and iterates through potential neighbors to assess connectivity.
// tinh diem lang gieng if(pCot[bien[i].dpos]= ||type>=0&&pCot[bien[i].dpos]==type ||typelangGieng_8++; if( (i&01)==1)// i le pixel->langGieng_4++;
}//if if(pCot[bien[i].dpos]=)
{ pixel->langGiengDen_8++; if( (i&01)==1) pixel->langGiengDen_4++;
}//if // tinh nhom bien lien thong_4 if(typenhomBien_4++;
} Else { if((pCot[bien[i].dpos]=||pCot[bien[i].dpos]==type)&&pCot[bien[i+1] dpos]==TRANG) pixel->nhomBien_4++;
The algorithm calculates the number of connected groups of pixels in a grid It checks the conditions for neighboring pixels and updates the count of connected groups based on their positions Specifically, it identifies groups of four and eight connected pixels, ensuring that the process continues only if certain criteria are met The logic incorporates checks for pixel availability and connectivity to optimize the grouping process.
||pCot[bien[i].dpos]!&&pCot[bien[i+next].dpos]=
}//of for // hieu chinh lai nhomBien_4 if(pixel->nhomBien_4==0) { if( type=0&&(pCot[1]=||pCot[1]==type)
) pixel->nhomBien_4=8;// xung quanh toan diem DEN }// of if
// hieu chinh lai nhomBienDen_4 if(pixel->nhomBienDen_4==0&&pCot[1]=) // xung quanh toan diem DEN pixel->nhomBienDen_4=8;
// xac dinh tinh lien thong if(pixel->nhomBienDen_8==0&&pCot[1]!||pixel-
>nhomBienDen_8>2) pixel->lienThong=0;// khong lien thong else pixel->lienThong=1;//lien thong return;
Điểm ngã ba là một điểm giao nhau, nơi có ba hoặc nhiều hơn các điểm lân cận, và các đường dẫn phân khúc có thể được xác định dựa trên những điểm giao nhau này.
Trong giai đoạn phân khúc, kỹ thuật tách ngã ba dựa trên quyết định phân đoạn đầy đủ của các chuỗi ký tự và số được kết nối Bằng cách sử dụng các giá trị mờ, các phân đoạn chính được cô lập và hoàn thành từ các phân đoạn nhỏ, trong khi các kết nối không mong muốn nằm trong các phân khúc nhỏ của bộ xương ký tự Ở giai đoạn tách ký tự, các phân đoạn chính được kết hợp để tạo ra các bản phác thảo kết nối khác nhau Những bản phác thảo này được xây dựng thành hình ảnh ký tự mới, có thể được sử dụng làm đầu vào cho hệ thống nhận dạng ký tự.
Hình 3.1 Điểm ngã 3 và phân khúc trong ký tự
4 Phân đoạn tách nét dựa vào điểm ngã ba
Khi phân đoạn các ký tự trong một ảnh, việc tách biệt các thành phần ký tự trở nên khó khăn do sự kết dính giữa các chữ số khác nhau Do đó, quá trình phân đoạn được chia thành hai giai đoạn: phân khúc ban đầu và phân chia tổng thể Trong giai đoạn phân khúc ban đầu, hình ảnh ký tự đầu vào được xác định điểm ngã ba và thực hiện phân đoạn dựa trên điểm này.
Nghiên cứu này chỉ ra rằng phân khúc ban đầu sẽ không hoàn chỉnh do sự kết nối điểm không tiếp giáp giữa các phân khúc bộ xương Ví dụ, hình ảnh 3.1 cho thấy ký tự viết tay trong bộ xương không được tách thành "âm tính nghiêng" và hai "Ngang Lines" vì thiếu điểm ngã ba kết nối ở giữa Để khắc phục điều này, một thuật toán phân đoạn riêng biệt sử dụng các phân khúc dựa trên quy tắc phương pháp tiếp cận Để hiểu rõ về thuật toán, cần tìm hiểu một số định nghĩa quan trọng: điểm khởi là pixel trên bộ xương có thể bắt đầu; điểm khởi chính là điểm xác định trước khi bắt đầu traversal; điểm khởi nhỏ là điểm xác định trong cây qua bộ xương; hướng traversal là hướng từ pixel hiện tại đến pixel tiếp theo; và điểm cuối cùng là pixel trong khu vực tương quan không có pixel lân cận nào để thăm tiếp Sau khi xác định tất cả các điểm khởi lớn và điểm giao nhau, thuật toán bắt đầu đi ngang qua bộ xương ký tự, bắt đầu từ khởi điểm chính trong danh sách các điểm khởi, và trong quá trình tách ban đầu, các phân đoạn được xác định dựa trên danh sách điểm giao nhau.
CHƯƠNG TRÌNH VÀ MỘT SỐ KẾT QUẢ
Bước 3 : Phân đoạn tách nét và đánh dấu những điểm ngã ba Đây là kết quả phân đoạn tách nét khi chưa làm mảnh :
Một số kết quả thử nghiệm khác :
Kết luận: Thuật toán tách các ký tự viết tay khỏi kết dính đã chứng minh tính đáng tin cậy cao và đơn giản trong việc tạo ra các mô tả mờ cho mô hình ký tự bị kết dính Các thuật toán phân khúc phát triển cho công việc này có khả năng tách các kết nối của ký tự viết hoa thành các đoạn có ý nghĩa chính xác, với tỉ lệ nhận dạng cao khi đưa ký tự vào hệ thống để xác định các kết dính, bao gồm cả những kết dính không mong muốn.
Mặc dù các phương pháp hiện tại không xử lý được kết nối chồng từ hai chữ số kề nhau, hệ thống vẫn có khả năng tách các kết nối ký tự viết tay với các kết nối đơn hoặc kép Bài toán đề xuất là một phương pháp phát triển xác định, nhằm tách biệt các nét kết dính của các ký tự viết tay đã được đề cập.