diff options
Diffstat (limited to 'report')
| -rw-r--r-- | report/fig/2pixels_kmean.pdf | bin | 14662 -> 15084 bytes | |||
| -rw-r--r-- | report/fig/km-histogram.pdf | bin | 13076 -> 13511 bytes | |||
| -rw-r--r-- | report/fig/km-histtest.pdf | bin | 13919 -> 14352 bytes | |||
| -rw-r--r-- | report/paper.md | 14 |
4 files changed, 10 insertions, 4 deletions
diff --git a/report/fig/2pixels_kmean.pdf b/report/fig/2pixels_kmean.pdf Binary files differindex 1a95bad..f75d200 100644 --- a/report/fig/2pixels_kmean.pdf +++ b/report/fig/2pixels_kmean.pdf diff --git a/report/fig/km-histogram.pdf b/report/fig/km-histogram.pdf Binary files differindex f459978..99d1658 100644 --- a/report/fig/km-histogram.pdf +++ b/report/fig/km-histogram.pdf diff --git a/report/fig/km-histtest.pdf b/report/fig/km-histtest.pdf Binary files differindex c7da428..ccc09f0 100644 --- a/report/fig/km-histtest.pdf +++ b/report/fig/km-histtest.pdf diff --git a/report/paper.md b/report/paper.md index d9cda73..5c538e9 100644 --- a/report/paper.md +++ b/report/paper.md @@ -6,18 +6,24 @@ 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 selected to build the visual vocabulary from the +In this courseworok 100-thousand descriptors have been extracted through SIFT to build the visual vocabulary from the Caltech dataset. ## Vocabulary size -The number of clusters or the number of centroids determine the vocabulary size when creating the codebook with the K-means the method. Each descriptor is mapped to the nearest centroid, and each descriptor belonging to that cluster is mapped to the same *visual word*. This allows similar descriptors to be mapped to the same word, allowing for comparison through bag-of-words techniques. +The number of clusters or the number of centroids determines the vocabulary size when creating the codebook with the K-means the method. Each descriptor is mapped to the nearest centroid, and each descriptor belonging to that cluster is mapped to the same *visual word*. This allows similar descriptors to be mapped to the same word, allowing for comparison through bag-of-words techniques. ## Bag-of-words histogram quantisation of descriptor vectors -An example histogram for training image shown on figure \ref{fig:histo_tr}, computed with a vocubulary size of 100. A corresponding testing image of the same class is shown in figure \ref{fig:histo_te}. 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 centroids) on the classificaiton accuracy in figure \ref{fig:km_vocsize}. +An example histogram for training image shown on figure \ref{fig:histo_tr}, computed with a vocubulary size of 100. A corresponding testing image of the same class is shown in figure \ref{fig:histo_te}. 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-mean 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. -The time complexity of quantisation with a K-means codebooks is $O(n^{dk+1})$ , where n is the number of entities to be clustered, d is the dimension 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. An alternative method is NUNZIO PUCCI WRITE HERE +The time complexity of quantisation with a K-means codebooks is $O(n^{dk+1})$ , where n is the number of entities to be clustered, d is the dimension 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 vecotrs 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. +Running for multiple instances significantly affects the computation process, leading to a linear increase in execution time. +Attempting centroid initialization more than once didn't cause significant improvements in terms of accuracy for the data analysed in +this coursework, only leading to an increase in execution time. \begin{figure}[H] \begin{center} |