RANSAC-sylinterit puunrungon mallinnuksessa pistepilvidatasta
Kankaala, Tuuli (2023)
Kankaala, Tuuli
2023
Teknis-luonnontieteellinen DI-ohjelma - Master's Programme in Science and Engineering
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2023-12-12
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-2023120710536
https://urn.fi/URN:NBN:fi:tuni-2023120710536
Tiivistelmä
Random Sample Consensus eli RANSAC on satunnaisotoksiin perustuva menetelmä mallin sovittamiseksi havaintodataan niin, että datan sisältämien poikkeavien havaintojen vaikutus muodostuvaan malliin tulee minimoiduksi. RANSAC on laajasti sovellettu ja siitä on kehitetty erilaisia versioita, joista tässä työssä on toteutettu MATLAB-ohjelmistolla seitsemän. Toteutettujen RANSAC-versioiden suoriutumista on vertailtu tarkastelemalla niiden tuottamien mallien tarkkuudesta ja niiden suoritustehokkuudesta kertovia mittareita.
Toteutettuja menetelmiä on sovellettu sylinterimallien sovittamiseksi osittaiseen kolmiulotteiseen pistepilvidataan, joka sisältää kohinaa ja poikkeavia havaintoja. Tällainen sovitustilanne on käsillä mallinnettaessa puunrunkoa sarjana peräkkäisiä sylintereitä laserkeilaamalla muodostetusta pistepilvidatasta, sillä olosuhteet luonnossa tuottavat puiden laserkeilausdataan aukkoja ja poikkeavia havaintoja. Työssä on käytetty sekä keinotekoisesti generoitujen yksittäisten sylinterien pistepilviä että keskikokoisesta tammirungosta laserkeilaamalla tuotettua pistepilvidataa, jonka resoluutiota ja käytettyjen laserskannausten määrää on varioitu. Yksittäisiä sylintereitä mallinnettaessa malliparametreille ei asetettu rajoitteita, mutta puunrunkoa mallinnettaessa hyväksyttävien sylinterimallien akselien suuntaa ja säteen suuruutta rajoitettiin.
Kaikki seitsemän RANSAC-versiota sovittivat mediaanitilavuudeltaan alle 10 % poikkeavia runkomalleja runkopistepilveen, jonka resoluutio oli 0,5 datapistettä per neliösenttimetri ja joka sisälsi vain yhden laserskannauksen tuottamat datapisteet. Resoluution nostaminen moninkertaiseksi vähensi tulosten hajontaa mallinnusta toistettaessa. Sen sijaan toisen laserskannauksen lisääminen ensimmäisen rinnalle oletusten vastaisesti heikensi mallinnustuloksia, mikä on voinut johtua joko toisen laserskannauksen tuottaman pistepilven heikommasta laadusta tai kahden skannauksen tuottamien pisteiden epäonnistuneesta yhteensovituksesta samaan koordinaatistoon.
MSAC-menetelmä tuotti puunrunkoja mallinnettaessa toteutetuista menetelmistä tarkimpia tuloksia, mutta vaati eniten RANSAC-iteraatiokierroksia. Kt-uudelleensovitusmenetelmän tulokset eivät generoituja yksittäisiä sylintereitä mallinnettaessa olleet kehuttavia, mutta puunrunkoja mallinnettaessa se suoriutui vähintään RANSACin standardiversion tasoisesti ja välillä sitä paremmin. Pienimmän neliösumman korvaaminen pienimmällä neliömediaanilla (LMS) Gauss-Newton-optimoinnin kustannusfunktiona hypoteesimallien sovittamisessa tuotti generoitua sylinteridataa käsiteltäessä paljon hajontaa tuloksiin, mutta runkomalleja muodostettaessa LMS suoriutui kaikilla mittapuilla RANSACin standardiversion kanssa samantasoisesti ja kaikkien toteutettujen menetelmien kesken keskitasoisesti. T_{d,d} -testin käyttö lisäsi puunrunkoja mallinnettaessa käytettyjen iteraatioiden määrää ja tulosten hajontaa. Inner-RANSAC-uudelleensovitusmenetelmä ja sen yhdistäminen Kt-uudelleensovitusmenetelmään eivät vaikuttaneet parantavan tuloksia tai vähentävän tarvittavien iteraatioiden määrää tarpeeksi kompensoidakseen näiden menetelmien vaatimista ylimääräisistä mallisovitusoperaatioista koituvia kustannuksia laskenta-ajassa. RANSAC (Random Sample Consensus) is a method for fitting a model into observational data in the presence of possible measuring errors, called outliers, and measuring noise. The goal of its use is to minimise the effect of the outliers on the fitted model. RANSAC is widely applicable and has been modified into many different versions, of which seven are implemented in this thesis work using MATLAB software. The performance of the seven versions of RANSAC is studied by analysing markers of the fit of the produced models and of the required computational costs.
The implemented RANSAC methods have been applied to fitting cylinder models into three-dimensional point cloud data, which covers only a part of the cylinder surface and contains outliers and noise. This kind of modelling situation is relevant when modelling a tree trunk as a series of subsequent cylinders from LiDAR (Light Detection and Ranging) point cloud data, since environmental factors often cause formation of gaps and outlier clusters in the point clouds produced from trees. Both artificially generated cylinder point cloud data and real LiDAR point cloud data from a medium-sized oak trunk were used in this thesis. The density and the number of scanning directions used in the LiDAR point clouds were varied. Restrictions on model parameters were not implemented when modelling single cylinders from the artificially generated data, but during the tree modelling phase limits were set for an acceptable cylinder radius and cylinder axis angle.
The median volumes of the fitted tree trunk models deviated less than 10 % for all seven implemented RANSAC-versions, when a point cloud from only one scan with the density of 0,5 points per square centimeter was used. Multiplying the point density reduced the dispersion of the results, when models where regenerated multiple times. Contrary to expectations, adding points from a second laser scan from a different direction weakened the modelling results, which may have been a consequence of the second point cloud being of inferior quality or an unsuccesful registration of two LiDAR scans to the same coordinate system.
Of the seven methods, MSAC produced the most accurate tree trunk volumes but required the most RANSAC-iterations. Refitting the model iteratively by scaling the used error tolerance did not impress with the results when processing the generated cylinder point clouds, but with the LiDAR data the method slightly outperformed the standard RANSAC. Replacing least sum of squares with least median of squares (LMS) as the cost function of Gauss-Newton optimisation heightened dispersion of the results when fitting singular cylinders to the generated point cloud data. However, for the tree trunk LiDAR point clouds this was not the case and LMS-modified RANSAC performed at the same level with the standard version. The use of T_{d,d} test increased the dispersion of the results and the amount of used iterations when modelling tree trunks. Refitting tree models with inner-RANSAC and combining inner-RANSAC with iterative rescaled error tolerance did not appear to improve the results or to reduce the amount of iterations enough to compensate for the time consuming additional model refitting operations that these methods perform.
Toteutettuja menetelmiä on sovellettu sylinterimallien sovittamiseksi osittaiseen kolmiulotteiseen pistepilvidataan, joka sisältää kohinaa ja poikkeavia havaintoja. Tällainen sovitustilanne on käsillä mallinnettaessa puunrunkoa sarjana peräkkäisiä sylintereitä laserkeilaamalla muodostetusta pistepilvidatasta, sillä olosuhteet luonnossa tuottavat puiden laserkeilausdataan aukkoja ja poikkeavia havaintoja. Työssä on käytetty sekä keinotekoisesti generoitujen yksittäisten sylinterien pistepilviä että keskikokoisesta tammirungosta laserkeilaamalla tuotettua pistepilvidataa, jonka resoluutiota ja käytettyjen laserskannausten määrää on varioitu. Yksittäisiä sylintereitä mallinnettaessa malliparametreille ei asetettu rajoitteita, mutta puunrunkoa mallinnettaessa hyväksyttävien sylinterimallien akselien suuntaa ja säteen suuruutta rajoitettiin.
Kaikki seitsemän RANSAC-versiota sovittivat mediaanitilavuudeltaan alle 10 % poikkeavia runkomalleja runkopistepilveen, jonka resoluutio oli 0,5 datapistettä per neliösenttimetri ja joka sisälsi vain yhden laserskannauksen tuottamat datapisteet. Resoluution nostaminen moninkertaiseksi vähensi tulosten hajontaa mallinnusta toistettaessa. Sen sijaan toisen laserskannauksen lisääminen ensimmäisen rinnalle oletusten vastaisesti heikensi mallinnustuloksia, mikä on voinut johtua joko toisen laserskannauksen tuottaman pistepilven heikommasta laadusta tai kahden skannauksen tuottamien pisteiden epäonnistuneesta yhteensovituksesta samaan koordinaatistoon.
MSAC-menetelmä tuotti puunrunkoja mallinnettaessa toteutetuista menetelmistä tarkimpia tuloksia, mutta vaati eniten RANSAC-iteraatiokierroksia. Kt-uudelleensovitusmenetelmän tulokset eivät generoituja yksittäisiä sylintereitä mallinnettaessa olleet kehuttavia, mutta puunrunkoja mallinnettaessa se suoriutui vähintään RANSACin standardiversion tasoisesti ja välillä sitä paremmin. Pienimmän neliösumman korvaaminen pienimmällä neliömediaanilla (LMS) Gauss-Newton-optimoinnin kustannusfunktiona hypoteesimallien sovittamisessa tuotti generoitua sylinteridataa käsiteltäessä paljon hajontaa tuloksiin, mutta runkomalleja muodostettaessa LMS suoriutui kaikilla mittapuilla RANSACin standardiversion kanssa samantasoisesti ja kaikkien toteutettujen menetelmien kesken keskitasoisesti. T_{d,d} -testin käyttö lisäsi puunrunkoja mallinnettaessa käytettyjen iteraatioiden määrää ja tulosten hajontaa. Inner-RANSAC-uudelleensovitusmenetelmä ja sen yhdistäminen Kt-uudelleensovitusmenetelmään eivät vaikuttaneet parantavan tuloksia tai vähentävän tarvittavien iteraatioiden määrää tarpeeksi kompensoidakseen näiden menetelmien vaatimista ylimääräisistä mallisovitusoperaatioista koituvia kustannuksia laskenta-ajassa.
The implemented RANSAC methods have been applied to fitting cylinder models into three-dimensional point cloud data, which covers only a part of the cylinder surface and contains outliers and noise. This kind of modelling situation is relevant when modelling a tree trunk as a series of subsequent cylinders from LiDAR (Light Detection and Ranging) point cloud data, since environmental factors often cause formation of gaps and outlier clusters in the point clouds produced from trees. Both artificially generated cylinder point cloud data and real LiDAR point cloud data from a medium-sized oak trunk were used in this thesis. The density and the number of scanning directions used in the LiDAR point clouds were varied. Restrictions on model parameters were not implemented when modelling single cylinders from the artificially generated data, but during the tree modelling phase limits were set for an acceptable cylinder radius and cylinder axis angle.
The median volumes of the fitted tree trunk models deviated less than 10 % for all seven implemented RANSAC-versions, when a point cloud from only one scan with the density of 0,5 points per square centimeter was used. Multiplying the point density reduced the dispersion of the results, when models where regenerated multiple times. Contrary to expectations, adding points from a second laser scan from a different direction weakened the modelling results, which may have been a consequence of the second point cloud being of inferior quality or an unsuccesful registration of two LiDAR scans to the same coordinate system.
Of the seven methods, MSAC produced the most accurate tree trunk volumes but required the most RANSAC-iterations. Refitting the model iteratively by scaling the used error tolerance did not impress with the results when processing the generated cylinder point clouds, but with the LiDAR data the method slightly outperformed the standard RANSAC. Replacing least sum of squares with least median of squares (LMS) as the cost function of Gauss-Newton optimisation heightened dispersion of the results when fitting singular cylinders to the generated point cloud data. However, for the tree trunk LiDAR point clouds this was not the case and LMS-modified RANSAC performed at the same level with the standard version. The use of T_{d,d} test increased the dispersion of the results and the amount of used iterations when modelling tree trunks. Refitting tree models with inner-RANSAC and combining inner-RANSAC with iterative rescaled error tolerance did not appear to improve the results or to reduce the amount of iterations enough to compensate for the time consuming additional model refitting operations that these methods perform.