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

Topological repairing of 3D digital images

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2008年第3期30卷 249-274页

作者： Siqueira, Marcelo Latecki, Longin Jan Tustison, Nicholas Gallier, Jean Gee, James Univ Fed Mato Grosso do Sul Dept Computacao & Estat BR-79070900 Campo Grande MS Brazil Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA Univ Penn Penn Image & Comp Sci Lab Dept Radiol Philadelphia PA 19104 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

We present here a new randomized algorithm for repairing the topology of objects represented by 3D binary digital images. By "repairing the topology", we mean a systematic way of modifying a given binary image in order to produce a similar binary image which is guaranteed to be well-composed. A 3D binary digital image is said to be well-composed if, and only if, the square faces shared by background and foreground voxels form a 2D manifold. Well-composed images enjoy some special properties which can make such images very desirable in practical applications. For instance, well-known algorithms for extracting surfaces from and thinning binary images can be simplified and optimized for speed if the input image is assumed to be well-composed. Furthermore, some algorithms for computing surface curvature and extracting adaptive triangulated surfaces, directly from the binary data, can only be applied to well-composed images. Finally, we introduce an extension of the aforementioned algorithm to repairing 3D digital multivalued images. Such an algorithm finds application in repairing segmented images resulting from multi-object segmentations of other 3D digital multivalued images.

关键词： well-composed images digital topology randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Uniform hashing in constant time and optimal space

引用

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 85-96页

作者： Pagh, Anna Pagh, Rasmus IT Univ Copenhagen DK-2300 Copenhagen S Denmark

Many algorithms and data structures employing hashing have been analyzed under the uniform hashing assumption, i.e., the assumption that hash functions behave like truly random functions. Starting with the discovery of universal hash functions, many researchers have studied to what extent this theoretical ideal can be realized by hash functions that do not take up too much space and can be evaluated quickly. In this paper we present an almost ideal solution to this problem: a hash function h : U. V that, on any set of n inputs, behaves like a truly random function with high probability, can be evaluated in constant time on a RAM and can be stored in (1+epsilon) n lg vertical bar V vertical bar + O(n+lg lg vertical bar U vertical bar) bits. Here epsilon can be chosen to be any positive constant, so this essentially matches the entropy lower bound. For many hashing schemes this is the first hash function that makes their uniform hashing analysis come true, with high probability, without incurring overhead in time or space.

关键词： hash function uniform hashing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

On approximating the depth and related problems

引用

SIAM JOURNAL ON COMPUTING 2008年第3期38卷 899-921页

作者： Aronov, Boris Har-Peled, Sariel Polytech Univ Dept Comp & Informat Sci New York NY 11201 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA

We study the question of finding a deepest point in an arrangement of regions and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when the deepest point is shallow. This implies, among other results, a fast algorithm for approximately solving linear programming problems with violations. We also use this technique to approximate the disk covering the largest number of red points, while avoiding all the blue points, given two such sets in the plane. Using similar techniques implies that approximate range counting queries have roughly the same time and space complexity as emptiness range queries.

关键词： approximation randomized algorithms computational geometry

来源：评论

学校读者我要写书评

暂无评论

Hard Bounds on the Probability of Performance With Application to Circuit Analysis

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2008年第10期55卷 3178-3187页

作者： Lagoa, Constantino M. Dabbene, Fabrizio Tempo, Roberto Penn State Univ University Pk PA 16802 USA Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy Politecn Torino CNR Inst IEIIT Turin Italy

In this paper, we address the problem of analyzing the performance of an electrical circuit in the presence of uncertainty in the network components. In particular, we consider the case when the uncertainties are known to be bounded and have probabilistic nature, and aim at evaluating the probability that a given system property holds. In contrast with the standard Monte Carlo approach, which utilizes random samples of the uncertainty to estimate "soft" bounds on this probability, we present a methodology that provides "hard" (deterministic) upper and lower bounds. To this aim, we develop an iterative algorithm, based on a property oracle, which is shown to converge asymptotically to the true probability of property satisfaction. Construction of the property oracles for specific applications in circuit analysis is explicitly presented. In particular, we study in full detail the problems of assessing the probability that the gain of a purely resistive network does not exceed a prescribed value, and of evaluating the probability of stability of an uncertain network under parameter variations. The paper is accompanied by illustrating examples and extensive numerical simulations.

关键词： Circuit simulation control theory ladder networks probabilistic methods randomized algorithms resistive circuits robustness

来源：评论

学校读者我要写书评

暂无评论

Analysis of Distributed Random Grouping for aggregate computation on wireless sensor networks with randomly changing graphs

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2008年第8期19卷 1136-1149页

作者： Chen, Jen-Yeu Hu, Jianghai Natl Dong Hwa Univ Dept Elect Engn Hualien 97401 Taiwan Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

Dynamical connection graph changes are inherent in networks such as peer-to-peer networks, wireless ad hoc networks, and wireless sensor networks. Considering the influence of the frequent graph changes is, thus, essential for precisely assessing the performance of applications and algorithms on such networks. In this paper, using stochastic hybrid systems (SHSs), we model the dynamics and analyze the performance of an epidemic-like algorithm, Distributed Random Grouping (DRG), for average aggregate computation on a wireless sensor network with dynamical graph changes. Particularly, we derive the convergence criteria and the upper bounds on the running time of the DRG algorithm for a set of graphs that are individually disconnected but jointly connected in time. An effective technique for the computation of a key parameter in the derived bounds is also developed. Numerical results and an application extended from our analytical results to control the graph sequences are presented to exemplify our analysis.

关键词： performance analysis aggregate computation sensor networks randomized algorithms distributed algorithms stochastic hybrid systems graph theory

来源：评论

学校读者我要写书评

暂无评论

A randomized competitive algorithm for evaluating priced AND/OR trees

引用

21st Annual Symposium on Theoretical Aspects of Computer Science

作者： Laber, Eduardo Sany Dept Informat PUC Rio BR-22453901 Rio De Janeiro RJ Brazil

ISBN: (纸本)9783540212362

Recently, Charikar et al. investigated the problem of evaluating AND/OR trees, with non-uniform costs on its leaves, from the perspective of the competitive analysis. For an AND/OR tree T they presented a mu(T)-competitive deterministic polynomial time algorithm, where mu(T) is the number of leaves that must be read, in the worst case, in order to determine the value of T. Furthermore, they proved that mu(T) is a lower bound on the deterministic competitiveness, which assures the optimality of their algorithm. The power of randomization in this context has remained as an open question. Here, we take a step towards solving this problem by presenting a 5/6 mu(T)-competitive randomized polynomial time algorithm. This contrasts with the best known lower bound mu(T)/2. (c) 2008 Elsevier B.V. All rights reserved.

关键词： randomized algorithms competitive analysis function evaluation AND/OR trees

来源：评论

学校读者我要写书评

暂无评论

Constrained Sequential Resource Allocation and Guessing Games

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第11期54卷 4946-4965页

作者： Chang, Nicholas B. Liu, Mingyan Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

In this paper, we consider a constrained sequential resource allocation problem where an individual needs to accomplish a task by repeatedly guessing/investing a sufficient level of effort/input. If the investment falls short of a minimum required level that is unknown to the individual, she fails;with each unsuccessful attempt, the individual then increases the input and tries again until she succeeds. The objective is to complete the task with as little resources/cost as possible subject to a delay constraint. The optimal strategy lies in the proper balance between 1) selecting a level (far) below the minimum required and therefore having to try again, thus wasting resources, and 2) selecting a level (far) above the minimum required, and therefore, overshooting and wasting resources. A number of motivating applications arising from communication networks are provided. Assuming that the individual has no knowledge on the distribution of the minimum effort required to complete the task, we adopt a worst-case cost measure and a worst-case delay measure to formulate the above constrained optimization problem. We derive a class of optimal strategies, shown to be randomized, and obtain their performance as a function of the constraint.

关键词： Competitive analysis constrained optimization data query and search exponential functions minimax problems online algorithms randomized algorithms stochastic analysis

来源：评论

学校读者我要写书评

暂无评论

PROBABILISTIC ROBUSTNESS ANALYSIS-RISKS, COMPLEXITY, AND algorithms

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2008年第5期47卷 2693-2723页

作者： Chen, Xinjia Zhou, Kemin Aravena, Jorge Louisiana State Univ Dept Elect & Comp Engn Baton Rouge LA 70803 USA

It is becoming increasingly apparent that probabilistic approaches can overcome conservatism and computational complexity of the classical worst-case deterministic framework and may lead to designs that are actually safer. In this paper we argue that a comprehensive probabilistic robustness analysis requires a detailed evaluation of the robustness function, and we show that such an evaluation can be performed with essentially any desired accuracy and confidence using algorithms with complexity that is linear in the dimension of the uncertainty space. Moreover, we show that the average memory requirements of such algorithms are absolutely bounded and well within the capabilities of today's computers. In addition to efficiency, our approach permits control over statistical sampling error and the error due to discretization of the uncertainty radius. For a specific level of tolerance of the discretization error, our techniques provide an efficiency improvement upon conventional methods which is inversely proportional to the accuracy level;i.e., our algorithms get better as the demands for accuracy increase.

关键词： robustness analysis risk analysis randomized algorithms uncertain system computational complexity

来源：评论

学校读者我要写书评

暂无评论

The fractional congestion bound for efficient edge disjoint routing

引用

NETWORKS 2008年第3期51卷 190-199页

作者： Baveja, Alok Rutgers State Univ Sch Business Camden NJ 08102 USA

This article investigates the following problem: Given the fractional relaxation of the edge disjoint routing problem, how small a fractional congestion is sufficient to guarantee efficient edge disjoint routing? That is, what is the largest possible value v such that a fractional flow with congestion at most v, can be efficiently converted into an edge disjoint routing? Leighton, Lu, Rao, and Srinivasan (SIAM J Comput 2001) have established that fractional congestion of at most the order of O(1/(d log k)) is sufficient, where d is the maximum path length in the fractional relaxation, and k is the number of pairs to be routed. It is also known that Theta)(1/d) is the correct bound, if we are only interested in an existence result (Leighton, Rao, and Srinivasan, Hawaii International Conference on System Sciences, 1998). Motivated by the fact that d is small for many types of routing problems, specifically, polylogarithmic for expander graphs, this article improves upon the former result by showing O(11(d log d)) fractional congestion to suffice. (C) 2007 Wiley Periodicals, Inc.

关键词： disjoint paths routing multicommodity flow randomized algorithms rounding

来源：评论

学校读者我要写书评

暂无评论

A pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2008年第2期24卷 503-520页

作者： Chung, Kuo-Liang Huang, Yong-Huai Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 106 Taiwan

Shape analysis is a fundamental problem in image processing field. In shape analysis, lines, circles, and ellipses are three important features since they often occur in the image. Based on the determined windows on the edge map, this paper first presents a novel pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses. Especially, our proposed strategy can be plugged into several existing randomized algorithms to reduce the required computation time while preserving the same robustness. In addition, some related time complexity analyses are provided to show the Computational advantage of our proposed strategy. Under some real images, experimental results confirm our theoretic analyses.

关键词： circles ellipses lines pruning-and-voting strategy randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：