Every time I snorkeled near the Cottesloe groyne, I would see a few of these horned blennies sitting on the rocks underwater. They would just sit there still, so you would have to look carefully. I put these images up on the Dive-Oz forum and Shadowkiller identified them to be the horned blenny (Parablennius intermedius).
I know the image quality isn't that good. But these are the best I could get. It was hard to steady myself when the water kept moving me back and forth.
There are nicer images of horned blennies here. There is a close-up shot which shows you the 'horns'.
The Cottesloe groyne