SENIOR PROJECT PRESENTATIONS 2010

Matt Baker will present on Monday, 10 May, at 11:30am in OLB 105
Phil Tully will present on Tuesday, 11 May, at 1pm in OLB 105
Toby Fox will present on Tuesday, 11 May, at 2pm in OLB 105.

Each presentation and associated opportunity to ask questions will last no more than an hour, so... come one, come All!  Abstracts for all three senior projects are below.

Monday, 10 May, 11:30am in OLB 105
Projective Brush Stroke Texturing for Real-Time Painterly Animation

Matt Baker ('10)
Thesis Advisor: Tom Ellman

Non-photorealistic 3D rendering is the series of techniques for displaying 3D model data in a stylized manner, often with the purpose of emulating physical media such as ink, pencil, or charcoal.  Though a subset of these techniques have seen remarkable successes – most notably, rendering methods capable of emulating traditional hand-drawn animation – many styles remain difficult unsolved problems.  Painterly rendering is one such difficult style: keeping track of the thousands of brush strokes that make up a painted scene often overwhelms existing rendering algorithms, especially ones attempting real-time speeds. 
The purpose of this thesis is to explore the possibilities of creating a painterly rendering system using a method of texture projection commonly used for real-time water simulations, with the goal of creating a system capable of producing real-time 3D animations with strokes similar to Impressionist paintings.  Because 3D rendering is extremely parallelizable – each vertex and pixel of a 3D object, given the appropriate matrices, is capable of transforming and rendering itself without knowledge of its surroundings – Nvidia’s Cg shading language is used to target the massively-parallel Graphics Processing Units (GPUs) found on most modern computers.  The results are promising: using this method, brush strokes are capable of being placed on a scene reliably at speeds upwards of 120 frames per second.  However, the method is not without its flaws: the system produced noticeably mechanical-looking output when presented with certain scene types, and unlike traditional oil paintings, the edges of the objects that it renders are smooth and distinct.  Its sheer rendering speed, however, makes it likely possible to combine the system with other, slower techniques for the cases in which it fails, and still obtain reliably real-time framerates.

Tuesday, 11 May, 1pm in OLB 105
MarsRF: A GPU-based MapReduce Algorithm for Calculating Robinson-Foulds Distances over Large Collections of Evolutionary Trees

Philip Tully ('10)
Advisor: Marc L. Smith

The Robinson-Foulds (RF) distance is a measure of topological dissimilarity between a pair of evolutionary trees. Calculating the all-pairs RF distance matrix for a large collection of trees is a way of analyzing how those trees cluster in tree space. This RF matrix requires O(nt2) time to calculate sequentially (for a collection of t trees of n taxa), but this performance can be improved. In particular, RF distance matrix computation is an embarrassingly parallelizable task because individual RF distance calculations are independent. Matthews and Williams (2010) developed MrsRF, which uses randomized hashing techniques in conjunction with Phoenix’s MapReduce framework to parallelize parts of the RF matrix computation.
We explore the feasibility of parallelizing RF distance matrix computation on a Graphics Processing Unit (GPU). The price, power consumption, and physical space requirements of one GPU are an order of magnitude less than that of a multi-core cluster of nodes. Originally, GPU hardware was developed to speed up computation for rendering graphics and animation. More recently, the inspiration for general-purpose computation on GPUs (GPGPU) has emerged to exploit the parallel processing capabilities provided by GPUs for scientific applications. NVIDIA’s Compute Unified Device Architecture (CUDA) library provides an interface for programmers to develop applications to be executed on the GPU device. Conveniently, Mars augments the CUDA API with a GPU-specific MapReduce framework. Using these tools, we develop a set of algorithms inspired by MrsRF, collectively named MarsRF, which enable us to compute the all-pairs RF distance matrix on a massively parallel GPU device residing within a single desktop computer. 

Tuesday, 11 May, 2pm in OLB 105
Computing Metaphor: Integrating Corpora and Language Resources to Automate Interpretation of Metaphors

Toby Fox '10 
Advisor: Nancy Ide
  
Among the many problems we face in processing natural (human) languages computationally, the problem of comprehending figurative language is less well researched and understood, though in the last decade computer scientists and linguists have begun to study it in more detail.  One particular area of this larger problem is the problem of understanding the meaning intended by metaphors.  Generally, it takes more information to understand a metaphor than can be found in either the dictionary entries for the words involved or in the context of the sentence.  The way we create and interpret metaphors harnesses common sense and an understanding of the world that, at this point, is only fully accessible to humans: much figurative language relies on the contextual associations that we have with particular words based on the experiences that we have with those concepts in our lives.  This thesis attempts to get at some of that world knowledge via text mining techniques on corpora (large bodies of real world text) as well as by taking advantage of knowledge encoded in databases such as WordNet (a highly structured dictionary containing many semantic relations between words) and SUMO (the Suggested Upper Merged Ontology: a formal representation of the relationships between various concepts).  Metaphors are a tool to understand and describe one concept (the "target") by its similarities to another concept (the "source").  Using information gathered from these resources, I have come up with an algorithm that attempts to define any given metaphor by listing the discrete associations between concepts that this metaphor might be highlighting, organized by an estimated measure of likeliness.  Each association consists of one attribute in the source being mapped onto one attribute in the target.  The approach I use varies from that used by other researchers who have looked at this problem, but it can be improved by integration with existing systems, and has applications for other problems involving figurative language.