Near-optimal detection of geometric objects by fast multiscale methods
Near-optimal detection of geometric objects by fast multiscale methods
复制标题
DOI：
10.1109/tit.2005.850056
复制
发表时间：
2005-07-01
影响因子：
2.5
通讯作者：
Huo, XM
中科院分区：
文献类型：
--
作者：
Arias-Castro, E;Donoho, DL;Huo, XM
我们在嘈杂的数据中构建了“几何”对象的检测器。示例包括一个具有二维图像数据中未知长度，位置和方向的线段的检测器，并带有添加性白色高斯噪声。我们关注以下两个问题。 ，检测信号略微超过检测阈值所需的复杂性。我们描述了涵盖几类几何定义信号的一般方法。例如，使用一维数据，在间隔上具有较高平均值的信号，并且在D维数据中，信号在矩形，球或椭球上具有均值升高的信号。在所有这些问题中，我们表明一种天真或直接的方法会导致检测阈值和算法在渐近远离最佳的算法。同时，对这些对象类别的多尺寸几何分析使我们能够为近距离检测器得出渐近的最佳检测阈值和快速算法。
We construct detectors for "geometric" objects in noisy data. Examples include a detector for presence of a line segment of unknown length, position, and orientation in two-dimensional image data with additive white Gaussian noise. We focus on the following two issues.i) The optimal detection threshold-i.e., the signal strength below which no method of detection can be successful for large dataset size n.ii) The optimal computational complexity,of a near-optimal detector, i.e., the complexity required to detect signals slightly exceeding the detection threshold.We describe a general approach to such problems which covers several classes of geometrically defined signals; for example, with one-dimensional data, signals having elevated mean on an interval, and, in d-dimensional data, signals with elevated mean on a rectangle, a ball, or an ellipsoid. In all these problems, we show that a naive or straightforward approach leads to detector thresholds and algorithms which are asymptotically far away from optimal. At the same time, a multiscale geometric analysis of these classes of objects allows us to derive asymptotically optimal detection thresholds and fast algorithms for near-optimal detectors.