Writing CAS/HFP on XML file

Since I will now test the CAS/HFP algorithm with larger collections, I needed to devise a way to store the segmentation in order to be able to re-use it without having to process it again. Thus, I have implemented a feature that allows writing to (and reading from) a XML file the segmented collection. Moreover, the computed signatures for segments and corresponding similarities are also saved. Below is an excerpt of a XML file describing a collection decomposition.

Excerpt of XML decomposition file.

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

Me and C++, a love/hate relationship

It is not something new. It has always been like that. These last two days were just another example of this. Yesterday, I was cursing C++. I have been fighting to solve some major memory leaks on my code... and it was hard... I hate C++!!! Today I finally finished solving that problem and moved forward. Moved to a completely different issue. In this I apply the flexibility and power of C++ to implement an algorithm that can be compiled using only standard libraries or using wxWidgets (and taking advantage of it). The most beautiful point is that I did it in just a couple of hours and the only thing I now have to do, if I want to switch, is change a single line of code. Indeed, I love C++!!!

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

I have took a few days off to spent with my family here in Genoa. Now they returned home and I'm back to work. Nevertheless, there were a short but very good vacations, where we had lots of fun. At least my son enjoyed everything. Specially the children's race track at Corso Italia.

My son riding on the children's race track

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.

Listing directory contents with C++

Listing the contents of a directory is a basic functionality. However, there are no standard C++ function to do it. Usually, for this purpose additional libraries are used, such as Boost or wxWidgets, since they provide lots of useful functionalities. But this time I just needed that my code was able to get the directory contents in both Windows and Linux. I was not interested including a bunch of unnecessary stuff.

Thus, based on a article by Daniel Schuller, I wrote a small piece of portable code that read the contents of a directory. A link for downloading the source file are available bellow:

• C++ code for listing directory contents
  

Computing Spherical Harmonics Descriptor

Based on work by Michael Kazhdan, I implemented a prototype that produces the spherical harmonics descriptor (SHA) for a 3D model. To that end I used not only the executables for computing SHA representations provided by Kazhdan, but also some code developed by Simone Marini to read the binary signatures. The results produced by my prototype for shape m87 from the PSB (the dog model I often use) are illustrated below. You can also take a look at the VRML file containing the 3D SHA representation of this model.

2D chart of SHA representation of dog model

3D view of SHA representation

Cold front but pleasant view

During the last few days a cold front hit Italy, making the thermometers show unusually low temperatures for this time of the year, together with strong winds. Despite off all the problems and inconvenience created by this bad weather, I am enjoying pretty much the pleasant view from my office at IMATI-Ge, where I'm currently working with the Shape Modelling Group.

Sampierdarena viewed from the IMATI-Ge offices


My workplace

Polygon Detector v0.1

More that four years after the publication of the algorithm in the paper "Polygon Detection from a Set of Lines", I finally found time to re-write the code. Since it was implemented within a larger project, it was sharing several pieces of code and dependent of classes containing lots of functionalities unnecessary for this purpose.

The "Polygon Detector" prototype takes as input an SVG file containing a set of lines and produces another SVG file with the corresponding polygon set. Note that the polygon detection algorithm runs in O(n^4), where "n" is the number of lines obtained after intersection removal. Thus, for a complex line set, it may take a while to detect the polygons. For instance, processing the line set depicted below took around twelve minutes in a Intel Pentium M 2GHz 1MB RAM computer running Windows XP.

Line set with 100 random lines, corresponding to 2286 non-intersecting lines

The polygon detection algorithm created, from the line set illustrated above, a set of almost one thousand polygons depicted below. The current version of the prototype produces an SVG file containing colored polygons, however the coloring algorithm used is quite simple and still needs some improvements, namely to avoid (or at least minimize) color repetition. Something to be solved in a future version.

Set of detected polygons, containing 995 elements.

If interested, you can download the current stable version of the prototype [ZIP 434KB] or the paper where the algorithm was initially paper, "Polygon Detection from a Set of Lines", Ferreira, A., Fonseca, M.J. and Jorge, J.A., Actas do 12º Encontro Português de Computação Gráfica (12th EPCG), pages 159-162, Porto, Portugal, Oct 2003 [PDF 86KB].

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

New version of QiQA prototype

After a few weeks of hard work, the core of the "Quick Quotation Assistant" (QiQA) prototype was redesigned from scratch. Although the interface remains unchanged (except for a minor detail on QiQA-Builder) the implementation of algorithms is now absolutely different. These are now independent from each other, whilst in the previous version all were implemented together,with several cross-dependencies and lots of unnecessary functionalities. The current version of the prototype and a small drawing collection are available at the QiQA software download page.

A long lasting bug was solved!

Since the beginning of the QiQA prototype development I have been battling with a weird problem. The application just ended unexpectedly while processing some drawings during database building. However, I never had the opportunity to study this problem properly. Instead I choose to skip the problematic drawings, flagging them as "nor processable".

Fortunately, thanks to recent improvements in the feature extraction algorithms, the drawing processing is much faster than before (at least ten times faster). Thus, I decided to focus on the above referred problem.

After identifying a drawing that triggers the above referred error, I patiently started to debug the code. After several boring hours of detailed analysis, I finally found the portion of the code that causes this damned error.

Code exit point.

It was during the access to a list within the CALI code, developed by Manuel João da Fonseca. When the given index value is outside the valid bounds, this library simply calls the C++ "exit" function. And that's it. But why and when does this happen? During the computation of convex hull of the "CIScribble".

The source of the problem

Indeed, it seems to be missing a test in the "while" sentence, which allows a variable with a unacceptably low value to be used as index to access a list. Therefore, for now the solution was just adding a test to the "while" test expression and voilá... it works fine.

Modular QiQA

The main problem with QiQA prototype was the time it took to process a collection. This was due to a unstructured design. Indeed, this prototype was built from my master thesis work, by simple adding functionalities. The result of this evolution was a complex program with lots of unnecessary code, used during the years for several purposes and never removed.

To improve its efficiency I redesigned the application from scratch, focusing now on modularity. Therefore, I produced a modular solution, based on a set of packages, shown below.

QiQA solution packages

Fluviário de Mora

Yesterday, to take the most of my last weekend in Portugal before leaving to Genoa, I went with my wife and son to the Fluviário de Mora. An aquarium dedicated to wildlife of rivers, in a small town in rural countryside. It was somehow a disappointment, especially because we are used to the wonderful Oceanário de Lisboa with its huge 5.000 cubic meters main tank. Anyway, I took some nice pictures in the Fluviário.

A frog from the tropical rain forest.

New documents available on web page

After a researcher from the City University of Hong Kong asked me for a couple of reports on 3D shape retrieval, I decided to publish them on my institutional web page. Therefore, it is now possible to download directly from there the two technical reports on 3D shape analysis and retrieval written within the DecorAR project. Additionally, I also published my PhD thesis proposal.