|
<bimagicLab> |
home \ people \ research \ publications \ software \ teaching
\ contact
|
Frames Redundancy
is a common tool in our daily lives. We double- and triple-check that we
turned off gas and lights, took our keys, money, etc. (at least those
worrywarts among us do). When an important date is coming up, we drive our
loved ones crazy by confirming ``just once more'' they are on top of it. Of
course, the reason we are doing that is to avoid a disaster by missing or
forgetting something, not to drive our loved ones crazy. The
same idea of removing doubt is present in signal representations. Given a signal,
we represent it in another system, typically a basis, where its
characteristics are more readily apparent in the transform coefficients (for
example, wavelet-based compression). However, these representations are
typically nonredundant, and thus corruption or loss
of transform coefficients can be fatal. In comes redundancy; we build a
safety net into our representation so that we can avoid those fatal
disasters. The redundant counterpart of a basis is called a frame. It is
generally acknowledged that frames were born in 1952 in the paper by Duffin and Schaeffer Despite being over half a century
old, frames gained popularity only in the last decade, due mostly to the work
of the three wavelet pioneers---Daubechies, Grossman and Meyer. Frame-like
ideas, that is, building redundancy into a signal expansion, can be seen in
pyramid coding, quantization, denoising, robust
transmission, CDMA systems, multiantenna code
design, segmentation, classification, prediction of epileptic seizures,
restoration and enhancement, motion estimation, signal reconstruction, coding
theory, operator theory and quantum theory and computing. While
frames are often associated with wavelet frames, it is important to remember
that frames are more general than that.
Wavelet frames possess structure; frames are redundant representations
that only need to represent signals in a given space with a certain amount of
redundancy. The simplest frame is called the Mercedes-Benz (MB). The question
now is: Why and where would one use frames? The answer is obvious: anywhere
where redundancy is a must. The host of the applications mentioned above
illustrates that richly. We are concerned only with finite-dimensional frames. When we do venture into the infinite-dimensional one, we will do so only using filter banks---structured expansions used in applications. We will stay away from all other infinite-dimensional settings. Our current work is on constructing frame families for use in bioimaging. |
|
Overview Sponsor This material is based upon
work supported by the National Science Foundation under Grant No. 0515152. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the sponsor(s). Collaborators Amina
Chebira, Stephen Lin, Yann Barbotin, Gowri Srinivasa, Charles Jackson, Markus
Püschel, Pete Casazza, Matthew Fickus, John Ozolek, Carlos Castro Research
Corner Frames in a wireless environment Teaching
Corner Software Multiresolution
frame classification Links |
|
General papers A.
Chebira and J. Kovačević, “Frames in bioimaging”, Proc.
CISS, Princeton, NJ, Mar. 2008. A.
Chebira and J. Kovačević, “Adaptive multiresolution frame
classification of biological and biometric images”, Proc. SPIE Conf. on
Wavelet Applications in Signal and Image Processing, San Diego, USA, Aug.
2007. A multiresolution approach to automated classification
of protein subcellular location images Background: The problem of
automated interpretation of fluorescence microscope images depicting subcellular
protein locations is at the forefront of the current trend in biology towards
understanding the role and function of all proteins. Over the past ten years,
the feasibility of using machine learning methods to recognize all major
subcellular location patterns has been convincingly demonstrated, using
diverse feature sets and combinations of classifiers. On a well-studied data set of 2D HeLa
single-cell images, the best performance to date, 91.5%, was obtained upon
the addition of a simple set of multiresolution features. Results: We report here a
novel approach for the classification of subcellular location patterns by
classifying in multiresolution subspaces. Our system is able to work with any
feature set and any classifier. It consists of multiresolution (MR)
decomposition, followed by feature computation and classification in each MR
subspace, yielding local decisions that are then combined into a global
decision. With 26 texture
features alone and a neural network classifier, we obtained an increase in
accuracy on the 2D HeLa data set to 95.3%. Conclusions: We demonstrate
that the space-frequency localized information in the multiresolution
subspaces adds significantly to the discriminative power of the system.
Moreover, we show that a vastly reduced set of features is sufficient,
consisting of our novel modified Haralick texture
features. Our proposed system is general, allowing for any combinations of
sets of features and any combination of classifiers. A.
Chebira, Y. Barbotin, C. Jackson, T. Merryman, G. Srinivasa, R. F. Murphy and
J. Kovačević, “A multiresolution
approach to automated classification of protein subcellular location images,”
BMC Bioinformatics, vol. 8, no. 210, 2007. [rrc] G.
Srinivasa, T. Merryman, A. Chebira, A. Mintos and J. Kovačević,
“Adaptive
multiresolution techniques for subcellular protein location image
classification”, Proc. IEEE Int. Conf. Acoust., Speech, and
Signal Proc., Toulouse, France, May 2006, pp. V:1177-1180. Invited paper. T.
Merryman, K. Williams, G. Srinivasa, A. Chebira and J. Kovačević,
“A multiresolution enhancement to generic classifiers
of subcellular protein location images”, Proc. IEEE Intl.
Symp. Biomed. Imaging, Towards
an image analysis toolbox for high-throughput Drosophila embryo RNAi screens We build an image analysis
toolbox for high-throughput Drosophila
embryo RNAi screens. The goal is to tag the embryo as normal, developmentally
delayed or abnormal based on the ventral furrow formation. We break the problem into two parts:
in the first, we detect the developmental stage based on the progress of the
ventral furrow formation, and in the second, we tag the embryo as
normal/developmentally delayed/abnormal based on the stage detected and the
elapsed time. The crux of the algorithm is the multiresolution classifier,
and we show that, by classifying in multiresolution spaces, we obtain better
results than by classifying the embryo image alone. The final 2D accuracy
obtained was 93.17%, while by using 3D information, it increased to 98.35%. R. A.
Kellogg, A. Chebira, A. Goyal, P. A. Cuadra, S. F. Zappe, J. S. Minden and J.
Kovačević, “Towards an image analysis toolbox for high-throughput
Drosophila embryo RNAi screens”,
Proc. IEEE Intl. Symp. Biomed. Imaging, Frame classification in histopathology We propose a system for identification
of germ layer components in teratomas derived from human and nonhuman primate
embryonic stem cells. Tissue
regeneration and repair, drug testing and discovery, the cure of genetic and
developmental syndromes all may rest on the understanding of the biology and
behavior of embryonic stem (ES) cells.
Within the field of stem cell biology, an ES cell is not considered an
ES cell until it can produce a teratoma tumor (the
``gold'' standard test); a seemingly disorganized mass of tissue derived from
all three embryonic germ layers; ectoderm, mesoderm, and endoderm.
Identification and quantification of tissue types within teratomas derived
from ES cells may expand our knowledge of abnormal and normal developmental
programming and the response of ES cells to genetic manipulation and/or toxic
exposures. In addition, because
of the tissue complexity, identifying and quantifying the tissue is tedious
and time consuming, but in turn the teratomas provides an excellent
biological platform to test robust image analysis algorithms. We use a multiresolution (MR)
classification system with texture features, as well as develop novel nuclear
texture features to recognize germ layer components. With redundant MR transform,
we achieve a classification accuracy of approximately 88%. A.
Chebira, J. A. Ozolek, C. A. Castro, W. G. Jenkinson, M. Gore, R. Bhagavatula, I.
Khaimovich, S. E. Ormon, C.
S. Navara, M. Sukhwani, K.
E. Orwig, A. Ben-Yehudah, G.
Schatten, G. K. Rohde and J.
Kovačević, “Multiresolution
identification of germ layer components in teratomas derived from human and
nonhuman primate embryonic stem cells”,
Proc. IEEE Intl. Symp. Biomed. Imaging, Paris, France, May 2008, pp. 979-982. |
|
An Adaptive Multiresolution Approach to
Fingerprint Recognition We propose an adaptive
multiresolution (MR) approach to the classification of fingerprint images.
The system adds MR decomposition in front of a generic classifier consisting
of feature computation and classification in each MR subspace, yielding local
decisions, which are then combined into a global decision using a weighting
algorithm. In our previous work on classification of protein subcellular
location images, we showed that the space-frequency localized information in
the MR subspaces adds significantly to the discriminative power of the
system. Here, we go one step farther; We develop a new weighting method which
allows for the discriminative power of each subband to be expressed and
examined within each class. This, in turn, allows us to evaluate the
importance of the information contained within a specific subband. Moreover,
we develop a pruning procedure to eliminate the subbands
that do not contain useful information.
This leads to potential identification of the appropriate MR
decomposition both on a per class basis and for a given dataset. With this new approach, we make the system
adaptive, flexible as well as more accurate and efficient. A. Chebira, L. P. Coelho, A. Sandryhaila, S. Lin, G. W. Jenkinson, J. MacSleyne, C. Hoffman, P. Cuadra, C. Jackson, M. Püschel and J. Kovačević, "An adaptive multiresolution approach to fingerprint recognition", Proc. IEEE Conf. on Image Proc., San Antonio, TX, Sep. 2007, pp. I:457–460. Wavelet
packet correlation methods in biometrics We introduce wavelet packet
correlation filter classifiers. Correlation filters are traditionally
designed in the image domain by minimization of some criterion function of
the image training set. Instead, we perform classification in wavelet spaces
that have training set representations that provide better solutions to the
optimization problem in the filter design. We propose a pruning algorithm to
find these wavelet spaces by using a correlation energy cost function, and we
describe a match score fusion algorithm for applying the filters trained
across the packet tree. The proposed classification algorithm is suitable for
any object recognition task. We present results by implementing a biometric
recognition system that uses the NIST 24 fingerprint database, and show that
applying correlation filters in the wavelet domain results in considerable
improvement of the standard correlation filter algorithm. We also motivate
the use of frames in future work by demonstrating the effect of shift
variance on recognition and identification accuracy. P.
Hennings Yeomans, J. Thornton, J. Kovačević and B.V.K.V. Kumar, "Wavelet packet correlation methods in
biometrics'', Applied Optics, special issue
on Biometric Recognition Systems, vol. 44, no. 5, February 2005., pp.
637-646. J.T.
Thornton, P. Hennings Yeomans, J. Kovačević and B.V.K.V. Kumar, ''Wavelet
packet correlation methods in biometrics'',
Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., Philadelphia, PA,
March 2005., pp. II:81-84. |
|
Frame
families robust to erasures Motivated by the use of
frames for robust transmission over the Internet, we present a first
systematic construction of real tight frames with maximum robustness to
erasures. We approach the problem in steps: we first construct maximally
robust frames by using polynomial transforms. We then add tightness as an
additional property with the help of orthogonal polynomials. Finally, we impose the last
requirement of equal norm and construct, to our best knowledge, the first
real, tight, equal-norm frames maximally robust to erasures. M.
Püschel and J. Kovačević, ''Real, tight frames with maximal robustness to
erasures'', Proc. Data Compr. Conf.,
Snowbird, UT, March 2005, pp. 63-72. Quantized
frame expansions with erasures This work discusses frames in
a new setting: when some of the elements are lost. Since some subsets of a
redundant frame are themselves frames, a quantized frame expansion (QFE) can
be a useful representation even when only a subset of the transform
coefficients are available for computing a reconstruction. This yields
robustness to losses in packet networks such as the Internet. With a simple additive noise
model for quantization, it is shown that a normalized frame minimizes
mean-squared error (MSE) if and only if it is tight. With one quantized frame
coefficient erased, a tight frame is again optimal among normalized frames,
both in average and worse-case scenarios. For more erasures, a general
analysis indicates some optimal designs. V. K
Goyal, J. Kovačević and J.A. Kelner, ''Quantized frame expansions
with erasures'', Journal of Appl. and
Comput. Harmonic Analysis, vol. 10, no. 3, May 2001, pp. 203-233. V. K
Goyal, J. Kovačević and M. Vetterli, ''Multiple
description transform coding: Robustness to erasures using tight frame
expansions'', Proc. IEEE Int. Symp. on
Inform. Th., V. K
Goyal, J. Kovačević and M. Vetterli, ''Quantized frame expansions as source-channel codes
for erasure channels'', Proc. Wavelets
and Appl. Workshop, V. K
Goyal, J. Kovačević and M. Vetterli, ''Quantized frame expansions as source-channel codes
for erasure channels'', Proc. Data
Compr. Conf., Snowbird, UT, March, 1999. P.L.
Dragotti, J. Kovačević and V. K Goyal, ''Quantized
oversampled filter banks with erasures'',
Proc. Data Compr. Conf., Snowbird, UT, March, 2001, pp. 173-182. Filter
bank frame expansions with erasures The frames we started with
are finite dimensional. Due to their practical importance, we decided to
investigate those in l2(Z)
implementable by filter banks. The paper below analyzes the system in
parallel: for finite-dimensional spaces and l2(Z). We found that any equal-norm tight
frame is optimal when no erasures are present. When there is one erasure, we
know that any oversampled filter bank which implements a strongly equal-norm
tight frame is robust to one erasure and minimizes the MSE. When there are
e>1 erasures, depending on whether e is smaller or larger then N, the
minimum occurs when the erased elements are either orthogonal or form a tight
frame. J.
Kovačević, P.L. Dragotti and V. K Goyal, ''Filter
bank frame expansions with erasures'',
IEEE Trans. Inform. Th., special issue in Honor of Aaron D. Wyner, vol. 48,
no. 6, June 2002, pp. 1439-1450. Invited paper. P.L.
Dragotti, J. Kovačević and V. K Goyal, ''Quantized
oversampled filter banks with erasures'',
Proc. Data Compr. Conf., Snowbird, UT, March 2001, pp. 173-182. |
|
Frames in a wireless environment Quantized
frame expansions in a wireless environment Here, we study frames for
robust transmission over a multiple-antenna wireless system - BLAST. By
considering as erased a component received with an SNR inferior to a given
threshold, we place frames in a setting where some of the elements are
deleted. In ``Quantized frame expansions with
erasures'', we focused on the performance of quantized frame
expansions up to M-N erased components, the structure of a frame being thus
preserved. In this work we consider every possible scenario of erasures for
low-dimensional frames and we present optimal designs for corresponding
systems using a small number of antennas. A. C.
Lozano, J. Kovačević and M Andrews,
''Quantized frame expansions in a
wireless environment'', Proc. Data Compr. Conf., Snowbird, UT,
March 2002, pp. 480-489. A. C.
Lozano, J. Kovačević and M Andrews, ''Quantized frame expansions in a wireless
environment'', Proc. DIMACS Workshop
on Source Coding and Harmonic Analysis, |
|
Lapped
tight frame transforms We propose a new class of
equal-norm tight frames termed Lapped Tight Frame Transforms (LTFTs). These can be seen as a redundant
counterpart to bases known as Lapped Orthogonal Transforms (LOTs) introduced
by Malvar and Cassereau,
as well as an infinite-dimensional counterpart to Harmonic Tight Frames
(HTFs). To construct LTFTs, we seed them from LOTs and show that, in a
specific case, the process preserves the equal norm. As both their basis
counterpart LOTs as well as their finite-dimensional one HTFs, LTFTs possess
many desirable properties, such as equal norm and efficient implementation. A.
Chebira and J. Kovačević, “Lapped
tight frame transforms”, Proc. IEEE Int.
Conf. Acoust., Speech, and Signal Proc., Toronto, Honolulu, HI, Apr. 2007,
pp. III:857-860. Physical
interpretation of finite tight frames We find finite tight frames
when the lengths of the frame elements are predetermined. In particular, we derive
a ``fundamental inequality" which completely characterizes those
sequences which arise as the lengths of a tight frame's elements.
Furthermore, using concepts from classical physics, we show that this
characterization has an intuitive physical interpretation. P.G.
Casazza, M. Fickus, J. Kovačević, M. Leon and J. Tremain, ''A
physical interpretation of finite tight frames'', Harmonic Analysis and Applications, C. Heil, Ed.,
Birkhauser, Equal-norm
tight frames with erasures Since equal-norm tight frames
have been shown to be useful for robust data transmission, we give the first
systematic study of the general class of equal-norm tight frames and their
properties. We search for efficient constructions of such frames. We show
that the only equal-norm tight frames with the group structure and one or two
generators are the generalized harmonic frames. Finally, we give a complete
classification of frames in terms of their robustness to erasures. P.G.
Casazza and J. Kovačević, ''Equal-norm tight frames with
erasures'', Advances in Computational
Mathematics, special issue on Frames, 2002. Invited paper. P.G.
Casazza and J. Kovačević, ''Uniform tight frames for signal processing and
communications'', Proc. SPIE Conf. on
Wavelet Appl. in Signal and Image Proc., San Diego, CA, July 2001. |
|
J.
Kovačević and A. Chebira, An Introduction to Frames, Foundations
and Trends in Signal Processing, Now Publishers, 2008. J.
Kovačević and A. Chebira, “Life beyond bases: The advent of
frames (Part II)”, IEEE SP Mag., vol. 24, no. 5, Sep. 2007, pp.
115-125. Feature article. J.
Kovačević and A. Chebira, “Life beyond bases: The advent of
frames (Part I)”, IEEE SP Mag., vol. 24, no. 4, Jul. 2007, pp. 86-104.
Feature article. A.
Chebira, Y. Barbotin, C. Jackson, T. Merryman, G. Srinivasa, R. F. Murphy and
J. Kovačević, “A multiresolution
approach to automated classification of protein subcellular location images,”
BMC Bioinformatics, vol. 8, no. 210, 2007. [rrc] P.G.
Casazza, M. Fickus, J. Kovačević, M. Leon and J. Tremain, ''A
physical interpretation of finite tight frames'', Harmonic Analysis and Applications, C.
Heil, Ed., Birkhauser, M.
Püschel and J. Kovačević, ''Real, tight frames with maximal robustness to
erasures'', Proc. Data Compr. Conf., Snowbird,
UT, March 2005, pp. 63-72. |
|
|
|
Under construction |