Automatic annotation of anatomical structures can help simplify work-flow during interventions in numerous clinical applications but usually involves a large amount of annotated data. The complexity of the labeling task, together with the lack of representative data, slows down the development of robust solutions. In this paper, we propose a solution requiring very few annotated cases to label 3D pelvic arterial trees of patients with benign prostatic hyperplasia. We take advantage of Large Deformation Diffeomorphic Metric Mapping (LD-DMM) to perform registration based on meaningful deformations from which we build an atlas. Branch pairing is then computed from the atlas to new cases using optimal transport to ensure one-to-one correspondence during the labeling process. To tackle topological variations in the tree, which usually degrades the performance of atlas-based techniques, we propose a simple bottom-up label assignment adapted to the pelvic anatomy. The proposed method achieves 97.6% labeling precision with only 5 cases for training, while in comparison learning-based methods only reach 82.2% on such small training sets.