FAST detector giving wrong results

[cayv]

I implemented my own version of the FAST detector and decided to compare my results to Images.jl's implementation. They were very different, so I created a test image for debugging. After manual analysis of the pixels, I'm convinced that Images.jl's implementation is wrong.

The test image contains only white, black, and gray 50% pixels. You can see the detected corner pixels in red, while in green is the continuous circle around one of the pixels that was wrongly detected by Images.jl as a corner. You can count that there are only 9 green pixels, when only 12 or more green pixels should be detected as a corner.

I did not bother to find out what is wrong with Images.jl's source code. My implementation is a bit faster and uses less memory.

(Performance results for "lighthouse" from TestImages.jl)

Should I open a PR with my code? I can modify it so that the API is the same as the current implementation.

[johnnychen94]

Yes please open a PR for this by all means!

I can modify it so that the API is the same as the current implementation.

This isn't really my field, but it would be reasonable to revisit the API in this case and deprecate the legacy ones.

The name fastcorners doesn't sound good according to the style guide #767, I would suggest a new implementation in perhaps ImageFeatures and deprecate the old one in Images.jl.

[timholy]

I'm not an expert here either. I agree with @johnnychen94; a lot of this code was written in early Julia history (v0.4?) and so I'm all in favor of someone coming in and refreshing things a bit.

[cayv]

Well, I'm very new to Julia (started learning this week), so I'm going to need some help here. I've further optimized the code and now it's faster proportionally to image size. It's over 100% faster than the current implementation for large images. I've also added the n parameter to keep API compatibility even though the original paper uses a fixed value of 12. It has no performance impact, so I guess we might as well have it.

I'm still in doubt about the function name. I think fast would be fine, but the style guide says it should be a verb. Another problem is that sometimes people expect to also get the corners' descriptors and that would have a profound performance impact due to the many allocations that would be necessary. I don't know what is the most idiomatic way in Julia to do that. Should I overload the function, add another parameter or create a separate function?

I agree that it should belong in ImageFeatures. I will try to create the PR in the next couple days.

[johnnychen94]

Here's the API we're using in some of the newly developed packages (ImageQualityIndexes, ImageBinarization, etc):

abstract type AbstractCornerDetector end

struct FAST <: AbstractCornerDetector
... # some FAST exclusive parameters
end

detector = FAST(...)
detect_corners(img, detector)  # dispatch to FAST implementation

This API design makes it super easy to add new potential corner detection methods. You can take a look at those packages and see how multiple algorithms are developed without interfering others.

Another problem is that sometimes people expect to also get the corners' descriptors and that would have a profound performance impact due to the many allocations that would be necessary.

Correct me if I'm wrong.

An intuitive but not preferred way to do this is:

corners = detect_corners(img, FAST(), require_descriptor=false)
corners, descriptors = detect_corners(img, FAST(), require_descriptor=true)

but this would hit an inference issue, for example, you'll hit something like this:

julia> using Test

julia> function detect_corners(img, detector, require_descriptor=false)
           # a toy case
           if require_descriptor
               return img, [1, 2, 3]
           else
               return img
           end
       end

julia> @inferred detect_corners(img, FAST());

julia> @inferred detect_corners(img, FAST(), require_descriptor=true);
ERROR: return type Tuple{Array{Float64,2},Array{Int64,1}} does not match inferred return type Union{Array{Float64,2}, Tuple{Array{Float64,2},Array{Int64,1}}}

julia> @btime detect_corners(img, FAST());
  1.419 ns (0 allocations: 0 bytes)

julia> @btime detect_corners(img, FAST(), true);
  67.387 ns (2 allocations: 144 bytes)

This is a smell of bad code and would slow the codes for a bit. I think Julia has involved a lot to optimize this case but I'm not sure.

Fortunately, most computer vision tasks are non-trivial and this inference issue won't cause much trouble in performance. Personally I think it would be acceptable. I think this fits the function barrier suggestion.

Another question is: where should this require_descriptor go? as an argument to the constructor of FAST, or as a keyword parameter to detect_corners. That's really implementation-dependent and I don't know which is the better option.

---

Speaking of the inference issue, there is actually a workaround (I don't think we need to tweak this so much but I'd like to mention the possibility here):

struct FAST{D} <: AbstractCornerDetector end
FAST(; need_descriptor=true) = need_descriptor ? FAST{true}() : Fast{false}()
detect_corners(img, detector::FAST{true}) = img, [1, 2, 3]
detect_corners(img, detector::FAST{false}) = img

This, however, doesn't have an inference issue, but I don't think we need it for "modern" Julia. As you can see, the benchmark shows they're almost "equivalent" (If you check @code_llvm you'll find out that this version has more concise IR representation):

julia> @btime detect_corners(img, FAST(; need_descriptor=false));
  1.419 ns (0 allocations: 0 bytes)

julia> @btime detect_corners(img, FAST(; need_descriptor=true));
  67.937 ns (2 allocations: 144 bytes)

julia> @inferred detect_corners(img, FAST(; need_descriptor=true));

julia> @inferred detect_corners(img, FAST(; need_descriptor=false));

IMO, this trick could be critical for the fundamental operations which are mostly in the inner loop, but for CV tasks it would be a bit of over-optimization.

[johnnychen94]

Also ping @zygmuntszpak here. I think he knows a lot of CV things 😃

[zygmuntszpak]

Thank you for taking the time to report this issue. I agree with Johhny's API suggestion since that is what we have been systematically doing as we refactor a lot of code. Interestingly, the corner detection and corner feature description are currently kept as two distinct processes in the ecosystem. It turns out that all the corner detection code actually lives in Images.jl, whereas the descriptors that one can associate with a corner are kept in ImageFeatures.jl. Given that we want to move functionality out of Images.jl we may want to have the corner detection in an ImageFeatures or even ImageCorners package.

I just read through a description of the fast corner detector and am still a little perplexed with the results you are obtaining.

Let us look at just the top-left hand grey pixel that is surrounded by a broken "circle" of pixels in your test image. Shouldn't just the grey pixel be flagged as a corner? I don't see why the current Images.jl method flags the points on the broken circle as corner candidates. Your implementation also flags some points on the circle as corner points.

Do you mind uploading the actual test image that you are currently using?

[cayv]

Here's the test image:

I was intrigued about the test results, too, as I designed the test so that only the left gray pixels would be detected as corners. However, it turns out my results are correct. Some of the black pixels are located in positions that do not "see" other black pixels due to the way how FAST works. The algorithm thinks they are surrounded only by white pixels and flags them as corners. This is unlikely to happen in real world cases though.

I will experiment with my code in my own project for a couple more days until I can decide on a final API and then I'll submit a PR for opinions.