Unbalancing Binary Trees

Assuming Zipf's Law to be accurate, we show that existing techniques for partially optimizing binary trees produce results that are approximately 10% worse than true optimal. We present a new approximate optimization technique that runs in O(n log n) time and produces trees approximately 1% worse than optimal. The running time is comparable to that of the Garsia-Wachs algorithm but the technique can be applied to the more useful case where the node being searched for is expected to be contained in the tree as opposed to outside of it.

Introduction
Binary trees are often used to store and index large amounts of data. Many such trees are balanced in the sense that the left and right children of any particular parent are similar in size. A consequence of this is that every node can be reached in at most log 2 (n) steps from the root of the tree, where n is the tree's size.
While a bound on worst case performance is obviously desirable, a bound on average-case performance may be more important in an environment where large trees are searched often. Note that in cases where searches are frequent indeed, statistical information gathered from past searches can be used to determine the probability p(x) that a particular node x in the tree is the target of a randomly selected query. If we denote the depth of a node x by d(x), the problem of optimizing for average-case performance becomes that of finding a tree structure T for which the cost is minimized, where T is the set of all nodes in some particular tree and c(T ) is the expected cost of a single lookup in the tree.
A variety of authors have considered this problem, and two approaches have historically been taken. Some researchers have focused on finding a globally optimal tree, while others have focused on methods that construct approximately optimal trees. As one might expect, the complexity of the approximate methods is lower than their exact counterparts. Knuth [10] provides a reasonable summary with focus on the construction of globally optimal trees, while Nagaraj [14] provides a somewhat broader description.
Finding a globally optimal tree in general takes time O(n 2 ), prohibitive given the size of modern search trees. There are two possible improvements: 1. Karpinski et.al. [8] have developed an O(n 1.6 ) algorithm if there is a fixed lower bound on the relative probability of any particular node in the sense that there is some fixed δ such that if {v 1 , . . . , v n } is an ordering of the values in the tree, then the probability that a query is between v i−1 and v i+1 is always at least δ/n. This assumption of relative uniformity among the weights of the nodes is unlikely to be valid in practice because of Zipf's law [18,and Section 2] and the fact that the harmonic sequence n i=1 1 i diverges. In any event, n 1.6 is itself unlikely to be viable for large trees. 2. Garsia and Wachs [6] and many successors [7,9,13, and others] have considered O(n log n) algorithms in the special case where it is known that the element v being searched for is not in fact in the tree in question, and the goal is therefore to find two consecutive existing values It is perhaps not surprising that the complexity is lower in this case, since the placement of the internal nodes is less important if the search must proceed to the fringe of the tree in any case. Once again, however, this work is of limited practical use in a setting where (for example) one is trying to make Internet search more efficient -after all, when is the last time you did a Google search and got no results?
A wide variety of authors have also considered fast (generally O(n log n)) methods for constructing nearly optimal binary trees. The three most popular ideas appear to be the following: 1. Splay trees were introduced by Sleater and Tarjan [17]. The tree is initially constructed randomly, but every query moves its target to the top of the tree, hopefully causing frequent queries to have small depths. Splay trees are intended to be adjusted online as queries are received, as opposed to depending on a knowledge of relative probabilities in advance. 2. Treaps were developed by Aragon and Seidel [2,16] although the method is hinted at earlier by Mehlhorn [12]. In this approach, the binary tree is constructed by inserting points in probability order. Although the average case complexity is within a constant factor of optimal, Mehlhorn points out that in the worst case, the tree produced may be quite far from optimal.
Mehlhorn argues that the method should be discarded for that reason. 3. Weight-balanced binary trees also appear in Mehlhorn's work [12]. In the construction of the tree or any subtree, the node at the root is the one that most evenly divides the aggregated probabilities of the residual nodes between the left and right subtrees.
If H is the entropy of the frequency distribution of the nodes in the tree, Mehlhorn shows that the cost C of the tree constructed in this fashion is bounded below by H/log 3 ≈ 0.63H and above by and that these bounds apply to the optimal tree as well. For H ≥ 14.5, the lower bound was subsequently improved by De Prisco and De Santis [15] to For treaps and weight-balanced trees, it can be shown that the average case performance of the data structure in question is within some constant factor of optimal. (Indeed, for weight-balanced trees, the cost is within a constant factor of optimal in every case.) This is suspected to be the case for splay trees as well, but this "dynamic optimality conjecture" has not been proven. The best result of this general type appears to be due to Lecomte and Weinstein [11], who show that Tango Trees [5] are within a factor of O(log(log(n))) of optimal.
In today's world, however, where significant computing resources are devoted to finding objects on the Internet, even a pure constant factor is arguably not good enough. All of the above methods (except Tango Trees) were developed in an environment where it was assumed that tree searches would be approximately as common as insertions. 1 Such an assumption is obviously no longer valid today; I (thankfully!) search the Internet far more frequently than I modify it in a publicly accessible way.
Our goal in this paper is to describe a technique that unbalances binary trees in a way that improves their average-case performance. The technique that we will present can run in time O(n), although performance will be better as run time is permitted to increase, and is guaranteed to improve the expected performance of the tree being optimized.
We discuss our basic experimental framework and the baseline corresponding to existing techniques in the next section, and our new ideas are introduced in Section 3. Experimental results are presented in Section 4, and suggestions for future work appear in Section 5.

Baseline
We will work with randomly generated binary trees of 100 to 10 7 nodes. In each case, we follow Knuth [10] and assign weights to the nodes using Zipf's Law [18], so that the n th most popular node has relative probability 1/n. A variety of other authors have concluded both through observation [3, 4, and others] and theory [1, and others] that Zipf's Law reasonably approximates the relative number of accesses to any particular web site, and therefore presumably the number of searches for a particular word or phrase on the Internet as well. 2 For each size of tree investigated, we consider five basic types of trees: simple binary trees, treaps, weight-balanced trees, splay trees, and trees that are provably optimal given the underlying weight distribution. For splay trees, we generate random but appropriately distributed queries and repeatedly move the node being searched for to the root of the tree. The number of queries generated is 3n, where n is the size of the tree.
Optimal orderings were only computed for trees of 50,000 nodes or fewer. Both the time and (more importantly) the memory needed by the best known algorithm here [10] are O(n 2 ) where n is the number of nodes in the tree, and n > 50000 was simply too large to be practical on the machine being used (a 32-core AMD Ryzen with 128GB of memory).
All experiments used 500 samples for each size considered, and the basic results appear in Figure 1. Tree size is on the x-axis using a log scale, and the average number of node expansions during a single (assumed to be successful) search is on the y-axis.
The curves in the legend are ordered from worst to best; simple binary trees perform the worst (not surprisingly), followed by splay trees, followed by treaps, and weight-balanced binary trees perform the best. Expected cost is essentially linear in the log of the size of the search tree, as one might expect.

Technique
We now turn to our new idea, which is simply to hill climb using rotations to improve the expected cost of the tree.
Definition 1 Let T be a tree. T will be called weighted if there is a function p : T → IR that assigns a weight to each node in T and for which x∈T p(x) = 1.
If x ∈ T is not the root of T , we will denote the parent of x by π(x). We will use ∅ as a placeholder for a node that is not in T . So, for example, we take π(x) to be ∅ if x is the root of the tree. If T is binary and x ∈ T , we denote the left child of x by l(x) and the right child of x by r(x). Thus x is a fringe node if l(x) = r(x) = ∅. We denote the sibling of x by σ(x).
For a node x ∈ T , we will define the depth of x, to be denoted by d(x), to be d(∅) = 0 and d(x) = 1 + d(π(x)) otherwise.
Given a weighted tree T , the cost of T , to be denoted c(T ), will be defined to be One additional property that will be of interest to us is a node that is either the left child of the left child of its grandparent, or the right child of the right child of its grandparent.
Definition 2 Let T be a binary tree, and x ∈ T not the root node. We will define the like-minded child of x, to be denoted by λ(x), to be: Many algorithms manipulate binary trees via what are known as rotations. As an example, if T is of the form shown in Figure 2, where each of c, d and e may be the roots of further subtrees, the result of operating on T with a right rotation is the new tree shown in Figure 3. Note that the new tree retains the ordering of the original (presumably c < b < d < a < e), and that c, d and e remain apparent fringe nodes in the new tree so that if they are in fact the roots of subtrees, those subtrees can remain attached as previously. The rotation here is generally referred to as the right rotation rooted at a, where a is the root of the subtree being rotated.
Similarly, we will say that a left rotation at b produces Figure 2 from Figure 3.
Definition 3 Let T be a tree, and let x ∈ T be a non-root node. By the result of bumping x in T , to be denoted by T x , we will mean the result of right rotating T at π(x) if x is the left child of π(x), and the result of left rotating T at π(x) if x is the right child of π(x). If r is the root of T , we will take T r to be T itself.
Thus Figure 3 shows the result of bumping b in Figure 2, and Figure 2 is the result of bumping a in Figure 3.
Recall that we are assuming that for any particular node x ∈ T , the weight p(x) is the probability that x is the target of a randomly selected search query. The essential point underlying our ideas is that the impact of bumping x ∈ T can be computed exactly based purely on values of a handful of nodes surrounding x.
Definition 4 For a node x in a tree T , we will denote by x the subtree of T rooted at x. We will denote by p(x) the aggregated weight of the points in x: We take ∅ = ∅ (the empty set), and thus p(∅) = 0.
Proposition 5 Let T be a weighted binary tree, and x a non-root node in T . Then Proof. This is clear. Examining Figures 2 and 3, we see that the node b has its depth reduced by 1, reducing the expected cost of a lookup by p(b); the node a = π(b) has its depth increased by 1. The entire subtree rooted at c = λ(b) has its depth decreased by 1, reducing the cost by p(λ(b)) while the subtree rooted at e = σ(b) has its depth increased by 1. Right bumps are similar, and (1) follows.

Definition 6
We will refer to the quantity in (1) as the merit of bumping x, denoting it by µ(x, T ), or simply by µ(x) if no ambiguity is possible. If T is a weighted binary tree, we will say that the result of bumping T , to be denoted β(T ), is: For an integer k ≥ 0, we define β k (T ) recursively by β 0 (T ) = {T } and β k (T ) = ∪ t∈β k−1 (T ) β(t) The notation would be somewhat simpler (but less precise) if we either assumed there to be a unique x ∈ T for which µ(x) was maximal, or allowed β(T ) to be the result of bumping T by an arbitrarily selected x if multiple choices were available.
Since we only bump trees at nodes that have positive merit, we immediately have: Proof. The result will hold for any k ≥ N , where N is the total number of binary trees of the given size. Since each tree has a fixed associated cost, there can be no sequence of properly increasing costs (as per the lemma) of size greater than N .
Proposition 9 Let T be a weighted binary tree of size n. Then if k is a positive integer, an element of β k (T ) can be found in time O((n + k) log(min(n, k))).
Proof. The result will follow from the following: 1. It is possible to compute both p(x) and µ(x) for all x ∈ T in time O(n) in an initialization phase, along with 2. A list of at least min(n, k) nodes, sorted by merit, that can be initialized in time O(n log(min(n, k))), 3. When a node is bumped, it is possible to update the various p(x) and µ(x) in time O(1), and 4. It is possible to update the merit-sorted list of nodes in time O(log(min(n, k))).
The proposition then follows immediately, since the running time is O(n + n log(min(n, k))) for the initialization and O(1 + log(min(n, k))) for each of k iterations. The total running time is thus as described in the statement of the proposition.
1. p can be computed for all of the nodes in the tree in time O(n) by simply working back from the fringe. µ can then be computed, also in time O(n), by virtue of Proposition 5. 2. Given merits for all of the nodes, the k highest-merit nodes can be found in time O(n log k). If k > n, it suffices to simply sort the merits, so that the time is therefore O(n log(min(n, k))). Figures 2 and 3. When a node x is bumped, the value of p(x) will change only for x itself, since its parent is now a child, and x's parent π(x), since both x and one of the subtrees rooted at a child of x are no longer descendants of π(x). Computing p(z) for each of these two nodes takes constant time.

Consider
Similarly, µ(z) changes only for the nodes labeled a through e in the figures. Again, the update takes constant time. 4. When the merits are recomputed, inserting any new positive values into the list of nodes to bump takes time O(log s), where s is the size of that list, with s ≤ min(n, k) as a result. Note that we don't need to search the entire tree for a node to "replace" the one that was just bumped; if we only plan on bumping k nodes in total, we will be interested in one fewer node on the next iteration.

Experimental results
It follows from the results of the previous section that we can use our ideas to reduce the expected cost of searching a binary tree, and that doing so can be done in a timely fashion. It is not clear, of course, whether the methods will be effective in practice.
For each of the four basic tree constructions described in Section 2, we bumped nodes with the highest merit until quiescence, so that the tree could not be improved further with our simple method. The results are shown in Figure 4.
Two immediate observations are that the cost remains essentially linear in the logarithm of the tree size, and that the techniques we have proposed are by no means a panacea. They work well for some trees and clearly less well for others. Balanced binary trees, for example, provided the worst performance both before and after the trees are unbalanced.
Beyond that, however, the results are more interesting. Unbalanced splay trees and unbalanced weight-balanced trees perform virtually identically, even though their performance was starkly different before unbalancing. (In actuality, the weight-balanced trees benefited almost not at all from our ideas; the splay trees improved substantially.) Perhaps more surprising is that after unbalancing, the treaps have become easily the most effective method, and their performance is very nearly optimal for all tree sizes. As shown in Figure 5, the approximately 9-10% improvement optimization (relative to either weight-balanced trees or their unbalanced versions) will provide computationally meaningful savings in practice; the 1% difference between the unbalanced treaps and optimal trees is much less interesting.
Of course, given the weak bounds on the number of possible bumps before quiescence, our methods might not be viable in practice after all. Data regarding this (for unbalancing treaps, which appears to be the situation of interest) appears in Figure 6. For each size tree, we show both the mean number of bumps improving a treap of that size, and the maximum number of bumps. As can be seen, both numbers stabilize at b ≈ 0.21n, where b is the number of bumps. It follows from Proposition 9 that the optimized tree can be found in time O(n log(n)), a complexity identical to the cost of building the tree in the first place.
Before concluding, we should expand slightly on our earlier remark that our ideas are not a panacea; consider the tree in Figure 7 where the nodes are labeled with their respective probabilities.. This tree is locally optimal under rotation, since either a left or right rotation will move one high probability node up and the other down (for no net benefit), but move the low probability node down for a net loss. The optimal tree, which has one high probability node at the root and the other at depth 1, cannot be reached in a single rotation from the tree in the figure.

Conclusion and future work
The techniques that we have described appear to lead to clear and measurable improvements in access times for binary trees, but only scratch the surface of potential applications. Some obvious candidates for future work: Non-binary trees There is no reason to restrict our ideas to binary trees; any data structure where a similar measure of merit can be computed locally should be amenable to similar treatment.
Unbalancing restrictions It is possible to apply additional constraints when selecting a node to bump. As an example, if we begin with a binary tree where the maximum node depth is d, we could require that no node can be bumped if it pushes another node below depth d. This would lead to guaranteed performance improvements with no impact on worst-case performance. We could also obviously limit the maximum depth of a post-bump node in some less restrictive way. Since it is possible to compute and maintain d(x) for each node x, the impact on computational expense should be minimal. 3 Termination before quiescence Alternatively, one could limit the number of bumps to be a sublinear function of tree size in some way, although this may be difficult without significantly impacting performance. Figure 8, for example, shows performance both for optimized treaps and for treaps where at most 1000 bumps were permitted before the optimization was stopped. As can be seen, allowing our methods to proceed until quiescence provides significant improvement without changing the overall complexity of constructing the tree. Of course, we have no guarantee that the number of bumps will be linear in tree size, and we could obviously limit the number of bumps to (say) 50% of the number of nodes in the tree. Given the "maximum" curve in Figure 6, doing so would not impact any of the results we have presented.
Multiple bumps One can imagine situations where bumping a node once degrades overall performance, but bumping it twice provides an improvement. In general, updating the merits after a single bump involves recomputing values for 5 nodes; updating the merits after a bump of l levels will involve recomputing values for 2l + 3 nodes.
It follows that as long as the depth of the tree is bounded at some fixed multiple of log(n), we can consider not just single bumps but bumps of any number of levels and only add a factor of log(n) to the worst-case running time. Of course, given that we are producing trees with search costs within 1% of optimal, the additional complexity of such considerations may not be warranted.
Testing all of these ideas should be straightforward.

Conflict of interest
Funding: Not applicable.
Conflicts or competing interest: None.
Availability of data, material and code: Code and other materials will be provided upon request. The author reserves the right to patent the techniques described here. In the event that such patents are filed and granted, publication of this paper carries with it a permanent, royalty-free license for noncommercial use of the technology herein described.


extfieldsofstudy:
Computer Science
Medicine

text:
Dynamic Parameter Calibration Framework for Opinion Dynamics Models

In the past decade, various opinion dynamics models have been built to depict the evolutionary mechanism of opinions and use them to predict trends in public opinion. However, model-based predictions alone cannot eliminate the deviation caused by unforeseeable external factors, nor can they reduce the impact of the accumulated random error over time. To solve this problem, we propose a dynamic framework that combines a genetic algorithm and a particle filter algorithm to dynamically calibrate the parameters of the opinion dynamics model. First, we design a fitness function in accordance with public opinion and search for a set of model parameters that best match the initial observation. Second, with successive observations, we tracked the state of the opinion dynamic system by the average distribution of particles. We tested the framework by using several typical opinion dynamics models. The results demonstrate that the proposed method can dynamically calibrate the parameters of the opinion dynamics model to predict public opinion more accurately.

Introduction
Public opinion is the embodiment of the opinions, attitudes, and emotions expressed by the public, which affects multiple fields, such as human interactions, political orientation, financial policy, and even the military. Therefore, predicting the evolution trend of public opinion and providing valid explanations for its causes is a significant problem, both in theory and practice. Researchers have solved this problem by building opinion dynamics models. They simulate the interaction between individuals in society and changes in people's opinions, which can effectively reveal the generation, diffusion, and aggregation of public opinion.
Faced with the problem of public opinion prediction and explanation, researchers have attempted to reveal and analyze the laws of the public opinion system by establishing opinion dynamics models. Earlier research in this field can be traced back to the French model proposed in 1956 and its subsequent French-Degroot model [1]. Since then, multiple opinion dynamics models have been proposed, which can be divided into two categories: discrete and continuous. Typical discrete opinion dynamics models include the Voter [2], the majority rule [3], and the Sznajd [4] models. The study of discrete opinion dynamics has become popular in recent years [5,6]. In these models, agent opinions have only two values: mostly "1" represents support and "−1" represents against. This makes them suitable for depicting either/or cases; for example, political election prediction [7,8]. However, they cannot distinguish between neutral and extreme opinions or situations that are more complicated. Continuous opinion dynamic models have solved this problem. The most famous among them are the Hegselmann-Krause (HK) model [9] and the Deffuant-Weisbuch (DW) model [10]. These two models also introduced an important concept of opinion dynamics, that is, the bounded confidence rule: individuals' opinions are affected by others only when the difference between their own opinions and others' opinions is less than a threshold [11]. Based on this research, researchers have proposed multiple extended models [12][13][14][15][16].
However, it is still difficult to predict public opinion using only dynamic opinion models. On the one hand, public opinion may be disturbed by unpredictable external factors, such as emergent public events or the speaking of Internet celebrities. On the other hand, because models are not the same as real systems, the result of model prediction will inevitably fail owing to the accumulation of random and systematic errors over time. Therefore, in addition to model construction, two questions need to be answered to use the opinion dynamics model to predict the evolution of public opinion.
Problem 1 How to determine the initial values of the model parameters?
To solve this problem, the proposed framework determines the initial model parameters based on the genetic algorithm. We design a fitness function according to the characteristics of opinion dynamics and public opinion, which enables the framework to calibrate the parameters of the opinion dynamics models. Through selection, crossover, and mutation operations, we search for the parameters that best match the initial observation.
Problem 2 How can parameters be adjusted dynamically when public opinion changes owing to external factors or errors?
One feasible way to solve the above problem is to include empirical observation in opinion dynamics research to predict public opinion more accurately.
Machine learning is a popular data-driven method in multiple fields. Many studies have tried to predict the evolution of public opinion through machine learning methods [17][18][19][20][21][22][23]. However, compared with agent-based opinion dynamics models, machine learning cannot explain the inner mechanism of the system; it lacks interpretability and requires too much data to gain accuracy.
Traditional opinion dynamics models are mainly based on theoretical self-consistent and deductive analyses, which cannot be directly applied to predict public opinion. Recently, researchers have begun to import real social networks to test their models. Wang et al. [24] proposed an opinion dynamics analysis framework for a weighted directed complex network and imported a real email network to test their method. Zhu et al. [25] proposed an opinion dynamics model based on individuals' attitude-hiding behaviors and simulated their model on real Epinions networks, which can well explain Duncan's online social experiments [26]. However, these models are not yet associated with real observations; thus, they can only explain part of the public opinion phenomena and cannot calibrate the parameters of the models through simulation.
Currently, some researchers attempt to introduce data obtained from real social networks to correlate theoretical models with empirical data. In most of their studies, a part of the data was selected as the training set to learn the parameters of the model, and the rest of the data were used as the test set to verify the prediction accuracy of the model. De et al. [27] used the spectral projected gradient method to maximize the likelihood function of the model parameters, thus realizing parameter calibration of their model. Xion [28,29] collected data from the product review websites Epinions and Ciao, randomly selected X% of the data as a training set to learn model parameters, obtain individual opinions, and model-related topic vectors. The remaining data were used as a test set to evaluate the accuracy of their model prediction. Moreover, Xiong gathered a large amount of data from Twitter and conducted sentiment analysis using part of the early data for parameter calibration and curve fitting; they then used the model to predict the remaining opinion dynamics and compared the results with the rest of the real data [30]. Johnson et al. [31,32] proposed an adapted genetic algorithm for modeling opinion diffusion and tested the method using the Degroot model with limited data. Kotisz [33] proposed a minimal opinion formation model that is flexible and can reproduce a wide variety of existing micro-influence assumptions and models. The model was calibrated using datasets gathered from real social networks [34,35]. Lu [36] collected large-scale data from Douban.com and expanded the Ising model to explore how individuals behave and the evolutionary mechanisms of their life cycles. The above studies introduced real data from social networks to fit their model parameters, but their calibration work was static; they did not calibrate their models with new observations. Monti et al. [37] proposed an inference mechanism Entropy 2022, 24, 1112 3 of 16 that can fit the opinion dynamics model to the social trajectory in the real world, thereby increasing the ability to fit real data. However, in different social networks, user interaction behaviors and social trajectories may not be the same. Thus, it may not be suitable to apply the mechanism to other online social networks with different structures. In addition, compared to observing public opinion, collecting the social trajectories of users is more complicated.
In summary, the field of opinion dynamics requires a dynamic calibration method that can be widely applied to all types of online social networks according to successive observations. Dynamic calibration is an important issue in the field of modeling and simulation. Recently, many researchers have explored dynamic calibration methods [38][39][40][41][42][43][44]. However, few have aimed at the field of opinion dynamics [45]. Thus, combining the advantages of the theoretical model and data-driven method to predict public opinion is a direction for future opinion dynamics research [46], and one way to achieve this is to introduce a data assimilation method. Common data assimilation algorithms include the Kalman filter, optimal interpolation, and the extended Kalman filter [47]. However, neither the Kalman filter nor the optimal interpolation method can deal with non-normally distributed and nonlinear systems. Furthermore, the extended Kalman filter requires that the probability distribution of the system be expressed by simple parameters, which is also not suitable for dealing with cases in opinion dynamics systems. Compared with other methods, a particle filter can be applied to nonlinear systems [48,49]. Moreover, the use of particle filters to realize data assimilation in discrete event simulation has also been proposed by researchers in recent years [50,51]. This indicates that a particle filter has the potential to be used in the prediction calibration of opinion dynamics.
Inspired by data assimilation methods, to predict the state of the changing opinion dynamic system, the framework uses a particle filter algorithm to calibrate the parameters of the models dynamically with successive observations. In the framework, we initialize the particles according to the results of the initial parameter calibration and determine the particle weights with successive observations. By continuously resampling the particles and updating the particle weights, the framework enables models to track the changing state of the opinion dynamic system by the average distribution of particles that hold the largest weights.
We test the framework with four typical opinion dynamics models based on synthetic data, which simulate the changing public opinion systems. The results show that the framework can effectively determine the initial parameters of the models and dynamically calibrate the parameters of the opinion dynamics models over time, thus predicting public opinion more accurately.
As illustrated above, in this study, the main contributions to the fields of opinion dynamics are as follows: (1) We propose a framework that can dynamically calibrate the parameters of the opinion dynamics model to predict public opinion more accurately. (2) We combine model prediction and empirical data into opinion dynamics research.
(3) We verified the effectiveness of the framework by simulation experiments.
The remainder of this paper is organized as follows. Section 2 provides the basis for our proposal. Section 3 describes the proposed framework in detail. Section 4 presents the simulation testing analysis. Section 5 provides a summary of this study.

Preliminary
To provide a basis for our proposal, we introduce some basic concepts of opinion dynamics and typical models, which will be used in the experiments in this study.

Brief Introduction of Opinion Dynamics
Opinion dynamics model the evolution process of agents' opinions. Individuals in the system interact with others according to preset rules, and constantly update their opinions. As shown in Equation (1), let x i (t) be the opinion of individual i at time t. When an opinion Entropy 2022, 24, 1112 4 of 16 dynamics system evolves to a steady state, it always shows an opinion distribution of consensus, polarization, or fragmentation, as shown in Figure 1 [52]. (1) ions. As shown in Equation (1), let ( ) be the opinion of individual at time t. When an opinion dynamics system evolves to a steady state, it always shows an opinion distribution of consensus, polarization, or fragmentation, as shown in Figure 1 [52].
Generally, an agent's opinion at the next moment is influenced by the opinions of other individuals. Individuals whose opinions influence each other can be regarded as having interactive relationships. The relationship between individual interactions can be depicted as a graph. Social networks can be regarded as a directed graph G = (V, E), where V denotes the set of nodes (agents) in the network and E is the edge set formed by the connection of nodes, representing the interaction and influence relationship between individuals in the network.

Hegselmann-Krause Model
The HK model [5] is one of the classic opinion dynamics models. The model is based on the bounded confidence rule; agents' opinions are quantified as values ranging from 0 to 1, and ( ) is the opinion of the agent at time t. Agent only interacts with agent whose opinion satisfies the condition | ( ) − ( ) < |. At each time step, individuals update their opinions as follows: Generally, an agent's opinion at the next moment is influenced by the opinions of other individuals. Individuals whose opinions influence each other can be regarded as having interactive relationships. The relationship between individual interactions can be depicted as a graph. Social networks can be regarded as a directed graph G = (V, E), where V denotes the set of nodes (agents) in the network and E is the edge set formed by the connection of nodes, representing the interaction and influence relationship between individuals in the network.

Hegselmann-Krause Model
The HK model [5] is one of the classic opinion dynamics models. The model is based on the bounded confidence rule; agents' opinions are quantified as values ranging from 0 to 1, and x i (t) is the opinion of the ith agent at time t. Agent i only interacts with agent j whose opinion satisfies the condition |x i (t) − x(t) < ε|. At each time step, individuals update their opinions as follows:

Expressed and Private Opinion Model
The expressed and private opinion (EPO) model [7], proposed by Anderson, is an improvement of the classic FJ model [53,54]. In the simulation process, the model updates agents' opinions using the following rules: where a ij is the influence weight individual i has on individual j, λ i , θ i denote agents' stubbornness and adjustment coefficient, respectively. x i (t) is agent A i 's private opinion at time t andx i (k) is its expressed opinion at time t.

Adapted Deffuant-Weisbuch Model
The adapted Deffuant-Weisbuch (ADW) model was proposed in 2022 [27] and is an adaptive model of the classic DW model. In the model, let x i (t) be individual i's private opinion at time t,x i (t) be its expressed opinion at time t, and µ i , p i be related parameters for individuals. In the process of simulation, the model will randomly select two individuals in each iteration, if x i (t) −x j (t) < ( is the bounded confidence threshold), individuals' opinions will be updated by the following rules:

Attitude-Hiding Model
The attitude-hiding (AH) model was proposed in 2022 [10], which depicts online users' behavior of hiding attitudes toward online social networks and can evolve multiple types of opinion dynamics.
In this model, agents estimate the popularity of their expressible opinions in their messages according to empirical knowledge. According to the outcome of their estimation, they decide whether to post messages as usual or to remain silent. Let x i (t) be agent A i 's opinion at time t and m i (t) be the opinion A i wants to express at time t. For A i 's fan A j , the value of the feedback parameter F j = 1, 0 or −1, depending on whether A j likes, has no comment, or disagrees after A j receives A i 's message with the opinion m i (t). Thus, the feedback F j is determined by where α is the boundary inside of which A j would give positive feedback (F j = 1), and β is the boundary outside of which A j would give negative feedback (F j = −1). Let inN(i) be the set of A i 's fans and let #inN(i) denote the number of A i 's fans. A i 's popularity of its messages to fans can be denoted by the feedback from its fans, which is If φ i be a given threshold (−1 < φ i < 1), and if R(m i (t)) > φ i , A i would believe that the potential gain from expressing opinions is large enough, it will express its opinion m i (t).

Dynamic Framework to Calibrate Opinion Dynamics Models
In this section, we introduce a detailed dynamic calibration framework for the prediction of opinion dynamics. Let the opinions of agents in the models be variables ranging from (0,1) and divide the opinion interval [0, 1] to K intervals uniformly. In this framework, we suppose that the observation of public opinion at time t is a vector with K dimensions Upon importing opinion dynamics models and initial observations into the framework, we first calibrate the model parameters based on the genetic algorithm, searching for a set of parameters with high adaptability to the initial data. Second, we conduct a particle filter based on the initial parameters obtained in the previous step and dynamically calibrate the model parameters with successive observations. The overall process of the framework is shown in Algorithm 1.
Algorithm 1 Framework of calibrating the prediction for opinion dynamics models 1: Initialize population; Population codes parameters of opinion dynamics models 2: Evaluate population by O t 0 ; 3: while the genetic algorithm method is searching do 4: Select population that best matches the observation; 5: Crossover to generate new population, so as to search more efficiently; 6: Mutate to realize local random search, and avoid unmature convergence; Simulate opinion dynamics models according to the particles; 12: Update particle weights; 13: Estimate new system state through the average distribution of particles with the largest weights; 14: Resample particles; 15: end if

Initial Parameter Calibration Based on Genetic Algorithm
The genetic algorithm is a global search algorithm that is conducted through selection, crossover, and mutation operations to its generation during iterations, and evaluates its generation by calculating the fitness function. The proposed framework calibrates the initial parameters for the model based on the genetic algorithm and uses the results in the next step.
In this section, we introduce details of the method used in the framework.

Fitness Function
In this framework, individuals in the genetic algorithm correspond to a set of parameters of the opinion dynamics model. The smaller the deviation between the model output and initial data, the higher the fitness of the individual with the corresponding parameters.
Let the fitness function f be the reciprocal of the total deviation between the model output and initial data as follows:

Selection
Individuals in the current population are selected with a certain probability for the next generation; this process is called selection. The probability of selection for the next generation depends on the fitness of the individual. The higher the fitness value, the higher the probability. In the proposed framework, we use one of the most popular selection methods, the roulette wheel selection method. In this method, the selection probability of each individual is proportional to its fitness value; the greater the fitness value, the greater the selection probability. Therefore, individuals with a large fitness value have a greater probability to be selected as a parent to generate a new individual. Let the probability of an individual x i be selected as p(x i ), the fitness value of (x i ) be f (x i ), and the sum of all individuals' fitness values be S; the roulette wheel selection method can be presented as follows:

Crossover
The genetic algorithm maintains the diversity of the population through a crossover operator, which includes three steps. First, the number of individuals to be crossed is set according to the crossover probability, and then randomly select individuals to be exchanged. Second, the intersection position was randomly selected. Third, paired individuals exchange their corresponding attribute strings at the crossing position, thus forming new individuals. In this study, single-point crossing with a fixed crossover probability is used for the replication operation, which is performed by taking two chromosomes, dividing them at a randomly selected location, and swapping the right part, resulting in two different daughter chromosomes. For cases where selecting an intersection location has a certain meaning, single point crossover will cause less damage to the chromosomes.

Mutation
In a genetic algorithm, the diversity of the population can be guaranteed by a mutation operation, which also prevents premature convergence. The mutation probability is small. In the mutation operation, first, the number of genes to be mutated is determined by the mutation probability, and then alleles to be reversed or replaced are randomly selected.
We code the parameter values in binary form in the chromosomes, as shown below: Let the variable X to be optimized within the interval [a, b], the number of genes be m, and the coding length be l, also the coding method is accurate to c decimal places, then: Therefore, the mutation is to select a certain location of the chromosome according to a fixed mutation probability and invert its value (0 becomes 1, 1 becomes 0), so as to enhance the random search ability of the genetic algorithm. Because the genetic algorithm can only search for one set of data and cannot retain historical information, the method introduced in Section 3.1 is a calibration method for determining initial parameters. We then combined more observations and used the data assimilation method to calibrate the models dynamically.

Dynamic Calibration Based on Particle Filters
In this step, we first express the probability distribution of the system state as a particle set. Particles are simulated to predict the prior distribution of the system state using the Monte Carlo method. We then merged real-time observations to calibrate the posterior distribution of the system state to ensure accurate analysis and prediction of the evolution of public opinion in social networks.
Let each particle have a set of parameters corresponding to the opinion dynamics model θ i , and let the state of the particle at time t be θ i t . After parameter calibration, we obtained a set of optimal parameters for the initial observation, θ t 0 .
For a particle, let particle i's initial parameter state be sampled from a Gaussian distribution, θ t 0 ∼ N θ t 0 , σ 2 , where σ 2 is the preset sampling deviation. Simultaneously, because of the nonlinear relationship between the opinion dynamics system and the output of the model with different parameters, we retain some of the particles whose initial state is sampled from a random distribution, θ t 0 ∼ U(0, 1). However, we assume that public opinion is in a steady state before being disturbed. Therefore, before obtaining the latest observation, the states of the particles remain the same, that is, θ i t+1 = θ i t .
where p(S t |S t−1 ) represents the probability function of the state transition, which corresponds to the opinion dynamics model. Because we assume that the observed public opinion is in a steady state before O t is obtained, the models also output the results after they have evolved to a steady state. Therefore, S t = S t−1 before a new observation was obtained. The posterior probability density of S t , p S t −→ O 1:t can be formulated as: where η is the normalization coefficient, and the above equation represents the calibration process, which uses the likelihood p Because it is difficult to obtain analytical solutions for nonlinear and non-Gaussian opinion dynamic systems, particle filters represent the posterior probability distribution of S t with a group of random samples (particles). When the number of particles is sufficiently large, the posterior probability of the system can be approximated sufficiently. The process of the proposed data assimilation method in the framework is illustrated in Figure 2.
the Monte Carlo method. We then merged real-time observations to calibrate the posterior distribution of the system state to ensure accurate analysis and prediction of the evolution of public opinion in social networks.
Let each particle have a set of parameters corresponding to the opinion dynamics model , and let the state of the particle at time t be . After parameter calibration, we obtained a set of optimal parameters for the initial observation, . For a particle, let particle 's initial parameter state be sampled from a Gaussian distribution, ~( , σ ), where σ is the preset sampling deviation. Simultaneously, because of the nonlinear relationship between the opinion dynamics system and the output of the model with different parameters, we retain some of the particles whose initial state is sampled from a random distribution, ~(0,1). However, we assume that public opinion is in a steady state before being disturbed. Therefore, before obtaining the latest observation, the states of the particles remain the same, that is, = . Let the state at time t be , and the observation be ⃗ . According to the Chapman-Kolmogorov equation, the prior probability density of , : ⃗ can be calculated as where ( | ) represents the probability function of the state transition, which corresponds to the opinion dynamics model. Because we assume that the observed public opinion is in a steady state before is obtained, the models also output the results after they have evolved to a steady state. Therefore, = before a new observation was obtained. The posterior probability density of , : ⃗ can be formulated as: where is the normalization coefficient, and the above equation represents the calibration process, which uses the likelihood ⃗ between the state and observation to obtain the posterior distribution of states at the next moment : ⃗ .
Because it is difficult to obtain analytical solutions for nonlinear and non-Gaussian opinion dynamic systems, particle filters represent the posterior probability distribution of with a group of random samples (particles). When the number of particles is sufficiently large, the posterior probability of the system can be approximated sufficiently. The process of the proposed data assimilation method in the framework is illustrated in Figure  2.

St-1
Importance sampling  Figure 2. Data assimilation process for opinion dynamics based on particle filter.
In the particle filter, the posterior distribution is approximated by a set of particles S k t , w k t k = 1, . . . , N . Here, S i t represents the state of the ith particle and SM t is the model output when evolving to a steady state under the corresponding settings of each particle. w i t is the weight of the ith particle. Each particle is a possible realization of a state; thus, the posterior distribution of the opinion dynamics system at time t can be represented as: In the proposed framework, particles are a configuration set of the model, including the parameter setting and structure of the social interaction graph. Suppose S k t−1 , w k t−1 k = 1, . . . , N is known; then, the possible state at time t SM k t can be inferred based on the opinion dynamics model; thus, newly generated sets of particles can be regarded as the particle representation of the prior distribution. Subsequently, each particle can calculate and update its weight according to the following observation: In detail, according to the calculation of the fitness function in Section 4.1, the closer the model output with parameters that correspond to a particle is to the observation, the greater the particle weight; thus, we have After several iterations, the estimated variance of the particle weight gradually increases, resulting in particle degradation; that is, the weight of most particles is too small for the particle set to effectively express the posterior probability distribution of the system state, and the simulation of these low-weight particles is not sufficiently meaningful. To this end, the method resamples the particles from the particle sets SM k t k = 1, . . . , N . Generally, the probability of selecting a particle is determined by its corresponding weight. Particles with high confidence are sampled more, which ensures that the particles converge to a state with high confidence and can obtain the posterior particle set S k t k = 1, . . . , N . After outputting the results, the framework continues to resample the particles. It retains the ν particles with the highest weights. Let the average state of those particles be θ t avg , and the new states of other particles be sampled from a Gaussian distribution N θ t aνg , σ 2 . Meanwhile, some particles are still selected, and their new states are sampled from the random distribution U(0, 1).

Simulation Tests and Analysis
In this section, we use the AH, ADW, EPO, and HK models to test the proposed dynamic calibration framework and solve the two problems. In Section 4.1, we calibrated the initial parameters of the four models based on synthetic datasets to verify the feasibility of the method proposed in Section 3.1. In Section 4.2, we solve the second problem, that is, assuming that the model is correct, how to calibrate the model as public opinion changes owing to external factors. Based on the results in Section 4.1, we initialized the particles and dynamically calibrated the four models using the particle filter method. The reason to use synthetic data is that the proposed framework is designed to solve the problem that, assume the opinion dynamics model is correct, how to dynamically calibrate the parameters with a new observation, so as to achieve more accurate model predictions. Whether the model can evolve specific real public opinion is not what this study considered. Compared with real public opinion data, synthetic data generated from opinion dynamics models fit better with corresponding models, which is easier to demonstrate whether the framework can dynamically calibrate model parameters to achieve more accurate predictions.
To quantitatively express the accuracy of the prediction and calibration, we propose the concept of deviation distance: Let a node in the parameter space have an N-dimensional coordinate (x 1 , x 2 , . . . , x n ), and the coordinates of the node that correspond to the actual parameters in the data are (x 1 ,x 2 , . . . ,x n ). Then, the deviation distance was.

Calibration to Determine Initial Parameters
In this section, we search for the optimal initial parameters of the AH, ADW, EPO, and HK models using the parameter calibration method in the framework. For the initial observation, we set a combination of parameters for the four models and took the model output under these parameters as the synthetic initial observation.
For the AH model, we set = 0.4, λ i = 0.5, φ i = −0.5, α = 0.35, and β = 0.4 to generate synthetic data. For the ADW model, we set µ i = 0.1, p i = 0.8, and = 0.3. For the EPO model, we set λ i = 0.8 and θ i = 0.3. For the HK model, we set ε = 0.1. The number of agents in the above models is 1000, and for those models that include a social network structure, we import a scale-free network with 1000 nodes. The initial opinions of the agents in the models were randomly sampled.
Calibrating the initial parameters for the four models, the results are shown in Tables 1-4: As shown in the tables, as the number of iterations increased, the deviation in the results for each model decreased. This indicates that the parameter calibration method in the proposed framework can infer the initial parameters of opinion dynamics models, thus answering Problem 1. The above results demonstrate the feasibility of the parameter calibration method and the reliability of the initial parameters for the models.
Note that the genetic algorithm may still obtain a local optimal solution instead of a global optimal solution. For example, in the results of the EPO model, the deviation with 100 iterations was greater than that with 50 iterations. A solution to this problem is to calibrate the model multiple times to avoid such situations.
Because prior knowledge cannot be fully used by the genetic algorithm to calibrate the model parameters with more observations, we then use the particle filter in the framework to dynamically calibrate the above models.

Dynamic Calibration with Successive Observation
First, we initialized the particles based on the results presented in Section 4.1. In the following experimental results, we present the particles with the largest weight in the parameter space.
In the experiments, synthetic data were generated after the models had evolved to a steady state under the preset parameters. The first group of data was the initial synthetic data used in Section 4.1. For the AH model, we changed , λ i , and the remaining groups of data were generated with ( ,λ i ) = (0.8, 0.2) and (0.5, 0.5). For the ADW model, we changed µ i , p i , and the remaining data were generated with (µ i , p i ) = (0.6, 0.4) and (0.3, 0.5). For the EPO model, we changed µ i and p i , and the remaining data were generated with (µ i , p i ) = (0.5, 0.5) and (0.2, 0.8). For the HK model, the data were generated with ε = 0.2 and 0.05. The other parameters and configurations of the four models were the same as those in Section 4.1. Five hundred particles were used for the calibration of each model.
First, we present the results of the HK model. The results is shown in Tables 5-7. We selected 10 particles with the greatest weight as the results (the top 10 particle weights have been normalized), and it can be observed from the tables that, with the change in observed data, the parameters of the optimal particle can always be around the position corresponding to the real parameter. However, note that the original HK model is mainly used to analyze the dynamic changes in opinion dynamics caused by different bounded confidence thresholds; the model is not built to fuse observations. Although the data assimilation algorithm proposed in this framework can be used to track and forecast self-generated synthetic data, the HK model may not be able to evolve some situations in public opinion due to the social network structure, other attributes of individuals, and even external influences.
We then show the results of the AH, ADW, and EPO models in Figures 3-5, respectively, on scatter plots in the parameter space.         The average deviation of the above results is shown in Figure 6. The average deviation of the above results is shown in Figure 6. Figure 6. Deviation between the average position of the optimal particles after filtering and the position of the parameters for synthetic data.
From the above results, it can be concluded that the above models can track changes in the observations and dynamically calibrate the model prediction under the proposed framework. The positions of the calibrated particles in the parameter space can be approximately the positions of the parameters for the synthetic data. The results prove that the framework can dynamically calibrate the parameters of opinion dynamics models as public opinion changes and track the system through successive observations. Among the above models, the ADW model has the highest precision for calibration on synthetic datasets, whereas the distribution of particles of the EPO model for the second observation in Figure 5b is relatively dispersed. This may be because the ADW model is affected less by random factors than the EPO or the AH model. In addition, the results of the AH model are less accurate than the others, which may be due to its complexity. The AH model is built to predict real public opinion, and its mechanism is more complicated than that of the other models. Furthermore, a different set of parameters in the AH model may derive similar opinion dynamics, making particles that actually deviate from the real location significantly increase in weight, thus affecting the accuracy of the results. Nevertheless, opinion dynamics models with different parameters might show similar output results, leading to situations in which some particles in the above three experiments deviated more from the synthetic values. In future work, we will attempt to avoid this problem by improving the weight update rules. From the above results, it can be concluded that the above models can track changes in the observations and dynamically calibrate the model prediction under the proposed framework. The positions of the calibrated particles in the parameter space can be approximately the positions of the parameters for the synthetic data. The results prove that the framework can dynamically calibrate the parameters of opinion dynamics models as public opinion changes and track the system through successive observations. Among the above models, the ADW model has the highest precision for calibration on synthetic datasets, whereas the distribution of particles of the EPO model for the second observation in Figure 5b is relatively dispersed. This may be because the ADW model is affected less by random factors than the EPO or the AH model. In addition, the results of the AH model are less accurate than the others, which may be due to its complexity. The AH model is built to predict real public opinion, and its mechanism is more complicated than that of the other models. Furthermore, a different set of parameters in the AH model may derive similar opinion dynamics, making particles that actually deviate from the real location significantly increase in weight, thus affecting the accuracy of the results. Nevertheless, opinion dynamics models with different parameters might show similar output results, leading to situations in which some particles in the above three experiments deviated more from the synthetic values. In future work, we will attempt to avoid this problem by improving the weight update rules.

Conclusions
In this study, a dynamic framework is proposed to calibrate the parameters of opinion dynamics models to predict public opinion more accurately. The framework does not require detailed observation from individuals' social traces or activity records, but the overall public opinion, which is easier to obtain comparing with others' work. The simulation results for the AH, ADW, EPO, and HK models show that the framework can be applied to multiple opinion dynamics models without changing the structure of the model, integrating model output and observation, and dynamically calibrating model parameters. However, due to time constraints, we did not test the framework with more particles on multi-dimension parameters for opinion dynamics models. In future work we will further improve the proposed framework by developing data crawling and sentiment analysis methods to make a prediction system. In addition, we will try to adjust the algorithm to achieve a parallel mechanism (both a genetic algorithm and a particle filter algorithm are suitable for a parallel algorithm) and use high-performance computing to set more particles and populations for simulation, so as to achieve more rapid and accurate prediction results with good interpretation. Lastly, we will attempt to obtain real public opinion data and improve the weight update rule and sampling strategy in the framework to support opinion dynamics models to predict real public opinion.


Algorithms for Extracting various Local Texture Features

In the machine learning and computer vision domain, images are represented using their features. Color, shape, and texture are some of the prominent types of features. Over time, the local features of an image have gained importance over the global features due to their high discerning ability in localized regions. The texture features are widely used in image indexing and content-based image retrieval. In the last two decades, various local texture features have been formulated. For a complete description of images, effective and efficient features are necessary. In this paper, we provide algorithms for 10 local texture feature extraction. These texture descriptors have been formulated since the year 2015. We have designed algorithms so that they are time efficient and memory space-efficient. We have implemented these algorithms and verified their output correctness.

Introduction
Image indexing and Content-based Image retrieval are solutions to efficient searching of images from large image databases. For efficient indexing and retrieval of images first, the images are described by using their features. Local Binary Pattern introduced by Ojala et al. [1] is one of the earliest and efficient texture feature descriptors. Since then, various types of local texture features have been introduced by various researchers. In this article, we provide 10 algorithms for various recent texture feature descriptors.
This work is part of a research project on content-based medical image retrieval. We plan to use these algorithms in the task of extracting features from medical images. Algorithms will provide detailed steps for tasks. In this paper, the task is extracting various textural features from images. As of date, more than about 20 texture feature descriptors being formulated by various researchers. Out of these, we have chosen recent 10 texture descriptors. We have provided efficient and easy-to-read algorithms.
The outline of this paper is as follows. In Section 2, we cover the literature review. In Section 3, we cover algorithms for various local texture feature extraction. In Section 4, we provide the future scope and conclude.
2 Literature Review One of the earliest local texture descriptors is Local Binary Pattern(LBP) [1]. In this feature computation for each non-border pixel, the neighbors at a radius are compared with the center pixel. Based on the sign of the difference formed from comparison, the pattern is generated. The LBP is simple and has been the basis for devising various other local texture descriptors. Co-occurrence of pixel pairs is a statistical approach towards describing images. In the Center Symmetric Local Binary Co-occurrence pattern(CSLBCoP) [2], first, the center symmetric pattern is computed and then the obtained feature map's co-occurrence pattern is computed in different directions.
A texture feature descriptor that gives importance to diagonal extremas is proposed and is named Local Diagonal Extrema Pattern(LDEP) [3]. In this feature computation, the firstorder local diagonal derivates are computed and then these are compared with the center pixel to form the feature vector. In Local Wavelet Pattern(LWP) [4], the relationship among the neighboring pixels is first wavelet decomposed. Next, the center pixel is transformed to match the range of decomposed neighbors. By establishing the relation between the two, the LWP is derived. The researchers propose this method for CT images retrieval based on their content. Local Tri-directional Pattern(LTriDP) [5] uses the relationship between adjacent neighbors with neighboring pixels and the relationship of the neighboring pixel with the center pixel. A threedirectional relationship is encoded in this pattern.
Local Bit-plane Decoded Pattern(LBDP) [6] is similar to LBP. But instead of comparing pixel intensities of neighbors with center pixel, a transformed neighbors with center pixel is used. The vector formed out of each bit from among neighbors is used instead of the direct neighbor intensity. Local Neighborhood Difference Pattern(LNDP) [7], is a texture feature descriptor that considers the relation between neighbors with its adjacent pixels. The sign of difference of neighbor with its adjacent pixel is used in computing the pattern. A novel texture feature descriptor called Local Neighborhood Intensity difference Pattern(LNIP) is proposed [8]. This descriptor encodes the difference of neighboring pixels with its adjacent neighbors. Along with the difference(sign) pattern, the magnitude pattern is also encoded in this pattern. Two new feature descriptors named Threshold Local Binary AND Pattern(TLBAP) and Local Adjacent Neighborhood Average Difference Pattern(LANADP) are proposed [9]. TLBAP uses a threshold calculated from among neighbors and performs bit-wise AND with LBP feature to compute the feature at a center pixel. This is repeated for all non-border pixels to compute the TLBAP feature for the entire image. The LANADP feature [9] is computed based on the difference of neighboring pixels with its neighbors in vertical, horizontal, and diagonal directions.
3 Algorithms for various Local Texture Features Extraction 3.1 Local Binary Pattern Algorithm 1 shows detailed steps for Local Binary Pattern feature extraction from an image. The image intensity matrix is arr, which is input to the findLBP function as an argument. The arrays dx and dy contain the relative offset in the X and the Y direction required for determining the immediate 8 neighbors around a center pixel. The array multiple2 contains powers of two ranging from 2 0 to 2 7 . If the sign of differences of the neighbor pixel with the center pixel is positive or zero, the corresponding powers of two are added. The for loop in line 12 in the algorithm is used to traverse across the 8 neighbors of a center pixel.

Center Symmetric Local Binary Co-occurrence Pattern
Algorithm 2 shows steps for computation of Center Symmetric Local Binary Co-occurrence Pattern. In line 10 in the algorithm, the center symmetric pattern is computed. The difference of a neighbor with its symmetric neighbor is used in the center symmetric pattern. Then in line 12, using the GRAY COM AT RIX function, the co-occurrence feature of the center symmetric pattern is generated by taking offset in 4 angles(0°,45°,90°, and 135°).
return lnips, lnipm 3.9 Threshold Local Binary AND Pattern Algorithm 9 shows steps for determining Threshold Local Binary AND Pattern(TLBAP). This descriptor uses both Threshold Local Pattern and Local Binary Pattern. An input threshold(a value between 0 and 1) is used in this descriptor. First, the maximum among neighbors is determined and then the maximum is multiplied by the threshold. Based on the sign of difference of this with the neighbors, Threshold Local Binary Pattern is generated. Then, the Local Binary Pattern is computed for the center pixel. These two patterns are ANDed to produce TLBAP.

Results
We have implemented each of the algorithms using MATLAB R2020b. We have tested the output from each of the algorithms for correctness. The obtained output and expected output are shown in the following Table1. The input image matrix of size 5 × 5 is given as