Final report of my internship at Boston University


My summer at Boston University was a very good experience. I learned a lot from my 10 weeks here and got a good exposure to graduate school and also research in the Computer Science field. When I accepted the internship here, it was a big step, since I had never been here and didn't even know anyone here. But after coming here, I have made a lot of new friends and had some wonderful experiences. The bus rides to work everyday, taking care of two dogs and living alone have all been new to me. I praise God for the opportunity He gave me to come here. I would never have thought I would end in Boston. I thought I would work in Minnesota, live in Bethel dorms and work there. But God had other plans. He knew what was best. This has definitely worked out well. I am thankful to everyone who made this possible, the Reids', Prof. Betke, Harry and Waltham Evangelical Free Church.

Research Statement

In the summer of 2002, I was selected to participate in the DMP Mentorship program sponsored by the Computer Research Association. I worked at Boston University with Prof. Betke in the Image and Video Computing group of the Computer Science department. I worked closely with her and her graduate students on their research projects in the field computer vision in particular, medical image analysis.

The project we worked on was the alignment of CT scans. We worked on finding an optimal method to align lung surfaces of two successive scans of the same patient. Two papers resulted from our research. The first one was about the multilevel method and was accepted at the International Conference on Diagnostic Imaging and Analysis in August 2002. The second paper was a journal paper about landmark detection in chest scans and use of their positions to align two scans. This paper was presented to the journal, ýMedical Image Analysisţ.

Multilevel Method

We explored the multilevel method, which improved both the efficiency and accuracy of the non-multilevel method. The multilevel method is used to solve optimization problems. This method involved three steps, namely coarsening, projection and smoothing. First, the problem is coarsened, which means it is reduced in size. Then, we find an initial solution. This solution is projected onto the next level and used as an initial estimate of the solution. Then the solution is smoothed, to reconstruct the solution of the previous level for the current level.

We used the multilevel method to solve the problem of lung surface registration. We reduced the number of points on the surface by half for a given number of levels. We then found a solution to the level with lowest resolution and used this solution to find the alignment of the set of points at the next level. The alignment of the two scans is based on six parameters. They are the translation and rotation in the X, Y and Z direction, respectively.

We also used a variation of the Iterative Closest Point algorithm(Besl Ý92) by using a nearest neighbor search. An exhaustive search to find the closest points from one scan to another would require quadratic time complexity. In the nearest neighbor search, the search space is divided up into voxels. For each point of the second scan, its adjacent voxels are checked. If they contain transformed points of the first scan, the closest one is chosen as the corresponding point. However, if no points exist in that region, the region is expanded in every direction by one voxel and the search is repeated till a closest point is found.

We also explored another possibility. If the scans were severely misaligned to start with, the optimal solution may not have been found. So we included an initial alignment based on the position of landmarks. I implemented the method that searches through a given slice to find the local of the sternum and spine. We used a correlation method based on Hounsfield Units. We obtained a detection rate of 100%.

To improve accuracy of the correspondences we tested another variation. Instead of using the closest point by the nearest neighbor search algorithm, we took the average of the two closest points. This method improved on accuracy but also increased the time taken. Hence, there is a tradeoff in using this method.

Chamfer matching Method in 3D

Another area of medical imaging that I worked with was chamfer matching (Borgefors, Ý88). This is a method to find the closest point of two sets of data using a look up table. Prof. Betke and I worked on finding a method that generalized the chamfer method to 3D that would make sense to use for lung surface alignment.

The building of the look up table is the slowest part of the algorithm, but once done, it can be used to find distances of two surfaces efficiently. Each position in the table is initially assigned an infinitely large number. Then for every point on the lung surface, its corresponding position in the table is set to 0. Then, by doing a forward and backward pass on a 3D array of the pixel space, each position in the array is given a value based on its distance from the closest point of scan 2. We give it the smallest value between the point itself and its neighbors weighted according to its distance from the point concerned. Then we do a reverse pass on that slice. We then proceed to the next slice and repeat the process. Once complete in the forward direction, we repeat the process in the reverse direction. Once the table is made, finding the distance between two sets of points is easy. We go through each point in the first scan and look up its corresponding position in the table. That number is that pointÝs distance from its closest point in scan 2.

The chamfer method was initially used as a comparison to the method we originally implemented for registration namely the nearest neighbor search. But now we are exploring the idea of finding the optimal rotation and transformation of the misaligned scans using the chamfer measure.

Since its still in its initial stages, I have experimented with a number of possible variations. In the first method, I implemented the gradient descent method and experimented with variations in the sequence of optimization of the six parameters to find the point at which it converges. However, as expected, we have found that it tends to converge at local minima rather than the global minimum.

The other method I tried was to do a six dimensional search varying all six parameters at the same time. This definitely is more accurate and is more likely to find the global minima. However, it was an exhaustive search in the subspace of the 6D solution space. So the problem is the time taken. There are many optimizations possible, and this is where the project currently stands. It is still in the implementation stages as far as the optimization goes.

There are many things I will take away from this internship. I have got a good exposure to what research and a career in academia would entail. I have learnt a lot about the area of medical imaging and the current status on this area of research with regard to CT scans. I have also learnt different methods like the multilevel method and the chamfer matching method. I have learned a little about using Linux machines and also learnt a lot about I/O in C.