From 5465197675ff82c54b477cebff3be7beccfec560 Mon Sep 17 00:00:00 2001 From: Vasil Zlatanov Date: Tue, 12 Feb 2019 20:11:42 +0000 Subject: Fixes to intro --- report/paper.md | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'report') diff --git a/report/paper.md b/report/paper.md index d5d5d37..bbd7d73 100644 --- a/report/paper.md +++ b/report/paper.md @@ -6,8 +6,7 @@ A common technique for codebook generation involves utilising K-means clustering image descriptors. In this way descriptors may be mapped to *visual* words which lend themselves to binning and therefore the creation of bag-of-words histograms for the use of classification. -In this courseworok 100-thousand descriptors have been extracted through SIFT to build the visual vocabulary from the -Caltech dataset. +In this courseworok 100-thousand random SIFT descriptors of the Caltech dataset are used to build the K-means visual vocabulary. ## Vocabulary size @@ -15,9 +14,9 @@ The number of clusters or the number of centroids determines the vocabulary size ## Bag-of-words histogram quantisation of descriptor vectors -An example histograms for training and testing images is shown on figure \ref{fig:histo_tr}, computed with a vocubulary size of 100. The histograms appear to have similar counts for the same words, demonstrating they had a descriptors which matched the *keywowrds* in similar proportions. We later look at the effect of the vocubalary size (as determined by the number of K-means centroids) on the classificaiton accuracy in figure \ref{fig:km_vocsize}. A small vocabulary size turns out to misrepresent the information contained in the different patches, resulting in poor classification accuracy. When the vocabulary size gets too big (too many k-mean centroids), the result is instead overfitting. Figure \ref{fig:km_vocsize} shows a plateau after 60 cluster centers. +An example histograms for training and testing images is shown on figure \ref{fig:histo_tr}, computed with a vocubulary size of 100. The histograms of the same class appear to have comparable magnitudes for their respective keywords, demonstrating they had a similar number of descriptors which mapped to each of the clusters. The effect of the vocubalary size (as determined by the number of K-means centroids) on the classificaiton accuracy is shown in figure \ref{fig:km_vocsize}. A small vocabulary size tends to misrepresent the information contained in the different patches, resulting in poor classification accuracy. Conversly a large vocabulary size (many K-mean centroids), may display overfitting. In our tests, we observe a plateau after a cluster count of 60 on figure \ref{fig:km_vocsize}. -The time complexity of quantisation with a K-means codebooks is $O(DNK)$ , where N is the number of entities to be clustered (descriptors), D is the dimension (of the descriptors) and K is the cluster count @cite[km-complexity]. As the computation time is high, the tests we use a subsample of descriptors to compute the centroids. An alternative method we tried is applying PCA to the descriptors vectors to improve time performance. However in this case the descriptors' size is relatively small, and for such reason we opted to avoid PCA for further training. +The time complexity of quantisation with a K-means codebooks is $O(DNK)$, where N is the number of entities to be clustered (descriptors), D is the dimension (of the descriptors) and K is the cluster count @cite[km-complexity]. As the computation time is high, the tests we use a subsample of descriptors to compute the centroids (a random selection of 100 thousand descriptors). An alternative method we tried is applying PCA to the descriptors vectors to improve time performance. However in this case the descriptors' size is relatively small, and for such reason we opted to avoid PCA for further training. K-means is a process that converges to local optima and heavilly depends on the initialization values of the centroids. Initializing k-means is an expensive process, based on sequential attempts of centroids placement. @@ -50,7 +49,7 @@ for K-means 100 cluster centers. \end{center} \end{figure} -Random forests will select a random number of features on which to apply a weak learner (such as axis aligned split) and then select the best feature of the selected ones to perform the split on, based on some criteria (our results use the *Gini index*). The fewer features that are compared for each split the quicker the trees are built and the more random they are. Therefore the randomness parameter can be considered the number of features used when making splits. We evaluate accuracy given different randomness when using a K-means vocabulary in figure \ref{fig:kmeanrandom}. The results in the figure use a forest size of 100 as we found that this estimatator count the improvement for $\sqrt{n}$ performance gains tend to plateau. +Random forests will select a random number of features on which to apply a weak learner (such as axis aligned split) and then chose the best feature of the sampled ones to perform the split on, based on a given criteria (our results use the *Gini index*). The fewer features that are compared for each split the quicker the trees are built and the more random they are. Therefore the randomness parameter can be considered the number of features used when making splits. We evaluate accuracy given different randomness when using a K-means vocabulary in figure \ref{fig:kmeanrandom}. The results in the figure use a forest size of 100 as we found that this estimatator count the improvement for $\sqrt{n}$ performance gains tend to plateau. \begin{figure}[H] \begin{center} -- cgit v1.2.3-54-g00ecf From 288e28070d27c496d6ac4af5676734451f8430e9 Mon Sep 17 00:00:00 2001 From: Vasil Zlatanov Date: Tue, 12 Feb 2019 20:13:27 +0000 Subject: Properly reference --- report/paper.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'report') diff --git a/report/paper.md b/report/paper.md index af3f8d3..06d8357 100644 --- a/report/paper.md +++ b/report/paper.md @@ -16,7 +16,7 @@ The number of clusters or the number of centroids determines the vocabulary size An example histograms for training and testing images is shown on figure \ref{fig:histo_tr}, computed with a vocubulary size of 100. The histograms of the same class appear to have comparable magnitudes for their respective keywords, demonstrating they had a similar number of descriptors which mapped to each of the clusters. The effect of the vocubalary size (as determined by the number of K-means centroids) on the classificaiton accuracy is shown in figure \ref{fig:km_vocsize}. A small vocabulary size tends to misrepresent the information contained in the different patches, resulting in poor classification accuracy. Conversly a large vocabulary size (many K-mean centroids), may display overfitting. In our tests, we observe a plateau after a cluster count of 60 on figure \ref{fig:km_vocsize}. -The time complexity of quantisation with a K-means codebooks is $O(DNK)$, where N is the number of entities to be clustered (descriptors), D is the dimension (of the descriptors) and K is the cluster count @cite[km-complexity]. As the computation time is high, the tests we use a subsample of descriptors to compute the centroids (a random selection of 100 thousand descriptors). An alternative method we tried is applying PCA to the descriptors vectors to improve time performance. However in this case the descriptors' size is relatively small, and for such reason we opted to avoid PCA for further training. +The time complexity of quantisation with a K-means codebooks is $O(DNK)$, where N is the number of entities to be clustered (descriptors), D is the dimension (of the descriptors) and K is the cluster count [@km-complexity]. As the computation time is high, the tests we use a subsample of descriptors to compute the centroids (a random selection of 100 thousand descriptors). An alternative method we tried is applying PCA to the descriptors vectors to improve time performance. However in this case the descriptors' size is relatively small, and for such reason we opted to avoid PCA for further training. K-means is a process that converges to local optima and heavilly depends on the initialization values of the centroids. Initializing k-means is an expensive process, based on sequential attempts of centroids placement. -- cgit v1.2.3-54-g00ecf