MATHEMATICS AND COMPUTATION IN IMAGING
SCIENCE AND
INFORMATION PROCESSING
(July - December 2003)
~ Abstracts ~
Huang's Empirical Mode
Decomposition and splines
Sherman D. Riemenschneider, Dept. of Mathematics, West
Virginia University, USA
Cubic splines play a major role in the Empirical Mode Decomposition introduced by Norden Huang for non-stationary and nonlinear signals as means to define an instantaneous frequency via the Hilbert Spectrum. In this talk we give some elementary results about the Hilbert transforms of splines, and other roles that splines may play in the obtaining an EMD.
Generating a good triangular mesh
Gilbert Strang, Dept. of Mathematics, Massachusetts
Institute of Technology, USA
An essential first step in many problems of numerical analysis and computer graphics is to cover a region with a reasonably regular mesh.
We describe every line of a short MATLAB code that begins with a "distance function" to describe the region: d(x,y) is the distance to the boundary (with d < 0 inside the region). The code must decide the location of nodes and the choice of edges. At each iteration the mesh becomes a truss (with forces in the edges that move the nodes). Then the Delaunay algorithm resets the topology of the triangles. The input includes a size function h(x,y) to give desired meshlengths over the region.
The code is adaptable and public. It extends directly to n dimensions. The 2D meshes are remarkably regular. The theory is not complete.
Orthogonal frames of translates
Eric S. Weber, Dept. of Mathematics, University of Wyoming,
USA
A frame sequence (or Bessel sequence) defines an operator, called an analysis operator, which maps the Hilbert space into a space of coefficient sequences. The composition of the adjoint of the operator with an analysis operator from another frame sequence is a bounded operator on the Hilbert space which is a sum of rank one tensors. This operator, sometimes called a ``Mixed Dual Grammian'', is an important operator in frame theory. The duality condition of two frames corresponds to this operator being the identity.
Two Bessel sequences are said to be orthogonal if this operator is the 0 operator. The motivation for orthogonal Bessel sequences comes from the following problems:
1) Given a frame, can we find all of the dual frames?
2) How can frames be used in orthogonal division multiple access communications?
3) How can perfect reconstruction of vectors in a subspace be accomplished when the vectors are not in the subspace?
We shall describe these problems, and also describe some other applications which arise from the problems, such as cryptography and watermarking. We shall then give characterizations of when two Bessel sequences are orthogonal when the Bessel sequences have the form of translates of a finite number of functions in L2(Rd). The characterizations are applied to Bessel sequences which have an affine structure, a quasi-affine structure, a Gabor structure, and also an irregular structure. Moreover, we characterize perfect reconstruction (duality) of subspace frames for translation invariant subspaces of L2(Rd).
Uncertainty principles and
wavelets
Tim N. T. Goodman, Dept of Mathematics, The University of
Dundee
Heisenberg’s uncertainty principle gives a lower bound on the ‘uncertainty product’ of a function, a measure of its spread in both time and frequency. It is seen that for certain sequences of functions satisfying self-similarity equations, the uncertainty products converge to the minimum. We then introduce the related wavelets: functions which allow decomposition simultaneously in time and frequency with orthogonality between different frequencies. For such bandpass filters the uncertainty principle is modified and we examine the convergence to the minimum of the appropriate uncertainty products of the wavelets. We also discuss uncertainty principles for periodic functions. In these cases the minimum uncertainty is not attained and we consider sequences of trigonometric polynomials whose uncertainty products converge to the minimum. These results are extended to functions on general spheres, and we also suggest an uncertainty principle on the circle for which minimum uncertainty is attained.
CT and MR imaging
Chye Hwang Yan, DSO National Laboratories and Borys Shuter,
Department of Radiology, National University Hospital
The purpose of this tutorial is to present a technical overview on computed tomography and magnetic resonance imaging. It will cover the underlying physics and also the mathematical techniques used for image reconstruction. A portion of the tutorial will address the limitations, such as artifacts and noises, of these imaging modalities. The tutorial will end with a survey on the current state of the art CT and MR machines.
Image processing and soft computing
techniques for medical applications
Kap Luk Chan, School of Electrical and Electronic
Engineering Nanyang Technological University
Early detection and treatment of colorectal cancer helps reducing the number of deaths from this disease. It is thus meaningful to develop image processing and analysis techniques and apply them to endoscopic (colonscopic) images acquired through colonoscopy for this purpose. In this presentation, we report several techniques developed for detection of abnormalities in the colon from colonoscopic images which may assist subsequent analysis for detection of colorectal cancer by doctors and health care providers. We have developed edge-based techniques for abnormality detection through edge curvature analysis, region-based techniqiues through region segmentation using neural network and fuzzy-logics and etc. Both color and textural image properties are explored. In a more recent attempt, a new concept-learning approach is taken to overcome the ambiguity in the problem definition. Through learning from image data labeled by the medical experts, diagnosis models can be extracted automatically. We evaluate our methods on a set of colonoscope images. The experimental results show the feasibility of our methods and suggest promising applicability for clinical implementation.
Current clinical applications and
limitations of CT/MR imaging
Poh Sun Goh, Department of Radiology National University
Hospital
This talk covers the advantages and limitations of CT/MR Imaging.
Advanced signal processing
algorithms for fMRI
Sadasivan Puthusserypady, Department of Electrical and
Computer Engineering National University of Singapore
fMRI is a new technique for localising brain activity; whereas independent component analysis (ICA) is a relatively new technique for blind source separation (BSS). Principle of brain modularity states that different region of the brain perform different function independently, thus spatial ICA can be applied on fMRI. Brain signal has proven to be nonlinear, hence applying nonlinear ICA on fMRI signal should arrive at a better results. However, nonlinear ICA has the problem of non-unique solutions therefore post-nonlinear (PNL) ICA model is used. Furthermore, PNL-ICA model closely resemble to the balloon model. The balloon model is a biomechanical model of the haemodynamic of the blood system, which includes the transient states.
Automated retinal image analysis
Sanjaya P.M.D. Perera, School of Computing, National
University of Singapore
Diabetic retinopathy is a major cause of blindness in the world. Regular screening and timely intervention can halt or reverse the progression of this disease. Digital retinal imaging technologies have become an integral part of eye screening programs worldwide due to their greater accuracy and repeatability in staging diabetic retinopathy. Existing automated techniques to detect diabetic retinopathy lesions and retinal structures are neither adaptable nor sufficiently sensitive and specific for real-life screening application. This talk presents accurate and robust algorithms for automated detection of hard exudates, retinal vessels, optic disc and macular region. Hard exudates detection algorithm which incorporates domain knowledge has achieved 100% sensitivity and 72% specificity with 543 consecutive digital retinal images. Large retinal vessel detection algorithm and optic disc detection algorithm has achieved above 90% accuracy and finally macular region detection has the ability to classify hard exudates further into macular exudates with 92% sensitivity and 92% specificity.
Non-rigid registration in MRI
mammography
Ek Tsoon Tan, Department of Electrical and Computer
Engineering National University of Singapore
Magnetic resonance imaging (MRI) has been suggested as an alternative to x-ray mammography because of its 3D tomography, better contrast between tissue types, and because it is radiation-free. The use of a contrast agent for highlighting regions with malignant lesions results in an intensity increase between the pre- and post-contrast scans. Image registration is required to capture involuntary patient movement and the non- uniform intensity increases, so as to correctly identify malignant lesions. Recent work in this volume registration task employed rigid and non-rigid models with entropy-based cost functions. The long computational time is the main drawback for entropy-based algorithms.
The talk presents a new adaptive Normalized Mutual Information (NMI) optimization scheme that will significantly reduce the computational requirements. The new scheme makes use of the current histogram to (1) perform a clever prediction of the change introduced by the contrast agent, and (2) adapts the standard deviation of the Parzen window for each intensity level.
Cramer-Rao Lower Bound for parameter
estimation of multidimensional NMR data
ZhiPing Lin, School of Electrical and Electronic
Engineering Nanyang Technological University
Nuclear magnetic resonance (NMR) is one of the two major experimental techniques for determining proteins' 3D structures. One of the key steps in multidimensional NMR data processing is parameter estimation. This talk presents a new method for the calculation of the Fisher information matrix, the inverse of which gives the Cramer-Rao lower bound. Our method is based on a novel concept of derivative system and solutions to certain Lyapunov equations. The techniques are illustrated by a simulation example from NMR spectroscopy.
On fast algorithms to compute
canonical windows for gabor frames
A.J.E.M. Janssen, Philips Research Laboratories, The
Netherlands
We present iterative algorithms, some of which were already known to Feichtinger and Strohmer, for the computation of the canonical tight (gt) and dual (gd) window associated with a Gabor frame (g, a, b). To this end we develop a mechanism for proposing iterative algorithms [involving the current frame operator and (for gt) its inverse] with a desired conver- gence rate. The algorithms so obtained with cubic convergence and using frame operators only (no inverses) are conditionally convergent, requiring a minimal value of the initial frame bound ratio A/B. These minimal values can be estimated by using a sharp form of Kantorovich's inequality.
Tight frames and their symmetries
Shayne Waldron, Dept. of Mathematics, University of
Auckland
Frame representations are useful because they are technically similar to orthogonal expansions (they simply have more terms) and can be constructed to have desirable properties that may be impossible for an orthogonal basis, e.g., in the case of wavelets certain smoothness and small support properties.
Here we show that frames are of interest where the desirable properties are symmetries of the underlying space (which an orthogonal basis cannot express). One important example is orthogonal polynomials of several variables for a weight which has some symmetries. It turns out that there are a finite number of tight frames of n vectors in d dimensions generated by an abelian subgroup of its symmetries. We discuss how this list of so called harmonic frames was calculated using the symbolic algebra package MAGMA, and how to use it.
Recent progress in iteratively
regularized image reconstruction
Martin Hanke-Bourgeois, Johannes-Gutenberg-Universität,
Germany
We survey various options for the regularized reconstruction of blurred and noisy images, given complete information about the blurring operator. The topics we will focus on include preconditioning, in particular multilevel preconditioning, and the possibility of regularization by iteration or by hybrid combinations of the Lanczos method with other regularizing schemes. We shall also briefly comment on the delicate issue of how to incorporate nonnegativity constraints.
A Multigrid technique for restoring
images with Dirichlet boundary conditions
Stefano Serra Capizzano, Dipartimento di Chimica, Fisica, e
Matematica Universita dell'Insubria - Sede di Como
We propose a method of multigrid type which has an optimal computational cost and whose convergence speed is robust both with respect to the size of the problem and to the regularization parameter.
Boundary conditions and fast
deblurring models
Stefano Serra Capizzano, Dipartimento di Chimica, Fisica, e
Matematica Universita dell'Insubria - Sede di Como
Anti-reflecting boundary conditions (AR-BC) for blurring models were recently introduced (see Serra-Capizzano, SISC, to appear): the idea seems promising both from the computational and approximation viewpoint. The key point is that, under certain symmetry conditions, the AR-BC matrices can be essentially simultaneously diagonalized by the (fast) sine transform DST I and, moreover, a C1 continuity at the border is guaranteed in the 1D case.
Here we give more details for the 2D case and we perform extensive numerical simulations which illustrate that the AR-BC can be superior to Dirichlet, periodic and reflective BCs in certain applications.
Applications of 3D digital
technologies in cultural heritage
Hongbin Zha, Center for Information Science, National
Laboratory on Machine Perception, Peking University, China
In the presentation, I will report new progress in our research on applications of 3D digital technologies in heritage digitization and digital museum. The main topics include: 3D modeling of cultural artifacts, relics and sites; digital geometry processing for large heritage models; photorealistic visualization of cultural scenes.
The fast and parallel processing
for bit-plane coding in JPEG2000
Chao Xu, Center for Information Science, National
Laboratory on Machine Perception, Peking University, China
Abstact: In JPEG2000 image compression standard the fractional bit-plane coding is adopted for the context forming for arithmetic coding. The fractional bit-plane coding generates more quality and resolution scalability, while makes more computation difficulty for fast implementation. In this paper, we present a parallel processing for bit-plane coding that reduce the computation time greatly. A preprocessor is proposed to make each bit-plane coding independent for parallel processing. The encoder is divided into multiple modules to analyse, and a method of assignment modules in terms of the statistic of module application is proposed. The parallel processing is suitable for architecture implementation. With increasing about 4 times of circuit resource it can achieve 8 times of speed-up.
Omni-directional vision based motion
detection for multiple human bodies
Hong Liu, Center for Information Science, National
Laboratory on Machine Perception, Peking University, China
Computer vision systems for moving targets tracking are widely used in many applications such as smart surveillance, virtual reality, advanced user interfaces, motion analysis and model-based image coding. One of the most important issues in visual surveillance is to expand the view fields of visual sensors. Since traditional cameras suffer from the problems of having limited visual fields, lose of global visual information, hard to control for active one, we have proposed a new real-time visual system based on omni-directional vision, for detecting and tracking multiple human bodies in indoor environment. First, an omni-directional camera is used to obtain 360º view images of the scene to enlarge the monitored area. Then, omni-directional images are changed into the cylindrical panoramic images. Secondly, an adaptive subtraction method is utilized to improve the robustness for segmenting moving targets in dynamic environments. Moreover, shape and color information are used for tracking and identifying multiple peoples whether they are in groups or separated from each other. Experiments show that the system can track multiple moving human bodies with large view fields in a dynamic environment in real-time. Finally, potential applications and research plan on omni-directional vision will be discussed.
M-band wavelet construction and
compound image compression
Tong Lin, Center for Information Science, National
Laboratory on Machine Perception, Peking University, China
Two parts of work are reported in this talk. One is on the algebraic construction of M-band orthogonal wavelets. A system of constraint equations is obtained for M-band orthonormal filters, and then a solution based on SVD is developed to produce innumerable wavelet bases of given length. Also the property of 2 vanishing moments is integrated into our wavelet construction process, which provides another way to compute 2-regular M-band filter banks. Another part is on compound image compression for real-time computer-generated screen transmission. A block-based lossless coding algorithm is designed for textual and graphical contents, which contains several techniques such as shape-based coding, palette-based coding, run-length coding, and palette reuse. The coded bitstream is fed into a LZW coder for further compression. Then we integrate the lossless algorithm with lossy JPEG into a hybrid image compression scheme. The key is to extract the text and graphics as foreground from photographic pictures within a low complexity constraint. The shape-based coding in our lossless algorithm elegantly provides the intelligence to extract computer-generated text/graphics without efforts.
Medical image series segmentation
based on modified active contour model
Jie Tian, Institute of Automation, Chinese Academy of
Science, National Laboratory of Pattern Recognition, China
Abstract: In this paper, we propose an algorithm for the semiautomatic segmentation of medical image series based on the combination of the live wire algorithm and the active contour model. We modified the traditional live wire algorithm by combining watershed transform and obtain accurate segmentation of one or more slices in a medical image series by the live wire algorithm. Based on the segmentation of previous slices, the computer will segment the nearby slice using the modified active contour model automatically. To make full use of the correlative information between contiguous slices, we introduce a gray-scale model to the boundary points of the active contour model to record the local region characters of the desired object in the segmented slice and replace the external energy of the traditional active contour model with the energy decided by the likelihood of the gray-scale model. Moreover we introduce the active region concept of the snake to improve the segmentation accuracy and reduce the complexity of dynamic program. Experiment shows that our algorithm can obtain the boundary of the desired object from a series of medical images quickly and reliably with only little user intervention.
Wavelet-type expansions
Lasse Borup, Dept. of Mathematical Sciences, Aalborg
University, Denmark
We consider an orthonormal basis for L2(R) consisting of functions that are well localized in the spatial domain and have compact support in the frequency domain. The construction is based on smooth local cosine bases and is inspired by F. Meyer and R. Coifman's brushlets, which are local exponentials in the frequency domain.
We will see that brushlet systems associated with an exponential type partition of the frequency axis, bear some resemblance to wavelet systems. E.g. such a system constitutes an unconditional basis for various function spaces - Lebesgue, Besov, Triebel-Lizorkin, Hardy, BMO - and the norm in these spaces can be expressed in terms of the expansion coefficients.
If instead, the brushlet system is associated with a partition of the frequency axis based on a polynomial rule with a parameter α (0<α≤1) we will see that the system forms an unconditional basis for the α-modulation spaces introduced by P. Gröbner.
Gabor analysis, Rieffel induction
and Feichtinger's algebra as a link
Franz Luef, NuHAG, Dept. of Mathematics, University of of
Vienna
Frames and flexibility
Ole Christensen, Dept. of Mathematics, Technical University
of Denmark
The increased flexibility (compared to orthonormal bases) is often an argument for using frames. However, in most cases we also want our frames to have some structure, and there are cases where this additional constraint limits (or removes) the freedom. For this reason we seek to extend classical frame theory by allowing duals belonging to a different space than the frame.
Given a frame for a subspace W of a Hilbert space H, we characterize the set of oblique dual frame sequences (i.e., dual frame sequences that are not constrained to lie in W). We then consider frame sequences in shift invariant spaces, and characterize the translation invariant oblique dual frame sequences. For a given translation invariant frame sequence an easily verifiable condition on another shift-invariant frame sequence implies that its closed linear span contains a generator for a translation invariant dual of the frame sequence we start with; in particular, this result shows that classical frame theory does not provide any freedom if we want the dual to be translation invariant. In the case of frame sequences generated by B-splines we can use our approach to obtain dual generators of arbitrary regularity
Camera calibration and pose
determination from N points
Yihong Wu, National Laboratory of Pattern Recognition,
Institute of Automation, Chinese Academy of Sciences
Perspective-N-Point camera calibration and pose determination, simply called PNP problem, has attracted lot of attention in the literature. PNP problem has different definitions, and different definition usually implies different set of solutions, different computational complexity, and different robustness.
When N<3, the PNP problem is under constrained, and When N>=6 the PNP problem can be linearly determined for the intrinsic parameters and pose parameters. When N=3,4,5, the constraints from N points are not enough to determine all the intrinsic parameters and pose parameters. So, usually, the literatures assume that the intrinsic parameters are known, then determine the camera pose; or determine the intrinsic and pose parameters from prior knowledge on the intrinsic parameters.
In this work, with known intrinsic parameters, we investigate the PNP problem for N=3,4,5 from both geometric and algebraic standpoints, and has the following contributions: Firstly, we formally proved that the PNP problem under distance-based definition is equivalent to the PnP problem under orthogonal-transformation-based definition when N>3, and is equivalent to the PnP problem under rotation-transformation-based definition when N=3. In other words, if the rotation matrix in perspective matrix is relaxed to an orthogonal matrix, then the distance-based definition and the transformation based definition become equivalent when N>3. Secondly, we introduce a depth-ratio based technique to solve PnP problem. This technique is shown to be advantageous over the traditional techniques of either directly determining the distances or transformation matrix. Thirdly, from the geometrical point of view, we obtained the upper bounds of the PnP problem under different definitions, and provided some insights into the fact that the different bounds are generally associated with different definitions. Fourthly, a construction of multiple solutions is presented for P3P problem. Lastly, the degenerated cases, i.e., the coplanar control points, or collinear control points, are discussed. Surprisingly enough, it is shown that if all the control points are collinear, the PnP problem under distance-based definition has a unique solution, but the PnP problem under transformation-based definition is determined only up to one free parameter.
Content-based visual information
retrieval
Yu Jin Zhang, Dept. of Electronic Engineering, Tsinghua
University, China
While advances in compression algorithms have relaxed the storage and transmission requirements to some extent, the large volume of images and videos makes it difficult for a user to browse through the entire database. On the other side, when such a collection is available or accessible, the question asked by a user is often how a particular image or a clip of video is located. In the last ten years, researches on content-based image and video retrieval have made a number of progresses and provided some suitable ways to answer efficiently the above question. This talk will be based on a recent book “Content-based Visual Information Retrieval”. Using the information collected for writing this book as well as the research experiments and results that supply suitable materials for this book, a general overview in this research direction will be introduced, different techniques for querying and retrieving image as well as for organizing and searching video will be described. In addition, some existing problems and further research trends will be discussed.
A Quasi-Wavelet algorithm for
second kind boundary integral equations
Han-lin Chen, Institute of Mathematics, Academia Sinica and
Silong Peng, National Asia Design Engineering Center, Chinese
Academy of Science
In solving integral equations with a logarithmic kernel, we combine the Galerkin Approximation with periodic quasi-wavelet (PQW). We develop an algorithm for solving the integral equations with only O(N log N) arithmetic operations where N is the number of knots. We also proved that the Galerkin approximation has a polyno- mial rate of convergence.
Spectral radii of refinement and
subdivision operators
Victor Didenko, Faculty of Science, Universiti Brunei
Darussalam
The spectral radii of refinement and subdivision operators can be estimated by using norms of their symbols. In several cases the exact value of the spectral radius is found.
The construction of wavelets and
its some applications to pattern recognition
Daren Huang, Sun Yat-sen University
In this paper, the construction of wavelets, especially multiband wavelets, and their corresponding properties are discussed. As wavelet applications, multiband wavelets are used to classify textures successfully; an algorithm for image recognition, such as face images, is developed based on nonlinear wavelets. Also, researches on the application of wavelets to similar numeral discrimination are presented.
Radial basis, radial basis interpolation and meshless
method
Zongmin Wu, Dept. of Mathematics, Fudan University
This talk will introduce the radial basis function, which is composed of linear combination of shifts of radial function Φ(||x||). Radial basis interpolation method and related topics is reviewed, especially the method, how to interpolate the linear functional data is introduced. The radial basis interpolations scheme for linear functional data will be applied to solve linear partial differential equation as a numerical meshless method. Existence, uniqueness as well as the convergence and related topics for the method are discussed.
Convergence rates of subdivsion
schemes associated with nonhomogeneous refinement equation
Song Li, Zhejiang University
On the spectrums of frame
multiresolution analyses
Hong Oh Kim, Division of Applied Mathematics, KAIST
We characterize the spectrum of the 'central' space of an FMRA and then give a new condition for an FMRA to admit a single wavelet solely in terms of the spectrum of an FMRA. This improves the results prevously obtained by Benedetto and Treiber and also by us. Our methods and results are applied to the problem of the 'containments' of FMRAs in MRAs. We first prove that any FMRA is always contained in an MRA, and then we characterize those MRAs that contain 'genuine' FMRAs in terms the unique masks of the MRAs and the spectrums of the central spaces of the FMRAs to be contained.
Adaptive short time Fourier
transform for Whale call classification
Zhenyong Lin, Temasek Laboratories
Short-time Fourier transform is a classic time-frequency analysis method for non-stationary signal processing and representation. However, since its time and frequency resolution is fixed, it is not adaptive to signals. In this report, we developed an adaptive short-time Fourier transform algorithm, and use it as an analysis tool to underwater whale call classification. Experiments show that our method can achieve excellent results.
Dual Gramian analysis
Zuowei Shen, Dept. of Mathematics, National University of
Singapore
The dual Gramian analysis has been used in the study of the frame properties of shift invariant systems. It allows us to decompose the frame operator into a collection of simpler operators (fibers) in the Fourier domain. Each one of the `fiber’ operators acts from a sequence space to the same sequence space and its matrix representation can be explicitly described in terms of the Fourier transforms of the generators of the shift invariant system. Application to the Gabor systems which are shift invariant shows the power of the analysis. However, it cannot be directly applied to many other systems such as the wavelet systems, which are not shift invariant. This leads us to consider the dual Gramian analysis in a more general setting, i.e. general shift invariant systems which include wavelet system as a special case. In this talk, I will give the development and the recent results on the dual Gramian analysis.
A Panoramic View on Gabor Analysis
(from linear algebra to pseudo-differential operators)
Hans G. Feichtinger, Dept. of Mathematics, University of
Vienna, Austria
It is the purpose of this series of lectures (the duration and choice of specific topics will be flexible, depending on the audience) to point the relevance of Banach frames and Riesz projection bases in the context of Gabor analysis, and to provide background on the importance of certain Banach spaces of functions (called Wiener amalgam spaces) in the treatment of families of function spaces (so-called modulation spaces) described by the time-frequency behaviour of their elements. These spaces in turn are relevant for the description of the behaviour of various kinds of operators, in particular slowly time varying systems.
Rough outline:
A) From linear algebra to Gabor analysis over finite Abelian groups (generating systems, frames, pseudo-inverse and frames, Gram matrix and biorthogonal systems; specific properties of coherent systems; redundancy; algebraic properties of Gabor systems). Introductory part (avoiding questions of convergence and continuity)
B) Continuous transforms (in particular STFT), sampling, the role of Wiener amalgam spaces and their basic properties, modulation spaces defined by means of the STFT (1-2 hours)
C) Fundamental properties of Gabor-Weyl-Heisenberg systems (Janssen representation, fundamental identity, adjoint TF-lattice, Ron-Shen principle, etc.) and the role of modulation spaces in the description of these facts; in particular the usefulness of the Gelfand triple (S_0,L_2,S_0') (Feichtinger's algebra and its dual). (1 hour)
D) Description of operators using time-frequency concepts (e.g. the Kohn-Nirenberg symbol resp. the spreading function), indications on pseudo-differential operators (Heil, Groechenig) in the context of time-frequency analysis (1+ hour)
As time permits we may come also to a discussion of the following topics: E) Possible continuation (rather for discussions): irregular Gabor families, questions of excess and redundancy, changing the lattice constants, automatic continuity properties of the frame operator and much more
HINT: final talk on Gabor Multipliers will make use of many of the results described in this tutorial session.
A theory of Gabor multipliers
Hans G. Feichtinger, Dept. of Mathematics, University of
Vienna, Austria
Gabor multipliers are linear operators which arise by pointwise multiplication of Gabor coefficients of a function/distribution by a certain sequence of real numbers (over the TF-lattice in use). We will emphasize questions of the following type:
- what are the mapping properties of such operators (e.g. in term of modulation spaces)
- what about the uniqueness of the representation of a Gabor multiplier
- approximation properties of general mappings by Gabor multipiers
- similarity of Gabor multipliers using similar lattices
Gabor Deconvolution: the
recovery of seismic reflectivity in an attenuating medium
Gary Margrave, Dept. of Geology and Geophysics, The
University of Calgary
Seismic wave propagation is associated with a progressive loss of frequency content as the wave propagates. This means that the reflected waveforms recorded at the earth's surface form a seismogram with nonstationary spectral character. While Wiener deconvolution was designed to sharpen these reflections by estimating and inverting their waveform, its inherent stationarity means that it can only succeed in a limited and local sense. We present an extension of the Wiener process that is accomplished in the Gabor transform domain. Using a pseudodifferential operator model for the attenuation process, we show that Gabor deconvolution can estimate and invert a nonstationary waveform with surprising success. In essence, we use the Gabor transform to accomplish an approximate factorization of the pseudodifferential operator. The resulting reflectivity estimates have greater resolution than can be achieved with stationary processes. Tests on real seismic data have produced excellent images. In a controlled experiment, in which a seismic wavefield was measured simultaneously in a borehole and on the earth's surface, we find that the wavforms estimated in the borehole closely match those estimated by Gabor deconvolution on the surface data.
The representation of linear
operators by Gabor multipliers
Michael P. Lamoureux, Dept. Mathematics and Statistics,
University of Calgary
For a given pair of analysis and synthesis window, we examine what class of linear operators can be represented as a Gabor multiplier, and their relationship to the symbol of a Gabor multiplier. The notion of a compatible window pair is introduced, which includes Gaussians, as well as other examples of smooth windows. A complete answer to the representation question is obtained for compatible windows. These results are used to justified numerical techniques in seismic imaging that use Gabor multipliers to represent non-stationary filters and wavefield extrapolators.
Filter approximation by Wavelet
filter banks
Silong Peng, National Asia Design Engineering Center,
Chinese Academy of Science
In many applications, we need to construct signal adaptive filters, especially adaptive wavelet filters. It mainly leads to an optimal problem which is difficult to be solved. For real time image processing, it is better to have a fast algorithm. In this paper, we give a direct method to approximate a given filter with wavelet filter banks. Experiments show the excellent performance.
Content based image data
retrieval and classification using nonnegative encoding
Robert Plemmons, Dept. of Maths & Computer Science, Wake
Forest University, USA
This study introduces novel clustering methodology for image and sensor data retrieval, analysis and classification. The methodology is based upon encoding the data using low rank nonnegative matrix factorization algorithms to preserve natural data nonnegativity and thus avoid subtractive basis vector and encoding interactions present in methodologies such as principal component analysis. Some existing nonnegative matrix factorization techniques are reviewed and some new ones are proposed. Numerical experiments are reported using iris image data in biometric identification systems, phase screen correlation data in atmospheric imaging applications, and spectral data for identification and classification of orbital space objects.
General uncertainty principles for
Hilbert spaces
Say Song Goh, Dept. of Mathematics, National University of
Singapore
The classical Heisenberg uncertainty principle plays an important role in time-frequency analysis of signals. This inequality could be generalized and formulated under an abstract mathematical setting. In this talk, we shall present a general uncertainty inequality bounding the commutator of two linear operators acting on a Hilbert space, where no additional assumptions are made on the two operators. The Heisenberg uncertainty principle and the periodic uncertainty principle proposed by Breitenberger are special cases of this general inequality. We shall also discuss about a characterization of equality in the general inequality, and asymptotic equality in the absence of equality for specific examples. Another issue of interest that will be highlighted is the description of geometric regions formed by quantities appearing in the inequality when the two operators involved are self-adjoint. Finally, we shall extend the general uncertainty principle to handle the multivariate case and also provide results on equality and asymptotic equality. Frequent references to the settings of the Heisenberg uncertainty principle and the periodic uncertainty principle will be made throughout the talk as illustrations. This talk is based on collaborations with Charles A. Micchelli and Tim N. T. Goodman.
Loop groups, conjugate quadrature
filters and wavelet approximation
Wayne M. Lawton, Dept. of Mathematics, National University
of Singapore
Orthonormal wavelet bases associated to a multiresolution analysis are constructed from sequences c whose Fourier transforms C correspond to matrices [C(z) zC(-z); -zC(-z) C(z)] that map the unit circle into the special unitary group. The set of such functions, under pointwise multiplication, forms an infinite dimensional loop group. Smooth wavelets arise from C that admit divisors having the form (1 + z) while compactly supported wavelets arise from C that are Laurent polynomials and this subgroup is dense by a classical approximation result that is based on Trotter’s formula. We extend this result to show that every wavelet can be approximated, in appropriate Sobelev Spaces, by a sequence of compactly supported wavelets. We obtain this existence by combining methods and results from the theory of loop groups with a classical result from alegrabic topology and an extension of a recent approximation theoretic result concerning Bezout identities.
An integrated optical/digital
approach for improved image restoration
Robert J. Plemmons, Wake Forest University
A novel and successful optical/digital approach for removing certain aberrations in optical imaging systems involves placing an optical mask between an image-recording device and an object to encode the wave front phase before the image is recorded, followed by digital image restoration to decode the phase. We have shown that when appropriately engineered, such an optical mask can also act as a form of preconditioner for certain types of image restoration algorithms. Moreover it can boost information in the signal before it is recorded well above the noise level, leveraging digital restorations of very high quality. In this talk, we 1) examine the influence that a phase mask has on the incoming signal and how it subsequently affects the performance of restoration algorithms, and 2) explore the design of optical masks, a difficult nonlinear optimization problem with multiple design parameters, for removing certain aberrations and for maximizing information content in recorded images. The talk involves joint work with Paul Pauca, Sudhakar Prasad, Todd Torgersen, and Joe van der Gracht, on Pupil Phase Engineering.
Preconditioning regularized least
squares problems arising from high-resolution image
reconstruction from low-resolution frames
Furong Lin, Dept. of Mathematics, Shantou University, China
In this paper, we study the problem of reconstructing a high- resolution image from multiple undersampled, shifted, degraded frames with subpixel displacement errors from multisensors. Preconditioned conjugate gradient methods with cosine transform based precondition- ers and incomplete factorization based preconditioners are applied to solve this image reconstruction problem. Numerical examples are given to demonstrate the effciency of these preconditioners. We find that cosine transform based preconditioners are e®ective when the num- ber of shifted low-resolution frames are large, but are less effective when the number is small. However, incomplete factorization based preconditioners work quite well independent of the number of shifted low-resolution frames.
Wavelet algorithms for high
resolution image reconstruction
Zuowei Shen, Dept. Mathematics, National University of
Singapore
High-resolution image reconstruction refers to the reconstruction of high-resolution images from multiple low-resolution, shifted, degraded samples of a true image. In this talk, we give a method based on the wavelet analysis. By expressing the true image as a function, we derive iterative algorithms which recover the function completely from the given low-resolution functions. These algorithms decompose the function obtained from the previous iteration into different frequency components in the wavelet transform domain via a redundant or irredundant system and add them into the new iterate to improve the approximation. We apply wavelet (packet) thresholding methods to denoise the function obtained in the previous step before adding it into the new iterate. Our numerical results show that the reconstructed images from our wavelet algorithms are better than that from the Tikhonov least-squares approach. Some other applications of this method are also discussed.
Scalable multimedia communication
over heterogeneous network
Fuchun Shang, Temasek Laboratories, Singapore
In heterogeneous network environment, the hardware capabilities of network devices to consume multimedia information are very different. For efficient utilization of system resource, it is important to transmit the just enough information that the receiving end can handle. Issues of scalable media compression, media stream organization and media quality negotiation and control in a multimedia communication system that can provide different media quality streams to different users at both codec and system level will be presented.
A numerical method for maximum
entropy deconvolution
Jian-Guo Liu, Dept. of Mathematics, University of Maryland
In this talk, I will discuss some numerical methods for image deconvolution based on maximum entropy. Numerical issues such as efficiency, reliability in designing of this kind of the numerical methods will discussed. Comparison with other kind deconvolution technologies will be presented by using examples in image deconvolution in the surface physics.
Research of the centre for
wavelets, approximation and information processing
Say Song Goh, Dept. of Mathematics, National University of
Singapore
The Centre for Wavelets, Approximation and Information Processing of the National University of Singapore is a research centre of the Faculty of Science in the Department of Mathematics. It is a multidisciplinary research centre that emphasizes the synergy of mathematics, engineering and computer science. Its research activities are on mathematical signal, image and information processing, as well as their analysis and understanding. In this talk, we shall provide an overview of the centre and highlight its various areas of research. Some of the centre’s research capabilities include image, document image and video compression, video summarization, denoising and resolution enhancement, underwater signal processing and recognition, and signal identification and classification.
Image restoration for historical
documents using directional wavelet transform
Tao Xia, CWAIP, National University of Singapore
In this talk we will introduce a novel algorithm to clean up a large collection of historical handwritten documents. Due to the seepage of ink over long period of storage, the front page of each document has been severely marred by the reverse side writing. Earlier attempts have been made to match both sides of a page to identify the offending strokes to eliminate them with the aid of a wavelet transform. Perfect matching, however, is difficult due to document skews, differing resolutions, inadvertently missing out reverse side and warped pages during image capture. A new approach is proposed to avoid double side mapping by using a directional wavelet transform to distinguish the foreground and reverse side strokes much better than the conventional wavelet transform. Experiments have shown that the algorithm enhances the readability of each document significantly without the mapping with its reverse side.
FOI/ROI video compression
Li Hui, CWAIP, National University of Singapore
In video compression techniques, frames-of-interest (FOI) and region-of-interest (ROI) could be addressed for more attention. Thus, high priority is given to FOI or ROI by allocating more bits than others. It can obtain higher subjective video quality at the same rate, by sacrificing the quality of the other parts. We developed new FOI/ROI algorithms for video compression. Simulation results show excellent performance.
Multiwavelets, diamond search, and
multi-scalable video codec platform
Jo-Yew Tham, Centre for Industrial Mathematics, National
University of Singapore
The recent explosion in digital video storage and delivery has presented strong motivations for high performance video compression solutions. Coupling this with the growing heterogeneity of user and network requirements, there arises a pressing need for a flexible video compression framework that can support a “generate once, scale many” concept. This talk presents an overview of a highly scalable video compression platform, covering the design and application of good multiwavelet filters, a novel diamond search algorithm for fast block-based motion compensation, and a multi-scalable video codec architecture that supports simultaneous video scalability in terms of bit rate, distortion, frame rate, color, spatial resolution, and computational complexity within a single compressed video bit stream.
Wavelet-Galerkin method and natural
boundary integral equations
Wei Lin, Dept. of Mathematics, Zhongshan University
In this paper we apply the wavelet- Galerkin method to numerical solutions for Harmonic Equations, Biharmonic Equations, Stokes Equations, Elasticity Equations and Helmholtz Equations respectively. All of them are reduced to the natural boundary integral equations with the strong-singular kernel. Hermite wavelets, Shannon wavelets and spline wavelets are utilized.
Fingerprint recognition technology
Jufu Feng, Center for Information Science, National
Laboratory on Machine Perception, Peking University, China
In this talk, I will introduce the fingerprint history and automated fingerprint identification system(AFIS). Ancien people were aware of the individuality of fingerprint. From the late sixteenth centurty to the late ninteenth century, a lot of findings established the foundation of morden fingerprint recognition. In the early 1960s, automated fingerprint identification system(AFIS) was developed. Since then, AFIS has benn used worldwide.
Wavelet decompositions and
non-linear approximations
Dung Dinh, Information Technology Institute, Vietnam
National University
In this talk, we will discuss the following questions:
- Nonlinear approximations of functions by sets of finite cardinality and the classical entropy number measuring their optimality,
- Nonlinear approximations of functions by sets of finite pseudo-dimension and the related nonlinear widths measuring their optimality, and
- Constructions and use of wavelet decompositions for constructing asymptotically optimal methods for these nonlinear approximation characterizations
Tiles, self-affine sets and scaling
functions
Ka Sing Lau, Dept. of Mathematics, The Chinese University
of Hong Kong
Scaling functions are used to construct wavelets. Such a function is gererated by the subdivsion scheme. The most studied case is for scaling 2 and with integral translations; the multivariate case is more complicated. In this talk we will consider the support of such functions which can be considered, more generally, as the invariant sets of iterated function systems with expanding integral dilation matrices and integral translations; these are self-affine sets. A special case is the self-affine tiles. We will discuss the geometry of such sets and the related properties.
A wavelet set construction and
tight frames
Songkiat Sumetkijakan, Chulalongkorn University, Thailand
Since wavelet sets were introduced in the first existence proof of multidimensional single dyadic orthonormal wavelets by Dai, Larson, and Speegle, many examples and a few general constructions have been given. An intuitive wavelet set construction is due to Benedetto and Leon. Starting from a set K_0 and a map T with some specified properties, it is an iterative construction of sets K_n that approach a wavelet set. Though the scope of this construction has some limitations, we extend it to a more general setting. In particular, the construction can produce a multidimensional Journ'e wavelet set, the wedding cake set, and a wavelet set with only two connected components. In addition, each finite iteration of the construction is proved to give rise to a tight frame wavelet set.
Wavelet frames: theory and
constructions
Zuowei Shen, Dept. Mathematics, National University of
Singapore
This talk is about wavelet frames. The redundant representation offered by wavelet frames has already been put to good use for signal denoising, and is currently explored for image compression. We restrict our attention to wavelet frames constructed via multiresolution analysis, because this guarantees the existence of fast implementation algorithms. We shall explore the `power of redundancy' to establish general principles and specific algorithms for constructing framelets and tight framelets. In particular, we shall give several systematic constructions of spline and pseudo-spline tight frames and symmetric bi-frames with short supports and high approximation orders. Several explicit examples are discussed. This talk is based on joint work with Ingrid Daubechies, Bin Han and Amos Ron.
Pointwise properties of bounded refinable function
vectors
Di-Rong Chen, Dept. of Applied Mathematics, Beijing
University of Aeronautics and Astronautics
Eigenvalues and Biorthogonal
Eigensystems of scaling operators
Seng Luan Lee, Dept. of Mathematics, National University of
Singapore
Approximation and interpolation by
radial basis function on Sobolev space
Jungho Yoon, Dept. of mathematics, Ewha W. University, S.
Korea
Approximation by translates of suitable radial basis functions is an important approach towards solving the (multivariate) scattered data problem. Its strengths are as follows:
- it facilitates the evaluation of the approximant;
- the accuracy of approximation is usually very satisfactory provided the approximand f is reasonably smooth;
- there is enough flexibility in the choice of basis functions.
In this talk, we discuss the approximation power of radial basis function interpolation and approximation on Sobolev space.
An orthogonal splines approach to
periodic wavelet frames
Say Song Goh, Dept. of Mathematics, National University of
Singapore
Wavelet frames are of much current interest in wavelet research. They contain redundancy and could provide more flexibility in some applications. In this talk, we shall present an approach based on orthogonal splines for the study of frame multiresolution analyses and wavelet frames of periodic functions. Results on frames for shift-invariant subspaces of periodic functions will be obtained in terms of orthogonal splines. We shall also discuss about equivalent conditions for the existence of a wavelet frame starting from a frame multiresolution analysis, and an algorithmic construction when such a wavelet frame exists. Trigonometric polynomial frames will be used to illustrate the ideas presented.
Multiwavelets associated with
countable groups of unitary operators in Hilbert spaces
Wai Shing Tang, Dept. of Mathematics, National University
of Singapore
We give a characterization of biorthogonality among Riesz multiwavelets in terms of certain invariant properties of their associated core spaces. A large family of non-biorthogonal Riesz multiwavelets is exhibited. We also discuss some results on linear perturbation of orthonormal multiwavelets. This is joint work with David Larson and Eric Weber.
Singularity and Instantaneous
Frequency Detection from Modulus Maxima of Continuous Wavelet
Transforms
Wen-Liang Hwang, Institute of Information Sciences Academia
Sinica
Many problems in signal processing, image processing, and pattern recognitions use wavelet transform to detection local features. Among them, the most important features may be singularity and instantaneous frequency. Singularity measures the local irregularity of a signal and instantaneous frequency measures the local dominant variations. Singularity can be detected from the modulus maxima of a real-valued wavelet, while the instantaneous frequency can be obtained from that of complex-valued wavelets. We proof that isolated singularity can be detected from modulus maxima of complex-valued wavelets. Thus, using complex-valued wavelet transform, one is about to simultaneously detection isolated singularity and instantaneous frequency from its modulus. We will also show applications in which shape are derived from texture variations measured by instantaneous frequencies in textured images.
What's Math got to do with it ?
Mathematics at the frontiers of sciences and technology
Tony Chan, Department of Mathematics, University of
California, USA
Mathematics is probably the least understood (and appreciated) among the hard sciences by the general public. Its public image is probably a mixture of inscrutability, fear and irrelevance to everyday life. And this despite that most adults have been exposed to many years of mathematics during their education. In fact, mathematics is at the foundation of our highly technological society. It is at the core of much of the current information technology revolution and many predict that it will play an equally important role in the burgeoning bio-medical revolution ushered in by the advent of modern genetics.
So why is Mathematics having such a hard time getting the message across to the public? The cynics will say it is because of the abysmal and often traumatic experience many people experienced in mathematics classes in school. It is true that the rigor, the abstraction, and the scope of mathematics is quite challenging for many students. And much of frontier research mathematics is close to impossible for outsiders to understand. However, the APPLICATION of mathematics can be found in almost all walks of life, and often in the most unexpected places. My conviction is that if the public is more aware of the "usefulness" and "ubiquity" of mathematics, not only will the public image of mathematics improve, but it'll also provide the public with the necessary understanding to make informed political decisions regarding how society should invest in its technological future.
In this talk, I'll provide some examples of interesting applications of frontier research mathematics in areas that are quite close to everyday life. Examples include the movies, the stock market, the internet, medicine, communication, etc.
Mathematics in the real world and
the fake world
Stanley Osher, University of California, Los Angeles, USA
With the advent of the computer we can now develop algorithms that perform incredible tasks-special effects in Hollywood, catching bad guys on video, predicting all kinds of natural and unnatural phenomena. A common theme in these algorithms is rather elementary geometry. In this talk I'll discuss geometric algorithms and their applications in every day life.
Impulse noise removal by median-type
noise detector and edge-preserving regularization
Chung-Wa Ho, Department of Mathematics, The Chinese
University of Hong Kong
This paper proposes a two-phase scheme for impulsive noise removal. In the first phase, an adaptive median filter is used to identify the noise candidates. In the second phase, the image is restored by an edge-preserving regularization method that applies only to the noise candidates. In terms of edge preserving and noise suppression, our restored images are significantly better than those restored by using just nonlinear filters or edge-preserving regularization only.
The numerical algorithm for an
inverse problem in optical mammography
Jerry Yin-Tzer Shih, Department of Medical Imaging
Technology, Chung Shan Medical University
We discuss the implementation of a finite element algorithm with C1 Elements for solving a coupled system of generalized biharmonic type equations related to a certain inverse problem. We consider both direct and preconditioned conjugate gradient methods for rapid solution of the resulting rather large linear system and our development of an efficient preconditioner.
Super-resolution image restoration
from blurred low-resolution images
Andy Chin Ko Yau, Department of Mathematics, The Chinese
University of Hong Kong
Latest results in image
superresolution
Nirmal Bose, Pennsylvania State University, USA
The wavelet superresolution algorithm proposed by Nguyen et al in 2000 ignored the effects of using different choices of mother wavelets and scaling functions. In their work, only the Daubechies wavelet and scaling function were applied and tested. Here, a detailed comparison of the desirable properties in superresolution of several finitely supported scaling function and wavelet families is given. Second, adaptation to nonsmooth domains, irregularly sampled data, and weighted measures is considered. Third, a comparison in performance, features, and constraints of several superresolution algorithms that have been popularized during the last decade is provided. Finally, problems to be overcome are summarized.
Non smooth cost-functions in
image and signal reconstruction
Mila Nikolova, Centre de Mathematiques et de Leurs
Applications CMLA (CNRS UMR 8536) ENS de Cachan, France
We consdier the recovery of an image or a signal x*, based on data y, by minimizing a cost function of the form F(x,y)=D(x,y)+c R(x), where D is a data-fidelity term, R is a regularization term and c>0 is a parameter. Examples of applications are image restoration, segmentation, motion estimation, color reproduction, optical imaging, tomography, seismic and nuclear imaging. Classical ways to construct cost-functions F are based on calculus of variations or on probabilistic considerations. In the past, different heuristics have been adapted to specify cost-functions for different applications. Instead, we analyze the properties of minimizers x* as an implicit function of both the data y and the shape of the function F. In this talk, we focus on the smoothness of the cost function F. Points of interest are the recovery of homogeneous regions and edges, and the processing of outliers and impulse noise.
(a) Non-smooth regularization to recover strongly homogeneous regions
Regularization R accounts for priors on x such as smoothness and other properties. Usually R is the sum of terms of the form f(||g_i x||) where g_i are linear operators which yield the differences between neighboring samples in x and f is a potential function. We show that typically, the local minimizers x* of F(.,y) satisfy g_i x*=0 for numerous indexes i. So, if g_i yield first-order differences, x* involves constant regions. This explains the stair-casing effect observed in total variation methods. If g_i yield second-order differences, x* involves planar regions, etc. We call such regions strongly homogeneous. This is a striking property, both visually and mathematically. In comparison, such a behavior does not occur if R is smooth.
(b) Non-smooth data-fidelity to satisfy exactly a certin number of the data entries
Data-fidelity D is generally a smooth function. Non-smooth data-fidelity terms are avoided in image processing. We focus on functions D combining terms of the form d(a_i x-y_i) where a_i are linear operators modelling the data acquisition, and d is a function which is non-smooth at zero. We show that typically, the local minimizers x* of F(.,y) fit exactly a certain number of the data entries: there are many indexes i for which a_i x*=y_i. This is a strong mathematical property which produces a surprising visual effect. Based on it, we construct cost-functions allowing outliers and impulse noise to be detected and selectively smoothed.
All theoretical results are illustrated using various numerical experiments in the context of practical image and signal reconstruction problems.
Analysis of half-quadratic
minimization methods for signal and image recovery
Mila Nikolova, Centre de Mathematiques et de Leurs
Applications CMLA (CNRS UMR 8536) ENS de Cachan, France
We address the minimization of regularized convex cost functions which are customarily used for edge-preserving restoration and reconstruction of signals and images. In order to accelerate computation, multiplicative and additive half-quadratic reformulation of the original cost-function have been pioneered in Geman & Reynolds (1992) and Geman & Yang (1995). The alternate minimization of the resultant (augmented) cost-functions has a simple explicit form. Our goal is to provide a systematic analysis of the convergence rate achieved by each one of these methods. We show that the number of iterations required for convergence is quite smaller for the multiplicative form than for the additive form. However, the computational cost of each iteration is much higher for the multiplicative form than for the additive form. The global assessment is that minimization using the additive form of half-quadratic regularization is faster than using the multiplicative form. When the additive form is applicable, it is hence recommended. Extensive experiments demonstrate that both methods are substantially faster than the standard Matlab routines. (joint work with Michael Ng, University of Hong Kong)
Structured matrix computation and
image recovery applications
Michael Ng, Dept. of Mathematics, University of Hong Kong
In this talk, we address some structured matrix computation issues related to image recovery applications:
- the multiplicative and the additive forms in the minimization of regularized convex cost functions which are customarily used for edge-preserving restoration and reconstruction of signals and images;
- the factorized banded inverse preconditioners for matrices with Toeplitz structure arising in nonlinear image restoration applications.
- the preconditioning regularized least squares problems arising from high-resolution image reconstruction from low-resolution frames.
Data hiding - theory and
applications
Pierre Moulin, Dept. of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
Nasir Memon, Computer Science Dept., Polytechnic University,
USA
In the first part of the tutorial we will look at applications of data hiding. Specifically, we look at what mechanisms could be used to securely realize these applications. We will examine the following four applications (50 minute sessions each):
- Ownership assertion: Basic framework. Invertibility attack and copy attack. Countering invertibility attack. Protocol for secure ownership assertion. Zero knowledge protocols.
- Authentication: Basic framework. Attacks. Key management problem. Distortion bounded authentication.
- Steganography: Review of techniques. Steganalysis techniques. Universal steganalysis. Notions of steganography capacity and security. Discussion on the future of steganography.
- Copy protection: Basic framework. Attacks. Review of data hiding based copy protection mechanisms in consumer appliances and discussion of their security.
In the second part of this tutorial we will present some recent approaches to modeling watermarking and data hiding as communication problems. We first overview the watermarking problem (low payload) and show how it can be formulated as a problem of shaping signal statistics. We further describe how several popular watermarking techniques fit into this model and describe their performance. We also review the data hiding problem (high payload) and reduce it to a channel coding problem with side information. The unifying theme is that watermarking algorithms can (should) be based on fundamentals of detection theory, estimation theory, game theory, and information theory in general. The second part will be organized into five 50 minute sessions as follows:
- Early Work: spread-spectrum techniques and LSB techniques
- Binning schemes; modern quantization-based codes: ideas and basic constructions
- Performance analysis for watermarking systems: error probabilities
- Data Hiding: relation to communication with side information, capacity analysis, random binning, application to images.
- Advanced topics: desynchronization attacks, sensitivity attacks, steganography
Wavelet algorithms for
high-resolution image reconstruction
Raymond Chan, Dept. of Mathematics, Chinese University
of Hong Kong
High-resolution image reconstruction refers to the reconstruction of high-resolution images from multiple low-resolution, shifted, degraded samples of a true image. In this talk, we analyze this problem from the wavelet point of view. By expressing the true image as a function in L2( R2), we derive iterative algorithms which recover the function completely in the L2 sense from the given low-resolution functions. These algorithms decompose the function obtained from the previous iteration into different frequency components in the wavelet transform domain and add them into the new iterate to improve the approximation. We apply wavelet (packet) thresholding methods to denoise the function obtained in the previous step before adding it into the new iterate. Our numerical results show that the reconstructed images from our wavelet algorithms are better than that from the Tikhonov least-squares approach.
Algorithms for association rules
Markus Hegland Mathematical Sciences Institute, Australian
National University
Association rules are "if-then rules" with two measures which quantify the support and confidence of the rule for a given data set. Having their origin in market basked analysis, association rules are now one of the most popular tools in data mining. This popularity is to a large part due to the availability of efficient algorithms following from the development of the Apriori algorithm.
In these lectures we will introduce basic concepts of association rule discovery including support, confidence, interestingness, the apriori property, and hierarchical and quantitative association rules. The core of the lectures consists of a review of the most important algorithms for association rule discovery. Some familiarity with concepts like predicates, probability, expectation and random variables is assumed.
Domain decomposition methods for
image processing
Shiu-Hong Liu, Dept. of Mathematics, University of
Manitoba, Canada
We investigate the application of domain decomposition methods for nonlinear parabolic PDEs arising from a combination of schemes to denoise digital images. We initially apply the mean curvature flow equation to annihilate salt and pepper noise. Then we apply a Perona--Malik type scheme to remove additive Gaussian noise. At each time step, we employ the Schwarz alternating method to solve a linear system of equations. Some numerical examples illustrate the efficiency of the method.
Wavelet adaptation for hybrid
wavelet-large margin classifiers
Julia Neumann, Dept. of Mathematics & Computer Science,
University of Mannheim, Germany
Hybrid wavelet-large margin classifiers have recently proven to solve difficult signal classification problems in cases where merely using a large margin classifier like, e.g., the Support Vector Machine may fail. In our case, we investigate the classification of electrophysiological signals. The features for our hybrid classifier are selected from the outputs of all orthonormal filter banks of fixed length with respect to criteria measuring class separability and generalisation error.
We evaluate a range of such adaptation criteria to perform feature selection for hybrid wavelet – large margin classifiers. The two main points we focus on are (i) approximation of the radius-margin error bound as the ultimate criterion for the target classifier, and (ii) computational costs of the approximating criterion for feature selection relative to those for the classifier design.
We show that by virtue of the adaptivity of the filter bank, criteria which are more efficient than computing the radius-margin are sufficient for wavelet adaptation and, hence, feature selection.
Another important issue for the extraction of signal features based on wavelet filtering is translation invariance. In order to provide a library of decimated shift insensitive perfect reconstruction wavelet transforms, we propose the use of complex wavelets defined in the frequency domain. These enable us to select shift insensitive wavelet features for the classifi- cation problem at hand.
Edge and ramp preserving noise
removal based on nonlinear diffusion with Gauss curvature
conductance
Suk-Ho Lee, Dept. of Mathematics, Yonsei University,
Korea
In this paper we propose the gauss curvature as the conductance of the diffusion equation for noise removal. The motivation for using the gauss curvature is that it goes to zero if any one of the principle curvatures goes to zero. Thus it has the property of preserving curved edges, ramps, features with small gradient magnitude and other small-scaled features, which other noise removal scheme such as the total variation based noise removal, mean curvature evolution, curvature based evolution fail to preserve. The properties and performance of the proposed scheme will be given theoretically and experimentally.
Introduction to digital watermarking
Ee-Chien Chang, Dept. of Computer Science, National
University of Singapore
Mohan Kankanhalli, Dept. of Computer Science, National
University of Singapore
This tutorial provides the background information necessary to understand the applications and problems of watermarking and data-hiding.
Content-dependent filter (CDF)
design and analysis: CDF design and analysis based on the
anisotropic diffusion model
Charles Chui, Stanford University and University of
Missouri - St. Louis, USA
Several limitations of numerical solution of the anisotropic diffusion (AD) PDE as well as the bilateral filter will be discussed. To address these limitations, the notion of "content-dependent filtering" (CDF) is introduced in the first presentation. Both design criteria and theoretical analysis of these innovative filters will be addressed. The second presentation will focus on technical details. It will be clear that with appropriate modifications, CDFs also apply to image enhancement and image segmentation.
Content-dependent filter (CDF)
design and analysis: Design of CDFs for image noise reduction
Jianzhong Wang, Mathematics, Computer Science and
Statistics, Sam Houston State University
Several limitations of numerical solution of the anisotropic diffusion (AD) PDE as well as the bilateral filter will be discussed. To address these limitations, the notion of "content-dependent filtering" (CDF) is introduced in the first presentation. Both design criteria and theoretical analysis of these innovative filters will be addressed. The second presentation will focus on technical details. It will be clear that with appropriate modifications, CDFs also apply to image enhancement and image segmentation.
Fast fourth-order time-stepping
for stiff PDE
Nick Trefethen, Oxford University
Many partial differential equations combine higher-order linear terms with lower-order nonlinear terms. Examples include the KdV, Allen-Cahn, Burgers, and Kuramoto-Sivashinsky equations. High accuracy is typically needed because the solutions may be highly sensitive to small perturbations. For simulations in simple geometries, spectral discretization in space is excellent, but what about the time discretization? Too often, second-order methods are used because higher order seems impractical. In fact, fourth-order methods are entirely practical for such problems, and we present a comparison of the competing methods of linearly implicit schemes, split step schemes, integrating factors, "sliders", and ETD or exponential time differencing. In joint work with A-K Kassam we have found that a fourth-order Runge-Kutta scheme known as ETDRK4, developed by Cox and Matthews, performs impressively if its coefficients are stably computed by means of contour integrals in the complex plane. Online examples show that accurate solutions of challenging nonlinear PDE can be computed by a 30-line Matlab code in less than a second of laptop time. For reaction-diffusion equation in 2D or 3D, we can often beat standard finite-difference methods by a factor of 10 or more in speed.
Sparse grids and the analysis of
high dimensional large scale data
Markus Hegland, Mathematical Sciences Institute, Australian
National University
The search for interesting variable stars, the discovery of relations between geomorphological properties, satellite observations and mineral concentrations, and the analysis of biological networks all require the solution of a large number of complex learning problems with large amounts of data. A major computational challenge faced in these investigations is posed by the curse of dimensionality. A well known aspect of this curse is the exponential dependence of the size of regular grids on the dimension of the domain. This makes traditional finite element approaches infeasible for high-dimensional domains. It is less known that this curse also affects computations of radial basis function approximations -- in a slightly more subtle way.
Sparse grid functions can deal with the major problems of the curse of dimensionality. As they are the superposition of traditional finite element spaces, many well-known algorithms can be generalised to the sparse grid context. Sparse grids have been successfully used to solve partial differential equations in the past and, more recently, have been shown to be competitive for learning problems as well. The talk will provide a general introduction to the major properties of sparse grids and will discuss connections with kernel based methods and parallel learning algorithms. It will conclude with a short review over some recent work on algorithms based on the combination technique.
References:
- Additive Sparse Grid Fitting, M. Hegland, Curve and Surface Fitting: Saint-Malo 2002, pp. 209-219,Nashboro Press, Brentwood, 2003.
- Adaptive sparse grids, M. Hegland, Proceedings of 10th Computational Techniques and Applications Conference CTAC-2001, ANZIAM Journal, vol. 44, C335--C353, Available online.
(for other references see http://datamining.anu.edu.au)
Relations between nonlinear
denoising methods in signal and image processing
Gabriele Steidl, Fakultaet fuer Mathematik und Informatik,
Universitaet Mannheim
Wavelet shrinkage, nonlinear diffusion filtering, and nonquadratic regularization methods are three useful techniques for edge-preserving denoising of signals and images.
In the first part of the talk we analyze relations between the important 1-D prototypes soft Haar wavelet shrinkage, space-discrete total variation (TV) diffusion and discrete total variation (TV) regularization: we prove that space-discrete TV diffusion and TV regularization are identical. We show that applying translationally invariant soft Haar wavelet shrinkage on a single scale can be regarded as an absolutely stable explicit discretisation of TV diffusion. Afterwards we show that wavelet shrinkage on multiple scales can be regarded as a single step diffusion filtering of the Laplacian pyramid of the signal.
In the second part of the talk we study general relations between arbitrary shrinkage functions and diffusivities: we show that one step of a (stabilized) explicit discretisation of nonlinear diffusion can be expressed in terms of wavelet shrinkage on a single spatial level. This equivalence allows a fruitful exchange of ideas between the two fields. For example. we derive new wavelet shrinkage functions from existing diffusivitv functions, and identify some previously used shrinkage functions as corresponding to well known diffusivities. Moreover, by transferring stability notions from diffusion filtering to wavelet shrinkage, we derive conditions on the shrinkage function that ensure that shift invariant single-level Haar wavelet shrinkage is maximum-minimum stable. monotonicity preserving, and variation diminishing.
Finally, we present some novel diffusion-inspired wavelet shrinkage methods with improved rotation invariance in 2D.
Underwater acoustic signal
classification
Zhenyong Lin, Temasek Laboratories
we applied a fast adaptive short-time Fourier transform algorithm for underwater whale song signal representation, and extract first and second order statistics from its time-frequency representation as features for underwater Humped Back whale call classification. After the optimisation of parameters for classification, we have achieve excellent results.
Bayesian resolution enhancement of
compressed video
Aggelos Katsaggelos, Electrical and Computer Engineering,
Northwestern University, USA
Super-resolution algorithms recover high-frequency information from a sequence of low-resolution observations. In this presentation we consider some recent results on the impact of video compression on the super-resolution task. Hybrid motion-compensation and transform coding schemes are the focus, as these methods provide observations of the underlying displacement values as well as a variable noise process. We utilize the Bayesian framework to incorporate this information and fuse the super-resolution and post-processing problems. A tractable solution is defined, and the relationship between algorithm parameters and information in the compressed bit-stream is established. The association between resolution recovery and compression ratio is also explored. Simulations illustrate the performance of the procedure with both synthetic and non-synthetic sequences.
Challenges and new solutions
predicting Tsunami waves
M. M. Lavrentiev, Jr., Sobolev Institute for Mathematics SD
RAS, Novosibirsk, Russia
In this paper the problem of tsunamigenic earthquake is concerned. Perhaps, only on the basis of multimethod approach the reasonable forecast of tsunami danger will be available. Among the possible methods to be used we list determination of initial displacement at source solving the corresponding inverse problem (A. Avdeev et. al., 2001, F. Gonzalez et. al, 2003), neural network analysis of the time series.
Pacific Marine Environmental Laboratory (PMEL) has developed the Deep-ocean Assessment and Reporting Tsunami (DART) system and has deployed it at six locations around the Pacific. DART systems obtain high-quality data of tsunami amplitudes in the open ocean. This data can be used to reconstruct the true tsunami source parameters. To achieve that goal, PMEL has created a database of pre-calculated time series of tsunami waves from (unit) sources at subduction zones around Pacific. The solutions from the database can be combined using developed Web interface (called FACTS – Facility for the Analysis and Comparison of Tsunami Simulation), to reconstruct tsunami sources recorded by DART. This approach will be used in the next generation of the real-time tsunami forecasting system, which is under development by the National Tsunami Hazard Mitigation Program (NTHMP).
In order to reconstruct tsunami sources with in automatic mode a special algorithm and a software application has been developed. This module is designed to determine the tsunami source parameters by processing the marigrams, obtained at the DARTS stations. The module effectively determines the amplification coefficients for unit sources, which makes possible to approximate the shape of vertical displacement of the sea surface at the tsunami source area. The algorithm is based on minimization of the calculated difference between the measured marigram(s) and the linear combination of synthetic marigrams, taken from the FACTS database.
This inversion algorithm has been numerically tested with the historical data for the 1996 Andreanov tsunami. The module has been implemented into the FACTS database