# Implementation of 2D Discrete Wavelet Transform by Number Theoretic Transform and 2D Overlap-Save Method

Authors: Lina Yang; Yuan Yan Tang; Qi Sun
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

To reduce the computation complexity of wavelet transform, this paper presents a novel approach to be implemented. It consists of two key techniques: (1)  fast number theoretic transform(FNTT)  In the FNTT, linear convolution is replaced by the circular one. It can speed up the computation of 2D discrete wavelet transform. (2) In two-dimensional overlap-save method directly calculating the FNTT to the whole input sequence may meet two difficulties; namely, a big modulo obstructs the effective implementation of the FNTT and a long input sequence slows the computation of the FNTT down. To fight with such deficiencies, a new technique which is referred to as 2D overlap-save method is developed. Experiments have been conducted. The fast number theoretic transform and 2D overlap-method have been used to implement the dyadic wavelet transform and applied to contour extraction in pattern recognition.


---

## Body

## 1. Introduction

Wavelet transform plays an important role in image processing, pattern recognition, document analyses, and so forth [1–12]. The basic operation of it, in fact, is a linear convolution.In digital signal processing, a signal is represented by a discrete sequence. Therefore, the discrete wavelet transform can be utilized to process it. We have [13]
(1)
W
s
i
f
(
n
,
m
)
=
∬
f
(
u
,
v
)
ψ
s
i
(
n
-
u
,
m
-
v
)
d
u
d
v
=
∑
k
,
l
‍
f
(
n
-
1
-
k
,
m
-
1
-
l
)
ψ
k
,
l
s
,
i
,
where
(2)
ψ
k
,
l
s
,
i
=
∬
[
k
,
k
+
1
]
×
[
l
,
l
+
1
]
ψ
s
i
(
u
,
v
)
d
u
d
v
=
∫
k
/
s
(
k
+
1
)
/
s
‍
d
u
∫
l
/
s
(
l
+
1
)
/
s
‍
ψ
i
(
u
,
v
)
d
v
,
i
=
1,2
.
Explicitly, either continuous wavelet transform or discrete wavelet transform is essentially the operation of filtering. Directly calculating (1) may be time-consuming, because the number of multiplication operations may come large in this way. Although Mallat algorithm [14] can implement the wavelet transform successfully in some special cases, that is, in an orthogonal wavelet basis or in the multiresolution analysis, it is not a solution of all kinds of wavelet transforms. Therefore, studying how to speed up the general discrete wavelet transform is of great practical significance.Actually, the filtering is a linear convolution in signal processing. In the following, without loss of generality, we will begin with the definition ofLinear Convolution of two 2D sequences.The equation for a 2D finite impulse response of a filter can be represented in the similar way and given by(3)
y
n
1
,
n
2
=
∑
k
1
=
0
l
2
-
1
∑
k
2
=
0
m
2
-
1
h
k
1
,
k
2
x
n
1
-
k
1
,
n
2
-
k
2
n
1
-
k
1
≥
0
,
n
2
-
k
2
≥
0
fffffffffffffffffffff
⁡
d
d
d
n
1
=
0,1
,
…
,
n
2
=
0,1
,
…
,
where x
n
1
,
n
2 and y
n
1
,
n
2
(
n
1
=
0,1
,
…
,
n
2
=
0,1
,
…
,
) stand for the input and output of the filter, respectively, and h
k
1
,
k
2 denote the filtering coefficients (k
1
=
0,1
,
…
,
l
2
-
1, k
2
=
0,1
,
…
,
m
2
-
1).In many certain applications, we are required to compute only such an output sequence which is with a finite length in (3). Let x
n
1
,
n
2 be a 2D finite input of the filter with lengths l
1 and m
1. We compute the finite output as follows:
(4)
y
n
1
,
n
2
=
∑
k
1
=
0
l
2
-
1
∑
k
2
=
0
m
2
-
1
h
k
1
,
k
2
x
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
l
1
dddddddddddddddd
0
≤
n
2
-
k
2
<
m
1
ddddddddddddddd
⁡
d
i
n
1
=
0,1
,
…
,
l
1
-
1
,
n
2
=
0,1
,
…
,
m
1
-
1
.
hhddddhhhhh
In practice, the difference between the length of the input signal and that of the filter is often large. If we calculate convolution (4) directly, a large number of multiplication operations will be executed. In the meantime, a series of calculations to treat zeros will be performed, if fast Fourier transform (FFT) is used to speed up the computation. Both of these two methods will be time-consuming to compute the linear convolution. To overcome this problem, in this paper we will present a novel approach which is referred to our previous work as number theoretic transform (NTT) [15–17]. Also, we will prove that the computation of the linear convolution can be replaced by that of the cyclic convolution of two 2D sequences with lengths N
1
=
l
1
+
l
2
-
1 and N
2
=
m
1
+
m
2
-
1, respectively.For two 2D sequencesx
n
1
,
n
2 and h
n
1
,
n
2 of finite lengths N
1 and N
2, their cyclic convolution can be written by
(5)
y
n
1
,
n
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
h
k
1
,
k
2
x
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
,
dddd
where 〈
x
〉
N denotes the remainder r of x modulo N; that is, x
=
q
N
+
r, q is any integer and 0
≤
r
<
N.The number theoretic transform (NTT) provides an effective way to calculate the cyclic convolution. However, there exist two difficulties, if directly applying the NTT to the whole input sequence, namely:(i)
a considerable bigmodulo M has to be imposed. It obstructs the effective implementation of the NTT due to the limited length of the word which is used to store data in computers. It will, thus, become a bottleneck in the computation of convolution;
(iii)
the advantage of the fast computation of the NTT cannot be reached when the difference between the length of the input sequence and that of the filter sequence is large. Thus, it may not speed up the calculation of convolution in this case.To avoid using a bigmodulo M, we can use Chinese remainder theorem to reduce the length of themodulo M and successfully apply the NTT to calculate the convolution. Unfortunately, the number of multiplication operations will be at least doubled, and thus the computational complexity will increase. The second key technique will be worked out in this paper to overcome the above difficulties and speed up the calculation of the convolution. It is termed 2D overlap-save method, which is an expansion of the 1D overlap-save method. It can be used to implement the 2D wavelet transform when a big difference between the length of the input sequence x
n
1
,
n
2 and that of the filter sequence h
n
1
,
n
2 occurs. This method consists of three steps.(i)
First, the original 2D input sequence is equivalently divided into many small separated sections. This division brings two evident improvements.
(a)
The size of each section is much smaller than that of the whole input sequence, such that a smallmodulo M can be used, and the NTT can, therefore, be performed in a computer system.
(b)
The difference between the length of one section and that of the filter sequence becomes smaller, which makes the effective application of the NTT.
(ii)
In the second step, we calculate the cyclic convolution of each section with the filter sequence by NTT.
(iii)
Finally, the result of (4) is obtained by picking out data from each of the results calculated in the second step and combining these data together.In comparison with direct method and fast Fourier transform (FFT), it will be proved explicitly that the number of multiplication operations in the 2D overlap-save method will be smaller than that in any of those two methods in many particular cases.In the next section, the number theoretic transform (NTT) will be presented. Details of the 2D overlap-method will be discussed in Section3. A comparison of computation of the multiplication in three methods will be given in Section 4. A computational example will be presented as well as a practical experiment in Section 5 which will verify the efficiency of the proposed approach. In the experiment, the fast number theoretic transform and 2D overlap-method were applied to implement the dyadic wavelet transform extracting the contours in recognition of Chinese handwriting.


## 2. Number Theoretic Transform (NTT)

Suppose thath
k
1
,
k
2 are the filter coefficients (
k
1
=
0,1
,
…
,
l
2
-
1, k
2
=
0,1
,
…
,
m
2
-
1
); x
n
1
,
n
2 and y
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
1
-
1, n
2
=
0,1
,
…
,
m
1
-
1
) are the input and output of the filter, respectively. In the concrete applications of the discrete wavelet transform (DWT), the lengths of the input and output are very long (l
1 and m
1 are very big), while lengths of the filter coefficients are short (l
2 and m
2 are small). Therefore, if the direct method is used to calculate their linear convolution, the number of multiplication operations will be large. In this section, the 2D number theoretic transform (FNTT) will be applied to calculate the 2D circular convolution of 2D sequences of lengths N
1
=
l
1
+
l
2
-
1 and N
2
=
m
1
+
m
2
-
1. In a 2D number theoretic transform (NTT), if a modulo M is too big, the Chinese remainder theorem (CRT) will be utilized to reduce the length.


### 2.1.2D Linear Convolution and 2D Circular Convolution

Given two 2-dimensional sequencesx
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
1
-
1
,
n
2
=
0,1
,
…
,
m
1
-
1
) and h
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
2
-
1
,
n
2
=
0,1
,
…
,
m
2
-
1
), their linear convolution is defined by
(6)
y
n
1
,
n
2
=
∑
k
1
=
0
l
1
-
1
∑
k
2
=
0
m
1
-
1
x
k
1
,
k
2
h
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
l
2
ffffffffffffffffff
0
≤
n
2
-
k
2
<
m
2
fffffffffffffffff
⁡
=
∑
k
1
=
0
l
2
-
1
∑
k
2
=
0
m
2
-
1
h
k
1
,
k
2
x
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
l
1
fffffffffffffffffi
0
≤
n
2
-
k
2
<
m
1
ffffffffffffffffi
⁡
n
1
=
0,1
,
…
,
l
1
+
l
2
-
2
,
n
2
=
0,1
,
…
,
m
1
+
m
2
-
2
.
Given two 2-dimensional sequences x
n
1
,
n
2 and h
n
1
,
n
2 of lengths N
1 and N
2, respectively, their circular convolution is
(7)
d
d
y
n
1
,
n
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
h
k
1
,
k
2
x
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
,
where 〈
x
〉
N denotes the remainder r, x
=
q
N
+
r
,
0
≤
r
<
N.Proposition 1.
The linear convolution (6) can be computed by computing circular convolution of two 2-dimensional sequences of lengths N
1
=
l
1
+
l
2
-
1 and N
2
=
m
1
+
m
2
-
1, respectively.


### 2.2. Using 2D Number Theoretic Transform to Calculate the 2D Circular Convolution

LetM be a positive integer and suppose that x
n
1
,
n
2 and h
n
1
,
n
2 are two 2-dimensional integer sequences (
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
).Let(8)
d
d
X
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
α
n
1
k
1
β
n
2
k
2
(
mod
⁡
M
)
,
(9)
d
d
d
d
d
H
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
h
n
1
,
n
2
α
n
1
k
1
β
n
2
k
2
(
mod
⁡
M
)
,
(10)
d
d
d
d
d
Y
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
y
n
1
,
n
2
α
n
1
k
1
β
n
2
k
2
(
mod
⁡
M
)
,where (
k
1
=
0,1
,
…
,
N
1
-
1
,
k
2
=
0,1
,
…
,
N
2
-
1
), andα and β are two given integers, and y
n
1
,
n
2 denote the circular convolution as shown in (7), n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1.If a 2-dimensional transform (8) has an inverse transform
(11)
x
n
1
,
n
2
≡
N
1
-
1
·
N
2
-
1
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
X
k
1
,
k
2
α
-
n
1
k
1
α
-
n
2
k
2
(
mod
⁡
M
)
(
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
) and has circular convolution property,
(12)
Y
k
1
,
k
2
≡
X
k
1
,
k
2
H
k
1
,
k
2
(
mod
⁡
M
)
(
k
1
=
0,1
,
…
,
N
1
-
1
,
k
2
=
0,1
,
…
,
N
2
-
1
)
,
then congruence equation (8) is referred to as a 2-dimensional number theoretic transform mod
⁡
M and can be abbreviated to NTT mod
⁡
M.Agarwal and Burrus gave some sufficient conditions for existence of 2-dimensional NTT given withM
>
1, N
1
>
1, and N
2
>
1, (see [15]). In [17], the authors gave some sufficient and necessary conditions for existence. We have the following theorem.Theorem 2.
IfM
=
p
1
l
1
⋯
p
s
l
s, (
l
j
≥
1, j
=
1
,
…
,
s
), p
1
,
…
,
p
s are distinct primes, then the congruence equation (8) is a 2-dimensional NTT mod
⁡
M with the first dimension of length N
1 and the second dimension of length N
2, if and only if α
N
1
≡
1
(
mod
⁡
M
), β
N
2
≡
1
(
mod
⁡
M
) and α
j
≢
1
(
mod
⁡
p
k
)
(
1
≤
j
≤
N
1
-
1
), β
i
≢
1
(
mod
⁡
p
k
)
(
1
≤
i
≤
N
2
-
1
), k
=
1
,
…
,
s.Corollary 3.
The congruence equation (8) is a 2-dimensional NTT mod
⁡
M if and only if
(13)
l
c
m
[
N
1
,
N
2
]
∣
g
c
d
(
p
1
-
1
,
…
,
p
s
-
1
)
,
where l
c
m
[
N
1
,
N
2
] denotes the least common multiple of two integers N
1 and N
2 and g
c
d
(
a
,
b
) denotes the greatest common divisor of two integers a and b.Corollary 4.
Letp be an odd prime, and M
=
p. Then the congruence equation (8) is a 2-dimensional NTT mod
⁡
p, if and only if α
N
1
≡
1
(
mod
⁡
p
) and α
j
≢
1
(
mod
⁡
p
)
(
1
≤
j
≤
N
1
-
1
), β
N
2
≡
1
(
mod
⁡
p
), and β
j
≢
1
(
mod
⁡
p
)
(
1
≤
j
≤
N
2
-
1
).Clearly, from congruence equations (8), (9), (11), and (12), we can use the 2-dimensional NTT to calculate a 2-dimensional circular convolution.Finally, we obtain(14)
y
n
1
,
n
2
≡
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
(
mod
⁡
M
)
,
i
g
g
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
.SelectM so that
(15)
|
y
n
1
,
n
2
|
≤
min
⁡
{
|
x
n
1
,
n
2
|
max
⁡
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
|
h
k
1
,
k
2
|
,
d
d
d
d
d
d
|
h
n
1
,
n
2
|
max
⁡
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
|
x
k
1
,
k
2
|
}
<
M
2
,
where n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1, and M is an odd.If we use the 2-dimensional NTT to calculate the 2-dimensional circular convolutiony
n
1
,
n
2 so that |
y
n
1
,
n
2
|
<
M
/
2, then form congruence equation (14) we deduce that
(16)
d
d
d
y
n
1
,
n
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
,
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
.


### 2.3. Fast Number Theoretic Transform (FNTT)

The idea of FFT can be used to perform the NTT. In this subsection, a theoretic description will be presented briefly. More details will be given in Section5.Let(17)
U
0
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
0
,
n
2
β
n
2
k
2
,
…
,
U
N
1
-
1
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
N
1
-
1
,
n
2
β
n
2
k
2
(
mod
⁡
M
)
,
d
d
d
d
d
d
i
d
k
2
=
0,1
,
…
,
N
2
-
1
.From congruence equation (17), we deduce that
(18)
X
k
1
,
0
≡
∑
n
1
=
0
N
1
-
1
‍
U
n
1
,
0
α
n
1
k
1
,
…
,
X
k
1
,
N
2
-
1
≡
∑
n
1
=
0
N
1
-
1
‍
U
n
1
,
N
2
-
1
α
n
1
k
1
(
mod
⁡
M
)
,
f
d
f
d
d
d
d
d
k
1
=
0,1
,
…
,
N
1
-
1
.Suppose thatN
1 and N
2 satisfy inequalities, and we then can use the idea of FFT to calculate the congruence equations (17) and (18).For computing every(19)
U
n
1
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
β
n
2
k
2
(
mod
⁡
M
)
,
kkkki
(
k
2
=
0,1
,
…
,
N
2
-
1
)
in congruence equation (17), the numbers of all multiplication necessary are (
N
2
log
⁡
N
2
)
/
2 by using FFT algorithm. Hence, if using FFT algorithm to calculate the congruence
(20)
U
n
1
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
β
n
2
k
2
(
mod
⁡
M
)
,
sdfssf
(
k
2
=
0,1
,
…
,
N
2
-
1
)
in congruence equation (17), the numbers of all multiplication necessary are (
(
N
1
N
2
)
/
2
)
log
⁡
N
2.Similarly, if using FFT algorithm to calculate all congruence equations in (18), then the numbers of all multiplication necessary are (
(
N
2
N
1
)
/
2
)
log
⁡
N
1.Therefore, if using the fast number theoretic transform (FNTT) to calculate the congruence equation (8), the number of all multiplication necessary is
(21)
N
1
N
2
2
log
⁡
N
2
+
N
2
N
1
2
log
⁡
N
1
=
N
1
N
2
2
log
⁡
(
N
1
N
2
)
.
If M is very large, we may reduce the length of a word by using Chinese remainder theorem and it can be abbreviated to CRT.Therefore, we have the following proposition.Proposition 5.
Suppose that congruence equation (8) is a 2-dimensional NTT mod
⁡
M, where M
=
p
1
l
1
⋯
p
s
l
s
,
p
1
,
…
,
p
s are distinct primes; then, we have a total of s 2-dimensional NTT mod
⁡
p
i
l
i, and they are described as follows:
(22)
X
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
α
i
n
1
k
1
β
i
n
2
k
2
,
(
mod
⁡
p
i
l
i
)
g
i
k
1
=
0,1
,
…
,
N
1
-
1
,
k
2
=
0,1
,
…
,
N
2
-
1
,
where α
i
=
〈
α
〉
p
i
l
i, β
i
=
〈
β
〉
p
i
l
i,i
=
1,2
,
…
,
s.
If(23)
y
n
1
,
n
2
=

∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
≡
y
n
1
,
n
2
(
i
)
(
mod
⁡
p
i
l
i
)
ddddddddid
(
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
)
,
then
(24)
y
n
1
,
n
2
≡
∑
i
=
1
s
‍
M
i
′
M
i
y
n
1
,
n
2
(
i
)
(
mod
⁡
M
)
(
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
)
,
where M
=
p
i
l
i
M
i
,
M
i
′
M
i
≡
1
(
mod
⁡
p
i
l
i
)
,
i
=
1
,
…
,
s.Proof.
Because the congruence equation (8) is a 2-dimensionalNTT
mod
⁡
M, hence(25)
α
N
1
≡
1
(
mod
⁡
M
)
,
β
N
2
≡
1
(
mod
⁡
M
)
,
α
N
1
≡
1
(
mod
⁡
p
i
)
,
α
j
≢
1
(
mod
⁡
p
i
)
,
1
≤
j
<
N
1
,
β
N
2
≡
1
(
mod
⁡
p
i
)
,
β
h
≢
(
mod
⁡
p
i
)
,
1
≤
h
<
N
2
,
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
f
f
b
b
b
b
b
b
b
b
b
f
f
i
b
i
=
1,2
,
…
,
s
,
so
(26)
α
N
1
≡
1
(
mod
⁡
p
i
l
i
)
,
β
N
2
≡
1
(
mod
⁡
p
i
l
i
)
,
α
i
N
1
≡
α
N
1
≡
1
(
mod
⁡
p
i
)
,
α
i
j
≢
1
(
mod
⁡
p
i
)
,
ddddddddddddddddddddddidd
1
≤
j
<
N
1
,
β
i
N
2
≡
β
N
2
≡
1
(
mod
⁡
p
i
)
,
β
i
h
≢
1
(
mod
⁡
p
i
)
,
dddddddddddddddddddddddid
1
≤
h
<
N
2
,
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
i
=
1
,
…
,
s
.
Hence, the congruence equation (22) has a total of s 2-dimensional NTTs mod
⁡
p
i
l
i
,
i
=
1
,
…
,
s. From CRT and the congruence equation (23), we deduce that the congruence equation (24) holds.


## 2.1.2D Linear Convolution and 2D Circular Convolution

Given two 2-dimensional sequencesx
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
1
-
1
,
n
2
=
0,1
,
…
,
m
1
-
1
) and h
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
2
-
1
,
n
2
=
0,1
,
…
,
m
2
-
1
), their linear convolution is defined by
(6)
y
n
1
,
n
2
=
∑
k
1
=
0
l
1
-
1
∑
k
2
=
0
m
1
-
1
x
k
1
,
k
2
h
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
l
2
ffffffffffffffffff
0
≤
n
2
-
k
2
<
m
2
fffffffffffffffff
⁡
=
∑
k
1
=
0
l
2
-
1
∑
k
2
=
0
m
2
-
1
h
k
1
,
k
2
x
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
l
1
fffffffffffffffffi
0
≤
n
2
-
k
2
<
m
1
ffffffffffffffffi
⁡
n
1
=
0,1
,
…
,
l
1
+
l
2
-
2
,
n
2
=
0,1
,
…
,
m
1
+
m
2
-
2
.
Given two 2-dimensional sequences x
n
1
,
n
2 and h
n
1
,
n
2 of lengths N
1 and N
2, respectively, their circular convolution is
(7)
d
d
y
n
1
,
n
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
h
k
1
,
k
2
x
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
,
where 〈
x
〉
N denotes the remainder r, x
=
q
N
+
r
,
0
≤
r
<
N.Proposition 1.
The linear convolution (6) can be computed by computing circular convolution of two 2-dimensional sequences of lengths N
1
=
l
1
+
l
2
-
1 and N
2
=
m
1
+
m
2
-
1, respectively.


## 2.2. Using 2D Number Theoretic Transform to Calculate the 2D Circular Convolution

LetM be a positive integer and suppose that x
n
1
,
n
2 and h
n
1
,
n
2 are two 2-dimensional integer sequences (
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
).Let(8)
d
d
X
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
α
n
1
k
1
β
n
2
k
2
(
mod
⁡
M
)
,
(9)
d
d
d
d
d
H
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
h
n
1
,
n
2
α
n
1
k
1
β
n
2
k
2
(
mod
⁡
M
)
,
(10)
d
d
d
d
d
Y
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
y
n
1
,
n
2
α
n
1
k
1
β
n
2
k
2
(
mod
⁡
M
)
,where (
k
1
=
0,1
,
…
,
N
1
-
1
,
k
2
=
0,1
,
…
,
N
2
-
1
), andα and β are two given integers, and y
n
1
,
n
2 denote the circular convolution as shown in (7), n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1.If a 2-dimensional transform (8) has an inverse transform
(11)
x
n
1
,
n
2
≡
N
1
-
1
·
N
2
-
1
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
X
k
1
,
k
2
α
-
n
1
k
1
α
-
n
2
k
2
(
mod
⁡
M
)
(
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
) and has circular convolution property,
(12)
Y
k
1
,
k
2
≡
X
k
1
,
k
2
H
k
1
,
k
2
(
mod
⁡
M
)
(
k
1
=
0,1
,
…
,
N
1
-
1
,
k
2
=
0,1
,
…
,
N
2
-
1
)
,
then congruence equation (8) is referred to as a 2-dimensional number theoretic transform mod
⁡
M and can be abbreviated to NTT mod
⁡
M.Agarwal and Burrus gave some sufficient conditions for existence of 2-dimensional NTT given withM
>
1, N
1
>
1, and N
2
>
1, (see [15]). In [17], the authors gave some sufficient and necessary conditions for existence. We have the following theorem.Theorem 2.
IfM
=
p
1
l
1
⋯
p
s
l
s, (
l
j
≥
1, j
=
1
,
…
,
s
), p
1
,
…
,
p
s are distinct primes, then the congruence equation (8) is a 2-dimensional NTT mod
⁡
M with the first dimension of length N
1 and the second dimension of length N
2, if and only if α
N
1
≡
1
(
mod
⁡
M
), β
N
2
≡
1
(
mod
⁡
M
) and α
j
≢
1
(
mod
⁡
p
k
)
(
1
≤
j
≤
N
1
-
1
), β
i
≢
1
(
mod
⁡
p
k
)
(
1
≤
i
≤
N
2
-
1
), k
=
1
,
…
,
s.Corollary 3.
The congruence equation (8) is a 2-dimensional NTT mod
⁡
M if and only if
(13)
l
c
m
[
N
1
,
N
2
]
∣
g
c
d
(
p
1
-
1
,
…
,
p
s
-
1
)
,
where l
c
m
[
N
1
,
N
2
] denotes the least common multiple of two integers N
1 and N
2 and g
c
d
(
a
,
b
) denotes the greatest common divisor of two integers a and b.Corollary 4.
Letp be an odd prime, and M
=
p. Then the congruence equation (8) is a 2-dimensional NTT mod
⁡
p, if and only if α
N
1
≡
1
(
mod
⁡
p
) and α
j
≢
1
(
mod
⁡
p
)
(
1
≤
j
≤
N
1
-
1
), β
N
2
≡
1
(
mod
⁡
p
), and β
j
≢
1
(
mod
⁡
p
)
(
1
≤
j
≤
N
2
-
1
).Clearly, from congruence equations (8), (9), (11), and (12), we can use the 2-dimensional NTT to calculate a 2-dimensional circular convolution.Finally, we obtain(14)
y
n
1
,
n
2
≡
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
(
mod
⁡
M
)
,
i
g
g
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
.SelectM so that
(15)
|
y
n
1
,
n
2
|
≤
min
⁡
{
|
x
n
1
,
n
2
|
max
⁡
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
|
h
k
1
,
k
2
|
,
d
d
d
d
d
d
|
h
n
1
,
n
2
|
max
⁡
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
|
x
k
1
,
k
2
|
}
<
M
2
,
where n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1, and M is an odd.If we use the 2-dimensional NTT to calculate the 2-dimensional circular convolutiony
n
1
,
n
2 so that |
y
n
1
,
n
2
|
<
M
/
2, then form congruence equation (14) we deduce that
(16)
d
d
d
y
n
1
,
n
2
=
∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
,
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
.


## 2.3. Fast Number Theoretic Transform (FNTT)

The idea of FFT can be used to perform the NTT. In this subsection, a theoretic description will be presented briefly. More details will be given in Section5.Let(17)
U
0
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
0
,
n
2
β
n
2
k
2
,
…
,
U
N
1
-
1
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
N
1
-
1
,
n
2
β
n
2
k
2
(
mod
⁡
M
)
,
d
d
d
d
d
d
i
d
k
2
=
0,1
,
…
,
N
2
-
1
.From congruence equation (17), we deduce that
(18)
X
k
1
,
0
≡
∑
n
1
=
0
N
1
-
1
‍
U
n
1
,
0
α
n
1
k
1
,
…
,
X
k
1
,
N
2
-
1
≡
∑
n
1
=
0
N
1
-
1
‍
U
n
1
,
N
2
-
1
α
n
1
k
1
(
mod
⁡
M
)
,
f
d
f
d
d
d
d
d
k
1
=
0,1
,
…
,
N
1
-
1
.Suppose thatN
1 and N
2 satisfy inequalities, and we then can use the idea of FFT to calculate the congruence equations (17) and (18).For computing every(19)
U
n
1
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
β
n
2
k
2
(
mod
⁡
M
)
,
kkkki
(
k
2
=
0,1
,
…
,
N
2
-
1
)
in congruence equation (17), the numbers of all multiplication necessary are (
N
2
log
⁡
N
2
)
/
2 by using FFT algorithm. Hence, if using FFT algorithm to calculate the congruence
(20)
U
n
1
,
k
2
≡
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
β
n
2
k
2
(
mod
⁡
M
)
,
sdfssf
(
k
2
=
0,1
,
…
,
N
2
-
1
)
in congruence equation (17), the numbers of all multiplication necessary are (
(
N
1
N
2
)
/
2
)
log
⁡
N
2.Similarly, if using FFT algorithm to calculate all congruence equations in (18), then the numbers of all multiplication necessary are (
(
N
2
N
1
)
/
2
)
log
⁡
N
1.Therefore, if using the fast number theoretic transform (FNTT) to calculate the congruence equation (8), the number of all multiplication necessary is
(21)
N
1
N
2
2
log
⁡
N
2
+
N
2
N
1
2
log
⁡
N
1
=
N
1
N
2
2
log
⁡
(
N
1
N
2
)
.
If M is very large, we may reduce the length of a word by using Chinese remainder theorem and it can be abbreviated to CRT.Therefore, we have the following proposition.Proposition 5.
Suppose that congruence equation (8) is a 2-dimensional NTT mod
⁡
M, where M
=
p
1
l
1
⋯
p
s
l
s
,
p
1
,
…
,
p
s are distinct primes; then, we have a total of s 2-dimensional NTT mod
⁡
p
i
l
i, and they are described as follows:
(22)
X
k
1
,
k
2
≡
∑
n
1
=
0
N
1
-
1
‍
∑
n
2
=
0
N
2
-
1
‍
x
n
1
,
n
2
α
i
n
1
k
1
β
i
n
2
k
2
,
(
mod
⁡
p
i
l
i
)
g
i
k
1
=
0,1
,
…
,
N
1
-
1
,
k
2
=
0,1
,
…
,
N
2
-
1
,
where α
i
=
〈
α
〉
p
i
l
i, β
i
=
〈
β
〉
p
i
l
i,i
=
1,2
,
…
,
s.
If(23)
y
n
1
,
n
2
=

∑
k
1
=
0
N
1
-
1
‍
∑
k
2
=
0
N
2
-
1
‍
x
k
1
,
k
2
h
〈
n
1
-
k
1
〉
N
1
,
〈
n
2
-
k
2
〉
N
2
≡
y
n
1
,
n
2
(
i
)
(
mod
⁡
p
i
l
i
)
ddddddddid
(
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
)
,
then
(24)
y
n
1
,
n
2
≡
∑
i
=
1
s
‍
M
i
′
M
i
y
n
1
,
n
2
(
i
)
(
mod
⁡
M
)
(
n
1
=
0,1
,
…
,
N
1
-
1
,
n
2
=
0,1
,
…
,
N
2
-
1
)
,
where M
=
p
i
l
i
M
i
,
M
i
′
M
i
≡
1
(
mod
⁡
p
i
l
i
)
,
i
=
1
,
…
,
s.Proof.
Because the congruence equation (8) is a 2-dimensionalNTT
mod
⁡
M, hence(25)
α
N
1
≡
1
(
mod
⁡
M
)
,
β
N
2
≡
1
(
mod
⁡
M
)
,
α
N
1
≡
1
(
mod
⁡
p
i
)
,
α
j
≢
1
(
mod
⁡
p
i
)
,
1
≤
j
<
N
1
,
β
N
2
≡
1
(
mod
⁡
p
i
)
,
β
h
≢
(
mod
⁡
p
i
)
,
1
≤
h
<
N
2
,
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
f
f
b
b
b
b
b
b
b
b
b
f
f
i
b
i
=
1,2
,
…
,
s
,
so
(26)
α
N
1
≡
1
(
mod
⁡
p
i
l
i
)
,
β
N
2
≡
1
(
mod
⁡
p
i
l
i
)
,
α
i
N
1
≡
α
N
1
≡
1
(
mod
⁡
p
i
)
,
α
i
j
≢
1
(
mod
⁡
p
i
)
,
ddddddddddddddddddddddidd
1
≤
j
<
N
1
,
β
i
N
2
≡
β
N
2
≡
1
(
mod
⁡
p
i
)
,
β
i
h
≢
1
(
mod
⁡
p
i
)
,
dddddddddddddddddddddddid
1
≤
h
<
N
2
,
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
i
=
1
,
…
,
s
.
Hence, the congruence equation (22) has a total of s 2-dimensional NTTs mod
⁡
p
i
l
i
,
i
=
1
,
…
,
s. From CRT and the congruence equation (23), we deduce that the congruence equation (24) holds.


## 3. Two-Dimensional Overlap-Save Method

Select two positive integersN
′ and M
′, so that N
′
+
l
2
-
1
=
N
<
l
1 and M
′
+
m
2
-
1
=
M
<
m
1; either N or M is given by an integer power of 2; that is, N
=
2
d
1 and M
=
2
d
2 where d
1 and d
2 are two positive integers.Assuming that the input sequencex
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
1
-
1, n
2
=
0,1
,
…
,
m
1
-
1
) is divided into many small sections, which are termed submatrices,
(27)
d
d
d
d
{
x
n
1
+
v
1
N
′
,
n
2
+
v
2
M
′
}
n
1
=
0
,
n
2
=
0
n
1
=
N
-
1
,
n
2
=
M
-
1
dd
(
v
1
=
0,1
,
…
,
v
2
=
0,1
,
…
)
.
dd
The consecutive matrix is overlapped by the previous one. As a simple example, four blocks chosen from the divided input matrices are overlapped and are graphically shown in Figure 1. Parameters v
1 and v
2 can be considered as shift parameters, because changing either v
1 or v
2 will select different submatrix. For the first submatrix shown in Figure 1(a), we select v
1
=
0 and v
2
=
0. Second submatrix (v
1
=
0 and v
2
=
1) is displayed in Figure 1(b). Third one with parameters of v
1
=
1 and v
2
=
0 is given in Figure 1(c). Fourth matrix shown in Figure 1(d) has parameters v
1
=
1 and v
2
=
1. The procedure of the overlapping is also graphically illustrated in Figure 1.Four divided input submatrices are overlapped using the 2D overlap-save method: (a) the first submatrix, with parametersv
1
=
0
,
v
2
=
0, is located on the top-left corner; (b) the second one (v
1
=
1
,
v
2
=
0) overlaps by the first submatrix, and the size of the overlapping between them is N times m
2
-
1; (c) the third divided input submatrix has parameters of v
1
=
0
,
v
2
=
1. It is overlapped by the first submatrix, and the size of the overlapping between them is l
2
-
1 times M; (d) the fourth one with v
1
=
1
,
v
2
=
1 is overlapped by the first submatrix, and the size of the overlapping between them is l
2
-
1 times m
2
-
1.
(a)
(b)
(c)
(d)For the operation of circular convolution, it is necessary to have two sequences with the same length. Taking (7) for example, the sequences x
n
1
,
n
2 and h
n
1
,
n
2 are of the same length of N
1
×
N
2. Since the input sequence has already divided into submatrices of N
×
M by (27), the filter sequence has to be of length N
×
M. Therefore, N
-
l
2 augmenting zeros are required to be added to the row and M
-
m
2 zeros to the column of the filter sequence h
n
1
,
n
2. As a result, the sequence h
n
1
,
n
2 becomes
(28)
h
n
1
,
n
2
′

=

{
h
n
1
,
n
2
if
n
1
=
0,1
,
…
,
l
2
-
1
,
n
2
=
0,1
,
…
,
m
2
-
1
0
if
l
2
≤
n
1
<
N
or
m
2
≤
n
2
<
M
,
where n
1
=
0,1
,
…
,
N
-
1 and   n
2
=
0,1
,
…
,
M
-
1.The following form shows how a sequenceh
n
1
,
n
2
′ is yielded by adding augmenting zeros to the filter sequence h
n
1
,
n
2:
(29)
{
h
}
⟹
{
h
′
}
=
{
{
h
}
0
}
.
For each of the divided submatrices, we can give v
1 and v
2 and compute the circular convolution of two 2D sequences x
n
1
+
v
1
N
′
,
n
2
+
v
2
M
′ and h
n
1
,
n
2
′
(
n
1
=
0,1
,
…
,
N
-
1, n
2
=
0,1
,
…
,
M
-
1
) by
(30)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
N
-
1
‍
∑
n
2
=
0
M
-
1
‍
h
n
1
,
n
2
′
x
〈
t
1
-
n
1
〉
N
+
v
1
N
′
,
〈
t
2
-
n
2
〉
M
+
v
2
M
′
,
d
d
d
d
i
t
1
=
0,1
,
…
,
N
-
1
,
t
2
=
0,1
,
…
,
M
-
1
.From (28), we deduce that
(31)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
l
2
-
1
‍
∑
n
2
=
0
m
2
-
1
‍
h
n
1
,
n
2
x
〈
t
1
-
n
1
〉
N
+
v
1
N
′
,
〈
t
2
-
n
2
〉
M
+
v
2
M
′
.
The result of (31) is that of circular convolution. As we will see below, there exists an important connection between the circular convolution and the linear one. In fact, since n
1
=
0,1
,
…
,
l
2
-
1  and  n
2
=
0,1
,
…
,
m
2
-
1, we can choose t
1
=
l
2
-
1
,
…
,
N
-
1 and t
2
=
m
2
-
1
,
…
,
M
-
1 in (31); this makes N
>
t
1
-
n
1
>
0 and M
>
t
2
-
n
2
>
0 in (31). Thus, the remainder can exactly be equal to t
1
-
n
1 and t
2
-
n
2. Then, the circular convolution of (31) becomes
(32)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
l
2
-
1
‍
∑
n
2
=
0
m
2
-
1
‍
h
n
1
,
n
2
x
〈
t
1
-
n
1
〉
N
+
v
1
N
′
,
〈
t
2
-
n
2
〉
M
+
v
2
M
′
=
∑
n
1
=
0
l
2
-
1
‍
∑
n
2
=
0
m
2
-
1
‍
h
n
1
,
n
2
x
t
1
-
n
1
+
v
1
N
′
,
t
2
-
n
2
+
v
2
M
′
=
y
t
1
+
v
1
N
′
,
t
2
+
v
2
M
′
.
In order to clearly understand the procedure of obtaining the components of linear convolution from the circular convolution equation (31), a graphic description of it can be found in Figure 2. We show a dashed rectangle with size of N by M, in Figure 2(a), to represent the circular convolution which is described in (31) and a darkened rectangle with size of N
′ by M
′, to indicate the linear convolution stated in (32). Obviously, if the first l
2
-
1 data in rows and the first m
2
-
1 data in columns are discarded from the dashed rectangle, the darkened rectangle can be obtained. In the following, we will explain how to obtain the result of (4).Two consecutive output submatrices: (a) the first block ofv
1
=
0 and v
2
=
0 and (b) the second block of v
1
=
1 and v
2
=
1.
(a)
(b)The output of the whole equation (4) can be represented in the following matrix:
(33)
Y
=
(
y
0,0
⋯
⋯
y
0
,
m
1
-
1
⋮
⋮
⋮
⋮
y
l
1
-
1,0
⋯
⋯
y
l
1
-
1
,
m
1
-
1
)
,
which is an l
1
×
m
1 matrix.So, (32) gives a N
′
×
M
′ submatrix of matrix Y (note that N
′
=
N
-
l
2
+
1 and that M
′
=
M
-
m
2
+
1):
(34)
(
y
l
2
-
1
+
v
1
N
′
,
m
2
-
1
+
v
2
M
′
⋯
⋯
y
l
2
-
1
+
v
1
N
′
,
M
-
1
+
v
2
M
′
⋮
⋮
⋮
⋮

y
N
-
1
+
v
1
N
′
,
m
2
-
1
+
v
2
M
′
⋯
⋯
y
N
-
1
+
v
1
N
′
,
M
-
1
+
v
2
M
′

)
.
Next, to obtain the whole result, we need to compute the circular convolution of two 2D sequences x
n
1
+
(
v
1
+
1
)
N
′
,
n
2
+
(
v
2
+
1
)
M
′ and h
n
1
,
n
2
′
(
n
1
=
0,1
,
…
,
N
-
1, n
2
=
0,1
,
…
,
M
-
1
). With the same reasoning as above, a consecutive submatrix of the matrix (34) is evinced as follows:
(35)
(
y
N
+
v
1
N
′
,
M
+
v
2
M
′
⋯
⋯
y
N
+
v
1
N
′
,
M
+
M
′
-
1
+
v
2
M
′
⋮
⋮
⋮
⋮

y
N
+
N
′
-
1
+
v
1
N
′
,
M
+
v
2
M
′
⋯
⋯
y
N
+
N
′
-
1
+
v
1
N
′
,
M
+
M
′
-
1
+
v
2
M
′

)
.
The corresponding graphic description is indicated in Figure 2(b). We will darken the rectangle in Figure 2(b) to express the submatrix (35) and the dashed one on its upper-left-corner to be the graphic description of the submatrix (34).Clearly, if(
v
1
,
v
2
)
≠
(
v
1
′
,
v
2
′
), then (
t
1
+
v
1
N
′
,
t
2
+
v
2
M
′
)
≠
(
t
1
′
+
v
1
′
N
′
,
t
2
′
+
v
2
′
M
′
), where l
2
-
1
≤
t
1
,
t
1
′
≤
N
-
1
,
m
2
-
1
≤
t
2andt
2
′
≤
M
-
1. Let [
x
] represent the largest integer that is less than or equal to the real number x; therefore, when v
1
=
0,1
,
…
,
[
(
l
1
-
N
)
/
N
′
] and v
2
=
0,1
,
…
,
[
(
m
1
-
M
)
/
M
′
], we will obtain all N
′
×
M
′ submatrices of the matrix Y. If l
1
=
s
1
N
′
+
N and m
1
=
s
2
M
′
+
M, then [
(
l
1
-
N
)
/
N
′
]
=
(
l
1
-
N
)
/
N
′ and [
(
m
1
-
M
)
/
M
′
]
=
(
m
1
-
M
)
/
M
′. The input matrix x
n
1
,
n
2 will be divided with no remainder. Figure 3 displays a series of small rectangles. Each rectangle stands for one N
′
×
M
′ submatrix. The entire matrix Y can be obtained by combining them.Figure 3
AllN
′
×
M
′ submatrices of the output, except the boundary of Γ-type area.In Figure3, there is a white Γ-type area indicating that there are no output data. Two calculation methods can be applied to obtain the data. The first way is by using a direct method because only a few computations are needed. Alternatively, we can compute the data of Γ-type area with the overlap-save method proposed above, if N
′
=
l
2
-
1 and M
′
=
m
2
-
1. The detail of it is presented in the Technical Report [18]. The entire result is completed and is demonstrated in Figure 4 graphically.Figure 4
The full result of (4) computed by 2D overlap-save method, where l
1
=
s
1
N
′
+
N,  m
1
=
s
2
M
′
+
M, and N
′
+
l
2
-
1
=
N
<
l
1 and  M
′
+
m
2
-
1
=
M
<
m
1.The two-dimensional overlap-save method is summarized as follows.(i)
Select two positive integersN
′ and M
′, so that N
′
+
l
2
-
1
=
N
<
l
1 and M
′
+
m
2
-
1
=
M
<
m
1. Either N or M is given by an integer power of 2 for using an FFT; that is, N
=
2
d
1 and M
=
2
d
2 where d
1 and d
2 are two positive integers.
(ii)
Leth
n
1
,
n
2
′ satisfy (28).
(iii)
Compute the circular convolution of two sequencesx
n
1
+
v
1
N
′
,
n
2
+
v
2
M
′ and h
n
1
,
n
2
′
(
n
1
=
0,1
,
…
,
N
-
1, n
2
=
0,1
,
…
,
M
-
1
). When t
1
=
l
2
-
1
,
…
,
N
-
1, t
2
=
m
2
-
1
,
…
,
M
-
1 and v
1
=
0,1
,
…
,
[
(
l
1
-
N
)
/
N
′
], v
2
=
0,1
,
…
,
[
(
m
1
-
M
)
/
M
′
], we obtain all N
′
×
M
′ submatrices of the matrix of Y whose form is as (34). If l
1
=
s
1
N
′
+
N and m
1
=
s
2
M
′
+
M, then [
(
l
1
-
N
)
/
N
′
]
=
(
l
1
-
N
)
/
N
′ and [
(
m
1
-
M
)
/
M
′
]
=
(
m
1
-
M
)
/
M
′. The input matrix x
n
1
,
n
2 will be divided with no remainder.
(iv)
Fort
1
=
0,1
,
…
,
l
2
-
2, t
2
=
0,1
,
…
,
m
1
-
1, andt
1
=
0,1
,
…
,
l
1
-
1
,
t
2
=
0,1
,
…
,
m
2
-
2, compute y
t
1
,
t
2 by using the direct method.
IfN
′
=
l
2
-
1 and M
′
=
m
2
-
1, we will add zeros to the sequence x
n
1
,
n
2 so that the 2D sequences are of lengths l
1
+
N
′ and m
1
+
M
′. Then, we will compute y
n
1
,
n
2
(
t
1
=
0,1
,
…
,
l
2
-
2, t
2
=
0,1
,
…
,
m
1
-
1, and t
1
=
0,1
,
…
,
l
1
-
1, t
2
=
0,1
,
…
,
m
2
-
2
) by using an overlap-save method. The detail of it is presented in the Technical Report [18].We will introduce the way of using FNTT and 2D overlap-save method with two examples. One is numerical computation and the other is an experiment of extracting the contour of a Chinese handwritten character.


## 4. Comparison of the Numbers of Multiplication

LetN
=
N
′
+
l
2
-
1
<
l
1, M
=
M
′
+
m
2
-
1
<
m
1, N
′
=
l
2
-
1, M
′
=
m
2
-
1,l
2
=
2
u
+
1, m
2
=
2
u
′
+
1, and l
1
=
s
1
N
′
+
N, m
1
=
s
2
M
′
+
M. Suppose that a
1 and a
2 satisfy 2
a
1
-
1
<
l
1
+
l
2
-
1
≤
2
a
1
=
N
1 and a
a
2
-
1
<
m
1
+
m
2
-
1
≤
2
a
2
=
N
2. Let L
1, L
2, and L
3 denote the numbers of multiplication necessary for computing the convolution (4) by using direct method, FNTT, or FFT to calculate (4) (using Proposition 1) and 2D overlap-save method, respectively. In [18], we compared the number of multiplications necessary for computing the convolution (4) of two 2D sequences x
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
1
-
1
,
n
2
=
0,1
,
…
,
m
1
-
1
) and h
n
1
,
n
2
(
n
1
=
0,1
,
…
,
l
2
-
1, n
2
=
0,1
,
…
,
m
2
-
1
) by three different methods.We proved the following results:(1)
Ifl
2
<
l
1
,
m
2
<
m
1, then
(36)
L
1
=
l
2
m
2
(
l
2
+
1
)
(
m
2
+
1
)
4
+
(
m
1
-
m
2
)
m
2
l
2
(
l
2
+
1
)
2
+
(
l
1
-
l
2
)
l
2
m
2
(
m
2
+
1
)
2
+
(
l
1
-
l
2
)
(
m
1
-
m
2
)
l
2
m
2
.
Also, if l
1
=
m
1
=
l, l
2
=
m
2
=
l
′, then
(37)
L
1
=
(
l
′
(
2
l
-
l
′
+
1
)
2
)
2
.
(2)
Consider(38)
L
2
=
2
a
1
+
a
2
-
1
(
3
a
1
+
3
a
2
+
2
)
.
(3)
Ifl
1
=
m
1
=
2
u
+
h,  l
2
=
m
2
=
2
u
+
1, N
=
M
=
2
u
+
1, and N
′
=
M
′
=
2
u, where u
≥
3
,
h
≥
2, then
(39)
L
1
=
(
(
2
u
+
1
)
2
u
-
1
(
2
h
+
1
-
1
)
)
2
,
L
2
=
2
2
u
+
2
h
+
1
(
6
u
+
6
h
+
8
)
,
L
3
=
2
(
2
u
+
h
)
2
(
6
u
+
8
)
.In this section, we will suppose thatN
′
≠
l
2
-
1
,
M
′
≠
m
2
-
1. Let N
=
N
′
+
l
2
-
1
<
l
1, M
=
M
′
+
m
2
-
1
<
m
1, and l
1
=
s
1
N
′
+
N
,
m
1
=
s
2
M
′
+
M. For t
1
=
0,1
,
…
,
l
2
-
2
,
t
2
=
0,1
,
…
,
m
1
-
1 and t
1
=
0,1
,
…
,
l
1
-
1
,
t
2
=
0,1
,
…
,
m
2
-
2, we computer y
t
1
,
t
2 by using the direct method.We have the following proposition.Proposition 6.
Ifl
2
<
l
1
,
m
2
<
m
1, then
(40)
L
=
l
2
m
2
4
(
(
l
2
-
1
)
(
m
2
-
1
)
+
2
(
l
2
-
1
)
s
s
s
s
s
s
i
×
(
m
1
-
m
2
+
1
)
+
2
(
m
2
-
1
)
(
l
1
-
l
2
+
1
)
)
,
where L denotes the number of multiplication necessary for computing y
n
1
,
n
2 by using the direct method, t
1
=
0,1
,
…
,
l
2
-
2, t
2
=
0,1
,
…
,
m
1
-
1, and t
1
=
0,1
,
…
,
l
1
-
1, t
2
=
0,1
,
…
,
m
2
-
2.
Also, ifl
1
=
m
1
=
l and l
2
=
m
2
=
l
′, then
(41)
L
=
l
′
2
(
l
′
-
1
)
4
(
4
l
-
3
l
′
+
3
)
.Proof.
LetI,II, andIII denote the number of multiplication necessary for computing the A, B
, and C by direct method, respectively, where
(42)
A
=
(
y
0,0
⋯
y
0
,
m
2
-
2
⋮
⋮
⋮
y
l
2
-
2,0
⋯
y
l
2
-
2
,
m
2
-
2
)
,
B
=
(
y
0
,
m
2
-
1
⋯
y
0
,
m
1
-
1
⋮
⋮
⋮
y
l
2
-
2
,
m
2
-
1
⋯
y
l
2
-
2
,
m
1
-
1
)
,
C
=
(
y
l
2
-
1,0
⋯
y
l
2
-
1
,
m
2
-
2
⋮
⋮
⋮
y
l
2
-
1,0
⋯
y
l
2
-
1
,
m
2
-
2
)
.
Then
(43)
I
=
(
1
+
2
+
⋯
+
(
m
2
-
1
)
)
(
1
+
2
+
⋯
+
(
l
2
-
1
)
)
=
l
2
m
2
(
l
2
-
1
)
(
m
2
-
1
)
4
,
I
I
=
m
2
(
1
+
2
+
⋯
+
(
l
2
-
1
)
)
(
m
1
-
1
-
(
m
2
-
2
)
)
=
l
2
m
2
(
l
2
-
1
)
(
m
1
-
m
2
+
1
)
2
,
I
I
I
=
l
2
(
1
+
2
+
⋯
+
(
m
2
-
1
)
)
(
l
1
-
1
-
(
l
2
-
2
)
)
=
l
2
m
2
(
m
2
-
1
)
(
l
1
-
l
2
+
1
)
2
.
So,
(44)
L
=
I
+
I
I
+
I
I
I
=
l
2
m
2
4
(
(
l
2
-
1
)
(
m
2
-
1
)
+
2
(
l
2
-
1
)
(
m
1
-
m
2
+
1
)
s
s
s
s
s
s
i
s
s
+
2
(
m
2
-
1
)
(
l
1
-
l
2
+
1
)
)
.
Clearly, if l
1
=
m
1
=
l and l
2
=
m
2
=
l
′, then (41) holds. This completes the proof.Proposition 7.
Ifl
1
=
m
1
=
2
u
+
h, l
2
=
m
2
=
2
u
+
1, N
=
M
=
2
u
+
2, and N
′
=
M
′
=
3
·
2
u, where u
≥
3, h
≡
0
(
mod
⁡
2
), h
≥
4, then
(45)
L
4
=
(
2
u
+
1
)
2
2
2
(
u
-
1
)
(
2
h
+
2
-
3
)
+
(
4
(
2
h
-
2
-
1
)
3
+
1
)
2
2
2
(
u
+
2
)
(
3
u
+
7
)
,
where L
4 denotes the number of multiplication necessary for computing (4) by using 2D overlap-save method.Proof.
BecauseN
′
≠
l
2
-
1, M
′
≠
m
2
-
1, l
1
=
m
1
=
2
u
+
h, and l
2
=
m
2
=
2
u
+
1, by (41), we have
(46)
L
=
(
2
u
+
1
)
2
·
2
u
-
2
(
2
u
+
h
+
2
-
3
(
2
u
+
1
)
+
3
)
=
(
2
u
+
1
)
2
2
2
(
u
-
1
)
(
2
h
+
2
-
3
)
.
Compute the cyclic convolution of two sequences x
n
1
+
v
1
N
′
,
n
2
+
v
2
M
′ and h
n
1
,
n
2
′
(
n
1
=
0,1
,
…
,
2
u
+
2
-
1, n
2
=
0,1
,
…
,
2
u
+
2
-
1
); that is, compute matrix (35), by using FNNT. It is well known that using FNTT to calculate the (35) requires
(47)
N
M
(
3
2
log
⁡
N
M
+
1
)
=
2
2
(
u
+
2
)
(
3
u
+
7
)
,
where N
=
M
=
2
u
+
2.
WhenN
=
M
=
2
u
+
2, N
′
=
M
′
=
3
·
2
u, u
≥
3
,
h
≡
0
(
mod
⁡
2
), and h
≥
4, then
(48)
[
l
1
-
N
N
′
]
=
[
m
1
-
M
M
′
]
=
[
2
u
+
h
-
2
u
+
2
3
·
2
u
]
=
[
4
(
2
h
-
2
-
1
)
3
]
=
4
(
2
h
-
2
-
1
)
3
,
where 4
(
2
h
-
2
-
1
)
/
3 is a positive integer.
So, the input matrixx
n
1
,
n
2 will be divided with no remainder. When v
1
=
0,1
,
…
,
[
(
l
1
-
N
)
/
N
′
] and v
2
=
0,1
,
…
,
[
(
m
1
-
M
)
/
M
′
], we obtain all matrices as (35). Thus,
(49)
L
4
=
(
2
u
+
1
)
2
2
2
(
u
-
1
)
(
2
h
+
2
-
3
)
+
(
4
(
2
h
-
2
-
1
)
3
+
1
)
2
2
2
(
u
+
2
)
(
3
u
+
7
)
,
equal to (45) holds. This completes the proof.Example 8.
Suppose thatu
=
h
=
4; that is, l
1
=
m
1
=
256, l
2
=
m
2
=
17, N
=
M
=
64, and N
′
=
M
′
=
48; then,
(50)
L
4
=
3073856
.
If l
1
=
m
1
=
256, l
2
=
m
2
=
17, N
=
M
=
32, and N
′
=
M
′
=
16, then
(51)
L
3
=
4194304
.
This example shows that L
4
<
L
3 in some particular cases.


## 5. Experiments

The theoretic description of the 2D overlap-save method has been provided in the preceding section. This section further examines how such a technique will be performed and how it will be applied to the wavelet transform. Particularly, we will use image processing as an example. The experiment will focus on the application of the 2D overlap-save method to the dyadic wavelet transform extracting the contours of Chinese handwriting.


### 5.1. Numerical Computation

Leth
n
1
,
n
2 denote a digital filter and let a two-dimensional sequence
(52)
(
h
n
1
,
n
2
)
=
(
1
0
1
1
1
0
0
1
1
)
be the coefficients of the filter. A two-dimensional sequence
(53)
(
x
n
1
,
n
2
)
=
(
1
3
2
-
3
0
2
1
1
3
1
0
-
1
2
-
2
-
1
0
0
-
1
1
1
3
2
0
-
1
2
3
-
1
1
0
1
1
0
3
-
2
1
0
-
1
1
1
1
-
1
0
2
3
1
1
0
1
1
-
1
0
1
0
1
-
1
0
-
1
0
1
1
0
1
0
1
)
represents the input of the filter. In this example, because l
1
=
m
1
=
8 and l
2
=
m
2
=
3, the length of input matrix is 8
×
8 and that of the filter is 3
×
3.Using the overlap-save method to calculate the output of the filter(54)
x
x
x
x
x
x
s
i
s
s
i
s
s
x
y
n
1
,
n
2
=
∑
k
1
=
0
2
∑
k
2
=
0
2
h
k
1
,
k
2
x
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
8
ddddddddddddddddd
0
≤
n
2
-
k
2
<
8
ddddddddddddddddd
⁡
n
1
=
0,1
,
2,3
,
4,5
,
6,7
,
n
2
=
0,1
,
2,3
,
4,5
,
6,7
,
means that the elements of the matrix
(55)
Y
=
(
y
0,0
y
0,1
⋯
y
0,7
y
1,0
y
1,1
⋯
y
1,7
⋮
⋮
⋮
⋮
y
7,0
y
7,1
⋯
y
7,7
)
need to be computed.The solution is given below.Sincel
1
=
m
1
=
8, l
2
=
m
2
=
3, by selecting N
′
=
l
2
-
1
=
2, and M
′
=
m
2
-
1
=
2, we have N
=
M
=
4. In order to use the FNTT, the input matrix is divided into 9 submatrices of size 4
×
4. Each consecutive submatrix is partly overlapped with the size of 2
×
2 pixels. In addition, zeros of size 1
×
1 are added to the filtering sequence to ensure that its length is equivalent to that of the submatrix. Therefore, the filtering sequence h
n
1
,
n
2 is extended to h
n
1
,
n
2
′; that is,
(56)
h
n
1
,
n
2
′
=
{
h
n
1
,
n
2
if
n
1
=
0,1
,
2
,
n
2
=
0,1
,
2
,
0
if
n
1
=
3
or
n
2
=
3
,
where n
1
=
0,1
,
2,3
,
n
2
=
0,1
,
2,3.Next, we compute the circular convolution of the two sequencesx
n
1
+
2
v
1
,
n
2
+
2
v
2 and h
n
1
,
n
2
′
(
n
1
=
0,1
,
2,3, n
2
=
0,1
,
2,3
),
(57)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
h
n
1
,
n
2
′
x
〈
t
1
-
n
1
〉
4
+
2
v
1
,
〈
t
2
-
n
2
〉
4
+
2
v
2
=
∑
n
1
=
0
2
‍
∑
n
2
=
0
2
‍
h
n
1
,
n
2
x
〈
t
1
-
n
1
〉
4
+
2
v
1
,
〈
t
2
-
n
2
〉
4
+
2
v
2
,
where t
1
=
0,1
,
2,3
,
t
2
=
0,1
,
2,3.Whent
1
=
2,3
,
t
2
=
2,3, we arrive at the following result:
(58)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
2
‍
∑
n
2
=
0
2
‍
h
n
1
,
n
2
x
t
1
-
n
1
+
2
v
1
,
t
2
-
n
2
+
2
v
2
=
y
t
1
+
2
v
1
,
t
2
+
2
v
2
.
After choosing all the parameters of v
1
=
0,1
,
2, v
2
=
0,1
,
2
(
[
(
l
1
-
N
)
/
N
′
]
=
[
(
m
1
-
M
)
/
M
′
]
=
[
(
8
-
4
)
/
2
]
=
2
), all 2
×
2 submatrices of the matrix Y, defined in (34), will be obtained as follows:
(59)
(
y
2,2
y
2,3
y
3,2
y
3,3
)
(
y
2,4
y
2,5
y
3,4
y
3,5
)
(
y
2,6
y
2,7
y
3,6
y
3,7
)
(
y
4,2
y
4,3
y
5,2
y
5,3
)
(
y
4,4
y
4,5
y
5,4
y
5,5
)
(
y
4,6
y
4,7
y
5,6
y
5,7
)
(
y
6,2
y
6,3
y
7,2
y
7,3
)
(
y
6,4
y
6,5
y
7,4
y
7,5
)
(
y
6,6
y
6,7
y
7,6
y
7,7
)
.
For y
t
1
,
t
2
(
t
1
=
0,1, t
2
=
0,1
,
2,3
,
4,5
,
6,7, t
1
=
0,1
,
2,3
,
4,5
,
6,7, t
2
=
0,1
), we can compute it by using an overlap-save method. The detail of it is presented in the Technical Report [18].The fast number theoretic transform (FNTT) is now applied to the implementation of the circular convolution(60)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
h
n
1
,
n
2
x
〈
t
1
-
n
1
〉
4
,
〈
t
2
-
n
2
〉
4
,
d
i
t
1
=
0,1
,
2,3
,
t
2
=
0,1
,
2,3
.
The computation is performed in the following five steps shown in Figure 5.Figure 5
Five steps of applying FNTT to calculate the output of (54).Step 1 (choosingM).
Since(61)
|
y
¯
t
1
,
t
2
|
≤
|
x
n
1
,
n
2
|
max
⁡
∑
k
1
=
0
3
‍
∑
k
2
=
0
3
‍
|
h
k
1
,
k
2
|
=
3
×
6
=
18
,
we can select m
=
257
=
2
8
+
1 so that 18
<
257
/
2, where 257 is aprime. Clearly, 1
6
4
≡
1
(
mod
⁡
257
), and 1
6
j
≢
1
(
mod
⁡
257
), for 1
≤
j
≤
3.
Thus,(62)
X
k
1
,
k
2
≡
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
x
n
1
,
n
2
1
6
n
1
k
1
·
1
6
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
i
i
i
k
1
=
0,1
,
2,3
,
k
2
=
0,1
,
2,3
is a 2D number theoretic transform. It has the following inverse transform:
(63)
x
n
1
,
n
2
≡
4
-
1
·
4
-
1
∑
k
1
=
0
3
‍
∑
k
2
=
0
3
‍
X
k
1
,
k
2
(
-
16
)
n
1
k
1
(
-
16
)
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
d
d
d
d
i
i
d
d
d
d
d
d
n
1
=
0,1
,
2,3
,
n
2
=
0,1
,
2,3
,
where 4
-
1 denotes an integer so that (
4
-
1
)
·
4
≡
1
(
mod
⁡
257
).Step 2 (calculating the number theoretic transform of input matrix by the FNTT).
For computational convenience, here, one writes(64)
U
0
,
k
2
≡
∑
n
2
=
0
3
‍
x
0
,
n
2
1
6
n
2
k
2
,
U
1
,
k
2
≡
∑
n
2
=
0
3
‍
x
1
,
n
2
1
6
n
2
k
2
(
mod
⁡
257
)
U
2
,
k
2
≡
∑
n
2
=
0
3
‍
x
2
,
n
2
1
6
n
2
k
2
,
U
3
,
k
2
≡
∑
n
2
=
0
3
‍
x
3
,
n
2
1
6
n
2
k
2
(
mod
⁡
257
)
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
i
d
d
d
d
d
d
d
d
d
d
d
k
2
=
0,1
,
2,3
.
Then, (62) becomes
(65)
X
k
1,0
≡
∑
n
1
=
0
3
‍
U
n
1,0
1
6
n
1
k
1
,
X
k
1,1
≡
∑
n
1
=
0
3
‍
U
n
1,1
1
6
n
1
k
1
(
mod
⁡
257
)
X
k
1,2
≡
∑
n
1
=
0
3
‍
U
n
1,2
1
6
n
1
k
1
,
X
k
1,3
≡
∑
n
1
=
0
3
‍
U
n
1,3
1
6
n
1
k
1
(
mod
⁡
257
)
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
k
1
=
0,1
,
2,3
.
Use the FNTT to calculate (64) and (65).
So,(66)
(
U
0,0
U
0,1
U
0,2
U
0,3
U
1,0
U
1,1
U
1,2
U
1,3
U
2,0
U
2,1
U
2,2
U
2,3
U
3,0
U
3,1
U
3,2
U
3,3
)
≡
(
3
95
3
-
97
3
35
3
-
29
1
-
33
1
31
5
35
-
3
-
29
)
(
mod
⁡
257
)
,
X
=
(
X
0,0
X
0,1
X
0,2
X
0,3
X
1,0
X
1,1
X
1,2
X
1,3
X
2,0
X
2,1
X
2,2
X
2,3
X
3,0
X
3,1
X
3,2
X
3,3
)
≡
(
12
132
4
-
124
-
30
128
98
-
128
-
4
-
8
4
-
8
34
128
-
94
-
128
)
(
mod
⁡
257
)
.Step 3 (calculating the number theoretic transform of the filter by the FNTT).
The FNTT of the filterh
n
1
,
n
2 is written as
(67)
H
k
1
,
k
2
≡
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
h
n
1
,
n
2
′
1
6
n
1
k
1
·
1
6
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
i
d
d
d
d
k
1
=
0,1
,
2,3
,
k
2
=
0,1
,
2,3
.
Similarly, we have
(68)
H
=
(
H
0,0
H
0,1
H
0,2
H
0,3
H
1,0
H
1,1
H
1,2
H
1,3
H
2,0
H
2,1
H
2,2
H
2,3
H
3,0
H
3,1
H
3,2
H
3,3
)
≡
(
6
32
2
-
32
32
0
2
34
2
-
2
2
-
2
-
32
-
30
2
0
)
(
mod
⁡
257
)
.Step 4 (compute the number theoretic transform of the output of the filter).
From the preceding three steps, we can compute the circular convolution of the filter by defining the product ofX and H as
(69)
Y
¯
=
(
Y
0,0
Y
0,1
Y
0,2
Y
0,3
Y
1,0
Y
1,1
Y
1,2
Y
1,3
Y
2,0
Y
2,1
Y
2,2
Y
2,3
Y
3,0
Y
3,1
Y
3,2
Y
3,3
)
≡
X
⊙
H
=
(
X
0,0
H
0,0
X
0,1
H
0,1
X
0,2
H
0,2
X
0,3
H
0,3
X
1,0
H
1,0
X
1,1
H
1,1
X
1,2
H
1,2
X
1,3
H
1,3
X
2,0
H
2,0
X
2,1
H
2,1
X
2,2
H
2,2
X
2,3
H
2,3
X
3,0
H
3,0
X
3,1
H
3,1
X
3,2
H
3,2
X
3,3
H
3,3
)
≡
(
72
112
8
113
68
0
-
61
17
-
8
16
8
16
-
60
15
69
0
)
(
mod
⁡
257
)
,
where
(70)
Y
k
1
,
k
2
≡
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
y
¯
n
1
,
n
2
1
6
n
1
k
1
·
1
6
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
d
d
k
1
=
0,1
,
2,3
,
k
2
=
0,1
,
2,3
,
and the y
¯
n
1
,
n
2
(
n
1
=
0,1
,
2,3, n
2
=
0,1
,
2,3
) is the circular convolution of (60).Step 5 (calculate the output of the linear convolution).
From (63), we deduce the inverse transform of (70):
(71)
y
¯
n
1
,
n
2
≡
4
-
1
·
4
-
1
∑
k
1
=
0
3
‍
∑
k
2
=
0
3
‍
Y
k
1
,
k
2
(
-
16
)
n
1
k
1
dddddddddddddi
·
(
-
16
)
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
d
i
i
n
1
=
0,1
,
2,3
,
n
2
=
0,1
,
2,3
.
Using FNTT to calculate (71), we have
(72)
(
y
¯
0,0
y
¯
0,1
y
¯
0,2
y
¯
0,3
y
¯
1,0
y
¯
1,1
y
¯
1,2
y
¯
1,3
y
¯
2,0
y
¯
2,1
y
¯
2,2
y
¯
2,3
y
¯
3,0
y
¯
3,1
y
¯
3,2
y
¯
3,3
)
≡
(
8
6
4
0
1
7
13
1
2
2
6
4
1
5
5
7
)
(
mod
⁡
257
)
.
Then, the linear convolution in (58) is obtained:
(73)
(
y
2,2
y
2,3
y
3,2
y
3,3
)
=
(
y
¯
2,2
y
¯
2,3
y
¯
3,2
y
¯
3,3
)
=
(
6
4
5
7
)
.


### 5.2. Application to Image Processing

The proposed method can be applied to many fields such as image processing and pattern recognition. An example of the application to the image processing is illustrated in Figure6. The original image shown in Figure 6(a) is a 2-dimensional image of an aircraft with a size of 256 × 256 pixels; that is, l
1
=
m
1
=
256. Our task is to extract its contours. The discrete wavelet transform with scale s
=
2
j where j
=
2 was applied and the spline wavelet, described in (1), of size 17
×
17 was chosen; that is l
2
=
m
2
=
17. We use the filtering coefficients tabulated in Table 1. Using the 2D overlap-save method, this original image was divided into 25 sections, with each one having the dimension of 64 × 64 pixels; that is, we select N
=
M
=
64, N
′
=
M
′
=
48
,
[
(
l
1
-
N
)
/
N
′
]
=
[
(
m
1
-
M
)
/
M
′
]
=
4. (See Example 8 in Section 4.) Figure 6(b) shows these subimages. The overlapped part can be explicitly observed in each subimage.Table 1
Filtering coefficients{
ψ
k
,
l
2
j
,
1
}
,
(
j
=
2
)
,
ψ
(
r
), are a quadratic spline wavelet.
l
/
k
k
=
0
k
=
1
k
=
2
k
=
3
l
=
0
−0.0838140026
−0.0472041145
−0.0129809398
−0.0012592132
l
=
1
−0.1416904181
−0.0758706033
−0.0196341425
−0.0012698699
l
=
2
−0.0651057437
−0.0327749476
−0.0063385521
−0.0000750836
l
=
3
−0.0088690016
−0.0030044997
−0.0001088651A 2-dimensional image of an aircraft was processed with 2D overlap-save method. (a) Original Chinese handwriting and (b) the divided up subimages of the character.
(a)
(b)To facilitate the presentation of the 2D overlap-save method, the procedure of it is diagonally displayed in Figure7, where a series of the divided subimages are illustrated. The image in Figure 6(a) was equivalently divided into 25 sections by applying (27). In Figure 7(a), we represent 5 subimages of v
0
=
0, v
1
=
0, v
0
=
1, v
1
=
1, v
0
=
2, v
1
=
2 and v
0
=
3, v
1
=
3, and v
0
=
4, v
1
=
4, consecutively. The lower-right corner of each subimage is repeated in the upper-left corner of its consecutive subimage. Four subimages are displayed in Figure 7(b), and the parameters of v
0
=
0, v
1
=
1, v
0
=
1, v
1
=
2, v
0
=
2, v
1
=
3, and v
0
=
3, v
1
=
4 were chosen. In Figure 7(c), we selected 3 subimages of v
0
=
0, v
1
=
2, v
0
=
1, v
1
=
3, and v
0
=
2, v
1
=
4. There are 3 subimages of v
0
=
0, v
1
=
3 and v
0
=
1, v
1
=
4 in Figure 7(d). Figure 7(e) displays subimages of v
0
=
0, v
1
=
4. In Figure 7(f), v
0
=
1, v
1
=
0, v
0
=
2, v
1
=
1, v
0
=
3, v
1
=
2, and v
0
=
4, v
1
=
3 were chosen. In Figure 7(g) the parameters were decided upon v
0
=
2, v
1
=
0, v
0
=
3, v
1
=
1, and v
0
=
4, v
1
=
2. Two subimages are shown in Figure 7(h) by selecting v
0
=
3, v
1
=
0, and v
0
=
4, v
1
=
1. There is one subimage of v
0
=
4, v
1
=
0 in Figure 7(i).A 2-dimensional image of an aircraft is dividing into separated small subimages; the parameters ofv
0 and v
1 are chosen as follows: (a) v
0
=
0, v
1
=
0, v
0
=
1, v
1
=
1, v
0
=
2, v
1
=
2 and v
0
=
3, v
1
=
3, and v
0
=
4 and v
1
=
4; (b) v
0
=
0, v
1
=
1, v
0
=
1, v
1
=
2, v
0
=
2, v
1
=
3, and v
0
=
3 and v
1
=
4; (c) v
0
=
0, v
1
=
2, v
0
=
1, v
1
=
3, and v
0
=
2 and v
1
=
4; (d) v
0
=
0, v
1
=
3, and v
0
=
1 and v
1
=
4; (e) v
0
=
0 and v
1
=
4; (f) v
0
=
1, v
1
=
0, v
0
=
2, v
1
=
1, v
0
=
3, v
1
=
2, and v
0
=
4 and v
1
=
3; (g) v
0
=
2, v
1
=
0, v
0
=
3, v
1
=
1, and v
0
=
4 and v
1
=
2; (h) v
0
=
3, v
1
=
0, and v
0
=
4 and v
1
=
1; and (i) v
0
=
4 and v
1
=
0.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)We select a 2D NTT(74)
X
k
1
,
k
2
≡
∑
n
1
=
0
63
‍
∑
n
2
=
0
63
‍
x
n
1
,
n
2
2
n
1
k
1
2
n
2
k
2
(
mod
⁡
2
32
+
1
)
,
which has inverse transform
(75)
x
n
1
,
n
2
≡
6
4
-
1
6
4
-
1
∑
k
1
=
0
63
‍
∑
k
2
=
0
63
‍
X
k
1
,
k
2
(
-
2
31
)
n
1
k
1
d
d
d
d
d
d
d
d
d
d
d
d
d
×
(
-
2
31
)
n
2
k
2
(
mod
⁡
2
32
+
1
)
,
d
d
d
d
d
d
d
d
i
n
1
=
0,1
,
…
,
63
,
n
2
=
0,1
,
…
,
63
,
where 6
4
-
1 denotes integer so that (
6
4
-
1
)
64
≡
1
(
mod
⁡
2
32
+
1
), and |
x
n
1
,
n
2
|
≤
255.The FNTT was applied to calculate the circular convolution of each subimage. After applying (31) to each of the subblocks, a series of segments of the contours were obtained.By using (32), we can gradually reach the final result of the linear convolution. Figure 8(a) illustrates those pixels which satisfy (35), where l
2
=
m
2
=
17, N
=
M
=
64, N
′
=
M
′
=
48, and v
1
,
v
2
=
0,1
,
2,3
,
4. Combining them together, the contours of the whole character were obtained and displayed in Figure 8(c) which excludes the Γ-type border. Next, the Γ-type border was computed by direct method. Figure 8(b) shows the result. Combining this result with that shown in Figure 8(c), the entire contours of the Chinese handwriting were combined. Figure 8(d) represents the entire contour.The linear outputs of 2D overlap-save method: (a) the outputs of the linear convolution of each subimages, (b) the left border and the upper border of the outputs of the image of aircraft, (c) the combined outputs of linear convolution, exceptΓ-type border, and (d) the entire contour extracted using 2D overlap-save method under wavelet transform.
(a)
(b)
(c)
(d)


## 5.1. Numerical Computation

Leth
n
1
,
n
2 denote a digital filter and let a two-dimensional sequence
(52)
(
h
n
1
,
n
2
)
=
(
1
0
1
1
1
0
0
1
1
)
be the coefficients of the filter. A two-dimensional sequence
(53)
(
x
n
1
,
n
2
)
=
(
1
3
2
-
3
0
2
1
1
3
1
0
-
1
2
-
2
-
1
0
0
-
1
1
1
3
2
0
-
1
2
3
-
1
1
0
1
1
0
3
-
2
1
0
-
1
1
1
1
-
1
0
2
3
1
1
0
1
1
-
1
0
1
0
1
-
1
0
-
1
0
1
1
0
1
0
1
)
represents the input of the filter. In this example, because l
1
=
m
1
=
8 and l
2
=
m
2
=
3, the length of input matrix is 8
×
8 and that of the filter is 3
×
3.Using the overlap-save method to calculate the output of the filter(54)
x
x
x
x
x
x
s
i
s
s
i
s
s
x
y
n
1
,
n
2
=
∑
k
1
=
0
2
∑
k
2
=
0
2
h
k
1
,
k
2
x
n
1
-
k
1
,
n
2
-
k
2
0
≤
n
1
-
k
1
<
8
ddddddddddddddddd
0
≤
n
2
-
k
2
<
8
ddddddddddddddddd
⁡
n
1
=
0,1
,
2,3
,
4,5
,
6,7
,
n
2
=
0,1
,
2,3
,
4,5
,
6,7
,
means that the elements of the matrix
(55)
Y
=
(
y
0,0
y
0,1
⋯
y
0,7
y
1,0
y
1,1
⋯
y
1,7
⋮
⋮
⋮
⋮
y
7,0
y
7,1
⋯
y
7,7
)
need to be computed.The solution is given below.Sincel
1
=
m
1
=
8, l
2
=
m
2
=
3, by selecting N
′
=
l
2
-
1
=
2, and M
′
=
m
2
-
1
=
2, we have N
=
M
=
4. In order to use the FNTT, the input matrix is divided into 9 submatrices of size 4
×
4. Each consecutive submatrix is partly overlapped with the size of 2
×
2 pixels. In addition, zeros of size 1
×
1 are added to the filtering sequence to ensure that its length is equivalent to that of the submatrix. Therefore, the filtering sequence h
n
1
,
n
2 is extended to h
n
1
,
n
2
′; that is,
(56)
h
n
1
,
n
2
′
=
{
h
n
1
,
n
2
if
n
1
=
0,1
,
2
,
n
2
=
0,1
,
2
,
0
if
n
1
=
3
or
n
2
=
3
,
where n
1
=
0,1
,
2,3
,
n
2
=
0,1
,
2,3.Next, we compute the circular convolution of the two sequencesx
n
1
+
2
v
1
,
n
2
+
2
v
2 and h
n
1
,
n
2
′
(
n
1
=
0,1
,
2,3, n
2
=
0,1
,
2,3
),
(57)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
h
n
1
,
n
2
′
x
〈
t
1
-
n
1
〉
4
+
2
v
1
,
〈
t
2
-
n
2
〉
4
+
2
v
2
=
∑
n
1
=
0
2
‍
∑
n
2
=
0
2
‍
h
n
1
,
n
2
x
〈
t
1
-
n
1
〉
4
+
2
v
1
,
〈
t
2
-
n
2
〉
4
+
2
v
2
,
where t
1
=
0,1
,
2,3
,
t
2
=
0,1
,
2,3.Whent
1
=
2,3
,
t
2
=
2,3, we arrive at the following result:
(58)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
2
‍
∑
n
2
=
0
2
‍
h
n
1
,
n
2
x
t
1
-
n
1
+
2
v
1
,
t
2
-
n
2
+
2
v
2
=
y
t
1
+
2
v
1
,
t
2
+
2
v
2
.
After choosing all the parameters of v
1
=
0,1
,
2, v
2
=
0,1
,
2
(
[
(
l
1
-
N
)
/
N
′
]
=
[
(
m
1
-
M
)
/
M
′
]
=
[
(
8
-
4
)
/
2
]
=
2
), all 2
×
2 submatrices of the matrix Y, defined in (34), will be obtained as follows:
(59)
(
y
2,2
y
2,3
y
3,2
y
3,3
)
(
y
2,4
y
2,5
y
3,4
y
3,5
)
(
y
2,6
y
2,7
y
3,6
y
3,7
)
(
y
4,2
y
4,3
y
5,2
y
5,3
)
(
y
4,4
y
4,5
y
5,4
y
5,5
)
(
y
4,6
y
4,7
y
5,6
y
5,7
)
(
y
6,2
y
6,3
y
7,2
y
7,3
)
(
y
6,4
y
6,5
y
7,4
y
7,5
)
(
y
6,6
y
6,7
y
7,6
y
7,7
)
.
For y
t
1
,
t
2
(
t
1
=
0,1, t
2
=
0,1
,
2,3
,
4,5
,
6,7, t
1
=
0,1
,
2,3
,
4,5
,
6,7, t
2
=
0,1
), we can compute it by using an overlap-save method. The detail of it is presented in the Technical Report [18].The fast number theoretic transform (FNTT) is now applied to the implementation of the circular convolution(60)
y
¯
t
1
,
t
2
=
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
h
n
1
,
n
2
x
〈
t
1
-
n
1
〉
4
,
〈
t
2
-
n
2
〉
4
,
d
i
t
1
=
0,1
,
2,3
,
t
2
=
0,1
,
2,3
.
The computation is performed in the following five steps shown in Figure 5.Figure 5
Five steps of applying FNTT to calculate the output of (54).Step 1 (choosingM).
Since(61)
|
y
¯
t
1
,
t
2
|
≤
|
x
n
1
,
n
2
|
max
⁡
∑
k
1
=
0
3
‍
∑
k
2
=
0
3
‍
|
h
k
1
,
k
2
|
=
3
×
6
=
18
,
we can select m
=
257
=
2
8
+
1 so that 18
<
257
/
2, where 257 is aprime. Clearly, 1
6
4
≡
1
(
mod
⁡
257
), and 1
6
j
≢
1
(
mod
⁡
257
), for 1
≤
j
≤
3.
Thus,(62)
X
k
1
,
k
2
≡
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
x
n
1
,
n
2
1
6
n
1
k
1
·
1
6
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
i
i
i
k
1
=
0,1
,
2,3
,
k
2
=
0,1
,
2,3
is a 2D number theoretic transform. It has the following inverse transform:
(63)
x
n
1
,
n
2
≡
4
-
1
·
4
-
1
∑
k
1
=
0
3
‍
∑
k
2
=
0
3
‍
X
k
1
,
k
2
(
-
16
)
n
1
k
1
(
-
16
)
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
d
d
d
d
i
i
d
d
d
d
d
d
n
1
=
0,1
,
2,3
,
n
2
=
0,1
,
2,3
,
where 4
-
1 denotes an integer so that (
4
-
1
)
·
4
≡
1
(
mod
⁡
257
).Step 2 (calculating the number theoretic transform of input matrix by the FNTT).
For computational convenience, here, one writes(64)
U
0
,
k
2
≡
∑
n
2
=
0
3
‍
x
0
,
n
2
1
6
n
2
k
2
,
U
1
,
k
2
≡
∑
n
2
=
0
3
‍
x
1
,
n
2
1
6
n
2
k
2
(
mod
⁡
257
)
U
2
,
k
2
≡
∑
n
2
=
0
3
‍
x
2
,
n
2
1
6
n
2
k
2
,
U
3
,
k
2
≡
∑
n
2
=
0
3
‍
x
3
,
n
2
1
6
n
2
k
2
(
mod
⁡
257
)
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
i
d
d
d
d
d
d
d
d
d
d
d
k
2
=
0,1
,
2,3
.
Then, (62) becomes
(65)
X
k
1,0
≡
∑
n
1
=
0
3
‍
U
n
1,0
1
6
n
1
k
1
,
X
k
1,1
≡
∑
n
1
=
0
3
‍
U
n
1,1
1
6
n
1
k
1
(
mod
⁡
257
)
X
k
1,2
≡
∑
n
1
=
0
3
‍
U
n
1,2
1
6
n
1
k
1
,
X
k
1,3
≡
∑
n
1
=
0
3
‍
U
n
1,3
1
6
n
1
k
1
(
mod
⁡
257
)
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
k
1
=
0,1
,
2,3
.
Use the FNTT to calculate (64) and (65).
So,(66)
(
U
0,0
U
0,1
U
0,2
U
0,3
U
1,0
U
1,1
U
1,2
U
1,3
U
2,0
U
2,1
U
2,2
U
2,3
U
3,0
U
3,1
U
3,2
U
3,3
)
≡
(
3
95
3
-
97
3
35
3
-
29
1
-
33
1
31
5
35
-
3
-
29
)
(
mod
⁡
257
)
,
X
=
(
X
0,0
X
0,1
X
0,2
X
0,3
X
1,0
X
1,1
X
1,2
X
1,3
X
2,0
X
2,1
X
2,2
X
2,3
X
3,0
X
3,1
X
3,2
X
3,3
)
≡
(
12
132
4
-
124
-
30
128
98
-
128
-
4
-
8
4
-
8
34
128
-
94
-
128
)
(
mod
⁡
257
)
.Step 3 (calculating the number theoretic transform of the filter by the FNTT).
The FNTT of the filterh
n
1
,
n
2 is written as
(67)
H
k
1
,
k
2
≡
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
h
n
1
,
n
2
′
1
6
n
1
k
1
·
1
6
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
i
d
d
d
d
k
1
=
0,1
,
2,3
,
k
2
=
0,1
,
2,3
.
Similarly, we have
(68)
H
=
(
H
0,0
H
0,1
H
0,2
H
0,3
H
1,0
H
1,1
H
1,2
H
1,3
H
2,0
H
2,1
H
2,2
H
2,3
H
3,0
H
3,1
H
3,2
H
3,3
)
≡
(
6
32
2
-
32
32
0
2
34
2
-
2
2
-
2
-
32
-
30
2
0
)
(
mod
⁡
257
)
.Step 4 (compute the number theoretic transform of the output of the filter).
From the preceding three steps, we can compute the circular convolution of the filter by defining the product ofX and H as
(69)
Y
¯
=
(
Y
0,0
Y
0,1
Y
0,2
Y
0,3
Y
1,0
Y
1,1
Y
1,2
Y
1,3
Y
2,0
Y
2,1
Y
2,2
Y
2,3
Y
3,0
Y
3,1
Y
3,2
Y
3,3
)
≡
X
⊙
H
=
(
X
0,0
H
0,0
X
0,1
H
0,1
X
0,2
H
0,2
X
0,3
H
0,3
X
1,0
H
1,0
X
1,1
H
1,1
X
1,2
H
1,2
X
1,3
H
1,3
X
2,0
H
2,0
X
2,1
H
2,1
X
2,2
H
2,2
X
2,3
H
2,3
X
3,0
H
3,0
X
3,1
H
3,1
X
3,2
H
3,2
X
3,3
H
3,3
)
≡
(
72
112
8
113
68
0
-
61
17
-
8
16
8
16
-
60
15
69
0
)
(
mod
⁡
257
)
,
where
(70)
Y
k
1
,
k
2
≡
∑
n
1
=
0
3
‍
∑
n
2
=
0
3
‍
y
¯
n
1
,
n
2
1
6
n
1
k
1
·
1
6
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
d
d
k
1
=
0,1
,
2,3
,
k
2
=
0,1
,
2,3
,
and the y
¯
n
1
,
n
2
(
n
1
=
0,1
,
2,3, n
2
=
0,1
,
2,3
) is the circular convolution of (60).Step 5 (calculate the output of the linear convolution).
From (63), we deduce the inverse transform of (70):
(71)
y
¯
n
1
,
n
2
≡
4
-
1
·
4
-
1
∑
k
1
=
0
3
‍
∑
k
2
=
0
3
‍
Y
k
1
,
k
2
(
-
16
)
n
1
k
1
dddddddddddddi
·
(
-
16
)
n
2
k
2
(
mod
⁡
257
)
,
d
d
d
d
d
d
d
d
i
i
n
1
=
0,1
,
2,3
,
n
2
=
0,1
,
2,3
.
Using FNTT to calculate (71), we have
(72)
(
y
¯
0,0
y
¯
0,1
y
¯
0,2
y
¯
0,3
y
¯
1,0
y
¯
1,1
y
¯
1,2
y
¯
1,3
y
¯
2,0
y
¯
2,1
y
¯
2,2
y
¯
2,3
y
¯
3,0
y
¯
3,1
y
¯
3,2
y
¯
3,3
)
≡
(
8
6
4
0
1
7
13
1
2
2
6
4
1
5
5
7
)
(
mod
⁡
257
)
.
Then, the linear convolution in (58) is obtained:
(73)
(
y
2,2
y
2,3
y
3,2
y
3,3
)
=
(
y
¯
2,2
y
¯
2,3
y
¯
3,2
y
¯
3,3
)
=
(
6
4
5
7
)
.


## 5.2. Application to Image Processing

The proposed method can be applied to many fields such as image processing and pattern recognition. An example of the application to the image processing is illustrated in Figure6. The original image shown in Figure 6(a) is a 2-dimensional image of an aircraft with a size of 256 × 256 pixels; that is, l
1
=
m
1
=
256. Our task is to extract its contours. The discrete wavelet transform with scale s
=
2
j where j
=
2 was applied and the spline wavelet, described in (1), of size 17
×
17 was chosen; that is l
2
=
m
2
=
17. We use the filtering coefficients tabulated in Table 1. Using the 2D overlap-save method, this original image was divided into 25 sections, with each one having the dimension of 64 × 64 pixels; that is, we select N
=
M
=
64, N
′
=
M
′
=
48
,
[
(
l
1
-
N
)
/
N
′
]
=
[
(
m
1
-
M
)
/
M
′
]
=
4. (See Example 8 in Section 4.) Figure 6(b) shows these subimages. The overlapped part can be explicitly observed in each subimage.Table 1
Filtering coefficients{
ψ
k
,
l
2
j
,
1
}
,
(
j
=
2
)
,
ψ
(
r
), are a quadratic spline wavelet.
l
/
k
k
=
0
k
=
1
k
=
2
k
=
3
l
=
0
−0.0838140026
−0.0472041145
−0.0129809398
−0.0012592132
l
=
1
−0.1416904181
−0.0758706033
−0.0196341425
−0.0012698699
l
=
2
−0.0651057437
−0.0327749476
−0.0063385521
−0.0000750836
l
=
3
−0.0088690016
−0.0030044997
−0.0001088651A 2-dimensional image of an aircraft was processed with 2D overlap-save method. (a) Original Chinese handwriting and (b) the divided up subimages of the character.
(a)
(b)To facilitate the presentation of the 2D overlap-save method, the procedure of it is diagonally displayed in Figure7, where a series of the divided subimages are illustrated. The image in Figure 6(a) was equivalently divided into 25 sections by applying (27). In Figure 7(a), we represent 5 subimages of v
0
=
0, v
1
=
0, v
0
=
1, v
1
=
1, v
0
=
2, v
1
=
2 and v
0
=
3, v
1
=
3, and v
0
=
4, v
1
=
4, consecutively. The lower-right corner of each subimage is repeated in the upper-left corner of its consecutive subimage. Four subimages are displayed in Figure 7(b), and the parameters of v
0
=
0, v
1
=
1, v
0
=
1, v
1
=
2, v
0
=
2, v
1
=
3, and v
0
=
3, v
1
=
4 were chosen. In Figure 7(c), we selected 3 subimages of v
0
=
0, v
1
=
2, v
0
=
1, v
1
=
3, and v
0
=
2, v
1
=
4. There are 3 subimages of v
0
=
0, v
1
=
3 and v
0
=
1, v
1
=
4 in Figure 7(d). Figure 7(e) displays subimages of v
0
=
0, v
1
=
4. In Figure 7(f), v
0
=
1, v
1
=
0, v
0
=
2, v
1
=
1, v
0
=
3, v
1
=
2, and v
0
=
4, v
1
=
3 were chosen. In Figure 7(g) the parameters were decided upon v
0
=
2, v
1
=
0, v
0
=
3, v
1
=
1, and v
0
=
4, v
1
=
2. Two subimages are shown in Figure 7(h) by selecting v
0
=
3, v
1
=
0, and v
0
=
4, v
1
=
1. There is one subimage of v
0
=
4, v
1
=
0 in Figure 7(i).A 2-dimensional image of an aircraft is dividing into separated small subimages; the parameters ofv
0 and v
1 are chosen as follows: (a) v
0
=
0, v
1
=
0, v
0
=
1, v
1
=
1, v
0
=
2, v
1
=
2 and v
0
=
3, v
1
=
3, and v
0
=
4 and v
1
=
4; (b) v
0
=
0, v
1
=
1, v
0
=
1, v
1
=
2, v
0
=
2, v
1
=
3, and v
0
=
3 and v
1
=
4; (c) v
0
=
0, v
1
=
2, v
0
=
1, v
1
=
3, and v
0
=
2 and v
1
=
4; (d) v
0
=
0, v
1
=
3, and v
0
=
1 and v
1
=
4; (e) v
0
=
0 and v
1
=
4; (f) v
0
=
1, v
1
=
0, v
0
=
2, v
1
=
1, v
0
=
3, v
1
=
2, and v
0
=
4 and v
1
=
3; (g) v
0
=
2, v
1
=
0, v
0
=
3, v
1
=
1, and v
0
=
4 and v
1
=
2; (h) v
0
=
3, v
1
=
0, and v
0
=
4 and v
1
=
1; and (i) v
0
=
4 and v
1
=
0.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)We select a 2D NTT(74)
X
k
1
,
k
2
≡
∑
n
1
=
0
63
‍
∑
n
2
=
0
63
‍
x
n
1
,
n
2
2
n
1
k
1
2
n
2
k
2
(
mod
⁡
2
32
+
1
)
,
which has inverse transform
(75)
x
n
1
,
n
2
≡
6
4
-
1
6
4
-
1
∑
k
1
=
0
63
‍
∑
k
2
=
0
63
‍
X
k
1
,
k
2
(
-
2
31
)
n
1
k
1
d
d
d
d
d
d
d
d
d
d
d
d
d
×
(
-
2
31
)
n
2
k
2
(
mod
⁡
2
32
+
1
)
,
d
d
d
d
d
d
d
d
i
n
1
=
0,1
,
…
,
63
,
n
2
=
0,1
,
…
,
63
,
where 6
4
-
1 denotes integer so that (
6
4
-
1
)
64
≡
1
(
mod
⁡
2
32
+
1
), and |
x
n
1
,
n
2
|
≤
255.The FNTT was applied to calculate the circular convolution of each subimage. After applying (31) to each of the subblocks, a series of segments of the contours were obtained.By using (32), we can gradually reach the final result of the linear convolution. Figure 8(a) illustrates those pixels which satisfy (35), where l
2
=
m
2
=
17, N
=
M
=
64, N
′
=
M
′
=
48, and v
1
,
v
2
=
0,1
,
2,3
,
4. Combining them together, the contours of the whole character were obtained and displayed in Figure 8(c) which excludes the Γ-type border. Next, the Γ-type border was computed by direct method. Figure 8(b) shows the result. Combining this result with that shown in Figure 8(c), the entire contours of the Chinese handwriting were combined. Figure 8(d) represents the entire contour.The linear outputs of 2D overlap-save method: (a) the outputs of the linear convolution of each subimages, (b) the left border and the upper border of the outputs of the image of aircraft, (c) the combined outputs of linear convolution, exceptΓ-type border, and (d) the entire contour extracted using 2D overlap-save method under wavelet transform.
(a)
(b)
(c)
(d)


## 6. Conclusions

A novel approach to reduce the computation complexity of the wavelet transform has been presented in this paper. Two key techniques have been applied in this new method, namely, fast number theoretic transform (FNTT) and two-dimensional overlap-save technique. In the fast number theoretic transform, the linear convolution is replaced by the circular convolution. It can speed up the computation of 2D discrete wavelet transform. Directly calculating the fast number theoretic transform to the whole input sequence may meet two difficulties; namely, a big modulo obstructs the effective implementation of the fast number theoretic transform and a long input sequence slows the computation of the fast number theoretic transform down. To fight with such deficiencies, a new technique which is referred to as 2D overlap-save method has been developed. Experiments have been conducted. The fast number theoretic transform and 2D overlap-method have been used to implement the dyadic wavelet transform and applied to contour extraction in image processing and pattern recognition.



---

*Source: 532979-2014-05-27.xml*