Chuyển đổi 2D nhanh cho DSP

Question

Tôi muốn triển khai một số thuật toán xử lý hình ảnh được thiết kế để chạy trên beagleboard. Các thuật toán này sử dụng các convolutions rộng rãi. Tôi đang cố gắng để tìm một thực hiện tốt C cho 2D convolution (có thể sử dụng Fast Fourier Transform). Tôi cũng muốn các thuật toán để có thể chạy trên DSP của beagleboard, bởi vì tôi đã nghe nói rằng DSP được tối ưu hóa cho các loại hoạt động (với hướng dẫn nhân tích lũy của nó).

Tôi không có nền tảng trong lĩnh vực này vì vậy tôi nghĩ sẽ không tốt nếu thực hiện bản thân chập chững (tôi có lẽ sẽ không làm tốt như người hiểu tất cả toán học đằng sau nó). Tôi tin rằng một thực hiện tốt C convolution cho DSP tồn tại một nơi nào đó nhưng tôi đã không thể tìm thấy nó?

Ai đó có thể trợ giúp?

EDIT: Tắt hạt nhân là khá nhỏ. Kích thước của nó là 2X2 hoặc 3X3. Vì vậy, tôi đoán tôi không tìm kiếm một triển khai dựa trên FFT. Tôi đã tìm kiếm convolution trên web để xem định nghĩa của nó vì vậy tôi có thể thực hiện nó một cách thẳng về phía trước (tôi không thực sự biết những gì convolution là). Tất cả tôi đã tìm thấy là một cái gì đó với tích phân nhân và tôi không có ý tưởng làm thế nào để làm điều đó với ma trận. Ai đó có thể cho tôi một đoạn mã (hoặc mã giả) cho vỏ hạt nhân 2X2 không?

Answer 1

Kích thước của hình ảnh và hạt nhân là gì? Nếu hạt nhân lớn thì bạn có thể sử dụng phép biến đổi dựa trên FFT, nếu không cho các hạt nhân nhỏ chỉ sử dụng chập trực tiếp.

DSP có thể không phải là cách tốt nhất để làm điều này mặc dù - chỉ vì nó có lệnh MAC không có nghĩa là nó sẽ hiệu quả hơn. CPU ARM trên Bảng Beagle có NEON SIMD không? Nếu vậy thì đó có thể là cách để đi (và vui hơn nữa).

Đối với một hạt nhân nhỏ, bạn có thể làm chập trực tiếp như thế này:

// in, out are m x n images (integer data) 
// K is the kernel size (KxK) - currently needs to be an odd number, e.g. 3 
// coeffs[K][K] is a 2D array of integer coefficients 
// scale is a scaling factor to normalise the filter gain 

for (i = K/2; i < m - K/2; ++i) // iterate through image 
{ 
    for (j = K/2; j < n - K/2; ++j) 
    { 
    int sum = 0; // sum will be the sum of input data * coeff terms 

    for (ii = - K/2; ii <= K/2; ++ii) // iterate over kernel 
    { 
     for (jj = - K/2; jj <= K/2; ++jj) 
     { 
     int data = in[i + ii][j +jj]; 
     int coeff = coeffs[ii + K/2][jj + K/2]; 

     sum += data * coeff; 
     } 
    } 
    out[i][j] = sum/scale; // scale sum of convolution products and store in output 
    } 
} 

Bạn có thể sửa đổi này để hỗ trợ thậm chí giá trị của K - nó chỉ mất một chút chăm sóc với các chữ hoa/giới hạn thấp hơn trên hai vòng trong.

Answer 2

Tôi biết nó có thể không có chủ đề nhưng do sự giống nhau giữa C và JavaScript tôi tin rằng nó vẫn có thể hữu ích. PS: Lấy cảm hứng từ câu trả lời @Paul R.

Hai kích thước 2D thuật toán chập trong JavaScript sử dụng các mảng

function newArray(size){ 
    var result = new Array(size); 
    for (var i = 0; i < size; i++) { 
     result[i] = new Array(size); 
    } 

    return result; 
} 

function convolveArrays(filter, image){ 
    var result = newArray(image.length - filter.length + 1); 

    for (var i = 0; i < image.length; i++) { 
     var imageRow = image[i]; 
     for (var j = 0; j <= imageRow.length; j++) { 

      var sum = 0; 
      for (var w = 0; w < filter.length; w++) { 
       if(image.length - i < filter.length) break; 

       var filterRow = filter[w]; 
       for (var z = 0; z < filter.length; z++) { 
        if(imageRow.length - j < filterRow.length) break; 
        sum += image[w + i][z + j] * filter[w][z]; 
       } 
      } 

      if(i < result.length && j < result.length) 
       result[i][j] = sum; 
     } 
    } 

    return result; 
} 

Bạn có thể kiểm tra các bài viết trên blog đầy đủ tại http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional-convolution-algorithm-with-arrays-in-javascript/