共查询到20条相似文献,搜索用时 109 毫秒
1.
Remco Duits Michael Felsberg Gösta Granlund Bart ter Haar Romeny 《International Journal of Computer Vision》2007,72(1):79-102
Inspired by the early visual system of many mammalians we consider the construction of-and reconstruction from- an orientation
score
as a local orientation representation of an image,
. The mapping
is a wavelet transform
corresponding to a reducible representation of the Euclidean motion group onto
and oriented wavelet
. This wavelet transform is a special case of a recently developed generalization of the standard wavelet theory and has the
practical advantage over the usual wavelet approaches in image analysis (constructed by irreducible representations of the
similitude group) that it allows a stable reconstruction from one (single scale) orientation score. Since our wavelet transform
is a unitary mapping with stable inverse, we directly relate operations on orientation scores to operations on images in a
robust manner.
Furthermore, by geometrical examination of the Euclidean motion group
, which is the domain of our orientation scores, we deduce that an operator Φ on orientation scores must be left invariant
to ensure that the corresponding operator
on images is Euclidean invariant. As an example we consider all linear second order left invariant evolutions on orientation
scores corresponding to stochastic processes on G. As an application we detect elongated structures in (medical) images and automatically close the gaps between them.
Finally, we consider robust orientation estimates by means of channel representations, where we combine robust orientation
estimation and learning of wavelets resulting in an auto-associative processing of orientation features. Here linear averaging
of the channel representation is equivalent to robust orientation estimation and an adaptation of the wavelet to the statistics
of the considered image class leads to an auto-associative behavior of the system.
The Netherlands Organization for Scientific Research is gratefully acknowledged for financial support. This work has been
supported by EC Grant IST-2003-004176 COSPAL. 相似文献
2.
Abstract We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we
prove the existence of a unique function in
, polyharmonic of order p on each strip
,
, and periodic in its last n variables, whose restriction to the parallel hyperplanes
,
, coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in
. The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal
-splines.
Keywords: cardinal
-splines, polyharmonic functions, multivariable interpolation
Mathematics Subject Classification (2000): 41A05, 41A15, 41A63 相似文献
3.
Eric Allender Anna Bernasconi Carsten Damm Joachim von zur Gathen Michael Saks Igor Shparlinski 《Computational Complexity》2003,12(1-2):23-47
We study various combinatorial complexity measures of
Boolean functions related to some natural arithmetic problems about
binary polynomials, that is, polynomials over
.
In particular, we consider
the Boolean function deciding whether a given polynomial over
is squarefree. We obtain an exponential lower bound on the size of a
decision tree for this function, and derive an asymptotic formula, having
a linear main term, for its average sensitivity. This allows us to estimate
other complexity characteristics such as the formula size, the average decision
tree depth and the degrees of exact and approximative polynomial
representations of this function. Finally, using a different method, we
show that testing squarefreeness and irreducibility of polynomials over
cannot be done in
for any odd prime p. Similar results are
obtained for deciding coprimality of two polynomials over
as well. 相似文献
4.
5.
6.
R. F. Streater 《Open Systems & Information Dynamics》2004,11(4):359-375
Let H0 be a selfadjoint operator such that Tr
is of trace class for some
, and let
denote the set of ε-bounded forms, i.e.,
for some
0 $$" align="middle" border="0">
. Let χ := Span
. Let
denote the underlying set of the quantum information manifold of states of the form
. We show that if Tr
,
Presented at the 36th Symposium on Mathematical Physics, ‘Open Systems & Quantum Information’, Toruń, Poland, June 9-12, 2004. 相似文献
1. | the map Φ,
| |
2. | The Orlicz space defined by Φ is the tangent space of at ρ0; its affine structure is defined by the (+1)-connection of Amari | |
3. | The subset of a ‘hood of ρ0, consisting of p-nearby states (those obeying for some 1$$" align="middle" border="0"> ) admits a flat affine connection known as the (-1) connection, and the span of this set is part of the cotangent space of | |
4. | These dual structures extend to the completions in the Luxemburg norms. |
7.
Emanuele Viola 《Computational Complexity》2005,13(3-4):147-188
We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function
computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant
such that every circuit of size
fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a
computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies
under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function
(i.e. there is a constant
such that every circuit of size
fails to compute f on some input) for every positive constant
there is no black-box construction of a
computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes. 相似文献
8.
9.
The generalized Zakharov system (ZS) couples a dispersive field E (scalar or vectorial) and
nondispersive fields
with a propagating speed of
. In this paper, we extend our one-dimensional time-splitting spectral method (TSSP) for the generalized ZS into higher dimension.
A main new idea is to reformulate the multi-dimensional wave equations for the nondispersive fields into a first-order system
using a change of variable defined in the Fourier space. The proposed scheme TSSP is unconditionally stable, second-order
in time and spectrally accurate in space. Moreover, in the subsonic regime, it allows numerical capturing of the subsonic
limit without resolving the small parameters
. Numerical examples confirm these properties of this method 相似文献
10.
The Sum of D Small-Bias Generators Fools Polynomials of Degree D 总被引:1,自引:1,他引:0
Emanuele Viola 《Computational Complexity》2009,18(2):209-217
11.
12.
Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack;
if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape
domain
as an abstract interpretation of concrete states, which we then refine into an abstract domain
which is more concrete than
and, hence, leads to a more precise escape analysis than
. We provide optimality results for both
and
, in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois
insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of
is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of
Java (bytecode) applications. 相似文献
13.
Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion
, where
is a compact set of matrices, is asymptotically stable if and only if
can be extended to a set
of nonnegative matrices B with
or
. Similar results are derived for differential inclusions. 相似文献
14.
Coupling and self-stabilization 总被引:1,自引:0,他引:1
A randomized self-stabilizing algorithm
is an algorithm that, whatever the initial configuration is, reaches a set
of М legal configurations} in finite time with probability 1. The proof of convergence towards
is generally done by exhibiting a potential function
, which measures the “vertical” distance of any configuration to
, such that
decreases with non-null probability at each step of
. We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance
between any pair of configurations, such that
decreases in expectation at each step of
. In contrast with classical methods, our coupling method does not require the knowledge of
. In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different
measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as
examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs. 相似文献
15.
16.
We construct a linear interval system Ax = b with a 4 × 4 interval matrix whose all proper interval coefficients (there are also some noninterval ones) are of the form [–, ]. It is proved that for each > 0, the interval hull
and interval hull of the midpoint preconditioned system
satisfy
and
, hence midpoint preconditioning produces a 100% overestimation of
independently of in this case. The example was obtained as a result of an extensive MATLAB search. 相似文献
17.
On Defining Integers And Proving Arithmetic Circuit Lower Bounds 总被引:1,自引:1,他引:0
Peter Bürgisser 《Computational Complexity》2009,18(1):81-103
18.
Hiroki Ishizaka Hiroki Arimura Takeshi Shinohara 《Annals of Mathematics and Artificial Intelligence》1998,23(1-2):101-115
This paper is concerned with the problem of finding a hypothesis in
consistent with given positive and negative examples. The hypothesis class
consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages.
Especially, we consider the problem from the point of view of the consistency problem for
. The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative
examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of
efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete
for many hypothesis spaces. In this paper, the problem for the class
is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained
by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for
in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by
the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result,
we have that the consistency problem for
is solved in polynomial time using membership queries.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
19.
Hierarchical matrices (
-matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for
-matrices is almost optimal. In this paper we present an algebraic approach for constructing
-matrices which combines multilevel clustering methods with
-matrix arithmetic to compute the
-inverse,
-LU, and the
-Cholesky factors of a matrix. Then the
-inverse,
-LU or
-Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical
results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or
AMG, for solving some large, sparse linear systems, and is comparable to other
-matrix constructions based on Nested Dissection. 相似文献
20.
Let
be a finite field withq elements and
a rational function over
. No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on
. The problem has been shown to be in co-R
co-NP, and in this paper we prove that it is inR
NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over
. Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented. 相似文献