How to give each segment a new colour in image segmentation?
Deep learning based image segmentation is basically pixel-wise image classification.

So instead of predicting a $C$ dimensional vector $\vec{x}$ where $C$ corresponds to the number of class labels, you predict a tensor $x\in\mathbb{R}^{h\times w \times C}$ of the same height and width dimensions as your input image, and with $C$ channels which correspond to the different classes. 

The paper "U-Net: Convolutional Networks for Biomedical Image Segmentation" provides a good overview of the current methods.