Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Comparing normal estimation methods for the rendering of unorganized point clouds
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Jämförelse av beräkningsmetoder för normaler i oorganiserade punktmoln (Swedish)
Abstract [en]

Surface normals are fundamental in computer graphics applications such as computer vision, object recognition, and lighting calculations. When working with unorganized point clouds of surfaces, there exists a need for fast and accurate normal estimation methods.

This thesis presents the investigation and implementation of two different methods of normal estimation on fixed-size local neighborhoods in unorganized pointclouds.

Two main categories of tests were conducted. The first type was visual inspection and the second consisted of numeric analysis of the normal estimation process and results. Point cloud data used in the study included numerically exact representations of spheres, cubes, cones, as well as both uniformly sampled or laser-scanned real-world point clouds with millions of points.

Complete triangle averaging was found to be the method of choice on small neighborhoods, justified by faster running-time while still estimating high-quality normals. When larger neighborhood sizes were needed, a size breakpoint was found above which principal component analysis should be used instead, which estimates normals of similar quality as the complete triangle averaging but with the added benefit of near-constant running-time independent of neighborhood size.

Abstract [sv]

Ytnormaler är fundamentalt viktiga i datorgrafiktillämpningar som exempelvis datorseende, objektigenkänning och belysningsberäkningar. Det finns ett behov av snabba och precisa beräkningsmetoder för uppskattade normaler vid hanteringen av o-organiserade punktmoln.

I denna uppsats presenteras undersökningen och implementationen av två olika sätt att beräkna normaler för punkter i o-organiserade punktmoln från grannskap av förbestämt antal.

Två huvudkategorier av tester utfördes. Den första typen var visuell inspektion och den andra bestod av numerisk analys av både beräkning och de beräknade normalerna. Punktmolnen som användes för undersökningarna inkluderade matematiskt korrekta sfärer, kuber och koner, samt både regelbundet samplade och laserskannade verkliga punktmoln med miljontals punkter.

Komplett Triangulering av grannar visade sig vara den föredragna metoden för små grannskap, motiverad av kortare beräkningstid och högkvalitativt resultat. När antalet använda grannar steg kunde en brytpunkt ses, där ett byte till principalkomponentanalys kunde motiveras, då resultatet var normaler av likvärdig kvalitet, men med fördelen av nära konstant körtid oberoende av antalet använda grannar.

Place, publisher, year, edition, pages
2019. , p. 47
Series
TRITA-EECS-EX ; 2019:411
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-261598OAI: oai:DiVA.org:kth-261598DiVA, id: diva2:1358700
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2019-10-08 Created: 2019-10-08

Open Access in DiVA

fulltext(7168 kB)2 downloads
File information
File name FULLTEXT01.pdfFile size 7168 kBChecksum SHA-512
81141ede5d56f01ac1af0ea4186d32ac5455c3f33065d3b5de9a59bafa73004186a126e380739b271e487bb7e0f13169d64d23e414bb0eea271bade97c42476c
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 2 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 11 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf