Computing Minimum Cuts by Randomized Search Heuristics

We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bi-criteria approach based on the famous maximum-flow minimum-cut theorem that enables evolutionary algorithms to find an optimal solution in expected polynomial time.     

Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle

We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: They can be equivalently defined by their "catchment basins” (through a steepest descent property) or by the "dividing lines” separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations.     

从局部极小到全局最优

所有控制决策问题本质上均可归结为优化问题,但大部分存在多极小,因此如何摆脱局部极小以实现全局最优一直是理论界和工程界关注的热点课题。文章总结了若干全局优化技术的机制和特点,包括模拟退火、进化计算、禁忌搜索、变邻域搜索、噪声方法、巢分区、混沌搜索、隧道方法、平滑技术、混合算法等,力求为优化研究人员了解全局优化技术和开发高效算法提供指导。     

Minimum Convex Partition of a Polygon with Holes by Cuts in Given Directions

Let be a given family of directions in the plane. The problem of partitioning a planar polygon P with holes into a minimum number of convex polygons by cuts in the directions of is proved to be NP-hard if and it is shown to admit a polynomial-time algorithm if . Received February 1997, and in revised form November 1997, and in final form February 1998.     

节点和边都有容量的有向平面网络中的最小截和最大流

在一般网络中,节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题.但传统转化方法用在平面网络中破坏了网络的平面性,使平面网络中节点和边都有容量的问题比仅边有容量的问题难.使用传统转化方法得到的两个问题的算法复杂度均为O（n2logn）（n表示网络中的节点数）.对此,作者曾给出了无向平面网络中最小截问题的保持平面性的转化方法.在此基础上,这里进一步讨论有向平面网络中的最小截、最大流问题,给出有向网络中保持平面性的转化方法,并利用此转化得到了复杂度均为O（nlogn）的最小截和最大流算法.从并行计算复杂性角度来看,传统方法转化后的问题是P-完全的.而使用新方法可以得到NC算法,且可以证明节点和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC的.     

一种具有去噪能力的全局最小值分割模型

几何主动轮廓模型的能量泛函是非凸性的,导致图像分割结果依赖于曲线的初始化条件,对噪声敏感。针对该问题,提出一种全局最小值分割模型,对能量泛函进行凸性非约束改进,利用基于总变分对偶公式的快速数值化算法实现图像的分割。对合成图像和医学图像的分割结果表明,利用该模型可以准确提取出对象的边界,分割速度快,对噪声具有较好的鲁棒性。     

Forward Light Cuts: A Scalable Approach to Real‐Time Global Illumination

We present Forward Light Cuts, a novel approach to real‐time global illumination using forward rendering techniques. We focus on unshadowed diffuse interactions for the first indirect light bounce in the context of large models such as the complex scenes usually encountered in CAD application scenarios. Our approach efficiently generates and uses a multiscale radiance cache by exploiting the geometry‐specific stages of the graphics pipeline, namely the tessellator unit and the geometry shader To do so, we assimilate virtual point lights to the scene's triangles and design a stochastic decimation process chained with a partitioning strategy that accounts for both close‐by strong light reflections, and distant regions from which numerous virtual point lights collectively contribute strongly to the end pixel. Our probabilistic solution is supported by a mathematical analysis and a number of experiments covering a wide range of application scenarios. As a result, our algorithm requires no precomputation of any kind, is compatible with dynamic view points, lighting condition, geometry and materials, and scales to tens of millions of polygons on current graphics hardware.     

一种改进型全局最小熵ISAR距离对准算法

在研究全局最小熵距离对准算法的基础上,结合了亚距离单元对准方法,并通过分析回波相关性对原算法的影响,提出了一种改进型全局最小熵算法。该算法可分为距离像分块对准和亚距离单元对准两部分。本文通过对回波相关性的分析,利用距离像分块对准改善了原算法距离对准的准确性;并通过亚距离单元对准提高了原算法距离对准的精度。实测数据处理结果表明,改进型算法具有较高的距离对准精度,从而提高了成像质量。     

出现网的t型s切和t切

首先引入出现网的t切的转移的概念,利用t切的转移集τ,可以得到t切p[τ]。其次引入s切的伴随集E(u)和t型s切的概念。证明了出现网的t型s切和t切有对应的关系以及这种对应关系保持t型s切的转移和t切的转移。给出了在s切有向图中查找t切的算法,证明了出现网的t切都是t型s切的伴随集。     

Global Minimum for Active Contour Models: A Minimal Path Approach

A new boundary detection approach for shape modeling is presented. It detects the global minimum of an active contour models energy between two end points. Initialization is made easier and the curve is not trapped at a local minimum by spurious edges. We modify the snake energy by including the internal regularization term in the external potential term. Our method is based on finding a path of minimal length in a Riemannian metric. We then make use of a new efficient numerical method to find this shortest path.It is shown that the proposed energy, though based only on a potential integrated along the curve, imposes a regularization effect like snakes. We explore the relation between the maximum curvature along the resulting contour and the potential generated from the image.The method is capable to close contours, given only one point on the objects' boundary by using a topology-based saddle search routine.We show examples of our method applied to real aerial and medical images.     

Generalized Prioritized Multicriteria Aggregation

After investigating prioritized multicriteria decision‐making or aggregation problems in depth, we reveal that priority relationships among criteria may be incomplete. In a complex and practical multicriteria decision‐making problem, the relationships of a pair of criteria can be multiform including priority relationships, except for independence. For such cases, we present a generalized prioritized multicriteria aggregation (GPMA) model with incomplete priority relationships in this paper. First, we elaborate GPMA problems, and describe them by using a dendriform structure after designing a top‐to‐bottom method to form priority hierarchies according to the given priority relationships. Furthermore, a common process for handling GPMA problems is proposed based on the premeditation that the weights associated with the lower‐priority criteria need to be revised according to the satisfaction of the higher‐priority criteria. At length, we develop two GPMA operators with respect to the GPMA with strictly and weakly ordered prioritizations, respectively, based on triangular norms, and we verify that both of them are aggregation functions.     

分簇无线传感器网络中全局最小能耗传输策略

无线传感器网络能量均衡策略中存在能耗大小的问题。在圆形的网络模型中,通过比较不同分环数下总能耗大小,得出在能量均衡前提下,能耗最小的网络分环数。算法同时能够明确网络所需的最优簇头数。实验数据表明,该策略可以最大限度的减少节点能耗,延长网络寿命。     

Multicriteria Decision-Making Using Fuzzy Measures

We are interested in the formulation of multicriteria decision functions based on the use of a measure over the space of criteria. Specifically, the relationship between the criteria is expressed using a monotonic set measure. We then use the Choquet integral to construct decision functions based on the measure. We look at a number of different decision functions generated from specific classes of measures.     

Image Thresholding Using Graph Cuts

A novel thresholding algorithm is presented in this paper to improve image segmentation performance at a low computational cost. The proposed algorithm uses a normalized graph-cut measure as thresholding principle to distinguish an object from the background. The weight matrices used in evaluating the graph cuts are based on the gray levels of the image, rather than the commonly used image pixels. For most images, the number of gray levels is much smaller than the number of pixels. Therefore, the proposed algorithm requires much smaller storage space and lower computational complexity than other image segmentation algorithms based on graph cuts. This fact makes the proposed algorithm attractive in various real-time vision applications such as automatic target recognition. Several examples are presented, assessing the superior performance of the proposed thresholding algorithm compared with the existing ones. Numerical results also show that the normalized-cut measure is a better thresholding principle compared with other graph-cut measures, such as average-cut and average-association ones.      

Multicriteria Problems with Importance-Ordered Criteria Groups

Automation and Remote Control - We develop a statement of the decision-making problem in the presence of information about the importance of criteria groups, give definitions of the relationships...     

Evaluating the Validity of Multicriteria Decision-Making

The paper provides an approach to the assessment of the validity of decisions made for complex systems using multicriteria methods. It is also proposed to evaluate the validity based on the relevant criterion, which involves not only assessment of the results obtained by the multicriteria methods but also preliminary stages related to preparation of the initial data.     

Multicriteria Robust Fitting of Elliptical Primitives

Geometric fitting is present in different fields of science, engineering and astronomy. In particular, ellipse shapes are some of the most commonly employed geometric features in digital image analysis and visual pattern recognition. Most geometric and algebraic methods are sensitive to noise and outlier points and so the results are not usually acceptable. In this paper, a robust geometric multicriteria method based on the mean absolute geometric error and the eccentricity to fit an ellipse to set of points is proposed. It is well known that the least mean absolute error criterion leads to robust estimations. The experimental results on different real and synthetic data have shown that the proposed algorithm is robust to outliers. Moreover, it allows us to identify outliers and remove them.     

Minimum Dwell Time for Global Exponential Stability of a Class of Switched Positive Nonlinear Systems

This paper will investigate global exponential stability analysis for a class of switched positive nonlinear systems under minimum dwell time switching, whose nonlinear functions for each subsystem are constrained in a sector field by two odd symmetric piecewise linear functions and whose system matrices for each subsystem are Metzler. A class of multiple time-varying Lyapunov functions is constructed to obtain the computable sufficient conditions on the stability of such switched nonlinear systems within the framework of minimum dwell time switching. All present conditions can be solved by linear/nonlinear programming techniques. An example is provided to demonstrate the effectiveness of the proposed result.