Michael Lindenbaum
Computer Science Department
Technion, Israel Institute of Technology
Haifa 32000, Israel.
Tel: +972-4-8294331
Fax: +972-4-8293900
Home page:
http://www.cs.technion.ac.il/~mic/
Email address: mic at
cs.technion.ac.il
Main Research Topics and some Publications
Performance Prediction
My main
research interest is computer vision, with a focus on the analysis and
prediction of visual process performance. Performance is usually evaluated
empirically, by implementing the algorithm and testing it on real images. I am
interested in developing methods for statistically modeling the image data and
using these models to analytically predict the performance of algorithm. In order for the predictions to be useful, the models must be simple enough for
analysis but also realistic. The analysis tells us what to expect from an
algorithm's performance and what level of performance can be achieved.
My work on
performance analysis began with theoretical models (Geometric Probing) but
then moved on to more realistic domains. See some examples of Recognition, Grouping, and recently, Attention.
Attention
Visual search is required in situations
where a person or a machine views a scene with the goal of finding one or more
familiar entities. The highly effective visual search (or, more generally,
attention) mechanisms in the human visual system were extensively studied from the viewpoints of
psychophysics and physiology and were also used as models for
computer vision implementations.
Taking a stochastic approach, we modeled the target presence in different image
regions as a set of correlated random variables taking target/non-target values.
We proposed an efficient search algorithm, based on linear estimation, which can
handle both inner-scene similarity and top-down information, when available.
Being interested in inherent limitations, we characterized the difficulty of
search tasks using a metric-space cover (similar to Kolmogorov's
epsilon-covering), and derived (tight) bounds on the performance of all search
algorithms.
T. Avraham and M. Lindenbaum,
Dynamic Visual Search using Inner Scene Similarity - Algorithms and Inherent
Limitations. Proceedings of the 8th European Conference on Computer
Vision, volume II, pages 58-70, 2004.
T. Avraham and M. Lindenbaum,
Attention-based Dynamic Visual Search using Inner-scene
Similarity: Algorithms and Bounds. IEEE Trans. Pattern Analysis and Machine Intelligence,
28(2):251-264, 2006..
It turned out that the predictions developed in the quantitative
computer vision context are relevant also in the human vision context
and that a search task is harder if its associated
metric cover is larger.
Y. Yeshurun, T. Avraham and M. Lindenbaum,
Predicting Visual-search Performance by
Quantifying Stimuli Similarities. Journal of Vision, 8(4):1{22, 2008.
Object Recognition
Analysis of Object Recognition Tasks
In recognition performance, we first considered the relation between
the number of data features collected from the image and the probability of
success in the recognition task that relies on this data. In other words, we
asked how much data is required to decide, with some pre-specified reliability,
that some familiar object is in the scene. The answer depends on factors such as object
similarity, transformation class, and noise. One of our papers
suggests a way to measure the effect of object similarity, while another
uses an integrated random model in the context of a
complex cluttered scene. (See the figure above for an instance of the random model.)
M. Lindenbaum, Bounds on Shape Recognition Performance. IEEE Trans. on PAMI-17, No. 7, pp. 666-680, 1995.
M. Lindenbaum, An
Integrated Model for Evaluating the Amount of Data Required for
Reliable Recognition, IEEE Trans. on PAMI-19, No. 11, pp. 1251-1264, 1997.
Similar (but less tight) results may be derived by observing that the
recognition task is equivalent to a learning task. Thus, we re-answered our
question by reformulating it in the PAC (Probably Approximately Correct)
theoretical learning model, and finding the VC-dimension of a class containing
the instances of a particular model under all transformations.
M. Lindenbaum and S. Ben-David, Applying
VC-dimension Analysis to Object Recognition. Proceedings of the 3rd
European Conference on Computer Vision, 1994, pp. 239-240.
M. Lindenbaum and S. Ben-David, Applying
VC-dimension Analysis to 3D Object Recognition from Perspective
Projections. Proceedings of the 12th National Conf. on Artificial
Intelligence (AAAI), 1994, pp. 985-990.
These results quantify many prior intuitive observations,
such as "similar objects are harder to discriminate," or "higher reliability
requires more data." They are useful for setting the required data subset
size when designing a new algorithm, for analyzing reported results by comparing
them to the theoretical bounds, for inferring performance when conditions are
changed, and for ranking different recognition tasks according to their
difficulty. The results are concerned with the ability of a "consistency test"
to reject incorrect hypotheses and are independent of the hypothesis generating
mechanism. Thus, they are, in a sense, algorithm independent.
Grouping-based Nonadditive
Verification
Perceptual grouping can be informative for object recognition
as well. Intuitively, we can say that a good hypothesis should also be a good group. This
criterion turns out to be powerful and significantly improves the reliability of
the verification process.
A. Amir and M. Lindenbaum, Grouping-based
Nonadditive Verification . IEEE Trans. on PAMI-20, No. 2, pp. 186-192,
1998.
Comparing Images under Varying Illumination or Why Gabor Jets Are So Effective ?
Comparing images is fundamental to vision systems. This task becomes
harder under variable lighting. Most of the proposed methods work
well on rough objects containing discontinuities or areas of rapid change in
albedo or shape. Comparing images of smooth surfaces with no edges or
texture under varying illumination is, however, more challenging.
When the surface is smooth, its normals are highly correlated if they are in close proximity.
We model such surfaces as Gaussian
processes and derive the resulting statistical characterization of the
corresponding images. Supported by this model, we treat the difference between
two images associated with the same surface and different lighting as colored
Gaussian noise, and use the whitening tool from signal detection theory to
construct a measure of difference between them.
While our Gaussian assumption is a simplification, the resulting
measure functions very well for both synthetic and real smooth objects. Thus we
improve upon methods for matching images of smooth objects, while providing
insight into their performance.
And how does this whitening relate to Gabor jets ? It turns out that
Gabors jets may be interpreted as a combination of gradient direction
comparison (a great method for rough surfaces) and whitening (which
works for smooth surfaces). This way, they win in both worlds.
M. Osadchy, M. Lindenbaum, and D. Jacobs Whitening for Photometric Comparison of Smooth Surfaces under Varying Illumination.
ECCV04, volume IV, pages 217-228, 2004.
M. Osadchy, D. Jacobs, and M. Lindenbaum
Surface Dependent Representations for Illumination Insensitive Image Comparison.
. IEEE Trans. Pattern Analysis and Machine Intelligence,
29(1):98{111, 2007.
Analysis of Grouping Processes
Grouping processes
partition an image (or some partial representation of it,
such as an edge map) into regions such that all data elements in one region
correspond to one imaged object. As in the recognition problem, my
interest in grouping is mainly in modeling and prediction. That is, my work is
concerned with suggesting probabilistic models, assesing their validity, and using them to derive predictions on grouping performance with specific
algorithms.
Maximum Likelihood (Generic) Grouping Processes and
Their Analysis
Together with Arnon Amir, I proposed a quantitative approach
to grouping, which consists of a generic grouping method, applicable to many
domains, and an analysis of the expected grouping quality. This paper is
distinctive in two important ways. First, unlike previous
grouping approaches, which were limited to specific domains, the proposed
approach is generic. In our study, we demonstrated this virtue by implementing
three domain-specific grouping algorithms as instances of the proposed one. The
second crucial difference is that we provide results relating the expected
grouping quality to the cue reliability and to the computational effort
invested.
A. Amir and M. Lindenbaum, Quantitative Analysis
of Grouping Processes. IEEE Trans. on PAMI-20, No. 2, pp. 168-185, 1998.
(A shorter version appeared in ECCV, pp. 371-384, 1996.)
An Analysis of Connected Components Grouping
Processes
We consider the extremely fast connected components grouping
process and use probabilistic models to analyze its performance. We
derived the expected number of addition errors and the group fragmentation rate
and showed that they depend on a few inherent and intuitive parameters.
Furthermore, we showed that the grouping process may be controlled so that the
performance may be chosen within a given tradeoff. The analytic results are
supported by implementing the algorithm and testing it on synthetic and real
images.
A. Berengolts and M. Lindenbaum, On the
Performance of Connected Components Grouping . IJCV 41(3), pp. 195-216,
2001.
A Probabilistic Interpretation of the Saliency
Network
Saliency algorithms aim to find image curves, maximizing some
deterministic quality measure which grows with the length of the curve, its
smoothness, and its continuity. We proposed a modified saliency estimation
mechanism that is based on probabilistically specified grouping cues. In the
context of the proposed method, the well-known saliency mechanism proposed by
Shaashua and Ullman may be interpreted as a process that tries to detect the curve
with maximal expected length. Besides the new interpretation, the proposed
characterization has other advantages: First, the probabilistic characterization
may be derived and verified from typical images (rather than relying on a
preconceived characterization of "important" figure subsets). Second, the
probabilistic saliency is more abstract and thus more generic than the common
geometric formulations. Therefore, it lends itself to different realizations of
saliencies, based on different cues. We demonstrated this by creating, as an instances of the general approach, a saliency process that
is based on grey level similarity but still preserves the same interpretation.
We then turned to analyze the expected performance of
the saliency process. Regarding the basic grouping information (grouping
cues) as random variables, we used ergodicity and asymptotic analysis to derive
the saliency distribution associated with the main curves ("figure") and with
the rest of the image ("background"). We further considered finite-length curves
and analyzed their saliency values. The derived distributions were used to show
how to set thresholds on the saliency for deciding optimally between figure and
background, how to choose saliency cues, and how to
estimate bounds on saliency performance.
M. Lindenbaum and A. Berengolts, A
Probabilistic Interpretation of the Saliency Network . ECCV, vol. II,
pp. 257-272, 2000.
A. Berengolts and M. Lindenbaum, On the
Distribution of Saliency . CVPR (2), pp. 543-549, 2004.
An Information-based Measure for Grouping
Quality
The evaluation of grouping results is not straightforward and is
often heuristic. We proposed a method for measuring grouping quality, based on
the following observation: a better grouping result provides more information
about the true, unknown grouping. The amount of information is evaluated by the
number of queries required to specify the true grouping. A related measure of
informativeness is the uncertainty of the true grouping, characterized by means of a
probabilistic model and common information theory terms such as surprise and
entropy. This relation between the measures is established and experimentally
supported. The proposed information-based quality measure is relatively free
from arbitrary choices, treats different types of grouping errors in a uniform
way, and does not favor any algorithm. The query count was found to be
approximately monotonic in the entropy and independent of the grouping error type,
indicating that the query count is an
adequate unbiased means for comparing grouping results. Moreover, we found that
the query count measure approximates human judgment better than other
methods and, as such, gives better results when used to optimize a segmentation
algorithm, as demonstrated in our experiments.
E.A. Engbers, M. Lindenbaum and A.W.M. Smeulders, An
Information-Based Measure for Grouping Quality. ECCV (3), pp. 392-404,
2004
Unsupervised Estimation of Segmentation Quality using Nonnegative Factorization
Recently I became interested in unsupervised performance estimation
using empirical models. Such models evaluate the accuracy/reliability
of a particular result or predict performance before the algorithm is
run, using a model which is partly derived, in an unsupervised way,
from a particular image. The prediction is therefore image adaptive.
We observed, for example, that additive properties of segments (e.g.,
histograms of some feature), provided by some segmentation algorithm
are linear combinations of the corresponding properties associated
with the true (in some sense) segmentation. Then, using many
segmentations of the same image and nonnegative matrix factorization
(NMF) techniques, we were able to get the properties of the true
segments. This allowed us to estimate the precision/recall of a given
segmentation without ground truth.
R. Sandler and M. Lindenbaum,
Unsupervised Estimation of Segmentation Quality using Nonnegative Factorization. Proc. IEEE Conf. Computer Vision and Pattern Recognition -
CVPR08, 2008.
Adaptive and progressive image sampling
What is the best method for progressively sampling an image?
We proposed a progressive sampling algorithm, which retains (deterministic)
uniformity with the increased density and places the samples irregularly, thus
providing excellent anti-aliasing properties. The uniformity metric can be either
image-independent or image-dependent, so an adaptive sampling scheme (such as the
one in the image above) can be derived as well.
Yuval Eldar, Michael Lindenbaum, Moshe Porat and Yehoshua Y. Zeevi, The Farthest Point
Strategy for Progressive Image Sampling, IEEE Transactions on Image
Processing, 6, No. 9, pp. 1305-1315, 1997.
Efficient Karhunen Loeve (PCA) Basis Computations
The
computational cost of the approximated Karhunen Loeve basis calculation (or PCA)
is often prohibitive. Together with Hiroshi Murase, I reduced both the
computational and storage requirements by exploiting the spatial and temporal
correlations common in many image sets.
H. Murase and M. Lindenbaum, Spatial Temporal Adaptive Method for Partial
Eigenstructure Decomposition of Large Image Matrices, IEEE Trans. on Image
Processing, IP-4, No. 5, pp. 620-629, 1995.
Together with Avi Levy, I developed a sequential method for calcualting the
KL basis. The algorithm is faster in typical applications than the usual batch
algorithm, and is especially advantageous for image sequences: the KL basis
calculation is done with much shorter delay and allows for dynamic updating of
object databases for recognition. Systematic tests of the implemented algorithm
show that these advantages are indeed obtained with the same accuracy as batch KL algorithms.
A. Levy and M. Lindenbaum, Sequential
Karhunen-Loeve Basis Extraction, IEEE Transactions on Image processing
9(8), pp. 1371-1374, 2000 (or an older version in Int Conf. on Image Processing
(ICIP) 1998.)
You are welcome to use the software
package and demo implementing this algorithm (in Unix and Windows).
Some Results in Learning Theory
It turns out that the results we
proved for analyzing vision tasks are also of interest
for the learning theory community.
S. Ben-David and M. Lindenbaum, Localization vs.
Identification of Semi-Algebraic Sets. Proceedings of the 6th ACM
Conference on Computational Learning Theory, 1993, pp. 327-336.
S. Ben-David and M. Lindenbaum, Learning
Distributions by their Density Levels - A Paradigm for Learning Without a
Teacher. Journal of Computer and Systems Sciences, 1997, pp. 171-182.
Example Selection in the Context of Nearest
Neighbor Classifiers
In many domains, getting examples for learning is
easy but labeling them is costly. In such cases, it is beneficial to actively
select the examples for labeling with the goal of reducing the labeling cost.
Together with Dmitry Rusakov
and Shaul Markovitch, I
proposed a lookahead selective sampling process, whose goal is to select the
examples with the highest utility and which uses a random field model for the
required estimate of the possible labels' probability. We found empirically
that the proposed algorithm outperforms other selective sampling methods in
terms of the average error rate and performance stability.
M. Lindenbaum, S. Markovich, and D. Rusakov, Selective
Sampling for Nearest Neighbor Classifiers. Proceedings of AAAI-99.
Geometric Probing
My thesis,
supervised by Freddy Bruckstein, was concerned with algorithmic
robotics issues. We considered geometric probing tasks,
where one is asked to provide a strategy for finding an object's shape using a small number of simple measurements (probes). Part of
my work on this subject was dedicated to finding (the first) strategies
for parallel probing, as well as lower bounds which prove that they
are optimal. The other part was concerned with broadening the
traditional geometric probing scope, which was based on the
non-realistic object polygonality assumption. Here, we provided an
efficient strategy for reconstructing non-polygonal objects with a
finite number of probes and with a certain pre-specified precision.
M. Lindenbaum and A. Bruckstein, Parallel Strategies for
Geometric Probing . Journal of Algorithms 13, pp. 320-349, 1992.
M. Lindenbaum and A. Bruckstein, Blind Approximation of Planar
Convex Shapes, IEEE Trans. on Robotics and Automation, RA-10,
No. 4, pp. 517-529, 1994.
Distributed Ant Robotics
Computational robotics
is no longer my main research direction but I am still involved with
some topics. In distributed robotics one considers a population of
robots driven by the same (usually simple and local)
strategy, with the aim of selecting the strategy which leads to a useful
emergent behavior. Together with Israel Wagner and Freddy
Bruckstein, and inspired by ant communication (using pheromones), I
investigated the ability of a group of robots, who communicate by
leaving traces, to perform the task of cleaning the floor of an
unmapped building, or any task that requires traversing an
unknown network. More specifically, we considered robots that leave
chemical odor traces. These traces evaporate over time, and the robots are able to
evaluate the strength of the odor at every point they reach, with some
measurement error. Our abstract model is a decentralized multia(ge)nt
adaptive system with a shared memory, moving on a graph whose vertices
are the floor tiles. We describe three methods of cooperatively
covering a graph, using smell traces that gradually vanish,
and show that they all result in eventual task completion, two of them
in a time polynomial in the number of tiles. As opposed to existing
traversal methods (e.g., DFS), our algorithms are adaptive: they will
complete the traversal of the graph even if some of the agents die or
the graph changes (edges/vertices added or deleted) during the
execution, as long as the graph stays connected.
Israel A. Wagner, Michael Lindenbaum, and Alfred M. Bruckstein.
Cooperative
Covering by Ant-Robots Using Evaporating Traces,
For more
details and other computational robotics issues, see the home page of
Israel Wagner.
For a demo, you might want to look at our Simulators.
Visual Servoing
Together with Keisuke Kinoshita,
I considered the task of visual servoing with partial information, proposed a
generic control rule for such tasks and, using techniques from optimization,
characterized the conditions required for the convergence. We then focused on
one particular task from this class: position and orientation control with a
single rotating camera. We suggested strategies for control and camera motion, and
implemented the 3D task of inserting a rod into a hollow pipe.
K. Kinoshita and M. Lindenbaum, Robotic Control
with Partial Visual Information, ICCV, pp. 883-888, 1998
Teaching
236327 Introduction
to Signal and Image Processing
234262 Logic Design
236815
Computer Vision seminar
Information for current/future graduate students.
You are visitor number 
.