Image Data Structures:Virtual Quadtrees

By -
Virtual Quadtrees

The quadtree has become a major data structure in image processing. Though the quadtree has better storage efficiency compared to other data structures such as the array, it also has considerable storage overhead. Jones and Iyengar [10] have proposed two ways in which quadtrees may be efficiently stored: as “forest of quadtrees” and as “compact quadtrees”. They called these new data structures virtual quadtrees because the basic operations per- formed in quadtrees can also be performed on the new representations. The virtual quadtree is a space-efficient way of representing a quadtree. It is a structure that simulates quadtrees in such a way that we can,

1. Determine the color of any node in the quadtree.

image

2. Find the child node of any node, in any direction in the quadtree.

3. Find the parent node of any node in the quadtree.

The two types of virtual quadtrees, which we are going to discuss, are the compact quadtree and the forest of quadtrees.

Compact Quadtrees

The compact quadtree has all the information contained in a quadtree but needs less space. It is represented as C(T), where T is the quadtree it is associated with. Each set of four sibling nodes in the quadtree is represented as a single node called metanode in the corre- sponding compact quadtree.

The metanode M has four fields, which are explained as follows:

• MCOLOR(M, D) – The colors of the nodes included in M. Where D ∈ {NW,NE,SW,SE}.

• MSONS(M) – Points to the first metanode that represents offsprings of a node represented in M; NIL if no offspring exists.

• MFATHER(M) – Points to the metanode that holds the representation of the parent of the nodes that M represents.

• MCHAIN(M) – If there are more than one metanode that represent offspring of nodes represented by a given metanode M, then these are linked by MCHAIN field.

The compact quadtree for the quadtree shown in the Figure 57.6 is given in Figure 57.7.

image

In Figure 57.7 downward links are MSON links, horizontal links are MCHAIN links and upward links are MFATHER links.

The compact quadtree uses the same amount of space for the storage of color but it uses very less space for storage of pointers. In Figure 57.7, the compact quadtree has 10 metanodes, whereas the quadtree has 41 nodes. Thus it saves about 85 percent of the storage space. Since the number of nodes in a compact quadtree is less a simple recursive tree traversal can be done more efficiently.

Forest of Quadtrees (FQT)

Jones and Iyengar [8] proposed a variant of quadtrees called forest of quadtrees to improve the space efficiency of quadtrees. A forest of quadtrees is represented by F(T) where T is the quadtree it represents. A forest of quadtrees, F(T) that represents T consists of a table of triples of the form (L, K, P), and a collection of quadtrees where,

1. Each triple (L, K, P) consists of the coordinates, (L, K), of a node in T, and a pointer, P, to a quadtree that is identical to the subtree rooted at position (L, K) in T.

2. If (L, K) and (M, N) are coordinates of nodes recorded in F(T), then neither node is a descendant of the other.

3. Every black leaf in T is represented by a black leaf in F(T).

image

To obtain the corresponding forest of quadtrees, the nodes in a quadtree need to be classified as good and bad nodes. A leaf node with black color or an intermediate node that has two or more black child nodes are called good nodes, the rest are called bad nodes. Only the good nodes are stored in the forest of quadtrees thereby saving lot of storage space.

image

Figure 57.8 contains a forest of quadtrees that represents the quadtree shown in Figure 57.6. To reduce a quadtree to a forest of quadtrees, we first need to identify the good nodes and the bad nodes. We then break down the quadtree into smaller quadtrees in such a way that each of them has a good root node and none of them is a subtree of another and the bad nodes encountered by forest are freed. This collection of quadtrees is called as forest of quadtrees. The time required for the execution of the conversion is obviously linear in the number of nodes in the quadtree [10].

Theorem: The maximum number of trees in a forest of quadtrees derived from a quadtree that represents a square of dimension 2k x 2k is 4k−1, i.e., one-fourth the area of the square. For proof see [10].

The corresponding quadtree can be easily reconstructed from a forest of quadtrees F. The reconstructed quadtree R(F) consists of real nodes and virtual nodes (nodes corresponding to the bad nodes that are deleted while creating the forest). Since the virtual nodes require no storage they are located by giving their coordinates. The virtual nodes are represented as v(L, K).

image

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