We combine ideas from shock graph theory with more recent appearance-based\nmethods for medial axis extraction from complex natural scenes, improving upon\nthe present best unsupervised method, in terms of efficiency and performance.\nWe make the following specific contributions: i) we extend the shock graph\nrepresentation to the domain of real images, by generalizing the shock type\ndefinitions using local, appearance-based criteria; ii) we then use the rules\nof a Shock Grammar to guide our search for medial points, drastically reducing\nrun time when compared to other methods, which exhaustively consider all points\nin the input image;iii) we remove the need for typical post-processing steps\nincluding thinning, non-maximum suppression, and grouping, by adhering to the\nShock Grammar rules while deriving the medial axis solution; iv) finally, we\nraise some fundamental concerns with the evaluation scheme used in previous\nwork and propose a more appropriate alternative for assessing the performance\nof medial axis extraction from scenes. Our experiments on the BMAX500 and\nSK-LARGE datasets demonstrate the effectiveness of our approach. We outperform\nthe present state-of-the-art, excelling particularly in the high-precision\nregime, while running an order of magnitude faster and requiring no\npost-processing.\n