Study On Object Detection And The Semidefinite Programming Relaxed Clustering Algorithm

Object detection technology and the clustering algorithms are two important issuesin the fields of computer vision, patterns recognition and intelligent systems. The objectdetectiontechnology, thatmainlydealswiththeaccurateandefficientdetectionofobjectsin images or videos, and the clustering algorithms, that deal with the clustering of similardata, are two foundations of some high-level tasks, such as man-machine interface, en-vironment perception and image understanding. So it is meaningful to research on them.This thesis targets two problems: the problem of pedestrian detection in images which isa special case of general object detection, and the clustering problems with semidefiniteprogramming relaxation.This thesis makes the following four main contributions.(1) A method of extracting dense features, which are distinctive and efficient, isdeveloped to encode image regions for pedestrian detection. The center-symmetric localbinary patterns (CS-LBP) and the center-symmetric local ternary patterns (CS-LTP) areapplied to encode image regions for pedestrian detection for the first time. The CS-LBPandCS-LTP,whicharemodifiedversionsofthefamousLBPandLTP,inheritthedesirablepropertiesofbothLBPandHOGandcancaptureboththetextureinformationandgradientinformation. Besides, they are computational efficient. Firstly, the dense CS-LBP featureextraction method is developed; Secondly,the pyramid CS-LBP and the pyramid CS-LTPfeatureextractionmethodsaredevelopedtogaintheabilityofcapturingricherspatialinformation, and the integral image method is applied to speed up the the extraction offeatures. Experiments on the INRIA pedestrian dataset show that the proposed featuresoutperform HOG and the pyramid HOG features.(2)Some promising nonlinear kernels are designed for Support vector machines. Byusing kernel tricks, some distance-based nonlinear kernel SVM, which have both strongclassification ability and rapid classification speed, are proposed. Firstly, based on L1distance, a nonlinear kernel for SVM is designed and it is equivalent to the famous his-togram intersection kernel. For cross-bin distance is superior to bin-to-bin distance, wepropose a nonlinear kernel for SVM based on Earth mover's distance, which is a kind ofcross-bin distance, and we also propose a pedestrian detection approach, which regardsthe feature extraction and classifier as an unit. Thirdly, a special approximation method is employed to reduce the SVM classifier's complicity, which is reduced to O(n) (n is thedimension of the input features). Finally, experiments on INRIA dataset show that theproposed pedestrian detection approaches outperform the state of the art approach, whichis constructed by the pyramid HOG features with HIK SVM classifier.(3)Featurescombinationmethodsareexaminedtoimprovetheperformanceofpedes-trian detection. The Multiple kernel learning (MKL) method is applied to combine fea-tures for pedestrian detection for the first time. Firstly, the sparse MKL method is em-ployedtocombinesomekindsofdensefeaturesproposedinthisthesis,anditoutperformsthe averaging kernels methods; Secondly, the non-sparse MKL methods is examined tocombinethedensefeaturesanditcanmakeuseofevenmorefeaturesthanthesparseMK-L methods. The experiments on INRIA dataset show that the features combination basedon MKL can significantly improve the pedestrian detection performance. MKL methods.(4) The clustering algorithm with SDP relaxations is studied. The SDP relaxed clus-tering algorithm comes to a SDP problem, which is NP-hard and very expensive to solve.An efficient approach is proposed to solve the SDP problem. Firstly, the dual of the SDPisdeduced and an iterative process, inspiredby the matrix generation algorithm, is used tosolve the SDP problem. At each iteration, Exponentiated gradient algorithm is employedto solve the special subproblem. The iterations stops if some conditions of the originalproblems and the dual are met. The simulating results show that the proposed method cansolve the SDP problems efficiently and it is scalable very well with the matrix dimension.Experiments on UCI dataset show that the proposed SDP relaxed clustering algorithmcan achieve much higher clustering accuracy than K-means and the spectral clusteringalgorithm.