检索结果-内蒙古大学图书馆

A fast and robust circle detection method using isosceles triangles sampling

PATTERN RECOGNITION 2016年 54卷 218-228页

作者： Zhang, Hanqing Wiklund, Krister Andersson, Magnus Umea Univ Dept Phys Linneaus Vaeg 9 SE-90187 Umea Sweden

Circle detection using randomized sampling has been developed in recent years to reduce computational intensity. However, randomized sampling is sensitive to noise that can lead to reduced accuracy and false-positive candidates. To improve on the robustness of randomized circle detection under noisy conditions this paper presents a new methodology for circle detection based upon randomized isosceles triangles sampling. It is shown that the geometrical property of isosceles triangles provides a robust criterion to find relevant edge pixels which, in turn, offers an efficient means to estimate the centers and radii of circles. For best efficiency, the estimated results given by the sampling from individual connected components of the edge map were analyzed using a simple clustering approach. To further improve on the accuracy we applied a two-step refinement process using chords and linear error compensation with gradient information of the edge pixels. Extensive experiments using both synthetic and real images have been performed. The results are compared to leading state-of-the-art algorithms and it is shown that the proposed methodology has a number of advantages: it is efficient in finding circles with a low number of iterations, it has high rejection rate of false-positive circle candidates, and it has high robustness against noise. All this makes it adaptive and useful in many vision applications. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Circle detection randomized algorithm Sampling strategy Isosceles triangles

来源：评论

学校读者我要写书评

暂无评论

Exact Simulation of the First-Passage Time of Diffusions

引用

JOURNAL OF SCIENTIFIC COMPUTING 2019年第3期79卷 1477-1504页

作者： Herrmann, S. Zucca, C. Univ Bourgogne Franche Comte CNRS UMR 5584 IMB F-21000 Dijon France Univ Torino Dept Math G Peano Via Carlo Alberto 10 I-10123 Turin Italy

Since diffusion processes arise in so many different fields, efficient technics for the simulation of sample paths, like discretization schemes, represent crucial tools in applied probability. Such methods permit to obtain approximations of the first-passage times as a by-product. For efficiency reasons, it is particularly challenging to simulate directly this hitting time by avoiding to construct the whole paths. In the Brownian case, the distribution of the first-passage time is explicitly known and can be easily used for simulation purposes. The authors introduce a new rejection sampling algorithm which permits to perform an exact simulation of the first-passage time for general one-dimensional diffusion processes. The efficiency of the method, which is essentially based on Girsanov's transformation, is described through theoretical results and numerical examples.

关键词： First-passage time Brownian motion Diffusion processes Girsanov's transformation Exact simulation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Stability analysis of sampled-data switched systems with quantization

引用

AUTOMATICA 2016年 69卷 157-168页

作者： Wakaiki, Masashi Yamamoto, Yutaka Univ Calif Santa Barbara Ctr Control Dynam Syst & Computat CCDC Santa Barbara CA 93106 USA Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

We propose a stability analysis method for sampled-data switched linear systems with finite-level static quantizers. In the closed-loop system, information on the active mode of the plant is transmitted to the controller only at each sampling time. This limitation of switching information leads to a mode mismatch between the plant and the controller, and the system may become unstable. A mode mismatch also makes it difficult to find an attractor set to which the state trajectory converges. A switching condition for stability is characterized by the total time when the modes of the plant and the controller are different. Under this condition, we derive an ultimate bound on the state trajectories by using a common Lyapunov function computed from a randomized algorithm. The switching condition can be reduced to a dwell-time condition. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Quantization Sampled-data control Switched systems Lyapunov function randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic sampling for deterministic structural topology optimization with many load cases: Density-based and ground structure approaches

引用

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING 2017年 325卷 463-487页

作者： Zhang, Xiaojia Shelly de Sturler, Eric Paulino, Glaucio H. Georgia Inst Technol Sch Civil & Environm Engn 790 Atlantic Dr Atlanta GA 30332 USA Virginia Tech Dept Math McBryde Hall225 Stanger St Blacksburg VA 24061 USA

We propose an efficient probabilistic method to solve a fully deterministic problem - we present a randomized optimization approach that drastically reduces the enormous computational cost of optimizing designs under many load cases for both continuum and truss topology optimization. Practical structural designs by deterministic topology optimization typically involve many load cases, possibly hundreds or more. The optimal design minimizes a, possibly weighted, average of the compliance under each load case (or some other objective). This means that, in each optimization step, a large finite element problem must be solved for each load case, leading to an enormous computational effort. On the contrary, the proposed randomized optimization method with stochastic sampling requires the solution of only a few (e.g., 5 or 6) finite element problems (large linear systems) per optimization step. Based on simulated annealing, we introduce a damping scheme for the randomized approach. Through numerical examples in two and three dimensions, we demonstrate that the randomization algorithm drastically reduces computational cost to obtain similar final topologies and results (e.g., compliance) to those of standard algorithms. The results indicate that the damping scheme is effective and leads to rapid convergence of the proposed algorithm. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Topology optimization with many load cases Stochastic sampling randomized algorithm Trace estimator Density-based method Ground structure method

来源：评论

学校读者我要写书评

暂无评论

Testing consistency of quartet topologies: A parameterized approach

引用

INFORMATION PROCESSING LETTERS 2013年第22-24期113卷 852-857页

作者： Chang, Maw-Shang Lin, Chuang-Chieh Rossmanith, Peter Acad Sinica Genom Res Ctr Taipei 115 Taiwan Hungkuang Univ Dept Comp Sci & Informat Engn Taichung 43302 Taiwan RVVTH Aachen Univ Dept Comp Sci D-52056 Aachen Germany

Property testing considers the following task: given a function psi over a domain D, a property P and a parameter 0 < epsilon < 1, by querying function values of f over o(vertical bar D vertical bar) elements in D, determine if psi satisfies P or differs from any one which satisfies P in at least epsilon vertical bar D vertical bar elements. We focus on consistency of quartet topologies. Given a set Q of quartet topologies over an n-taxon set and an upper bound k on the number of quartets whose topologies are missing, we present a non-adaptive property tester with one-sided error, which runs in O(1.7321(k)kn(3)/epsilon) time and uses O(kn(3)/epsilon) queries, to test if Q is consistent with an evolutionary tree. (C) 2013 Elsevier B.V. All rights reserved.

关键词： randomized algorithm Property testing Evolutionary tree Quartet method

来源：评论

学校读者我要写书评

暂无评论

LSRN: A PARALLEL ITERATIVE SOLVER FOR STRONGLY OVER- OR UNDERDETERMINED SYSTEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2014年第2期36卷 C95-C118页

作者： Meng, Xiangrui Saunders, Michael A. Mahoney, Michael W. Stanford Univ ICME Stanford CA 94305 USA Stanford Univ Dept Management Sci & Engn Syst Optimizat Lab Stanford CA 94305 USA Stanford Univ Dept Math Stanford CA 94305 USA

We describe a parallel iterative least squares solver named LSRN that is based on random normal projection. LSRN computes the min-length solution to min(x is an element of Rn) vertical bar vertical bar Ax - b vertical bar vertical bar(2), where A is an element of R-mxn with m >> n or m << n, and where A may be rank-deficient. Tikhonov regularization may also be included. Since A is involved only in matrix-matrix and matrix-vector multiplications, it can be a dense or sparse matrix or a linear operator, and LSRN automatically speeds up when A is sparse or a fast linear operator. The preconditioning phase consists of a random normal projection, which is embarrassingly parallel, and a singular value decomposition of size inverted right perpendicular gamma min(m, n) inverted left perpendicular x min(m, n), where gamma is moderately larger than 1, e.g., gamma = 2. We prove that the preconditioned system is well-conditioned, with a strong concentration result on the extreme singular values, and hence that the number of iterations is fully predictable when we apply LSQR or the Chebyshev semi-iterative method. As we demonstrate, the Chebyshev method is particularly efficient for solving large problems on clusters with high communication cost. Numerical results show that on a shared-memory machine, LSRN is very competitive with LAPACK's DGELSD and a fast randomized least squares solver called Blendenpik on large dense problems, and it outperforms the least squares solver from SuiteSparseQR on sparse problems without sparsity patterns that can be exploited to reduce fill-in. Further experiments show that LSRN scales well on an Amazon Elastic Compute Cloud cluster.

关键词： linear least squares overdetermined system underdetermined system rank-deficient minimum-length solution LAPACK sparse matrix iterative method preconditioning LSQR Chebyshev semi-iterative method Tikhonov regularization ridge regression parallel computing random projection random sampling random matrix randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Noise Adding Mechanisms for Approximate Differential Privacy

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第2期62卷 952-969页

作者： Geng, Quan Viswanath, Pramod Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Google Inc New York NY 10011 USA

We study the (nearly) optimal mechanisms in (epsilon, delta)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between epsilon and delta in utility and privacy analysis for histogram-like query functions, and show that the (epsilon, delta)-differential privacy is a framework not much more general than the (epsilon, 0)-differential privacy and (0, delta)-differential privacy in the context of l(1) and l(2) cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of l(1) and l(2) cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (epsilon, delta) -> (0, 0)). We conclude that in (epsilon, delta)-differential privacy, the optimal noise magnitude and the noise power are Theta(min((1/epsilon), (1/delta))) and Theta(min((1/epsilon(2)), (1/delta(2)))), respectively, in the high privacy regime.

关键词： Data privacy randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Bottleneck detour tree of points on a path

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2019年 79卷 30-36页

作者： Aloupis, Greg Carmi, Paz Chaitman-Yerushalmi, Lilach Katz, Matthew J. Langerman, Stefan Tufts Univ Dept Comp Sci Medford MA 02155 USA Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Univ Libre Bruxelles Dept Informat Brussels Belgium

Every pair of points lying on a polygonal path P in the plane has a detour associated with it, which is the ratio between their distance along the path and their Euclidean distance. Given a set S of points along the path, this information can be encoded in a weighted complete graph on S. Among all spanning trees on this graph, a bottleneck spanning tree is one whose maximum edge weight is minimum. We refer to such a tree as a bottleneck detour tree of S. In other words, a bottleneck detour tree of S is a spanning tree in which the maximum detour (with respect to the original path) between pairs of adjacent points is minimum. We show how to find a bottleneck detour tree in expected O (n log(3) n + m) time, where P consists of m edges and vertical bar S vertical bar = n. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Polygonal path Detour Bottleneck spanning tree randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Bounded information dissemination in multi-channel wireless networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第3期31卷 996-1012页

作者： Yan, Yu Yu, Dongxiao Wang, Yuexuan Yu, Jiguo Lau, Francis C. M. Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Qufu Normal Univ Sch Comp Sci Rizhao 276800 Peoples R China

More and more wireless networks and devices now operate on multiple channels, which poses the question: How to use multiple channels to speed up communication? In this paper, we answer this question for the case of wireless ad-hoc networks where information dissemination is a primitive operation. Specifically, we propose a randomized distributed algorithm for information dissemination that is very near the optimal. The general information dissemination problem is to deliver information packets, stored initially in different nodes (the packet holders), to all the nodes in the network, and the objective is to minimize the time needed. With an eye toward the reality, we assume a model where the packet holders are determined by an adversary, and neither the number nor the identities of packet holders are known to the nodes in advance. Not knowing the value of sets this problem apart from broadcasting and all-to-all communication (gossiping). We study the information dissemination problem in single-hop networks with bounded-size messages. We present a randomized algorithm which can disseminate all packets in rounds with high probability, where is the number of available channels and is the bound on the number of packets a message can carry. Compared with the lower bound , the given algorithm is very close to the asymptotical optimal except for an additive factor. Our result provides the first solid evidence that multiple channels can indeed substantially speed up information dissemination, which also breaks the lower bound that holds for single-channel networks (even if is infinity).

关键词： Information dissemination Multi-channel wireless network Distributed algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Mathematical Model and Random Search algorithm for the Optimal Planning Problem of Replacing Traditional Public Transport with Electric

引用

AUTOMATION AND REMOTE CONTROL 2020年第5期81卷 803-818页

作者： Kovalyov, M. Y. Rozin, B. M. Guschinsky, N. N. Natl Acad Sci Belarus United Inst Informat Problems Minsk BELARUS

We investigate the complex optimization problem that arises in the planning of the transition process from traditional public transport to electric transport. We define the assumptions, input and output parameters of the problem, as well as its mathematical model and a randomized algorithm for solving it. We also give an extensive bibliography of publications on the problem at hand.

关键词： electric transport optimization mathematical programming randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：