Анализ блоков кадров AV1 для точечных запросов ⇐ C++

[Anonymous]

Вопрос. Учитывая данные в формате, который я описываю ниже, какое представление является наиболее эффективным для эффективных запросов, к какому блоку принадлежит точка.
Я хочу проанализировать блоки кодирования видеокадра в некоторую структуру данных, чтобы быстро запросить, какому блоку принадлежит та или иная позиция пикселя. Единственная информация, которая у меня есть, — это двумерный массив, где каждая запись (x,y) сообщает мне размер блока, к которому относится блок (

Код: Выделить всё

4*x

, 4*y) размером 4 x 4 принадлежит (т. е. массив представляет собой исходный кадр, дискретизация которого уменьшена в 4 x 4 раза). Итак, для каждой позиции я теперь знаю, какому блоку принадлежит этот блок, но не знаю, где этот блок начинается (информация извлекается из библиотеки libaom). Конечные блоки были сгенерированы видеокодером с использованием рекурсивного разделения суперблоков (блоки фиксированного размера 64x64 или 128x128). Разделение может быть любым из 10 типов, указанных AV1:

Я попробовал разложить проблему на два этапа:

• На основе информации, предоставленной массивом, построить блоки, чтобы получить (x,y,ширина,высота)
• Создайте некоторую структуру данных/алгоритм для хранения пространственно близких блоков для быстрого запроса точек

Задача 1
Для первой я подумал о том, чтобы сделать DFS и всегда добавлять 3 угловые точки текущего блока в качестве следующих потенциальных начальных позиций для некоторых блоков. Но это оказалось неправильно, так как вместо правильного большого блока в некоторых случаях я мог добавить маленький. Аналогичная ситуация происходит, если я использую BFS.
То, что я тогда сделал, это использовать BFS на основе приоритетной очереди, где я всегда сначала выбираю блоки по их самой низкой координате y и если они равны по наименьшей координате x. Однако, когда я это делаю, иногда получаются невозможные разделы (проблема на следующем изображении заключается в том, что раздел внутри отмеченной области создает перекрывающиеся области, поскольку я рисую их контур):

Когда я использую Манхэттенское расстояние, кажется, все работает нормально:


Однако я не понимаю почему это происходит, и я не хочу иметь решение, которое работает только с теми разделами, которые я проверяю вручную.
Может быть, кто-нибудь может дать больше информации по этому поводу?
Проблема 2
Для точечного запроса я нашел два решения, которые не являются оптимальными.
В дальнейшем пусть n — количество блоков в фрейм.

• Линейный поиск

• Перебор каждый блок и проверьте, находится ли точка внутри. Если да, вернуть блок
• Предварительная обработка: O(1)
• Запрос: O (n)

• Двоичный поиск
  • Сначала отсортируйте блоки по их координате X.
  • Если теперь кто-то хочет запросить точку, мы можем искать наибольшую координату x
    
    Подробнее здесь: https://stackoverflow.com/questions/793 ... se-queries