Three-dimensional viewpoint invariance can be an important requirement on the representation of surfaces for recognition tasks. In general, the parameters in a parametric surface representation can be arbitrarily defined. A canonical, intrinsic parameterization provides us with a consistent, invariant form for describing surfaces. Our goal here is to define and construct such a parametrization. This paper presents an efficient technique for invariant surface reconstruction from a depth map. Our approach, which is based on a differential geometric analysis of surfaces, is computationally efficient compared to prior invariant representations. We present a two stage technique for the construction of a canonical parameterization of the surface in terms of arc lengths along lines of curvature. The first stage requires the minimization of a parameterized functional, which leads to a locally-coupled, sparse linear system solvable using efficient iterative methods. This minimization yields a surface that is invariant to 3D rigid motion. This is followed by the second stage, involving the computation of canonical parameter curves namely, the lines of curvature, and the numerical generation of a new grid on the surface which incorporates these parameters. We present experimental results on synthetically generated sparse noisy data.