kNN Results

Experiment Setup: The 400 odd examples where used as positive examples and the image was run on the image marked up by Dr. Marc. 13248 examples generated by rotating converged synapses where taken as positive examples. Randomly selected other patches (14400) where selected as negative examples. k = 5 Nearest Neighbor classifier was used as the classifier. The test data was the drifted SIFT points generated by the SIFT algorithm.

Results: There where totally 98.94% of SIFT points identified as synapses. That is whopping 49040 (of 49567) synapses in place of 65 identified :(.

Modifications for the next experiment:

1. Ground truth data: Mr. Marc's dataset will be used as the training dataset and first dataset as testing dataset as per Antonio's recommendation.
   
2. Convergence of centroids: Need to understand if the centroid is converging to the darkest or largest dark patch
3. Pick tougher negative examples: The negative examples selected last time where random locations. This time it will be the drifted SIFT point farther than (2 * diskSize) distance.
4. Performance enhancement: We need C Code for distance calculation and interface with Matlab.
   

kNN Results

The kNN experiment was run for values of k=1,2,3,4,5,10,15,20 and surprisingly all of them have got an accuracy of 1. Weird!!! The result files are stored in the files /usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/kNN/knnsynapse-resultsX.mat where X = k value of the classifier. I am skeptical about the results. I will review the code again generate SIFT points for image 2 marked up my Dr. Marc and test the results on it.

Gabor Filter Banks

Gabor Filter: The Gabor filter is linear filter. It is a harmonic function (sinusoidal function) multiplied with the a Gaussian envelope function.

Gabor = Harmonic function X 2D Gaussian envelope.

The harmonic function has two attributes the wavelength and phase and the Gaussian envelope has sigma_x and sigma_y and theta the orientation of the ellipsoidal shaped Gaussian. When constructing a filter bank we need to construct many Gabor filter of various wavelengths and orientations. The gabor filters can be generated by the code found in /usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/textureClassification/gabor_fn.m
The below image are a sample of these filters.

The Gabor filter response looks like a edge detection filter. The below images are the original & Gabor filter bank response. The filter bank is constructed for 20 different orientations. The max response of a pixel for each filter bank is chosen as the filter bank response.



Synapse Status: As the kNN classifier continues to run, I am going through the various filtering approaches of texture classification as described in here. This blog talks about Gabor filters in general.

Porting code to C++

Since the crash of the hex, I have been porting my Matlab code to C++. I have been experimenting with Qt, Xerces and ITK.

Texture Classification: Signal Processing: Heuristically designed filters

Laws Filter Masks
The laws filters tried to identify the levels, edges, spots, waves, ripple features in the image. It provides 25 features which are a combination of filters to detect the above features in the image. The code to generate the Laws features can be found in the following file
/usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/textureClassification/generateLawsFeatures.m


References:

1. http://www.c3.lanl.gov/~kelly/notebook/laws.shtml
   

Texture Classification

For adding features that could be used for the synapse classification, we will be looking into methods that are used for texture classification. Texture classification is one of the important components of texture analysis. The other components of texture analysis are texture segmentation, texture synthesis, shape identification from texture.

Texture classification is done by different types of Techniques. The major types are the following:

1. Statistical
1. Co-occurrence
2. Angular Second Moment
3. Contrast
4. Correlation
5. Entropy
   
2. Geometrical
   
3. Structural
4. Model-based
1. Multi-resolution autoregressive
   
5. Signal processing features
1. Heuristically designed filter banks
1. Laws Filter Masks
2. Ring and Wedge Filters
3. Dyadic Gabor Filter bank
4. Wavelet transfer, Packets and Frames
5. Discrete Cosine Transform
6. Quadrature Mirror Filters
7. Tree structured Gabor Filter bank
2. Optimized filter and filter banks
1. Eigenfilter
2. Prediction error filter
3. Optimized representation Gabor Filter bank
4. Optimized Two-Class Gabor Filter
5. Optimized Multi-Class Gabor Filter
6. Optimized Two-Texture FIR Filters
7. Optimized FIR Filter bank
8. Back Propagation Designed Mask
   

References:

1. Filtering for Texture Classification: A Comparative Study
   
2. http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/OJALA1/texclas.htm

Animated GIFs showing rotated Synapses regions

I created code that will create Animated GIFs in MATLAB the code can be found in the following location
/usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/kNN/CreateRotatedRegionGIFs.m

The animated GIFs of the rotating synapses were created successfully but it looks like the animated GIFs don't work in the Blog :( .

Orientation of Synapse: From Image moments

In this method we will calculate the orientation of the synapse from the image moments. Here the moments are calculated calculated from the gray scale image. The method is described in the following location in Wikipedia. The code for this method and the previous method are in /usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/orientation/getOrientation.m.

The result for that is almost the same as the previous method.

Orientation of Synapse

Apart from predicting the location of the synapse we will also predict the orientation of the synapse. We will be trying out the following methods to determine the orientation:

1. Fitting an ellipse
   
2. Image moments
3. Gradient image analysis
   
4. Image processing toolbox

As per previous months meeting discussions apart from determining the orientation of the synapse the direction of the synapse also has to be Synapse also has to be determined. The clue that we have is the pre-synaptic densities bend the membrane to a concave shape (from the receptor neuron). One visual clue that we have is that the pre-synaptic density if vesicles makes the transmitter part of the Synapses appear blobbier.

The easiest one to try quickly is the one in image processing toolbox. The algorithm for determining the angle that is the following.

1. For the circular patch, threshold values below the gray value that is at 50 percentile point.
2. For the resulting binary image choose the largest patch and determine the orientation of the match from the "regionprops" command.
3. The orientation of the synapse is perpendicular to the orientation of the region.

The results for this method are shown below. The input image is shown to the left. THe input image is an image downsampled 25% and smoothened by perona-malik smoothening for 25 iterations. Then the grey values of this image have be ordered and the 50 percentile grey value is calculated and all grey value above it are set as "1" and the rest are set as "0".

The result of the above thresholding is shown to the left here. The region property of orientation is determined which is likely to the orientation of the membrane. The orientation of the synapse is perpendicular to the synapse. Hence the orientation of the synapse is +15.7 degrees to the positive X-axis.

Normalized Cross-correlation

One of the dissimilarity measures is Normalized cross-correlation. More information can be found in http://www.cs.unc.edu/~marc/tutorial/node50.html.

This dissimilarity measure is used as the distance between the images.

Creating rotated Samples

Results of Perona Malik smoothened image (25 iterations). They are pretty the same as 10 iterations.
Now we will see the extracted images from the Synapses points. The code to generate the rotated samples is in the following location.
/usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/kNN/CreateRotatedRegions.m


....Rotating GIFs here......


The examples of non-synapses are generated by the following code
/usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/kNN/CreateFalseExamples.m

So that we have a dataset for a the kNN classifier.
The positive example images are found in
/usr/sci/crcnsdata/CRCNS/Synapses/data/roiExport3/RotatedImages1/
The negative example images are found in
/usr/sci/crcnsdata/CRCNS/Synapses/data/roiExport3/FalseExamples/

Now the learning experiment has to be set up. The images will be read and the raw pixel values will be stored as the attributes of the data points. Then kNN experiment will be run.

Creating samples for the kNN Classifier

After the reasonable results in the previous experiments we will move on to constructing rotated examples of the image. The following algorithm will be used for extracting the regions and applying rotations to them:

1. For every converged synapse point, extract the square region of side equal to diameter of the disk.
2. Rotate the image and extract the circular region from center of the image.
   

Verifying Assumption: Centroid convergence 2

Yesterday's experiment was repeated with the SIFT key points instead of noisy synaptic co-ordinates. The results are shown below.

We see that more than 95% of the converged synapses have the converged SIFT key points within 5 pixels. This is much more that yesterday's results. We will go ahead with the image rotation part of the example synapses and building the k-NN based classifier.

Verifying Assumption: Centroid convergence

Now in the first step we are experimenting to find if the centroid is converging to a darker region in side the synapse.

Convergence: The algorithm described in the previous blog was run on the following images:

1. Original image
2. Smoothened image (15x15 Gaussian blur) (GIMP generated)
   
3. Perona-Malik anisotropic diffusion image (MATLAB Central)

In all the images the the centroid converges. The results are shown below.

Convergence of nearby points to Center: The next step is to prove that if taken a point around the synapse it would converge again to the synapse location. To prove this we add some Uniform noise to the Synapse co-ordinate locations and run the algorithm to find out the centroids.

On running it on the third image. The histogram of distance between the original points convergence and the noisy co-ordinates convergence is shown below. The noise levels are 10, 20, 30 pixels



Now looking at the data we see that distance is really really LARGE, more than 50% of pixels is farther than 10 pixels from where the original convergence is. We made an assumption that noise is uniform. Still to go ahead with approach we need to see if the positioning of the SIFT key points is really same as co-ordinates affected by uniform noise. We can attempt to converge the actual SIFT points in the image and then see the number of synapses having SIFT points closer to them hoping that the noisy synaptic locations are not a correct representation of the SIFT key points.

The new kNN based classifier

I will be working on a new k-Nearest Neighbor based Machine learning approach. The distance metric that will be used in this method will be normalized cross correlation. We will learn over the given synapse examples marked up by the Marc lab as we did in the previous experiments. The experiment set up will be as follows.

Setting up examples
Positive examples: For the few chosen samples synapses, we will try to find out the center of the dark mass of pixels. After finding the center we will rotate the image about that center by 10 degrees and create 35 new samples. Say we chose 50 example synapses, we will have 1750 (35 x 50) positive examples. We rotate the example to come around the rotation variability. The examples regions will be circular in shape again.

Negative examples: Negative examples chosen will be any location that doesn't enclose even part of any synapses.

Running the experiment
Sub sampling few pixels: Getting to the center of dark regions of the synapses by iterating through all pixels of the image will be a costly operation. So just like the the previous experiments we will used the SIFT key points filtered by a thresholded CLAHE image. At this point we are assuming we will be able to find center of dark region near the key point. After finding the center point. For the calculated center points, we will find the normalized cross correlation to all the positive and negative examples. Then we will use these distance measurements and run a kNN based classifier.

Verifying Assumption: The primary assumption for the experiment is that we will be able to find the center of the synapse if we are close enough to the synapse. Hence, first we will verify if the assumption is reasonable enough. For that will take the ground truth Synapse markup and extract the region around them and try finding the center. The following algorithm will be used to find out the center of the Synapse:

1. For each marked up synapse point extract a circular region around it.
2. We will weigh the image by the darkness of the pixels(inversely proportional to pixel intensity), and closeness to the marked up point (inversely proportional to the distance from markup). Hence we will invert the image (255 - Image) and weigh the pixels away from the point by a Gaussian and find the new center for the region.
3. Use the new center and repeat step 2 to find new center till it converges.

I guess, if at least 90% of the Synapses converge it would be a reasonable assumption.

Project Status

2008 Aug 27th, Wednesday
Matlab to C++ conversion - ongoing
Learn ANN -Until Backpropagation Algorithm
kNN - Still running
Texture Classification - Tried Gabor Filters

Changing the feature vector

All code has been organized so that the same code can handle generation of all datasets and running all the learning experiments. The following changes have been made to the feature generation code:

1. Removing the translation in variance factor.
2. Removing the scale invariance factor.
3. Decreasing the number of bins in CDF attributes 0 - 5, 6 - 10 to 0 - 10, 11 - 20 etc.
4. Removing the histogram attributes.

The code to generate all datasets is in the files generateFeatures.m and momentCalc9.m in the following location /usr/sci/crcnsdata/CRCNS/Synapses/Code/Matlab/featureGeneration. The generateFeatures function takes the dataset name as argument and generates the datasets. The run.m has been modified so that it takes the dataset and learner types are inputs and learns accordingly.

After this change was done the new datasets were generated for the following datasets:

1. Synapses Dataset
2. Tough Brodatz Textures Dataset
   
3. Cell Membrane Dataset

Once the datasets have been generated. Both the perceptron classifier and decision stump classifiers were used to learn over them.

The results of the various experiments are shown in the below graphs. Left side graphs are Stump based classifiers and perceptron classifier results to the right.

Tough Brodatz Textures Dataset Results: This experiment was run with a required true positive rate of 0.7


Synapses Dataset Results: This experiment was run with a required true positive rate of 0.7


Cell Membrane Dataset Results: This experiment was run with a required true positive rate of 0.7