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?
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