Tuesday, April 11, 2006 

Seminar report

here is my seminar report, images are missing as i used latex2html for it.
here is the link
http://www.cse.iitb.ac.in/~ajitb/seminar/

Thursday, April 06, 2006 

Types of queries

Now after defining these data structure our database is ready to answer fundamental queries like:
  • Whole Match Queries: Given a collection of N objects O1,.., On and aquery object Q find data objects that are within distance delta from Q
  • Sub-pattern Match: Given a collection of N objects O1,.., On and a query(sub-) object Q and a tolerance delta identify the parts of the data objects that match the query Q.
  • K- Nearest Neighbor queries: Given a collection of N objects O1,.., On and a query object Q find the K most similar data objects to Q.
  • All pairs queries (or ”spatial joins”): Given a collection of N objects O1 ,.., On find all objects that are within distance delta from each other.
for solving such queries we first need to find a distance function between two objects and find one or more numerical feature-extraction functions (to provide a quick test). Then Use a SAM (e.g., R-tree) to store and retrieve k-d feature vectors. here is an example of queries in context to computer games which uses these data structures :
  • Visibility - What can I see?
  • Ray intersections - What did the player just shoot?
  • Collision detection - Did the player just hit a wall?
  • Proximity queries - Where is the nearest power-up?

 

Why are apatial access methods important

The main purpose is to is to support efficient spatial selection, for example range queries or nearest neighbour queries of spatial objects. Without a spatial index,every object in database need to be checked whether it meets selection criterion,i.e complete linear scan of relational database.
Clustering is needed to group those objects which are often requested together. Otherwise, many different disk pages will have to be fetched, resulting in slow response. For spatial selecting the clustering implies storing objects which are close together in reality also close together in the computer memory (instead of scattered over the whole memory).
In traditional database systems sorting (or ordering) the data is the basis for efficient searching. Higher dimensional data can not be sorted in an obvious manner, as it is possible for text strings, numbers, or dates (one-dimensional data). Basically, computer memory is one-dimensional. However, spatial data is 2D, 3D (or even higher) and must be organized somehow in the memory. An intuitive solution to organize the data is using a regular grid just as on a paper map. Each grid cell has a unique name; e.g. ’A3’, ’C6’, or ’D5’. The cells are stored in some order in the memory and can each contain a (fixed) number of object references. In a grid
cell, a reference is stored to an object whenever the object (partially) overlaps the cell. However, this will not be very efficient due to the irregular data distribution of spatial data: many cells will be empty, e.g. in the ocean, while many other cells will be overfull, e.g. in the city center. Therefore, more advanced techniques have been developed.

 

Representing image through quadtree

Let’s say we divide the picture area into 4 sections. Those 4 sections are then further divided into 4 subsections. We continue this process, repeatedly dividing a square region by 4. We must impose a limit to the levels of division otherwise we could go on dividing the picture forever. Generally, this limit is imposed due to storage considerations or to limit processing time or due to the resolution of the output device. A pixel is the smallest subsection of the quad tree.
To summarize, a square or quadrant in the picture is either :
  1. entirely one color
  2. composed of 4 smaller sub-squares
To represent a picture using a quad tree, each leaf must represent a uniform area of the picture. If the picture is black and white, we only need one bit to represent the colour in each leaf; for example, 0 could mean black and 1 could mean white.

Now consider the following image :
The definition of a picture is a two-dimensional array, where the elements of the array are colored points .

Given Image in pixel form In Quad tree-form


Now when this image is represneted as quad tree it will look like :
The quad tree of the above example picture. The quadrants are shown
in counterclockwise order from the top-right quadrant. The root is the top node.
(The 2nd and 3rd quadrants are not shown.)


For matching procedure, color structure descriptor is first extracted from sample image and then matched with the descriptors associated to the images contained in the DB. Now here we can have a result image in certain range of tolerance according to two criterion : Quadtree Structure Similarity (QSS) and Quadtree Color Similarity(QCS). The main concept is that the difference in the structure of two quadtrees can be evaluated through the number of changes in the structure that need to be performed to make one of the quadtrees equivalent to the other. This process is called quadtree warping. Once the two quadtrees have the same structure, they are recursively navigated and the difference is computed between the colors of
the corresponding leaves. The final formula used for the similarity matching(SM) is the following:
SM = A1*QSS + A2*QCS
where the constants A1 and A2 are determined empirically for normalization and
weighting of the two metrics.