Method for filtering data with arbitrary kernel filters
View Patent ↗A computer implemented method filters input data with a kernel filter. A kernel filter is defined, and a set of unique filter coefficients for the kernel filter are determined. A linkage set is constructed for each unique filter coefficient such that the linkage set includes relative links to positions in the kernel filter that have identical filter coefficients, and in which each relative link is an inverse of the position of the unique filter coefficient. Each input data point is processed by multiply values on which the kernel filter is centered by each of the unique filter coefficients, and adding results of the multiplying to the corresponding output data points as referenced by the relative links.
1. A computer implemented method for filtering input data with a kernel filter, comprising the steps of:
defining a kernel filter S in a d-dimensional real valued Cartesian space R d , in which the kernel filter maps input data I within the kernel filter centered around an input data point p=[x 1 , . . . , x d ] in the space, to corresponding m-dimensional output data points
I ( p; S )→ y ( p )=[ y 1 , . . . , y m ], and in which
filter assigns a real valued coefficient f(p) to each of the input data points p in the kernel filter;
determining a set of unique filter coefficients w i =i=1, . . . , U for the kernel filter;
constructing a linkage set L i for each unique filter coefficient w i such that the linkage set includes relative links to positions in the kernel filter that have identical filter coefficients L i ={l i0 , . . . , l i L i }, in which each relative link l ij is an inverse of the position of the unique filter coefficient; and
processing each input data point by multiply values on which the kernel filter is centered by each of the unique filter coefficients, and adding results of the multiplying to the corresponding output data points as referenced by the relative links:
w
1
I
(
p
)
→
y
(
p
+
l
11
)
,
…
,
y
(
p
+
l
1
L
1
)
⋮
→
⋮
w
U
I
(
p
)
→
y
(
p
+
l
U
1
)
,
…
,
y
(
p
+
l
UL
U
)
.
2. The method of claim 1 , in which the input data are bounded within a range N 1 , . . . , N d , where 0≦x i <N i .
3. The method of claim 2 , in which a single channel image kernel filter is defined in two dimensions, and color and video kernel filters are defined in three dimensions.
4. The method of claim 1 , in which a response of the kernel filter is
y
(
p
)
=
∑
k
∈
S
f
(
k
)
I
(
k
+
p
)
.
5. The method of claim 1 , in which m=1, and the kernel filter maps to a scalar, and y(p)=y 1 .
6. The method of claim 1 , in which the position in the kernel filter is (x 1 , x 2 ) and the relative link is (−x 2 , −x 2 ) with respect to indexing the kernel filter.
7. The method of claim 1 , in which the unique filter coefficients and the relative links are predetermined one time for the kernel filter in a preprocessing phase.
8. The method of claim 1 , further comprising:
determining p ij =(x 1 (i,j), x 2 (i,j)) and l ij =(−x 1 (i,j), −x 2 (i,j) for each input data point.
9. The method of claim 1 , in which the input data are pixels in an image, and the kernel filter is swept across the image in a selected order, and further comprising:
weighting each input data point I(x 1 , x 2 ) using the corresponding relative links.
10. The method of claim 1 , in which each input data point is multiplied only once by each unique filter coefficient, while adding the results of the multiplying to the corresponding output data points using the corresponding relative links.
11. The method of claim 1 , further comprising:
determining a summation
y
(
p
)
=
∑
i
U
(
w
i
∑
j
L
j
I
(
p
+
l
ij
)
)
.
12. The method of claim 1 , in which the kernel filter is selected from a group comprising quad-symmetric filters, Gabor filters, moving average filters, gray level morphological operator filters, volume smoothing functions, Gaussian filters, sinc filters, and low-pass filters.
13. The method of claim 1 , in which the kernel filter has an arbitrary shape and size.
14. The method of claim 1 , in which the kernel filter is a linear filter.
15. The method of claim 1 , in which the input data points are processed simultaneously in parallel by accumulating the results to the corresponding output data points.