Patent Document ID: 20010051860
Application ID: 09866890
Patent Flag: 0

Claim One:
1. A method for performing convolution of an n-dimensional pattern p(x1,..., x n ), with a smooth kernel d which is at least approximately equal to a separated-spline kernel, to generate data indicative of a convolution result r&equals;Dp&equals;d×p, where D is the circulant of d, and n is greater than one, said method including the steps of: (a) specifying the separated-spline kernel as k(x 1,..., x n )&equals;k 1 (x x )... k n (x n ), where k j has circulant K j, k(x 1,..., x n ) admits of an operator A&equals;A 1 A 2... A n, and A j is an annihilation or flattening operator which operates on the circulant K j of kernel k j in such a manner that A j K j is sparse (when A j is an annihilation operator) or A j K j is almost everywhere a locally constant matrix (when A j is a flattening operator); (b) processing pattern data indicative of the pattern p and kernel data indicative of the kernel k, to generate additional data indicative of q 1 &equals;A 1 k 1 ×p for each row of the pattern p; (c) processing the additional data to backsolve A 1 r 1 &equals;q 1 for said each row of the pattern to determine data indicative of r 1 &equals;k 1 ×p for said pattern, by performing a preliminary ignition step in which a small number of components of r 1 are computed directly, and then determining all other ones of the components of r 1 using a natural recurrence relation determined by the operator A 1 ; (d) processing the data indicative of r 1 &equals;k 1 ×p to generate data indicative of q 2 &equals;A 2 k 2 ×(k 1 ×p) T for each row of (k 1 ×p) T, where r 1 T &equals;(k 1 ×p) T denotes transposition of r 1 ; and (e) processing the data indicative of q 2 &equals;A 2 k 2 ×r 1 T to backsolve A 2 r 2 T &equals;q 2 for said each row of (k 1 ×p) T thereby determining data indicative of r 2 T &equals;(k 2 ×k 1 ×p) T for said pattern p.