广义Hough变换:多个圆的快速随机检测

以随机采样到的2个图像点及在此2点的中垂线上搜索第3个图像点来确定候选圆．当随机采样2个图像点时,通过剔除孤立、半连续噪声点减少了无效采样;当搜索候选圆的第3点时,剔除上述2种噪声点、非共圆点并给出快速确认候选圆是否为真圆的方法,尽可能减少无效计算．数值实验结果表明：文中算法能快速检测多个圆．在检测多个圆并且具有噪声的情况下,与随机圆检测算法相比,其检测速度快一个数量级．     

随机Hough变换的概率模型:有限数据点

该文研究了基于有限个数据点的随机Hough变的的概率模型，在这个模型中，主要讨论了在随机Hough变换的基本算法中起相当关键作用的两个量，累加器数组的控制以及从图像中提取全部基元所需随机抽样的总次数，这两个量对随机Hough变换的算法设计及其终止规则是相当有用的。该文的主要结果包括两部分，其一是对累加器数组引入了多项分布，系统地研究了累加器数组的概率结构及其相互关系，同时也计算了提取全部基元所需的随机抽样总次数的分布，均值和方差，另者是基于不断的随机抽样而使得累加器数组的随机变化。作者引入了多维纯生过程，有了提取全部基元所需随机抽样的总次数服从离散的PH分布，从而它的各阶矩都可用简洁的矩阵形式统一地表出，针对于图像的固有因素，作者也讨论了基元的平稳提取概率，该文的结果为随机Hough变换的进一步研究和应用提供了较为严格的理论依据。     

Shape of Basic Clusters: Using Analogues of Hough Transform in Higher Dimensions

A new unified method for improving a wide class of linear decision rules is proposed on the basis of using the concept of Generalized Precedent and analogues of Hough transform in higher dimensions.     

Hough变换的特性分析:一种全局观点(II)

使用基本Hough变换进行椭圆的检测与提取,利用形状在投影时各投影区间中点是否在一条有效的正弦曲线上来检测形状是否具有中心对称性;结合对投影区间长度变化规律的分析,实现了在二维空间中椭圆的检测,并通过仿真实验说明了该方法的有效性;利用整周期上峰值线的对称性确定了多个形状投影分布的判定,使得对几何基元的提取纳入了统一的框架.     

基于数学形态学与Hough变换的乐谱谱线探测算法研究

数学形态学是综合了多学科知识的交叉学科,是一种非线性的图像分析理论,己成为图像处理的重要工具之一。文章简单介绍了数学形态学和二值形态学的基本运算—腐蚀和膨胀,并提出了基于数学形态学的乐谱谱线探测算法。实验结果证明,与Hough变换探测直线算法相比,该乐谱谱线探测算法具有运算速度快、效率高、抗噪声能力强等优点。     

Fuzzy Distance Transform: Theory, Algorithms, and Applications

This paper describes the theory and algorithms of distance transform for fuzzy subsets, called fuzzy distance transform (FDT). The notion of fuzzy distance is formulated by first defining the length of a path on a fuzzy subset and then finding the infimum of the lengths of all paths between two points. The length of a path π in a fuzzy subset of the n-dimensional continuous space ⁿ is defined as the integral of fuzzy membership values along π. Generally, there are infinitely many paths between any two points in a fuzzy subset and it is shown that the shortest one may not exist. The fuzzy distance between two points is defined as the infimum of the lengths of all paths between them. It is demonstrated that, unlike in hard convex sets, the shortest path (when it exists) between two points in a fuzzy convex subset is not necessarily a straight line segment. For any positive number θ≤1, the θ-support of a fuzzy subset is the set of all points in ⁿ with membership values greater than or equal to θ. It is shown that, for any fuzzy subset, for any nonzero θ≤1, fuzzy distance is a metric for the interior of its θ-support. It is also shown that, for any smooth fuzzy subset, fuzzy distance is a metric for the interior of its 0-support (referred to as support). FDT is defined as a process on a fuzzy subset that assigns to a point its fuzzy distance from the complement of the support. The theoretical framework of FDT in continuous space is extended to digital cubic spaces and it is shown that for any fuzzy digital object, fuzzy distance is a metric for the support of the object. A dynamic programming-based algorithm is presented for computing FDT of a fuzzy digital object. It is shown that the algorithm terminates in a finite number of steps and when it does so, it correctly computes FDT. Several potential applications of fuzzy distance transform in medical imaging are presented. Among these are the quantification of blood vessels and trabecular bone thickness in the regime of limited special resolution where these objects become fuzzy.     

O(m~2)时间求解SAT问题的随机算法

传统的求解 SAT问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 SAT问题的随机算法 Sat Test1和 Sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 SAT问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 Sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 SAT实例有较好的求解能力 .     

论计算思维——计算思维的科学定位、基本原理及创新路径

指出计算思维、实验思维与理论思维是人类三大科学思维方式,并初步梳理出可计算性原理、形理算一体原理与计算机设计原理等三大计算机基本原理.还指出,交叉创新是计算思维创新发展的根本途径.     

O（m^2）时间求解SAT问题的随机算法

传统的求解SAT问题的随机算法主要是对满足解进行搜索,在找不到满足解的情况下,则无法正确判断问题的可满足性。该文提出了两个时间复杂度为O（m^2）求解SAT问题的随机算法SatTestl和SatTest2,这里m为CNF公式中的子句数。这两个随机算法是通过对不满足解数的估计来判断SAT问题的可满足性,不同于传统的随机算法。其中第二个算法SatTest2在搜索满足解的同时又可以对不满足解数进行估计,是对传统随机算法的重要改进。试验结果表明,文中提出的算法对相变区域的难SAT实例有较好的求解能力。     

MAX(1)和MARG(1)中公式改名的复杂性

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.     

Computational Auditory Scene Analysis: Principles, Algorithms, and Applications (Wang, D. and Brown, G.J., Eds.; 2006) [Book review]

This book focuses on computational auditory scene analysis (CASA), an interdisciplinary area derived from the field of auditory scene analysis (ASA). The book comprises chapters written by ten researchers in the field of auditory modeling, speech analysis and recognition, statistical signal processing, sound localization, reverberation processing, music processing, and networks of oscillatory or firing neurons. A very interesting feature of the book is the accompanying website http://www.casabook.org/, from which it is possible to download sound examples or Matlab software for some chapters. The book is geared to scientists and graduate students anxious to grasp this multidisciplinary area.     

Graph Clustering,Variational Image Segmentation Methods and Hough Transform Scale Detection for Object Measurement in Images

We consider the problem of scale detection in images where a region of interest is present together with a measurement tool (e.g. a ruler). For the segmentation part, we focus on the graph-based method presented in Bertozzi and Flenner (Multiscale Model Simul 10(3):1090–1118, 2012) which reinterprets classical continuous Ginzburg–Landau minimisation models in a totally discrete framework. To overcome the numerical difficulties due to the large size of the images considered, we use matrix completion and splitting techniques. The scale on the measurement tool is detected via a Hough transform-based algorithm. The method is then applied to some measurement tasks arising in real-world applications such as zoology, medicine and archaeology.     

Algorithms for Trigonometric Curves (Simplification,Implicitization, Parameterization)

A trigonometric curve is a real plane curve where each coordinate is given parametrically by a truncated Fourier series. The trigonometric curves frequently arise in various areas of mathematics, physics, and engineering. Some trigonometric curves can also be represented implicitly by bivariate polynomial equations. In this paper, we give algorithms for (a) simplifying a given parametric representation, (b) computing an implicit representation from a given parametric representation, and (c) computing a parametric representation from a given implicit representation.     

Serial and Parallel Algorithms for (k,2)-Partite Graphs

We introduce a class of layered graphs which we call (k,2)-partite and which we argue are an interesting class because of several important applications. We show that testing for (k,2)-partiteness can be done efficiently both on sequential and parallel machines, by showing that membership is in NSPACE(log n) and in NC². We show that (k,2)-partite graphs have bounded path width. We then show that a particular NP-complete problem, namely Maximum Independent Set, is solvable in linear time on bounded pathwidth graphs if the path decomposition is included in the input. Finally, we show that the Maximum Independent Set problem is in NC² for (k,2)-partite graphs. We note that linear time solutions for certain NP-complete problems have been shown for a wider class of graphs, namely partial k-trees. Our linear time algorithm is somewhat simpler in structure. We conjecture that our techniques can be used on many NP-complete problems to yield efficient algorithms for (k,2)-partite graphs.     

(I,A)-蕴涵及其基本性质

模糊蕴涵在模糊逻辑和近似推理领域中发挥着十分重要的作用，模糊蕴涵的构造是相关领域中的重要研究课题。基于模糊蕴涵[I]和聚合算子[A]构造出[(I,A)]-算子，研究[(I,A)]-算子成为模糊蕴涵的条件，其次研究[(I,A)]-蕴涵包括分配性和输入性在内的一些基本性质。     

Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms

We consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. In the maximum disjoint paths problem, we are given a sequence of connection requests for some communication network. Each request consists of a pair of nodes, that wish to communicate over a path in the network. The request has to be immediately connected or rejected, and the goal is to maximize the number of connected pairs, such that no two paths share an edge. In the call control problem, each request has an additional bandwidth specification, and the goal is to maximize the total bandwidth of the connected pairs (throughput), while satisfying the bandwidth constraints (assuming each edge has unit capacity). These classical problems are central in routing and admission control in high speed networks and in optical networks.We present the first known constant-competitive algorithms for both problems on the line. This settles an open problem of Garay et al. and of Leonardi. Moreover, to the best of our knowledge, all previous algorithms for any of these problems, are (logn)-competitive, where n is the number of vertices in the network (and obviously noncompetitive for the continuous line). Our algorithms are randomized and preemptive. Our results should be contrasted with the (logn) lower bounds for deterministic preemptive algorithms of Garay et al. and the (logn) lower bounds for randomized non-preemptive algorithms of Lipton and Tomkins and Awerbuch et al. Interestingly, nonconstant lower bounds were proved by Canetti and Irani for randomized preemptive algorithms for related problems but not for these exact problems.