Processing ground penetrating radar data to obtain well-focused images for object detection has been an active research area. Phase-shift migration (PSM) is a widely used method since it allows the wave velocity to vary with respect to multi-layer medium. However, this requires pixel-by-pixel calculation of the image, which is time-consuming. This paper presents an extended Omega-k algorithm for multi-layer medium imaging with significantly less computation complexity than the PSM algorithm. The extended Omega-k exploits fast interpolation in the wave-number domain instead of iterative calculating as done by PSM. The method of estimating the wave propagation velocity in different media is also proposed via vertex region extraction for phase compensation and image focusing. Various images of buried targets of a two-layer medium experiment are obtained, which validate the effectiveness of the proposed algorithm, and make it practical for some typical ground-based surveillance applications.