为什么OPENCV中Fast算法检测到的角点和我自己实现的不一样？

Question

我已经使用 C++ boost 算法实现了一个简单的 FAST 角点检测器。目前它没有非最大抑制。我运行我的实现和下面这张照片上的 OPENCV 实现

OPENCV的输出是

我的实施输出是

这是我的代码

#include <bits/stdc++.h>
#include <boost/gil.hpp>
#include <boost/gil/extension/io/jpeg.hpp>
#include <boost/gil/extension/io/png.hpp>
#include <boost/gil/image_processing/circle.hpp>
namespace gil = boost::gil;
template <typename T, typename U>
bool FastCornerDetector(const T& buffer, int r, int c, std::vector<U> points,
                        int t = 20) {
    int valid_points_count = 16;
    for (auto& u :
         points) // checking whether all the 16 points lie within the image
    {
        if (u[1] + r >= buffer.height() || u[0] + c >= buffer.width()) {
            return false;
        } else if (u[1] + r < 0 || u[0] + c < 0) {
            return false;
        } else {
            u += gil::point_t(c, r);
        }
    }

    int threshold_indicator[16], index = -1;
    memset(threshold_indicator, -1, sizeof(threshold_indicator));
    // marking the pixel value of every pixel as >I_p+t or <I_p-t or between
    // these two
    for (const auto& point : points) {
        if (buffer(point) < buffer(gil::point_t(c, r)) - t) {
            threshold_indicator[++index] = -1;
        } else if (buffer(point) > buffer(gil::point_t(c, r)) + t) {
            threshold_indicator[++index] = 1;
        } else {
            threshold_indicator[++index] = 0;
        }
    }

    bool is_feature_point = false;
    // threshold check for n=9 consecutive points. I am not doing the speed test
    std::ptrdiff_t count = 0;
    for (int i = 0; i < 25; i++) {
        if (threshold_indicator[i] == -1) {
            if (++count > 8) {
                is_feature_point = true;
                break;
            }
        } else
            count = 0;
    }

    if (!is_feature_point) {
        count = 0;
        for (int i = 0; i < 25; i++) {
            if (threshold_indicator[i] == 1) {
                if (++count > 8) {
                    is_feature_point = true;
                    break;
                }
            } else
                count = 0;
        }
    }
    return is_feature_point;
}

int main() {
    const std::ptrdiff_t radius = 3;
    const auto rasterizer       = gil::midpoint_circle_rasterizer{};
    int number_of_points        = rasterizer.point_count(radius);
    std::vector<gil::point_t> circle_points(number_of_points);
    rasterizer(radius, {0, 0}, circle_points.begin());

    auto cmp = [](const auto& a, const auto& b) {
        return a[0] < b[0] || a[1] < b[1];
    };
    std::set<gil::point_t, decltype(cmp)> s(cmp);
    for (const auto& point : circle_points) {
        s.insert(point);
    }

    // std::cout<<s.size()<<std::endl;
    std::vector<gil::point_t> points_clockwise[4];
    for (const auto& point : s) {
        if (point[1] > 0 && point[0] >= 0) {
            points_clockwise[0].push_back(point);
        } else if (point[1] <= 0 && point[0] > 0) {
            points_clockwise[1].push_back(point);
        } else if (point[1] < 0 && point[0] <= 0) {
            points_clockwise[2].push_back(point);
        } else if (point[1] >= 0 && point[0] < 0) {
            points_clockwise[3].push_back(point);
        }
    }

    std::sort(points_clockwise[0].begin(), points_clockwise[0].end(),
              [](const auto& a, const auto& b) -> bool {
                  if (a[1] == b[1])
                      return a[0] < b[0];
                  return a[1] > b[1];
              });

    std::sort(points_clockwise[1].begin(), points_clockwise[1].end(),
              [](const auto& a, const auto& b) -> bool {
                  if (a[1] == b[1])
                      return a[0] > b[0];
                  return a[1] > b[1];
              });

    std::sort(points_clockwise[2].begin(), points_clockwise[2].end(),
              [](const auto& a, const auto& b) -> bool {
                  if (a[1] == b[1])
                      return a[0] > b[0];
                  return a[1] < b[1];
              });

    std::sort(points_clockwise[3].begin(), points_clockwise[3].end(),
              [](const auto& a, const auto& b) -> bool {
                  if (a[1] == b[1])
                      return a[0] < b[0];
                  return a[1] < b[1];
              });

    std::vector<gil::point_t> final_points_clockwise;

    // all the 16 points on the circumference of the circle are present in
    // clockwise format in final_points_clockwise
    final_points_clockwise.insert(final_points_clockwise.end(),
                                  points_clockwise[0].begin(),
                                  points_clockwise[0].end());
    final_points_clockwise.insert(final_points_clockwise.end(),
                                  points_clockwise[1].begin(),
                                  points_clockwise[1].end());
    final_points_clockwise.insert(final_points_clockwise.end(),
                                  points_clockwise[2].begin(),
                                  points_clockwise[2].end());
    final_points_clockwise.insert(final_points_clockwise.end(),
                                  points_clockwise[3].begin(),
                                  points_clockwise[3].end());

    gil::gray8_image_t input_image;
    gil::rgb8_image_t input_color_image;
    gil::rgb8_view_t input_color_image_view;
    gil::read_image("box_image.png", input_image, gil::png_tag{});
    gil::read_image("box.jpg", input_color_image, gil::jpeg_tag{});
    input_color_image_view = gil::view(input_color_image);
    auto input_image_view =
        gil::color_converted_view<gil::gray8_pixel_t>(gil::view(input_image));
    s.clear();
    for (int i = 0; i < input_image_view.height(); i++) {
        for (int j = 0; j < input_image_view.width(); j++) {
            if (FastCornerDetector(input_image_view, i, j,
                                   final_points_clockwise)) {
                // if it is a corner draw a circle against it
                for (auto u : final_points_clockwise) {
                    input_color_image_view(u + gil::point_t(j, i)) =
                        gil::rgb8_pixel_t(0, 255, 0);
                }
            }
        }
    }

    gil::write_view("Fast_Output.jpeg", input_color_image_view,
                    gil::jpeg_tag{});
}

我没有使用速度测试和非最大抑制，但我不认为这是角落后面没有被检测到的原因。正如我验证的那样，在我的代码中计算出的半径为 3 的 bresenham 圆的坐标是正确的。我找不到输出不同的原因。为什么在我的输出中检测到的角点较少？两种情况下的阈值都设置为 20。请，如果有人可以帮助我...

Answer 1

我无法编译你的代码。我只能发现一些随机的东西，它们可能会帮助你解决问题：

你的 threshold_indicator 数组是十六个元素，但是你的循环转到索引 24 这将导致 Undefined Behaviour （除非循环顺便说一下 breaks 之前点)
valid_points_count 未使用，但正在初始化为幻数

您可以通过减少重复自己来减少大量代码。例如，您的下一位代码需要 45 行代码。那是 >4 倍。

std::vector<gil::point_t> final_points_clockwise;
for (auto& pc : points_clockwise) {
    std::sort(pc.begin(), pc.end(),
              [](const auto& a, const auto& b) -> bool {
                  if (a[1] == b[1])
                      return a[0] < b[0];
                  return a[1] > b[1];
              });
    final_points_clockwise.insert(final_points_clockwise.end(), pc.begin(),
                                  pc.end());
}
// all the 16 points on the circumference of the circle are present in
// clockwise format in final_points_clockwise

In fact, further down it becomes just

 std::vector<gil::point_t> final_cw;
 for (auto& pc : points_clockwise) {
       std::sort(pc.begin(), pc.end(), ClockwiseCmp{});
       final_cw.insert(final_cw.end(), pc.begin(), pc.end());
 }

同理，所有

std::ptrdiff_t count = 0;
for (int i = 0; i < 25; i++) {
    if (threshold_indicator[i] == -1) {
        if (++count > 8) {
            is_feature_point = true;
            break;
        }
    } else
        count = 0;
}
if (!is_feature_point) {
    count = 0;
    for (int i = 0; i < 25; i++) {
        if (threshold_indicator[i] == 1) {
            if (++count > 8) {
                is_feature_point = true;
                break;
            }
        } else
            count = 0;
    }
}
return is_feature_point;

可以替换为

bool is_feature_point =
    indicator.end() != std::search_n(indicator.begin(), indicator.end(), 8, -1) ||
    indicator.end() != std::search_n(indicator.begin(), indicator.end(), 8, 1);

这立即消除了初始化指标数组的需要和循环索引超出指标大小的问题。

事实上我可能会把整个FastCornerDetector写成

template <typename T, typename U>
bool FastCornerDetector(T const& buffer, int r, int c,
                        std::vector<U> points, int t = 20)
{
    assert(points.size() == 16);

    if (std::any_of(points.begin(), points.end(), [&](auto& u) {
            u += gil::point_t(c, r);
            return (u[1] >= buffer.height() || u[0] >= buffer.width()) ||
                (u[1] < 0 || u[0] < 0);
        })) {
        return false;
    }

    // marking every pixel as >I_p+t or <I_p-t
    auto const I_p = buffer(gil::point_t(c, r));

    std::vector<int> indicator;
    std::transform(
        points.begin(), points.end(), back_inserter(indicator),
        [&buffer, low = I_p - t, hi = I_p + t](auto const& point) {
            if (buffer(point) < low)     return -1;
            else if (buffer(point) > hi) return 1;
            else                         return 0;
        });

    bool is_feature_point =
        indicator.end() != std::search_n(indicator.begin(), indicator.end(), 8, -1) ||
        indicator.end() != std::search_n(indicator.begin(), indicator.end(), 8, 1);
    return is_feature_point;
}

那是

不到代码行数的一半
可读性提高一倍以上¹
更不容易出错，因为
- 无手动（循环）索引
- 没有神奇的数字
更容易维护；例如现在很容易将特征点标准改写为其他东西

这个比较看起来很破：

auto cmp = [](const auto& a, const auto& b) {
    return a[0] < b[0] || a[1] < b[1];
};

我希望

auto cmp = [](const auto& a, const auto& b) {
    if (a[0] < b[0])  return true;
    if (a[0] == b[0]) return a[1] < b[1];
    return false;
};

或者，您知道，不太容易出错：

auto cmp = [](const auto& a, const auto& b) {
    return std::tie(a[0], a[1]) < std::tie(b[0], b[1]);
};

事实上我可能会定义它 out-of-line:

并且由于您不需要事先知道光栅化点的数量，并且除了填充 set 之外永远不要使用 circle_points 矢量，为什么不只是

constexpr std::ptrdiff_t radius = 3;
auto const rasterizer = gil::midpoint_circle_rasterizer{};

std::set<gil::point_t, PointCmp> s;
rasterizer(radius, {0, 0}, inserter(s, s.end()));

试图简化点分离：

std::vector<gil::point_t> points_clockwise[4];
for (const auto& point : s) {
    auto index = 0;
    if (false);
    else if (point[1] >  0 && point[0] >= 0) { index = 0; }
    else if (point[1] <= 0 && point[0] >  0) { index = 1; }
    else if (point[1] <  0 && point[0] <= 0) { index = 2; }
    else if (point[1] >= 0 && point[0] <  0) { index = 3; }
    points_clockwise[index].push_back(point);
}

让我怀疑不一致（？）边界处理是否是故意的。我假设它可能是。我的几何感不是很好

（逆）时针排序看起来很有趣。它是如何工作的？我没有在互联网上找到任何不从角度来实现这一目标的代码。无论如何，您至少可以使用上面的技巧 (proof of quivalence):

再次将代码重构为等效的比较器

struct ClockwiseCmp {
    bool operator()(gil::point_t const& a, gil::point_t const& b) const {
        return std::make_tuple(-a[1], a[0]) < std::make_tuple(-b[1], b[0]);
    }
};

std::vector<gil::point_t> final_cw;
for (auto& pc : points_clockwise) {
    std::sort(pc.begin(), pc.end(), ClockwiseCmp{});
    final_cw.insert(final_cw.end(), pc.begin(), pc.end());
}

上市

完全reviewed/refactored上市。请注意，由于缺少 GIL headers.

，我无法运行任何代码

"Live" On Compiler Explorer

#include <boost/gil.hpp>
#include <boost/gil/extension/io/jpeg.hpp>
#include <boost/gil/extension/io/png.hpp>
#include <set>

#if 0
    #include <boost/gil/image_processing/circle.hpp>
#else
    namespace boost::gil { // mockups to satisfy the compiler
        struct midpoint_circle_rasterizer{
            void operator()(ptrdiff_t, gil::point_t, auto iterator) const {}
        };
    }
#endif

namespace gil = boost::gil;

namespace /*file static*/ {
    template <typename T, typename U>
    bool FastCornerDetector(T const& buffer, int r, int c,
                            std::vector<U> points, int t = 20)
    {
        assert(points.size() == 16);

        if (std::any_of(points.begin(), points.end(), [&](auto& u) {
                u += gil::point_t(c, r);
                return (u[1] >= buffer.height() || u[0] >= buffer.width()) ||
                    (u[1] < 0 || u[0] < 0);
            })) {
            return false;
        }

        // marking every pixel as >I_p+t or <I_p-t
        auto const I_p = buffer(gil::point_t(c, r));

        std::vector<int> indicator;
        std::transform(
            points.begin(), points.end(), back_inserter(indicator),
            [&buffer, low = I_p - t, hi = I_p + t](auto const& point) {
                if (buffer(point) < low)     return -1;
                else if (buffer(point) > hi) return 1;
                else                         return 0;
            });

        bool is_feature_point =
            indicator.end() != std::search_n(indicator.begin(), indicator.end(), 8, -1) ||
            indicator.end() != std::search_n(indicator.begin(), indicator.end(), 8, 1);
        return is_feature_point;
    }

    struct PointCmp {
        bool operator()(const gil::point_t& a, const gil::point_t& b) const {
            return std::tie(a[0], a[1]) < std::tie(b[0], b[1]);
        }
    };

    struct ClockwiseCmp {
        bool operator()(gil::point_t const& a, gil::point_t const& b) const {
            return std::make_tuple(-a[1], a[0]) < std::make_tuple(-b[1], b[0]);
        }
    };
} // namespace

int main() {
    constexpr std::ptrdiff_t radius = 3;
    auto const rasterizer = gil::midpoint_circle_rasterizer{};

    std::set<gil::point_t, PointCmp> s;
    rasterizer(radius, {0, 0}, inserter(s, s.end()));

    // std::cout<<s.size()<<std::endl;
    std::vector<gil::point_t> points_clockwise[4];
#if 0 // old boundary spellings:
    for (const auto& point : s) {
        auto index = 0;
        if (false);
        else if (point[1] >  0 && point[0] >= 0) { index = 0; }
        else if (point[1] <= 0 && point[0] >  0) { index = 1; }
        else if (point[1] <  0 && point[0] <= 0) { index = 2; }
        else if (point[1] >= 0 && point[0] <  0) { index = 3; }
        points_clockwise[index].push_back(point);
    }
#else // unified version (UNTESTED):
    for (const auto& point : s) {
        bool const a = point[0] < 0;
        bool const b = point[1] > 0;

        auto index = 0;
            if (!a &&  b) { index = 0; }
        else if (!a && !b) { index = 1; }
        else if ( a && !b) { index = 2; }
        else if ( a &&  b) { index = 3; }
        points_clockwise[index].push_back(point);
    }
#endif

    std::vector<gil::point_t> final_cw;
    for (auto& pc : points_clockwise) {
        std::sort(pc.begin(), pc.end(), ClockwiseCmp{});
        final_cw.insert(final_cw.end(), pc.begin(), pc.end());
    }
    // all the 16 points on the circumference of the circle are present in
    // clockwise format in final_cw

    gil::gray8_image_t input_image;
    gil::rgb8_image_t  input_color_image;
    gil::rgb8_view_t   input_color_image_view;

    gil::read_image("box_image.png", input_image, gil::png_tag{});
    gil::read_image("box.jpg", input_color_image, gil::jpeg_tag{});

    input_color_image_view = gil::view(input_color_image);
    auto input_image_view =
        gil::color_converted_view<gil::gray8_pixel_t>(gil::view(input_image));

    for (int i = 0; i < input_image_view.height(); i++) {
        for (int j = 0; j < input_image_view.width(); j++) {
            if (FastCornerDetector(input_image_view, i, j, final_cw)) {
                // if it is a corner draw a circle against it
                for (auto& u : final_cw) {
                    input_color_image_view(u + gil::point_t(j, i)) =
                        gil::rgb8_pixel_t(0, 255, 0);
                }
            }
        }
    }
    gil::write_view("Fast_Output.jpeg", input_color_image_view,
                    gil::jpeg_tag{});
}

¹ (citation needed)

为什么OPENCV中Fast算法检测到的角点和我自己实现的不一样？

Why the corners detected by Fast algorithm in OPENCV and my own implementation are not same?

c++

boost

opencv

gil

上市