Đồ án Xác định góc nghiêng văn bản

Mục lục lời mở đầu Trong số các thông tin con người thu nhận từ thế bên ngoài, cố đến hơn 80% được ghi nhận bằng mắt tức là ở dạng ảnh. Vì vậy xử lý ảnh là một ngành khoa học đã và đang và sẽ phát triển mạnh cò ứng dụng rộng rãi trong khoa học và đới sống thực tiễn. Các hệ thống xử lý ảnh cho phép con người thu nhận lưu trữ, phân tích và nhận dạng ảnh. Một bộ phận quan trọng của xử lý ảnh là xử lý văn bản. Một trong những nhiện vụ và là đối tượng chính của xử lý ảnh văn bản là tự động hoá công việc văn phòng. Một trong những vấn đề đầu tiên và kinh điển trong xử lý ảnh văn bản là bài toán góc nghiêng văn bản. Nguyên nhân đẫn đến văn bản bị nghiêng một góc xuất phát từ quá trình quét ảnh hoặc copy ảnh. Do đặt ảnh vào bệ máy quét và máy in là một công đoạn được thực hiện bằng tay lên ảnh có thể bị lệch so với bệ máy một góc mà mắt thường không nhận thấy được, đẫn đến ảnh bị lệch đi một góc tương ứng. Văn bản bị lệch có ảnh hưởng rất lớn đến các quá trình xử lý ảnh tiếp theo, vì vậy việc phát hiện và chỉnh sửa góc nghiêng văn bản là nhiệm vụ quan trong đấu tiên trong xử lý ảnh văn bản. Từ hai thập kỷ gần đây, cùng với sự phát triển của xử lý ảnh văn bản, đã có nhiều phương pháp và thuật toán cho bài toán góc nghiêng văn bản. Một trong những cách tiếp cận phổ biến và dễ hiểu nhất là phương pháp hình chiếu. Phương pháp này tính histogram cho các góc khác nhau và góc lệch văn bản tương ứng là góc có histogram lớn nhất. Một thuật toàn khác phát hiện góc nghiêng văn bản là dùng biến đổi Hough. Biến đôi Hough là dụng cho một số điểm ảnh đại diện của các đối tượng và dùng một mảng tích luỹ để ước lượng góc nghiêng văn bản. Trong khi đó một số thuật toán xác định góc nghiêng văn bản bằng cách gom các nhóm đối tượng láng giềng trong ảnh vào sử dụng một vector chỉ phương cho mỗi nhóm. Ngoài các phương pháp tiếp cận phổ biến trên bài toán góc nghiêng văn bản còn được giải quyết theo một số phương pháp khác như phương pháp dùng phép toán hình thái, phương pháp dùng logic mờ, phương pháp biến đổi Fourire v.v.. Đồ án tốt nghiệp này đề cập đến một phương pháp giải quyết bài toán góc nghiêng văn bản. Con người thường căn cứ vào một số đối tượng chủ đạo trong các văn bản để kết luận góc nghiêng và góc nghiêng nếu có là góc của đường thẳng nối các điểm giữa đáy của một đối tượng chủ đạo đó. Thực tế này gợi ý cho ta một phương pháp phát hiện góc nghiêng văn bản là chỉ dựa vào những đồi tượng có kích thước chủ đạo trong ảnh để ước lượng góc nghiêng. Các đối tượng ảnh có kích thước chủ đạo được xác định thông qua việc phân loại đối tượng dựa trên các biểu đồ tần xuất kích thước của chúng. Góc nghiêng văn bản được xác định bằng cách áp dụng biến đổi Hough lên điểm giữa đáy của hình chữ nhật ngoại tiếp các đối tượng có kích thước chủ đạo trong ảnh. Việc xác định các hình chữ nhật này dựa vào biên hay chu tuyến ngoài của các đối tượng. Thuật toán phát hiện góc nghiêng văn bản được trình bày ở đây là làm việc với ảnh PCX (trắng đen). Luận văn được chia thành bốn chương: Chương 1: Tổng quan về xử lý ảnh và bài toán phát hiện góc nghiêng. Chương 2: Biên của và các phương pháp dò biên. Chương 3: Biến đổi Hough và bài toán phát hiện góc nghiêng văn bản. Chương 4: Chương trình phát hiện góc nghiêng văn bản Lời cảm ơn Trong suốt quá trình làm khoá luận tốt nghiệp vừa qua, dưới sự giúp đỡ, chỉ bảo nhiệt tình của thấy giáo hướng dẫn TS Đỗ Năng Toàn khoá luận tốt nghiệp của em đã được hoàn thành. Mặc dù đã cố gắng hết sức cùng với sự tận tâm của thầy giáo hướng dẫn song do trình độ còn hạn chế, nội dung đề tài còn quá mới mẻ đối với em nên em khó tránh khỏi những thiếu sót trong quá trình làm khoá luận. Để hoàn thành được khoá luận này. Em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo Đỗ Năng Toàn, người đã tận tình hướng dẫn em trong suốt quá trình tìm hiểu, xây dựng và phát triển bài toán khoá luận tốt nghiệp này. Và em cũng xin chân thành cảm ơn các thầy cô giáo trong khoa Công Nghệ Thông Tin trường Đại Học Dân Lập Hải Phòng đã giúp đỡ, tạo điều kiện tốt nhất để chúng em hoàn thành tốt khoá luận của mình. Em xin được gửi lời cảm ơn của mình tới gia đình và bạn bè, những người đã động viên giúp đỡ em trong quá trình làm khoá luận tốt nghiệp. Cuối cùng em rất mong nhận được sự chỉ dẫn của các thầy cô và sự góp ý của các bạn để chương trình của em được hoàn thiện hơn. Hải Phòng ngày......tháng......năm2004 Sinh viên thực hiện Cao Thi Thu Thuỷ Chương 1 Tổng quan về xử lý ảnh và bài toán phát hiện góc nghiêng 1.1. Xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh 1.1.1. Xử lý ảnh là gì? Xử lý ảnh là đối tượng nghiên cứu của lĩnh vực thị giác máy, là quá trình biến đổi từ một cảnh ban đầu sang một ảnh mới với các đặc tính và tuân theo ý muốn của người sử dụng. Xử lý ảnh có thể gồm quá trình phân tích, phân lớp các đối tượng, làm tăng chất lượng, phân đoạn và tách cạnh, gán nhãn cho vùng hay quá trình biên dịch các thông tin hình ảnh của ảnh. Cũng như xử lý dữ liệu bằng đồ hoạ, xử lý ảnh số là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ hoạ đề cập đến những ảnh nhân tạo, các ảnh này được xem xét như là một cấu trúc dữ liệu và được tạo ra bởi các chương trình. Xử lý ảnh số bao gồm các phương pháp và kĩ thuật để biến đổi, để truyền tải hoặc mã hoá các ảnh tự nhiên. Mục đích của xử lý ảnh gồm: Biến đổi ảnh, làm tăng chất lượng ảnh. Tự động nhận dạng ảnh, đoán nhận ảnh, đánh giá các nội dung của ảnh. Nhận biết và đánh giá các nội dung của ảnh là sự phân tích một hình ảnh thành những phần có ý nghĩa, để phân biệt đối tượng này với đối tượng khác. Dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu. Có thể liệt kê một số phương pháp nhận dạng cơ bản như nhận dạng cạnh của các đối tượng trên ảnh, tách cạnh, phân đoạn hình ảnh v.v.. kỹ thuật này được dùng nhiều trong y học (xử lý tế bào, nhiễm sắc thể), nhận dạng chữ trong văn bản. Hình 1: Các giai đoạn chính trong xử lý ảnh Camera Sensor Thu nhận ảnh Số hoá Phân tích ảnh Nhận dạng Hệ quyết định Lưu trữ Lưu trữ Sơ lược về ảnh nhị phân: Trong quá trình xử lý ảnh một ảnh thu nhập vào máy tính phải được mã hoá. Hình ảnh khi lưu trữ dưới dạng tập tin phải được số hoá. Tiêu chuẩn đặt ra là ảnh phải được lưu trữ thế nào sao cho các ứng dụng khác nhau có thể thao tác trên các loại dữ liệu này. Một số dạng ảnh đã được chuẩn hoá như GIF, BMP, PCX … nhìn chung mỗi kiểu lưu trữ ảnh đều có điểm riêng. Tuỳ theo vùng các giá trị xám của điểm ảnh, mà các ảnh được phân chia ra thành ảnh màu, ảnh xám, ảnh nhị phân. Khi trên một ảnh chỉ có giá trị 0 hoặc 1 thì ta nói đó là ảnh nhị phân hoặc ảnh đen trắng và các điểm ảnh của nó gọi là điểm ảnh nhị phân. Việc xử lý ảnh nhị phân là một bước tiền xử lý của các ảnh để phân đoạn và tách ra các đặc tính, đây là một phương pháp quan trọng của kĩ thuật xử lý ảnh số. Nhờ vậy, ta có thể biết được mối quan hệ giữa các điểm ảnh cũng như thực hiện các phép biến đổi ảnh không tuyến tính đạt hiệu quả; trong quá trình xử lý ảnh các phép biến đổi này làm cho việc đánh giá ảnh trở lên đơn giản. Việc đếm các điểm ảnh trên ảnh nhị phân đã qua biến đổi tạo điều kiện thuận lợi cho việc tách ra các đặc tính. Bằng cách sử dụng các ảnh nhị phân đã qua xử lý như là những mặt nạ đối với các ảnh xám, ta có thể tách ra các vùng đáng quan tâm của một ảnh xám từ tập hợp các ảnh. Để tạo ra một ảnh nhị phân, một ảnh đa cấp xám cần phải được biến đổi thành một ảnh nhị phân nhờ một quá trình phân đoạn thích hợp. Muốn thế phương pháp đơn giản nhất là phương pháp tách ngưỡng. Các giá trị nằm ở trên ngưỡng được gán giá trị trị 1 còn ở bên dưới ngưỡng thì được gán giá trị 0. Tác động xử lý ảnh nhị phân có thể được thực hiện một cách rất hiệu quả bằng chương trình trên một máy tính. Nhiều hệ thống xử lý ảnh hiện đại, được dùng cho việc xử lý ảnh nhị phân, trong đó thường là có trang bị các phần cứng đặc biệt để đạt được tốc độ xử lý cao. Đối với một ảnh thu được từ thực tế, không phải bao giờ cũng có được giá trị đúng của các điểm ảnh. Có thể quá trình thu nhận ảnh từ thiết bị ngoại vi đã xuất hiện nhiều lần và độ tương phản kém. Vì thế, thông thường để thực hiện một phép xử lý, đó là loại bỏ nhiễu và làm trơn ảnh đảm bảo cho quá trình xử lý tiếp theo được chính xác hơn. Màn hình đồ hoạ Camera Bộ xử lý tương tự Bộ nhớ ảnh Máy chủ Bộ xử lý ảnh số Màn hình Bàn phím Bộ nhớ ngoài Máy in Hình2 : Các thành phần chính của hệ thống xử lý ảnh 1.1.2 Các vấn đề cơ bản trong xử lý ảnh ảnh và điểm ảnh ảnh là một mảng số thực hai chiều (Ii j ) có kích thước (m * n), trong đó mỗi phần tử I i j ( i=1….m , j = 1…..n) biểu đố mức xám của ảnh tại vi trí (i, j )tương ứng. ảnh được gọi là nhị phân nếu các giá trị chỉ nhận 0 hoặc 1 Các điểm 4 và 8 láng giềng Các điểm 4, 8-láng giềng: Giả sử (i,j) là một điểm ảnh, khi đó các điểm 4-láng giềng là: N4 = {(i-1, j); (i+1, j); (i, j-1); (i, j+1)} Các điểm 8-láng giềng là: N8 = N4 ẩ {(i-1,j-1); (j-1, j+1); (i+1, j-1); (i+1, j+1)} Đối tượng ảnh Ta chỉ xét tới ảnh nhị phân vì mọi ảnh đều có thể đưa về dạng nhị phân bằng kỹ thuật phân ngưỡng. ký hiệu F là tập các điểm vùng F là tập các điểm nền F: là điểm đen F : là điểm trắng Quan hệ K liên thông (K= 4,8 ) là một quan hệ phản xạ, đối xứng, bắt cầu, là quan hệ tương đương . Mỗi lớp tương đương của nó biểu diễn một thành phần K liên thông của ảnh. Về sau ta gọi mõi thành phần K liên thông của ảnh là một đối tượng ảnh. a.Phép xoay chuyển toạ độ Như chúng ta đã biết trong các chương trình xử lý ảnh chúng ta có khả năng xoay ảnh với một góc nào đó để được một ảnh khác thực chất ảnh đó được xoay đi một góc nào đó. Phép dịch chuyển toạ độ Để quay được ảnh ta chuyển hệ tạo độ vào tâm của ảnh xp = x – x1 yp = y – y1 Với : (xp,yp): là toạ độ của ảnh trong hệ trục mới (x,y): Là toạ độ của ảnh trong hệ trục cũ x1: Là độ lệch của toạ độ cũ so với toạ độ mới mà ta tịnh tiến theo trục x x2: Là độ lệch của toạ độ cũ so với toạ độ mới mà ta tịnh tiến theo trục y Phép xoay một điểm Để có thể xoay được ảnh ta phải dùng cách là tính từng điểm ảnh của ảnh mới là tương ứng với vị trí nào của ảnh cũ để có thể lấy được màu của chúng Để xoay một điểm ảnh ta có hai cách quay là quay theo chiều dương ngược kim đồng hồ và quay theo âm cùng chiều kim đồng hồ. Quay theo chiều dương có công thức là : xp=x*cosA-y*sinA yp=y*cosA+x*sinA Quay theo chiều âm có công thức là : xp=x*cosA+y*sinA yp=y*cosA-x*sinA Trong đó : xp, yp là điểm ảnh trên ảnh mới. (x,y) là điểm ảnh trên ảnh cũ tương ứng A góc quay của ảnh cũ so với ảnh mới Chú ý - Khi quay ta phải được một ảnh mới là ảnh cũ xoay đi một góc A. Nhưng trong thực tế, thì ta phải tạo ra một ảnh mới có kích thước lớn hơn và kích thước của ảnh mới sẽ là : Width={Width*cosA}+{Height*sinA} Height={Width*sinA}+{Height*cosA} Khi quay hình thì ta không thể ánh xạ từ ảnh cũ sang ảnh mới mà ta phải làm phép toán ngược là tìm xem điểm ảnh của mới đó ứng với điểm ảnh nào của ảnh cũ, nếu không trong trường hợp tính toán số nguyên sẽ có sai số và thực chất là một điểm ảnh của ảnh mới sẽ bị mất dữ liệu vì không được tính đến. b. Kỹ thuật phóng to, thu nhỏ ảnh Khi ảnh quá lớn chúng ta muốn nhìn toàn bộ ảnh thì chúng ta phải thu nhỏ ảnh lại và ngược khi ta muốn xem chi tiết một bộ phận nào đó của ảnh thì ta phải phóng to nó lên. Kỹ thuật phóng to ảnh Khi phóng to ảnh với một tỉ lệ k nào đó ta thu được ảnh mới to gấp k lần ảnh cũ (k là độ phóng của ảnh) như thế ảnh mới sẽ có kích thước là : Height=Height*k Width=Widht*k Việc tính các điểm ảnh tương ứng của ảnh mới sẽ được tính theo công thức: xp=x/k yp=y/k Kỹ thuật thu nhỏ ảnh Tương tự như phóng to ảnh, khi thu nhỏ ảnh ta thu được ảnh mới giống ảnh cũ nhưng có kích thước nhỏ hơn ảnh cũ. Kích thước của ảnh mới là : Height=Height/k Width=Widht/k Việc tính các điểm ảnh tương ứng của ảnh mới sẽ được tính theo công thức: xp=x*k yp=y*k 1.2. Bài toán phát hiện góc nghiêng 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 góc nghiêng như một bước đầu tiên và cũng không thể tránh khỏi. 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ác thuật toán phát hiện góc nghiêng văn bản thường được xây dựng cho các hệ thống phân tích ảnh văn bản cụ thể vì vậy thường chỉ giải quyết cho một số loại văn bản. sau đây. Sau đây là một số hướng tiếp cận phổ biến cho bài toán phát hiện góc nghiêng văn bản. 1.2.1 Thuật toán dựa vào hình chiếu Đây là một trong những phương pháp phổ biến nhất trong phát hiện góc nghiêng văn bản. ý tưởng chính của phương pháp này là tính Histogram cho tất cả các góc lệch. Histogram của một góc là số điểm đen trong ảnh sao cho các điểm này nằm trên những đường thẳng có cùng một hướng tương ứng với góc đó. Sau đó, dùng một hàm chi phí áp dụng cho các giá trị Histogram này. Góc nghiêng văn bản tương ứng với góc có giá trị hàm chi phí cực đại. Các thuật toán phát hiện góc nghiêng văn bản dựa vào hình chiếu thường bao gồm các bước chính sau: Dùng một hàm rút gọn F để chuyển ảnh đầu vào thành một tập các bộ ba(x,y,w) trong đó (x,y) là toạ độ của một điểm ảnh đại diện cho một đối tượng và w là trọng số của điểm đó. ở đây, điểm đại diện được hiểu theo nghĩa là điểm biểu diễn các kí tự trong các đối tượng của ảnh. Trọng số w sẽ được đề cập sau và thường phụ thuộc vào từng thuật toán. Một hàm P dùng chiếu các điểm tìm được ở trên vào một mảng đếm A theo các góc chiếu khác nhau. ứng với mỗi góc j có một mảng Aj dùng lưu số điểm đại diện. Mảng A j là mảng một chiều, phần tử Aj[ r ] sẽ cho biết số điểm đại diện nằm trên đường thẳng tạo với trục ox góc j và khoảng cách từ gốc toạ độ tới đường thẳng đó là r. Sau khi tính được mảng Aj [r], áp dụng một hàm tối ưu hoá W cho các giá trị của mảng này theo một tiêu chuẩn nào đó. Cuối cùng góc lệch của văn bản là góc tương ứng có giá trị hàm tối ưu hoá cực đại. 1.2.2 Các thuật toán dựa vào biến đổi Hough ( Hough Transform) Sự khác nhau chủ yếu của các thuật toán theo phương pháp này chính là việc xây dựng các hàm rút gọn F và tồi ưu hoá W. Một hướng tiếp cận phổ biến khác cho bài toán phát hiện góc nghiêng văn bản là phương pháp dùng biến đổi Hough. Những 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 toạ độ tới đường thẳng đó và j là góc nghiêng của đường thẳng đó so với trục tung. 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 luỹ Histogram. số các điểm đen được áp dụng biến đổi Hough tuỳ 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ỉ những điểm thoả mãn một số rằng buộc nào đó hoặc chỉ là đáy của các đối tượng ảnh. Liên quan đến hướng tiếp cận này là những thuật toán được đề xuất bởi các tác giả: Hinds, Jiang, Nakano, nhóm Srihari và Govidaraju….. Trong số đó, 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ừ nào 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 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ò nhiều đối tượng phi ký tự nhiễu, bảng biểu hay ảnh. 1.2.3 Các thuật toán phân tích láng giềng Một hướng tiếp cận khác của bài toàn phát hiện góc nghiêng văn bản là phương pháp phân tích láng giềng thân cân cận hay láng giềng gần nhất. Các thuật toán liên quan đến phương pháp này được dề xuất bởi các tác giả: Hashirume, ơ Goman, Tiang, loibios, nhóm Yue Lu và Chew Lim Tan, nhóm pal và Chaudhuri, nhóm Shivakumara, Kumar, Guru. Theo hướng tiếp cận này, các thuật toán trước hết dùng các kỹ thuật xác định biên cho các đối tượng riêng lẻ. Sau đó, với mỗi đối tượng xác định một số láng giềng gần nó nhất, dùng mộ một vector . tơ định hướng với hai đầu là hai điểm được chọn từ hai trong số các đối tượng này để xác định góc nghiêng. Hai đối tượng là láng giềng thân cận của nhau nếu kích thước của chúng phải thuộc một khoảng nào đó và khoảng cách giữa chúng cũng thoả mãn bé hơn một ngưỡng nào đó được định nghĩa trước. Hai điểm đại diện cho hai đối tượng cò thể là các toạ độ giữa đáy cảu chúng, có thể là toạ độ dưới trái nhưng cũng có thể là tâm hình chữ nhật chứa các đối tượng đó tuỳ từng thuật toàn cụ thể. Vector của mỗi một nhóm láng giềng thân cận sẽ cho một góc lệch tương ứng cho nhóm đó. Thông thường, các thuật toán theo phương pháp này dùng một mảnh tích luỹ để lưu Histogram cho các góc lệch này. Nghĩa là, giá trị của một phần tử mảng tích luỹ sẽ cho biết nhóm láng giềng và vector định hướng cho góc bằng với chỉ số của phần tử mảng đó. Góc lệch của văn bản là góc tương ứng với phàn tử Histogam lớn nhất. Việc gom các đối tượng thành các cặp láng giềng gần nhất mục đích để gom các cặp ký tự kề nhau trong các dòng văn bản và vector giữa các đối tượng này cho biết góc của đường thẳng đi qua đáy của nhóm ký tự đó. Tuy nhiên, theo đó, trong trường hợp ảnh có nhiều nhiễu hoặc với ảnh có độ phân giải thấp, các ký tự chữ cái được chia thành nhiều phần riêng biệt, thì các vector định hướng sẽ không phản ánh dược đùng hướng lệch của văn bản nữa. Hashizume lựa chọn số đối tượng trong nhóm láng giềng là hai. Trong khi đó Ơ goman đế xuất một phương pháp gom các láng giềng với số lượng lớn hơn, K đối tượng trong một cụm láng giềng. Mục đích để gom các ký tự trong một từ thành một cụm và vector định hường là vector đi qua nhiều nhất các điểm đại diện của các đối tượng. Vì vậy vector định hướng sẽ phản ánh chính xác hơn góc lệch của các dòng văn bản. Tuy nhiên phương pháp của Ơ Gorman vẫn gặp khó khăn vì các ký tự được chia thành nhiều phần và đặc biệt với những góc nghiêng khá lớn. Khi khoảng cách giữa các ký tự trong văn bản lớn thì rất có thể các láng giềng tìm được trong thuật toán không phải là các ký tự nằm trên cùng một dòng văn bản, thay vào đó là các ký tự năm trên các dòng văn bản khác. Vì vậy thuật toán sẽ đưa ra một góc lệch sai cho văn bản. Cũng theo hướng cải tiến của Ơ gorman, Liobios đé xuất một phương pháp gom các láng giềng theo số lượng nhiều nhất có thể. Phương pháp này tương tự như giải quyết bài toán xác định các dòng cho một văn bản. Vì vậy, hạn chế chính của Ơ Gorman là sự phụ thuộc vào cả khoảng cách tứ cấc dòng văn bản lẫn phông chữ tức là các đối tượng phải cố kích thước gần bằng nhau và chỉ nên áp dụng với những văn bản có chứa nhiều ký tự chữ cái. Một thuật toán được xem là có nhiều cải tiến nhất cho hướng tiếp cận này được đề xuất bởi hai tác giả Yue Lu và Chew Lim Tan thuộc khoa học máy tính trường Đại Học Quốc Gia singapore. Thuật toán này cải tiến cách gom các đối tượng thành các láng giềng gần nhất theo một số tiêu chí đồng thời cho phép thay đổi số láng giềng trong quá trình xử lý. Đại diện cho lớp các thuật toán cũng liên quan đến hướng tiếp cận láng giềng gần nhất. 1.2.4 Phương pháp dùng phép toán hình thái Một số thuật toán xác định góc nghiêng sử dụng các phép toán hình thái. í tưởng chủ đạo của phương pháp này xuất phát từ đặc điểm của phép đóng ảnh là có phả năng gắn các đối tượng gần nhau. Các thuật toán này thường dùng phép đòng nhiều lần với mục đích nối các dòng văn bản với nhau. Giai đoạn tiếp theo là dùng các vector chỉ phương của các dòng xác định góc nghiêng cho văn bản tương tự như trong phương pháp phân tích láng giềng. Theo hướng tiếp cận này các thuật toán được đế xuất bởi các tác giả: L.Naman, nhóm S.Chen và R.M.Haralick….Thuật toán của L.Najman có thể xem là cải tiến nhất trong số các thuật toán dùng phép toán hình thái xác định góc nghiêng văn bản. Chương 2 Biên và các phương pháp dò biên 2.1. Biên của đối tượng ảnh Một cách tổng quát có thể nói rằng bất kỳ một hệ thống xử lý ảnh nào cũng tuân theo một giai đoạn sau : Trích chọn đặc trưng Phân đoạn ảnh Phân loại Phân loại ảnh đầu vào cho quá trình tiền xử lý Con người thường nhìn nhận sự vật theo hai cách hoặc là dựa vào biên hoặc là dựa vào xương của chúng. Chẳng hạn, ta dựa vào biên khi quan sát các đối tượng như ao, hồ hoặc một cái xe ôtô. Nhưng nếu để phân biệt một khúc sông với những đối tượng khác trên bản đồ địa hình thì ta dựa vào xương của nó. Vì vậy, cùng với xương thì biên có một tầm quan trọng đặc biệt trong phân tích ảnh. Biên là một vấn đề chủ yếu trong phân tích ảnh vì các kĩ thuật phân đoạn ảnh chủ yếu dựa vào biên. Có thể thấy tầm quan trọng của biên khi ta theo dõi một hoạ sĩ làm việc. Giả sử, anh ta muốn vẽ một quả bóng, nét đầu tiên được phác hoạ chính là đường biên của quả bóng sau đó mới đến các múi bên trong. Như vậy, mới chỉ nhìn biên của sự vật ta cũng hình dung ít nhiều về nó và vì vậy có thể phân biệt được với các sự vật khác. Một điểm ảnh được xem là biên của một đối tượng nếu ở đó có sự thay đổi đột ngột về mức xám. Tập hợp các điểm biên tạo thành biên hay một đường bao của ảnh. Trong một ảnh nhị phân một điểm ảnh thuộc biên nếu đó là một điểm đen và có ít nhất một điểm trắng lân cận. Nhìn chung, về mặt toán học có thể xem điểm biên của ảnh là một điểm mà ở đó có sự thây đổi đột ngột về độ sáng. Xuất phát từ cơ sở đó, người ta thường sử dụng hai phương pháp phát hiện biên sau : Phương pháp phát hiện biên trực tiếp là làm nổi biên dựa vào sự biến thiên độ sáng của ảnh. Kĩ thuật chủ yếu được dùng là dụa vào đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp Gradient, nếu lấy đạo hàm bậc hai ta có phương pháp Laplace. Phương pháp phát hiện biên gián tiếp. Nếu bằng một cách nào đó ta phân biệt được ảnh bằng các vùng thì đường phân ranh giới giữa các vùng đó chính là biên. Hai kỹ thuật dò biên và phân vùng các đối tượng là hai bài toán đối ngẫu. Thật vậy, dò biên để phân lớp đối tượng ảnh , nếu phân lớp song thì có nghĩa là đã phân vùng được các đối tượng ảnh và ngược lại, khi đã phân vùng được các đối tượng ảnh thì cũng đã phân lớp được các đối tượng ảnh và ta có thể phát hiện được biên. Phương pháp phát hiện biên trực tiếp tỏ ra khá hiệu quả và ít chịu ảnh hưởng của nhiễu, song nếu sự vật có sự biến đổi độ sáng không đột ngột, phương phấp này tỏ ra khá hiệu quả. Phương pháp phát hiện biên gián tiếp tuy khó cài đặt nhưng lại áp dụng rất tốt cho những ảnh có sự biến thiên độ sáng bé. 2.2. Các phương pháp dò biên trực tiếp 2.2.1. Phương pháp Gradient Theo định nghĩa, gradient là một vector có các thành phần biểu thị tốc độ, thay đổi giá trị của điểm ảnh theo hai hướng x và y Với Dx, Dy là các khoảng cách giữa các điểm theo hướng x và hướng y (tính theo số điểm). Trong thực tế người ta thường lấy Dx = Dy = 1. Nếu theo toạ độ cực ta có: Hướng sảy ra khi:  Chú ý rằng, do lạm dụng về ngôn từ, tuy ta nói lấy đạo hàm của ảnh, nhưng thực ra chỉ là mô phỏng và xấp xỉ đạo hàm bằng kỹ thuật nhân chập (cuộn). Do ảnh số là tín hiệu rời rạc, do vậy đạo hàm không tồn tại. Trong phương pháp Gradient, người ta chia nhỏ thành hai kỹ thuật: kỹ thuật gradient và kỹ thuật la bàn. Kỹ thuật gradient dùng toán tử gradient lấy đạo hàm theo một hướng; còn kỹ thuật la bàn dùng toán tử la bàn lấy đạo hàm theo tám hướng chính: Bắc, Nam, Đông, Tây, Đông Nam, Đông Tây, Tây Nam, Tây Bắc. 2.2.1.1. Kỹ thuật Gradient Kỹ thuật gradient sử dụng hai mặt nạ H1 và H2 trực giao. Ta xét một số toán tử sử dụng kỹ thuật gradient tiêu biểu: Robert, Sobel, Prewitt,... 2.2.1.1.1.Toán tử Robert Kỹ thuật này sử dụng hai mặt nạ: Khi đó ta áp dụng toán tử Robert với ảnh nguồn I ta có ảnh kết quả Ikq như sau: Ikq = I Ä H1 + I Ä H2 Ký hiệu Ä là phép nhân chập (cuộn), được định nghĩa như sau: Giả sử ta có ảnh I, kích thước MxN ; ma trận T, có kích thước mxn. Khi đó ảnh I được cuộn theo mẫu T bởi công thức: Hoặc 2.2.1.1.2. Toán tử Prewitt Sử dụng hai mặt nạ: Giả sử ta có ảnh I, khi đó phương pháp gradient sử dụng toán tử Prewitt ta có ảnh kết quả như sau: Ikq = I Ä Hx + I Ä Hy 2.2.1.1.3. Toán tử Sobel Sử dụng hai mặt nạ: Giả sử ta có ảnh I, khi đó phương pháp gradient sử dụng toán tử Sobel ta có ảnh kết quả như sau: Ikq = I Ä Hx + I Ä Hy 2.2.1.2. Kỹ thuật la bàn Có nhiều toán tử la bàn khác nhau. Ta xét chi tiết một toán tử đó là toán tử Kirsh. Toán tử này sử dụng tám mặt nạ: Giả sử ta có ảnh I, khi đó phương pháp gradient sử dụng toán tử Kirsh cho ta ảnh kết quả là: 2.2.2. Phương pháp Laplace Các phương pháp sử dụng đạo hàm bậc nhất làm việc khá tốt khi mà độ sáng thay đổi rõ nét. Khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp tách cho hiệu quả hơn là phương pháp sử dụng đạo hàm bậc hai mà trong phần trên gọi là phương pháp Laplace. Toán tử đạo hàm bậc hai được định nghĩa như sau: Ta có: Do đó: Từ đó ta có mặt nạ: Thông thường người ta thường lấy các ma trận mặt nạ sau: Giả sử ta có ảnh I, khi đó phương pháp Laplace cho ta ảnh kết quả là: Ikq = I Ä H 2.3. Phương pháp dò biên tổng quát 2.3.1. Định nghĩa chu tuyến Định nghĩa chu tuyến Chu tuyến của đối tượng ảnh E được định nghĩa là dãy các điểm ảnh P0, p1, p2......pn của E thoả mãn " i= 1,2...,n $ Q thuộc E với Q là 4 láng giềng của Pi và Pi-1,Pj-1 là 8 láng giềng của Pi. Trong đó P0 = Pn khi đó ta cũng gọi n là độ dài chu vi của chu tuyến. Trong đó 4 láng giềng được định nghĩa là các điểm trực tiếp bên trên, dưới, trái, phải của một điểm.Và 8 láng giềng là những điểm 4 láng giềng hoặc các điểm trên trái, trên phải, dưới trái dưới phải trực tiếp của một điểm Chu tuyến đối ngẫu Chu tuyến C = và C - = được gọi là chu tuyến đối ngẫu của mhau nếu mọi i = 0, n – 1 tồn tại j và k sao cho : Pi , Qj Là 4 láng giềng của nhau Pi+1 , Qk là 4 láng giềng của nhau Qj , Qk Là 8 láng giềng của nhau Nếu Pi là vùng thì Qj là nền và ngược lại. Chu tuyến trong Chu tuyến C được gọi là chu tuyến trong nếu và chỉ nếu: Chu tuyến đối ngẫu C’ của nó là chu tuyến của các điểm nền. Độ dài chu tuyến C’ nhỏ hơn độ dài chu tuyến C Chu tuyến ngoài Chu tuyến C được gọi là chu tuyến ngoài nếu và chỉ nếu: Chu tuyến đối ngẫu C’ của C là chu tuyến của các điểm nền. Độ dài chu tuyến C’ lớn hơn độ dài chu tuyến C Từ định nghĩa, ta thấy chu tuyến ngoài của một đối tượng là một đa giác có độ dày bằng một bao quanh đối tượng Chu tuyến C Chu tuyến C’ Chu tuyến C Chu tuyến ngoài Chu tuyến trong Chu tuyến C ‘ Ví dụ về chu tuyến đối ngẫu Ví dụ về chu tuyến trong và chu tuyến ngoài của một đối tượng 2.3.2. Phương pháp dò biên tổng quát Giả sử ảnh đã được phân vùng. Về cơ bản thuật toán dò biên trong một vùng bao gồm các bước cơ bản sau: Bước 1: Xác định điểm biên xuất phát. Bước 2: Dự báo điểm biên tiếp theo: bn+1 = T(bn) Bước 3: Lặp lại bước hai cho đến khi nào gặp điểm xuất phát Do xuất phát từ một tiêu chuẩn và định nghĩa khác nhau về điểm biên, quan hệ liên thông, nên các toán tử dò biên cho ta những đường biên với sắc thái khác nhau. Kết quả tác động của toán tử dò biên lên một điểm biên (bn) là một điểm biên (bn+1), là điểm 8-láng giềng của bn. Thông thường các toán tử này được xây dựng như một hàm đại số bool trên các 8-láng giềng của bn. Mỗi cách xây dựng toán tử đều phụ thuộc vào định nghĩa quan hệ liên thông về điểm biên, và sẽ gây khó khăn cho việc khảo sát các tính chất của đường biên. Ngoài ra vì mỗi bước dò biên đều phải kiểm tra tất cả 8-láng giềng của mỗi điểm nên toán tử thường kém hiệu quả. Để khắc phục hạn chế trên ta sẽ phân tích toán tử dò biên thành hai bước: Xác định cặp nền vùng tiếp theo. Lựa chọn điểm biên. Bởi vậy thuật toán tổng quát sẽ trở thành: Bước 1: Xác định cặp nền vùng xuất phát. Bước 2: Xác định cặp nền vùng tiếp theo. Bước 3: Lặp lại bước hai cho đến khi gặp cặp nền vùng xuất phát. Khái niệm cặp vùng nền được định nghĩa gồm một điểm vùng và một điểm nền, trong đó nếu điểm vùng đi được một vòng chu tuyến thì điểm nền cũng đi được một vòng chu tuyến đối ngẫu. Các bước được mô tả cụ thể như sau: Bước 1: Việc xác định cặp nền vùng xuất phát được xác định bằng cách duyệt ảnh lần lượt từ trên xuống dưới, từ trái qua phải, rồi kiểm tra điều kiện theo định nghĩa ánh xạ cặp nền vùng (chỉ mang tính quy ước). ở đây ta vùng xuất phát là điểm vùng đầu tiên duyệt đến. Điểm nền xuất phát là điểm ngay sau điểm vùng xuất phát (theo chiều ngang). Bước 2: Ta gọi ánh xạ cặp nền vùng tiếp theo là toán tử dò biên. Cách tìm cặp nền vùng tiếp theo như sau: lấy tâm là điểm vùng hiện tại, ta quay theo chiều kim đồng hồ bắt đầu từ điểm nền hiện tại, cho đến khi gặp một điểm vùng là 8-láng giềng của điểm vùng hiện tại thì dừng lại, điểm đó chính là điểm vùng tiếp theo. Vẫn lấy tâm là điểm vùng hiện tại, điểm nền tiếp theo là điểm 8-láng giềng của điểm vùng hiện tại ngay sau điểm vùng tiếp theo quay ngược chiều kim đồng hồ. Bước 3: Cặp nền vùng tiếp theo tìm được trong bước hai được coi là cặp nền vùng hiện tại. Sau đó lặp lại bước hai. Bước 3 được lặp lại cho đến gặp cặp nền vùng xuất phát. Chương 3 Biến đổi hough và bài toán phát hiện góc nghiêng văn bản Trong các chương trước, chúng ta đã tìm hiểu một số thuật toán phát hiện góc nghiêng văn bản theo các hướng tiếp cận khác nhau. Nhìn chung hầu hết các thuật toán chỉ làm việc tốt cho một số trường hợp ảnh đầu vào. Trong đó một số thuật toán chỉ chính xác với các ảnh đầu vào có góc lệch bé hoặc có kích thước bé, một số thuật toán không chính xác với những ảnh có ít ký tự chữ cái hoặc nhiều nhiễu, có những thuật toán dựa vào phông chữ và nhiều thuật toán có chi phí rất lớn. Để xây dựng được thuật toán xác định góc nghiêng văn bản, trước hết ta phải dùng kỹ thuật dò biên để xác định chu tuyến cho các đối tượng ảnh. Các hình chữ nhật chứa các đối tượng này được lưu lại cho các quá trình xử lý tiếp theo. Dựa váo sơ đò phân bố các kích thước của các đối tượng, xác định các ngưỡng kích thước để phân loại các đối tượng và lựa chọn một số đối tượng có kích thước chủ đạo trong ảnh rồi dùng biến đổi Hough áp dụng cho các điểm đại diện là điểm giữa đáy của hình chữ nhật ngoại tiếp các đối tượng này. Cuối cùng góc nghiêng văn bản sẽ được ước lượng từ mảng tích luỹ trong quá trình áp dụng biến đổi Hough. 3.1. Phát hiện góc nghiêng văn bản từ biên của đối tượng Như đã nói ở các phần trên, góc nghiêng được xác định dựa vào biến đổi Hough. Và ở đây, ta chỉ áp dụng biến đổi Hough cho những điểm giữa đáy của hình chữ nhật ngoại tiếp các đối tượng có kích thước chủ đạo trong ảnh. Như vậy công việc đầu tiên cần thực hiện là xác định được các hình chữ nhật ngoại tiếp các đối tượng hay nói cách khác là xác định biên của đối tượng. Trong các chương trước chùng ta đã đề cập tới biên của một đối tượng ảnh và các phương pháp xác định biên. ở đây, chúng ta dùng thuật toán dò biên tổng quát để xác định biên cho các đối tượng trong ảnh văn bản. Hình chữ nhật ngoại tiếp đối tượng sẽ được xác định ngay sau khi dò biên cho đối tượng đó. Hình 3: ví dụ về một văn bản nghiêng Trong cài đặt, các hình chữ nhật ngoại tiếp là những bản ghi hay cấu trúc gồm các trường top, lef, bot và rig tương ứng sẽ cho biết các toạ độ trên, trái, dưới và phải của một đối tượng ảnh hay chính xác là toạ độ các điểm biên của đối tượng đó. Giá trị của các trường này được xác định trong quá trình xây dựng các điểm biên. Như vậy mỗi khi dò xong biên cho một đối tượng ảnh, ta được một hình chữ nhật ngoại tiếp đối tượng ảnh đó và điểm giữa đáy của hình chữ nhật sẽ được xác định từ các giá trị top, lef, bot, rig tương ứng. 3.2. Biến đổi Hough và phát hiện góc nghiêng văn bản 3.2.1 Đường thẳng Hough trong toạ độ cực x y m j Hình 4. Đường thẳng trong toạ độ cực Mỗi đường thẳng trong toạ độ cực được xác định bởi cặp (r, j) như hình vẽ r Giả sử (x,y) là một điểm thuộc đường thẳng thì ta tìm công thức ràng buộc giữa x, y, r và j. Ta có: r = (m + y) . sinj Mặt khác ta có: tgj = x/m Û sinj / cosj = x/m Û m.sinj = x.cosj Do đó ta có mối liên hệ giữa ( x, y ) và (r, j ) như sau : r = x.cosj + y.sinj Như vậy, nếu N điểm (x0, y0) nằm trên một đường thẳng thì ta có phương trình : r = x0.cosj0 + y0.sinj0 , mọi i = 0...n Biến đổi Hough ánh xạ N điểm này thành N đường sin trong toạ độ cực mà các đường này đều đi qua (r0, j0 ). Giao điểm (r0, j0 ) của N đường sin sẽ xác định một đường thẳng trong mặt phẳng. Như vậy, những đường thẳng đi qua điểm (x,y) sẽ cho duy nhất một cặp (r, j ) và có bao nhiêu đường qua (x,y) thì có bấy nhiêu cặp giá trị (r, j). 3.2.2 áp dụng biến đổi Hough trong phát hiện góc nghiêng văn bản ý tưởng của việc áp dụng biến đổi Hough trong phát hiện góc nghiêng văn bản là dùng một mảng tích luỹ để đếm số điểm ảnh nằm trên một đường thẳng trong không gian ảnh. Mảng tích luỹ là một mảng hai chiều với chỉ số hàng của mảng cho biết góc lệch j của một đường thẳng và chỉ số cột chính là giá trị r, khoảng cách từ gốc toạ độ tới đường thẳng đó. Sau đó tính tổng số điểm ảnh nằm trên đường thẳng song song nhau theo các góc lệch thay đổi. Góc nghiêng văn bản tương ứng với góc có tổng giá trị mảng tích luỹ cực đại. Theo biến đổi Hough, mỗi một đường thẳng trong mặt phẳng tương ứng được biểu diễn bởi một cặp (r, j). Giả sử ta có một điểm ảnh (x,y) trong mặt phẳng, vì qua điểm ảnh này có vô số đường thẳng, mỗi đường cho một cặp (r, j) nên với mỗi điểm ảnh ta sẽ xác định được một số cặp (r, j) thoả mãn phương trình Hough. 0 x y R1 = x.cosj + y.sinj Hough[j][r1] = 3 Hough[j][r2] = 4 Hình 5: ứng dụng biến đổi Hough trong phát hiện góc nghiêng văn bản R2 = x.cosj + y.sinj j Nhìn vào hình trên cho ta thấy, đây là cách minh hoạ dùng biến đổi Hough để phát hiện góc nghiêng văn bản. Giả sử ta có một số điểm ảnh, đây là những điểm giữa đáy hình chữ nhật ngoại tiếp các đối tượng đã được lựa chọn từ những bước trước. ở đây ta thấy, trên mặt phẳng có hai đường thẳng song song nhau. Đường thứ nhất có 3 điểm ảnh lên giá trị mảng tích luỹ bằng 3, đường thẳng thứ hai có 4 điểm ảnh lên giá trị mảng tích luỹ bằng 4. Do đố, tổng giá trị mảng tích luỹ cho cùng góc j trong trường hợp này bằng 7. Gọi Hough[360][max] là mảng tích luỹ, giả sử M và N tương ứng là chiều rộng và chiều cao của ảnh, ta có các bước chính trong quá trình dùng biến đổi Hough để xác định góc nghiêng văn bản như sau: Bước 1: Khai báo mảng chỉ số Hough[j][r] với 00 Ê j < 3600 Gán giá trị 0 cho tất cả các phần tử mảng. Bước 2: Với mỗi điểm (x, y) là điểm đáy của hình chữ nhật ngoại tiếp đối tượng : Với mỗi ji từ 0 đến 360 tính giá trị ri theo công thức Ri = x.cosji + y.sinji Làm tròn giá trị ri thành số nguyên gần nhất là r0 Tăng giá trị của phần tử mảng Hough[ji][r0] lên một đơn vị. Bước 3: Trong mảng Hough[j][r], tính tổng giá trị các phần tử theo từng hàng và góc nghiêng văn bản tương ứng hàng có tổng giá trị lớn nhất. Do số phần tử của một phần tử mảng Hough[j0][r0] chính là số điểm ảnh thuộc đường thẳng r0 = x.cosj0 + y.sinj0 vì vậy tổng số phần tử của một hàng chính là tổng số điểm ảnh thuộc các đường thẳng tương ứng được biểu biển bởi góc j của hàng đó. Do đó, góc nghiêng của văn bản tương ứng là hàng có tổng giá trị các phần tử mảng tích luỹ lớn nhất. 3.3. Chỉnh sửa góc nghiêng văn bản Sau khi xác định được góc nghiêng cho toàn văn bản. Để chỉnh sửa góc nghiêng cho văn bản ta quay lại ảnh với độ lệch đó. Quay ảnh là một trong những kỹ thuật phổ biến trong mọi hệ thống xử lý ảnh. Thuật toán quay ảnh đơn giản là chuyển một điểm ảnh (x,y) từ ảnh ban đầu thành điểm ảnh mới có toạ độ (x1, y1) trong ảnh kết quả với x1,y1 được xác định theo công thức: X1 = x.cosj + y.sinj Y1 = y.sinj - x.cosj 0 y x P ( x1, y1) P ( x, y) Hình 6: Quay một điểm ảnh quanh gốc toạ độ j Tuy nhiên một vấn đề kinh điển trong kỹ thuật quay ảnh mà bất kỳ hệ thống xử lý ảnh nào cũng gặp phải là giải quyết những lỗ hổng hay những điểm không được gán màu trong ảnh kết quả trong quá trình quay. Lý do dẫn đến sự xuất hiện những lỗ hổng chính là tứ công thức quay ảnh. Do phải làm tròn các giá trị thành số nguyên nên trong ảnh đích có một số điểm ảnh không tương ứng được ánh xạ từ ảnh gốc sang những lỗ hổng. Để giải quyết vấn đề lỗ hổng, ta duyệt ảnh đích ta gán màu cho chúng dựa vào màu của các láng giềng. Với ảnh đen trắng, các lỗ hổng được gán màu đen. 3.4 Thuật toán phát hiện góc nghiêng văn bản Về cơ bản thuật toán phát hiện góc nghiêng văn bản gồm các bước chủ yếu sau: Bước 1: Duyệt ảnh theo thứ tự từ trên xuống và từ trái qua phải, với mỗi điểm ảnh. Nếu gặp một điểm vùng (x,y) chưa xét thực hiện các bước: + áp dụng thuật toán xác định chu tuyến với đầu vào là (x,y) và màu tương ứng. + Dùng hình chữ nhật ngoại tiếp kiểm tra nếu đối tượng có có kích thước bình thường áp dụng biến đổi Hough cho điểm giữa của hình chữ nhật. Nếu gặp một điểm đã xét, tìm một điểm ảnh trên cùng dòng có nhãn bằng với điểm ảnh đanh xét và tiến hành duyệt lại từ đây. Bước 2: Dựa vào kết quả của phép biến đổi Hough ước lượng góc nghiêng cho văn bản. Bước 3: Dựa vào góc nghiêng xác định được tứ bước 2 áp dụng thuật toán quay ảnh. Tuy nhiên, nếu áp dụng biến đổi Hough cho tất cả các đối tượng của ảnh, thì thuật toán sẽ không chính xác hoặc là tốn nhiều thời gian thực hiện hoặc cả hai. Vì Vậy chúng ta không áp dụng biến đổi Hough cho tất cả các đối tượng sau khi tìm được chu tuyến của chúng mà loại ra những đối tượng có kích thước kỳ lạ, hoặc là rất bé so với ký tự thường….. Mô hình giải thuật: Xác định các đối tượng ảnh và hình chữ nhật chứa nó Lấy điểm trung bình cạnh đáy của từng hình chữ nhật Xác định các đối tượng ảnh và hình chữ nhật chứa nó Xoay văn bản với góc tìm được XĐ đường thẳng áp dụng biến đổi Hough để xác định đường thẳng từ tập điểm vừa tìm được F T Chương 4 chương trình phát hiện góc nghiêng văn bản 4.1 Sơ đồ chức năng của chương trình Hệ thống Mở tệp Đóng tệp Thoát ảnh gốc Dò biên Chỉnh văn bản Quay ngược kim đồng hồ Quay cùng chiều kim đồng hồ Phóng to ảnh Thu nhỏ ảnh Làm béo Làm gầy Tăng độ sáng Giảm độ sáng Thuật toán được cài đặt bằng ngôn ngữ C ++ trên Windows trong môi trường visual C ++ của Microsoft. 4.2. Thiết kế Menu Menu chính của chương trình Menu chi tiết chương trình 4.3. Thiết kế thanh công cụ ý nghĩa các thanh công cụ trên 4.4. Giao diện chính của chương trình Sau đây là giao diện chính của chương trình phát hiện góc nghiêng văn bản và chỉnh lại văn bản.  Giả sử chương trình đọc một ảnh và lần lượt thực hiện việc dò biên, phát hiện góc nghiêng và quay lại văn bản. Chức năng dò biên của đối tượng ảnh. Chương trình phát hiện ghiêng văn bản và đưa ra hộp thông báo. 4.5. Mô tả các lớp và các hàm thành phần Sau đây là mã nguồn của một số Modul chính trong chương trình được viết bằng ngôn ngữ lập trình Visual C ++ void WINAPI Dobien(HDIB hDIB,CDC *pDC) { n_t=0;n_n=0; CPoint tam[10000]; ::Xoa(pDC); LPSTR lpDIB=(LPSTR)::GlobalLock(hDIB); LPBITMAPINFOHEADER pDIB = (LPBITMAPINFOHEADER)(lpDIB); DWORD wBytes = (WORD)WIDTHBYTES(pDIB->biWidth*pDIB->biBitCount); CPoint moi,dau; BYTE dir,next_dir; DWORD i,j; CString a; long nn=0; long nv=0; long dem; for(i=0;i<S;i++) for(j=0;j<S;j++) cx[i][j] = 1; long t=0,n=0; int k; for( i=0;i<H;i++) for(j=0;j<W;j++) if(GetPixel1(lpDIB,j,i)==0&& cx[i][j]) { nn=0;nv=0; if(GetPixel1(lpDIB,j-1,i)==0)continue; moi.x=j; moi.y=i; dir=4; dau=moi; cx[i][j]=0; dem=1; while(1) { ++dem; nv++; next_dir=Next1(lpDIB,moi,dir); if(next_dir==8)break; moi += orient[next_dir]; k=0; for(int x=(dir+7)%8;x!=next_dir;x=(x+7)%8) { if((k%2)==0) { nn++; tam[nn]=moi+orient[x]; } k++; } dir=((((next_dir+1)/2)*2)%8+2)%8; cx[moi.y][moi.x] = 0; if(dem>=10000)break; if(moi==dau)break; } if(nn>nv) { for(long h=0;h<nn;h++) { pDC->SetPixel(tam[h],0); NN[n_n+h]=tam[h]; } n_n+=nn; } else { for(long h=0;h<nn;h++) { pDC->SetPixel(tam[h],255); NT[n_t+h]=tam[h]; } n_t+=nn; } } ::GlobalUnlock(hDIB); } //================================================// void WINAPI Xoa(CDC *pDC) { CPen lpen(PS_SOLID,1500,RGB(255,255,255)); pDC->SelectObject(&lpen); pDC->MoveTo(0,0); pDC->LineTo(800,600); } //=================================================// HDIB WINAPI quay(HDIB hDIB,double gA) { LPSTR lpDIB=(LPSTR)::GlobalLock(hDIB); LPBITMAPINFOHEADER pDIB = (LPBITMAPINFOHEADER)(lpDIB); HBYTE pLine = ((HBYTE)::FindDIBBits((LPSTR)pDIB)); LPRGBQUAD lpRGB = (LPRGBQUAD)(lpDIB + (DWORD)sizeof(BITMAPINFOHEADER)); DWORD wByte = (WORD)WIDTHBYTES(pDIB->biWidth*pDIB->biBitCount); if(!hDIB)return false; HDIB hDIB1=::CreatImage(hDIB,gA); if(!hDIB1)return false; // Put the header // Calculate number of byte per line LPSTR lpDIB1=(LPSTR)::GlobalLock(hDIB1); LPBITMAPINFOHEADER pDIB1 = (LPBITMAPINFOHEADER)(lpDIB1); LPRGBQUAD lpRGB1 = (LPRGBQUAD)(lpDIB1 + (DWORD)sizeof(BITMAPINFOHEADER)); HBYTE pLine1 = ((HBYTE)::FindDIBBits((LPSTR)pDIB1)); long xp,yp; for(long i=0;ibiHeight;i++) for(long j=0;jbiWidth;j++) { xp=(long)(j*cos(gA)-(i-wByte*sin(gA))*sin(gA)+0.5); yp=(long)(j*sin(gA)+(i-wByte*sin(gA))*cos(gA)+0.5); if(yp>=0&&ypbiHeight&&xp>=0&&xp<long(wByte)) pLine1[i*pDIB1->biWidth+j]=pLine[yp*wByte+xp]; else pLine1[i*pDIB1->biWidth+j]=(char)255; } for(int l=0;l<255;l++) lpRGB1[l]=lpRGB[l]; lpRGB1[255].rgbBlue=lpRGB1[255].rgbGreen=lpRGB1[255].rgbRed=255; ::GlobalUnlock(hDIB); ::GlobalUnlock(hDIB1); return hDIB1; } //============================================= HDIB WINAPI quayam(HDIB hDIB,double gA) { LPSTR lpDIB=(LPSTR)::GlobalLock(hDIB); LPBITMAPINFOHEADER pDIB = (LPBITMAPINFOHEADER)(lpDIB); HBYTE pLine = ((HBYTE)::FindDIBBits((LPSTR)pDIB)); LPRGBQUAD lpRGB = (LPRGBQUAD)(lpDIB + (DWORD)sizeof(BITMAPINFOHEADER)); DWORD wByte = (WORD)WIDTHBYTES(pDIB->biWidth*pDIB->biBitCount); if(!hDIB)return false; HDIB hDIB1=::CreatImage(hDIB,gA); if(!hDIB1)return false; // Put the header // Calculate number of byte per line LPSTR lpDIB1=(LPSTR)::GlobalLock(hDIB1); LPBITMAPINFOHEADER pDIB1 = (LPBITMAPINFOHEADER)(lpDIB1); LPRGBQUAD lpRGB1 = (LPRGBQUAD)(lpDIB1 + (DWORD)sizeof(BITMAPINFOHEADER)); // HBYTE pLine1 = ((HBYTE)::FindDIBBits((LPSTR)pDIB1)); long xp,yp; for(long i=0;ibiHeight;i++) for(long j=0;jbiWidth;j++) { xp=(long)((j-pDIB->biHeight*sin(-gA))*cos(gA)-(i)*sin(gA)+0.5); yp=(long)((j-pDIB->biHeight*sin(-gA))*sin(gA)+(i)*cos(gA)+0.5); if(yp>=0&&ypbiHeight&&xp>=0&&xp<long(wByte)) pLine1[i*pDIB1->biWidth+j]=pLine[yp*wByte+xp]; else pLine1[i*pDIB1->biWidth+j]=(char)255; } for(int l=0;l<255;l++) { lpRGB1[l]=lpRGB[l]; } lpRGB1[255].rgbBlue=lpRGB1[255].rgbGreen=lpRGB1[255].rgbRed=255; ::GlobalUnlock(hDIB); ::GlobalUnlock(hDIB1); return hDIB1; } //=============================================// double WINAPI Xacdinhgoc(LPSTR lpDIB,CDC *pDC) { LPBITMAPINFOHEADER pDIB= (LPBITMAPINFOHEADER)(lpDIB); DWORD wBytes = (WORD)WIDTHBYTES(pDIB->biWidth*pDIB->biBitCount); ::Xoa(pDC); CPoint p; CString aa; vv.t=0; int so_goc=0; for(long k=10;kbiHeight-10;k++) for(DWORD l=10;l<wBytes-10;l++) if(GetPixel(lpDIB,l,k)==0) { p.x=l;p.y=k; if(Timdong(lpDIB,p,pDC)>20) { k=vv.b+1; double b=Xacdinhgocduong(); if(fabs(b)<10)return b; break; } else{ break;} } return 0; } //=============================================// void WINAPI Canle(LPSTR lpDIB,LPSTR lpDIB1,int letrai,int letren) { LPBITMAPINFOHEADER pDIB= (LPBITMAPINFOHEADER)(lpDIB); DWORD wByte = (WORD)WIDTHBYTES(pDIB->biWidth*pDIB->biBitCount); int tang=0; long xt,yt; for(long i=pDIB->biHeight-1;i>0;i--) { tang=0; for(DWORD j=0;j<wByte;j++) if(GetPixel(lpDIB,j,i)==0)tang++; if(tang>2) { yt=pDIB->biHeight-i; break; } } for(DWORD l=0;l<wByte;l++) { tang=0; for(long j=0;jbiHeight;j++) if(GetPixel(lpDIB,i,j)==0)tang++; if(tang>2) { xt=i; break; } } HBYTE pLine = ((HBYTE)::FindDIBBits((LPSTR)lpDIB)); HBYTE pLine1 = ((HBYTE)::FindDIBBits((LPSTR)lpDIB1)); for(i=0;i<H;i++) for(DWORD j=0;j<W;j++) { if((i+letren-yt)*wByte+j-xt+letrai>pDIB->biSizeImage) pLine1[i*nW+j]=pLine[(i+letren-yt)*wByte+j-xt+letrai]; } } //=============================================// void CPcxView::OnTaoanh() { CPcxDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); CDC *pDC; pDC=GetDC(); if (!pDoc->m_hDIB) return; /// HDIB hDIB1=::CreatImage1(pDoc->m_hDIB,1.5); LPSTR lpDIB1 = (LPSTR)::GlobalLock(hDIB1); CPalette m_pPal; PaletteSize(lpDIB1); RECT rc = {0,0,::DIBWidth(lpDIB1)-1, ::DIBHeight(lpDIB1)-1}; ::GlobalUnlock(hDIB1); ::PaintDIB1(pDC->m_hDC, &rc, hDIB1, &rc,&m_pPal); } //==============================================// void CPcxView::OnDobien() { CPcxDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); CDC *pDC; pDC=GetDC(); if (!pDoc->m_hDIB) return; ::Dobien(pDoc->m_hDIB,pDC); } //=======================================// void CPcxView::OnProcessChinhvanban() { CPcxDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); CDC *pDC; LPSTR lpDIB =(LPSTR)::GlobalLock(pDoc->m_hDIB); pDC=GetDC(); double b=::Xacdinhgoc(lpDIB,pDC); CString aa; aa.Format("goc lech cua van ban la %d",int(b*180/3.14)); ::AfxMessageBox(aa); HDIB hDIB1; if(b==0){::AfxMessageBox(" khong xac dinh duoc goc"); hDIB1=pDoc->m_hDIB; } else { if(b>0)pDoc->m_hDIB=hDIB1=::quay(pDoc->m_hDIB,b); else pDoc->m_hDIB=hDIB1=::quayam(pDoc->m_hDIB,b); } LPSTR lpDIB1 = (LPSTR)::GlobalLock(hDIB1); ::Canle(lpDIB1,lpDIB,20,20); pDoc->m_hDIB=hDIB1; RECT rc = {0,0,::DIBWidth(lpDIB1)-1, ::DIBHeight(lpDIB1)-1}; ::PaintDIB(pDC->m_hDC, &rc, pDoc->m_hDIB, &rc,&pDoc->m_pPal); ::GlobalUnlock(hDIB1); ::GlobalUnlock(pDoc->m_hDIB); } Kết luận Xử lý ảnh văn bản là một bộ phận quan trọng của nghành xử lý ảnh và có nhiều ứng dụng rộng rãi trong khoa học và đời sống thực tiễn. Một nhiệm vụ quan trong của xử lý ảnh văn bản là tự đọng hoá văn phòng. Một cách tự nhiên và tất yếu, vấn đề đấu tiên và cũng là vấn đề không thể tránh khỏi trong xử lý ảnh văn bản là bài toán góc nghiêng văn bản. Sở dĩ con người có thể kết luận rằng một văn bản bị nghiêng góc là vì chúng ta đã dựa vào một số đối tượng chủ đạo trong văn bản và quan sát thấy đường nối các điểm giữa đáy của chúng lệch đi một góc. Quan điểm trên đã hình thành ý tưởng chính cho bài toán phát hiện góc nghiêng văn bản được trình bày trong khoá luận này. Thuật toán dựa vào những đối tượng ảnh có kích thước chủ đạo để kết luận góc nghiêng. Dùng phương pháp dò biên, và biến đổi Hough để xác định được góc nghiêng, và chỉnh sửa góc nghiêng đó nó được áp dụng thành công trong ảnh trắng đen. Thuật toán được cài đặt thành công bằng công cụ lập trình là ngôn ngữ Visual C++, đã được thử nghiệm và cho kết quả khả quan trong chương trình Phát hiện góc nghiêng văn bản. Trong phạm vi một khoá luận tôt nghiệp đại học, do thời gian còn hạn chế. Tuy thuật toán đã được cài đặt thành công đối với ảnh đen trắng, nhưng vẫn không tránh khỏi những thiếu sót trong quá trình làm đề tài này và đây cũng là một trong những mặt tồn tại. Hướng phát triển trong tương lai: Mở rộng chương trình cho tất cả các định dạng ảnh Chương trình được làm với ảnh nhiều màu. Hoàn thiện hơn về mặt giao diện. Tài liệu tham khảo Lương Mạnh Bá - Nguyễn Thanh Thuỷ. Nhập Môn Xử Lý ảnh Số. Nhà xuất bản Khoa học và kỹ thuật, 1999. Ngô Diên Tập, “Xử lý ảnh bằng máy tính”, 1997. Nguyễn Kim Sách, “Xử lý ảnh và video số”, 1997. J.P.parker, “algorithms for image processing and computer vision”, 1997. Roland Wilson and Chang-Tsun Li “A Class of Disecrete Multiresolution Random Fields and Its Application to Image Segmentation” IEEE transactions on pattern analysis and machine intelligence vol.25, No. 1, January 2002. Jayaram k. Udupa, Punam K. Saha, Roberto A. Lotufo “Relative Fuzzy Connectedness and Object Definition: Theory, Algorithms, and Applications in Image Segmentation” IEEE transactions on patternanalysis and machine intelligence vol.24, No.1, January 2002. G. Iannizzotto, A. Puliafito and L. Vita. A new Method for Extracting and Representing Object Contours in Real Image. Infomation Science Vol 93. 1996, tr. 159-185. P. K. Saha, J. K. Udupa, and D. Odhner, “Scale-Based Fuzzy Connected Image Segmentation: Theory, Algorithms, and Validation” Computer Vision and Image Understanding, vol. 77, pp. 145-1.74, 2000. Bill Green. Canny Edge Detection Tutorial. Image Processing Algorithms. G. Iannizzotto, A. Puliafito and L. Vita. A new Method for Extracting and Representing Object Contours in Real Image. Infomation Science Vol 93. 1996, tr. 159-185. James R.Parker, Algorithms for Image Processing and Computer Vision, Wiley Computer Publishing, 1997, tr.1-67. Ioannis, “Digital Image Processing Algorithm”, 1993.