To address the problem of accurate navigation without relying on additional infrastructures, this paper proposes an accurate dual-foot micro-inertial autonomous navigation system. This system consists of two low-cost inertial measurement units (IMUs) and the inertial tracking algorithms. By fusing the foot-mounted inertial tracking results with the empirical stride size as a constraint, the proposed system can significantly reduce the accumulated error of IMUs and thus improve the tracking accuracy and robustness. Moreover, this paper also presents a map matching algorithm based on the new reduced particle Filter in order to obtain the estimated trajectory on a map in mapped environments, e.g. indoors. In addition, we utilize a backward belief propagation approach to find the initial positions of the trajectories. Real-world experiments have been conducted to validate the accuracy and robustness of the proposed system. It is demonstrated that the pseudo-observation of empirical stride size can significantly reduce the drift of inertial trajectories and the map matching can further improve the tracking accuracy in mapped environments.