About This Assignment:

This assingment does not target any specific topic in 461. Instead, it draws upon various components to help solve a more complex problem. It is hoped that this makes it more interesting and relevant than, say, "Implement a B-Tree".

NOTE: The programming parts of this assignment are worth ~1/2 of the total marks. The other 1/2 is for design and discussion.

Scenario: I'm doing a project which involves the creation of a few web pages. I need to find some images. I have a few that I like but I want a few more that are similar. This assignment is to devise a "Search Engine" for images. For example, if I have a picture of some mountains, I want this "search engine" to be able to find more pictures of mountains.

The basic idea is as follows:

1. Load the search page in my browser (let's say Netscape, for simplicity)
2. Type in the URL (or local file name) of one (or more) images
3. Your search engine will examine all available images in that site and search for one's similar to the one first given. [Note: This is a trick - see later for explanation.]
4. Your search engine will provide a report of images examined, and display those images classified as "matches" along with some analysis data indicating why these images are considered as matches.
   

Before We Begin:

There are two main approaches to the solution of this assignment:

1. You can solve the Search Engine Component.

The solution to this is known. It is fairly clear-cut. It will involve numerous programs and will produce a solution that can be run as a demo. It will require you to design a file format for storing image data that has been gathered; creating a file in that format; searching it; and producing output.

2. You can solve the Image Matching Component.

The solution to this part is not known. By anyone. It isn't at all clear cut. In fact, you may end up with nothing definitive. You may end up with a bunch of data that indicates your 'solution' was the wrong one. This is one of the few assignments where bad results will be acceptable. This approach involves relatively little code but lots of running of your program and lots of data gathering and analysis. It will require your writing a number of components that will serve as testing tools and then running many images through your system; changing your parameters; and doing it again; and again; and again.

Do NOT attempt to do both. It's way too much work.

Data consists of an undetermined number (could be from 10's to 1000's) of files in a given directory tree. To keep it simple, your system should be capable of gathering data on any website in the www.cpsc.ucalgary.ca domain. If you have your own website, try that. If not, you may use any of the sites in our department (www.cpsc.ucalgary.ca; pages.cpsc.ucalgary.ca) or any of mine: ~becker/461 ~becker/461old ~becker/231 ~becker/233. Notice each has a 'main' directory and numerous sub-directories. The engine should search all pages in all sub-directories. If time permits, a sample website will be placed in the 461 directory in the directory called WWW

Part 1: Outline/Design: [the requirements for part 1 are the same for both approaches]

- submit a 2-5 page report (professional appearance is required) outlining your intended design for the search engine

- explain what attributes you intend to measure (with examples), and why you think they will be successful

- all design decisions must be justified

---

Part 2 - Version 1: The Search Engine:

2 Main Components:

1. program(s) to build (indices) and update the database file.

2. program(s) to do the retrieving - these must be connected to a webpage

The Generator

This component may consist of multiple programs and utilities (it need not be a singlre program). If so, all parts must be "wrapped" in a shell program so the system's webmaster can use it by simply running a single script. One possible approach:

First:Given a directory containing images, write a program or utility that will extract summary data from each image in the directory and produce a list of image data-web link pairs (relative pathnames are permissible but not required):

Next: Sort the output produced by Part 1 (note: efficiency counts);

Eliminate duplicates. Merge all the pairs so each image appears only once in the final list followed by the number of pages it appears in and a list of the URLs for the pages themselves.

Then: Design a file structure that will allow for an efficient search when necessary but still leave us with only a single, relatively small file. Explain and Justify your choices.

The Search Engine:

Build a simple query system that

- uses the file created above

- can be executed from a web-page (i.e. input comes from a web form, the 'program' will be automatically run when the user submits a query, and the results will be displayed in one or more html pages)

- given a sample image to search for, shows the URL for each image deemed to be a match (again, efficiency counts)

 

If you are creating your own form for the search, be sure to keep the user interface as simple as possible. That is not the focus of this assignment.

---

Part 2 - Version 2: The Image Match:

2 Main Components:

1. program(s) to read images and gather data.

2. program(s) to do the matching - these must have a simple, but effective user interface

The Collector :

This component may consist of multiple programs and utilities (it need not be a singlre program). If so, all parts must be "wrapped" in a shell program so the system's webmaster can use it by simply running a single script. One possible approach:

First:Given a directory containing images, write a program or utility that will extract summary dtaa from each image in the directory and produce a file of image data-pathname pairs (relative pathnames are permissible but not required):

Then: Design a file structure that will allow for an efficient search when necessary but still leave us with only a single, relatively small file. Explain and Justify your choices.

The Image Match:

Build a simple query system that

- uses the file created above

- given a sample image to search for, shows the URL or filename of each image deemed to be a match (again, efficiency counts) including any applicable summary analysis

 Requirements:

Part 3: Analysis and Discussion [The Post-Mortem]:

[Note that this is NOT a complete list, merely a few suggested questions to consider]

- how successful was your design?

- what could have been inproved?

- how did your design change from your original, and why?

- if you had it to do again, what would you change? (and why, always why).

- what have you learned from this?

Describe and fully justify your structure(s) :

- Your implementation should make efficient use of space and minimize downloading time and searching as much as possible. Justify all design decisions regarding data structures used and how they affect efficiency and speed.

- Comment on any special problems encountered as a result of your design and possible solutions or modifications recommended for the next version.

- Remember that this application should be able to deal with thousands of images so design your structures and algorithms accordingly.

How is the index implemented?

- diagrams (like UML or some such) are acceptable

 

 

What kind of index search did you implement? What makes it efficient? What are the costs? Why did you choose this one?

- Remember, it must be efficient for a directory or set of directories that contain hundreds or thousands of documents.

 

Assuming that the website may be updated from time to time, how would you design an update program that can add to the index without having to re-create the entire set?

---

All explanations must be clear and concise or they will not be marked. All code MUST be fully documented and both a programmer's manual and a user's manual must be supplied (can be in same document but must be obviously separate). Programmer documentation must include a description of the structures used, algorithm outlines, and justification for your decisions.

If adequate documentation is not supplied your maximum grade will be C.

---

IF YOU DEVIATE FROM THE SPECS YOU MUST HAVE A GOOD REASON. In other words you may use your own judgment but you must be able to convince your TA that it's really a good idea!

A major portion of the marks for this assignment is allowed for discussion. You need not implement the most efficient methods you know. Give it some thought at the beginning and then do the implementation. Do not redesign your program if you discover inefficiencies. Instead, discuss what is good about your design and what is not. Make some suggestions for how this program could be redesigned to be more efficient. Gross inefficiencies and efforts clearly below a third-year level or expertise are unacceptable.

 Copyright © 2002 Katrin Becker 1998-2002 Last Modified May 16, 2003 11:35 PM