The Experts below are selected from a list of 11457 Experts worldwide ranked by ideXlab platform
Micha Sharir - One of the best experts on this subject based on the ideXlab platform.
-
Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications
Discrete & Computational Geometry, 2020Co-Authors: Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha SharirAbstract:We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $$L_p$$ L p -norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $$O(n \log ^3 n)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ O ( log n ) time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $$O(n^{\varepsilon })$$ O ( n ε ) factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “Vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the Vertical Decomposition of these levels. Finally, to obtain our structure, we combine our Vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).
-
Decomposing Arrangements of Hyperplanes: VC-Dimension, Combinatorial Dimension, and Point Location
Discrete & Computational Geometry, 2019Co-Authors: Esther Ezra, Haim Kaplan, Sariel Har-peled, Micha SharirAbstract:This work is motivated by several basic problems and techniques that rely on space Decomposition of arrangements of hyperplanes in high-dimensional spaces, most notably Meiser’s 1993 algorithm (Meiser in Inf Comput 106(2):286–303, 1993) for point location in such arrangements. A standard approach to these problems is via random sampling, in which one draws a random sample of the hyperplanes, constructs a suitable Decomposition of its arrangement, and recurses within each cell of the Decomposition with the subset of hyperplanes that cross the cell. The efficiency of the resulting algorithm depends on the quality of the sample, which is controlled by various parameters. One of these parameters is the classical VC-dimension , and its associated primal shatter dimension , of a suitably defined corresponding range space. Another parameter, which we refer to here as the combinatorial dimension , is the maximum number of hyperplanes that are needed to define a cell that can arise in the Decomposition of some sample of the input hyperplanes; this parameter arises in Clarkson’s (and later Clarkson and Shor’s) random sampling technique. We re-examine these parameters for the two main space Decomposition techniques— bottom-vertex triangulation , and Vertical Decomposition , including their explicit dependence on the dimension d , and discover several unexpected phenomena, which show that, in both techniques, there are large gaps between the VC-dimension (and primal shatter dimension), and the combinatorial dimension. Our main application is to point location in an arrangement of n hyperplanes is $$\mathbb {R}^d$$ R d , in which we show that the query cost in Meiser’s algorithm can be improved if one uses Vertical Decomposition instead of bottom-vertex triangulation, at the cost of some increase in the preprocessing cost and storage (which seem to be stated incorrectly, and are not worked out, in Meiser’s work). Our improved bounds rely on establishing several new structural properties and improved complexity bounds for Vertical Decomposition, which are of independent interest, and which we expect to find additional applications.
-
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
arXiv: Computational Geometry, 2017Co-Authors: Esther Ezra, Sariel Har-peled, Haim Kaplan, Micha SharirAbstract:$\renewcommand{\Re}{\mathbb{R}}$ We re-examine parameters for the two main space Decomposition techniques---bottom-vertex triangulation, and Vertical Decomposition, including their explicit dependence on the dimension $d$, and discover several unexpected phenomena, which show that, in both techniques, there are large gaps between the VC-dimension (and primal shatter dimension), and the combinatorial dimension. For Vertical Decomposition, the combinatorial dimension is only $2d$, the primal shatter dimension is at most $d(d+1)$, and the VC-dimension is at least $1 + d(d+1)/2$ and at most $O(d^3)$. For bottom-vertex triangulation, both the primal shatter dimension and the combinatorial dimension are $\Theta(d^2)$, but there seems to be a significant gap between them, as the combinatorial dimension is $\frac12d(d+3)$, whereas the primal shatter dimension is at most $d(d+1)$, and the VC-dimension is between $d(d+1)$ and $5d^2 \log{d}$ (for $d\ge 9$). Our main application is to point location in an arrangement of $n$ hyperplanes is $\Re^d$, in which we show that the query cost in Meiser's algorithm can be improved if one uses Vertical Decomposition instead of bottom-vertex triangulation, at the cost of some increase in the preprocessing cost and storage. The best query time that we can obtain is $O(d^3\log n)$, instead of $O(d^4\log d\log n)$ in Meiser's algorithm. For these bounds to hold, the preprocessing and storage are rather large (super-exponential in $d$). We discuss the tradeoff between query cost and storage (in both approaches, the one using bottom-vertex trinagulation and the one using Vertical Decomposition).
-
Symposium on Computational Geometry - A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM
2017Co-Authors: Esther Ezra, Micha SharirAbstract:We show that the k-SUM problem can be solved by a linear decision tree of depth O(n^2 log^2 n),improving the recent bound O(n^3 log^3 n) of Cardinal et al. Our bound depends linearly on k, and allows us to conclude that the number of linear queries required to decide the n-dimensional Knapsack or SubsetSum problems is only O(n^3 log n), improving the currently best known bounds by a factor of n. Our algorithm extends to the RAM model, showing that the k-SUM problem can be solved in expected polynomial time, for any fixed k, with the above bound on the number of linear queries. Our approach relies on a new point-location mechanism, exploiting "Epsilon-cuttings" that are based on Vertical Decompositions in hyperplane arrangements in high dimensions. A major side result of the analysis in this paper is a sharper bound on the complexity of the Vertical Decomposition of such an arrangement (in terms of its dependence on the dimension). We hope that this study will reveal further structural properties of Vertical Decompositions in hyperplane arrangements.
-
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
SIAM Journal on Computing, 1999Co-Authors: Pankaj K. Agarwal, Alon Efrat, Micha SharirAbstract:Let ${\cal F}$ be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the Vertical Decomposition of the $({\le}k)$-level of the arrangement $\A({\cal F})$ is $O(k^{3+\varepsilon}\psi({n/k}))$ for any $\varepsilon>0$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of at most $r$ functions of ${\cal F}$. This bound is nearly optimal in the worst case and implies the existence of shallow cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 169--186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3-dimensional range-searching problems; (ii) dynamic data structures for planar nearest- and farthest-neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.
R. R. K. Sharma - One of the best experts on this subject based on the ideXlab platform.
-
Vertical Decomposition Approach to Solve Single Stage Capacitated Warehouse Location Problem (SSCWLP)
American Journal of Operations Research, 2011Co-Authors: Priyanka Verma, R. R. K. SharmaAbstract:Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we give a “Vertical Decomposition” approach to solve SSCWLP that uses Lagrangian relaxation. This way SSCWLP is broken into two versions of capacitated plant location problem (the CPLP_L and CPLP_R) by relaxing the flow balance constraints. For CPLP_R, we use well known Lagrangian relaxations given in literature (Christofides and Beasley [5] and Nauss [6]); and adopt them suitably for solving CPLP_L. We show theoretically in this paper that SSCWLP can be more efficiently solved by techniques of Vertical Decomposition developed in this paper than the method available in literature (Sharma and Berry [4]). Encouraging computational study is reported in this paper
-
Vertical Decomposition approach to solve single stage capacitated warehouse location problems
2007 IEEE International Conference on Industrial Engineering and Engineering Management, 2007Co-Authors: Pratima Verma, R. R. K. SharmaAbstract:In this paper Vertical Decomposition approach is used for the first time to solve single stage capacitated warehouse location problems (SSCWLP). Stages of warehouse location problems are decomposed to get smaller sized problems, which are relatively easier to solve. New formulation of SSCWLP is developed using the style of (R.R.K. Sharma, 1991); and worked out by applying Vertical Decomposition approach. Relaxation of flow balance constraints leads to two different versions of capacitated plant location problem (CPLP), referred to as RHS_CPLP and LHS_CPLP. It is found that RHS_CPLP is exactly identical to CPLP (R. Sridharan, 1986); but LHS_CPLP is different from RHS_CPLP. Reference (R. Sridharan, 1986) gives 13 relaxations of CPLP (which is found identical to RHSCPLP for this paper). We extend these relaxations for the problem LHSCPLP also. 13 different relaxations of SSCWLP (with the proofs comparing their strengths) are developed. We found that the strong relaxation of SSCWLP given in (R.R.K. Sharma and V. Berry, 2007), is same as relaxation R3_O given in this paper. Also, there are other relaxations of SSCWLP that are better than strong relaxation proposed in (R.R.K. Sharma and V. Berry, 2007).
Etienne Memin - One of the best experts on this subject based on the ideXlab platform.
-
Image assimilation for motion estimation of atmospheric layers with shallow-water model
2016Co-Authors: Nicolas Papadakis, Patrick Heas, Etienne MeminAbstract:The complexity of dynamical laws governing 3D atmospheric flows associated to incomplete and noisy observations makes very difficult the recovery of atmospheric dynamics from satellite images sequences. In this paper, we face the challenging problem of joint estimation of time-consistent horizontal motion fields and pressure maps at various atmospheric depths. Based on a Vertical Decomposition of the atmosphere, we propose a dense motion estimator relying on a multi-layer dynamical model. Noisy and incomplete pressure maps obtained from satellite images are reconstructed according to shallow-water model on each cloud layer using a framework derived from data assimilation. While reconstructing dense pressure maps, this variational process estimates time-consistent horizontal motion fields related to the multi-layer model. The proposed approach is validated on a synthetic example and applied to a real world meteorological satellite image sequence.
-
Pressure image assimilation for atmospheric motion estimation
2016Co-Authors: Thomas Corpetti, Patrick Heas, Etienne Memin, Nicolas PapadakisAbstract:The complexity of dynamical laws governing 3D atmospheric flows associated with incomplete and noisy observations makes the recovery of atmospheric dynamics from satellite images sequences very difficult. In this report, we face the challenging problem of estimating physical sound and time consistent horizontal motion fields at various atmospheric depths for a whole image sequence. Based on a Vertical Decomposition of the atmosphere, we propose two dynamically consistent atmospheric motion estimators relying on different multi-layer dynamical models. Both estimators use a framework derived from data assimilation and are applied on noisy and incomplete pressure difference observations derived from satellite images. In the first model, dense pressure difference maps are reconstructed according to a shallow-water model on each cloud layer. While performing this reconstruction, the variational process estimates the average horizontal wind fields of the multi-layer model. The second model relies on a simplified vorticity-divergence form of the previous multi-layer shallow-water model. In this case, average horizontal motion fields are estimated for each layer without reconstructing pressure maps. While the simplified model is not as precise as the exact shallow-water model, the latter estimator exploits finer spatio-temporal image structures and succeeds in characterizing motion at smaller spatial scales. The performance of both methods is assessed on synthetic examples and on real world meteorological satellite image sequences.
-
Time-consistent estimators of 2D/3D motion of atmospheric layers from pressure images
2016Co-Authors: Patrick Heas, Nicolas Papadakis, Etienne MeminAbstract:In this paper, we face the challenging problem of estimation of time-consistent layer motion fields at various atmospheric depths. Based on a Vertical Decomposition of the atmosphere, we propose three different dense motion estimator relying on multi-layer dynamical models. In the first method, we propose a mass conservation model which constitutes the physical background of a multi-layer dense estimator. In the perspective of adapting motion analysis to atmospheric motion, we propose in this method a two-stage Decomposition estimation scheme. The second method proposed in this paper relying on a 3D physical model for a stack of interacting layers allows us to recover a Vertical motion information. In the last method, we use the exact shallow-water formulation of the Navier-Stokes equations to control the motion evolution across the sequence. This is done through a variational approach derived from data assimilation principle which combines the dynamical model and the pressure difference observations obtained from satellite images. The three methods use sparse pressure difference image observations derived from top of cloud images and classification maps. The proposed approaches are validated on synthetic example and applied to real world meteorological satellite image sequences.
-
IGARSS (2) - Variational Pressure Image Assimilation for Atmospheric Motion Estimation
IGARSS 2008 - 2008 IEEE International Geoscience and Remote Sensing Symposium, 2008Co-Authors: Thomas Corpetti, Patrick Heas, Etienne Memin, Nicolas PapadakisAbstract:The complexity of dynamical laws governing 3D atmospheric flows associated with incomplete and noisy observations make the recovery of atmospheric dynamics from satellite images sequences very difficult. In this paper, we face the challenging problem of estimating physical sound and time-consistent horizontal motion fields at various atmospheric depths for a whole image sequence. Based on a Vertical Decomposition of the atmosphere, we propose a dynamically consistent atmospheric motion estimator relying on a multi-layer dynamical model. This estimator is based on a weak constraint variational data assimilation scheme and is applied on noisy and incomplete pressure difference observations derived from satellite images. The dynamical model consists in a simplified vorticity-divergence form of a multi-layer shallow-water model. Average horizontal motion fields are estimated for each layer. The performance of the proposed technique is assessed on real world meteorological satellite image sequences.
-
Three-Dimensional Motion Estimation of Atmospheric Layers From Image Sequences
IEEE Transactions on Geoscience and Remote Sensing, 2008Co-Authors: Patrick Heas, Etienne MeminAbstract:In this paper, we address the problem of estimating three-dimensional motions of a stratified atmosphere from satellite image sequences. The analysis of three-dimensional atmospheric fluid flows associated with incomplete observation of atmospheric layers due to the sparsity of cloud systems is very difficult. This makes the estimation of dense atmospheric motion field from satellite images sequences very difficult. The recovery of the Vertical component of fluid motion from a monocular sequence of image observations is a very challenging problem for which no solution exists in the literature. Based on a physically sound Vertical Decomposition of the atmosphere into cloud layers of different altitudes, we propose here a dense motion estimator dedicated to the extraction of three-dimensional wind fields characterizing the dynamics of a layered atmosphere. Wind estimation is performed over the complete three-dimensional space using a multi-layer model describing a stack of dynamic horizontal layers of evolving thickness, interacting at their boundaries via Vertical winds. The efficiency of our approach is demonstrated on synthetic and real sequences.
Vladlen Koltun - One of the best experts on this subject based on the ideXlab platform.
-
Almost tight upper bounds for Vertical Decompositions in four dimensions
Journal of the ACM, 2004Co-Authors: Vladlen KoltunAbstract:We show that the complexity of the Vertical Decomposition of an arrangement of n fixed-degree algebraic surfaces or surface patches in four dimensions is O(n4+e), for any e > 0. This improves the best previously known upper bound for this problem by a near-linear factor, and settles a major problem in the theory of arrangements of surfaces, open since 1989. The new bound can be extended to higher dimensions, yielding the bound O(n2d−4+e), for any e > 0, on the complexity of Vertical Decompositions in dimensions d ≥ 4. We also describe the immediate algorithmic applications of these results, which include improved algorithms for point location, range searching, ray shooting, robot motion planning, and some geometric optimization problems.
-
Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions
Discrete and Computational Geometry, 2004Co-Authors: Vladlen KoltunAbstract:We prove tight and near-tight combinatorial complexity bounds for Vertical Decompositions of arrangements of hyperplanes and 3-simplices in four dimensions. In particular, we prove a tight upper bound of Θ(n4) for the Vertical Decomposition of an arrangement of n hyperplanes in four dimensions, improving the best previously known bound [8] by a logarithmic factor. We also show that the complexity of the Vertical Decomposition of an arrangement of n 3-simplices in four dimensions is O(n4 α (n) log2 n), where α (n) is the inverse Ackermann function, improving the best previously known bound [2] by a near-linear factor.
-
Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions
Discrete & Computational Geometry, 2004Co-Authors: Vladlen KoltunAbstract:We prove tight and near-tight combinatorial complexity bounds for Vertical Decompositions of arrangements of hyperplanes and 3-simplices in four dimensions. In particular, we prove a tight upper bound of Θ(n^4) for the Vertical Decomposition of an arrangement of n hyperplanes in four dimensions, improving the best previously known bound [8] by a logarithmic factor. We also show that the complexity of the Vertical Decomposition of an arrangement of n 3-simplices in four dimensions is O(n^4 α (n) log^2 n), where α (n) is the inverse Ackermann function, improving the best previously known bound [2] by a near-linear factor.
-
FOCS - Almost tight upper bounds for Vertical Decompositions in four dimensions
Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 2001Co-Authors: Vladlen KoltunAbstract:We show that the complexity of the Vertical Decomposition of an arrangement of n fixed-degree algebraic surfaces or surface patches in four dimensions is O(n/sup 4+/spl epsi//) for any /spl epsi/ > 0. This improves the best previously known upper bound for this problem by a near-linear factor, and settles a major problem in the theory of arrangements of surfaces, open since 1989. The new bound can be extended to higher dimensions, yielding the bound O (n/sup 2d-4+/spl epsi//), for any /spl epsi/ > 0, on the complexity of Vertical Decompositions in dimensions d /spl ges/ 4. We also describe the immediate algorithmic applications of these results, which include improved algorithms for point location, range searching, ray shooting, robot motion planning, and some geometric optimization problems.
-
WADS - Complexity Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions
Lecture Notes in Computer Science, 2001Co-Authors: Vladlen KoltunAbstract:We prove tight and near-tight combinatorial complexity bounds for Vertical Decompositions of arrangements of linear surfaces in four dimensions. In particular, we prove a tight upper bound of Θ(n4) for the Vertical Decomposition of an arrangement of n hyperplanes in four dimensions, improving the best previously known bound [7] by a logarithmic factor. We also show that the complexity of the Vertical Decomposition of an arrangement of n 3-simplices in four dimensions is O(n4α(n) log n), improving the best previously known bound [3] by a near-linear factor. We believe that the techniques used for obtaining these results can also be extended to analyze Decompositions of arrangements of fixed-degree algebraic surfaces (or surface patches) in four dimensions.
Patrick Heas - One of the best experts on this subject based on the ideXlab platform.
-
Image assimilation for motion estimation of atmospheric layers with shallow-water model
2016Co-Authors: Nicolas Papadakis, Patrick Heas, Etienne MeminAbstract:The complexity of dynamical laws governing 3D atmospheric flows associated to incomplete and noisy observations makes very difficult the recovery of atmospheric dynamics from satellite images sequences. In this paper, we face the challenging problem of joint estimation of time-consistent horizontal motion fields and pressure maps at various atmospheric depths. Based on a Vertical Decomposition of the atmosphere, we propose a dense motion estimator relying on a multi-layer dynamical model. Noisy and incomplete pressure maps obtained from satellite images are reconstructed according to shallow-water model on each cloud layer using a framework derived from data assimilation. While reconstructing dense pressure maps, this variational process estimates time-consistent horizontal motion fields related to the multi-layer model. The proposed approach is validated on a synthetic example and applied to a real world meteorological satellite image sequence.
-
Pressure image assimilation for atmospheric motion estimation
2016Co-Authors: Thomas Corpetti, Patrick Heas, Etienne Memin, Nicolas PapadakisAbstract:The complexity of dynamical laws governing 3D atmospheric flows associated with incomplete and noisy observations makes the recovery of atmospheric dynamics from satellite images sequences very difficult. In this report, we face the challenging problem of estimating physical sound and time consistent horizontal motion fields at various atmospheric depths for a whole image sequence. Based on a Vertical Decomposition of the atmosphere, we propose two dynamically consistent atmospheric motion estimators relying on different multi-layer dynamical models. Both estimators use a framework derived from data assimilation and are applied on noisy and incomplete pressure difference observations derived from satellite images. In the first model, dense pressure difference maps are reconstructed according to a shallow-water model on each cloud layer. While performing this reconstruction, the variational process estimates the average horizontal wind fields of the multi-layer model. The second model relies on a simplified vorticity-divergence form of the previous multi-layer shallow-water model. In this case, average horizontal motion fields are estimated for each layer without reconstructing pressure maps. While the simplified model is not as precise as the exact shallow-water model, the latter estimator exploits finer spatio-temporal image structures and succeeds in characterizing motion at smaller spatial scales. The performance of both methods is assessed on synthetic examples and on real world meteorological satellite image sequences.
-
Time-consistent estimators of 2D/3D motion of atmospheric layers from pressure images
2016Co-Authors: Patrick Heas, Nicolas Papadakis, Etienne MeminAbstract:In this paper, we face the challenging problem of estimation of time-consistent layer motion fields at various atmospheric depths. Based on a Vertical Decomposition of the atmosphere, we propose three different dense motion estimator relying on multi-layer dynamical models. In the first method, we propose a mass conservation model which constitutes the physical background of a multi-layer dense estimator. In the perspective of adapting motion analysis to atmospheric motion, we propose in this method a two-stage Decomposition estimation scheme. The second method proposed in this paper relying on a 3D physical model for a stack of interacting layers allows us to recover a Vertical motion information. In the last method, we use the exact shallow-water formulation of the Navier-Stokes equations to control the motion evolution across the sequence. This is done through a variational approach derived from data assimilation principle which combines the dynamical model and the pressure difference observations obtained from satellite images. The three methods use sparse pressure difference image observations derived from top of cloud images and classification maps. The proposed approaches are validated on synthetic example and applied to real world meteorological satellite image sequences.
-
IGARSS (2) - Variational Pressure Image Assimilation for Atmospheric Motion Estimation
IGARSS 2008 - 2008 IEEE International Geoscience and Remote Sensing Symposium, 2008Co-Authors: Thomas Corpetti, Patrick Heas, Etienne Memin, Nicolas PapadakisAbstract:The complexity of dynamical laws governing 3D atmospheric flows associated with incomplete and noisy observations make the recovery of atmospheric dynamics from satellite images sequences very difficult. In this paper, we face the challenging problem of estimating physical sound and time-consistent horizontal motion fields at various atmospheric depths for a whole image sequence. Based on a Vertical Decomposition of the atmosphere, we propose a dynamically consistent atmospheric motion estimator relying on a multi-layer dynamical model. This estimator is based on a weak constraint variational data assimilation scheme and is applied on noisy and incomplete pressure difference observations derived from satellite images. The dynamical model consists in a simplified vorticity-divergence form of a multi-layer shallow-water model. Average horizontal motion fields are estimated for each layer. The performance of the proposed technique is assessed on real world meteorological satellite image sequences.
-
Three-Dimensional Motion Estimation of Atmospheric Layers From Image Sequences
IEEE Transactions on Geoscience and Remote Sensing, 2008Co-Authors: Patrick Heas, Etienne MeminAbstract:In this paper, we address the problem of estimating three-dimensional motions of a stratified atmosphere from satellite image sequences. The analysis of three-dimensional atmospheric fluid flows associated with incomplete observation of atmospheric layers due to the sparsity of cloud systems is very difficult. This makes the estimation of dense atmospheric motion field from satellite images sequences very difficult. The recovery of the Vertical component of fluid motion from a monocular sequence of image observations is a very challenging problem for which no solution exists in the literature. Based on a physically sound Vertical Decomposition of the atmosphere into cloud layers of different altitudes, we propose here a dense motion estimator dedicated to the extraction of three-dimensional wind fields characterizing the dynamics of a layered atmosphere. Wind estimation is performed over the complete three-dimensional space using a multi-layer model describing a stack of dynamic horizontal layers of evolving thickness, interacting at their boundaries via Vertical winds. The efficiency of our approach is demonstrated on synthetic and real sequences.