The body constitution is much related to the diseases and the corresponding treatment programs in Traditional Chinese Medicine. It can be recognized by the tongue image diagnosis, so that it is essentially regarded as a problem of tongue image classification, where each tongue image is classified into one of nine constitution types. This paper first presents a system framework to automatically identify the constitution through natural tongue images, where deep convolutional neural networks are carefully designed for tongue coating detection, tongue coating calibration, and constitution recognition. Under the system framework, a novel complexity perception (CP) classification method is proposed to nicely perform the constitution recognition, which can better deal with the bad influence of the variation of environmental condition and the uneven distribution of the tongue images on constitution recognition performance. CP performs the constitution recognition based on the complexity of individual tongue images by selecting the classifier with the corresponding complexity. To evaluate the performance of the proposed method, experiments are conducted on three sizes of clinic tongue images from hospitals. The experimental results illustrate that CP is effective to improve the accuracy of body constitution recognition. Copyright © 2019 Elsevier B.V. All rights reserved.