Target tracking is very important in computer vision and related areas. It is usually difficult to accurately track fast motion target with appearance variations. Sometimes the tracking algorithms fail for heavy appea...Target tracking is very important in computer vision and related areas. It is usually difficult to accurately track fast motion target with appearance variations. Sometimes the tracking algorithms fail for heavy appearance variations. A multiple template method to track fast motion target with appearance changes is presented under the framework of appearance model with Kalman filter. Firstly, we construct a multiple template appearance model, which includes both the original template and templates affinely transformed from original one. Generally speaking, appearance variations of fast motion target can be covered by affine transformation. Therefore, the affine tr templates match the target of appearance variations better than conventional models. Secondly, we present an improved Kalman filter for approx- imate estimating the motion trail of the target and a modified similarity evaluation function for exact matching. The estimation approach can reduce time complexity of the algorithm and keep accuracy in the meantime. Thirdly, we propose an adaptive scheme for updating template set to alleviate the drift problem. The scheme considers the following differences： the weight differences in two successive frames; different types of affine transformation applied to templates. Finally, experiments demonstrate that the proposed algorithm is robust to appearance varia- tion of fast motion target and achieves real-time performance on middle/low-range computing platform.展开更多
The traditional multiple pattern matching algorithm, deterministic finite state automata, is implemented by tree structure. A new algorithm is proposed by substituting sequential binary tree for traditional tree. It i...The traditional multiple pattern matching algorithm, deterministic finite state automata, is implemented by tree structure. A new algorithm is proposed by substituting sequential binary tree for traditional tree. It is proved by experiment that the algorithm has three features, its construction process is quick, its cost of memory is small. At the same time, its searching process is as quick as the traditional algorithm. The algorithm is suitable for the application which requires preprocessing the patterns dynamically.展开更多
In this paper,we investigate the matched filter based spectrum sensing in a more reasonable cognitive radio(CR) scenario when the primary user(PU) has more than one transmit power levels,as regulated in most standards...In this paper,we investigate the matched filter based spectrum sensing in a more reasonable cognitive radio(CR) scenario when the primary user(PU) has more than one transmit power levels,as regulated in most standards,i.e.,IEEE 802.11 Series,GSM,LTE,LTE-A,etc.This new multiple primary transmit power(MPTP) scenario is specialized by two different targets:detecting the presence of PU and identifying the power level.Compared to the traditional binary sensing where only the presence of PU is checked,SU may attain more information about the primary network(making CR more "intelligent") and design the subsequent optimization strategy.The key technology is the multiple hypothesis testing as opposed to the traditional binary hypothesis testing.We discuss two situations under whether the channel phase is known or not,and we derive the closed form solutions for decision regions and several performance metrics,from which some interesting phenomenons are observed and the related discussions are presented.Numerical examples are provided to corroborate the proposed studies.展开更多
A color based system using multiple templates was developed and implem ented for detecting human faces in color images. The algorithm consists of three image processing steps. The first step is human skin color stati...A color based system using multiple templates was developed and implem ented for detecting human faces in color images. The algorithm consists of three image processing steps. The first step is human skin color statistics. Then it separates skin regions from non-skin regions. After that, it locates the fronta l human face(s) within the skin regions. In the first step, 250 skin samples from persons of different ethnicities are used to determine the color distribution o f human skin in chromatic color space in order to get a chroma chart showing lik elihoods of skin colors. This chroma chart is used to generate, from the origina l color image, a gray scale image whose gray value at a pixel shows its likelih ood of representing the skin. The algorithm uses an adaptive thresholding proces s to achieve the optimal threshold value for dividing the gray scale image into separate skin regions from non skin regions. Finally, multiple face templates ma tching is used to determine if a given skin region represents a frontal human fa ce or not. Test of the system with more than 400 color images showed that the re sulting detection rate was 83%, which is better than most color-based face dete c tion systems. The average speed for face detection is 0.8 second/image (400×300 pixels) on a Pentium 3 (800MHz) PC.展开更多
Pattern matching is a fundamental approach to detect malicious behaviors and information over Internet, which has been gradually used in high-speed network traffic analysis. However, there is a performance bottleneck ...Pattern matching is a fundamental approach to detect malicious behaviors and information over Internet, which has been gradually used in high-speed network traffic analysis. However, there is a performance bottleneck for multi-pattern matching on online compressed network traffic(CNT), this is because malicious and intrusion codes are often embedded into compressed network traffic. In this paper, we propose an online fast and multi-pattern matching algorithm on compressed network traffic(FMMCN). FMMCN employs two types of jumping, i.e. jumping during sliding window and a string jump scanning strategy to skip unnecessary compressed bytes. Moreover, FMMCN has the ability to efficiently process multiple large volume of networks such as HTTP traffic, vehicles traffic, and other Internet-based services. The experimental results show that FMMCN can ignore more than 89.5% of bytes, and its maximum speed reaches 176.470MB/s in a midrange switches device, which is faster than the current fastest algorithm ACCH by almost 73.15 MB/s.展开更多
Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design effic...Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.展开更多
Objectives:Genomic signatures like k-mers have become one of the most prominent approaches to describe genomic data.As a result,myriad real-world applications,such as the construction of de Bruijn graphs in genome ass...Objectives:Genomic signatures like k-mers have become one of the most prominent approaches to describe genomic data.As a result,myriad real-world applications,such as the construction of de Bruijn graphs in genome assembly,have been benefited by recognizing genomic signatures.In other words,an efficient approachof genomic signatureprofiling is an essential need for tackling high-throughput sequencing reads.However,most of the existing approaches only recognize fixed-size k-merswhile many research studies have shown the importance of considering variable-length k-mers.Methods:In this paper,we present a novel genomic signature profiling approach,TahcoRoll,by extending the Aho–Corasick algorithm(AC)for the task of profiling variable-length k-mers.We first group nucleotides into two clusters and represent each cluster with a bit.The rolling hash technique is further utilized to encode signatures and read patterns for efficient matching.Results:In extensive experiments,TahcoRoll significantly outperforms the most state-of-the-art k-mer counters and has the capability of processing reads across different sequencing platforms on a budget desktop computer.Conclusions:The single-thread version of TahcoRoll is as efficient as the eight-thread version of the state-of-the-art,JellyFish,while the eight-thread TahcoRoll outperforms the eight-thread JellyFish by at least four times.展开更多
基金Supported by the National Science Foundation of China(61472289)Hubei Province Science Foundation(2015CFB254)
文摘Target tracking is very important in computer vision and related areas. It is usually difficult to accurately track fast motion target with appearance variations. Sometimes the tracking algorithms fail for heavy appearance variations. A multiple template method to track fast motion target with appearance changes is presented under the framework of appearance model with Kalman filter. Firstly, we construct a multiple template appearance model, which includes both the original template and templates affinely transformed from original one. Generally speaking, appearance variations of fast motion target can be covered by affine transformation. Therefore, the affine tr templates match the target of appearance variations better than conventional models. Secondly, we present an improved Kalman filter for approx- imate estimating the motion trail of the target and a modified similarity evaluation function for exact matching. The estimation approach can reduce time complexity of the algorithm and keep accuracy in the meantime. Thirdly, we propose an adaptive scheme for updating template set to alleviate the drift problem. The scheme considers the following differences： the weight differences in two successive frames; different types of affine transformation applied to templates. Finally, experiments demonstrate that the proposed algorithm is robust to appearance varia- tion of fast motion target and achieves real-time performance on middle/low-range computing platform.
基金This project was supported by the National "863" High Technology Research and Development Program of China(2003AA142160) and the National Natural Science Foundation of China (60402019)
文摘The traditional multiple pattern matching algorithm, deterministic finite state automata, is implemented by tree structure. A new algorithm is proposed by substituting sequential binary tree for traditional tree. It is proved by experiment that the algorithm has three features, its construction process is quick, its cost of memory is small. At the same time, its searching process is as quick as the traditional algorithm. The algorithm is suitable for the application which requires preprocessing the patterns dynamically.
基金supported in part by the National Basic Research Program of China(973 Program)under Grant 2013CB336600the Beijing Natural Science Foundation under Grant 4131003+1 种基金the National Natural Science Foundation of China under Grant{61201187,61422109}the Importation and Development of High-Caliber Talents Project of Beijing Municipal Institutions under Grant YETP0110
文摘In this paper,we investigate the matched filter based spectrum sensing in a more reasonable cognitive radio(CR) scenario when the primary user(PU) has more than one transmit power levels,as regulated in most standards,i.e.,IEEE 802.11 Series,GSM,LTE,LTE-A,etc.This new multiple primary transmit power(MPTP) scenario is specialized by two different targets:detecting the presence of PU and identifying the power level.Compared to the traditional binary sensing where only the presence of PU is checked,SU may attain more information about the primary network(making CR more "intelligent") and design the subsequent optimization strategy.The key technology is the multiple hypothesis testing as opposed to the traditional binary hypothesis testing.We discuss two situations under whether the channel phase is known or not,and we derive the closed form solutions for decision regions and several performance metrics,from which some interesting phenomenons are observed and the related discussions are presented.Numerical examples are provided to corroborate the proposed studies.
文摘A color based system using multiple templates was developed and implem ented for detecting human faces in color images. The algorithm consists of three image processing steps. The first step is human skin color statistics. Then it separates skin regions from non-skin regions. After that, it locates the fronta l human face(s) within the skin regions. In the first step, 250 skin samples from persons of different ethnicities are used to determine the color distribution o f human skin in chromatic color space in order to get a chroma chart showing lik elihoods of skin colors. This chroma chart is used to generate, from the origina l color image, a gray scale image whose gray value at a pixel shows its likelih ood of representing the skin. The algorithm uses an adaptive thresholding proces s to achieve the optimal threshold value for dividing the gray scale image into separate skin regions from non skin regions. Finally, multiple face templates ma tching is used to determine if a given skin region represents a frontal human fa ce or not. Test of the system with more than 400 color images showed that the re sulting detection rate was 83%, which is better than most color-based face dete c tion systems. The average speed for face detection is 0.8 second/image (400×300 pixels) on a Pentium 3 (800MHz) PC.
基金supported by China MOST project (No.2012BAH46B04)
文摘Pattern matching is a fundamental approach to detect malicious behaviors and information over Internet, which has been gradually used in high-speed network traffic analysis. However, there is a performance bottleneck for multi-pattern matching on online compressed network traffic(CNT), this is because malicious and intrusion codes are often embedded into compressed network traffic. In this paper, we propose an online fast and multi-pattern matching algorithm on compressed network traffic(FMMCN). FMMCN employs two types of jumping, i.e. jumping during sliding window and a string jump scanning strategy to skip unnecessary compressed bytes. Moreover, FMMCN has the ability to efficiently process multiple large volume of networks such as HTTP traffic, vehicles traffic, and other Internet-based services. The experimental results show that FMMCN can ignore more than 89.5% of bytes, and its maximum speed reaches 176.470MB/s in a midrange switches device, which is faster than the current fastest algorithm ACCH by almost 73.15 MB/s.
基金supported by the National Natural Science Foundation of China under Grant Nos.60803030,60925009,60921002the National Basic Research 973 Program of China under Grant No.2011CB302502
文摘Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.
文摘Objectives:Genomic signatures like k-mers have become one of the most prominent approaches to describe genomic data.As a result,myriad real-world applications,such as the construction of de Bruijn graphs in genome assembly,have been benefited by recognizing genomic signatures.In other words,an efficient approachof genomic signatureprofiling is an essential need for tackling high-throughput sequencing reads.However,most of the existing approaches only recognize fixed-size k-merswhile many research studies have shown the importance of considering variable-length k-mers.Methods:In this paper,we present a novel genomic signature profiling approach,TahcoRoll,by extending the Aho–Corasick algorithm(AC)for the task of profiling variable-length k-mers.We first group nucleotides into two clusters and represent each cluster with a bit.The rolling hash technique is further utilized to encode signatures and read patterns for efficient matching.Results:In extensive experiments,TahcoRoll significantly outperforms the most state-of-the-art k-mer counters and has the capability of processing reads across different sequencing platforms on a budget desktop computer.Conclusions:The single-thread version of TahcoRoll is as efficient as the eight-thread version of the state-of-the-art,JellyFish,while the eight-thread TahcoRoll outperforms the eight-thread JellyFish by at least four times.
