c++ - 计算两个梯形的 'percentage matched'的最快方法

Question

我问了以下问题here并得到了一个很好的解决方案，但发现它的性能太慢(640x480 图像需要 2-300 毫秒)。现在我想考虑如何优化它。

问题:
给定两个多边形(总是平行于 X 轴的梯形)，我想通过某种方式计算它们的匹配程度。我的意思是重叠面积是不够的，因为如果一个多边形有多余的面积，则需要以某种方式对其进行计数。最理想的是，我想知道两个多边形创建的面积的共同百分比是多少。例如，请参阅所需的图像。

一个有效(但缓慢)的解决方案:
- 在空图像上绘制多边形一(cv::fillConvexPoly)
- 在空图像上绘制多边形二 (cv::fillConvexPoly)
- 执行按位运算并创建所有重叠像素的图像
- 计算所有非零像素 --> 重叠像素
- 反转第一个图像并使用非反转的第二个图像重复 --> 像素过多
- 反转第二个图像并使用非反转的第一个图像重复 --> 更多过多的像素
- 将“重叠像素”除以“过多像素”的总和

正如您所看到的，当前的解决方案计算量很大，因为它对图像的每个像素进行约 12 次评估/操作。我更喜欢一个计算该区域的解决方案，该解决方案需要经过繁琐的构建和评估多个图像。

现有代码:

#define POLYGONSCALING 0.05
typedef std::array<cv::Point, 4> Polygon;

float PercentMatch( const Polygon& polygon,
                    const cv::Mat optimalmat )
{
    //Create blank mats
    cv::Mat polygonmat{ cv::Mat(optimalmat.rows, optimalmat.cols, CV_8UC1, cv::Scalar(0)) };
    cv::Mat resultmat{ cv::Mat(optimalmat.rows, optimalmat.cols, CV_8UC1, cv::Scalar(0)) };

    //Draw polygon
    cv::Point cvpointarray[4];
    for  (int i =0; i < 4; i++ ) {
        cvpointarray[i] = cv::Point(POLYGONSCALING * polygon[i].x, POLYGONSCALING *
            polygon[i].y);
    }
    cv::fillConvexPoly( polygonmat, cvpointarray, 4,  cv::Scalar(255) );

    //Find overlapped pixels
    cv::bitwise_and(polygonmat, optimalmat, resultmat);
    int overlappedpixels { countNonZero(resultmat) };

    //Find excessive pixels
    cv::bitwise_not(optimalmat, resultmat);
    cv::bitwise_and(polygonmat, resultmat, resultmat);
    int excessivepixels { countNonZero(resultmat) };
    cv::bitwise_not(polygonmat, resultmat);
    cv::bitwise_and(optimalmat, resultmat, resultmat);
    excessivepixels += countNonZero(resultmat);

    return (100.0 * overlappedpixels) / (overlappedpixels + excessivepixels);
}

目前，我设计的唯一性能改进是在函数外部绘制“optimalmat”，这样它就不会重新绘制(它与许多其他多边形进行比较)，而且我还添加了 POLYGONSCALING 来缩小多边形的大小，失去一些分辨率，但获得一些性能。还是太慢了。

Answer 1

我可能误解了你想要什么，但我认为你应该能够像这样更快地完成......

• 在零背景上用 1 填充第一个梯形。
• 在零背景上用 2 填充第二个梯形。
• 将两个垫子添加在一起。

现在每个像素必须为 0、1、2 或 3。创建一个包含 4 个元素的数组，并在一次遍历所有元素时，不使用 if 语句，只需增加相应的数组元素即可根据每个像素的值。

然后，数组的第一个索引中的像素总数是梯形都不存在的位置，索引 1 和 2 的元素是存在梯形 1 或 2 的元素，索引 3 的元素重叠。

此外，尝试对两个梯形的洪水填充进行基准测试，如果这是一个很大的比例，如果您有时间，也许有第二个线程填充第二个梯形。

基准

我编写了一些代码来尝试上述理论，对于 640x480 的图像，它需要:

• 绘制第一个多边形需要 181 微秒
• 绘制第二个多边形需要 84 微秒
• 计算重叠需要 481 微秒

因此，我的 iMac 上的总时间为 740 微秒。

您可以与第一个多边形并行绘制第二个多边形，但线程创建和连接时间约为 20 微秒，因此您只能节省 60 微秒，即 8% 左右 - 可能不值得。

大部分代码都是计时和调试:

#include "opencv2/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>

using namespace cv;
using namespace std;

const int COLS=640;
const int ROWS=480;

typedef std::chrono::high_resolution_clock hrclock;
hrclock::time_point t1,t2;
std::chrono::nanoseconds elapsed;
int e;

int
main(int argc,char*argv[]){

   Mat canvas1(ROWS,COLS,CV_8UC1,Scalar(0));
   Mat canvas2(ROWS,COLS,CV_8UC1,Scalar(0));
   Mat sum(ROWS,COLS,CV_8UC1,Scalar(0));

   //Draw polygons on canvases
   Point vertices1[4]={Point(10,10),Point(400,10),Point(400,460),Point(10,460)};
   Point vertices2[4]={Point(300,50),Point(600,50),Point(600,400),Point(300,400)};

   t1 = hrclock::now();
   // FilConvexPoly takes around 150 microseconds here
   fillConvexPoly(canvas1,vertices1,4,cv::Scalar(1));
   t2 = hrclock::now();
   elapsed = t2-t1;
   e=elapsed.count();
   cout << "fillConvexPoly: " << e << "ns" << std::endl;

   imwrite("canvas1.png",canvas1);

   t1 = hrclock::now();
   // FilConvexPoly takes around 80 microseconds here
   fillConvexPoly(canvas2,vertices2,4,cv::Scalar(2));
   t2 = hrclock::now();
   elapsed = t2-t1;
   e=elapsed.count();
   cout << "fillConvexPoly: " << e << "ns" << std::endl;
   imwrite("canvas2.png",canvas2);
   sum=canvas1+canvas2;
   imwrite("sum.png",sum);

   long totals[4]={0,0,0,0};
   uchar* p1=sum.data;
   t1 = hrclock::now();
   for(int j=0;j<ROWS;j++){
      uchar* data= sum.ptr<uchar>(j);
      for(int i=0;i<COLS;i++) {
         totals[data[i]]++;
      }
   }
   t2 = hrclock::now();
   elapsed = t2-t1;
   e=elapsed.count();
   cout << "Count overlap: " << e << "ns" << std::endl;
   for(int i=0;i<4;i++){
      cout << "totals[" << i << "]=" << totals[i] << std::endl;
   }
}

示例运行

fillConvexPoly: 181338ns
fillConvexPoly: 84759ns
Count overlap: 481830ns
totals[0]=60659
totals[1]=140890
totals[2]=70200
totals[3]=35451

使用 ImageMagick 进行验证，如下所示:

identify -verbose sum.png | grep -A4 Histogram:

Histogram:
 60659: (  0,  0,  0) #000000 gray(0)
140890: (  1,  1,  1) #010101 gray(1)
 70200: (  2,  2,  2) #020202 gray(2)
 35451: (  3,  3,  3) #030303 gray(3)