21 
Bone Graphs: Medial Abstraction for Shape Parsing and Object RecognitionMacrini, Diego 31 August 2010 (has links)
The recognition of 3D objects from their silhouettes demands a shape representation which is invariant to minor changes in viewpoint and articulation. This invariance can be achieved by parsing a silhouette into parts and relationships that are stable across similar object views. Medial descriptions, such as skeletons and shock graphs, attempt to decompose a shape into parts, but suffer from instabilities that lead to similar shapes being represented by dissimilar part sets. We propose a novel shape parsing approach based on identifying and regularizing the ligature structure of a given medial axis. The result of this process is a bone graph, a new medial shape abstraction that captures a more intuitive notion of an object’s parts than a skeleton
or a shock graph, and offers improved stability and withinclass deformation
invariance over the shock graph.
The bone graph, unlike the shock graph, has attributed edges that specify how and where two medial parts meet. We propose a novel shape matching framework that exploits this relational information by formulating the problem as an inexact directed acyclic graph matching, and extending a leading bipartite graphbased matching framework introduced for matching shock graphs. In addition to accommodating the relational information, our new framework is better able to enforce hierarchical and sibling constraints between nodes, resulting in a more general and more powerful matching framework. We evaluate our matching framework with respect to a competing shock graph matching framework, and show that for the task of viewbased object categorization, our matching framework applied to bone graphs outperforms the competing framework. Moreover, our matching framework applied to shock graphs also outperforms the competing shock graph matching algorithm, demonstrating the generality and improved performance of our matching algorithm.

22 
Tree Spanners of Simple GraphsPapoutsakis, Ioannis 09 August 2013 (has links)
A tree $t$spanner $T$ of a simple graph $G$ is a spanning tree of $G$,
such that for every pair of vertices of $G$ their distance in $T$ is at
most $t$ times their distance in $G$, where $t$ is called a stretch
factor of $T$ in $G$. It has been shown that there is a linear time
algorithm to find a tree 2spanner in a graph;
it has also been proved that, for each $t>3$, determining whether a graph
admits a tree $t$spanner is an NPcomplete problem. This thesis studies
tree $t$spanners from both theoretical and algorithmic perspectives.
In particular, it is proved that a nontree graph admits a unique tree
$t$spanner for at
most one value of stretch factor $t$. As a corollary, a nontree
bipartite graph cannot admit a unique tree $t$spanner for any $t$.
But, for each $t$, there are infinitely many nontree graphs that admit
exactly one tree $t$spanner. Furthermore, for each $t$, let U($t$) be
the set of graphs being the union of two tree $t$spanners of a graph.
Although graphs in U(2) do not have cycles of length greater than 4,
graphs in U(3) may contain cycles of arbitrary length. It turns out that
any even cycle is an induced subgraph of a graph in U(3), while no graph in
U(3) contains an induced odd cycle other than a triangle; graphs in U(3)
are shown to be perfect. Also, properties of induced even cycles of graphs
in U(3) are presented. For each $t>3$, though, graphs in U($t$) may
contain induced odd cycles of any length.
Moreover, there is an efficient algorithm to recognize graphs that admit a
tree 3spanner of diameter at most 4, while it is proved that, for
each $t>3$, determining whether a graph admits a tree $t$spanner of
diameter at most $t+1$ is an NPcomplete problem. It is not known if it
is hard to recognize graphs that admit a tree 3spanner of general diameter;
however integer programming is employed to provide certificates of tree
3spanner inadmissibility for a family of graphs.

23 
PScout: Analyzing the Android Permission SpecificationAu, Kathy Wain Yee 18 March 2013 (has links)
Modern smartphone operating systems (OSs) have been developed with a greater emphasis on security and protecting privacy. One of the security mechanisms these systems use is permission system. We perform an analysis of the Android permission system in an attempt to begin answering some of the questions that have arisen about its design and implementation. We developed PScout, a tool that extracts the permission specification from the Android OS source code using static analysis and analyzed 5 versions of Android spanning version 2.2 up to the recently released Android 4.1. Our main findings are that while there is little redundancy in the permission specification, if applications could be constrained to only use documented APIs, then about 1826% of the nonsystem permissions can be hidden. Finally, we find that a tradeoff exists between enabling leastprivilege security with finegrained permissions and maintaining stability of the permission specification as the Android OS evolves.

24 
Customizable Services for Applicationlayer Overlay NetworksZhao, Yu 17 July 2013 (has links)
Applicationlayer overlay networks have emerged as a powerful paradigm for providing network services. While most approaches focus on providing a predefined set of network services, we provide a mechanism for network applications to deploy customizable data delivery services. We present the design, implementation, and evaluation of applicationdefined data delivery services that are executed at overlay nodes by transmitting messages marked with service identifiers. In our approach, a data delivery services is specified as an XML specification that define a finitestate machines that respond to network events, and perform a set of network primitives. We implemented a mechanism to execute these XML specifications in the HyperCast overlay middleware, and have evaluated this mechanism quantitatively on an Emulab testbed. The experiments show that our approach is effective in realizing a variety of data delivery services without incurring unreasonable performance overhead.

25 
Mechanism Design with Partial RevelationHyafil, Nathanael 28 July 2008 (has links)
With the emergence of the Internet as a global structure for communication and interaction,
many “business to consumer” and “business to business” applications have migrated online,
thus increasing the need for software agents that can act on behalf of people, institutions or
companies with private and often conflicting interests. The design of such agents, and the
protocols (i.e., mechanisms) through which they interact, has therefore naturally become an
important research theme.
Classical mechanism design techniques from the economics literature do not account for the costs
entailed with the full revelation of preferences that they require. The aim of this thesis is to
investigate how to design mechanisms that only require the revelation
of partial preference information and are applicable in any mechanism design context. We call this
partial revelation mechanism design. Reducing revelation
costs is thus our main concern. With only partial revelation, the designer has some remaining
uncertainty over the agents’ types, even after the mechanism has been executed. Thus, in
general, the outcome chosen will not be optimal with respect to the designer’s objective function.
This alone raises interesting questions about which (part of the) information should be
elicited in order to minimize the degree of suboptimality incurred by the mechanism. But this
suboptimality of the mechanism’s outcome choice function has additional important consequences:
most of the results in classical mechanism design which guarantee that agents will
reveal their type truthfully to the mechanism rely on the fact that the optimal outcome is chosen.
We must therefore also investigate if, and how, appropriate incentives can be maintained
in partial revelation mechanisms.
We start by presenting our own model for partial revelation mechanism design. Our second
contribution is a negative one regarding the quasiimpossibility of
implementing partial revelation mechanisms with exact incentive properties. The rest of the
thesis shows, in different settings, how this negative result can be bypassed in various settings,
depending on the designer's objective (e.g., social welfare, revenue...) and the interaction type
(sequential or one shot). Finally, we study how the approximation of the
incentive properties can be further improved when necessary, and in the process, introduce
and proves the existence of a new equilibrium concept.

26 
Neural Representation, Learning and Manipulation of UncertaintyNatarajan, Rama 21 April 2010 (has links)
Uncertainty is inherent in neural processing due to noise in sensation and the sensory transmission processes, the illposed nature of many perceptual tasks, and temporal dynamics of the natural environment, to name a few causes. A wealth of evidence from physiological and behavioral experiments show that these various forms of uncertainty have major effects on perceptual learning and inference. In order to use sensory inputs efficiently to make decisions and guide behavior, neural systems must represent and manipulate information about uncertainty in their computations.
In this thesis, we first consider how spiking neural populations might encode and decode information about continuous dynamic stimulus variables including the uncertainty about them. We explore the efficacy of a complex encoder that is paired with a simple decoder which allows computationally straightforward representation and manipulation of dynamically changing uncertainty. The encoder we present takes the form of a biologically plausible recurrent spiking neural network where the output population recodes its inputs to produce spikes that are independently decodeable. We show that this network can be learned in a supervised manner, by a simple, local learning rule. We also demonstrate that the coding scheme can be applied recursively to carry out meaningful uncertaintysensitive computations such as dynamic cue combination.
Next, we explore the computational principles that underlie nonlinear response characteristics such as perceptual bias and uncertainty observed in audiovisual spatial illusions that involve multisensory interactions with conflicting cues. We examine in detail, the explanatory power of one particular causal model in characterizing the impact of conflicting inputs on perception and behavior. We also attempt to understand from a computational perspective, whether and how different task instructions might modulate the interaction of information from individual (visual and auditory) senses. Our analyses reveal some new properties of the sensory likelihoods and stimulus prior which were thought to be well described by Gaussian functions. Our results conclude that taskspecific expectations can influence perception in ways that relate to a choice of inference strategy.

27 
Computing exact approximations of a Chaitin omega numberShu, ChiKou January 2004 (has links)
A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (selfdelimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is noncomputable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the nth step, the algorithm produces four main output files: all halting strings, looping strings, runtime errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or runtime error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.

28 
Mechanism Design with Partial RevelationHyafil, Nathanael 28 July 2008 (has links)
With the emergence of the Internet as a global structure for communication and interaction,
many “business to consumer” and “business to business” applications have migrated online,
thus increasing the need for software agents that can act on behalf of people, institutions or
companies with private and often conflicting interests. The design of such agents, and the
protocols (i.e., mechanisms) through which they interact, has therefore naturally become an
important research theme.
Classical mechanism design techniques from the economics literature do not account for the costs
entailed with the full revelation of preferences that they require. The aim of this thesis is to
investigate how to design mechanisms that only require the revelation
of partial preference information and are applicable in any mechanism design context. We call this
partial revelation mechanism design. Reducing revelation
costs is thus our main concern. With only partial revelation, the designer has some remaining
uncertainty over the agents’ types, even after the mechanism has been executed. Thus, in
general, the outcome chosen will not be optimal with respect to the designer’s objective function.
This alone raises interesting questions about which (part of the) information should be
elicited in order to minimize the degree of suboptimality incurred by the mechanism. But this
suboptimality of the mechanism’s outcome choice function has additional important consequences:
most of the results in classical mechanism design which guarantee that agents will
reveal their type truthfully to the mechanism rely on the fact that the optimal outcome is chosen.
We must therefore also investigate if, and how, appropriate incentives can be maintained
in partial revelation mechanisms.
We start by presenting our own model for partial revelation mechanism design. Our second
contribution is a negative one regarding the quasiimpossibility of
implementing partial revelation mechanisms with exact incentive properties. The rest of the
thesis shows, in different settings, how this negative result can be bypassed in various settings,
depending on the designer's objective (e.g., social welfare, revenue...) and the interaction type
(sequential or one shot). Finally, we study how the approximation of the
incentive properties can be further improved when necessary, and in the process, introduce
and proves the existence of a new equilibrium concept.

29 
Algorithms in 3D Shape SegmentationSimari, Patricio Dario 23 February 2010 (has links)
Surfaces in 3D are often represented by polygonal meshes and point clouds obtained from 3D modeling tools or acquisition processes such as laser range scanning. While these formats are very flexible and allow the representation of a wide variety of shapes, they are rarely appropriate in their raw form for the range of applications that benefit from their use. Their decomposition into simpler constituting parts is referred to as shape segmentation, and its automation remains a challenging area within computer science.
We will present and analyze different aspects of shape segmentation. We begin by looking at useful segmentation criteria and present a categorization of current methods according to which type of criteria they address, dividing them into affinitybased, modelfitting, and propertybased approaches.
We then present two algorithmic contributions in the form of a modelbased and a propertybased segmentation approaches. These share the goals of automatically finding redundancy in a shape and propose shape representations that leverage this redundancy to achieve descriptive compactness. The first is a method for segmenting a surface into piecewise ellipsoidal parts, motivated by the fact that most organic objects and many manufactured objects have large curved areas. The second is an algorithm for robustly detecting global and local planarreflective symmetry and a hierarchical segmentation approach based on this detection method.
We note within these approaches the variation in segmentations resulting from different criteria and propose a way to generalize the segmentation problem to heterogenous criteria. We introduce a framework and relevant algorithms for multiobjective segmentation of 3D shapes which allow for the incorporation of domainspecific knowledge through multiple objectives, each of which refers to one or more segmentation labels. They can assert properties of an individual part or they can refer to part interrelations. We thus cast the segmentation problem as an optimization minimizing an aggregate objective function which combines all objectives as a weighted sum.
We conclude with a summary and discussion of the contributions presented, lessons learned, and a look at the open questions remaining and potential avenues of continued research.

30 
On Generalizations of Gowers NormsHatami, Hamed 01 March 2010 (has links)
Inspired by the definition of Gowers norms we study integrals of products of multivariate functions. The $L_p$ norms, certain trace norms, and the Gowers norms are all defined by taking the proper root of one of these integrals. These integrals are important from a combinatorial point of view as inequalities between them are useful
in understanding the relation between various subgraph densities.
Lov\'asz asked the following questions: (1) Which integrals correspond to norm functions? (2) What are the common properties of the corresponding normed spaces? We address these two questions.
We show that such a formula is a norm if and only if it satisfies a H\"older type inequality. This condition turns out to be very useful: First we apply it to prove various necessary conditions on the structure of the integrals which correspond to norm functions.
We also apply the condition to an important conjecture of Erd\H{o}s, Simonovits, and Sidorenko. Roughly speaking, the conjecture says that among all graphs with the same edge density, random graphs contain the least number of copies of every bipartite graph. This had been verified previously for trees, the $3$dimensional cube, and a few other families of bipartite graphs. The special case of the conjecture for paths, one of the simplest families of bipartite
graphs, is equivalent to the BlakleyRoy theorem in linear algebra.
Our results verify the conjecture for certain graphs including all hypercubes, one of the important classes of bipartite graphs, and thus generalize a result of Erd\H{o}s and Simonovits. In fact, for hypercubes we can prove statements that are surprisingly stronger than the assertion of the conjecture.
To address the second question of Lov\'asz we study these normed spaces from a geometric point of view, and determine their moduli of smoothness and convexity. These two parameters are among the most important invariants in Banach space theory. Our result in particular determines the moduli of smoothness and convexity of Gowers norms. In some cases we are able to prove the Hanner
inequality, one of the strongest inequalities related to the concept
of smoothness and convexity. We also prove a complex interpolation theorem for these normed spaces, and use this and the Hanner
inequality to obtain various optimum results in terms of the constants involved in the definition of moduli of smoothness and
convexity.

Page generated in 0.0713 seconds