alex dodge (°_°)

A System for Non-linear Exploration of Visual Information

Abstract:

The amount of personal data in the form of social media, email, music, video, and personal photos continues to grow at a rapid pace. While some advances have been made in the more conventional methods of indexing and searching large catalogues of images, few approaches address the need for a system that enables users to explore their personal libraries in a non-linear and dynamic way. In this paper we propose an interactive system that enables users to explore their personal photographs by dynamically organizing them based on multiple image attributes such as, but not limited to: time, location, face recognition, color, as well as social attributes. A prototype system and interface were developed. The underlying processing of image data employed a suite of algorithmic methods including hierarchical clustering, face detection and recognition, histogram analysis, and others…

Face Recognition, XML, initial clusters…
Closing in on a working backend system

We, being myself and Akira Shibata, accomplished a lot over the break. The current face recognition system based on Phillip Wagner’s Eigen Face implementation is working and provides a good starting point that can be improved upon later. For now it provides us with fit values that we can use to cluster faces with.

Above is an Eigen Face reconstruction using a combination of faces we extracted, about 500 faces. For fun we decided to run our PCA Test (Principal Component Analysis) but with the test image included in the training set (below). The result is clear with the image rapidly converging. Beside it is a colorized grayscale version of Eigen Faces a useful  method for showing variation that the human eye has a hard time discerning in gray. Also a short animation combining the progression of all Eigen Faces.

XML

Next we began anticipating the need to make data available to a front-end interactive system. We researched a number of methods including existing xml schemas but in the end nothing existed that fit our needs so we created our own that our Python can generate:

<Photo>
    <DayOfWeek>Wednesday</DayOfWeek>
    <Month>3</Month>
    <UnixTime>1268248703.0</UnixTime>
    <NumFaces>0</NumFaces>
    <Longitude>35.6816666667</Longitude>
    <Filename>IMG_2255.jpg</Filename>
    <Latitude>139.706833333</Latitude>
    <Year>2010</Year>
    <Date>10</Date>
    <TimeOfDay>14:18</TimeOfDay>
    <Size>(640, 480)</Size>
</Photo>

Clustering

Finally we began what we had really been waiting for… clustering. We are still trying to make our way around Matplotlib, but we were able to make an initial time-based cluster and make a combination plot with a dendrogram (seen above). Because we tend to think of time in a linear fashion the plotted representation may seem couter intuitive at first, but this cluster is our first attempt toward very rudimentary event detection. We are essentially trying finding a likeness among the photos based entirely on the EXIF time data represented in UNIX time. The dendrogram method configures the clusters so that things are in a rough sequence from left to right, but it also avoids intersecting itself so there is some shuffling, but we can interpret the dendrogram as illustrating a series of larger events containing various levels of sub-events. The dark blue represents more recent events with the lighter colors receding into the past. One can imagine how this method of event detection could become more interesting with histogram and faces combined, but already it shows different and possibly interesting way of interpreting one’s personal data.

Histograms and Frequency
…ever closer to face clustering, but not just yet.

Using the birthday data set a plot of face frequency over 5 years. Not especially meaningful as it is, but getting ready for face comparison and clustering.

Playing with im.histogram() method in PIL (Python Image Library) to cluster images based on their RGB histograms.

A simplified approach to PCA with PIL an Numpy from Jan Erik Solem’s blog.

from PIL import Image
from numpy import *
 
def pca(X):
  # Principal Component Analysis
  # input: X, matrix with training data as flattened arrays in rows
  # return: projection matrix (with important dimensions first),
  # variance and mean
 
  #get dimensions
  num_data,dim = X.shape
 
  #center data
  mean_X = X.mean(axis=0)
  for i in range(num_data):
      X[i] -= mean_X
 
  if dim>100:
      print 'PCA - compact trick used'
      M = dot(X,X.T) #covariance matrix
      e,EV = linalg.eigh(M) #eigenvalues and eigenvectors
      tmp = dot(X.T,EV).T #this is the compact trick
      V = tmp[::-1] #reverse since last eigenvectors are the ones we want
      S = sqrt(e)[::-1] #reverse since eigenvalues are in increasing order
  else:
      print 'PCA - SVD used'
      U,S,V = linalg.svd(X)
      V = V[:num_data] #only makes sense to return the first num_data
 
  #return the projection matrix, the variance and the mean
  return V,S,mean_X

Extracting EXIF data from images for clusteringI was able to use the Python image library (PIL) to extract time and GPS location data from a test image set. The test set is comprised of roughly 500 images from various devices including iPhone and point and shoot cameras. The images are from birthday parties over a 5 year period.

These simple plots of EXIF time and location. The frequency of images can clearly be seen with spikes each year. The two points in the GPS plot are Tokyo and New York with 4 of the 5 birthdays were in New York and 1 was in Tokyo.

Research on face recognition has yielded som promising leads, especially a 2011 paper:

Zhu, C., Wen, F., & Sun, J. (2011). A rank-order distance based clustering algorithm for face tagging. Cvpr 2011, 481-488. Ieee. doi:10.1109/CVPR.2011.5995680

This paper describes a method of clustering faces using “rank-order distance” in which a clustering can be optimized by understanding a face’s neighbors:

“The Rank-Order distance is motivated by an observation that faces of the same person usually share their top neighbors. Specifically, for each face, we generate a ranking order list by sorting all other faces in the dataset by absolute distance (e. g., L1 or L2 distance between extracted face recognition features).”