Kỹ thuật hiệu chỉnh biến dạng trang

 (mzucker.github.io)
2 điểm bởi GN⁺ 2024-05-14 | 1 bình luận | Chia sẻ qua WhatsApp
  • Để biến ảnh chụp tài liệu bị cong thành ảnh phẳng, phương pháp này mô hình hóa tư thế 3D và độ cong, rồi giải dưới dạng bài toán tối ưu căn chỉnh các điểm mốc văn bản
  • Tương tự Leptonica và CTM, quy trình chia văn bản theo từng dòng, rồi tìm phép biến đổi tọa độ để các dòng trông song song và gần như nằm ngang
  • Mô hình gồm vector quay r, vector tịnh tiến t, độ dốc độ cong α, β, cùng các độ lệch x, y của các span văn bản, và tối thiểu hóa lỗi chiếu lại
  • Pipeline gồm cắt biên trang, phát hiện đường bao văn bản, lắp ráp span, lấy mẫu điểm mốc, tạo giá trị khởi tạo, tối ưu Powell, rồi ánh xạ lại bằng cv2.remap
  • Trong các ví dụ chạy thử, số tham số nằm trong khoảng 104~600, tổng thời gian chạy là 5.3~24.8 giây, và phần lớn thời gian dành cho tối ưu hóa nên vẫn còn dư địa tăng tốc bằng solver khác hoặc ngôn ngữ biên dịch

Giải bài toán trang cong như một bài toán tối ưu

  • Script cũ để chuyển ảnh chụp chữ viết tay thành PDF chỉ dừng ở mức dùng adaptiveThreshold và gộp nhiều ảnh vào PDF, nhưng với ảnh tài liệu lưu trữ thì độ cuộn của trang làm văn bản bị cong đáng kể
  • Mục tiêu là tạo một chương trình tự động chuyển ảnh chụp trang cong thành ảnh tài liệu phẳng
  • Mã nguồn được công khai trên GitHub tại page_dewarp

Luồng cơ bản lấy từ Leptonica và CTM

  • Hiệu chỉnh biến dạng ảnh tài liệu là một bài toán đã được nghiên cứu từ trước, và cũng đã được triển khai trong thư viện xử lý ảnh mã nguồn mở Leptonica của Dan Bloomberg
  • Tài liệu tham khảo gồm bản tóm tắt kết quả dewarping contest và bài báo về phương pháp chiến thắng là Coordinate Transform Model, tức CTM
  • Leptonica và CTM cùng chia bài toán thành hai bước
    • Tách văn bản theo từng dòng
    • Tìm biến dạng hoặc phép biến đổi tọa độ để các dòng song song và nằm ngang
  • Cách triển khai này biểu diễn hình dạng trang bằng nhiều tham số
    • r, t: vector quay và vector tịnh tiến biểu diễn hướng 3D và vị trí của trang
    • α, β: hai độ dốc xác định độ cong của bề mặt trang
    • y₁ ... yₙ: độ lệch theo chiều dọc của n span ngang trên trang
    • xᵢ: độ lệch theo chiều ngang của nhiều điểm mốc trong mỗi span

Bề mặt 3D và lỗi chiếu lại

  • Hình dạng 3D của trang được biểu diễn bằng một bề mặt tạo ra bằng cách quét một đường cong theo trục y cục bộ
  • Tọa độ ngang x của trang được ánh xạ thành độ dịch chuyển theo trục z của bề mặt, và các mặt cắt ngang được mô hình hóa bằng spline bậc ba
    • Hai đầu mút của spline được cố định ở 0
    • Hình dạng spline được xác định chỉ bởi độ dốc đầu mút α, β
  • Khi các tham số tư thế và độ cong được xác định, mỗi tọa độ (x, y) trên trang sẽ được chiếu tới một vị trí cụ thể trên mặt phẳng ảnh
  • Từ ảnh gốc, hệ thống tìm các keypoint của các span văn bản ngang, rồi bắt đầu từ giá trị ước lượng ban đầu để tìm bộ tham số tối thiểu hóa lỗi chiếu lại của các keypoint
  • Trước tối ưu hóa, giả định là không có độ cong nên các điểm chiếu lại nằm trên một đường thẳng, nhưng sau tối ưu hóa thì các điểm chiếu của mô hình gần như trùng với các keypoint được phát hiện thực tế

Pipeline xử lý ảnh

  • Cắt biên trang

    • Thay vì dùng toàn bộ ảnh, hệ thống chỉ cắt vùng giữa với margin cố định để tránh các vùng thừa ở rìa
    • Không dùng phương pháp phát hiện biên trang thông minh

  • Phát hiện đường bao văn bản

    • Áp dụng adaptive threshold ban đầu
    • Thực hiện morphological dilation) bằng hộp ngang để nối các pixel mask liền kề theo phương ngang
    • Thực hiện erosion) bằng hộp dọc để loại nhiễu cao một pixel
    • Sau connected component analysis, lọc bỏ các blob quá cao hoặc quá dày
    • Các đường bao văn bản còn lại được xấp xỉ bằng đoạn thẳng khớp tốt nhất qua PCA

  • Bổ sung phát hiện đường ngang

    • Một số đầu vào là bảng biểu có nhiều chữ theo cột dọc, nên nếu không phát hiện đủ văn bản ngang thì hệ thống cũng thử phát hiện các đường ngang hoặc rule

Tạo span văn bản và lấy mẫu điểm mốc

  • Để gom các đường bao phát hiện được vào cùng một span ngang, hệ thống tạo edge ứng viên cho mọi cặp đường bao và tính chi phí
  • Nếu hai đường bao chồng lấn quá nhiều theo chiều dài, quá xa nhau, hoặc khác góc quá lớn thì chi phí được đặt là vô cùng
  • Chi phí của edge hợp lệ được tính bằng tổ hợp tuyến tính của khoảng cách và thay đổi góc
  • Sau khi sắp xếp edge theo chi phí, hệ thống dùng cách tham lam bậc hai theo thời gian chỉ nối khi cả hai đường bao vẫn chưa được kết nối
    • Do phần lớn thời gian chạy dành cho tối ưu hóa, độ phức tạp bậc hai của bước này không phải vấn đề lớn
  • Sau khi tạo span, các span quá nhỏ và không giúp xác định mô hình sẽ bị loại bỏ
  • Vì mô hình tham số cần các điểm mốc rời rạc, hệ thống chọn một keypoint cho mỗi khoảng 20 pixel của đường bao văn bản

Tạo giá trị khởi tạo và tối ưu Powell

  • Hướng trung bình của tất cả các span được ước lượng bằng PCA
  • Dùng thành phần chính từ kết quả PCA để thiết lập giải tích các tọa độ x, y ban đầu và tư thế của một trang phẳng không cong
  • Việc chiếu lại lấy độ lệch z của các điểm đối tượng bằng cách lấy mẫu spline bậc ba, rồi dùng hàm OpenCV để chiếu lên mặt phẳng ảnh
    • cv2.solvePnP
    • cv2.projectPoints
  • Việc tối thiểu hóa lỗi chiếu lại dùng scipy.optimize.minimize và solver 'Powell'
    • Được dùng như một công cụ tối ưu không đạo hàm kiểu hộp đen
    • Bản thân bài toán thuộc loại bình phương tối thiểu phi tuyến
    • Tác giả không thử nghiệm nhiều với solver khác hay solver bình phương tối thiểu phi tuyến chuyên biệt
  • Gần như 100% thời gian chạy của chương trình nằm ở bước tối ưu hóa này

Ánh xạ lại và tạo ảnh đầu ra

  • Sau khi tối ưu xong, hệ thống tách riêng r, t, α, β để tạo phép biến đổi tọa độ
  • Quá trình dewarp thực tế được thực hiện bằng cách chiếu dense mesh của các điểm 3D trên trang qua cv2.projectPoints, rồi truyền các tọa độ ảnh đó vào cv2.remap
  • Kết quả cuối cùng được lưu thành PNG hai mức bằng cv2.adaptiveThreshold và Pillow

Kết quả ví dụ và thời gian chạy

  • Kho lưu trữ GitHub có kèm nhiều ảnh ví dụ
  • Thống kê khi chạy trên một máy MacBook Pro 2012 như sau
Đầu vào Spans Keypoints Parameters Thời gian tối ưu Tổng thời gian
boston_cooking_a.jpg 38 554 600 23.3 giây 24.8 giây
boston_cooking_b.jpg 38 475 521 18.0 giây 18.8 giây
linguistics_thesis_a.jpg 20 161 189 5.1 giây 6.1 giây
linguistics_thesis_b.jpg 7 89 104 4.2 giây 5.3 giây
  • Ngay cả mô hình nhỏ nhất cũng có 104 tham số, còn mô hình lớn nhất có 600 tham số, nên đây không phải bài toán tối ưu nhỏ
  • Tốc độ tối ưu có thể được cải thiện nếu thử phương pháp khác hoặc dùng ngôn ngữ biên dịch

Những giới hạn còn lại

  • Cách tiếp cận tổng thể là đọc một ít tài liệu nền tảng rồi phát biểu toàn bộ bài toán sao cho đầu ra thu được từ một quá trình tối ưu hóa
  • Cách này gợi nhớ đến deformable part models và active appearance models, nhưng không tinh vi bằng hai hướng đó
  • Leptonica và CTM cố gắng mô hình hóa và hiệu chỉnh không chỉ biến dạng dọc mà cả biến dạng ngang
  • Cách triển khai này không xử lý đến mức hiệu chỉnh biến dạng ngang
    • Vì spline bậc ba không được tham số hóa theo arc-length, nên ở các vùng có độ dốc spline lớn thì văn bản bị nén nhẹ
    • Do dự án chủ yếu là một proof-of-concept, vấn đề này không được tiếp tục đào sâu
  • Mã cuối cùng được công khai trong kho GitHub, nhưng phần chú thích chi tiết vẫn chưa thực sự đầy đủ

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-05-14
Các ý kiến trên Hacker News

  • Cần cẩn trọng với việc áp dụng thresholding mạnh lên đầu ra như tác giả đã làm
    Các trang văn bản thường thì nhận khá tốt, nhưng tôi đã thấy trên nhiều trang của Google Books, hình minh họa hoặc chú thích nhỏ bị hỏng đến mức không đọc được
    Nếu bản scan Google Books là tài liệu duy nhất thì coi như bế tắc hoàn toàn

    • Không phải thresholding dùng để tìm các điểm mốc nhằm chọn tham số hiệu chỉnh biến dạng sao?
      Một khi tìm được điểm mốc, có vẻ có thể áp dụng các tham số đó lên ảnh gốc

  • Đã là năm 2024 rồi mà thật bực khi các ứng dụng quét tài liệu vẫn chưa tích hợp sẵn mặc định tính năng này

    • Ở trường tôi dùng GeniusScan, và nó có tính năng này: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
    • Rất tuyệt
      Có vẻ việc đặt ra một mô hình biến dạng trang chiều thấp để tối ưu hóa là điểm mấu chốt giúp cách này hoạt động tốt
      Đây đúng là bài toán vừa tầm YC. Có lẽ chỉ mất vài tuần để đưa ra thị trường, chi phí ra mắt khoảng vài trăm nghìn đô la
      Ứng dụng điện thoại của Apple cần chỉnh thủ công quá nhiều, còn Office Lens / Microsoft Lens của Microsoft thì có những đánh giá kiểu “các mép rốt cuộc phát điên và trông kinh khủng”
      Vì vậy rõ ràng có thị trường cho một sản phẩm hoạt động tốt, và cũng có khả năng exit bằng cách bán cho các bên thường hay mua lại
    • Tôi có cảm giác Google Drive trước đây từng làm việc này đúng cách, nhưng trong vài năm qua đã tệ hơn nhiều
    • Có lẽ quản lý sản phẩm đã cho rằng rủi ro kỹ thuật không đáng để gánh
      Họ hẳn thấy nó quá phức tạp và quá toán học, rồi thay vào đó nghĩ rằng nếu rà hoạt động mạng xã hội của người dùng để tạo mô hình căn thời điểm thông báo tinh vi hơn thì chỉ số người dùng sẽ tốt hơn
      Trong quá trình cố giảm tỷ lệ rời bỏ, những người ra quyết định đã quyết định một cách nghiêm ngặt dựa trên dữ liệu
    • vflat rất tốt cho mục đích này

  • Sau khi John Warnock rời vị trí CEO của Adobe, ông tham gia sâu hơn vào Octavo, một công ty bảo tồn sách lịch sử hiếm
    Một trong những thách thức họ gặp phải là làm phẳng độ cong của các trang scan không thể ép mở ra được
    https://en.m.wikipedia.org/wiki/Rare_Book_Room

  • Bài viết rất hay
    Có thể dùng trong công ty như một ví dụ tham khảo về cách ghi chép hiệu quả một dự án kỹ thuật và các quyết định của nó

  • Hồi đại học, khi định làm một ứng dụng scan ghi chú được phân biệt bằng màu, tôi gặp một vấn đề khác
    Màu bị lệch dần từ trên xuống dưới trang, khiến rất khó phân biệt ổn định giữa bút xanh dương và bút xanh lá
    Một ngày nào đó tôi nên xem lại việc này

    • Nếu giả định nền trắng cũng bị lệch theo cùng cách, một mẹo hay là sao chép ảnh, làm mờ thật mạnh, rồi chia ảnh gốc cho phiên bản đã làm mờ đó
      Làm vậy về cơ bản sẽ loại bỏ các biến thiên màu sắc/độ sáng tần số thấp
      Cách này thường được dùng để khử bóng khi chụp ảnh giấy, và tôi nghĩ nó cũng sẽ hiệu quả tương tự với gradient màu

  • Trông đủ ổn
    Tuy nhiên, mô hình biến dạng có vẻ hơi quá mang tính toàn cục
    Một số biến dạng phức tạp hơn của giấy không được mô hình nắm bắt, và vẫn thấy chúng như biến dạng còn sót lại trong kết quả cuối

  • Gặp lỗi khi cài đặt:
    ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)
    ERROR: No matching distribution found for cv2>=3.0
    Tôi đã mở issue trên GitHub

  • Rất tuyệt
    Ước gì có một ứng dụng quét tài liệu tốt dùng được trên di động, làm tốt cả hiệu chỉnh biến dạng, thresholding và tạo PDF
    Hiện tôi bị kẹt với Adobe Scan vì kết quả của nó còn tạm là tốt nhất, nhưng phần hiệu chỉnh biến dạng vẫn khá tệ

    • Tôi nghe nói Microsoft Lens tốt, nhưng mở trên điện thoại của tôi thì nó cứ treo luôn

  • Đọc thật sự thú vị
    Có vẻ là bài viết từ năm 2016 mà tôi đã bỏ lỡ; tôi thích cách nó thể hiện rõ toàn bộ mạch “có vấn đề này, áp dụng một kỹ thuật thông minh và thu được lời giải hoạt động tốt”
    Cá nhân tôi chắc sẽ không bao giờ cần thứ như thế, nhưng đây là một ví dụ tuyệt vời về việc xử lý vấn đề theo cách tốt và thỏa hiệp vừa phải trong phạm vi mà kết quả đầu ra và kỳ vọng cho phép
    Bài viết cũng được viết tốt và giải thích hay

  • Nếu không cần hiển thị cuốn sách bằng hình ảnh mà chỉ cần OCR, có lẽ có thể bỏ qua bước này
    Google đã giải quyết vấn đề này hơn 10 năm trước: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
    Nếu bản thảo thực sự có giá trị, cũng có thể hiệu chỉnh biến dạng không tiếp xúc bằng chụp cắt lớp tia X: https://scrollprize.org/tutorial1

    • Vậy thì cứ tìm phần mềm dùng được rồi giới thiệu là được
      Phía Google đã dùng phần cứng, còn chuyện chụp cắt lớp tia X nghe rất có mùi ChatGPT
      Dù vậy, cách trong bài này vẫn đẹp và đơn giản nếu xét theo thời điểm năm 2016