Luận án Phân tích cấu trúc hình học trang ảnh tài liệu dựa trên phương pháp ngưỡng thích nghi

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ...*** HÀ ĐẠI TÔN PHÂN TÍCH CẤU TRÚC HÌNH HỌC TRANG ẢNH TÀI LIỆU DỰA TRÊN PHƯƠNG PHÁP NGƯỠNG THÍCH NGHI Chuyên ngành: Cớ sở Toán học cho Tin học Mã số: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018 2 Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học: TS. Nguyễn Đức Dũng Phản biện 1: Phản biện 2: Phản biện 3: . Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi giờ ..’, ngày tháng năm 201. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam 3 MỞ ĐẦU Nhận dạng văn bản là một lĩnh vực đã được quan tâm nghiên cứu và ứng dụng trong nhiều năm nay. Quá trình nhận dạng văn bản được thực hiện qua các bước chính như sau: Trang ảnh đầu vào sẽ qua bước tiền xử lý, sau đó là bước phân tích trang, kết quả đầu ra của phân tích trang sẽ là đầu vào của bước nhận dạng, cuối cùng là bước hậu xử lý. Kết quả của một hệ thống nhận dạng phụ thuộc chính vào hai bước: phân tích trang và nhận dạng. Đến thời điểm này, bài toán nhận dạng trên các văn bản chữ in đã được giải quyết gần như trọn vẹn (sản phẩm thương mại FineReader 12.0 của hãng ABBYY có thể nhận dạng chữ in trên nhiều ngôn ngữ khác nhau, phần mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện Công nghệ Thông Tin Hà Nội có thể nhận dạng với độ chính xác trên 98%). Tuy nhiên trên thế giới cũng như ở Việt Nam, bài toán phân tích trang vẫn còn là một thách thức lớn đối với các nhà nghiên cứu. Cho đến này phân tích trang vẫn đang nhận được sự quan tâm của nhiều nhà nghiên cứu. Cứ hai năm một lần trên thế giới lại có cuộc thi phân tích trang quốc tế nhằm thúc đẩy sự phát triển các thuật toán phân tích trang. Chính những điều này đã là động lực thúc đẩy luận án cố gắng nghiên cứu để đề xuất các giải pháp hữu hiệu cho bài toán phân tích trang.ThuậtTrong những năm gần đây đã có rất nhiều các thuật toán phân tích trang được phát triển, đặc biệt là các thuật toán phát triển theo hướng tiếp cận lại ghép (hybrid). Các thuật toán được đề xuất đều thể hiện những điểm mạnh, điểm yếu khác nhau, nhưng nhìn chung hầu hết vẫn mắc phải hai lỗi cơ bản là: lỗi phân tách một vùng chữ đúng ra thành các vùng chữ nhỏ hơn làm sai hoặc mất thông tin của các dòng chữ hay đoạn văn bản (over-segmentation), lỗi gộp các vùng chữ ở các cột văn bản hay các đoạn văn bản lại với nhau (under-segmentation). Vì vậy mục tiêu của luận án là nghiên cứu phát triển các thuật toán phân tích trang giảm đồng thời cả hai kiểu lỗi: over-segmentation, under-segmentation. Các vấn đề trong phân tích trang là rất rộng vì vậy luận án giới hạn phạm vi nghiên cứu trong khuôn khổ các trang ảnh văn bản được soạn thảo bằng ngôn ngữ Latin cụ thể là Tiếng Anh và tập trung vào phân tích các vùng chữ. Luận án chưa đề xuất đến vấn đề phát hiện và phân tích cấu trúc của các vùng bảng, phát hiện các vùng ảnh và phân tích cấu trúc logic. Với những mục tiêu đặt ra luận án đã đạt được một số kết quả sau: 1. Đề xuất một giải pháp làm tăng tốc thuật toán phát hiện nền trang ảnh. 2. Đề xuất phương pháp tham số thích nghi làm giảm sự ảnh hưởng của kích cỡ và kiểu phông chữ đến kết quả phân tích trang. 3. Đề xuất một giải pháp mới cho vấn đề phát hiện và sử dụng các đối tượng phân tách trong các thuật toán phân tích trang. 4. Đề xuất một giải pháp mới tách các vùng chữ thành các đoạn văn bản dựa trên phân tích ngữ cảnh. 4 CHƯƠNG 1. TỔNG QUAN VỀ PHÂN TÍCH TRANG ẢNH TÀI LIỆU Trong chương này, tôi trình bày tổng quan hệ thống nhận dạng văn bản, bài toán phân tích trang, các thuật toán phân tích trang tiêu biểu, những lỗi cơ bản nhất của các thuật toán phân tích trang. Từ đó dẫn đến mục tiêu nghiên cứu và những kết quả đạt được của luận án này. 1.1. Các thành phần chính của hệ thống nhận dạng văn bản Về cơ bản, một hệ thống nhận dạng văn bản thường được thực hiện qua các bước cơ bản như được mô tả ở hình 1. Những thông tin ở dạng văn bản như sách, báo, tạp chí, ... sau quá trình scan sẽ cho ta kết quả là các file ảnh văn bản. Những file ảnh này sẽ là đầu vào của một hệ thống nhận dạng, kết quả đầu ra của hệ thống nhận dạng là những file văn bản có thể dễ dàng chính sửa và lưu trữ, ví dụ như file *.doc, *.docx, *.excel, *.pdf, ... Luận án chỉ tập trung vào nghiên cứu bước phân tích trang, trong đó trọng tập là phân tích cấu trúc hình học của trang ảnh. Hình 1: Minh họa các bước xử lý cở bản của một hệ thống nhận dạng văn bản. 1.1.1. Tiền xử lý Nhiệm vụ của quá trình tiền xử lý trang ảnh thông thường là nhị phân hóa, xác định các thành phần liên thông ảnh, lọc nhiễu, căn trình độ nghiêng. Kết quả đầu ra của bước tiền xử lý sẽ là đầu vào của quá trình phân tích trang. Do đó, kết quả của quá trình tiền xử lý cũng sẽ có những ảnh hưởng đáng kể đến kết quả phân tích trang. 1.1.2. Phân tích trang ảnh tài liệu Phân tích trang ảnh tài liệu (document layout analysis) là một trong những thành phần chính của các hệ thống nhận dạng văn bản (OCR - System). Ngoài ra nó còn được ứng dụng rộng rãi trong các lĩnh vực khác của tin học ví dụ như số hóa tài liệu, nhập liệu tự động, thị giác máy tính,... Nhiệm vụ của phân tích trang bao gồm việc tự động phát hiện những vùng ảnh có trên một trang ảnh tài liệu (cấu trúc vật lý) và phân loại chúng thành những vùng dữ liệu khác nhau như vùng chữ, ảnh, bảng biểu, header, footer... (cấu trúc logic). Kết quả phân tích trang được sử dụng như một thông tin đầu vào cho quá trình nhận dạng và nhập liệu tự động của các hệ thống xử lý ảnh tài liệu (document imaging). 1.1.3. Nhận dạng kí tự quang học Đây là giái đoạn quan trọng nhất, giái đoạn này quyết định độ chính xác của hệ thống nhận dạng. Có nhiều phương pháp phân lớp khác nhau được áp dụng cho các hệ thống nhận dạng chữ, ví dụ như: phương pháp đối sánh, phương pháp tiếp cận trực tiếp, phương pháp ngữ pháp, phương pháp đồ thị, mạng nơ ron, phương pháp thống kê, máy véc tơ tựa (SVM). 1.1.4. Hậu xử lý Đây là công đoạn cuối cùng của quá trình nhận dạng. Có thể hậu xử lý là bước ghép nối các kí tự đã nhận dạng thành các từ, các câu, các đoạn văn bản nhằm tái hiện lại văn bản đồng thời phát hiện ra các lỗi nhận dạng sai bằng cách kiểm tra chính tả dựa trên cấu trúc và ngữ nghĩa của các từ, các câu hoặc các đoạn văn bản. Việc phát hiện ra các lỗi, các sai sót trong nhận dạng ở bước này góp phần đáng kể vào việc nâng cao chất lượng nhận dạng. 1.2. Các thuật toán phân tích cấu trúc hình học (phân tách) trang tiêu biểu Qua hàng chục năm phát triển cho đến nay đã có rất nhiều các thuật toán phân tích trang đã được công bố. Dựa trên thứ tự thực hiện của các thuật toán, các thuật toán phân tách trang ảnh tài liệu có thể được chia thành ba hướng tiếp cận khác nhau: từ trên xuống (top-down), từ dưới lên (bottom-up) và các phương pháp lai ghép (hybrid). 5 1.2.1 Hướng tiếp cận từ trên xuống (top-down) Các thuật toán top-down tiêu biểu như: X-Y Cut, WhiteSpace,... Các thuật toán theo hướng tiếp cận này thực hiện phân tích trang bằng cách chia đệ quy trang ảnh văn bản theo các phương ngang hoặc phương thẳng đứng dọc theo các khoảng trắng trong trang. Những khoảng trằng này thường là dọc theo biên của các cột văn bản (column) hoặc biên của các đoạn ảnh văn bản (paragraph). Điểm mạnh của các thuật toán này là độ phức tạp tính toán thấp, cho kết quả phân tách tốt trên những trang ảnh có cấu trúc hình chữ nhật (rectangle) tức là các trang ảnh mà các vùng ảnh có thể được bao quanh bởi các hình chữ nhật không giáo nhao. Tuy nhiên, chúng không thể xử lý được những trang vùng ảnh không phải là hình chữ nhật (non-rectangular). 1.2.2. Hướng tiếp cận từ dưới lên (bottom-up) Các thuật toán bottom-up tiêu biểu như: Smearing, Docstrum, Voronoi,... Các thuật toán theo hướng tiếp cận này bắt đầu với các vùng nhỏ của ảnh (các pixel điểm ảnh hoặc các kí tự) và lần lượt nhóm các vùng nhỏ có cùng kiểu lại với nhau để hình thành nên các vùng ảnh. Điểm mạnh của hướng tiếp cận này là các thuật toán có thể xử lý tốt những trang ảnh với cấu trúc bất kì (rectangle hoặc non-rectangle). Điểm yếu của các thuật toán bottom-up là tốn bộ nhớ, chậm, do các vùng nhỏ được gộp lại với nhau dựa trên những tham số khoảng cách mà thông thường các tham số này được ước lượng trên toàn trang ảnh nên các thuật toán này thường quá nhạy cảm với giá trị tham số và mắc lỗi chia quá nhỏ (over-segmentation) các vùng ảnh văn bản, đặc biệt là các vùng chữ có sự khác biệt về kích cỡ và kiểu phông. 1.2.3. Hướng tiếp cận lai ghép (hybrid) Từ những phân tích trên cho thấy ưu điểm của hướng tiếp cận bottom-up là nhược điểm của hướng tiếp cận Top-down và ngược lại. Do đó, trong những năm gần đầy đã có nhiều các thuật toán phát triển theo hướng lai ghép giữa top-down và bottom-up, một trong các thuật toán tiêu biểu như: RAST , Tab-Stop , PAL ,... Các thuật toán phát triển theo hướng này thường dựa trên các đối tượng phân tách ví dụ như, các vùng trắng hình chữ nhật, các tab-stop, ... để suy ra cấu trúc các cột văn bản. Từ đó các vùng ảnh được xác định bằng phương pháp bottom-up. Các kết quả đánh giá đã cho thấy các thuật toán lai ghép đã khắc phục được phần nào hạn chế của các thuật toán top-down và bottom-up, đó là có thể thực hiện trên những trang ảnh với cấu trúc bất kì và ít hạn chế hơn vào các tham số khoảng cách. Tuy nhiên, việc xác định các đối tượng phân tách lại là một bài toán gặp phải rất nhiều khó khắn bởi nhiều lý do, ví dụ như có những vùng chữ ở quá gần nhau, các vùng chữ được căn lề, trái phải không thẳng hàng hoặc khoảng cách giữa các thành phần liên thông là quá lớn,... điều này đã làm cho các thuật toán hiện tại thường mắc phải các lỗi quên hoặc xác định nhầm các đường phần tách dẫn đến kết quả phân tách lỗi. 1.3. Các phương pháp và các tập dữ liệu đánh giá các thuật toán phân tách trang ảnh tài liệu 1.3.1. Độ đo Đánh giá các thuật toán phân tích trang ảnh tài liệu luôn là một vấn đề phức tạp vì nó phụ thuộc nhiều vào tập dữ liệu, ground-truth và phương pháp đánh giá. Vấn đề đánh giá chất lượng của các thuật toán phân tích trang đã nhận được nhiều sự quan tâm. Trong luận án này sử dụng ba đô đo: F-Measure, PSET-Measure và PRImA- Measure cho tất các đánh giá thực nghiệm. Độ đo PRImA-Measure đã được sử dụng thành công tại các cuộc thi phân tích trang quốc tế ở các năm 2009, 2011, 2013, 2015 và 2017. 1.3.2. Dữ liệu Trong luận án này, tôi sử dụng ba tập dữ liệu UW-III, tập dữ liệu PRImA và tập dữ liệu UNLV để đánh giá thực nghiệm và so sánh các thuật toán phân tích trang ảnh tài liệu. Tập UW- III có 1600 ảnh, tập PRImA có 305 ảnh và tập UNLV có 2000 ảnh. Các tập dữ liệu này đều có ground-truth ở cấp độ đoạn văn bản và cấp độ dòng chữ, được biểu diễn bởi các đa giác không giáo nhau. Các trang ảnh đều được quét với độ phân giải 300 DPI và đã được căn trỉnh lại độ 6 nghiêng. Nó chứa nhiều trang ảnh đa dạng về các kiểu trang ảnh, phản ảnh nhiều thách thức trong phân tích trang. Cấu trúc của trang ảnh chứa đựng một sự pha trộn từ đơn giản đến phức tạp, gồm nhiều bức ảnh có phần chữ bao quanh các trang ảnh, có sự thay đổi lớn về kích cỡ kiểu phông chữ. Do đó, đây là những tập dữ liệu rất tốt để thực hiện đánh giá so sánh các thuật toán phân tích trang. 1.4. Kết luận chương Chương này đã giới thiệu một cách tổng quan về lĩnh vực nhận dạng văn bản, trong đó phân tích trang là một khâu quan trọng. Cho đến nay bài toán phân tích trang vẫn là một vấn đề được nhiều nghiên cứu trong và ngoài nước quan tâm. Đã có nhiều thuật toán phân tích trang được đề xuất, đặc biệt là tại các cuộc thi phân tích trang quốc tế (ICDAR). Tuy nhiên các thuật toán vẫn mắc phải hai lỗi cơ bản: over-segmentation và under-segmentation. Vì vậy, luận án sẽ tập trung nghiên cứu các giải pháp cho bài toán phân tích trang ảnh tài liệu. Có ba hướng tiếp cận chính cho bài toán phân tích trang ảnh tài liệu: top-down, bottom-up và hybrid. Trong đó, hybrid là hướng tiếp cận được phát triển mạnh trong giái đoạn gần đây do nó khắc phục được nhược điểm của hai hướng tiếp cận top-down và bottom-up. Bởi vì lý đó đó, luận án sẽ phân tích trọng tâm hơn vào các thuật toán hybrid, đặc biệt là các kĩ thuật phát hiện và sử dụng các đối tượng phân tách của các thuật toán hybrid. Chương tiếp theo của luận án trình bày về một kĩ thuật phát hiện nền trang ảnh nhanh, kĩ thuật này sẽ được sử dụng như một module trong thuật toán được đề xuất ở Chương 3. 7 CHƯƠNG 2. THUẬT TOÁN NHANH PHÁT HIỆN NỀN TRANG ẢNH TÀI LIỆU Chương này trình bày ưu, nhược điểm của hướng tiếp cận dựa trên nền trang ảnh trong phân tích trang ảnh tài liệu, thuật toán phân tích trang WhiteSpace, thuật toán phát hiện nền trang ảnh nhanh và cuối cùng là các kết quả thực nghiệm. 2.1. Ưu nhược điểm của hướng tiếp cận dựa trên nền trang ảnh trong phân tích trang ảnh tài liệu Về mặt trực quan, trong rất nhiều trường hợp có thể thấy phát hiện nền trang ảnh là dễ dàng hơn, đồng thời dựa trên nền trang ảnh có thể dễ dàng tách được trang ảnh thành các vùng ảnh khác nhau. Do vậy, từ rất sớm đã có nhiều thuật toán phân tích trang dựa trên nền trang ảnh được phát triển, ví dụ điển hình như, X-Y Cut, WhiteSpace-Analysis, WhiteSpace-Cuts, ...và gần đây cũng có nhiều thuật toán mạnh dựa trên trang ảnh được phát triển, ví dụ như, Fraunhofer (chiến thắng tại IC- DAR2009), Jouve (chiến thắng tại ICDAR2011), PAL (chiến thắng tại ICDAR2013),... Không chỉ trong phân tích trang, hướng tiếp cận dựa trên nền trang ảnh còn được ứng dụng rộng rãi trong bài toán phát hiện bảng, phân tích cấu trúc bảng, phân tích cấu trúc logic. Qua các ví dụ trên có thể thấy được hướng tiếp cận dựa trên nền trang ảnh có nhiều ưu điểm. Đã có nhiều thuật toán khác nhau được phát triển để phát hiện nền trang ảnh, ví dụ như X-Y Cuts, WhiteSpace-Analysis, WhiteSpace-Cuts (sau đây gọi tắt là WhiteSpace), ...Trong đó, WhiteSpace được biết đến như một thuật toán hình học rất nổi tiếng trong việc phát hiện nền trang ảnh, thuật toán có trong bộ mã nguồn mở OCROpus vì vậy nó được sử dụng rộng rãi như một bước cơ bản để phát triển thuật toán. Tuy nhiên, thuật toán WhiteSpace có hạn chế là thời gián thực thi khá chậm, xem Hình 2. Do đó, việc tăng tốc thuật toán WhiteSpace có nhiều ý nghĩa thực tiến. Hình 2: Minh họa thời gián thực thi trung bình của mỗi thuật toán. 2.2. Thuật toán phát hiện nền trang ảnh (WhiteSpace) cho bài toán phân tích trang 2.2.1. Định nghĩa Vùng trắng lớn nhất trong một trang ảnh được định nghĩa là hình chữ nhất lớn nhất nằm trong hình bao của trang ảnh và không chữ một kí tự nào, xem Hình 3. Hình 3: Hình chữ nhật màu xanh thể hiển cho vùng trắng lớn nhất tìm được. 8 2.2.2. Thuật toán tìm vùng trắng lớn nhất Thuật toán tìm vùng trắng lớn nhất (sau đây được gọi MaxWhitespace) có thể áp dụng cho các đối tượng là các điểm hoặc các hình chữ nhật. Ý tưởng mẫu chốt của thuật toán là phương pháp nhánh cận và thuật toán Quicksort. Hình 5 a) và 4 minh họa giả code của thuật toán và bước chia hình chữ nhật thành các hình chữ nhật con. Trong khuôn khổ của luận án này, đầu vào của thuật toán là một tập các hình chữ nhật rectangles (hình bao của các kí tự), hình chữ nhật bound (hình bao của cả trang ảnh) và hàm quality(rectangle) trả về diện tích của mỗi hình chữ nhật, xem Hình 4.a). Thuật toán định nghĩa một trang thái (state) bao gồm một hình chữ nhật r, tập các hình chữ nhật obstacles (hình bao của các kí tự) nằm trong hình chữ nhật r và diện tích của hình chữ nhật r (q = quality(r)). Trạng thái 𝑠𝑡𝑎𝑡𝑒𝑖 được định nghĩa là lớn hơn trạng thái 𝑠𝑡𝑎𝑡𝑒𝑗 nếu 𝑞𝑢𝑎𝑙𝑖𝑡𝑦(𝑟𝑖) > 𝑞𝑢𝑎𝑙𝑖𝑡𝑦(𝑟𝑗). Hàng đợi ưu tiên queue được sử dụng để lưu trữ các trạng thái. Mỗi vòng lặp thuật toán sẽ lấy ra trạng thái state = (q, r, obstacles) là đầu của hàng đợi ưu tiên, đây là trạng thái mà hình chữ nhật r có diện tích lớn nhất. Nếu không có hình chữ nhật obstacles nào chứa trong r thì r là vùng trắng hình chữ nhật lớn nhất tìm được và thuật toán kết thúc. Ngược lại, thuật toán sẽ chọn một trong các hình chữ nhật obstacles làm chốt (pivot), cách chọn tốt nhất là càng gần tâm của hình chữ nhật r càng tốt, xem Hình 4.b). Chúng ta biết rằng vùng trắng lớn nhất sẽ không chứa bất kì một hình chữ nhật obstacles nào vì vậy nó cũng sẽ không chứa pivot. Do đó, có bốn khả năng có thể xảy ra của vùng trắng lớn nhất: là bên trái và bên phải của pivot, xem Hình 4.c), hoặc bên trên và bên dưới của pivot, xem Hình 4.d). Tiếp theo, thuật toán sẽ xác định các hình chữ nhật obstacles giáo với mỗi hình chữ nhật con này, có bốn hình chữ nhật con 𝑟0 , 𝑟1 , 𝑟2 , 𝑟3 được sinh ra từ hình chữ nhật 𝑟, xem Hình 5 và tính toán chặn trên của vùng trắng lớn nhất có thể có trong mỗi hình chữ nhật con mới được tạo ra, chặn trên được lựa chọn chính là diện tích của mỗi hình chữ nhật con. Các hình chữ nhật con cùng với các obstacles nằm trong nó và chặn trên tương ứng với nó được đẩy vào hàng đợi ưu tiên và các bước trên được lặp lại cho đến khi xuất hiện trạng thái với hình chữ nhật r không chữ bất kì một obstacles nào. Hình chữ nhật này là nghiệm toàn cục của bài toán tìm vùng trắng lớn nhất. a) b) c) d) Hình 4: Mô tả bước chia trang ảnh thành bốn miền con của thuật toán tìm vùng trắng lớn nhất, (a) hình bao và các hình chữ nhật, (b) điểm chốt tìm được, (c, d) các miền con trái/phải và trên/dưới. 9 a) b) Hình 5: a) minh họa giả code của thuật toán tìm các vùng trắng lớn nhất. b) minh họa thuật toán tìm các vùng trắng bao phủ nền trang ảnh 2.2.3. Thuật toán phát hiện nền trang ảnh Để phát hiện nền trang ảnh thuật toán được đề xuất như một mô đun của thuật toán WhiteSpace áp dụng thuật toán MaxWhitespace Để tìm m — Whitespace vùng trắng (với m — Whitespace khoảng 300 là đủ Để mô tả tốt nền trang ảnh), sau đây thuật toán phát hiện nền được gọi là WhiteSpaceDetection. Sơ đồ của thuật toán được the hiện ở Hình 5 b). 2.3. Tăng tốc thuật toán phát hiện nền trang ảnh Để tìm các vùng trắng bao phủ nền của trang ảnh, thuật toán tìm vùng trắng chia đệ quy trang ảnh thành các vùng con sao cho vùng con tìm được không chứa một kí tự nào. Tại mỗi lần lặp thuật toán sẽ chia mỗi vùng con của trang ảnh thành bốn miền con khác nhau, xem Hình 6. Quá trình này sẽ tạo thành một cây tứ phân do vậy nếu vòng lặp lớn thì số lượng các miền còn cần được xem xét đến sẽ là rất lớn. Chính vì vậy thời gián thực thi của thuật toán thường rất chậm. Do đó, để tăng tốc thuật toán phát hiện nền trang ảnh cần phải làm giảm tối đa số các vùng con cần phải xét đến, bằng cách hạn chế sinh ra các nhanh con không cần thiết của cây tứ phân. Hình 6 cho thấy miền ZG (Vùng ông bà) được chia làm bốn miền con: miền con trên ZP T, miền con dưới ZP B , miền con trái ZPL và miền con phải ZPR. Tiếp tục chia miền ZPT, thì miền con phải ZC T R sẽ nằm trọn trong miền ZP R, nên khi xét đến miền ZP R thì cũng xem xét luôn miền ZC T R, hay miền ZC T R được xem xét lại. Ví dụ minh họa ở Hình 6 cho thấy miền con trên ZC R T của miền ZP R đã xét lại miền ZC T R. Quá trình phân chia này sẽ tạo thành một cây tứ phân và càng xuống sâu thì sẽ càng có nhiều các vùng con bị xem xét lại nhiều lần. Trong chương này, luận án đề xuất một giải pháp làm giảm tối đa số các miền con bị xét lại. Thuật toán được đề xuất (sau đây gọi là Fast-WhiteSpaceDetection) sẽ không sinh ra các miền con mà nó nằm trọn vẹn trong các miền con trước đó, bằng cách dựa vào vị trí tương đối giữa Pivot của miền đang xét với Pivot của miền cha. Như ví dụ ở Hình 6, miền con ZC T R sẽ không được sinh ra vì nó nằm trong miền (ZP R). Tuy nhiên, chỉ xem xét loại bỏ các mi