Shape from silhouette using Dempster-Shafer theory

This work proposes a novel shape from silhouette (SfS) algorithm using the Dempster-Shafer (DS) theory for dealing with inconsistent silhouettes. Standard SfS methods makes assumptions about consistency in the silhouettes employed. However, total consistency hardly ever happens in realistic scenarios because of inaccuracies in the background subtraction or occlusions, thus leading to poor reconstruction outside of controlled environments.Our method classify voxels using the DS theory instead of the traditional intersection of all visual cones. Sensors reliability is modelled taking into account the positional relationships between camera pairs and voxels. This information is employed to determine the degree in which a voxel belongs to a foreground object. Finally, evidences collected from all sensors are fused to choose the best hypothesis that determines the voxel state.Experiments performed with synthetic and real data show that our proposal outperforms the traditional SfS method and other techniques specifically designed to deal with inconsistencies. In addition, our method includes a parameter for adjusting the precision of the reconstructions so that it could be adapted to the application requirements.     

Interactive Indirect Illumination Using Voxel Cone Tracing

Indirect illumination is an important element for realistic image synthesis, but its computation is expensive and highly dependent on the complexity of the scene and of the BRDF of the involved surfaces. While off‐line computation and pre‐baking can be acceptable for some cases, many applications (games, simulators, etc.) require real‐time or interactive approaches to evaluate indirect illumination. We present a novel algorithm to compute indirect lighting in real‐time that avoids costly precomputation steps and is not restricted to low‐frequency illumination. It is based on a hierarchical voxel octree representation generated and updated on the fly from a regular scene mesh coupled with an approximate voxel cone tracing that allows for a fast estimation of the visibility and incoming energy. Our approach can manage two light bounces for both Lambertian and glossy materials at interactive framerates (25–70FPS). It exhibits an almost scene‐independent performance and can handle complex scenes with dynamic content thanks to an interactive octree‐voxelization scheme. In addition, we demonstrate that our voxel cone tracing can be used to efficiently estimate Ambient Occlusion.     

Shape from silhouettes based on a centripetal pentahedron model

In this paper we present a novel volumetric shape from silhouette (SfS) algorithm based on a centripetal pentahedron model (pent-model). The pent-model is an object-centered volumetric model composed of a set of pentahedrons cut from the centripetal triangular pyramids, which together partition the 3D space. The SfS algorithm first computes the pyramids by constructing a geodesic sphere. These pyramids are then projected onto the image planes of all cameras. The intersections between the projected pyramids and the silhouettes, which are a set of hexagons, are computed. This process can be performed very efficiently with pre-computed polar silhouette graphs (PSGs) and reduced PSGs. The hexagons are then back-projected into the 3D space, where the intersections are calculated and the pent-model is derived. After that, a mesh surface model can be extracted by marching pentahedrons. Our algorithm has the combined advantages of robustness, speediness and preciseness. Experimental results based on both synthetic images and real photos are presented.     

Discrete Ray-Tracing of Huge Voxel Spaces

The quality of images produced by Discrete Ray-Tracing voxel spaces is highly dependent on 3d grid resolution. The huge amount of memory needed to store such grids often discards discrete Ray-Tracing as a practical visualization algorithm. The use of an octree can drastically change this when most of space is empty, as such is the case in most scenes. Although the memory problem can be bypassed using the octree, the performance problem still remains. A known fact is that the performance of discrete traversal is optimal for quite low resolutions. This problem can be easily solved by dividing the task in two steps, working in two low resolutions instead of just one high resolution, thus taking advantage of optimal times in both steps. This is possible thanks to the octree property of representing the same scene in several different resolutions. This article presents a two step Discrete Ray-Tracing method using an octree and shows, by comparing it with the single step version, that a substantial gain in performance is achieved.     

Exhaustive and heuristic search approaches for learning a software defect prediction model

In this paper, we propose a software defect prediction model learning problem (SDPMLP) where a classification model selects appropriate relevant inputs, from a set of all available inputs, and learns the classification function. We show that the SDPMLP is a combinatorial optimization problem with factorial complexity, and propose two hybrid exhaustive search and probabilistic neural network (PNN), and simulated annealing (SA) and PNN procedures to solve it. For small size SDPMLP, exhaustive search PNN works well and provides an (all) optimal solution(s). However, for large size SDPMLP, the use of exhaustive search PNN approach is not pragmatic and only the SA–PNN allows us to solve the SDPMLP in a practical time limit. We compare the performance of our hybrid approaches with traditional classification algorithms and find that our hybrid approaches perform better than traditional classification algorithms.     

基于八叉树空间分割的三维点云模型密写

针对三维点云模型的信息隐藏,提出一种基于八叉树空间分割的空域密写算法。对经过主成分分析后的三维点云模型建立包围盒,利用八叉树空间分割得到小体元并记录分割过程,通过顶点位移将信息嵌入到小体元内的不同空间位置。实验结果表明,该算法在提取信息时不需要原始模型数据,具有嵌入量高、失真度低的特点,能够抵抗旋转、平移、均匀缩放和顶点重排序攻击,适合于任意网格的三维模型信息隐藏。     

A semi-supervised approach to space carving

In this paper, we present a semi-supervised approach to space carving by casting the recovery of volumetric data from multiple views into an evidence combining setting. The method presented here is statistical in nature and employs, as a starting point, a manually obtained contour. By making use of this user-provided information, we obtain probabilistic silhouettes of all successive images. These silhouettes provide a prior distribution that is then used to compute the probability of a voxel being carved. This evidence combining setting allows us to make use of background pixel information. As a result, our method combines the advantages of shape-from-silhouette techniques and statistical space carving approaches. For the carving process, we propose a new voxelated space. The proposed space is a projective one that provides a colour mapping for the object voxels which is consistent in terms of pixel coverage with their projection onto the image planes for the imagery under consideration. We provide quantitative results and illustrate the utility of the method on real-world imagery.     

Discrete shading of three-dimensional objects from medial axis transform

In this paper, we present a discrete shading technique using medial axis transform (MAT) of 3D binary image data based on digital generalized octagonal distances. Our method is computationally attractive as it does not require the explicit computation of surface normals. We have compared our results with images rendered from voxel and octree representations while using analytical surface rendered images as bench marks. The quality of rendering by our method is certainly superior to those obtained from voxel and octree representations.     

Combining Shape from Shading and Stereo: A Joint Variational Method for Estimating Depth,Illumination and Albedo

Shape from shading (SfS) and stereo are two fundamentally different strategies for image-based 3-D reconstruction. While approaches for SfS infer the depth solely from pixel intensities, methods for stereo are based on a matching process that establishes correspondences across images. This difference in approaching the reconstruction problem yields complementary advantages that are worthwhile being combined. So far, however, most “joint” approaches are based on an initial stereo mesh that is subsequently refined using shading information. In this paper we follow a completely different approach. We propose a joint variational method that combines both cues within a single minimisation framework. To this end, we fuse a Lambertian SfS approach with a robust stereo model and supplement the resulting energy functional with a detail-preserving anisotropic second-order smoothness term. Moreover, we extend the resulting model in such a way that it jointly estimates depth, albedo and illumination. This in turn makes the approach applicable to objects with non-uniform albedo as well as to scenes with unknown illumination. Experiments for synthetic and real-world images demonstrate the benefits of our combined approach: They not only show that our method is capable of generating very detailed reconstructions, but also that joint approaches are feasible in practice.     

Path planning in complex 3D environments using a probabilistic roadmap method

This paper presents a 3D path planning algorithm for an unmanned aerial vehicle （UAV） in complex environments. In this algorithm, the environments are divided into voxels by octree algorithm. In order to satisfy the safety requirement of the UAV, free space is represented by free voxels, which have enough space margin for the UAV to pass through. A bounding box array is created in the whole 3D space to evaluate the free voxel connectivity. The probabilistic roadmap method （PRM） is improved by random sampling in the bounding box array to ensure a more efficient distribution of roadmap nodes in 3D space. According to the connectivity evaluation, the roadmap is used to plan a feasible path by using A＊ algorithm. Experimental results indicate that the proposed algorithm is valid in complex 3D environments.     

Out‐of‐Core Construction of Sparse Voxel Octrees

Voxel‐based rendering has recently received significant attention due to its potential in the context of efficiently rendering massively large and highly detailed scenes. Unfortunately, few scenes are available in the form of sparse voxel octrees. In this paper, we present an out‐of‐core algorithm for constructing a sparse voxel octree from a triangle mesh. Our algorithm allows the input triangle mesh, the output sparse voxel octree and, most importantly, the intermediate high‐resolution 3D voxel grid, to be larger than available memory. We demonstrate that our out‐of‐core algorithm can construct sparse voxel octrees from triangle meshes using only a fraction of the memory required by an in‐core algorithm in roughly the same time, and that our out‐of‐core algorithm can also handle extremely large triangle meshes.     

Shape from incomplete silhouettes based on the reprojection error

Traditional shape from silhouette methods compute the 3D shape as the intersection of the back-projected silhouettes in the 3D space, the so called visual hull. However, silhouettes that have been obtained with background subtraction techniques often present miss-detection errors (produced by false negatives or occlusions) which produce incomplete 3D shapes. Our approach deals with miss-detections, false alarms, and noise in the silhouettes. We recover the voxel occupancy which describes the 3D shape by minimizing an energy based on an approximation of the error between the shape 2D projections and the silhouettes. Two variants of the projection – and as a result the energy – as a function of the voxel occupancy are proposed. One of these variants outperforms the other. The energy also includes a sparsity measure, a regularization term, and takes into account the visibility of the voxels in each view in order to handle self-occlusions.     

Fast Gradient-Domain Video Processing Using Octree Data Structure

We present a fast gradient domain video processing using hierarchical data structure which subdivides the processing region into an octree data. It is hard to handle large video processing by solving a 3D Poisson equation, as the derived linear system is usually large. Solving the system requires large memory space and long computational time, which makes it intractable on a standard computer. To address the scalability problem, rather than processing the video in the gradient-domain pixel by pixel, we perform the video processing in a reduced space using octree data structure, which significantly reduces the variables. We show that the proposed octree approach is efficient in both seamless and mixing gradient-domain video processing. The method enables to perform video processing in greatly reduced computational time and memory space, while receiving visually identical results with that computed from the full solution.     

An intelligent system approach to higher-dimensional classification of volume data

In volume data visualization, the classification step is used to determine voxel visibility and is usually carried out through the interactive editing of a transfer function that defines a mapping between voxel value and color/opacity. This approach is limited by the difficulties in working effectively in the transfer function space beyond two dimensions. We present a new approach to the volume classification problem which couples machine learning and a painting metaphor to allow more sophisticated classification in an intuitive manner. The user works in the volume data space by directly painting on sample slices of the volume and the painted voxels are used in an iterative training process. The trained system can then classify the entire volume. Both classification and rendering can be hardware accelerated, providing immediate visual feedback as painting progresses. Such an intelligent system approach enables the user to perform classification in a much higher dimensional space without explicitly specifying the mapping for every dimension used. Furthermore, the trained system for one data set may be reused to classify other data sets with similar characteristics.     

A solution to illumination direction estimation of a shaded image: Genetic algorithm

In oblique shape from shading (SfS), the illumination direction is essential for recovering the 3D surface of a shaded image. On the other hand, fast marching methods (FMM) are SfS algorithms that use the mechanism of wave propagation to reconstruct the surface. In this paper, the estimation of illumination direction is addressed and we model it as an optimization problem. The idea is to minimize the inconsistency of wave propagation of FMM during the reconstruction. As the consistency of wave propagation is a multi-modal function of illumination direction, genetic algorithm (GA) is utilized. The proposed algorithm is examined on four synthetic models and a real world object. The experimental results show that the proposed algorithm is superior to benchmark methods.     

点云数据在深度学习中表示方法的研究

为了实现在深度学习中能够端到端表示点云模型,提出基于八叉树和K-D树（OctKD）的点云数据表示方法。该方法将无组织的点云转换为体素空间,在体素空间对三维模型进行八叉树剖分,改进了八叉树编码方式;构建节点间的邻接关系,在GPU端并行构建八叉树;为了克服八叉树编码检索效率低的问题,采用三维K-D树索引单个三维空间点。实验结果表明该方法能够真实反映模型本身的细节特征,提高了点云模型的构造时间和检索效率。这种新的数据结构实现将点云转换为卷积神经网络可以接收的数据形式。     

Adaptive cell division for ray tracing

In ray tracing the two most commonly used data structures are the octree and uniform cell division. The octree structure allows efficient adaptive subdivision of space, while taking care of the spatial coherence of the objects in it; however, the tree structure locating the next node in the path of a ray is complex and time consuming. The cell structure, on the other hand, can be stored in a three-dimensional array, and each cell can be efficiently accessed by specifying three indices. However, such a uniform cell division does not take care of object coherence. The proposed data structure combines the positive features of the above data structures while minimising their disadvantages. The entire object space is implicitly assumed to be a three-dimensional grid of cells. Initially, the entire object space is a single voxel which later undergoes “adaptive cell division.” But, unlike in the octree structure, where each voxel is divided exactly at the middle of each dimension, in adaptive cell division, each voxel is divided at the nearest cell boundary. The result is that each voxel contains an integral number of cells along each axis. Corresponding to the implicit cell division we maintain a three-dimensional array, with each array element containing the voxel number which is used to index into the voxel array. The voxel array is used to store information about the structure of each voxel, in particular, the objects in each voxel. While a ray moves from one voxel to another we always keep track of the cell through which the ray is currently passing. Since only arrays are involved in accessing the next voxel in the path of the ray, the operation is very efficient.     

Shape-from-Shading Under Perspective Projection

Shape-from-Shading (SfS) is a fundamental problem in Computer Vision. A very common assumption in this field is that image projection is orthographic. This paper re-examines the basis of SfS, the image irradiance equation, under a perspective projection assumption. The resultant equation does not depend on the depth function directly, but rather, on its natural logarithm. As such, it is invariant to scale changes of the depth function. A reconstruction method based on the perspective formula is then suggested; it is a modification of the Fast Marching method of Kimmel and Sethian. Following that, a comparison of the orthographic Fast Marching, perspective Fast Marching and the perspective algorithm of Prados and Faugeras on synthetic images is presented. The two perspective methods show better reconstruction results than the orthographic. The algorithm of Prados and Faugeras equates with the perspective Fast Marching. Following that, a comparison of the orthographic and perspective versions of the Fast Marching method on endoscopic images is introduced. The perspective algorithm outperformed the orthographic one. These findings suggest that the more realistic set of assumptions of perspective SfS improves reconstruction significantly with respect to orthographic SfS. The findings also provide evidence that perspective SfS can be used for real-life applications in fields such as endoscopy.This research has been supported in part by Tel-Aviv University fund, the Adams Super-Center for Brain Studies, the Israeli Ministry of Science, the ISF Center for Excellence in Applied Geometry, the Minerva Center for geometry, and the A.M.N. fund.     

Anytime discovery of a diverse set of patterns with Monte Carlo tree search

The discovery of patterns that accurately discriminate one class label from another remains a challenging data mining task. Subgroup discovery (SD) is one of the frameworks that enables to elicit such interesting patterns from labeled data. A question remains fairly open: How to select an accurate heuristic search technique when exhaustive enumeration of the pattern space is infeasible? Existing approaches make use of beam-search, sampling, and genetic algorithms for discovering a pattern set that is non-redundant and of high quality w.r.t. a pattern quality measure. We argue that such approaches produce pattern sets that lack of diversity: Only few patterns of high quality, and different enough, are discovered. Our main contribution is then to formally define pattern mining as a game and to solve it with Monte Carlo tree search (MCTS). It can be seen as an exhaustive search guided by random simulations which can be stopped early (limited budget) by virtue of its best-first search property. We show through a comprehensive set of experiments how MCTS enables the anytime discovery of a diverse pattern set of high quality. It outperforms other approaches when dealing with a large pattern search space and for different quality measures. Thanks to its genericity, our MCTS approach can be used for SD but also for many other pattern mining tasks.     

基于动态极大度的极小碰集求解方法

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.