Human identification at a distance has received significant interest due to the ever increasing surveillance infrastructure. Biometrics such as face and gait offer a suitable physical attribute to uniquely identify people from a distance. When linking this with human perception, these biometrics suffer from the semantic gap which is the difference between how people and how biometrics represent and describe humans. Semantic biometrics bridges this gap, allowing conversions between gait biometrics and semantic descriptions. One possible application of semantic biometrics is to automatically search surveillance footage for a person who best matches a given semantic description - possibly obtained from an eyewitness report. We now exploit patterns and structure within the physical descriptions to be able to predict occluded or erroneous data, thereby widening application potential. We show how imputation techniques can be used to increase accuracy and robustness of automatic semantic annotation of gait signatures.