Module: Convolver

Defined in:
lib/convolver.rb,
lib/convolver/version.rb,
ext/convolver/convolver.c

Constant Summary collapse

VERSION = 
"0.3.2"

Class Method Summary collapse

Class Method Details

.convolve(signal, kernel) ⇒ NArray

Chooses and calls likely fastest method from #convolve_basic and #convolve_fftw3. The two parameters must have the same rank. The output has same rank, its size in each dimension d is given by

signal.shape[d] - kernel.shape[d] + 1

If you always perform convolutions of the same size, you may be better off benchmarking your own code using either #convolve_basic or #convolve_fftw3, and have your code use the fastest.

Parameters:

  • signal (NArray) —

    must be same size or larger than kernel in each dimension

  • kernel (NArray) —

    must be same size or smaller than signal in each dimension

Returns:

  • (NArray) —

    result of convolving signal with kernel



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/convolver.rb', line 16

def self.convolve signal, kernel
  # For small signals or kernels, just go straight to basic
  if signal.size < 1000 || kernel.size < 100
    return convolve_basic( signal, kernel )
  end

  # If predicted time is less than a millisecond, just do a basic convolve
  basic_time_predicted = predict_convolve_basic_time( signal, kernel )
  if basic_time_predicted < 0.1
    return convolve_basic( signal, kernel )
  end

  # Factor of two to allow for large uncertainty in predictions for FFTW3
  fft_time_predicted = predict_convolve_fft_time( signal, kernel )
  if fft_time_predicted < 2 * basic_time_predicted
    return convolve_fftw3( signal, kernel )
  end

  convolve_basic( signal, kernel )
end

.convolve_basic(signal, kernel) ⇒ NArray

Calculates convolution of an array of floats representing a signal, with a second array representing a kernel. The two parameters must have the same rank. The output has same rank, its size in each dimension d is given by

signal.shape[d] - kernel.shape[d] + 1

Parameters:

  • signal (NArray) —

    must be same size or larger than kernel in each dimension

  • kernel (NArray) —

    must be same size or smaller than signal in each dimension

Returns:

  • (NArray) —

    result of convolving signal with kernel



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'ext/convolver/convolver.c', line 73

static VALUE narray_convolve( VALUE self, VALUE a, VALUE b ) {
  struct NARRAY *na_a, *na_b, *na_c;
  volatile VALUE val_a, val_b, val_c;
  int target_rank, i;
  int target_shape[LARGEST_RANK];

  val_a = na_cast_object(a, NA_SFLOAT);
  GetNArray( val_a, na_a );

  val_b = na_cast_object(b, NA_SFLOAT);
  GetNArray( val_b, na_b );

  if ( na_a->rank != na_b->rank ) {
    rb_raise( rb_eArgError, "narray a must have equal rank to narray b (a rack %d, b rank %d)", na_a->rank,  na_b->rank );
  }

  if ( na_a->rank > LARGEST_RANK ) {
    rb_raise( rb_eArgError, "exceeded maximum narray rank for convolve of %d", LARGEST_RANK );
  }

  target_rank = na_a->rank;

  for ( i = 0; i < target_rank; i++ ) {
    target_shape[i] = na_a->shape[i] - na_b->shape[i] + 1;
    if ( target_shape[i] < 1 ) {
      rb_raise( rb_eArgError, "narray b is bigger in one or more dimensions than narray a" );
    }
  }

  val_c = na_make_object( NA_SFLOAT, target_rank, target_shape, CLASS_OF( val_a ) );
  GetNArray( val_c, na_c );

  convolve_raw(
    target_rank, na_a->shape, (float*) na_a->ptr,
    target_rank, na_b->shape, (float*) na_b->ptr,
    target_rank, target_shape, (float*) na_c->ptr );

  return val_c;
}

.convolve_fftw3(signal, kernel) ⇒ NArray

Uses FFTW3 library to calculate convolution of an array of floats representing a signal, with a second array representing a kernel. The two parameters must have the same rank. The output has same rank, its size in each dimension d is given by

signal.shape[d] - kernel.shape[d] + 1

Parameters:

  • signal (NArray) —

    must be same size or larger than kernel in each dimension

  • kernel (NArray) —

    must be same size or smaller than signal in each dimension

Returns:

  • (NArray) —

    result of convolving signal with kernel



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/convolver.rb', line 44

def self.convolve_fftw3 signal, kernel
  combined_shape, shift_by, ranges = fft_offsets( signal.shape, kernel.shape )

  mod_a = NArray.sfloat(*combined_shape)
  mod_a[*shift_by] = signal

  mod_b = NArray.sfloat(*combined_shape)

  Convolver.fit_kernel_backwards( mod_b, kernel )

  afreqs = FFTW3.fft(mod_a)
  bfreqs = FFTW3.fft(mod_b)
  cfreqs = afreqs * bfreqs

  (FFTW3.ifft( cfreqs ).real * (1.0/mod_a.size))[*ranges]
end

.predict_convolve_basic_time(signal, kernel) ⇒ Float

A rough estimate of time that #convolve will take, based on complexity of its operations, and some rough benchmarking. A value of 1.0 corresponds to results varying bewteen 2 and 8 milliseconds on the test computer.

Parameters:

  • signal (NArray) —

    must be same size or larger than kernel in each dimension

  • kernel (NArray) —

    must be same size or smaller than signal in each dimension

Returns:

  • (Float) —

    rough estimate of time for convolution compared to baseline



77
78
79
80
 
# File 'lib/convolver.rb', line 77

def self.predict_convolve_basic_time signal, kernel
  outputs = shape_to_size( result_shape( signal.shape, kernel.shape ) )
  4.54e-12 * (outputs * shape_to_size( signal.shape ) * shape_to_size( kernel.shape ))
end

.predict_convolve_fft_time(signal, kernel) ⇒ Float

A rough estimate of time that #convolve_fftw3 will take, based on complexity of its operations, and some rough benchmarking. A value of 1.0 corresponds to results varying between 1 and 12 milliseconds on the test computer.

Parameters:

  • signal (NArray) —

    must be same size or larger than kernel in each dimension

  • kernel (NArray) —

    must be same size or smaller than signal in each dimension

Returns:

  • (Float) —

    rough estimate of time for convolution compared to baseline



67
68
69
 
# File 'lib/convolver.rb', line 67

def self.predict_convolve_fft_time signal, kernel
  16 * 4.55e-08 * result_shape(signal.shape,kernel.shape).inject(1) { |t,x| t * x * Math.log(x) }
end