This paper proposes a fast image segmentation method that gives high segmentation performance as graph-cut based methods. Graph-cut based image segmentation methods show high segmentation performance, however, the computational complexity is high to solve a computationally-intensive eigen-system. This is because solving eigen-system depends on the size of square matrix obtained from similarities between all pairs of pixels in the input image. Therefore, the proposed method uses the small-size square matrix, which is obtained from all the similarities among regions obtained by segmenting locally an image into several regions by graph-based method. Experimental results show that the proposed multi-scale image segmentation method using the algebraic multi-grid shows higher performance than existing methods.