In this paper a novel algorithm for distant aircraft detection for visual sense-and-avoid for UAV is presented. The algorithm uses local edge density to partition the frame into two types of regions. The first type is the unstructured or homogeneous part like sky region and the second part where there is a structured background, like high contrast clouds or terrain regions. The airplanes are detected on the two types of regions with different strategies. The algorithm was planned to run in an embedded environment with low power consumption, thus it can be run onboard of a small or mid-size UAV. First steps towards the GPU implementation on the nVidia Jeston TK1 development board are done and also presented in the paper.