EG 3DOR 2012

The fifth Eurographics workshop on 3D Object Retrieval (EG3DOR'12) will be take place on May 13, 2012 in Caliari (Italy), as a co-event of the 33rd Annual Conference of the European Association for Computer Graphics (Eurographics 2012). I am program chair of this event, together with Alexander Bronstein from Tel-Aviv University. Researchers and practitioners are invited to submit original and unpublished research and practical applications in all areas of 3D Object Retrieval.

3DORuS web page published

I am the principal investigator of the 3DORuS: 3D Object Retrieval using Skecthes project, funded by Portuguese Science and Technology Foundation (FCT). This project focus on interfaces for 3D object retrieval and started in March 2010. After a few delays, we made now available online the 3DORuS project webpage. Feel free to visit it and give us some feedback.

ACM MM 3DOR 2010

Last week I attended the International Workshop on 3D Object Retrieval, a co-event of ACM Multimedia 2010. This workshop brought together researchers from different fields, ranging from computer vision, computer graphics, machine learning and human-computer interaction, whose works relates to 3D object retrieval.

Although all work presented in this forum was relevant to my research, I was particularly interested in the paper "Local Visual Patch for 3D Shape Retrieval" by Mohamed Daoudi et.al. and the poster "A Benchmark for Best View Selection of 3D Objects" by Afzal Godil et.al.

Spherical Harmonics Visual Representation

Although I had developed most of the code in the last year, just today I assembled all together in order to create a prototype that produces visual representations of spherical harmonics (SHA) signatures. The SHaVisRep prototype receives as input the binary signature created by the the executable for computing SHA representations provided by Kazhdan and produce a visual representation for this descriptor. This visual representation can be a 3D column chart or a 2D line chart in VRML or BMP format, respectively. The Win32 version of the prototype is avaliable for download [ZIP 110KB].

Ant 3D model
___

Shperical harmonics of ant 3D model, represented as a 3D column chart
___

Shperical harmonics of ant 3D model, represented as a 2D line chart

The 3D shape thesaurus

Those who have been following my PhD work know that one of the main contributions of my research is the development of a 3D shape thesaurus. However, despite some previous efforts, I had never been able to clearly illustrate this concept in a diagram. Until yesterday. Thanks to a welcomed inspiration I created a very good (i.m.h.o.) diagram to represent a 3D shape thesaurus. Of course it is almost meaningless without proper context (you will find it in my thesis) , but I'm so keen about this diagram that I can't resist to publish it right now.

Schematic representation of a 3D shape thesaurus

Clustering Reader

As part of my PhD research I needed to cluster the the shape segments according to its spherical harmonics signature. After accomplishing this step I want to easily "see" the results and create a directory tree filled according to a given partition (I compute four different ones). To that end, I developed "Clustering Reader" a simple Windows applications that reads the XML file produced by the clustrering algorithm, shows the computed partitions and distributes the corresponding segments (VRML files) by the corresponding directories.

Screenshot of Clustering Reader

Disjoint component identification

Within my PhD work I developed a small prototype that identifies disjoint components on 3D meshes. The "Disjoint Component Detector" takes as input an OFF file and can produce three distinct outputs. It can create a VRML file with the model colorized according to the detected disjoint components. It can create a set of OFF files, containing each one of them a single component. Or it can write a text file describing the disjoint components detection results. If interested in try it, you can download the current stable version of the prototype [ZIP 143KB].

Ant model from PSB with disjoint components identified.

This simple prototype provides a straightfoward method to identify segments in some models from the PSB collection, since they are already coded with disjoint segments.

Identifying segments using disjoint components in a model from PSB.

Results for CaS collection decomposition

In order to allow a quick analysis of the XML file produced by the Collection-aware Segmentation (CaS) algorithm, I wrote a simple XSL transformation that shows CaS results in an easily readable format.

For instance, here you can take a look at the result of decomposing the Flat-Thin Components cluster from Purdue's ESB with CaS.

Model complexity in ESB

I need to study the complexity of models in the PRECISE engineering shape benchmark (ESB) collection. Although such approximation is not always true, I considered that more complex objects contain more faces, while meshes with less triangles represent simpler models. Indeed, a simpler object might contain more faces than a more complex one, depending on the mesh. However, this is not common in the ESB collection and the face count is easy to estimate. From this estimation, I concluded that the majority of the models in this collection contain more than ten thousand polygons, as illustrated in chart below.

Distribution of models from ESB collection according to face count

Counting faces in STL files

To help me creating statistics on collections of 3D models I developed a small application that counts the faces of models stored in STL files. It can be used to analyze a single model or a collection of models. The first is done by specifying the corresponding STL file and the second by specifying the folder that contains the collection. If you think such application might be useful, you can download the windows binary [ZIP 71KB] or ask me the cross-platform source code.

Output produced by FaceCounter application

CAS shape pool segment growth

As I was expecting, the context-aware segmentation (CAS) approach can potentially led to an exponential growth of the number of segments in the shape pool. Theoretically, if all the branches of the segmentation tree are expanded, after seven iterations the number of segments can grow so much that will be impossible to store in memory all their signatures. The charts below illustrate the worst case for two distinct collections with one and eight hundred models respectively.

Number of segments in shape pool

Memory necessary to store segment signatures

CAS/HFP versus HFP

During the last weeks I've been implementing the context-aware decomposition based on hierarchical fitting primitives (CAS/HFP) algorithm. Now that I finally have a working prototype, I was able to compare the result produced by CAS/HFP with the ones produced by applying only the hierarchical fiting primitives (HFP) segmentation. To that end I use a very small collection extracted from the PRECISE Engineering Shape Benchmark. Below I show the segmentation trees produced by the two algorithms for the same shape.

Decomposition tree produced by HFP

Decomposition tree produced by CAS/HFP

First approach to context-aware segmentation

In a first approach to context-aware segmentation (CAS), I have implemented a prototype that uses spherical harmonics descriptor and cord-and-angle histogram to estimate similarities between segments. This prototype decomposes all models in a given collection according to all others. Bellow is an example of a model extracted from the PRECISE Engineering Shape Benchmark and decomposed along with others from this benchmark using the CAS approach.

View of 3D model decomposed using CAS

Shape Segmentation with HFP

I have just combined the fitting primitives mesh clustering (HFP) algorithm proposed by Marco Attene in is paper "Hierarchical mesh segmentation based on fitting primitives" with the prototype that produces the spherical harmonics descriptor (SHA) and cord and angle histogram (CAH) for a 3D model. The result is an application that decomposes a model using the HFP approach and then computes for each segment the corresponding descriptors. This application produces a navigable VRML file containing the segmented model. By clicking on segments it is possible to see the descriptors for that segment and even the segment alone or a possible random sampling. To view an example based on a model extracted from the ESB click on screen-shot below.

Screen-shot of shape description page.

Decomposing 3D models

Moving forward into my main goal, I am now concerned with model segmentation. In my first approach to this problem I used the fitting primitives mesh clustering algorithm proposed by Marco Attene in is paper "Hierarchical mesh segmentation based on fitting primitives". A result obtained from a model extracted from the ESB with a preliminary prototype is depicted below, different colors representing distinct segments.

Segmented model

OFFtoVRLM v0.3 released

Since many 3D models (especially CAD models) are stored in the STL format, I decided to include in OFFtoVRML prototype the capability to read from this type of file. Thus, among some other functionalities, such as reading OFF segmented models, and a few solved bugs, version 0.3 reads files in STL ASCII format. Bellow is a view of the VRML produced from a model extracted from the PRECISE Engineering Shape Benchmark. Another useful new feature is the possibility of including the reference axis in the VRML file.

The current stable version of the prototype is available for download [ZIP 136KB].

VRML model produced from an STL file.

Computing the Cord and Angle Histogram

As a first step during the development of a prototype for computing descriptors for 3D shapes, I implemented the Cord and Angle Histogram (CAH) descriptor. Below are the results of the computation for the dog model I often use (m87 from the PSB). Additionally, you can see the corresponding VRML model showing the estimated cords.

Estimated cords colored according to length and angles with reference planes.

Computed cord and angle histograms

OFFtoVRLM v0.2 released

After a couple of changes, this prototype is now able to generate VRML code with explicit edges and showing both vertex and face normal for models with a large number of triangles. For instance, the Stanford Bunny with 70K polygons is processed in less then ten seconds, generating a 16.5MB VRML file containing the mesh and showing its convex hull, bounding box and sphere, polygon edges and normals at faces and vertices. A larger file, the 345K polygons Armadillo, is processed in around fifty seconds, generating a 70MB VRML file.

For illustration purposes we processed the 'Dino' model from AIM@SHAPE shape repository. It has around 50K polygons and below I show a couple of snapshots of the resulting VRLM model, containing normals and explicit edges.

The current stable version of the prototype is available for download [ZIP 118KB].

VRML model of 'Dino'

Close-up illustrating the normals and polygon edges

Computation of vertex normals

Resuming the development of my OFF to VRML converter, I added one more feature: the computation of vertex normals. For this purpose I follow the method described in the Computer Graphics bible, Foley et.al "Computer Graphics: Principles and Practice in C" . In my approach I use the area of the adjacent polygons to determine the length of the normal vector.

Model with vertex normals and colored according to distance to barycenter

Coloring according to distance to barycenter

In the OFF to VRML converter, it is now possible to colorize the
mesh surface according to distances from the corresponding vertices to the object barycenter.

Mesh with surface colored according to distance to barycenter