Loading...
  • 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Current Issue

    • 论文
      Parallel generation algorithm for
      Delaunay TIN with massive data 
      ZHANG Zhen
      2013, 35(4): 1-7. doi:
      Abstract ( 211 )   PDF (848KB) ( 264 )     

      The paper studied a parallel generation algorithm for Delaunay TIN with massive data. To meet the efficient demands of processing massive data, the paper proposed a merge method of generating the Delaunay TIN. According to the spatial distribution of data points, the method firstly sorts the data by their x coordinates, allocates the sorted data to the corresponding threads, generates a series of initial subTINs, and merges two adjacent subTINs recursively. All the subTINs are finally merged to a TIN. The relativity between subTINs is weak in the process of merging, so that it is easy to be processed in parallel and pipelined. The algorithm can run in the serial mode、the multithread mode、the multicore mode, and the distributed parallel computing environment. The experiment proves that the algorithm is efficient and the worst serial time complexity is O (nlogn) and often less than O(n2).

      SSTD:Scalable parallel debug tool based on stack trace analysis    
      JIANG Jie1,FANG Li2,LU Kai1,LIU Jie1,WU Linping3
      2013, 35(4): 8-13. doi:
      Abstract ( 134 )   PDF (480KB) ( 202 )     

      In this paper, a scalable parallel debug tool (SSTD) was proposed. By capturing and dumping process stack traces when the target parallel program exits abnormally, the SSTD can help users fast locate program faults and improve parallel debug efficiency. The system architecture and some key technologies of the SSTD, including scalable communication infrastructure and process equivalence classification, were discussed in detail.

      Numerical study of two types of secondary nozzle in chemical laser    
      XIAO Nan,HUA Weihong,LIU Wenguang
      2013, 35(4): 14-17. doi:
      Abstract ( 124 )   PDF (993KB) ( 195 )     

      The second nozzle of the gain generator in the chemical laser provides optical cavity with chemical fuel and dilute gas, and refrigerates the main nozzle flow. Design optimization of several distribution flow pipeline levels in nozzle blade is vital for uniformization of reaction flow and cooling the nozzle blade by the secondary nozzle flow. Characteristics of the secondary nozzle were studied based on threedimensional fluid dynamics method. Nozzle with three distribution flow pipeline level transport structure and 2SLOT were compared. Flow field uniformity of every distribution flow pipeline levels were calculated under the 1st level inlet pressure of 3atm 5 atm and 8atm. The uniformity of the nozzle with three levels distribution flow pipeline structure is better than 2SLOT nozzle at the same parameters such as area ratio of input and output surfaces and throat. The parameters of existing design of three levels distribution flow pipeline nozzle structure requires further optimization. It is useful to obtain the uniformization of reaction flow with raising the inlet pressure.

      Parallel slope and aspect algorithm in terrain analysis     
      JIANG Ling,LIU Xuejun,TANG Guoan,SONG Xiaodong
      2013, 35(4): 18-23. doi:
      Abstract ( 134 )   PDF (1234KB) ( 281 )     

      Digital Terrain Analysis (DTA) is a digital information processing technology based on Digital Elevation Model (DEM) for the terrain attribute calculation and features extraction. Slope and aspect are the basic terrain parameters of DTA and widely used in different fields. However, it is always more difficult to get slope and aspect from DEM and normally needs more time to calculate slope and aspect due to large study area and huge data. Based on the analysis of serial algorithm features of slope and aspect in terrain analysis, the strategies of the data division, the data fusion and I/O of DTA algorithms are analyzed, and the parallel method was constructed from the aspect of data parallelism in the paper. The research indicates that the parallel method is efficient in performing the parallelization of sequential algorithms of slope and aspect, and the parallel method increases the execution efficiency of algorithms and achieves a good performance. The proposed parallel method can also be as a reference for the parallelization of the algorithms with the similar matrix type data.

      Survey and design of chiperror
      correcting algorithm in memory system  
      LI Yongjin,MAO Jianbiao,HUANG Jinfeng
      2013, 35(4): 24-28. doi:
      Abstract ( 145 )   PDF (568KB) ( 331 )     

      Memory is an important part of computer systems, and it is selfevident that the accuracy of information access has meaningful effect upon the entire system. As computer applications are widely used, memory error detection and correction is an effective means to improve the reliability of storage system. The storage system can recover correct data through ECC (Error Correcting Code) when errors occur in memory. This paper introduced some ECC algorithms used in the current computer storage systems, and analyzed the limitations of these algorithms. To cover these shortages, we proposed a chiperror correcting code based on the Bossen’s 2redundant badjacent error coding, gave the process of coding and error correction coding of this algorithm, and then used the language of verilog HDL to do the logic design. The simulation results show that the algorithm can effectively correct all singlebyte errors, and can detect most of the multiplebyte errors.

      BPEL based asynchronous interaction
      and composition of RESTful Web service      
      TIE Wei,HUANG Zhiqiu,WANG Jin
      2013, 35(4): 29-36. doi:
      Abstract ( 145 )   PDF (933KB) ( 234 )     

      RESTful Web service has become a primary method to publish services in cloud computing, due to its lightweight and specific semantics. However, because RESTful Web service only support synchronous interaction, it is difficult of using synchronous composition to meet the requirement of the complex business process. Therefore, the paper proposed a callback based asynchronous interaction approach under REST style. The approach enables the composition of both synchronous and asynchronous RESTful Web services by extending the BPEL meta model. The architecture of the execution engine for the extended BPEL was designed and implemented as well.

      Design and implementation of rasterization
      parallel algorithm based on boundary algebra filling  
      ZHOU Chen,CHEN Zhenjie,ZHANG Shuai
      2013, 35(4): 37-41. doi:
      Abstract ( 186 )   PDF (938KB) ( 307 )     

      Rasterization is often required in many fields, such as geoscience analysis of remote sensing and analysis of spatial decision. Faced with the reality demand of rapid conversion of mass data, the existing serial rasterization algorithms based on the traditional single machine and single process are difficult to meet the requirements. In this paper, on basis of the analysis of the existing rasterization algorithms, the boundary algebra filling method is studied since it is simple, reliable and fast operational. The rasterization parallel algorithm based on boundary algebra filling was designed and implemented by MPI, GDAL and C++. In order to evaluate the parallel efficiency of the algorithm, different scale data were applied in the experiment. Experimental results show that this algorithm is right and improves the calculating efficiency. What’s more, when the data is larger, the advantage of the algorithm is greater.

      Parallel algorithm of the vulnerability of the combination
      of multiple submunitions attacking area targets 
      WANG Duolei,LONG Han,CHEN Xuan
      2013, 35(4): 42-46. doi:
      Abstract ( 118 )   PDF (608KB) ( 188 )     

      This paper studies the vulnerability problem of area target based on the background of the combination of multiple submunitions.In this paper, the importance issues of damage probability and damage failure time in the vulnerability of area target is introduced;the performance evaluation of vulnerability of area target through related damages is analyzed;the combination of submunitions about delay capacity and nondelay capacity are considered in damage sources;the demand of computation resources is analyzed for the MonteCarlo simulation of damage probability;a suitable highperformance platform is constructed with this parallel algorithm;and finally,a numerical simulation example is given to test the algorithm’s efficiency.The simulation results show that those problems of computation resources,speed and efficiency can  all be solved effectively by this parallel algorithm.

      Energy conservation research in wireless sensor
      networks based on maximum cover sets 
      YAO Lan1,ZENG Feng2
      2013, 35(4): 47-52. doi:
      Abstract ( 140 )   PDF (1711KB) ( 187 )     

      Energy conservation in wireless sensor networks is an important research subject. In this paper, we studied energy conservation in wireless sensor networks based on the maximum cover sets problem. First, the distributed tokenbased mechanism was proposed for the collection of the path between a sink and a sensor. Through the mechanism, sink nodes can collect at most K paths for each sensor, and the parameter K can be adjusted to make a balance between algorithm performance and communication overhead. Then, based on the selected paths, an iterative optimization mechanism was presented to find a cover set of the network while using the number of sensors as small as possible. Finally, simulation work was done to evaluate the proposed energysaving strategies and algorithms. Simulation results show that the proposed algorithm performs better than the other two algorithms. Moreover, experimental analysis shows that algorithm parameters have the impact on the experimental results.

      Research of heuristic algorithm based on
      MDSMCC problem in wireless sensor networks   
      XIA Yun,CHEN Zhigang,ZENG Feng
      2013, 35(4): 53-58. doi:
      Abstract ( 128 )   PDF (495KB) ( 175 )     

      Under the circumstance of maintaining coverage and connectivity of wireless sensor networks, to extend the lifetime of networks through energy conservation technique is a critical issue. A heuristic algorithm based on the MDSMCC problem takes advantages of power aware organization to acquire long lifetime, and it uses greedy strategy to select maximum disjoint sets, the strategy selects the nodes which has the shortest path. Combining DFS and BFS, the paper proposed a new method called DBFS. The DBFS method takes the coverage as the first consideration to select disjoint sets. The simulation results prove that the performance of DBFS is better than greedy strategy in terms of the number of disjoint sets and the stability in different networks respectively.

      Design and implementation of a software life
      cycle oriented authorization and protection system   
      OUYANG Xue,ZHOU Huan,DENG Jinzhou,REN Jiangchun
      2013, 35(4): 59-64. doi:
      Abstract ( 156 )   PDF (1211KB) ( 330 )     

      Nowadays, the software development model has transformed from independent development to collaborative development, while the selling pattern of software industry has turned into module based way from traditional whole software selling. The existing software protection techniques such as softdog and registration code can no longer meet these new requirements, and the problem of infringement has become more and more severe. Based on this, a software life cycle oriented authorization and protection system was designed. This system synthetically applied the UKey technology, authentication technology, digital signature technology, certificate chain technology and hardwarebased encryption technology. And especially, an authorization model which is customizable to software developers and the license file which takes modules as the basic authorization unit were adopted. The prototype system shows our design is functionally well and reasonable, the security requirements of software in all stages, from developing stage to sale and using, are provided.

      Research on GNSS’s securityprotection  
      ZHANG Wangxun,HOU Hongtao,WANG Weiping
      2013, 35(4): 65-69. doi:
      Abstract ( 108 )   PDF (663KB) ( 196 )     

      SecurityProtection of global navigation satellite systems plays an important role in navigation systems and materiel. Firstly, its definition, description and study contents were introduced. Secondly, according to the view of system engineering, the process of securityprotection was indicated, followed by a mathematical model which consists of interference strategy, attack level, the level of protection and combat scenario. Finally, an example was used to analyze the GNSS receivers’ securityprotection. The results first indicate that: 1) the protection level relative to the level of enemy attacks is a key factor affecting the operational utility; 2) different combat scenarios have different needs for the level of protection, and 3) the effect of enemy interference policy on our operational utility depends on the corresponding level of protection.

      Topological map building algorithm
      based on middle line of free space       
      SU Liying,SONG Hualei
      2013, 35(4): 70-74. doi:
      Abstract ( 128 )   PDF (507KB) ( 282 )     

      Firstly, the paper constructed a metric map, which is represented by point sets, by using laser sensors to scan data. Secondly, a new algorithm named middle line of free space (MLFS) is proposed so as to extract the topological structure of the free space of the environment where the robots are. The posture of the robot is added into the node of the topology and the topological map is built. Experiments are carried out in both Z type and T type environments respectively, and the results proves that this algorithm is effective, intime and compact to represent the environment.                             

      Study on image processing technique of
      rock mass discontinuities’ parameters    
      LUO Jia1,LIU Dagang2
      2013, 35(4): 75-80. doi:
      Abstract ( 125 )   PDF (751KB) ( 228 )     

      The rock mass discontinuities’ parameters measurement based on image processing technique is a new method which differs from the traditional measurements in many ways. It is usually composed of image determination, image processing and image analyses. This method takes common digital camera as a main tool to collect information of rock mass discontinuities and depends on computer to process image information. In this way the tunnel building face information of rock mass discontinuities’ parameters can be gained at fast. This paper made an entire and systemic study on the new method and developed a software to realize automation and intelligentize of processing. The real experimental evaluation of the typical rock mass image shows this method has better precision and higher efficiency. Therefore, we can conclude that the paper studied a new way of rock mass discontinuities’ parameters measurement.           

      Fast intraprediction mode selection algorithm
      for H.264/AVC based on texture  
      ZHANG Xiaohong,ZHANG Yuan
      2013, 35(4): 81-86. doi:
      Abstract ( 120 )   PDF (516KB) ( 169 )     

      Intraframe encoding in H.264/AVC video standard usually adopts Rate Distortion Optimization (RDO) technique. By computing all possible coding modes, the one which has the lowest cost of rate distortion is selected as the best mode. The RDO technique improves the reliability, accuracy and error resilience of encoding while increasing the complexity and search time of the encoding. The residual value between the current and reconstructed 4×4 block is calculated in the circumstances of analyzing the standard intraprediction. If the value is smaller than a certain threshold the macro block coding can be ended in advance. Conversely, a fast 4×4 intraprediction mode selection algorithm was proposed by utilizing the correlation between the texture direction of block and the choice of predict modes. Based on the improved Canny operator and square gradient method, this algorithm extracts the texture of the current block and analyzes the corresponding relations between texture direction and the predict modes in detail. Experiments were carried out on the reference model JM13.2 of H.264/AVC. The results show that, compared with the standard algorithm, the encoding time is substantially declined in the case of keeping the bit rate and the PSNR are nearly unchanged.

      Collision detection optimization algorithm #br# based on mixed bounding volumes    
      ZHENG Yanbin, GUO Lingyun, LIU Jingjing
      2013, 35(4): 87-92. doi:
      Abstract ( 117 )   PDF (536KB) ( 153 )     

        To improve the realtime ability of bounding volumes collision detection, a collision detection optimization algorithm based on mixed bounding volumes was proposed in the paper. In the preprocessing stage, the algorithm constructs dual bounding volumes binary trees of the objects. Bounding spheres are established at the outer layer nodes, different inner bounding volumes, which are selected based on the geometrical features of the objects and the characteristics of various bounding volume, are established at the inner layer nodes. In the process of the collision detection, the intersection test firstly uses the outer layer spheres to get rid of nonintersecting objects, and uses the inner layer bounding volumes to further judge the contact status among objects. Comparing with classical algorithm, experiment results show that the proposed algorithm is efficient in improving the realtime and accuracy of collision detection.

      论文
      Color image segmentation by combining
      improved watershed and region growing         
      CHEN Lifang,LIU Yiming,LIU Yuan
      2013, 35(4): 93-98. doi:
      Abstract ( 121 )   PDF (711KB) ( 233 )     

      The result of color image segmentation directly affects understanding the image. The watershed segmentation has over-segmentation phenomenon, and a pixel as the seed region grows slowly. Aiming at these two problems, the paper proposed a new color image segmentation method that is based on LUV color space model and combines watershed and region growing. The experiments show that the method features high effect and fast speed.

      Adaptive threshold based slow motion
      replay detection method for tennis video          
      ZHANG Xiaoli,ZHI Min
      2013, 35(4): 99-103. doi:
      Abstract ( 115 )   PDF (512KB) ( 166 )     

      Slow motion is one of the most important semantic contents in sports video. This paper studied the logo transition based slow motion replay detection of tennis video. Firstly, the candidate logo shots from the video streaming are detected. Secondly, the logo template is generated. Thirdly, the similarity matching between video frames and logo template in the candidate logo shots is done, and, according to the matching results, the size of the adaptive threshold is determined and the boundaries of slow motion is located roughly. Finally, the brightness changes during the logo transition process are used to accurately locate the boundaries of slowmotion. Experiments results show that,unlike previous approaches, this method has great improvement in both precision rate and positioning accuracy of the boundaries,and can be used for other sports videos which also have logo transition.

      Homotopybased sparse coding for robust feature learning    
      HUI Yinhua,LI Fanzhang
      2013, 35(4): 104-110. doi:
      Abstract ( 121 )   PDF (695KB) ( 182 )     

      In the face recognition problem, in order to overcome the difficulties caused by the changes in posture and facial expressions, homotopic image pseudoinvariants for openset recognition and image retrieval is proposed. However, the illumination change is also caused by the continuous rotation of the face relative to the image acquisition equipment. In this paper we proposed a more general robust feature learning method based on homotopy equivalence with sparse coding. We tested it on the Yale B datasets and got a good result.

      Approximation algorithm for limited facility location problem         
      LIU Yutang,FANG Qizhi
      2013, 35(4): 111-114. doi:
      Abstract ( 109 )   PDF (336KB) ( 424 )     

      The paper presented an approximation algorithm for the Limited Facility Location problem (LFL), which is a new variant of the classical Uncapacitated Facility Location problem(UFL). The algorithm is based on randomized LP rounding, and its approximation ratio was analyzed.