Search code examples
algorithmpseudocodeoverlapface-detection

Face Detection - Filter overlapping windows


I am writing face detection algorithm, and now I have much windows detected that overlapping.
I consider that windows are overlapping if center(windowA) in windowB or center(windowB) in windowA.

My algorithm was:

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

But some overlapping windows remain. So, I extended it to:

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

It's much better, but a few overlapping windows are remain.
Is there a known algorithm that do it fast and good? (The trivial O(n^2) solution is a bit slow)
Or there is another way I can improve my algorithm to work perfectly?


Solution

  • I don't know what the problem was, but with this new code it works as well:

    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