During development, infants rapidly build models of the world around them, segmenting the visual scene into clusters of features that can be indexed as proto-objects. These proto-objects form the foundation of more specialised object perception later on, but also act as a means for generalising, comparing and recognising similar objects. This paper takes inspiration from psychological studies to present an approach for building representations of proto-objects that can be learned on-line on a robotic platform and used for object recognition. In particular, from our previous studies of infant visual development, we first identify four types of features; brightness, motion, colour and edges, and then apply heuristics to cluster them into proto-object representations. When correlations of the observed features are made, pairs of features are used to construct graphs that encapsulate information of the observed phenomena. By a three-phase experiment we demonstrate the robot's ability of effectively learn proto-object representations and then, by utilising the graphs, to recognise what is presented to it and report on the impact uncertainties in object recognition have on fixation times.