We present TerraPN, a novel method that learns the surface properties\n(traction, bumpiness, deformability, etc.) of complex outdoor terrains directly\nfrom robot-terrain interactions through self-supervised learning, and uses it\nfor autonomous robot navigation. Our method uses RGB images of terrain surfaces\nand the robot's velocities as inputs, and the IMU vibrations and odometry\nerrors experienced by the robot as labels for self-supervision. Our method\ncomputes a surface cost map that differentiates smooth, high-traction surfaces\n(low navigation costs) from bumpy, slippery, deformable surfaces (high\nnavigation costs). We compute the cost map by non-uniformly sampling patches\nfrom the input RGB image by detecting boundaries between surfaces resulting in\nlow inference times (47.27% lower) compared to uniform sampling and existing\nsegmentation methods. We present a novel navigation algorithm that accounts for\na surface's cost, computes cost-based acceleration limits for the robot, and\ndynamically feasible, collision-free trajectories. TerraPN's surface cost\nprediction can be trained in ~25 minutes for five different surfaces, compared\nto several hours for previous learning-based segmentation methods. In terms of\nnavigation, our method outperforms previous works in terms of success rates (up\nto 35.84% higher), vibration cost of the trajectories (up to 21.52% lower), and\nslowing the robot on bumpy, deformable surfaces (up to 46.76% slower) in\ndifferent scenarios.\n