Đề tài Biến đổi hough và ứng dụng phát hiện góc nghiêng văn bản

thuật trước khi đảo ngược một tài liệu như kỹ thuật số có thể được nạp vào bộ xử lý từ. Trong những năm gần đây, thêm một thách thức thú vị trong nghiên cứu nhận dạng. Đọc văn bản từ nhừng hình ảnh tự nhiên ghi bằng máy ảnh, nhiều vấn đề được đặt ra, ta đang fải đối phó với một số hạn chế ứng dụng như: việc nhận dạng tự động của các chữ số trong bức ảnh chụp của tấm giấy phép ôtô trở thành một vấn để kỹ thuật đơn thuần, cách đọc dựa trên camera của văn bản ví dụ, trong hệ thống hỗ trợ cho người mù, chỉ bắt đầu hiển thị kết quả sơ bộ. 1.3. Bài toán phát hiện góc nghiêng văn bản. Xử lý văn bản hình ảnh có nhiều nhiệm vụ khác nhau và có các phương pháp để thực hiện các nhiệm vụ này. Trong khi quét văn bản, nghiêng là không tránh khỏi khi văn bản hình ảnh được đưa vào. Góc nghiêng là sự sai lệch bất kỳ của hình ảnh từ văn bản gốc, mà không song song với chiều ngang hoặc dọc. Góc nghiêng văn bản là một trong những nhiệm vụ quan trọng cần được sửa chữa trong xử lý văn bản. Góc nghiêng văn bản là một bài toán kinh điển trong xử lý ảnh văn bản. Một hệ thống xử lý ảnh văn bản thường phải giải quyết bài toán phát hiện góc nghiêng như một bước đầu tiên và tất yếu. Chính vì vậy, cùng với sự phát triển của xử lý ảnh nói chung và xử lý ảnh văn bản nói riêng, bài toán góc nghiêng văn bản cũng được quan tâm ngày càng nhiều và dưới nhiều góc độ khác nhau. Có rất nhiều hướng tiếp cận cho bài toán góc nghiêng văn bản từ trước tới nay. Các thuật toán phát hiện góc nghiêng thường được xây dựng cho các hệ thống phân tích ảnh văn bản khác nhau nên chỉ giải quyết cho những loại ảnh văn bản cụ thể. Có thể chia ra một số hướng tiếp cận cơ bản cho bài toán góc nghiêng văn bản như sau: - Các thuật toán dựa vào phương pháp Base - point - Các thuật toán dựa vào biến đổi Hough (Hough Transform) - Các thuật toán dựa vào biến đổi Fourier (Fourier Transform) - Các thuật toán phân tích láng giềng (Nearest Neighbour Clustering) - Các thuật toán dựa vào phương pháp scanline… Dựa vào tính chất mỗi đối tượng ảnh có duy nhất một chu tuyến ngoài và quan niệm con người nhận ra độ nghiêng của văn bản dựa vào cỡ chữ chiếm chủ đạo trong văn bản. Mục này đề cập đến việc tính toán kích thước chủ đạo của các đối tượng ảnh trong văn bản thông qua kỹ thuật tính biểu đồ tần xuất kích thước hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh. Việc xác định góc nghiêng văn bản sẽ được xác định nhờ phép biến đổi Hough cho những điểm giữa đáy của hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh cho các đối tượng ảnh có kích thước chủ đạo. Kết luận Nội dung chương 1 đã giới thiệu tổng quan các bước tiền xử lý văn bản, vai trò của nó trong việc nhận dạng văn bản. Bước đầu tiếp cận với bài toán phát hiện góc nghiêng văn bản. Qua nghiên cứu có rất nhiều cách tiếp cận khác nhau đối với bài toán phát hiện góc nghiêng văn bản. Một số thuật toán tiêu biểu sẽ được trình bày chi tiết hơn trong chương 2. Chương 2 CÁC THUẬT TOÁN PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN Có nhiều phương pháp khác nhau để phát hiện góc nghiêng hình ảnh văn bản quét. Trong chương này chúng tôi nghiêng cứu 3 thuật toán phát hiện góc nghiêng văn bản tiêu biêu nhất là: Phát hiện góc nghiêng dựa vào phương pháp Base-point, dựa vào biến đổi Fourier và phát hiện góc nghiêng dựa vào phương pháp Scanline. 2.1. Phát hiện góc nghiêng dựa vào phương pháp Base-point. Đầu tiên chúng ta sẽ thảo luận về các phương pháp pháp hiện góc nghiêng bằng cách sử dụng thuật toán staight line phù hợp. Các bước liên quan và cộng thêm tiêu chuẩn khác nhau mà nó tăng hiệu quả của các thuật toán đã được thảo luận. Cuối cùng đưa ra các ví dụ thích hợp. 2.1.1. Lựa chọn của một phân vùng và đối tượng 2.1.1.1. Lựa chọn phân vùng Dòng văn bản trong một tài liệu nói chung là song song với nhau theo hướng ngang và khoảng cách giữa hai dòng văn bản liên tiếp là tương đối cố định. Từ khi quét tất cả các điểm ảnh trong toàn bộ ảnh văn bản là tốn thời gian, nó thích hợp để chọn phân vùng phù hợp để tính toán theo hướng dòng văn bản mà tương ứng với góc nghiêng của ảnh. Mặc dù các điểm ảnh trong một trang hình ảnh thể hiện các thông tin về nhiều mặt, nó tốn thời gian để phân tích tất cả các điểm ảnh trong hình ảnh. Thành phần kết nối, cái mà tập hợp có liên quan đến các điểm ảnh, cũng có thể thể hiện thông tin trong nhiều mặt như bố cục trang.[5] Trong một văn bản hình ảnh được quét, có một số cạnh đen mà không chỉ ảnh hưởng đến tính chính xác của thuật toán mà còn tăng chi phí tính toán. Mục đích để tránh những ảnh hưởng tiêu cực của các cạnh đen, các cạnh của văn bản hình ảnh không cần phải lựa chọn bao gồm cả vùng. Hơn nữa, kích thước của vùng cần phải chon cẩn thận để đạt được tốc độ cao hơn và độ chính xác tốt hơn. Cách lựa chon vùng R cần phải thoả mãn điều kiện sau: R={(x,y)|w1≤x≤w2,h1≤y≤h2,(w1-w2)≥ Wc,(h1-h2)≥Th} (2.1) Ở đây Wc là trung bình chiều rộng của các ký tự chữ và số, và Th là khoảng ngưỡng giữa những dòng kế tiếp. Cho độ rộng của văn bản hình ảnh là W và chiều cao là H, đường biên trái của vùng nên là w1=W/3, đường biên phải w2=W2/3, biên trên h1=H/3, biên dưới h2=H2/3. Theo thống kê, số lượng thành phần kết nối trong một dòng văn bản n nên lớn hơn 10, và số lượng của các dòng văn bản trong vùng k nên lớn hơn 3, mà có thể đảm bảo độ chính xác của thuật toán này. Đồng thời mối quan hệ giữa các thành phần liên kết liền kề phân tích với một số thuật toán như là phép chiếu, mà nó có thể chắc chắn được lựa chọn vùng chỉ bao gồm một cột văn bản. 2.1.1.2. Lựa chọn đối tượng Hộp ranh giới của tất cả các thành phần liên kết được tạo ra trước tiên. Và một ký tự đơn hoặc các ký tự chạm vào được chứa trong hộp ranh giới được coi như là một đối tượng. Theo thống kê, phần lớn đáy các đối tượng chữ số đều nằm trên một đường cơ sở, như là: A, s, x, ect. Chỉ có rất ít đối tượng chữ số đi xuyên qua một hộp ranh giới đường cơ sở, như là: p, q, g,… Kích thước của các đối tượng đánh dấu chấm câu là rõ ràng nhỏ hơn so với những chữa số. Để loại bỏ những tác động tiêu cực của đánh dấu chấm câu, các đối tượng chỉ có thể thoả mãn các điều kiện sau đây có thể được lựa chọn là ứng cử viên cho thuật toán phát hiện độ nghiêng. C={Ci|W(Ci)≥Dw V H(Ci)≥Dh,1≤x≤k} (2.2) Ở đây C là tập hợp các ứng viên cho các thuật toán phát hiện góc nghiêng, W(Ci) và H(Ci) có chiều rộng và chiều cao của hộp ranh giới của đối tượng Ci, tương ứng Dw là ngưỡng của độ rộng, Dh là ngưỡng của chiều cao của đối tượng hộp ranh giới, và k là số đối tượng ứng cử viên. Hình 2.1. Hộp bao quanh và điểm cơ sở của một ký tự 2.1.2. Tập các điểm cơ sở. 2.1.2.1. Định nghĩa Định nghĩa 1: Base-point của một đối tượng là trung tâm ở phía dưới trong hộp ranh giới của một đối tượng. (hình 2.1) Định nghĩa 2: Base-group là một nhóm chứa tất cả các điểm cơ sở trong cùng một dòng văn bản. 2.1.2.2. Tập hợp các điểm cơ sở. Trong một vùng văn bản rõ ràng nơi mà những dòng văn bản là song song, các điểm cơ sở trong dòng văn bản khác nhau có thể được chia thành các nhóm cơ sở khác nhau theo ngưỡng không gian Th. Sau đây là thủ tục chi tiết. Bước 1: Khởi tạo mỗi điểm cơ sở để nó không có trong bất kỳ nhóm cơ sở nào, và thiết lập k = 0. Bước 2: Trong phân vùng đã chọn R, nếu điểm cơ sở Pi(xi,yi) phía trên trái không tìm thấy trong bất kỳ nhóm cơ sơ nào, thiết lập k++ và đưa Pi vào nhóm mới G(k). Bước 3: Trong phạm vi hình chữ nhật {(xi,yi-Th/2)}, {(w2,yi+Th/2)}, nếu điểm cơ sở trái nhất Pj(xj,yj) không tìm thấy trong bất kỳ nhóm cơ sở nào, đưa Pj vào G(k) và thiết lập Pi= Pj(i.e.xi=xj,yi=yj). Lặp lại bước này cho đến khi tất cả các điểm cơ sở nằm trong nhóm cơ sở nhất định trong phạm vi hình chữ nhật này. Bảng 2.1: so sánh kết quả độ nghiêng văn bản quét của tài liệu khác nhau tính toán góc ban đầu sử dụng phương pháp Base – point. Góc => Tính góc nghiêng (θs) Góc nghiêng ban đầu (θ) Các hình văn bản quét Hình 2.3 (a) Hình 2.3 (c) Hình 2.4 (a) Hình 2.4 (c) Hình 2.5 (a) Hình 2.5 (c) -4 -2 -1 -1 -4 -3 -8 6 -7 15 16 -18 Bước 4: quay lại bước 2 cho đến khi tất cả các điểm cơ sở trong vùng R đã được đưa vào trong các nhóm cơ sở khác nhau. Áp dụng cho đường thẳng phù hợp, sử dụng phương pháp tối ưu, đối với mỗi nhóm thu được ở cuối bước 4 để có được độ nghiêng của đường đó phù hợp nhất cho mỗi nhóm. Lấy giá trung bình tất cả các giá trị độ nghiêng thu được trong bước trước đó. Đây là góc nghiêng của chúng tôi. 2.1.3. Độ phức tạp Cho số điểm ảnh trong vùng R là NR. Sau thuật toán các điểm cơ sở thì cho độ phức tạp thời gian O(NR). (a) Ảnh đầu tiên quét từ sách (b) kết quả hiệu chỉnh từ (a) (c) ảnh thứ 2 quét từ sách (d) kết quả hiệu chỉnh (c) Hình 2.2: Quét tài liệu từ sách với phương pháp Base - point (a) ảnh đầu tiên quét từ bài thi (b) kết quả hiệu chỉnh (a) (c) Ảnh thứ 2 quét từ bài thi (d) kết quả hiệu chỉnh (c) Hình 2.3: Ảnh quét từ bài thi với phương pháp Base – point (a) Ảnh quét từ danh mục điện thoại (b) kết quả hiệu chỉnh từ (a) (c) Ảnh thứ 2 quét từ danh mục điện thoại (d) kết quả hiệu chỉnh từ (c) Hình 2.4: Ảnh quét từ danh mục điện thoại với phương pháp Base – point (a) Ảnh thứ 3 quét từ danh mục điện thoại (b) kết quả hiệu chỉnh (b) (c) Ảnh thứ 4 quét từ DM điện thoại (d) kết quả hiệu chỉnh (c) Hình 2.5: Ảnh quét từ danh mục điện thoại với phương pháp Base – point 2.2. Phát hiện góc nghiêng dựa vào biến đổi Fourier Biến đổi Fourier là một công cụ quan trọng trong xử lý hình ảnh được sử dụng để phân hủy một hình ảnh thành hình sin của nó và các thành phần cosin. Kết quả của biến đổi đại diện cho hình ảnh trong fourier hoặc miền tần số, trong khi hình ảnh đầu vào là các miền không gian tương đương. Trong những hình ảnh miền Fourier, mỗi điểm đại diện cho một tần số đặc biệt chứa trong hình ảnh miền không gian. Việc chuyển đổi Fourier được sử dụng trong một loạt các ứng dụng như: phân tích hình ảnh, hình ảnh lọc tái tạo ảnh, nén ảnh… 2.2.1. Phép biến đổi Fourier và các đặc trưng hình học Biến đổi fourier rời rạc không chứa tất cả các tần số tạo thành một hình ảnh, nhưng chỉ có một tập hợp các mẫu là đủ lớn để mô tả đầy đủ hình ảnh miền không gian. Số lượng các tần số tương ứng với số lượng điểm ảnh trong hình ảnh miền không gian, tức là hình ảnh trong và Fourier miền không gian có cùng kích thước. Để có một hình vông có kích thước NxN, các DFT hai chiều cho bởi: Fk,l=1N2a=0N-1b=0N-1fa,be-t2π(kaN+lbN) (2.3) Trong đó f (a, b) là hình ảnh trong lĩnh vực không gian và thời hạn theo cấp số nhân là cơ sở chức năng tương ứng với mỗi điểm F (k, l) trong không gian Fourier. Phương trình có thể được hiểu là: giá trị của mỗi điểm F (k, l) thu được bằng cách nhân các hình ảnh không gian với các chức năng cơ bản tương ứng và tổng hợp kết quả. Theo cách tương tự thì hình ảnh Fourier có thể được tái chuyển vào miền không gian. Biến đổi Fourier ngược cho bởi fa,b=1N2k=0N-1l=0N-1Fk,let2π(kaN+lbN) (2.4) Để có được kết quả cho các phương trình trên, giá trị gấp đôi đã được tính cho mỗi điểm ảnh. Tuy nhiên, do chuyển đổi Fourier là tách được nó được viết là: Fk,l=1Nb=0N-1P(k,b)e-t2πlbN (2.5) Với Pk,b=1Na=0N-1f(a,b)e-t2πkaN (2.6) Sử dụng hai công thức, hình ảnh miền không gian là lần đầu tiên chuyển đổi thành một hình ảnh trung gian bằng cách sử dụng N một chiều biến đổi Fourier. Ngay cả khi tiết kiệm tính toán, một chiều thông thường có DFT N2 phức tạp. Điều này có thể giảm xuống Nlog2N nếu ta sử dụng biến đổi nhanh Fourier (FFT) tính DFTs một chiều. Đây là một cải tiến đáng kể, đặc biệt cho hình ảnh lớn. Có nhiều hình thức khác nhau của FFT và hầu hết trong số đó hạn chế kích thước của hình ảnh ban đầu và có thể chuyển đổi thường xuyên N=2n trong đó n là một số nguyên. Trong xử lý hình ảnh, thường thì chỉ có độ lớn của biến đổi Fourier được hiển thị, vì nó chứa hầu hết các thông tin về cấu trúc hình học của hình ảnh miền không gian. Tuy nhiên, nếu chúng ta muốn tái biến đổi hình ảnh Fourier vào miền trong không gian chính xác sau khi một số xử lý trong lĩnh vực tần số. Việc chuyển đổi Fourier được sử dụng nến chúng ta muốn truy cập các đặc tính hình học của một hình ảnh miền không gian. Bởi vì hình ảnh trong lĩnh vực Fourier bị phân hủy thành các thành phần hình sin của nó, nó rất dễ dàng để kiểm tra hoặc quá trình tần số ổn định của hình ảnh, do đó ảnh hưởng đến cấu trúc hình học trong lĩnh vực không gian. 2.2.2. Biến đổi Fourier trong định dạng văn bản Xác định nghiêng văn bản là một công cụ quan trong trọng tài liệu phân tích bởi vì nhiều tài liệu phân tích kỹ thuật yêu cầu hoàn toàn phù hợp với tài liệu hình ảnh để làm việc cho tốt. Nếu nghiêng mà tài liệu chưa được sử lý thì tính chính xác của các kỹ thuật khác có thể bị hạn chế. Với vấn đề này, kỹ thuật được đề xuất dựa trên các sử dụng biến đổi Fourier cho góc nghiêng dự toán chính xác. Góc nghiêng có thể tìm thấy từ 2D phổ Fourier bằng cách tích hợp tỏa tròn hoặc việc tìm kiếm các góc độ của đỉnh có giá trị cao nhất. Việc xác định độ lệch sử dụng các dòng trong Fourier không gian để xác định góc nghiêng theo thuật toán sau: Hình ảnh được phân thành các khối có kích thước nxn. Phân tích Fourier là phổ Fourier tính toán cho mỗi khối (sử dụng FFT) và đại diện với nguồn trung tâm. Một cửa sổ nhỏ có kích thước WxW, với tâm tại gốc( thiết lập là không) và giá trị còn lại trong quang phổ được chuẩn hóa để có được sự nhất quán các giá trị giữa các khối. Đỉnh cặp phát hiện trong 5 cặp cao nhất và các góc tương ứng với trục dọc của phổ quang phổ, đỉnh này xảy trong các cặp kể cả đầu vào là giá trị thực. Histogram – Biểu đồ góc lệch xây dựng nơi mà các góc lệch có giá tri nguyên. Mỗi góc độ tính toán các thùng tương ứng với giá trị nguyên của nó được tăng lên bằng giá trị bình thường của các đỉnh trong Fourier phổ. Các giá trị góc lệch thực tế được giữ lại. Góc lệch tính có giá trị nguyên – Histogram sau đó được làm nhẵn và cao điểm nhất chọn là giá trị nguyên của các góc nghiêng. Giá trị góc thực tính – trong tất cả giá trị thực góc trong t0 ± của các số nguyên có giá trị là góc lựa chọn và tính trung bình nó. Điều này, giá trị trung bình đại diện cho góc nghiêng cuối cùng của văn bản 2.3. Phát hiện góc nghiêng dựa vào phương pháp Scanline. Có nhiều phương pháp khác nhau để phát hiện góc nghiêng hình ảnh văn bản quét. Nhưng ở đây chúng tôi tập trung dựa trên phương pháp Scanline tức là phương pháp Scanline trên biến đổi Hough. 2.3.1. Thuật toán Scanline Phương pháp này chiếu các hình ảnh ở nhiều góc cạnh và xác định mức độ thay đổi số điểm ảnh màu đen chiếu mỗi dòng quét. Góc mà tại đó giá trị lớn nhất xảy ra không phải là góc nghiêng. Thuật toán: 1. Tính toán toạ độ trong mặt phẳng ảnh, cho mỗi dòng quét song song nằm ở một góc nghiêng tan(θ) trong mặt phẳng ảnh. Toạ độ được tính toán sử dụng thuật toán Bresenham’s Line Drawing. 2. Đối với mỗi dòng quét, điếm số điểm ảnh không là nền nằm trên dòng. 3. Tính v số lượng điểm ảnh màu đen nằm trên mỗi dòng quét với một góc θ xác định 4. Góc nghiêng θ là cho bởi góc mà phương sai lớn nhất vmax được tìm thấy. Độ phức tạp: Với N là số đỉêm ảnh trong văn bản ảnh được quét, độ phức tạp là: O(N). (a) Ảnh đầu tiên quét từ sách (b) kết quả hiệu chỉnh từ (a) (c) ảnh thứ 2 quét từ sách (d) kết quả hiệu chỉnh (c) Hình 2.6: Quét tài liệu từ sách với phương pháp Scanline (a) ảnh đầu tiên quét từ bài thi (b) kết quả hiệu chỉnh (a) (c) Ảnh thứ 2 quét từ bài thi (d) kết quả hiệu chỉnh (c) Hình 2.7: Ảnh quét từ bài thi với phương pháp Scanline (a) Ảnh quét từ danh mục điện thoại (b) kết quả hiệu chỉnh từ (a) (c) Ảnh thứ 2 quét từ danh mục điện thoại (d) kết quả hiệu chỉnh từ (c) Hình 2.8: Ảnh quét từ danh mục điện thoại với phương pháp Scanline (a) Ảnh thứ 3 quét từ danh mục điện thoại (b) kết quả hiệu chỉnh (b) (c) Ảnh thứ 4 quét từ DM điện thoại (d) kết quả hiệu chỉnh (c) Hình 2.9: Ảnh quét từ danh mục điện thoại với phương pháp Scanline Bảng 2.2: So sánh kết quả độ nghiêng văn bản quét của tài liệu khác nhau tính toán góc ban đầu sử dụng phương pháp Scanline. Góc => Tính góc nghiêng (θs) Góc nghiêng ban đầu (θ) Các hình văn bản quét Hình 2.7 (a) Hình 2.7 (c) Hình 2.8 (a) Hình 2.8 (c) Hình 2.9 (a) Hình 2.9 (c) -8 6 -7 15 16 -18 -8 6 -7 15 16 -18 2.3.2. Biến đổi Hough. Thuật toán dùng biến đổi Hough thường xác định một số điểm đen và dùng biến đổi Hough tác động lên các điểm đó. Biến đổi Hough ánh xạ một đường thẳng trong mặt phẳng thành các cặp (r,j) trong không gian Hough với r là khoảng cách từ gốc tọa độ tới đường thẳng đó và j là góc nghiêng của đường thẳng đó so với trục hoành. Góc nghiêng văn bản tương ứng là góc có tổng số điểm nằm trên những đường thẳng cùng lệch góc lớn nhất. Thông thường để đếm số các điểm đen này các thuật toán dùng một mảng tích lũy Histogram. Số các điểm đen được áp dụng biến đổi Hough tùy thuộc vào từng thuật toán, có thể là tất cả các điểm đen hoặc có thể chỉ là những điểm thỏa mãn một số ràng buộc nào đó hoặc chỉ là đáy của các đối tượng ảnh. Phương pháp của Srihari và Govidaraju là áp dụng biến đổi Hough cho tất cả các điểm đen của ảnh. Tất nhiên, việc áp dụng không có loại trừ một điểm nào dẫn đến chi phí tính toán rất lớn và ảnh hưởng tới độ chính xác của thuật toán. Để giảm thời gian chạy và tăng một phần độ chính xác của thuật toán, Hinds chỉ áp dụng biến đổi Hough cho một số ít điểm hơn bằng phân tích chạy dài theo chiều dọc. Mục đích của nén chạy dài theo chiều dọc trong thuật toán này là lấy ra các điểm đáy của các dòng văn bản, loại bỏ đi những điểm đen khác kể cả chúng thuộc vào một ký tự dùng biến đổi Hough lên các điểm đen đó. Tuy nhiên, chi phí tính toán của thuật toán này vẫn còn lớn và việc áp dụng biến đổi Hough cho tất cả các điểm đen ở đáy có thể dẫn đến những kết quả sai trong trường hợp ảnh đầu vào còn nhiều đối tượng phi ký tự: nhiễu, bảng biểu hay ảnh. Biến đổi Hough được sử dụng rộng rãi trong phân tíc hình ảnh, tầm nhìn máy tính và xử lý hình ảnh kỹ thuật số. Nó là một kỹ thuật sử dụng để tìm các hình dạng trong một hình ảnh kỹ thuật số nhị phân. Các tiếp cận này được ưa thích khi mục tiêu là để tìm đường hoặc đường cong trong một hình ảnh. Nó được xác định bởi các đại diện tham số được sử dụng để mô tả các đường trong mặt phẳng ảnh. Nó được giới thiệu bởi Paul Hough vào năm 1962 và bằng sáng chế của IBM. Các biến đổi biểu diễn bằng tham số mô tả về một đặc trưng tại vị trí bất kỳ được đưa ra trong một không gian ảnh gốc. Ý tưởng cơ bản là “mỗi đường thẳng trong một hình ảnh có thể được mô tả bởi một phương trình và mỗi điểm trắng nếu xem xét trong sự cô lập có thể nằm trên vô số đường thẳng”. Trong biến đổi Hough mỗi phiếu điểm cho mỗi dòng nó có thể được ủng hộ. Các dòng có số phiếu cao nhất giành chiến thắng. Xem xét một điểm (xi,yi) trong mặt phẳng xy và có phương trình tổng quát của một đường thẳng có dạng yi=axi+b. Các đường thẳng hữu hạn đi qua (xi,yi) nhưng tất cả đều thoả mãn phương trình yi=axi+b với giá trị a và b thay đổi. Tuy nhiên, phương trình được viết là:b= -xia+yi và thực tế mặt phẳng ab (còn gọi là tham số không gian.) còn có phương trình của một đường thẳng duy nhất cho θ = +450 x y (xi,yi) (xj,yj) một cặp (xi,yi) cố định. Hơn nữa, điểm (xj,yj) thứ 2 cũng là một đường thẳng trong không gian tham số phụ thuộc với nó, và trừ phi chúng song song, đường thẳng chặn này cắt đường thẳng với điểm (xi,yi) tại điểm (a’,b’). Trong đó độ nghiêng a’ và b’ chặn của đường thẳng bao gồm cả 2 điểm (xi,yi) và (xj,yj) trong mặt phẳng xy. Trong thực tế các điểm nằm trên đường thẳng có các đường thẳng nằm trong tham số không gian cắt nhau tại (a’,b’). Hình 2.10: Đại diện dòng bình thường Về nguyên tác, các đường thẳng tham số không gian tương ứng với tất cả các điểm (xk,yk) trong mặt phẳng xy có thể là đồ thị, và chính các đường thẳng trong mặt phẳng có thể tìm thấy bởi điểm xác định trong tham số không gian nơi mà có số lượng lớn các tham số không gian giao nhau. Một khó khăn thực tế với cách tiếp cận này, tuy nhiên là một (độ nghiêng của đường thẳng) cách tiếp cận vô cực như là tiếp cận phương pháp phát hiện đường thẳng. Vấn đề này có thể giải quyết bằng cách biểu diễn thông thường của đường thẳng. xcosθ + ysinθ = ρ (2.7) Hình 2.10 biểu diễn hình học giải thích tham số θ và ρ. Đường nằm ngang có θ=00 với ρ là giá trị dương cực x. Tương tự, một đường dọc có θ=90, với ρ là giá trị dương cực y hoặc θ=-90 với ρ là giá trị âm cực y. Mỗi đường cong sin trong hình 2.6 biểu diễn họ các đường đi qua một điểm cụ thể (xk,yk) trong mặt phẳng xy. Các giao điểm (ρ,θ) trong hình 2.10 tương ứng với đường thẳng đi qua cả 2 điểm (xi,yi) và (xj,yj). hình 2.10 Sự hấp dẫn trong tính toán của biến đổi Hough xuất phát từ phân chia không gian tham số ρθ vào trong các ô cũng gọi là accumulator nơi mà (ρmin,ρmax) và (θmin,θmax) là phạm vi các giá trị có thể xảy ra của tham số: - 900≤θ≤90 và -D≤ρ≤D trong đó D là khoảng cách tối đa giữa các góc đối diện trong một hình ảnh. Các ô ở toạ độ (i,j) với giá trị A(i,j) tương ứng với hình liên kết với không gian tham số toạ độ (ρi,θj). Ban đầu các phần tử này được thiết lập bằng 0. Sau đó, cứ mỗi điểm (xk,yk) không nền trong mặt phẳng xy, chúng tôi cho θ bằng mỗi giá trị phân chia được cho phép trên trục θ và giải quyết cho ρ tương ứng bằng cách sử dụng phương trình ρ=xkcosθ+yksinθ. Các giá trị kết quả ρ này sau đó được làm tròn với giá trị gần nhất cho phép giá trị dọc theo trục ρ. Nếu chọn một góc θp kết quả trong vấn đề pp, sau đó chúng tôi cho A(p,q)=A(p,q) + 1. Số lượng các đơn vị trong mặt phẳng ρθ xác định chính xác của điểm trên cùng một đường thẳng. Một hình ảnh đầu vào được lấy và biến đổi Hough đã được triển khai. Giá trị của θ được tăng lên theo các hàng và giá trị của ρ tăng lên theo các cột. Phương sai được tính cho giá trị trong mỗi cột nghĩa là phương sai giữa số lượng các điểm và số lượng các điểm nằm trên đường thẳng song song. Các θ này cho phương sai tối đa là góc nghiêng. Thực hiện biến đổi Hough: Một hình ảnh đầu vào được lấy và biến đổi Hough đã được triển khai. Giá trị của θ được tăng lên theo các hàng và giá trị của ρ tăng lên theo các cột. Phương sai được tính cho giá trị trong mỗi cột nghĩa là phương sai giữa số lượng các điểm và số lượng các điểm nằm trên đường thẳng song song. Các θ này cho phương sai tối đa là góc nghiêng. 2.3.3. Độ phức tạp Với số lượng điểm ảnh non-background Nnb trong ảnh văn bản được quét. Và Nθ là số lượng các góc được tính toán sử dụng biến đổi Hough. Độ phức tạp là 0(NnbNθ) Kết luận Trên thực tế có rất nhiều cách tiếp cận bài toán phát hiện góc nghiêng văn bản với các phương pháp khác nhau. Trong chương này chúng tôi nghiên cứu 3 phương pháp điển hình. Mỗi phương pháp đều có những ưu nhược điểm, độ phức tạp tính toán và tính chính xác khác nhau. Phương pháp Scanline là phương pháp dựa trên thuật toán biến đổi Hough.Và vấn đề này sẽ được trình bày trong phần tiếp theo. Chương 3 THUẬT TOÁN BIẾN ĐỔI HOUGH VÀ KHẢ NĂNG KHAI THÁC TRONG MÔI TRƯỜNG MATLAB Trong chương này chúng tôi đề cập đến một số đặc điểm tính toán của biến đổi Hough, các bước công việc tính toán tìm kiếm góc nghiêng. Từ đó ước lượng góc nghiêng văn bản và phương pháp quay góc nghiêng văn bản. 3.1. Thuật toán biến đổi Hough và một số đặc điểm tính toán Thực hiện biến đổi Hough Biến đổi Hough là phương pháp phổ biến nhất được sử dụng trong việc phát hiện góc nghiêng văn bản, nhưng nó tương đối đắt tiền. Để giảm bớt chi phí tính toán, một số phương pháp sửa đổi được đề xuất. ví dụ: Một hình ảnh mức xám có thể đại diện bởi các dòng chạy mã số dài, và các điểm được chọn dùng biến đổi Hough phải là các mã trong phạm vi nhất định. Sử dụng các điểm ảnh dưới cùng của các đối tượng ứng viên được chọn để biến đổi Hough. Kỹ thuật biến đổi Hough cũng được thông qua ý tưởng chính của phương pháp trên là giảm số lượng dữ liệu đầu vào, nhưng độ phức tạp còn cao. Các bước cho việc tìm kiếm góc nghiêng sử dụng biến đổi Hough như sau Đối với mỗi điểm ảnh P(‘xi’,’yi’). Tính giá trị của ρ,ρj tương ứng đối với -90≤θi≤90. Giá trị ρ được làm tròn số với giá trị gần nhất cho phép dọc theo trục ρ. Độ lớn các Hough tương ứng với phần tử H(j,i), bởi một kết quả xử lý phía trên trong ma trận Hough, mà mỗi phần tử (i,j) này mang đến số các điểm này nằm trên đường thẳng với tham số ρ và θ, (ρi,θj). Mỗi cột của ma trận Hough cho tất cả các điểm nằm trên tập hợp các đường thẳng song song, không phân biệt giá trị của ρ. Vì vậy, việc tìm kiếm các giá trị phương sai dọc theo mỗi cột cho chúng ta phương sai về số lượng các điểm ảnh nền nằm trên các đường thẳng song song. Một lần nữa, góc nghiêng là góc mà tại đó phương sai là lớn nhất. Xác định góc nghiêng của văn bản Sau khi tìm được các góc nghiêng của các vùng bao hình chữ nhật, chia khoảng [-10,10] thành các đoạn nhỏ có độ dài là 10, sắp xếp và tính tổng các góc nằm trong các khoảng [-10,-9], [-9,-8],….[8,9], [9,10]. Tìm ra khoảng có tổng các góc là lớn nhất và số lượng các góc thuộc khoảng đó. Giá trị góc nghiêng văn bản được ước lượng: Giả sử: angleMax là tong các góc lớn nhất thuộc khoảng [a,b] nào đó max: số lượng góc tương ứng thuộc khoảng [a,b] angle: góc của văn bản angle = angleMaxmax (3.1) * Kết quả thực nghiệm: qua quá trình thự