Image Data Structures:Quadtrees and R-trees and Octrees

By -
Quadtrees and R-trees

Quadtrees and R-trees [3] are two commonly used spatial data structures to locate or organize objects in a given image. Both quadtrees and R-trees use bounding boxes to depict the outline of the objects. Therefore, the data structure only needs to keep track of the boundaries instead of the actual shape and size of the objects in the image. The size of the bounding boxes usually depends on the size of the object we are trying to locate.

The R-tree (see also Chapter 21) is a hierarchical, height balanced data structure, similar to the B+-tree that aggregates objects based on their spatial proximity. It is a multidimensional generalization of the B+-tree. The R-tree indexes multidimensional data objects by enclosing data objects in bounding rectangles, which may further be enclosed in bounding rectangles; these bounding rectangles can overlap each other. Each node except the leaf node has a pointer and the corresponding bounding rectangle. The pointer points to the subtree with all the objects enclosed in its corresponding rectangle. The leaf node has a bounding rectangle and the pointer pointing to the actual data object. The root node has a minimum of two children unless it is a leaf node and all the leaf nodes appear at the same level. Figure 57.9 Shows the R-tree representation of an image.

The main difference between quadtrees and R-trees is that unlike R-trees the bounding rectangle of quadtrees do not overlap. In real world objects overlap; in such cases more than

image

one node in a quadtree can point to the same object. This is a serious disadvantage for the quadtree. Figure 57.10 shows the quadtree representation of the image in Figure 57.9.

As you can see from the Figure 57.10 objects like ‘C’ and ‘D’ are represented by more than one node. This makes it difficult to find the origin of the quadtree.

The R-tree is a dynamic structure, so its contents can be modified without having to reconstruct the entire tree. It can be used to determine which objects intersect a given query region. The R-tree representation of an image is not unique; size and placement of rectangles in the tree depends on the sequence of insertions and deletions resulting in the tree starting from the empty R-tree.

Octrees

Octrees are 3D equivalent of quadtrees and are used for representing 3D images. An octree is formed by dividing a 3D space into 8 sub-cubes called cells. This process of dividing the cube into cells is carried on until the (image) objects lie entirely inside or outside the cells. The root node of an octree represents a cube, which encompasses the objects of interest.

In the octree each node except the leaf node has eight child nodes, which represent the sub-cubes of the parent node. The node stores information like pointer to the child nodes, pointer to the parent node, and pointers to the contents of the cube. An example of an

image

The Octree become very ineffective if the objects in the image that it is representing are not uniformly distributed, as in that case many nodes in the octree will not contain any objects. Such an octree is also very costly to compute as a large amount of data has to be examined.

Comments

Post a Comment

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

By -
Introduction Important advances in programming languages have occurred since the early days of assembly languages and op codes, and modern programming languages have significantly simplified the task of writing computer programs. Unfortunately, tools for un d e rstanding programs have not achieved the accompanying levels of improvement. Software developers still face difficulties in understanding, analyzing, debugging, and improving code. As an example of the difficulties still evident, consider a developer who has just implemented a new algorithm and is now ready to examine the program’s behavior. After issuing a command to begin program execution, the developer examines output data and/or inter- active behavior, attempting to ascertain if the program functioned correctly, and if not, the reasons for the program’s failure. This task can be laborious and usually requires the use of a debugger or perhaps even the addition of explicit checking code, usually through output statements. Furt
Read more

Collision Detection:Penetration Depth Computation

By -
Image
Penetration Depth Computation In this section, we give a brief overview of penetration depth (PD) computation algorithms between convex polytopes and general polyhedral models. The PD of two inter-penetrating objects A and B is defined as the minimum translation distance that one object undergoes to make the interiors of A and B disjoint. It can be also defined in terms of the TCSO. When two objects are overlapping, the origin of the Minkowski sum of A and − B is contained inside the TCSO. The penetration depth corresponds to the minimum distance from the origin to the surface of TCSO [18]. PD computation is often used in motion planning [37], contact resolution for dynamic simulation [38, 39] and force computation in haptic rendering [40]. For example, computation of dynamic response in penalty-based methods often needs to perform PD queries for imposing the non-penetration constraint for rigid body simulation. In addition, many applications, such as motion planning and dynamic simula
Read more

Concurrent Data Structures:Linked Lists

By -
Linked Lists Consider implementations of concurrent search structures supporting insert, delete, and search operations. If these operations deal only with a key value, then the resulting data structure is a se t ; if a data value is associated with each key, we have a dic tionary [24]. These are closely related data structures, and a concurrent set implementation can often be adapted to implement a dictionary. In the next three sections, we concentrate on implementing sets using different structures: linked lists, hash tables, and trees. Suppose we use a linked list to implement a set. Apart from globally locking the linked list to prevent concurrent manipulation, the most popular approach to concurrent lock- based linked lists is ha nd-over-hand locking (sometimes called l o c k coupling ) [14, 89]. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventin
Read more