Pattern matching is a very important algorithm used in many applications such as search engine and DNA analysis. They are aiming to find a pattern in a text. This paper proposes a Pattern Matching Algorithm Using Chan...Pattern matching is a very important algorithm used in many applications such as search engine and DNA analysis. They are aiming to find a pattern in a text. This paper proposes a Pattern Matching Algorithm Using Changing Consecutive Characters (PMCCC) to make the searching pro- cess of the algorithm faster. PMCCC enhances the shift process that determines how the pattern moves in case of the occurrence of the mismatch between the pattern and the text. It enhances the Berry Ravindran (BR) shift function by using m consecutive characters where m is the pattern length. The formal basis and the algorithms are presented. The experimental results show that PMCCC made enhancements in searching process by reducing the number of comparisons and the number of attempts. Comparing the results of PMCCC with other related algorithms has shown significant enhancements in average number of comparisons and average number of attempts.展开更多
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.展开更多
This paper presents an efficient pattern matching algorithm (FSW). FSW improves the searching process for a pattern in a text. It scans the text with the help of four sliding windows. The windows are equal to the leng...This paper presents an efficient pattern matching algorithm (FSW). FSW improves the searching process for a pattern in a text. It scans the text with the help of four sliding windows. The windows are equal to the length of the pattern, allowing multiple alignments in the searching process. The text is divided into two parts;each part is scanned from both sides simultaneously using two sliding windows. The four windows slide in parallel in both parts of the text. The comparisons done between the text and the pattern are done from both of the pattern sides in parallel. The conducted experiments show that FSW achieves the best overall results in the number of attempts and the number of character comparisons compared to the pattern matching algorithms: Two Sliding Windows (TSW), Enhanced Two Sliding Windows algorithm (ETSW) and Berry-Ravindran algorithm (BR). The best time case is calculated and found to be??while the average case time complexity is??.展开更多
文摘Pattern matching is a very important algorithm used in many applications such as search engine and DNA analysis. They are aiming to find a pattern in a text. This paper proposes a Pattern Matching Algorithm Using Changing Consecutive Characters (PMCCC) to make the searching pro- cess of the algorithm faster. PMCCC enhances the shift process that determines how the pattern moves in case of the occurrence of the mismatch between the pattern and the text. It enhances the Berry Ravindran (BR) shift function by using m consecutive characters where m is the pattern length. The formal basis and the algorithms are presented. The experimental results show that PMCCC made enhancements in searching process by reducing the number of comparisons and the number of attempts. Comparing the results of PMCCC with other related algorithms has shown significant enhancements in average number of comparisons and average number of attempts.
基金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 paper presents an efficient pattern matching algorithm (FSW). FSW improves the searching process for a pattern in a text. It scans the text with the help of four sliding windows. The windows are equal to the length of the pattern, allowing multiple alignments in the searching process. The text is divided into two parts;each part is scanned from both sides simultaneously using two sliding windows. The four windows slide in parallel in both parts of the text. The comparisons done between the text and the pattern are done from both of the pattern sides in parallel. The conducted experiments show that FSW achieves the best overall results in the number of attempts and the number of character comparisons compared to the pattern matching algorithms: Two Sliding Windows (TSW), Enhanced Two Sliding Windows algorithm (ETSW) and Berry-Ravindran algorithm (BR). The best time case is calculated and found to be??while the average case time complexity is??.
