Please ask questions in the comments below.
Q: Where do I get FAST?
A: http://mi.eng.cam.ac.uk/~er258/work/fast.html
Q: Why is the code so hard to read?
A: It is machine generated. You aren’t supposed to read it 
Q: How do I get N corners?
A: You have to sdjust the threshold t automatically:
- If N is too high, increase t. If N is too low, decrease t.
- Perform binary search over t to find the value which gives N corners
- Set t too low (N too high). Compute the corner score and sort corners by the score. Then keep the N with the highest score.
Q: Why is the Python/MATLAB code slow?
A: The FAST algorithm has been designed to work as quickly as possible and is therefore target strongly towards compiled languages. The code is provided for ease of use for interpreted languages, but it will not be especially quick. If you need it to run quickly you will need to interface to the C version.
How can I use the software for matlab to match corners between images and not only to find corners?
FAST is just a system for detecting interest points.
The type of matching that you want will depend on the application. A very simple scheme is to extract a small square of pixels (e.g. 11×11) from around the FAST interest points, as a vector. You can match two points by looking at the norm of the difference between them. Then, you have to compare every point in the first image to every point in the second to find the best match.
What’s the major difference between using non-maximal suppression and not using that? Which one has better result? The second question: can threshold 0 to be used if the image intensity is low? Thanks.
The corner strength in FAST (and all other corner detectors) tends to be high in a region around a corner. E.g. consider a FAST corner which is a light spot on a black background. If the profile through the spot looks something like
0 0 0 0 200 255 200 0 0 0
then FAST strength will be high on the pixels with values 200 and 255. Nonmaximal suppression removes all but the highest ones in a small region, so only the corner centred on 255 will be kept.
You usually want nonmaximal suppression because the non-maximal corners tend to provide little or no extra information and tend to be less stable.
It will depend on your application though. If in doubt, try both and see which works better.
In FAST-9 you are detecting for a segment of at least 9 contiguous pixels. You also published a machine learned FAST-ER detector, and I was interested to see what your training arrived at (in terms of the decision tree). In other words, I’m quite curious as to what specifically makes it a more repeatable detector compared to FAST-9, and if there is an equivalent intuitive way of describing it (such as 9 contiguous pixels of different intensity around the circumference compared to the centre pixel).
You can download the decision tree in the FAST-ER source code distribution and take a look. The tree is very large however. I do not believe that there is an obvious intuitive explanation as to how it works. I think decision trees are much like other machine learning systems (SVMs, Neural Networks) in that they essentially create a black box which partitions up the high dimensional space of inputs.
I would like to impliment FAST code in C# .Net 4.0, is the the datastructure for input image same or will need any sort of conversion ?
There are several ways you can go about implementing it in C#. If you can use some unmanaged code, then you may be able to link against the pure C implementation as-is.
Probably a better choice it to generate some native C# code. The FAST-ER source code comes with some ready-made trees in a language neutral format, and some scripts to turn the code into C, C++, MATLAB and Python. It should be straigtforward to modify one of the scripts to generate C# code instead.
The scripts are written in a mixture of GAWK and BASH. Since you’re using C#, you’re probably using Windows: you can get GAWK and BASH for Windows from either the Cygwin or MINGW projects.
It is should be easy to rewrite the scripts in another language. The language neutral trees are in a very simple format designed for easy conversion to new languages. The conversion can be sone by simple textual search and replace, since the trees are essentially a list of if-else statemets.
In your code(ex. fast_9.cpp), the decision tree has already been conerted into C-code. It is a very long string of nested if-then-else statements. How can I make it?? What’s the machine learning?? Please explain the process to me.
It depends if you want to create code from a tree, or make a whole new tree.
Either way, you will want the FAST-ER source code.
Pre-made trees which are not yet converted into code are available. Look for the file “FAST_trees.tar.bz2″ and untar it. The raw (unconverted) trees have the suffix
.ftree. They contain trees in a language neutral format which should be easy to convert into source code using your language of choice. I’ve used shell scripts to perform the conversion. See fast_tree_to_CXX as an example.If you want to make your own trees from scratch, then you need to use the
learn_fast_treeprogram. That takes as input a list of extracted features. You can generate all features for fast-N usingfast_N_featuresto ensure your tree is exact. I have a program to extract fast-N features from images, but it isn’t currently in the distribution. Let me know if you need it and I will add it.Let me know if you need any more information.
You consider points which are approximately 3 pixels away from the point being tested to find out if its a feature or not. Will the radius of 3pixels work for all image sizes or we need to change it based on the image size.
The radius you need depends on the scale of the features, rather than the size of the image. If the features are very blurry, then you will need a bigger ring. The easiest and most efficient way to do this is to subsample the image, e.g. by taking 2×2 squares, and averaging the pixels inside to make a single output pixel.
I just ported FAST12 to Java for my Master’s thesis. I have a question though.. Do we have to convert the input image to grayscale before running FAST on it, or can we do it on a coloured image by checking each channel separately?
Thanks.
So far, I have only used FAST on greyscale images. The proper way is to convert to grey by using the CIE weightings. The easiest/quickest way is to use the green channel, which is not a bad approximation of the CIE weightings.
It is possible to run it on every channel separately, but the colour reproduction on most cameras is quite poor and is heavily biased in favour of green, anyway.
Would you be interested in releasing the Java code? I can make it available on the FAST page if you are interested.
Hi,
Thanks for your response. I will look into CIE weightings.
I am interested to release the code but it is not very mature yet and it lacks the non-maximal suppression step. When it is fully ported and optimised, I will send you an email about it. Is that ok?
Alex
There is some non-maximal suppression code packaged with the FAST corner detector. It should port to Java relatively easily because almost all of the work is done using array indices, rather than pointers.
I would really be interested in the Java code. I am building an open source image feature extraction library in java.
Thanks!
Hi,
In the “Fusing Points and Lines for High Performance Tracking” paper, you mentioned that the test to check “if the intensities of 12 contiguous pixels are all above or all below the intensity of the center pixel can be optimized by examining pixels 1 , 9 , 5 and 13″ However the auto-generated code does not implement this optimization. I was just wondering if there was reason behind that.
Regards
Guy
The ID3 algorithm is better at finding a good sequence of tests than I am. The four tests: 1,9,5, 13 are quite good, but there are better choices. Also, they only work for N=12. The ID3 algorithm is used to automatically learn an ordering of the tests.
There is a visualisation of the tests in the following presentation:
http://mi.eng.cam.ac.uk/~er258/work/rosten_2008_faster_presentation.pdf
slides 40–52 show you the ordering of the tests, assuming that the pixels tested are all significantly brighter than the centre.
Slides 53-56 show what happens if the first pixel tested is too similar, or the first is bright but the second is too similar, or the first two are bright and the third is too similar, etc…
Is the python code released on 2010-09-17 a learned detector? Or do I have to train this first? I read that you have leanred FAST detectors but am unsure which ones to download.
Thanks
The python code released on 2010-09-17 is a learned detector and should be ready to use as-is.
Any file with a name like fast-X-src.tar.gz or fast-X-src.zip is a learned detector which is ready to use.
The learning code is in fast-er-1.4.tar.gz, which also contains ready made detectors.
Thanks for your fast reply
, and excuse my noob question!
Is there an example of using the FAST corner detection using python? I ran the fast9.py with a image opened by OpenCV 2.2 in python and it took a good few minutes to run? Below is a simple code
import cv
import fast9 as fast
greyimg = cv.imread(‘Capture.PNG’,2)
corners = fast.detect(greyimg,30,1)
print len(corners), “points found”
cv.waitKey(0)
It looks like you’ve used it correctly.
Currently FAST in python is implemented in pure python, so it will be very slow, since python is rather slow at loops compared to C.
One option is to use cython instead of python. I think that it will be a question of adding a few cdef’s to the FAST python code. If you get that working, please let me know, and I’ll add it to the source code.
Another option is to use the FAST detector which is now in OpenCV.
The only problem is that there does not seem to be a python version of the FAST detector in OpenCV 2.2. I will investigate cython and let you know if I can work it out.
Is there an example of using the FAST corner detection using python? I ran the fast9.py with a image opened by OpenCV 2.2 in python and it took a good few minutes to run? Below is a simple code
import cv
import fast9 as fast
greyimg = cv.imread(‘Capture.PNG’,2)
corners = fast.detect(greyimg,30,1)
print len(corners), “points found”
cv.waitKey(0)
The Python code implements the FAST algorithm, but it won’t run especially quickly, because python is much less efficient compared to a compiled language for this type of code.
If you want the corder detection to run quickly then you will need to use a compiled language. I expect the simplest way to do that is to convert the python code into Pyrex by putting cdef’s in front of the loop indices.
IS it possible to use FAST Features for hand shape classification?
If there is a hand shape classification algorithm which uses corners then you could probably replace the corner detector with FAST. However, FAST will only make up a small part (if any) of a hand shape classification algorithm.
Hello, I see that FAST has been recently added to OpenCV but unfortunately I can’t find any documentation on how to use it! When you merged the code, did you add a sample program too? If so – I would like to know the name! If not could you send me some code or alternatively, point me in the right direction on how to use this magical tool?
Thanks for all your hard work … you truly are a wizard,
Josh
There is a sample program in the OpenCV tests directory:
tests/cv/src/fast.cpp
which makes use of the FAST detector. This is different from the test program I submitted, since the submitted code matches the OpenCV 1.x style but the OpenCV authors updated the FAST code to match the rather better OpenCV 2.x style.
Thanks for this! Tis exactly what I needed.
Can I get the revised version of fast corner detection algorithm, which uses only 3×3 mask?
-1 0 1
-1 0 1
-1 0 1
I tried to change your source code, but that was very difficult to do that
P.S I’m using MATLAB
I’m not entirely sure I understand the question. What would a corner look like?
You won’t be able to modify the FAST code, since it is machine generated. However, it is possible generate your own code by training FAST for different mask sizes.
Hi, I have noticed the FAST iPhone app by Success Software Solutions. Has this code been integrated into other apps or other commercial uses? Are there any restrictions on doing so?
The FAST corner detector has certainly been used in a number of commercial ventures. The FAST detector itself is available under the BSD license which places no restrictions on usage. Licensing details of the Success Labs port are available on the Success Labs page.
Hi,
I am testing the source code of iPhone corner detection app. I use Xcode 4.2 and get the corner points as an output. I would like to have the image + the dots but could not figure how to do that!! (in other words, the option “Camera” is always off!!). Can you help in that?
Thanks
MJ
The iPhone app is provided by successlabs, so I can’t offer any advice on getting it to work.
Dear Dr. Edrosten ,
Nice to see you, Edrosten . I am a graduate student in Taiwan.
I am appreciated deeply for your wonderful method, FAST.
I tried the Matlab version. It is good.
But now, I have to implement my method including FAST in C++.
Therefore, I call the FAST in the OpenCV library.
But the augment is so hard to understand. Do you have some example code?
I am eager for the help. Thanks so much.
I hope it is not to disturb you.
Best Regards,
————————————–
潘 志 宏 (Peter Pan)Chih-Hung Pan
The function prototype is:
void FAST(const Mat& image, vector& keypoints, int threshold, bool nonmaxSupression=true)You need to provide an OpenCV image (for instance loaded from a file) as the first argument.
The second argument returns the list of detected KeyPoint structs.
For the threshold, you will need to pick a number that gives a reasonable number of corners (eg 500-2000 for a 640×480 image). This will depend on the type of image. For a video, it may be as low as 20, for a high contrast photograph, perhaps as high as 100.
Hi, I am interested in FAST-ER
I run ‘./configure && make’ in fast-er-1.4, but I got the error message:
checking libCVD… yes
checking for dgetri_ in -lcvd… no
configure: error: libCVD must be compiled with lapack support.
Can you help me?
Do you have the LAPACK development libraries installed on your machine? If so, libCVD should pick them out automatically. Try the following:
1. Check the configure output from libcvd. If it doesn’t find LAPACK, then install the LAPACK development libraries.
2. Check the built libcvd using ldd /usr/local/lib/libcvd.so and see if it has a reference to lapack. If it’s not there, then there libCVD has failed to pick up lapack properly. If 1 is OK and 2 isn’t, then let me know.
3. As a workaround, run export LDFLAGS=-llapack before running ./configure to get LAPACK manually.
Hi,
I’m running into the same problem when compiling FAST-ER. I have liblapack-dev installed via Ubuntu’s package manager, but I’ve also tried installing lapack manually and exporting the LDFLAGS variable.
I get this when configuring libCVD:
checking if Accelerate framework is needed for LAPACK…
checking for dgesvd_… no
checking for dgesvd_ in -llapack… yes
so I guess it is finding the lapack library. But later, ldd libcvd.so doesn’t return any link to liblapack.
In the end, I get the same error than Kang. Any clue? Thanks!
Hi,
I also meet this problem and do not know how to fix it? I already install the liblapack but I do not know why ldd libcvd.so doesn’t return any links related to liblapack.
OS: Ubuntu 12.4
libCVD: libcvd-20120202
First, I must express my appreciation for this algorithm. It truly is fast: average execution time of 20ms for a 800×480 image on a modern smartphone and it doesn’t even need a binarized image.
Questions:
1. Does FAST store the type of corner it finds? Outer corners (where majority of pixels are bright) versus inner corners (where majority of pixels are dark). If it does store this, can this be accessed in the OpenCV version? If it doesn’t store this, would it be a significant change for someone without prior knowledge of the FAST code (i.e. myself) to make?
2. In the KeyPoint structure returned from FAST feature detection, there are a number of fields, but the only one that changes besides the location is “response”. Can you tell me what the value of this field means in the context of FAST? The values were larger for corners farther from the camera, and the range (in my tests) was 10 to 30.
Thank you.
1. FAST doesn’t currently store the type of corner. It is certainly possible, though the current code isn’t set up to do it. I think it would be possible as a hack by post-processing the FAST trees. There are copies of the trees in the fast-er codebase which are designed to make postprocessing as easy as possible.
Probably the easiest way is to examine the ring of 16 pixels after detecting the corner. Count the number of pixels >= corner+threshold and the number of pixels <=corner-threshold. One will dominate (since it is a corner) and that will tell you which type it is. The cost should be tiny compared to the cost of doing corner detection.
2. The response is the highest threshold at which the points are still detected as corners. Ones with a higher response are stronger in that they will likely be detected more reliably under adverse conditions.
Hey
I just wanted to tell you that you are my life saver. I just used your code for my final year project and it works like a charm. Actually I was on the verge of failing my project and was very worried about it until I saw your code. Thanks a lot. :’)
But the thing is, I do not understand the program at all. At least, could you give me the gist of what the code actually does? Because I have to explain it in my report and also to my professor.
Your help is greatly appreciated!
Vinny
I’m glad it was so helpful.
The code is almost impossible to read because it is machine generated.
What it does is tell you if there is a contiguous arc of 9 or more pixels which are either all much brighter or all much darker than the centre pixel.
Instead of looking at pixels in the circle in sequence, the program uses a decision tree in order to reject non-corners as quickly as possible.
By the way , with regards to the my above message, I am referring to FAST version 1.
Thanks
Vinny
Phenomenal algorithm.
I’m trying to compile the faster.cc decision tree. Any estimate on how long the compile is ‘supposed’ to take? I started the compile awhile ago and still waiting for it to finish (been a few hours now). Just want to make sure it didn’t hang up on me.
Thanks!
and a follow up on this: The compiler was indeed hung up. Turns out the FAST-ER decision tree is much too large for the arm7 compiler. It gets a branch out of range error. If there is any options to help fix this I’d appreciate it, but I’m suspecting the architecture just can’t handle it.
There’s no direct way that I know of to solve the problem. My suggestion is that you try FAST-ER on a PC to see if the extra complexity is worth the effort. It is possible to run an interpreted version of FAST-ER, but it’s probably under 1/10 of the speed.
Hi Mr. Roston
Indeed I return on the descriptor of the points detected by FAST, is there someting new on the extraction of a reliable descriptor? The proposal made at the beginning (take the neighborhood pixels 11 x 11 as a descriptor vector) is likely to be of low robustness against the usual changes (rotation, brightness, change of scale). Is it possible to used the quarter arc of the circle (16 pixels) to calculate the difference with the intensity of the colors between this arc the rest of the circle.
Thanks for your engagement
I’m not entirely sure I follow the suggestion.
A number of people have had good success extracting SIFT-like features from FAST keypoints.
If you want to determine the orientation of a patch, this paper: http://www.bmva.org/bmvc/2009/Papers/Paper322/Paper322.html contains a simple and efficient method.
Just curious… I’ve observed in the paper that when considering pixels in the circle the test order goes darker-similar-brighter while in the implementation provided goes brighter-darker-similar. Does it make any difference at all? Thanks!
I don’t think it would make any difference, unless your data contains one corner type very prominently compared to others.
Hello Dr. Roston,
Actually I need to use Fast detector on OpenCV and I want to extract my own descriptor using 16 pixels ring which is used by Fast while each interest point is being detected. I need to do this in an efficient way indeed. In addition I don’t have access to .cpp file in opencv but just .hpp file.
Your help would be much appreciated on how I can make this change and define my own descriptor.
Thanks
The cpp files should be in the OpenCV distribution. You can download this from the OpenCV website. Alternatively, you can get the source code for FAST from the FAST web site.
The FAST code gives you an array of x-y locations. You can simply copy the 16 pixels around each x-y location into a 16 element array to form your descriptor. A description of the offsets you need for the 16 pixels is in the paper and source code of FAST.
Hi, and thanks for this very nice algorithm.
My questions are mainly on the construction of the decision tree from the training images.
1. The minimization of the entropy function is used only for creating the decision tree?
2. Does the training set needs to be annotated? (I guess not, since all 16 pixels are checked)
3. I assume that with very few training samples (corners), a very simple decision tree will be created. When new corners are trained, how is the tree expanded? (maybe the answer is in the paper, I haven’t been able to figure it out yet)
Thanks.
To answer your questions:
I actually use a combination of both methods. I generate all possible corners to get a complete coverage of the data. I then extract corners and non corners from a number of images, so that the pixel statistics are represented in the detector.
Bear in mind that when it gets as far as training, the pixels are either b (brighter), d (darker) or s (similar) relative to the centre, so corner candidates can be thought of as a list of 16 elements like
bsdbbddbsdbsbdsbThere is program in the FAST-ER distribution to generate exactly one of each type of corner and non-corner, along with the classification.
Pingback: match corners between images « Firefly's space
I always used to study article in news papers but now as I am
a user of web therefore from now I am using net for posts, thanks to web.
Hi! (My comment is rather long… sorry)
I’m writing my Master Thesis in Computer Science and I have several questions about the precompiled program and the source codes you provide in the website, I’ve been studying your paper and code for several weeks now.
My thesis is about reproducing the behaviour of the FAST algorithm in Hardware synthesis (using an FPGA) in order to accelerate and parallelize the basic operation: decide whether a pixel p is a feature or not.
Here are my questions, given the same image, threshold and same points fast with nonmaximal suppression:
- Your C source code displays a result set “A”.
- Your Python source code displays a different* result set “B”.
- Your precompiled program (Linux_x86-64) displays a different* result set “C”.
- My conceptual implementation in C (which is a parallel implementation of the Hardware architecture concept) displays sometimes (small images) a result set “C” as the precompiled and sometimes (big images) a different* result set “D”.
* when I say here “different” or “differences” I refer to the number of features detected, but every result set shows the same pattern in big images.
So, all the result sets are close between them, but they’re not the same for the same image…
Another questions I have is about the C source code, regarding timings:
I’ve prepared a main function to launch fast9 function and mine in order to measure times on them and I found something rather weird: if I test both functions with a small raw matrix of bytes (100 bytes, a 10×10 pixel grayscale image) hard coded on the source, fast9 function has a time T1 and my function a time T2, 4 times faster than T1.
BUT if I test both functions with the same 10×10 grayscale image read from a file and stored dynamically with malloc calls, my function still reports a T2 execution time (approx) but fast9 has a time T3 of the same order as T2 and sometimes faster than T2… why is this happening if the source code is the same, the image is the same… the only difference is the use of static or dynamic memory.
I hope I explained myself clearly enough, that these are not too many questions and that you have the time to answer me soon.
Thanks so much in advance for your time.
There are a number of reasons for the differences:
The precompiled binary uses an old version of the algorithm. The old version is not quite exact (incomplete coverage of data). Also, it uses a rather ad-hoc method for scoring which will affect the nonmaximal suppression.
I haven’t thoroughly tested the Python source code, but it seemed bug free. The C code from version 2 onwards should be correct. You could try doing a diff on the feature sets to see what the differences are.
That’s a very strange result about the static and dynamic memory. A 10×10 image is very small. Have you tried it on something much larger (e.g. 1000×1000) to see if the results are similar in nature?
Please can you tell me how exactly to run the C code in Eclipse!! I’m in a bit of tight spot and really need this code to run!
I’m not familiar with eclipse, but it’s standard C code so you should just be able to add it and have it compile. Once it’s added you just need to supply a pointer to the image data and the image size.