On the design of high-performance algorithms for aligning multiple protein sequences on mesh-based multiprocessor architectures

In this paper, we address the problem of multiple sequence alignment (MSA) for handling very large number of proteins sequences on mesh-based multiprocessor architectures. As the problem has been conclusively shown to be computationally complex, we employ divisible load paradigm (also, referred to as divisible load theory, DLT) to handle such large number of sequences. We design an efficient computational engine that is capable of conducting MSAs by exploiting the underlying parallelism embedded in the computational steps of multiple sequence algorithms. Specifically, we consider the standard Smith–Waterman (SW) algorithm in our implementation, however, our approach is by no means restrictive to SW class of algorithms alone. The treatment used in this paper is generic to a class of similar dynamic programming problems. Our approach is recursive in the sense that the quality of solutions can be refined continuously till an acceptable level of quality is achieved. After first phase of computation, we design a heuristic scheme that renders the final solution for MSA. We conduct rigorous simulation experiments using several hundreds of homologous protein sequences derived from the Rattus Norvegicus and Mus Musculus databases of olfactory receptors. We quantify the performance based on speed-up metric. We compare our algorithms to serial or single machine processing approaches. We testify our findings by comparing with conventional equal load partitioning (ELP) strategy that is commonly used in the parallel processing literature. Based on our extensive simulation study, we observe that DLT paradigm offers an excellent speed-up characteristics and provides avenues for its use in several other biological sequence processing related problem. This study is a first time attempt in using the DLT paradigm to devise efficient strategies to handle large scale multiple protein sequence alignment problem on mesh-based multiprocessor systems.     

Handling biological sequence alignments on networked computing systems: A divide-and-conquer approach

In this paper, we address the biological sequence alignment problem, which is one of the most commonly used steps in several bioinformatics applications. We employ the Divisible Load Theory (DLT) paradigm that is suitable for handling large-scale processing on network-based systems to achieve a high degree of parallelism. Using the DLT paradigm, we propose a strategy in which we carefully partition the computation work load among the processors in the system so as to minimize the overall computation time of determining the maximum similarity between the DNA/protein sequences. We consider handling such a computational problem on networked computing platforms connected as a linear daisy chain. We derive the individual load quantum to be assigned to the processors according to computation and communication link speeds along the chain. We consider two cases of sequence alignment where post-processes, i.e., trace-back processes that are required to determine an optimal alignment, may or may not be done at individual processors in the system. We derive some critical conditions to determine if our strategies are able to yield an optimal processing time. We apply three different heuristic strategies proposed in the literature to generate sub-optimal solutions for processing time when the above conditions cannot be satisfied. To testify the proposed schemes, we use real-life DNA samples of house mouse mitochondrion and the DNA of human mitochondrion obtained from the public database GenBank [GenBank, http://www.ncbi.nlm.nih.gov] in our simulation experiments. By this study, we conclusively demonstrate the applicability and potential of the DLT paradigm to such biological sequence related computational problems.     

一种指纹图像的快速分割方法

利用数学形态学变形虫法进行指纹图像分割时计算量大,导致分割速度变慢。针对该问题,提出一种将数学形态学变形虫法和离散小波变换相结合的指纹图像快速分割方法。先对原始图像进行小波分解,再对获取的低频图像采用形态学变形虫分割。实验结果表明,该方法在保证良好分割精度的同时分割速度较快。     

基于小波变换的自同步音频水印算法

该文提出了一种基于DWT的自同步音频水印算法．该算法具有如下特点：(1)在隐藏水印信息的同时，嵌入一个同步信号，使水印具有自同步能力；(2)同步信号与水印隐藏于DWT域低频子带，在改善同步信号鲁棒性的同时，利用DWT的时频局部特性，有效地提高在变换域内搜索同步信号的效率，较好地解决了同步信号鲁棒性与其搜索计算量之间的矛盾．实验表明，所提出的方法在抵抗各种通用的音频处理和攻击(如高斯噪声、MP3压缩、重采样、重量化、裁剪等)方面具有良好的性能．     

Effective input order of dynamics learning tree

In this paper, we discuss about the learning performance of dynamics learning tree (DLT) while mainly focusing on the implementation on robot arms. We propose an input-order-designing method for DLT. DLT has been applied to the modeling of boat, vehicle, and humanoid robot. However, the relationship between the input order and the performance of DLT has not been investigated. In the proposed method, a developer is able to design an effective input order intuitively. The proposed method was validated in the model learning tasks on a simulated robot manipulator, a real robot manipulator, and a simulated vehicle. The first/second manipulator was equipped with flexible arm/finger joints that made uncertainty around the trajectories of manipulated objects. In all of the cases, the proposed method improved the performance of DLT.     

Data compression techniques in Wireless Sensor Networks

The advancement in the wireless technologies and digital integrated circuits led to the development of Wireless Sensor Networks (WSN). WSN consists of various sensor nodes and relays capable of computing, sensing, and communicating wirelessly. Nodes in WSNs have very limited resources such as memory, energy and processing capabilities. Many image compression techniques have been proposed to address these limitations; however, most of them are not applicable on sensor nodes due to memory limitation, energy consumption and processing speed. To overcome this problem, we have selected Discrete Cosine Transform (DCT) and Discrete Wavelet Transform (DWT) image compression techniques as they can be implemented on sensor nodes. Both DCT and DWT allow an efficient trade-off between compression ratio and energy consumption. In this paper, both DCT and DWT are analyzed and implemented using TinyOS on TelosB hardware platform. The metrics used for performance evaluation are peak signal-to-noise ratio (PSNR), compression ratio (CR), throughput, end-to-end (ETE) delay and battery lifetime. Moreover, we also evaluated DCT and DWT in a single-hop and in multi-hop networks. Experimental results show that DWT outperforms DCT in terms of PSNR, throughput, ETE delay and battery lifetime. However, DCT provides better compression ratio than DWT. The average media access control layer (MAC) delay for both DCT and DWT is also calculated and experimentally demonstrated.     

Ridgelet变换在图像压缩中的应用

Ridgelet变换特别适合描述具有直线或超平面奇性的高维信号。本文将介绍有关Ridgelet变换的理论,并在此基础上提出一种新的基于正交有限Ridgelet变换（FRIT）的图像压缩方法一FRIT＋DWT。试验结果表明,FRIT＋DWT方法较传统Wavelet方法获得了更高的压缩比和更好的压缩效果。     

抗裁剪的DWT域CDMA扩频图像水印

提出一种具有抗裁剪自同步性能的DWT(Discrete Wavelet Transform)域DS-CDMA Direct Sequence Code Division Multiple Access)扩频图像水印算法.该算法具有如下特点:1)在 嵌入过程中,首先对水印数据进行CDMA扩频编码:在DWT的LL3子带隐藏水印信息的同时, 按一定结构模式嵌入同步信号,使水印具有自同步能力;2)在水印的盲检测过程中,先搜索同步 信息并对任意裁剪攻击后的图像进行准确定位,再进行CDMA解码检测出水印信息.算法利用 DWT的时频局部特性,有效地提高在变换域内搜索同步信号的效率.实验证明,采用本算法生 成的水印信息不仅对JPEG(Joint Picture Expert Group)压缩、Gaussian噪声攻击等具有很好的稳 健性,特别在抗裁剪攻击方面有比较明显的效果.     

An efficient implementation of one-dimensional discrete wavelet transform algorithms for GPU architectures

The Journal of Supercomputing - In this paper, the authors present several self-developed implementation variants of the Discrete Wavelet Transform (DWT) computation algorithms and compare their...     

Energy-based adaptive orthogonal FRIT and its application in image denoising

Efficient representation of linear singularities is discussed in this paper. We analyzed the relationship between the “wrap around” effect and the distribution of FRAT (Finite Radon Transform) coefficients first, and then based on study of some properties of the columnwisely FRAT reconstruction procedure, we proposed an energy-based adaptive orthogonal FRIT scheme (EFRIT). Experiments using nonlinear approximation show its superiority in energy concentration over both Discrete Wavelet Transform (DWT) and Finite Ridgelet Transform (FRIT). Furthermore, we have modeled the denoising problem and proposed a novel threshold selecting method. Experiments carried out on images containing strong linear singularities and texture components with varying levels of addictive white Gaussian noise show that our method achieves prominent improvement in terms of both SNR and visual quality as compared with that of DWT and FRIT.     

FPGA-based IP cores implementation for face recognition using dynamic partial reconfiguration

This paper presents a combination of novel feature vectors construction approach for face recognition using discrete wavelet transform (DWT) and field programmable gate array (FPGA)-based intellectual property (IP) core implementation of transform block in face recognition systems. Initially, four experiments have been conducted including the DWT feature selection and filter choice, features optimisation by coefficient selections and feature threshold. To examine the most suitable method of feature extraction, different wavelet quadrant and scales have been evaluated, and it is followed with an evaluation of different wavelet filter choices and their impact on recognition accuracy. In this study, an approach for face recognition based on coefficient selection for DWT is presented, and the significant of DWT coefficient threshold selection is also analysed. For the hardware implementation, two architectures for two-dimensional (2-D) Haar wavelet transform (HWT) IP core with transpose-based computation and dynamic partial reconfiguration (DPR) have been synthesised using VHDL and implemented on Xilinx Virtex-5 FPGAs. Experimental results and comparisons between different configurations using partial and non-partial reconfiguration processes and a detailed performance analysis of the area, power consumption and maximum frequency are also discussed in this paper.     

Across-scale process similarity based interpolation for image super-resolution

A pivotal step in image super-resolution techniques is interpolation, which aims at generating high resolution images without introducing artifacts such as blurring and ringing. In this paper, we propose a technique that performs interpolation through an infusion of high frequency signal components computed by exploiting ‘process similarity’. By ‘process similarity’, we refer to the resemblance between a decomposition of the image at a resolution to the decomposition of the image at another resolution. In our approach, the decompositions generating image details and approximations are obtained through the discrete wavelet (DWT) and stationary wavelet (SWT) transforms. The complementary nature of DWT and SWT is leveraged to get the structural relation between the input image and its low resolution approximation. The structural relation is represented by optimal model parameters obtained through particle swarm optimization (PSO). Owing to process similarity, these parameters are used to generate the high resolution output image from the input image. The proposed approach is compared with six existing techniques qualitatively and in terms of PSNR, SSIM, and FSIM measures, along with computation time (CPU time). It is found that our approach is the fastest in terms of CPU time and produces comparable results.     

Face recognition using decimated redundant discrete wavelet transforms

As discrete wavelet transform (DWT) is sensitive to the translation/shift of input signals, its effectiveness could be lessened for face recognition, particularly when the face images are translated. To alleviate drawbacks resulted from this translation effect, we propose a decimated redundant DWT (DRDWT)-based face recognition method, where the decimation-based DWTs are performed on the original signal and its 1-stepshift, respectively. Even though the DRDWT realizes the decimation, it enables us to explore the translation invariant DWT representation for the periodic shifts of the probe image that is the most similar to the gallery images. Therefore, it can solve the problem of translation sensitivity of the original DWT and address the translation effect occurring between the probe image and the gallery image. To further improve the recognition performance, we combine the global wavelet features obtained from the entire face and the local wavelet features obtained from face patches to represent both holistic and detail facial features, apply separate classifiers to global and local features and combine the resulted global and local classifiers to form an ensemble classifier. Experimental results reported for the FERET and FRGCv2.0 databases show the effectiveness of the DRDWT method and quantify its performance.     

一种精简的二维DWT结构设计

设计了一种低功耗的二维离散小波变换(DWT)结构，用于无线传感器网络中的图像压缩。该结构实现了精简复杂性的(5,3)整数离散小波变换，采用流水线和延迟线技术，在获得高运算吞吐率的同时，使数据尽可能被处理单元高效利用，以减少对片内存储器和片外存储器的访问次数。多级二维DWT采用展开方法实现，这种方法可尽早开始下一级变换，不需要大的片内存储器和片内存取操作。模拟试验和FPGA实现验证了系统在满足需要性能的前提下具有低复杂性、低功耗、片内存储器小等优点。     

The secure wavelet transform

There has been an increasing concern for the security of multimedia transactions over real-time embedded systems. Partial and selective encryption schemes have been proposed in the research literature, but these schemes significantly increase the computation cost leading to tradeoffs in system latency, throughput, hardware requirements and power usage. In this paper, we propose a light-weight multimedia encryption strategy based on a modified discrete wavelet transform (DWT) which we refer to as the secure wavelet transform (SWT). The SWT provides joint multimedia encryption and compression by two modifications over the traditional DWT implementations: (a) parameterized construction of the DWT and (b) subband re-orientation for the wavelet decomposition. The SWT has rational coefficients which allow us to build a high throughput hardware implementation on fixed point arithmetic. We obtain a zero-overhead implementation on custom hardware. Furthermore, a Look-up table based reconfigurable implementation allows us to allocate the encryption key to the hardware at run-time. Direct implementation on Xilinx Virtex FPGA gave a clock frequency of 60 MHz while a reconfigurable multiplier based design gave a improved clock frequency of 114 MHz. The pipelined implementation of the SWT achieved a clock frequency of 240 MHz on a Xilinx Virtex-4 FPGA and met the timing constraint of 500 MHz on a standard cell realization using 45 nm CMOS technology.     

基于线对应的单应矩阵估计及其在视觉测量中的应用

单应矩阵估计在视觉测量、摄像机标定、三维重建等领域有重要的应用价值, 但是在具体应用中如何鲁棒、精确地估计单应矩阵仍是一个没有很好解决的问题. 在研究和实际应用中我们发现,直接线性方法在基于线对应的单应矩阵估计中会出现在某些特殊的摄像机姿态下误差较大的情况. 针对这一情况, 我们提出了一种基于线对应的归一化单应矩阵估计方法并将其应用到视觉测量中,即通过简单的归一化操作使测量矩阵元素的大小分布尽量均匀, 从而降低了测量矩阵的条件数, 提高了算法的鲁棒性, 同时又保持了直接线性方法简单、快速、易实现等优点. 模拟实验和真实图像实验均验证了该方法的有效性.     

基于小波变换的彩色图象数字水印算法

提出了一种基于离散小波变换（DWT）域的彩色图象序列加密数字水印新方法，算法选用了彩色图象RGB色彩空间的G分量嵌入水印，数字水印图象含有密钥信息，因此算法具有很好的安全性。同时利用人类视觉系统（HVS）的亮度掩蔽特性和纹理掩蔽特性，把低频分量根据局部纹理的强弱分成两类，将二值水印图象加密后自适应的嵌入到宿主图象的DWT域的低频分量中，从而很好的兼顾了水印的不可见性与鲁棒性。大量仿真结果表明本算法对于诸如JPEG压缩、高斯噪声干扰和图象剪切具有很好的鲁棒性。     

SAR复图像数据的CCSDS-IDC编码性能分析与四叉树编码

目的：CCSDS-IDC (国际空间数据系统咨询委员会-图像数据压缩) 是NASA制定的基于离散小波变换(DWT)尺度间衰减性的空间图像数据压缩标准,适用于合成孔径雷达(SAR)幅度图像及各类遥感图像的压缩。然而,与光学图像不同,常见的SAR图像都是复图像数据,其在干涉测高等许多场合具有广泛应用,分析研究CCSDS-IDC对SAR复图像数据的编码性能具有重要的应用价值。方法：由于SAR复图像数据不具有尺度间的衰减性,因此将其用于SAR复图像数据编码时性能较低。考虑到SAR复图像数据DWT系数呈现出聚类特性,提出将四叉树(QC)用于DWT域的SAR复图像数据编码,发现QC对SAR复图像数据具有高效的压缩性能。结果：实验结果表明,在同等码率下,对基于DWT的SAR复图像数据压缩, QC比CCSDS-IDC最多可提高幅度峰值信噪比4.4dB,平均相位误差最多可降低0.368;与基于方向提升小波变换（DLWT）的CCSDS-IDC相比,QC可提高峰值信噪比3.08dB,降低平均相位误差0.25;对其它类型的图像压缩,基于聚类的QC仍能获得很好的编码性能。结论：CCSDS-IDC对SAR复图像数据编码性能低下,而QC能获得很好的编码性能。对应于图像平滑分布的尺度间衰减性,其在某些特殊图像中可能不存在,而对应于图像结构分布的聚类特性总是存在的,故在基于DWT的图像编码算法设计中,应优先考虑利用小波系数的聚类特性,从而实现对更多种类图像的高效编码。     

Distributed scheduling strategy for divisible loads on arbitrarily configured distributed networks using load balancing via virtual routing

In this paper, we consider a scheduling problem for divisible loads originating from single or multiple sites on arbitrary networks. We first propose a generalized mathematical model and formulate the scheduling problem as an optimization problem with an objective to minimize the processing time of the loads. We derive a number of theoretical results on the solution of the optimization problem. On the basis of these first set of results, we propose an efficient algorithm for scheduling divisible loads using the concept of load balancing via virtual routing for an arbitrary network configuration. The proposed algorithm has three major attractive features. Firstly, the algorithm is simple to realize and can be implemented in a distributed fashion. The second one is in its style of working by avoiding the need for generating a timing diagram explicitly for any complex networks having an arbitrary network topology. The last one is its capability of handling divisible loads originating from both single and multiple sites. When divisible loads originate from a single node, we compare the proposed algorithm with a recently proposed RAOLD algorithm which is based on minimum cost spanning tree [J. Yao, V. Bharadwaj, Design and performance analysis of divisible load scheduling strategies on arbitrary graphs, Cluster Computing 7(2) (2004) 191–207]. When divisible loads originate from multiple sites, we test the performance on sparse, medium and densely connected networks. This is the first time in the divisible load theory (DLT) literature that such a generic approach for handling divisible loads originating from multiple sites on arbitrary networks employing load balancing via virtual routing is attempted.     

A regulatory control framework for decentrally governed DLT systems: Action design research

Although distributed ledger technology (DLT) systems seem to address conventional regulatory governance concerns, they also present systemic risks. This paper aims to address the risks of decentrally governed DLT systems. It achieves this by identifying regulatory controls that address the altered governance dynamics of decentralized systems. To address the research gap in DLT regulation, we co-designed regulatory control treatments with Australian regulatory DLT experts using a participatory action design research approach. This paper provides a theory-ingrained, practitioner-vetted framework to inform regulators, regulated entities and researchers of appropriate control responses to systemic and participant risks presented by decentrally governed DLT systems.