本发明属于计算光刻、掩模分类、图信号处理领域，尤其涉及一种掩模特征图形的图谱聚类方法。
背景技术：
在如今电气化、数字化、网络化的时代，电子设备在生活、工作中占有非常重要的地位。芯片是许多电子设备的核心，芯片制造技术的突破带动了半导体产业的发展。在芯片制造工序中，光刻工艺是重要的环节。光学光刻是基于投影成像原理，将印有电子线路的掩模版图在光源下曝光，使掩模上的电路图案转移到涂有光刻胶的晶圆上，从而在晶圆上形成所刻蚀的电子线路图形。
在光刻工艺中，掩模作为模板是重要的光学元件。由于掩模图案的线宽非常细微，因此掩模版图中分布着大量形状规则的几何图形，称为特征图形，这些特征图形组成了电子线路的基本单元。掩模上的几何图形按照空间结构、频域分布等特征的不同，可以分为多个种类，同种类的掩模特征图形具有较为相似的空间结构特征或频谱分布特征。在一些重要的光刻优化中，例如光源掩模联合优化流程中，需要将众多掩模特征图形聚类到不同的分组中，并在每个分组的挑选出具有代表性的特征图形，称为代表性特征图形。这些代表性特征图形包含了该分组中全部特征图形所共有的特征结构，以备后续的优化过程使用。
谱聚类是一种基于图信号的聚类方法，可在任意形状的样本空间上聚类，并且能收敛于全局最优解，因此适用于掩模特征图形的分类问题。谱聚类通过相似矩阵计算图的拉普拉斯矩阵，进而计算其前k个最小特征值所对应的特征列向量，将这k个特征列向量组成矩阵，最后再对该矩阵所有的k维行向量进行聚类。
对掩模特征图形进行谱聚类的首要步骤是构建包含所有特征图形的图结构，并计算图结构的相似矩阵。传统方法是逐个计算相似矩阵中的元素，即每一个掩模特征图形都需要和其他所有的掩模特征图形计算相似度，然后将其放入相似矩阵中。但是当全掩模中包含大量的特征图形结构时，其对应的图信号中也会包含大量的顶点，这样计算其相似矩阵的过程会引入较大的计算量，增加了谱聚类过程的运算时间。
综上，有必要提出一种快速的掩模图形聚类方法，针对掩模特征图形数据量大的特点，提升掩模版图相似矩阵的补全精度，以及对掩模特征图形谱聚类的效率和准确率。
技术实现要素：
为解决上述问题，本发明提供一种掩模特征图形的图谱聚类方法，首次将矩阵补全方法应用于掩模特征图形谱聚类中，并将矩阵补全问题转化为scp范数最小化问题，并利用分裂布雷格曼算法求解该问题，大大提升了掩模特征图形谱聚类的效率和准确率。
一种掩模特征图形的图谱聚类方法，包括以下步骤：
s1：获取待分类的n个二维掩模特征图形对应的相似矩阵
s2：通过基于分裂布雷格曼-scp范数最小化方法对相似矩阵
s3：获取相似矩阵
进一步地，所述相似矩阵
s201：基于分裂布雷格曼方法构建如下目标函数：
其中，ρ为权重系数，c为辅助变量矩阵，||·||scp为scp范数，指数p∈(0,1]，x为优化变量矩阵，pω(·)表示正交投影算子，ω为已知元素所在位置的集合，||·||f为frobenius范数，λ为残差项系数；
s202：采用分裂布雷格曼迭代算法从目标函数获取优化变量矩阵x、辅助变量矩阵c以及残差b的迭代方程组如下：
其中，k表示迭代的次数，残差b表示优化变量矩阵x与辅助变量矩阵c之间的残差；
s203：按照迭代方程组不断对优化变量矩阵x、辅助变量矩阵c以及残差b进行迭代计算，直到满足设定的迭代终止条件，最终得到的优化变量矩阵则为补全完成的相似矩阵
进一步地，对于优化变量矩阵x：如果位置(i,j)∈ω，则pω(x)的定义为pω(xi,j)＝xi,j，否则pω(xi,j)＝0；对于相似矩阵
进一步地，scp范数的定义为
进一步地，所述迭代终止条件为迭代次数达到设定上限值或者
进一步地，所述相似矩阵
s101：确定相似矩阵
s102：确定各已知元素所在位置的集合ω，其中集合ω的获取方式为：
假设蓝噪声模板为
依次判断位置(i,j)是否满足αe(i,j) β≥t(i,j)，其中α和β为用于控制位置个数的参数，若满足，则将位置(i,j)加入集合ω，直到集合ω中的位置个数为ns；
s103：分别计算集合ω中各位置(i,j)对应的两个二维掩模特征图形之间的皮尔逊相关系数绝对值，并将皮尔逊相关系数绝对值作为位置(i,j)处的已知元素值。
进一步地，两个二维掩模特征图形之间的皮尔逊相关系数绝对值
其中，si和sj分别为位置(i,j)对应的两个二维掩模特征图形的扫描向量，sip和sjp分别为si和sj的第p个分量，
进一步地，根据集合ω构建采样矩阵pω，其中，如果位置(i,j)∈ω，则采样矩阵pω位置(i,j)上的元素pω(i,j)＝1，否则pω(i,j)＝0。
进一步地，所述归一化拉普拉斯矩阵l′的计算公式为：
其中，d为度矩阵，d＝diag{d1,d2,…,dn}，
进一步地，采用k-means聚类算法对特征矩阵
有益效果：
1、本发明提供一种掩模特征图形的图谱聚类方法，仅从掩模特征图形集合中直接计算出其相似矩阵的部分元素，而非直接计算相似矩阵的所有元素，再利用分裂布雷格曼-scp范数最小化的低秩矩阵补全方法快速补全相似矩阵中其余未知元素，降低了相似矩阵的补全误差，同时提升了相似矩阵的计算效率，并将相似矩阵的快速计算方法应用于谱聚类算法中，进而提高整个掩模特征图形聚类过程的计算速度；由此可见，本发明首次将矩阵补全方法应用于掩模特征图形的相似矩阵快速计算以及掩模特征图形谱聚类的过程中，大大提升了掩模特征图形谱聚类的计算效率和准确率，降低了计算时间，且在一定的采样率下，也能够保持较高的分类正确率和重构精度。
2、本发明提供一种掩模特征图形的图谱聚类方法，将相似矩阵的快速计算方法应用于谱聚类算法中，有效地提升了掩模特征图形谱聚类的计算效率，降低了计算时间，且在一定的采样率下，能够提升掩模特征图形聚类的计算效率和准确率。
3、本发明提供一种掩模特征图形的图谱聚类方法，采用蓝噪声模板从相似矩阵中选出已知元素的对应位置，并利用了蓝噪声采样方法计算掩模版图相似矩阵的部分真实元素值，由于蓝噪声降采样具有较高的均匀性，该方法所计算的真实元素值会均匀地分布在整个相似矩阵当中，使得后续的矩阵补全过程中更容易获得误差较低的相似矩阵估计结果。
附图说明
图1为本发明提供的一种掩模特征图形的快速谱聚类方法的流程图；
图2为本发明用于谱聚类实验的二维掩摸特征图形的样本示例，其中掩摸特征图形的大小为512×512像素，共50张，分为5组，图中给出了每组中具有较强相关性的两张掩模特征图形作为示例；
图3为多种相似矩阵补全方法的计算误差随采样率的变化曲线；
图4为采用多种相似矩阵补全方法的掩摸特征图形谱聚类分类正确率随采样率的变化曲线。
具体实施方式
为了使本技术领域的人员更好地理解本申请方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述。
相似矩阵中的元素代表图节点数据样本间的相似度，本发明令每一个图节点对应一个掩模特征图形，则相似矩阵的每一行(或一列)的元素表示某个特定掩模特征图形与其他所有掩模特征图形的相似度，该相似度可用两个掩模特征图形的归一化内积来计算，如皮尔逊相关系数等；因此，相似矩阵中的行或列之间具有很高的线性相关性，所以掩模特征图形的相似矩阵可以视为低秩矩阵；基于此，本发明可以先从掩模特征图形集合中直接计算出其相似矩阵的部分元素(而非直接计算相似矩阵的所有元素)，再利用分裂布雷格曼-scp范数最小化的低秩矩阵补全方法快速补全其余未知元素，从而提高相似矩阵的计算效率，进而提高整个掩模特征图形聚类过程的计算速度。
具体的，如图1所示，一种掩模特征图形的图谱聚类方法，包括以下步骤：
s1：获取待分类的n个二维掩模特征图形对应的相似矩阵
进一步地，所述相似矩阵
s101：确定相似矩阵
s102：确定各已知元素所在位置的集合ω，其中集合ω的获取方式为：
假设蓝噪声模板为
依次判断位置(i,j)是否满足αe(i,j) β≥t(i,j)，其中α和β为用于控制位置个数的参数，若满足，则将位置(i,j)加入集合ω，直到集合ω中的位置个数为ns；
需要说明的是，在位置的筛选过程中，被选中的位置的个数是不断增长的，这些位置大体上趋于均匀分布，先选的位置是通过蓝噪声模板确定的，带有宏观上的随机性，当被选中的位置个数到达ns个后，不再考虑后续没有参与选择的位置。
s103：分别计算集合ω中各位置(i,j)对应的两个二维掩模特征图形之间的皮尔逊相关系数绝对值，并将皮尔逊相关系数绝对值作为位置(i,j)处的已知元素值。其中，皮尔逊相关系数绝对值
其中，n个掩模特征图形扫描得到向量记为s1,s2,…,sn，则si和sj分别为位置(i,j)对应的两个二维掩模特征图形的扫描向量，sip和sjp分别为si和sj的第p个分量，
也就是说，本发明提供了一种基于蓝噪声降采样的相似矩阵真值抽样计算方法。蓝噪声降采样和随机采样相比，采样点的分布更加均匀。对于一个初始矩阵，其全部元素为零，选择适当的采样率并根据蓝噪声分布对该矩阵元素的某些位置进行筛选采样，将全部被采样位置，也即被选来作为已知元素的位置记为集合ω，再用皮尔逊相关系数绝对值计算集合ω中所包含的相似矩阵元素，作为待补全相似矩阵的真实元素值。蓝噪声降采样的方法使直接计算得到的相似矩阵中的真实元素值分布较为均匀，使得在后续的矩阵补全过程中更容易获得误差较低的相似矩阵估计结果。
s2：通过基于分裂布雷格曼-scp范数最小化方法(简称scp splitbregman)对相似矩阵
需要说明的是，低秩矩阵补全方法主要可以分为：基于核范数松弛的补全方法、基于矩阵分解的补全方法、基于非凸函数松弛的矩阵补全方法。其中，现有的scp范数最小化方法属于非凸函数，该非凸函数在不同情况下可以退化为现有的核范数、schattenp范数、capped范数，也能够结合秩函数和核范数的优势。现有技术利用交替方向乘子法(admm)求解scp范数最小化问题，但是admm算法的复杂度较高，导致相似矩阵的计算效率低下，此外该技术也未将矩阵补全方法应用于掩模特征图形的相似矩阵快速计算，以及掩模特征图形谱聚类的过程中。
基于此，本发明提出一种基于分裂布雷格曼-scp范数最小化方法，并将其首次应用于矩阵补全，具体包括以下步骤：
s201：基于分裂布雷格曼方法构建如下目标函数：
其中，ρ为权重系数，c为辅助变量矩阵，||·||scp为scp范数，scp范数的定义为
s202：采用分裂布雷格曼迭代算法从目标函数获取优化变量矩阵x、辅助变量矩阵c以及残差b的迭代方程组如下：
其中，k表示迭代的次数，残差b表示优化变量矩阵x与辅助变量矩阵c之间的残差；
s203：按照迭代方程组不断对优化变量矩阵x、辅助变量矩阵c以及残差b进行迭代计算，直到满足设定的迭代终止条件，如迭代次数达到设定上限值或者
需要说明的是，为了更便于迭代，可以将迭代方程组中优化变量矩阵x的迭代公式
其中，pω为根据集合ω构建的采样矩阵，其中，如果位置(i,j)∈ω，则采样矩阵pω位置(i,j)上的元素pω(i,j)＝1，否则pω(i,j)＝0。值得一提的是，pω(·)表示算子，而pω表示矩阵，这两者的关系为：pω(x)＝pω⊙x。
s3：获取相似矩阵
所述归一化拉普拉斯矩阵l′的计算公式为：
其中，d为度矩阵，d＝diag{d1,d2,…,dn}，
采用k-means聚类算法对特征矩阵
下面给出迭代方程组的详细推导过程。
传统方法中构造的矩阵补全的目标函数如下：
本发明利用分裂布雷格曼方法对上述优化问题进行求解。引入辅助变量c≈x，将目标函数转化为如下公式：
其中λ为残差项系数，显然，本发明将传统目标函数中的x的变量分解为x和c这两个变量来优化。
令
其中
这样上述可以转化为如下：
需要说明的是，残差b表示优化变量矩阵x与辅助变量矩阵c之间的残差，ck-xk表示第k次迭代中优化变量矩阵与辅助变量矩阵迭代得到的实际值之间的残差，bk表示前k次迭代得到的残差的累计值。
后续即可通过迭代的方式更新变量矩阵x、更新辅助变量矩阵c、更新残差b，进而求解x，其中的奇异值分解过程用随机奇异值分解算法(randomizedsingularvaluedecomposition，简称rsvd)来计算，该方法所需的计算时间较短，提升了矩阵补全和谱聚类算法的运算效率。
进一步地，辅助变量矩阵c的优化问题的求解过程为：
将迭代公式
其中ζ＝ρ/λ；y＝ck；g＝xk 1 bk。
步骤1、对g进行奇异值分解，得到g＝uδvt，其中δ＝diag({δi}1≤i≤n)，此奇异值分解过程可用rsvd来计算。
步骤2、计算v＝[2ζ(1-p)]1/2-p和v′＝v ζpvp-1。
步骤3、比较δi和v′的大小，然后通过下式确定x′i，其中i＝1,…,n：
其中当v′i＜δi时，可利用梯度下降法计算
步骤4、计算
步骤5、比较
步骤6、，将计算得到
步骤7、计算y＝uσ*vt，这里u和v是g的左、右奇异矩阵，最终得到的y为scp范数与frobenius范数的最小化问题的解。
进一步地，本发明所述步骤3中优化问题的求解过程为：
步骤301～303用于计算公式
步骤301、初始化
步骤302、更新
步骤303、如果条件满足则停止迭代，获得
下面参考图2～图4以及表1，针对本发明实施例提供的一种掩模特征图形的快速谱聚类方法进行说明。
图3所示为五种矩阵补全方法的误差曲线，这五种方法分别为scp splitbregman rsvd方法、scp splitbregman方法、svt方法、核范数 splitbregman方法，scp admm方法。scp splitbregman rsvd方法使用了随机奇异值分解算法计算奇异值，其余四种方法中皆采用svd计算奇异值。误差的计算方法为：将补全完成的相似矩阵与所有元素都为真实值的相似矩阵作差，再取frobenius范数的平方。从整体来看，补全误差随着采样率的提升而减小，这是因为采样率越高，待补全矩阵中的未知元素越少，更有利于通过算法或的更高精度的补全结果，从而降低了误差。从图3可看出，scp splitbregman rsvd方法和scp splitbregman方法的补全误差都很低，且这二者十分接近，这两种方法的误差也比另外三种方法低，图中的scp splitbregman rsvd方法和scp splitbregman方法皆用黑色实线表示。scp splitbregman rsvd方法的误差仅比scp splitbregman方法的误差高一点，这是由于rsvd方法中利用高斯分布矩阵将高维矩阵映射到低维矩阵，从而较scp splitbregman方法引入了微小的误差，但是由表1可知，前者的计算速度快于后者。
图4所示为基于五种矩阵补全方法的谱聚类正确率曲线。由图可见随着采样率逐渐降低，谱聚类的正确率逐渐下降。可见scp splitbregman rsvd方法的正确率最高。需要说明的是，scp splitbregman rsvd方法与scp splitbregman方法的正确率完全相同，且比其他三种方法的正确率高。
表1：不同采样率下不同谱聚类方法的掩模版图聚类运行耗时
表1给出了不同采样率下，基于五种矩阵补全算法的谱聚类方法的运行时间，以及未采用矩阵补全算法(而是直接计算所有相似矩阵元素真值)的谱聚类方法的运行时间。可见，本发明采用矩阵补全的谱聚类方法所耗时间显著低于未用矩阵补全的谱聚类方法。此外在不同的采样率下，scp splitbregman rsvd方法的谱聚类耗时最短。也就是说，本发明提供一种掩模特征图形的图谱聚类方法，在谱聚类算法中计算相似矩阵为首要步骤，将分裂布雷格曼-scp范数最小化低秩矩阵补全方法应用于掩模特征图形相似矩阵的计算，然后采用补全后的相似矩阵执行谱聚类的后续操作，最终得到掩模特征图形的聚类结果，能够快速实现掩模特征图形的聚类。
当然，本发明还可有其他多种实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员当然可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。
