This paper presents a novel two-stage vessel segmentation framework applied to retinal fundus images. In the first stage a convolutional neural network (CNN) is used to correlate an image patch with a corresponding groundtruth reduced using Totally Random Trees Embedding. In the second stage training patches are forward propagated through CNN to create a visual codebook. The codebook is used to build a generative nearest neighbour search space that can be queried by feature vectors created through forward propagating previously-unseen patches through CNN. The proposed framework is able to generate segmentation patches that were not seen during training. Evaluated using publicly available datasets (DRIVE, STARE) demonstrated better performance than state-of-the-art methods in terms of multiple evaluation metrics. The accuracy, robustness, speed and simplicity of the proposed framework demonstrates its suitability for automated vessel segmentation.