Modeling the motion that occurs between frames of a video sequence is a key component of video coding applications. Typically it is not possible to represent the motion between frames by a single model and therefore a quad-tree structure is employed where smaller, variable size regions or blocks are allowed to take on separate motion models. Quad-tree structures however suffer from two fundamental forms of redundancy. First, quad-trees exhibit structural redundancy due to their inability to exploit the dependence between neighboring leaf nodes with different parents. The second form of redundancy is due to the quad-tree structure itself being limited to capture only horizontal and vertical edge discontinuities at dyadically related locations; this means that general discontinuities in the motion field, such as those caused by boundaries of moving objects, become difficult and expensive to model. In our work, we address the issue of structural redundancy by introducing leaf merging. We describe how the intuitively appealing leaf merging step can be incorporated into quad-tree motion representations for a range motion modeling contexts. In particular, the impact of rate-distortion (R-D) optimized merging for two motion coding schemes, these being spatially predictive coding, as used by H.264, and hierarchical coding, are considered. Our experimental results demonstrate that the merging step can provide significant gains in R-D performance for both the hierarchical and spatial prediction schemes. Hierarchical coding has the advantage that it offers scalable access to the motion information; however due to the redundancy it introduces hierarchical coding has not been traditionally pursued. Our work shows that much of this redundancy can be mitigated with the introduction of merging. To enable scalable decoding, we employ a merging scheme which ensures that the dependencies introduced via merging can be hierarchically decoded. Theoretical investigations confirm the inherent advantages of leaf merging for quad-tree motion models. To enable quad-tree structures to better model motion discontinuity boundaries, we introduce geometry information to the quad-tree representation. We choose to model motion and geometry using separate quad-tree structures; thereby enabling each attribute to be refined separately. We extend the leaf merging paradigm to incorporate the dual tree structure allowing regions to be formed that have both motion and geometry attributes, subject to rate-distortion optimization considerations. We employ hierarchical coding for the motion and geometry information and ensure that the merging process retains the property of resolution scalability. Experimental results show that the R-D performance of the merged dual tree representation, is significantly better than conventional motion modeling schemes. Theoretical investigations show that if both motion and boundary geometry can be perfectly modeled, then the merged dual tree representation is able to achieve optimal R-D performance. We explore resolution scalability of merged quad-tree representations. We consider a modified Lagrangian cost function that takes into account the possibility of scalable decoding. Experimental results reveal that the new cost objective can considerably improve scalability performance without significant loss in overall efficiency and with competitive performance at all resolutions.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19111号 / 情博第557号 / 新制||情||98(附属図書館) / 32062 / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 松山 隆司, 教授 美濃 導彦, 准教授 梁 雪峰 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Every entity in the real world can be described uniquely by it’s attributes. It is possible to rank similar entities based on these attributes, i.e. a professor can be ranked by his/her number of publications, citations etc. A community is formed by a group of connected entities. Individual ranking of an entity plays an important role in the quality of a community. Skyline community in a network represents the highest ranked communities in the network. But how do we define this ranking? Ranking system in some model considers only a single attribute [16], whereas the other [15] [23] considers multiple attributes. Intuitively multiple attributes represent a community better and produce good results. We propose a novel community discovery model, which considers multiple attribute when ranking the community and is efficient in terms of computation time and result size. We use a progressive (can produce re- sults gradually without depending on the future processing) algorithm to calculate the community in an order such that a community is guaranteed not to be dominated by those generated after it. And to verify the dominance relationship between two communities, we came up with a range based comparison where the dominance rela- tionship is decided by the set of nodes each group dominates. If domination list of a group is a subset of another group, we say the second group dominates the first. Because a groups domination list contains it’s member along with the nodes they dominate. So in the example, the second group dominates every node of the first group. / Graduate

No description available.

No description available.

The environment is made up of composition of small particles. Hence, particle simulation is an important tool in many scientific and engineering research fields to simulate the real life processes of the environment. Because of the enormous amount of data in such simulations, data management, storage and processing are very challenging tasks. Spatial Distance Histogram (SDH) is one of the most popular queries being used in this field. In this thesis, we are interested in investigating the performance of improvement of an existing algorithm for computing SDH. The algorithm already being used is using a conceptual data structure called density map which is implemented via a quad tree index. An algorithm having density maps implemented via binary tree is proposed in this thesis. After carrying out many experiments and analysis of the data, we figure out that although the binary tree approach seems efficient in earlier stage, it is same as the quad tree approach in terms of time complexity. However, it provides an improvement in computing time by a constant factor for some data inputs. The second part of this thesis is dedicated to an approach that can potentially reduce the computational time to a great extent by taking advantage of regions where data points are uniformly distributed.

Particle simulation has become an important research technique in many scientific and engineering fields in latest years. However, these simulations will generate countless data, and database they required would therefore deal with very challenging tasks in terms of data management, storage, and query processing. The two-body correlation function (2-BCFs), a statistical learning measurement to evaluate the datasets, has been mainly utilized to measure the spatial distance histogram (SDH). By using a straightforward method, the process of SDH query takes quadratic time. Recently, a novel algorithm has been proposed to compute the SDH based on the concept of density map (DM), and it reduces the running time to ϴ(N(3/2)) for two-dimensional data and ϴ (N(5/3) ) for three-dimensional data, respectively. In the DM-SDH algorithm, there are two types of DMs that can be plugged in for computation: Quad-tree (Oct-tree for three-dimensional data) and k-d tree data structure. In this thesis paper, by using the geometric method, we prove the unre- solvable ratios on the k-d tree. Further, we analyze and compare the difference in the performance in each potential case generated by these DM-SDH algorithms. Experimental results confirm our analysis and show that the k-d tree structure has better performance in terms of time complexity in all cases. However, our qualitative analysis shows that the Quad-tree (Oct-tree) has an advantage over the k-d tree on aspect of space complexity.

This diploma thesis defines the term indexing and in preamble are discussed known indexing algorithms and difference between indexing static and moving objects. The practical part of this diploma thesis is aimed to designing and implementing of indexing algorithm for open source application MaNGOS with respect to generic design pattern and effectiveness of spatial search queries for selection of the objects given properties in the specified area. At the end I present and discuss reached results.

This work is aimed for proposing acceptable indexing of moving objects. With the enlargement of mobile computing it is needed to manage large sets of spatiotemporal data. We introduce the problem of spatiotemporal data and basic general approaches of indexing these data. Further, we show support of spatial data in Oracle. The movement is typically represented as trajectory in two dimensional space with temporal component in third dimension. The thesis contains experiments performed in database Oracle on artificially generate data.

Les moyens mis en œuvre pour surveiller la surface de la Terre, notamment les zones urbaines, en cas de catastrophes naturelles telles que les inondations ou les tremblements de terre, et pour évaluer l’impact de ces événements, jouent un rôle primordial du point de vue sociétal, économique et humain. Dans ce cadre, des méthodes de classification précises et efficaces sont des outils particulièrement importants pour aider à l’évaluation rapide et fiable des changements au sol et des dommages provoqués. Étant données l’énorme quantité et la variété des données Haute Résolution (HR) disponibles grâce aux missions satellitaires de dernière génération et de différents types, telles que Pléiades, COSMO-SkyMed ou RadarSat-2 la principale difficulté est de trouver un classifieur qui puisse prendre en compte des données multi-bande, multi-résolution, multi-date et éventuellement multi-capteur tout en gardant un temps de calcul acceptable. Les approches de classification multi-date/multi-capteur et multi-résolution sont fondées sur une modélisation statistique explicite. En fait, le modèle développé consiste en un classifieur bayésien supervisé qui combine un modèle statistique conditionnel par classe intégrant des informations pixel par pixel à la même résolution et un champ de Markov hiérarchique fusionnant l’information spatio-temporelle et multi-résolution, en se basant sur le critère des Modes Marginales a Posteriori (MPM en anglais), qui vise à affecter à chaque pixel l’étiquette optimale en maximisant récursivement la probabilité marginale a posteriori, étant donné l’ensemble des observations multi-temporelles ou multi-capteur / The capabilities to monitor the Earth's surface, notably in urban and built-up areas, for example in the framework of the protection from environmental disasters such as floods or earthquakes, play important roles in multiple social, economic, and human viewpoints. In this framework, accurate and time-efficient classification methods are important tools required to support the rapid and reliable assessment of ground changes and damages induced by a disaster, in particular when an extensive area has been affected. Given the substantial amount and variety of data available currently from last generation very-high resolution (VHR) satellite missions such as Pléiades, COSMO-SkyMed, or RadarSat-2, the main methodological difficulty is to develop classifiers that are powerful and flexible enough to utilize the benefits of multiband, multiresolution, multi-date, and possibly multi-sensor input imagery. With the proposed approaches, multi-date/multi-sensor and multi-resolution fusion are based on explicit statistical modeling. The method combines a joint statistical model of multi-sensor and multi-temporal images through hierarchical Markov random field (MRF) modeling, leading to statistical supervised classification approaches. We have developed novel hierarchical Markov random field models, based on the marginal posterior modes (MPM) criterion, that support information extraction from multi-temporal and/or multi-sensor information and allow the joint supervised classification of multiple images taken over the same area at different times, from different sensors, and/or at different spatial resolutions. The developed methods have been experimentally validated with complex optical multispectral (Pléiades), X-band SAR (COSMO-Skymed), and C-band SAR (RadarSat-2) imagery taken from the Haiti site