Historical topographic maps are a valuable and often the only data source for tracking long-term land-use changes. Their availability and vast spatio-temporal coverage make these maps an important source of information for climate and earth system modeling (ESM). However, the automated retrieval of complex and compound geographical objects from these historical maps is a challenging task. To facilitate the laborious information extraction from these maps, we present a two-stage machine learning-based approach for segmenting urban land-use from gray-scale scans using only a small set of training samples. We employ a Conditional Random Field (CRF) which obtains its unary potentials from a Random Forest (RF). The method is tested using two inference algorithms. To evaluate the performance and the scalability of the approach over large amounts of data sets, we conduct parallel computing experiments within a High Performance Computing (HPC) environment at the Center for Information Services and High Performance Computing at TU Dresden. We evaluated the methodology on the first Central-European set of trigonometry-based maps (1:25000) from 1850-1940 with large spatial and temporal coverage, which makes them particularly valuable for land-use change research and historical geo-information systems (HGIS). Experimental results indicate the suitability of both, the methodological approach and its parallel implementation.