CN103279450A

CN103279450A - Fast method for three-dimensional discrete Hartley transformation

Info

Publication number: CN103279450A
Application number: CN2013101350991A
Authority: CN
Inventors: 董志芳; 陈廷欢
Original assignee: Southeast University
Current assignee: Southeast University
Priority date: 2013-04-17
Filing date: 2013-04-17
Publication date: 2013-09-04

Abstract

The invention discloses a fast method for three-dimensional discrete Hartley transformation. The method for three-dimensional discrete Hartley transformation is applied to the fields of analysis, processing and the like of computer vision, high-definition televisions, video telephones and moving images. The method includes the steps that based on the divide-and-conquer method and the butterfly arithmetic, a 3m*3m*3m data block is decomposed to 27 3m-1*3m-1*3m-1 sub-modules by using linear transformation and trigonometric function transformation characteristics with the method of frequency domain decimation; each data sub-block continues to be decomposed with the method till each data sub-block only contains 3*3*3 data; at last, only a plurality of 3*3*3 data blocks need to be calculated. Based on a traditional butterfly structure, the hardware structure is simple and regular and has in-place performance, internal data do not need to be rearranged, the fast method for three-dimensional discrete Hartley transformation is suitable for realizing engineering hardware and high in accuracy, and computational efficiency of the fast method for three-dimensional discrete Hartley transformation is improved by about 12%-24% compared with that of a classic determinant method.

Description

A Fast Method for 3D Discrete Hartley Transform

技术领域technical field

本发明涉及一种三维离散Hartley变换的快速方法，特别是一种用于图像与视频编码中的三维离散Hartley变换的快速方法，属于数字数据处理技术领域。The invention relates to a fast method for three-dimensional discrete Hartley transformation, in particular to a fast method for three-dimensional discrete Hartley transformation in image and video coding, and belongs to the technical field of digital data processing.

背景技术Background technique

自1987年Buneman提出多维离散DHT后，它便在多维信号处理中引起了广泛的关注。如四维的DHT可以用来分析三维运动图像，也可以用来计算多维的离散傅里叶变换，从而降低计算的复杂度；特别在三维的磁共振图像压缩中，DHT变换具有独特的优越性。Sunder等分别利用三维DHT、三维DCT和三维DFT这三种变换对一幅磁共振脑图像和一幅X线图像进行压缩，比较不同变换方法压缩重建的峰值信噪比（PSNR）和比特率。Sunder的实验结果表明：三维DHT在压缩磁共振脑图像的效果要优于其他两种变换；但对于X线图像的压缩而言，三维DCT的效果最好，而三维DHT次之。多维DHT变换的核函数具有不可分离性，所以很难将一维的算法直接推广至高维。目前较常用的两种快速计算DHT的方法分别是传统的行-列算法和基于多项式的算法，Bortfeld和Dinter也提出利用一维DFT来计算多维DHT。这些方法能够比较有效地减少算术运算量，但算法实现的结构比较复杂。向量基的算法是目前能够有效平衡计算复杂度和实现结构的一种算法。Boussakta等提出三维的向量基-2×2×2（下面简称基-2）时域抽取（Decimation-in-time：DIT）DHT算法和频域的抽取（Decimation-in-frequency：DIF）的算法；之后，Bouguezel等人将基-2的算法推广至任意维数（M-D）的DHT计算，建立了M维DHT的向量基方法与M维复信号FFT算法之间的关系，他们还引入分裂向量基算法用来快速计算三维DHT，并同时将算法推广到更高维DHT的计算。已有研究表明，基于蝶形结构的DHT较行-列法和多项式法在计算复杂度和计算效率之间取得了更好的平衡，向量基的方法不仅可以充分利用变换之间的关系，而且实现结构更为简单、规则。目前，三维DHT快速算法的研究针对的信号长度多为2或4的倍数，但许多实际应用中数据的类型并不局限于此，对数据类型为其他长度的算法也值得进一步探索。Since Buneman proposed the multidimensional discrete DHT in 1987, it has attracted widespread attention in multidimensional signal processing. For example, four-dimensional DHT can be used to analyze three-dimensional moving images, and can also be used to calculate multi-dimensional discrete Fourier transform, thereby reducing the complexity of calculation; especially in three-dimensional magnetic resonance image compression, DHT transform has unique advantages. Sunder et al. used three-dimensional DHT, three-dimensional DCT and three-dimensional DFT to compress an MRI brain image and an X-ray image respectively, and compared the peak signal-to-noise ratio (PSNR) and bit rate of compressed reconstruction with different transformation methods. Sunder's experimental results show that: 3D DHT is better than the other two transformations in compressing MRI brain images; but for the compression of X-ray images, 3D DCT has the best effect, and 3D DHT takes the second place. The kernel function of multi-dimensional DHT transformation is inseparable, so it is difficult to directly extend the one-dimensional algorithm to high-dimensional. Currently, the two commonly used fast calculation methods of DHT are traditional row-column algorithm and polynomial-based algorithm. Bortfeld and Dinter also proposed to use one-dimensional DFT to calculate multi-dimensional DHT. These methods can effectively reduce the amount of arithmetic operations, but the structure of the algorithm is more complicated. The vector-based algorithm is currently an algorithm that can effectively balance the computational complexity and implementation structure. Boussakta et al. proposed a three-dimensional vector base-2×2×2 (hereinafter referred to as base-2) time domain extraction (Decimation-in-time: DIT) DHT algorithm and frequency domain extraction (Decimation-in-frequency: DIF) algorithm ; Later, Bouguezel et al. extended the base-2 algorithm to the DHT calculation of any dimension (M-D), and established the relationship between the M-dimensional DHT vector basis method and the M-dimensional complex signal FFT algorithm. They also introduced the split vector The basic algorithm is used to quickly calculate the three-dimensional DHT, and at the same time extend the algorithm to the calculation of higher-dimensional DHT. Existing studies have shown that the DHT based on the butterfly structure has achieved a better balance between computational complexity and computational efficiency than the row-column method and the polynomial method. The vector-based method can not only make full use of the relationship between transformations, but also The implementation structure is simpler and more regular. At present, the research on fast algorithms for 3D DHT mostly focuses on signal lengths that are multiples of 2 or 4, but the types of data in many practical applications are not limited to this, and algorithms with data types of other lengths are also worthy of further exploration.

发明内容Contents of the invention

发明目的：针对现有技术中存在的问题与不足，本发明提供一种运用于图像和视频编码的三维离散Hartley变换的快速方法。Purpose of the invention: Aiming at the problems and deficiencies in the prior art, the present invention provides a fast method for three-dimensional discrete Hartley transform applied to image and video coding.

技术方案：一种三维离散Hartley变换的快速方法，离散Hartley变换基于蝶形算法的结构，采用分治法的思想，将数据大小为3^m×3^m×3^m的数据块，通过频域抽取将数据通过线性变换和三角函数变换性质将数据块分解为27个3^m-1×3^m-1×3^m-1子模块，将每个子数据块继续通过此方法分解，直至每个子数据只包含3×3×3数据，最后只需计算若干个3×3×3数据块。该方法分三步实现：Technical solution: A fast method for three-dimensional discrete Hartley transform. Discrete Hartley transform is based on the structure of butterfly algorithm, adopts the idea of divide and conquer, and extracts data blocks with a data size of 3 ^m × 3 ^m × 3 ^m through frequency domain The data is decomposed into 27 sub-modules of 3 ^m-1 × 3 ^m-1 × 3 ^m-1 through linear transformation and trigonometric function transformation properties, and each sub-data block is continuously decomposed by this method until each sub-data is only Contains 3×3×3 data, and finally only needs to calculate several 3×3×3 data blocks. This method is implemented in three steps:

利用三角函数变换性质和线性组合计算中间变量S,Si,Dii＝1,2,…,13；Use trigonometric function transformation properties and linear combination to calculate intermediate variables S, Si, Dii=1,2,...,13;

将频域抽取的N×N×N序列分解成

的S序列的计算（其中N为数据每一个维度的大小）；返回第一步对

计算，直至序列大小为3×3×3。重述N×N×N实序列x(n₁,n₂,n₃)三维DHT定义如下：Decompose the N×N×N sequence extracted in the frequency domain into

The calculation of the S sequence (where N is the size of each dimension of the data); return the first step to

Calculate until the sequence size is 3×3×3. Restate the N×N×N real sequence x(n ₁ ,n ₂ ,n ₃ ) three-dimensional DHT definition as follows:

$X x (({k k}_{11},, {k k}_{22},, {k k}_{33})) = = {Σ Σ}_{{n no}_{11} = = 00}^{N N - - 11} {Σ Σ}_{{n no}_{22} = = 00}^{N N - - 11} {Σ Σ}_{{n no}_{33} = = 00}^{N N - - 11} x x (({n no}_{11},, {n no}_{22} {n no}_{33})) cas cas [[\frac{22 π π}{N N} (({n no}_{11} {k k}_{11} + + {n no}_{22} {k k}_{22} + + {n no}_{33} {k k}_{33}))]] {k k}_{1,2,3 1,2,3} = = 0,1,2 0,1,2,, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; N N - - - - - - ((00))$

其中x（n₁,n₂,n₃）是输入序列，X(k₁,k₂,k₃)是输出序列。where x(n ₁ ,n ₂ ,n ₃ ) is the input sequence, and X(k ₁ ,k ₂ ,k ₃ ) is the output sequence.

这里要求数据的模块大小满足N＝3^q Here the module size of the data is required to satisfy N=3 ^q

根据三角函数性质，可以推导出DHT具有以下性质：According to the properties of trigonometric functions, it can be deduced that DHT has the following properties:

X(k₁,k₂,N-k₃)＝X(k₁,k₂,-k₃) (1)X(k ₁ ,k ₂ ,Nk ₃ )=X(k ₁ ,k ₂ ,-k ₃ ) (1)

X(k₁,N-k₂,k₃)＝X(k₁,-k₂,k₃) (2)X(k ₁ ,Nk ₂ ,k ₃ )=X(k ₁ ,-k ₂ ,k ₃ ) (2)

X(N-k₁,k₂,k₃)＝X(-k₁,k₂,k₃) (3)X(Nk ₁ ,k ₂ ,k ₃ )=X(-k ₁ ,k ₂ ,k ₃ ) (3)

X(k₁,N-k₂,N-k₃)＝X(k₁,-k₂,-k₃) (4)X(k ₁ ,Nk ₂ ,Nk ₃ )=X(k ₁ ,-k ₂ ,-k ₃ ) (4)

X(N-k₁,k₂,N-k₃)＝X(-k₁,k₂,-k₃) (5)X(Nk ₁ ,k ₂ ,Nk ₃ )=X(-k ₁ ,k ₂ ,-k ₃ ) (5)

X(N-k₁,N-k₂,k₃)＝X(-k₁,-k₂,k₃) (6)X(Nk ₁ ,Nk ₂ ,k ₃ )=X(-k ₁ ,-k ₂ ,k ₃ ) (6)

X(N-k₁,N-k₂,N-k₃)＝X(-k₁,-k₂,-k₃) (7)根据式(1)-(7)所示的DHT性质，N×N×N点的DHT可以根据输出序列的k₁,k₂,k₃除以3的非负余数分组求取：X(Nk ₁ , Nk ₂ , Nk ₃ )=X(-k ₁ ,-k ₂ ,-k ₃ ) (7) According to the DHT properties shown in formulas (1)-(7), N×N×N points The DHT of can be calculated according to the non-negative remainder of k ₁ , k ₂ , k ₃ of the output sequence divided by 3:

$[\begin{matrix} {A A}_{i i} (({k k}_{11},, {k k}_{22},, {k k}_{33})) \\ {B B}_{i i} (({k k}_{11},, {k k}_{22},, {k k}_{33})) \end{matrix}] = = [\begin{matrix} 11 & 11 \\ 11 & - - 11 \end{matrix}] [\begin{matrix} X x (({33 k k}_{11} + + {p p}_{i i},, {33 k k}_{22} + + {q q}_{i i},, {33 k k}_{33} + + {r r}_{i i})) \\ X x (({33 k k}_{11} - - {p p}_{i i},, {33 k k}_{22} - - {q q}_{i i},, {33 k k}_{33} - - {r r}_{i i})) \end{matrix}] - - - - - - ((88))$

其中in

[pqr]_i＝[001,010,100,011,101,110,01(-1),10(-1),1(-1)0,111,11(-1),1(-1)1,(-1)11]，i＝1,2,3,...,13。[pqr] _i = [001,010,100,011,101,110,01(-1),10(-1),1(-1)0,111,11(-1),1(-1)1,(-1)11], i=1 ,2,3,...,13.

定义中间变量Define intermediate variables

为简化书写计算，我们在计算A_i(k₁,k₂,k₃),B_i(k₁,k₂,k₃)时引入一些符号：In order to simplify the written calculation, we introduce some symbols when calculating A _i (k ₁ ,k ₂ ,k ₃ ),B _i (k ₁ ,k ₂ ,k ₃ ):

a₀＝x(n₁,n₂,n₃), $a_{1} = x (n_{1}, n_{2}, n_{3} + \frac{N}{3}),$ $a_{2} = x (n_{1}, n_{2}, n_{3} + \frac{2 N}{3}),$ a ₀ =x(n ₁ ,n ₂ ,n ₃ ), $a_{1} = x ({no}_{1}, {no}_{2}, {no}_{3} + \frac{N}{3}),$ $a_{2} = x ({no}_{1}, {no}_{2}, {no}_{3} + \frac{2 N}{3}),$

${a a}_{33} = = x x (({n no}_{11},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33})),,$ ${a a}_{44} = = x x (({n no}_{11},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33} + + \frac{N N}{33})),,$ ${a a}_{55} = = x x (({n no}_{11},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33} + + \frac{22 N N}{33})),,$

${a a}_{66} = = x x (({n no}_{11},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33})),,$ ${a a}_{77} = = x x (({n no}_{11},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33} + + \frac{N N}{33})),,$ ${a a}_{88} = = x x (({n no}_{11},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33} + + \frac{22 N N}{33})),,$

${a a}_{99} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22},, {n no}_{33})),,$ ${a a}_{1010} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22},, {n no}_{33} + + \frac{N N}{33})),,$ ${a a}_{1111} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22},, {n no}_{33} + + \frac{22 N N}{33})),,$

${a a}_{1212} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33})),,$ ${a a}_{1313} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33} + + \frac{N N}{33})),,$

${a a}_{1414} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33} + + \frac{22 N N}{33})),,$ ${a a}_{1515} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33})),,$

${a a}_{1616} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33} + + \frac{N N}{33})),,$ ${a a}_{1717} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33} + + \frac{22 N N}{33})),,$

${a a}_{1818} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22},, {n no}_{33})),,$ ${a a}_{1919} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22},, {n no}_{33} + + \frac{N N}{33})),,$

${a a}_{2020} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22},, {n no}_{33} + + \frac{22 N N}{33})),,$ ${a a}_{21 twenty one} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33})),,$

${a a}_{22 twenty two} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33} + + \frac{N N}{33})),,$ ${a a}_{23 twenty three} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33} + + \frac{22 N N}{33})),,$

${a a}_{24 twenty four} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33})),,$ ${a a}_{2525} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33} + + \frac{N N}{33})),,$

${a a}_{2626} = = x x (({n no}_{11} + + \frac{22 N N}{33},, {n no}_{22} + + \frac{22 N N}{33},, {n no}_{33} + + \frac{22 N N}{33})),,$

并定义如下变量：And define variables like this:

c₁＝a₁+a₂,c₂＝a₃+a₆,c₃＝a₄+a₈,c₄＝a₅+a₇,c₅＝a₉+a₁₈,c₆＝a₁₀+a₂₀,c₇＝a₁₁+a₁₉,c₈＝a₁₂+a₂₄,c₉＝a₁₃+a₂₆,c₁₀＝a₁₄+a₂₅,c₁₁＝a₁₅+a₂₁,a₁₂＝a₁₆+a₂₃,c₁₃＝a₁₇+a₂₂.c ₁ =a ₁ +a ₂ ,c ₂ =a ₃ +a ₆ ,c ₃ =a ₄ +a ₈ ,c ₄ =a ₅ +a ₇ ,c ₅ =a ₉ +a ₁₈ ,c ₆ =a ₁₀ +a ₂₀ ,c ₇ =a ₁₁ +a ₁₉ ,c ₈ =a ₁₂ +a ₂₄ ,c ₉ =a ₁₃ +a ₂₆ ,c ₁₀ =a ₁₄ +a ₂₅ ,c ₁₁ =a ₁₅ +a ₂₁ ,a ₁₂ ＝a ₁₆ +a ₂₃ ,c ₁₃ ＝a ₁₇ +a ₂₂ .

为了减少计算量，将变量线性组合：To reduce computation, the variables are linearly combined:

$S S = = {Σ Σ}_{i i = = 00}^{2626} {a a}_{i i} = = {a a}_{00} + + {Σ Σ}_{i i = = 11}^{1313} {c c}_{i i} - - - - - - ((99))$

$[\begin{matrix} {S S}_{11} \\ {S S}_{22} \\ {S S}_{33} \\ {S S}_{44} \\ {S S}_{55} \\ {S S}_{66} \\ {S S}_{77} \\ {S S}_{88} \\ {S S}_{99} \\ {S S}_{1010} \\ {S S}_{1111} \\ {S S}_{1212} \\ {S S}_{1313} \end{matrix}=]] = = 33 [\begin{matrix} 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 \\ 11 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 & 00 & 00 & 00 \\ 11 & 11 & 11 & 11 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\ 00 & 00 & 00 & 11 & 11 & 00 & 00 & 00 & 00 & 11 & 00 & 11 & 00 \\ 00 & 11 & 00 & 00 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 \\ 00 & 00 & 11 & 00 & 11 & 00 & 00 & 00 & 00 & 11 & 00 & 00 & 11 \\ 00 & 11 & 00 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \end{matrix}] [\begin{matrix} {c c}_{11} \\ {c c}_{22} \\ {c c}_{33} \\ {c c}_{44} \\ {c c}_{55} \\ {c c}_{66} \\ {c c}_{77} \\ {c c}_{88} \\ {c c}_{99} \\ {c c}_{1010} \\ {c c}_{1111} \\ {c c}_{1212} \\ {c c}_{1313} \end{matrix}] + + {33 a a}_{00} - - S S - - - - - - ((1010))$

以及as well as

d₁＝a₁-a₂,d₂＝a₃-a₆,d₃＝a₄-a₈,d₄＝a₅-a₇,d₅＝a₉-a₁₈,d₆＝a₁₀-a₂₀,d₇＝a₁₁-a₁₉,d₈＝a₁₂-a₂₄,d₉＝a₁₃-a₂₆,d₁₀＝a₁₄-a₂₅,d₁₁＝a₁₅-a₂₁,d₁₂＝a₁₆-a₂₃,d₁₃＝a₁₇-a₂₂.d ₁ =a ₁ -a ₂ ,d ₂ =a ₃ -a ₆ ,d ₃ =a ₄ -a ₈ ,d ₄ =a ₅ -a ₇ ,d ₅ =a ₉ -a ₁₈ ,d ₆ =a ₁₀ -a ₂₀ ,d ₇ =a ₁₁ -a ₁₉ ,d ₈ =a ₁₂ -a ₂₄ ,d ₉ =a ₁₃ -a ₂₆ ,d ₁₀ =a ₁₄ -a ₂₅ ,d ₁₁ =a ₁₅ -a ₂₁ ,d ₁₂ ＝a ₁₆ -a ₂₃ ,d ₁₃ ＝a ₁₇ -a ₂₂ .

和and

$[\begin{matrix} {D D.}_{11} \\ {D D.}_{22} \\ {D D.}_{33} \\ {D D.}_{44} \\ {D D.}_{55} \\ {D D.}_{66} \\ {D D.}_{77} \\ {D D.}_{88} \\ {D D.}_{99} \\ {D D.}_{1010} \\ {D D.}_{1111} \\ {D D.}_{1212} \\ {D D.}_{1313} \end{matrix}] = = [\begin{matrix} 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 \\ 00 & 11 & 11 & 11 & 00 & 00 & 00 & 11 & 11 & 11 & - - 11 & - - 11 & - - 11 \\ 00 & 00 & 00 & 00 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 11 & 11 & - - 11 & 00 & 11 & 11 & - - 11 & 11 & - - 11 & 00 & - - 11 & 00 & 11 \\ 11 & 00 & 11 & - - 11 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 & 00 \\ 00 & 11 & 11 & 11 & 11 & 11 & 11 & - - 11 & - - 11 & - - 11 & 00 & 00 & 00 \\ 11 & - - 11 & 00 & 11 & 00 & 11 & - - 11 & - - 11 & 00 & 11 & 11 & - - 11 & 11 \\ 11 & 00 & 11 & - - 11 & - - 11 & 11 & - - 11 & 00 & 00 & 11 & - - 11 & 00 & 11 \\ 00 & 11 & 11 & 11 & - - 11 & - - 11 & - - 11 & 00 & 00 & 11 & 00 & 11 & 11 \\ 11 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & - - 11 & 00 & 11 & 00 & 11 & - - 11 \\ 11 & - - 11 & 00 & 11 & 11 & - - 11 & 00 & 00 & 11 & - - 11 & - - 11 & 00 & 11 \\ 11 & - - 11 & 00 & 11 & 11 & - - 11 & 00 & 00 & 11 & - - 11 & - - 11 & 00 & 11 \\ 11 & 11 & - - 11 & 00 & - - 11 & 00 & 11 & 00 & 11 & - - 11 & 11 & - - 11 & 00 \end{matrix}] [\begin{matrix} {d d}_{11} \\ {d d}_{22} \\ {d d}_{33} \\ {d d}_{44} \\ {d d}_{55} \\ {d d}_{66} \\ {d d}_{77} \\ {d d}_{88} \\ {d d}_{99} \\ {d d}_{1010} \\ {d d}_{1111} \\ {d d}_{1212} \\ {d d}_{1313} \end{matrix}] - - - - - - ((1111))$

计算A₀(k₁,k₂,k₃)，A_i(k₁,k₂,k₃),B_i(k₁,k₂,k₃),i＝1,2,3,...,13。Calculate A ₀ (k ₁ ,k ₂ ,k ₃ ), A _i (k ₁ ,k ₂ ,k ₃ ),B _i (k ₁ ,k ₂ ,k ₃ ),i=1,2,3,.. .,13.

1）计算A₀(k₁,k₂,k₃)＝X(3k₁,3k₂,3k₃)1) Calculate A ₀ (k ₁ ,k ₂ ,k ₃ )=X(3k ₁ ,3k ₂ ,3k ₃ )

其中

in

这样N×N×N点的DHT计算就转化成了

点序列S的DHT的计算。In this way, the DHT calculation of N×N×N points is transformed into

Computation of the DHT of the point sequence S.

2）计算A₁(k₁,k₂,k₃)和B₁(k₁,k₂,k₃)2) Calculate A ₁ (k ₁ ,k ₂ ,k ₃ ) and B ₁ (k ₁ ,k ₂ ,k ₃ )

其中 $θ_{1} = \frac{2 π n_{3}}{N} .$ in $θ_{1} = \frac{2 π {no}_{3}}{N} .$

从上式可以看到，N×N×N点序列x(n₁,n₂,n₃)的DHT就转化成了

点的序列

{(S}_{1} \cos θ_{1} - \sqrt{3} D_{1} \sin θ_{1})

的DHT计算。It can be seen from the above formula that the DHT of the N×N×N point sequence x(n ₁ ,n ₂ ,n ₃ ) is transformed into

sequence of points

{(S}_{1} \cos θ_{1} - \sqrt{3} {D.}_{1} \sin θ_{1})

DHT calculation.

下面计算B₁(k₁,k₂,k₃)Calculate B ₁ (k ₁ ,k ₂ ,k ₃ ) below

但上式的形式并不是

点的DHT形式。根据式三角函数性质可以知道：But the form of the above formula is not

The DHT form of the point. According to the properties of trigonometric functions, we can know:

${B B}_{11} ((\frac{N N}{33} - - {k k}_{11},, \frac{N N}{33} - - {k k}_{22},, \frac{N N}{33} - - {k k}_{33})) = = {B B}_{11} (({- - k k}_{11},, {- - k k}_{22},, {- - k k}_{33}))$

因此只要求出的值，再做反褶运算，同样能够得到B₁(k₁,k₂,k₃)。Therefore only ask for The value of B ₁ (k ₁ ,k ₂ ,k ₃ ) can also be obtained by defolding operation.

下面求 $B_{1} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) :$ Seek below $B_{1} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) :$

得出：inferred:

${B B}_{11} ((\frac{N N}{33} - - {k k}_{11},, \frac{N N}{33} - - {k k}_{22},, \frac{N N}{33} - - {k k}_{33})) = = {Σ Σ}_{{n no}_{11} = = 00}^{N N / / 33 - - 11} {Σ Σ}_{{n no}_{22} = = 00}^{N N / / 33 - - 11} {Σ Σ}_{{n no}_{33} = = 00}^{N N / / 33 - - 11} (({S S}_{11} cos cos {θ θ}_{11} - - \sqrt{33} {D D.}_{11} sin sin {θ θ}_{11})) casφ casφ$

这样N×N×N点x(n1,n2,n3)的DHT也转化成为

点序列的DHT。再对输出序列做反褶运算，就可以得到B₁(k₁,k₂,k₃)。In this way, the DHT of N×N×N point x(n1,n2,n3) is also transformed into

point sequence DHT. Then defold the output sequence to obtain B ₁ (k ₁ ,k ₂ ,k ₃ ).

根据三角函数性质可以得到According to the properties of trigonometric functions, we can get

$X x (({33 k k}_{11},, {33 k k}_{22},, {33 k k}_{33} + + 11)) = = \frac{11}{22} [[{A A}_{11} (({k k}_{11},, {k k}_{22},, {k k}_{33})) + + {B B}_{11} (({k k}_{11},, {k k}_{22},, {k k}_{33}))]]$

$X x (({33 k k}_{11},, {33 k k}_{22},, {33 k k}_{33} - - 11)) = = \frac{11}{22} [[{A A}_{11} (({k k}_{11},, {k k}_{22},, {k k}_{33})) - - {B B}_{11} (({k k}_{11},, {k k}_{22},, {k k}_{33}))]]$

这样N×N×N点的DHT变换就可以通过

点DHT变换求得。In this way, the DHT transformation of N×N×N points can be passed

Obtained by point DHT transformation.

3）同理，计算A_i(k₁,k₂,k₃),B_i(k₁,k₂,k₃),i＝1,2,3,...,133) Similarly, calculate A _i (k ₁ ,k ₂ ,k ₃ ), B _i (k ₁ ,k ₂ ,k ₃ ), i=1,2,3,...,13

其中

in

$[\begin{matrix} {θ θ}_{11} \\ {θ θ}_{22} \\ {θ θ}_{33} \\ {θ θ}_{44} \\ {θ θ}_{55} \\ {θ θ}_{66} \\ {θ θ}_{77} \\ {θ θ}_{88} \\ {θ θ}_{99} \\ {θ θ}_{1010} \\ {θ θ}_{1111} \\ {θ θ}_{1212} \\ {θ θ}_{1313} \end{matrix}] = = \frac{22 π π}{N N} [\begin{matrix} 00 & 00 & 11 \\ 00 & 11 & 00 \\ 11 & 00 & 00 \\ 00 & 11 & 11 \\ 11 & 00 & 11 \\ 11 & 11 & 00 \\ 00 & 11 & - - 11 \\ 11 & 00 & - - 11 \\ 11 & - - 11 & 00 \\ 11 & 11 & 11 \\ 11 & 11 & - - 11 \\ 11 & - - 11 & 11 \\ - - 11 & 11 & 11 \end{matrix}] [\begin{matrix} {n no}_{11} \\ {n no}_{22} \\ {n no}_{33} \end{matrix}] - - - - - - ((1717))$

从式(12)(15)（16）（17）可以看到，N×N×N序列x(n₁,n₂,n₃)的3-D DHT转化成了27个长度

序列的DHT变换，这样不断分解直至分解到3×3×3的序列。From equations (12)(15)(16)(17), it can be seen that the 3-D DHT of the N×N×N sequence x(n ₁ ,n ₂ ,n ₃ ) is transformed into 27 length

The DHT transformation of the sequence is continuously decomposed until it is decomposed into a 3×3×3 sequence.

有益效果：本发明提供的三维离散Hartley变换的快速方法，针对长度为的3^m×3^m×3^m序列的处理十分有效，若数据长度不为3^m×3^m×3^m可以进行补零；本方法基于蝶形结构，具有简单、规整的结构；本方法在保证精度与背景技术中的方法基本相同的情况下，有效的减少了运算量。Beneficial effects: the fast method of three-dimensional discrete Hartley transform provided by the present invention is very effective for the processing of 3 ^m × 3 ^m × 3 ^m sequence, if the data length is not 3 ^m × 3 ^m × 3 ^m , zero padding can be performed ; This method is based on the butterfly structure and has a simple and regular structure; this method effectively reduces the amount of computation while ensuring that the accuracy is basically the same as the method in the background technology.

附图说明Description of drawings

图1为本发明实施例的基-3的3D DHT变换计算结构图。Fig. 1 is the 3D DHT transformation calculation structural diagram of base-3 of the embodiment of the present invention.

具体实施方式Detailed ways

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。Below in conjunction with specific embodiment, further illustrate the present invention, should be understood that these embodiments are only used to illustrate the present invention and are not intended to limit the scope of the present invention, after having read the present invention, those skilled in the art will understand various equivalent forms of the present invention All modifications fall within the scope defined by the appended claims of this application.

实施例1：Example 1:

采用图1所示的三维离散Hartley变换的快速方法结构。A fast method structure using the three-dimensional discrete Hartley transform shown in Fig. 1.

三维离散Hartley变换的快速方法变换过程如下：The fast method transformation process of three-dimensional discrete Hartley transformation is as follows:

先将输入序列进行线性组合和三角函数变换，得到中间变量S_i，D_i，然后再将S_i，D_i进行线性组合和三角函数变换得到频域数据。First, the input sequence is linearly combined and transformed by trigonometric functions to obtain intermediate variables S _i and D _i , and then linearly combined and transformed by S _i and D _i to obtain frequency domain data.

输入3×3×3序列：Enter a 3×3×3 sequence:

将输入序列利用公式Convert the input sequence using the formula

进行符号化，得到：Symbolize to get:

a₀ a ₀ a₁ a ₁ a₂ a ₂ a₃ a ₃ a₄ a ₄ a₅ a ₅ a₆ a ₆ 00 11 22 33 44 55 66 a₇ a ₇ a₈ a ₈ a₉ a ₉ a₁₀ a ₁₀ a₁₁ a ₁₁ a₁₂ a ₁₂ a₁₃ a ₁₃ 77 88 99 1010 1111 1212 1313 a₁₄ a ₁₄ a₁₅ a ₁₅ a₁₆ a ₁₆ a₁₇ a ₁₇ a₁₈ a ₁₈ a₁₉ a ₁₉ a₂₀ a ₂₀ 1414 1515 1616 1717 1818 1919 2020 a₂₁ a ₂₁ a₂₂ a ₂₂ a₂₃ a ₂₃ a₂₄ a ₂₄ a₂₅ a ₂₅ a₂₆ a ₂₆ 21twenty one 22twenty two 23twenty three 24twenty four 2525 2626

利用公式use the formula

和and

进行线性组合，得：Perform linear combination to get:

c₁ c ₁ c₂ c ₂ c₃ c ₃ c₄ c ₄ c₅ c ₅ c₆ c ₆ c₇ c ₇ c₈ c ₈ c₉ c ₉ c₁₀ c ₁₀ c₁₁ c ₁₁ c₁₂ c ₁₂ c₁₃ c ₁₃ 33 99 1212 1212 2727 3030 3030 3636 3939 3939 3636 3939 3939 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 ₁₃ -1-1 -3-3 -4-4 -2-2 -9-9 -10-10 -8-8 -12-12 -13-13 -11-11 -6-6 -7-7 -5-5

利用公式：Use the formula:

$S S = = {Σ Σ}_{i i = = 00}^{2626} {a a}_{i i} = = {a a}_{00} + + {Σ Σ}_{i i = = 11}^{1313} {c c}_{i i}$

$[\begin{matrix} {S S}_{11} \\ {S S}_{22} \\ {S S}_{33} \\ {S S}_{44} \\ {S S}_{55} \\ {S S}_{66} \\ {S S}_{77} \\ {S S}_{88} \\ {S S}_{99} \\ {S S}_{1010} \\ {S S}_{1111} \\ {S S}_{1212} \\ {S S}_{1313} \end{matrix}=]] = = 33 [\begin{matrix} 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 \\ 11 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 & 00 & 00 & 00 \\ 11 & 11 & 11 & 11 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\ 00 & 00 & 00 & 11 & 11 & 00 & 00 & 00 & 00 & 11 & 00 & 11 & 00 \\ 00 & 11 & 00 & 00 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 \\ 00 & 00 & 11 & 00 & 11 & 00 & 00 & 00 & 00 & 11 & 00 & 00 & 11 \\ 00 & 11 & 00 & 00 & 00 & 11 & 00 & 00 & 11 & 00 & 00 & 11 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \\ 11 & 00 & 00 & 00 & 00 & 00 & 00 & 11 & 11 & 11 & 00 & 00 & 00 \end{matrix}] [\begin{matrix} {c c}_{11} \\ {c c}_{22} \\ {c c}_{33} \\ {c c}_{44} \\ {c c}_{55} \\ {c c}_{66} \\ {c c}_{77} \\ {c c}_{88} \\ {c c}_{99} \\ {c c}_{1010} \\ {c c}_{1111} \\ {c c}_{1212} \\ {c c}_{1313} \end{matrix}] + + {33 a a}_{00} - - S S$

$[\begin{matrix} {D D.}_{11} \\ {D D.}_{22} \\ {D D.}_{33} \\ {D D.}_{44} \\ {D D.}_{55} \\ {D D.}_{66} \\ {D D.}_{77} \\ {D D.}_{88} \\ {D D.}_{99} \\ {D D.}_{1010} \\ {D D.}_{1111} \\ {D D.}_{1212} \\ {D D.}_{1313} \end{matrix}] = = [\begin{matrix} 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 \\ 00 & 11 & 11 & 11 & 00 & 00 & 00 & 11 & 11 & 11 & - - 11 & - - 11 & - - 11 \\ 00 & 00 & 00 & 00 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 11 & 11 & - - 11 & 00 & 11 & 11 & - - 11 & 11 & - - 11 & 00 & - - 11 & 00 & 11 \\ 11 & 00 & 11 & - - 11 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & 11 & - - 11 & 00 \\ 00 & 11 & 11 & 11 & 11 & 11 & 11 & - - 11 & - - 11 & - - 11 & 00 & 00 & 00 \\ 11 & - - 11 & 00 & 11 & 00 & 11 & - - 11 & - - 11 & 00 & 11 & 11 & - - 11 & 11 \\ 11 & 00 & 11 & - - 11 & - - 11 & 11 & - - 11 & 00 & 00 & 11 & - - 11 & 00 & 11 \\ 00 & 11 & 11 & 11 & - - 11 & - - 11 & - - 11 & 00 & 00 & 11 & 00 & 11 & 11 \\ 11 & 11 & - - 11 & 00 & 11 & - - 11 & 00 & - - 11 & 00 & 11 & 00 & 11 & - - 11 \\ 11 & - - 11 & 00 & 11 & 11 & - - 11 & 00 & 00 & 11 & - - 11 & - - 11 & 00 & 11 \\ 11 & - - 11 & 00 & 11 & 11 & - - 11 & 00 & 00 & 11 & - - 11 & - - 11 & 00 & 11 \\ 11 & 11 & - - 11 & 00 & - - 11 & 00 & 11 & 00 & 11 & - - 11 & 11 & - - 11 & 00 \end{matrix}] [\begin{matrix} {d d}_{11} \\ {d d}_{22} \\ {d d}_{33} \\ {d d}_{44} \\ {d d}_{55} \\ {d d}_{66} \\ {d d}_{77} \\ {d d}_{88} \\ {d d}_{99} \\ {d d}_{1010} \\ {d d}_{1111} \\ {d d}_{1212} \\ {d d}_{1313} \end{matrix}]$

得到中间变量S_i，D_i：Get intermediate variables S _i , D _i :

然后再将S_i，D_i利用公式，Then S _i , D _i use the formula,

其中

in

$[\begin{matrix} {θ θ}_{11} \\ {θ θ}_{22} \\ {θ θ}_{33} \\ {θ θ}_{44} \\ {θ θ}_{55} \\ {θ θ}_{66} \\ {θ θ}_{77} \\ {θ θ}_{88} \\ {θ θ}_{99} \\ {θ θ}_{1010} \\ {θ θ}_{1111} \\ {θ θ}_{1212} \\ {θ θ}_{1313} \end{matrix}] = = \frac{22 π π}{N N} [\begin{matrix} 00 & 00 & 11 \\ 00 & 11 & 00 \\ 11 & 00 & 00 \\ 00 & 11 & 11 \\ 11 & 00 & 11 \\ 11 & 11 & 00 \\ 00 & 11 & - - 11 \\ 11 & 00 & - - 11 \\ 11 & - - 11 & 00 \\ 11 & 11 & 11 \\ 11 & 11 & - - 11 \\ 11 & - - 11 & 11 \\ - - 11 & 11 & 11 \end{matrix}] [\begin{matrix} {n no}_{11} \\ {n no}_{22} \\ {n no}_{33} \end{matrix}]$

$[\begin{matrix} {A A}_{i i} (({k k}_{11},, {k k}_{22},, {k k}_{33})) \\ {B B}_{i i} (({k k}_{11},, {k k}_{22},, {k k}_{33})) \end{matrix}] = = [\begin{matrix} 11 & 11 \\ 11 & - - 11 \end{matrix}] [\begin{matrix} X x (({33 k k}_{11} + + {p p}_{i i},, {33 k k}_{22} + + {q q}_{i i},, {33 k k}_{33} + + {r r}_{i i})) \\ X x (({33 k k}_{11} - - {p p}_{i i},, {33 k k}_{22} - - {q q}_{i i},, {33 k k}_{33} - - {r r}_{i i})) \end{matrix}]$

进行线性组合和三角函数变换得到频域数据，并与通过定义式（0）计算得出的结果对比：Perform linear combination and trigonometric function transformation to obtain frequency domain data, and compare it with the result calculated by definition (0):

实施例2Example 2

采用图1所示的三维离散Hartley变换的快速方法结构。A fast method structure using the three-dimensional discrete Hartley transform shown in Figure 1.

输入3×3×3序列：Enter a 3×3×3 sequence:

将输入序列利用公式Convert the input sequence using the formula

${a a}_{99} = = x x (({n no}_{11},, {n no}_{22} + + \frac{N N}{33},, {n no}_{33})),,$ ${a a}_{1010} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22},, {n no}_{33} + + \frac{N N}{33})),,$ ${a a}_{1111} = = x x (({n no}_{11} + + \frac{N N}{33},, {n no}_{22},, {n no}_{33} + + \frac{22 N N}{33})),,$

进行符号化，得到：Symbolize to get:

a₀ a ₀ a₁ a ₁ a₂ a ₂ a₃ a ₃ a₄ a ₄ a₅ a ₅ a₆ a ₆ 00 11 00 00 00 00 00 a₇ a ₇ a₈ a ₈ a₉ a ₉ a₁₀ a ₁₀ a₁₁ a ₁₁ a₁₂ a ₁₂ a₁₃ a ₁₃ 00 00 00 00 00 00 00 a₁₄ a ₁₄ a₁₅ a ₁₅ a₁₆ a ₁₆ a₁₇ a ₁₇ a₁₈ a ₁₈ a₁₉ a ₁₉ a₂₀ a ₂₀ 00 00 00 00 00 00 00 a₂₁ a ₂₁ a₂₂ a ₂₂ a₂₃ a ₂₃ a₂₄ a ₂₄ a₂₅ a ₂₅ a₂₆ a ₂₆ 00 00 00 00 00 00

利用公式： $S = Σ_{i = 0}^{26} a_{i} = a_{0} + Σ_{i = 1}^{13} c_{i}$ Use the formula: $S = Σ_{i = 0}^{26} a_{i} = a_{0} + Σ_{i = 1}^{13} c_{i}$

得到中间变量S_i，D_i：Get intermediate variables S _i , D _i :

然后再将S_i，D_i利用公式Then S _i , D _i use the formula

其中 in

Claims

1. the fast method of 3 d-dem Hartley conversion is characterized in that: be 3 with size of data ^m* 3 ^m* 3 ^mData block, extract by frequency domain data be decomposed into 27 3 by linear transformation and trigonometric function conversion character with data block ^M-1* 3 ^M-1* 3 ^M-1Submodule only comprises 3 * 3 * 3 data until each subdata, last several 3 * 3 * 3 data blocks of calculating that only need; This method divided for three steps realized:

1) list entries is utilized trigonometric function conversion character and linear combination calculate intermediate variable S, S _i, D _iI=1,2 ... 13;

2) output sequence is resolved into

The calculating of S sequence, wherein N is the size of each dimension of data;

3) return the 1st) step right

Sequence is carried out decomposition computation, is 3 * 3 * 3 data blocks until sequence size.

2. the fast method of 3 d-dem Hartley according to claim 1 conversion is characterized in that: utilize trigonometric function conversion character with the k of N * N * N Discrete Hartley Transform sequence according to output sequence ₁, k ₂, k ₃K is asked in non-negative remainder grouping divided by 3 ₁, k ₂, k ₃Be the sequence coordinate, X is the Discrete Hartley Transform sequence data, by following or represent with the formula of following equivalence:

A ₀(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂,3k ₃)

A ₁(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂,3k ₃+1)+X(3k ₁,3k ₂,3k ₃-1)

B ₁(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂,3k ₃+1)-X(3k ₁,3k ₂,3k ₃-1)

A ₂(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂+1,3k ₃)+X(3k ₁,3k ₂-1,3k ₃)

B ₂(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂+1,3k ₃)-X(3k ₁,3k ₂-1,3k ₃)

A ₃(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂,3k ₃)+X(3k ₁-1,3k ₂,3k ₃)

B ₃(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂,3k ₃)-X(3k ₁-1,3k ₂,3k ₃)

A ₄(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂+1,3k ₃+1)+X(3k ₁,3k ₂-1,3k ₃-1)

B ₄(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂+1,3k ₃+1)-X(3k ₁,3k ₂-1,3k ₃-1)

A ₅(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂,3k ₃+1)+X(3k ₁-1,3k ₂,3k ₃-1)

B ₅(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂,3k ₃+1)-X(3k ₁-1,3k ₂,3k ₃-1)

A ₆(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂+1,3k ₃)+X(3k ₁-1,3k ₂-1,3k ₃)

B ₆(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂+1,3k ₃)-X(3k ₁-1,3k ₂-1,3k ₃)

A ₇(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂+1,3k ₃-1)+X(3k ₁,3k ₂-1,3k ₃+1)

B ₇(k ₁,k ₂,k ₃)＝X(3k ₁,3k ₂+1,3k ₃-1)-X(3k ₁,3k ₂-1,3k ₃+1)

A ₈(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂,3k ₃-1)+X(3k ₁-1,3k ₂,3k ₃+1)

B ₈(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂,3k ₃-1)-X(3k ₁-1,3k ₂,3k ₃+1)

A ₉(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂-1,3k ₃)+X(3k ₁-1,3k ₂+1,3k ₃)

B ₉(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂-1,3k ₃)-X(3k ₁-1,3k ₂+1,3k ₃)

A ₁₀(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂+1,3k ₃+1)+X(3k ₁-1,3k ₂-1,3k ₃-1)

B ₁₀(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂+1,3k ₃+1)-X(3k ₁-1,3k ₂-1,3k ₃-1)

A ₁₁(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂+1,3k ₃-1)+X(3k ₁-1,3k ₂-1,3k ₃+1)

B ₁₁(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂+1,3k ₃-1)-X(3k ₁-1,3k ₂-1,3k ₃+1)

A ₁₂(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂-1,3k ₃+1)+X(3k ₁-1,3k ₂+1,3k ₃-1)

B ₁₂(k ₁,k ₂,k ₃)＝X(3k ₁+1,3k ₂-1,3k ₃+1)-X(3k ₁-1,3k ₂+1,3k ₃-1)

A ₁₃(k ₁,k ₂,k ₃)＝X(3k ₁-1,3k ₂+1,3k ₃+1)+X(3k ₁+1,3k ₂-1,3k ₃-1)

A ₁₃(k ₁,k ₂,k ₃)＝X(3k ₁-1,3k ₂+1,3k ₃+1)-X(3k ₁+1,3k ₂-1,3k ₃-1)

Following formula can be unified to be write as:

[\begin{matrix} A_{i} (k_{1}, k_{2}, k_{3}) \\ B_{i} (k_{1}, k_{2}, k_{3}) \end{matrix}] = [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] [\begin{matrix} X ({3 k}_{1} + p_{i}, {3 k}_{2} + q_{i}, {3 k}_{3} + r_{i}) \\ X ({3 k}_{1} - p_{i}, {3 k}_{2} - q_{i}, {3 k}_{3} - r_{i}) \end{matrix}]

Wherein

[pqr] _i＝[001,010,100,011,101,110,01(-1),10(-1),1(-1)0,111,11(-1),1(-1)1,(-1)11]，i＝1,2,3,...,13。

3. the fast method of 3 d-dem Hartley according to claim 2 conversion is characterized in that: in order to write conveniently, calculating A _i(k ₁, k ₂, k ₃), B _i(k ₁, k ₂, k ₃) time define symbol a ₁～a ₂₆, c ₁～c ₁₃, d ₁～d ₁₃, and utilize trigonometric function character to a ₁～a ₂₆, c ₁～c ₁₃, d ₁～d ₁₃Linear combination obtains S ₁～S ₁₃, D ₁～D ₁₃Wherein, x is the list entries data; By following or represent with the formula of following equivalence:

a ₀＝x(n ₁,n ₂,n ₃),

a_{1} = x (n_{1}, n_{2}, n_{3} + \frac{N}{3}),

a_{2} = x (n_{1}, n_{2}, n_{3} + \frac{2 N}{3}),

a_{3} = x (n_{1}, n_{2} + \frac{N}{3}, n_{3}),

a_{4} = x (n_{1}, n_{2} + \frac{N}{3}, n_{3} + \frac{N}{3}),

a_{5} = x (n_{1}, n_{2} + \frac{N}{3}, n_{3} + \frac{2 N}{3}),

a_{6} = x (n_{1}, n_{2} + \frac{2 N}{3}, n_{3}),

a_{7} = x (n_{1}, n_{2} + \frac{2 N}{3}, n_{3} + \frac{N}{3}),

a_{8} = x (n_{1}, n_{2} + \frac{2 N}{3}, n_{3} + \frac{2 N}{3}),

a_{9} = x (n_{1} + \frac{N}{3}, n_{2}, n_{3}),

a_{10} = x (n_{1} + \frac{N}{3}, n_{2}, n_{3} + \frac{N}{3}),

a_{11} = x (n_{1} + \frac{N}{3}, n_{2}, n_{3} + \frac{2 N}{3}),

a_{12} = x (n_{1} + \frac{N}{3}, n_{2} + \frac{N}{3}, n_{3}),

a_{13} = x (n_{1} + \frac{N}{3}, n_{2} + \frac{N}{3}, n_{3} + \frac{N}{3}),

a_{14} = x (n_{1} + \frac{N}{3}, n_{2} + \frac{N}{3}, n_{3} + \frac{2 N}{3}),

a_{15} = x (n_{1} + \frac{N}{3}, n_{2} + \frac{2 N}{3}, n_{3}),

a_{16} = x (n_{1} + \frac{N}{3}, n_{2} + \frac{2 N}{3}, n_{3} + \frac{N}{3}),

a_{17} = x (n_{1} + \frac{N}{3}, n_{2} + \frac{2 N}{3}, n_{3} + \frac{2 N}{3}),

a_{18} = x (n_{1} + \frac{2 N}{3}, n_{2}, n_{3}),

a_{19} = x (n_{1} + \frac{2 N}{3}, n_{2}, n_{3} + \frac{N}{3}),

a_{20} = x (n_{1} + \frac{2 N}{3}, n_{2}, n_{3} + \frac{2 N}{3}),

a_{21} = x (n_{1} + \frac{2 N}{3}, n_{2} + \frac{N}{3}, n_{3}),

a_{22} = x (n_{1} + \frac{2 N}{3}, n_{2} + \frac{N}{3}, n_{3} + \frac{N}{3}),

a_{23} = x (n_{1} + \frac{2 N}{3}, n_{2} + \frac{N}{3}, n_{3} + \frac{2 N}{3}),

a_{24} = x (n_{1} + \frac{2 N}{3}, n_{2} + \frac{2 N}{3}, n_{3}),

a_{25} = x (n_{1} + \frac{2 N}{3}, n_{2} + \frac{2 N}{3}, n_{3} + \frac{N}{3}),

a_{26} = x (n_{1} + \frac{2 N}{3}, n_{2} + \frac{2 N}{3}, n_{3} + \frac{2 N}{3}),

c ₁＝a ₁+a ₂,c ₂＝a ₃+a ₆,c ₃＝a ₄+a ₈,c ₄＝a ₅+a ₇,c ₅＝a ₉+a ₁₈,c ₆＝a ₁₀+a ₂₀,c ₇＝a ₁₁+a ₁₉,c ₈＝a ₁₂+a ₂₄,c ₉＝a ₁₃+a ₂₆,c ₁₀＝a ₁₄+a ₂₅,c ₁₁＝a ₁₅+a ₂₁,a ₁₂＝a ₁₆+a ₂₃,c ₁₃＝a ₁₇+a ₂₂.

S = Σ_{i = 0}^{26} a_{i} = a_{0} + Σ_{i = 1}^{13} c_{i}

[\begin{matrix} S_{1} \\ S_{2} \\ S_{3} \\ S_{4} \\ S_{5} \\ S_{6} \\ S_{7} \\ S_{8} \\ S_{9} \\ S_{10} \\ S_{11} \\ S_{12} \\ S_{13} \end{matrix}=] = 3 [\begin{matrix} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} c_{1} \\ c_{2} \\ c_{3} \\ c_{4} \\ c_{5} \\ c_{6} \\ c_{7} \\ c_{8} \\ c_{9} \\ c_{10} \\ c_{11} \\ c_{12} \\ c_{13} \end{matrix}] + {3 a}_{0} - S

And

d ₁＝a ₁-a ₂,d ₂＝a ₃-a ₆,d ₃＝a ₄-a ₈,d ₄＝a ₅-a ₇,d ₅＝a ₉-a ₁₈,d ₆＝a ₁₀-a ₂₀,d ₇＝a ₁₁-a ₁₉,d ₈＝a ₁₂-a ₂₄,d ₉＝a ₁₃-a ₂₆,d ₁₀＝a ₁₄-a ₂₅,d ₁₁＝a ₁₅-a ₂₁,d ₁₂＝a ₁₆-a ₂₃,d ₁₃＝a ₁₇-a ₂₂

With

[\begin{matrix} D_{1} \\ D_{2} \\ D_{3} \\ D_{4} \\ D_{5} \\ D_{6} \\ D_{7} \\ D_{8} \\ D_{9} \\ D_{10} \\ D_{11} \\ D_{12} \\ D_{13} \end{matrix}] = [\begin{matrix} 1 & 0 & 1 & - 1 & 0 & 1 & - 1 & 0 & 1 & - 1 & 0 & 1 & - 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & - 1 & - 1 & - 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & - 1 & 0 & 1 & 1 & - 1 & 1 & - 1 & 0 & - 1 & 0 & 1 \\ 1 & 0 & 1 & - 1 & 1 & - 1 & 0 & 1 & - 1 & 0 & 1 & - 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & - 1 & - 1 & - 1 & 0 & 0 & 0 \\ 1 & - 1 & 0 & 1 & 0 & 1 & - 1 & - 1 & 0 & 1 & 1 & - 1 & 1 \\ 1 & 0 & 1 & - 1 & - 1 & 1 & - 1 & 0 & 0 & 1 & - 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & - 1 & - 1 & - 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & - 1 & 0 & 1 & - 1 & 0 & - 1 & 0 & 1 & 0 & 1 & - 1 \\ 1 & - 1 & 0 & 1 & 1 & - 1 & 0 & 0 & 1 & - 1 & - 1 & 0 & 1 \\ 1 & - 1 & 0 & 1 & 1 & - 1 & 0 & 0 & 1 & - 1 & - 1 & 0 & 1 \\ 1 & 1 & - 1 & 0 & - 1 & 0 & 1 & 0 & 1 & - 1 & 1 & - 1 & 0 \end{matrix}] [\begin{matrix} d_{1} \\ d_{2} \\ d_{3} \\ d_{4} \\ d_{5} \\ d_{6} \\ d_{7} \\ d_{8} \\ d_{9} \\ d_{10} \\ d_{11} \\ d_{12} \\ d_{13} \end{matrix}]

4. the fast method of 3 d-dem Hartley according to claim 3 conversion is characterized in that: described intermediate variable, utilize trigonometric function conversion character, and the Discrete Hartley Transform sequence that N * N * N is ordered is calculated and has just been changed into

The calculating of the Discrete Hartley Transform of some intermediate variable sequence S; In other words, calculate A exactly ₀(k ₁, k ₂, k ₃), A _i(k ₁, k ₂, k ₃), B _i(k ₁, k ₂, k ₃), i=1,2,3 ..., 13; By following or represent with the formula of following equivalence:

1) calculates A ₀(k ₁, k ₂, k ₃)=X (3k ₁, 3k ₂, 3k ₃)

A_{0} (k_{1}, k_{2}, k_{3}) = Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) cas \frac{2 π}{N / 3} (n_{1} k_{1} + n_{2} k_{2} + n_{3} k_{3})

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} Σ_{i = 0}^{2} Σ_{j = 0}^{2} Σ_{k = 0}^{2}

x (n_{1} + i \frac{N}{3}, n_{2} + j \frac{N}{3}, n_{3} + k \frac{N}{3}) cas \frac{2 π}{N / 3} (n_{1} k_{1} + n_{2} k_{2} + n_{3} k_{3})

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} S \cdot cas (φ)

Wherein

N * N * N DHT of ordering calculates and has just changed into like this

The calculating of the DHT of point sequence S;

2) calculate A ₁(k ₁, k ₂, k ₃) and B ₁(k ₁, k ₂, k ₃)

A_{1} (k_{1}, k_{2}, k_{3}) = X ({3 k}_{1}, {3 k}_{2}, {3 k}_{3} + 1) + X ({3 k}_{1}, {3 k}_{2}, {3 k}_{3} - 1)

= Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) {cas \frac{2 π}{N} [{3 n}_{1} k_{1} + {3 n}_{2} k_{2} + n_{3} ({3 k}_{3} + 1)]

+ cas \frac{2 π}{N} [{3 n}_{1} k_{1} + {3 n}_{2} k_{2} + n_{3} ({3 k}_{3} - 1)]}

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π n_{3}}{N} cas (φ)

Use the character of trigonometric function:

cas(θ+C)-cas(θ-C)＝2sinCcas(-θ)

cas(θ+C)+cas(θ-C)＝2cosCcas(-θ)

Can further put in order and be:

Wherein

θ_{1} = \frac{{2 πn}_{3}}{N};

As can be seen from the above equation, (DHT n3) has just changed into N * N * N point sequence x for n1, n2 The sequence of point

(S_{1} \cos θ_{1} - \sqrt{3} D_{1} \sin θ_{1})

DHT calculate;

Calculate B below ₁(k ₁, k ₂, k ₃):

But the form of following formula is not

The DHT form of point; Can know according to formula trigonometric function character:

B_{1} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = B_{1} ({- k}_{1}, {- k}_{2}, {- k}_{3})

As long as therefore obtain

Value, do anti-pleat computing again, can access B equally ₁(k ₁, k ₂, k ₃).

Ask below

B_{1} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) :

Draw:

B_{1} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{1} \sin θ_{1} + \sqrt{3} D_{1} \cos θ_{1}) casφ

N * N * (DHT n3) also transforms into N point x for n1, n2 like this

Point sequence

(S_{1} \sin θ_{1} + \sqrt{3} D_{1} \cos θ_{1})

DHT; Again output sequence is done anti-pleat computing, just can obtain B ₁(k ₁, k ₂, k ₃);

According to above-mentioned A ₁(k ₁, k ₂, k ₃) and

Calculating formula can obtain:

X ({3 k}_{1}, {3 k}_{2}, {3 k}_{3} + 1) = \frac{1}{2} [A_{1} (k_{1}, k_{2}, k_{3}) + B_{1} (k_{1}, k_{2}, k_{3})]

X ({3 k}_{1}, {3 k}_{2}, {3 k}_{3} - 1) = \frac{1}{2} [A_{1} (k_{1}, k_{2}, k_{3}) - B_{1} (k_{1}, k_{2}, k_{3})]

N * N * N DHT conversion of ordering just can be passed through like this

Point DHT conversion is tried to achieve;

3) calculate A ₂(k ₁, k ₂, k ₃) and B ₂(k ₁, k ₂, k ₃)

Wherein

θ_{2} = \frac{{2 πn}_{2}}{N},

B_{2} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{2} \sin θ_{2} + \sqrt{3} D_{2} \cos θ_{2}) casφ

4) calculate A ₃(k ₁, k ₂, k ₃) and B ₃(k ₁, k ₂, k ₃)

A_{3} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1, {3 k}_{2}, {3 k}_{3}) + X ({3 k}_{1} - 1, {3 k}_{2}, {3 k}_{3})

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{{2 πn}_{1}}{N} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} + {2 a}_{1} + {2 a}_{2} + {2 a}_{3} + {2 a}_{4} + {2 a}_{5} + {2 a}_{6} + {2 a}_{7} + {2 a}_{8} - a_{9}

- a_{10} - a_{11} - a_{12} - a_{13} - a_{14} - a_{15} - a_{16} - a_{17} - a_{18} - a_{19} - a_{20}

- a_{21} - a_{22} - a_{23} + {2 a}_{24} - a_{25} - a_{26}] \cos \frac{{2 πn}_{1}}{N}

- \sqrt{3} [a_{9} + a_{10} + a_{11} + a_{12} + a_{13} + a_{14} + a_{15} + a_{16} + a_{17} - a_{18} - a_{19} - a_{20}

- a_{21} - a_{22} - a_{23} - a_{24} - a_{25} - a_{26}] \sin \frac{2 π n_{1}}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{3} \cos θ_{3} - \sqrt{3} D_{3} \sin θ_{3}) casφ

Wherein

θ_{3} = \frac{{2 πn}_{1}}{N};

B_{3} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{3} \cos θ_{3} + \sqrt{3} D_{3} \sin θ_{3}) casφ

5) calculate A ₄(k ₁, k ₂, k ₃) and B ₄(k ₁, k ₂, k ₃)

A_{4} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} {, 3 k}_{2} + 1, {3 k}_{3} + 1) + X ({3 k}_{1}, {3 k}_{2} - 1, {3 k}_{3} - 1)

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} - a_{1} - a_{2} - a_{3} - a_{4} + {2 a}_{5} - a_{6} + {2 a}_{7} - a_{8} + 2 a_{9} - a_{10} - a_{11}

{- a}_{12} - a_{13} + 2 a_{14} - a_{15} + 2 a_{16} - a_{17} + 2 a_{18} - a_{19} - a_{20}

- a_{21} - a_{22} + 2 a_{23} - a_{24} + 2 a_{25} - a_{26}] \cos \frac{2 (n_{2} + n_{3}) π}{N}

- \sqrt{3} [a_{1} - a_{2} + a_{3} - a_{4} - a_{6} + a_{8} + a_{10} - a_{11} + a_{12} - a_{13} - a_{15} + a_{17}

+ a_{19} - a_{20} + a_{21} - a_{22} - a_{24} + a_{26}] \sin \frac{2 (n_{2} + n_{3}) π}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{4} \cos θ_{4} - \sqrt{3} D_{4} \sin θ_{4}) casφ

Wherein

θ_{4} = \frac{2 π (n_{2} + n_{3})}{N};

B_{4} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{4} \cos θ_{4} + \sqrt{3} D_{4} \sin θ_{4}) casφ

6) A ₅(k ₁, k ₂, k ₃) and B ₅(k ₁, k ₂, k ₃)

A_{5} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1, {3 k}_{2}, {3 k}_{3} + 1) + X ({3 k}_{1} - 1, {3 k}_{2}, {3 k}_{3} - 1)

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{1} + n_{3})}{N} cas \frac{2 π}{N / 3} (n_{1} k_{1} + n_{2} k_{2} + n_{3} k_{3})

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} - a_{1} - a_{2} + {2 a}_{3} - a_{4} - a_{5} + {2 a}_{6} {- a}_{7} - a_{8} {- a}_{9} - a_{10} + 2 a_{11}

{- a}_{12} - a_{13} + 2 a_{14} - a_{15} {- a}_{16} + 2 a_{17} {- a}_{18} + 2 a_{19} - a_{20}

- a_{21} + 2 a_{22} {- a}_{23} - a_{24} + 2 a_{25} - a_{26}] \cos \frac{2 (n_{1} + n_{3}) π}{N}

- \sqrt{3} [a_{1} - a_{2} + a_{4} - a_{5} + a_{7} - a_{8} + a_{9} - a_{10} + a_{12} - a_{13} + a_{15} - a_{16}

- a_{18} + a_{20} - a_{21} + a_{23} - a_{24} + a_{26}] \sin \frac{2 (n_{1} + n_{3}) π}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{5} \cos θ_{5} - \sqrt{3} D_{5} \sin θ_{5}) casφ

Wherein

θ_{5} = \frac{2 π (n_{1} + n_{3})}{N}

B_{5} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{5} \cos θ_{5} + \sqrt{3} D_{5} \sin θ_{5}) casφ

7) calculate A ₆(k ₁, k ₂, k ₃) and B ₆(k ₁, k ₂, k ₃)

A_{6} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1 {, 3 k}_{2} + 1, {3 k}_{3}) + X ({3 k}_{1} - 1, {3 k}_{2} - 1, {3 k}_{3})

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{1} + n_{2})}{N} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} + 2 a_{1} + 2 a_{2} - a_{3} - a_{4} {- a}_{5} - a_{6} {- a}_{7} - a_{8} {- a}_{9} - a_{10} - a_{11}

{- a}_{12} - a_{13} {- a}_{14} + 2 a_{15} + 2 a_{16} + 2 a_{17} {- a}_{18} - a_{19} - a_{20}

+ 2 a_{21} + 2 a_{22} + 2 a_{23} - a_{24} {- a}_{25} - a_{26}] \cos \frac{2 (n_{1} + n_{2}) π}{N}

+ \sqrt{3} [a_{3} + a_{4} + a_{5} - a_{6} - a_{7} - a_{8} + a_{9} + a_{10} + a_{11} - a_{12} + a_{13} - a_{14}

- a_{18} - a_{19} - a_{20} + a_{24} + a_{25} + a_{26}] \sin \frac{2 (n_{1} + n_{2}) π}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{6} \cos θ_{6} - \sqrt{3} D_{6} \sin θ_{6}) casφ

Wherein:

θ_{6} = \frac{2 π (n_{1} + n_{2})}{N}

B_{6} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{6} \cos θ_{6} + \sqrt{3} D_{6} \sin θ_{6}) casφ

8) calculate A ₇(k ₁, k ₂, k ₃) and B ₇(k ₁, k ₂, k ₃)

A_{7} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} {, 3 k}_{2} + 1, {3 k}_{3} - 1) + X ({3 k}_{1}, {3 k}_{2} - 1, {3 k}_{3} + 1)

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{2} - n_{3})}{N} cas \frac{2 π}{N / 3} (n_{1} k_{1} + n_{2} k_{2} + n_{3} k_{3})

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} - a_{1} - a_{2} - a_{3} + 2 a_{4} - a_{5} - a_{6} - a_{7} + 2 a_{8} + 2 a_{9} - a_{10} - a_{11}

{- a}_{12} + 2 a_{13} - a_{14} - a_{15} - a_{16} + {2 a}_{17} + 2 a_{18} - a_{19} - a_{20}

- a_{21} + 2 a_{22} {- a}_{23} - a_{24} {- a}_{25} + 2 a_{26}] \cos \frac{2 (n_{2} - n_{3}) π}{N}

+ \sqrt{3} [a_{1} - a_{2} - a_{3} + a_{5} + a_{6} - a_{7} + a_{10} - a_{11} - a_{12} + a_{14} + a_{15} - a_{16}

+ a_{19} - a_{20} - a_{21} + a_{23} + a_{24} - a_{25}] \sin \frac{2 (n_{2} - n_{3}) π}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{7} \cos θ_{7} - \sqrt{3} D_{7} \sin θ_{7}) casφ

B_{7} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{7} \cos θ_{7} + \sqrt{3} D_{7} \sin θ_{7}) casφ

Wherein

θ_{7} = \frac{2 π (n_{2} - n_{3})}{N}

9) calculate A ₈(k ₁, k ₂, k ₃) and B ₈(k ₁, k ₂, k ₃)

A_{8} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1 {, 3 k}_{2}, {3 k}_{3} - 1) + X ({3 k}_{1} - 1, {3 k}_{2}, {3 k}_{3} + 1)

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{1} - n_{3})}{N} cas \frac{2 π}{N / 3} (n_{1} k_{1} + n_{2} k_{2} + n_{3} k_{3})

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} - a_{1} - a_{2} + 2 a_{3} - a_{4} - a_{5} + 2 a_{6} - a_{7} - a_{8} {- a}_{9} + 2 a_{10} - a_{11}

{- a}_{12 +} 2 a_{13} - a_{14} - a_{15} + {2 a}_{16} - a_{17} {- a}_{18} - a_{19} + 2 a_{20}

- a_{21} {- a}_{22} {+ 2 a}_{23} - a_{24} {- a}_{25} + 2 a_{26}] \cos \frac{2 (n_{1} - n_{3}) π}{N}

+ \sqrt{3} [a_{1} - a_{2} + a_{4} - a_{5} + a_{7} - a_{8} - a_{9} + a_{11} - a_{12} + a_{14} - a_{15} + a_{17}

+ a_{18} - a_{19} + a_{21} - a_{22} + a_{24} - a_{25}] \sin \frac{2 (n_{1} - n_{3}) π}{N}} casφ

Wherein

θ_{8} = \frac{2 π (n_{1} - n_{3})}{N};

B_{8} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{8} \cos θ_{8} + \sqrt{3} D_{8} \sin θ_{8}) casφ

10) calculate A ₉(k ₁, k ₂, k ₃) and B ₉(k ₁, k ₂, k ₃)

A_{9} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1 {, 3 k}_{2} - 1, {3 k}_{3}) + X ({3 k}_{1} - 1, {3 k}_{2} + 1, {3 k}_{3})

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{1} - n_{2})}{N} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} + 2 a_{1} + 2 a_{2} {- a}_{3} - a_{4} - a_{5} {- a}_{6} - a_{7} - a_{8} {- a}_{9} {- a}_{10} - a_{11}

{+ 2 a}_{12} + 2 a_{13} + 2 a_{14} - a_{15} {- a}_{16} - a_{17} {- a}_{18} - a_{19} {- a}_{20}

- a_{21} {- a}_{22} {- a}_{23} + 2 a_{24} {+ 2 a}_{25} + 2 a_{26}] \cos \frac{2 (n_{1} - n_{2}) π}{N}

+ \sqrt{3} [a_{3} + a_{4} + a_{5} - a_{6} - a_{7} - a_{8} - a_{9} - a_{10} - a_{11} + a_{15} + a_{16} + a_{17}

+ a_{18} + a_{19} + a_{20} - a_{21} - a_{22} - a_{23}] \sin \frac{2 (n_{1} - n_{2}) π}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{9} \cos θ_{9} - \sqrt{3} D_{9} \sin θ_{9}) casφ

Wherein

θ_{9} = \frac{2 π (n_{1} - n_{2})}{N};

B_{9} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{9} \cos θ_{9} + \sqrt{3} D_{9} \sin θ_{9}) casφ

11) calculate A ₁₀(k ₁, k ₂, k ₃) and B ₁₀(k ₁, k ₂, k ₃)

A_{10} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1 {, 3 k}_{2} + 1, {3 k}_{3} + 1) + X ({3 k}_{1} - 1, {3 k}_{2} - 1, {3 k}_{3} - 1)

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{1} + n_{2} + n_{3})}{N} cas \frac{2 π}{N / 3} (n_{1} k_{1} + n_{2} k_{2} + n_{3} k_{3})

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} - a_{1} - a_{2} {- a}_{3} - a_{4} + 2 a_{5} {- a}_{6} + 2 a_{7} - a_{8} {- a}_{9} {- a}_{10} + 2 a_{11}

{- a}_{12} + 2 a_{13} - a_{14} + 2 a_{15} {- a}_{16} - a_{17} {- a}_{18} + 2 a_{19} {- a}_{20}

+ 2 a_{21} {- a}_{22} {- a}_{23} - a_{24} {- a}_{25} + 2 a_{26}] \cos \frac{2 π (n_{1} + n_{2} + n_{3})}{N}

- \sqrt{3} [a_{1} - a_{2} + a_{3} - a_{4} - a_{6} + a_{8} + a_{9} - a_{10} - a_{12} + a_{14} + a_{16} - a_{17}

- a_{18} + a_{20} + a_{22} - a_{23} + a_{24} - a_{25}] \sin \frac{2 π (n_{1} + n_{2} + n_{3})}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{10} \cos θ_{10} - \sqrt{3} D_{10} \sin θ_{10}) casφ

Wherein

θ_{10} = \frac{2 π (n_{1} + n_{2} + n_{3})}{N};

B_{10} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{10} \cos θ_{10} + \sqrt{3} D_{10} \sin θ_{10}) casφ

12) calculate A ₁₁(k ₁, k ₂, k ₃) and B ₁₁(k ₁, k ₂, k ₃)

A_{11} (k_{1}, k_{2}, k_{3})

= X ({3 k}_{1} + 1 {, 3 k}_{2} + 1, {3 k}_{3} - 1) + X ({3 k}_{1} - 1, {3 k}_{2} - 1, {3 k}_{3} + 1)

= 2 Σ_{n_{1} = 0}^{N - 1} Σ_{n_{2} = 0}^{N - 1} Σ_{n_{3} = 0}^{N - 1} x (n_{1}, n_{2}, n_{3}) \cos \frac{2 π (n_{1} + n_{2} - n_{3})}{N} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} {[{2 a}_{0} - a_{1} - a_{2} {- a}_{3} + 2 a_{4} - a_{5} {- a}_{6} - a_{7} + 2 a_{8} {- a}_{9} {+ 2 a}_{10} - a_{11}

{- a}_{12} - a_{13} + 2 a_{14} + 2 a_{15} {- a}_{16} - a_{17} {- a}_{18} - a_{19} {+ 2 a}_{20}

+ 2 a_{21} {- a}_{22} {- a}_{23} - a_{24} {+ 2 a}_{25} - a_{26}] \cos \frac{2 π (n_{1} + n_{2} - n_{3})}{N}

+ \sqrt{3} [a_{1} - a_{2} - a_{3} + a_{5} + a_{6} - a_{7} - a_{9} + a_{11} + a_{12} - a_{13} + a_{16} - a_{17}

+ a_{18} - a_{19} + a_{22} - a_{23} - a_{24} + a_{26}] \sin \frac{2 π (n_{1} + n_{2} - n_{3})}{N}} casφ

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{11} \cos θ_{11} - \sqrt{3} D_{11} \sin θ_{11}) casφ

Wherein

θ_{11} = \frac{2 π (n_{1} + n_{2} - n_{3})}{N};

B_{11} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{11} \cos θ_{11} + \sqrt{3} D_{11} \sin θ_{11}) casφ

13) calculate A ₁₂(k ₁, k ₂, k ₃) and B ₁₂(k ₁, k ₂, k ₃)

A_{12} (k_{1}, k_{2}, k_{3}) = X ({3 k}_{1} + 1 {, 3 k}_{2} - 1, {3 k}_{3} + 1) + X ({3 k}_{1} - 1, {3 k}_{2} + 1, {3 k}_{3} - 1)

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{12} \cos θ_{12} - \sqrt{3} D_{12} \sin θ_{12}) casφ

Wherein

θ_{12} = \frac{2 π (n_{1} - n_{2} + n_{3})}{N};

B_{12} (\frac{N}{3} - k_{1}, \frac{N}{3} - k_{2}, \frac{N}{3} - k_{3}) = Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{12} \cos θ_{12} + \sqrt{3} D_{12} \sin θ_{12}) casφ

14) calculate A ₁₃(k ₁, k ₂, k ₃) and B ₁₃(k ₁, k ₂, k ₃)

A_{13} (k_{1}, k_{2}, k_{3}) = X ({3 k}_{1} - 1 {, 3 k}_{2} + 1, {3 k}_{3} + 1) + X ({3 k}_{1} + 1, {3 k}_{2} - 1, {3 k}_{3} - 1)

= Σ_{n_{1} = 0}^{N / 3 - 1} Σ_{n_{2} = 0}^{N / 3 - 1} Σ_{n_{3} = 0}^{N / 3 - 1} (S_{13} \cos θ_{13} - \sqrt{3} D_{13} \sin θ_{13}) casφ

Wherein

θ_{13} = \frac{2 π ({- n}_{1} + n_{2} + n_{3})}{N};

Can see N * N * N sequence x (n from above-mentioned ₁, n ₂, n ₃) 3-D DHT changed into 27 length

The DHT conversion of sequence, so continuous decomposition is until the sequence that decomposes 3 * 3 * 3.