2.1. Optimization of 3D Animation Image Structure Based on e K-means Algorithm
With the utilization of 3D animation technology in gaming, VR, and film and television,
the widespread application has led to explosive growth in data volume, posing severe
challenges to storage and transmission efficiency [10]. To effectively reduce the storage space of 3D animation and improve transmission
speed, optimizing the 3DAD structure has become key. To optimize 3D animation images,
the first step is to understand their formation process, as shown in Fig. 1.
Fig. 1. The process of forming 3D animation images.
In Fig. 1, the formation of a 3D animated image is first achieved by determining point positions
to form lines, then creating polyhedra based on the lines, and finally rendering them
to form a complete image. However, the vertex arrangement of traditional 3DAD is disordered,
making it difficult to directly perform clustering compression. The K-means is utilized
in clustering tasks since its simplicity, efficiency, and suitability for large-scale
data processing [11]. However, the traditional K-means has some drawbacks, such as being very sensitive
to the selection of initial clustering centers, which may lead to unstable clustering
results. The number of clusters $K$ needs to be pre-set. Choosing the appropriate
$K$ value is often a challenge and is also sensitive to noise and outliers [12]. To address these shortcomings, this study proposes an e K-means algorithm that reduces
dependence on initial cluster center selection by ensuring that each cluster is of
equal size, thereby improving the stability and reliability. The e K-means algorithm
calculates the number of cluster centers based on the total number of vertices and
the preset sub block size, dynamically adjusts vertex allocation during the iteration
process, and ensures that the number of vertices in each cluster strictly matches
the sub block size, thereby forcing the constraint of equal cluster sizes. In addition,
the e K-means dynamically adjusts the number of clusters during the clustering process,
avoiding the problem of needing to pre-set $K$ values. The framework of the K-means
algorithm is shown in Fig. 2.
Fig. 2. e K-means algorithm structure diagram.
In Fig. 2, the e K-means algorithm is an improved clustering algorithm used for structuring
3DAD. It first randomly selects $K$ initial cluster centers from the vertex data of
the first frame of the 3 animations. The $K$ is calculated based on the gross of vertices
and the size of sub blocks to ensure that the size of each cluster is equal. The initialization
calculation of cluster centers is shown in Eq. (1)
[13].
In Eq. (1), $K$ is the amount of cluster centers. $V$ is the total number of vertices in the
first frame of the 3D animation. $B$ is the size of each sub block. Next, the algorithm
calculates the distance from each vertex to $K$ and assigns the vertices to the clusters
represented by the nearest cluster center, forming $K$ clusters. The distance formula
is shown in Eq. (2)
[14].
In Eq. (2), $d_{ij}$ is the Euclidean distance between vertex $V_i$ and cluster center $C_j$.
$\|\ \|$ is the calculation of Euclidean distance, which is the second norm of a vector.
$V_i$ is the $i$-th vertex. $C_j$ is the $j$-th cluster center. Then, the mean of
all vertices in each cluster is calculated and used as the new cluster center. The
formula for updating cluster centers is shown in Eq. (3)
[15].
In Eq. (3), $C'_j$ is similar to $C_j$. $|S_j|$ is the quantity of vertices in the $j$-th cluster.
$S_j$ denotes the $j$-th cluster. $V_{S_j}$ means the vertex in cluster $S_j$. Convergence
can be determined by calculating $\tilde{E}$, the sum of the distances from all vertices
to the center of their respective clusters. If the value no longer changes significantly
or reaches the preset maximum iterations, the algorithm ends; Otherwise, return to
the clustering allocation step and continue iterating. The convergence judgment calculation
is shown in Eq. (4).
In Eq. (4), $\tilde{E}$ is used to determine whether the algorithm converges. Finally, $K$ clusters
are output. Each cluster contains an equal number of vertices, and the index value
sequence of the cluster is used to reorder the original vertex set, thereby structuring
the unordered vertex data into an ordered matrix form. The e K-means algorithm reduces
the dependence on the initial cluster center selection by constraining the size of
the clusters, improves the stability and reliability of the algorithm, and better
adapts to subsequent compression processing. When using the e K-means for image structure
optimization, the Sub-Block Size (SBS) of 3D animated images will affect the subsequent
compression effect, so it is necessary to choose an appropriate size. The process
of selecting SBS is shown in Fig. 3.
Fig. 3. Optimal sub-block size selection process
In Fig. 3, it is first necessary to determine a set of candidate SBSs based on the characteristics
of 3DAD, such as common ones such as $4 \times 4$, $8 \times 8$, $16 \times 16$, $32
\times 32$, etc. Next, the e K-means algorithm is used to cluster the vertex data
of each frame of the 3D animation, reordering the vertex data and storing it in matrix
form. Then, the vertex matrix of each frame is segmented according to the candidate
SBSs. This study applies compression operations such as Discrete Cosine Transform
(DCT), quantization, and entropy encoding to each candidate SBS, and then reconstructs
it to calculate the reconstruction error. The DCT transform formula is shown in Eq.
(5).
In Eq. (5), $F(u, v)$ is the DCT coefficient matrix at position $(u, v)$. $f(u, v)$ is the pixel
value at position $(u, v)$ in the sub-block. $C(u)$ and $C(v)$ are normalization factors
for DCT coefficients, used to adjust the calculation of DCT transform. $N$ is the
size of the sub block. The quantification formula is shown in Eq. (6).
In Eq. (6), $Q(u, v)$ is the quantized DCT coefficient. $Q'(u, v)$ is the quantized value in
the quantization table. This study enlarges the DCT coefficient matrix by a factor
of $B_{dul}$ based on different images to preserve the floating point data. The reconstruction
error calculation is shown in Eq. (7).
In Eq. (7), $KGError$ is the reconstruction error, usually expressed as a percentage. The smaller
the value, the closer the compressed data is to the original data during reconstruction,
and the better the compression effect. $I$ and $J$ are the number of rows and columns
of data. $f_{\text{original}}(i, j)$ is the value of the original data at position
$(i, j)$. $f_{\text{reconstructed}}(i, j)$ is the value of the compressed and reconstructed
data at position $(i, j)$. Based on the comparison of compression effects under different
SBSs, the size that achieves the best balance between compression ratio and reconstruction
error is selected. The compression ratio formula is shown in Eq. (8).
In Eq. (8), $bpvf$ is the number of Bits Per Vertex per Frame (BPVF) used to measure compression
ratio. $\text{encoded}_{\text{bits}}$ is the total number of bits after encoding.
Finally, the SBS that maximizes the compression rate while ensuring image quality
was selected. This process usually requires multiple iterations and adjustments to
find the optimal SBS, thereby achieving a balance between computational efficiency
and compression effect.
2.2. 3D Animation Image Compression Method Based on DZIP Algorithm
This study utilizes the e K-means to process the structure of 3D animation images,
enabling them to better leverage their advantages in subsequent image compression
and achieve more efficient and stable clustering effects. This study establishes a
SBS selection mechanism based on different images to improve compression performance.
However, as a video, the essence of 3D animation is to capture Mark points through
motion, and then use the information of Mark to transform it into a computer. The
generation process is shown in Fig. 4.
Fig. 4. 3D animation generation process.
In Fig. 4, the generation process of 3D animation mainly relies on the camera capturing the
movements of the captured personnel, constructing corresponding motion models, and
generating real-time dynamic models. Finally, a complete 3D animation was obtained
by rendering based on the dynamic model. Therefore, each frame action in 3D animation
is a separate image and has a certain correlation. The video frames of 3D animation
can be divided into Intra-Coded Frames (ICF), Forward Predicted Frames (PF), and Bidirectional
Interpolated Frames (BPF) [16]. The compression of 3D animation requires the removal of redundant information, and
the process of removing redundant information is shown in Fig. 5.
Fig. 5. Redundant information removal process diagram.
In Fig. 5, the removal of redundant information in 3D animation compression is a multi-step
optimization process. Firstly, the model is simplified through geometric data compression,
reducing the number of vertices and polygons and lowering the accuracy of vertex coordinates.
Next, the animation data is compressed, keyframes are optimized, and interpolation
algorithms are used to generate intermediate frames, reducing the amount of animation
data. Texture data are compressed using image compression algorithms or specialized
texture formats to reduce texture storage space. Subsequently, spatial and temporal
correlations are utilized to remove redundant information in space and time through
prediction and differential encoding. Finally, entropy encoding is used to further
compress the data, ensuring maximum reduction of data volume while maintaining visual
effects, thereby achieving efficient 3D animation compression. The ZIP algorithm,
as a conventional compression algorithm, is commonly used for video and image compression,
but the compression effect is poor. To further compress 3D animation images, this
study proposes a DZIP algorithm, combined with Locally Linear Embedding (LLE) algorithm,
and employs both lossless and lossy compression methods for dual optimization. LLE
is suitable for processing non-linear structures of high-dimensional data in 3D animation
images, and can effectively reduce dimensionality while preserving local geometric
features such as topological relationships between vertices and texture details, providing
low dimensional and complete basic data for subsequent compression processing. The
image data processing flow of DZIP algorithm is shown in Fig. 6.
Fig. 6. DZIP algorithm compression 3D animation process.
In Fig. 6, the optimization process of DZIP algorithm starts from 3DAD input, and first uses
the e K-means algorithm to structurally process the vertex data of each frame. Next,
the LLE algorithm is used to reduce the dimensionality of each frame and extract 2D
features. In the dimensionality reduction process of LLE algorithm, the Singular Value
Decomposition (SVD) of the neighborhood matrix is first calculated. The formula for
SVD is shown in Eq. (9).
In Eq. (9), $\tilde{A}$ is the neighborhood matrix. $\tilde{U}$ and $\tilde{V}$ are SVD matrices.
$\Sigma$ is a SVD matrix. In the LLE algorithm, it is necessary to select singular
values that make the residual error less than a threshold to determine the dimensionality
reduction feature dimension, as shown in Eq. (10).
In Eq. (10), $\sigma_k$ is the residual error of the singular value matrix, and $\epsilon$ is
a threshold. Subsequently, linear regression is used to map high-dimensional data
to a low-dimensional space. The original data are $X^*$, which can be expressed as
Eq. (11).
In Eq. (11), $W$ denotes the weight matrix. $\Phi(X^*)$ means the feature vector of the original
data. $b^*$ is the bias vector. The corresponding minimization error function is shown
in Eq. (12).
In Eq. (12), $E_{W^*}$ is the minimization error function of the weight matrix. The linear relationship
between data points in the neighborhood is shown in Eq. (13).
In Eq. (13), $x_i$ is the $i$-th data point. $W_i$ is the corresponding weight matrix. $z_i$
is a low dimensional vector. $b_i$ is the corresponding bias term. The dimensionality
reduction of high-dimensional data also requires calculating the reconstruction error
of high-dimensional data as shown in Eq. (14).
In Eq. (14), $E_g$ is the reconstruction error of high-dimensional data. $\tilde{x}_i$ is a high-dimensional
data point reconstructed from a low dimensional vector $z_i$. The update of dimensionality
reduction linear coefficients adopts gradient descent method, as shown in Eq. (15).
In Eq. (15), $w_{ij}$ is the dimensionality reduction linear coefficient. $k_{ij}$ is the similarity
between data points, which can be calculated based on the distance relationship between
data points. For ICF and PF, this study uses the Deflate algorithm for lossless compression,
combined with Lempel-Ziv-77 dictionary encoding and Huffman encoding, to ensure high-precision
restoration of these keyframe data. This study uses DCT transform for lossy compression
of BPF, including DCT, quantization, and Huffman coding, to reduce data volume and
improve compression ratio. Finally, the compressed data is stored as the final compressed
file. This optimization process fully utilizes the high fidelity processing of keyframes
by lossless compression and the efficient compression of a large number of BPF frames
by lossy compression, thereby significantly reducing file size while ensuring the
quality of 3D animation.