基于分布估计算法的连续函数全局优化问题研究

分布估计算法从宏观的角度建立一个概率模型,用来描述解空间的分布,从而通过进化计算获得优势个体。目前,离散型分布估计算法研究已经比较成熟,而连续型分布估计算法研究进展缓慢。采用均匀分布缩小采样领域的思想,设计新的分布估计算法求解连续型优化问题。实验数据表明,该分布估计算法对于求解连续型问题是有效的。     

Graphical model based continuous estimation of distribution algorithm

In this paper, a new estimation of distribution algorithm is introduced. The goal is to propose a method that avoids complex approximations of learning a probabilistic graphical model and considers multivariate dependencies between continuous random variables. A parallel model of some subgraphs with a smaller number of variables is learned as the probabilistic graphical model. In each generation, the joint probability distribution of the selected solutions is estimated using a Gaussian Mixture model. Then, learning the graphical model of dependencies among random variables and sampling are done separately for each Gaussian component. In the learning step, using the selected solutions of each Gaussian mixture component, the structure of a Markov network is learned. This network is decomposed to maximal cliques and a clique graph. Then, complete Bayesian network structures are learned for these subgraphs using an optimization algorithm. The proposed optimization problem is a 0–1 constrained quadratic programming which finds the best permutation of variables. Then, sampling is done from each Bayesian network of each Gaussian component. The introduced method is compared with the other network-based estimation of distribution algorithms for optimization of continuous numerical functions.     

Evolutionary optimization with Markov random field prior

This work discusses an evolutionary algorithm in which the constituent variables of a solution are modeled by a Markov random field (MRF). We maintain a population of potential solutions at every generation and for each solution a fitness value is calculated. The evolution, however, is not achieved through genetic recombination. Instead, each variable in a solution will be updated by sampling from its probability distribution. According to the MRF prior, local exploitation is encoded in the conditional probabilities. For evolutionary exploration, we estimate the probabilities as fitness-weighted statistics. These two kinds of search are combined smoothly in our algorithm. We compare it with two representative algorithms [iterated conditional modes (ICM) and simulated annealing (SA)] on noisy and textured image segmentation. Remarkable performance is observed.     

Segmentation of fuzzy images: a novel and fast two-step pseudo MAP method

This paper presents a new two-step pseudo maximum a posteriori (MAP) segmentation method for the Markov random field (MRF)-modeled image because the exact MAP estimation is hard to implement due to intractable complexity. The expectation maximization (EM) and Markov Chain Monte Carlo (MCMC) methods are adopted to estimate the parameters for the MRF model due to their comparatively good performance. Although the image segmentation algorithms via graph cuts have become very popular nowadays, our proposed algorithm still performs significantly better in automatic identification and segmentation of fuzzy images than them, which is shown by the quantitative results on synthesized images. In practical applications, the proposed two-step pseudo MAP method is superior in segmenting the fuzzy laser images reflected from the weld pool surfaces during the P-GMAW welding process.     

自助重要性采样用于实时多目标视觉跟踪

多目标视觉跟踪的主要困难来自于多个目标交互(部分或完全遮挡)导致的歧义性. 马尔可夫随机场(Markov random field, MRF)可以消除这种歧义性且无需显式的数据关联. 但是, 通用概率推理算法的计算代价很高. 针对上述问题, 本文做出了3点贡献: 1)设计了新的具有"分散-集中-分散"结构的递归贝叶斯跟踪框架—自助重要性采样粒子滤波器, 它 使用融入当前时刻观测的重要性密度函数解决维数灾难问题, 将计算复杂度从指数增长变为线性增长; 2)提出了新的蒙特卡洛策略— 自助重要性采样, 利用MRF的因子分解性质进行重要性采样, 并使用自助法产生低成本高质量的样本、降低似然度计算次数和维持多模式分布; 3)采用了新的边缘化技术—使用辅助变量采样进行边缘化, 使用自助直方图对边缘后验分布进行密度估计. 实验结果表明, 本文提出的算法能够对大量目标进行实时跟踪, 能够处理目标间复杂的交互, 能够在目标消失后维持多模式分布.     

A Markov random field model-based approach to image interpretation

An image is segmented into a collection of disjoint regions that form the nodes of an adjacency graph, and image interpretation is achieved through assigning object labels (or interpretations) to the segmented regions (or nodes) using domain knowledge, extracted feature measurements, and spatial relationships between the various regions. The interpretation labels are modeled as a Markov random field (MRF) on the corresponding adjacency graph, and the image interpretation problem is then formulated as a maximum a posteriori (MAP) estimation rule, given domain knowledge and region-based measurements. Simulated annealing is used to find this best realization or optimal MAP interpretation. This approach also provides a systematic method for organizing and representing domain knowledge through appropriate design of the clique functions describing the Gibbs distribution representing the pdf of the underlying MRF. A general methodology is provided for the design of the clique functions. Results of image interpretation experiments on synthetic and real-world images are described     

Modeling textured images using generalized long correlation models

The long correlation (LC) models are a general class of random field (RF) models which are able to model correlations, extending over large image regions with few model parameters. The LC models have seen limited use, due to lack of an effective method for estimating the model parameters. In this work, we develop an estimation scheme for a very general form of this model and demonstrate its applicability to texture modeling applications. The relationship of the generalized LC models to other classes of RF models, namely the simultaneous autoregressive (SAR) and Markov random field (MRF) models, is shown. While it is known that the SAR model is a special case of the LC model, we show that the MRF model is also encompassed by this model. Consequently, the LC model may be considered as a generalization of the SAR and MRF models     

基于图论优化的块采样纹理合成

基于马尔可夫随机场(MRF)模型和已有的块采样合成技术,提出一种改进的合成算法,采用图论的最小割线算法对MRF的似然性进行优化,将合成时的光栅扫描方式改为之字形扫描方式,以抑制纹理的倾向性和纹元的不完整性。试验证明,该算法的合成效果较好。     

Incorporating higher-order point distribution model priors into MRFs using convex quadratic programming

Recently, with the advent of powerful optimisation algorithms for Markov random fields (MRFs), priors of high arity (more than two) have been put into practice more widely. The statistical relationship between object parts encoding shape in a covariant space, also known as the point distribution model (PDM), is a widely employed technique in computer vision which has been largely overlooked in the context of higher-order MRF models. This paper focuses on such higher-order statistical shape priors and illustrates that in a spatial transformation invariant space, these models can be formulated as convex quadratic programmes. As such, the associated energy of a PDM may be optimised efficiently using a variety of different dedicated algorithms. Moreover, it is shown that such an approach in the context of graph matching can be utilised to incorporate both a global rigid and a non-rigid deformation prior into the problem in a parametric form, a problem which has been rarely addressed in the literature. The paper then illustrates an application of PDM priors for different tasks using graphical models incorporating factors of different cardinalities.     

Bayesian estimation of motion vector fields

A stochastic approach to the estimation of 2D motion vector fields from time-varying images is presented. The formulation involves the specification of a deterministic structural model along with stochastic observation and motion field models. Two motion models are proposed: a globally smooth model based on vector Markov random fields and a piecewise smooth model derived from coupled vector-binary Markov random fields. Two estimation criteria are studied. In the maximum a posteriori probability (MAP) estimation, the a posteriori probability of motion given data is maximized, whereas in the minimum expected cost (MEC) estimation, the expectation of a certain cost function is minimized. Both algorithms generate sample fields by means of stochastic relaxation implemented via the Gibbs sampler. Two versions are developed: one for a discrete state space and the other for a continuous state space. The MAP estimation is incorporated into a hierarchical environment to deal efficiently with large displacements     

基于层次MRF的MR图像分割

核磁共振图像(MRI)的定量分析在神经疾病的早期治疗中有很重要作用.提出了一种基于层次Markov随机场模型的MRI图像分割新方法.在高层次的标记图象中采用了混合模型,即区域的内部用各向同性均匀MRF来建模,边界用各向异性非均匀MRF来建模.所以方向性被引入到边界信息中,这样可以更准确的表达标记图象的特性;在低层次的像素图像中,不同区域中像素的灰度分布用不同的高斯纹理来描述.分割问题可以被转换成一种最大后验概率估计问题.采用基于直方图的DAEM算法来估计SNFM参数的全局最优值;并基于MRF先验参数的实际意义,提出一种近似的方法来简化这些参数的估计,实验显示该方法能获得更好的结果.     

基于马尔可夫随机场的SAR图象目标分割

运动、静止目标获取与识别（MSTAR）计划表明，将合成孔径雷达（SAP）图象分割成目标、阴影和背景杂波区域对于从开放环境中进行目标识别是一种有效的手段。但是由于SAP图象所固有的斑点噪声的影响，传统的分割方法很难获得准确的分割。为此提出了一种基于MRF(Markov random field)模型的SAP图象分割算法。用MRF模型描述待分割图象的先验知识，利用最大似然（ML）估计从训练数据中获得图象各区域的先验概率分布，采用Bayes方法，在观测数据基础上，根据分割图象的后验分布所对应的MRF模型的条件概率，利用Metroplis采样器获得最大后验概率（MAP）准则下的图象分割。通过对MSTAR的样本目标图象应用该算法，结果表明它可以获得稳健和准确的分割效果。     

基于马尔科夫随机场的散乱点云全局特征提取

为了精确提取点云数据中的特征信息,针对激光扫描获取的三维散乱点云数据,提出一种基于马尔科夫随机场（Markov random field, MRF）的散乱点云特征提取方法.首先,根据散乱点的曲率估计及阈值初始化点标号并判定稳定点,将稳定点标记存储在数组中;然后,将优化不稳定点的标号问题转化为随机场标号的能量函数问题,引用贝叶斯估计求后验概率分布函数及MAP-MRF（Maximum a posteriori-Markov random field）框架归约得到目标函数;最后,根据图割法α-expansion算法,利用标号调整过程中标号集相对能量变化得到不稳定点的最优标号集,将其与存储稳定点的数组综合,根据点标号提取特征点.实验结果表明,该方法简单、高效、无需人工调参,能够依据全局能量的变化自适应提取特征,特征提取结果令人满意.     

融入邻域作用的高斯混合分割模型及简化求解

目的 基于高斯混合模型（GMM）的图像分割方法易受噪声影响,为此采用马尔可夫随机场（MRF）将像素邻域关系引入GMM,提高算法抗噪性。针对融入邻域作用的高斯混合分割模型结构复杂、参数估计困难,难以获得全局最优分割解等问题,提出一种融入邻域作用的高斯混合分割模型及其简化求解方法。方法 首先,构建融入邻域作用的GMM。为了提高GMM的抗噪性,采用MRF建模混合模型权重系数的先验分布。然后,利用贝叶斯理论建立图像分割模型,即品质函数;由于品质函数中参数较多（包括权重系数,均值,协方差）、函数结构复杂,导致参数求解困难。因此,将品质函数中的均值和协方差定义为权重系数的函数,由此简化模型结构并方便其求解;虽然品质函数中仅包含参数权重系数,但结构比较复杂,难以求得参数的解析式。最后,采用非线性共轭梯度法（CGM）求解参数,该方法仅需利用品质函数值和参数梯度值,降低了参数求解的复杂性,并且收敛快,可以得到全局最优解。结果 为了有效而准确地验证提出的分割方法,分别采用本文算法和对比算法对合成图像和高分辨率遥感图像进行分割实验,并定性和定量地评价和分析了实验结果。实验结果表明本文方法的有效抗噪性,并得到很好的分割结果。从参数估计结果可以看出,本文算法有效简化了模型参数,并获得全局最优解。结论 提出一种融入邻域作用的高斯混合分割模型及其简化求解方法,实验结果表明,本文算法提高了算法的抗噪性,有效地简化了模型参数,并得到全局最优参数解。本文算法对具有噪声的高分辨率遥感影像广泛适用。     

基于层次随机图模型的脑网络链路预测

针对一般链路预测算法在具有层次结构的脑网络中计算效率低且复杂度高的问题,提出了一种基于最大似然估计的层次随机图模型。该算法首先利用脑网络数据建立层次随机图,然后通过改进的马尔科夫蒙特卡罗算法采样树状图空间,最后计算脑网络边的平均连接概率,且通过评价指标对算法进行评价。实验结果表明,利用该算法对脑网络和3种不同的层次结构网络进行链路预测比较, 脑网络的预测结果最好。此外,所提出的算法较之传统的基于相似性的算法,该算法效果明显,且具有理想的计算复杂度。     

一种HRG模型初始化算法及在链路预测中的应用

在利用层次随机图(HRG)模型对真实网络进行链路预测的过程中,需要构造一个初始层次随机图来初始化马尔科夫链以运行马尔科夫链蒙特卡洛抽样算法。针对现有的层次随机图初始化方案效率不高的问题,本文对初始层次随机图模型进行重建,提出一种新的层次随机图模型初始化算法。该算法分为2个阶段,第一阶段引入相似性指标(LHN-I指标)为网络中的边进行排序;第二阶段利用排序好的边对层次随机图模型进行构造。在该过程中,设计一种将网络顶点插入到层次随机图模型中的方法。通过3个实例网络对提出的算法与现有算法的性能进行比较,实验结果表明,利用提出的初始化算法构造出的初始层次随机图不仅有着较高的似然值,而且使得马尔科夫链蒙特卡洛算法能够更快地收敛,进而降低链路预测的时间消耗。除此之外,在链路预测实验中,改进的基于层次随机图模型的链路预测算法相比一些基于相似性指标的链路预测算法有着较好的预测精度。     

求解混合流水车间调度问题的分布估计算法

针对混合流水车间调度问题(Hybrid flow-shop scheduling problem, HFSP)的特点, 设计了基于排列的编码和解码方法, 建立了描述问题解空间的概率模型, 进而提出了一种有效的分布估计算法(Estimation of distribution algorithm, EDA). 该算法基于概率模型通过采样产生新个体, 并基于优势种群更新概率模型的参数. 同时, 通过实验设计方法对算法参数设置进行了分析并确定了有效的参数组合. 最后, 通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.     

Inexact graph matching by means of estimation of distribution algorithms

Estimation of distribution algorithms (EDAs) are a quite recent topic in optimization techniques. They combine two technical disciplines of soft computing methodologies: probabilistic reasoning and evolutionary computing. Several algorithms and approaches have already been proposed by different authors, but up to now there are very few papers showing their potential and comparing them to other evolutionary computational methods and algorithms such as genetic algorithms (GAs). This paper focuses on the problem of inexact graph matching which is NP-hard and requires techniques to find an approximate acceptable solution. This problem arises when a nonbijective correspondence is searched between two graphs. A typical instance of this problem corresponds to the case where graphs are used for structural pattern recognition in images. EDA algorithms are well suited for this type of problems.

This paper proposes to use EDA algorithms as a new approach for inexact graph matching. Also, two adaptations of the EDA approach to problems with constraints are described as two techniques to control the generation of individuals, and the performance of EDAs for inexact graph matching is compared with the one of GAs.     

VBI-MRF model for image segmentation

In statistical image segmentation, the distribution of pixel values is usually assumed to be Gaussian and the optimal result is believed to be the one that has maximum a posteriori (MAP) probability. In spite of its prevalence and computational efficiency, the Gaussian assumption, however, is not always strictly followed, and hence may lead to less accurate results. Although the variational Bayes inference (VBI), in which statistical model parameters are also assumed to be random variables, has been widely used, it can hardly handle the spatial information embedded in pixels. In this paper, we incorporate spatial smoothness constraints on pixels labels interpreted by the Markov random field (MRF) model into the VBI process, and thus propose a novel statistical model called VBI-MRF for image segmentation. We evaluated our algorithm against the variational expectation-maximization (VEM) algorithm and the hidden Markov random field (HMRF) model and MAP-MRF model based algorithms on both noise-corrupted synthetic images and mosaics of natural texture. Our pilot results suggest that the proposed algorithm can segment images more accurately than other three methods and is capable of producing robust image segmentation.     

Estimating optimal parameters for MRF stereo from a single image pair

This paper presents a novel approach for estimating the parameters for MRF-based stereo algorithms. This approach is based on a new formulation of stereo as a maximum a posterior (MAP) problem in which both a disparity map and MRF parameters are estimated from the stereo pair itself. We present an iterative algorithm for the MAP estimation that alternates between estimating the parameters while fixing the disparity map and estimating the disparity map while fixing the parameters. The estimated parameters include robust truncation thresholds for both data and neighborhood terms, as well as a regularization weight. The regularization weight can be either a constant for the whole image or spatially-varying, depending on local intensity gradients. In the latter case, the weights for intensity gradients are also estimated. Our approach works as a wrapper for existing stereo algorithms based on graph cuts or belief propagation, automatically tuning their parameters to improve performance without requiring the stereo code to be modified. Experiments demonstrate that our approach moves a baseline belief propagation stereo algorithm up six slots in the Middlebury rankings