人脸检测 - 过滤重叠 windows

Question

我正在写人脸检测算法，现在我有很多windows检测到重叠。
我认为如果 center(windowA) in windowB or center(windowB) in windowA.

windows 是重叠的

我的算法是：

resultList <- empty list
for each windowA detected
    handled <- False
    for each windowB in resultList
        if windowA and windowB are overlapping
            keep the window with bigger value
            handled <- True
            brick inner loop
    if not handled
        append windowA to resultList

但一些重叠 windows 仍然存在。所以，我将其扩展为：

resultList <- empty list
for each windowA detected
    handled <- False
    for each windowB in resultList
        if windowA and windowB are overlapping
            keep the window with bigger value
            handled <- True
            break inner loop
    if not handled
        append windowA to resultList
    for each windowB in resultList, starting from after windowA
        if windowA and windowB are overlapping
            if windowA has bigger value
                remove windowB
            else
                remove windowA and break

好多了，但仍有一些重叠 windows。
有没有一种已知的算法可以快速又好地完成它？（简单的 O(n^2) 解决方案有点慢）
或者有另一种方法可以改进我的算法以使其完美运行？

Answer 1

你的算法还是不行。

考虑一下您考虑的前三个矩形的位置如下图所示：

请注意，矩形的三个中心位于其他矩形之外，因此前三个不重叠。

现在想象一下，第四个非常大的矩形出现了。它的中心在蓝色矩形中，它的值非常大。那么正确的做法是移除所有最初的三个矩形，但你不会。

关于快速解决问题的方法：

首先根据它们的值（降序）对所有矩形进行排序，这样如果它与已经放置的矩形重叠，您就永远不会想要放置一个矩形（注意：这里我指望所有值都是不同的，但如果这是不正确，那么你必须详细说明什么是最佳解决方案。
现在您的任务转换为："You iterate all rectangles sequentially and are interested if the new center happens to be inside any placed rectangle or if the rectangle itself covers any center"
这转化为两个问题：
- 一个。是否有任何一组点在新给定的矩形内
- 乙。新点是否在任何给定的非相交矩形集中。

问题 A 如果您将已准备好的 selected 中心保留在两个点列表中（每个中心存储在两个列表中）。其中一个列表根据 X 坐标排序，另一个列表根据 Y 排序。您可以使用二进制搜索 select 中心，X 坐标在矩形的 X 坐标之间，Y 坐标在矩形的 Y 坐标之间.如果这两个集合有重叠 - 那么矩形中包含一个中心（注意：我已经说过列表，但实际上为中心维护树集合会更优化）。

问题B： 再次分别求解X和Y坐标：你想知道哪些矩形的X坐标是它们的最小值和最大值 X 之间的新点（Y 坐标相同）。在重叠的情况下 - 有一个包含新点的矩形。使用二叉索引树的自适应可以优化解决此任务。

请注意，我的两种解决方案的算法复杂性都比您提出的直接方法差，但我希望它们在所有现实生活中的测试用例中都将得到相当大的优化。

Answer 2

我不知道问题出在哪里，但使用这个新代码它也能正常工作：

result_list = empty list
for each windowA detected
    found_better = False
    for each windowB in result_list
        if windowA and windowB are overlap
            if windowA is better
                remove windowB from result_list
            else (so, windowB is better)
                found_better = True
                break inner loop
    if not found_better
        append windowA to result_list

人脸检测 - 过滤重叠 windows

Face Detection - Filter overlapping windows

algorithm

pseudocode

overlap

face-detection