Abstract: This paper presents two novel robot self-localization methods based on planar laser measurement. The first one is an improved Hough density spectrum based method, into which a novel Hough density spectrum is introduced, and by which the location accuracy and robustness can be both enhanced. The key advantageous aspect of our new spectrum is that its implementation does not involve any discretization error in the Hough space, which is the major source of location inaccuracy in the conventional method. The second one is an Fourier-Mellin transform based method. This method first converts the two measurement point sets into two binary images, then uses the Fourier-Mellin based image matching technique, a popular technique in image matching field, to determine the rotation parameter and finally invokes a standard ICP technique with the Hausdorff distance as its cost to estimate the two translation parameters. Experimental results show that both methods can perform robustly and accurately.