# Fast Adaptive Character Animation Synthesis Based on Greedy Algorithm

Authors: Yanqiu Zhu; Qixing Chen; Jing Liu; Xiaoying Tian
Journal: Complexity
 (2021)

---

## Abstract

On the premise of ensuring the animation effect and real-time performance, it is of great significance and value for large-scale group character animation synthesis how to reduce the disaster coincidence degree among various models of fast adaptive character animation synthesis. The realization method of object-oriented finite state machine is studied in detail. Finite state machine (FSM) is an efficient behavior modeling method, which can describe the behavioral decisions of fast adaptive character animation synthesis in a complex virtual environment. Based on the implementation defects of the finite state machine in the traditional structure, using object-oriented thinking, combined with the state design mode, we further studied a finite state machine implementation method based on object-oriented technology. This achieves code reuse and simple program maintenance. The effect is extensible and effectively overcomes the shortcomings of traditional character animation synthesis. Secondly, the multipath matching tracking algorithm of the greedy algorithm is studied to generate multiple candidate sets through multiple paths, and finally, the candidate set with the minimum residual error is selected as the estimated support set, so as to improve the reconstruction performance. Further, based on the idea of multipath, using the regularization method of the ROMP algorithm, the regularized multipath matching tracking RMSP algorithm is proposed. It uses the regularized subset method to generate multiple paths and chooses the path with the fastest residual reduction as the support set of this iteration. The simulation results show that the RMSP algorithm has better reconstruction performance than the SP algorithm.


---

## Body

## 1. Introduction

Group character animation synthesis has always been a technical problem in computer character animation synthesis. The artificial life method of computer animation overcomes the defects of traditional character animation synthesis technology and improves the efficiency of group character animation synthesis. However, as the character animation synthesis model-making technology used in this method is becoming more and more complex, the disaster coincidence degree among the models of the animation system is also increasing, which makes the character animation synthesis more and more difficult. In particular, when the number of intelligent characters increases, the computational complexity will increase rapidly, which greatly affects the real-time performance of character animation synthesis and limits the wide application of this method. The above problems are studied in depth. Without reducing animation and real-time capabilities, we need to reduce the degree of damage between animation models, reduce computer calculations, and improve the efficiency of character animation synthesis. Based on the two-layer decomposition of independent character animation synthesis and animation, a comprehensive model of group character animation is designed, and the specific realization technology of the model has been studied and realized in depth.On the basis of the “artificial fish” animation framework, computer vision, machine learning [1, 2], cognitive model [3, 4], and other aspects have been widely carried out, and it has taken the lead in the world. Among them, computer vision research mainly uses computer graphics knowledge to establish a “comprehensive visual model” for character animation synthesis to improve the perceptual performance of character animation synthesis when the number of characters in group animation increases and/or when the living environment of character animation synthesis is complex and changeable [5]. The research on machine learning and cognitive model is mainly used to improve the intelligence of character animation synthesis, especially the intelligence of higher organisms, so as to realize the simulation of high-level character animation synthesis [6]. At present, the research on the artificial life method of computer animation combined with the multirole animation synthesis system (MAS) and complex adaptive system (CAS) has become the feature and hotspot of computer animation research and creation. Classic greedy reconstruction algorithms include MP algorithm, OMP algorithm, piecewise orthogonal matching tracking algorithm [7], ROMP algorithm [8], compressed sampling matching tracking algorithm [9], subspace tracking algorithm [10], and sparsity adaptive matching tracking algorithm [11]. In addition to the greedy algorithm, there are also a lot of improved algorithms. In literature [12], a multipath subspace tracking algorithm is proposed, which improves the SP algorithm by using the idea of the MMP algorithm. The MSP algorithm has two different threshold choices in the atomic selection stage. The multipath strategy is used to improve the reconstruction of the algorithm. In literature [13], an improved adaptive matching tracking algorithm is proposed. By using the excess criterion of sparsity estimation, the range of sparsity is estimated first, and then, the estimated sparsity is corrected, which speeds up the execution speed of the algorithm and is an improvement of the SAMP algorithm. Literature [14] proposed an improved algorithm, which improved the reconstruction performance of the algorithm by modifying the number of iterations. Literature [15] proposed a regularized adaptive matching tracking algorithm, which combines the characteristics of the SAMP algorithm and ROMP algorithm to improve the reconstruction performance of the algorithm. In literature [16], the SP algorithm is embedded in the OMP algorithm. In each iteration of the OMP algorithm, SP algorithm is used to optimize the estimated support set of the OMP algorithm, which improves the reconstruction accuracy of the algorithm. In literature [17], a forward orthogonal matching pursuit algorithm is proposed, which is the improvement of the OMP algorithm; in each iteration, the LAOMP algorithm selects L atoms and then puts all the atoms into the estimated support set; we choose the smallest residual as the cycle of the currently selected atoms, and the LAOMP algorithm can greatly improve the accuracy of the support set. Literature [18] combined the ROMP algorithm and genetic algorithm to improve the image reconstruction performance of the algorithm. In literature studies [19, 20], Monte Carlo matching tracking algorithm was proposed. The recursive Bayesian process was used to obtain the denoising estimation of signals, and the sparse degree of weakly matched constrained signals was used to reconstruct signals under the condition of unknown sparsity and noise pollution. The core of the automatic generation scheme of bipedal character animation is to create a real-time data-driven character animation synthesis generation model, which enables the character animation synthesis to control the generation of character animation through natural, fluent, and diversified character animation synthesis after making behavioral decisions autonomously [21]. Gaussian process implicit variable model [22] is applied to calculate the low-dimensional potential space of data to help solve the redundancy problem of reverse dynamics [1]. The model based on the kernel method [23] is affected by the high memory cost of processing the covariance matrix. A local GP method to limit the number of interpolating samples is proposed to overcome this problem, but the K-nearest neighbor search algorithm [24] is needed. This algorithm requires high memory requirements in both predictive computation and runtime when processing high-dimensional data such as human character animation data. In order to generate the character animation synthesis that adapts to the environment geometry in real time in the character animation, a phase function neural network [25, 26] is proposed, which can map the control information of the game controller as input to the character animation synthesis. The model uses a phase function to generate variables representing the period of the character animation as the weight of the regression network for each frame [27]. Once generated, these weights will be used in the neural network to generate the role posture of the current frame matching the control parameters in real time [28–30]. In addition, the PFNN also solves the drift problem by performing IK posttreatment on the feet.The fast adaptive character animation synthesis of the multipath greedy reconstruction algorithm is studied. Firstly, the MMP algorithm is introduced in detail, then the MMP algorithm is analyzed, and the RIP condition of the MMP algorithm is given for the correct reconstruction of the signal support set under noisy and noiseless conditions. The reconstruction performance of the MMP algorithm under noisy and noiseless conditions is simulated and analyzed. On this basis, the regularized multipath subspace tracking algorithm is proposed, and the SP algorithm is improved by using the idea of MMP algorithm and ROMP algorithm regularization. This paper proposes a greedy algorithm-based automatic character animation generation solution for the character animation synthesis and describes the network model structure in this solution and how to use this model to generate the character animation synthesis rapidly adaptive to the character animation synthesis, including the processing of training samples and the training of the model. This paper deals with the defects of the finite state machine (FSM) based on the structural method in implementing the role behavior decision model. When describing the behavioral decisions of swarm intelligence roles with changeable states, complex external stimuli, and frequent state transitions, there are great defects in the implementation, which increase the difficulty of implementation. Studying and solving the above defects are beneficial to reduce the difficulty in animation implementation, realize code reuse, and improve the efficiency of implementation.


## 2. Automatic Generation Scheme for Fast Adaptive Character Animation Synthesis

Aiming at the defects of the character animation synthesis model similar to “artificial fish,” such as difficulty in establishment and control, complex constraint relation, huge computation, and limited real-time performance of animation, a new group character animation synthesis model was designed, which is a two-layer decomposition group character animation synthesis model based on autonomous character animation synthesis. From another point of view, the character animation of an intelligent character can be decomposed into two relatively independent character animations in the world coordinate system and in the local coordinate system, in which the intelligent character is regarded as a particle in the world coordinate system, and the speed and direction of the character animation are specified for this particle. The character animation in the local coordinate system specifically analyzes the character animation of different parts of the body in the local coordinate system of the intelligent character. At any moment, the character animation of the intelligent character is the synthesis of the character animation of the intelligent character in the world coordinate system and the character animation of the intelligent character in the local coordinate system. According to this idea, a two-layer decomposition group character animation synthesis model based on autonomous character animation synthesis was designed (see Figure1).Figure 1
Flowchart of the autonomous character animation synthesis system.It can be seen from Figure1 that the two-layer decomposition group character rapid adaptive animation synthesis model based on autonomous character animation synthesis can be divided into three models: perception model, behavior decision model, and character animation model, which correspond to the perception system, behavior control system, and character animation system that realize the individual role of animation, respectively. Among them, the behavior decision model is divided into two submodels: motivation model and behavioral decision model. The body character animation model also includes two submodels: the whole character animation model and the animation model.First, the original animation uses a data segmentation algorithm, and the key frame extraction algorithm uses character animation data editing technology to preprocess the data, and then, according to the semantic characteristics of semantic annotation, the same semantic character animation quickly adapts to the character animation data structure, and the relationship between the database according to the national construction character animation and the design of the database structure is optimized with character animation, and it can provide interface for the expression of user demand not only according to the needs of users in the database to perform role animation query, role animation connection, role animation smooth, and other role animation editing operations but also according to the needs of users to meet the requirements of the role animation sequence.In the process of character animation synthesis, the corresponding character animation segment is selected from the character animation library according to the semantics. If the end frame of a certain state is similar to the start frame parameter of another state, a connection relationship can be established between the animation states of these two characters, or an artificial connection relationship can be established. The design of the finite behavior state machine requires the character animation database with semantic annotation, which is constructed with randomness, and the diversity of the generated character animation behavior also depends on the design automaton. By building a finite behavior state machine, the character animation of a virtual person in a virtual environment can be generated under the target drive and can be applied to different roles and a variety of complex environments. When a new type of character animation captures data, manually and semantically annotate the data for the new type of character animation as a new state node and then add a new state node for the automaton to be applied.Given a fast adaptive character animation path curvet(u) and a velocity function m(t), the task of velocity interpolation is to calculate the fast adaptive root joint interpolation position in each frame period. Let n be the arc length of the curve. According to the definition, the derivative of arc length with respect to parameter U can be obtained:(1)dndu=dxdu+dydu2+dzdu2.All the joints used when capturing animation data are Euler angles to represent the joint rotation, and due to the direct interpolation algorithm, the use of Euler angles will appear unrealistic. Therefore, we first convert the quaternion of Euler angles, then proceed linear interpolation, and finally convert Euler angle:(2)st=sinθsints1+sin1−θsin1−ts2.Based on the finite behavior state machine, the search tree is established by the global search algorithm, and the search path is generated in real time according to the two-dimensional grid map. The construction process of the tree is the search and search process of the character animation synthesis state, which is subject to the constantly changing environment constraints. The global search algorithm adopts the algorithm to establish two related data structures: search tree and state cost queue. In the global search algorithm, the steps to select the best advantage include the lowest cost node in the queue, the end node, and all the state nodes that can be connected after the Sbest node, as shown in Figure2. The character animation synthesis uses motion capture data to create a directed graph, which is composed of the original motion segments and the transitions between motion segments and can represent the relationship between motion segments. After the character animation composition is established, the new movement can be generated by traversing the graph. The traversing process is the process of combining the motion fragments.Figure 2
Fast adaptive character animation synthesis process for the finite behavior state machine.


## 3. Research on Fast Adaptive Character Animation Synthesis Based on the Greedy Algorithm

In the practical process of solving the problem, the multipath greedy algorithm has several key points as follows: the first is to set the initial conditions. Usually, the initial conditions are generated according to the problem to be solved, but the optimal initial conditions can be made in conjunction with the local optimal solution method to the extent allowed. The second is how to solve the problem of local optimization. The optimization problem is generally solved by proposing an optimization function. The quality of the optimization function directly determines the quality of the whole greedy algorithm, which is the most critical link of the greedy algorithm. The third point is to judge the end conditions. The so-called end condition includes two parts. One is the end condition of the global greedy algorithm, which should be determined according to the accuracy requirement of the problem. The other is the constraint condition for optimal selection at each local stage, which determines whether the optimal solution has been obtained for the optimization function. Therefore, it determines the overall complexity of the algorithm to some extent. To sum up, the basic idea of the greedy algorithm to solve problems can be summarized as follows:(1)
Determine the end condition of the algorithm according to the problem target(2)
Analyze the constraint conditions for obtaining the local optimal solution of the problem(3)
According to the constraints of the optimal solution and the understanding of the overall problem, determine the optimization function(4)
According to the algorithm end conditions determined by the three steps above, the constraint conditions of the optimal solution, and the optimization function, formulate the greed criterion so that each link can be connected to determine the optimal solution to the greatest extentIn the actual problem-solving process, the specific solving steps of the multipath greedy algorithm can be summarized as follows:Step 1: set up the initial solution to the problemStep 2: follow the greedy strategy loopt and search for the next target until the exit loop is satisfiedStep 3: calculate a solution elements in the feasible solutionStep 4: recombine all the resulting solution elements to become a final feasible solution to the problemIn the process of the multipath greedy algorithm, the smallest element is added to the existing merge scheme. In order to ensure the operation speed of the algorithm, after adding a new minimum unit each time, onlyK merging schemes with the maximum current value are kept. When the maximum value is in parallel, the remaining schemes are randomly selected. The algorithm runs until the minimum unit merge is complete. Taking K = 2 as an example, this paper shows how the greedy algorithm adds the smallest unit to the existing merge scheme. The algorithm is shown in Algorithm 1, and the algorithm flowchart is shown in Figure 3.Algorithm 1: Reconstruction of the multipath greedy algorithm.
Input: minimum cellT and maximum number of reserved schemes LOutput: regionR after integration(1)
ti⟶T(2)
for eachti do(3)
for eachsi⟶S do(4)
si∪ti⟶S′(5)
for eachs(6)
si+ti(7)
S′∪si∪tiend for(8)
for eachti do(9)
S′∪si∪ti⟶fitend forThe biggestK solutions of fitend forThe biggest solution of fitreturnRFigure 3
Multipath greedy algorithm reconstruction of the character animation synthesis flowchart.The core of the biped character animation automatic generation scheme is to create real-time character animation synthesis based on a data-driven model. This enables character animation synthesis to control the formation of character animation through natural, smooth, and diverse character animation synthesis. The difference lies in that the character animation synthesis of the fast adaptive character is more complex, so the fast adaptive animation is more difficult. In general, animators must be specially trained to create complex character animation compositions for fast adaptive characters.The MANN-based character animation synthesis and generation scheme mainly includes two parts:(1)
Model training: using a large number of character animation synthesis capture data for model training, the character animation synthesis generation model was obtained(2)
Composition and generation of character animations: using the trained character animation synthesis model, the character animation trend control synthesis obtains the behavior control module behavior modeling character animation synthesis (the user controls when replacing the training model), and the character animation synthesis is generated to obtain the character animation synthesis generation model inputThe MANN framework is divided into three stages: pretreatment stage, training stage, and operation stage. In the preprocessing stage, training data are first prepared, including the gait category label of the character animation synthesis data. In the training phase, the MANN is trained with these data in order to generate character animation synthesis in each frame with given control parameters. During the operational phase, MANN’s input parameters are collected from the character animation synthesis and environment and input into the system to determine the character animation synthesis.MANN's input/output and corresponding features to be extracted are described. Input for each frame includes the following: the position, direction, and speed of the trajectory, the character's gait category, and the position, speed, and rotation angle of the previous state node. Similarly, the output includes the predicted trajectory position, direction, and velocity, the position angle and velocity of the joints in the current state, the transformation of the root node, and the velocity of the previous frame. In order to avoid the quaternion interpolation problem of the neural network during training, the rotation of the joint is represented by the rotation of the relative forward and upward vectors. These are taken from the original quaternions in the character animation synthesis capture and converted back at run time to generate the character animation synthesis.The input is divided into two parts:(1)
The synthesis state of the role animation in the previous frame is represented by the position, rotation, and velocity of the joint node. After obtaining the global features, it is projected to the ground, and the rotation is aligned with the forward vector of the role.(2)
In the control part, frame I is used as the center of the time window to check everyt frame around. For example, t = 12 is used to sample the surrounding frames, covering the character animation synthesis of 1 second before and 1 second after. A series of features were extracted from each sampled frame fragment data, including label variables for the position, orientation, speed, and gait of the character in frame I.The output is divided into two parts:(1)
The synthesis state of the role animation of the current frame is represented by the position of the joint node relative to the root node, the speed and rotation, the displacement of the root node, and the angular velocity projected by the root node to the ground(2)
Prediction of the position, direction, and speed of the synthetic trajectory of character animation in the next frameThe description of network hyperparameters is shown in Table1.Table 1
MANN network hyperparameters.
Parameter nameParameter selectionLearning rate0.0002Batch size34Epoch155Dropout0.9Weight decay rate0.0028Number of expert networksK3.5After the training, the parameters of the gating network and character animation synthesis prediction network were saved as the final model parameters. During the operation, neural network inputX must be provided for each frame, and variables related to joint position and speed are used as input for the next frame by means of autoregression with the calculated results of the previous frame. Input X also includes past/future trajectories.The future trajectory is predicted. When preparing MANN’s operation inputX, the character animation synthesis gait label is obtained through the character animation synthesis control parameters of the character animation synthesis, enabling the required character animation synthesis, including sitting, standing, idle, lying flat, jumping, and moving, and obtaining the speed and direction of the character. The target velocity and direction are interpolated smoothly and are ultimately used to predict future trajectories. The trajectory curve is inferred using an exponential weighted bias value, which defines the maximum length of the future trajectory to provide the required velocity of the role in m/s and to produce a smooth trajectory. This constitutes all of MANN’s input variables, at which point the output Y can be calculated.The character animation synthesis obtains the terrain height information through the perception system and passes it as a parameter to the character animation synthesis generation system. The obtained character animation synthesis can better adapt to the terrain, make varied character animation synthesis, and increase the diversity and sense of nature of the character animation synthesis.


## 4. Example Verification

The reconstruction performance of the MMP algorithm is analyzed by MATLAB simulation and compared with the OMP algorithm and SP algorithm. In the case of no noise, the probability of successful reconstruction of these algorithms is compared, and in the case of noise, their reconstruction errors are compared.Set the signal lengthN = 256, the size of the measurement matrix is 128 × 256, the sparsity K selects different values between 10 and 70, and the step length is 5. For each fixed sparsity, 500 independent experiments were carried out with the reconstruction probability varying with the sparsity. The change of K with successful reconstruction is shown in Figure 4, where Figure 4(a) is the reconstruction result of Gaussian signal and Figure 4(b) is the reconstruction result of 0-1 signal. As can be seen from Figure 4, for the reconstruction of Gaussian signal and 0-1 signal, the reconstruction performance of the MMP algorithm is between the OMP algorithm and SP algorithm.Figure 4
.Variation of reconstruction probability of different greedy reconstruction algorithms with sparsityK. (a) Gaussian signal. (b) 0-1 signal.
(a)(b)Set the signal lengthN = 256 and the signal sparsity K = 30, and select different measurement number M between 60 and 160 with a step length of 5. Conduct 500 independent experiments for each fixed measurement number, and the reconstruction results are shown in Figure 5, where Figure 5(a) is the reconstruction of the Gaussian signal and Figure 5(b) is the reconstruction of 0-1 signal.Figure 5
Variation of reconstruction probability of different greedy reconstruction algorithms with measured numberM. (a) Gaussian signal. (b) 0-1 signal.
(a)(b)As can be seen from Figure5, the OMP algorithm has the worst reconstruction effect for Gaussian signal reconstruction, the MMP algorithm and SP algorithm have better reconstruction effect, and when the number of measurements is small, the MMP algorithm is better than the SP algorithm; when the number of measurements is large, the SP algorithm is better than the MMP algorithm. For 0-1 signal reconstruction, the reconstruction performance of the MMP algorithm is between the OMP algorithm and SP algorithm.As can be seen from Figure6, in the case of noise, the MMP algorithm has the best reconstruction effect for Gaussian signal reconstruction, while for 0-1 signal reconstruction, the MMP algorithm has the middle reconstruction effect.Figure 6
.Variation of reconstruction errors of different greedy reconstruction algorithms with sparsityK. (a) Gaussian signal. (b) 0-1 signal.
(a)(b)MATLAB was used to simulate the greedy algorithm’s fast adaptive character animation synthesis algorithm. Figure7 shows the simulation results of placing the greedy algorithm under unlimited and limited conditions. It can be observed from Figure 7 that the bar chart represents the energy consumption under the unlimited condition and the limited condition. It can be seen from the figure that the energy consumption under the restricted condition is not greater than that under the unlimited condition.Figure 7
Energy consumption of greedy algorithm’s fast adaptive character animation synthesis.As can be seen from Figure8, when the maximum number of schemes retained by the greedy algorithm is fixed, with the increase of the minimum number of units 1, the running time of the minimum unit combination can be approximated to polynomial time. When K = 7, the operation time is around 3 s.Figure 8
Greedy algorithm’s fast adaptive character animation synthesis time. (a) Greedy algorithm time. (b) Animation composition time consumed.
(a)(b)It can be seen from the score that the method in this paper has higher score than the regular deformation method in terms of exaggeration and artistry, which shows that the greedy algorithm is effective in discovering character animation, and the exaggeration of features is also in line with people's observation purpose of character animation synthesis. The comparison results are shown in Table2.Table 2
Comparison table of result evaluation scores.
MethodRole 1Role 2Role 3Greedy algorithmRules of lawGreedy algorithmRules of lawGreedy algorithmRules of lawSimilarity3.543.773.354.03.233.65Exaggeration3.853.623.773.694.123.46Artistry3.543.384.083.53.733.54Evenly split3.643.593.733.733.693.66


## 5. Conclusion

The multipath greedy algorithm is studied, and the performance of the MMP algorithm in noisy and noise-free character animation synthesis and reconstruction is theoretically analyzed. The RIP condition obtained is better than the existing algorithm. The RMSP algorithm is further improved, and the RMSP algorithm is proposed. This algorithm uses the feature of the MMP algorithm multipath and ROMP algorithm regularization for reference and selects the path with the minimum residual error to estimate the support set. The simulation results show that the RMSP algorithm has a good performance of rapid adaptive character animation synthesis and reconstruction. An object-oriented finite state machine implementation method is studied in detail. Finite state machine (FSM) is an efficient behavior modeling method, which can effectively depict the behavioral decisions of organisms in a complex virtual living environment. For large fast adaptive character animation synthesis, traditional finite state machine implementation based on the structured method of multifarious, code reuse, hard maintenance, and expandability of issue, using object-oriented technology, combining with the state design pattern, further study of a kind of method is realized by using the finite state machine of object-oriented technology, effectively solving the defects of traditional fast adaptive character animation synthesis.



---

*Source: 6685861-2021-02-08.xml*