Unexploded ordnance (UXO) pose a significant threat to post-conflict communities, and current efforts to locate bombs rely on time-intensive and dangerous in-person enumeration. Very high resolution (VHR) sub-meter satellite images may offer a low-cost and high-efficiency approach to automatically detect craters and estimate UXO density. Machine-learning methods from the meteor crater literature are ill-suited to find bomb craters, which are smaller than meteor craters and have high appearance variation, particularly in spectral reflectance and shape, due to the complex terrain environment. A two-stage learning-based framework is created to address these challenges. First, a simple and loose statistical classifier based on histogram of oriented gradient (HOG) and spectral information is used for a first pass of crater recognition. In a second stage, a patch-dependent novel spatial feature is developed through dynamic mean-shift segmentation and SIFT descriptors. We apply the model to a multispectral WorldView-2 image of a Cambodian village, which was heavily bombed during the Vietnam War. The proposed method increased true bomb crater detection by over 160 percent. Comparative analysis demonstrates that our method significantly outperforms typical object-recognition algorithms and can be used for wide-area bomb crater detection. Our model, combined with declassified records and demining reports, suggests that 44 to 50 percent of the bombs in the vicinity of this particular Cambodian village may remain unexploded.