有害音视频一致性检测方法的研究与实现
2017-01-11王媛媛
王媛媛， 詹 远， 白 涛
(1.乌鲁木齐市公安局， 新疆乌鲁木齐 830063; 2.新疆警察学院， 新疆乌鲁木齐 830014;3.新疆农业大学计算机与信息工程学院， 新疆乌鲁木齐 830052)
有害音视频一致性检测方法的研究与实现
王媛媛1， 詹 远2， 白 涛3
(1.乌鲁木齐市公安局， 新疆乌鲁木齐 830063; 2.新疆警察学院， 新疆乌鲁木齐 830014;3.新疆农业大学计算机与信息工程学院， 新疆乌鲁木齐 830052)
针对音视频一致性检测在有害音视频管控方面的实际需求，提出了能够适应不同应用场景，不同计算、存储资源条件限制的一致性检测方法。该方法基于MD5值比对、切片与帧提取、帧内容分析等算法，能够处理由于个别字节发生变化，或视频经过剪辑、合并及格式转换而造成的MD5值改变的情况。基于此研发的检测系统具有简单、高效、易用的特点，在实际测试中，具有很高的识别率和较好的检测效率。
MD5； 有害音视频； 一致性检测； 切片算法； 内容分析
0 引言
有害音视频是指涉及暴力恐怖、非法宗教、淫秽色情等内容，危害国家安全、违反法律法规、扰乱社会秩序、破坏社会稳定的音视频文件。近年来，随着网络环境的日益完善、移动互联技术的飞速发展和智能设备的快速普及，犯罪分子借助网络、移动存储介质等方式传播有害音视频的案件日益增多，社会危害性极大。例如，从近年来新疆破获的暴力恐怖犯罪案件来看，制作、传播暴力恐怖音视频，成为当前暴恐案件多发的重要诱因[1]，暴恐音视频的非法传播已成为恐怖主义犯罪的新趋势[2]。在这种形势下，对有害音视频的管控和打击已成为公安部门的重要任务之一，因此研究一种满足实战需要的有害音视频快速检测和识别方法就显得尤为必要。
目前，对有害音视频的检测与识别主要依托已掌握的有害音视频样本，建立参照样本库，通过将待检样本与样本库进行一致性检测来实现。主要有三种应用情况：一是通过便携式设备对智能移动终端中的音视频进行检测；二是对移动存储设备、台式机或笔记本上的音视频进行批量检测；三是在音视频网站中对传播的音视频文件进行自动检测。本文提出的检测方法能够适应不同应用场景，根据计算和存储资源条件的不同，兼顾检测速度和准确性。
1 基于MD5的检测算法
根据《电子物证文件一致性检验技术规范》(GA/T 827—2009)[3]，鉴定两个文件是否一致可以比较两个文件的哈希值，若两个哈希值相同，则可以判断两个文件的数据相同；若两个散列值不同，则可以判断两个文件的数据不同。因此通过MD5(Message Digest Algorithm 5)消息摘要算法[4]实现有害音视频的快速检测是一种可行的办法，其核心思想是利用 hash 算法来对文件数据进行摘要，通过对比摘要值来检测文件[5]。
MD5算法是计算机安全领域广泛使用的一种散列函数，可以将任意长度的消息压缩成固定长度的信息摘要，并且对原文内容变化高度敏感，因此对MD5值的比对非常高效和准确。假定已有音视频样本库为S，计算得到的MD5值数据库为MS，待检样本为v，计算得到的MD5值为Mv，目标是判断Mv是否在MS中，从而确定v是否为有害音视频，其基本流程如图1所示。
基于MD5的检测算法实现简单，适用于计算、存储资源有限的场景下。但MD5是典型的Hash(Key-Value)结构，其设计思想是使Key中的任意关键字经过变换，能够在Value空间中尽可能均匀分布，即对输入高度敏感。因此，该算法对待检样本发生细微改变的特殊情况处理仍存在局限性。例如利用WinHex等工具修改原音视频文件的个别字节，或通过echo命令在文件末尾插入几个字节等(图2中划线部分)，都会产生完全不同的MD5值(MD5值中无法体现原文件的相似性)，在这种情况下，直接通过MD5值比对的检测算法将会失效，无法保证检测的准确性和可靠性。
图1 基于MD5的检测算法流程
图2 字节修改和末尾增加字节示例
2 基于MD5的切片检测算法
基于MD5的切片检测方法是对音视频文件的切片进行MD5值比对，通过局部片段的比对结果来计算待检样本与样本库参照样本的相似度，从而避免了因为个别字节的变化而带来的漏检。主要有两种实现方式：基于字节流的切片方法和基于帧提取的切片方法。
图3 基于字节流切片方法示意图
2.1 基于字节流切片方法
基于字节流切片方法是将音视频文件按字节流读入，进行适当等长切分，通过对各切片计算MD5值，并分别比对，以实现快速检测。基本算法流程如下：
(1)获取待检样本v的大小size；
(2)遍历样本库S，获取S中所有大小与size邻近的样本，建立临时样本集合TS；
(3)根据size确定切片大小segLen，切片数为奇数，设为n；
(4)对待检样本v按segLen进行切片，对每一片计算MD5；
(5)从TS中提取一个样本v′按segLen进行切片，对每一片计算MD5，将待检样本v的切片逐一与参照样本v′的对应切片进行MD5值比对，如图3所示。如果相同取1，不同则取0。设n个片断取值的和为m，计算相似度m/n；
(6)遍历TS，重复步骤5，选择相似度最高的记录，与设定的阈值threshold比较。如果大于 threshold，检测结果为“是”，反之为“否”。
在上述算法中，切片数n越大，片段越小，判断越准确，但同时计算量会增大，在实践中根据待检样本的大小取20～30之间的奇数即可。此外，阈值的设定也会影响检测结果，由于变动大多数情况下不超过2处，最多存在于2个片段中，因此设置为0.9是比较合适的。
2.2基于帧提取的切片方法
基于字节流切片方法需要对音视频文件的全部字节流进行处理，当待检样本较大时，检测效率较低。特别是针对大小达到G级的视频文件，切片操作的时间成本较高。基于帧提取的切片方法可以提高对大视频文件的检测效率。对于给定的一段视频，为了视觉感知上的连续性，帧率至少为24帧/秒[6]，若对全部帧进行提取和比对计算量仍然很大。因此首先对待检样本按固定时间间隔提取帧，然后对每一帧计算MD5值，对样本库中的样本也按同样的时间间隔提取帧，计算MD5值，然后逐帧进行比对。算法基本流程如下：
(1)获取带检样本v的大小size；
(2)遍历样本库S，获取S中所有大小与size邻近的样本，建立临时样本集合TS；
(3)根据size确定提取帧的时间间隔interval，提取的帧数为奇数，设为n，如图4所示；
(4)对待检样本v按interval进行帧提取，对每一帧计算MD5；
(5)从TS中提取一个样本v′按interval提取帧，对每一帧计算MD5，将待检样本v的帧逐一与参照样本v′的对应帧进行MD5值比对，如果相同取1，不同则取0。设n个帧取值的和为m，计算相似度m/n；
(6)遍历TS，重复步骤5，选择相似度最高的记录，与设定的阈值threshold比较。如果大于threshold，检测结果“是”，反之为“否”。
图4 基于帧提取的切片方法示意图
该算法的时间间隔interval可以根据样本时长和检测速度的实际需要设定，设置的越大，帧提取的密度越小，执行效率越高；反之，帧提取的密度越大，需要比对的次数越多，执行效率越低。该方法与基于字节流切片方法相比，主要区别是该方法只针对视频文件，按固定间隔提取帧，计算量上要小于基于字节流的切片方法；相同点是都能够处理待检样本局部字节修改或末尾增加个别字节的情况，并且对计算机的运行速度和存储能力都有一定要求。
3 基于关键帧内容特征的检测算法
对视频文件的剪辑或格式转换会造成文件内容和编码、封装格式上的变化，基于MD5的算法无法处理这种情况。以视频剪辑为例，剪辑主要包括合并和裁剪操作，剪辑后的视频文件和源文件内容关系如图5所示。
图5 视频剪辑示意图
由于剪辑后的视频很难与源文件找到完全一致的基准，所以无论是基于字节的切片还是基于时间的帧提取，都很难保证局部片段内容完全一致。因此，利用MD5这种对原文件内容非常敏感的算法无法应对这种情况。
基于关键帧内容分析的相似度检测算法的基本思路是通过对视频提取关键帧，将选定的关键帧作为视频摘要[7]，通过对关键帧进行相似度比较来判断视频的相似度。视频的结构是由场景、镜头和帧构成。镜头是一段连续的视频帧序列，是视频结构的基础单元[8]；关键帧是用来描述一个镜头内部主要内容的某帧或某几帧图像[9]。因此，只要采取一定的时间间隔提取关键帧，就能保证提取到足够充分的视频特征。
基于这个思路，检测算法分为如下几个步骤：
(1)根据待检样本v大小确定合适的时间间隔interval，按照interval对待检样本v和参照样本v′进行关键帧提取；
(2)提取v的一帧与v′的全部帧进行相似度检测，并保存最大相似度值和参照样本对应的帧；
(3)重复执行步骤(2)，获取v所有帧的最大相似度和参照样本的对应帧；
(4)统计v的最大相似度大于给定阈值的帧数，计算占v的总帧数的比例，大于视频相似度阈值threshold即判定v与v′相似。
以图6为例，待检样本提取5帧，参照样本提取10帧，将待检样本的5帧逐一与参照样本帧进行相似度计算，即可得到相似度矩阵。假定帧间相似度阈值为0.9，统计待检样本每一帧的最大相似度(矩阵右侧带下划线的数字)，大于阈值的帧有4个，计算视频相似度为0.8，再根据视频相似度阈值threshold即可判定待检样本与参照样本是否相似。
图6 相似度矩阵示意图
其中步骤(2)中计算帧之间相似度的关键问题是特征提取，Lowe[10]提出的一种基于尺度空间的局部特征点提取和匹配算法(SIFT)。由于采用了局部特征描述，在特征提取上需要消耗较多的时间[11]，因此这里采用基于像素RGB信息的全局特征。具体计算方法如下：
(1)首先扫描帧，获取每个像素的RGB值，保存到以RGB值为键(Key)、以该RGB值出现次数为值(Value)的HashMap中；
(2)将HashMap做为帧的特征向量，向量维数视作所有出现过的RGB值，分量的值则是对应RGB值出现的次数，进行归一化；
(3)计算两个特征向量的余弦相似度作为两帧之间的相似性的度量。值越趋近于1，代表两个向量的方向越趋近于0，向量的方向越一致，相似度也越高。
由于该方法计算量较大，需要进一步优化：当待检样本v的第一个最大相似度大于阈值的帧确定后，其参照样本的帧的位置非常重要。由于视频剪辑的基本单位是镜头，内容是连续的，因此v后续的帧检测从参照样本当前帧开始搜索即可。这样会减小搜索空间，提高运行效率。
图7 逐帧相似度检测优化示意图
不失一般性，以图7为例，假设待检样本v的第一个最大相似度大于阈值的帧是f1，对应的参照样本帧是f′4，则检测v的f2帧时，参照帧从f′4开始搜索即可。
该算法能够处理视频文件经过复杂变化(剪辑、格式转换等)的情况，适应性较强，但对计算和存储资源条件要求较高。
4 系统设计与实现
基于以上检测方法，系统设计主要分为MD5快速检测、基于字节流切片检测、基于帧提取检测和基于帧内容分析检测。主要针对4种情况：待检样本包含在样本库中，可直接采用MD5值比对；待检样本有个别字节发生改变，文件较小，采用字节流切片检测；体积较大的视频文件，采用帧提取的检测算法；对其他尺寸差距较大的视频文件，采用基于帧内容分析的检测算法。
4.1 系统实现
出于跨平台的考虑，系统采用Java实现，从技术实现上主要有4个关键问题，MD5算法、字节流切片、帧提取以及帧内容分析。
(1)MD5算法
Java.security包的MessageDigest类中提供了计算MD5值的方法digest()。
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] buff = md.digest(input);
digest()方法返回的是一个字节数组，需要转成16进制的字符串。这可以利用Integer类的toHexString方法实现。
Integer.toHexString(buff[i] & 0xFF);
由于Java中二进制采用的是补码形式，byte的大小为8bits而int的大小为32bits，因此在转换时需要首先逐字节与“0xFF”进行“与”运算。
(2)字节流切片
待检样本音视频计算MD5值直接比对无命中记录时，即调用切片检测算法。首先定义InputStream对象，通过available()方法获取文件大小，并定义临时字节数组tempbytes。
in = new FileInputStream(fileName);
intbyteread = in.available();
byte[]tempbytes = new byte[byteread]
从输入流中读取一定数量的字节，并将其存储在缓冲区数组 b 中，以整数形式返回实际读取的字节数。
in.read(tempbytes)
在字节数组tempbytes截取特定位置和长度的片段可以采用数组对象Arrays的copyOfRange方法。方法原型如下：
public static byte[] copyOfRange(byte[] original, int from, int to)
其中，original是原字节数组；from表示复制的起始位置；to表示截取的长度。
byte[] newData = Arrays.copyOfRange(tempbytes,i*segLen,(i+1)* segLen);
其中，segLen表示切片长度。
(3)帧提取
对视频的帧提取采用的是FFmpeg，FFmpeg是一套可以用来记录、转换数字音频、视频，并能将其转化为流的开源计算机程序。FFmpeg包含了先进的音视频编解码库libavcodec，支持常见的音视频格式，并且能够实现跨平台编译运行。基于FFmpeg的按固定间隔提取帧主要是通过调用FFmpeg的命令来实现的。
ffmpeg -i inputfile -r 0.2 -f image2 %03d.jpg
在Java中，可以利用Java.lang中ProcessBuilder类实现，该类用于创建操作系统进程，并提供了一种启动和管理进程的方法。
(4)帧内容分析
对视频关键帧的提取可以通过FFmpeg提供的SDK完成，内容分析分为提取像素RGB信息、特征向量归一化、计算余弦相似度和通过各帧的最大相似度评价视频相似度等步骤。
提取像素RGB信息通过BufferedImage类读取帧信息，利用BufferedImage类的getRGB方法读取像素的RGB数据，然后存储在HashMap对象中以提高处理速度：
BufferedImage bi_image=ImageIO.read(new File(fileName));
HashMaphm_rgb=new HashMap();
RGBValue= bi_image.getRGB(x, y);
hm_rgb.put(RGBValue, cnt);
特征向量归一化需要首先计算特征向量的模，然后通过归一化使特征向量按比例缩放到单位长度，只保留方向信息。然后计算两个特征向量的点积，通过计算两个向量的夹角余弦值来评估他们的相似度。最后通过创建二维ArrayList对象(ArrayList
4.2 实验测试
有害音视频样本库是在案件侦办、电子物证检验鉴定及嫌疑人审理过程中获取的，是通过人工鉴定，经过多年积累而形成的。从中随机抽取音频、视频各300条，共600条建立参照样本库，其中音频大小在3～24 M之间，平均大小16.7 M；视频大小在162～487 M之间，平均大小269.7 M。再从测试样本库中随机选择100个样本作为待检样本，其中30个样本利用WinHex工具对个别字节进行修改、增减；40个视频样本利用Boilsoft Video Splitter、格式工厂等工具进行裁剪、合并及格式转换，实验结果如表1所示。
表1 实验结果
实验结果显示，对未发生变动的30个样本的识别率为100%；对于发生变化的70个样本的平均识别率为97.14%。从时间上看，对未发生变动的样本检测时间较短，平均用时为3.83秒，主要的时间消耗是MD5计算；发生变化的待检样本平均用时差异较大，原因是内容变化的情况下，文件大小变化不大，通过样本大小在参照样本库中进行预先筛选，减少了比对样本数，提高了检测速度；而视频经过合并、裁剪或格式转换后，文件大小变化不确定，只能与几乎所有视频参照样本比对，因此用时较长。
5 结语
目前，对有害音视频的管控和打击已成为公安部门的重要任务之一，特别是处在维稳处突一线的新疆公安部门面临着更加严峻的形势，对于有害音视频，特别是暴恐音视频的快速、准确地检测与识别面临着比较复杂的应用环境。本文提出的基于MD5值比对、切片与帧提取、帧内容分析的一致性检测方法，能够适用于各种应用场景下有害音视频检测，并在此基础上研发了验证系统。实验证明，该方法具有简单、高效、检测准确等特点。
[1] 潘从武.涉暴恐音视频非法传播危害严重须严惩[N].法制日报,2014-05-22(4).
[2] 刘炯.网络时代暴恐音视频传播防控研究[J].中国人民公安大学学报(社会科学版),2015,31(1): 1-9.
[3] 中华人民共和国公安部.GA/T 827—2009,电子物证文件一致性检验技术规范[S]. 北京：中国标准出版社，2009.
[4] RIVEST R. The MD5 message-digest algorithm[S]. MIT Laboratory for Computer Science and RSA DATA SECURITY. Inc, 1992.
[5] 方燕飞, 王俊, 何王全. 基于多层MD5消息摘要的文件完整性实时检测技术[J]. 计算机应用与软件, 2015, 32(1): 20-23.
[6] 李海涛, 林新棋, 吴鹏, 高智, 詹晓珊. 基于颜色内容一致性的视频篡改检测[J]. 福建师范大学学报(自然科学版), 2014, 30(2): 26-33.
[7] ELDIB M Y，ZAID B S A，ZAWBAA H M，et al. Soccer video summarization using enhanced logo detection[C]∥ Proceedings of the 16th IEEE international conference on Image processing. IEEE Press，2009：4345- 4348.
[8] 吕晓宇. 视频镜头分割方法[J]. 办公自动化, 2011(2): 33-34.
[9] 魏玮, 刘静, 王丹丹. 视频镜头分割方法综述[J]. 计算机系统应用, 2013, 22(1): 5-7，69.
[10] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision，2004，60(2)：91-110.
[11] 刘守群,朱明,郑烇.一种基于内容相似性的重复视频片段检测方法[J].中国科学技术大学学报, 2010,40(11):33-38.
(责任编辑 于瑞华)
乌鲁木齐市应用开发研究计划项目“危害国家安全类电子数据哈希库建设”(Y131320006)。
王媛媛(1979—)，女，新疆哈密人，硕士，网络安全支队技术保障科科长。研究方向为信息网络安全、大数据处理。
TN912.34
