CN110222239B - A structure-variable pattern generation and a method for generating a browsing interface using patterns - Google Patents

Abstract

The invention discloses a method for generating a structure-variable pattern and using the pattern to generate a browsing interface. The pattern generating method includes the following steps: S1, constructing a relational graph model for the elements in the pattern; S2, adopting a discrete energy equation Optimize the model and match elements between different topological patterns; S3, based on the RJMCMC algorithm, sample between different topological patterns to obtain new patterns. The method for generating a browsing interface by using a pattern includes the following steps: 1) Acquiring the high-dimensional vector expression features of the new pattern obtained by sampling to obtain a high-dimensional vector space; the high-level vector expression features are expressed by the vector representation of the pattern ; 2), use GPLVM to compress the high-dimensional vector space into a two-dimensional manifold space; 3), inversely map the points in the two-dimensional manifold space to the high-dimensional space, obtain a new pattern, and perform post-processing on it ; 4), generating a pattern browsing interface.

Description

A structure-variable pattern generation and a method for generating a browsing interface using patterns

technical field

The invention relates to the fields of computer pattern generation and pattern browsing, in particular to a method for pattern generation with variable structure and a browsing interface generated by using patterns.

Background technique

Existing mature algorithms and systems can simply and quickly obtain many variant candidates with different element sizes, positions, and directions based on the morphological structure of a single pattern. For example, in the paper PATEX:exploring pattern variations, the author uses the geometric relationship between the pattern parts to describe the pattern and obtains many pattern variants based on the source pattern by sampling those patterns that satisfy a subset of different geometric relations. However, this method is only aimed at a single pattern variation, and cannot automatically create patterns among multiple patterns that can maintain some characteristics of different source patterns and bring some new changes.

In addition, for different patterns, the elements and arrangement characteristics between them may be quite different. There are also countless pattern variations between two simple patterns. Such different new pattern results need to be sampled as much as possible. Finally, current pattern design tools lack patterns that would allow designers to browse through all these elemental and morphologically varied pattern variations within the same collection in quick succession.

Contents of the invention

The present invention provides a system for sampling some new patterns between given two patterns and provides an interactive browsing interface for generating patterns. These new patterns can not only maintain some local features in the source patterns, but also have some changes, even if the number of elements and element arrangement characteristics between these reference source patterns may be different. Designers can browse all these elements and pattern results with different shapes in the interface. The present invention mainly solves the problem of how to identify and utilize the respective morphological features of these different topological patterns and the problem of how to sample in different space sets composed of new patterns with different arrangement features and element quantities. At the same time, it provides an interactive browsing interface for patterns, which allows designers to freely browse all possible pattern variants that can be searched.

The present invention is realized through at least one of the following technical solutions.

A method for generating patterns with a variable structure, comprising the following steps:

S1. Construct a relational graph model for the elements in the pattern;

S2. Using a discrete optimization model of the energy equation to match elements between different topological patterns;

S3. Based on the RJMCMC algorithm (Reverse Jump Markov Chain Monte Carlo, reversible jump Markov chain Monte Carlo algorithm), sampling between different topological patterns to obtain new patterns.

Further, the relationship described in step S1 includes the relationship type of the element and the relationship type of the relationship, wherein the relationship type of the element includes the distance relationship between elements, the direction angle relationship between elements, and the size ratio between elements Relationship; the relationship type of relationship includes that the distance between elements is equal difference or proportional relationship, and the angle relationship between the orientation of a certain element in the pattern and the orientation of other elements.

Further, the relationship diagram model constructed in step S1 is used to describe the relationship between elements in the pattern and the relationship between the relationships;

The relationship diagram model includes a relationship diagram vector, a relationship diagram vector represents a pattern; a relationship diagram vector is a one-dimensional vector consisting of three parts, the first part of which is the position (x, y) of each element in the pattern in turn , orientation θ, and size s, the second part contains the value of the relationship between elements, and the third part is the relationship value r, which includes the relationship value between elements and the relationship between elements value, the relationship diagram vector μ is as follows:

μ=(x ₁ ,y ₁ ,θ ₁ ,s ₁ ,x ₂ ,y ₂ ,θ ₂ ,s ₂ ,..., _xi ,y _i ,θ _i ,s _i ,r ₁ ,r ₂ ,r ₃ ,...,r _i ) (1)

进行表示，有向图的节点N＝E∪R，其中E是图案中元素的集合，第i个元素表示为E_i＝(x_i,y_i,θ_i,s_i)，E_i∈E，i表示元素的数量；R是图案中关系的集合，R＝R^E∪R^R，R^E是元素关系集合，R^R是关系间的关系集合，每一个关系有相应的关系值，其中第i个关系的关系值表示为R_i＝(r_i)，R_i∈R；将节点N_i对应关系图向量的所有的元素信息或关系值记做

以及

其中E_j∈E；有向图的边A＝{(N_i1,R_i),(N_i2,R_i)}_i＝1...k+l，其中k是关系图模型中元素关系的数量，l是关系的关系数量。例如N_i1和节点N_i2是均与关系值R_i相关的元素E₁和元素E₂或者关系R₁和关系R₂，其中R_i的值由节点N_i1和节点N_i2的值计算得到；Relational graph models through directed graphs

For representation, the node N=E∪R of the directed graph, where E is the set of elements in the pattern, and the i-th element is expressed as E _i =( _xi ,y _i ,θ _i ,s _i ), E _i ∈ E , i represents the number of elements; R is the set of relations in the pattern, R = R ^E ∪ ^{R R} , R ^E is the set of element relations, R ^R is the set of relations between relations, and each relation has a corresponding relation value, among which The relationship value of i relationship is expressed as R _i = (ri ), R _{i ∈} R; write all the element information or relationship value of node N _i corresponding to the relationship graph vector as

as well as

where E _j ∈ E; the edge A of the directed graph={(N _i1 ,R _i ),(N _i2 ,R _i )} _i=1...k+l , where k is the element relationship in the relational graph model Quantity, l is the relation number of relations. For example, N _i1 and node N _i2 are element E ₁ and element E ₂ or relationship R ₁ and relationship R ₂ that are both related to the relationship value R _i , where the value of R _i is calculated from the values of node N _i1 and node N _i2 ;

Specifically, there are 6 types of relationship of elements and 3 types of relationship of relationship, among which, the relationship types of 6 elements are:

1), the distance between an element E _a in the representative pattern and the center of another element E _b in the representative pattern is defined as the Euclidean distance relationship between the elements, wherein the value of the relationship value R _i is:

Wherein, (x _a , y _a ) is the position of element E _a , (x _a , y _b ) is the position of element E _b ;

2), the angle difference between an element E _a in the representative pattern and the direction of another element E _b in the representative pattern is defined as the direction difference relationship between the elements, and the value range of the relation value R _i is [- π,π], clockwise angle changes are negative:

Among them, θ _a and θ _b are the orientations of E _a and E _b respectively;

3), the difference between the size of an element E _a in the representative pattern and the size of another element E _b in the representative pattern is defined as the size difference relationship between the elements, the relationship value R _i :

R _i =s _a -s _b

Wherein, S _a and S _b are the dimensions of E _a and E _b respectively;

4), the angle between the connection line between an element E _a in the representative pattern and the central point of another element E _b in the representative pattern and the X axis is defined as the absolute angle difference relationship, and the relationship value R _i The value range is [-π,π], and the clockwise angle change is negative:

5), the angle between the line between an element E _a in the representative pattern and the center point of another element E _b in the representative pattern and the direction of the element E _a is defined as the relative angle difference between the elements Relationship, the value range of the relationship value R _i is [-π, π], and the clockwise angle change is a negative number:

6), the absolute value of the angle between the line between an element E _a in the representative pattern and the center point of another element E _b in the representative pattern and the direction of the element E _a is defined as the angle between the elements Symmetric angle difference relationship, the value range of the relationship value R _i is [0, π], and the angle changes of clockwise and counterclockwise are both positive numbers:

The relationship types of the three relationships are:

3-1), two relations E _v and E _d that are not angular relations, the difference between their values R _v and R _d is defined as the relation of relation difference, the value of relation value R _i :

R _i =R _v -R _d

3-2), the difference between the values R _v and R _d of two angular relationships E _v and E _d is defined as the relationship between the difference in angular relationship, and the value range of the relationship value R _i is [0, π]

3-3), the quotient of the values R _v and R _d of two relations E _v and E _d is defined as the relation value R _i of the relation quotient:

R _i =R _v /R _d

Further, the energy equation-based discrete optimization model described in step S2 is as follows:

make

与后一项

Among them, m and n are the number of elements of pattern a and pattern b for element matching respectively, X _ij is used to specify whether the i-th element in a pattern corresponds to the j-th element of another pattern, i∈m , j∈n; X _ij being 1 means that there is a corresponding relationship between element i and element j, otherwise it does not exist; V _ij is used to specify the consumption caused by the correspondence when X _ij is 1; the corresponding consumption between elements Defined as the Euclidean distance between two elements; λ is the weight used to balance the previous term in the discrete optimization model

with the latter

The latter item is used to avoid that two symmetrical elements in one pattern correspond to two asymmetrical patterns in other patterns respectively. Therefore, a list is established, and each item in the list is a four-element (p,q,g , h), where p and g indicate that the pth and qth elements in pattern a are in a symmetrical relationship, and q and h indicate that the qth and hth elements in pattern a are in a symmetrical relationship; let the length of the list be K , then the S _k of the kth list calculation formula in the latter item is defined as:

是异或操作；Where X _{p, g} is used to specify whether the p-th element in pattern a corresponds to the q-th element in pattern b, and X _{q, h} is used to specify whether the q-th element in pattern a corresponds to the q-th element in pattern b The hth element corresponds to,

is an XOR operation;

表示图案a中的每一个元素至少要与图案b中的一个元素存在对应关系；

则表示图案b中的每一个元素也至少要与图案a中的一个元素存在对应关系；

则表示当图案a中的第i个元素与图案b中的第j个元素产生对应关系后，如果图案a中的第i个元素与图案b中的不是第j个元素的其他元素产生对应，则图案b中的第j个元素不能再与图案a中不是的第i个元素的其他元素产生对应；同样如果图案b中的第j个元素与图案a中的不是第i个元素的其他元素产生对应，则图案a中的第i个元素不能再与图案b中不是的第j个元素的其他元素产生对应。At the same time, the discrete optimization model needs to meet the following three constraints:

Indicates that each element in pattern a must have a corresponding relationship with at least one element in pattern b;

Then it means that each element in the pattern b also has a corresponding relationship with at least one element in the pattern a;

It means that when the i-th element in pattern a corresponds to the j-th element in pattern b, if the i-th element in pattern a corresponds to other elements in pattern b that are not the j-th element, Then the j-th element in pattern b can no longer correspond to other elements in pattern a that are not the i-th element; similarly, if the j-th element in pattern b matches other elements in pattern a that are not the i-th element Correspondingly, the i-th element in pattern a can no longer correspond to other elements in pattern b that are not the j-th element.

Further, step S3 uses the RJMCMC sampling algorithm to obtain new patterns that can not only maintain the local characteristics of the original pattern but also have some additional changes between the patterns of different topological structures. During the acquisition process, the RJMCMC algorithm maintains a random variable The variable-dimensional Markov chain of Markov chain, the random variable continuously generated in the Markov chain gradually approaches a fixed probability distribution p in the iterative process until the probability distribution p is completely stable, and then from the Markov chain All random variables sampled in the chain satisfy this fixed probability distribution;

The described RJMCMC algorithm is as follows:

Specify the probability density function:

Among them, p represents the probability distribution, Z is the partition function that normalizes the distribution, sampling is performed when the RJMCMC algorithm does not need to calculate the partition function, and F is the energy function;

F＝F(μ,μ ^a ,μ ^b ) (4)

The probability density function of the graph vector μ is expressed as:

Among them, β is the temperature coefficient set artificially;

The specific sampling process is as follows: input the relationship graph vector μ a of pattern a and the relationship graph vector μ ^b of pattern ^b into the RJMCMC algorithm, μ ^a ∈ μ, μ ^b ∈ μ, μ ^a will be used as the initial variable of the Markov chain with e ₀ means that each variable e _i obtained by the Markov chain represents a relationship graph vector μ _i represents a new pattern;

中采样的偏移量得到，该正态分布

将由人为指定；In the process of obtaining new variables of the Markov chain in each iteration of the RJMCMC algorithm, it first randomly selects one of the roaming operations or jump operations; if the mth variable e _m in the Markov chain is obtained The m iterations select the roaming operation, then the new variable e _m of the Markov chain will add a value from the normal distribution to any item μ _i of the relationship graph vector μ represented by the previous variable em _-1

The offset of sampling in is obtained, the normal distribution

will be manually designated;

If the i-th iteration of the i-th variable x _i in the Markov chain chooses the jump operation, the candidate variable x _i ' of the new variable x _i of the Markov chain will be passed in the previous variable x _i-1 Randomly increase or decrease the dimension of the vector to obtain, specifically, in the relationship graph vector μ _{i- 1 represented by the variable x i-1} , randomly select a group of corresponding relationships of elements according to the corresponding relationship of elements calculated in step S2, and put the new The elements of the corresponding relationship are added to the patterns that lack new elements, and the four information of the new elements are randomly generated, and at the same time, the relationship between the new elements and the elements in the pattern corresponding to the relationship graph vector μ _i-1 is generated, or subtracted Remove the extra elements, and at the same time eliminate the relationship between the extra elements and the elements in the pattern corresponding to the relationship diagram vector μ _i-1 , to form a new relationship diagram vector μ _i ;

The RJMCMC algorithm selects whether to accept the candidate variable x' _i as the new variable x _i according to the acceptance and rejection probability as follows:

表示接受x_i+1作为马尔科夫链中新变量的概率，取值[0,1]，如果本次迭代选择漫移操作，则拒绝接受概率选择公式(6)，其中p(μ_i+1)是使用关系图向量μ_i+1计算得到的概率密度；p(μ_i)是使用关系图向量μ_i计算得到的概率密度；如果本次迭代选择跳跃操作，则拒绝接受概率选择公式(7)，其中q(μ_i|μ_i+1)是从关系图向量μ_i+1通过增减向量的维度得到关系图向量μ_i的概率；q(μ_i+1|μ_i)是从关系图向量μ_i通过增减向量的维度得到关系图向量μ_i+1的概率；然后RJMCMC算法从一个0-1分布中随机采样一个数字t；如果数字t小于

则RJMCMC算法接受x_i+1作为马尔科夫链中新变量；如果数字t大于

则RJMCMC算法不接受x_i+1作为马尔科夫链中新变量，保持x_i作为马尔科夫链中新变量；in

Indicates the probability of accepting x _i+1 as a new variable in the Markov chain, and takes the value [0,1]. If the roaming operation is selected for this iteration, the probability selection formula (6) is rejected, where p(μ _{i+ 1} ) is the probability density calculated by using the relationship graph vector μ _i+1 ; p(μ _i ) is the probability density calculated by using the relationship graph vector μ _i ; if the jump operation is selected for this iteration, the probability selection formula ( 7), where q(μ _i |μ _i+1 ) is the probability of obtaining the relationship graph vector μ _i from the relationship graph vector μ _i+1 by increasing or decreasing the dimension of the vector; q(μ _i+1 |μ _i ) is obtained from The relationship graph vector μ _i obtains the probability of the relationship graph vector μ _i+1 by increasing or decreasing the dimension of the vector; then the RJMCMC algorithm randomly samples a number t from a 0-1 distribution; if the number t is less than

Then the RJMCMC algorithm accepts x _i+1 as a new variable in the Markov chain; if the number t is greater than

Then the RJMCMC algorithm does not accept _xi+1 as a new variable in the Markov chain, and keeps _xi as a new variable in the Markov chain;

After a period of iterations, the probability of occurrences of the random variables of the Markov chain in the RJMCMC algorithm calculated according to formula (5) will be equal to the calculated value, and these variables will be used as the sampling results of the RJMCMC algorithm.

Further, the following energy function is constructed between the two patterns, which is used to measure the quality of the new pattern obtained by the new sampling in step S3:

Among them, μ is the relationship diagram vector of the elements in the new pattern, μ ^a and μ ^b are the relationship diagram vectors of the elements in the given pattern a and pattern b respectively; α is the weight of the first item in the energy function; in the energy function The first term F _valid (μ) is defined as:

F _valid (μ)＝μ-σ(μ) (9)

Where σ(μ) is a new set of vectors composed of the elements in the relationship diagram vector and the actual value of their relationship

则是从节点N_i所代表的元素的若干个信息中获取到计算所需要的位置信息、方向信息或者角度信息，则

表示根据节点N_i所代表的关系类型利用其相关的两个输入节点N_i1和N_i2所包含的相应的元素信息计算出该关系的实际值；如果μ中的第i项是关系图向量中一个关系与关系之间的关系值，σ(μ)中的第i项同样是该关系的实际值，则

表示根据节点N_i所代表的关系类型利用其相关的两个输入节点N_i1和N_i2所包含的关系值计算出该关系的实际值；Where σ _i (μ) represents the i-th item in the σ(μ) vector, and μ _i represents the i-th item in the μ vector, if the i-th item in μ is the information of an element in the pattern, then in σ(μ) The i-th item in μ keeps the value of the i-th item in μ still representing the same information of the element in the pattern; if the i-th item in μ is the value of the relationship between an element and an element in the pattern, the value of the i-th item in σ(μ) The i item is the actual value of the relationship;

It is to obtain the position information, direction information or angle information required for the calculation from several pieces of information of the elements represented by the node N _i , then

Indicates that according to the relationship type represented by node N _i , the actual value of the relationship is calculated by using the corresponding element information contained in the two related input nodes N _i1 and N _i2 ; if the i-th item in μ is in the relationship graph vector The relationship value between a relationship and the relationship, the i-th item in σ(μ) is also the actual value of the relationship, then

Indicates that according to the relationship type represented by node N _i , the actual value of the relationship is calculated by using the relationship values contained in the two related input nodes N _i1 and N _i2 ;

β is the weight of the second item in the energy function. Some elements in the new pattern obtained by user constraint sampling are to maintain the position, size and direction of some elements in the given pattern a and pattern b, so F _constrain (μ,μ ^a , μ ^b ) is defined as the measure of the gap between the information of the constrained elements in the graph vector of the new pattern and the information of the elements in the specified pattern:

F _constrain (μ,μ ^a ,μ ^b )＝μ{E _ca }-μ ^a {E _c ' _a }+μ{E _cb }-μ ^b {E' _cb } (11)

Where E _ca represents the set of elements in the new pattern that are constrained to keep the element information in pattern a, E' _ca represents the set of elements in pattern a that the elements in E _ca need to maintain; E _cb represents the set of elements in the new pattern that are constrained and need to maintain The element set of element information in pattern b, E' _cb means the element set in pattern b that the elements in E _cb need to keep; μ{E _ca } means that the elements in the E _ca set are in the relationship graph vector μ of the new pattern μ ^a {E' _ca } means the element information of the elements in the E' _ca set in the pattern a vector μ ^a ; μ ^b {E' _cb } means the elements in the E' _cb set are in the pattern The element information in the relationship diagram vector μ ^b of b;

γ is the weight of the third term in the energy function, and F _group (μ) is defined to measure the distance between the symmetric relation group and its mean value:

表示第h个集合中所有关系值的平均值。F _group (μ) is a one-dimensional vector composed of the gap between all symmetric relationship groups in the relationship graph vector μ and their average value. The symmetry of elements in the pattern is expressed as the relationship value in the relationship graph vector, and G indicates the symmetric relationship Sets with equal relationship values in the group, assuming that there are H sets with equal relationship values in the newly generated pattern, μ{G _h } represents the vector composed of the values of the relationship in the hth set in the relationship graph vector, H= 1～h,

Denotes the average of all relation values in the hth set.

δ is the weight of the fourth item in the energy function, randomly select a pattern from the given pattern a and pattern b as the guiding pattern of the new pattern, and the relationship graph vector of the guiding pattern is expressed as τ, so F _local (μ,τ ) is defined as a measure of the gap between the new pattern and the guide pattern:

F _local (μ,τ)=μ-τ (13)

Finally, from the energy equation, a best pattern satisfies: the actual value of the relationship in the pattern is equal to the relationship value in the relationship vector diagram μ corresponding to the pattern; the relationship value in the relationship vector diagram μ corresponding to the pattern is symmetrical to its location The average value of the relationship value in the relationship group is equal; the information of the constrained elements in the pattern is equal to the information of the elements that need to be kept; the relationship vector graph μ corresponding to the pattern is equal to the guiding relationship vector graph τ;

A method for generating a browsing interface by using patterns, comprising the following steps:

1), obtain the high-dimensional vector expression feature of the new pattern obtained by sampling, and obtain the high-dimensional vector space; the high-level vector expression feature adopts the relationship diagram vector representation of the pattern;

2), using GPLVM (Gaussian Process Latent Variable Model, Gaussian process latent variable model) to compress the high-dimensional vector space into a two-dimensional manifold space;

3) Inversely map the points in the two-dimensional manifold space to the high-dimensional space to obtain a new pattern, and perform post-processing on it;

4), generate a pattern browsing interface, the pattern browsing interface is divided into two parts, one part is the obtained two-dimensional manifold heat map, the user slides on the two-dimensional manifold heat map through the mouse, and the other part will appear corresponding new pattern.

Further, step 2) of

Compression is to use the Gaussian process hidden variable model toolbox, which reduces the dimensionality of high-dimensional vector expression features into two-dimensional vectors to form a two-dimensional manifold space, and all two-dimensional vectors are used as corresponding coordinates, and the coordinates determine the sampling results The two-dimensional manifold of the high-dimensional vector space of . At the same time, the toolbox will also calculate the covariance value of all patterns and sampling results in the high-dimensional vector space. The larger the covariance value, the redder the color displayed on the two-dimensional manifold; the smaller the covariance value, the two The bluer the color displayed on the two-dimensional manifold, the final form is a two-dimensional manifold heat map.

Further, step 3) is specifically to use the Gaussian process hidden variable model toolbox to inversely map the coordinates of the points in the two-dimensional manifold space to obtain a corresponding new relationship graph vector. A whole new diagram vector defines a whole new pattern.

Further, step 3) is to perform post-processing through the following pattern repair function to repair the symmetric relationship existing in the pattern:

Among them, μ ^* is the vector of the pattern relationship diagram satisfying the minimum value of formula (14), μ is the variable of the repair function, and μ ₀ is the vector of the relationship diagram of the pattern that needs to be repaired by this function.

The beneficial effect of the present invention is that: the genetic algorithm-based element correspondence allocation scheme of the present invention can effectively record special physical effects such as splitting and merging caused by deformation between these different topological structure patterns. The RJMCMC sampling algorithm can stably obtain a large number of new patterns between two source patterns with different topological structures, which can not only maintain the local characteristics of multiple source patterns, but also have some additional changes. The GPLVM algorithm can learn the high-dimensional space in which these sampling results are located and express this high-dimensional space through the method of low-dimensional manifolds. In this space, some new patterns with continuous changing effects can be browsed uniformly and quickly.

Description of drawings

Fig. 1 is a flow chart of a method for generating a structurally variable pattern and using the pattern to generate a browsing interface in an embodiment;

Fig. 2 is a schematic diagram of attributes of two levels of a pattern in the present embodiment;

Fig. 3 is the directed graph of the relation diagram vector of a pattern of the present embodiment;

Fig. 4 is pattern a and pattern b that need to carry out element pairing in this embodiment;

Fig. 5 is the result figure of this embodiment pairing the elements of the two patterns in Fig. 4;

Fig. 6 is the new pattern that present embodiment RJMCMC algorithm obtains;

Fig. 7 is another new pattern obtained by the RJMCMC algorithm of the present embodiment;

FIG. 8 is a schematic diagram of the browsing interface generated by patterns in this embodiment.

detailed description

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the drawings in the embodiments of the present invention.

A method for generating patterns with a variable structure as shown in Figure 1, comprising the following steps:

S1. Construct a relational graph model for the elements in the original pattern;

The original pattern described in step S1 is composed of elements. The elements of these patterns are characterized by a strong geometric arrangement. There is a certain relationship between the elements of the pattern, and there is a higher-level relationship between these relationships, that is, the relationship of the relationship. The relationship described in step S1 includes the relationship type of the element and the relationship type of the relationship, wherein the relationship type of the element Including the distance relationship between elements, the direction angle relationship between elements, and the size ratio relationship between elements; the relationship type includes the distance between elements is equal difference or proportional relationship, a certain pattern in the pattern The angles between the elements and the orientations of other elements maintain a consistent relationship, etc.

The pattern in this embodiment has six element relationship types and three relationship relationship types.

The relationship types of the six elements are:

(1) The distance between the centers of one element E ₁ in representative pattern ① and the center of another element E ₂ in representative pattern ② is defined as the Euclidean distance relationship between elements. ( ₂ ) The angle difference between the direction representing _one element E1 in the pattern and the direction representing another element E2 in the pattern is defined as the direction difference relationship between elements. The value range of the relationship value is [-π, π], and the clockwise angle change is a negative number. (3) The difference between the size of _one element E1 in the representative pattern and the size of another element _E2 in the representative pattern is defined as the size difference relationship between the elements. (4) The angle between the line representing one element E ₁ in the pattern and the center point representing another element E ₂ in the pattern and the X axis is defined as the absolute angle difference relationship. The value range of the relationship value is [-π, π], and the clockwise angle change is a negative number. (5) The angle between the line representing _one element E1 in the pattern and the center point representing another element _E2 in the pattern and the direction _of the element E1 is defined as the relative angle difference between the elements relation. The value range of the relationship value is [-π, π], and the clockwise angle change is a negative number. (6) The absolute value of the angle between the line representing one element E ₁ in the pattern and the center point of another element E ₂ in the pattern and the direction of the element E ₁ is defined as the Symmetrical angle difference relationship. The value range of the relationship value is [0, π], and the angle changes both clockwise and counterclockwise are positive numbers. The difference between (5) and (6) is whether or not to obtain the absolute value.

The relationship types of the three relationships are:

1. The difference R ₁ -R ₂ of two relations is defined as the relation of relation difference. 2. The difference between two angular relations is defined as the relation of the difference between the angular relations, and the value range of the relation value is [0, π]. 3. The quotient R ₁ /R ₂ of two relations is defined as the relation of the relation quotient.

A pattern has two layers of attributes: the first layer attribute is the element, and the second layer attribute is the arrangement. Take the pattern in the left frame in Figure 2 as an example, the part in the dotted line frame of the pattern has two layers of attributes, the first layer attribute is the element, and the second-level attribute is the arrangement, which is represented by the distance relationship between elements.

Step S1 uses a relational graph model to describe the relationship between elements in the pattern and the relationship between these relationships.

A relational graph model can be represented by a relational graph vector. Specifically, it is assumed that μ is a graph vector of the elements in a pattern. The relationship graph vector is a one-dimensional vector consisting of three parts, the first part of which is the position (x, y), orientation θ, and size s of each element in the pattern in turn, and the second part contains The value of the relationship between elements and elements, and the third part is the value of the relationship between elements. The relationship value (including the relationship value and the relationship value of the relationship) is uniformly represented by r in the relationship graph vector:

μ=(x ₁ ,y ₁ ,θ ₁ ,s ₁ ,x ₂ ,y ₂ ,θ ₂ ,s ₂ ,...,r ₁ ,r ₂ ,r ₃ ,...)(1)

进行表示，有向图的节点N＝E∪R，其中E是图案中元素的集合，第i个元素表示为E_i＝(x_i,y_i,θ_i,s_i)，E_i∈E，i表示元素的数量；R是图案中关系的集合，R＝R^E∪R^R，R^E是元素关系集合，R^R是关系间的关系集合，每一个关系有相应的关系值，其中第i个关系的关系值表示为R_i＝(r_i)，R_i∈R；有向图的边A＝{(N_i1,R_i),(N_i2,R_i)}_i＝1...k+l，其中k是关系图模型中元素关系的数量，l是关系的关系的数量。根据节点N_i1和节点N_i2是与关系R_i相关的两个元素E₁、E₂或者关系R₁、R₂，其中R_i的值由节点N_i1和节点N_i2包含的值计算得到。Relational graph models through directed graphs

For representation, the node N=E∪R of the directed graph, where E is the set of elements in the pattern, and the i-th element is expressed as E _i =( _xi ,y _i ,θ _i ,s _i ), E _i ∈ E , i represents the number of elements; R is the set of relations in the pattern, R = R ^E ∪ ^{R R} , R ^E is the set of element relations, R ^R is the set of relations between relations, and each relation has a corresponding relation value, among which The relationship value of _i relationship is expressed as R _i =(ri ),R _i ∈R; the edge A of the directed graph={(N _i1 ,R _i ),(N _i2 ,R _i )} _{i=1.. .k+l} , where k is the number of element relations in the relational graph model and l is the number of relations of relations. According to the node N _i1 and the node N _i2 are two elements E ₁ , E ₂ or the relationship R ₁ , R ₂ related to the relationship R _i , where the value of R _i is calculated from the values contained in the node N _i1 and the node N _i2 .

以及

其中E_j∈E。Record all element information or relationship values of the node N _i corresponding to the relationship graph vector as

as well as

where E _j ∈ E.

Specifically, there are 6 element relationship types and 3 relationship relationship types in the pattern, where the 6 element relationship types are:

1), the distance between an element E _a in the representative pattern and the center of another element E _b in the representative pattern is defined as the Euclidean distance relationship between the elements, E _a ∈ E, E _b ∈ E, where The value of relation value R _i is:

Wherein, (x _a , y _a ) is the position of element E _a , (x _a , y _b ) is the position of element E _b ;

2), the angle difference between an element E _a in the representative pattern and the direction of another element E _b in the representative pattern is defined as the direction difference relationship between the elements, and the value range of the relation value R _i is [- π,π], clockwise angle changes are negative:

Among them, θ _a and θ _b are the orientations of E _a and E _b respectively;

3), the difference between the size of an element E _a in the representative pattern and the size of another element E _b in the representative pattern is defined as the size difference relationship between the elements, the relationship value R _i :

R _i =s _a -s _b

Wherein, S _a and S _b are the dimensions of E _a and E _b respectively;

4), the angle between the connection line between an element E _a in the representative pattern and the central point of another element E _b in the representative pattern and the X axis is defined as the absolute angle difference relationship, and the relationship value R _i The value range is [-π,π], and the clockwise angle change is negative:

5), the angle between the line between an element E _a in the representative pattern and the center point of another element E _b in the representative pattern and the direction of the element E _a is defined as the relative angle difference between the elements Relationship, the value range of the relationship value R _i is [-π, π], and the clockwise angle change is a negative number:

6), the absolute value of the angle between the line between an element E _a in the representative pattern and the center point of another element E _b in the representative pattern and the direction of the element E _a is defined as the angle between the elements Symmetric angle difference relationship, the value range of the relationship value R _i is [0, π], and the angle changes of clockwise and counterclockwise are both positive numbers:

The relationship types of the three relationships are:

3-1), two relations E _v and E _d that are not angular relations, the difference between their values R _v and R _d is defined as the relation of relation difference, the value of relation value R _i :

R _i =R _v -R _d

3-2), the difference between the values R _v and R _d of two angular relationships E _v and E _d is defined as the relationship between the difference in angular relationship, and the value range of the relationship value R _i is [0, π]

3-3), the quotient of the values R _v and R _d of two relations E _v and E _d is defined as the relation value R _i of the relation quotient:

R _i =R _v /R _d

Figure 3 is a directed graph of the relationship graph vector of a pattern. The relationship between the elements in the pattern and the distance difference is the relationship type of the first element; the difference relationship between the distances is the relationship type of the third relationship. .

S2. Matching elements between different topological patterns;

A discrete optimization model based on the following energy equation was constructed to find corresponding elements between two patterns:

与后一项

Among them, m and n are the number of elements of pattern a and pattern b for element matching respectively, X _ij is used to specify whether the i-th element in a pattern corresponds to the j-th element of another pattern, i∈m , j∈n; X _ij being 1 means that there is a corresponding relationship between element i and element j, otherwise it does not exist; V _ij is used to specify the consumption caused by the correspondence when X _ij is 1; the corresponding consumption between elements Defined as the Euclidean distance between two elements; λ is the weight used to balance the previous term in the discrete optimization model

with the latter

The latter item is used to avoid that two symmetrical elements in one pattern correspond to two asymmetrical patterns in other patterns respectively. Therefore, a list is established, and each item in the list is a four-element (p,q,g , h), where p and g indicate that the p-th and q-th elements in pattern a are in a symmetrical relationship, and q and h indicate that the q-th and h-th elements in pattern a are in a symmetrical relationship. Suppose the length of the list is K, then the S _k of the kth list calculation formula in the latter item is defined as:

是异或操作；Among them, X _p , _g are used to specify whether the pth element in pattern a corresponds to the qth element in pattern b, and X _q , _h are used to specify whether the qth element in pattern a corresponds to the pattern b's The hth element corresponds to,

is an XOR operation;

表示图案a中的每一个元素至少要与图案b中的一个元素存在对应关系；

则表示图案b中的每一个元素也至少要与图案a中的一个元素存在对应关系；

则表示当图案a中的第i个元素与图案b中的第j个元素产生对应关系后，如果图案a中的第i个元素与图案b中的不是第j个元素的其他元素产生对应，则图案b中的第j个元素不能再与图案a中不是的第i个元素的其他元素产生对应；同样如果图案b中的第j个元素与图案a中的不是第i个元素的其他元素产生对应，则图案a中的第i个元素不能再与图案b中不是的第j个元素的其他元素产生对应。At the same time, the discrete optimization model needs to meet the following three constraints:

Indicates that each element in pattern a must have a corresponding relationship with at least one element in pattern b;

Then it means that each element in the pattern b also has a corresponding relationship with at least one element in the pattern a;

It means that when the i-th element in pattern a corresponds to the j-th element in pattern b, if the i-th element in pattern a corresponds to other elements in pattern b that are not the j-th element, Then the j-th element in pattern b can no longer correspond to other elements in pattern a that are not the i-th element; similarly, if the j-th element in pattern b matches other elements in pattern a that are not the i-th element Correspondingly, the i-th element in pattern a can no longer correspond to other elements in pattern b that are not the j-th element.

Fig. 4 is two patterns that need to carry out element pairing in the present embodiment, and Fig. 5 is the result that element pairing is carried out to the element of Fig. 4 two patterns by discrete optimization model, each element in the pattern in the figure has label, There is a corresponding relationship between the elements with the same label in the left and right patterns. According to the positional relationship of the elements in the two patterns, the discrete optimization model allows one point in one pattern to correspond to multiple points in the other pattern. In Figure 4, one point on the inner circle of the pattern on the left corresponds to two points on the inner circle of the pattern on the right.

S3, based on the RJMCMC algorithm, sampling between different topological patterns to obtain new patterns;

The following energy function is constructed between the two patterns to measure the quality of the newly sampled pattern:

F(μ,μ ^a ,μ ^b )＝||αF _valid (μ)|| ² +||βF _c o _nstrain (μ,μ ^a ,μ ^b )|| ² +||γF _gr o _up (μ) || ² +||δF _l o _cal (μ,τ)|| ²

stμ{R _ca }＝μ ^a {R _c ′ _a }andμ{R _cb }＝μ ^b {R _c ′ _b } (4)

Among them, μ is the relationship diagram vector of the elements in the new pattern, and μ ^a and μ ^b are the relationship diagram vectors of the elements in the given two patterns respectively. α is the weight of the first term in the energy function; the first term F _valid (μ) in the energy function is defined as:

F _valid (μ)＝μ-σ(μ) (5)

Where σ(μ) is a new vector composed of the elements in the relationship diagram vector and the actual value of their relationship

则是从节点N_i所代表的元素的若干个信息中获取到计算所需要的位置信息、方向信息或者角度信息，则

表示根据节点N_i所代表的关系类型利用其相关的两个输入节点N_i1和N_i2所包含的相应的元素信息计算出该关系的实际值；如果μ中的第i项是关系图向量中一个关系与关系之间的关系值，σ(μ)中的第i项同样是该关系的实际值，则

表示根据节点N_i所代表的关系类型利用其相关的两个输入节点N_i1和N_i2所包含的关系值计算出该关系的实际值；Where σ _i (μ) represents the i-th item in the σ(μ) vector, and μ _i represents the i-th item in the μ vector, if the i-th item in μ is the information of an element in the pattern, then in σ(μ) The i-th item in μ keeps the value of the i-th item in μ still representing the same information of the element in the pattern; if the i-th item in μ is the value of the relationship between an element and an element in the pattern, the value of the i-th item in σ(μ) The i item is the actual value of the relationship;

It is to obtain the position information, direction information or angle information required for the calculation from several pieces of information of the elements represented by the node N _i , then

Indicates that according to the relationship type represented by node N _i , the actual value of the relationship is calculated by using the corresponding element information contained in the two related input nodes N _i1 and N _i2 ; if the i-th item in μ is in the relationship graph vector The relationship value between a relationship and the relationship, the i-th item in σ(μ) is also the actual value of the relationship, then

Indicates that according to the relationship type represented by node N _i , the actual value of the relationship is calculated by using the relationship values contained in the two related input nodes N _i1 and N _i2 ;

β is the weight of the second item in the energy function. Some elements in the new pattern obtained by user constraint sampling are to maintain the position, size and direction of some elements in the given pattern a and pattern b, so F _constrain (μ,μ ^a , μ ^b ) is defined as the measure of the gap between the information of the constrained elements in the graph vector of the new pattern and the information of the elements in the specified pattern:

F _constrain (μ,μ ^a ,μ ^b )＝μ{E _ca }-μ ^a {E' _ca }+μ{E _cb }-μ ^b {E' _cb } (11)

Where E _ca represents the set of elements in the new pattern that are constrained to keep the element information in pattern a, E' _ca represents the set of elements in pattern a that the elements in E _ca need to maintain; E _cb represents the set of elements in the new pattern that are constrained and need to maintain The element set of element information in pattern b, E' _cb means the element set in pattern b that the elements in E _cb need to keep; μ{E _ca } means that the elements in the E _ca set are in the relationship graph vector μ of the new pattern μ ^a {E' _ca } means the element information of the elements in the E' _ca set in the pattern a vector μ ^a ; μ ^b {E' _cb } means the elements in the E' _cb set are in the pattern The element information in the relationship diagram vector μ ^b of b;

γ is the weight of the third term in the energy function, and F _group (μ) is defined to measure the distance between the symmetric relation group and its mean value:

表示第h个集合中所有关系值的平均值。F _group (μ) is a one-dimensional vector composed of the gap between all symmetric relationship groups in the relationship graph vector μ and their average value. The symmetry of elements in the pattern is expressed as the relationship value in the relationship graph vector, and G indicates the symmetric relationship Sets with equal relationship values in the group, assuming that there are H sets with equal relationship values in the newly generated pattern, μ{G _h } represents the vector composed of the values of the relationship in the hth set in the relationship graph vector, H= 1～h,

Denotes the average of all relation values in the hth set.

δ is the weight of the fourth item in the energy function, randomly select a pattern from the given pattern a and pattern b as the guiding pattern of the new pattern, and the relationship graph vector of the guiding pattern is expressed as τ, so F _local (μ,τ ) is defined as a measure of the gap between the new pattern and the guide pattern:

F _local (μ,τ)=μ-τ (13)

Finally, from the energy equation, a best pattern satisfies: the actual value of the relationship in the pattern is equal to the relationship value in the relationship vector diagram μ corresponding to the pattern; the relationship value in the relationship vector diagram μ corresponding to the pattern is symmetrical to its location The average value of the relationship value in the relationship group is equal; the information of the constrained elements in the pattern is equal to the information of the elements that need to be kept; the relationship vector graph μ corresponding to the pattern is equal to the guiding relationship vector graph τ;

Further, the RJMCMC sampling algorithm is used to obtain a large number of new patterns that can not only maintain the local characteristics in multiple source patterns but also have some additional changes between patterns of different topological structures; the RJMCMC algorithm maintains a random variable The dimension can be A variable Markov chain, in which the continuously generated random variable gradually approaches a fixed probability distribution p until it is completely stable. Then all the random variables sampled from the Markov chain satisfy this fixed probability distribution. Therefore, the RJMCMC algorithm sets such a probability density function:

where F is the energy function:

F＝F(μ,μ ^a ,μ ^b ) (11)

The probability density function of the graph vector μ can be expressed as

Z is the partition function that normalizes the distribution, usually complex, but the RJMCMC algorithm can sample without computing the partition function. β is a temperature coefficient. According to the energy equation calculated by the RJMCMC algorithm, the value of β is artificially set.

Input the relationship graph vector μ a of pattern a and the relationship graph vector μ ^b of pattern ^b into the RJMCMC algorithm, μ ^a ∈ μ, μ ^b ∈ μ, μ ^a will be represented by x ₀ as the initial variable of the Markov chain, Marko Each variable x _i obtained by the Markov chain represents a relational graph vector μ _i ; in the process of obtaining new variables of the Markov chain in each iteration of the RJMCMC algorithm, it first randomly selects one of the roaming operations or jumping operations operate.

Each variable e _i obtained by the Markov chain represents a relationship graph vector μ _i also represents a new pattern;

中采样的偏移量得到。该正态分布

将由人为指定。In the process of obtaining new variables of the Markov chain in each iteration of the RJMCMC algorithm, it first randomly selects one of the roaming operations or jump operations; if the mth variable e _m in the Markov chain is obtained The m iterations select the roaming operation, then the new variable e _m of the Markov chain will add a value from the normal distribution to any item μ _i of the relationship graph vector μ represented by the previous variable em _-1

The offset of the sample in is obtained. The normal distribution

will be specified manually.

If the i-th iteration of the i-th variable x _i in the Markov chain chooses the jump operation, the candidate variable x _i ' of the new variable x _i of the Markov chain will be passed in the previous variable x _i-1 Randomly increase or decrease the dimension of the vector to obtain, specifically, in the relationship graph vector μ _{i- 1 represented by the variable x i-1} , randomly select a group of corresponding relationships of elements according to the corresponding relationship of elements calculated in step S2, and put the new The elements added to the pattern lacking new elements in the corresponding relationship, the four information of the new elements are randomly generated. At the same time, the relationship between the new elements and the elements in the pattern corresponding to the relationship diagram vector μ _i-1 is generated, or the excess elements are subtracted, and the relationship between the excess elements and the relationship diagram vector μ _i-1 is eliminated at the same time The element relationship in the pattern forms a new relationship graph vector μ _i ;

The RJMCMC algorithm chooses whether to accept the candidate variable x _i ' as a new variable x _i according to the acceptance and rejection probability as follows:

表示接受x_i+1作为马尔科夫链中新变量的概率，取值[0,1]，如果本次迭代选择漫移操作，则拒绝接受概率选择公式(6)，其中p(μ_i+1)是使用关系图向量μ_i+1计算得到的概率密度；p(μ_i)是使用关系图向量μ_i计算得到的概率密度；如果本次迭代选择跳跃操作，则拒绝接受概率选择公式(7)，其中q(μ_i|μ_i+1)是从关系图向量μ_i+1通过增减向量的维度得到关系图向量μ_i的概率；q(μ_i+1|μ_i)是从关系图向量μ_i通过增减向量的维度得到关系图向量μ_i+1的概率；然后RJMCMC算法从一个0-1分布中随机采样一个数字t；如果数字t小于

则RJMCMC算法接受x_i+1作为马尔科夫链中新变量；如果数字t大于

则RJMCMC算法不接受x_i+1作为马尔科夫链中新变量，保持x_i作为马尔科夫链中新变量。in

Indicates the probability of accepting x _i+1 as a new variable in the Markov chain, and takes the value [0,1]. If the roaming operation is selected for this iteration, the probability selection formula (6) is rejected, where p(μ _{i+ 1} ) is the probability density calculated by using the relationship graph vector μ _i+1 ; p(μ _i ) is the probability density calculated by using the relationship graph vector μ _i ; if the jump operation is selected for this iteration, the probability selection formula ( 7), where q(μ _i |μ _i+1 ) is the probability of obtaining the relationship graph vector μ _i from the relationship graph vector μ _i+1 by increasing or decreasing the dimension of the vector; q(μ _i+1 |μ _i ) is obtained from The relationship graph vector μ _i obtains the probability of the relationship graph vector μ _i+1 by increasing or decreasing the dimension of the vector; then the RJMCMC algorithm randomly samples a number t from a 0-1 distribution; if the number t is less than

Then the RJMCMC algorithm accepts x _i+1 as a new variable in the Markov chain; if the number t is greater than

Then the RJMCMC algorithm does not accept _xi+1 as a new variable in the Markov chain, and keeps _xi as a new variable in the Markov chain.

After a period of iterations, the probability of occurrences of the random variables of the Markov chain in the RJMCMC algorithm calculated according to formula (5) will be equal to the calculated value, and these variables will be used as the sampling results of the RJMCMC algorithm.

得到变量维度为n的X′₁，RJMCMC算法经过漫移操作相继得到X′₂、X′₃、X′₄，接下来跳转操作

得到了变量维度为m的X′₅.RJMCMC算法再经过漫移操作相继得到变量X′₆、X′₇、X′₈，接下来采取跳转操作

得到另外维度的变量。这些变量将作为RJMCMC算法采样得到的结果。图6和图7分别是图4中的两个图案进行RJMCMC算法得到的两个新图案，分别为图案X3′和图案X7′。The RJMCMC algorithm undergoes a jump operation during the iterative process

Obtain X′ ₁ with a variable dimension of n, the RJMCMC algorithm obtains X′ ₂ , X′ ₃ , and X′ ₄ successively through the roaming operation, and then jumps

Obtained X′ ₅ with a variable dimension of m. The RJMCMC algorithm obtains the variables X′ ₆ , X′ ₇ , and X′ ₈ successively through the roaming operation, and then takes the jump operation

Get the variable of another dimension. These variables will be taken as the results of RJMCMC algorithm sampling. Fig. 6 and Fig. 7 are respectively two new patterns obtained by performing the RJMCMC algorithm on the two patterns in Fig. 4, which are pattern X3' and pattern X7' respectively.

As shown in the figure, the radius line of the circle in the figure represents the direction of the element, and the number of elements on the inner circle of the patterns in Figures 6 and 7 is different from the elements on the inner circle in the given two patterns in Figure 4 .

A method for generating a browsing interface using the pattern with variable structure, comprising the following steps:

1), obtain the high-dimensional vector expression feature of the new pattern obtained by sampling;

Since the new patterns sampled by the RJMCMC algorithm have their own relationship graph vectors, the high-level vector expression features of the new patterns can be directly represented by the relationship graph vectors of the pattern.

2), using GPLVM (Gaussian Process Latent Variable Model Gaussian process latent variable model) to compress the above high-dimensional vector space into a two-dimensional manifold space;

Gaussian Process Hidden Variable Model Toolbox was used for spatial dimensionality reduction. This tool can directly compress and reduce the high-dimensional vector expression features of new patterns into a two-dimensional vector for representation. All two-dimensional vectors as coordinates define a two-dimensional manifold of the high-dimensional vector space of the sampling results. At the same time, the toolbox will also calculate the covariance value of all patterns and sampling results in the high-dimensional vector space. The larger the covariance value, the redder the color displayed on the two-dimensional manifold; the smaller the covariance value, the two The bluer the color displayed on the two-dimensional manifold, the final form is a two-dimensional manifold heat map.

3) Inversely map the points in the two-dimensional manifold space to the high-dimensional space to obtain a new pattern, and perform post-processing on it;

The following pattern repair function is constructed for post-processing to repair the symmetry relationship existing in the pattern

where μ is the variable of the inpainting function, and _μ0 is the graph vector of patterns that need to be inpainted by this function.

S7. Generate a pattern browsing interface: the pattern browsing interface is divided into two parts, one part is the obtained two-dimensional manifold heat map, the user slides the mouse on the two-dimensional manifold heat map, and the other part will appear corresponding new pattern.

As shown in Figure 8, the heat map of the two-dimensional manifold is shown on the left, and the new pattern of the corresponding high-dimensional space is shown on the right;

The user's browsing method is as follows: the user slides the mouse on the two-dimensional manifold heat map on the left side of the interface, and the corresponding pattern appears on the right side of the interface. As shown in Figure 8, the two-dimensional manifold heat map is displayed on the left side of the interface. When the user drags the mouse on the map at will, the corresponding pattern will appear on the right side of the interface.

The technical solutions provided by the embodiments of the present invention have been described in detail above. In the present invention, specific examples have been used to illustrate the principles and implementation modes of the present invention. The descriptions of the above embodiments are only used to help understand the methods and methods of the present invention. core idea; at the same time, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific implementation and scope of application. In summary, the content of this specification should not be construed as limiting the present invention .

Claims (8)

1. A method for generating patterns with variable structure, comprising the following steps: S1. Construct a relationship diagram model for the elements in the pattern; the constructed relationship diagram model is used to describe the relationship between the elements in the pattern and the relationship between the relationships; The relationship diagram model includes a relationship diagram vector, wherein a relationship diagram vector represents a pattern; the relationship diagram vector is a one-dimensional vector mainly composed of three parts, wherein the first part is the position of each element in the pattern in turn (x _i , y _i ), orientation θ _i and size s _i , the second part contains the value of the relationship between elements, the third part is the relationship value r, and the relationship value r includes the element The relationship value with the element and the relationship value of the relationship, the relationship graph vector μ is as follows: μ=(x ₁ ,y ₁ ,θ ₁ ,s ₁ ,x ₂ ,y ₂ ,θ ₂ ,s ₂ ,..., _xi ,y _i ,θ _i ,s _i ,r ₁ ,r ₂ ,r ₃ ,...,r _i ) (1) Relational graph models through directed graphs

For representation, the node N=E∪R of the directed graph, where E is the set of elements in the pattern, and the i-th element is expressed as E _i =( _xi ,y _i ,θ _i ,s _i ), E _i ∈ E , i represents the number of elements; R is the set of relations in the pattern, R=RE ∪R ^R , R ^E is the set of element relations, ^{R R is} the set of relations between relations, and each relation has a corresponding relation value, among which The relationship value of _i relationship is expressed as R _i =(ri ),R _i ∈R; the edge A of the directed graph={(N _i1 ,R _i ),(N _i2 ,R _i )} _{i=1.. .k+l} , where k is the number of element relationships in the relationship graph model, and l is the number of relationships in the relationship; record all the element information or relationship values of the node N _i corresponding to the relationship graph vector as

if N _i =E _j ∈ E and

if N _i = R _j ∈ R, where E _j ∈ E; Specifically, there are 6 relationship types of elements and 3 relationship types of relationships, among which, the relationship types of 6 elements are: 1), the distance between an element E _a in the representative pattern and the center of another element E _b in the representative pattern is defined as the Euclidean distance relationship between the elements, wherein the value of the relationship value R _i is:

Wherein, (x _a , y _a ) is the position of element E _a , (x _a , y _b ) is the position of element E _b ; 2), the angle difference between an element E _a in the representative pattern and the direction of another element E _b in the representative pattern is defined as the direction difference relationship between the elements, and the value range of the relation value R _i is [- π,π], clockwise angle changes are negative:

Among them, θ _a and θ _b are the orientations of E _a and E _b respectively; 3), the difference between the size of an element E _a in the representative pattern and the size of another element E _b in the representative pattern is defined as the size difference relationship between the elements, the relationship value R _i : R _i =s _a -s _b Among them, s _a and s _b are the dimensions of E _a and E _b respectively; 4), the angle between the connection line between an element E _a in the representative pattern and the central point of another element E _b in the representative pattern and the X axis is defined as the absolute angle difference relationship, and the relationship value R _i The value range is [-π,π], and the clockwise angle change is negative:

5), the angle between the line between an element E _a in the representative pattern and the center point of another element E _b in the representative pattern and the direction of the element E _a is defined as the relative angle difference between the elements Relationship, the value range of the relationship value R _i is [-π, π], and the clockwise angle change is a negative number:

6), the absolute value of the angle between the line between an element E _a in the representative pattern and the center point of another element E _b in the representative pattern and the direction of the element E _a is defined as the angle between the elements Symmetric angle difference relationship, the value range of the relationship value R _i is [0, π], and the angle changes of clockwise and counterclockwise are both positive numbers:

The relationship types of the three relationships are: 3-1), two relations E _v and E _d that are not angular relations, the difference between their values R _v and R _d is defined as the relation of relation difference, the value of relation value R _i : R _i =R _v -R _d 3-2), the difference between the values R _v and R _d of two angular relationships E _v and E _d is defined as the relationship between the difference in angular relationship, and the value range of the relationship value R _i is [0, π]

3-3), the quotient of the values R _v and R _d of two relations E _v and E _d is defined as the relation value R _i of the relation quotient: R _i =R _v /R _d ; S2. Using a discrete optimization model of the energy equation to match elements between different topological patterns; S3. Based on the RJMCMC algorithm, sampling between patterns of different topological structures to obtain new patterns. 2. A kind of pattern generation method with variable structure according to claim 1, characterized in that: the discrete optimization model based on energy equation described in step S2 is as follows:

make

Among them, m and n are the number of elements of pattern a and pattern b for element matching respectively, X _ij is used to specify whether the i-th element in a pattern corresponds to the j-th element of another pattern, i∈m , j∈n; X _ij being 1 means that there is a corresponding relationship between element i and element j, otherwise it does not exist; V _ij is used to specify the consumption caused by the correspondence when X _ij is 1; the corresponding consumption between elements Defined as the Euclidean distance between two elements; λ is the weight used to balance the previous term in the discrete optimization model

with the latter

The latter item is used to avoid that two symmetrical elements in one pattern correspond to two asymmetrical patterns in other patterns respectively. Therefore, a list is established, and each item in the list is a four-element (p,q,g , h), where p and g indicate that the pth and qth elements in pattern a are in a symmetrical relationship, and q and h indicate that the qth and hth elements in pattern a are in a symmetrical relationship; let the length of the list be K , then the S _k of the kth list calculation formula in the latter item is defined as:

Where X _{p, g} is used to specify whether the p-th element in pattern a corresponds to the q-th element in pattern b, and X _{q, h} is used to specify whether the q-th element in pattern a corresponds to the q-th element in pattern b The hth element corresponds to,

is an XOR operation; At the same time, the discrete optimization model needs to meet the following three constraints:

Indicates that each element in pattern a must have a corresponding relationship with at least one element in pattern b;

Then it means that each element in the pattern b also has a corresponding relationship with at least one element in the pattern a;

It means that when the i-th element in pattern a corresponds to the j-th element in pattern b, if the i-th element in pattern a corresponds to other elements in pattern b that are not the j-th element, Then the j-th element in pattern b can no longer correspond to other elements in pattern a that are not the i-th element; similarly, if the j-th element in pattern b matches other elements in pattern a that are not the i-th element Correspondingly, the i-th element in pattern a can no longer correspond to other elements in pattern b that are not the j-th element. 3. a kind of variable pattern generation method according to claim 1, is characterized in that, the RJMCMC algorithm described in step S3 is as follows: Specify the probability density function:

Among them, p represents the probability distribution, Z is the partition function that normalizes the distribution, sampling is performed when the RJMCMC algorithm does not need to calculate the partition function, and F is the energy function; F＝F(μ,μ ^a ,μ ^b ) (4) The probability density function of the graph vector μ is expressed as:

Among them, β is the temperature coefficient set artificially; The specific sampling process is as follows: input the relationship graph vector μ a of pattern a and the relationship graph vector μ ^b of pattern ^b into the RJMCMC algorithm, μ ^a ∈ μ, μ ^b ∈ μ, μ ^a will be used as the initial variable of the Markov chain with e ₀ means that each variable e _i obtained by the Markov chain represents a relationship graph vector μ _i represents a new pattern; In the process of obtaining new variables of the Markov chain in each iteration of the RJMCMC algorithm, it first randomly selects one of the roaming operations or jump operations; if the m'th variable e _m' in the Markov chain is obtained The mth iteration chooses the roaming operation, then the new variable e _{m' of} the _Markov chain will add a from normal distribution

The offset of sampling in is obtained, the normal distribution

will be manually designated; If the i-th iteration of the i-th variable x _i in the Markov chain chooses the jump operation, the candidate variable x _i ' of the new variable x _i of the Markov chain will be passed in the previous variable x _i-1 Randomly increase or decrease the dimension of the vector to obtain, specifically, in the relationship graph vector μ _{i- 1 represented by the variable x i-1} , randomly select a group of corresponding relationships of elements according to the corresponding relationship of elements calculated in step S2, and put the new The elements of the corresponding relationship are added to the patterns that lack new elements, and the four information of the new elements are randomly generated, and at the same time, the relationship between the new elements and the elements in the pattern corresponding to the relationship graph vector μ _i-1 is generated, or subtracted Remove the extra elements, and at the same time eliminate the relationship between the extra elements and the elements in the pattern corresponding to the relationship diagram vector μ _i-1 , to form a new relationship diagram vector μ _i ; The RJMCMC algorithm chooses whether to accept the candidate variable x _i ' as a new variable x _i according to the acceptance and rejection probability as follows:

in

Indicates the probability of accepting x _i+1 as a new variable in the Markov chain, and takes the value [0,1]. If the roaming operation is selected for this iteration, the probability selection formula (6) is rejected, where p(μ _{i+ 1} ) is the probability density calculated by using the relationship graph vector μ _i+1 ; p(μ _i ) is the probability density calculated by using the relationship graph vector μ _i ; if the jump operation is selected for this iteration, the probability selection formula ( 7), where q(μ _i |μ _i+1 ) is the probability of obtaining the relationship graph vector μ _i from the relationship graph vector μ _i+1 by increasing or decreasing the dimension of the vector; q(μ _i+1 |μ _i ) is obtained from The relationship graph vector μ _i obtains the probability of the relationship graph vector μ _i+1 by increasing or decreasing the dimension of the vector; then the RJMCMC algorithm randomly samples a number t from a 0-1 distribution; if the number t is less than

Then the RJMCMC algorithm accepts x _i+1 as a new variable in the Markov chain; if the number t is greater than

Then the RJMCMC algorithm does not accept _xi+1 as a new variable in the Markov chain, and keeps _xi as a new variable in the Markov chain; After a period of iterations, the probability of occurrences of the random variables of the Markov chain in the RJMCMC algorithm calculated according to formula (5) will be equal to the calculated value, and these variables will be used as the sampling results of the RJMCMC algorithm. 4. A method for generating patterns with a variable structure according to claim 1, characterized in that: the following energy function is constructed between the two patterns for measuring the quality of the new pattern obtained by the new sampling in step S3:

Wherein, μ is the relation diagram vector, and μ ^a and μ ^b are the relation diagram vectors of elements in the given pattern a and pattern b respectively; α is the weight of the first term in the energy function; the first term F _valid ( μ) is defined as: F _valid (μ)＝μ-σ(μ) (9) Where σ(μ) is a new set of vectors composed of the elements in the relationship diagram vector and the actual value of their relationship

Where σ _i (μ) represents the i-th item in the σ(μ) vector, and μ _i represents the i-th item in the μ vector, if the i-th item in μ is the information of an element in the pattern, then in σ(μ) The i-th item in μ keeps the value of the i-th item in μ still representing the same information of the element in the pattern; if the i-th item in μ is the value of the relationship between an element and an element in the pattern, the value of the i-th item in σ(μ) The i item is the actual value of the relationship;

It is to obtain the position information, direction information or angle information required for the calculation from several pieces of information of the elements represented by the node N _i , then

Indicates that according to the relationship type represented by node N _i , the actual value of the relationship is calculated by using the corresponding element information contained in the two related input nodes N _i1 and N _i2 ; if the i-th item in μ is in the relationship graph vector The relationship value between a relationship and the relationship, the i-th item in σ(μ) is also the actual value of the relationship, then

Indicates that according to the relationship type represented by node N _i , the actual value of the relationship is calculated by using the relationship values contained in the two related input nodes N _i1 and N _i2 ; β is the weight of the second item in the energy function. Some elements in the new pattern obtained by user constraint sampling are to maintain the position, size and direction of some elements in the given pattern a and pattern b, so F _constrain (μ,μ ^a , μ ^b ) is defined as the measure of the gap between the information of the constrained elements in the graph vector of the new pattern and the information of the elements in the specified pattern:

Where E _ca represents the set of elements in the new pattern that are constrained to keep the element information in pattern a, E' _ca represents the set of elements in pattern a that the elements in E _ca need to maintain; E _cb represents the set of elements in the new pattern that are constrained and need to maintain The element set of element information in pattern b, E' _cb means the element set in pattern b that the elements in E _cb need to keep; μ{E _ca } means that the elements in the E _ca set are in the relationship graph vector μ of the new pattern μ ^a {E' _ca } means the element information of the elements in the E' _ca set in the pattern a vector μ ^a ; μ ^b {E' _cb } means the elements in the E' _cb set are in the pattern The element information in the relationship diagram vector μ ^b of b; γ is the weight of the third term in the energy function, and F _group (μ) is defined to measure the distance between the symmetric relation group and its mean value:

F _group (μ) is a one-dimensional vector composed of the gap between all symmetric relationship groups in the relationship graph vector μ and their average value. The symmetry of elements in the pattern is expressed as the relationship value in the relationship graph vector, and G indicates the symmetric relationship Sets with equal relationship values in the group, assuming that there are H sets with equal relationship values in the newly generated pattern, μ{G _h } represents the vector composed of the values of the relationship in the hth set in the relationship graph vector, H= 1～h,

Indicates the average value of all relationship values in the hth set; δ is the weight of the fourth item in the energy function, randomly select a pattern from the given pattern a and pattern b as the guiding pattern of the new pattern, and the relationship graph vector of the guiding pattern is expressed as τ, so F _local (μ,τ ) is defined as a measure of the gap between the new pattern and the guide pattern: F _local (μ,τ)=μ−τ (13). 5. A method for pattern generation browsing interface, said pattern is generated by the pattern generation method with variable structure according to claim 4, characterized in that, comprising the following steps: 1), obtain the high-dimensional vector expression feature of the new pattern that sampling obtains, obtain high-dimensional vector space; Described high-dimensional vector expression feature adopts the relation graph vector representation of this pattern; 2), using the Gaussian process hidden variable model to compress the high-dimensional vector space into a two-dimensional manifold space; 3) Inversely map the points in the two-dimensional manifold space to the high-dimensional space to obtain a new pattern, and perform post-processing on it; 4), generate a pattern browsing interface, the pattern browsing interface is divided into two parts, one part is the obtained two-dimensional manifold heat map, the user slides on the two-dimensional manifold heat map through the mouse, and the other part will appear corresponding new pattern. 6. the method for pattern generation browsing interface according to claim 5, is characterized in that, the compression of step 2) is to use Gaussian process latent variable model toolbox, and this toolbox will high-dimensional vector expression feature dimension reduction into two-dimensional vector , forming a two-dimensional manifold space, all two-dimensional vectors are used as corresponding coordinates, and the coordinates determine the two-dimensional manifold of the high-dimensional vector space of the sampling result. 7. the method for pattern generation browsing interface according to claim 5, is characterized in that, step 3) specifically is by Gaussian process hidden variable model toolbox the coordinate inverse mapping of the point in the two-dimensional manifold space to obtain corresponding New Diagram Vector, a brand new diagram vector defines a brand new pattern. 8. the method for pattern generation browsing interface according to claim 5, is characterized in that, step 3) is to carry out post-processing by following pattern repair function, is used to repair the symmetrical relationship that exists in the pattern:

Among them, μ ^* is the vector of the pattern relationship diagram satisfying the minimum value of formula (14), μ is the variable of the repair function, and μ ₀ is the vector of the relationship diagram of the pattern that needs to be repaired by this function.

Images