1,720,983 research outputs found
Quadra-Embedding: Binary Code Embedding with Low Quantization Error
No full textThanks to their compact data representations and fast similarity computation, many binary code embedding techniques have been recently proposed for large-scale similarity search used in many computer vision applications including image retrieval. Most of prior techniques have centered around optimizing a set of projections for accurate embedding. In spite of active research efforts, existing solutions suffer from diminishing marginal efficiency as more code bits are used, and high quantization errors naturally coming from the binarization.
In order to reduce both quantization error and diminishing efficiency we propose a novel binary code embedding scheme that assigns two bits for each projection to define four quantization regions, and a novel binary code distance function tailored specifically to our encoding scheme. Furthermore, we formulate an optimization problem of finding four quantization regions, in order to maximize benefits of our encoding scheme. Our method is directly applicable to a wide variety of binary code embedding methods. Our scheme combined with four state-of-the-art embedding methods has been evaluated with four public image benchmarks. We have observed that our scheme achieves meaningful accuracy improvement (up to 100%) in most experimental configurations under k- and e-NN search
Distance Encoded Product Quantization for Approximate K-Nearest Neighbor Search in High-Dimensional Space
No full textApproximate K-nearest neighbor search is a fundamental problem in computer science. The problem is especially important for high-dimensional and large-scale data. Recently, many techniques encoding high-dimensional data to compact codes have been proposed. The product quantization and its variations that encode the cluster index in each subspace have been shown to provide impressive accuracy. In this paper, we explore a simple question: is it best to use all the bit-budget for encoding a cluster index? We have found that as data points are located farther away from the cluster centers, the error of estimated distance becomes larger. To address this issue, we propose a novel compact code representation that encodes both the cluster index and quantized distance between a point and its cluster center in each subspace by distributing the bit-budget. We also propose two distance estimators tailored to our representation. We further extend our method to encode global residual distances in the original space. We have evaluated our proposed methods on benchmarks consisting of GIST, VLAD, and CNN features. Our extensive experiments show that the proposed methods significantly and consistently improve the search accuracy over other tested techniques. This result is achieved mainly because our methods accurately estimate distances.
Data management for SSDs for large-scale interactive graphics applications
Full text linkThis research is partially funded by NSF grant CCF-0811809.
Sung-eui Yoon was supported in part by MKE/MCST/IITA
[2008-F-033-02], MKE digital mask control, KRF-2008-313-
D00922, KMCC, MSRA, BK, DAPA/ADD (UD080042AD),
MKE/KEIT [KI001810035261], and MEST/NRF/WCU (R31-
2010-000-30007-0)
HPCCD: Hybrid Parallel Continuous Collision Detection using CPUs and GPUs
Full text linkWe present a novel, hybrid parallel continuous collision detection (HPCCD) method that exploits the availability of multi-core CPU and GPU architectures. HPCCD is based on a bounding volume hierarchy (BVH) and selectively performs lazy reconstructions. Our method works with a wide variety of deforming models and supports selfcollision detection. HPCCD takes advantage of hybrid multi-core architectures – using the general-purpose CPUs to perform the BVH traversal and culling while GPUs are used to perform elementary tests that reduce to solving cubic equations. We propose a novel task decomposition method that leads to a lock-free parallel algorithm in the main loop of our BVH-based collision detection to create a highly scalable algorithm. By exploiting the availability of hybrid, multi-core CPU and GPU architectures, our proposed method achieves more than an order of magnitude improvement in performance using four CPU-cores and two GPUs, compared to using a single CPU-core. This improvement results in an interactive performance, up to 148 fps, for various deforming benchmarks consisting of tens or hundreds of thousand triangles.We would like to thank anonymous reviewers for their
constructive feedbacks. We also thank Min Tang, Dinesh
Manocha, Joon-Kyung Seong, Young J. Kim, Samuel Brice,
and members of SGLab. for their supports and code sharing.
The tested models are courtesy of the UNC dynamic model
benchmarks. This project was supported in part by MKE/MCST/
IITA [2008-F-033-02,2008-F-030-02], MCST/KEIT
[2006-S-045-1], MKE/IITA u-Learning, MKE digital mask
control, MCST/KOCCA-CTR&DP-2009, KRF-2008-313-
D00922, and MSRA E-heritage
Spherical Hashing
No full textMany binary code encoding schemes based on hashing have been actively studied recently, since they can provide efficient similarity search, especially nearest neighbor search, and compact data representations suitable for handling large scale image databases in many computer vision problems. Existing hashing techniques encode high dimensional data points by using hyperplane-based hashing functions. In this paper we propose a novel hypersphere- based hashing function, spherical hashing, to map more spatially coherent data points into a binary code compared to hyperplane-based hashing functions. Furthermore, we propose a new binary code distance function, spherical Hamming distance, that is tailored to our hypersphere-based binary coding scheme, and design an efficient iterative optimization process to achieve balanced partitioning of data points for each hash function and independence between hashing functions. Our extensive experiments show that our spherical hashing technique significantly outperforms six state-of-the-art hashing techniques based on hyperplanes across various image benchmarks of sizes ranging from one to 75 million of GIST descriptors. The performance gains are consistent and large, up to 100% improvements. The excellent results confirm the unique merits of the proposed idea in using hyperspheres to encode proximity regions in high-dimensional spaces. Finally, our method is intuitive and easy to implement
FASTCD
No full textSimulating complex phenomena such as fracture requires collision detection (CD) methods to avoid any inter-collisions among deforming models and self-collisions (i.e. intra-collisions) within each deforming model. CD is typically the main computational bottleneck of simulating such complex phenomena.We would like to thank anonymous reviewers and the members
of SGLab. for their helpful feedbacks. This work was
supported in part by NSFC (No. 60803054), Spanish Dept.
of Science and Innovation (projects TIN-2009-07942 and
PSE-300000-2009-5), BK, KAIST, KOSEF/MEST (2009-
0077290), MKE/IITA u-Learning, KRF-2008-313-D00922,
MKE/MCST/IITA[2008-F-033-02], MKE digital mask control,
MCST/KOCCA-CTR&DP-2009, MSRA, KMCC,
DAPA/ADD (UD080042AD), and the MKE/KEIT/MCST
project of semi-realtime renderer
Fracturing-aware stable collision detection
No full text학위논문(석사) - 한국과학기술원 : 전산학과, 2010.08, [ vii, 37 p. ]Simulating realistic fractures in deforming models is one of the main challenges in computer animation, sculpting in CAD, virtual surgery, etc. Simulating such complex phenomena requires collision detection methods to avoid any inter-collisions among deforming models and self-collisions within each deforming model. Moreover, fractures change the mesh connectivity , in addition to changing the geometry. Also, at a fracture or merge event, multiple parts of the same object can appear in a close proximity, causing a higher computation time for collision detection. As a result, collision detection including self-collision detection is typically the main computational bottleneck of simulating these complex phenomena.
In this thesis, we present a collision detection method for complex and large-scale fracturing models that have geometric and topological changes. We first propose a novel dual-cone culling method to improve the performance of collision detection, especially self-collision detection among fracturing models. Our dual-cone culling method has a small computational overhead and a conservative algorithm. Combined with bounding volume hierarchies (BVHs), our dual-cone culling method becomes approximate. However, we found that our method does not miss any collisions in the tested benchmarks. We also propose a novel, selective restructuring method that improves the overall performance of collision detection and reduces performance degradations at fracturing events. Our restructuring method is based on a culling efficiency metric that measures the expected number of overlap tests of a BVH. To further reduce the performance degradations at fracturing events, we also propose a novel, fast BVH construction method that builds multiple levels of the hierarchy in one iteration using a grid and hashing. We test our method with four different large-scale deforming benchmarks. Compared to the state-of-the-art methods, our method shows a more stable performance for coll...한국과학기술원 : 전산학과
- …
