16787369
Fast block matching algorithm based on the winner-update strategy
Block matching is a widely used method for stereo vision, visual tracking, and video compression. Many fast algorithms for block matching have been proposed in the past, but most of them do not guarantee that the match found is the globally optimal match in a search range. This paper presents a new fast algorithm based on the winner-update strategy which utilizes an ascending lower bound list of the matching error to determine the temporary winner. Two lower bound lists derived by using partial distance and by using Minkowski's inequality are described. The basic idea of the winner-update strategy is to avoid, at each search position, the costly computation of the matching error when there exists a lower bound larger than the global minimum matching error. The proposed algorithm can significantly speed up the computation of the block matching because: 1) computational cost of the lower bound we use is less than that of the matching error itself; 2) an element in the ascending lower bound list will be calculated only when its preceding element has already been smaller than the minimum matching error computed so far; 3) for many search positions, only the first several lower bounds in the list need to be calculated. Our experiments have shown that, when applying to motion vector estimation for several widely-used test videos, 92% to 98% of operations can be saved while still guaranteeing the global optimality. Moreover, the proposed algorithm can be easily modified either to meet the limited time requirement or to provide an ordered list of best candidate matches. Our source codes of the proposed algorithm are available at http://smart.iis.sinica.edu.tw/html/winup.html.
14744012
Winner-update algorithm for nearest neighbor search
This paper presents an algorithm, called the winner-update algorithm, for accelerating the nearest neighbor search. By constructing a hierarchical structure for each feature point in the l/sub p/ metric space, this algorithm can save a large amount of computation at the expense of moderate preprocessing and twice the memory storage. Given a query point, the cost for computing the distances from this point to all the sample points can be reduced by using a lower bound list of the distance established from Minkowski's inequality. Our experiments have shown that the proposed algorithm can save a large amount of computation, especially when the distance between the query point and its nearest neighbor is relatively small. With slight modification, the winner-update algorithm can also speed up the search for k nearest neighbors, neighbors within a specified distance threshold, and neighbors close to the nearest neighbor.
2968797
Ego-motion estimation using optical flow fields observed from multiple cameras
In this paper, we consider a multi-camera vision system mounted on a moving object in a static three-dimensional environment. By using the motion flow fields seen by all of the cameras, an algorithm which does not need to solve the point-correspondence problem among the cameras is proposed to estimate the 3D ego-motion parameters of the moving object. Our experiments have shown that using multiple optical flow fields obtained from different cameras can be very helpful for ego-motion estimation.
7506034
Fast Algorithm for Nearest Neighbor Search Based on a Lower Bound Tree
This paper presents a novel algorithm for fast nearest neighbor search. At the preprocessing stage, the proposed algorithm constructs a lower bound tree by agglomeratively clustering the sample points in the database. Calculation of the distance between the query and the sample points can be avoided ifthe lower bound of the distance is already larger than the minimum distance. The search process can thus be accelerated because the computational cost of the lower bound, which can be calculated by using the internal node of the lower bound tree, is less than that of the distance. To reduce the number of the lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. Moreover; the query and the sample points can be transformed for further efficiency improvement. Our experiments show that the proposed algorithm can greatly speed up the nearest neighbor search process. When applying to the real database used in Nayar’s object recognition system, the proposed algorithm is about one thousand times faster than the exhaustive search.
33065239
Triangle-free Hamiltonian Kneser graphs
The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2,...,n}. Two vertices are adjacent if the k-sets are disjoint. When n > 3k, the Kneser Graph K(n, k) has no triangle. In this paper, we prove that K(n,k) is Hamiltonian for n ≥ (3k + 1 + √5k2- 2k + 1)/2, and extend this to the bipartite Kneser graphs. Note that (3k + 1 + √5k2 - 2k + 1)/2 > 2.62k + 1.
1548803
I/O-efficient techniques for computing pagerank
Over the last few years, most major search engines have integrated link-based ranking techniques in order to provide more accurate search results. One widely known approach is the Pagerank technique, which forms the basis of the Google ranking scheme, and which assigns a global importance measure to each page based on the importance of other pages pointing to it. The main advantage of the Pagerank measure is that it is independent of the query posed by a user; this means that it can be precomputed and then used to optimize the layout of the inverted index structure accordingly. However, computing the Pagerank measure requires implementing an iterative process on a massive graph corresponding to billions of web pages and hyperlinks.In this paper, we study I/O-efficient techniques to perform this iterative computation. We derive two algorithms for Pagerank based on techniques proposed for out-of-core graph algorithms, and compare them to two existing algorithms proposed by Haveliwala. We also consider the implementation of a recently proposed topic-sensitive version of Pagerank. Our experimental results show that for very large data sets, significant improvements over previous results can be achieved on machines with moderate amounts of memory. On the other hand, at most minor improvements are possible on data sets that are only moderately larger than memory, which is the case in many practical scenarios.
206473788
Booth's law of word frequency
Booth’s (1967) law is widely used to model the incidence of low frequency words in English text. Fedorowicz (198 1, 1982a, 1982b) used equation (3) below to study automated bibliographic systems. Pao (1978) used equation (4) to derive a transition point in automatic text analysis. The present communication confirms this usage, corrects a deficiency in the original derivation, and makes the results more general. Booth’s results are based on Zipf’s (1949) well-known relationship between the probability of occurrence, p(r), and the corresponding rank, r, of a word where
14597615
Priority assignment optimization for minimization of current surge in high performance power efficient clock-gated microprocessor
We propose an integrated architectural/physical-planning approach named priority assignment optimization to minimize the current surge in high performance power efficient clock-gated microprocessors. The proposed approach balances the current demands across the floorplan by assigning optimized priorities to the functional units (FUs). Two complementary methods -- physical planning with soft modules and issue pattern management - to enhance our proposed approach are also discussed for various applications. Experimental results show that the proposed approach reduces the peak noise by 11.75% and consequently, the decoupling capacitance (Decap) requirement by 24.22% without any degradation in IPC (Instruction Per Cycle). We also show that our approach does not increase the clock period for the 0.18μm technology and beyond.
10107398
Yet Another Induction Algorithm
Inducing general functions from specific training examples is a central problem in the machine learning. Using sets of If-then rules is the most expressive and readable manner. To find If-then rules, many induction algorithms such as ID3, AQ, CN2 and their variants, were proposed. Sequential covering is the kernel technique of them. To avoid testing all possible selectors, Entropy gain is used to select the best attribute in ID3. Constraint of the size of star was introduced in AQ and beam search was adopted in CN2. These methods speed up their induction algorithms but many good selectors are filtered out. In this work, we introduce a new induction algorithm that is based on enumeration of all possible selectors. Contrary to the previous works, we use pruning power to reduce irrelative selectors. But we can guarantee that no good selectors are filtered out. Comparing with other techniques, the experiment results demonstrate that the rules produced by our induction algorithm have high consistency and simplicity.