Browsing by Author "Wu, KS"

Now showing 1 - 5 of 5

An efficient nearest neighbor searching algorithm with application to LBG codebook gene ration
(1996-11-01)
Wu, KS
;
Lin, JC
;
資訊工程學系
;
Department of Computer Science
The nearest neighbor (NN) searching problem has wide applications. In vector quantization (VQ), both the codebook generation phase and encoding phase (using the codebook just generated) often need to use the NN search. Improper design of the searching algorithm will make the complexity quite big as vector dimensionality k or codebook size N increases. In this paper, a fast NN searching method is proposed, which can then accelerate the LEG codebook generation process for VQ design. The method successfully modifies and improves the LAESA method. Unlike LAESA, the proposed k/2 ''fixed'' points (allocated far from the data) and the origin are used as the k/2+1 reference points to reduce the searching area. The overhead in memory is only linearly proportional to N and k. The time complexity, including the overhead, is of order O(kN). According to our experiments, the proposed algorithm can reduce the time burden while the distortion remains identical to that of the full search.
An efficient nearest neighbor searching algorithm with application to LBG codebook gene ration
(1996-11-01)
Wu, KS
;
Lin, JC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
The nearest neighbor (NN) searching problem has wide applications. In vector quantization (VQ), both the codebook generation phase and encoding phase (using the codebook just generated) often need to use the NN search. Improper design of the searching algorithm will make the complexity quite big as vector dimensionality k or codebook size N increases. In this paper, a fast NN searching method is proposed, which can then accelerate the LEG codebook generation process for VQ design. The method successfully modifies and improves the LAESA method. Unlike LAESA, the proposed k/2 ''fixed'' points (allocated far from the data) and the origin are used as the k/2+1 reference points to reduce the searching area. The overhead in memory is only linearly proportional to N and k. The time complexity, including the overhead, is of order O(kN). According to our experiments, the proposed algorithm can reduce the time burden while the distortion remains identical to that of the full search.
Critical point energy as a function of electric field determined by electroreflectance of surface-intrinsic-n(+) type doped GaAs
(2004-11-01)
Chen, YS
;
Wu, KS
;
Wang, DP
;
Huang, KF
;
Huang, TC
Electroreflectance of surface-intrinsic-n(+) type doped GaAs has been measured over a various biased voltage. The spectra have exhibited many Franz-Keldysh oscillations (FKOs) above band gap energy E-g. The electric field F and critical point energy E-c can be determined from the slope and intercept of FKOs fitting. Hence, we can obtain E-c as a function of F. In most of previous works, E-c is taken as E-g. However, it was found that E-c increases with F in this work. In order to explain this, the gain of energy of electron and hole in F was discussed. (C) 2004 American Institute of Physics.
Fast full search in motion estimation by hierarchical use of Minkowski's inequality (humi)
(1998-07-01)
Lu, JY
;
Wu, KS
;
Lin, JC
;
資訊工程學系
;
Department of Computer Science
In this paper, we extend the idea of successive elimination algorithm (SEA) to obtain a fast full search (FS) algorithm accelerating the block matching procedure of motion estimation. Based on the monotonic relation between the accumulated absolution distortions (AAD) obtained for distinct layers of a pyramid structure; the proposed method successfully rejects many impossible candidates considered in the FS. The derivation of the monotonicity relation repeatedly uses in a four-dimensional vector space the l(1)-version of Minkowski's inequality, an inequality which is quite well-known in the field of mathematics. Simulation results show that the processing speed is faster than that of several well-known fast full search methods, including the SEA that uses just once the Minkowski's inequality (in a vector space of 256 dimension when the block size is 16 x 16). The processing speed of the proposed method is also competitive with that of the three-step search (TSS), which is often used for block matching in interframe video coding, although the visual quality performance of TSS is usually a little poorer than that of the FS. (C) 1998 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
Fast VQ encoding by an efficient kick-out condition
(2000-02-01)
Wu, KS
;
Lin, JC
;
資訊工程學系
;
Department of Computer Science
A new fast approach to the nearest codeword search using a single kick-out condition is proposed. The nearest codeword found by the proposed approach is identical to the one Found by the full search, although the processing time is much shorter. The principle is to bypass those codewords which satisfy the proposed kick-out condition without the actual (and time-consuming) computation of the distortions from the bypassed codewords to the query vector. Due to the efficiency and simplicity of the proposed condition, a considerable saving of the central processing unit time needed to encode a data set (using a given codebook) can be achieved. Moreover, the memory requirement is low. Comparisons with some recent works are included to show these two benefits.