|
< |
bimagicLab |
> |
|
bioimage informatics lab |
home \ people \ research \ publications
\ 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 |