Analysieren von AV1-Frame-Blöcken für punktuelle Abfragen ⇐ C++

[Guest]

Frage: Was ist angesichts der Daten in dem Format, das ich unten beschreibe, die effizienteste Darstellung, um effiziente Abfragen durchzuführen, zu welchem ​​Block ein Punkt gehört?
Ich möchte die Codierungsblöcke eines Videobilds in eine Datenstruktur analysieren, um schnell abzufragen, zu welchem ​​Block eine Pixelposition gehört. Die einzige Information, die ich habe, ist ein 2D-Array, in dem mir jeder Eintrag (x,y) die Größe des Blocks angibt, zu dem der Block (

Code: Select all

4*x

, 4*y) mit der Größe 4 x 4 gehört zu (d. h. das Array ist der ursprüngliche Frame, der um den Faktor 4 x 4 heruntergerechnet wurde). Für jede Position weiß ich nun, zu welchem ​​Block dieser Block gehört, aber ich weiß nicht, wo der Block beginnt (die Informationen werden aus der libaom-Bibliothek extrahiert). Die endgültigen Blöcke wurden von einem Video-Encoder mithilfe einer rekursiven Aufteilung von Superblöcken (Blöcke mit fester Größe 64 x 64 oder 128 x 128) generiert. Die Aufteilung kann einer der 10 von AV1 angegebenen Typen sein:

Was ich versucht habe, war, das Problem in zwei Schritte zu zerlegen:

• Konstruieren Sie aus den vom Array bereitgestellten Informationen Blöcke zum Abrufen (x,y,width,height)
• Konstruieren Sie eine Datenstruktur/einen Algorithmus, um räumlich nahe Blöcke für eine schnelle Punktabfrage zu speichern

Problem 1
Für das erste habe ich darüber nachgedacht, ein DFS zu erstellen und immer die 3 Eckpunkte des aktuellen Blocks als nächste mögliche Startpositionen für einige Blöcke hinzuzufügen. Dies stellte sich jedoch als falsch heraus, da ich in einigen Fällen einen kleinen Block anstelle des richtigen großen hinzufügen konnte. Ähnliches passiert, wenn ich BFS verwende.
Was ich dann getan habe, war, ein auf Prioritätswarteschlangen basierendes BFS zu verwenden, bei dem ich Blöcke immer zuerst anhand ihrer niedrigsten Y-Koordinate auswähle und ob dies der Fall ist gleich, durch die niedrigste x-Koordinate. Wenn ich das mache, erhalte ich jedoch manchmal Partitionen, die unmöglich sind (das Problem im folgenden Bild besteht darin, dass die Partition innerhalb des markierten Bereichs überlappende Regionen erzeugt, da ich deren Umrisse zeichne):

Wenn ich die Manhattan-Distanz verwende, scheint alles zu funktionieren gut:


Ich verstehe jedoch nicht, warum das passiert und nicht Ich möchte eine Lösung haben, die nur auf den Partitionen funktioniert, die ich manuell überprüfe.
Vielleicht könnte jemand mehr Einblick in dieses Thema geben?
Problem 2
Für die Punktabfrage I habe 2 Lösungen gefunden, die nicht optimal sind.
Im Folgenden sei n die Anzahl der Blöcke im Frame.

• < li>Lineare Suche

• Iteriere über jeden Block und überprüfe, ob der Punkt darin liegt. Wenn ja, geben Sie den Block zurück
• Vorverarbeitung: O(1)
• Abfrage: O (n)

• Binäre Suche
  • Sortieren Sie zunächst die Blöcke nach ihrer x-Koordinate.
  • Wenn man nun nach einem Punkt suchen möchte, kann man nach dem größten suchen x-Koordinate