22-01-2011, 06:13 PM
IN-PICTURE SEARCH ALGORITHM
B.Tech Seminar Report
by
Anand Babu N B
Department of Computer Science and Engineering
Government Engineering College, Thrissur
December 2010
B.Tech Seminar Report
by
Anand Babu N B
Department of Computer Science and Engineering
Government Engineering College, Thrissur
December 2010
[attachment=8376]
Abstract
In this advanced world researchers are more interested in searching for fragments that
are similar to a query, than a total data item that is similar to a query; the search
interest is for contains, not is. This paper presents an O(log n)algorithm, called the
generalized virtual node (GVN)algorithm. The GVN algorithm is a search algorithm
for data fragments that have similar contents to that of a query. Each image is
transformed into characteristic features and these features are stored in a hierarchical
multidimensional structure, called a k-tree. The experimental results of this in-picture
search algorithm on an image database demonstrate a search quality is qualitatively
and quantitatively acceptable, with a retrieval time faster than other algorithms, such
as brute-force and Partial Matching.
Chapter 1
Introduction
Image (multimedia) data query can be classified into two different approaches:
• a-whole-picture (a-wholeobject) search
• in-picture (in-object) search
Each approach generates a different type of query result. A-whole-picture or thumbnail-
based search approach searches for data that is globally similar to the query input; on
the other hand, an in-object search approach searches for a large piece of data contains
a fragment that is similar to the query. An example of a-whole-picture search is to
find a picture in a database using the picture or its thumbnail image as a query. An
example of in-picture search is to find a picture that contains parts that are similar
to the query, where the query is a part of an image regardless what the backgrounds
are. Most of the recent work in the field of multimedia retrieval emphasizes the a-
whole-object search approach ; only a few researchers are working on in-object search
approach .
Chapter 2
K-TREE INDEX STRUCTURE
A k-tree is a directed graph.Each node has 2k incoming edges and one outgoing edge
with a balanced structure.
The structure of the k-tree is feature independent.Therefore, the positions of the
nodes in the tree are always the same, no matters what features are. Figure 2.1 shows
the comparison between using k-tree and R-tree structures as indices by using two
different features. Compared to other feature-dependent index structure (illustrated
in Figure 2.2), using the k-tree approach to search every feature altogether takes
shorter computing time than using feature-dependent structure to search on many
indices individually, merge all results,and filter them with spatial constraints.
The generalized indexing/retrieval
model
The k-tree structure is used to retain location information and a histogram is used to
store the characteristics of each portion the data that corresponds to a part of the tree.
This generalized model is depicted in Figure 3. First, either general mathematical
models, or special methods extract the feature of interest. Second, the domain of
datatype is reduced into a set and each item in the database is also mapped to the
set. Third, virtual data values are added to data items, if necessary, to create such
that each item will generate a balanced k-tree. A k-tree is built using histogram values
for each feature.
