2.3
解码关系图拓扑排序认证算法

编码后的视频数据包之间存在解码依赖关系，这种关系在H.264/SVC视频流中主要体现在图像组的时域帧之间、帧内空域层之间。分析视频码率中的解码逻辑关系有助于提高视频流的认证效率。首先建立基于解码关系的视频逻辑单元图 G （ V ， E ），其中视频逻辑单元可以是视频的时域帧认证单元（Authentication Unit，AU），也可以是视频的空域层单元，即分别在时域和空域建立相应的解码关系图。

视频逻辑单元图 G （ V ， E ）中， V 表示视频逻辑单元集合，其元素称为顶点； E 表示顶点之间的解码依赖关系。视频逻辑单元集合 V 为{ v ₁ ， v ₂ ，…， v _n }，将视频逻辑单元映射为顶点时的序号{1，2，…， n }与该视频逻辑单元的解码次序一致，即接收端将依次解码视频逻辑单元 v ₁ 、 v ₂ 、…、 v _n 。采用有向边 v _i →v _j 表示顶点 v _j 解码依赖于顶点 v _i ，即只有当顶点 v _i 被正确接收后，顶点 v _j 才能实现解码，用于恢复视频图像，故该解码关系图为一个有向图。令 L 为解码关系图的邻接表，邻接表中表头节点和表节点的结构如图2-6所示。表头节点中包含该顶点的出度Outdegree和链接边域*Edgefirst，表节点中包含所有指向该顶点发出边的顶点对应的顶点序号构成的链表，即该顶点解码所依赖的顶点构成的链表，其中VertexId表示顶点序号，*Next表示链接的下一个顶点地址。

邻接表 L 的结构与视频编码过程有关，不同的编码方法对应的邻接表取值不尽相同。而该邻接表由视频编码参数获得，如H.264/SVC中视频编码时域帧之间的预测模式可以是“IBBP”“IPPP”等（分别表示时域编码采用IDR、B帧或P帧的次序）。由邻接表可知，若邻接表第 i 个表头节点的出度为0，则表示没有其他任何顶点的解码依赖于顶点 v _i ；若第 i 个表头节点的出度大于或等于1，则表示至少有1个其他顶点的解码依赖于顶点 v _i ；若第 i 个表头节点的出度取最大值，则表示顶点 v _i 的被解码依赖程度最高，重要性最高，通常该顶点是时域或空域的基础层数据单元。

根据邻接表 L 中的元素取值，对视频逻辑单元图中的顶点进行拓扑排序认证，以获取相应的哈希值附着方式。若 L [ i ].Outdegree=0，则将顶点 v _i 的哈希值 H _i 附着在 L [ i ].Edgefirst所指向的链表中max{VertexId}对应的顶点内容之后，并且将该链接中所有{VertexId}对应的表头节点中的Outdegree值减1。之所以将顶点 v _i 的哈希值附着在其链表中最大序号的顶点上，是因为根据视频逻辑单元序号与顶点序号的映射关系，对于网络带宽较低的接收端，若仅获取较低码率的视频流，则该接收端不需要被丢弃视频逻辑单元的哈希认证，有利于降低认证负载。

解码关系图拓扑排序认证算法TS（ V ）如图2-7所示。算法输入为视频逻辑单元图的顶点和邻接表，且算法采用循环方式依次处理未被其他顶点解码依赖的顶点的哈希认证。与普通有向图的拓扑排序不同，此处拓扑排序的主要作用在于寻找有向图中顶点之间的解码依赖关系，并根据此关系进行认证，拓扑排序认证的结果唯一；而普通有向图的拓扑排序认证结果不唯一，其主要目的在于寻找顶点之间的偏序关系并构成线性序列。

为提高算法的处理效率，采用栈结构存放当前所有出度为0的顶点序列，以便认证时使用。算法分为栈 S 初始化与认证两个部分：栈 S 初始化部分通过遍历邻接表的表头节点，将所有出度为0的表头节点序号入栈；认证部分依次针对出栈的顶点选择相应的哈希值附着顶点序号。

算法第7行中的{ i ≺ j }表示顶点 v _i 的哈希值应附着在顶点 v _j 的内容之后，并将该排序关系依次存放在链表Sort中；算法第8～10行用于更新认证后表头节点的出度；算法第11行表示所处理的是最后一个顶点，将对其直接进行哈希值计算；算法输出Sort为该视频逻辑单元哈希认证次序。

由以上算法可以看出，对视频逻辑单元图 G （ V ， E ）进行认证的空间复杂度为 O （2 n+e ），时间复杂度为 O （ n+e ），其中 e 为边的条数。通常视频的编解码参数对整个视频中的每个图像组、空域层数据单元来说都是相同的，因此该算法仅需在对第一个图像组或空域层进行认证时遍历整个邻接表，并记录下拓扑排序，后续在对其他图像组或空域层进行认证时，直接按照拓扑排序进行认证即可，无须再次遍历邻接表。这样有利于提高算法的认证效率，从而降低接收端的延迟时间。 P5VjCaJsuqxoB1nWutJeRJEIwfjcld1wic4a/lrxCcTUzps0giMAPvfzWmuZ82F5