Kernel Approximations - KA

Reference: I. S. Montagner, R. Hirata, N. S. T. Hirata and S. Canu, "Kernel Approximations for W-Operator Learning," 2016 29th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), Sao Paulo, 2016, pp. 386-393.

KA is a method that employs kernels to process image. Think of a kernel as a similarity function between two images. It they are similar its value is close to 1, but if they are different it is closer to 0. There are two kernels in TRIOS: Gaussian (adequate for gray-level images) and Polynomial (adequate for binary images). KA works as a feature extractor such that the inner product between two computed feature vectors (two image patches) represents their similarity.

Although KA can be used with any classifier, best results are achieved using SVMs. Since this classifier may require a large amount of memory, we only use a subset of the training images for training (otherwise memory requirements blow up). In both examples we use scikit-learn's implementation of linear SVMs and a fixed subset of 20.000 training samples.

Binary images and the polynomial kernel

To use a polynomial kernel we must determine the degree of the polynomial used. In all experiments in the reference article found 3 to be the best value for this parameter. We also need to determine the number of computed features. We fix this parameter as 1000 in this example. The larger the number of computed features the larger the memory consumption will be.

# file docs/examples/methods/ka1.py
from trios.contrib.kern_approx import NystromFeatures
from trios.classifiers import SKClassifier
from trios.feature_extractors import RAWFeatureExtractor
import trios
import numpy as np

from sklearn.svm import LinearSVC

if __name__ == '__main__':
    np.random.seed(10) 
    images = trios.Imageset.read('../jung-images/training.set')
    test = trios.Imageset.read('../jung-images/test.set')

    domain = np.ones((9, 7), np.uint8)
    raw = RAWFeatureExtractor(domain)
    ka_features = NystromFeatures(raw, images, n_components=1000, 
        kernel='poly', degree=3, batch_size=20000)
    svm = SKClassifier(LinearSVC(), partial=True)
    op = trios.WOperator(domain, svm, ka_features)
    op.train(images)

    print('Error:', op.eval(test))

Error: 0.007091876164931582

Gray level images and the gaussian kernel

To use a gaussian kernel we must determine its bandwidth \(\gamma\), which is typicall a small value between 0.1 and 0.00001. In the article above we have determined \(\gamma=0.01\) as a good value for the DRIVE dataset and use 200 computed features.

This examples needs the DRIVE dataset (download)

# file docs/examples/methods/ka2.py
from trios.contrib.kern_approx import NystromFeatures
from trios.classifiers import SKClassifier
from trios.feature_extractors import Aperture
import trios
import numpy as np

from sklearn.svm import LinearSVC

from aperture import training, testset

if __name__ == '__main__':
    np.random.seed(10) 
    domain = np.ones((11, 11), np.uint8)
    ap = Aperture(domain, k=10, mul=0.5)
    ka_features = NystromFeatures(ap, training, n_components=200, 
        kernel='gaussian', gamma=0.01, batch_size=20000)
    svm = SKClassifier(LinearSVC(), partial=True)

    op = trios.WOperator(domain, svm, ka_features)
    op.train(training)

    print('Accuracy:', 1 - op.eval(testset[:2]))

Accuracy: 0.934125981168681

This value is much better than the one we obtained using Aperture alone! By using larger computed feature vectors and larger training sets we can improve even more this result.