Web page with PhD work

I don't know why I took so much time to create a web page about my PhD research. However, it's better late than never, so I have just created one. It's not complete, but it is a beginning.

Visit the web page of my PhD research, which focused on Thesaurus-based 3D Shape Retrieval, T-b3DR for short. There you can find some information about my work and a couple of useful prototypes.

LaTeX equation editor

I've been using a very useful tool for writing equations in LaTeX. Although it is quite easy to found on the internet, I notice that some of my colleagues did not know about it. Thus, I thought it might be a good idea to publicise it here.

So, if you're using LaTeX you should give a look at the LaTeX equation editor. It is simple, fast, and accurate. And you do not need to install anything, it runs on your web browser.

Writing a number set in LaTeX

I needed to write the formal notation of a multi-dimensional dataset in my PhD dissertation. Since I'm using LaTeX and this dataset consists on a real number set I just have to use the mathbb font, provided by amsfonts or amssymb packages.

Thus, providing that the proper packages were included in the preamble of the document, I just had to use, in math mode:

\mathbb{R}^n

to obtain:

Random Number Generator

During my tests I often needed to produce some random numbers. Sometimes, when the occasion does not justify more worries, I used a very useful site developed by Mads Haahr of the School of Computer Science and Statistics at Trinity College, Dublin in Ireland. The RANDOM.ORG produces true random numbers and has been a useful help. It seems that it is now turning into a commercial site but I hope it remains free, at least for the basic features.

Feature vector distances between similar shapes

While writing the PhD dissertation I need to depict some data I gathered during my research. One example regards the distances measured between spherical harmonics feature vectors of similar 3D shapes. In the last couple of days I've been working on this, producing results such as the depicted below.

Distances between SHA feature vectors for a set of similar shapes.

Chart depicting the distances of top 5 similar shapes on ESB collection

Prototypes working on Linux

Although developed aiming a cross-platform solution, the prototypes of my PhD research only have been compiled in Windows. Until now. Moved by the need of having my prototypes running on a Linux system, I dedicated a few hours to creating a makefile and making some slight changes in the code in order to compile the prototypes in Linux. It worked fine! Now I have my prototypes running in both Windows and Linux!

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

Prototype packages

The prototype developed during my PhD research is divided into four distinct applications: CASDecomposer; Segment Clustering; ThesaurusBuilder; and ShapeRetriever. These are simple console applications that allow the user to control the algorithms behaviour. However, instead of independent applications, the whole prototype is composed by a set packages presented below.

Prototype packages (click on image to enlarge)

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

Eurtooling21 project concluded.

The Eurotooling21 project has just come to the end. As part of our participation in this EC funded project, we developed the Quick Quotation Assistant (QiQA) tool. Noticeably, the QiQA was selected as one of the Top 10 results of this project that comprises 33 partners from ten EU member states. Detailed information on this tool can found at the QiQA's final technical report.

Filipa and Tiago Wedding

Last weekend my colleague and office mate, Tiago Guerreiro, got married. We attended the wedding and subsequent reception. It was a nice ceremony at the church followed by a phenomenal event at the "Pousada de Palmela", as you can check in the picture below.

One of the highlights of any wedding: throwing the bouquet... and the girls disputing for it!

Just kidding. No girl fighting! Unfortunately! Eh eh eh... But the party was awesome and went on till very late night (or early morning, to be more correct).

I published more pictures of this event on a Picasa Web Album. Feel free to take a look.

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

QiQA idea overview

While preparing the Quick Quotation Assistant (QiQA) final report, within my collaboration on Eurotooling21 project, I redesign from scratch the diagram that represents the idea behind this tool. Below you can find the new diagram, depicting the basic principles of the quotation assistance environment.

Ammersee

In the day after the Sketch Tools for Diagramming workshop in Herrsching (Germany) and before return home, I went for a boat trip in the Ammersee lake plus a walk around the town. In the picture below you can see me in the boat deck after leaving Riederau, on the oposite side of the lake.

EditION presented in Sketch Workshop

Last Monday I presented the paper titled "EditION: A Collaborative Calligraphic Tool to Manage Virtual Environments" at the 2008 IEEE Symposium on Visual Languages and Human-Centric Computing workshop Sketch Tools for Diagramming held on Herrsching am Ammersee, Germany. An electronic version of the paper can be downloaded from the on line proceedings.

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.

Keeping words together

I needed to keep two words together in the same line while writing a document with Microsoft Word. Although this is easy to do in LATeX, I have no idea how to do it in Word. After a few searches, I found out that it is even simpler. If one wants to keep to words separated by a space together, just have to use a non-breaking space instead of a "traditional" space.

To insert a non-breaking space in Microsoft Word simply press <CTRL>+<SHIFT>+<SPACE> instead of <SPACE>.

Professor Randy Pausch died on July 25th

Last friday, July 25th, Professor Randy Paush died of complications from pancreatic cancer. I have no words to describe the loss it represents not only for the computer science community, but for all the academic world. You can read more at the CMU page.

Paper accepted at SketchWS

The paper titled "EditION: A Collaborative Calligraphic Tool to Manage Virtual Environments" has been accepted for presentation at the 2008 IEEE Symposium on Visual Languages and Human-Centric Computing workshop Sketch tools for diagramming. According to reviewers comments, it needs just a few changes. Let's work on that!

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.

Hybrid Shape Descriptor by P.Papadakis

In the Eurographics 2008 Workshop on 3D Object Retrieval, Papadakis Panagiotis et.al. presented a paper titled 3D Object Retrieval using an Efficient and Compact Hybrid Shape Descriptor". Since I was very interested in this work but was not able to find it online, I send an email to Papadikis Panagiotis asking him for a copy. His quick answer (in less than twenty minutes I have the printed paper in my hands) was extraordinary and motivating. If the proposed technique is as faster as its author, it will be a blast!

A blog on Mobile Accessibility

Tiago Guerreiro, my colleague at VIMMI group, released a blog on mobile accessibility, the topic of his PhD work. In this blog you can find news on mobile accessibility and usability. Accessibility to mobile devices and through mobile devices.

Take a look at Mobile Accessibility blog by Tiago Guerreiro.

Tapada Nacional de Mafra

This weekend we went to the Tapada Nacional de Mafra and spent a quite pleasant time there. My son just loved to chase deers...

Chasing a deer...

The deer stops and looks back. Probably it is time to return.

Kindergarten party

Last Tuesday I went to my son's kindergarten end-of-year party. It was a very special afternoon. Both for him and for us.

Tiago playing his role in the "recycle theater"

Annecy 2008

After the SBIM'08 workshop and during the last day of the Annecy Animation Film Festival, Saturday, I used some spare time to enjoy the city and its surroundings. In my rollerblades I went to Duingt, a small town in the left margin of the lake, a dozen kilometers south of Annecy. It was a quite pleasant trip in a cycleway by the lake. During that day I rollerbladed more than forty kilometers, the longest distance I have ever ride in a single day. But the conditions for that were great. If you're planning to visit Annecy I strongly recommend to consider taking your bike or skates with you. It's worthy.

Rollerblading in Annecy (France) surroundings

LSketchIt

Last week I've been in the fifth Eurographics workshop on sketch-based interfaces and modeling (SBIM'08). The workshop took place during the famous Annecy Animation Film Festival and was held together with the premier conference for techniques in expressive rendering and animation: the non photo realistic animation and rendering conference (NPAR'2008).

At the SBIM'08, I presented our more recent work on sketch based modeling (see paper "Using Sketches and Retrieval to Create LEGO Models"). The LSketchIt is a calligraphic tool for creating LEGO models that uses sketches and retrieval to ease and speed up the modeling process. Check out LSketchIt working in the demonstration video below.

LSketchIt demonstration video

Deleting VirusScan Enterprise quarantine files

I am using the Networks Associate VirusScan Enterprise 8.0 with patch 10 and found out that it was using more than 400MB to store the quarantined files. Version 8.5 provides a tool that allows users to manage these files, the Quarantine Manager. However, version 8.0 don't have such tool and I was not even able to manually delete the corresponding ".Vir" files, since they were locked by the application.

Fortunately, I found a solution to overcome this problem in the McAfee Support Forums. Indeed it is quite simple.To delete files in the Quarantine directory, on must disable the On-Access Scanner, and delete the file. After that it is important to remember to enable it again. Although it can be done using GUI, I present bellow the corresponding console commands:

% cd \quarantine
% net stop mcshield
% del *.Vir
% net start mcshield

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 name change

From discussions with colleagues from SMG at IMATI-Ge, we concluded that the name originally given to the decomposition algorithm was not the most appropriate. Indeed, it might lead to some confusion and misinterpretation. Therefore, we decided to change the algorithm name to "Collection-Aware Segmentation".

Goodbye Genoa

My fellowship at CNR IMATI-Ge finished last Friday. Thus, on Saturday morning I was packing and in the afternoon embarking on a ferry to Barcelona, from where I rode to Lisbon.

I want to thank everybody at the Shape Modeling Group for the way they welcomed and supported me: it was a pleasure to work with you, guys.

Waiting, with other motorcyclists, to went on board.

Godbye Genova.

In practice it is not so bad

After making some changes in the CAS algorithm and improving the prototype (basically, I write its core from scratch) I could study its behavior with larger collections. The results were positive because the growth of the shape pool is far below the simulated worst case. Indeed, after the third iteration the number of segments to add to shape pool decreases and within seventh iteration is very low. The chart bellow illustrates exactly this.

Shape pool growth (using a set of 273 models extracted from ESB)

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

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