Given an inhomogeneous chain embedded in a noisy image, we consider the conditions under which such an embedded chain is detectable. Many applications, such as detecting moving objects, detecting ship wakes, can be abstracted as the detection on the existence of chains. In this work, we provide the detection algorithm with low order of computation complexity to detect the chain and the optimal theoretical detectability regarding SNR (signal to noise ratio) under the normal distribution model. Specifically, we derive an analytical threshold that specifies what is detectable. We design a longest significant chain detection algorithm, with computation complexity in the order of $O(nlog n)$. We also prove that our proposed algorithm is asymptotically powerful, which means, as the dimension $n rightarrow infty$, the probability of false detection vanishes. We further provide some simulated examples and a real data example, which validate our theory.
Download