http:^^www.tc.cornell.edu^visualization^education^cs718^fall1995^landis^index.html

This data set contains WWW-pages collected from computer science departments of various universities

<h3> <a name="Analysis Manager">Analysis Manager</a> </h3>

The Analysis Manager, <!WA139><!WA139><!WA139><!WA139><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/analmgr.h">analmgr.h</A> performs
analysis on images as they are added to the system. The result is a set of feature
vectors, one for each type of query class. The greatest
change in a CBIR system is likely to be the addition of new query
classes. The Analysis Manager provides extensibility via registration of
feature extractors which generate feature vectors. The class relationships are shown
in the following class diagram.
<br>
<p align=center>
<!WA140><!WA140><!WA140><!WA140><img src="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/analmgr.jpg">
</p>

When a user adds a new image to the system, the user interface calls the 
<tt>analyze()</tt> member function. This function uses the <b>StorageManager</b>
to create a new <b>Image</b> which it then analyzes by calling <tt>extract()</tt>
on each installed
feature extractor. New feature extractor objects are added by calling
<tt>addFeature()</tt> when the system is initialized.
<p>  
The <b>FeatureExtractor</b> abstract class provides an interface definition to be
used by all feature extractors (<!WA141><!WA141><!WA141><!WA141><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/features.h">features.h</A>).
Concrete feature extractor classes inherit the interface
and provide implementations appropriate for the needs of the feature vectors they
generate. A feature extractor object is responsible for analyzing the image, creating
a <b>FeatureVector</b>, and installing the <b>FeatureVector</b> in the <b>Feature</b>
object of the <b>Image</b>.
<p>
The <b>FeatureExtractor</b> classes play an important role: they encapsulate all 
important information for a particular query class. When adding a new query class,
most of the effort is in creating a new subclass of <b>FeatureExtractor</b>. Other
classes can get query class specific information 
from feature extractors. For example, the <b>QueryManager</b> calls the
<tt>similarityFunc()</tt> when comparing two images.
<p>
The <b>AnalysisManager</b>, feature extractors, <b>Features</b>, and
the <b>FeatureVector</b> have an important relationship. At initialization
time, all the feature extractors are installed into the singleton instance of
the <b>AnalysisManager</b> (<!WA142><!WA142><!WA142><!WA142><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/init.cpp">init.cpp</A>). The <b>AnalysisManager</b>
tells each feature extractor its position in the set of feature vectors stored in
the <b>Features</b> objects. It also tells the <b>Features</b> class how many 
feature vectors every <b>Features</b> object must be capable of storing.
Every feature extractor implementation knows how large to make the
data portion of its <b>FeatureVector</b>. By encapsulating knowledge in this fashion,
new features can easily be added. 

<h3> <a name="Query Manager">Query Manager</a> </h3>

The <b>QueryManager</b> class provides two important functions: the ability to query
the database, and the ability to maintain a query history
(<!WA143><!WA143><!WA143><!WA143><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/querymgr.h">querymgr.h</A>). The Query Manager accepts a <b>Features</b> 
object and a <tt>similarityFunc()</tt> from the User Interface and formulates a 
query. The formulated query is used to retrieve similar images
from the Storage Manager. A client requests an initialized
<b>Features</b> object from the <b>AnalysisManager</b>, (which knows the position
and size information for every feature), and fills it in with the information to be
matched in the query. The client gets the <tt>similarityFunc</tt> from the feature
extractor class defined for the query class. 
<p>
Similarity functions are static member functions of the derived feature extractor class.
This is necessary when passing a member function pointer as a function argument.
They accept two <b>Features</b> objects and compute a distance between them.  
Similarity functions must return a non-negative value representing the
distance between the feature vectors. The function can also optionally return a
value less than zero if the two feature vectors
are dissimilar. The <b>QueryManager</b> uses the return value to rank
images by distance. After the <b>QueryManager</b> completes the processing of a query, it passes the
ranked list of images to the <b>DisplayManager</b> for presentation.   
<p>
The current implementation contains similarity functions that only operate upon a 
single query class. Since the specifics of the similarity computation are external
to the <b>QueryManager</b> it is possible to provide similarity functions which take
into account multiple query classes. One way to do this is to provide a
hierarchy of queries in which the results of one level of queries are passed to
a different similarity function.

<h3> <a name="Display Manager">Display Manager and the User Interface</a> </h3>

The display manager, <!WA144><!WA144><!WA144><!WA144><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/displmgr.h">displmgr.h</A>, is responsible for displaying
images on the screen and tracking mouse selection of images. 
This class is closely related to the user interface provided
by the operating system. It maintains the list of currently displayed images and
responds to paint messages generated by the window system.

<br>
<p align=center>
<!WA145><!WA145><!WA145><!WA145><img src="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/displmgr.jpg">
</p>

A client of the display manager can submit a list of images by calling 
<tt>display()</tt>. This will replace the existing list
of images held by the display manager with the list passed to this function.
Then the images will be displayed.
<p>
Note that the <b>Image</b> lists that many of the manager objects maintain are lists
of pointers to <b>Image</b> objects. To avoid memory leaks, clients pass a
<em>deletion policy</em> to the <tt>display()</tt> member function telling
the <b>DisplayManager</b> how to manage the memory in the image list.
<p>
The user interface provides typical menu options according to the Windows(tm) style.
To see a screen capture showing the application area filled with wallpaper
images, click <!WA146><!WA146><!WA146><!WA146><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/images.jpg"> here</A>.
Each image has a label which is the name of the database file containing the pixmap.

<h4><a name="Image Menu">Image Menu</a></h4>

The <b>Image</b> menu provides options for adding images and for querying the database. 
Selecting
a query option presents a dialog designed to solicit a query for a particular query
class. For example, the following screen capture shows the dialogs used to compose a
<!WA147><!WA147><!WA147><!WA147><a href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/qcolor.jpg"> query by color</a>.
<p>
Composing a color query is a multi-step process involving two dialogs. 
The <b>Query By Color</b> dialog allows the user to specify up to 3 color 
percentages for the query. To specify each color, the user manipulates the controls
in the <b>Color</b> dialog. This is a standard Windows dialog that allows selection
of colors directly from the system color palette. The user may also create up to sixteen
custom colors.
<p>
Once the query is composed, the user presses the <b>OK</b> button and the query is
submitted to the <b>QueryManager</b>. All similar images will be displayed by the
<b>DisplayManager</b>.
  
<h4><a name="View Menu">View Menu</a></h4>

The <b>View</b> menu provides selections that allow the user to view information about
the database and its images. The <b>Database</b> item causes the <b>DisplayManager</b>
to display the entire image database. In a real application, this would be impractical;
intelligent browsing tools would be necessary for traversing a large set of images.
<p>
Selecting the <b>Features...</b> item presents the user with the <b>Image Features</b>
dialog containing a list box of
all the image names. The user selects an image and presses the desired button in
the <b>Display</b> group. The following screen capture shows what happens after the
<b>ColorHistogram</b> button is <!WA148><!WA148><!WA148><!WA148><a href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/hist.jpg"> pressed</a>.
</p>
The <b>Color Histogram</b> dialog presents two histograms of the selected image. The
<b>Original Image Histogram</b> is the color histogram of the image as stored in the
database. Each bar represents the relative number of pixels that are assigned the 
displayed color. The <b>Total Color Bins</b> field is the number of bins in each
histogram, and the <b>Total Empty Bins</b> field is the number of bins which do not
contain any pixels.
<p>
The <b>Image Feature Histogram</b> is the histogram of the feature vector. It is
a quantized version of the original histogram. A high 
percentage of empty bins in the feature histogram is common.
<p>
Selecting the <b>Pattern Histogram</b> button from the <b>Image Features</b>
dialog, presents the <b>Pattern Histogram</b> <!WA149><!WA149><!WA149><!WA149><a href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/phist.jpg">dialog</a>. 
The dialog shows the directional bias of the image. The numbers below each of 
the three bins represent the relative biases in each direction. The 
integer values range
between 0 and 3 representing WEAK, NOT STRONG, STRONG, and VERY STRONG. The dialog
shows that the image is very strongly biased vertically and strongly biased 
horizontally.
<p>
The <b>Color Values...</b> item on the <b>View</b> menu presents the user with 
a dialog for viewing the predominant <!WA150><!WA150><!WA150><!WA150><a href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/clrvalue.jpg"> feature colors</a>.
The <b>Image Color Values</b> dialog displays the five most prevalent colors, their 
percentage of distribution,
and their RGB value. The color and the RGB values shown are the value at 
the center of each quantization range. This dialog 
is very useful for testing the quality of the similarity function.

<h3><a name="Query by Color Algorithms">Query by Color Algorithms</a></h3>

When an image is added to the database, the <b>AnalysisManager</b> calls the 
<tt>extract()</tt> member function on the <b>ColorHistogram</b> object,
<!WA151><!WA151><!WA151><!WA151><A href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/clrhistx.h">clrhistx.h</A>. This function is responsible for creating
a query class specific feature vector and installing it in the <b>Image</b>.
<p>
<b>ColorHistogram</b> creates a 64-dimensional color histogram feature vector
similar to the one used in IBM's Ultimedia Manager<!WA152><!WA152><!WA152><!WA152><a href="#ref13">[13]</a>.
Each element of the feature vector represents a cube-shaped subspace of RGB
space as shown in the following figure.   
<br>
<br>
<p align=center>
<!WA153><!WA153><!WA153><!WA153><img src="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/rgb.jpg">
</p>

Each pixel is quantized into one of the bins. After traversing the image, the
histogram contains the number of pixels contained in each color cube. Each 
bin value is then converted to a percentage representing the relative number
of pixels contained in that color cube.
<p>
The similarity function of <b>ColorHistogram</b>
computes the distance between two histograms using th <!WA154><!WA154><!WA154><!WA154><a href="#L2 norm">L2 norm</a>.
This distance is compared to a user-definable
threshold value to determine similarity. The 
<b>QueryManager</b> uses the return value to order images, most similar first.
<p>
The L2 norm only works well on sparse matrices. This is fine when
the user provides three colors via a <!WA155><!WA155><!WA155><!WA155><a href="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/landis/qcolor.jpg">dialog</a> because only
entries with values are compared. When querying by example, the similarity function
ignores small percentages if they are present in both histograms, reducing the 
problem of false positives due
to contribution of insignificant differences between histograms.
<p>
Query by example requires a larger similarity threshold since it
usually involves many more comparisons than queries
via the dialog. For the data I used,
9.0 to 24.0 worked for three color queries and 25.0 to 40.0 
was good for query by example.

<h3><a name="Query by Pattern Algorithms">Query by Pattern Algorithms</a></h3>

Query by pattern algorithms automatically recognize the
directional biases of an image.