A novel approach for fast codebook re-quantization

In this paper, we present a fast codebook re-quantization algorithm (FCRA) using codewords of a codebook being re-quantized as the training vectors to generate the re-quantized codebook. Our method is different from the available approach, which uses the original training set to generate a re-quantized codebook. Compared to the traditional approach, our method can reduce the computing time dramatically, since the number of codewords of a codebook being re-quantized is usually much smaller than the number of original training vectors. Our method first classifies codewords of a re-quantized codebook into static and active groups. This approach uses the information of codeword displacements between successive partitions to reject impossible candidates in the partition process of codebook re-quantization. By implementing a fast search algorithm used for vector quantization encoding (MFAUPI) in the partition step of FCRA, the computational complexity of codebook re-quantization can be further reduced significantly. Using MFAUPI, the computing time of FCRA can be reduced by a factor of 1.55–3.78. Compared with the available approach OARC (optimization algorithm for re-quantization codebook), our proposed method can reduce the codebook re-quantization time by a factor of about 8005 using a training set of six real images. This reduction factor is increased when the re-quantized codebook size and/or training set size are increased. It is noted that our proposed algorithm can generate the same re-quantized codebook as that produced by the OARC.     

A novel encoding algorithm for vector quantization using transformed codebook

In this paper, a novel encoding algorithm for vector quantization is presented. Our method uses a set of transformed codewords and partial distortion rejection to determine the reproduction vector of an input vector. Experimental results show that our algorithm is superior to other methods in terms of the computing time and number of distance calculations. Compared with available approaches, our method can reduce the computing time and number of distance calculations significantly. Compared with the available best method of reducing the number of distance computations, our approach can reduce the number of distance calculations by 32.3-67.1%. Compared with the best encoding algorithm for vector quantization, our method can also further reduce the computing time by 19.7-23.9%. The performance of our method is better when a larger codebook is used and is weakly correlated to codebook size.     

Fast agglomerative clustering using information of k-nearest neighbors

In this paper, we develop a method to lower the computational complexity of pairwise nearest neighbor (PNN) algorithm. Our approach determines a set of candidate clusters being updated after each cluster merge. If the updating process is required for some of these clusters, k-nearest neighbors are found for them. The number of distance calculations for our method is O(N²), where N is the number of data points. To further reduce the computational complexity of the proposed algorithm, some available fast search approaches are used. Compared to available approaches, our proposed algorithm can reduce the computing time and number of distance calculations significantly. Compared to FPNN, our method can reduce the computing time by a factor of about 26.8 for the data set from a real image. Compared with PMLFPNN, our approach can reduce the computing time by a factor of about 3.8 for the same data set.     

基于数据流聚类策略的GPU码书初始化算法

码书生成是基于矢量量化压缩体绘制的关键之一。在码书生成中,初始码书对码书生成算法有较大的影响。现有的码书初始化方法需要对原始海量数据进行多次迭代,数据频繁在硬盘、内存和GPU（图形处理器）之间进行数据传输,导致算法效率不高。本文针对码书生成的初始码书提取问题,提出了基于数据流聚类策略的初始码书生成算法。其基本思想是将海量三维数据体当作一个数据流（分块）,对每一部分数据形成局部码书,再对所有的局部码书进行分类形成最终的初始码书。利用本方法可以极大的减少数据的读取和传输的次数,同时,充分利用GPU并行计算能力。通过仿真结果分析表明,本文提出的方法在效率上和效果上都有较大的提高。     

一种快速、有效的LBG初始码书生成算法

针对LBG算法依赖初始码书的问题,以贪婪树增长算法与码书间距最大化算法为基础,提出了一种新的LBG初始码书生成算法。该算法用贪婪树增长算法生成基础码书,再采用码书间距最大化算法从基础码书中生成初始码书。该算法相对于常用的分裂法降低了计算复杂度,节约了运算时间。与两种基本算法相比,它降低了量化的失真度与平均谱包络失真。     

利用PNN算法改进初始码书的GLA算法

针对改进广义Lloyd算法（GLA）对初始码书的敏感性,提出用成对最近邻（PNN）算法训练码书作为GLA算法的初始码书,再由GLA算法产生最终码书。PNN算法得到的码书作为GLA算法的初始码书,其码字能在整个输入矢量空间中很好地散开,尽可能地占据输入概率密度较大区域,提高最后码书的质量。仿真实验中,利用正态分布的随机数训练码书,恢复一段正态分布的随机数,采用Mahalanobis失真测度评价恢复数据的失真度。仿真结果表明,改进算法降低了GLA算法对初始码书的敏感性,提高了最终训练码书的质量,降低了恢复数据的失真。     

Fast global k-means clustering using cluster membership and inequality

In this paper, we present a fast global k-means clustering algorithm by making use of the cluster membership and geometrical information of a data point. This algorithm is referred to as MFGKM. The algorithm uses a set of inequalities developed in this paper to determine a starting point for the jth cluster center of global k-means clustering. Adopting multiple cluster center selection (MCS) for MFGKM, we also develop another clustering algorithm called MFGKM+MCS. MCS determines more than one starting point for each step of cluster split; while the available fast and modified global k-means clustering algorithms select one starting point for each cluster split. Our proposed method MFGKM can obtain the least distortion; while MFGKM+MCS may give the least computing time. Compared to the modified global k-means clustering algorithm, our method MFGKM can reduce the computing time and number of distance calculations by a factor of 3.78-5.55 and 21.13-31.41, respectively, with the average distortion reduction of 5,487 for the Statlog data set. Compared to the fast global k-means clustering algorithm, our method MFGKM+MCS can reduce the computing time by a factor of 5.78-8.70 with the average reduction of distortion of 30,564 using the same data set. The performances of our proposed methods are more remarkable when a data set with higher dimension is divided into more clusters.     

基于改进CPN的快速矢量量化

对向传播神经网络(CPN)可以作为矢量量化器用于图像压缩，但CPN学习算法在进行码书设计时存在两个明显的缺陷。本文对CPN学习算法进行改进，提出了一种新的码书设计算法——快速竞争学习及误差修正算法(FCLECA)和一个基于改进CPN的快速矢量量化器模型，并讨论了FCLECA中的重要步骤和重要参数。仿真实验结果表明，FCLECA在生成高质量码书的同时大幅减少了训练时间，可以有效地实现快速矢量量化。     

基于概率分布估计算法的进化规划码书设计算法

提出一种以最近邻划分变异为搜索策略,并以EP(进化规划)与EDA(概率密度估计算法)相结合的混合进化方法作为搜索引擎的新型码书设计算法.在最近邻划分上,引入最近邻划分控制因子作为进化算法的染色体表示,实现最近邻划分变异,从而改变质心运动轨迹.染色体与矢量同维,编码空间相对较小,并且进化操作易于控制和实现.在混合进化方法中,EDA为EP提供了最优个体的搜索方向,加速了算法的收敛速度.实验结果表明该方法是能有效提高码书性能的一种优化方法.     

一种快速图像块填充算法及其在遥感影像处理中的应用

针对Drori的图像块填充算法计算复杂度高,计算量大的缺点,提出了一个快速的改进算法。并结合光学遥感影像的特点,将其应用到遥感影像中的厚云及阴影去除上。实验结果表明,在能够取得近似相同结果的情况下,本文算法与Drori算法相比,能够较好地缩短计算时间。     

一种新的矢量量化编码算法

矢量量化是低位率图像压缩非常有效的一种方法 ,矢量量化基本方法的一个关键问题是需要较长的编码时间 ,尤其对于高维矢量或大的码书 .提出了一种基于 1/ 2 L2 -范数金字塔数据结构的快速编码算法 ,明显加快了编码过程 ,减少了实际对存储器的需求 ,特别对高维矢量和大的码书效果更显著 ,同时保持与全搜索方法相同的编码质量     

改进的基于主分量分析的码书设计算法

针对基于主分量分析和遗传算法的码书设计算法中当码书大小超过64时码书性能下降的问题,提出了一种改进的码书设计算法．首先采用主分量分析对训练矢量降维以减少计算复杂度,然后利用遗传算法的全局优化能力计算得到接近全局最优的码书．实验结果表明,与原算法和经典的LBG算法相比,文中算法所生成的码书性能有了明显提高,而且计算时间也少于LBG算法．     

基于预测码矢的快速搜索新算法

在ｋ维欧氏空间Ｒｋ中，给定一个有限子集Ｗ及一个向量ｘ，如何搜索Ｗ中与ｘ距离最近的向量，具有重要的实际应用价值，尤其在图象的矢量量化编码、神经网络模式识别［１］等问题中，快速搜索起决定性的作用。在分析已有快速搜索算法的基础上，给出一种新的快速搜索算法，该算法利用图象相邻块的码书地址，作为当前块的预测值，使搜索空间缩小更快。     

基于改进人工蜂群的图像矢量量化码书设计算法

为了进一步提高图像矢量量化的码书质量,提出了一种新的图像压缩矢量量化码书设计算法。该算法采用均方误差(MSE)作为码书设计的适应度函数,利用改进的人工蜂群算法进行适应度函数的优化求解,增强了算法的自组织性和收敛性,大大减少了陷入局部收敛的可能性。将一种基于和值特性的快速码字搜索思想引入到码书设计算法中,使算法计算量明显降低。仿真结果表明,该算法具有计算时间短、收敛速度快的优点,并且生成的码书质量好、稳定性强。     

利用帕累托非支配关系实现高效三目标差分进化的方法

在多目标进化算法中,时间复杂度过高是普遍的问题,特别是三个目标函数以上时,解的等级分配占用了过多运算时间。针对三目标问题,利用帕累托支配关系,对解的等级分配进行研究,发现经典的等级排序及分配方法存在一定冗余操作,需对全部的解先排序后,才能再分配等级并选择下一代,造成部分不必要的运算。为减少该冗余,利用帕累托非支配关系结合差分进化,实现高效三目标进化算法。算法每次迭代对种群中最高等级的个体进行计算,在分配等级同时进行选择后代个体操作,当后代种群生成时便跳出计算,从而减少个体的计算数量,降低运算量,同时给出该方法的相关理论分析和证明过程。然后,针对一系列三目标优化问题,将提出方法与著名排序方法NSGAII,及近年来优秀的ENS方法进行对比实验。仿真实验结果表明,提出方法在时间复杂度和收敛速度上优于经典方法,稍差于ENS方法。在标准测试函数DTLZ1-DTLZ6的性能上,提出方法近似于ENS方法,优于NSGAII算法,从而验证了提出方法的有效性和正确性。     

基于多相机的多目标跟踪算法

多目标的稳定跟踪是计算机视觉领域的一个具有挑战性的问题. 本文提出了一种基于多相机的多目标定位跟踪算法.首先, 利用不同高度层上的标志物, 计算基于多层的不同视角间的单应性矩阵.然后, 利用码本模型对背景进行建模, 检测多个视角的前景似然信息.最后, 通过单应性变换获得多目标在不同高度层上的定位信息, 利用最短路径优化算法实现跟踪. 与其他算法相比, 本算法不需要计算多相机的隐消点, 降低了算法的复杂度, 提高了算法的准确性.采用最短路径优化算法, 提高了跟踪算法的效率. 实验结果表明, 本算法对遮挡具有很强的鲁棒性, 并且能够满足实时性要求.     

云计算下基于改进遗传算法的聚类融合算法

针对无监督聚类缺少数据分类等先验信息、基聚类的准确性受聚类算法影响以及一般聚类融合算法空间复杂度高的问题,提出一种基于改进遗传算法的聚类融合算法（CEIGA）;同时针对传统聚类融合算法已经不能满足大规模数据处理对于时间的要求的问题,提出一种云计算下使用Hadoop平台的基于改进遗传算法的并行聚类融合算法（PCEIGA）。首先,基聚类生成机制产生的基聚类划分在完成簇标签转化后进行基因编码作为遗传算法的初始种群。其次,通过改进遗传算法的选择算子,保证基聚类的多样性;再根据改进的选择算子对染色体进行交叉和变异操作并使用精英策略得到下一代种群,保证基聚类的准确性。如此循环,使聚类融合最终结果达到全局最优,提高算法准确度。通过设计两个MapReduce过程并加入Combine过程减少节点通信,提高算法运行效率。最后,在UCI数据集上比较了CEIGA、PCEIGA和四个先进的聚类融合算法。实验结果表明,与先进的聚类融合算法相比,CEIGA性能最好;而PCEIGA能在不影响聚类结果准确度的前提下明显降低算法运行时间,提高算法效率。     

基于自组织特征映射神经网络的矢量量化

近年来,许多学者已经成功地将Ｋｏｈｏｎｅｎ的自组织特征映射（ＳＯＦＭ）神经网络应用于矢量量化（ＶＱ）图象压缩编码,相对于传统的ＫＬＢＧ算法,基于的ＳＯＦＭ算法的两个主要缺点是计算量大和生成的码书性能较差因此为了改善码书性能,对基本的ＳＯＦＭ算法的权值调整方法作了一些改进,同时为了降低计算量,又在决定获得胜神经元的过程中,采用快速搜索算法,在将改进的算法用于矢量量化码书设计后,并把生成的码书用于图象     

基于改进GA的云计算任务调度算法

云计算通常需要处理大量的计算任务,任务调度策略在决定云计算效率方面起着关键作用。如何合理地分配计算资源,有效地调度任务运行,使所有任务运行完成所需的时间较短、成本较小是个重要的问题。提出一种考虑时间-成本约束的遗传算法(TCGA),通过此算法调度产生的结果不仅能使任务完成所需的时间较短,而且成本较小。通过实验,将TCGA与考虑时间约束的遗传算法(TGA)、考虑成本约束的遗传算法(CGA)进行比较,实验结果表明,该算法是云计算中一种有效的任务调度算法。     

使用2-范数匹配的快速分形图像编码算法

尽管分形图像压缩在高压缩比时具有高的重建图像质量,但由于它编码过程耗时而未能在图像压缩领域广泛应用。为了提高分形图像编码过程的速度,提出了基于2－范数匹配的快速分形图像编码算法,该算法先把码书里的码块按2－范数大小赋序,然后对每个输入Range块,在赋序码书中寻找与它的2－范数最接近的码块,进而在这个码块的领域内搜索Range块的最佳匹配块。计算机仿真结果显示,在不影响基本分形图像编码算法解码图像质量的情况下,该方案大大加快了它的编码速度。