Stereo matching cost computation based on nonsubsampled contourlet transform

A new matching cost computation method based on nonsubsampled contourlet transform (NSCT) for stereo image matching is proposed in this paper. Firstly, stereo image is decomposed into high frequency sub-band images at different scales and along different directions by NSCT. Secondly, by utilizing coefficients in high frequency domain and grayscales in RGB color space, the computation model of weighted matching cost between two pixels is designed based on the gestalt laws. Lastly, two types of experiments are carried out with standard stereopairs in the Middlebury benchmark. One of the experiments is to confirm optimum values of NSCT scale and direction parameters, and the other is to compare proposed matching cost with nine known matching costs. Experimental results show that the optimum values of scale and direction parameters are respectively 2 and 3, and the matching accuracy of the proposed matching cost is twice higher than that of traditional NCC cost.     

以一种新的距离度量作为反馈的相关跟踪方法

基于相关的模板匹配方法在图像跟踪中得到了广泛的应用,但是这种方法的主要缺点是对图像噪声非常敏感,而且由这种方法得出的相关曲面比较平坦。为了有效抑制噪声和局部遮挡对图像的影响,提出用鲁棒统计中的一个值代替相关值作为距离度量。它不是计算两幅图像的对应像素差值,而是计算两幅图像中差别不大的对应像素对的个数。实验证明这样得到的曲面相对　　收稿日期:2003 08 31;　修订日期:2003 10 28作者简介:张桂林(1944 ),男,天津人,教授,博士生导师,主要研究方向为自动识别、人体生物统计特征识别、图像处理算法与系统性能评估等。　　　　　　　要尖锐得多。当上述的距离度量应用于跟踪过程中时,模板的合理更新对跟踪非常重要。基于上述的距离度量方法,提出了一种新的模板更新策略。利用两幅图像中近似像素在整修匹配模板像素中所占的比例大小决定加权系数。这种加权策略可以自适应地根据图像序列的变化选择更新相关模板,同时在一定程度上减小模板漂移的危险。     

Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

Fold‐2‐covering triangular embeddings

For a graph G and a positive integer m, G_(m) is the graph obtained from G by replacing every vertex by an independent set of size m and every edge by m² edges joining all possible new pairs of ends. If G triangulates a surface, then it is easy to see from Euler's formula that G_(m) can, in principle, triangulate a surface. For m prime and at least 7, it has previously been shown that in fact G_(m) does triangulate a surface, and in fact does so as a “covering with folds” of the original triangulation. For m = 5, this would be a consequence of Tutte's 5‐Flow Conjecture. In this work, we investigate the case m = 2 and describe simple classes of triangulations G for which G₍₂₎ does have a triangulation that covers G “with folds,” as well as providing a simple infinite class of triangulations G of the sphere for which G₍₂₎ does not triangulate any surface. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 79–92, 2003     

语音识别算法的确定与实现

在语音识别的实验中，对几种算法方案进行了比较、分析和择优淘劣，标准是在一定词汇量的条件下，权衡占用机器的内存空间、（正确）识别率和响应速度。力争使与话者有关的单词语音识别系统的设计达到优化，取得满意的结果。本文即是此项实验的总结。     

Indexing text using the Ziv–Lempel trie

Let a text of u characters over an alphabet of size σ be compressible to n phrases by the LZ78 algorithm. We show how to build a data structure based on the Ziv–Lempel trie, called the LZ-index, that takes 4nlog₂n(1+o(1)) bits of space (that is, 4 times the entropy of the text for ergodic sources) and reports the R occurrences of a pattern of length m in worst case time O(m³logσ+(m+R)logn). We present a practical implementation of the LZ-index, which is faster than current alternatives when we take into consideration the time to report the positions or text contexts of the occurrences found.     

Practical algorithms for transposition-invariant string-matching

We consider the problems of (1) longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (that is, transposed) to match the second, and (2) transposition-invariant text searching using indel distance. These problems have applications in music comparison and retrieval. We introduce two novel techniques to solve these problems efficiently. The first is based on the branch and bound method, the second on bit-parallelism. Our branch and bound algorithm computes the longest common transposition-invariant subsequence (LCTS) in time O((m²+loglogσ)logσ) in the best case and O((m²+logσ)σ) in the worst case, where m and σ, respectively, are the length of the strings and the size of the alphabet. On the other hand, we show that the same problem can be solved by using bit-parallelism and thus obtain a speedup of O(w/logm) over the classical algorithms, where the computer word has w bits. The advantage of this latter algorithm over the present bit-parallel ones is that it allows the use of more complex distances, including general integer weights. Since our branch and bound method is very flexible, it can be further improved by combining it with other efficient algorithms such as our novel bit-parallel algorithm. We experiment on several combination possibilities and discuss which are the best settings for each of those combinations. Our algorithms are easily extended to other musically relevant cases, such as δ-matching and polyphony (where there are several parallel texts to be considered). We also show how our bit-parallel algorithm is adapted to text searching and illustrate its effectiveness in complex cases where the only known competing method is the use of brute force.     

Ku波段10W功率PHEMT

报告了研制的 9.6mm栅宽双δ-掺杂功率 PHEMT,在 fo=1 1 .2 GHz、Vds=8.5 V时该器件输出功率3 7.2 8d Bm,功率增益 9.5 d B,功率附加效率 44.7% ,在 Vds=5～ 9V的范围内 ,该器件的功率附加效率均大于42 % ,两芯片合成 ,在 1 0 .5～ 1 1 .3 GHz范围内 ,输出功率大于 3 9.92 d Bm,最大功率达到 40 .3 7d Bm,功率增益大于 9.9d B,典型的功率附加效率 40 %。     

单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2 的一个赛程安排方案