Topological derivative has been employed for image segmentation and restoration. The topological derivative-based segmentation uses two sparse matrices, and the computational complexity of the segmentation grows up dramatically as the image size increases due to the size of the sparse matrix. Therefore, to provide a fast and accurate segmentation with low complexity, an effective scheme is proposed with keeping the same segmentation performance. To further reduce the computational complexity, the parallel processing structure for the proposed scheme is designed and implemented on graphics processing unit (GPU). In particular, to reduce the computational cost of generating and multiplying sparse matrices that are squared symmetric, the 2D filters consisting of the coefficients at nonborder regions of sparse matrices are defined, and the multiplication is converted into a convolution filtering. In addition, to design a parallel processing for the segmentation with the proposed scheme on a GPU, an image is divided into several blocks and they are processed in parallel. Experimental results show that the proposed scheme for topological derivative-based segmentation reduces the computational complexity ~ 908 times, and the complexity of the proposed scheme is reduced ~ 17 times more from the parallel structure. In particular, the higher efficiency can be obtained from large sized images because the complexity of the proposed scheme does not depend on the image size. Moreover, the proposed scheme can provide almost identical segmentation result with the original sparse matrix-based approach. Therefore, we believe that the proposed scheme can be a useful tool for efficient topological derivative-based segmentation.