ImageMesh : A Convex Hull based 3D Reconstruction Method

Andrew R. Garcia

garcia.gtr@gmail.com

Abstract

ImageMesh is a method available in versions \(\ge\) 2.0 of the voxelmap Python library that generates 3D models from images using Convex Hull in 3-D to enclose external points obtained from a series of partitioned point clouds. These point clouds are generated by assigning the relative pixel intensities from the partitioned images as the depth dimension to the points. In this paper, we describe the limitations of the original ImageMesh method and the quick solution we have implemented to address them. Additionally, we introduce MeshView, a Python visualization tool developed in tandem with ImageMesh that provides a convenient way to visualize the 3D models generated by ImageMesh. Finally, we discuss the GPU memory space complexity of both methods.

Introduction

An image of a crochet donut

3-D reconstruction of donut image to voxel cloud done by transforming relative pixel intensities to 3-D depth with the ImageMap method.

3-D reconstruction of donut image with the ImageMesh method.

ImageMesh is a 3D reconstruction method. It utilizes Convex Hull in 3-D to enclose external points obtained from a series of partitioned point clouds, which are generated by assigning the relative pixel intensities from the partitioned images as the depth dimension to the point clouds. ImageMesh and ImageMap methods utilize the CCIR 601 luma protocol to transform input images into 2-dimensional “intensity” matrices that represent relative grayscale values. These intensity values are then mapped to the depth dimension to form third-order arrays. ImageMesh generates 3-D model .obj files from images by drawing the smallest collection of triangular polygons that satisfies this rule in three-dimensional space. In simpler terms, it’s like placing a fabric over a 3-D object. However, it is important to note that a single convex hull operation may fail to draw a structure with holes or bumps, which are essentially 2-D local extrema.

To address this limitation, we have implemented a quick solution that involves partitioning the input image into multiple segments and placing 3-D convex hull “sheets” on each segment to perform triangulation. Figure 3 shows how this partitioning can process more local extrema with the 3-D Convex Hull method and create more realistic 3-D reconstructions.

Schematic representation of the performance of ImageMesh with more segments.

In the Figure 4, blurring is performed to create a more realistic 3-D texture with the ImageMesh method. Blurring an image can be thought of as a process of smoothing out the details in the image by reducing the contrast between adjacent pixels. This results in a 3-D effect where the image appears to have a more uniform and continuous surface. Instead of sharp edges and abrupt changes in color or texture, blurred images have a softer and more gradual transition between different parts of the image.

Blurring of former image to create a smoother 3-D texture with ImageMesh.

Complementing ImageMesh is MeshView, a Python visualization tool developed in tandem to provide a convenient way to visualize the 3D models generated by ImageMesh. MeshView is capable of loading the .obj files generated by ImageMesh and rendering them in a PyVista VTK window, allowing for interactive 3D visualization of the models

The graphical effect of increasing the number of 3-D Convex Hull (CH) sectors in each column. The left column shows 1 CH sector, the middle column shows 4 CH sectors, and the right column shows 16 CH sectors.

Time Complexity

When using a voxel-based approach for 3-D reconstruction from an image, that is, converting the 2-D image to a voxel cloud, the time complexity for converting the 2-D image to a voxel cloud is \(\mathcal{O}(w h d)\), where \(w\) and \(h\) are the width and height of the image, and \(d\) is the depth of the voxel cloud. In comparison, the ImageMesh method for 3-D reconstruction involves 3 main steps which have its own computational complexity. In the next paragraphs we elaborate on the steps for this method and their associated time complexities.

In the first step, the image is sliced into equally-sized sectors: \(\mathcal{O}(w h)\), where \(w\) is the width of the image and \(h\) is its height. After this, each of the 2-D sectors are mapped to 3-D point clouds, with a time complexity \(\mathcal{O}(w h)\), where w and h are the width and height of the image.

3-D Convex Hull is then performed on each of these point clouds with \(\mathcal{O}(n \log n)\), where \(n\) is the number of points in each 3-D point cloud. For this last step, we use the scipy.spatial.ConvexHull algorithm for computing the convex hull of the 3-D point clouds. Th algorithm uses a divide-and-conquer approach based on the QuickHull algorithm, which has an average case time complexity of \(\mathcal{O}(n \log n)\). This makes the scipy.spatial.ConvexHull algorithm efficient for computing the convex hull of a 3-D point cloud, especially for larger datasets. However, the time complexity for the worst-case scenario of QuickHull is \(\mathcal{O}(n^2)\), which means that in some cases, the scipy.spatial.ConvexHull algorithm may take longer to run.

Therefore, the overall time complexity of ImageMesh can be estimated as \(\mathcal{O}(w h n \log n)\), where \(w\) and \(h\) are the width and height of the image, and \(n\) is the number of points in each 3-D point cloud.

When considering the time complexity of the two methods, it is clear that ImageMesh, a method which generates a single mesh with multiple steps, has a higher computational cost than the voxel-based approac, a method which generates multiple voxel meshes. However, it is important to note that the graphical manipulation of the single mesh is superior to the latter method. This is because a single mesh can update all its defined vertices more efficiently than updating multiple voxel meshes.

As a result, ImageMesh is more suitable for applications that require real-time graphical manipulation or rendering, where the speed of the graphics processing is crucial. On the other hand, the voxel mesh method may be more appropriate for applications where the accuracy of the reconstruction is more important than the graphical performance, and where the computational cost can be distributed over multiple processors or computer nodes.

Conclusion

ImageMesh, coupled with MeshView, provides a powerful and efficient 3D reconstruction method. By implementing the Convex Hull-based method with partitioning, we have addressed the limitation of a single convex hull operation and increased the resolution of the reconstructed 3D models. With the reduction in GPU space complexity, the new method has become more practical for real-world applications.