{'fraction_non_alphanumeric': 0.035865140926196144, 'fraction_numerical': 0.010214269257353506, 'mean_word_length': 4.489881956155143, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fast cosine transform for FCC lattices

Voxel representation and processing is an important issue in a broad spectrum of applications. E.g., 3D imaging in biomedical engineering applications, video game development and volumetric displays are often based on data representation by voxels. By replacing the standard sampling lattice with a face-centered lattice one can obtain the same sampling density with less sampling points and reduce aliasing error, as well. We introduce an analog of the discrete cosine transform for the facecentered lattice relying on multivariate Chebyshev polynomials. A fast algorithm for this transform is deduced based on algebraic signal processing theory and the rich geometry of the special unitary Lie group of degree four.


I. INTRODUCTION
The approximation of real world objects by voxel data and fast processing of these 3D-samples is of great interest in a broad field of applications. For example, in biomedical engineering one is interested in fast processing of volumetric data in a variety of 3D-imaging procedures, like computed tomography, magnetic resonance imaging and positron emission tomography to name just a few. In computer games engineering there is an ongoing trend to rely graphics on voxels instead of polygons. Another field of voxel processing is volumetric displays requiring a large amount of bandwith for refreshing. Hence, achieving the same sampling density by less data would be highly desirable. Besides faster processing, reducing aliasing errors and jitter noise by alternative data sampling techniques is a motivation for the presented study. A method to achieve this, is to change the sampling lattice from the standard rectangular lattice, also known as cartesian cube (CC) lattice, to either the face-centered cubic (FCC) lattice or the body-centered cubic (BCC) lattice. The FCC lattice is associated to a densest sphere packing, while the BCC lattice is interrelated to a sphere covering [1]. These lattices are in duality to each other, i.e. the frequency data of data sampled on one lattice will sit on the other lattice and vice versa. Both lattices have advantageous sampling properties when compared to the CC lattice, each in its own region of This work is partially supported by the European Regional Development Fund (ERDF) sampling frequency [2], [3]. For example, one could achieve the same sampling density on a FCC lattice compared to a CC lattice with 29 % less sampling points. Recently, tools for interpolation on these lattices were published, e.g. the Voronoi splines [4]. Furthermore, it was shown that human beings recognize the sampled object at least as good as if the data was sampled on a CC lattice [5]. The superiority of sampling on non-standard lattices has been shown in medical applications [6], as well.
Even though there are classical abstract sampling and reconstruction theorems on arbitrary lattices [7] and methodologies for decomposing general lattices into cartesian sublattices for computing Fourier transforms [8], FFTs on FCC and BCC lattices have been elaborated only recently [9]. One big disadvantage of these transforms is that they implicitly assume directed lattices, while 3D images are space-dependent objects, and hence it is more natural to model them on undirected lattices. Using the theory of algebraic signal processing [10] it is easy to realize that 1D undirected lattices are connected to discrete cosine transforms, which are based on Chebyshev polynomials [11], and deduce the corresponding FFT-like algorithms [12]. Relying on this concept, an analog of the discrete cosine transform on the hexagonal lattice, based on two variable Chebyshev polynomials, was derived together with its fast algorithm [13]. Recently, discrete cosine transforms on hexagonal lattices have gained attention as feature generators for artificial neural networks in face detection [14].
The multivariate Chebyshev polynomials [15] are now classical, but have found applications only in the last years. Apart from the applications in algebraic signal processing they are applied in the discretization of partial differential equations in [16], [17], for the derivation of cubature formulas in [18], [19], [20] and developing discrete transforms in [21].
In this paper we are studying the derivation of an analog of the discrete cosine transform on the FCC lattice and the corresponding fast algorithm. Our derivation is based on algebraic signal processing theory, which is recalled in section II, and Chebyshev polynomials of the first kind in three variables, whose construction is shown in section III. The nice properties of the Chebyshev polynomials in three variables are due to the connection to the rich geometry of the Lie group SU(4), which is briefly sketched. We derive the fast algorithm in section IV and apply the transform to an artifical data set in section V.

II. ALGEBRAIC SIGNAL PROCESSING
Algebraic signal processing theory [10] gives a unified notion for the central concepts of linear signal processing. The basic objects in this theory are signal models, which consist of triples (A , M, Φ), where A is the filter space, M the signal space, and Φ : C N → M is a bijective map, called z-transform. Typically, the filter and the signal space are choosen to be equal as polynomials in multiple variables. The multiplication of the polynomials is defined modulo some subset, termed ideal, I of polynomials, i.e. A = M = C[x 1 , . . . , x n ] I. If we choose a Gröbner basis [22] for the ideal this results in multiplication modulo the polynomials in that Gröbner basis. Choosing a basis in M gives rise to the z-transform Φ by mapping each vector entry to a coefficient of the basis elements of M . For example choosing The zeros of z −n −1 are precisely the discrete frequencies ω k n , with ω n being an nth root of unity. If the zeros α i of the ideal I are distinct, we have, by the Chinese remainder theorem, a decomposition of the signal space into one-dimensional subspaces A matrix realizing this decomposition is called Fourier transform of the signal model. In the case of the discrete, finite time signal model this is precisely the discrete Fourier transform.
There are distinguished elements of the filter space which generate the whole space. In the context of the algebraic signal processing theory, they are called shifts. In the example C[z −1 ] z −n −1 the generator would be z −1 . The generators allow for visualization of the signal model by multiplying each basis element with the generators and drawing arrows to the basis elements appearing in the result.

III. PERMUTATIONS AND GENERALIZED CHEBYSHEV POLYNOMIALS
We briefly discuss the construction of multivariate Chebyshev polynomials via permutation groups. The construction yields a basis of the space of multivariate polynomials. This basis has useful properties, which can be exploited to develop FFT-like algorithms. We start by recalling the definition of the classical Chebyshev polynomials of the first kind as for θ ∈ (0, 1) and x = cos(θ). The appearing numbers 1 and −1 can be interpreted as 1 × 1 matrices representing the permutations of two elements. The number 2 is then the number of all such permutations, i.e. we average over all permutations. For a generalization of Chebyshev polynomials in one variable to polynomials in multiple variables, we replace the permutations of two elements by another permutation group and represent it as matrices. Then we multiply these matrices with vectors, exponentiate and average over them.
More formally, let (k, θ) := exp(2πik θ) for k ∈ Z d , θ ∈ R d , and denote by (k, θ) s := 1 |W | w∈W (k, wθ), termed Wsymmetrization or generalized cosine [15], for a permutation group W . The definition of multivariate Chebyshev polynomials is then straightforward: Definition 1 Let W be a permutation group. For each k ∈ Z d define the corresponding multivariate Chebyshev polynomials of the first kind as with x j (θ) := (e j , θ) s being a change of variables for j = 1, . . . , d, here e j ∈ Z d denote the standard basis vectors.
We list some of the properties multivariate Chebyshev polynomials obey.
Proposition 2 For the multivariate Chebyshev polynomials associated to the permutation group W one has i.) T 0 (x 1 , . . . , v.) the multivariate Chebyshev polynomials span the space of multivariate polynomials, vi.) the decomposition property for k, ∈ Z, i.e. the generalized Chebyshev polynomials form a semigroup, vii.) the Chebyshev polynomials T nej , for j = 1, . . . , d, form a Gröbner basis for the ideal they generate.

Remark 3 i.)
There is an intimate connection to differential geometry, as the permutation groups are a special case of so called Weyl groups associated to simple, simplyconnected, compact Lie groups. The construction can indeed be carried out for every Weyl group. ii.) Properties i.) to iv.) of Prop. 2 also hold for any group of integer matrices. iii.) By looking at the definition it is not easy to derive that the multivariate Chebyshev polynomials are actually polynomials. This can be clarified by the recurrence relation using a suitable and sufficient set of starting conditions. iv.) The decomposition property Prop. 2, vi.) is stated in a more intricate form in [15,Sect. 6] for Chebyshev polynomials associated to affine Weyl groups and in [23, Sect. 3] using the algebraic generalization.
We are interested in the permutation group S 4 . This group yields multivariate Chebyshev polynomials giving rise to a signal model on the FCC lattice. There are 24 possiblities to permute 4 elements. These permutations can be represented as 3 × 3 matrices, with generator matrices These matrices satisfy s 2 All other matrices, representing a permutation of 4 letters, can be generated by various multiplications of these three matrices.
Let θ 1 θ 2 θ 3 ∈ R 3 Z 3 . Using coordinates u := e 2πiθ1 , v := e 2πiθ2 , and w := e 2πiθ3 , we obtain the general power form The polynomial form can be obtained via the parametrization Note that x and z are complex conjugates while y is real since u = u −1 , v = v −1 , and w = w −1 . Hence we have a real representation if we use the coordinates x := 1 2 (x + z) and z := 1 2i (x − z). Using the power form we can easily deduce the common zeros of a suitable subset of the generalized Chebyshev polynomials, which we need for the development of a Cooley-Tukey-type-algorithm on the FCC lattice.
The 512 common zeros for n = 8 are displayed in Fig. 1, where we used the real coordinates from above. In case of the symmetric group S 4 the general recurrence relation Prop. 2, iv.) reads This recurrence relation allows to derive the visualization of the signal model.
(b) Convex hull of the shifts, a rhombic dodecahedron.
(c) Space-filling via rhombic dodecahedra on FCC lattice points.
The elements T 1,0,0 , T 0,1,0 , and T 0,0,1 are the shifts of our signal model. If we multiply any element of M by one of these, the element gets shifted into certain directions, as illustrated in Fig. 2a. These resemble the roots of the Lie group SU (4) and generate the FCC lattice. The convex hull of these shifts forms a rhombic dodecahedron, see . This basis change, which has O(n 3 ) entries, will be described in future works. For (23)   get a permutation matrix P n in (25). The fast algorithm is given as the matrix factorization DCT n×n×n (r, s, t) Looking at the matrix representation makes it easy to see that the whole algorithm has cost O(n 3 log(n)). Hence it can compete with the tensor product of standard Cooley-Tukey FFTs or fast Cosine transforms. First numerical experiments verify the effectivity of the proposed methodology compared to the naive O(n 6 ) implementation, as depicted in Fig. 3.

V. APPLICATION TO VOXEL DATA AND FUTURE WORK
One of the main advantages of using the algebraic signal model is that we do not actually have to sample data on the FCC lattice, but can instead use the z-transform to map any data on it. Hence we can compare the effect of the FCC transform directly with the standard approach to discrete cosine transforms on cc lattices.
For graphic representation of voxel data on a rectangular grid, each data point gets assigned to a cuboid and can define certain properties, like color or opacity. Now for the FCC lattice we have to assign the points to rhombic dodecahedra instead, as they fill the space on this lattice. The difference in the graphical representation is shown in Fig 4, where we created an artifical data set portraying a sword. The data values were mapped to opacity values, i.e. data points with value 0 are not visible, while the ones with 1 are fully visible. In Fig. 5a we see the effect of the threefold tensor product of the discrete cosine transform and in Fig. 5b the effect of the FCC Chebyshev transform. Aside from an explicit description of the matrices used in the decomposition steps, we plan to derive Cooley-Tukey-type-algorithms based on generalized Chebyshev polynomials for all simple, compact Lie groups.