基于广义骑士巡游的图像和视频压缩与加密同步技术研究

。.Nowadays the security of images and videos has become increasingly important in many fields, such as confidential transmission, video surveillance, military and medical applications and so on. This requires that the communication systems have a good security level (encryption) and an acceptable transmission rate (compression rate). Compression and encryption technologies are important to the efficient solving of network bandwidth and security issues. So it is the major motivation for us to focus our research on this direction. In order to use optical correlation, encryption and compression techniques cannot be deployed independently or in a cascade manner. Otherwise, our system will suffer from two major problems. Firstly，in fact, we cannot simply use these techniques in a cascade manner without considering the impact of one technique on another. Secondly, a standard compression can affect the correlation decision, because the correlation is sensitive to the loss of information. To solve both problems, we are exploring a new technique to compress & encrypt images and videos simultaneously by using generalized knight's tour (GKT). .Knight's tour Problem (KTP) is to find a sequence or knight's tour matrix (KTM) of legal moves such that a knight visits each square of an 8×8 chessboard once and only once. This problem may be translated into the problem that determines whether the graph (horse-pace graph) has a Hamiltonian circuit or Hamiltonian path. .In our previous work we had studied and implemented image and video encryption by using KTM. In this General Program, the KTP is generalized to an m×n chessboard in a 2-dimensional space or an m×n×l chessboard in a 3-dimensional space to get a generalized knight's tour problem (GKTP), and to explore the existence of Hamiltonian circuit or Hamiltonian path of GKT. On this basis, we using divide-and-conquer, graph isomorph, algebra, number theory, ant colony optimization algorithm (ACO), neural network, genetic algorithm, parallel computing and other methods to solve the correlation problems with the GKTP, such as some sufficient conditions for a 3D chessboard not to admit a closed or open GKT with given move patterns, the quickly solution algorithm for GKTP, the number of Hamiltonian circuits or Hamiltonian paths of the GKTP, etc. We shall study the application of the Hamiltonian circuits or Hamiltonian paths of GKT in generating M sequence (de Bruijn) and study simultaneous compression & encryption method for images and videos. Moreover, we shall explore the relation of the "KTP parameters" (i.e. the begin point-end point, the step length, the touring direction, the searching- backtracking strategy of a knight's tour) with the existence and the number of Hamiltonian circuits or Hamiltonian paths, so as to establish the base for designing the cryptosystem of simultaneously compress & encrypt for images and videos, to provide a new efficient and safe transmition schemes for image and video.

图像和视频高效、安全传输越来越需要，这激发我们从事图像和视频压缩加密同步技术的研究。加密造成相关性破坏，影响压缩性能；压缩后用传统方法加密又不大适合数据量大的图像和视频。本项目探索利用广义骑士巡游来解决这一矛盾的方法。.本项目将骑士巡游问题推广到2维和3维空间，率先研究并证实了广义骑士巡游Hamilton路（圈）可应用于图像和视频加密。在此基础上，用分治、同构、代数、数论、蚁群优化等方法，探索3维空间广义骑士巡游Hamilton路（圈）存在的条件、快速求解算法及Hamilton路（圈）数量等；研究Hamilton路（圈）在M序列生成、图像和视频压缩与加密同步进行算法中的应用；揭示巡游起止点、巡游步长、搜索策略等"巡游参数"与Hamilton路（圈）的存在性、数量等的关系，为图像和视频压缩与加密同步的密码体制设计及安全性评估等问题奠定基础，为图像和视频高效、安全传输提供新的解决方案。

在一些应用场合，图像和视频需要高效、安全传输，传统的压缩、加密分离方法不太适应新的应用需求，这需要研究新的图像和视频压缩加密同步技术。.本项目主要进行了4方面研究：广义骑士巡游Hamilton路和圈的快速求解生成方法、基于Hamilton圈的M序列生成方法、图像和视频压缩加密同步算法及相关应用研究。.第一，将SemiHam算法推广到了三维空间的广义骑士巡游问题求解，能用计算机快速求出部分广义骑士(1,k1,k2)在3维空间的巡游随机Hamilton圈；证明得到了广义棋盘存在或不存在Hamilton圈的5个定理。.第二，研究并设计了基于骑士巡游Hamilton圈的2类伪随机序列生成方法，得到的序列通过了NIST SP800-22的随机性测试。.第三，提出了6类图像和视频加密压缩算法，主要有：（1）基于广义骑士巡游的RGB图像加密压缩算法，该算法在满足一定安全性的前提下，压缩效率得到了很大的提高；（2）基于离散超混沌系统和改进zigzag扫描编码的加密压缩同步算法，实现了对明文图像的快速加密，同时得到了较高的压缩性能和安全性能；（3）基于CABAC的视觉质量可控的快速感知加密算法，该算法对码率无影响，编码时间仅增加 7‰左右，视频质量由参数调控以满足感知加密的应用需求。（4）基于图像分块DCT系数置乱加密算法，该算法能抵抗已知明图像和Non-zero-counting攻击；（5）基于格式变换的图像压缩加密算法，该算法实现了压缩加密同步且加密速度快、加密图像所占存储空间几乎不变；（6）基于混沌和小波变换的图像加密压缩算法，实现了加密和压缩同时进行，具有良好的加密和压缩性能；.第四，研究了加密图像和视频在图像检索、隐私保护、篡改认证等方面的应用，提出了3种比较有实用价值的方法。.在基金资助下，已发表SCI论文8篇，国内核心期刊论文11篇，国际会议论文9篇，已获授权国家发明专利3项。联合培养博士研究生2名，已培养毕业硕士研究生9名。.通过研究，发展了广义骑士巡游问题的相关理论和求解方法、完善了图像和视频加密压缩的理论和方法，并为实际应用提供了关键技术支撑。