[en] AN ALGORITHM FOR CURVE RECONSTRUCTION FROM SPARSE POINTS

CRISTIANE AZEVEDO FERREIRA

[pt] UM ALGORITMO PARA RECONSTRUÇÃO DE CURVAS A PARTIR DE PONTOS ESPARSOS

dc.contributor	HELIO CORTES VIEIRA LOPES
dc.creator	CRISTIANE AZEVEDO FERREIRA
dc.date	2004-01-23
dc.date.accessioned	2022-09-21T21:42:15Z
dc.date.available	2022-09-21T21:42:15Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4430@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4430@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.4430
dc.identifier.uri	https://hdl.handle.net/20.500.12032/42506
dc.description	[pt] A reconstrução de curvas e superfícies a partir de pontos esparsos é um problema que tem recebido bastante atenção ultimamente. A não-estruturação dos pontos (ou seja, desconhecimento das relações de vizinhança e proximidade) e a presença de ruído são dois fatores que tornam este problema complexo. Para resolver este problema, várias técnicas podem ser utilizadas, como triangulação de Delaunay, reconstrução de iso-superfícies através de Marching Cubes e algoritmos baseados em avanço de fronteira. O algoritmo proposto consiste de quatro etapas principais: a primeira etapa é a clusterização dos pontos de amostragem de acordo com sua localização espacial. A clusterização fornece uma estrutura espacial para os pontos, e consiste em dividir o espaço em células retangulares de mesma dimensão, classificando as células em cheias (caso possuam pontos de amostragem em seu interior) ou vazias (caso não possuam pontos de amostragem em seu interior). A estrutura de dados gerada nesta etapa permite também obter o conjunto dos pontos de amostragem de cada uma das células. A segunda etapa é o processamento dos pontos através de projeções MLS. A etapa de pré- processameno visa reduzir ruído dos pontos de amostragem, bem como adequar a densidade de pontos ao nível de detalhe esperado, adicionando ou removendo pontos do conjunto inicial. A terceira etapa parte do conjunto das células que possuem pontos de amostragem em seu interior (células cheias) e faz a esqueletonização deste conjunto de células, obtendo, assim, uma aproximação digital para a curva a ser reconstruída. Este esqueleto é encontrado através do afinamento topológico das células que possuem pontos. A implementação do algoritmo de afinamento é feita de modo que o número de pontos em cada célula seja levado em consideração, removendo primeiro sempre as células com menor número de pontos. Na quarta etapa, a reconstrução da curva é finalmente realizada. Para tal, parte-se do esqueleto obtido na terceira etapa e constrói-se uma curva linear por partes, onde cada vértice é obtido a partir da projeção MLS do ponto médio de cada célula do esqueleto.
dc.description	[en] Curve and surface reconstruction from sparse data has been recognized as an important problem in computer graphics. Non structured data points (i.e., a set of points with no knowledge of connectivity and proximity) together with the existence of noise make this problem quite difficult. In order to solve it, several techniques have been proposed, such as, some of them are based on Delaunay triangulation, other are based on implicit surface reconstruction or on the advancing front techniques. Our algorithm consists basically in four steps. In the first step, a clustering procedure is performed in order to group the sample points according to their spatial location. This procedure obtains an spatial structure for the points by subdividing uniformly the plane in rectangular cells, and classifying them into two categories: empty (when the cell contains no point inside) or not empty (otherwise). At this stage, a data structure is built in such way that it is possible to query the set of sample points that belong to a given rectangular cell. The second step processes the point through the Moving Least Squares method. Its objective is not only to reduce the noise on the data, but also to adapt the number of point to the desired level, by adding or removing points from the initial set. The third step builds the skeleton of the set of cells that have sample point on its interior. Such skeleton is in fact a digital approximation for the curve that will be reconstructed. It is obtained by the use of a topological thinning algorithm, and its implementation is done in such a way that the number of points in each cell is considered, for example, the cells with less number of points are not considered for the thinning. In the last step, the curve is finally reconstructed To do so, the skeleton obtained in the third step is used to construct a piecewise-linear approximation for the curve, where each vertex is obtained from the MLS projection on the middle point of the skeleton rectangular cell.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] RECONSTRUCAO DE CURVAS
dc.subject	[pt] AFINAMENTO TOPOLOGICO
dc.subject	[pt] MINIMOS QUADRADOS
dc.subject	[en] CURVE RECONSTRUCTION
dc.subject	[en] TOPOLOGICAL THINNING
dc.subject	[en] LEAST SQUARES
dc.title	[en] AN ALGORITHM FOR CURVE RECONSTRUCTION FROM SPARSE POINTS
dc.title	[pt] UM ALGORITMO PARA RECONSTRUÇÃO DE CURVAS A PARTIR DE PONTOS ESPARSOS
dc.type	TEXTO

Ficheros en el ítem

Ficheros	Tamaño	Formato	Ver
No hay ficheros asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Documentos - PUC-RIO

Mostrar el registro sencillo del ítem