Study On Shape Decomposition And Machine Learning Based Image Retrieval

Thanks to the rapid progress of imaging and internet technologies, we are now livedin a world which images are part of our daily lives. How to manage the overwhelmingamount of image data and how to retrieve relevant information in a short time are becom-ing more and more important to fulfill the pressing desire of the user. However, theseContent-Based Image Retrieval technologies are suffered from the semantic gap betweenlow-level image features and higher-level user concepts. In this dissertation, we try toreduce the semantic gap in two folds. The first part focuses on shape decomposition, abasic problem of shape-based image feature. The second part studies on learning-basedimage hashing, image classification and similarity analysis technologies. The main con-tributions are as follows:(1) A novel2D shape decomposition model is proposed based on the short-cut rule.Theshort-cutruleoriginatesfromcognitionresearch,andstatesthatthehumanvisualsys-tem prefers to decompose an object into parts using the shortest possible cuts. We deviseand implement a computational model for the short-cut rule and apply it to the problemof shape decomposition, which achieves decomposition results well corresponded to hu-man intuition. Furthermore, we define a quantitative evaluation for shape decompositionmethods, which are often judged by inspection of a small number of examples, based onthe results of psychological experiments.(2) A novel unsupervised maximum variance image hashing approach is developed.The essential purpose of image hashing is to map high dimensional image features intolowdimensionalbinarycodes. Inspiredbytheclassicnon-lineardimensionalityreductionalgorithm—maximum variance unfolding, we propose maximum variance hashing. Theideaistomaximizethetotalvarianceofthehashcodeswhilepreservingthelocalstructureof the training data. To solve the derived optimization problem, we propose a columngeneration algorithm, and then extend it using anchor graphs to reduce the computationalcost. Experiments on large-scale image datasets demonstrate that the proposed methodavoids the crowd problem and can maintain the manifold structure of the training data insome sense.(3) A novel simplex coding multi-class boosting algorithm is developed. Conven-tional study usually decompose a multi-class problem into multiple independent binary problems. Most of them have complexity which is more than linear in the number ofclasses. We propose a new optimization objective by combining simplex coding and leastsquare support vector machine. It is then solved in a boosting framework by regarding thecombine of weak learners as a kernel function. Training complexity of the proposed algo-rithm is not very sensitive to the number of classes, while it can achieve high accuraciesin image classification tasks.(4)Anovelsimilaritydiffusionprocesswhichcanfusemultiplefeaturesisproposed.Linearlycombinationofmultiplefeaturesmaysubmergeusefulinformationintotheback-ground. We therefore propose to partly fuse them by setting non-adjacent edges to zerosin the kNN graph of each feature, and then propagate on the combined graph to exploitthe underlying structure of the dataset. This approach achieves a score of100%in the“bull’s eye test” on the MPEG-7shape database, which is the best reported result to date.(5) A self-adaptive neighborhood selection algorithm is proposed to overcome thedifficulty of neighborhood parameter setting in learning-based image retrieval algorithm-s. It briefly is a self-adaptive variation of nearest neighborhood, which the radius isdetermined by the dominant set of a weighted initial neighborhood. The image retrievalexperimental results demonstrate that the proposed method can produce comparable re-sults without trial-and-error for the neighborhood size.