Optimal quadtrees for image segments

Quadtrees are compact hierarchical representations of images. In this paper, we define the efficiency of quadtrees in representing image segments and derive the relationship between the size of the enclosing rectangle of an image segment and its optimal quadtree. We show that if an image segment has an enclosing rectangle having sides of lengths x and y, such that 2N-1 × max (x, y) ? 2N, then the optimal quadtree may be the one representing an image of size 2N × 2N or 2N+1 × 2N+1. It is shown that in some situations the quadtree corresponding to the larger image has fewer nodes. Also, some necessary conditions are derived to identify segments for which the larger image size results in a quadtree which is no more expensive than the quadtree for the smaller image size.     

Linear-time border-tracing algorithms for quadtrees

In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.     

Linear quadtrees: A blocking technique for contour filling

Given a linear quadtree forming a region's contour, an algorithm is presented to determine all the pixels 4-connected to the border's elements. The procedure, based on a connectivity technique, associates a two-valued state (“blocked” or “unblocked”) with each node and fills increasingly larger quadrants with black nodes whose state is known to be unblocked. Advantages of the proposed procedure over existing ones are: (i) multiply connected regions can be reconstructed; (ii) the border can be given as a set of either 4- or 8-connected pixels.     

Boundary matching algorithm for connected component labelling using linear quadtrees

A computationally fast top-down recursive algorithm for connected component labelling using linear quadtrees is presented. The input data structure used is a linear quadtree representing only black leaf nodes. The boundary matching approach used ensures that at most two adjacencies of any black leaf node are considered. Neighbour searching is carried out within restricted subsets of the input quadtree. The time and space complexities of the algorithm are O(Bn) and O(B) respectively for a linear quadtree with B black leaves constructed from a binary array of size 2ⁿ × 2ⁿ. Simulations show the algorithm to be twice as fast as an existing algorithm that uses an identical input data structure. The top-down algorithm presented can also be used to efficiently generate a linear quadtree representing all nodes — ‘grey’, ‘black’ and ‘white’ — in preorder when given an input linear quadtree representing only ‘black’ leaf nodes. The boundary matching algorithm is computationally fast and has low static and dynamic storage costs, making it useful for applications where linear quadtrees are held in main memory.     

A minimization method for boolean functions

Algorithms are proposed for constructing one and all prime implicants covering a given point, a DNF consisting of prime implicants, and a reduced DNF. The complexity of the proposed algorithms is investigated.Translted from Kibernetika, No. 5, pp. 44–48, September–October, 1989.     

Attribute-based key-insulated signature for boolean formula

In order to minimize the impact of secret signing key exposure in attribute-based signature scenario, we construct an attribute-based key-insulated signature (ABKIS) scheme for expressive monotone boolean function access structures utilizing only four pairing operations in verification process and making the signature length constant, that is, the number of pairings required for signature verification and the size of signature are independent of the size of attribute set participated in the respective process. The (strong) key-insulated selective security of our ABKIS scheme is reduced to the computational Diffie–Hellman Exponent problem without using any random oracles. The proposed construction attains signer privacy, which is a fundamental requirement of the signature schemes in the attribute-based setting.     

MOSAIC: Declarative platform for dynamic overlay composition

Overlay networks create new networking services using nodes that communicate using pre-existing networks. They are often optimized for specific applications and targeted at niche vertical domains, but lack interoperability with which their functionalities can be shared. Mosaic is a declarative platform for constructing new overlay networks from multiple existing overlays, each possessing a subset of the desired new network’s characteristics.This paper focuses on the design and implementation of Mosaic: composition and deployment of control and/or data plane functions of different overlay networks, dynamic compositions of overlay networks to meet changing application needs and network conditions, and seamless support for legacy applications. Mosaic overlays are specified using Mozlog, a new declarative language for expressing overlay properties independently from their particular implementation or underlying network.Mosaic is validated experimentally using compositions specified in Mozlog in order to create new overlay networks with compositions of their functions: the i3 indirection overlay that supports mobility, the resilient overlay network (RON) overlay for robust routing, and the Chord distributed hash table for scalable lookups. Mosaic uses runtime composition to simultaneously deliver application-aware mobility, NAT traversal and reliability. We further demonstrate Mosaic’s dynamic composition capabilities by Chord switching its underlay from IP to RON at runtime.Mosaic’s benefits are obtained at a low performance cost, as demonstrated by measurements on both a local cluster environment and the PlanetLab global testbed.     

Chams: Churn-aware overlay construction for media streaming

Overlay networks support a wide range of peer-to-peer media streaming applications on the Internet. The user experience of such applications is affected by the churn resilience of the system. When peers disconnect from the system, streamed data may be delayed or lost due to missing links in the overlay topology. In this paper, we explore a proactive strategy to create churn-aware overlay networks that reduce the potential of disruptions caused by churn events. We describe Chams, a middleware for constructing overlay networks that mitigates the impact of churn. Chams uses a ??hybrid?? approach??it implicitly defines an overlay topology using a gossip-style mechanism, while taking the reliability of peers into account. Unlike systems for overlay construction, Chams supports a variety of topologies used in media streaming systems, such as trees, multi-trees and forests. We evaluate Chams with different topologies and show that it reduces the impact of churn, while imposing only low computational and message overheads.     

A model for the analysis of neighbor finding in pointer-based quadtrees

A natural byproduct of the tree-like nature of the quadtree is that many basic image processing operations can be implemented as tree traversals which differ in the nature of the computation that is performed at each node. Some of these computations involve the inspection of a node's adjacent neighbors (termed neighbor finding). A new model is developed for images represented by quadtrees, and it is used to analyze various neighbor-finding techniques. The model's predicted costs for neighbor finding correlate very closely with empirical results and it is superior to the model that was used previously.     

Algorithm for converting a forest of quadtrees to a binary array

An algorithm for reconstructing a binary array of size N sx N from its forest of quadtree representation is presented. The algorithm traverses each tree of the forest in preorder and maps each ‘black’ node into the spatial domain. The time complexity in mapping is O(log N × B_n + B_p), where B_n is the number of black nodes in the forest and B_p is the number of black pixels in the N × N array. The algorithm has been implemented on an Apple II.     

基于限制性四叉树LOD大规模地形预处理算法

LOD（Level Of Detail,层次细节）技术是解决大规模地形实时渲染的关键技术之一,通过这种技术可以较好地简化场景的复杂度,减少图形显示的失真度,满足一定的实时性要求。传统的算法将四叉树和LOD技术相结合将大规模数字高程模型数据（DEM）进行分块,并对块内数据按照分辨率的大小分层存储。通过对四叉树的研究,在限制性四叉树的基础上引入预处理算法,提高了地形读取速度,增强了实时显示效果。该算法是基于限制性四叉树的一种高效的规则网格划分方法,内存开销少,降低了CPU的负担。实验结果表明该算法提高了地形导入的效率,能实现大规模地形的实时漫游。     

线性四叉树描述的二值图像八邻域内邻居寻找算法

通过研究线性四叉树描述的二值图像位置码属性,提出了图像块八邻域内相邻的判别条件,在此基础上给出了相应的图像块八邻域内邻居寻找算法。该算法利用四分块子图像之间的位置,通过对图像块的位置码码元进行比较寻找图像块的邻居,因此计算量较少,便于计算机实现。     

Linear strategy for boolean ring based theorem proving

Two inference rules are discussed in boolean ring based theorem proving,and linear strategy is developed.It is shown that both of them are complete for linear strategy,Moreover,by introducing a partial ordering on atoms,pseudo O-linear and O-linear strategies are presented.The former is complete,the latter,however,is complete for clausal theorem proving.     

Replaceability and computational equivalence for monotone boolean functions

Summary Replacement rules have played an important role in the study of monotone boolean function complexity. In this paper, notions of replaceability and computational equivalence are formulated in an abstract algebraic setting, and examined in detail for finite distributive lattices — the appropriate algebraic context for monotone boolean functions. It is shown that when computing an element f of a finite distributive lattice D, the elements of D partition into classes of computationally equivalent elements, and define a quotient of D in which all intervals of the form [t f, t f] are boolean. This quotient is an abstract simplicial complex with respect to ordering by replaceability. Other results include generalisations and extensions of known theorems concerning replacement rules for monotone boolean networks. Possible applications of computational equivalence in developing upper and lower bounds on monotone boolean function complexity are indicated, and new directions of research both abstract mathematical and computational, are suggested.     

Tree-assisted gossiping for overlay video distribution

Given its readily deployable nature and broad applications for digital entertainment, video streaming through overlay networks has received much attention recently. While a tree topology is often advocated due to its scalability, it suffers from discontinuous playback under highly dynamic network environments. For on-demand streaming, the asynchronicity among client requests further aggravates the problem. On the other hand, gossip protocols using random message dissemination, though robust, fail to meet the real-time constraints for streaming applications. In this paper, we propose TAG, a Tree-Assisted Gossip protocol that addresses the above issues. TAG adopts a tree structure with time indexing to accommodate asynchronous requests, and an efficient pull-based gossip algorithm to mitigate the impact of network dynamicity. It seamlessly integrates these two approaches and realizes their best features, namely, low delay with a regular tree topology, and robust delivery with smart switching among multiple paths, thus making effective use of the available bandwidth in the network. We evaluate the performance of TAG under various settings, and the results demonstrate that it is quite robust in the presence of local and global bandwidth fluctuations. As compared to pure tree-based overlay VOD system, it achieves much lower and stable segment missing rates, even under highly dynamic network conditions.This research is supported by a Canadian NSERC Discovery Grant, an NSERC RTI Grant, a CFI New Oppurtunities Grant, and an SFU President's Research Grant.The author names are in alphabetical order.     

Multimodal Interaction for Information Access: Exploiting Cohesion

Multimodality is a powerful concept for dealing with dialogue cohesion in a human–computer natural language (NL)‐centered system. This work is a modest step toward more effective exploitation of the potentially large bandwidth of communication provided by this situation. The relations between exploration, navigation, and NL‐based communication are discussed in general and with reference to two prototypes. Light cognitive load feedback and direct manipulation are proposed so that user and system can cooperate in mutually establishing the structure of the ongoing dialogue. The main points are: (i) use of an appropriate dialogue structure to constrain inference in the anaphora resolution process; (ii) use of a graphical representation of the structure, to limit the problem of opacity; (iii) allowance for the possibility of direct manipulation on this representation, to avoid the necessity of operating linguistically at the metalevel. The context of the work is within NL‐centered multimodal information access systems, in which basic entities are pairs (most commonly question and answer). A dialogue model is provided by a modified version of the centering model; it is both sufficiently simple to be displayed in an intuitive fashion on the screen, and sufficiently powerful to give accurate results. An extension of the discourse model, oriented to the treatment of deixis, is also proposed. Finally, steps toward an overall approach to the integration of navigational and mediated aspects of interaction are discussed.