Обнаружение лица - перекрытие фильтров окон

Question

Я пишу алгоритм обнаружения лиц, и теперь у меня много окон, которые обнаруживают, что перекрываются.
Я считаю, что окна перекрываются, если center(windowA) in windowB or center(windowB) in windowA.

Мой алгоритм был:

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 

Но остаются некоторые перекрывающиеся окна. Итак, я распространил его на:

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 

Это намного лучше, но осталось несколько перекрывающихся окон.
Есть ли известный алгоритм, который делает это быстро и хорошо? (Тривиальное решение O (n^2) немного медленное)
Или есть другой способ, которым я могу улучшить свой алгоритм, чтобы работать отлично?

Answer 1

Я не знаю, в чем проблема, но с этим новым кодом он работает, а также:

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 

Answer 2

Ваш алгоритм все равно не будет работать.

Рассмотрим случай, в котором первые три прямоугольника вы считали позиционируются как изображено на рисунке ниже:

Отметим, что три центра прямоугольников находятся за пределами других прямоугольников, так что первый три не перекрываются.

Теперь представьте, что наступает четвертый действительно большой прямоугольник. Его центр находится в синем прямоугольнике, и его значение действительно велико. Тогда правильным было бы удалить все начальные три прямоугольника, но вы бы этого не сделали.

Что касается быстрого способа решить проблему:

• сортировать все прямоугольники в соответствии с их значениями (по убыванию), так что вы никогда не хотели бы разместить прямоугольник, если он перекрывает уже помещен прямоугольник (примечание : здесь я считаю, что все значения отличаются друг от друга, но если это не так, вам нужно подробно остановиться на том, какое оптимальное решение есть).
• Теперь ваши задачи переходит в: «Вы перебирать все прямоугольники последовательно и интересно, если новый центр случается внутри любого помещенного прямоугольника или если сам прямоугольник охватывает любой центр»
• это трансформирует две проблемы:
  • A. Независимо от того, существует ли какой-либо из множества точек внутри вновь заданного прямоугольника
  • B. то ли новая точка находится внутри любого заданного непересекающегося множества прямоугольников.

Задача А можно оптимизировать, если вы держите laready выбранные центры в двух списках точек (каждый центр находится в обоих списках). Один из списков сортируется по X-cordinate, другой соответствует Y. они вы можете, используя двоичный поиск, выбрать центры с координатой X между координатой X прямоугольника и координатой Y между координатами Y прямоугольника. Если два набора перекрываются - тогда есть центр, содержащийся в прямоугольнике (ПРИМЕЧАНИЕ: я сказал список, когда на самом деле было бы более оптимальным для вас поддерживать наборы деревьев для центров).

Задача B: Опять решения отдельно по X и Y координат: вы заинтересованы, чтобы знать, какие прямоугольники имеют координаты Х новой точки между их максимальным и минимальным X (то же самое для Y координат). В случае перекрытия - есть прямоугольник, который содержит новую точку. Эта задача может быть оптимально решена с помощью адаптации двоичных деревьев индексов.

Обратите внимание, что мои решения имеют худшую унификацию алгоритма, чем прямой подход, который вы предлагаете, но я ожидаю, что они будут значительной оптимизацией во всех реальных тестовых случаях.