This research presents a novel methodology that combines stereo vision and parallel processing, based on GPU and the use of binary descriptors, for fast High-Level Structures extraction. Typical stereo algorithms require an image rectification stage that has to run on a frame-to-frame basis, increasing the computational burden and with the possibility of compromising high frame rate operation. Hence, it is proposed to use a semi-calibrated stereo approach, meaning that only calibration of extrinsic parameters of the stereo rig is carried out, thus avoiding a rectification process of the frames captured by the stereo camera. For the latter, the proposed approach relies on feature matching of salient points detected on the stereo images, from which image correspondences are obtained. These correspondences are triangulated to generate a point cloud that is passed to a plane fitting module. As feature matching is a cumbersome task, this study presents a novel GPU architecture to accelerate such process, thus achieving a real-time performance of up to 50 fps for the whole process. To demonstrate our approach, we also present an augmented reality application that exploits the planes extracted with our approach.