Computer Engineering & Science

A hybrid biogeography-based optimization

algorithm for task scheduling in cloud computing

TONG Zhao1,2，CHEN Hong-jian1,2，CHEN Ming1,2，MEI Jing1,2,LIU Hong1,2

2018, 40(05): 765-772. doi:

Abstract ( 137 )

PDF (887KB) ( 285 ) 　　

Task scheduling plays a critical role in cloud computing and is a key factor affecting the performance of cloud computing. It has been proved to be an NP problem. Heuristic algorithm is one of the most effective methods to solve this problem. This paper focuses on the Biogeography-Based Optimization (BBO) algorithm, which serves in recent years as a new heuristic algorithm. Because the BBO algorithm converges slowly in the solution process, by combining Particle Swarm Optimization (PSO) algorithm, we propose a novel task scheduling algorithm, named Hybrid Migrating Biogeography-Based Optimization (HMBBO). A comparison experiment using Makespan as the objective function is performed on the Cloudsim cloud simulation platform. The experiment results show that, compared with several classical heuristic algorithms, HMBBO has the advantages of strong optimization ability, fast convergence speed and high-quality solution, and provides a new way to solving the task scheduling problem in cloud computing environment.

A multithreaded parallel Delaunay triangulation

algorithm based on lock-free atomic operations

WANG Jun-ji1,2,ZHU Chao-yan1,2,4,CHEN Jian-jun1,2,ZHENG Peng3,5,XU Quan3

2018, 40(05): 773-779. doi:

Abstract ( 134 )

PDF (575KB) ( 163 ) 　　

This paper uses OpenMP to implement a fine-grain parallel incremental insertion algorithm for Delaunay triangulation, which adopts an exclusive criterion of cavity overlapping and lock-free atomic operations. Based on the serial algorithm, Hilbert sorting is introduced into the point set so that adjacent points are also geometrically adjacent. An exclusive criterion that the points can be inserted simultaneously only if their cavities share neither common elements nor common boundaries is introduced to guarantee that the whole mesh has the Delaunay property according to the Delaunay lemma. Each element uses an atomic variable to mark whether the element is occupied by any of the threads. While calculating the Delaunay cavities, threads try to occupy those elements, but only one of them can succeed to write the atomic variable, so the exclusivity of the algorithm is guaranteed. Numerical experiments on the platform with a 16-core Intel Xeon CPU E5-2640 v3 @ 2.60GHz and a 64 GiB memory show that,for a 107-point set, the algorithm can reach the speedup of 7.06 with 16 cores.

OpenCV parallel optimization on TI 6678 DSP

LI Jin1，LUO Xin-jie2，HU Xiao1,CHEN Yue-yue1

2018, 40(05): 780-786. doi:

Abstract ( 503 )

PDF (728KB) ( 332 ) 　　

Digital Signal Processing (DSP) is widely used in various industrial fields and military equipment fields. OpenCV is a common open source image processing algorithm library. However, there are few implementations for OpenCV transplantation and optimization on DSP platforms. In this paper, OpenCV is successfully transplanted on a TMS320C6678 DSP platform and generates an underlying support library with most functions preserved. Based on this, we deeply analyze the computational features and data flow of some OpenCV library functions running on this platform. As a result, an optimization method for these OpenCV library functions is proposed. This method combines DMA, Cache operations and OpenMP parallel frameworks, which are supported by TI 6678 architecture. According to this method, we implement the optimization and multi-core parallelism for a class of OpenCV library functions on the TI 6678 chip. With the help of our method, the optimized OpenCV library function running on a single core of TI 6678 chip can be speeded up by up to 3.6 times. On this basis, we parallelize this class of library functions on 8 cores, obtaining the speedup of 2.55 to 7.06.

A parallel multi-classifier fusion approach

based on selective ensemble

TAO Xiao-ling1,2,KANG Rui-nan3,LIU Li-yan3

2018, 40(05): 787-792. doi:

Abstract ( 138 )

PDF (529KB) ( 174 ) 　　

In order to solve the problem of large time and low accuracy in the process of multi-classifier fusion,a Parallel Multi-Classifier Fusion Approach based on Selective Ensemble (PMCF-SE) is proposed by adopting both the improved Baggingmethod and MapReduce technique. Our approach is based on the MapReduce parallel computing framework.In the Map phase,the base classifiers with better classification performance are selected. In the Reduce phase,the base classifiers of greater diversity are selected, and then the selected base classifiers are fused with the D-S evidence theory. Experimental results show that, compared with the stand-alone environment, the execution efficiency of the classification model in the cluster environment is improved. PMCF-SE has higher classification accuracy than the Bagging algorithm under different numbers of base classifiers.

A scalar multiplication structure for elliptic curve

over prime fields and its FPGA implementation

WU Gui-ming,WANG Miao,XIE Xiang-hui

2018, 40(05): 793-797. doi:

Abstract ( 119 )

PDF (453KB) ( 191 ) 　　

Based on a pipelined linear array for high radix Montgomery modular multiplication simplifying quotient determination, a scalar multiplication structure for elliptic curve over prime fields is proposed and implemented. The proposal uses the modified Jacobian projective coordinates to exploit the point addition and point doubling of elliptic curves, and adopts the Montgomery inverse algorithm proposed by Kaliski. Experimental results show that our structure can achieve better performance than the related work.

A BLAS library optimization method

based on genetic algorithm

SUN Cheng-guo1,LAN Jing2,JIANG Hao1

2018, 40(05): 798-804. doi:

Abstract ( 173 )

PDF (642KB) ( 226 ) 　　

Based on OpenBLAS and BLIS, the two open source linear algebra libraries, the performance optimization of dense matrix multiplication (GEMM) operation is studied. Aiming at how to select the key block parameters of GEMM, a performance optimization model is established. An improved genetic algorithm is used to solve the above performance optimization model. The performance value of the GEMM corresponding to a certain parameter combination (individual) is taken as the fitness of the individual. The optimal combination of block parameters is found through continuous iterative selection, crossover and mutation operations in order to make the performance of GEMM optimal. Numerical experiments show that the performance of GEMM based on genetic algorithm is better than the performance under the initial block parameters, and hence the optimization is achieved.

Privacy-preserving multi-recipient aggregate signcryption

for heterogeneous cryptography systems

NIU Shu-fen,NIU Ling,WANG Cai-fen,YANG Xi-yan,JIA Xiang-dong

2018, 40(05): 805-812. doi:

Abstract ( 108 )

PDF (617KB) ( 187 ) 　　

Taking into account the secure communication and privacy protection in heterogeneous cryptography systems, we propose a heterogeneous aggregate signcryption scheme from certificateless cryptosystems to identity-based cryptography systems, which allows multiple senders to communicate securely with multiple recipients. The scheme makes the senders anonymous in the system, and only trust agencies can track the senders’ real information. For the receivers, the disclosure of the legitimate recipients’ user information to unauthorized users is prevented by applying the Lagrange interpolation formula. In the random oracle model, it is proved that the scheme possesses indistinguishability against adaptive chosen ciphertext attacks and existential unforgeability against adaptive chosen-message attacks. Experimental results show that the scheme effectively improves the computational efficiency of the system.

Integrating Piazza Q&A and Open edX platforms

ZHANG Yan-ni1，LU Hui-mei1，XIANG Yong2

2018, 40(05): 813-820. doi:

Abstract ( 83 )

PDF (890KB) ( 136 ) 　　

The Piazza Q&A platform and the Open edX platform are independent of each other, which is inconvenient for users to utilize the platform data efficiently. In response to the above issue, this paper persists in storing Piazza Q&A data, uses the multi-tag filtering method to improve the searching ability of the Piazza Q&A data, uses the Piazza-Xblock plug-in to find and display the Piazza Q&A data on the Open edX platform, and uses URL parameters to directly access the Piazza specific pages, thus achieving the effect of intergrating the Piazza Q&A platform and Open edX platform.

RSS threshold model-based positioning

error suppression of Amorphous algorithm

SONG Hai-sheng,ZHU Chang-ju,WU Jia-xin,YANG Hong-wu

2018, 40(05): 821-828. doi:

Abstract ( 97 )

PDF (949KB) ( 140 ) 　　

For the problem that the positioning algorithm has a large error in wireless sensor networks under different communication models, based on the average network connectivity of the off-line computation of Amorphous algorithm, four RSS (Received Signal Strength) threshold models are built up to suppress the positioning error of Amorphous algorithm under different communication models. The threshold obtained from different threshold models can be utilized to modify the gradient of the algorithm to different extents, so that the positioning error is suppressed. Simulation results show that, when Amorphous algorithm passes through the Regular model, the optimal threshold model is selected between Regular threshold model and Log-normal threshold model. When the algorithm passes through the Log-normal model, the optimal threshold model is selected among Regular threshold model, Log-normal threshold model, DOI threshold model and RIM threshold model. When the algorithm passes through the DOI model and RIM model, the optimal threshold model is selected among Log-normal threshold model, DOI threshold model and RIM threshold model. Finally, the optimal threshold model of Amorphous algorithm under different communication models, communication radiuses and irregularity degrees can be obtained.

A human fall detection method

based on D-S evidence theory

SUN Zi-wen1,2,LI Song1,SUN Xiao-wen1

2018, 40(05): 829-835. doi:

Abstract ( 101 )

PDF (585KB) ( 123 ) 　　

To solve the problem of high false negative rate in human fall detection, a detection algorithm based on D-S evidence theory is studied. Acceleration sensors and gyro sensors are built into a smartphone to obtain the three-dimensional motion data of the human body's arm movement. A three-step moving average filter is used to preprocess the three-dimensional raw data obtained from the two types of sensors. Then, the detection features consisting of movement range, inclination degree and rotation degree are extracted from the three-dimensional preprocessed data. The dynamic time warping method is used for local detection according to the three features. The local decision results act as evidences to be fused by the combinational rule of D-S evidence theory to get the final global detection result, in which each evidence is modified by the weight of evidence to avoid the evidence conflict problem. Experimental results show that the accuracy of the proposed algorithm is higher than that of other algorithms, which can effectively improve the detection performance.

Design & implementation of a visual SLAM algorithm

based on Kinect sensor and ORB feature

XU Fen,WANG Zhen

2018, 40(05): 836-841. doi:

Abstract ( 150 )

PDF (935KB) ( 165 ) 　　

This paper designs and implements a visual Simultaneous Localization And Mapping (SLAM) algorithm based on embedded platform and Kinect sensors. Kinect sensors consist of a RGB camera and an infrared CMOS camera that uses structured light to measure depth. The algorithm uses the Oriented FAST and Rotated BRIEF (ORB) operator as the description information of the environmental feature points and uses the nearest neighbor repairing method based on edge detection to correct the depth image so as to obtain a complete depth map. Based on this, Locality-Sensitive Hashing (LSH) algorithm is used to match feature points. Experimental results show that the visual SLAM algorithm based on ORB features is feasible, has good positioning accuracy, and can be widely used in autonomous navigation tasks of indoor robots.

A color image denoising algorithm based on

sparse representation and dictionary learning

YANG Pei1,GAO Lei-fu1,WANG Jiang1,ZI Ling-ling2

2018, 40(05): 842-848. doi:

Abstract ( 122 )

PDF (1127KB) ( 217 ) 　　

To solve the problems of fuzzy phenomenon and pseudo color in the denoising process of color images, a dictionary algorithm combining multiple information is proposed. Firstly, the definitions of the weighted gradients based on the channel model values in RGB color space are presented. On this basis, an over-complete structure of the dictionary is established, which uses brightness, weighted gradient and color information. Secondly, the iterative dictionary training process is continually updated and processed by using the sparsity of the noised image, and the optimal sparse coefficients and optimal learning dictionary are found, which can separate noise information from useful information of images, accurately reconstruct images which only requiring the color values computation and obtain the denoised color image. Experimental results show that, compared with the existing algorithms, the proposed algorithm achieves better visual effects and higher objective index values under different noise intensities, indicating that the algorithm has good denoising performance.

Generalized maximum noise fraction on image matrix

ZHANG Da-ming，ZHANG Xue-yong,LI Lu,LIU Hua-yong

2018, 40(05): 849-855. doi:

Abstract ( 102 )

PDF (1135KB) ( 187 ) 　　

Principal Component Analysis (PCA) is an important transform method in pattern recognition and is widely used in feature extraction and dimensionality reduction. However, since the two-dimensional images must be converted into one-dimensional vectors, there will be high dimensional data and the spatial information of pixels will be lost. Generalized Principal Component Analysis (GPCA) is the extension of PCA on two-dimensional image matrix, which does not change the location information of pixels, and its calculation cost is also significantly reduced. However, neither PCA or GPCA considers the noise that unavoidably exists in actual images. Maximum Noise Fraction (MNF) is a transform method that is designed to decrease noise. In contrast to the maximization of variance for PCA, MNF is based on the maximization of Signal-Noise Ratio (SNR). Similar to GPCA, this paper extends MNF on two-dimensional image matrix and proposes a Generalized Maximum Noise Fraction (GMNF) algorithm. GMNF is also based on the maximization of SNR. Meanwhile, GMNF does not lose the spatial information of pixels and has less computational complexity. Experimental results on face and hyperspectral images verify the effectiveness of the proposed algorithm.

An image encryption algorithm based on

spatiotemporal chaos and wavelet transform

WANG Lei，XUE Wei

2018, 40(05): 856-862. doi:

Abstract ( 183 )

PDF (825KB) ( 191 ) 　　

An image encryption algorithm based on spatiotemporal chaotic system is proposed. First, the plaintext image is scrambled by the Zigzag method. After the initial scrambled image is divided into blocks, the blocks are scrambled by the pseudo-random sequence generated by logistic chaotic system. Second, the integer wavelet transform is performed. Low-frequency wavelet coefficients are scrambled by three pseudo-random sequences produced by CML chaotic system. Meanwhile, the low-frequency wavelet coefficients are diffused. Then, the inverse integer wavelet transform is performed. Finally, the image is encrypted by using a pseudo-random sequence produced by CML chaotic system. The algorithm has good encryption performance. Encrypted images can effectively resist attacks such as difference and plaintext.

An edge detection algorithm based on

multi-scale adaptive diffusion equations

GUO Wei，DONG Hong-liang，SHI Shang

2018, 40(05): 863-871. doi:

Abstract ( 125 )

PDF (1294KB) ( 184 ) 　　

Aiming at the shortcomings of Canny's algorithm in the selection of high-density salt-pepper noise and double threshold, an improved method is proposed, in which multi-scale adaptive anisotropic diffusion equations are used to smooth images in order to effectively remove the high-density pulse signal and better retain edge profile information. In the selection of double threshold, the OTSU method is used to select an adaptive threshold according to the gray information of images, which can better meet the real-time requirements. To verify the algorithm's performance, experiments were carried out under different noise concentrations. Experimental results show that the improved edge detection algorithm can keep a complete set of edges, improve the accuracy of edge detection and get ideal edge profile information.

UAV gesture control system based on

computer vision and deep learning

MA Le-le,LI Zhao-yang,DONG Jia-rong,HOU Yong-hong

2018, 40(05): 872-879. doi:

Abstract ( 175 )

PDF (857KB) ( 409 ) 　　

The traditional Unmanned Aerial Vehicle (UAV) human-machine interaction requires specialized equipment and professional training, and convenient and innovative ways of interaction are often more popular. In this paper, with ordinary cameras, we study the UAV gesture control system based on computer vision and deep learning. The system first uses the fast tracking algorithm to extract the operator’s region in the video sequence, greatly reducing the pressure of subsequent video processing while removing the influence of complex background and camera drift. Secondly, according to the time information of the actions, the optical flow features are encoded in different colors and superimposed on a picture, and the video is converted into a color texture map that contains both temporal features and spatial features. Finally, colored texture images are well learned and classified by a deep Convolutional Neural Network (CNN) and UAV controlling commands are generated according to the classified results. The proposed system estimates actions within 1.6s every 0.4s and uses CNN to classify pictures so as to achieve real-time human-computer interaction. The system has a recognition accuracy of over 93% within 60 meters. In indoor and outdoor environments, the operator can conveniently control the UAV by imitating command actions.

A personalized ranking method fusing the

HUANG Jin，ZHOU Dong

2018, 40(05): 880-887. doi:

Abstract ( 106 )

PDF (718KB) ( 132 ) 　　

With the development of network technology, more and more resources are applied in information retrieval in the Internet. Numerous studies show that the social annotation can be used to improve search quality. In the existing personalized ranking methods, the similarity between users is usually calculated by their commonly used tag sets. However, in reality, there are some problems such as the sparseness of user annotation data and label synonyms, which makes the similarity calculation inaccurate. Based on the previous researches, this paper proposes a personalized ranking method for fusing the similar topic domains. Firstly, this method separates the webpage and tags with different thematic meanings, and finds the tag synonyms by constructing the network of similar tags. Secondly, this method finds the users of similar interests by combing the user’s tags and the preference of topic domains, and extends the user’s tag information to improve the personalized information retrieval effectively. Experimental results on real data show that this method can effectively alleviate the problems of data sparsity and tag synonyms, and can help to improve the user’s search experience.

A nearest feature space embedding method based on the

combination of nonlinear distance metric and included angle

DU Hong-yan,WANG Shi-tong,LI Tao

2018, 40(05): 888-897. doi:

Abstract ( 142 )

PDF (857KB) ( 171 ) 　　

Nearest Feature Space Embedding(NFSE) algorithm uses traditional Euclidean distance measure when choosing the nearest feature spaces in the training phase, which causes within-class scatters and between-class scatters change synchronously. The nearest neighborhoodmatching rule also uses Euclidean distance measure in the matching phase, but straight-line distances among samples in higher space are almost the same. They both can reduce the recognition rate. In order to solve this problem, this paper proposes a nearest feature space embedding method based on the combination of nonlinear distance metric and included angle (NL-IANFSE). In the training phase, NL-IANFSE brings nonlinear distance measure to make the change rate of within-class scatter much slower than that of between-class scatter so that distances of samples within same class are smaller and distances of samples belong to different classes are larger in the transformed space.In the matching phase, NL-IANFSE uses the nearest neighbor classifier that combines Euclidean distance and included anglebetween two samples，takes the relationship between similarity of samples and included angles of samples into account，and hence is more suitablefor sample classification in high-dimensional space.Experimental results show that the proposed method outperforms the other algorithms in terms of samples classification in high dimensional space.

A collaborative filtering algorithm based on fuzzy cognition

LIU Jing-ping,LI Ping

2018, 40(05): 898-905. doi:

Abstract ( 111 )

PDF (967KB) ( 291 ) 　　

Collaborative filtering is one of the most successful personalized recommendation techniques currently used in E-commerce recommendation systems. However, traditional collaborative filtering algorithms assume the ratings to be static in each period. To solve this problem, two kinds of fuzzy cognition are proposed: fuzzy increasing of ratings and fuzzy increasing of time weights. Firstly, item ratings are divided into time windows, the similarity between items is calculated using a chain-structure, and the nearest neighbors of the target item is selected. Secondly, time weights are assigned to ratings, a weight function is proposed, and the traditional prediction method is improved. At the same time, a hierarchical optimization strategy is proposed in the prediction phase to solve the time weights of ratings, thus completing the recommendation. Finally, experiments on the Netflix datasets show that, compared with the traditional collaborative filtering algorithms, our proposal improves the recommendation accuracy by 9.8%~14.1%.

A multiple subgroups fruit fly optimization algorithm based

on sequential quadratic programming local search

#br#

WANG Ying-bo1，WANG Yi-xing2

2018, 40(05): 906-915. doi:

Abstract ( 86 )

PDF (756KB) ( 133 ) 　　

The Fruit fly Optimization Algorithm (FOA) is easy to fall into premature convergence due to the decrease of population diversity in the process of optimization. In order to overcome the problem, a multiple subgroups fruit fly optimization algorithm based on sequential quadratic programming local search (MFOA-SQP) is proposed. The fruit flies are assigned to multiple subgroups and the mutual learning between subgroups adjusts the step by introducing the inertia weight and learning factors in particle swarm optimization algorithm. The subgroups are reclassified every a certain number of iterations, which can improve population diversity and avoid premature convergence. The best individual is searched by SQP to improve the local fruit fly depth search capability, improving the stability and accelerating the evolution of population in the late iterations. Experiments on 6 benchmark test functions are carried out and an application case that classifies banking customers by the optimized generalized regression neural network is adopted. The results show that the proposed algorithm has superior performance in terms of optimization accuracy and speed, and can effectively improve the classification accuracy of generalized regression neural networks.

Current Issue

Author center

Review center

Online journal