Visual Place Recognition (VPR) has advanced significantly with high-capacity foundation models like DINOv2, achieving remarkable performance. Nonetheless, their substantial computational cost makes deployment on resource-constrained devices impractical. In this paper, we introduce an efficient asymmetric VPR framework that incorporates a high-capacity gallery model for offline feature extraction with a lightweight query network for online processing. A key challenge in this setting is ensuring compatibility between these heterogeneous networks, which conventional approaches address through computationally expensive k-NN-based compatible training. To overcome this, we propose a geographical memory bank that structures gallery features using geolocation metadata inherent in VPR databases, eliminating the need for exhaustive k-NN computations. Additionally, we introduce an implicit embedding augmentation technique that enhances the query network to model feature variations despite its limited capacity. Extensive experiments demonstrate that our method not only significantly reduces computational costs but also outperforms existing asymmetric retrieval techniques, establishing a new aspect for VPR in resource-limited environments.

Nearest neighbor (NN) graph based visual re-ranking has emerged as a powerful approach for improving retrieval accuracy, offering the advantages of effectively exploring high-dimensional manifolds without requiring additional fine-tuning. However, the effectiveness of NN graph-based re-ranking is fundamentally constrained by the quality of its edge connectivity, as incorrect connections between dissimilar (negative) images frequently occur. This is known as a noisy edge problem, which hinders the re-ranking performance of existing techniques and limits their potential. To remedy this issue, we propose a complementary denoising method based on Continuous Conditional Random Fields (C-CRF) that leverages statistical distances derived from similarity-based distributions. As a pre-processing step for enhancing NN graph-based retrieval, our approach constructs fully connected cliques around each anchor image and employs a novel statistical distance metric to robustly alleviate noisy edges before re-ranking while achieving efficient processing through offline computation. Extensive experimental results demonstrate that our method consistently improves three different NN graph-based re-ranking approaches, yielding significant gains in retrieval accuracy.

While generalizable 3D Gaussian splatting enables efficient, high-quality rendering of unseen scenes, it heavily depends on precise camera poses for accurate geometry. In real-world scenarios, obtaining accurate poses is challenging, leading to noisy pose estimates and geometric misalignments. To address this, we introduce SHARE, a pose-free, feed-forward Gaussian splatting framework that overcomes these ambiguities by joint shape and camera rays estimation. Instead of relying on explicit 3D transformations, SHARE builds a pose-aware canonical volume representation that seamlessly integrates multi-view information, reducing misalignment caused by inaccurate pose estimates. Additionally, anchor-aligned Gaussian prediction enhances scene reconstruction by refining local geometry around coarse anchors, allowing for more precise Gaussian placement. Extensive experiments on diverse real-world datasets show that our method achieves robust performance in pose-free generalizable Gaussian splatting.

The outstanding capability of diffusion models in generating high-quality images poses significant threats when misused by adversaries. In particular, we assume malicious adversaries exploiting diffusion models for inpainting tasks, such as replacing a specific region with a celebrity. While existing methods for protecting images from manipulation in diffusion-based generative models have primarily focused on image-to-image and text-to-image tasks, the challenge of preventing unauthorized inpainting has been rarely addressed, often resulting in suboptimal protection performance. To mitigate inpainting abuses, we propose ADVPAINT, a novel defensive framework that generates adversarial perturbations that effectively disrupt the adversary’s inpainting tasks. ADVPAINT targets the self- and cross-attention blocks in a target diffusion inpainting model to distract semantic understanding and prompt interactions during image generation. ADVPAINT also employs a two-stage perturbation strategy, dividing the perturbation region based on an enlarged bounding box around the object, enhancing robustness across diverse masks of varying shapes and sizes. Our experimental results demonstrate that ADVPAINT’s perturbations are highly effective in disrupting the adversary’s inpainting tasks, outperforming existing methods; ADVPAINT attains over a 100-point increase in FID and substantial decreases in precision.

Quadruped robots face limitations in long-range navigation efficiency due to their reliance on legs. To ameliorate the limitations, we introduce a Reinforcement Learning-based Active Transporter Riding method (RL-ATR), inspired by humans' utilization of personal transporters, including Segways. The RL-ATR features a transporter riding policy and two state estimators. The policy devises adequate maneuvering strategies according to transporter-specific control dynamics, while the estimators resolve sensor ambiguities in non-inertial frames by inferring unobservable robot and transporter states. Comprehensive evaluations in simulation validate proficient command tracking abilities across various transporter-robot models and reduced energy consumption compared to legged locomotion. Moreover, we conduct ablation studies to quantify individual component contributions within the RL-ATR. This riding ability could broaden the locomotion modalities of quadruped robots, potentially expanding the operational range and efficiency.

We propose a hierarchical reinforcement learning (HRL) framework for efficient Navigation Among Movable Obstacles (NAMO) using a mobile manipulator. Our approach combines interaction-based obstacle property estimation with structured pushing strategies, facilitating the dynamic manipulation of unforeseen obstacles while adhering to a preplanned global path. The high-level policy generates pushing commands that consider environmental constraints and path-tracking objectives, while the low-level policy precisely and stably executes these commands through coordinated whole-body movements. Comprehensive simulation-based experiments demonstrate improvements in performing NAMO tasks, including higher success rates, shortened traversed path length, and reduced goal-reaching times, compared to baselines. Additionally, ablation studies assess the efficacy of each component, while a qualitative analysis further validates the accuracy and reliability of the real-time obstacle property estimation.

Existing open-set recognition (OSR) studies typically assume that each image contains only one class label, with the unknown test set (negative) having a disjoint label space from the known test set (positive), a scenario referred to as full-label shift. This paper introduces the mixed OSR problem, where test images contain multiple class semantics, with both known and unknown classes co-occurring in the negatives, leading to a more complex super-label shift that better reflects real-world scenarios. To tackle this challenge, we propose the OpenSlot framework, based on object-centric learning, which uses slot features to represent diverse class semantics and generate class predictions. The proposed anti-noise slot (ANS) technique helps mitigate the impact of noise (invalid or background) slots during classification training, addressing the semantic misalignment between class predictions and ground truth. We evaluate OpenSlot on both mixed and conventional OSR benchmarks. Without elaborate designs, our method not only excels existing approaches in detecting super-label shifts across OSR tasks, but also achieves state-of-the-art performance on conventional benchmarks. Meanwhile, OpenSlot can localize class objects without using bounding boxes during training, demonstrating competitive performance in open-set object detection and potential for generalization.

We present “SemCity,” a 3D diffusion model for semantic scene generation in real-world outdoor environments. Most 3D diffusion models focus on generating a single object, synthetic indoor scenes, or synthetic outdoor scenes, while the generation of real-world outdoor scenes is rarely addressed. In this paper, we concentrate on generating a real-outdoor scene through learning a diffusion model on a realworld outdoor dataset. In contrast to synthetic data, real-outdoor datasets often contain more empty spaces due to sensor limitations, causing challenges in learning realoutdoor distributions. To address this issue, we exploit a triplane representation as a proxy form of scene distributions to be learned by our diffusion model. Furthermore, we propose a triplane manipulation that integrates seamlessly with our triplane diffusion model. The manipulation improves our diffusion model's applicability in a variety of downstream tasks related to outdoor scene generation such as scene inpainting, scene outpainting, and semantic scene completion refinements. In experimental results, we demonstrate that our triplane diffusion model shows meaningful generation results compared with existing work in a real-outdoor dataset, SemanticKITTI. We also show our triplane manipulation facilitates seamlessly adding, removing, or modifying objects within a scene. Further, it also enables the expansion of scenes toward a city-level scale. Finally, we evaluate our method on semantic scene completion refinements where our diffusion model enhances predictions of semantic scene completion networks by learning scene distribution. Our code is available at https://github.com/zoom.in-lee/SemCity.

Generalizable neural implicit surface reconstruction aims to obtain an accurate underlying geometry given a limited number of multi-view images from unseen scenes. However, existing methods select only informative and rel-evant views using predefined scores for training and testing phases. This constraint makes the model impractical because we cannot always ensure the availability of favorable combinations in real-world scenarios. We observe that previous methods output degenerate solutions under arbi-trary and unfavorable sets. Building upon this finding, we propose UFORecon, a robust view-combination general-izable surface reconstruction framework. To this end, we apply cross-view matching transformers to model interactions between source images and build correlation frustums to capture global correlations. In addition, we explicitly encode pairwise feature similarities as view-consistent pri-ors. Our proposed framework largely outperforms previous methods not only in view-combination generalizability but also in the existing generalizable protocol trained with favorable view-combinations. The code is available at https://github.com/Youngju-NaIUFORecon.

Audio-visual segmentation (AVS) aims to segment sound sources in the video sequence, requiring a pixel-level understanding of audiovisual correspondence. As the Segment Anything Model (SAM) has strongly impacted extensive fields of dense prediction problems, prior works have investigated the introduction of SAM into AVS with audio as a new modality of the prompt. Nevertheless, constrained by SAM’s single-frame segmentation scheme, the temporal context across multiple frames of audio-visual data remains insufficiently utilized. To this end, we study the extension of SAM’s capabilities to the sequence of audio-visual scenes by analyzing contextual cross-modal relationships across the frames. To achieve this, we propose a Spatio-Temporal, Bidirectional Audio-Visual Attention (ST-BAVA) module integrated into the middle of SAM’s image encoder and mask decoder. It adaptively updates the audio-visual features to convey the spatio-temporal correspondence between the video frames and audio streams. Extensive experiments demonstrate that our proposed model outperforms the state-of-the-art methods on AVS benchmarks, especially with an 8.3% mIoU gain on a challenging multi-sources subset.

LiDAR-camera calibration plays a crucial role in autonomous driving. However, operation-induced factors such as physical vibrations and temperature variations degrade the pre-deployment calibration accuracy, leading to the environmental perception performance deterioration. Recent recalibration methods have achieved online calibration without a target board by leveraging the relative attributes of LiDAR and camera. Nevertheless, we proposes a novel framework for LiDAR-camera online calibration which employs a Transformer network to learn crucial interactions between cameras and LiDAR sensors. Additionally, our novel framework design enables the effective calibration by utilizing correspondence point information between the two sensors. This allows the utilization of global spatial context and achieves high performance by integrating information across modalities. Experimental results indicate that our method demonstrates superior performance compared to state-of-the-art benchmarks.

A quadruped robot faces balancing challenges on a six-degrees-of-freedom moving platform, like subways, buses, airplanes, and yachts, due to independent platform motions and resultant diverse inertia forces on the robot. To alleviate these challenges, we present the Learning-based Active Stabilization on Moving Platforms (LAS-MP), featuring a self-balancing policy and system state estimators. The policy adaptively adjusts the robot’s posture in response to the platform’s motion. The estimators infer robot and platform states based on proprioceptive sensor data. For a systematic training scheme across various platform motions, we introduce platform trajectory generation and scheduling methods. Our evaluation demonstrates superior balancing performance across multiple metrics compared to three baselines. Furthermore, we conduct a detailed analysis of the LAS-MP, including ablation studies and evaluation of the estimators, to validate the effectiveness of each component.

In the field of off-road navigation, integrating terrain data into path planning is becoming increasingly vital. It considers terrain roughness, slope, and step height, which are crucial parameters to ensure stability. This approach significantly differs from indoor driving scenarios, where the terrain is generally flat and exhibits less variability. In this paper, we define the traversability of terrain, numerically quantify it in terms of cost, and apply various asymptotically optimal planners, including RRT-Connect, RRT*, and PRM*, to identify the most cost-effective optimally traversable path. These planners are specifically designed to iteratively improve their solutions over time, gradually approaching the optimal solution as computation time increases. The effectiveness of these planners is evaluated within a limited time budget to assess their performance in simulation under realistic off-road conditions.

Domain generalizable person re-identification (DG re-ID) aims to learn discriminative representations that are robust to distributional shifts. While data augmentation is a straightforward solution to improve generalization, certain augmentations exhibit a polarized effect in this task, enhancing in-distribution performance while deteriorating out-of-distribution performance. In this paper, we investigate this phenomenon and reveal that it leads to sparse representation spaces with reduced uniformity. To address this issue, we propose a novel framework, Balancing Alignment and Uniformity (BAU), which effectively mitigates this effect by maintaining a balance between alignment and uniformity. Specifically, BAU incorporates alignment and uniformity losses applied to both original and augmented images and integrates a weighting strategy to assess the reliability of augmented samples, further improving the alignment loss. Additionally, we introduce a domain-specific uniformity loss that promotes uniformity within each source domain, thereby enhancing the learning of domain-invariant features. Extensive experimental results demonstrate that BAU effectively exploits the advantages of data augmentation, which previous studies could not fully utilize, and achieves state-of-the-art performance without requiring complex training procedures. The code is available at https://github.com/yoonkicho/BAU.

Generating reliable pseudo masks from image-level labels is challenging in the weakly supervised semantic segmentation (WSSS) task due to the lack of spatial information. Prevalent class activation map (CAM)-based solutions are challenged to discriminate the foreground (FG) objects from the suspicious background (BG) pixels (a.k.a. co-occurring) and learn the integral object regions. This paper proposes a simple fine-grained background representation (FBR) method to discover and represent diverse BG semantics and address the co-occurring problems. We abandon using the class prototype or pixel-level features for BG representation. Instead, we develop a novel primitive, negative region of interest (NROI), to capture the fine-grained BG semantic information and conduct the pixel-to-NROI contrast to distinguish the confusing BG pixels. We also present an active sampling strategy to mine the FG negatives on-the-fly, enabling efficient pixel-to-pixel intra-foreground contrastive learning to activate the entire object region. Thanks to the simplicity of design and convenience in use, our proposed method can be seamlessly plugged into various models, yielding new state-of-the-art results under various WSSS settings across benchmarks. Leveraging solely image-level (I) labels as supervision, our method achieves 73.2 mIoU and 45.6 mIoU segmentation results on Pascal Voc and MS COCO test sets, respectively. Furthermore, by incorporating saliency maps as an additional supervision signal (I+S), we attain 74.9 mIoU on Pascal Voc test set. Concurrently, our FBR approach demonstrates meaningful performance gains in weakly-supervised instance segmentation (WSIS) tasks, showcasing its robustness and strong generalization capabilities across diverse domains.

Physically based differentiable rendering allows an accurate light transport simulation to be differentiated with respect to the rendering input, i.e., scene parameters, and it enables inferring scene parameters from target images, e.g., photos or synthetic images, via an iterative optimization. However, this inverse Monte Carlo rendering inherits the fundamental problem of the Monte Carlo integration, i.e., noise, resulting in a slow optimization convergence. An appealing approach to addressing such noise is exploiting an image denoiser to improve optimization convergence. Unfortunately, the direct adoption of existing image denoisers designed for ordinary rendering scenarios can drive the optimization into undesirable local minima due to denoising bias. It motivates us to reformulate a new image denoiser specialized for inverse rendering. Unlike existing image denoisers, we conduct our denoising by considering the target images, i.e., specific information in inverse rendering. For our target-aware denoising, we determine our denoising weights via a linear regression technique using the target. We demonstrate that our denoiser enables inverse rendering optimization to infer scene parameters robustly through a diverse set of tests.

Deep neural networks are susceptible to adversarial attacks due to the accumulation of perturbations in the feature level, and numerous works have boosted model robustness by deactivating the non-robust feature activations that cause model mispredictions. However, we claim that these malicious activations still contain discriminative cues and that with recalibration, they can capture additional useful information for correct model predictions. To this end, we propose a novel, easy-to-plugin approach named Feature Separation and Recalibration (FSR) that recalibrates the malicious, non-robust activations for more robust feature maps through Separation and Recalibration. The Separation part disentangles the input feature map into the robust feature with activations that help the model make correct predictions and the non-robust feature with activations that are responsible for model mispredictions upon adversarial attack. The Recalibration part then adjusts the non-robust activations to restore the potentially useful cues for model predictions. Extensive experiments verify the superiority of FSR compared to traditional deactivation techniques and demonstrate that it improves the robustness of existing adversarial training methods by up to 8.57% with small computational overhead. Codes are available at https://github.com/wkim97/FSR

This paper introduces the first two landmark pixel retrieval benchmarks. Pixel retrieval is segmented instance retrieval. Like semantic segmentation extends classification to the pixel level, pixel retrieval is an extension of image retrieval and offers information about which pixels are related to the query object. In addition to retrieving images for the given query, it helps users quickly identify the query object in true positive images and exclude false positive images by denoting the correlated pixels. Our user study results show pixel-level annotation can significantly improve the user experience. Compared with semantic and instance segmentation, pixel retrieval requires a fine-grained recognition capability for variable-granularity targets. To this end, we propose pixel retrieval benchmarks named PROxford and PRParis, which are based on the widely used image retrieval datasets, ROxford and RParis. Three professional annotators label 5,942 images with two rounds of double-checking and refinement. Furthermore, we conduct extensive experiments and analysis on the SOTA methods in image search, image matching, detection, segmentation, and dense matching using our pixel retrieval benchmarks. Results show that the pixel retrieval task is challenging to these approaches and distinctive from existing problems, suggesting that further research can advance the content-based pixel-retrieval and thus user search experience. The datasets can be downloaded from this link.

Real-time remote manipulation requires careful operations by a user to ensure the safety of a robot, which is designed to follow user's commands, against dynamic obstacles. However, a user may give commands to a robot at the risk of collision with dynamic obstacles due to a user's unfamiliar control ability or unexpected situations. In this paper, we propose a risk-aware user command adjustment method to avoid potential collision with dynamic obstacles. Our method consists of a network that predicts the risk of dynamic obstacles and another network that synthesizes commands to avoid obstacles. Based on the predicted risk, our method decides an adjusted command between a user command and a command to avoid collisions. We evaluate our method in problems that face collisions with dynamic obstacles when following given commands and in problems with static obstacles. We show that our method improves safety against the risk of dynamic obstacles or follows user commands when there is no risk. We also demonstrate the feasibility of our method using the real fetch manipulator with seven-degrees-of-freedom.

Trajectory optimization (TO) is an efficient tool to generate a redundant manipulator's joint trajectory following a 6-dimensional Cartesian path. The optimization performance largely depends on the quality of initial trajectories. However, the selection of a high-quality initial trajectory is non-trivial and requires a considerable time budget due to the extremely large space of the solution trajectories and the lack of prior knowledge about task constraints in configuration space. To alleviate the issue, we present a learning-based initial trajectory generation method that generates high-quality initial trajectories in a short time budget by adopting example-guided reinforcement learning. In addition, we suggest a null-space projected imitation reward to consider null-space constraints by efficiently learning kinematically feasible motion captured in expert demonstrations. Our statistical evaluation in simulation shows the improved optimality, efficiency, and applicability of TO when we plug in our method's output, compared with three other baselines. We also show the performance improvement and feasibility via real-world experiments with a seven-degree-of-freedom manipulator.

This paper presents an innovative approach to enhancing explainable image retrieval, particularly in situations where a fine-tuning set is unavailable. The widely-used SPatial verification (SP) method, despite its efficacy, relies on a spatial model and the hypothesis-testing strategy for instance recognition, leading to inherent limitations, including the assumption of planar structures and neglect of topological relations among features. To address these shortcomings, we introduce a pioneering technique that replaces the spatial model with a topological one within the RANSAC process. We propose bio-inspired saccade and fovea functions to verify the topological consistency among features, effectively circumventing the issues associated with SP's spatial model. Our experimental results demonstrate that our method significantly outperforms SP, achieving state-of-the-art performance in non-fine-tuning retrieval. Furthermore, our approach can enhance performance when used in conjunction with fine-tuned features. Importantly, our method retains high explainability and is lightweight, offering a practical and adaptable solution for a variety of real-world applications.

Abstract For the realistic and immersive experience in a virtual environment, it is important to estimate and reflect the acoustic characteristic of the real indoor scenes. This article proposes a method of directly measuring the reflection coefficient of a surface, which is an acoustic characteristics in the real environment. Because expensive optimization‐based studies that mainly aim to reproduce recorded sounds indirectly estimate acoustic materials, new estimates are required whenever the actual environment changes. Our approach utilizes the method of the acoustics field to enable anyone to easily and directly measure the reflection coefficient of a real environment and generate sound in a virtual environment. We obtain the impulse response (IR) for the target surface, separate the direct sound and the reflected sound, and calculate the reflection coefficient for each surface. The measurement of the IR and the reflection coefficient calculation takes about 2 s. Our result produces a sound with a similar reverberation time to the sound recorded in the real environment.

With increasing demands for high-quality semantic segmentation in the industry, hard-distinguishing semantic boundaries have posed a significant threat to existing solutions. Inspired by real-life experience, i.e., combining varied observations contributes to higher visual recognition confidence, we present the equipotential learning (EPL) method. This novel module transfers the predicted/ground-truth semantic labels to a self-defined potential domain to learn and infer decision boundaries along customized directions. The conversion to the potential domain is implemented via a lightweight differentiable anisotropic convolution without incurring any parameter overhead. Besides, the designed two loss functions, the point loss and the equipotential line loss implement anisotropic field regression and category-level contour learning, respectively, enhancing prediction consistencies in the inter/intra-class boundary areas. More importantly, EPL is agnostic to network architectures, and thus it can be plugged into most existing segmentation models. This paper is the first attempt to address the boundary segmentation problem with field regression and contour learning. Meaningful performance improvements on Pascal Voc 2012 and Cityscapes demonstrate that the proposed EPL module can benefit the off-the-shelf fully convolutional network models when recognizing semantic boundary areas. Besides, intensive comparisons and analysis show the favorable merits of EPL for distinguishing semantically-similar and irregular-shaped categories.

Unsupervised person re-identification (re-ID) aims at learning discriminative representations for person retrieval from unlabeled data. Recent techniques accomplish this task by using pseudo-labels, but these labels are inherently noisy and deteriorate the accuracy. To overcome this problem, several pseudo-label refinement methods have been proposed, but they neglect the fine-grained local context essential for person re-ID. In this paper, we propose a novel Part-based Pseudo Label Refinement (PPLR) framework that reduces the label noise by employing the complementary relationship between global and part features. Specifically, we design a cross agreement score as the similarity of k-nearest neighbors between feature spaces to exploit the reliable complementary relationship. Based on the cross agreement, we refine pseudo-labels of global features by ensembling the predictions of part features, which collectively alleviate the noise in global feature clustering. We further refine pseudo-labels of part features by applying label smoothing according to the suitability of given labels for each part. Thanks to the reliable complementary information provided by the cross agreement score, our PPLR effectively reduces the influence of noisy labels and learns discriminative representations with rich local contexts. Extensive experimental results on Market-1501 and MSMT17 demonstrate the effectiveness of the proposed method over the state-of-the-art performance. The code is available at https://github.com/yoonkicho/PPLR.

Humans can easily imagine a scene from auditory information based on their prior knowledge of audio-visual events. In this paper, we mimic this innate human ability in deep learning models to improve the quality of video inpainting. To implement the prior knowledge, we first train the audio-visual network, which learns the correspondence between auditory and visual information. Then, the audio-visual network is employed as a guider that conveys the prior knowledge of audio-visual correspondence to the video inpainting network. This prior knowledge is transferred through our proposed two novel losses: audio-visual attention loss and audio-visual pseudo-class consistency loss. These two losses further improve the performance of the video inpainting by encouraging the inpainting result to have a high correspondence to its synchronized audio. Experimental results demonstrate that our proposed method can restore a wider domain of video scenes and is particularly effective when the sounding object in the scene is partially blinded.

Adversarial attacks with improved transferability –the ability of an adversarial example crafted on a known model to also fool unknown models –have recently received much attention due to their practicality. Nevertheless, existing transferable attacks craft perturbations in a deterministic manner and often fail to fully explore the loss surface, thus falling into a poor local optimum and suffering from low transferability. To solve this problem, we propose Attentive-Diversity Attack (ADA), which disrupts diverse salient features in a stochastic manner to improve transferability. Primarily, we perturb the image attention to disrupt universal features shared by different models. Then, to effectively avoid poor local optima, we disrupt these features in a stochastic manner and explore the search space of transferable perturbations more exhaustively. More specifically, we use a generator to produce adversarial perturbations that each disturbs features in different ways depending on an input latent code. Extensive experimental evaluations demonstrate the effectiveness of our method, outperforming the transferability of state-of-the-art methods. Codes are available at https://github.com/wkim97/ADA.

Super-resolution of LiDAR range images is crucial to improving many downstream tasks such as object detection, recognition, and tracking. While deep learning has made a remarkable advances in super-resolution techniques, typical convolutional architectures limit upscaling factors to specific output resolutions in training. Recent work has shown that a continuous representation of an image and learning its implicit function enable almost limitless upscaling. However, the detailed approach, predicting values (depths) for neighbor pixels in the input and then linearly interpolating them, does not best fit the LiDAR range images since it does not fill the unmeasured details but creates a new image with regression in a high-dimensional space. In addition, the linear interpolation blurs sharp edges providing important boundary information of objects in 3-D points. To handle these problems, we propose a novel network, Implicit LiDAR Network (ILN), which learns not the values per pixels but weights in the interpolation so that the super-resolution can be done by blending the input pixel depths but with non-linear weights. Also, the weights can be considered as attentions from the query to the neighbor pixels, and thus an attention module in the recent Transformer architecture can be leveraged. Our experiments with a novel large-scale synthetic dataset demonstrate that the proposed network reconstructs more accurately than the state-of-the-art methods, achieving much faster convergence in training.

This paper considers the problem of prolonged occlusions on navigation sensors due to dust, smudges, soils, etc. Such uncontrollable occlusions often cause lower visibility as well as higher uncertainty that require considerably sophisticated behavior. To secure visibility (i.e., confidence about the world), we propose a confidence-based navigation method that encourages the robot to explore the uncertain region around the robot maximizing its local confidence. To effectively extract features from the variable size of sensor occlusions, we adopt a point-cloud based representation network. Our method returns a resilient navigation policy via deep reinforcement learning, autonomously avoiding collisions under sensor occlusions while reaching a goal. We evaluate our method in simulated and real-world environments with either static or dynamic obstacles under various sensor-occlusion scenarios. The experimental result shows that our method outperforms baseline methods under the highly occurring sensor occlusion, and achieves maximum 90% and 80% success rates in the tested static and dynamic environments, respectively.

In this article, we present a novel localization method for multiple sources in indoor environments. Our approach can estimate different propagation paths, including the reflection and diffraction paths of sound waves based on a backward ray tracing technique. To estimate diffraction propagation paths, we combine a ray tracing algorithm with a uniform theory of diffraction model by exploiting the diffraction properties as propagation paths bend around the wedges of obstacles. We reconstruct the 3-D environments and wedges of obstacles in the precomputation phase and utilize these outcomes to generate primary, reflection, and diffraction acoustic rays in the runtime phase. We localize multiple sources when identifying the convergence regions of these acoustic rays based on Monte Carlo localization (MCL). Our approach supports not only stationary but also moving sources of human speech and clapping sounds. Our approach can also handle nonline-of-sight (NLOS) sources and distinguish between active and inactive source states. We evaluated and analyzed our algorithm in multiple scenarios containing obstacles and NLOS sources. Our approach can localize moving sources with the average of distance errors of 0.65 and 0.74 m in single and multiple source cases, respectively, in rooms, 7 m by 7 m in size with a height of 3 m; errors are measured according to the L2 distance between the estimated and actual source positions. We observed a 130% improvement of the localization accuracy over the prior work (J.-M. Valinet al.).

Vision aided dynamic exploration on bipedal robots poses an integrated challenge for perception and control. Rapid walking motions as well as the vibrations caused by the landing-foot contact-force introduce critical uncertainty in the visual-inertial system, which can cause the robot to misplace its feet placing on complex terrains and even fall over. In this paper, we present a streamlined integration of an efficient geometric footstep planner and the corresponding walking controller for a humanoid robot to dynamically walk across rough terrain at speeds up to 0.3 m/s. To handle perception uncertainty that arises during dynamic locomotion, we present a geometric safety scoring method in our footstep planner to optimally select feasible path candidates. In addition, the real-time performance of the perception pipeline allows for reactive locomotion such as generating a new corresponding swing leg trajectory in mid-gait if a sudden change in the terrain is detected. The proposed perception-control pipeline is evaluated and demonstrated with real experiments using a full-scale humanoid to traverse across various terrains.

Spatial verification is a crucial technique for particular object retrieval. It utilizes spatial information for the accurate detection of true positive images. However, existing query expansion and diffusion methods cannot efficiently propagate the spatial information in an ordinary graph with scalar edge weights, resulting in low recall or precision. To tackle these problems, we propose a novel hypergraph-based framework that efficiently propagates spatial information in query time and retrieves an object in the database accurately. Additionally, we propose using the image graph's structure information through community selection technique, to measure the accuracy of the initial search result and to provide correct starting points for hypergraph propagation without heavy spatial verification computations. Experiment results on ROxford and RParis show that our method significantly outperforms the existing query expansion and diffusion methods.

It is essential to predict the popularity of a particular shop type when investors decide which type of shops to open at a given location.Existing shop-type recommender systems have approached this problem by building a regiontype matrix and analyzing the relationship between different regions and shop types.However, these methods make recommendations for each region, thus having difficulty analyzing a specific shop, especially near the two regions' borders.To tackle this challenge, we propose a novel Graph Neural Network (GNN) model, called GraphShop, to represent shops as nodes in a graph and analyze each shop without assigning it to a region.As it is difficult to find the influential neighbors, we propose two aggregation methods, Distance-Module and TypeModule, in GraphShop.DistanceModule aggregates unordered nearby shops in every zone and filters them from the remote zones.TypeModule reorders the nearby shops based on their types and considers the interaction of different types.Furthermore, to address the lack of open shop-type recommendation datasets, we build a qualitative and large-scale dataset collected from a review website and location-based services.It contains most, if not all, shops in a region and is large and diverse, by containing 53,182 shops with 122 types.Our dataset is available at https://github.com/BoSamothrace/GraphShop.Through the experimental results, we demonstrate that our method outperforms the existing state-of-the-art methods for shoptype recommendation by a factor of up to 37 %.

Monte Carlo (MC) integration is used ubiquitously in realistic image synthesis because of its flexibility and generality. However, the integration has to balance estimator bias and variance, which causes visually distracting noise with low sample counts. Existing solutions fall into two categories, in-process sampling schemes and post-processing reconstruction schemes. This report summarizes recent trends in the post-processing reconstruction scheme. Recent years have seen increasing attention and significant progress in denoising MC rendering with deep learning, by training neural networks to reconstruct denoised rendering results from sparse MC samples. Many of these techniques show promising results in real-world applications, and this report aims to provide an assessment of these approaches for practitioners and researchers.

Image-space auxiliary features such as surface normal have significantly contributed to the recent success of Monte Carlo (MC) reconstruction networks. However, path-space features, another essential piece of light propagation, have not yet been sufficiently explored. Due to the curse of dimensionality, information flow between a regression loss and high-dimensional path-space features is sparse, leading to difficult training and inefficient usage of path-space features in a typical reconstruction framework. This paper introduces a contrastive manifold learning framework to utilize path-space features effectively. The proposed framework employs weakly-supervised learning that converts reference pixel colors to dense pseudo labels for light paths. A convolutional path-embedding network then induces a low-dimensional manifold of paths by iteratively clustering intra-class embeddings, while discriminating inter-class embeddings using gradient descent. The proposed framework facilitates path-space exploration of reconstruction networks by extracting low-dimensional yet meaningful embeddings within the features. We apply our framework to the recent image- and sample-space models and demonstrate considerable improvements, especially on the sample space. The source code is available at https://github.com/Mephisto405/WCMC.

This paper proposes a novel panoramic texture mapping-based rendering system for real-time, photorealistic reproduction of large-scale urban scenes at a street level. Various image-based rendering (IBR) methods have recently been employed to synthesize high-quality novel views, although they require an excessive number of adjacent input images or detailed geometry just to render local views. While the development of global data, such as Google Street View, has accelerated interactive IBR techniques for urban scenes, such methods have hardly been aimed at high-quality street-level rendering. To provide users with free walk-through experiences in global urban streets, our system effectively covers large-scale scenes by using sparsely sampled panoramic street-view images and simplified scene models, which are easily obtainable from open databases. Our key concept is to extract semantic information from the given street-view images and to deploy it in proper intermediate steps of the suggested pipeline, which results in enhanced rendering accuracy and performance time. Furthermore, our method supports real-time semantic 3D inpainting to handle occluded and untextured areas, which appear often when the user's viewpoint dynamically changes. Experimental results validate the effectiveness of this method in comparison with the state-of-the-art approaches. We also present real-time demos in various urban streets.

Recently, deep learning-based single image reflection separation methods have been exploited widely. To benefit the learning approach, a large number of training image pairs (i.e., with and without reflections) were synthesized in various ways, yet they are away from a physically-based direction. In this paper, physically based rendering is used for faithfully synthesizing the required training images, and a corresponding network structure and loss term are proposed. We utilize existing RGBD/RGB images to estimate meshes, then physically simulate the light transportation between meshes, glass, and lens with path tracing to synthesize training data, which successfully reproduce the spatially variant anisotropic visual effect of glass reflection. For guiding the separation better, we additionally consider a module, backtrack network (BT-net) for backtracking the reflections, which removes complicated ghosting, attenuation, blurred and defocused effect of glass/lens. This enables obtaining a priori information before having the distortion. The proposed method considering additional a priori information with physically simulated training data is validated with various real reflection images and shows visually pleasant and numerical advantages compared with state-of-the-art techniques.

We present a novel, robust sound source localization algorithm considering back-propagation signals. Sound propagation paths are estimated by generating direct and reflection acoustic rays based on ray tracing in a backward manner. We then compute the back-propagation signals by designing and using the impulse response of the backward sound propagation based on the acoustic ray paths. For identifying the 3D source position, we use a well-established Monte Carlo localization method. Candidates for a source position are determined by identifying convergence regions of acoustic ray paths. Those candidates are validated by measuring similarities between back-propagation signals, under the assumption that the back-propagation signals of different acoustic ray paths should be similar near the ground-truth sound source position. Thanks to considering similarities of back-propagation signals, our approach can localize a source position with an averaged error of 0.55 m in a room of 7 m by 7 m area with 3 m height in tested environments. We also place additional 67 dB and 77 dB white noise at the background, to test the robustness of our approach. Overall, we observe a 7 % to 100 % improvement in accuracy over the state-of-the-art method.

A redundant manipulator has multiple inverse kinematics solutions per end-effector pose. Accordingly, there can be many trajectories for joints that follow a given end-effector path in the Cartesian space. In this paper, we present a trajectory optimization of a redundant manipulator (TORM) to synthesize a trajectory that follows a given end-effector path accurately, while achieving smoothness and collision-free manipulation. Our method holistically incorporates three desired properties into the trajectory optimization process by integrating the Jacobian-based inverse kinematics solving method and an optimization-based motion planning approach. Specifically, we optimize a trajectory using two-stage gradient descent to reduce potential competition between different properties during the update. To avoid falling into local minima, we iteratively explore different candidate trajectories with our local update. We compare our method with state-of-the-art methods in test scenes including external obstacles and two non-obstacle problems. Our method robustly minimizes the pose error in a progressive manner while satisfying various desirable properties.

In this paper, we present a new approach, AKIMap, that uses an adaptive kernel inference for dense and sharp occupancy grid representations. Our approach is based on the multivariate kernel estimation, and we propose a simple, two-stage based method that selects an adaptive bandwidth matrix for an efficient and accurate occupancy estimation. To utilize correlations of occupancy observations given sparse and non-uniform distributions of point samples, we propose to use the covariance matrix as an initial bandwidth matrix, and then optimize the bandwidth matrix by adjusting its scale in an efficient, data-driven way for on-the-fly mapping. We demonstrate that the proposed technique estimates occupancy states more accurately than state-of-the-art methods given equal-data or equal-time settings, thanks to our adaptive inference. Furthermore, we show the practical benefits of the proposed work in on-the-fly mapping and observe that our adaptive approach shows the dense as well as sharp occupancy representations in a real environment.

Person following is an essential task for a robot to serve a person. In an indoor environment, however, the following task can be failed due to the occlusion of the target by structures, e.g., walls or pillars. To address this problem, we propose a method that helps the robot follow the target well and rapidly re-detect the target after missing. The proposed method is an optimization-based path planning which uses a Following Field that we propose in this paper. The following field consists of two sub-fields: the repulsion field getting the robot out of the occluded area, and the target attraction field pushing the robot toward the target. We introduce how to construct the fields and how to integrate the field into a path optimization process. We show that our method works properly for following the target well in a maze consisting of various in-door features.

Serious noise affects the rendering of global illumination using Monte Carlo (MC) path tracing when insufficient samples are used. The two common solutions to this problem are filtering noisy inputs to generate smooth but biased results and sampling the MC integrand with a carefully crafted probability distribution function (PDF) to produce unbiased results. Both solutions benefit from an efficient incident radiance field sampling and reconstruction algorithm. This study proposes a method for training quality and reconstruction networks (Q- and R-networks, respectively) with a massive offline dataset for the adaptive sampling and reconstruction of first-bounce incident radiance fields. The convolutional neural network (CNN)-based R-network reconstructs the incident radiance field in a 4D space, whereas the deep reinforcement learning (DRL)-based Q-network predicts and guides the adaptive sampling process. The approach is verified by comparing it with state-of-the-art unbiased path guiding methods and filtering methods. Results demonstrate improvements for unbiased path guiding and competitive performance in biased applications, including filtering and irradiance caching.

In mixed reality (MR), augmenting virtual objects consistently with real-world illumination is one of the key factors that provide a realistic and immersive user experience. For this purpose, we propose a novel deep learning-based method to estimate high dynamic range (HDR) illumination from a single RGB image of a reference object. To obtain illumination of a current scene, previous approaches inserted a special camera in that scene, which may interfere with user's immersion, or they analyzed reflected radiances from a passive light probe with a specific type of materials or a known shape. The proposed method does not require any additional gadgets or strong prior cues, and aims to predict illumination from a single image of an observed object with a wide range of homogeneous materials and shapes. To effectively solve this ill-posed inverse rendering problem, three sequential deep neural networks are employed based on a physically-inspired design. These networks perform end-to-end regression to gradually decrease dependency on the material and shape. To cover various conditions, the proposed networks are trained on a large synthetic dataset generated by physically-based rendering. Finally, the reconstructed HDR illumination enables realistic image-based lighting of virtual objects in MR. Experimental results demonstrate the effectiveness of this approach compared against state-of-the-art methods. The paper also suggests some interesting MR applications in indoor and outdoor scenes.

We present a novel sound localization algorithm for a non-line-of-sight (NLOS) sound source in indoor environments. Our approach exploits the diffraction properties of sound waves as they bend around a barrier or an obstacle in the scene. We combine a ray tracing-based sound propagation algorithm with a Uniform Theory of Diffraction (UTD) model, which simulate bending effects by placing a virtual sound source on a wedge in the environment. We precompute the wedges of a reconstructed mesh of an indoor scene and use them to generate diffraction acoustic rays to localize the 3D position of the source. Our method identifies the convergence region of those generated acoustic rays as the estimated source position based on a particle filter. We have evaluated our algorithm in multiple scenarios consisting of static and dynamic NLOS sound sources. In our tested cases, our approach can localize a source position with an average accuracy error of 0.7m, measured by the L2 distance between estimated and actual source locations in a 7m×7m×3m room. Furthermore, we observe 37% to 130% improvement in accuracy over a state-of-the-art localization method that does not model diffraction effects, especially when a sound source is not visible to the robot.

Mobile manipulation planning commonly adopts a decoupled approach that performs planning separately on the base and the manipulator. While this approach is fast, it can generate sub-optimal paths. Another direction is a coupled approach jointly adjusting the base and manipulator in a high-dimensional configuration space. This coupled approach addresses sub-optimality and incompleteness of the decoupled approach, but has not been widely used due to its excessive computational overhead. Given this trade-off space, we present a simple, yet effective mobile manipulation sampling method, harmonious sampling, to perform the coupled approach mainly in difficult regions, where we need to simultaneously maneuver the base and the manipulator. Our method identifies such difficult regions through a low-dimensional base space by utilizing a reachability map given the target end-effector pose and narrow passage detected by generalized Voronoi diagram. For the rest of simple regions, we perform sampling mainly on the base configurations with a predefined joint configuration, accelerating the planning process. We compare our method with the decoupled and coupled approaches in six different problems with varying difficulty. Our method shows meaningful improvements experimentally in terms of time to find an initial solution (up to 5.6 times faster) and final solution cost (up to 17% lower) over the decoupled approach, especially in difficult scenes with narrow space. We also demonstrate these benefits with a real, mobile Hubo robot.

We present volumetric tree*, a hybridization of sampling-based and optimization-based motion planning. Volumetric tree*constructs an adaptive sparse graph with volumetric vertices, hyper-spheres encoding free configurations, using a sampling-based motion planner for a homotopy exploration. The coarse-grained paths computed on the sparse graph are refined by optimization-based planning during the execution, while exploiting the probabilistic completeness of the sampling- based planning for the initial path generation. We also suggest a dropout technique probabilistically ensuring that the sampling- based planner is capable of identifying all possible homotopies of solution paths. We compare the proposed algorithm against the state-of-the-art planners in both synthetic and practical benchmarks with varying dimensions, and experimentally show the benefit of the proposed algorithm.

Abstract We present a new outlier removal technique for a gradient‐domain path tracing (G‐PT) that computes image gradients as well as colors. Our approach rejects gradient outliers whose estimated errors are much higher than those of the other gradients for improving reconstruction quality for the G‐PT. We formulate our outlier removal problem as a least trimmed squares optimization, which employs only a subset of gradients so that a final image can be reconstructed without including the gradient outliers. In addition, we design this outlier removal process so that the chosen subset of gradients maintains connectivity through gradients between pixels, preventing pixels from being isolated. Lastly, the optimal number of inlier gradients is estimated to minimize our reconstruction error. We have demonstrated that our reconstruction with robustly rejecting gradient outliers produces visually and numerically improved results, compared to the previous screened Poisson reconstruction that uses all the gradients.

Approximate 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.

In this paper, we present two novel approaches, super rays and culling region, for efficiently updating grid-based occupancy maps with point clouds. Rays, which traverse from the sensor origin to the sensor data, update the occupancy probabilities of a map representing an environment. Based on the ray model, we define a super ray as a representative ray to multiple rays having the same traversal patterns during the map updates. Our super rays utilize the geometric information of rays and reduce the number of points used for updating the map. For constructing super rays efficiently, we propose mapping lines for handling two- and three-dimensional cases from an observation that edges or grid points branch out the traversal patterns on the map. Furthermore, we introduce a culling region using the occupancy states of the updated map for reducing redundant computations occurred in updates. The super rays perform the update process in a single traversal, and the culling region reduces the number of unnecessary traversals for updating the map. As a result, our combined method improves the update performance without compromising any representation accuracy of a grid-based map. We test the update performance of the proposed method using public indoor and outdoor datasets. Our combined approach shows up to 11.8 times and 2.8 times performance improvement over the state-of-the-art update methods of grid-based maps in the indoor and outdoor scenes, respectively. Also, we compare the update speed and the representation accuracy of our method using the KITTI dataset over the state-of-the-art learning-based occupancy maps. In a navigation scenario that raw point clouds are acquired in 10 Hz, our method shows the best performance on the update speed and thus the highest representation accuracy within a given time.

We present a novel, reflection-aware method for 3D sound localization in indoor environments. Unlike prior approaches, which are mainly based on continuous sound signals from a stationary source, our formulation is designed to localize the position instantaneously from signals within a single frame. We consider direct sound and indirect sound signals that reach the microphones after reflecting off surfaces such as ceilings or walls. We then generate and trace direct and reflected acoustic paths using inverse acoustic ray tracing and utilize these paths with Monte Carlo localization to estimate a 3D sound source position. We have implemented our method on a robot with a cube-shaped microphone array and tested it against different settings with continuous and intermittent sound signals with a stationary or a mobile source. Across different settings, our approach can localize the sound with an average distance error of 0.8 m tested in a room of 7 m by 7 m area with 3 m height, including a mobile and non-line-of-sight sound source. We also reveal that the modeling of indirect rays increases the localization accuracy by 40% compared to only using direct acoustic rays.

A recent trend in optimal motion planning has broadened the research area toward the hybridization of sampling, optimization and grid-based approaches. We can expect that synergy from such integrations leads to overall performance improvement, but seamless integration and generalization is still an open problem. In this paper, we suggest a hybrid motion planning algorithm utilizing a sampling-based and optimization-based planner while simultaneously approximating a configuration free space. Unlike conventional optimization-based approaches, the proposed algorithm does not depend on a priori information or resolution-complete factors, e.g., a distance field. Ours instead learns spatial information on the fly by exploiting empirical information during the execution, and decentralizes the information over the constructed graph for efficient access. With the help of the learned information, our optimization-based local planner exploits the local area to identify the connectivity of configuration free space without depending on the precomputed domain knowledge. To show the novelty of proposed algorithm, we evaluate it against other asymptotic optimal planners in both synthetic and complex benchmarks with varying degrees of freedom. We also discuss the performance improvement, properties and limitations we have observed.

As personal autonomous mobility is getting to be more widely adopted, it is more important to consider comfortability of stuffs and persons carried by such mobility. In this work, we define the comfort of a trajectory as forces, specifically, translational force, received to objects carried by a robot while following the trajectory by measuring impulse. To maximize such a comfort, we propose a novel, kinodynamic comfort path planning method based on our definition of comfort. Our work is based on direct collocation method for handling our nonconvex objective function. We also introduce Bidirectional Obstacle Detection(BOD)that identifies the distances along the perpendicular directions to the trajectory. This is mainly designed for avoiding obstacles while minimizing forces causing discomfort. Our experimental results show that our method can compute trajectories whose comfort measures can be up to 18 times higher than those computed by prior related objectives, e.g., squared velocity used for generating smooth trajectory.

Abstract In this paper, we propose a new technique to incorporate recent adaptive rendering approaches built upon local regression theory into a gradient‐domain path tracing framework, in order to achieve high‐quality rendering results. Our method aims to reduce random artifacts introduced by random sampling on image colors and gradients. Our high‐level approach is to identify a feature image from noisy gradients, and pass the image to an existing local regression based adaptive method so that adaptive sampling and reconstruction using our feature can boost the performance of gradient‐domain rendering. To fulfill our idea, we derive an ideal feature in the form of image gradients and propose an estimation process for the ideal feature in the presence of noise in image gradients. We demonstrate that our integrated adaptive solution leads to performance improvement for a gradient‐domain path tracer, by seamlessly incorporating recent adaptive sampling and reconstruction strategies through our estimated feature.

Illumination changes such as shadows significantly affect the accuracy of various road detection methods, especially for vision-based approaches with an on-board monocular camera. To efficiently consider such illumination changes, we propose a PCA based technique, PCA-II, that finds the minimum projection space from an input RGB image, and then use the space as the illumination-invariant space for road detection. Our PCA based method shows 20 times faster performance on average over the prior entropy based method, even with a higher detection accuracy. To demonstrate its wide applicability to the road detection problem, we test the invariant space with both bottomup and top-down approaches. For a bottom-up approach, we suggest a simple patch propagation method that utilizes the property of the invariant space, and show its higher accuracy over other state-of-the-art road detection methods running in a bottom-up manner. For a top-down approach, we consider the space as an additional feature to the original RGB to train convolutional neural networks. We were also able to observe robust performance improvement of using the invariant space over the original CNN based methods that do not use the space, only with a minor runtime overhead, e.g., 50 ms per image. These results demonstrate benefits of our PCA-based illuminationinvariant space computation.

Abstract We present an interactive technique for generating realistic lightning. Our method captures the main characteristics of the dielectric breakdown model, a physical model for lightning formation. Our algorithm uses a distance‐based approximation to quickly compute the electric potentials of different charge types. In particular, we use a rational function in lieu of summed potentials to better produce interesting lightning patterns. We also propose to use the waypoints commonly available in many game scenes to guide lightning shapes in complex scenes. We found that our algorithm is 2 times faster than the state‐of‐the art method with better controls on lighting shapes, and can generate realistic lightning shapes interactively.

In this paper, we introduce a novel shortlist computation algorithm for approximate, high-dimensional nearest neighbor search. Our method relies on a novel distance estimator: the residual-aware distance estimator, that accounts for the residual distances of data points to their respective quantized centroids, and uses it for accurate short-list computation. Furthermore, we perform the residual-aware distance estimation with little additional memory and computational cost through simple pre-computation methods for inverted index and multi-index schemes. Because it modifies the initial shortlist collection phase, our new algorithm is applicable to most inverted indexing methods that use vector quantization. We have tested the proposed method with the inverted index and multi-index on a diverse set of benchmarks including up to one billion data points with varying dimensions, and found that our method robustly improves the accuracy of shortlists (up to 127% relatively higher) over the state-of-the-art techniques with a comparable or even faster computational cost.

We present a novel approach, Super Ray, for efficiently updating map representations such as grids and octrees with point clouds. In this paper, we define a super ray for points as a representative ray to them with an associated frustum. A super ray is constructed in a way that updating those points has the same set of cells accessed during the map update process. As a result, we can perform the update process with a super ray in a single traversal on the map, resulting in performance improvement without compromising any representation accuracy of the map. For constructing super rays efficiently, we propose mapping lines for handling 2-D and 3-D cases from an observation that edges or grid points branch out the access pattern of updating the map. Our method is general enough to be applied for variety of occupancy map structures based on axis-aligned space subdivisions such as grids and octrees. We test our method into indoor and outdoor benchmarks, and achieve 2.5 times on average (up to 3.5 times) performance improvement over the state-of-the-art update method for OctoMap and grid maps.

We present an efficient anytime motion planner for mobile robots that considers both other dynamic obstacles and uncertainty caused by various sensors and low-level controllers. Our planning algorithm, which is an anytime extension of the Rapidly-exploring Random Belief Tree (RRBT), maintains the best possible path throughout the robot execution, and the generated path gets closer to the optimal one as more computation resources are allocated. We propose a branch-and-bound method to cull out unpromising areas by considering path lengths and uncertainty. We also propose an uncertainty-aware velocity obstacle as a simple local analysis to avoid dynamic obstacles efficiently by finding a collision-free velocity. We have tested our method with three benchmarks that have non-linear measurement regions or potential collisions with dynamic obstacles. By using the proposed methods, we achieve up to five times faster performance given a fixed path cost.

Abstract We present a novel, compact bounding volume hierarchy, TSS BVH, for ray tracing subdivision surfaces computed by the Catmull‐Clark scheme. We use Tetrahedron Swept Sphere (TSS) as a bounding volume to tightly bound limit surfaces of such subdivision surfaces given a user tolerance. Geometric coordinates defining our TSS bounding volumes are implicitly computed from the subdivided mesh via a simple vertex ordering method, and each level of our TSS BVH is associated with a single distance bound, utilizing the Catmull‐Clark scheme. These features result in a linear space complexity as a function of the tree depth, while many prior BVHs have exponential space complexity. We have tested our method against different benchmarks with path tracing and photon mapping. We found that our method achieves up to two orders of magnitude of memory reduction with a high culling ratio over the prior AABB BVH methods, when we represent models with two to four subdivision levels. Overall, our method achieves three times performance improvement thanks to these results. These results are acquired by our theorem that rigorously computes our TSS bounding volumes.

We propose to use discriminative subgraphs to discover family photos from group photos in an efficient and effective way. Group photos are represented as face graphs by identifying social contexts such as age, gender, and face position. The previous work utilized bag-of-word models and considered frequent subgraphs from all group photos as features for classification. This approach, however, produces numerous subgraphs, resulting in high dimensions. Furthermore, some of them are not discriminative. To solve these issues, we adopt a state-of-the-art, frequent subgraph mining method that removes nondiscriminative subgraphs. We also use TF-IDF normalization, which is more suitable for the bag-ofword model. To validate our method, we experiment in two datasets. Our method shows consistently better performance, higher accuracy in lower feature dimensions, compared to the previous method. We also integrate our method with the recent Microsoft face recognition API and release it in a public website.

Abstract Monte Carlo integration is firmly established as the basis for most practical realistic image synthesis algorithms because of its flexibility and generality. However, the visual quality of rendered images often suffers from estimator variance, which appears as visually distracting noise. Adaptive sampling and reconstruction algorithms reduce variance by controlling the sampling density and aggregating samples in a reconstruction step, possibly over large image regions. In this paper we survey recent advances in this area. We distinguish between “a priori” methods that analyze the light transport equations and derive sampling rates and reconstruction filters from this analysis, and “a posteriori” methods that apply statistical techniques to sets of samples to drive the adaptive sampling and reconstruction process. They typically estimate the errors of several reconstruction filters, and select the best filter locally to minimize error. We discuss advantages and disadvantages of recent state‐of‐the‐art techniques, and provide visual and quantitative comparisons. Some of these techniques are proving useful in real‐world applications, and we aim to provide an overview for practitioners and researchers to assess these approaches. In addition, we discuss directions for potential further improvements.

Many binary code embedding schemes have been actively studied recently, since they can provide efficient similarity search, and compact data representations suitable for handling large scale image databases. Existing binary code embedding techniques encode high-dimensional data 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. We also propose a new binary code distance function, spherical Hamming distance, tailored for our hypersphere-based binary coding scheme, and design an efficient iterative optimization process to achieve both balanced partitioning for each hash function and independence between hashing functions. Furthermore, we generalize spherical hashing to support various similarity measures defined by kernel functions. Our extensive experiments show that our spherical hashing technique significantly outperforms state-of-the-art techniques based on hyperplanes across various benchmarks with sizes ranging from one to 75 million of GIST, BoW and VLAD descriptors. The performance gains are consistent and large, up to 100 percent improvements over the second best method among tested methods. These results confirm the unique merits of using hyperspheres to encode proximity regions in high-dimensional spaces. Finally, our method is intuitive and easy to implement.

We present a recursive path-planning method that efficiently generates a path by using reduced states of the search space and taking into account the kinematics, shape, and turning space of a car-like vehicle. Our method is based on a kinematics-aware node expansion method that checks for collisions based on the shape and turning space of a vehicle. We present two heuristics that simultaneously consider the kinematics of a vehicle with and without obstacles. In particular, for challenging environments containing complex obstacles and even narrow passages, we recursively identify intermediate goals and nodes that allow the vehicle to compute a path to its destination. We show the benefits of our method through simulations and experimental results by using an autonomous ground vehicle. Furthermore, we show that our method can efficiently generate a collision-free path for vehicles in complex environments with passageways.

We propose a new adaptive rendering algorithm that enhances the performance of Monte Carlo ray tracing by reducing the noise, i.e., variance, while preserving a variety of high-frequency edges in rendered images through a novel prediction based reconstruction. To achieve our goal, we iteratively build multiple, but sparse linear models. Each linear model has its prediction window, where the linear model predicts the unknown ground truth image that can be generated with an infinite number of samples. Our method recursively estimates prediction errors introduced by linear predictions performed with different prediction windows, and selects an optimal prediction window minimizing the error for each linear model. Since each linear model predicts multiple pixels within its optimal prediction interval, we can construct our linear models only at a sparse set of pixels in the image screen. Predicting multiple pixels with a single linear model poses technical challenges, related to deriving error analysis for regions rather than pixels, and has not been addressed in the field. We address these technical challenges, and our method with robust error analysis leads to a drastically reduced reconstruction time even with higher rendering quality, compared to state-of-the-art adaptive methods. We have demonstrated that our method outperforms previous methods numerically and visually with high performance ray tracing kernels such as OptiX and Embree.

Many binary code embedding techniques have been proposed for large-scale approximate nearest neighbor search in computer vision. Recently, product quantization that encodes the cluster index in each subspace has been shown to provide impressive accuracy for nearest neighbor search. In this paper, we explore a simple question: is it best to use all the bit budget for encoding a cluster index in each subspace? We have found that as data points are located farther away from the centers of their clusters, the error of estimated distances among those points becomes larger. To address this issue, we propose a novel encoding scheme that distributes the available bit budget to encoding both the cluster index and the quantized distance between a point and its cluster center. We also propose two different distance metrics tailored to our encoding scheme. We have tested our method against the-state-of-the-art techniques on several well-known benchmarks, and found that our method consistently improves the accuracy over other tested methods. This result is achieved mainly because our method accurately estimates distances between two data points with the new binary codes and distance metric.

We present a novel biased sampling technique, Cloud RRT∗, for efficiently computing high-quality collision-free paths, while maintaining the asymptotic convergence to the optimal solution. Our method uses sampling cloud for allocating samples on promising regions. Our sampling cloud consists of a set of spheres containing a portion of the C-space. In particular, each sphere projects to a collision-free spherical region in the workspace. We initialize our sampling cloud by conducting a workspace analysis based on the generalized Voronoi graph. We then update our sampling cloud to refine the current best solution, while maintaining the global sampling distribution for exploring understudied other homotopy classes. We have applied our method to a 2D motion planning problem with kinematic constraints, i.e., the Dubins vehicle model, and compared it against the state-of-the-art methods. We achieve better performance, up to three times, over prior methods in a robust manner.

In this paper we propose a novel efficient sampling bias technique to improve the performance of a task space trajectory planner for hyper-redundant manipulators. We defines productive regions in the task space as a set of states that can lead effectively to a goal state. We first compute a maximum reachable area (MRA) where a robot can reach from the node by an employed local planner for a node in the task space. When the MRA of a node contains the goal state, we call it promising and bias our sampling to cover promising MRAs. When the MRA does not contain the goal state, we call it unpromising and construct a detour sampling domain for detouring operations from obstacles constraining the manipulator. The union of promising MRAs and detour sampling domains approximates our productive regions, and we bias our sampling to cover these domains more. We have applied our Productive Regions Oriented Task space planner (PROT) to various types of robots in R2task space and achieved up to 3.54 times improvement over the state-of-the-art task space planner. We have additionally verified the benefits of our method by applying it to cabled mobile robot planning.

Monte Carlo rendering techniques have been widely used to render high-quality images and studied extensively in past decades. Nonetheless, it has remained as a challenging problem yet to construct such realistic images in an interactive manner.

Abstract In general, city trip planning consists of two main steps: knowing Points‐Of‐Interest (POIs), and then planning a tour route from the current point to next preferred POIs. We mainly consider the metro for traveling around touristic cities as the main means of transportation. In this context, existing tools lack a capability to effectively visualize POIs on the metro map for trip planning. To bridge this gap, we propose an interactive framework that holistically combines presentations of POIs and a metro network. Our idea is to identify popular POIs based on visual worth computation, and to introduce POI discovery for effectively identifying POIs within reach of a metro network for users. We use octilinear layouts to highlight the metro network, and show representative POI images in the layout space visualized within a user‐specified viewing window. We have implemented our working prototype showing touristic cities with a metro network. We have factored out various design guidelines that are basis for designing our method, and validated our approach with a user study surveying 70 individuals.

Monte Carlo ray tracing is considered one of the most effective techniques for rendering photo-realistic imagery, but requires a large number of ray samples to produce converged or even visually pleasing images. We develop a novel image-plane adaptive sampling and reconstruction method based on local regression theory. A novel local space estimation process is proposed for employing the local regression, by robustly addressing noisy high-dimensional features. Given the local regression on estimated local space, we provide a novel two-step optimization process for selecting bandwidths of features locally in a data-driven way. Local weighted regression is then applied using the computed bandwidths to produce a smooth image reconstruction with well-preserved details. We derive an error analysis to guide our adaptive sampling process at the local space. We demonstrate that our method produces more accurate and visually pleasing results over the state-of-the-art techniques across a wide range of rendering effects. Our method also allows users to employ an arbitrary set of features, including noisy features, and robustly computes a subset of them by ignoring noisy features and decorrelating them for higher quality.

We present a novel randomized path planner for rigid robots to efficiently handle various environments that have different characteristics. We first present a bridge line test that can identify narrow passage regions and then selectively performs an optimization-based retraction only at those regions. We also propose a noncolliding line test, which is a dual operator to the bridge line test, as a culling method to avoid generating samples near wide-open free spaces. These two line tests are performed with a small computational overhead. We have tested our method with different benchmarks that have varying amounts of narrow passages. Our method achieves up to several times improvements over prior RRT-based planners and consistently shows the best performance across all the tested benchmarks.

We propose several interactive global illumination techniques for a diverse set of massive models. We integrate these techniques within a progressive rendering framework that aims to achieve both a high rendering throughput and an interactive responsiveness. To achieve a high rendering throughput, we utilize heterogeneous computing resources consisting of CPU and GPU. To reduce expensive data transmission costs between CPU and GPU, we propose to use separate, decoupled data representations dedicated for each CPU and GPU. Our representations consist of geometric and volumetric parts, provide different levels of resolutions, and support progressive global illumination for massive models. We also propose a novel, augmented volumetric representation that provides additional geometric resolutions within our volumetric representation. In addition, we employ tile-based rendering and propose a tile ordering technique considering visual perception. We have tested our approach with a diverse set of large-scale models including CAD, scanned, simulation models that consist of more than 300 million triangles. By using our methods, we are able to achieve ray processing performances of 3 M~20 M rays per second, while limiting response time to users within 15~67 ms. We also allow dynamic modifications of light, and interactive setting of materials, while efficiently supporting novel view rendering.

In this paper we propose Pixel-based Random Parameter Filtering (P-RPF) for efficiently denoising images generated from complex illuminations with a high sample count. We design various operations of our method to have time complexity that is independent from the number of samples per pixel. We compute feature weights by measuring the functional relationships between MC inputs and output in a sample basis. To accelerate this sample-basis process we propose to use an up sampling method for feature weights. We have applied our method to a wide variety of models with different rendering effects. Our method runs significantly faster than the original RPF, while maintaining visually pleasing and numerically similar results. As a result, our method shows more visually pleasing and numerically better results than RPF in an equal-time comparison.

We present a fast, yet accurate k-nearest neighbor search algorithm for high-dimensional sampling-based motion planners. Our technique is built on top of Locality Sensitive Hashing (LSH), but is extended to support arbitrary distance metrics used for motion planning problems and adapt irregular distributions of samples generated in the configuration space. To enable such novel characteristics our method embeds samples generated in the configuration space into a simple l2norm space by using pivot points. We then implicitly define Voronoi regions and use local LSHs with varying quantization factors for those Voronoi regions. We have applied our method and other prior techniques to high-dimensional motion planning problems. Our method is able to show performance improvement by a factor of up to three times even with higher accuracy over prior, approximate nearest neighbor search techniques.

Abstract We propose an efficient and robust image‐space denoising method for noisy images generated by Monte Carlo ray tracing methods. Our method is based on two new concepts: virtual flash images and homogeneous pixels. Inspired by recent developments in flash photography, virtual flash images emulate photographs taken with a flash, to capture various features of rendered images without taking additional samples. Using a virtual flash image as an edge‐stopping function, our method can preserve image features that were not captured well only by existing edge‐stopping functions such as normals and depth values. While denoising each pixel, we consider only homogeneous pixels—pixels that are statistically equivalent to each other. This makes it possible to define a stochastic error bound of our method, and this bound goes to zero as the number of ray samples goes to infinity, irrespective of denoising parameters. To highlight the benefits of our method, we apply our method to two Monte Carlo ray tracing methods, photon mapping and path tracing, with various input scenes. We demonstrate that using virtual flash images and homogeneous pixels with a standard denoising method outperforms state‐of‐the‐art image‐space denoising methods.

We present a novel, linear programming (LP)-based scheduling algorithm that exploits heterogeneous multicore architectures such as CPUs and GPUs to accelerate a wide variety of proximity queries. To represent complicated performance relationships between heterogeneous architectures and different computations of proximity queries, we propose a simple, yet accurate model that measures the expected running time of these computations. Based on this model, we formulate an optimization problem that minimizes the largest time spent on computing resources, and propose a novel, iterative LP-based scheduling algorithm. Since our method is general, we are able to apply our method into various proximity queries used in five different applications that have different characteristics. Our method achieves an order of magnitude performance improvement by using four different GPUs and two hexa-core CPUs over using a hexa-core CPU only. Unlike prior scheduling methods, our method continually improves the performance, as we add more computing resources. Also, our method achieves much higher performance improvement compared with prior methods as heterogeneity of computing resources is increased. Moreover, for one of tested applications, our method achieves even higher performance than a prior parallel method optimized manually for the application. We also show that our method provides results that are close (e.g., 75 percent) to the performance provided by a conservative upper bound of the ideal throughput. These results demonstrate the efficiency and robustness of our algorithm that have not been achieved by prior methods. In addition, we integrate one of our contributions with a work stealing method. Our version of the work stealing method achieves 18 percent performance improvement on average over the original work stealing method. This result shows wide applicability of our approach.

Many 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.

We present a novel retraction-based planner, selective retraction-based RRT, for efficiently handling a wide variety of environments that have different characteristics. We first present a bridge line-test that can identify regions around narrow passages, and then perform an optimization-based retraction operation selectively only at those regions. We also propose a non-colliding line-test, a dual operator to the bridge line-test, as a culling method to avoid generating samples near wide-open free spaces and thus to generate more samples around narrow passages. These two tests are performed with a small computational overhead and are integrated with a retraction-based RRT. In order to demonstrate benefits of our method, we have tested our method with different benchmarks that have varying amounts of narrow passages. Our method achieves up to 21 times and 3.5 times performance improvements over a basic RRT and an optimization-based retraction RRT, respectively. Furthermore, our method consistently improves the performances of other tested methods across all the tested benchmarks that have or do not have narrow passages.

A mobile 3-D display processor with a subdivider is presented for higher visual quality on handhelds. By combining a subdivision technique with a 3-D display, the processor can support viewers see realistic smooth surfaces in the air. However, both the subdivision and the 3-D display processes require a high number of memory operations to mobile memory architecture. Therefore, we make efforts to save the bandwidth between the processor and off-chip memory. In the subdivider, we propose a recomputing based depth-first scheme that has much smaller working set than prior works. The proposed scheme achieves about 100:1 bandwidth reduction over the prior subdivision methods. Also the designed 3-D display engine reduces the bandwidth to 27% by reordering the operation sequence of the 3-D display process. This bandwidth saving translates into reductions of off-chip access energy and time. Consequently the overall bandwidth of both the subdivision and the 3-D display processes is affordable to a commercial mobile bus. In addition to saving bandwidth, our work provides enough visual quality and performance. Overall the 3-D display engine achieves 325 fps for 480×320 display resolution.

Solid state drives (SSDs) are emerging as an alternative storage medium to HDDs. SSDs have performance characteristics (e.g., fast random reads) that are very different from those of HDDs. Because of the high performance of SSDs, there are increasingly more research efforts to redesign the established techniques that are optimized for HDDs, to work well with SSDs. In this paper we focus on computing cache-coherent layouts of large-scale models for SSDs. It has been demonstrated that cache-oblivious layouts perform well for various applications running on HDDs. However, computing cache-oblivious layouts for large-models is known to be very expensive. Also these layouts cannot be maintained efficiently for dynamically changing models. Utilizing the properties of SSDs we propose an efficient layout computation method that produces a page-based cache-aware layout for SSDs. We show that the performance of our layout can be maintained under dynamic changes on the model and is similar to the cache-oblivious layout optimized for static models. We demonstrate the benefits of our method for large-scale walkthrough scene editing and rendering, and collision detection.

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. In addition, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra, hexahedra, triangular prisms, etc.). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

This course is intended for instructing students and practitioners on recent developments related to collision and proximity computations for interactive games and simulations.

Abstract Hierarchical culling is a key acceleration technique used to efficiently handle massive models for ray tracing, collision detection, etc. To support such hierarchical culling, bounding volume hierarchies (BVHs) combined with meshes are widely used. However, BVHs may require a very large amount of memory space, which can negate the benefits of using BVHs. To address this problem, we present a novel hierarchical‐culling oriented compact mesh representation, HCCMesh, which tightly integrates a mesh and a BVH together. As an in‐core representation of the HCCMesh, we propose an i‐HCCMesh representation that provides an efficient random hierarchical traversal and high culling efficiency with a small runtime decompression overhead. To further reduce the storage requirement, the in‐core representation is compressed to our out‐of‐core representation, o‐HCCMesh, by using a simple dictionary‐based compression method. At runtime, o‐HCCMeshes are fetched from an external drive and decompressed to the i‐HCCMeshes stored in main memory. The i‐HCCMesh and o‐HCCMesh show 3.6:1 and 10.4:1 compression ratios on average, compared to a naively compressed (e.g., quantized) mesh and BVH representation. We test the HCCMesh representations with ray tracing, collision detection, photon mapping, and non‐photorealistic rendering. Because of the reduced data access time, a smaller working set size, and a low runtime decompression overhead, we can handle models ten times larger in commodity hardware without the expensive disk I/O thrashing. When we avoid the disk I/O thrashing using our representation, we can improve the runtime performances by up to two orders of magnitude over using a naively compressed representation.

Abstract We propose a novel, multi‐resolution method to efficiently perform large‐scale cloth simulation. Our cloth simulation method is based on a triangle‐based energy model constructed from a cloth mesh. We identify that solutions of the linear system of cloth simulation are smooth in certain regions of the cloth mesh and solve the linear system on those regions in a reduced solution space. Then we reconstruct the original solutions by performing a simple interpolation from solutions computed in the reduced space. In order to identify regions where solutions are smooth, we propose simplification metrics that consider stretching, shear, and bending forces, as well as geometric collisions. Our multi‐resolution method can be applied to many existing cloth simulation methods, since our method works on a general linear system. In order to demonstrate benefits of our method, we apply our method into four large‐scale cloth benchmarks that consist of tens or hundreds of thousands of triangles. Because of the reduced computations, we achieve a performance improvement by a factor of up to one order of magnitude, with a little loss of simulation quality.

We present a cache-oblivious ray reordering method for ray tracing. Many global illumination methods such as path tracing and photon mapping use ray tracing and generate lots of rays to simulate various realistic visual effects. However, these rays tend to be very incoherent and show lower cache utilizations during ray tracing of models. In order to address this problem and improve the ray coherence, we propose a novelHit Point Heuristic(HPH) to compute a coherent ordering of rays. The HPH uses the hit points between rays and the scene as a ray reordering measure. We reorder rays by using a space-filling curve based on their hit points. Since a hit point of a ray is available only after performing the ray intersection test with the scene, we compute an approximate hit point for the ray by performing an intersection test between the ray and simplified representations of the original models. Our method is a highly modular approach, since our reordering method is decoupled from other components of common ray tracing systems. We apply our method to photon mapping and path tracing and achieve more than an order of magnitude performance improvement for massive models that cannot fit into main memory, compared to rendering without reordering rays. Also, our method shows a performance improvement even for ray tracing small models that can fit into main memory. This performance improvement for small and massive models is caused by reducing cache misses occurring between different memory levels including the L1/L2 caches, main memory, and disk. This result demonstrates the cache-oblivious nature of our method, which works for various kinds of cache parameters. Because of the cache-obliviousness and the high modularity, our method can be widely applied to many existing ray tracing systems and show performance improvements with various models and machines that have different cache parameters.

We present a novel compressed bounding volume hierarchy (BVH) representation, random-accessible compressed bounding volume hierarchies (RACBVHs), for various applications requiring random access on BVHs of massive models. Our RACBVH representation is compact and transparently supports random access on the compressed BVHs without decompressing the whole BVH. To support random access on our compressed BVHs, we decompose a BVH into a set of clusters. Each cluster contains consecutive bounding volume (BV) nodes in the original layout of the BVH. Also, each cluster is compressed separately from other clusters and serves as an access point to the RACBVH representation. We provide the general BVH access API to transparently access our RACBVH representation. At runtime, our decompression framework is guaranteed to provide correct BV nodes without decompressing the whole BVH. Also, our method is extended to support parallel random access that can utilize the multicore CPU architecture. Our method can achieve up to a 12:1 compression ratio, and more importantly, can decompress 4.2 M BV nodes ({=}135 {\rm MB}) per second by using a single CPU-core. To highlight the benefits of our approach, we apply our method to two different applications: ray tracing and collision detection. We can improve the runtime performance by more than a factor of 4 as compared to using the uncompressed original data. This improvement is a result of the fast decompression performance and reduced data access time by selectively fetching and decompressing small regions of the compressed BVHs requested by applications.

Given a data layout of a large walkthrough scene, we present a novel and simple spatial hierarchy on the disk-pages of the layout that has notable advantages over a conventional spatial hierarchy on the scene geometry. Assume that each disk-page consists of a set of triangles whose bounding boxes are computed. A spatial hierarchy of the walkthrough space is constructed, not with the given scene, but with the bounding boxes of disk-pages. The leaf nodes of the spatial-hierarchy refer directly to the page numbers of the pages of the bounding box it contains. We call this hierarchy on the pages as the disk-page hierarchy. We also propose a self-contained disk-page format that would suit this data structure well. Further, we present a new cache-oblivious graph-based data layout algorithm called the 2-factor layout that would preserve the proximity and orientation properties of the primitives in the layout. Walkthrough experiments have been conducted on a city scene consisting of over 110M triangles. Our system renders this scene on a laptop within a one pixel projection error at over 20 fps with simple texture substitution based simplification of distant objects, and with no explicit data/cache management.

Abstract We 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 self‐collision 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 present an interactive algorithm for continuous collision detection between deformable models. We introduce multiple techniques to improve the culling efficiency and the overall performance of continuous collision detection. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh as part of self-collision tests. Second, we introduce the concept of "procedural representative triangles" to remove all redundant elementary tests between nonadjacent triangles. Finally, we exploit the mesh connectivity and introduce the concept of "orphan sets" to eliminate redundant elementary tests between adjacent triangle primitives. In practice, we can reduce the number of elementary tests by two orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior collision detection algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations, and breaking objects.

This course instructs students in the software and hardware strategies needed for real-time visualization and interaction with massive models. Seven international researchers and practitioners are the instructors. The general form of the course will be lecture with live demos.

Interactive visualization of massive models still remains a challenging problem. This is mainly due to a combination of ever increasing model complexity with the current hardware design trend that leads to a widening gap between slow data access speed and fast data processing speed. We argue that developing efficient data access and data management techniques is key in solving the problem of interactive visualization of massive models. Particularly, we discuss visibility culling, simplification, cache-coherent layouts, and data compression techniques as efficient data management techniques that enable interactive visualization of massive models.

We present an interactive algorithm for continuous collision detection between deformable models. We introduce two techniques to improve the culling efficiency and reduce the number of potentially colliding triangle candidate pairs. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh from self-collision tests. Second, we exploit the mesh connectivity and introduce the concept of orphan sets to eliminate almost all redundant elementary tests between adjacent triangles. In particular, we can reduce the number of elementary tests by many orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations and breaking objects.

Abstract We present a novel representation and algorithm, ReduceM, for memory efficient ray tracing of large scenes. ReduceM exploits the connectivity between triangles in a mesh and decomposes the model into triangle strips. We also describe a new stripification algorithm, Strip‐RT, that can generate long strips with high spatial coherence. Our approach uses a two‐level traversal algorithm for ray‐primitive intersection. In practice, ReduceM can significantly reduce the storage overhead and ray trace massive models with hundreds of millions of triangles at interactive rates on desktop PCs with 4‐8GB of main memory.

With the exponential growth in size of geometric data, it is becoming increasingly important to make effective use of multilevel caches, limited disk storage, and bandwidth. As a result, recent work in the visualization community has focused either on designing sequential access compression schemes or on producing cache-coherent layouts of (uncompressed) meshes for random access. Unfortunately combining these two strategies is challenging as they fundamentally assume conflicting modes of data access. In this paper, we propose a novel order-preserving compression method that supports transparent random access to compressed triangle meshes. Our decompression method selectively fetches from disk, decodes, and caches in memory requested parts of a mesh. We also provide a general mesh access API for seamless mesh traversal and incidence queries. While the method imposes no particular mesh layout, it is especially suitable for cache-oblivious layouts, which minimize the number of decompression I/O requests and provide high cache utilization during access to decompressed, in-memory portions of the mesh. Moreover, the transparency of our scheme enables improved performance without the need for application code changes. We achieve compression rates on the order of 20:1 and significantly improved I/O performance due to reduced data transfer. To demonstrate the benefits of our method, we implement two common applications as benchmarks. By using cache-oblivious layouts for the input models, we observe 2?6 times overall speedup compared to using uncompressed meshes.

Abstract We present a novel algorithm to compute cache‐efficient layouts of bounding volume hierarchies (BVHs) of polygonal models. Our approach does not make any assumptions about the cache parameters or block sizes of the memory hierarchy. We introduce a new probabilistic model to predict the runtime access patterns of a BVH. Our layout computation algorithm utilizes parent‐child and spatial localities between the accessed nodes to reduce both the number of cache misses and the size of the working set. Our algorithm also works well for spatial partitioning hierarchies including kd‐trees. We use our algorithm to compute layouts of BVHs and spatial partitioning hierarchies of large models composed of millions of triangles. We compare our cache‐efficient layouts with other layouts in the context of collision detection and ray tracing. In our benchmarks, our layouts consistently show better performance over other layouts and improve the performance of these applications by 26%–300%without any modification of the underlying algorithms or runtime applications. Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Hierarchy and Geometric Transformations

Current computer architectures employ caching to improve the performance of a wide variety of applications. One of the main characteristics of such cache schemes is the use of block fetching whenever an uncached data element is accessed. To maximize the benefit of the block fetching mechanism, we present novel cache-aware and cache-oblivious layouts of surface and volume meshes that improve the performance of interactive visualization and geometric processing algorithms. Based on a general I/O model, we derive new cache-aware and cache-oblivious metrics that have high correlations with the number of cache misses when accessing a mesh. In addition to guiding the layout process, our metrics can be used to quantify the quality of a layout, e.g. for comparing different layouts of the same mesh and for determining whether a given layout is amenable to significant improvement. We show that layouts of unstructured meshes optimized for our metrics result in improvements over conventional layouts in the performance of visualization applications such as isosurface extraction and view-dependent rendering. Moreover, we improve upon recent cache-oblivious mesh layouts in terms of performance, applicability, and accuracy.

We present a novel method for computing cache-oblivious layouts of large meshes that improve the performance of interactive visualization and geometric processing algorithms. Given that the mesh is accessed in a reasonably coherent manner, we assume no particular data access patterns or cache parameters of the memory hierarchy involved in the computation. Furthermore, our formulation extends directly to computing layouts of multi-resolution and bounding volume hierarchies of large meshes.We develop a simple and practical cache-oblivious metric for estimating cache misses. Computing a coherent mesh layout is reduced to a combinatorial optimization problem. We designed and implemented an out-of-core multilevel minimization algorithm and tested its performance on unstructured meshes composed of tens to hundreds of millions of triangles. Our layouts can significantly reduce the number of cache misses. We have observed 2--20 times speedups in view-dependent rendering, collision detection, and isocontour extraction without any modification of the algorithms or runtime applications.

We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We introduce novel cluster dependencies in the preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for LOD selection, occlusion culling, and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and avoid stalls. The CHPM reduces the refinement cost of view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundred million triangles at 15-35 frames per second with little loss in image quality.

We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We make use of novel cluster dependencies in preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for occlusion culling and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and to avoid stalls. The CHPM reduces the refinement cost for view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundreds of millions of triangles at 10-35 frames per second with little loss in image quality.

We present occlusion-switches for interactive visibility culling in complex 3D environments. An occlusion-switch consists of two GPUs (graphics processing units) and each GPU is used to either compute an occlusion representation or cull away primitives not visible from the current viewpoint. Moreover, we switch the roles of each GPU between successive frames. The visible primitives are rendered in parallel on a third GPU. We utilize frame-to-frame coherence to lower the communication overhead between different GPUs and improve the overall performance. The overall visibility culling algorithm is conservative up to image-space precision. This algorithm has been combined with levels-of-detail and implemented on three networked PCs, each consisting of a single GPU. We highlight its performance on complex environments composed of tens of millions of triangles. In practice, it is able to render these environments at interactive rates with little loss in image quality.

This paper presents an algorithm combining view-dependent rendering and conservative occlusion culling for interactive display of complex environments. A vertex hierarchy of the entire scene is decomposed into a cluster hierarchy through a novel clustering and partitioning algorithm. The cluster hierarchy is then used for view-frustum and occlusion culling. Using hardware accelerated occlusion queries and frame-to-frame coherence, a potentially visible set of clusters is computed. An active vertex front and face list is computed from the visible clusters and rendered using vertex arrays. The integrated algorithm has been implemented on a Pentium IV PC with a NVIDIA GeForce 4 graphics card and applied in two complex environments composed of millions of triangles. The resulting system can render these environments at interactive rates with little loss in image quality and minimal popping artifacts.

We present a new algorithm for interactive generation of hard-edged, umbral shadows in complex environments with a moving light source. Our algorithm uses a hybrid approach that combines the image quality of object-precision methods with the efficiencies of image-precision techniques. We present an algorithm for computing a compact potentially visible set (PVS) using levels-of-detail (LODs) and visibility culling. We use the PVSs computed from both the eye and the light in a novel cross-culling algorithm that identifies a reduced set of potential shadow-casters and shadow-receivers. Finally, we use a combination of shadow-polygons and shadow maps to generate shadows. We also present techniques for LOD-selection to minimize possible artifacts arising from the use of LODs. Our algorithm can generate sharp shadow edges and reduces the aliasing in pure shadow map approaches. We have implemented the algorithm on a three-PC system with NVIDIA GeForce 4 cards. We achieve 7--25 frames per second in three complex environments composed of millions of triangles.