Consumer RGB-D cameras such as the Microsoft Kinect have revitalized research in three dimensional Simultaneous Localization and Mapping (SLAM) due to their revolutionarily low cost. A number of 3D SLAM algorithms that use data obtained through RGB-D sensors have been developed, capable of producing rich and visually-appealing maps in indoor environments. However, a deeper inquiry reveals that such algorithms deal with the possibility of moving objects in only an implicit and incomplete way. Indeed, the maps created in such works are created in environments completely void moving objects, in particularly people moving around. This severely limits the application space of such approaches.

I developed an algorithm to explicitly identify and remove moving objects from multiple views of a scene with applications to Simultaneous Localization and Mapping (SLAM) in dynamic environments. I begin by segmenting out all objects/clusters in two views of the same scene, and computing a matrix describing the spatial relationships between objects in each view. I then find which objects from the two views correspond to each other. This allows me to detect when the relative position of one object to other objects in the scene changes, indicating that the object in question is moving. Such objects can be removed from the scene without affecting the rest of the scene. Using this algorithm as a preprocessing step in SLAM systems allows the creation of detailed three dimensional maps of indoor environments even in highly dynamic scenes with people moving about. I have tested my algorithm on real data captured in an office setting.

Read the paper: PDF (600 kB)

Optimizing Industrial Ventilation Systems by Clustering Workstations

In any factory where waste is produced, ventilation is necessary for health, safety, and manufacturing reasons. This is the case in a broad range of industries, including woodworking, metalworking, printing, chemical, or the automotive industry. Modern on-demand ventilation systems close ducts to workstations that are not in use using electronic gates; this allows the system to slow down the ventilation fan, saving electricity.

I applied hierarchical agglomerative clustering algorithms to datasets of workstation activity recorded in five-minute intervals over periods of time ranging from 9 days to one month. I grouped together workstations into ventilation subsystems based on the usage data as well as static pressure values measured in the factories. In simulations, I achieved significant energy savings even when the number of ventilation subsystems was small. I provide a procedure to guide factory management in dividing the ventilation system into smaller systems in order to achieve energy savings.

Full report: PDF (600 kB)

I've made HTML5 animations of some common synthesis of digital systems algorithms to demonstrate how they work. Just go to the animation, load up an example, and run the algorithm. You can also provide your own inputs, although be warned: there is no validity checking of the input. I particularly recommend Simulated Annealing, example 3.

Simulated Annealing is a general optimzation procedure based on making random changes, evaluating the optimality of the resulting solution, and accepting the move with a probability given by how the move changed the solution fitness, as well as how much time has elapsed.

The Quine–McCluskey algorithm minimizes boolean equations. It is equivalent to using K-Maps (Karnaugh maps), but more efficient to implement on a computer.

The Left Edge Algorithm is an algorithm used for channel routing. For example, suppose you had some functional blocks to place in a row, and wires that run between the cable. Changing the ordering of the blocks changes the number of channels necessary to route the problem. The left edge algorithm guarantees the minimum possible number of tracks used.

Approximating the Frequency of MAC Address Spoofing

Although MAC addresses are designed to be globally unique, this is not always the case due to issues such as counterfeiting or manufacturing errors. In this project, I calculate the probability of seeing a MAC address conflict under various conditions. I use real-world data for the number of network devices shipped globally to estimate the total number of network devices in use, and estimate the probability of seeing a conflict for different rates of counterfeiting as well as different sample sizes.

Full report: PDF (600 kB)

Cross-session Relevance Feedback in Content-Based Image-Retrieval

Content-based image retrieval provides the user with images similar to a query image based only on pictorial features. Relevance feedback allows the user to specify which retrieved images are relevant. Using this information with the original query image, the quality of the results can be further improved. I implemented the Cross-session Relevance Feedback algorithm described in Long-Term Cross-Session Relevance Feedback Using Virtual Features (PDF, 5.4 MB), and created a GUI testbench in Visual C++ to verify the algorithm. I used a dataset of around 38,000 images of butterflies to test the algorith. Relevance feedback significantly improved the retrieval performance.

Further details regarding this project are here.

Parallelizing Tracking in Video on a GPU using CUDA C