Surface Registration Techniques Applied to Archaeological Fragment Reconstruction

Abstract

[EN] Reconstruction of broken archaeological artifacts from fragments is a very time-consuming task that requires a big effort if performed manually. In fact, due to budgetary limitations, this is not even attempted in countless sites around the world, leaving vast quantities of material unstudied and stored indefinitely.

This Thesis dissertation faces the application of surface registration techniques to the automatic re-assembly of broken archaeological artifacts from fragments. To efficiently do so, the reconstruction problem has been divided into two groups: 3 degrees of freedom and 6 degrees of freedom problems. This distinction is motivated for two major reasons: archaeological interest of the application and computational complexity of the solution.

First kind of problems (3 degrees of freedom) deal with 2D objects or with flat 3D objects, like ripped-up documents or frescoes, respectively. In both cases, the mural paintings and engravings on the fragments' surface are of huge importance in the field of Cultural Heritage Recovery. In this sense, archaeologically speaking, the value of the reconstruction is not the final model itself, but the information stored in the upper surface. In terms of computation complexity, the reduced solution space allows using exhaustive techniques to ensure the quality of the results, while keeping execution times low. A fast hierarchical technique is introduced to face this kind of problems. Starting from an exhaustive search strategy, the technique progressively incorporates new features that lead to a hierarchical search strategy. Convergence and correction of the resulting technique are ensured using an optimistic cost function. Internal search calculations are optimized so the only operations performed are additions, subtractions and comparisons over aligned data. All heavy geometric operations are carried out by the GPU on a pre-processing stage that only happens once per fragment.

Second kind of problems (6 degrees of freedom) deal with more general situations, where no special constraints are considered. Typical examples are broken sculptures, friezes, columns... In this case, computational complexity increases considerably with the extra 3 degrees of freedom, making exhaustive approaches prohibitive. To face this problems, an efficient sparse technique is introduced that uses a pre-processing stage to reduce the size of the problem: singular key-points in the original point cloud are selected based on a multi-scale feature extraction process driven by the saliency of each point. By computing a modified version of the PFH descriptor, the local neighborhood of each key- point is described in a compact histogram. Using exclusively the selected key-points and their associated descriptors, a very fast one-to-one search algorithm is executed for each possible pair of fragments. This process uses a three-level hierarchical search strategy driven by the local similarity between key-points, and applying a set of geometric consistence tests for intermediate results. Finally, a graph-based global registration algorithm uses all the individual matches to provide the final reconstruction of the artifact by creating clusters of matching fragments, appending new potential matches and joining individual clusters into bigger structures.

[ES] La reconstrucción de objetos arqueológicos fracturados a partir de fragmentos es una actividad que, si se realiza manualmente, supone un gran coste temporal. De hecho, debido a restricciones presupuestarias, esta tarea no llega a abordarse en incontables yacimientos arqueológicos, dejando grandes cantidades de material sin ser estudiado y almacenado indefinidamente.

La presente propuesta de tesis aborda la aplicación de técnicas de registro de superficies a el re-ensamblado automático de objetos arqueológicos fracturados a partir de fragmentos. Por motivos de eficiencia, el problema de la reconstrucción se ha dividido en dos grupos: problemas de 3 grados de libertad y problemas de 6 grados de libertad. Esta distinción está motivada por dos razones: (1) el interés arqueológico de la aplicación final de las técnicas desarrolladas y (2) la complejidad computacional de la solución propuesta.

El primer tipo de problemas (3 grados de libertad) se enfrenta a objetos bidimensionales o tridimensionales planos como documentos fragmentados y frescos, respectivamente. En ambos casos, los murales y grabados sobre la superficie de los fragmentos son de gran importancia en el ámbito de la conservación del patrimonio cultural. En este sentido, desde el punto de vista arqueológico, el valor de la reconstrucción final no radica en el modelo en sí, sino en la información almacenada sobre su superficie. En términos de complejidad computacional, el reducido espacio de soluciones permite emplear técnicas de búsqueda exhaustivas que garantizan la corrección de los resultados obtenidos con tiempos de ejecución acotados. La técnica propuesta para abordar este tipo de problemas parte de una estrategia exhaustiva y, progresivamente, incorpora nuevas optimizaciones que culminan con una técnica íntegramente jerárquica. La convergencia y corrección de la solución propuesta están garantizadas gracias a una función de coste optimista. Los cálculos internos durante las búsquedas han sido optimizados de modo que sólo son necesarias operaciones de adición/substracción y comparaciones sobre datos alineados en memoria. Todas las operaciones complejas asociadas a la manipulación de datos geométricos son realizadas por la GPU durante una etapa de pre-procesamiento que se ejecuta una sola vez por fragmento.

El segundo tipo de problemas (6 grados de libertad) se enfrenta a situaciones más generales, en las que ninguna restricción especifica puede ser asumida. Ejemplos típicos son esculturas fragmentadas, frisos, columnas... En este caso, la complejidad computacional incrementa considerablemente debido a los 3 grados de libertad adicionales por lo que el coste temporal de las estrategias exhaustivas resulta prohibitivo. Para abordar este tipo de problemas, se propone una técnica dispersa eficiente apoyada en una fase de pre-procesamiento cuyo objetivo consiste en reducir la talla de los datos de entrada: a partir de las nubes de puntos originales, puntos clave singulares son identificados gracias a un proceso de extracción de características multi-escala apoyado en el valor de saliencia de cada punto. Mediante el cálculo de una versión modificada del descriptor PFH (Persistent Feature Histograms), el vecindario local de cada punto clave es descrito en un histograma compacto. Empleando únicamente estos puntos y sus descriptores asociados, un algoritmo de búsqueda uno-a-uno muy rápido se ejecuta sobre cada par de fragmentos. Dicho proceso emplea una estrategia de búsqueda jerárquica de tres niveles, dirigida por la similitud entre puntos clave y que aplica un conjunto de tests de consistencia geométrica sobre los resultados intermedios. Finalmente, un algoritmo de registro global toma como datos de entrada todas las correspondencias individuales para generar la reconstrucción final del objeto.

[CA] La reconstrucció d'objectes arqueològics fracturats a partir de fragments és una activitat que, si es realitza manualment, suposa un gran cost temporal. De fet, a causa de restriccions pressupostàries, esta tasca no arriba a abordar-se en incomptables jaciments arqueològics, deixant grans quantitats de material sense ser estudiat i emmagatzemat indefinidament.

La present proposta de tesi aborda l'aplicació de tècniques de registre de superfícies a l're-enssamblatge automàtic d'objectes arqueològics fracturats a partir de fragments. Per motius d'eficiència, el problema de la reconstrucció s'ha dividit en dos grups: problemes de 3 graus de llibertat i problemes de 6 graus de llibertat. Esta distinció està motivada per dues raons: (1) l'interès arqueològic de l'aplicació final de les tècniques desenvolupades i (2) la complexitat computacional de la solució proposada.

El primer tipus de problemes (3 graus de llibertat) s'enfronta a objectes bidimensionals o tridimensionals plans com documents fragmentats i frescos, respectivament. En tots dos casos, els murals i gravats sobre la superfície dels fragments són de gran importància en l'àmbit de la conservació del patrimoni cultural. En este sentit, des del punt de vista arqueològic, el valor de la reconstrucció final no es basa en el model en si, sinó en la informació emmagatzemada sobre la seva superfície. En termes de complexitat computacional, el reduït espai de solucions permet emprar tècniques de recerca exhaustives que garanteixen la correcció dels resultats obtinguts amb temps d'execució acotats. La tècnica proposada per abordar aquest tipus de problemes part d'una estratègia exhaustiva i, progressivament, incorpora noves optimitzacions que culminen amb una tècnica íntegrament jeràrquica. La convergència i correcció de la solució proposada estan garantides gràcies a una funció de cost optimista. Els càlculs interns durant les recerques s'han optimitzat de manera que només són necessàries operacions d'addició / substracció i comparacions sobre dades alineats en memòria. Totes les operacions complexes associades a la manipulació de dades geomètriques són realitzades per la GPU durant una etapa de pre-processament que s'executa una única vegada per fragment.

El segon tipus de problemes (6 graus de llibertat) s'enfronta a situacions més generals, en què cap restricció especifica pot ser assumida. Exemples típics són escultures fragmentades, frisos, columnes ... En este cas, la complexitat computacional s'incrementa considerablement a causa dels 3 graus de llibertat addicionals pel que el cost temporal de les estratègies exhaustives resulta prohibitiu. Per abordar este tipus de problemes, es proposa una tècnica dispersa eficient recolzada en una fase de pre-processament l'objectiu del qual consisteix a reduir la talla de les dades d'entrada: a partir dels núvols de punts originals, s'identifiquen punts clau singulars gràcies a un procés d'extracció de característiques multi-escala recolzat en el valor de saliència de cada punt. Mitjançant el càlcul d'una versió modificada del descriptor PFH (Persistent Feature Histograms), els veins locals de cada punt clau és descriuen en un histograma compacte. Emprant únicament estos punts i els seus descriptors associats, un algoritme de cerca un-a-un molt ràpid s'executa sobre cada parell de fragments. Aquest procés fa servir una estratègia de cerca jeràrquica de tres nivells, dirigida per la similitud entre punts clau i que aplica un conjunt de tests de consistència geomètrica sobre els resultats intermedis. Finalment, un algoritme de registre global pren com a dades d'entrada totes les correspondències individuals per generar la reconstrucció final de l'objecte.