I try to combine the FAST algorithm and parts of the SIFT Algorithm to get a fast Solution for Mobile Phones.
The code I created for that works like the following:

- Get Image
- calculate Size for Resize with
`src.rows/factor`

and `src.cols/factor`

where factor = sqrt(2) - resize Image (INTER_NEAREST) and Blur it with GaussianKernel(5x5)
- Run FAST over the new smaller and blurred Image
- Iterate through every candidate and make a Image Patch (15x15) with the candidate in its origin
- calculate the OrientationHistogram and get the peaks of it.

Here the ~~Code:~~

```
rows = src.rows/factor;
cols = src.cols/factor;
resize(src, tmp, Size(rows, cols),0,0,INTER_NEAREST);
GaussianBlur(tmp, dst, Size(5,5),0,0);
FAST(dst, candidates, 0,true);
if(candidates.size() > 0){
for(int i = 0; i < candidates.size(); i++){
if(candidates[i].pt.x > 7 && candidates[i].pt.y > 7){
KeyPoint kpt = candidates[i];
int px = kpt.pt.x -7;
int py = kpt.pt.y -7;
if(px + 15 >= src.cols || py + 15 >= src.rows)
continue;
patch = src(Rect(px,py,15,15));
float scl_octv = kpt.size * 0.5f / (1 << k);
float omax = calcOrientationHist(patch, kpt.pt, cvRound(SIFT_ORI_RADIUS * scl_octv), SIFT_ORI_SIG_FCTR * scl_octv, hist, n);
```

and the calcOrientationHist function:

```
static float calcOrientationHist(const Mat& img, Point pt, int radius, float sigma, float* hist, int n){
int i, j, k, len = (radius*2+1)*(radius*2+1);
float expf_scale = -1.f/(2.f * sigma * sigma);
AutoBuffer<float> buf(len*4+n+4);
float *X = buf, *Y = X + len, *Mag = X, *Ori = Y + len, *W = Ori + len;
float* temphist = W + len + 2;
for( i = 0; i < n; i++){
temphist[i] = 0.f;
}
for(i = -radius, k = 0; i <= radius; i++){
int y = pt.y+i;
if( y <= 0 || y >= img.rows -1)
continue;
for(j = - radius; j <= radius; j++){
int x = pt.x + j;
if(x <= 0 || x >= img.cols -1)
continue;
//in opencv sift at<sift_wt>
float dx = (float)(img.at<uchar>(y, x+1) - img.at<uchar>(y,x-1));
float dy = (float)(img.at<uchar>(y-1,x) - img.at<uchar>(y+1,x));
X[k] = dx; Y[k] = dy; W[k] = (i*i + j*j)*expf_scale;
k++;
}
}
len = k;
//compute gradient values, orientations and the weights over the pixel neighborhood
hal::exp32f(W, W, len);
hal::fastAtan2(Y, X, Ori, len, true);
hal::magnitude32f(X, Y, Mag, len);
for( k = 0; k < len; k ++){
int bin = cvRound((n/360.f)+Ori[k]);
if(bin >= n)
bin -=n;
if(bin < 0 )
bin +=n;
temphist[bin] += W[k]*Mag[k];
}
//smooth the histogram
temphist[-1] = temphist[n-1];
temphist[-2] = temphist[n-2];
temphist[n] = temphist[0];
temphist[n+1] = temphist[1];
for(i = 0; i < n; i++){
hist[i] = (temphist[i-2] + temphist[i+2])*(1.f/16.f)+
(temphist[i-1] +temphist[i+1])*(4.f/16.f)+
temphist[i]*(6.f/16.f);
}
float maxval = hist[0];
for(i = 1; i < n; i++)
maxval = std::max(maxval, hist[i]);
return maxval;
}
```

Code:
Migrated to Github because it is really long The Idea for this comes from this Paper

The first Steps are running pretty good. But the last one seems to result in **ONLY** 4 Keypoints while I get 220193 Candidates from FAST.

**EDIT I found such a low Keypoint size, because I was inserting the Point Location of the Interest Point in the Source Image not the Image Patch which I pass to the calcOrientationHist Function But now I got another Error look at EDIT2**

The Code I am using is similar with the code from calcOrientationHist Function from the sift.cpp The Input Image is my Image Patch, the Point is the Candidates Point. To calculate the radius and sigma I needed `scl_octv`

but because I dont really go in "Octaves" through the Image I just calculated it like this: `float scl_octv = kpt.size * 0.5f / (1 << 1);`

similar to the sift.cpp but with the difference that I add bytewise 1 and not the actual octave. The Peak detection after creating the histogram looks like this:

```
float mag_thr = (float)(omax * SIFT_ORI_PEAK_RATIO);
for(int j = 0; j < n; j++){
int l = j > 0 ? j - 1 : n -1;
int r2 = j < n-1 ? j+1 : 0;
if(hist[j] > hist[l] && hist[j] > hist[r2] && hist[j] >= mag_thr){
float bin = j + 0.5f * ( hist[i] - hist[r2] ) / ( hist[l] - 2 * hist[j] + hist[r2]);
bin = bin < 0 ? n +bin : bin >= n ? bin - n : bin;
kpt.angle = 360.f - (float)((360.f/n) * bin);
if(std::abs(kpt.angle - 360.f) < FLT_EPSILON)
kpt.angle = 0.f;
features.push_back(kpt);
```

Where `SIFT_ORI_PEAK_RATIO`

is 0.8f.
When I cout the size of features I get the number `4`

in the ~~console. The Image I am using for testing is this:~~

console.

After ~~it ~~the Image is read through `ìmread`

I turn it into a grayscale image with `cvtColor(bas, src, CV_BGR2GRAY);`

where `bas`

is the loaded Image and `src`

the output. In my Example I only go through one Resize and Blur step.

**EDIT2 After solving this Error, I get a Malloc Error now.**

The Position this Error is thrown is at Line 207 in my Code

I already tried to free as much Memory as possible, but I don't believe, that this is the Solution. XCode Analysis says, that my Application needs 9MB memory.

I hope somebody can see ~~why it doesn't work fine.~~the Error Occurs.