Nonlinear dimensionality reduction by locally linear embedding

"Nonlinear dimensionality reduction by locally linear embedding," Roweis & Saul, Science, 2000.



This paper present an unsupervised learning algorithm, locally linear embedding (LLE), which can construct a neighborhood preserving mapping based on the steps below:

1. Assign K neighbors for each data point Xi.
2. Reconstruct Xi from its neighbors with linear weight, by minimize the cost function
3. Compute the low-dimensional embedding vector Yi, by minimize the function

read more...

Eigenfaces for Reconition

"Eigenfaces for recognition," M Turk, A Pentland - Journal of Cognitive Neuroscience, 1991.




This paper propose a feature for dimension reduction. The significant features are known as "eigenfaces", and the center idea is to project face images onto the eigenfaces based on PCA. The main procedure is:

1. Given a set of face images :
2. Define the average face :
3. Each face differs from the average face :
4. Construct the M by M matrix L = A'A in replace of the covariance matrix C since there are at most M-1 meaningful eigenfaces, where M is the number of training data and
5. Now we can use L to find eigenfaces :

I think the "eigenfaces" is an intelligent and interesting idea in 1990s like today's SIFT and visual words, even though the times that computer is not so powerful nowadays. Although the approach is not work with unclear face images, it still gives us a idea for handling today's multimedia data.


read more...

[Note] 20090325

• feature significance (without label / subset)
  
• tf-idf, c-tf-idf
  
• feature significance (with label / subset)
  
• MI, x^2, correlation (subset)
  
• exploiting feature correlation (without label / transform)
  
• PCA, manifold methods (LLE, ISOMAP)
  
• exploiting feature correlation (with label / transform)
  
• fisher (LDA)
  
• optimizing classification (subset)
  
• adaboost, maximum entropy
  
• exploiting hidden semantics (topics)
  
• pLSA, SVD, LSI, Information Bottleneck
  

read more...

ContextSeer: Context Search and Recommendation at Query Time for Shared Consumer Photos

"ContextSeer: Context Search and Recommendation at Query Time for Shared Consumer Photos," Yi-Hsuan Yang, Po-Tun Wu, Ching-Wei Lee, Kuan-Hung Lin, Winston H. Hsu, ACM Multimedia 2008.




The advent of media-sharing sites has drastically increased the volume of multimedia resources on the web, yet these collections become more difficult for searching and navigating result from their magnitude. This paper present a novel search system called ContextSeer to improve search quality:

1. To develop wc-tf-idf, by improving the concept tf-idf with more emphasis on the higher-ranked object, since the context cues of lower-ranked objects should be less important than those of higher- ranked ones.
2. To propose a efficient canonical image selection algorithm cannoG, which generates multiple representative views related to the query.
   
3. To form a new benchmark Flickr550, which contains 0.5 million public photos from Flickr through Flickr API, for evaluating ContextSeer.

read more...

Distinctive Image Features from Scale-Invariant Keypoints

"Distinctive Image Features from Scale-Invariant Keypoints," Lowe, IJCV, 2004.




This paper presents a new method for image matching, which is called Scale Invariant Feature Transform(SIFT). SIFT can extract distinctive features from image data, and the features are invariant to image rotation and scale, and robust matching across affine distortion, addition of noise, and change in illumination.

1. Detection of scale-space extrema: use difference of Gaussian(DOG) to identify the candidate keypoints.
2. Accurate keypoint localization: do keypoint selection for rejecting some unstable candidate keypoints.
3. Orientation assignment: assign an orientation to each keypoint based on local image properties for invariance to image rotation.
   
4. Local image descriptor: tranform into a representation with above parameters.
   

I think local points is an creative idea that I have learnt in retrieve system, and the accuracy of SIFT is also amazing to me. Clustering had been move on a big step since SIFT.



read more...