Vessel width estimation has a wide range of applications in disease diagnosis and treatment. In this paper, vessel width estimation is cast as a regression problem, and a novel Convolutional Neural Network (CNN) based method is proposed for vessel width estimation. In our CNN-based method, the idea of divide-and-conquer is introduced to solve the challenge of imbalanced training samples. Besides, in order to solve the shortage of training samples required by CNN, a vessel width label generation method is proposed to generate width labels from vessel segmentation labels. In the experiments, we apply our vessel width label generation method and CNN-based width estimation method to two tasks which are retinal vessel width estimation and coronary artery width estimation. Experimental results show that our width label generation method can generate sufficiently realistic width labels using accurate segmentation labels. Also, our CNN-based method can solve the challenge of imbalanced training samples, achieving state-of-the-art performance with less inference time.