一种对变长二值化描述子的快速编解码算法

摘要

在多媒体内容描述领域里，存在很多的特征描述子。对于特征维数相对较高的特征描述子，数据量是巨大的。对特征描述子进行二值化是很多研究者的选择，但是二值化的方式种类繁多。而且，在保存二值化数据的时候往往存在很大的冗余。因此，需要一种合理的编码规则来规范二值化的表示方法。本发明提出了一种对变长二值化描述子的快速编解码算法。本发明提出的对变长二值化的编码算法，大大减少了数据冗余量，而且对各种形式的二值化方案提出了一个统一的标准。本发明相应提出了对变长二值化描述子的解码方案。对一个描述子而言，平均解码时间仅为1.90*10^-4s，并没有带来额外的时间损失，计算速度很快。

主权项

一种对变长二值化描述子的快速编解码算法，其特征在于，包括以下步骤：A、编码阶段本发明提出的编码采用二叉树标识和特征数据两部分组成；A1、二叉树标识二叉树标识——将二值化采取的具体方式进行编码；规则是：对二叉树的分支关系进行编码；具体编码方法是，对二叉树进行层次遍历，根节点一定进行二值化，不计入编码内，首先从左到右依次访问第一层的节点，然后访问第二层的节点，以此类推，自上而下，自左至右逐层访问树的节点；对于访问到的每一个节点，判断该节点是否有子孩子，如果有子孩子，则该节点编码为“1”，否则编码为“0”；A2、特征数据描述特征数据描述部分用来表示特征描述子经过二值化后得到的二值化数据；特征描述子进行二值化的最后结果是通过叶子节点上的数据来描述的；从二叉树的根节点开始遍历，根据每一个叶子节点的路径来获得该叶子节点的编码；二叉树的左右子树是互不相交的，所以不会出现叶子节点用二进制码型描述不唯一的情况；二值化后的特征描述子就通过码头和特征数据表示出来；码头用来判断采取的是何种二值化的方式，从而决定特征描述子进行二值化后的特征数据编码；B、解码阶段B1、首先对二值化标识部分进行解码，采取逐个节点进行判断的方法；从第一个节点开始，根据每个节点对应值是否为1，来判断是否进行二值化，若某一层的节点都为0，则二值化终止，即得到二值化标识；具体解码步骤为：（1）、从第一层开始进行解码，码字个数为2，用m来表示该层码字个数，此时，m=2；（2）、判断这一层中m个码字中1的个数n，若n=0，则解码终止，若n≠0，则进行步骤（3）；（3）、根据n值计算下一层码字的个数，此时用m来表示此层码字的个数，m=2*n；然后进行步骤（2），直至解码终止；B2、然后根据二值化标识部分对特征数据进行解码；为了更快的对特征数据进行解码操作，首先将二值化标识部分扩展成“满二叉树”的形式，因为满二叉树更容易来计算节点的位置，然后根据这种形式对特征数据部分进行解码；通过二值化标识部分的0或1来判断是否进行二值化，通过特征数据的0和1来判断节点所在左子节点还是右子节点，通过节点所在的位置来得到二值化标识部分中下一个相对应的节点，依次交替进行，直至特征数据解码完成；具体解码步骤为：1)判断特征数据的第一个数值，若数值为0，则对应于码头的第1位，用k来表示此数值所在码头的位置，此时，k=1；若数值为1，则对应于码头的第2位，此时，k=2；2)判断码头的第k位码字，若码字为0，说明此节点不再进行二值化，此节点为叶子节点，则解码终止，得到一个特征数据；若码字为1，则执行第3）步；3)读取特征数据中的下一个数值，判断数值为0或1；4)若特征数据中的数值为0，则表示位于左节点上，所在位置为2k+1，即对应于码头的第2k+1位，令k=2k+1，执行步骤2）；若特征数据中的数值为1，则表示位于右节点上，所在位置为2k+2，对应于码头的第2k+2位，令k=2k+2，执行步骤3）。