Tối ưu hóa biểu đồ vector: Tạo file SVG siêu nhỏ gọn với thuật toán ODF

Tối ưu hóa biểu đồ vector: Tạo file SVG siêu nhỏ gọn với thuật toán ODF

Đồ họa vector là phương thức tự nhiên và hiệu quả nhất để trực quan hóa các hàm số toán học. Khác với hình ảnh raster (dựa trên điểm ảnh), đồ họa vector sử dụng các đoạn đường cong để biểu diễn hình dạng, cho phép phóng to vô hạn mà không bị vỡ hình hay mất chi tiết. Tuy nhiên, việc tạo ra các file vector chất lượng cao nhưng vẫn giữ được dung lượng tối thiểu luôn là một thách thức lớn cho các lập trình viên.

Bài viết này sẽ khám phá cách sử dụng thuật toán Orthogonal Distance Fitting (ODF) để tạo ra các biểu đồ SVG siêu nhỏ gọn mà không làm giảm chất lượng hiển thị.

Ví dụ về đồ họa vector

Thách thức khi tạo biểu đồ vector thông thường

Khi sử dụng các thư viện vẽ biểu đồ phổ biến như Matplotlib, các hàm số mượt mà thường được xấp xỉ bằng hàng trăm đoạn thẳng kết nối nhau (piecewise linear). Ví dụ, khi vẽ hàm số f(t) = exp(-t)cos(-2πt) trên khoảng 0 ≤ t ≤ 5, Matplotlib có thể tạo ra tới 250 đoạn thẳng riêng biệt.

Mặc dù kết quả trông có vẻ mượt mà, nhưng cách tiếp cận này khiến file SVG trở nên cồng kềnh không cần thiết. Trong khi đó, các định dạng vector như SVG hay Postscript lại sử dụng đường cong Bézier bậc ba (cubic Bézier curves) làm nguyên thủy cơ bản. Việc tận dụng tối đa các đường cong này thay vì các đoạn thẳng đơn lẻ là chìa khóa để giảm dung lượng file.

Giải pháp: Thuật toán ODF và đường cong Bézier

Thay vì dùng hàng trăm đoạn thẳng, chúng ta có thể sử dụng thuật toán ODF để khớp (fit) dữ liệu vào chỉ một vài đường cong Bézier. Trong ví dụ trên, thuật toán này có thể giảm số lượng phần tử vẽ từ 250 xuống chỉ còn 8 đường cong Bézier, trong khi kết quả thị giác gần như không thể phân biệt được với bản gốc của Matplotlib.

Minh họa thuật toán khớp đường cong

Cơ chế hoạt động của thuật toán

Quy trình khớp đường cong (Algorithm F) hoạt động theo các bước chính sau:

1. Xấp xỉ chuỗi Chebyshev: Thuật toán đầu tiên khớp một chuỗi Chebyshev để xấp xỉ hàm số mục tiêu. Đối với các hàm giải tích, phương pháp nội suy tại các điểm nút Chebyshev mang lại sự hội tụ hình học nhanh chóng, vượt trội so với nội suy spline bậc ba hay đoạn tuyến tính.
2. Tối ưu hóa vùng tin cậy (Trust-region optimizer): Sau khi có chuỗi Chebyshev, thuật toán tìm kiếm đường cong Bézier tối ưu để xấp xỉ chuỗi này. Việc sử dụng trình tối ưu hóa vùng tin cậy giúp tránh bị mắc kẹt tại các điểm yên ngựa và đảm bảo tìm được nghiệm tối ưu toàn cục.
3. Kiểm tra sai số và chia nhỏ: Thuật toán tính toán khoảng cách trực giao tối đa giữa đường cong Bézier và hàm số. Nếu sai số nhỏ hơn ngưỡng cho phép, quá trình kết thúc. Nếu không, miền định nghĩa sẽ được chia làm hai và quá trình lặp lại cho đến khi đạt độ chính xác mong muốn.

Ứng dụng thực tế với thư viện bbai

Để áp dụng thuật toán này vào thực tế, chúng ta có thể sử dụng thư viện Python bbai. Thư viện này cung cấp công cụ BezierPath giúp chuyển đổi các hàm số phức tạp thành mã TikZ hoặc SVG một cách dễ dàng.

Ví dụ, để khớp một hàm Gaussian, ta chỉ cần vài dòng mã:

from bbai.graphics import BezierPath
import numpy as np

def f(t):
    return np.exp(-t * t)

path = BezierPath(
    dst_xmin=0, dst_xmax=9.5,
    dst_ymin=0, dst_ymax=2)
path.fit(f, -2, 2)
print(path.tikz_)

Kết quả là một đường cong mượt mà được tạo ra chỉ từ 2 đường cong Bézier, thay vì hàng trăm điểm rời rạc. Thư viện này cũng hỗ trợ các hàm số tham số phức tạp hơn như hình Hypotrochoid.

Xuất file SVG với MetaPost

Sau khi có mã đường cong (thường ở định dạng TikZ), bước cuối cùng là chuyển đổi nó thành hình ảnh SVG để sử dụng trên web. Mặc dù có thể dùng LaTeX để chuyển đổi, nhưng sử dụng MetaPost là phương pháp trực tiếp và hiệu quả hơn.

MetaPost là ngôn ngữ vẽ hình có khả năng xuất trực tiếp ra SVG. Bằng cách nhúng mã đường cong vào một file MetaPost đơn giản và chạy lệnh mpost, ta có thể nhận được file SVG chất lượng cao, sẵn sàng tích hợp vào các trang web.

Kết quả xuất SVG

Kết luận

Việc sử dụng thuật toán ODF để khớp đường cong Bézier mang lại lợi ích to lớn trong việc tối ưu hóa đồ họa vector. Đối với các hàm số giải tích hoặc có độ khả vi cao, phương pháp này tạo ra biểu diễn tối giản, giúp giảm đáng kể dung lượng file và tăng tốc độ tải trang mà vẫn giữ nguyên độ sắc nét.

Trong tương lai, thuật toán này có thể được mở rộng để xử lý tốt hơn các hàm số có điểm gãy (non-analytic points), mở rộng hơn nữa phạm vi ứng dụng trong trực quan hóa dữ liệu.