Two-dimensional visual search

Consider the problem of sequentially searching for a single target in an image. Let the image be divided into M × M equal sized segments where M determines the resolution of the search. The goal is to find the segment that contains the target quickly and accurately. In each step, the player can visually inspect an allowable combination of the segments, and the outcome of the inspection is noisy. In this paper, a lower bound on the optimal total cost is derived. Furthermore, two heuristic policies are considered: A policy that visually inspects a segment with the highest probability of having the target; and a policy that in each step inspects a combination that maximizes the Extrinsic Jensen- Shannon divergence. Via numerical and asymptotic analysis, the performance of the above policies are investigated.