Comparison of the efficiencies of image compression algorithms based on separable and nonseparable two-dimensional Haar wavelet bases

Compression algorithms for digital images are described that are based on nonseparable two-dimensional wavelet transforms on nonrectangular supports. The efficiencies of these algorithms are experimentally investigated and compared with those of a compression algorithm based on a separable Haar wavelet basis. Aleksandr Mikhailovich Belov. Born 1980. Graduated from the Samara State Aerospace University. Received candidate’s degree in physics and mathematics in 2007. Currently is a junior scientist at the Institute of Image Processing, Russian Academy of Sciences. Scientific interests: discrete orthogonal transforms, fast algorithms for discrete orthogonal transforms, and the theory of canonical number systems. Author of 20 publications, including 8 papers. Member of the Russian Pattern Recognition and Image Processing Association.     

计算Fibonacci数的对分迭代算法

Fibonacci数有很多应用,它的求值有几种不同的算法。对原有算法的时间复杂性在理论分析的基础上进行了实验的分析,实验结果表明采用逐项递归算法、对分递归算法、直接求值算法和迭代算法的程序,其运行速度依次递升。论文还提出了一种对分迭代算法,它比原有最快的迭代算法约快20%～60%。     

New cellular methods for matrix multiplication

This paper proposes two new cellular methods of matrix multiplication that allow one to obtain cellular analogs of well-known matrix multiplication algorithms with reduced computational complexities as compared with analogs derived on the basis of well-known cellular methods of matrix multiplication. The new fast cellular method reduces the multiplicative, additive, and overall complexities of the mentioned algorithms by 15%. The new mixed cellular method combines the Laderman method with the proposed fast cellular method. The interaction of these methods reduces the multiplicative, additive, and overall complexities of the matrix multiplication algorithms by 28%. Computational complexities of these methods are estimated using a model of obtaining cellular analogs of the traditional matrix multiplication algorithm.     

基于提升框架的实时视频降噪方法

针对基于离散小波变换的视频降噪方法难于实时处理的问题,提出了一种基于提升框架的可实时处理的视频降噪方法。首先,对每帧图像利用提升框架进行多级小波分解,得到尺度系数和小波系数;然后,对不同层次的小波系数采用软阈值收缩方法进行滤波;小波逆变换后,利用时间域滤波方法进一步提高降噪效果。实验结果表明,该方法具有较好的实时性和去噪效果。     

A unified cellular method for matrix multiplication

A unified cellular method for matrix multiplication is proposed. The method is a hybrid of three methods, namely, Strassen’s and Laderman’s recursive methods and a fast cellular method for matrix multiplication. The interaction of these three methods provides the highest (in comparison with well-known methods) percentage (equal to 37%) of minimization of the multiplicative, additive, and overall complexities of cellular analogues of well-known matrix multiplication algorithms. The estimation of the computational complexity of the unified method is illustrated by an example of obtaining a cellular analogue of the traditional matrix multiplication algorithm.     

Fast running algorithm for discrete <Emphasis Type="Italic">W</Emphasis> transform

A fast algorithm for computing the running type-II discrete W transform (DWT-II) is proposed. The algorithm is based on a recursive relationship between three subsequent local DWT-II spectra. The computational complexity of the algorithm is compared with that of known fast and running DWT-II algorithms. Fast inverse algorithms for signal processing in the domain of the running DWT-II are also proposed. Vitaly Kober obtained his MS degree in Applied Mathematics from the Air-Space University of Samara (Russia) in 1984, and his PhD degree in 1992 and Doctor of Sciences degree in 2004 in Image Processing from the Institute of Information Transmission Problems, Russian Academy of Sciences. Now he is a titular researcher at the Centro de Investigacion Cientifica y de Educacion Superior de Ensenada (Cicese), Mexico. His research interests include signal and image processing, pattern recognition. Iosif A. Ovseevich graduated from the Moscow Electrotechnical Institute of Telecommunications. Received candidate’s degree in 1953 and doctoral degree in information theory in 1972. At present he is Emeritus Professor at the Institute of Information Transmission Problems of the Russian Academy of Sciences. His research interests include information theory, signal processing, and expert systems. He is a Member of IEEE, Popov Radio Society.     

小波变换与纹理合成相结合的图像修复

目的 为了克服传统的图像修复算法在结构和纹理边界的错误修复,利用小波变换域的系数特征,探讨了一种基于小波变换与纹理合成相结合的修复算法。方法 算法先利用小波变换将待修复图像分解成具有不同分辨率的低频子图和高频子图,然后根据不同子图各自的特征分别进行修复。对代表图像结构信息的低频子图,采用FMM(fast marching method)算法进行修复;对代表图像纹理信息的高频子图,根据各子图中小波系数的特征,利用纹理合成方法进行修复。结果 分层、分类修复方法对边缘破损具有良好的修复效果,其峰值信噪比相比于传统算法提高了1~2 dB。结论 与相关算法相比,本文算法的综合修复能力较好,可以有效修复具有较强边缘和丰富纹理的破损图像,尤其对破损自然图像的修复,修复后图像质量得到较大提升,修复效果更符合人眼视觉效应。     

基于二维经验模态分解的医学图像融合算法

提出了一种自适应的二维经验模态分解(bidimensional empirical mode decomposition,简称BEMD)医学图像融合算法.待融合的医学图像经过BEMD分解成二维的内蕴模函数(bidimensional intrinsic mode function,简称BIMF)和趋势图像.BIMF图像经过Hilbert-Huang变换提取图像特征,然后,图像分解的各部分数据在区域融合规则下形成综合BEMD表示.最后,综合BEMD表示进行BEMD逆变换得到融合后的医学图像.BEMD分解方法是一种完全自适应的数据分解表达形式,具有比Fourier变化和小波分解更好的特性.该医学图像融合算法不需要预先定义滤波器或小波函数.实验结果表明,该算法与传统融合算法相比性能优越,能够大幅度提高融合图像的质量.     

基于快速非抽样小波变换的岩屑多聚焦图像融合

针对传统非抽样小波变换算法较复杂的缺点,结合空、频域处理上的特点,提出了一种基于快速非抽样小波变换的多聚焦图像融合算法。与之前基于非抽样小波变换的融合算法不同,该算法取消了反变换,它根据高频小波系数绝对值和取大原则,融合图像像素值直接在对应源图像的相应位置取值,从而大大提高了图像处理的实时性,改善了融合效果。通过与六种非抽样小波变换融合算法的比较,以及快速非抽样小波变换与非抽样小波变换的融合时间对比,直观地给出了该算法的效果和时间优势。     

Image denoising using statistical model based on quaternion wavelet domain

Image denoising is the basic problem of image processing.Quaternion wavelet transform is a new kind of multiresolution analysis tools.Image via quaternion wavelet transform,wavelet coefficients both in intrascale and in interscale have certain correlations.First,according to the correlation of quaternion wavelet coefficients in interscale,non-Gaussian distribution model is used to model its correlations,and the coefficients are divided into important and unimportance coefficients.Then we use the non-Gaussian distribution model to model the important coefficients and its adjacent coefficients,and utilize the MAP method estimate original image wavelet coefficients from noisy coefficients,so as to achieve the purpose of denoising.Experimental results show that our algorithm outperforms the other classical algorithms in peak signal-to-noise ratio and visual quality.     

递归最小二乘循环神经网络

针对循环神经网络(Recurrent neural networks, RNNs)一阶优化算法学习效率不高和二阶优化算法时空开销过大,提出一种新的迷你批递归最小二乘优化算法.所提算法采用非激活线性输出误差替代传统的激活输出误差反向传播,并结合加权线性最小二乘目标函数关于隐藏层线性输出的等效梯度,逐层导出RNNs参数的迷你批递归最小二乘解.相较随机梯度下降算法,所提算法只在RNNs的隐藏层和输出层分别增加了一个协方差矩阵,其时间复杂度和空间复杂度仅为随机梯度下降算法的3倍左右.此外,本文还就所提算法的遗忘因子自适应问题和过拟合问题分别给出一种解决办法.仿真结果表明,无论是对序列数据的分类问题还是预测问题,所提算法的收敛速度要优于现有主流一阶优化算法,而且在超参数的设置上具有较好的鲁棒性.     

Accurate and speedy computation of image Legendre moments for computer vision applications

A novel algorithm that permits the fast and accurate computation of the Legendre image moments is introduced in this paper. The proposed algorithm is based on the block representation of an image and on a new image representation scheme, the Image Slice Representation (ISR) method. The ISR method decomposes a gray-scale image as an expansion of several two-level images of different intensities (slices) and thus enables the partial application of the well-known Image Block Representation (IBR) algorithm to each image component. Moreover, using the resulted set of image blocks, the Legendre moments’ computation can be accelerated through appropriate computation schemes. Extensive experiments prove that the proposed methodology exhibits high efficiency in calculating Legendre moments on gray-scale, but furthermore on binary images. The newly introduced algorithm is suitable for the computation of the Legendre moments for pattern recognition and computer vision applications, where the images consist of objects presented in a scene.     

Content-based image indexing and searching using Daubechies' wavelets

This paper describes WBIIS (Wavelet-Based Image Indexing and Searching), a new image indexing and retrieval algorithm with partial sketch image searching capability for large image databases. The algorithm characterizes the color variations over the spatial extent of the image in a manner that provides semantically meaningful image comparisons. The indexing algorithm applies a Daubechies' wavelet transform for each of the three opponent color components. The wavelet coefficients in the lowest few frequency bands, and their variances, are stored as feature vectors. To speed up retrieval, a two-step procedure is used that first does a crude selection based on the variances, and then refines the search by performing a feature vector match between the selected images and the query. For better accuracy in searching, two-level multiresolution matching may also be used. Masks are used for partial-sketch queries. This technique performs much better in capturing coherence of image, object granularity, local color/texture, and bias avoidance than traditional color layout algorithms. WBIIS is much faster and more accurate than traditional algorithms. When tested on a database of more than 10 000 general-purpose images, the best 100 matches were found in 3.3 seconds.     

基于小波变换的图像融合算法研究

在小波变换的基础上提出了一种多光谱图像融合的算法,并与其它几种算法进行了比较,仿真结果表明该算法对图像的增强有较好的效果。
     

Fast k-nearest neighbor search algorithm based on pyramid structure of wavelet transform and its application to texture classification

Traditional fast k-nearest neighbor search algorithms based on pyramid structures need either many extra memories or long search time. This paper proposes a fast k-nearest neighbor search algorithm based on the wavelet transform, which exploits the important information hiding in the transform coefficients to reduce the computational complexity. The study indicates that the Haar wavelet transform brings two kinds of important pyramids. Two elimination criteria derived from the transform coefficients are used to reject those impossible candidates. Experimental results on texture classification verify the effectiveness of the proposed algorithm.     

基于2维灰度熵阈值选取快速迭代的图像分割

目的 为了使图像阈值分割的精度和速度进一步提高,提出了一种基于2维灰度熵阈值选取快速迭代的图像分割方法。方法 首先,提出了1维灰度熵阈值选取的快速迭代算法;然后,考虑图像目标和背景的类内灰度均匀性,给出了基于灰度—邻域平均灰度级直方图的灰度熵阈值选取准则;最后,提出了2维灰度熵阈值选取的快速迭代算法,并采用递推方式计算准则函数中的中间变量,避免其重复运算,加快了运算速度,大大减少了运算量。结果 大量实验结果表明,与近年来提出的3种阈值分割法相比,所提出的方法分割性能更优,分割后的图像中目标区域完整,边缘清晰,细节丰富且运行时间短,仅为基于混沌小生境粒子群优化的二维斜分倒数熵分割法运行时间的3%左右。结论 本文方法对不同类型灰度级图像的分割效果及运行速度均有明显优势,是实际系统中可选择的一种快速有效的图像分割方法。     

Efficiency of the reduced wise algorithm over a set of convolution algorithms

A reduction operation and the design of a reduced wise algorithm over a set of known algorithms of unvarying complexity are addressed. A direct convolution algorithm and the best-known algorithms based on fast discrete orthogonal transforms (with Cooley-Tukey and Good-Thomas decompositions and the Rader algorithm for short lengths) are used as a support set of known algorithms. It is shown that their combined use in the reduced wise algorithm decreases the computational complexity of the resulting convolution algorithm as compared to that of the algorithms in the support set. Alina Yur’evna Bavrina. Born 1980. Graduated from the Samara State Aerospace University in 2003. Received candidate’s degree in technical sciences in 2006. Junior researcher at the Image Processing Systems Institute of the Russian Academy of Sciences. Research interests: image processing, image compression, and geoinformation technology. Author of more than 20 publications, including 6 papers. Member of the Russian Association for Pattern Recognition and Image Analysis. Vladislav Valer’evich Myasnikov. Born 1971. Graduated from the Samara State Aerospace University (SSAU) in 1994. Started his graduate study at SSAU in 1995 and received candidate’s degree in technical sciences in 1998. Senior researcher at the Image Processing Systems Institute of the Russian Academy of Sciences and associate professor at the SSAU Department of Geoinformatics. Research interests: digital signal and image processing, geoinformatics, neural networks, and pattern recognition. Author of more than 60 publications, including 24 papers and 1 monograph (coauthored). Member of the Russian Association for Pattern Recognition and Image Analysis.     

Fast extraction of wavelet-based features from JPEG images for joint retrieval with JPEG2000 images

In this paper, some fast feature extraction algorithms are addressed for joint retrieval of images compressed in JPEG and JPEG2000 formats. In order to avoid full decoding, three fast algorithms that convert block-based discrete cosine transform (BDCT) into wavelet transform are developed, so that wavelet-based features can be extracted from JPEG images as in JPEG2000 images. The first algorithm exploits the similarity between the BDCT and the wavelet packet transform. For the second and third algorithms, the first algorithm or an existing algorithm known as multiresolution reordering is first applied to obtain bandpass subbands at fine scales and the lowpass subband. Then for the subbands at the coarse scale, a new filter bank structure is developed to reduce the mismatch in low frequency features. Compared with the extraction based on full decoding, there is more than 72% reduction in computational complexity. Retrieval experiments also show that the three proposed algorithms can achieve higher precision and recall than the multiresolution reordering, especially around the typical range of compression ratio.     

Two-dimensional discrete cosine transform on sliding windows

The discrete cosine transform (DCT) has been successfully used for a wide range of applications in digital signal processing. While there are efficient algorithms for implementing the DCT, its use becomes difficult in the sliding transform scenario where the transform window is shifted one sample at a time and the transform process is repeated. In this paper, a new two-dimensional sliding DCT (2-D SDCT) algorithm is proposed for fast implementation of the DCT on 2-D sliding windows. In the proposed algorithm, the DCT coefficients of the shifted window are computed by exploiting the recursive relationship between 2-D DCT outputs of three successive windows. The theoretical analysis shows that the computational requirement of the proposed 2-D SDCT algorithm is the lowest among existing 2-D DCT algorithms. Moreover, the proposed algorithm enables independent updating of each DCT coefficient.     

A unifying framework for linear estimation: Generalized partitioned algorithms

In this paper, generalized partitioned algorithms are presented that serve as the unifying framework for linear filtering and smoothing. The fundamental and all encompassing nature of the generalized partitioned algorithms (hereon denoted GPA) is clearly demonstrated by showing that the GPA contain as special cases important generalizations of past well-known linear estimation algorithms, as well as whole families of such algorithms, of which all previously obtained major filtering and smoothing algorithms are special cases. Specifically, generalized partitioned filtering and smoothing algorithms are given in terms of integral expressions, that are theoretically interesting, computationally attractive, as well as provide a unification of all previous approaches to linear filtering and smoothing, and clear delineation of their inter-relationships. In particular, the GPA for filtering are shown to contain as special cases families of filtering algorithms which constitute generalizations of the Kalman-Bucy, and Chandrasekhar algorithms as well as of the previously obtained partitioned algorithms of Lainiotis. These generalizations pertain to arbitrary initial conditions and time-varying models. Further, the GPA for smoothing are shown to contain two families of generalized backward and forward smoothing algorithms valid for arbitrary boundary conditions, of which all previous backward and forward algorithms are special cases. It is also shown that the GPA may also be given in terms of an imbedded generalized Chandrasekhar algorithm with the consequent computational advantages. Furthermore, the GPA are shown to serve as the basis of computationally effective, fast, and numerically robust algorithms for the numerical implementation of the estimation formulas. A particularly effective doubling algorithm is also given for calculating the steady-state filter. The partitioned numerical algorithms are given exactly in terms of a set of elemental solutions which are both simple as well as completely decoupled, and as such computable in either a parallel or serial processing mode. Moreover, the overall solution is given by a simple recursive operation on the elemental solutions.