A dynamic visual search framework based mainly on inner-scene
similarity is proposed. Algorithms as well as measures quantifying
the difficulty of search tasks are suggested.
Given a number of candidates (e.g. sub-images), our basic
hypothesis is that more visually similar candidates are more
likely to have the same identity. Both deterministic and
stochastic approaches, relying on this hypothesis, are used to
quantify this intuition.
Under the deterministic approach, we suggest a measure similar to
Kolmogorov’s $\epsilon$-covering that quantifies the difficulty of
a search task and bounds the performance of all search algorithms.
We also suggest a simple algorithm that meets this bound.
Under the stochastic approach, we model the identities of the
candidates as correlated random variables and characterize the task
using its second order statistics. We derive a search procedure based
on minimum MSE linear estimation. Simple extensions enable the
algorithm to use top-down and/or bottom-up information, when
available. Both approaches are evaluated experimentally.
A joint work with Tamar Avraham.