2020-11-01T00:04:33Zhttp://edoc.mpg.de/ac_ft_oai.ploai:edoc.mpg.de:2017952012-09-1987:934
Conference-Paper
A Framework for Dynamic Connectivity Meshes
English
ACM
New York, USA
2003
2004-07-12
49
55
Darmstadt, Germany
2003-03-31
OpenSG Symposium 2003
Implementing algorithms that are based on dynamic triangle meshes
often requires updating internal data-structures as soon as the
connectivity of the mesh changes. The design of a class hierarchy
that is able to deal with such changes is particularly challenging if the
system reaches a certain complexity.
The paper proposes a software design that enables the users to
efficiently implement algorithms that can handle these dynamic
changes while still maintaining a certain encapsulation of the
single components.
Our design is based on a callback mechanism. A client can register at some {\tt
Info}-object and gets informed whenever a change of the connectivity occurs.
This way the client is able to keep internal data up-to-date. Our framework
enables us to write small client classes that cover just a small dedicated
aspect of necessary updates related to the changing connectivity. These small
components can be combined to more complex modules and can often easily be
reused. Moreover, we do not have to store related 'dynamic data' in one central
place, e.g. the mesh, which could lead to a significant memory overhead if an
application uses some modules just for a short time.
We have used and tested this class design extensively for
implementing 'Dynamic Connectivity Meshes and
Applications~\cite{Vorsatz:2003:DRA}'. Additionally, as a
feasibility study, we have implemented and integrated our concept in the
\OM-framework.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9130&did=201795&ver=0
J.
Vorsatz
Jens
H.-P.
Seidel
Hans-Peter
D.
Reiners
D.
C125675300671F7B-7DB11C9D8C3B02F5C1256CED002FE17A-Vorsatz:2003:FDC
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018102010-12-0287:932
Conference-Paper
Citius altius fortius: Lessons learned from the Theorem Prover WALDMEISTER
English
Elsevier
Amsterdam, The Netherlands
2003
2004-06-22
1
13
Valencia, Spain
2003-06-12
Proceedings of the 4th International Workshop on First Order Theorem Proving, FTP'03
Electronic Notes in Theoretical Computer Science
In the last years, the development of automated theorem
provers has been advancing in a so to speak Olympic spirit,
following the motto "faster, higher, stronger"; and the
{Waldmeister} system has been a part of that endeavour. We
will survey the concepts underlying this prover, which
implements Knuth-Bendix completion in its unfailing variant.
The system architecture is based on a strict separation of
active and passive facts, and is realized via specifically
tailored representations for each of the central data
structures: indexing for the active facts, set-based
compression for the passive facts, successor sets for the
conjectures. In order to cope with large search spaces,
specialized redundancy criteria are employed, and the
empirically gained control knowledge is integrated to ease
the use of the system. We conclude with a discussion of
strengths and weaknesses, and a view of future prospects.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9134&did=201810&ver=0
T.
Hillenbrand
Thomas
I.
Dahn
Ingo
L.
Vigneron
Laurent
C1256104005ECAFC-13192155732F5DD1C1256D32004620FA-Hillenbrand2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018232010-12-0287:932
Conference-Paper
The New WALDMEISTER Loop at Work
English
Springer
Berlin, Germany
2003
2004-06-23
317
321
Miami, Florida
2003-07-28
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Artificial Intelligence
We present recent developments within the theorem prover \textsc{Waldmeister}.
They rely on a novel organization of the underlying saturation-based proof
procedure into a system architecture. As is known, the saturation process tends
to quickly fill the memory available unless preventive measures are employed.
To overcome this problem, our new ``\textsc{Waldmeister} loop'' features a
highly compact representation of the search state, exploiting its inherent
structure. The implementation just being available, the cost and the benefits
of the concept now can exactly be measured. Indeed are our expectations met
concerning the drastic cut-down of memory usage with only moderate overhead of
time.
In addition it has turned out that the revealed structure of the search state
paves the way to an easily implemented parallelization of the prover with
modest communication requirements and rewarding speed-ups. In order to minimize
communication-related latencies, we discuss some variations of the loop to
maximally profit from multiple processors.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9137&did=201823&ver=0
J.-M.
Gaillourdet
Jean-Marie
T.
Hillenbrand
Thomas
B.
Löchner
Bernd
H.
Spies
Hendrik
F.
Baader
Franz
C1256104005ECAFC-F7AE319E928299C3C1256D01002DD440-GaillourdetHillenbrandLoechner2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018342012-09-1987:931
Conference-Paper
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
English
Springer
Berlin, Germany
2003
2004-06-15
230
241
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
Given the positions of $n$ sites in a radio network
we consider the problem of finding routes between any pair of sites
that minimize energy consumption and do not use more than some
constant number $k$ of hops. Known exact algorithms for this problem
required $\Omega(n \log n)$ per query pair $(p,q)$. In this paper we
relax the exactness requirement and only require approximate
$(1+\epsilon)$ solutions which allows us to derive schemes which
guarantee constant query time using linear space and
$O(n\log n)$ preprocessing time. The dependence on $\epsilon$ is
polynomial in $1/\epsilon$.
One tool used might be of independent interest:
For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9141&did=201834&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3-540-20064-9
C1256428004B93B8-1EAC93284072E6C4C1256E150042DA25-Matijevic2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018352012-09-1987:931
Conference-Paper
On the Competitive Ratio for Online Facility Location
English
Springer
Berlin, Germany
2003
2004-06-15
637
652
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
We consider the problem of Online Facility Location, where demands arrive
online and must be irrevocably assigned to an open facility upon arrival. The
objective is to minimize the sum of facility and assignment costs. We prove
that the competitive ratio for Online Facility Location is $\Theta(\frac{\log
n}{\log\log n})$. On the negative side, we show that no randomized algorithm
can achieve a competitive ratio better than $O(\frac{\log n}{\log\log n})$
against an oblivious adversary even if the demands lie on a line segment. On
the positive side, we present a deterministic algorithm achieving a competitive
ratio of $O(\frac{\log n}{\log\log n})$. The analysis is based on a
hierarchical decomposition of the optimal facility locations such that each
component either is relatively well-separated or has a relatively large
diameter, and a potential function argument which distinguishes between the two
kinds of components.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9142&did=201835&ver=0
D.
Fotakis
Dimitris
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3-540-40493-7
C1256428004B93B8-6A9C56FA859349F5C1256D030043742D-Fot03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018392012-09-1987:934
Conference-Paper
Visualization of Volume Data with Quadratic Super Splines
English
IEEE
Los Alamitos, USA
2003
2004-08-03
393
400
Seattle, USA
2003-10-19
IEEE Visualization 2003 (VIS-03)
We develop a new approach to reconstruct non-discrete models from
gridded volume samples. As a model, we use quadratic trivariate super
splines on a uniform tetrahedral partition . The approximating splines
are determined in a natural and completely symmetric way by averaging
local data samples, such that appropriate smoothness conditions are
automatically satisfied. On each tetrahedron of , the
quasi-interpolating spline is a polynomial of total degree two which
provides several advantages including efficient computation,
evaluation and visualization of the model. We apply Bernstein-B´ezier
techniques well-known in CAGD to compute and evaluate the trivariate
spline and its gradient. With this approach the volume data can be
visualized efficiently e.g. with isosurface raycasting. Along an
arbitrary ray the splines are univariate, piecewise quadratics and
thus the exact intersection for a prescribed isovalue can be easily
determined in an analytic and exact way. Our results confirm the
efficiency of the quasi-interpolating method and demonstrate high
visual quality for rendered isosurfaces.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9143&did=201839&ver=0
C.
Rössl
Christian
F.
Zeilfelder
Frank
G.
Nürnberger
Günther
H.-P.
Seidel
Hans-Peter
G.
Turk
Greg
J.
van Wijk
Jarke
R.
Moorhead
Robert
C125675300671F7B-667BB45D09712520C1256D41005222E9-RoesslZeilfelderNuernbergerSeidel2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018412011-07-2287:937
Thesis
Hologrammsynthese und 3D-Analyse in der digitalen Holografie
German
Philipps-Universität Marburg
Marburg
2003
2004-07-02
diplom
Die holografische 3D-Visualisierung ist eine gro"se
Herausforderung in der aktuellen Forschung. Neben der
Entwicklung eines entsprechenden Ausgabeger"ats ist
die schnelle Hologrammsynthese eine Voraussetzung f"ur
ein interaktives holografisches Ausgabesystem. In
dieser Arbeit wird ein Algorithmus f"ur die effiziente
Erzeugung digitaler Hologramme mit PC Grafikhardware
vorgestellt. Des Weiteren werden
3D-Rekonstruktionsverfahren von Hologrammen
untersucht, die mit einer CCD-Kamera aufgenommen
werden k"onnen.
expertsonly
http://edoc.mpg.de/get.epl?fid=9144&did=201841&ver=0
C.
Petz
Christoph
C1256BDE005F57A8-C266FFE1528CDC65C1256D6E0038635B-Petz2002
MPI für Informatik
Graphics - Optics - Vision
2011-07-22 12:29:54.466393
oai:edoc.mpg.de:2018432012-09-1987:934
Conference-Paper
Dynamic Remeshing and Applications
English
ACM
New York, USA
2003
2004-06-30
167
175
Seattle, USA
2003-06-16
Proceedings: 8th ACM Symposium on Solid Modeling and Applications (SM-03)
Triangle meshes are a flexible and generally accepted boundary
representation for complex geometric shapes. In addition to their
geometric qualities and topological simplicity, \emph{intrinsic}
qualities such as the shape of the triangles, their distribution on
the surface and the connectivity are essential for many algorithms
working on them. In this paper we present a flexible and efficient
remeshing framework that improves these intrinsic properties while
keeping the mesh geometrically close to the original surface. We
use a particle system approach and combine it with an incremental
connectivity optimization process to trim the mesh towards the
requirements imposed by the user. The particle system uniformly
distributes the vertices on the mesh, whereas the connectivity
optimization is done by means of \emph{Dynamic Connectivity Meshes},
a combination of local topological operators that lead to a fairly
regular connectivity. A dynamic skeleton ensures that our approach
is able to preserve surface features, which are particularly
important for the visual quality of the mesh. None of the
algorithms requires a global parameterization or patch layouting in
a preprocessing step but uses local parameterizations only. We also
show how this general framework can be put into practice and sketch
several application scenarios. In particular we will show how the
users can adapt the involved algorithms in a way that the resulting
remesh meets their personal requirements.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9146&did=201843&ver=0
http://edoc.mpg.de/get.epl?fid=9145&did=201843&ver=0
J.
Vorsatz
Jens
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
G.
Elber
Gershon
V.
Shapiro
Vadim
C125675300671F7B-690DFDA53D7BD4D8C1256CD4004EB2F0-Vorsatz:2003:DRA
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018532010-12-0287:932
Conference-Paper
Superposition modulo a Shostak Theory
English
Springer
Berlin, Germany
2003
2004-06-17
182
196
Miami, Florida
2003-07-28
Automated Deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Artificial Intelligence
We investigate superposition modulo a Shostak theory $T$ in order to
facilitate reasoning in the amalgamation of $T$ and a free
theory~$F$.
%
Free operators occur naturally e.\,g.\ in program verification
problems when abstracting over subroutines. If their behaviour in
addition can be specified axiomatically, much more of the program
semantics can be captured.
%
Combining the Shostak-style components for deciding the clausal
validity problem with the ordering and saturation techniques
developed for equational reasoning, we derive a refutationally
complete calculus on mixed ground clauses which result for example
from CNF transforming arbitrary universally quantified formulae.
%
The calculus works modulo a Shostak theory in the sense that it
operates on canonizer normalforms. For the Shostak solvers that we
study, coherence comes for free: no coherence pairs need to be
considered.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9147&did=201853&ver=0
H.
Ganzinger
Harald
T.
Hillenbrand
Thomas
U.
Waldmann
Uwe
F.
Baader
Franz
3-540-40559-3
C1256104005ECAFC-4489C55BD13D7669C1256CFE005A7257-GanzingerHillenbrandWaldmann2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018572012-09-1987:931
Conference-Paper
Space Efficient Hash Tables with Worst Case Constant Access Time
English
Springer
Berlin, Germany
2003
2004-06-11
271
282
Berlin, Germany
2003-02-27
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003)
Lecture Notes in Computer Science
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing}
and show how this yields a simple hash table data structure that stores $n$
elements in $(1+\epsilon)\,n$ memory cells, for any constant $\epsilon > 0$.
Assuming uniform hashing, accessing or deleting table entries takes at most $d
= O(\ln\frac{1}{\epsilon})$ probes and the expected amortized insertion time is
constant. This is the first dictionary that has worst case constant access time
and expected constant update time, works with $(1+\epsilon)\,n$ space, and
supports satellite information. Experiments indicate that $d=4$ choices suffice
for $\epsilon \approx 0.03$. We also describe a hash table data structure using
explicit constant time hash functions, using at most $d=
O(\ln^2\frac{1}{\epsilon})$ probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum
cardinality matchings in a rather natural model of sparse random bipartite
graphs.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9148&did=201857&ver=0
D.
Fotakis
Dimitris
R.
Pagh
Rasmus
P.
Sanders
Peter
P.G.
Spirakis
Paul G.
H.
Alt
Helmut
M.
Habib
Michel
3-540-00623-0
C1256428004B93B8-6A3318B88A19B993C1256CD800533F95-FPSS03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018692012-09-1987:931
Conference-Paper
Fast Lightweight Suffix Array Construction and Checking
English
Springer
Heidelberg, Germany
2003
2004-08-02
55
69
Morelia, Michoacán, Mexico
2003-06-25
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003
Lecture Notes in Computer Science
We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9149&did=201869&ver=0
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
R.
Baeza-Yates
R.
E.
Chávez
E.
M.
Crochemore
M.
0302-9743
C1256428004B93B8-3E2B1773D0314EDEC1256E8A002B0F6D-Burkhardt2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018722012-09-1987:934
Conference-Paper
Accuracy of 3D Range Scanners by Measurement of the Slanted Edge Modulation Transfer Function
English
IEEE
Los Alamitos, USA
2003
2004-06-30
37
44
Banff, Canada
2003-10-06
4th International Conference on 3-D Digital Imaging and Modeling
We estimate the accuracy of a 3D~range scanner in terms of its
spatial frequency response. We determine a scanner's modulation
transfer function (MTF) in order to measure its frequency response.
A slanted edge is scanned from which we derive a superresolution
edge profile. Its Fourier transform is compared to the Fourier
transform of an ideal edge in order to determine the MTF of the
device. This allows us to determine how well small details can be
acquired by the 3D~scanner. We report the results of several
measurements with two scanners under various conditions.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9150&did=201872&ver=0
M.
Goesele
Michael
C.
Fuchs
Christian
H.-P.
Seidel
Hans-Peter
M.
Rioux
Marc
G.
Godin
Guy
P.
Boulanger
Pierre
C125675300671F7B-1D1EDF899D4E8731C1256D2E0029DF07-Goesele:2003:A3R
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2018942010-12-0287:932
Article
On Using Ground Joinable Equations in Equational Theorem Proving
English
2003
2004-06-23
217
233
Journal of Symbolic Computation
36
When rewriting and completion techniques are used for equational
theorem proving, the axiom set is saturated with the aim to get a
rewrite system that is terminating and confluent on ground terms.
To reduce the computational effort it should (1) be powerful for
rewriting and (2) create not too many critical pairs. These problems
become especially important if some operators are associative and
commutative (\AC). We show in this paper how these two goals can be
reached to some extent by using ground joinable equations for
simplification purposes and omitting them from the generation of new
facts.
%
For the special case of \AC-operators we present a simple redundancy
criterion which is easy to implement, efficient, and effective in
practice, leading to significant speed-ups.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9153&did=201894&ver=0
J.
Avenhaus
Jürgen
T.
Hillenbrand
Thomas
B.
Löchner
Bernd
0747-7171
C1256104005ECAFC-A129A5E170AD94F0C1256D01002C84B9-AvenhausHillenbrandLoechner2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2018982010-12-0287:932
PhD-Thesis
A Lattice-Theoretic Framework For Circular Assume-Guarantee Reasoning
English
Universität des Saarlandes
Saarbrücken, Saarland
2003
2004-06-29
We develop an abstract lattice-theoretic framework within which
we study soundness and other properties of circular assume-
guarantee (A-G) rules constrained by side conditions. We
identify a particular side condition, non-blockingness, which
admits an intelligible inductive proof of the soundness of
circular A-G reasoning. Besides, conditional circular rules
based on non-blockingness turn out to be complete in various
senses and stronger than a large class of sound conditional A-G
rules. In this respect, our framework enlightens the foundations
of circular A-G reasoning.
Due to its abstractness, the framework can be instantiated to
many concrete settings. We show several known circular A-G rules
for compositional verification to be instances of our generic
rules. Thus, we do the circularity-breaking inductive argument
once to establish soundness of our generic rules, which then
implies soundness of all the instances without resorting to
technically complicated circularity-breaking arguments for each
single rule. In this respect, our framework unifies many
approaches to circular A-G reasoning and provides a starting
point for the systematic development of new circular A-G rules.
notspecified
http://edoc.mpg.de/get.epl?fid=9155&did=201898&ver=0
P.
Maier
Patrick
C1256104005ECAFC-97A2749806AF9DF1C1256EC2005EAF70-Maier2003
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2019492012-09-1987:934
Conference-Paper
Using Feature Flow Fields for Topological Comparison of Vector Fields
English
Akademische Verlagsgesellschaft Aka
Berlin, Germany
2003
2004-08-03
521
528
Munich, germany
2003-11-19
Vision, Modeling and Visualization 2003 (VMV-03) : proceedings
In this paper we propose a new topology based metric for 2D vector
fields. This metric is based on the concept of feature flow
fields. We show that it incorporates both the characteristics and
the local distribution of the critical points while keeping the
computing time reasonably small even for topologically complex
vector fields. Finally, we apply the metric to track the
topological behavior in a time-dependent vector field, and to
evaluate a smoothing procedure on a noisy steady vector field.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9163&did=201949&ver=0
H.
Theisel
Holger
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
T.
Ertl
Thomas
B.
Girod
Bernd
G.
Greiner
Günther
H.
Niemann
Heinrich
H.-P.
Seidel
Hans-Peter
E.
Steinbach
Eckehard
R.
Westermann
Rüdiger
3-89838-048-3
C125675300671F7B-AF66E5B69EBC9F31C1256D79006C4D60-Theisel2003_vmv
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2019522012-09-1987:934
Conference-Paper
Tree-based Triangle Mesh Connectivity Encoding
English
Nashboro Press
Brentwood, USA
2003
2004-06-30
345
354
Saint Malo, France
2003-06-27
Curve and Surface Fitting: Saint-Malo 2002
We present a divide and conquer algorithm for triangle mesh
connectivity encoding. As the algorithm traverses the mesh it
constructs a weighted binary tree that holds all information required for
reconstruction. This representation can be used for compression.We derive a new
iterative single-pass decoding algorithm, and we show how to exploit the tree
data structure
for generating stripifications for efficient rendering that come with a
guaranteed cost saving.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9164&did=201952&ver=0
C.
Rössl
Christian
I.
Ivrissimtzis
Ioannis
H.-P.
Seidel
Hans-Peter
A.
Cohen
Albert
J.-L.
Merrien
Jean-Louis
L.L.
Schumaker
Larry L.
0-9728482-1-5
C125675300671F7B-892629445F84CDE3C1256D1100313849-Roessl:TBTMCE:2002
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2019702012-09-1987:934
Article
Image-Based Reconstruction of Spatial Appearance and Geometric Detail
English
2003
2004-06-30
234
257
ACM Transactions on Graphics
22
Real-world objects are usually composed of a number of different materials that
often show subtle changes even within a single material. Photorealistic
rendering of such objects requires accurate measurements of the reflection
properties of each material, as well as the spatially varying effects. We
present an image-based measuring method that robustly detects the different
materials of real objects and fits an average bidirectional reflectance
distribution function (BRDF) to each of them. In order to model local changes
as well, we project the measured data for each surface point into a basis
formed by the recovered BRDFs leading to a truly spatially varying BRDF
representation. Real-world objects often also have fine geometric detail that
is not represented in an acquired mesh. To increase the detail, we derive
normal maps even for non-Lambertian surfaces using our measured BRDFs. A high
quality model of a real object can be generated with relatively little input
data. The generated model allows for rendering under arbitrary viewing and
lighting conditions and realistically reproduces the appearance of the original
object.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9165&did=201970&ver=0
H.P.A.
Lensch
Hendrik P. A.
J.
Kautz
Jan
M.
Goesele
Michael
W.
Heidrich
Wolfgang
H.-P.
Seidel
Hans-Peter
C125675300671F7B-9DC8FDDC048DDFADC1256C5B002F0FA3-Lensch:IRS:2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
Permission to make digital or hard copies of part or all of this work for
personal or classroom use is granted without fee provided that copies are not
made or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for components
of this work owned by others than ACM must be honored. Abstracting with credit
is permitted. To copy otherwise, to republish, to post on servers or to
redistribute to lists, requires prior specific permission and/or a fee.
oai:edoc.mpg.de:2019732012-09-1987:934
Conference-Paper
Combining Topological Simplification and Topology Preserving Compression for 2D Vector Fields
English
IEEE
Los Alamitos, USA
2003
2004-07-12
419
423
Canmore, Canada
2003-10-08
11th Pacific Conference on Computer Graphics and Applications (PG-03)
Topological simplification techniques and topology preserving
compression approaches for 2D vector fields have
been developed quite independently of each other. In this
paper we propose a combination of both approaches: a vector
field should be compressed in such a way that its important
topological features (both critical points and separatrices)
are preserved while its unimportant features are allowed
to collapse and disappear. To do so, a number of new
solutions and modifications of pre-existing algorithms are
presented. We apply the approach to a flow data set which,
is both large and topologically complex, and achieve significant
compression ratios there.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9166&did=201973&ver=0
H.
Theisel
Holger
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
J.
Rokne
Jon
R.
Klein
Reinhard
W.
Wang
Wenping
C125675300671F7B-788BE51D4011CCC5C1256D64005C4F4A-TheiselPG2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2019752012-09-1987:934
Conference-Paper
Accurate Light Source Acquisition and Rendering
English
ACM
New York, USA
2003
2004-07-07
621
630
San Diego, USA
2003-07-27
Proceedings of ACM SIGGRAPH 2003 (SIGGRAPH-03)
ACM Transactions on Graphics
Realistic image synthesis requires both complex and realistic models
of real-world light sources and efficient rendering algorithms to deal
with them. In this paper, we describe a processing pipeline for
dealing with complex light sources from acquisition to global
illumination rendering. We carefully design optical filters to
guarantee high precision measurements of real-world light sources. We
discuss two practically feasible setups that allow us to measure light
sources with different characteristics.
Finally, we introduce an efficient importance sampling
algorithm for our representation that can be used, for example, in
conjunction with Photon Maps.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9168&did=201975&ver=0
M.
Goesele
Michael
X.
Granier
Xavier
W.
Heidrich
Wolfgang
H.-P.
Seidel
Hans-Peter
J.K.
Hodgins
Jessica K.
C125675300671F7B-82DCF25CF25AAD0BC1256CF4002FC3C0-Goesele:2003:ALS
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2019792012-09-1987:934
Conference-Paper
Interactive Visualization of Complex Real-World Light Sources
English
IEEE
Los Alamitos, USA
2003
2004-07-12
59
66
Canmore, Canada
2003-10-08
11th Pacific Conference on Computer Graphics and Applications (PG-03)
Interactive visualization of complex, real-world light
sources has so far not been feasible. In this paper, we
present an hardware accelerated direct lighting algorithm
based on a recent high quality light source acquisition technique.
By introducing an approximate reconstruction of the
exact model, a multi-pass rendering approach, and a compact
data representation, we are able to achieve interactive
frame rates. The method is part of the processing pipeline
from light source acquisition to high quality lighting of a
virtual world.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9169&did=201979&ver=0
X.
Granier
Xavier
M.
Goesele
Michael
W.
Heidrich
Wolfgang
H.-P.
Seidel
Hans-Peter
J.
Rokne
Jon
R.
Klein
Reinhard
W.
Wang
Wenping
C125675300671F7B-E31E17CB825AF057C1256D7B00743765-Granier:2003:IVO
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2019802012-09-1987:931
Article
Randomized Pursuit-Evasion in Graphs
English
2003
2004-06-15
225
244
Combinatorics, Probability and Computing
12
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9170&did=201980&ver=0
M.
Adler
Micah
H.
Räcke
Harald
N.
Sivadasan
Naveen
C.
Sohler
Christian
B.
Vöcking
Berthold
0963-5483
C1256428004B93B8-84FD4682AF9079ECC1256EAC0033DB77-Sivadas2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019852012-09-1987:934
Conference-Paper
Virtualizing Real-World Objects
English
IEEE Computer Society
Los Alamitos, USA
2003
2004-06-24
134
141
Tokyo, Japan
2003-07-09
Computer Graphics International (CGI 2003)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9171&did=201985&ver=0
H.P.A.
Lensch
Hendrik P. A.
J.
Kautz
Jan
M.
Goesele
Michael
J.
Lang
Jochen
H.-P.
Seidel
Hans-Peter
C125675300671F7B-15DED5A900778BE8C1256E14005FC106-Lensch:2003:VRO
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2019982012-09-1987:933
Conference-Paper
Stochastic Gradient Descent Training of Ensembles of DT-CNN Classifiers for Digit Recognition
English
Faculty of Electrical Engineering, Automatics, Computer Science and Electronics, AGH University of Science and Technology
Krakow, Poland
2003
2004-07-12
337
341
Krakow, Poland
2003-09-01
Proceedings of the 16th European Conference on Circuit Theory and Design ECCTD'03
We show how to train Discrete Time Cellular Neural Networks
(DT-CNN) successfully by backpropagation to perform pattern
recognition on a data set of handwritten digits. By using concepts
and techniques from Machine Learning, we can outperform Support
Vector Machines (SVM) on this problem.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9173&did=201998&ver=0
C.
Merkwirth
Christian
M.
Ogorzalek
Maciej
J.D.
Wichard
Jörg Daniel
M.
Ogorzalek
Maciej
Z.
Galias
Zbigniew
B.
Garda
Bartłomiej
B.
Kadeja
Bartłomiej
83-88309-95-1
C125673F004B2D7B-D22546C0E6C688C6C1256E19003E789C-Merkwirth2003ECCTD
MPI für Informatik
Computational Biology and Applied Algorithmics
2012-09-19 10:27:39.08038
oai:edoc.mpg.de:2020192010-12-0287:932
Conference-Paper
New Directions in Instantiation-Based Theorem Proving
English
IEEE
Los Alamitos, USA
2003
2004-06-17
55
64
Ottawa, Canada
2003-06-22
18th Annual IEEE Symposium on Logic in Computer Science (LICS-03)
We consider instantiation-based theorem proving whereby
instances of clauses are generated by certain inferences, and where
inconsistency is detected by propositional tests.
We give a model construction proof of completeness by which restrictive
inference
systems as well as admissible simplification techniques can be
justified. Another contribution of the paper are novel inference
systems that allow one to also employ decision procedures for
first-order fragments more complex than propositional logic.
The decision procedure provides for an approximative consistency test, and the
instance generation inference system is a means of
successively refining the approximation.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9176&did=202019&ver=0
H.
Ganzinger
Harald
K.
Korovin
Konstantin
P.
Kolaitis
Phokion
0-7695-1884-2
C1256104005ECAFC-9F899010FD50E7D7C1256D170066FF4B-GanzingerKorovin-03-lics
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2020262010-12-0287:932
Conference-Paper
A Representation Theorem and Applications
English
Springer
Berlin, Germany
2003
2004-06-17
50
61
Aalborg, Denmark
2003-07-02
Symbolic and Quantitative Approaches to Reasoning with Uncertainty :
7th European Conference, ECSQARU 2003
Lecture Notes in Computer Science
We introduce a set of transformations on the set of all probability
distributions over a finite state space, and show that these
transformations are the only ones that preserve certain
elementary probabilistic relationships. This result provides
a new perspective on a variety of probabilistic inference
problems in which invariance considerations play a role.
Two particular applications we consider in this paper
are the development of an equivariance-based approach to
the problem of measure selection, and a new justification for
Haldane's prior as the distribution that encodes prior
ignorance about the parameter of a multinomial distribution.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9177&did=202026&ver=0
M.
Jaeger
Manfred
T.D.
Nielsen
Thomas D.
N.L.
Zhang
Nevin L.
3-540-40494-5
C1256104005ECAFC-8F468E8BDA25A19FC1256D01002C63A8-JaegerECSQARU03
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2020272010-12-0287:932
Conference-Paper
Superposition with Equivalence Reasoning and Delayed Clause Normal Form Transformation
English
Springer
Berlin, Germany
2003
2004-06-17
335
349
Miami, Florida
2003-07-28
Automated Deduction, CADE-19 : 19th International Conference on Automated Deduction
Lecture Notes in Artificial Intelligence
The paper describes a superposition calculus where quantifiers are eliminated
lazily. Superposition and simplification inferences may employ equivalences
that have arbitrary formulas at their smaller side. A closely related calculus
is implemented in the Saturate system and has shown useful on many examples, in
particular in set theory. The paper presents a completeness proof and reports
on practical experience obtained with the Saturate system.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9178&did=202027&ver=0
H.
Ganzinger
Harald
J.
Stuber
Jürgen
F.
Baader
Franz
3-540-40559-3
C1256104005ECAFC-834A2D263C7BFE3F00256D200035E7D7-GanzingerStuber-2003-cade
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2020322010-12-0287:932
Conference-Paper
Subsumption of Concepts in FL_0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-complete
English
CEUR
Aachen, Germany
2003
2004-06-22
56
64
Rome, Italy
2003-09-05
2003 International Workshop on Description Logics (DL-03)
CEUR Workshop Proceedings
We close the gap in the complexity classification of subsumption in the simple
description logic ${\cal FL}_0$, which allows for
conjunctions and universal value restriction only. We prove that the
subsumption problem in ${\cal FL}_0$ is PSPACE-complete for descriptive
semantics when cyclic definitions are allowed. Our proof uses automata theory
and as a by-product we establish the PSPACE-completeness of a certain decision
problem for regular
languages.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9179&did=202032&ver=0
Y.
Kazakov
Yevgeny
H.
de Nivelle
Hans
D.
Calvanese
Diego
G.
De Giacomo
Giuseppe
E.
Franconi
Enrico
1613-0073
C1256104005ECAFC-746B1C632282C1C9C1256E23006ADC00-Kazakov03SubsumptionFLzero
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2020442012-09-1987:931
Conference-Paper
Smoothed Analysis of Three Combinatorial Problems
English
Springer
Berlin, Germany
2003
2004-06-15
198
207
Bratislava, Slovak Republic
2003-08-25
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Lecture Notes in Computer Science
Smoothed analysis combines elements over worst-case and
average case analysis. For an instance $x$, the smoothed complexity is the
average complexity of an instance obtained from $x$ by a perturbation. The
smoothed complexity of a problem is the worst smoothed complexity of any
instance. Spielman and Teng introduced this notion for
continuous problems. We apply the concept to combinatorial problems and study
the smoothed complexity of three classical discrete problems: quicksort,
left-to-right maxima counting, and shortest paths.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9181&did=202044&ver=0
C.
Banderier
Cyril
R.
Beier
Rene
K.
Mehlhorn
Kurt
B.
Rovan
Branislav
P.
Vojtáš
Peter
3-540-40671-9
C1256428004B93B8-09CF39E77E5072D5C1256E140059E6C7-Beier2003a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020462012-09-1987:934
Conference-Paper
Compression of 2D vector fields under guaranteed topology preservation
English
Blackwell
Oxford, UK
2003
2004-07-12
333
342
Granada, Spain
2003-09-01
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference
Computer Graphics Forum
In this paper we introduce a new compression technique for 2D vector fields
which preserves the complete topology, i.e., the critical points and the
connectivity of the separatrices. As the theoretical foundation of the
algorithm, we show in a theorem that for local modifications of a vector field,
it is possible to decide entirely by a local analysis whether or not the global
topology is preserved. This result is applied in a compression algorithm which
is based on a repeated local modification of the vector field - namely a
repeated edge collapse of the underlying piecewise linear domain. We apply the
compression technique to a number of data sets with a complex topology and
obtain significantly improved compression ratios in comparison to pre-existing
topology-preserving techniques.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9182&did=202046&ver=0
H.
Theisel
Holger
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
P.
Brunet
Pere
D.W.
Fellner
Dieter W.
C125675300671F7B-21FE90C7C981A5E3C1256D050047DB4B-Theisel:2003:CVFGTP
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2311772012-09-1987:931
Conference-Paper
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
English
Springer
Berlin, Germany
2004
2005-04-22
122
133
Bergen, Norway
2004-09-14
Algorithms – ESA 2004: 12th Annual European Symposium
Lecture Notes in Computer Science
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the
removal of which leaves no perfect matching in $G$. We give an explicit
characterization of the minimal blockers of a bipartite graph $G$. This result
allows us to obtain a polynomial
delay algorithm for finding all minimal blockers of a given bipartite graph.
Equivalently, this gives a polynomial delay algorithm for listing the
anti-vertices of the perfect matching polytope $P(G)=\{x\in
\RR^E~|~Hx=\be,~~x\geq 0\}$, where $H$ is the incidence matrix of $G$. We also
give similar generation algorithms for other related problems, including
generalized perfect matchings in bipartite graphs, and perfect 2-matchings in
general graphs.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13318&did=231177&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
S.
Albers
Susanne
T.
Radzik
Tomasz
3-540-23025-4
C1256428004B93B8-F7189E64F086B362C1256FB1004BD7DC-Elbassioni2004g
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311782012-09-1987:931
Conference-Paper
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
English
Springer
Berlin, Germany
2004
2005-04-21
152
162
New York, NY, USA
2004-06-07
Integer programming and combinatorial optimization : 10th International IPCO Conference
Lecture Notes in Computer Science
We consider the problems of enumerating all minimal strongly connected
subgraphs and all minimal dicuts of a given directed graph G=(V,E). We show
that the first of these problems can be solved in incremental polynomial time,
while the second problem is NP-hard: given a collection of minimal dicuts for
G, it is NP-complete to tell whether it can be extended. The latter result
implies, in particular, that for a given set of points , it is NP-hard to
generate all maximal subsets of contained in a closed half-space through the
origin. We also discuss the enumeration of all minimal subsets of whose convex
hull contains the origin as an interior point, and show that this problem
includes as a special case the well-known hypergraph transversal problem.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=13319&did=231178&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
D.
Bienstock
Daniel
G.
Nemhauser
George
3-540-22113-1
C1256428004B93B8-A571696CD00A38AEC1256FB1004ACE90-Elbassioni2004e
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311792012-09-1987:931
Conference-Paper
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
English
Springer
Berlin, Germany
2004
2005-05-23
488
498
Buenos Aires, Argentina
2004-04-05
LATIN 2004: Theoretical Informatics, 6th Latin American Symposium
Lecture Notes in Computer Science
Given a finite set $V$, and integers $k \geq 1$ and $r \geq 0$,
denote by $\AA(k,r)$ the class of hypergraphs $\cA \subseteq 2^V$
with $(k,r)$-bounded intersections, i.e. in which
the intersection of any $k$ distinct hyperedges has size at most $r$. We
consider the problem $MIS(\cA,\cI)$:
given a hypergraph $\cA$ and a subfamily $\cI \subseteq \In$,
of its maximal independent sets (MIS) $\In$, either extend this subfamily by
constructing a new MIS $I \in \In \setminus \cI$
or prove that there are no more MIS, that is $\cI = \In$.
We show that for hypergraphs $\cA\in\AA(k,r)$ with $k+r\le const$, problem
MIS$(\cA,\cI)$ is NC-reducible to problem MIS$(\cA',\emptyset)$ of generating a
single MIS for
a partial subhypergraph $\cA'$ of $\cA$. In particular, for this class of
hypergraphs, we get an incremental polynomial algorithm for generating all MIS.
Furthermore, combining this result with the currently known algorithms for
finding a single maximal independent set of a hypergraph, we obtain efficient
parallel algorithms for incrementally generating all MIS for hypergraphs in the
classes $\AA(1,c)$, $\AA(c,0)$, and $\AA(2,1)$, where $c$ is a constant. We
also show that,
for $\cA \in \AA(k,r)$, where $k+r\le const$, the problem of
generating all MIS of $\cA$ can be solved in incremental polynomial-time with
space polynomial only in the size of $\cA$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13320&did=231179&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
M.
Farach-Colton
Martin
3-540-21258-2
C1256428004B93B8-8FD2B06B5B82875EC1256FB1004A73B8-Elbassioni2004d
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311802012-09-1987:931
Conference-Paper
Generating Paths and Cuts in Multi-pole (Di)graphs
English
Springer
Berlin, Germany
2004
2005-04-26
298
309
Prague, Czech Republic
2004-08-22
Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004
Lecture Notes in Computer Science
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given
a set of (source-sink) pairs of vertices of G, an important problem that
arises in the computation of network reliability is the enumeration of minimal
subsets of edges (arcs) that connect/disconnect all/at least one of the given
source-sink pairs of . For undirected graphs, we show that the enumeration
problems for conjunctions of paths and disjunctions of cuts can be solved in
incremental polynomial time. For directed graphs both of these problems are
NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets
of arcs connecting respectively two given nodes s1 and s2 to a given vertex t1,
and each vertex of a given subset of vertices T2.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13321&did=231180&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
K.
Makino
Kazuhisa
J.
Fiala
Jirí
V.
Koubek
Václav
J.
Kratochvíl
Jan
3-540-22823-3
C1256428004B93B8-028218E7F7706A18C1256FB0006AFB8D-Elbassioni2004b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311812012-09-1987:931
Conference-Paper
An Efficient Implementation of a Joint Generation Algorithm
English
Springer
Berlin, Germany
2004
2005-04-21
114
128
Angra dos Reis, Brazil
2004-05-25
Experimental and efficient algorithms : Third International Workshop, WEA 2004
Lecture Notes in Computer Science
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property
defined over the elements of $\cC$. We consider the problems of incrementally
generating jointly the families $\cF_{\pi}$ and $\cI(cF_{\pi})$ of all minimal
subsets satisfying property $\pi$ and all maximal subsets not satisfying
property $\pi$, when $\pi$ is given by a polynomial-time satisfiability oracle.
Problems of this type arise in many practical applications. It is known that
the above joint generation problem can be solved in incremental
quasi-polynomial time. In this paper, we present an efficient implementation of
this procedure. We present experimental results to evaluate our implementation
for a number of interesting monotone properties $\pi$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13322&did=231181&ver=0
E.
Boros
Endre
K.
Elbassioni
Khaled
V.
Gurvich
Vladimir
L.
Khachiyan
Leonid
C.C.
Ribeiro
Celso C.
S.L.
Martins
Simone L.
3-540-22067-4
C1256428004B93B8-6A93A5BCF0711754C1256FB0006A0E15-Elbassioni2004a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311882012-09-1987:931
Conference-Paper
Engineering an External Memory Minimum Spanning Tree Algorithm
English
Kluwer
Norwell, USA
2004
2005-05-30
195
208
Toulouse, France
2004-08-23
3rd IFIP International Conference on Theoretical Computer Science (TSC2004)
We develop an external memory algorithm for computing minimum spanning
trees. The algorithm is considerably simpler than previously known
external memory algorithms for this problem and needs a factor of at
least four less I/Os for realistic inputs.
Our implementation indicates that this algorithm processes graphs only
limited by the disk capacity of most current machines in time no more
than a factor 2--5 of a good internal algorithm with sufficient memory
space.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13323&did=231188&ver=0
R.
Dementiev
Roman
P.
Sanders
Peter
D.
Schultes
Dominik
J.F.
Sibeyn
Jop F.
J.-J.
Lévy
Jean-Jacques
E.W.
Mayr
Ernst W.
J.C.
Mitchell
John C.
1-4020-8140-5
C1256428004B93B8-3C2394B7B7DA31D3C1256FA9004CA46A-DSSS04
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311922012-09-1987:931
Conference-Paper
Algorithms for recognizing coordinates in two variables over UFD's
English
ACM
New York, USA
2004
2005-06-07
135
140
Santander, Spain
2005-02-25
Proceedings of the 2004 International Symposium Symbolic and Algebraic Computation (ISSAC-04)
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13326&did=231192&ver=0
M.
El Kahoui
M'hammed
J.
Gutierrez
Jaime
1-58113-827-X
C1256428004B93B8-09E211DD8F4E6F84C1256FB30050DE55-ElKahoui2004c
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311932012-09-1987:931
Conference-Paper
Scalable Multimedia Disk Scheduling
English
IEEE
Los Alamitos, USA
2004
2005-04-21
498
509
Boston, USA
2004-03-30
20th International Conference on Data Engineering, ICDE 2004
A new multimedia disk scheduling algorithm, termed Cascaded-SFC, is presented.
The Cascaded-SFC multimedia disk scheduler is applicable in environments where
multimedia data requests arrive with different quality of service (QoS)
requirements such as real-time deadline and user priority. Previous work on
disk scheduling has focused on optimizing the seek times and/or meeting the
real-time deadlines. The Cascaded-SFC disk scheduler provides a unified
framework for multimedia disk scheduling that scales with the number of
scheduling parameters. The general idea is based on modeling the multimedia
disk requests as points in multiple multi-dimensional sub-spaces, where each of
the dimensions represents one of the parameters (e.g., one dimension represents
the request deadline, another represents the disk cylinder number, and a third
dimension represents the priority of the request, etc.). Each multi-dimensional
sub-space represents a subset of the QoS parameters that share some common
scheduling characteristics. Then the multimedia disk scheduling problem reduces
to the problem of finding a linear order to traverse the multi-dimensional
points in each sub-space. Multiple space-filling curves are selected to fit the
scheduling needs of the QoS parameters in each sub-space. The orders in each
sub-space are integrated in a cascaded way to provide a total order for the
whole space. Comprehensive experiments demonstrate the efficiency and
scalability of the Cascaded-SFC disk scheduling algorithm over other disk
schedulers.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13327&did=231193&ver=0
K.
Elbassioni
Khaled
M.F.
Mokbel
Mohamed F.
W.G.
Aref
Walid G.
I.
Kamel
Ibrahim
0-7695-2065-0
C1256428004B93B8-49B9CE582EADDFEAC1256FB1004B66A2-Elbassioni2004f
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311942012-09-1987:931
Conference-Paper
Incremental Algorithms for Facility Location and k-Median
English
Springer
Berlin, Germany
2004
2005-04-22
347
358
Bergen, Norway
2004-09-14
Algorithms – ESA 2004: 12th Annual European Symposium
Lecture Notes in Computer Science
In the incremental versions of Facility Location and k-Median, the demand
points arrive one at a time and the algorithm must maintain a good solution by
either adding each new demand to an existing cluster or placing it in a new
singleton cluster. The algorithm can also merge some of the existing clusters
at any point in time. We present the first incremental algorithm for Facility
Location with uniform facility costs which achieves a constant performance
ratio and the first incremental algorithm for k-Median which achieves a
constant performance ratio using O(k) medians.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13328&did=231194&ver=0
D.
Fotakis
Dimitris
S.
Albers
Susanne
T.
Radzik
Tomasz
3-540-23025-4
C1256428004B93B8-BB4F865FF034AAE3C1256FB4004B625B-Fotakis2004a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2311992012-09-1987:931
Conference-Paper
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
English
University of Bologna
Bologna, Italy
2004
2005-02-02
97
111
Boston, USA
2004-08-26
First International Workshop on Algorithms for Wireless and Mobile Networks
We investigate algorithms for computing
energy efficient paths in ad-hoc radio networks.
We demonstrate how advanced data structures from computational
geometry can be employed to preprocess the position of
radio stations in such a way that approximately
energy optimal paths can be retrieved in constant time, i.e.,
independent of the network size.
We put particular emphasis on actual implementations which
demonstrate that large constant factors hidden in the theoretical
analysis are not a big problem in practice.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13329&did=231199&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
C1256428004B93B8-E48460D48DE204C1C1256F88003F7310-FMS2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312222012-09-1987:931
Article
A simpler linear time 2/3 - eps approximation for maximum weight matching
English
2004
2005-05-30
271
276
Information Processing Letters
91
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13332&did=231222&ver=0
S.
Pettie
Seth
P.
Sanders
Peter
C1256428004B93B8-8C86AC1B497A2DDEC1256F8800518407-PettieSanders2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312242012-09-1987:931
Conference-Paper
Online scheduling with bounded migration
English
Springer
Berlin, Germany
2004
2005-05-23
1111
1122
Turku, Finnland
2004-07-12
Automata, languages and programming : 31st International Colloquium, ICALP 2004
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13333&did=231224&ver=0
P.
Sanders
Peter
N.
Sivadasan
Naveen
M.
Skutella
Martin
J.
Díaz
Josep
J.
Karhumäki
Juhani
A.
Lepistö
Arto
D.
Sannella
Donald
3-540-22849-7
C1256428004B93B8-AA794B91E683A1DEC1256F56004941D7-Sivadasan2004-2
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312262012-09-1987:931
Conference-Paper
Topology matters: Smoothed competitiveness of metrical task systems
English
Springer
Berlin, Germany
2004
2005-05-23
489
500
Montpellier, France
2004-03-25
21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04)
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13334&did=231226&ver=0
G.
Schäfer
Guido
N.
Sivadasan
Naveen
V.
Diekert
Volker
M.
Habib
Michel
3-540-21236-1
C1256428004B93B8-7F33404549ADEA5DC1256F560048EE68-Sivadasan2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312312012-09-1987:931
Thesis
Controlled Perturbation for Voronoi Diagrams
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-06-17
expertsonly
http://edoc.mpg.de/get.epl?fid=13335&did=231231&ver=0
C.
Klein
Christian
C1256428004B93B8-407186B9B72B2A1DC1256FA2005A295A-Klein2004
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2312522010-12-0287:932
Article
Fast Term Indexing with Coded Context Trees
English
2004
2005-02-02
103
120
Journal of Automated Reasoning
32
Indexing data structures have a crucial impact on
the performance of automated theorem provers. Examples are discrimination
trees, which are like tries where terms are seen as strings and common prefixes
are shared, and substitution trees, where terms keep their tree structure and
all common contexts can be shared. Here we describe a new indexing data
structure, called context trees, where, by means of a limited kind of context
variables, also common subterms can be shared, even if they occur below
different function symbols. Apart from introducing the concept, we also provide
evidence for its practical value. We show how context trees can be implemented
by means of abstract machine instructions. Experiments with matching benchmarks
show that our implementation is competitive with tightly coded current
state-of-the-art implementations of the other main techniques. In particular
space consumption of context trees is significantly less than for other index
structures.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13336&did=231252&ver=0
H.
Ganzinger
Harald
R.
Nieuwenhuis
Robert
P.
Nivela
Pilar
C1256104005ECAFC-B0EF8A197F4BBBE400256D20003B728C-GanzingerNieuwenhuisNivela-03-jar
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2312582010-12-0287:932
Conference-Paper
A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded Fragment
English
Springer
Berlin, Germany
2004
2005-02-02
372
384
Lisbon, Portugal
2004-09-27
Logics in artificial intelligence : 9th European Conference, JELIA 2004
Lecture Notes in Artificial Intelligence
We consider a two-variable guarded fragment with number restrictions for binary
relations and give a satisfiability preserving transformation of formulas in
this fragment to the three-variable guarded fragment. The translation can be
computed in polynomial time and produces a formula that is linear in the size
of the initial formula even for the binary coding of number restrictions. This
allows one to reduce reasoning problems for many description logics to the
satisfiability problem for the guarded fragment.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13337&did=231258&ver=0
Y.
Kazakov
Yevgeny
J.J.
Alferes
José Júlio
J.
Leite
João
3-540-23242-7
C1256104005ECAFC-3E0C7DF49217CA81C1256EE20080EDAC-Kazakov04GF2N
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
© Springer-Verlag
oai:edoc.mpg.de:2312652010-12-0287:932
Conference-Paper
Robust Pole Clustering of Parametric Uncertain Systems Using Interval Methods
English
Publ. for the International Federation of Automatic Control by Elsevier
Oxford
2004
2005-02-03
323
328
Milano
2003-07-07
Robust control design 2003 : (ROCOND 2003) ; a proceedings volume from the 4th IFAC symposium
In this paper a new methodology to solve the pole clustering problem for
parametric
uncertain systems is introduced: The problem of clustering the closed loop
poles into
prescribed D-regions in the complex plane is stated as a quantified
constraint problem
that represents bounded uncertain parameters by intervals; and an
engineering-oriented
approach based on interval methods is developed to solve this quantified
constraint
problem. The result is a new, robust, reliable and
design oriented method to deal with parametric uncertain systems.
The methodology presented in this paper allows to find a good
controller that places the closed loop poles in the desired
location in the complex plane. In case there is no solution, the
method allows also to "tune" the problem, either enlarging the pole
locations or reducing the uncertainty domain.
The approach presented in this paper can be used either for linear
or non-linear systems and for any kind of parametric bounded
uncertainty.
Several simple examples illustrate the uses, limits and scope of
the methodology.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13338&did=231265&ver=0
S.
Ratschan
Stefan
J.
Vehi
Josep
S.
Bittanti
Sergio
0-08-044012-6
C1256104005ECAFC-13B500BDBD6D466DC1256D0200300F64-Ratschan2002
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2312712010-12-0287:932
Conference-Paper
A Superposition View on Nelson-Oppen
English
CEUR
Aachen
2004
2005-02-02
16
20
Cork, Ireland
2004-08-04
Contributions to the Doctoral Programme of the 2nd International Joint Conference on Automated Reasoning
CEUR Workshop Proceedings
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13339&did=231271&ver=0
T.
Hillenbrand
Thomas
U.
Sattler
Ulrike
1613-0073
C1256104005ECAFC-8EAD4DC962EDE15BC1256EE40054344A-Hillenbrand2004
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2312722010-12-0287:932
Thesis
Instance Generation Methods for Automated Reasoning
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-04-27
There are several different methods which try to decide unsatisfiability of a
set of clauses by generating an unsatisfiable set of instances of the input
clauses. We consider the \emph{Disconnection Tableau Calculus}, \emph{Primal
Partial Instantiation} and \emph{Resolution-Based Instance-Generation}, all of
which can be seen as refinements of the clause linking approach. We present
these three methods accurately and in a consistent manner. Similarities and
equivalences of the methods will be pointed out and we will show if proofs of
one calculus can be simulated by a different method, generating only instances
from the given proof.
expertsonly
http://edoc.mpg.de/get.epl?fid=13340&did=231272&ver=0
S.
Jacobs
Swen
C1256104005ECAFC-288285D9C047581FC1256FC0004BA71E-Jacobs2004
MPI für Informatik
Programming Logics Group
2010-12-02 11:37:35.381871
oai:edoc.mpg.de:2313092012-09-1987:934
Conference-Paper
Interactive {Ray} {Tracing} of {Free-Form} {Surfaces}
English
ACM
New York, USA
2004
2005-04-27
99
106
Stellenbosch, South Africa
2004-10-03
Proceedings AFRIGRAPH 2004 : 3rd International Conference on Virtual Reality, Computer Graphics, Visualisation and Interaction in Africa
Even though the speed of software ray tracing has recently been
increased to interactive performance even on standard PCs, these
systems usually only supported triangles as geometric primitives.
Directly handling free-form surfaces such as spline or subdivision
surfaces instead of first tessellating them offers many advantages
such as higher precision results, reduced memory requirements, and
faster preprocessing due to less primitives. However, existing
algorithms for ray tracing free-form surfaces are much too slow for
interactive use.
In this paper we present a simple and generic approach for ray
tracing free-form surfaces together with specific implementations
for cubic B\'ezier and Loop subdivision surfaces. We show that our
approach allows to increase the performance by more than an order of
magnitude, requires only constant memory, and is largely independent
on the total number of free-form primitives in a scene. Examples
demonstrate that even scene with over one hundred thousand free-form
surfaces can be rendered interactively on a single processor at
video resolution.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13342&did=231309&ver=0
C.
Benthin
Carsten
I.
Wald
Ingo
P.
Slusallek
Philipp
L.
van Zijl
Lynette
P.
Marais
Patrick
1-58113-863-6
C125675300671F7B-EB7CDCFEDDFBEC60C1256F71005742AC-benthin:04:FreeFormRT
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313212012-09-1987:934
Article
DISCO - Acquisition of Translucent Objects
English
2004
2005-04-28
835
844
ACM Transactions on Graphics
23
Translucent objects are characterized by diffuse light scattering
beneath the object's surface. Light enters and leaves an object at
possibly distinct surface locations. This paper presents the first
method to acquire this transport behavior for arbitrary
inhomogeneous objects. Individual surface points are illuminated in
our DISCO measurement facility and the object's impulse response is
recorded with a high-dynamic range video camera. The acquired data
is resampled into a hierarchical model of the object's light
scattering properties. Missing values are consistently interpolated
resulting in measurement-based, complete and accurate
representations of real translucent objects which can be rendered
with various algorithms.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13343&did=231321&ver=0
M.
Goesele
Michael
H.P.A.
Lensch
Hendrik P. A.
J.
Lang
Jochen
C.
Fuchs
Christian
H.-P.
Seidel
Hans-Peter
J.
Marks
Joe
0730-0301
C125675300671F7B-8859179F7A701C6BC1256E6E0070994A-Goesele:2004:DAT
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313242012-09-1987:934
Conference-Paper
Realtime Caustics using Distributed Photon Mapping
English
Eurographics
Aire-la-Ville, Switzerland
2004
2005-06-10
111
121
Norkoeping, Sweden
2004-06-21
Rendering Techniques 2004 : Eurographics Symposium on Rendering
With the advancements in realtime ray tracing and new global illumination
algorithms we are now able to render the most important illumination effects at
interactive rates. One of the major remaining issues is the fast and efficient
simulation of caustic illumination, such as e.g. the illumination from a car
headlight. The photon mapping algorithm is a simple and robust approach that
generates high-quality results and is the preferred algorithm for computing
caustic illumination. However, photon mapping has a number of properties that
make it rather slow on today s processors. Photon mapping has also been
notoriously difficult to parallelize efficiently.
In this paper, we present a detailed analysis of the performance issues of
photon mapping together with signifi- cant performance improvements for all
aspects of the photon mapping technique. The solution forms a complete
framework for realtime photon mapping that efficiently combines realtime ray
tracing, optimized and improved photon mapping algorithms, and efficient
parallelization across commodity PCs. The presented system achieves realtime
photon mapping performance of up to 22 frames per second on non-trivial scenes,
while still allowing for interactively updating all aspects of the scene,
including lighting, material properties, and geometry.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13344&did=231324&ver=0
J.
Günther
Johannes
I.
Wald
Ingo
P.
Slusallek
Philipp
A.
Keller
Alexander
H.W.
Jensen
Henrik Wann
3-905673-12-6
C125675300671F7B-21006C516D311745C1256F710054704D-guenther:04:RTPM
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313382012-09-1987:934
Conference-Paper
Differential Coordinates for Interactive Mesh Editing
English
IEEE
Los Alamitos, USA
2004
2005-04-27
181
190
Genova, Italy
2004-06-07
Shape Modeling International 2004 (SMI 2004)
One of the main challenges in editing a mesh is to retain the visual appearance
of the surface after applying various modifications. In this paper we advocate
the use of linear differential coordinates as means to preserve the
high-frequency detail of the surface. The differential coordinates represent
the details and are defined by a linear transformation of the mesh vertices.
This allows the reconstruction of the edited surface by solving a linear system
that satisfies the reconstruction of the local details in least squares sense.
Since the differential coordinates are defined in a global coordinate system
they are not rotation-invariant. To compensate for that, we rotate them to
agree with the rotation of an approximated local frame. We show that the linear
least squares system can be solved fast enough to guarantee interactive
response time thanks to a precomputed factorization of the coefficient matrix.
We demonstrate that our approach enables to edit complex detailed meshes while
keeping the shape of the details in their natural orientation.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13346&did=231338&ver=0
Y.
Lipman
Yaron
O.
Sorkine
Olga
D.
Cohen-Or
Daniel
D.
Levin
David
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
F.
Giannini
Franca
A.
Pasko
Alexander
0-7695-1909-1
C125675300671F7B-9E569E3E56252F2FC1256E76002DDEAC-LSCLRS2004
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313402012-09-1987:934
Conference-Paper
A Hybrid Hardware-Accelerated Algorithm for High Quality Rendering of Visual Hulls
English
Canadian Information Processing Society
Mississauga, Canada
2004
2005-04-27
41
48
London, Canada
2004-05-17
Graphics Interface 2004
In this paper, a novel hybrid algorithm is presented for the fast construction
and high-quality rendering of visual hulls. We combine the strengths of two
complementary hardware-accelerated approaches: direct constructive solid
geometry (CSG) rendering and texture mapping-based visual cone trimming. The
former approach completely eliminates the aliasing artifacts inherent in the
latter, whereas the rapid speed of the latter approach compensates for the
performance deficiency of the former. Additionally, a new view-dependent
texture mapping method is proposed. This method makes efficient use of graphics
hardware to perform per-fragment blending weight computation, which yields
better rendering quality. Our rendering algorithm is integrated in a
distributed system that is capable of acquiring synchronized video streams and
rendering visual hulls in real time or at interactive frame rates from up to
eight reference views.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13348&did=231340&ver=0
M.
Li
Ming
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
W.
Heidrich
Wolfgang
R.
Balakrishnan
Ravin
1-56881-227-2
C125675300671F7B-5E97702EC03722F3C1256E530064E38A-Li:GI04:HybridVH
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313422012-09-1987:934
Article
Perception-motivated High Dynamic Range Video Encoding
English
2004
2005-04-28
733
741
ACM Transactions on Graphics
23
Due to rapid technological progress in high dynamic range (HDR)
video capture and display, the efficient storage and
transmission of such data is crucial for the completeness of any HDR
imaging pipeline. We propose a new approach for
inter-frame encoding of HDR video, which is embedded in the
well-established MPEG-4 video compression standard. The key
component of our technique is luminance quantization
that is optimized for the contrast threshold perception in the
human visual system. The quantization
scheme requires only 10--11 bits to encode 12 orders of magnitude of
visible luminance range and does not lead to perceivable contouring
artifacts. Besides video encoding, the proposed quantization
provides perceptually-optimized luminance sampling for fast
implementation of any
global tone mapping operator using a lookup table.
To improve the quality of synthetic video sequences, we introduce
a coding scheme for discrete cosine transform (DCT) blocks with
high contrast. We demonstrate the capabilities of HDR video in
a player, which enables decoding, tone mapping, and applying
post-processing effects in real-time. The tone mapping algorithm as well
as its parameters can be changed interactively while the video is playing.
We can simulate post-processing
effects such as glare, night vision, and motion blur, which appear
very realistic due to the usage of HDR data.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13349&did=231342&ver=0
http://edoc.mpg.de/get.epl?fid=13350&did=231342&ver=0
R.
Mantiuk
Rafal
G.
Krawczyk
Grzegorz
K.
Myszkowski
Karol
H.-P.
Seidel
Hans-Peter
J.
Marks
Joe
0730-0301
C125675300671F7B-2BA4C8B1EE81007BC1256EC1003757E0-Mantiuk2004HDREnc
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313432012-09-1987:934
Conference-Paper
Visible Difference Predictor for High Dynamic Range Images
English
IEEE
Piscataway, USA
2004
2005-04-29
2763
2769
Hague, The Netherlands
2004-10-10
2004 IEEE International Conference on Systems, Man & Cybernetics
Since new imaging and rendering systems commonly use physically
accurate lighting information in the form of High-Dynamic Range
data, there is a need for an automatic visual quality assessment of the
resulting images. In this work we extend the Visual Difference Predictor (VDP)
developed by Daly to handle HDR data. This let us predict if a human observer
is able to perceive differences for a pair of HDR images under the adaptation
conditions corresponding to the real scene observation.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13351&did=231343&ver=0
R.
Mantiuk
Rafal
K.
Myszkowski
Karol
H.-P.
Seidel
Hans-Peter
W.
Thissen
Wil
P.
Wieringa
Peter
M.
Pantic
Maja
M.
Ludema
Marcel
0-7803-8567-5
C125675300671F7B-4A5E8413EEF67127C1256F330053216A-Mantiuk2004HDRVDP
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313442012-09-1987:934
Conference-Paper
Fast and {Accurate} {Ray-Voxel} {Intersection} {Techniques} for {Iso-Surface} {Ray} {Tracing}
English
Akademische Verlagsgesellschaft Aka
Berlin, Germany
2004
2005-05-30
429
435
Stanford, USA
2004-11-16
Vision, modeling, and visualization 2004 (VMV-04)
Visualizing iso-surfaces of volumetric data sets is becoming
increasingly important for many practical applications. One crucial
task in iso-surface ray tracing is to find the correct intersection
of a ray with the trilinear-interpolated implicit surface defined by
the data values at the vertices of a given voxel. Currently
available solutions are either accurate but slow or they provide
fast but only approximate solutions.
In this paper, we analyze the available techniques and present a new
intersection algorithm. We compare and evaluate the new algorithm
against previous approaches using both synthetic test cases and real
world data sets.
The new algorithm is roughly three times faster but provides the
same image quality and better numerical stability as previous
accurate solutions.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13352&did=231344&ver=0
G.
Marmitt
Gerd
A.
Kleer
Andreas
H.
Friedrich
Heiko
I.
Wald
Ingo
P.
Slusallek
Philipp
B.
Girod
Bernd
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
3-89838-058-0
C125675300671F7B-2FFF0E33D4E3EF68C1256F7100563528-marmitt:04:IsoIsec
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313472012-09-1987:934
Article
Reconstruction of Volume Data with Quadratic Super Splines
English
2004
2005-05-24
397
409
IEEE Transactions on Visualization and Computer Graphics
10
We propose a new approach to reconstruct nondiscrete models from gridded volume
samples. As a model, we use quadratic trivariate super splines on a uniform
tetrahedral partition. We discuss the smoothness and approximation properties
of our model and compare to alternative piecewise polynomial constructions. We
observe as a non-standard phenomenon that the derivatives of our splines yield
optimal approximation order for smooth data, while the theoretical error of the
values is nearly optimal due to the averaging rules. Our approach enables
efficient reconstruction and visualization of the data. As the piecewise
polynomials are of the lowest possible total degree two, we can efficiently
determine exact ray intersections with an iso-surface for ray-casting.
Moreover, the optimal approximation properties of the derivatives allow to
simply sample the necessary gradients directly from the polynomial pieces of
the splines. Our results confirm the efficiency of the quasi-interpolating
method and demonstrate high visual quality for rendered isosurfaces.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=13353&did=231347&ver=0
C.
Rössl
Christian
F.
Zeilfelder
Frank
G.
Nürnberger
Günther
H.-P.
Seidel
Hans-Peter
C125675300671F7B-136B570DDA9525FAC1256E5300465D7C-rzns:qss:2004
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313482012-09-1987:934
Conference-Paper
Spline Approximation of General Volumetric Data
English
Eurographics
Aire-la-Ville, Switzerland
2004
2005-04-27
71
82
Genova, Italy
2004-06-09
Proceedings of the 9th ACM Symposium on Solid Modeling and Applications (SM 2004)
We present an efficient algorithm for approximating huge general
volumetric data sets, i.e.~the data is given over arbitrarily shaped
volumes and consists of up to millions of samples. The method is based
on cubic trivariate splines, i.e.~piecewise polynomials of total
degree three defined w.r.t. uniform type-6 tetrahedral partitions of
the volumetric domain. Similar as in the recent bivariate
approximation approaches, the splines in three variables
are automatically determined from the discrete data as a result of a
two-step method, where local discrete least
squares polynomial approximations of varying degrees are extended by
using natural conditions, i.e.the continuity and smoothness properties
which determine the underlying spline space. The main advantages of
this approach with linear algorithmic complexity are as follows: no
tetrahedral partition of the volume data is needed, only small
linear systems have to be solved, the local variation and
distribution of the data is automatically adapted,
Bernstein-B{\'e}zier techniques well-known in Computer Aided
Geometric Design (CAGD) can be fully exploited, noisy data are
automatically smoothed. Our numerical examples with huge data sets
for synthetic data as well as some real-world data confirm the
efficiency of the methods, show the high quality of the spline
approximation, and illustrate that the rendered iso-surfaces inherit
a visual smooth appearance from the volume approximating splines.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13354&did=231348&ver=0
C.
Rössl
Christian
F.
Zeilfelder
Frank
G.
Nürnberger
Günther
H.-P.
Seidel
Hans-Peter
G.
Elber
Gershon
N.
Patrikalakis
Nick
P.
Brunet
Pere
3-905673-55-X
C125675300671F7B-F422C083451D4DC4C1256E76002C2509-rzns:sagvd:04
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313502012-09-1987:934
Conference-Paper
Laplacian Surface Editing
English
Eurographics
Aire-la-Ville, Switzerland
2004
2005-06-09
179
188,274
Nice, France
2004-07-08
SGP 2004 (SGP-04) : Symposium on Geometry Processing
Surface editing operations commonly require geometric details of the surface to
be preserved as much as possible. We argue that geometric detail is an
intrinsic property of a surface and that, consequently, surface editing is best
performed by operating over an intrinsic surface representation. We provide
such a representation of a surface, based on the Laplacian of the mesh, by
encoding each vertex relative to its neighborhood. The Laplacian of the mesh is
enhanced to be invariant to locally linearized rigid transformations and
scaling. Based on this Laplacian representation, we develop useful editing
operations: interactive free-form deformation in a region of interest based on
the transformation of a handle, transfer and mixing of geometric details
between two surfaces, and transplanting of a partial surface mesh onto another
surface. The main computation involved in all operations is the solution of a
sparse linear system, which can be done at interactive rates. We demonstrate
the effectiveness of our approach in several examples, showing that the editing
operations change the shape while respecting the structural geometric detail.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13355&did=231350&ver=0
O.
Sorkine
Olga
Y.
Lipman
Yaron
D.
Cohen-Or
Daniel
M.
Alexa
Marc
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
R.
Scopigno
Roberto
D.
Zorin
Denis
D.
Fellner
Dieter
S.
Spencer
Stephen
3-905673-13-4/1727-8384
C125675300671F7B-33613951BE9C91C8C1256E9B002FBA94-SLCARS:2004
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313542012-09-1987:934
InBook
Topology Preserving Thinning of Vector Fields on Triangular Meshes
English
Springer
Berlin, Germany
2004
2005-05-24
353
366
Advances in Multiresolution for Geometric Modelling
Neil A. Dodgson, Michael S. Floater, Malcom A. Sabin
Mathematics and Visualization
We consider the topology of piecewise linear vector fields whose domain is a
piecewise linear 2-manifold, i.e. a triangular mesh. Such vector fields can
describe simulated 2-dimensional flows, or they may reflect geometric
properties of the underlying mesh. We introduce a thinning technique which
preserves the complete topology of the vector field, i.e. the critical points
and separatrices. As the theoretical foundation, we have shown in an earlier
paper that for local modiØcations of a vector field, it is possible to decide
entirely by a local analysis whether or not the global topology is preserved.
This result is applied in a number of compression algorithms which are based on
a repeated local modification of the vector field, namely a repeated
edge-collapse of the underlying piecewise linear domain.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13356&did=231354&ver=0
H.
Theisel
Holger
C.
Rössl
Christian
H.-P.
Seidel
Hans-Peter
N.A.
Dodgson
Neil A.
M.S.
Floater
Michael S.
M.A.
Sabin
Malcom A.
3-540-21462-3
C125675300671F7B-786D77D58525CD29C1256E77004B68B3-trs:tptfv:04
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313552012-09-1987:934
Conference-Paper
Normal Based Estimation of the Curvature Tensor for Triangular Meshes
English
IEEE
Los Alamitos, USA
2004
2005-04-27
288
297
Seoul, South Korea
2004-10-06
12th Pacific Conference on Computer Graphics and Applications, PG 2004
We introduce a new technique for estimating the curvature tensor of a
triangular mesh. The input of the algorithm is only a single triangle equipped
with its (exact or estimated) vertex normals. This way we get a smooth function
of the curvature tensor inside each triangle of the mesh. We show that the
error of the new method is comparable with the error of a cubic fitting
approach if the incorporated normals are estimated. If the exact normals of the
underlying surface are available at the vertices, the error drops signifi-
cantly. We demonstrate the applicability of the new estimation at a rather
complex data set.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=13357&did=231355&ver=0
H.
Theisel
Holger
C.
Rössl
Christian
R.
Zayer
Rhaleb
H.-P.
Seidel
Hans-Peter
D.
Cohen-Or
Daniel
H.-S.
Ko
Hyeong-Seok
D.
Terzopoulos
Demetri
J.
Warren
Joe
0-7695-2234-3
C125675300671F7B-32AFDE8594758F3EC1256EBF0032FD01-Theisel:PG:2004
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313642012-09-1987:934
Conference-Paper
An Interactive Out-of-Core Rendering Framework for Visualizing Massively Complex Models
English
Eurographics
Aire-la-Ville, Switzerland
2004
2005-06-10
81
92
Norrkoeping, Sweden
2004-06-21
Rendering Techniques 2004 : Eurographics Symposium on Rendering
With the tremendous advances in both hardware capabilities and
rendering algorithms, rendering performance is steadily increasing.
Even consumer graphics hardware can render many million
triangles per second. However, scene complexity seems to be rising
even faster than rendering performance, with no end to even more
complex models in sight.
In this paper, we are targeting the interactive visualization of the
``Boeing 777'' model, a highly complex model of 350 \emph{million}
individual triangles, which -- due to its sheer size and complex
internal structure -- simply cannot be handled satisfactorily by
today's techniques. To render this model, we use a combination of
real-time ray tracing, a low-level out of core caching and demand
loading strategy, and a hierarchical, hybrid
volumetric/lightfield-like approximation scheme for representing
not-yet-loaded geometry.
%
With this approach, we are able to render the full
777 model at several frames per second even on a single
commodity desktop PC.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13358&did=231364&ver=0
I.
Wald
Ingo
A.
Dietrich
Andreas
P.
Slusallek
Philipp
A.
Keller
Alexander
H.W.
Jensen
Henrik Wann
3-905673-12-6
C125675300671F7B-D4EF77FCF6330EBDC1256F710053C9A8-wald:04:Boeing
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313722012-09-1987:934
Conference-Paper
Multi-Video Compression in Texture Space
English
IEEE
Piscataway, USA
2004
2005-04-27
2467
2470
Singapore
2004-10-24
11th IEEE International Conference on Image Processing (ICIP 2004)
We present a model-based approach to encode multiple synchronized
video streams depicting a dynamic scene from different viewpoints.
With approximate 3D scene geometry available, we compensate for
motion as well as disparity by transforming all video images
to object textures prior to compression.
A two-level hierarchical coding strategy is employed to efficiently
exploit inter-texture coherence as well as to ensure quick random
access during decoding.
Experimental validation shows that attainable compression ratios
range up to 50:1 without subsampling.
The proposed coding scheme is intended for use in conjunction with
Free-Viewpoint Video and 3D-TV applications.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13360&did=231372&ver=0
G.
Ziegler
Gernot
H.P.A.
Lensch
Hendrik P. A.
N.
Ahmed
Naveed
M.
Magnor
Marcus
H.-P.
Seidel
Hans-Peter
0-7803-8555-1
C125675300671F7B-D17123167FD763FEC1256EC4004487AE-Ziegler2003
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2313912012-09-1987:930
Conference-Paper
Probabilistic Ranking of Database Query Results
English
Morgan Kaufmann
St. Louis, USA
2004
2005-06-15
888
899
Toronto, Canada
2004-08-31
Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)
We investigate the problem of ranking answers to a database query when many
tuples are returned. We adapt and apply principles of probabilistic models from
Information Retrieval structured data. Our proposed solution is domain
independent. It leverages data and workload statistics and corelations. Our
ranking functions can be further customized for different applications. We
present results of preliminary experiments which demonstrate the efficiency as
well as the quality of our ranking system.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=13369&did=231391&ver=0
S.
Chaudhuri
Surajit
G.
Das
Gautam
V.
Hristidis
Vagelis
G.
Weikum
Gerhard
M. A.
Nascimento
Mario A.
M. T.
Özsu
M. Tamer
D.
Kossmann
Donald
R. J.
Miller
Renee J.
J. A.
Blakeley
Jose A.
K. B.
Schiefer
K. Bernhard
0-12-088469-0
C1256DBF005F876D-6A49EE9F04259CF0C1256F80005257A6-ChaudhuriDHW04
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2313942012-09-1987:930
Conference-Paper
COMPASS: A Concept-based {Web} Search Engine for {HTML,} {XML,} and {Deep} {Web} {Data}
English
Morgan Kaufmann
St. Louis, USA
2004
2005-06-15
1313
1316
Toronto, Canada
2004-08-29
Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=13370&did=231394&ver=0
J.
Graupmann
Jens
M.
Biwer
Michael
C.
Zimmer
Christian
P.
Zimmer
Patrick
M.
Bender
Matthias
M.
Theobald
Martin
G.
Weikum
Gerhard
M. A.
Nascimento
Mario A.
M. T.
Özsu
M. Tamer
D.
Kossmann
Donald
R. J.
Miller
Renee J.
J. A.
Blakeley
Jose A.
K. B.
Schiefer
K. Bernhard
0-12-088469-0
C1256DBF005F876D-54A79EE228BBED50C1256F800055F92D-COMPASS_VLDB04
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2313952012-09-1987:930
Conference-Paper
Concept-Based Search on Semi-structured Data Exploiting Mined Semantic Relations
English
Springer
Berlin, Germany
2004
2005-06-16
34
43
Heraklion, Crete, Greece
2004-03-14
Current trends in database technology, EDBT 2004 Workshops : EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb
Lecture Notes in Computer Science
No
notspecified
published
http://edoc.mpg.de/get.epl?fid=13371&did=231395&ver=0
J.
Graupmann
Jens
W.
Lindner
Wolfgang
M.
Mesiti
Marco
C.
Türker
Can
Y.
Tzitzikas
Yannis
A.
Vakali
Athena
3-540-23305-9
C1256DBF005F876D-2534E2E61F8C5D84C1256F9000359EE6-Graupmann2004a
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2313972012-09-1987:930
Conference-Paper
Relevance Feedback in XML Retrieval
English
Springer
Berlin, Germany
2004
2005-05-31
187
196
Heraklion, Crete, Greece
2004-03-14
Current trends in database technology, EDBT 2004 Workshops : EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb
Lecture Notes in Computer Science
Highly heterogeneous XML data collections that do not have a global schema, as
arising, for example, in federations of digital libraries or scientific data
repositories, cannot be effectively queried with XQuery or XPath alone, but
rather require a ranked retrieval approach. As known from ample work in the IR
field, relevance feedback provided by the user that drives automatic query
refinement or expansion can often lead to improved search result quality (e.g.,
precision or recall). In this paper we present a framework for feedback-driven
XML query refinement and address several building blocks including reweighting
of query conditions and ontology-based query expansion.We point out the issues
that arise specifically in the XML context and cannot be simply addressed by
straightforward use of traditional IR techniques, and we present our approaches
towards tackling them.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13373&did=231397&ver=0
H.
Pan
Hanglin
W.
Lindner
Wolfgang
M.
Mesiti
Marco
C.
Türker
Can
Y.
Tzitzikas
Yannis
A.
Vakali
Athena
3-540-23305-9
C1256DBF005F876D-D84C9ABD4EC4326FC1256ED8003DB3DB-Pan2004a
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2313982012-09-1987:930
Conference-Paper
Query Refinement by Relevance Feedback in an XML Retrieval System (Demo)
English
Springer
Berlin, Germany
2004
2005-05-31
854
855
Shanghai, China
2004-11-08
Conceptual modeling, ER 2004 : 23rd International Conference on Conceptual Modeling
Lecture Notes in Computer Science
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13374&did=231398&ver=0
H.
Pan
Hanglin
A.
Theobald
Anja
R.
Schenkel
Ralf
P.
Atzeni
Paolo
W.
Chu
Wesley
H.
Lu
Hongjun
S.
Zhou
Shuigeng
T.W.
Ling
Tok Wang
3-540-23723-2
C1256DBF005F876D-30392E952BE82AADC1256EDF00345B4A-PanTS2004
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2313992012-09-1987:930
Conference-Paper
An Information System for Material Microstructures
English
IEEE
Los Alamitos, USA
2004
2005-05-31
329
332
Santorini Island Greece
2004-06-21
16th International Conference on Scientific and Statistical Database Management, SSDBM 2004
This paper presents an information system that supports a materialographic
laboratory in classifying material samples based on microstructure images. The
system uses database and Web technologies to manage its information and make it
accessible to Internet users. Its core is a classifier, based on support vector
machines, that provides an automatic diagnosis of the material class of a given
sample. The classifier uses texture features from an underlying image analysis,
the so-called Haralick parameters, and stereologic features such as fractal
dimension, Euler parameter, etc. In addition to the classifier, the system
provides a sensitivity analysis that allows the user to understand which
features are most influential for certain classification decisions. The system
is fully operational and can be used on the Web.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13375&did=231399&ver=0
K.
Roberts
Kathrin
F.
Mücklich
Frank
R.
Schenkel
Ralf
G.
Weikum
Gerhard
M.
Hatzopoulos
Michael
Y.
Manolopoulos
Yannis
0-7695-2146-0
C1256DBF005F876D-0DA69B7B0382AEB9C1256E660032C83C-RobertsMSW04
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314002012-09-1987:930
Conference-Paper
FliX: A Flexible Framework for Indexing Complex {XML} Document Collections
English
Springer
Berlin, Germany
2004
2005-05-31
240
249
Heraklion, Creta, Greece
2004-03-14
Current trends in database technology, EDBT 2004 Workshops : EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb
Lecture Notes in Computer Science
While there are many proposals for path indexes on XML documents, none of them
is perfectly suited for indexing large-scale collections of interlinked XML
documents. Existing strategies lack support for intra- or inter-document links,
require large amounts of time to build or space to store the index, or cannot
efficiently answer connection queries. This paper presents the {\em FliX}
framework for connection indexing that supports large, heterogeneous document
collections with many links, using the existing path indexes as building
blocks. We introduce some example configurations of the framework that are
appropriate for many important application scenarios. Experiments show the
feasibility of our approach.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13376&did=231400&ver=0
R.
Schenkel
Ralf
W.
Lindner
Wolfgang
M.
Mesiti
Marco
C.
Türker
Can
Y.
Tzitzikas
Yannis
A.
Vakali
Athena
3-540-23305-9
C1256DBF005F876D-AA94847CDADEF580C1256E3E002985D2-Schenkel2004
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314022012-09-1987:930
Conference-Paper
Restrictive Clustering and Metaclustering for self-organizing Document Collections
English
ACM
New York, USA
2004
2005-05-31
226
233
Sheffield, UK
2004-07-25
Proceedings of SIGIR 2004: the Twenty-Seventh Annual International ACM SIGIR Conference on Research and Development in Information Retrieval
This paper addresses the problem of automatically structuring
heterogenous document collections by using clustering
methods. In contrast to traditional clustering, we study
restrictive methods and ensemble-based meta methods that
may decide to leave out some documents rather than assigning
them to inappropriate clusters with low confidence.
These techniques result in higher cluster purity, better overall
accuracy, and make unsupervised self-organization more
robust. Our comprehensive experimental studies on three
different real-world data collections demonstrate these benefits.
The proposed methods seem particularly suitable for
automatically substructuring personal email folders or personal Web directories
that are populated by focused crawlers,
and they can be combined with supervised classification
techniques.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13378&did=231402&ver=0
S.
Siersdorfer
Stefan
S.
Sizov
Sergej
K.
Järvelin
Kalervo
J.
Allan
James
P.
Bruza
Peter
M.
Sanderson
Mark
C1256DBF005F876D-E59B5C01F1FE5919C1256F950033BD8F-SiersClust2004
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314032012-09-1987:930
Conference-Paper
Goal-oriented Methods and Meta Methods for Document Classification and their Parameter Tuning
English
ACM
New York, USA
2004
2005-05-31
59
68
Washington D.C., USA
2004-11-08
CIKM 2004 : proceedings of the Thirteenth Conference on Information and Knowledge Management
Automatic text classification methods come with various
calibration parameters such as thresholds for probabilities in
Bayesian classifiers or for hyperplane distances in SVM
classifiers. In a given application context these parameters
should be set so as to meet the relative importance of various
result quality metrics such as precision versus recall. In this
paper we consider classifiers that can accept a document for a
topic, reject it, or abstain. We aim to meet the application's
goals in terms of accuracy (i.e., avoid false acceptances or
rejections) and loss (i.e., limit the fraction of documents for which no
decision is
made).
To this end we investigate restrictive forms
of Support Vector Machine classifiers and we develop meta
methods that split the training data into subsets for
independently trained classifiers and then combine the results of
these classifiers. These techniques tend to improve accuracy at
the expense of document loss. We develop estimators that help to
predict the accuracy and loss for a given setting of the methods'
tuning parameters, and a methodology for efficiently deriving
a setting that meets the application's goals. Our experiments
confirm the practical viability of the approach.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13379&did=231403&ver=0
S.
Sizov
Sergej
S.
Siersdorfer
Stefan
G.
Weikum
Gerhard
D.A.
Evans
David A.
L.
Gravano
Luis
O.
Herzog
Otthein
C.
Zhai
ChengXiang
M.
Ronthaler
Marc
C1256DBF005F876D-EE103EB2A21109DCC1256F9500333F20-SizovClass2004
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314042012-09-1987:930
Conference-Paper
BINGO! and {Daffodil:} {Personalized} Exploration of Digital Libraries and {Web} Sources
English
LE CENTRE DE HAUTES ETUDES INTERNATIONALES (C.I.D.)
Paris, France
2004
2005-06-16
347
365
Avignon, France
2004-04-26
RIAO 2004
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13380&did=231404&ver=0
M.
Theobald
Martin
C.-P.
Klas
Claus-Peter
2 905450-09-6
C1256DBF005F876D-B385C8AFA1C8B7FCC1256E9E002FE9D3-Theobald2003
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314052012-09-1987:930
Conference-Paper
Top-k Query Evaluation with Probabilistic Guarantees
English
Morgan Kaufmann
St. Louis, USA
2004
2005-06-15
648
659
Toronto, Canada
2004-08-30
Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB)
Top-k queries based on ranking elements of multidimensional datasets are a
fundamental building block for many kinds of information discovery. The best
known general-purpose algo-rithm for evaluating top-k queries is Fagin’s
threshold algorithm (TA). Since the user’s goal behind top-k queries is to
identify one or a few relevant and novel data items, it is intriguing to use
approximative variants of TA to reduce run-time costs. This paper introduces a
family of approximative top-k algorithms based on probabilistic arguments. When
scanning index lists of the underlying multidimensional data space in
descending order of local scores, various forms of convolution and derived
bounds are employed to predict when it is safe, with high probability, to drop
candidate items and to prune the index scans. The precision and the efficiency
of the developed methods are experimentally evaluated based on a large Web
corpus and a structured data collection.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13381&did=231405&ver=0
M.
Theobald
Martin
G.
Weikum
Gerhard
R.
Schenkel
Ralf
M.A.
Nascimento
Mario A.
M.T.
Özsu
M. Tamer
D.
Kossmann
Donald
R.J.
Miller
Renée J.
J.A.
Blakeley
José A.
K.B.
Schiefer
K. Bernhard
0-12-088469-0
C1256DBF005F876D-D56A76BD22C08825C1256E9700284CB5-TheobaldWS04
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314082012-09-1987:930
Conference-Paper
Bookmark-driven Query Routing in Peer-to-Peer Web Search
English
Universität Duisburg-Essen
Duisburg, Germany
2004
2005-06-27
1
12
Sheffield, UK
2004-07-25
Proceedings of the SIGIR Workshop on Peer-to-Peer Information Retrieval : 27th Annual International ACM SIGIR Conference ; SIGIR 2004 P2PIR Workshop
We consider the problem of collaborative Web search and query routing
strategies in a peer-to-peer (P2P) environment.
In our architecture every peer has a full-fledged search engine with a
(thematically focused) crawler
and a local index whose contents may be tailored to the user's specific
interest profile.
Peers are autonomous and post meta-information about their bookmarks and index
lists to
a global directory, which is efficiently implemented in a decentralized manner
using
Chord-style distributed hash tables. A query posed by one peer is first
evaluated locally;
if the result is unsatisfactory the query is forwarded to selected peers. These
peers are
chosen based on a benefit/cost measure where benefit reflects the thematic
similarity
of peers' interest profiles, derived from bookmarks, and cost captures
estimated peer load
and response time. The meta-information that is needed for making these query
routing
decisions is efficiently looked up in the global directory; it can also be
cached and
proactively disseminated for higher availability and reduced network load.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13382&did=231408&ver=0
M.
Bender
Matthias
S.
Michel
Sebastian
C.
Zimmer
Christian
G.
Weikum
Gerhard
J.
Callan
Jamie
N.
Fuhr
Norbert
W.
Nejdl
Wolfgang
C1256DBF005F876D-866AC1720F945D9FC1256EDE003F3D47-BMZW_SIGIR04
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314092012-09-1987:930
Conference-Paper
XXL @ {INEX} 2003
English
INEX
Dagstuhl, Germany
2004
2005-06-27
59
66
Dagstuhl, Germany
2003-12-15
Proceedings of the Second INEX Workshop
Information retrieval on XML combines retrieval on content data (element and
attribute values) with retrieval on structural data (element and attribute
names). Standard query languages for XML such as XPath or XQuery support
Boolean retrieval: a query result is a (possibly restructured) subset of XML
elements or entire documents that satisfy the search conditions of the query.
Such search conditions consist of regular path expressions including wildcards
for paths of arbitrary length and boolean content conditions.
We developed a flexible XML search language called XXL for probabilistic ranked
retrieval on XML data. XXL offers a special operator '$\sim$' for specifying
semantic similarity search conditions on element names as well as element
values. Ontological knowledge and appropriate index structures are necessary
for semantic similarity search on XML data extracted from the Web, intranets or
other document collections. The XXL Search Engine is a Java--based prototype
implementation that support probabilistic ranked retrieval on a large corpus of
XML data.
This paper outlines the architecture of the XXL system and discusses its
performance in the INEX benchmark.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13383&did=231409&ver=0
R.
Schenkel
Ralf
A.
Theobald
Anja
G.
Weikum
Gerhard
N.
Fuhr
Norbert
M.
Lalmas
Mounia
S.
Malik
Saadia
C1256DBF005F876D-361ABEEBDA0D6B1CC1256DF10056E83A-SchenkelTW2003b
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314102012-09-1987:930
Thesis
Neighborhood-conscious Hypertext Categorization
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13384&did=231410&ver=0
R.
Angelova
Ralitsa
C1256DBF005F876D-6AF7A886CD7F422AC1256F9000399970-angelova2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314112012-09-1987:930
Thesis
Entwurf und Implementierung eines Mobile-Access-Servers
German
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-04
expertsonly
http://edoc.mpg.de/get.epl?fid=13385&did=231411&ver=0
T.
Bautz
Tim
C1256DBF005F876D-D04D3B3C48E0675DC1256EDE0039A7E1-Bautz2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314122012-09-1987:930
Thesis
Time-aware and Trend-based Authority Ranking
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13386&did=231412&ver=0
K.
Berberich
Klaus
C1256DBF005F876D-D5FCBC7165B8EF7EC1256F43004B2315-KBerberich2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314132012-09-1987:930
Thesis
Advanced Divide-and-Conquer Algorithms for Computing Two-Hop Covers for Large Collections of XML Documents
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13387&did=231413&ver=0
A.
Broschart
Andreas
C1256DBF005F876D-C4EFE1E784999AB3C1256F17003B455B-Broschart2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314142012-09-1987:930
Thesis
Bootstrapping Ontologies from the Web
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13388&did=231414&ver=0
J.
Cai
Jun
C1256DBF005F876D-912200C78757242DC1256EDE0039161C-JunCai2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314152012-09-1987:930
Thesis
Generische Anbindung von Datenhaltungssystemen mit Web Services am Beispiel von SAP R/3
German
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13389&did=231415&ver=0
J.
Diesinger
Jörg
C1256DBF005F876D-CFFDE3BA9F4F51E9C1256F900039FCA6-Diesinger2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314162012-09-1987:930
Thesis
User Profile Management in a Web Search Engine
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13390&did=231416&ver=0
V.
Eske
Vladimir
C1256DBF005F876D-983FC84653920A97C1256EDE00394B65-Eske2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314172012-09-1987:930
Thesis
Ein automatisches Annotationswerkzeug für HTML- und XML-Daten unter Verwendung von Hidden Markov Models und Named Entity Recognition
German
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13391&did=231417&ver=0
M.
Gerstacker
Miriam
C1256DBF005F876D-9C55BEF123831E3FC1256F1C003F4019-Gerstacker2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314182012-09-1987:930
Thesis
Implementation and Evaluation of a Path Indexing Framework for Large Collections of Interlinked XML Documents
English
Universität des Saarlandes
Saarbrücken, Saarland
2004-07
master
expertsonly
V, 115 S.
http://edoc.mpg.de/get.epl?fid=13392&did=231418&ver=0
M. A..
Khalid
Mahboob Alam
C1256DBF005F876D-3634C105CC851603C1256EDE003817E3-Khalid2004
MPI für Informatik
Databases and Information Systems Group
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314192012-09-1987:930
Thesis
Query-Log-based Authority Analysis for Web Information Search
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-03-09
expertsonly
http://edoc.mpg.de/get.epl?fid=13393&did=231419&ver=0
J.
Luxenburger
Julia
C1256DBF005F876D-60685A5A8742EFECC1256F43004CBCA8-JLuxenburger2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314202012-09-1987:930
Thesis
Intelligente Informationsorganisation und -suche für ein thematisch fokussiertes Web-Informationsportal
German
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13394&did=231420&ver=0
T.
Michels
Thomas
C1256DBF005F876D-E9A893DBDC82493EC1256FBF003B62F2-Michels2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314222012-09-1987:930
Thesis
A light-weight Workflow Management System based on Web Services
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-03-09
expertsonly
http://edoc.mpg.de/get.epl?fid=13396&did=231422&ver=0
S.
Vangala
Saipradeep
C1256DBF005F876D-BF121CF08F367FF1C1256F9000371E5A-Vangala2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314232012-09-1987:930
Thesis
Integrating Web Portals into a concept-based search engine using ontologies
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-03-09
expertsonly
http://edoc.mpg.de/get.epl?fid=13397&did=231423&ver=0
X.
Wang
Xueqiang
C1256DBF005F876D-794EBD492E683F6EC1256F1C00404071-Wang2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314242012-09-1987:930
PhD-Thesis
Variability of Packet Round-Trip Times and Passive Bottleneck Bandwidth Estimation
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
expertsonly
http://edoc.mpg.de/get.epl?fid=13398&did=231424&ver=0
M.
Ohlmann
Michael
C1256DBF005F876D-83AFE46D13FE04E2C1256F94003DFCE5-Ohlmann2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2314252012-09-1987:930
PhD-Thesis
Die XXL-Suchmaschine zur ontologiebasierten Ähnlichkeitssuche in XML-Dokumenten
English
Universität des Saarlandes
Saarbrücken, Saarland
2005-05-02
In dieser Arbeit wird die XXL-Suchmaschine vorgestellt. Sie wertet Anfragen
aus, die in der XML-Anfragesprache XXL formuliert sind. Eine XXL-Anfrage
umfasst dabei Suchbedingungen an die Struktur und an den Inhalt von
XML-Dokumenten.
expertsonly
http://edoc.mpg.de/get.epl?fid=13399&did=231425&ver=0
A.
Theobald
Anja
C1256DBF005F876D-877B9480E2F16E1FC1256F17003C90BC-ATheobald2004
MPI für Informatik
Databases and Information Systems Group
2019
2012-09-19 10:34:35.942723
oai:edoc.mpg.de:2318002010-12-0387:937
Conference-Paper
A Mobile System for Multi-Video Recording
English
Institution of Electrical Engineers
London, UK
2004
2005-05-30
127
132
Savoy Place, London, UK
2004-03-15
1st European Conference on Visual Media Production (CVMP)
\begin{abstract}
We present a portable system to record synchronised, multi-video data
for vision applications such as 3D
reconstruction and video-based rendering of dynamic scenes.
The aim of the project is
to gain access to a greater number of scenes than what a static, wired
indoor studio allows for. The portable acquisition system is
constructed from a number of independent modules, each consisting of
a FireWire camera and a laptop. Our software utilises wireless
networking making the system behave
like a tightly coupled unit without requiring the modules to be
physically connected to each other. The scheme also includes an
external calibration method suitable for general scenes.
The system is scalable and
allows for easy transportation and ad-hoc setup and configuration. We present
recent result
s acquired in the field and their use for free-viewpoint video.
\end{abstract}
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13426&did=231800&ver=0
L.
Ahrenberg
Lukas
I.
Ihrke
Ivo
M.
Magnor
Marcus
0863413919
C1256BDE005F57A8-0C723EB0277CED48C1256E8A0032E529-Ahrenberg2004a
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318012010-12-0387:937
Conference-Paper
Spacetime-coherent Geometry Reconstruction from Multiple Video Streams
English
IEEE
Los Alamitos, USA
2004
2005-05-30
365
372
Thessaloniki, Greece
2004-09-06
2nd International Symposium on 3D Data Processing, Visualization, and Transmission, 3DPVT 2004
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13427&did=231801&ver=0
M.
Magnor
Marcus
B.
Goldluecke
Bastian
Y.
Aloimonos
Y.
0-7695-2223-8
C1256BDE005F57A8-68938767035BFCFFC1256F47003C29B8-Magnor2004:SCG
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318022010-12-0387:937
Conference-Paper
Cloth Motion from Optical Flow
English
Akademische Verlagsgesellschaft Aka
Berlin, Germany
2004
2005-05-30
117
124
Stanford, USA
2004-11-16
Vision, modeling, and visualization 2004 (VMV-04)
This paper presents an algorithm for capturing the motion of deformable
surfaces, in particular textured cloth. In a calibrated multi-camera setup, the
optical flow between consecutive video frames is determined and 3D scene flow
is computed. We use a deformable surface model with constraints for vertex
distances and curvature to increase the robustness of the optical flow
measurements. Tracking errors in long video sequences are corrected by a
silhouette matching procedure. We present results for synthetic cloth
simulations and discuss how they can be extended to real-world footage.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13428&did=231802&ver=0
V.
Scholz
Volker
M.
Magnor
Marcus
B.
Girod
B.
M.
Magnor
M.
H.-.P.
Seidel
H.-P.
3-89838-058-0
C1256BDE005F57A8-DAB1C4108465E349C1256F5E003D5E98-Scholz2004
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318062010-12-0387:937
Conference-Paper
Constrained Inverse Volume Rendering for Planetary Nebulae
English
IEEE
Piscataway, USA
2004
2005-05-30
83
90
Austin, USA
2004-10-10
IEEE Visualization 2004 : VIS 2004
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13432&did=231806&ver=0
M.
Magnor
Marcus
G.
Kindlmann
Gordon
C.
Hansen
Charles
N.
Duric
Neb
H.
Rushmeier
Holly
G.
Turk
Greg
J.J.
van Wijk
Jarke J.
0-7803-8788-0
C1256BDE005F57A8-358F8EC33E4A418BC1256F3A002B87B4-Magnor04:CIVR
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318102010-12-0387:937
Conference-Paper
External camera calibration for synchronized multi-video systems
English
UNION Agency
Plzen, Czech Republic
2004
2005-05-30
537
544
Plzen, Czech Republic
2004-05-03
WSCG '2004 : the 12th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2004 ; short communication papers proceedings
Journal of WSCG
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13435&did=231810&ver=0
I.
Ihrke
Ivo
L.
Ahrenberg
Lukas
M.
Magnor
Marcus
1213-6972
C1256BDE005F57A8-DAB19CE6DD99DC79C1256E89005E3BB4-Ihrke04:ECC
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318132012-09-1987:934
Thesis
A flexible framework for learning-based Surface Reconstruction
English
Universität des Saarlandes
Saarbrücken, Saarland
2004-12-10
master
The problem of Surface Reconstruction arises in many real world situations. We
introduce in detail the problem itself and then take a brief look into its
applications and existing techniques, particularly learning based techniques,
developed for its solution. Having presented the context, we closely examine
one such learning based technique – the Neural Mesh algorithm for Surface
Reconstruction.
Despite being relatively recent, the Neural Mesh algorithm has already
undergone several revisions, thus giving rise to several variants of the
original algorithm. We study the algorithm and each of its variants in detail.
All variants rely in varying
degrees on a specific aspect of the algorithm – a signal counter. We observe
that algorithmic reliance on the signal counter impedes performance and propose
an alternate way of performing the same functionalities – using a list.
Additionally, on the practical side, we identify areas where inhouse
implementations of the algorithms were wanting in efficiency and revise those
areas.
Changing over from the signal counter to the list represents a change in
approach from the exact learning of the original algorithms to a comparative
learning framework. We show empirically that this change in approach does not
produce any significant difference in the quality of the algorithms’ output,
while performance, in terms of running time, increases dramatically.
expertsonly
http://edoc.mpg.de/get.epl?fid=13437&did=231813&ver=0
W.
Saleem
Waqar
C125675300671F7B-F4540CF23A7A0ECAC1256FC4005E2035-thesis05s
MPI für Informatik
Computer Graphics Group
2012-09-19 10:32:52.452725
oai:edoc.mpg.de:2318192010-12-0387:937
Conference-Paper
Image-Based Tomographic Reconstruction of Flames
English
Eurographics Association
Aire-la-Ville, Switzerland
2004
2005-05-30
367
375
Grenoble, Frace
2004-08-27
Computer Animation 2004 : ACM SIGGRAPH / Eurographics Symposium on Computer Animation
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13440&did=231819&ver=0
I.
Ihrke
Ivo
M.
Magnor
Marcus
R.
Boulic
R.
D.K.
Pai
D.K.
3-905673-14-2
C1256BDE005F57A8-794F8FF285F1F302C1256F3A003B3CEC-Ihrke2004:IBT
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318202010-12-0387:937
Conference-Paper
Weighted Minimal Hypersurfaces and Their Applications in Computer Vision
English
Springer
Berlin, Germany
2004
2005-05-30
366
378
Prague, Czech Republic
2004-05-11
Computer vision, ECCV 2004 : 8th European Conference on Computer Vision - part II
Lecture Notes in Computer Science
Many interesting problems in computer vision can be formulated as a
minimization problem for an {\em energy functional}.
If this functional is given as an integral of a scalar-valued weight function
over an unknown hypersurface, then the minimal surface we are looking for can
be determined as a solution of the functional's Euler-Lagrange equation.
This paper deals with a general class of weight functions
that may depend on the surface point and normal.
By making use of a mathematical tool called {\em the method of the moving
frame},
we are able to derive the Euler-Lagrange equation in arbitrary-dimensional
space and without the need for any surface parameterization.
Our work generalizes existing proofs, and we demonstrate that it
yields the correct evolution equations for a variety of previous
computer vision techniques which can be expressed in terms of our
theoretical framework.
In practical applications, the surface evolution which converges to a
solution of the Euler-Lagrange equation can be implemented using level
set techniques.
The well-known transition to a level set evolution equation,
which we briefly review in this paper, works in the general case as well.
That way, problems involving minimal hypersurfaces in dimensions higher than
three,
which were previously impossible to solve in practice, can now be introduced
and handled by generalized versions of existing algorithms.
As one example, we sketch a novel idea how to reconstruct
temporally coherent geometry from multiple video streams.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13441&did=231820&ver=0
B.
Goldluecke
Bastian
M.
Magnor
Marcus
T.
Pajdla
Tomás
J.
Matas
Jirí
3-540-21983-8
C1256BDE005F57A8-5D4FEC9A7AF94570C1256E8B00323A5F-Goldluecke2004:WMH
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
oai:edoc.mpg.de:2318212010-12-0387:937
Conference-Paper
Space-Time Isosurface Evolution for Temporally Coherent 3D Reconstruction
English
IEEE
Los Alamitos, USA
2004
2005-05-30
350
355
Washington, D.C., USA
2004-06-27
Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2004
We model the dynamic geometry of a time-varying scene as a 3D isosurface in
space-time.
The intersection of the isosurface with planes of constant time yields the
geometry at a
single time instant.
An optimal fit of our model to multiple video sequences is
defined as the minimum of an energy functional.
This functional is given by an integral over the entire hypersurface,
which is designed to optimize photo-consistency.
A PDE-based evolution derived from the Euler-Lagrange equation
maximizes consistency with all of the given video data simultaneously.
The result is a 3D model of the scene which varies smoothly over time.
The geometry reconstructed by this scheme
is significantly better than results obtained by space-carving approaches
that do not enforce temporal coherence.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=13442&did=231821&ver=0
B.
Goldluecke
Bastian
M.
Magnor
Marcus
0-7695-2158-4
C1256BDE005F57A8-B88539A181A327BBC1256E8B0032B085-Goldluecke2004:STI
MPI für Informatik
Graphics - Optics - Vision
2010-12-03 15:40:48.963684
ResultSet_9R22ajuUuPi_range_100-199