Frank Wefers. Partitioned convolution algorithms for real-time auralization. Logos Verlag Berlin GmbH. λογος - PDF

Description
Frank Wefers Partitioned convolution algorithms for real-time auralization Logos Verlag Berlin GmbH λογος Aachener Beiträge zur Technischen Akustik Editor: Prof. Dr. rer. nat. Michael Vorländer Institute

Please download to get full document.

View again

of 83
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Internet

Publish on:

Views: 20 | Pages: 83

Extension: PDF | Download: 0

Share
Transcript
Frank Wefers Partitioned convolution algorithms for real-time auralization Logos Verlag Berlin GmbH λογος Aachener Beiträge zur Technischen Akustik Editor: Prof. Dr. rer. nat. Michael Vorländer Institute of Technical Acoustics RWTH Aachen University Aachen Bibliographic information published by the Deutsche Nationalbibliothek The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available in the Internet at D 82 (Diss. RWTH Aachen University, 2014) c Copyright Logos Verlag Berlin GmbH 2015 All rights reserved. ISBN ISSN Vol. 20 Logos Verlag Berlin GmbH Comeniushof, Gubener Str. 47, D Berlin Tel.: +49 (0)30 / Fax: +49 (0)30 / Partitioned convolution algorithms for real-time auralization Von der Fakultät für Elektrotechnik und Informationstechnik der Rheinischen-Westfälischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines DOKTORS DER NATURWISSENSCHAFTEN genehmigte Dissertation vorgelegt von Dipl.-Inform. Frank Wefers aus Neuss Berichter: Universitätsprofessor Dr. rer. nat. Michael Vorländer Universitätsprofessor D.Sc. Lauri Savioja Tag der mündlichen Prüfung: 25. September 2014 Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfügbar. Abstract Virtual Reality (VR) aims at the creation of responsive simulations, that provide humans the illusion of a world or environment, they can interact with. Therefore, the user is stimulated with sensory cues that are computergenerated, based on a model of a virtual world (scene). Considering the sense of hearing, the acoustic description of the scene is transformed into auditory stimuli, which are then provided using headphones or loudspeakers. Signal processing is fundamental to this process, called auralization. It involves digital filtering in several uses and in diverse forms (e.g. non-linear and linear filtering, time-invariant and time-varying filtering). A common requirement for VR is a low latency (immediate system response). The computational extent however, ranges from moderate to highly complex, depending on the application. This work focuses on finite impulse response filters (FIR filters), which are applied in binaural synthesis, spatial sound reproduction and artificial reverberation. Straightforward FIR filtering in the time-domain fails to satisfy the requirements stated above. These are met by implementing the FIR filtering using efficient mathematical algorithms for fast convolution. Since the 1960s different algorithmic concepts have been developed, often from the divideand-conquer paradigm. The most popular example is fast convolution using the fast Fourier transform (FFT), which established as the standard tool. However, also fast convolution algorithms must be adapted to serve for realtime filtering. The most powerful concept hereby is partitioned convolution, which first splits the operands and then solves the partial problems using a fast convolution technique. Essential is that the decomposition conforms with real-time processing. This thesis considers three different classes of partitioned convolution algorithms for the use in real-time auralization: uniformly and non-uniformly partitioned filters, as well as unpartitioned filters. The algorithmic properties of each class are derived and guidelines for an optimal choice of parameters areprovided. Alltechniquesareanalyzedregardingmulti-channelprocessing, networks of filters and time-varying filtering, as needed in Virtual Reality. The work identifies suitable convolution techniques for different applications, rangingfromresource-awareauralization onmobiledevices toextensiveroom acoustical auralization on dedicated multi-processor systems. Zusammenfassung Virtuelle Realität (VR) schafft eine künstliche Wirklichkeit, in die ein Mensch eintauchen und mit der er interagieren kann. Ausgehend von der Beschreibung einer virtuellen Szene werden hierzu mit Hilfe von Computern, verschiedene Sinnesreize generiert, welche beim Benutzer die Illusion der Präsenz in dieser Wirklichkeit erzeugen. Für den Hörsinn bedeutet dies, dass man die akustische Beschreibung einer Szene in hörbare Signale überführen muss, welche dem Benutzer entsprechend dargeboten werden. Für diesen Prozess, der Auralisierung genannt wird, sind digitale Filter ein grundlegendes Werkzeug, das in verschiedenen Arten benötigt wird (z.b. lineare/nichtlineare Filter, zeitinvariante/zeitveränderliche Filter). Eine in der VR allgemeine Anforderung sind geringe Latenzen (möglichst zeitnahe Reaktion). Der Rechenaufwand hierfür reicht, je nach Anwendung, von moderat bis hochkomplex. Diese Arbeit befasst sich mit digitalen Filtern, welche endliche Impulsantworten haben, sogenannte FIR-Filter (von engl. finite impulse response). Für diese finden sich zahlreiche Anwendungen in der akustischen virtuellen Realität, wie beispielsweise in der binauralen Sythese, räumlichen Klangwiedergabeverfahren und bei der Erzeugung künstlichen Nachhalls. finite impulse response (FIR)-Filter können auf einfache Weise im Zeitbereich implementiert werden. Diese Art der Realisierung erfordert allerdings einen erheblichen Rechenaufwand und scheidet dadurch für die oben genannten Anwendungen aus. FIR-Filter können mit Hilfe schneller Faltungsalgorithmen effizienter implementiert werden. Seit Anfang der 1960er Jahre wurden verschiedene Konzepte zur schnellen Faltung entwickelt, häufig ausgehend vom teile und herrsche (divide-andconquer) Paradigma. Das populärste Beispiel hierfür ist die schnelle Faltung mittels der schnellen Fouriertransformation (engl. fast Fourier transform, FFT), welche sich als Standardverfahren etablierte. Leider sind die meisten schnellen Faltungsverfahren nicht direkt zur Filterung von Signalen in Echtzeit geeignet. Als leistungsfähigstes Konzept hat sich hierbei die Technik der partitionierten Faltung herausgestellt. Dieses zerteilt zunächst die Operanden der Faltung (Partitionierung) und realisiert dann die gewünschte Filterung mittels schneller Faltungen dieser Teilprobleme. Die Art der Zerlegung bestimmt hierbei maßgeblich die Fähigkeit der Echtzeitverarbeitung. Die vorliegende Arbeit untersucht drei Klassen von partitionierten Faltungen, welche für Echtzeit-Auralisierungen geeignet sind: Algorithmen, welche Filter als Ganzes (d.h. unpartitioniert) verarbeiten und solche, welche Filter in gleiche Teile (uniform) und ungleiche Teile (nicht uniform) zerlegen. Für jede Klasse werden die algorithmischen Eigenschaften im Detail hergeleitet und analysiert und Richtlinien für die optimale Wahl der Parameter werden angegeben. Dabei werden alle Techniken auch hinsichtlich weiterführender Aspekte untersucht, welche für die virtuelle Realität relevant sind, wie Mehrkanal-Filterung, Zusammenschaltungen von Filtern zu Netzwerken, sowie zeitveränderliche Filterung. Die Arbeit identifiziert die geeigneten Faltungstechniken (Filterungsverfahren) für die oben genannten Anwendungen auf verschiedenen Endgeräten, von Auralisierung auf mobilen Endgeräten mit begrenzter Rechenkapazität bis hin zu umfangreichen Raumakustik-Auralisierungen auf speziellen Multiprozessorsystemen. Contents Notation and symbols Acronyms I III 1. Introduction Objective Related work Problem description Outline Contributions Fast convolution techniques Discrete convolution Linear convolution Circular convolution Interpolation-based fast convolution Toom-Cook algorithm Karatsuba algorithm Improved Karatsuba convolution Conclusions Transform-based fast convolution Discrete Fourier Transform Fast Fourier Transform Symmetric filters Partial DFTs Discrete Hartley Transform Discrete Trigonometric Transforms Number Theoretic Transforms Number theoretic convolution techniques Multidimensional index mapping Agarwal-Cooley convolution algorithm Winograd convolution algorithm Summary 3. Partitioned convolution techniques Input partitioning Running convolutions Filter partitioning Filter partitioning scheme Filter structure Classification of partitioned convolution algorithms Elementary real-time FIR filtering using FFT-based convolution FFT-based running convolutions Overlap-Add Overlap-Save Computational complexity Transform sizes Performance Conclusions Filters with multiple inputs and outputs Dual channel convolutions Filter networks Filter exchange strategies Time-domain crossfading Frequency-domain crossfading Summary Uniformly partitioned convolution algorithms Motivation Uniform filter partitions Standard algorithm Computational complexity Performance Conclusions Generalized algorithm Conditions for frequency-domain processing Procedure Utilization of the transform period Parameters Computational costs Performance Conclusions Multi-dimensional convolutions Filter with multiple inputs or outputs Filter networks Filter exchange strategies Summary 6. Non-uniformly partitioned convolution Motivation History Non-uniform filter partitions Basic algorithm Standard parameters Computational complexity Timing dependencies Causal partitions Canonical partition Gardner s partitioning scheme Optimized filter partitions Optimization problem Optimization algorithm Minimal-load partitions Practical partitions Performance Complexity classes Implementation Filters with multiple inputs and outputs Filter networks Filter exchange strategies Real-time room acoustic auralization Perceptual convolution Summary Benchmarks Benchmark-based cost models Test system Benchmark technique Performance profiles Measurement procedure High resolution timing Initial behavior Transient behavior Outlier detection Robustness Basic operations Cost relations Accuracy Efficient FFTs Conclusions 8. Conclusion Summary Guidelines Outlook A. Appendix 229 A.1. Real-time audio processing A.2. Optimized non-uniform filter partitions A.3. Identities Bibliography 247 Acknowledgements 257 Notation and symbols Elementary math i, j, k, m, n Indices and superscripts (a,b,c,...) Tuple with elements a,b,c,... u, v, w, Vectors C, F, H Matrices diag(...) Diagonal matrix u, C Transpose of a vector or matrix X(z) = x 0 +x 1z +x 2z Polynomial over variable z deg( ) Degree of a polynomial e, e x Euler constant, exponential function log Natural logarithm (base e) log 2 Logarithmus dualis (base 2) i = 1 Imaginary unit a+bi = a bi Complex-conjugate Re{ }, Im{ } Real, imaginary part of a complex number W N = e 2πi/N Primitive N th roots of unity in C Ω( ), O( ) Asymptotic lower and upper bound (Landau notation) Discrete signals and spectra x(n) = [x(0),x(1),...] Discrete-time signal (finite or infinite length) X(k) = [X(0),...,X(K 1)] Discrete spectrum (finite length K) x(i),x(i) Sample or spectral coefficient of index i x i(n) Block of index i in the signal x(n) (continuous audio streams) x (i) (n) i th input or output signal (multichannel) h i(n) Sub filter of index i (filter partitions) h (i) (n) i th filter in an assembly x(n) = x n N N-periodic continuation of x(n) δ(n) Unit impulse I Notation and symbols Operators T { }, T 1 { } DFT (N) { } DFT 1 (N) { } P N{ x(n) } R N{ x(n) } Transform, inverse transform N-point discrete Fourier transform N-point inverse discrete Fourier transform Right-side zero-padding of x(n) to length N Rectangular window, extracting the first N elements of x(n) Transformation time frequency domain Transformation frequency time domain Pairwise or element-wise multiplication,, Linear, circular and symmetric convolution Number theory, a b, a b a b mod N n N gcd(a,b) lcm(a,b) Floor and ceiling function a divides b, a does not divide b Congruence relation Integer n modulo N (Rader notation) Greatest common divisor Least common multiple Algebraic structures N, Z Natural numbers, integers R, C Real numbers, complex numbers N 0 = N {0} Natural numbers with zero Z M = Z/MZ = {0,...,M 1} Set of integers modulo M R,K Ring, field R[z] Ring of polynomials (over variable z) K M M-element vector space over the field K K M N Set of M N-matrices over the field K Remarks Unless outlined, indices begin with 0 Polynomials are defined over the variable z II Acronyms AVR C2R CCP CCS CFM CMAC CMP CMUL CPU CRT DAG DCT DFT DHT DIF DIT DP DSP DST DTT FDL FDN FFT FHT FIR FNT GA GPU GUPOLS HRIR HRTF IDFT IFFT IIR LTI MDCT Acoustic Virtual Reality Complex-to-real Cyclic convolution property Complex-conjugate symmetric Common-factor map Complex-valued multiply-accumulate Convolution multiplication property Complex-valued multiply Central processing unit Chinese remainder theorem Directed acyclic graph Discrete cosine transform Discrete Fourier transform Discrete Hartley transform Decimation-in-frequency Decimation-in-time Dynamic programming Digital signal processor Discrete sine transform Discrete trigonometric transform Frequency-domain delay-line Feedback delay network Fast Fourier transform Fast Hartley transform Finite impulse response Fermat number transform Geometrical acoustics Graphics processing unit Generalized uniformly-partitioned Overlap-Save Head-related impulse response Head-related transfer function Inverse discrete Fourier transform Inverse fast Fourier transform Infinite impulse response Linear time-invariant Modified discrete cosine transform III Acronyms MDF MIMO MISO MNT NTT NUPOLA NUPOLS OLA OLS OS PC PFA PFM R2C RIR SIMD SIMO SISO SPS STFT TDL TDM TSC UPOLA UPOLS VDL VR WFTA Multidelay block frequency domain adaptive filter Multiple-input multiple-output Multiple-input single-output Mersenne number transform Number theoretic transform Non-uniformly partitioned Overlap-Add Non-uniformly partitioned Overlap-Save Overlap-Add Overlap-Save Operating system Personal computer Prime-factor algorithm Prime-factor map Real-to-complex Room impulse response Single-instruction multiple-data Single-input multiple-output Single-input single-output Symmetric periodic sequence Short-time Fourier transform Tapped delay-line Time-division multiplexing Time-stamp counter Uniformly partitioned Overlap-Add Uniformly partitioned Overlap-Save Variable delay-line Virtual Reality Winograd Fourier transform algorithm IV 1. Introduction Acoustic Virtual Reality (AVR) aims at the simulation of the acoustics in a non-existent world by the help of computers. The user is provided with generated auditory cues, that shall give him a feeling of presence in the virtual environment (immersion). A fundamental necessity for the belief in the simulation is that it confirms with the laws of physics and allows for interaction. The content of virtual scenes can emerge from reality (e.g. acoustic in cars, in traffic, in architecture, musical performances, etc.) or be fictional (e.g. computer games). Virtual reality has many uses. It can blend into our daily life and support us (e.g. 3D telephone). Advances in simulation technique make AVR nowadays usable for assessment tasks (e.g. noise scenarios) and planning tasks (e.g. acoustic in rooms, buildings, spaces). A central terminus in acoustic virtual reality is auralization [56]. It covers all necessary steps to create audible sound (stimuli) from the abstract description of a virtual world (scene). Auralization covers many partial aspects: synthesis (artificial generation of sound), simulation (sound field in an environment), rendering (applying the simulated sound field parameters to the audio signals) and reproduction (presentation of the generated stimuli to the user). Signal processing is fundamental to all of them. The basic tool for modifying the sounds to the need of the applications are digital filters of a variety of types. An example for non-linear filters are variable delaylines (VDLs), used to simulate time-varying propagation delays (Doppler shifts) [106]. Linear filters are used in form of filter banks (e.g. directivity of soundsources, medium attenuation, transmission modeling), forhead-related transfer functions (HRTFs) in binaural technology and for simulation reverberation using room impulse responses (RIRs) Linear filters are divided in two different classes: Feed-forward filters with finite impulse responses (FIR filters) and filters which facilitate feedback loops, resulting in potentially infinite impulse responses (IIR filters). Both types of filters are widely used in auralization. FIR filters allow complete control over the filter characteristic and avoid instabilities by concept. Unfortunately, they can demand a high computational effort (large number of arithmetic operations). The utilization of feedback loops in infinite impulse response (IIR) filters allows a significant reduction of the effort. However, their design is not trivial and issues of stability must be considered. 1 1. Introduction The computational burden of finite impulse response (FIR) filters is overcome by facilitating the tools of mathematics and implementing them with fast convolution methods. Their history dates back to the 1960s. Fast convolution techniques are manifold and have been developed from quite diverse mathematical fields. These include classical and linear algebra and number theory. Unfortunately, most of fast convolution algorithms can not be directly applied to real-time filtering and must be adapted accordingly. This is due to the fact, that real-time processing requires partial results to be provided during the convolution. Moreover, they are not computationally efficient, when short blocks of the signal are convolved with long impulse responses. Partitioned convolution solves this issue by decomposing large convolutions into better manageable shorter convolutions, while preserving a low latency. This makes it an essential algorithmic tool for the design of efficient real-time FIR filters Objective This thesis researches how FIR filters can be realized by partitioned convolution for applications in acoustic virtual reality. The filtering tasks in this field are characterized by a variety of requirements. The objective of this work is to identify and examine suited algorithms for these tasks. Immediate system responses are a fundamental requirement for interactive virtual environments. Hence, the focus lies on real-time FIR filters, which process the audio signals with minimal delays (latencies). A main intend is to realize the filters with the least computational load, the least possible runtimes or, in other words, within a minimal number of processor cycles. From a theoretical point of view, the complexity of algorithms can be expressed by the number of operations (mainly arithmetic operations, like multiplications and additions). On practical machines however, the performance of digital signal processor (DSP) algorithms is strongly affect by many further aspects, like the memory access, the caching and branching behaviour as well as the parallelization capabilities. In order to achieve an optimal performance, these aspects must be considered likewise. This thesis regards convolution algorithms from both perspectives: their analytic complexity and their performance on actual hardware. A frequently used term in this work is the computational efficiency of an algorithm. A high efficiency is achieved, when a particular filtering task is accomplished with a comparably low number of operations, regarding the problem from the analytical point of view, or, considering the practical perspective, within the least number of processor cycles. Both definitions asks of course for a reference, which is found in the conceptually simple, but computationally expensive time-domain FIR filters. A high efficiency is needed to overcome 2 1.2. Related work the present computational bottleneck, which limits the maximal number of sound sources in a virtual environment. In high-performance computing, simulations of more sources in very complex environments become possible. On mobile devices, auralization becomes less energy consuming. Here, a high computational efficiency helps saving battery life. A fast and efficient implementation is not the only attribute of inter
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks