4

我必须从一个

vector<cv::Point>

这是我的代码：

vector<cv::Point> contour;

...

Min = Point(640, 480) ;
Max = Point(0,0) ;
for (int j=0; j<(int)contour.size(); j++)
{
    if (contour[j].x < Min.x) Min.x = contour[j].x ;
    if (contour[j].y < Min.y) Min.y = contour[j].y ;
    if (contour[j].x > Max.x) Max.x = contour[j].x ;
    if (contour[j].y > Max.y) Max.y = contour[j].y ;
}

这工作正常。我使用 mimmax STL 开发了一个版本：

auto XminXmax = minmax_element(contour.begin(), contour.end(), [](Point p1,Point p2) {return p1.x < p2.x; });
auto YminYmax = minmax_element(contour.begin(), contour.end(), [](Point p1,Point p2) {return p1.y < p2.y; });
Point Min = Point((*XminXmax.first).x, (*YminYmax.first).y );
Point Max = Point((*XminXmax.second).x, (*YminYmax.second).y );

这也可以正常工作并给出相同的结果。然而，由于算法 minmax 被调用两次，因此执行时间是两倍。是否可以通过调用 minmax 算法来优化这一点？

4

2 回答 2

6

minmax_element对对象运行比较Point并将返回Point对象。

x和值是独立的y，很可能min(x)和min(y)将属于不同的对象。

我将for range用于这种特殊情况。

Min = Point(640, 480) ;
Max = Point(0,0) ;
for (auto &p : contour)
{
    Min.x = std::min(p.x, Min.x)
    Min.y = std::min(p.y, Min.y)
    Max.x = std::max(p.x, Max.x)
    Max.y = std::max(p.y, Max.y)
}
于 2016-03-11T11:21:51.257 回答
1

不，不可能通过单次调用来优化此问题，minmax_element因为minmax_element这不是解决此问题的最佳解决方案。

如果您坚持使用某些 STL 算法，请使用accumulate：

std::accumulate(begin(contour), end(contour), Bound{}, [](Bound acc, Point p)
{
    return Bound{minpos(acc.bottomleft, p), maxpos(acc.topright, p)};
});

但这需要一些准备工作：

#include <numeric>

struct Point
{
    int x;
    int y;

    Point(int x, int y)
        : x(x), y(y) {}
};

Point minpos(Point a, Point b)
{
    return {std::min(a.x, b.x), std::min(a.y, b.y)};
}

Point maxpos(Point a, Point b)
{
    return {std::max(a.x, b.x), std::max(a.y, b.y)};
}

struct Bound
{
    Point bottomleft;
    Point topright;

    Bound(Point bl = {640, 480}, Point tr = {0, 0})
        : bottomleft(bl), topright(tr) {}
};

accumulate将方法与 range for loop 方法进行比较，我们可以考虑两个方面：

  1. 可读性。accumulate方法稍微更好地表达了从几个点中收集单个边界框的意图。但这会导致代码稍长。
  2. 表现。对于这两种方法，gcc（5.3 和 6）生成几乎相同的代码。Clang 3.8 可以对循环范围进行矢量化，但不能为accumulate. 从 C++17 开始，我们将实现并行化 TS 标准化。算法的并行对应物，因此方法accumulate将允许更多的灵活性。reduceaccumulate/reduce

结论：两者accumulate/reduce都有一些（不利）优势。但可能一种完全不同的方法是最好的方法：如果cv::Point在 OP 中意味着您使用 openCV 库，那么同一个库具有boundingRect函数，它完全符合您想要实现的功能。

于 2016-03-13T13:45:52.087 回答