Tôi đang cố triển khai thuật toán thị giác, bao gồm một giai đoạn lọc sơ bộ với bộ lọc Laplacian-of-Gaussian 9x9. Bạn có thể trỏ đến tài liệu giải thích nhanh việc triển khai bộ lọc nhanh không? Tôi nghĩ rằng tôi nên sử dụng FFT để lọc hiệu quả nhất.Cách nhanh để thực hiện chuyển đổi 2D trong C
Bạn có chắc chắn muốn sử dụng FFT không? Đó sẽ là một biến đổi toàn bộ mảng, sẽ tốn kém. Nếu bạn đã quyết định trên một bộ lọc convolution 9x9, bạn không cần bất kỳ FFT.
Nói chung, cách rẻ nhất để thực hiện convolution trong C là thiết lập vòng lặp di chuyển con trỏ qua mảng, tổng hợp các giá trị được chuyển đổi tại mỗi điểm và ghi dữ liệu vào mảng mới. Vòng lặp này sau đó có thể được song song bằng cách sử dụng phương thức yêu thích của bạn (trình biên dịch vectơ hóa, các thư viện MPI, OpenMP, vv).
Về ranh giới:
4 điểm là vì ranh giới tối đa chồng chéo của hạt nhân 9x9 là 4 điểm bên ngoài lưới chính. Do đó, n điểm biên cần cho hạt nhân 2n + 1 x 2n + 1.
Nếu bạn cần convolution này thực sự nhanh, và/hoặc lưới của bạn lớn, hãy xem xét phân vùng thành các phần nhỏ hơn có thể được giữ trong bộ nhớ cache của bộ xử lý và do đó được tính toán nhanh hơn rất nhiều. Điều này cũng xảy ra với bất kỳ việc tải xuống GPU nào bạn có thể muốn thực hiện (chúng lý tưởng cho loại tính toán dấu phẩy động này).
Dưới đây là một liên kết lý thuyết http://hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf
Và đây là một liên kết đến fftw, mà là một thư viện FFT khá tốt mà tôi đã sử dụng trong quá khứ (giấy phép kiểm tra để chắc chắn rằng nó phù hợp) http://www.fftw.org/
Tất cả những gì bạn làm là FFT hình ảnh và hạt nhân của bạn (ma trận 9x9). Nhân với nhau, sau đó trở lại biến đổi.
Tuy nhiên, với ma trận 9x9 bạn vẫn có thể thực hiện tốt hơn trong các tọa độ thực (chỉ với vòng lặp đôi trên pixel hình ảnh và ma trận). Hãy thử cả hai cách!
Thực ra bạn không cần sử dụng kích thước FFT đủ lớn để giữ toàn bộ hình ảnh. Bạn có thể thực hiện nhiều bản ghép 2d chồng chéo nhỏ hơn. Bạn có thể tìm kiếm "convolution nhanh" "chồng chéo lưu" "chồng chéo thêm".
Tuy nhiên, đối với hạt nhân 9x9. Bạn có thể không thấy nhiều lợi thế theo chiều kim đồng hồ.
Sử dụng đường biên của số 0 cho rằng dữ liệu khá trắng và không có ý nghĩa. Sử dụng bộ lọc mờ trên dữ liệu trung bình khác không có ranh giới bằng 0 sẽ dẫn đến biến dạng không mong muốn trên các cạnh. –
Đủ rồi. Thay vào đó, việc sử dụng FFT sẽ giả định rằng dữ liệu kết thúc tốt đẹp ở các ranh giới, điều này cũng có thể sai. Các zero là để loại bỏ ifs đắt tiền. Tôi sẽ thêm một cái gì đó về ranh giới. –
Jukka ranh giới luôn luôn bị.Bạn phải làm một cái gì đó để giải thích cho nó và Phil đề cập đến một vài phương pháp truyền thống. Cách duy nhất để không bị ranh giới là thực hiện chuyển đổi 2d và sau đó cắt 4 pixel trên tất cả các cạnh của hình ảnh. –