0
$\begingroup$

I'm writing a program using opencv libraries that is performance is critical. I have found a solution to this problem, but the performance is very slow, so I'm hoping a mathematical approach may present a solution with better performance. The closest I've seen is

Problem: Given two polygons (ALWAYS trapezoids that are parallel to the X axis), I would like to calculate by some means how much they match up. By this, I mean overlapping area is not sufficient, because if one polygon has excess area, somehow that needs to count against it. Optimally, I would like to know what percent of the area created by both polygons is common. See image for example as what is desired.

Example

A working (but slow) solution:
- Draw polygon one on an empty image (cv::fillConvexPoly)
- Draw polygon two on an empty image (cv::fillConvexPoly)
- Perform a bitwise and to create an image of all the pixels that overlapped
- Count all nonzero pixels --> overlapped Pixels
- Invert the first image and repeat with non-inverted second --> excessive pixels
- Invert the second image and repeat with non-inverted first --> more excessive pixels
- Take the 'overlapped pixels' over the sum of the 'excessive pixels'

As you can see the current solution is computationally intensive because it is evaluating/ operating on every single pixel of an image ~12 times or so. I would rather a solution that calculates this area that goes through the tedious construction and evaluation of several images.

Given:
(x11, y11, x12, y12, x13, y13, x14, y14) where y11 = y12, y13 = y14
(x21, y21, x22, y22, x23, y23, x24, y24) where y21 = y22, y23 = y24

Desired:
Percentage match

$\endgroup$
  • $\begingroup$ Can't you just evaluate the areas algebraically? $\endgroup$ – N74 Oct 30 '16 at 19:09
  • $\begingroup$ Actually, that's exactly what I want to do and hoping to get some guidance with. $\endgroup$ – DrTarr Oct 30 '16 at 19:38
  • $\begingroup$ So $A_1=(x_{11}-x_{12}+x_{13}-x_{14})(y_{11}-y_{13})/2$, the same for $A_2$. $\endgroup$ – N74 Oct 30 '16 at 22:09
  • $\begingroup$ Yeah, but that only gives me the area for each individual trapezoid. I also need the overlapped area. $\endgroup$ – DrTarr Oct 31 '16 at 0:19
  • $\begingroup$ You can, maybe, simplify your calculations using the fact that the area of the non overlapping parts is $A_1+A_2-2A_C $ where $A_C$ is the area of the common part. So the match is $m={A_1+A_2 \over A_C} -2$. $\endgroup$ – N74 Oct 31 '16 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.