Implementação de algoritmos de geometria

Transcrição

Bolsa de integração na investigação
Instituto de Engenharia de Sistemas e Computadores de Coimbra
Filtragem de nuvens de pontos 3D utilizando a biblioteca CGAL
Implementação de algoritmos de geometria computacional
Bolseiro: Cristóvão Cordeiro
Orientador: Prof. Gil Gonçalves
1
Implementação de algoritmos de geometria computacional utilizando a biblioteca CGAL
●
Introdução
Os sistemas de varrimento laser (LIDAR – Light Detection and Ranging) produzem
nuvens de pontos muito densas (milhões de pontos x,y,z distribuídos irregularmente no
espaço 3D) que caracterizam a geometria dos objectos visados. Nesta bolsa, pretende-se
implementar algoritmos de processamento e filtragem sobre estas nuvens densas de pontos
3D utilizando a biblioteca de geometria computacional CGAL. Sob o ponto de vista prático,
pretende-se obter uma leitura simples e rápida de uma nuvem de pontos LIDAR e usando
essa informação lida, aplicar algoritmos de processamento e tratamento de pontos para que
se possa finalmente aplicar um último algoritmo baseado na triangulação Delaunay e daí
otber uma representação digital do nosso modelo geométrico.

Detecção óptica LIDAR (LIght Detection And Ranging)
➢
Envio e recepção de pulsos laser
Medição do ToF (time of flight);
➢
Velocidade da luz no ar: 300,000 km/s
➢
Análogo à tecnologia RADAR (radio detection and ranging)
2

Software utilizado:
➔
CGAL
➔
Boost
➔
Qt
➔
➔
CMake
➔
Matlab
➔
MeshLab
Microsoft Visual C++ 2008 Express Edition
3

Software utilizado: problemas de instalação
vs
Conflito entre instalação antiga do OpenGL com instalação recente do Qt

Solução:
Nova instalação de todo o software incluindo sistema operativo
(Windows XP) numa máquina virtual – Sun VirtualBox
4

CGAL
A CGAL é uma biblioteca gratuita (disponível online), que
oferece uma vasta lista de algoritmos relacionados com geometria
computacional, em C++.
Estruturas de dados e algoritmos oferecidos pela CGAL:
Triangulações;
➢Diagramas de Voronoi;
➢Criação de mesh files;
➢Interpolações;
➢Processamento e análise de conjuntos de pontos;
➢
A biblioteca CGAL ainda oferece interactividade
com outros tipos de software, como o Boost e Qt.
5

Website libLas
Foi retirado directamente da libLas um leitor de dados LIDAR. Apenas com
algumas adaptações, é relativamente simples executar este programa sem qualquer
problema.
Apesar da fácil implementação, esta biblioteca é bastante complexa e envolve
bastantes dependências (a bibliotecas de linkagem dinâmica .dll e a bibliotecas
estáticas .lib) .
Dynamiclink Libraries

geotiff.dll
msvcr80.dll
msvcp80.dll
libtiff.dll
liblas1.dll
zlib_osgeo.dll
jpeg_osgeo.dll
jpeg12_osgeo.dll
Static Libraries

liblas.lib
liblas_i.lib
6

libLas
Código principal:
#include "liblas/laspoint.hpp"
#include "liblas/lasreader.hpp"
#include <fstream> // std::ifstream
#include <iostream> // std::cout
Leitura do ficheiro Parcela1.las em
modo binário
int main(){
std::ifstream ifs;
ifs.open("Parcela1.las", std::ios::in | std::ios::binary);
Classe
'LASHeader'
liblas::LASReader reader(ifs);
Construtor do objecto 'reader' da
classe 'LASReader'
liblas::LASHeader const& header = reader.GetHeader();
std::cout << "Signature: " << header.GetFileSignature() << '\n';
std::cout << "Points count: " << header.GetPointRecordsCount() << '\n';
while (reader.ReadNextPoint())
{
liblas::LASPoint p=reader.GetPoint();
std::cout.precision(2);
Classe 'LASPoint'
std::cout << std::fixed << p.GetX() << ", " << p.GetY() << ", " <<
p.GetZ() << "\n";
}
}
7

libLas
Problemas na execução: RunTime Error ao executar o programa externamente.
Origem do erro desconhecida e a solução para o mesmo
não foi encontrada.
Executando o programa por intermédio do MVC++ é
possível contornar o problema.
8

libLas
Problemas na execução: Mesmo executando através do MVC++ , com uma
compilação em modo Debug não corre correctamente.
Problema: a biblioteca libLas não é distruibuida em modo
Debug.
Solução: Instalação da CGAL em modo Release.
9

libLas
Definir precisão para corrigir o truncamento dos pontos:
.
.
std::fixed
Excerto da execução:
550097.68, 4496147.07, 184.68
550098.10, 4496145.36, 178.44
550098.11, 4496145.94, 178.39
550098.11, 4496146.51, 178.35
550098.11, 4496147.12, 178.43
550098.12, 4496147.70, 178.41
550098.12, 4496148.29, 178.42
550098.14, 4496148.83, 178.25
550098.15, 4496149.39, 178.16
550098.16, 4496149.96, 178.12
550098.16, 4496150.56, 178.16
550098.17, 4496151.13, 178.11
550097.82, 4496153.10, 183.39
550098.16, 4496151.74, 178.24
550098.17, 4496152.33, 178.24
550098.17, 4496152.91, 178.26
550098.18, 4496153.48, 178.21
…
..
.
10

Processamento do conjunto de pontos
Para usar estes algoritmos da CGAL é necessário ter um
ficheiro “.xyz” com o nosso conjunto de pontos.
(..)
std::ofstream myfile;
myfile.open ("Parcela1.xyz");
Abre um ficheiro “.xyz” para escrita
while (reader.ReadNextPoint())
{
liblas::LASPoint const& p = reader.GetPoint();
myfile.precision(2);
myfile << std::fixed << p.GetX() << " " << p.GetY() << " " << p.GetZ() << "\n";
}
myfile.close();
Ficheiro “.xyz” e “.las” exactamente com a
mesma informação.
11

 Estimação e orientação das normais:
Duas funções possíveis para cálculo da direcção das normais:
➢
void run_pca_estimate_normals(PointList& points, unsigned int nb_neighbors_pca_normals)
➢
void run_jet_estimate_normals(PointList& points, unsigned int nb_neighbors_jet_fitting_normals)
Uma função para orientar as normais:
➢
void run_mst_orient_normals(PointList& points, unsigned int nb_neighbors_mst)
No nosso caso, as normais foram estimadas pela
função “run_jet_estimate_normals” (ideal para
superfícies curvas, que podem ser aproximadas
por equações de 2º grau) .
Método para cálculo das normais pode ser escolhido aquando da chamada do programa
12

Opções de chamada do programa:
Descrição do programa
Opções possíveis de passar como argv
Normal estimation
Reads a point set, compute and orient its normals,
and save the point set.
If the input mesh has normals, print the normals deviation.
Usage: normal_estimation file_in file_out [options]
Input file formats are .off, .xyz and .pwn.
Output file formats are .xyz and .pwn.
Options:
-estimate plane|quadric
Estimates normals direction
using a tangent plane or quadric (default=quadric)
-nb_neighbors_pca <int>
Number of neighbors
to compute tangent plane (default=18)
-nb_neighbors_jet_fitting <int> Number of neighbors
to compute quadric (default=18)
-orient MST
Orient normals
using a Minimum Spanning Tree (default=MST)
-nb_neighbors_mst <int>
Number of neighbors
to compute the MST (default=18)
Aviso do programa quando argc < 3
13

Grande precisão
Excertos do código:
(...)
std::string input_filename = argv[1];
std::string output_filename = argv[2];
(...)
PointList points;
std::cerr << "Open " << input_filename << " for reading..." << std::endl;
(…)
else if (extension == ".xyz" || extension == ".XYZ" ||
extension == ".pwn" || extension == ".PWN")
{
std::ifstream stream(input_filename.c_str());
success = stream &&
CGAL::read_xyz_points(stream,
std::back_inserter(points),
CGAL::First_of_pair_property_map<PointVectorPair>());
}
if (!success)
{
std::cerr << "Error: cannot read file " << input_filename << std::endl;
return EXIT_FAILURE;
}
(…)
14

Excertos do código: (continuação)
(...)
// Estimates normals direction.
if (estimate == "plane")
run_pca_estimate_normals(points, nb_neighbors_pca_normals);
else if (estimate == "quadric")
run_jet_estimate_normals(points, nb_neighbors_jet_fitting_normals);
// Orient normals.
if (orient == "MST")
run_mst_orient_normals(points, nb_neighbors_mst);
(...)
O resto do código implementa a
gravação dos pontos em conjunto com
as normais orientadas num ficheiro
“.xyz”
15

Executando o programa:
c:\path\Release> normal_estimation Parcela1.xyz ParcelaWithNormals.xyz
Informação relativa ao ficheiro lido, que é mostrada
na janela de comandos:
Normal estimation
Open Parcela1.xyz for reading...
Reads file Parcela1.xyz: 29947 points, 0.48 seconds
Estimates Normals Direction by Jet Fitting (k=18)...
done: 2.914 seconds, 3 Mb allocated
Orients Normals with a Minimum Spanning Tree (k=18)...
done: 1.833 seconds, 6 Mb allocated
Write file ParcelaWithNormals.xyz
Tool returned 0
16

Excerto da informação no ficheiro resultante:
Ponto P
Vector unitário normal à superfície S no ponto P
550091 4496175.64 176.88 0.2178821521681261 0.05271081636424266 0.9745506336793387
550091 4496176.22 176.91 0.1449646889139383 -0.05642341386417789 0.9878267243479478
550091 4496176.81 177 0.2193422413732339 -0.08205253354342558 0.972191525826301
550091 4496138.99 178.06 0.0160764040620549 0.004927955372905709 0.9998586222503041
550091.01 4496139.57 178.06 -0.2791705516940375 0.0942948342564521 0.9556004851921095
550091.02 4496140.74 178 -0.2441155117311228 -0.05167595639271157 0.9683683247933871
550091.03 4496141.33 178 -0.2157979087450553 0.006724779412310216 0.9764148912850093
550091.03 4496141.91 178 -0.162821151449296 0.02665432835564588 0.9862955030925746
550091.04 4496142.5 178.01 -0.0207145390298559 0.01984649258548568 0.9995884276064998
17

Reconstrução da superfície a partir do conjunto de pontos
➢
O algoritmo admite um conjunto de pontos:
- com normais orientadas;
- sem outliers (pontos que se encontram a uma distância acima da
média em relação aos seus pontos vizinhos);
- com pouco ruído;
- inseridos num ficheiro “.xyz”.
➢
Processo de reconstrução:
- leitura do conjunto de pontos;
- aplicação de uma variante do método de Poisson (ideal para
sólidos), que recebe os pontos que delimitam um sólido;
- define e cria o ficheiro mesh de saída (“.off”).
18

Esta variante do método de Poisson começa por construir uma
Triangulação Delaunay 3D a partir dos pontos lidos:
Critério de uma Triangulação Delaunay:
Um triângulo definido por três arestas (conexão entre pontos
vizinhos) pertence a uma triangulação Delaunay T, se e só se
existir um círculo que passe pelos três vértices desse triângulo e
não contenha mais nenhum vértice no seu interior.
19

Depois da triangulação é feito um refinamento dos pontos de forma
a eliminar qualquer má formação dos tetraedros resultantes.
Por fim é resolvida a seguinte equação de Poisson em cada vértice
da triangulação:
Δf = div(n)
O mesh file criado no final tem por defeito o
seguinte nome:
kitten_poisson-20-30-0.375.off
20

(...)
// Reads the point set file in points[].
// Note: read_xyz_points_and_normals() requires an iterator over points
// + property maps to access each point's position and normal.
// The position property map can be omitted here as we use iterators over Point_3
elements.
PointList points;
std::ifstream stream("data/ParcelaWithNormals.xyz");
if (!stream ||
!CGAL::read_xyz_points_and_normals(
stream,
std::back_inserter(points),
CGAL::make_normal_of_point_with_normal_pmap(std::back_inserter(points))))
{
std::cerr << "Error: cannot read file" << std::endl;
return EXIT_FAILURE;
}
Algoritmo de Poisson
(…)
// Creates implicit function from the read points using the default solver (TAUCS).
// Note: this method requires an iterator over points
// + property maps to access each point's position and normal.
// The position property map can be omitted here as we use iterators over Point_3 elements.
Poisson_reconstruction_function function(points.begin(), points.end(),
CGAL::make_normal_of_point_with_normal_pmap(points.begin()));
(...)
21

Ficheiro para escrita
(...)
// saves reconstructed surface mesh
std::ofstream out("kitten_poisson-20-30-0.375.off");
Polyhedron output_mesh;
CGAL::output_surface_facets_to_polyhedron(c2t3, output_mesh);
out << output_mesh;
}
return EXIT_SUCCESS;
22

Exexução do programa (output na janela de comandos):
Creates Poisson triangulation...
Creates Poisson triangulation: 0.951 seconds, 5 Mb allocated
Delaunay refinement...
Calls delaunay_refinement(radius_edge_ratio_bound=2.500000, cell_radius_bound=57
.758783, max_vertices=10000000, enlarge_ratio=1.500000)
Calls poisson_refine_triangulation()
5 Mb allocated
Creates queue
Max allocation in Delaunay refinement = 24 Mb
24 Mb allocated
End of poisson_refine_triangulation()
End of delaunay_refinement()
Delaunay refinement: added 58116 Steiner points, 6.77 seconds, 24 Mb allocated
Solve Poisson equation with normalized divergence...
Calls solve_poisson()
24 Mb allocated
Creates matrix...
Solver da biblioteca TAUCS
Creates matrix: done (7.83 s)
36 Mb allocated
Solve sparse linear system...
Max allocation in solver = 94 Mb
Solve sparse linear system: done (2.30 s)
35 Mb allocated
End of solve_poisson()
Solve Poisson equation: 10.144 seconds, 27 Mb allocated
23

Resumo do processo de reconstrução
24

Visualização da superfície reconstruida
Recorrendo ao MeshLab...
25

Explorando o MeshLab...
26

27

28

29

30

31

Exemplo de uma boa reconstrução (sólido):
32

Criação do MEX-File
Ficheiro cuja “linkagem” é feita de forma dinâmica, a partir
de código produzido, neste caso, em C++, e quando
compilado, pode ser visto como um executável de MATLAB
Configuração prévia:
mex -setup
Exemplo simples de um MEX-File:
#include "mex.h"
void mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[]) {
mexPrintf("Hello, world!\n");
}
Compilação:
>>mex helloWorld.cpp
Resultado:
>>Hello, world!
33

Programa pretendido recebe um conjunto de pontos
LIDAR e faz a triangulação 2D desses pontos (ignorando
a componente de elevação)
Usar exemplo “terrain” da CGAL.
int main()
{
std::ifstream ifs("data/triangulation_prog1.cin");
std::istream_iterator<Point> begin(ifs);
std::istream_iterator<Point> end;
Delaunay dt;
dt.insert(begin, end);
std::cout << dt.number_of_vertices() << std::endl;
getchar();
return 0;
}
34

Criação do MEX-File sem sucesso, usando o
compilador do MVC++. Problemas por resolver...
35

Referęncias
[1] CGAL-User and Reference Manual: All Parts , Release 3.6 , 20
March 2010. [Online] :
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/contents.html
[2] “ACG (Applied Computational Geometry Lab)” tutorial para instalação
da CGAL e software relacionado.[Online]: http://acg.cs.tau.ac.il/cgal-attau/installing-cgal-and-related-programs-on-windows/
[3] Fórum de discussão para utilizadores da CGAL. [Online] :
https://lists-sop.inria.fr/sympa/arc/cgal-discuss
[4] libLAS - LAS 1.0/1.1/1.2 ASPRS LiDAR data translation toolset.
[Online] : http://liblas.org/
[5] “LASTools” - Ferramentas de manuseamentos de informação LIDAR.
[Online] : http://www.cs.unc.edu/~isenburg/lastools/
[6] Fórum de discussão para utilizadores da libLas. [Online] :
http://liblas-developers.431198.n3.nabble.com/
[7] Software MeshLab. [Online] : http://meshlab.sourceforge.net/
[8] Guia informativo sobre criação de MEX-Files. [Online] :
http://www.mathworks.com/support/tech-notes/1600/1605.html#setup
[9] Lino Marques , Sensores Ópticos para Medição de Distâncias –
Automação Industrial 2007
36

Referęncias
[10] MSDN Fórum - Visual C++ Express Edition. [Online] :
http://social.msdn.microsoft.com/Forums/en-US/Vsexpressvc
[12] Informação geral acerca de programação C++.[Online]:
http://www.cplusplus.com/
[13] Mateusz Loskot , página pessoal – relatório de “bugs” da libLas.
[Online] : http://mateusz.loskot.net/category/projects/liblas-projects/
[14] Software CMake - Download. [Online] :
http://www.cmake.org/cmake/resources/software.html
[15] Software Qt - Download. [Online] : http://qt.nokia.com/downloads/
[16] Boost Downloads. [Online] : http://www.boost.org/users/download/
37
38

Implementação de algoritmos de geometria

Transcrição

Documentos relacionados

Leia Mais! - Diagnostic

N. Inscrição Entrevista 33329-452010 9,5 31676

plano de ensino

Motores com caixa tipo ZF

Projeto de Geometria Mosaico-Mandala 2015

Fluxograma - infes - Universidade Federal Fluminense

PROGRAMA - Aproged

ice - ciência da computação - concurso iii

OFERTA EXP 2011 BMW X5 4dr AWD Sports Activity Vehicle

agadir-marrocos