Več

Merjenje naravnosti odseka krivulje (predstavljeno kot polilinija)

Merjenje naravnosti odseka krivulje (predstavljeno kot polilinija)


Delam na algoritmu samodejnega označevanja kontur višine in eden od dejavnikov, ki jih želim upoštevati pri odločanju o položajih nalepk, je, kako "raven" je določen segment konture. Bolj kot je ravna, večja je verjetnost, da bo uporabljena za namestitev oznake na ta segment.

Vsaka kontura je predstavljena s polilinijo (vendar s točkami blizu skupaj, ki so videti kot krivulja s prostim očesom). Nato imam fiksno dolžino (širino nalepke), recimo 100 slikovnih pik. Če naključno (ali drugače) izberem konturni segment s širino 100 slikovnih pik, želim dobiti numerično količinsko vrednost njegove naravnosti (recimo nič za popolnoma raven konturni segment, neka vrednost večja od nič za ne torej naravnost segment, ta vrednost pa narašča z naraščanjem ukrivljenosti).

Iskal sem odgovore, vendar nisem našel ničesar res uporabnega. Hvaležen bi bil za kakršne koli napotke.


Odgovor je odvisen od konteksta: če boste raziskovali le majhno (omejeno) število segmentov, si boste morda lahko privoščili računalniško drago rešitev. Vendar se zdi verjetno, da boste ta izračun želeli vključiti v nekakšno iskanje dobrih točk oznake. Če je tako, je velika prednost imeti rešitev, ki je bodisi računsko hitra ali omogoča hitro posodabljanje rešitve, če se segment kandidatne vrstice nekoliko spreminja.

Na primer, recimo, da nameravate sistematično iskati po celotni povezani komponenti konture, predstavljeni kot zaporedje točk P (0), P (1),…, P (n). To bi naredili z inicializacijo enega kazalca (indeksa v zaporedje) s = 0 ("s" za "začetek") in drugega kazalca f (za "zaključek"), ki je najmanjši indeks, za katerega je razdalja (P (f), P (s))> = 100, nato pa napredujemo s tako dolgo, kot je razdalja (P (f), P (s+1))> = 100. Tako dobimo kandidatno polilinijo (P (s), P (s+ 1)…, P (f-1), P (f)) za oceno. Ko ste ocenili njegovo "sposobnost", da podpira oznako, bi nato povečali s za 1 (s = s+1) in nadaljevali s povečanjem f na (recimo) f 'in s na s', dokler kandidatna polilinija še enkrat ne preseže minimalnega nastane razpon 100, predstavljen kot (P (s '),… P (f), P (f+1),…, P (f')). Pri tem iz prejšnjega kandidata izpadejo oglišča P (s)… P (s'-1) in se mu dodajo oglišča P (f+1),…, P (f '). Zelo zaželeno je, da se fitnes lahko hitro posodobi na podlagi poznavanja le spuščenih in dodanih vrhov. (Ta postopek skeniranja bi se nadaljeval do s = n; kot ponavadi se mora v postopku f "previti" od n nazaj do 0.)

Ta premislek izključuje številne možne ukrepe fitnesa (vijugavost, mučnina itd.), ki bi sicer lahko bile privlačne. Pripelje nas do tega, da dajemo prednost ukrepom, ki temeljijo na L2, ker jih je običajno mogoče hitro posodobiti, ko se osnovni podatki nekoliko spremenijo. Analogija z glavnimi komponentami Analiza predlaga, da upoštevamo naslednji ukrep (kjer je majhno bolje, kot je zahtevano): uporabite manjšo od dveh lastnih vrednosti kovariančne matrike točkovnih koordinat. Geometrijsko je to eno merilo "tipičnega" odstopanja vrhov med stranmi v odseku kandidata na poliliniji. (Ena od razlag je, da je njen kvadratni koren manjša pol-os elipse, ki predstavlja druge vztrajnostne trenutke ogrodja polilinije.) Enaka bo nič samo za množice kolinearnih oglišč; v nasprotnem primeru presega nič. Meri povprečno odstopanje od strani do strani glede na osnovno črto 100 slikovnih pik, ustvarjeno z začetkom in koncem polilinije, zato ima preprosto razlago.

Ker je matrika kovariance le 2 do 2, se lastne vrednosti hitro najdejo z reševanjem ene kvadratne enačbe. Poleg tega je matrika kovariance vsota prispevkov iz vsakega od točkov v poliliniji. Tako se hitro posodobi, ko se izpustijo ali dodajo točke, kar privede do algoritma O (n) za konturo n-točke: to se bo dobro prilagodilo zelo podrobnim obrisom, ki so predvideni v vlogi.

Tukaj je primer rezultata tega algoritma. Črne pike so točke konture. Trdna rdeča črta je najboljši kandidatni del polilinije z dolžino od konca do konca, večjo od 100 znotraj te konture. (Vizualno očiten kandidat v zgornjem desnem kotu ni dovolj dolg.)


V skupnosti računalniške grafike je pogosto treba poiskati omejevalno polje okoli predmeta. Posledično je to dobro preučen problem s hitrimi algoritmi. Oglejte si na primer članek o minimalnih algoritmih omejevanja okvirjev Wikipedije. Najdete lahko pravokotnik z najmanjšo površino, ki obdaja vašo polilinijo, in nato uporabite razmerje stranic pravokotnika, višino/dolžino. Za natančnejšo meritev si lahko ogledate odstopanje polilinije od središčne črte omejenega pravokotnika.


Ne vem, ali to pomaga ali celo šteje kot odgovor, toda ko sem sedel tukaj in razmišljal o vprašanju, ki sem ga pravkar objavil, sem pomislil:

Kaj pa, če na konturno črto postavite krog določenega polmera. Ta krog bo vsaj na dveh mestih presekal konturno črto. Čim bolj ravna je črta, tem krajša je razdalja vzdolž konturne črte med dvema točkama križišča. Dlje ko je razdalja vzdolž konturne črte med točkami presečišča, bolj je ukrivljena črta. Če sta presečni točki več, je konturna črta preveč ukrivljena.

Ugotovili bi lahko, katera dolžina bi bila najboljši pokazatelj naravnosti, in nastavili rutino, da stopite vzdolž vsake konturne črte, in kjer je bila dovolj ravna, postavite etiketo.

Prepričan sem, da to ne pomaga preveč, in kar govorim v angleščini, je veliko težje v katerem koli programskem jeziku, ki ga uporabljate, vendar je to lahko začetek?


Najlažji pristop, ki si ga lahko zamislim, je razmerje med dejansko dolžino poti med začetkom in koncem ter najkrajšo razdaljo (ravna črta) od začetka do končne točke. Ravne črte bodo imele razmerja blizu ena, zelo ukrivljene črte pa zelo visoko razmerje.

To bi morala biti res enostavna izvedljiva rešitev.


Posodobitev: Kot je Mike pravilno opazil, bi bilo to enako Sinuosity.


Z iskanjem "ukrivljenost" in "polilinija" sem dobil te podatke. Kako lahko najdem ukrivljenost polilinije ?. Tam je predlagal, da se vrnemo k definiciji ukrivljenosti- K = DF/Ds. Tukaj doF.misliphi, ozTv zapisu wikipedije tukaj (http://en.wikipedia.org/wiki/Curvature).

Recimo, da imate zaporedje treh točk, p0, p1 in p2. izračunajte razdaljosmed p0 in p1, ki je delta s (Ds), ob predpostavki, da so si točke dovolj blizu. Potem potrebujete delto T (DT), ki je sprememba enote tangencialnega vektorja med p0 in p1. morda obstaja prefinjen način, toda surova metoda, ki se mi zdi, da vzamem dva bektorja p0-> p1, p1-> p2, normaliziram vsakega tako, da ima dolžino enega, nato vzamem vektorsko odštevanje teh dveh in nato določim velikost. To jeDT. Delitev daje ukrivljenostK0_1. za izračun primite p1, p2 in p3K1_2in tako naprej.

Sprašujem se, če konturo dobite kot polilinijo in ne kot upodobljene slikovne pike. Rekel si 100 slikovnih pik, zato me rahlo skrbi.


Poglej si posnetek: Geometry: Division of Segments and Angles Level 5 of 8. Examples IV