A novel representation of images for image retrieval is introduced in this
paper, by using a new type of feature with remarkable discriminative power.
Despite the multi-scale nature of objects, most existing models perform feature
extraction on a fixed scale, which will inevitably degrade the performance of
the whole system. Motivated by this, we introduce a hierarchical sparse coding
architecture for image retrieval to explore multi-scale cues. Sparse codes
extracted on lower layers are transmitted to higher layers recursively. With
this mechanism, cues from different scales are fused. Experiments on the
Holidays dataset show that the proposed method achieves an excellent retrieval
performance with a small code length.
Authors' comments: 5 pages, 6 figures, conference
Information systems usually show as a particular point of failure the
vagueness between user search terms and the knowledge orders of the information
space in question. Some kind of guided searching therefore becomes more and
more important in order to precisely discover information without knowing the
right search terms. Knowledge maps of digital library collections are promising
navigation tools through knowledge spaces but still far away from being
applicable for searching digital libraries. However, there is no continuous
knowledge exchange between the "map makers" on the one hand and the Information
Retrieval (IR) specialists on the other hand. Thus, there is also a lack of
models that properly combine insights of the two strands. The proposed workshop
aims at bringing together these two communities: experts in IR reflecting on
visual enhanced search interfaces and experts in knowledge mapping reflecting
on visualizations of the content of a collection that might also present a
context for a search term in a visual manner. The intention of the workshop is
to raise awareness of the potential of interactive knowledge maps for
information seeking purposes and to create a common ground for experiments
aiming at the incorporation of knowledge maps into IR models at the level of
the user interface.
Authors' comments: 6 pages, accepted workshop proposal for Digital Libraries 2014
We used Lemur Toolkit, an open source toolkit designed for Information
Retrieval (IR) research, for our automated indexing and retrieval experiments
on a TREC-like test collection for Turkish. We study and compare three
retrieval models Lemur supports, especially Language modeling approach to IR,
combined with language specific preprocessing techniques. Our experiments show
that all retrieval models benefits from language specific preprocessing in
terms of retrieval quality. Also Language Modeling approach is the best
performing retrieval model when language specific preprocessing applied.
Authors' comments: 3 pages
We consider the phase retrieval problem in which one tries to reconstruct a
function from the modulus of its wavelet transform. We study the unicity and
stability of the reconstruction. In the case where the wavelets are Cauchy
wavelets, we prove that the modulus of the wavelet transform uniquely
determines the function up to a global phase. We show that the reconstruction
operator is continuous but not uniformly continuous. We describe how to
construct pairs of functions which are far away in $L^2$-norm but whose wavelet
transforms are very close, in modulus. The principle is to modulate the wavelet
transform of a fixed initial function by a phase which varies slowly in both
time and frequency. This construction seems to cover all the instabilities that
we observe in practice; we give a partial formal justification to this fact.
Finally, we describe an exact reconstruction algorithm and use it to
numerically confirm our analysis of the stability question.
Authors' comments: Acknowledgments updated
We prove by means of elementary methods that phase retrieval of complex
polynomials p of degree less than N is possible with 4N-4 phaseless Fourier
measurements of p and p'. In addition, we provide an associated algorithm and
prove that it recovers p up to global phase.
Authors' comments: 10 pages
In this note we prove that reconstruction from magnitudes of frame
coefficients (the so called "phase retrieval problem") can be performed using
Lipschitz continuous maps. Specifically we show that when the nonlinear
analysis map $\alpha:{\mathcal H}\rightarrow\mathbb{R}^m$ is injective, with
$(\alpha(x))_k=|<x,f_k>|^2$, where $\{f_1,\ldots,f_m\}$ is a frame for the
Hilbert space ${\mathcal H}$, then there exists a left inverse map
$\omega:\mathbb{R}^m\rightarrow {\mathcal H}$ that is Lipschitz continuous.
Additionally we obtain the Lipschitz constant of this inverse map in terms of
the lower Lipschitz constant of $\alpha$. Surprisingly the increase in
Lipschitz constant is independent of the space dimension or frame redundancy.
Authors' comments: 12 pages, 1 figure
This review article provides a contemporary overview of phase retrieval in
optical imaging, linking the relevant optical physics to the information
processing methods and algorithms. Its purpose is to describe the current state
of the art in this area, identify challenges, and suggest vision and areas
where signal processing methods can have a large impact on optical imaging and
on the world of imaging at large, with applications in a variety of fields
ranging from biology and chemistry to physics and engineering.
This paper deals with sparse phase retrieval, i.e., the problem of estimating
a vector from quadratic measurements under the assumption that few components
are nonzero. In particular, we consider the problem of finding the sparsest
vector consistent with the measurements and reformulate it as a group-sparse
optimization problem with linear constraints. Then, we analyze the convex
relaxation of the latter based on the minimization of a block l1-norm and show
various exact recovery and stability results in the real and complex cases.
Invariance to circular shifts and reflections are also discussed for real
vectors measured via complex matrices.
Most content-based image retrieval systems consider either one single query,
or multiple queries that include the same object or represent the same semantic
information. In this paper we consider the content-based image retrieval
problem for multiple query images corresponding to different image semantics.
We propose a novel multiple-query information retrieval algorithm that combines
the Pareto front method (PFM) with efficient manifold ranking (EMR). We show
that our proposed algorithm outperforms state of the art multiple-query
retrieval algorithms on real-world image databases. We attribute this
performance improvement to concavity properties of the Pareto fronts, and prove
a theoretical result that characterizes the asymptotic concavity of the fronts.
This work compares concept models for cross-language retrieval: First, we
adapt probabilistic Latent Semantic Analysis (pLSA) for multilingual documents.
Experiments with different weighting schemes show that a weighting method
favoring documents of similar length in both language sides gives best results.
Considering that both monolingual and multilingual Latent Dirichlet Allocation
(LDA) behave alike when applied for such documents, we use a training corpus
built on Wikipedia where all documents are length-normalized and obtain
improvements over previously reported scores for LDA. Another focus of our work
is on model combination. For this end we include Explicit Semantic Analysis
(ESA) in the experiments. We observe that ESA is not competitive with LDA in a
query based retrieval task on CLEF 2000 data. The combination of machine
translation with concept models increased performance by 21.1% map in
comparison to machine translation alone. Machine translation relies on parallel
corpora, which may not be available for many language pairs. We further explore
how much cross-lingual information can be carried over by a specific
information source in Wikipedia, namely linked text. The best results are
obtained using a language modeling approach, entirely without information from
parallel corpora. The need for smoothing raises interesting questions on
soundness and efficiency. Link models capture only a certain kind of
information and suggest weighting schemes to emphasize particular words. For a
combined model, another interesting question is therefore how to integrate
different weighting schemes. Using a very simple combination scheme, we obtain
results that compare favorably to previously reported results on the CLEF 2000
dataset.
Authors' comments: 74 pages; MSc thesis at Saarland University
In this paper, we present the efficient content based image retrieval systems
which employ the color, texture and shape information of images to facilitate
the retrieval process. For efficient feature extraction, we extract the color,
texture and shape feature of images automatically using edge detection which is
widely used in signal processing and image compression. For facilitated the
speedy retrieval we are implements the antipole-tree algorithm for indexing the
images.
Authors' comments: 12 pages
The paper considers the phase retrieval problem in N-dimensional complex
vector spaces. It provides two sets of deterministic measurement vectors which
guarantee signal recovery for all signals, excluding only a specific subspace
and a union of subspaces, respectively. A stable analytic reconstruction
procedure of low complexity is given. Additionally it is proven that signal
recovery from these measurements can be solved exactly via a semidefinite
program. A practical implementation with 4 deterministic diffraction patterns
is provided and some numerical experiments with noisy measurements complement
the analytic approach.
Authors' comments: Preprint accepted for publication in Sampling Theory in Signal and
Image Processing -- Special issue on SampTa 2013
This paper considers the question of recovering the phase of an object from
intensity-only measurements, a problem which naturally appears in X-ray
crystallography and related disciplines. We study a physically realistic setup
where one can modulate the signal of interest and then collect the intensity of
its diffraction pattern, each modulation thereby producing a sort of coded
diffraction pattern. We show that PhaseLift, a recent convex programming
technique, recovers the phase information exactly from a number of random
modulations, which is polylogarithmic in the number of unknowns. Numerical
experiments with noiseless and noisy data complement our theoretical analysis
and illustrate our approach.
4194.
A Quantum Information Retrieval Approach to Memory
Kirsty Kitto, Peter Bruza, Liane Gabora
(2012). Proceedings of the International Joint Conference on
Neural Networks, (pp. 932-939). June 10-15, Brisbane, Australia, IEEE
Computational Intelligence Society
As computers approach the physical limits of information storable in memory,
new methods will be needed to further improve information storage and
retrieval. We propose a quantum inspired vector based approach, which offers a
contextually dependent mapping from the subsymbolic to the symbolic
representations of information. If implemented computationally, this approach
would provide exceptionally high density of information storage, without the
traditionally required physical increase in storage capacity. The approach is
inspired by the structure of human memory and incorporates elements of
Gardenfors' Conceptual Space approach and Humphreys et al.'s matrix model of
memory.
Authors' comments: 8 pages; 2 figures
We consider the problem of sparse phase retrieval, where a $k$-sparse signal
${\bf x} \in {\mathbb R}^n \textrm{ (or } {\mathbb C}^n\textrm{)}$ is measured
as ${\bf y} = |{\bf Ax}|,$ where ${\bf A} \in {\mathbb R}^{m \times n} \textrm{
(or } {\mathbb C}^{m \times n}\textrm{ respectively)}$ is a measurement matrix
and $|\cdot|$ is the element-wise absolute value. For a real signal and a real
measurement matrix ${\bf A}$, we show that $m = 2k$ measurements are necessary
and sufficient to recover ${\bf x}$ uniquely. For complex signal ${\bf x} \in
{\mathbb C}^n$ and ${\bf A} \in {\mathbb C}^{m \times n}$, we show that $m =
4k-2$ phaseless measurements are sufficient to recover ${\bf x}$. It is known
that the multiplying constant $4$ in $m = 4k-2$ cannot be improved.
Authors' comments: 6 pages
Duplicated code has a negative impact on the quality of software systems and
should be detected at least. In this paper, we discuss an approach that
improves source code retrieval using the structural information about the
programs. We developed a lexical parser to extract control statements and
method identifiers from Java programs. We propose a similarity measure that is
defined by the ratio of the number of sequentially full matching statements to
the number of sequentially partial matching ones. The similarity measure is
considered to be an extension of a set based similarity index, e.g.,
Sorensen-Dice index. Our key contribution of this research is the development
of a similarity retrieval algorithm that derives meaningful search conditions
from a given sequence, and then performs retrieval using all of the derived
conditions. Experiments show that our retrieval model outperforms the other
retrieval models up to 90.9% in the number of retrieved methods.
Authors' comments: 16 pages, 6 figures, 3 tables
In a variety of fields, in particular those involving imaging and optics, we
often measure signals whose phase is missing or has been irremediably
distorted. Phase retrieval attempts the recovery of the phase information of a
signal from the magnitude of its Fourier transform to enable the reconstruction
of the original signal. A fundamental question then is: "Under which conditions
can we uniquely recover the signal of interest from its measured magnitudes?"
In this paper, we assume the measured signal to be sparse. This is a natural
assumption in many applications, such as X-ray crystallography, speckle imaging
and blind channel estimation. In this work, we derive a sufficient condition
for the uniqueness of the solution of the phase retrieval (PR) problem for both
discrete and continuous domains, and for one and multi-dimensional domains.
More precisely, we show that there is a strong connection between PR and the
turnpike problem, a classic combinatorial problem. We also prove that the
existence of collisions in the autocorrelation function of the signal may
preclude the uniqueness of the solution of PR. Then, assuming the absence of
collisions, we prove that the solution is almost surely unique on 1-dimensional
domains. Finally, we extend this result to multi-dimensional signals by solving
a set of 1-dimensional problems. We show that the solution of the
multi-dimensional problem is unique when the autocorrelation function has no
collisions, significantly improving upon a previously known result.
Authors' comments: submitted to IEEE TIT
In many areas of imaging science, it is difficult to measure the phase of
linear measurements. As such, one often wishes to reconstruct a signal from
intensity measurements, that is, perform phase retrieval. In several
applications the signal in question is believed to be sparse. In this paper, we
use ideas from the recently developed polarization method for phase retrieval
and provide an algorithm that is guaranteed to recover a sparse signal from a
number of phaseless linear measurements that scales linearly with the sparsity
of the signal (up to logarithmic factors). This is particularly remarkable
since it is known that a certain popular class of convex methods is not able to
perform recovery unless the number of measurements scales with the square of
the sparsity of the signal. This is a shorter version of a more complete
publication that will appear elsewhere.
In many applications, signals are measured according to a linear process, but
the phases of these measurements are often unreliable or not available. To
reconstruct the signal, one must perform a process known as phase retrieval.
This paper focuses on completely determining signals with as few intensity
measurements as possible, and on efficient phase retrieval algorithms from such
measurements. For the case of complex M-dimensional signals, we construct a
measurement ensemble of size 4M-4 which yields injective intensity
measurements; this is conjectured to be the smallest such ensemble. For the
case of real signals, we devise a theory of "almost" injective intensity
measurements, and we characterize such ensembles. Later, we show that phase
retrieval from M+1 almost injective intensity measurements is NP-hard,
indicating that computationally efficient phase retrieval must come at the
price of measurement redundancy.
Authors' comments: 18 pages, 1 figure
The aureoles around stars caused by thin cirrus limit nighttime measurement
opportunities for ground-based astronomy but can provide information on
high-altitude ice crystals for climate research. In this paper we attempt to
demonstrate quantitatively how this works. Aureole profiles can be followed out
to ~0.2 degrees from stars and ~0.5 degrees from Jupiter. Interpretation of
diffracted starlight is similar to that for sunlight, but emphasizes larger
particles. Stellar diffraction profiles are very distinctive, typically being
approximately flat out to a critical angle followed by gradually steepening
power-law falloff with slope less steep than -3. Using the relationship between
the phase function for diffraction and the average Fourier transform of the
projected area of complex ice crystals we show that defining particle size in
terms of average projected area normal to the propagation direction of the
starlight leads to a simple, analytic approximation representing large-particle
diffraction that is nearly independent of crystal habit. A similar analytic
approximation for the diffraction aureole allows it to be separated from the
point spread function and the sky background. Multiple scattering is
deconvolved using the Hankel transform leading to the diffraction phase
function. Application of constrained numerical inversion to the phase function
then yields a solution for the particle size distribution in the range between
~50 microns and ~400 microns. Stellar aureole measurements can provide one of
the very few, as well as least expensive, methods for retrieving cirrus
microphysical properties from ground-based observations.
Authors' comments: 18 pages, 21 figures, Journal of Geophysical Research, in press
