Zvezna aproksimacija neenakomerno vzorčenih signalov

SODIN, DENIS (avtor), Košir, Andrej (mentor)

Magistrska naloga opisuje razvoj algoritma za aproksimacijo signala iz neenakomerno vzorčenih podatkov. Predlagana rešitev deluje na principu prevzorčenja merilnih podatkov in uporabe B-zlepkov za rekonstrukcijo signala. Pred realizacijo samega algoritma smo pregledali teorijo enakomernega in neenakomernega vzorčenja, postopke rekonstrukcije signala, razliko med aproksimacijo in interpolacijo, kriterije za kvaliteto aproksimacije, zgornjo frekvenčno mejo in odpravljanje šuma. Algoritmi so bili razviti v programskem jeziku Python, v katerega smo preko baze podatkov MongoDB uvozili vse potrebne merilne rezultate. Ti so bili pridobljeni med eksperimentom, v katerem so se kandidati učili slepega desetprstnega tipkanja. Med učenjem smo merili pospeške njihovih rok in velikost zenic. Na podlagi rekonstruiranega signala smo potem določali osredotočenost kandidatov na tipkanje. V začetni fazi smo skušali signal iz danih podatkov rekonstruirati s pomočjo polinomske interpolacije. Postopek se je zdel privlačen, saj deluje tako na enakomerno kot neenakomerno vzorčenih podatkih. Po izdelavi algoritma in pregledu rezultatov smo ugotovili, da za naš primer ta postopek ni dober. Problem se je pojavil zaradi velikega števila vzorčenih podatkov, ki so botrovali nastanku Rungevega fenomena. Gre za pojav, pri katerem se med dvema vzorčnima točkama pojavijo velike oscilacije, ki jih v našem primeru zagotovo ne bi mogli fizikalno upravičiti. Sledil je poskus implementacije teorema o neenakomernem vzorčenju, kjer pa se nam je zataknilo že pri izdelavi algoritma. Rezultati, ki smo jih dobivali, niso bili smiselni, kar je bilo po našem mnenju posledica nepravilnega obnašanja jedra funkcije, s katero smo signal skušali rekonstruirati. Preden smo napako odpravili, smo ugotovili, da nam tudi uspešna implementacija tega algoritma ne bi dala rezultatov, ki smo jih v našem primeru potrebovali. Razlog je v tem, da bi rezultat tega algoritma predstavljal interpolacijo vzorčnih točk, za naše podatke pa smo ugotovili, da vsebujejo šum, kar pomeni, da bi jih morali aproksimirati. To spoznanje nas je vodilo k preusmeritvi naše pozornosti na aproksimacijske postopke. Problem preprileganja (angl. overfitting), ki nastane pri interpolaciji merilnih točk, ki vsebujejo šum, smo se odločili reševati z uporabo B-zlepkov. V prvi iteraciji smo merilne točke skušali aproksimirati s pomočjo dinamičnega postavljanja vozlov. S tem postopkom smo odpravili problem previsokih frekvenc v rekonstruiranem signalu, vendar pa nam po drugi strani ni uspelo odpraviti težav z oscilacijami signala, ki se je pojavila na intervalih, kjer so bile vzorčne točke redke. Končni izdelani algoritem prav tako temelji na uporabi B-zlepkov. Njegova posebnost je ta, da smo na izmerjenih merilnih točkah najprej uporabili nizkopasovni filter in nato na prevzorčenih točkah izvedli interpolacijo. Tudi tukaj nam je uspelo odpraviti problematiko previsokih frekvenc, težave z oscilacijami signala na področjih z redkimi originalnimi vzorčnimi točkami pa smo nekoliko omilili, ni pa nam jih uspelo popolno odpraviti.

• Jezik: Slovenski jezik
• Ključne besede: neenakomerno vzorčenje, aproksimacija, interpolacija, prevzorčenje, zgornja frekvenčna meja, šum v podatkih, B-zlepek
• Vrsta gradiva: Magistrsko delo/naloga
• Organizacija: FE - Fakulteta za elektrotehniko
• Leto izida: 2017
• PID: 20.500.12556/RUL-89013
• Datum objave v RUL: 07.02.2017

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Continuous approximation of nonuniformly sampled signals

Izvleček

This master's thesis describes the development of an approximation signal algorithm from non-uniformed data sampling. Our proposed solution for signal reconstruction is based on resampling of data and usage of B-splines. We performed a quick review of uniformed and non-uniformed sampling, the difference between approximation and interpolation, signal reconstruction procedures, approximation quality criterias, upper frequency limit and noise elimination before implementing the algorithm. All of the algorithms proposed in the paper were developed in Python. Data points were obtained by experiment in which the candidates were learning how to touch type. During their learning we measured the acceleration of their hands and the size of their pupils. Based on reconstructed signal we then determined the candidates' focus on their typing. At the beginning phase we attempted to reconstruct the signal from given data by using polynomial interpolation. The method was appealing since it works for uniform and non-uniform sampling, however, after the implementation we discovered that this method cannot be used in our case because of the large amount of acquired data points that lead to Runge's phenomenon in which a great oscilation may occur between two neighbouring data points. In the next step we attempted to implement the theorem of non-uniform sampling (Paley-Wiener-Levinson theorem), but failed to get any results most likely because of incorrect behaviour of the function kernel. Before solving the problem with the kernel we realised, that this method would not give us the required results. The reason for that is noisy data, which should be approximated rather than interpolated to get meaningful results. This lead us to approximation based algorithms. We decided to use B-splines to deal with the problem of overfitting, which occurs when noisy data is interpolated. In the first iteration we attempted to approximate the data points using manually determined knots. With this method we eliminated the problem of high frequencies in reconstructed signal, but failed to remove the oscilations that appeared in the intervals with sparse data points. The final implemented algorithm also uses B-splines, however, here we decided to use low pass frequency filter on data points first and then interpolate the resampled data. This method eliminates the problem of high frequencies and reduces the oscilations, but does not eliminate them entirely.

• Ključne besede: non-uniform sampling, approximation, intepolation, resampling, upper frequency limit, noisy data, B-spline