diff options
Diffstat (limited to 'report')
| -rw-r--r-- | report/.gitignore | 2 | ||||
| -rw-r--r-- | report/.travis.yml | 7 | ||||
| -rw-r--r-- | report/LICENSE | 21 | ||||
| -rwxr-xr-x | report/bibliography.bib | 42 | ||||
| -rw-r--r-- | report/bibliography.csl | 339 | ||||
| -rw-r--r-- | report/fig/allbaselines.pdf | bin | 0 -> 15002 bytes | |||
| -rw-r--r-- | report/fig/baseline.pdf | bin | 0 -> 14619 bytes | |||
| -rw-r--r-- | report/fig/cdist.pdf | bin | 0 -> 10783 bytes | |||
| -rw-r--r-- | report/fig/clusteracc.pdf | bin | 0 -> 14898 bytes | |||
| -rw-r--r-- | report/fig/comparison.pdf | bin | 0 -> 14877 bytes | |||
| -rw-r--r-- | report/fig/eucranklist.png | bin | 0 -> 3137716 bytes | |||
| -rw-r--r-- | report/fig/jaccard.pdf | bin | 0 -> 12026 bytes | |||
| -rw-r--r-- | report/fig/kmeanacc.pdf | bin | 0 -> 13948 bytes | |||
| -rw-r--r-- | report/fig/lambda_acc.pdf | bin | 0 -> 13808 bytes | |||
| -rw-r--r-- | report/fig/lambda_acc_tr.pdf | bin | 0 -> 13822 bytes | |||
| -rw-r--r-- | report/fig/mAP.pdf | bin | 0 -> 14023 bytes | |||
| -rw-r--r-- | report/fig/mahalanobis.pdf | bin | 0 -> 41611 bytes | |||
| -rw-r--r-- | report/fig/pqvals.pdf | bin | 0 -> 14356 bytes | |||
| -rw-r--r-- | report/fig/ranklist.png | bin | 0 -> 2836148 bytes | |||
| -rw-r--r-- | report/fig/subspace.pdf | bin | 0 -> 10339 bytes | |||
| -rw-r--r-- | report/fig/train_subspace.pdf | bin | 0 -> 10108 bytes | |||
| -rw-r--r-- | report/fig/trainpqvals.pdf | bin | 0 -> 14355 bytes | |||
| -rwxr-xr-x | report/makefile | 18 | ||||
| -rwxr-xr-x | report/metadata.yaml | 21 | ||||
| -rwxr-xr-x | report/paper.md | 240 | ||||
| -rw-r--r-- | report/template.latex | 294 |
26 files changed, 984 insertions, 0 deletions
diff --git a/report/.gitignore b/report/.gitignore new file mode 100644 index 0000000..5236e1e --- /dev/null +++ b/report/.gitignore @@ -0,0 +1,2 @@ +*~ + diff --git a/report/.travis.yml b/report/.travis.yml new file mode 100644 index 0000000..49d89e9 --- /dev/null +++ b/report/.travis.yml @@ -0,0 +1,7 @@ +sudo: enabled +dist: trusty +install: + - sudo apt-get -qq update + - sudo apt-get install -y pandoc pandoc-citeproc texlive-full +script: + - make diff --git a/report/LICENSE b/report/LICENSE new file mode 100644 index 0000000..6c59dbd --- /dev/null +++ b/report/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2016 Santos Gallegos + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/report/bibliography.bib b/report/bibliography.bib new file mode 100755 index 0000000..8890439 --- /dev/null +++ b/report/bibliography.bib @@ -0,0 +1,42 @@ +@article{rerank-paper, + author = {Zhun Zhong and + Liang Zheng and + Donglin Cao and + Shaozi Li}, + title = {Re-ranking Person Re-identification with k-reciprocal Encoding}, + journal = {CoRR}, + volume = {abs/1701.08398}, + year = {2017}, + url = {http://arxiv.org/abs/1701.08398}, + archivePrefix = {arXiv}, + eprint = {1701.08398}, + timestamp = {Mon, 13 Aug 2018 16:47:43 +0200}, + biburl = {https://dblp.org/rec/bib/journals/corr/ZhongZCL17}, + bibsource = {dblp computer science bibliography, https://dblp.org} +} + +@article{mAP, + author = {Jonathan Hui}, + title = {mAP (mean Average Precision) for Object Detection}, + year = {2018}, + url = {https://medium.com/@jonathan_hui/map-mean-average-precision-for-object-detection-45c121a31173}, +} + +@inproceedings{deepreid, +title={DeepReID: Deep Filter Pairing Neural Network for Person Re-identification}, +author={Li, Wei and Zhao, Rui and Xiao, Tong and Wang, Xiaogang}, +booktitle={CVPR}, +year={2014} +} + +@article{sklearn, + title={Scikit-learn: Machine Learning in {P}ython}, + author={Pedregosa, F. and Varoquaux, G. and Gramfort, A. and Michel, V. + and Thirion, B. and Grisel, O. and Blondel, M. and Prettenhofer, P. + and Weiss, R. and Dubourg, V. and Vanderplas, J. and Passos, A. and + Cournapeau, D. and Brucher, M. and Perrot, M. and Duchesnay, E.}, + journal={Journal of Machine Learning Research}, + volume={12}, + pages={2825--2830}, + year={2011} +} diff --git a/report/bibliography.csl b/report/bibliography.csl new file mode 100644 index 0000000..9d967b0 --- /dev/null +++ b/report/bibliography.csl @@ -0,0 +1,339 @@ +<?xml version="1.0" encoding="UTF-8"?> +<style xmlns="http://purl.org/net/xbiblio/csl" class="in-text" version="1.0" demote-non-dropping-particle="sort-only"> + <info> + <title>IEEE</title> + <id>http://www.zotero.org/styles/ieee</id> + <link href="http://www.zotero.org/styles/ieee" rel="self"/> + <link href="http://www.ieee.org/documents/style_manual.pdf" rel="documentation"/> + <link href="http://www.ieee.org/documents/auinfo07.pdf" rel="documentation"/> + <author> + <name>Michael Berkowitz</name> + <email>mberkowi@gmu.edu</email> + </author> + <contributor> + <name>Julian Onions</name> + <email>julian.onions@gmail.com</email> + </contributor> + <contributor> + <name>Rintze Zelle</name> + <uri>http://twitter.com/rintzezelle</uri> + </contributor> + <contributor> + <name>Stephen Frank</name> + <uri>http://www.zotero.org/sfrank</uri> + </contributor> + <contributor> + <name>Sebastian Karcher</name> + </contributor> + <category citation-format="numeric"/> + <category field="engineering"/> + <category field="generic-base"/> + <updated>2013-12-17T18:04:02+00:00</updated> + <rights license="http://creativecommons.org/licenses/by-sa/3.0/">This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 License</rights> + </info> + <locale xml:lang="en"> + <terms> + <term name="chapter" form="short">ch.</term> + <term name="presented at">presented at the</term> + <term name="available at">available</term> + </terms> + </locale> + <!-- Macros --> + <macro name="edition"> + <choose> + <if type="bill book chapter graphic legal_case legislation motion_picture paper-conference report song" match="any"> + <choose> + <if is-numeric="edition"> + <group delimiter=" "> + <number variable="edition" form="ordinal"/> + <text term="edition" form="short"/> + </group> + </if> + <else> + <text variable="edition" text-case="capitalize-first" suffix="."/> + </else> + </choose> + </if> + </choose> + </macro> + <macro name="issued"> + <choose> + <if type="article-journal report" match="any"> + <date variable="issued"> + <date-part name="month" form="short" suffix=" "/> + <date-part name="year" form="long"/> + </date> + </if> + <else-if type=" bill book chapter graphic legal_case legislation motion_picture paper-conference song thesis" match="any"> + <date variable="issued"> + <date-part name="year" form="long"/> + </date> + </else-if> + <else> + <date variable="issued"> + <date-part name="day" form="numeric-leading-zeros" suffix="-"/> + <date-part name="month" form="short" suffix="-" strip-periods="true"/> + <date-part name="year" form="long"/> + </date> + </else> + </choose> + </macro> + <macro name="author"> + <names variable="author"> + <name initialize-with=". " delimiter=", " and="text"/> + <label form="short" prefix=", " text-case="capitalize-first"/> + <substitute> + <names variable="editor"/> + <names variable="translator"/> + </substitute> + </names> + </macro> + <macro name="editor"> + <names variable="editor"> + <name initialize-with=". " delimiter=", " and="text"/> + <label form="short" prefix=", " text-case="capitalize-first"/> + </names> + </macro> + <macro name="locators"> + <group delimiter=", "> + <text macro="edition"/> + <group delimiter=" "> + <text term="volume" form="short"/> + <number variable="volume" form="numeric"/> + </group> + <group delimiter=" "> + <number variable="number-of-volumes" form="numeric"/> + <text term="volume" form="short" plural="true"/> + </group> + <group delimiter=" "> + <text term="issue" form="short"/> + <number variable="issue" form="numeric"/> + </group> + </group> + </macro> + <macro name="title"> + <choose> + <if type="bill book graphic legal_case legislation motion_picture song" match="any"> + <text variable="title" font-style="italic"/> + </if> + <else> + <text variable="title" quotes="true"/> + </else> + </choose> + </macro> + <macro name="publisher"> + <choose> + <if type=" bill book chapter graphic legal_case legislation motion_picture paper-conference song" match="any"> + <group delimiter=": "> + <text variable="publisher-place"/> + <text variable="publisher"/> + </group> + </if> + <else> + <group delimiter=", "> + <text variable="publisher"/> + <text variable="publisher-place"/> + </group> + </else> + </choose> + </macro> + <macro name="event"> + <choose> + <if type="paper-conference speech" match="any"> + <choose> + <!-- Published Conference Paper --> + <if variable="container-title"> + <group delimiter=", "> + <group delimiter=" "> + <text term="in"/> + <text variable="container-title" font-style="italic"/> + </group> + <text variable="event-place"/> + </group> + </if> + <!-- Unpublished Conference Paper --> + <else> + <group delimiter=", "> + <group delimiter=" "> + <text term="presented at"/> + <text variable="event"/> + </group> + <text variable="event-place"/> + </group> + </else> + </choose> + </if> + </choose> + </macro> + <macro name="access"> + <choose> + <if type="webpage"> + <choose> + <if variable="URL"> + <group delimiter=". "> + <text term="online" prefix="[" suffix="]" text-case="capitalize-first"/> + <group delimiter=": "> + <text term="available at" text-case="capitalize-first"/> + <text variable="URL"/> + </group> + <group prefix="[" suffix="]" delimiter=": "> + <text term="accessed" text-case="capitalize-first"/> + <date variable="accessed"> + <date-part name="day" form="numeric-leading-zeros" suffix="-"/> + <date-part name="month" form="short" suffix="-" strip-periods="true"/> + <date-part name="year" form="long"/> + </date> + </group> + </group> + </if> + </choose> + </if> + </choose> + </macro> + <macro name="page"> + <group> + <label variable="page" form="short" suffix=" "/> + <text variable="page"/> + </group> + </macro> + <macro name="citation-locator"> + <group delimiter=" "> + <choose> + <if locator="page"> + <label variable="locator" form="short"/> + </if> + <else> + <label variable="locator" form="short" text-case="capitalize-first"/> + </else> + </choose> + <text variable="locator"/> + </group> + </macro> + <!-- Citation --> + <citation collapse="citation-number"> + <sort> + <key variable="citation-number"/> + </sort> + <layout delimiter=", "> + <group prefix="[" suffix="]" delimiter=", "> + <text variable="citation-number"/> + <text macro="citation-locator"/> + </group> + </layout> + </citation> + <!-- Bibliography --> + <bibliography entry-spacing="0" second-field-align="flush"> + <layout suffix="."> + <!-- Citation Number --> + <text variable="citation-number" prefix="[" suffix="]"/> + <!-- Author(s) --> + <text macro="author" suffix=", "/> + <!-- Rest of Citation --> + <choose> + <!-- Specific Formats --> + <if type="article-journal"> + <group delimiter=", "> + <text macro="title"/> + <text variable="container-title" font-style="italic" form="short"/> + <text macro="locators"/> + <text macro="page"/> + <text macro="issued"/> + </group> + </if> + <else-if type="paper-conference speech" match="any"> + <group delimiter=", "> + <text macro="title"/> + <text macro="event"/> + <text macro="issued"/> + <text macro="locators"/> + <text macro="page"/> + </group> + </else-if> + <else-if type="report"> + <group delimiter=", "> + <text macro="title"/> + <text macro="publisher"/> + <group delimiter=" "> + <text variable="genre"/> + <text variable="number"/> + </group> + <text macro="issued"/> + </group> + </else-if> + <else-if type="thesis"> + <group delimiter=", "> + <text macro="title"/> + <text variable="genre"/> + <text macro="publisher"/> + <text macro="issued"/> + </group> + </else-if> + <else-if type="webpage post-weblog" match="any"> + <group delimiter=", " suffix=". "> + <text macro="title"/> + <text variable="container-title" font-style="italic"/> + <text macro="issued"/> + </group> + <text macro="access"/> + </else-if> + <else-if type="patent"> + <group delimiter=", "> + <text macro="title"/> + <text variable="number"/> + <text macro="issued"/> + </group> + </else-if> + <!-- Generic/Fallback Formats --> + <else-if type="bill book graphic legal_case legislation motion_picture report song" match="any"> + <group delimiter=", " suffix=". "> + <text macro="title"/> + <text macro="locators"/> + </group> + <group delimiter=", "> + <text macro="publisher"/> + <text macro="issued"/> + <text macro="page"/> + </group> + </else-if> + <else-if type="article-magazine article-newspaper broadcast interview manuscript map patent personal_communication song speech thesis webpage" match="any"> + <group delimiter=", "> + <text macro="title"/> + <text variable="container-title" font-style="italic"/> + <text macro="locators"/> + <text macro="publisher"/> + <text macro="page"/> + <text macro="issued"/> + </group> + </else-if> + <else-if type="chapter paper-conference" match="any"> + <group delimiter=", " suffix=", "> + <text macro="title"/> + <group delimiter=" "> + <text term="in"/> + <text variable="container-title" font-style="italic"/> + </group> + <text macro="locators"/> + </group> + <text macro="editor" suffix=" "/> + <group delimiter=", "> + <text macro="publisher"/> + <text macro="issued"/> + <text macro="page"/> + </group> + </else-if> + <else> + <group delimiter=", " suffix=". "> + <text macro="title"/> + <text variable="container-title" font-style="italic"/> + <text macro="locators"/> + </group> + <group delimiter=", "> + <text macro="publisher"/> + <text macro="page"/> + <text macro="issued"/> + </group> + </else> + </choose> + </layout> + </bibliography> +</style>
\ No newline at end of file diff --git a/report/fig/allbaselines.pdf b/report/fig/allbaselines.pdf Binary files differnew file mode 100644 index 0000000..15b1aff --- /dev/null +++ b/report/fig/allbaselines.pdf diff --git a/report/fig/baseline.pdf b/report/fig/baseline.pdf Binary files differnew file mode 100644 index 0000000..04b2ac5 --- /dev/null +++ b/report/fig/baseline.pdf diff --git a/report/fig/cdist.pdf b/report/fig/cdist.pdf Binary files differnew file mode 100644 index 0000000..81d712c --- /dev/null +++ b/report/fig/cdist.pdf diff --git a/report/fig/clusteracc.pdf b/report/fig/clusteracc.pdf Binary files differnew file mode 100644 index 0000000..09459c4 --- /dev/null +++ b/report/fig/clusteracc.pdf diff --git a/report/fig/comparison.pdf b/report/fig/comparison.pdf Binary files differnew file mode 100644 index 0000000..e755c10 --- /dev/null +++ b/report/fig/comparison.pdf diff --git a/report/fig/eucranklist.png b/report/fig/eucranklist.png Binary files differnew file mode 100644 index 0000000..3f03a73 --- /dev/null +++ b/report/fig/eucranklist.png diff --git a/report/fig/jaccard.pdf b/report/fig/jaccard.pdf Binary files differnew file mode 100644 index 0000000..53cf407 --- /dev/null +++ b/report/fig/jaccard.pdf diff --git a/report/fig/kmeanacc.pdf b/report/fig/kmeanacc.pdf Binary files differnew file mode 100644 index 0000000..4b6e33b --- /dev/null +++ b/report/fig/kmeanacc.pdf diff --git a/report/fig/lambda_acc.pdf b/report/fig/lambda_acc.pdf Binary files differnew file mode 100644 index 0000000..9c3f749 --- /dev/null +++ b/report/fig/lambda_acc.pdf diff --git a/report/fig/lambda_acc_tr.pdf b/report/fig/lambda_acc_tr.pdf Binary files differnew file mode 100644 index 0000000..8041977 --- /dev/null +++ b/report/fig/lambda_acc_tr.pdf diff --git a/report/fig/mAP.pdf b/report/fig/mAP.pdf Binary files differnew file mode 100644 index 0000000..0cf7156 --- /dev/null +++ b/report/fig/mAP.pdf diff --git a/report/fig/mahalanobis.pdf b/report/fig/mahalanobis.pdf Binary files differnew file mode 100644 index 0000000..2362cfa --- /dev/null +++ b/report/fig/mahalanobis.pdf diff --git a/report/fig/pqvals.pdf b/report/fig/pqvals.pdf Binary files differnew file mode 100644 index 0000000..43cccdb --- /dev/null +++ b/report/fig/pqvals.pdf diff --git a/report/fig/ranklist.png b/report/fig/ranklist.png Binary files differnew file mode 100644 index 0000000..1cb2647 --- /dev/null +++ b/report/fig/ranklist.png diff --git a/report/fig/subspace.pdf b/report/fig/subspace.pdf Binary files differnew file mode 100644 index 0000000..2ab1f5b --- /dev/null +++ b/report/fig/subspace.pdf diff --git a/report/fig/train_subspace.pdf b/report/fig/train_subspace.pdf Binary files differnew file mode 100644 index 0000000..5ccdd36 --- /dev/null +++ b/report/fig/train_subspace.pdf diff --git a/report/fig/trainpqvals.pdf b/report/fig/trainpqvals.pdf Binary files differnew file mode 100644 index 0000000..210fea4 --- /dev/null +++ b/report/fig/trainpqvals.pdf diff --git a/report/makefile b/report/makefile new file mode 100755 index 0000000..77d8583 --- /dev/null +++ b/report/makefile @@ -0,0 +1,18 @@ +FILES = paper.md \ + metadata.yaml + +OUTPUT = build + +FLAGS = --bibliography=bibliography.bib \ + --csl=bibliography.csl \ + -s \ + -f markdown + +FLAGS_PDF = --template=template.latex + +pdf: + pandoc -o $(OUTPUT)/paper.pdf $(FLAGS) $(FLAGS_PDF) $(FILES) + +clean: + rm build/* + diff --git a/report/metadata.yaml b/report/metadata.yaml new file mode 100755 index 0000000..5f9f737 --- /dev/null +++ b/report/metadata.yaml @@ -0,0 +1,21 @@ +--- +title: 'EE4-68 Pattern Recognition (2018-2019) CW2' +author: + - name: Vasil Zlatanov (01120518), Nunzio Pucci (01113180) + email: vz215@ic.ac.uk, np1915@ic.ac.uk + link: 'Sources: < [git](https://git.skozl.com/e4-pattern/) - [tar](https://git.skozl.com/e4-pattern/snapshot/vz215_np1915-master.tar.gz) - [zip](https://git.skozl.com/e4-pattern/snapshot/vz215_np1915-master.zip) >' +numbersections: yes +lang: en +babel-lang: english +nocite: | + @deepreid, @sklearn + +abstract: | + This report analyses distance metrics learning techniques with regards to + identification accuracy for the dataset CUHK03. The baseline method used for + identification is Eucdidian based Nearest Neighbors based on Euclidean distance. + The improved approach evaluated utilises Jaccardian metrics to rearrange the NN + ranklist based on reciprocal neighbours. While this approach is more complex and introduced new hyperparameter, significant accuracy improvements are observed - + approximately 10% increased Top-1 identifications, and good improvements for Top-$N$ accuracy with low $N$. +... + diff --git a/report/paper.md b/report/paper.md new file mode 100755 index 0000000..a961be0 --- /dev/null +++ b/report/paper.md @@ -0,0 +1,240 @@ + +# Forulation of the Addresssed Machine Learning Problem + +## Probelm Definition + +The person re-identification problem presented in this paper requires matching +pedestrian images from disjoint cameras by pedestrian detectors. This problem is +challenging, as identities captured in photsos are subject to various lighting, pose, +blur, background and oclusion from various camera views. This report considers +features extracted from the CUHK03 dataset, following a 50 layer Residual network +(Resnet50). This paper considers distance metrics techniques which can be used to +perform person re-identification across *disjoint* cameras, using these features. + +## Dataset - CUHK03 Summary + +The dataset CUHK03 contains 14096 pictures of people captured from two +different cameras. The feature vectors used, extracted from a trained ResNet50 model +, contain 2048 features that are used for identification. + +The pictures represent 1467 different identities, each of which appears 9 to 10 +times. Data is seperated in train, query and gallery sets with `train_idx`, +`query_idx` and `gallery_idx` respectively, where the training set has been used +to develop the ResNet50 model used for feature extraction. This procedure has +allowed the evaluation of distance metric learning techniques on the query and +gallery sets, with the knowledge that we are not comparing overfitted features, +as they were extracted based on the model derived from the training set. + +## Probelm to solve + +The problem to solve is to create a ranklist for each image of the query set +by finding the nearest neighbor(s) within a gallery set. However gallery images +with the same label and taken from the same camera as the query image should +not be considered when forming the ranklist. + +## Nearest Neighbor ranklist + +Nearest Neighbor aims to find the gallery image whose feature are the closest to +the ones of a query image, predicting the class of the query image as the same +of its nearest neighbor(s). The distance between images can be calculated through +different distance metrics, however one of the most commonly used is euclidean +distance: + +$$ \textrm{NN}(x) = \operatorname*{argmin}_{i\in[m]} \|x-x_i\| $$ + +Alternative distance metrics exist such as jaccardian and mahalanobis, which can +be used as an alternative to euclidiean distance. + +# Baseline Evaluation + +To evaluate improvements brought by alternative distance learning metrics a baseline +is established through nearest neighbour identification as previously described. +Identification accuracies at top1, top5 and top10 are respectively 47%, 67% and 75% +(figure \ref{fig:baselineacc}). The mAP is 47%. + +\begin{figure} +\begin{center} +\includegraphics[width=20em]{fig/baseline.pdf} +\caption{Recognition accuracy of baseline Nearest Neighbor @rank k} +\label{fig:baselineacc} +\end{center} +\end{figure} + +Figure \ref{fig:eucrank} shows the ranklist generated through baseline NN for +5 query images(black). Correct identification is shown in green and incorrect +identification is shown in red. + +\begin{figure} +\begin{center} +\includegraphics[width=22em]{fig/eucranklist.png} +\caption{Ranklist @rank10 generated for 5 query images} +\label{fig:eucrank} +\end{center} +\end{figure} + +Magnitude normalization of the feature vectors does not improve +accuracy results of the baseline as it can be seen in figure \ref{fig:baselineacc}. +This is due to the fact that the feature vectors appear scaled, releative to their +significance, for optimal distance classification, and as such normalising loses this +scaling by importance which has previously been introduced to the features. + +## kMeans Clustering + +An addition considered for the baseline is *kMeans clustering*. In theory this method +allows to reduce computational complexity of the baseline NN by forming clusters and +performing a comparison between query image and clusters centers. The elements +associated with the closest cluster center are then considered to perform NN and +classify the query image. + +This method did not bring any major improvement to the baseline, as it can be seen from +figure \ref{fig:baselineacc}. It is noticeable how the number of clusters affects +performance, showing better identification accuracy for a number of clusters away from +the local minimum achieved at 60 clusters (figure \ref{fig:kmeans}). This trend can likely be explained by the number of distance comparison's performed. + +We would expect clustering with $k=1$ and $k=\textrm{label count}$ to have the same performance +the baseline approach without clustering, as we are performing the same number of comparisons. + +Clustering is a great method of reducing computation time. Assuming 39 clusters of 39 neighbours we would be performing only 78 distance computation for a gallery size of 1487, instead of the original 1487. This however comes at the cost of ignoring neighbours from other clusters which may be closer. Since clusters do not necessarily have the same number of datapoints inside them (sizes are uneven), we find that the lowest average number of comparison happens at around 60 clusters, which also appears to be the worst performing number of clusters. + +We find that for the query and gallery set clustering does not seem to improve identification accuracy, and consider it an additional baseline. + +\begin{figure} +\begin{center} +\includegraphics[width=17em]{fig/kmeanacc.pdf} +\caption{Top 1 Identification accuracy varying kmeans cluster size} +\label{fig:kmeans} +\end{center} +\end{figure} + +# Suggested Improvement + +## Comment on Mahalnobis Distance as a metric + +We were not able to achieve significant improvements using mahalanobis for +original distance ranking compared to square euclidiaen metrics. Results can +be observed using the `-m|--mahalanobis` when running evalution with the +repository complimenting this paper. + +**COMMENT ON VARIANCE AND MAHALANOBIS RESULTS** + +\begin{figure} +\begin{center} +\includegraphics[width=12em]{fig/cdist.pdf} +\includegraphics[width=12em]{fig/train_subspace.pdf} +\caption{Left:first two features of gallery(o) and query(x) data for 3 labels; Right:First two features of train data for three labels} +\label{fig:subspace} +\end{center} +\end{figure} + +## k-reciprocal Reranking Formulation + +The approach addressed to improve the identification performance is based on +k-reciprocal reranking. The following section summarizes the idea behind +the method illustrated in reference @rerank-paper. + +We define $N(p,k)$ as the top k elements of the ranklist generated through NN, +where p is a query image. The k reciprocal ranklist, $R(p,k)$ is defined as the +intersection $R(p,k)=\{g_i|(g_i \in N(p,k))\land(p \in N(g_i,k))\}$. Adding +$\frac{1}{2}k$ reciprocal nearest neighbors of each element in the ranklist +$R(p,k)$, it is possible to form a more reliable set +$R^*(p,k) \longleftarrow R(p,k) \cup R(q,\frac{1}{2}k)$ that aims to overcome +the problem of query and gallery images being affected by factors such +as position, illumination and foreign objects. $R^*(p,k)$ is used to +recalculate the distance between query and gallery images. + +Jaccard metric of the k-reciprocal sets is used to calculate the distance +between p and $g_i$ as: $$d_J(p,g_i)=1-\frac{|R^*(p,k)\cap R^*(g_i,k)|}{|R^*(p,k)\cup R^*(g_i,k)|}$$. + +However, since the neighbors of the query p are close to $g_i$ as well, +they would be more likely to be identified as true positive. This implies +the need of a more discriminative method, which is achieved +encoding the k-reciprocal neighbors into an N-dimensional vector as a function +of the original distance (in our case square euclidean $d(p,g_i) = \|p-g_i\|^2$) +through the gaussian kernell: + +\begin{equation} +\textit{V\textsubscript{p,g\textsubscript{i}}}= +\begin{cases} +e\textsuperscript{\textit{-d(p,g\textsubscript{i})}}, & \text{if}\ \textit{g\textsubscript{i}}\in \textit{R\textsuperscript{*}(p,k)} \\ +0, & \text{otherwise.} +\end{cases} +\end{equation} + +Through this transformation it is possible to reformulate the distance obtained +through Jaccardian metric as: + +$$ d_J(p,g_i)=1-\frac{\sum\limits_{j=1}^N min(V_{p,g_j},V_{g_i,g_j})}{\sum\limits_{j=1}^N max(V_{p,g_j},V_{g_i,g_j})} $$ + +It is then possible to perform a local query expansion using the g\textsubscript{i} neighbors of +defined as: +$$ V_p=\frac{1}{|N(p,k_2)|}\sum\limits_{g_i\in N(p,k_2)}V_{g_i} $$. +We refer to $k_2$ since we limit the size of the nighbors to prevent noise +from the $k_2$ neighbors. The dimension k of the *$R^*$* set will instead +be defined as $k_1$: $R^*(g_i,k_1)$. + +The distances obtained are then mixed, obtaining a final distance $d^*(p,g_i)$ that is used to obtain the +improved ranklist: $d^*(p,g_i)=(1-\lambda)d_J(p,g_i)+\lambda d(p,g_i)$. + +The aim is to learn optimal values for $k_1,k_2$ and $\lambda$ in the training set that improve top1 identification accuracy. +This is done through a simple multi-direction search algorithm followed by exhaustive search to estimate +$k_{1_{opt}}$ and $k_{2_{opt}}$ for eleven values of $\lambda$ from zero(only Jaccard distance) to one(only original distance) +in steps of 0.1. The results obtained through this approach suggest: $k_{1_{opt}}=9, k_{2_{opt}}=3, 0.1\leq\lambda_{opt}\leq 0.3$. + +It is possible to verify that the optimization of $k_{1_{opt}}$, $k_{2_{opt}}$ and $\lambda$ +has been successful. Figures \ref{fig:pqvals} and \ref{fig:lambda} show that the optimal values obtained from +training are close to the ones for the local maximum of gallery and query. + +\begin{figure} +\begin{center} +\includegraphics[width=12em]{fig/pqvals.pdf} +\includegraphics[width=12em]{fig/trainpqvals.pdf} +\caption{Identification accuracy varying K1 and K2 (gallery-query left, train right) KL=0.3} +\label{fig:pqvals} +\end{center} +\end{figure} + +\begin{figure} +\begin{center} +\includegraphics[width=12em]{fig/lambda_acc.pdf} +\includegraphics[width=12em]{fig/lambda_acc_tr.pdf} +\caption{Top 1 Identification Accuracy with Rerank varying lambda(gallery-query left, train right) K1=9, K2=3} +\label{fig:lambda} +\end{center} +\end{figure} + + +## k-reciprocal Reranking Evaluation + +Reranking achieves better results than the other baseline methods analyzed both as $top k$ +accuracy and mean average precision. +It is also necessary to estimate how precise the ranklist generated is. +For this reason an additional method of evaluation is introduced: mAP. See reference @mAP. + +It is possible to see in figure \ref{fig:ranklist2} how the ranklist generated for the same five queries of figure \ref{fig:eucrank} +has improved for the fifth query. The mAP improves from 47% to 61.7%. + +\begin{figure} +\begin{center} +\includegraphics[width=24em]{fig/ranklist.png} +\caption{Ranklist (improved method) @rank10 generated for 5 query images} +\label{fig:ranklist2} +\end{center} +\end{figure} + +Figure \ref{fig:compare} shows a comparison between $top k$ identification accuracies +obtained with the two methods. It is noticeable that the k-reciprocal reranking method significantly +improves the results even for $top1$, boosting identification accuracy from 47% to 56.5%. +The difference between the $top k$ accuracies of the two methods gets smaller as we increase k. + +\begin{figure} +\begin{center} +\includegraphics[width=20em]{fig/comparison.pdf} +\caption{Comparison of recognition accuracy @rank k (KL=0.3,K1=9,K2=3)} +\label{fig:compare} +\end{center} +\end{figure} + +# Conclusion + +# References + diff --git a/report/template.latex b/report/template.latex new file mode 100644 index 0000000..9917236 --- /dev/null +++ b/report/template.latex @@ -0,0 +1,294 @@ +\documentclass[$if(fontsize)$$fontsize$,$endif$$if(lang)$$babel-lang$,$endif$$if(papersize)$$papersize$paper,$endif$$for(classoption)$$classoption$$sep$,$endfor$]{IEEEtran} +$if(beamerarticle)$ +\usepackage{beamerarticle} % needs to be loaded first +$endif$ +$if(fontfamily)$ +\usepackage[$for(fontfamilyoptions)$$fontfamilyoptions$$sep$,$endfor$]{$fontfamily$} +$else$ +\usepackage{lmodern} +$endif$ +$if(linestretch)$ +\usepackage{setspace} +\setstretch{$linestretch$} +$endif$ +\usepackage{amssymb,amsmath} +\usepackage{ifxetex,ifluatex} +\usepackage{fixltx2e} % provides \textsubscript +\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex + \usepackage[$if(fontenc)$$fontenc$$else$T1$endif$]{fontenc} + \usepackage[utf8]{inputenc} +$if(euro)$ + \usepackage{eurosym} +$endif$ +\else % if luatex or xelatex + \ifxetex + \usepackage{mathspec} + \else + \usepackage{fontspec} + \fi + \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase} +$for(fontfamilies)$ + \newfontfamily{$fontfamilies.name$}[$fontfamilies.options$]{$fontfamilies.font$} +$endfor$ +$if(euro)$ + \newcommand{\euro}{€} +$endif$ +$if(mainfont)$ + \setmainfont[$for(mainfontoptions)$$mainfontoptions$$sep$,$endfor$]{$mainfont$} +$endif$ +$if(sansfont)$ + \setsansfont[$for(sansfontoptions)$$sansfontoptions$$sep$,$endfor$]{$sansfont$} +$endif$ +$if(monofont)$ + \setmonofont[Mapping=tex-ansi$if(monofontoptions)$,$for(monofontoptions)$$monofontoptions$$sep$,$endfor$$endif$]{$monofont$} +$endif$ +$if(mathfont)$ + \setmathfont(Digits,Latin,Greek)[$for(mathfontoptions)$$mathfontoptions$$sep$,$endfor$]{$mathfont$} +$endif$ +$if(CJKmainfont)$ + \usepackage{xeCJK} + \setCJKmainfont[$for(CJKoptions)$$CJKoptions$$sep$,$endfor$]{$CJKmainfont$} +$endif$ +\fi +% use upquote if available, for straight quotes in verbatim environments +\IfFileExists{upquote.sty}{\usepackage{upquote}}{} +% use microtype if available +\IfFileExists{microtype.sty}{% +\usepackage{microtype} +\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts +}{} +$if(geometry)$ +\usepackage[$for(geometry)$$geometry$$sep$,$endfor$]{geometry} +$endif$ +\usepackage[unicode=true]{hyperref} +$if(colorlinks)$ +\PassOptionsToPackage{usenames,dvipsnames}{color} % color is loaded by hyperref +$endif$ +\hypersetup{ +$if(title-meta)$ + pdftitle={$title-meta$}, +$endif$ +$if(author-meta)$ + pdfauthor={$author-meta$}, +$endif$ +$if(keywords)$ + pdfkeywords={$for(keywords)$$keywords$$sep$, $endfor$}, +$endif$ +$if(colorlinks)$ + colorlinks=true, + linkcolor=$if(linkcolor)$$linkcolor$$else$Maroon$endif$, + citecolor=$if(citecolor)$$citecolor$$else$Blue$endif$, + urlcolor=$if(urlcolor)$$urlcolor$$else$Blue$endif$, +$else$ + pdfborder={0 0 0}, +$endif$ + breaklinks=true} +\urlstyle{same} % don't use monospace font for urls +$if(lang)$ +\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex + \usepackage[shorthands=off,$for(babel-otherlangs)$$babel-otherlangs$,$endfor$main=$babel-lang$]{babel} +$if(babel-newcommands)$ + $babel-newcommands$ +$endif$ +\else + \usepackage{polyglossia} + \setmainlanguage[$polyglossia-lang.options$]{$polyglossia-lang.name$} +$for(polyglossia-otherlangs)$ + \setotherlanguage[$polyglossia-otherlangs.options$]{$polyglossia-otherlangs.name$} +$endfor$ +\fi +$endif$ +$if(natbib)$ +\usepackage{natbib} +\bibliographystyle{$if(biblio-style)$$biblio-style$$else$plainnat$endif$} +$endif$ +$if(biblatex)$ +\usepackage[$if(biblio-style)$style=$biblio-style$,$endif$$for(biblatexoptions)$$biblatexoptions$$sep$,$endfor$]{biblatex} +$for(bibliography)$ +\addbibresource{$bibliography$} +$endfor$ +$endif$ +$if(listings)$ +\usepackage{listings} +$endif$ +$if(lhs)$ +\lstnewenvironment{code}{\lstset{language=Haskell,basicstyle=\small\ttfamily}}{} +$endif$ +$if(highlighting-macros)$ +$highlighting-macros$ +$endif$ +$if(verbatim-in-note)$ +\usepackage{fancyvrb} +\VerbatimFootnotes % allows verbatim text in footnotes +$endif$ +$if(tables)$ +\usepackage{longtable,booktabs} +% Fix footnotes in tables (requires footnote package) +\IfFileExists{footnote.sty}{\usepackage{footnote}\makesavenoteenv{long table}}{} +$endif$ +\usepackage{graphicx} +$if(graphics)$ +\usepackage{graphicx,grffile} +\makeatletter +\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi} +\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi} +\makeatother +% Scale images if necessary, so that they will not overflow the page +% margins by default, and it is still possible to overwrite the defaults +% using explicit options in \includegraphics[width, height, ...]{} +\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio} +$endif$ +$if(links-as-notes)$ +% Make links footnotes instead of hotlinks: +\renewcommand{\href}[2]{#2\footnote{\url{#1}}} +$endif$ +$if(strikeout)$ +\usepackage[normalem]{ulem} +% avoid problems with \sout in headers with hyperref: +\pdfstringdefDisableCommands{\renewcommand{\sout}{}} +$endif$ +$if(indent)$ +$else$ +\IfFileExists{parskip.sty}{% +\usepackage{parskip} +}{% else +\setlength{\parindent}{0pt} +\setlength{\parskip}{6pt plus 2pt minus 1pt} +} +$endif$ +\setlength{\emergencystretch}{3em} % prevent overfull lines +\providecommand{\tightlist}{% + \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} +$if(numbersections)$ +\setcounter{secnumdepth}{$if(secnumdepth)$$secnumdepth$$else$5$endif$} +$else$ +\setcounter{secnumdepth}{0} +$endif$ +$if(subparagraph)$ +$else$ +% Redefines (sub)paragraphs to behave more like sections +\ifx\paragraph\undefined\else +\let\oldparagraph\paragraph +\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}} +\fi +\ifx\subparagraph\undefined\else +\let\oldsubparagraph\subparagraph +\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}} +\fi +$endif$ +$if(dir)$ +\ifxetex + % load bidi as late as possible as it modifies e.g. graphicx + $if(latex-dir-rtl)$ + \usepackage[RTLdocument]{bidi} + $else$ + \usepackage{bidi} + $endif$ +\fi +\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex + \TeXXeTstate=1 + \newcommand{\RL}[1]{\beginR #1\endR} + \newcommand{\LR}[1]{\beginL #1\endL} + \newenvironment{RTL}{\beginR}{\endR} + \newenvironment{LTR}{\beginL}{\endL} +\fi +$endif$ + +% set default figure placement to htbp +\makeatletter +\def\fps@figure{htbp} +\makeatother + +$for(header-includes)$ +$header-includes$ +$endfor$ + +$if(title)$ +\title{$title$$if(thanks)$\thanks{$thanks$}$endif$} +$endif$ +$if(subtitle)$ +\providecommand{\subtitle}[1]{} +\subtitle{$subtitle$} +$endif$ + +$if(author)$ +\author{ + $for(author)$ + \IEEEauthorblockN{$author.name$} + \IEEEauthorblockA{% + $author.affiliation$ \\ + $author.email$ \\ + $author.link$} + $sep$ \and + $endfor$ +} +$endif$ + +$if(institute)$ +\providecommand{\institute}[1]{} +\institute{$for(institute)$$institute$$sep$ \and $endfor$} +$endif$ +\date{$date$} + +\begin{document} +$if(title)$ +\maketitle +$endif$ +$if(abstract)$ +\begin{abstract} +$abstract$ +\end{abstract} +$endif$ + +$if(keywords)$ +\begin{IEEEkeywords} +$for(keywords)$ + $keywords$$sep$; +$endfor$ +\end{IEEEkeywords} +$endif$ + +$for(include-before)$ +$include-before$ + +$endfor$ +$if(toc)$ +{ +$if(colorlinks)$ +\hypersetup{linkcolor=$if(toccolor)$$toccolor$$else$black$endif$} +$endif$ +\setcounter{tocdepth}{$toc-depth$} +\tableofcontents +} +$endif$ +$if(lot)$ +\listoftables +$endif$ +$if(lof)$ +\listoffigures +$endif$ +$body$ + +$if(natbib)$ +$if(bibliography)$ +$if(biblio-title)$ +$if(book-class)$ +\renewcommand\bibname{$biblio-title$} +$else$ +\renewcommand\refname{$biblio-title$} +$endif$ +$endif$ +\bibliography{$for(bibliography)$$bibliography$$sep$,$endfor$} + +$endif$ +$endif$ +$if(biblatex)$ +\printbibliography$if(biblio-title)$[title=$biblio-title$]$endif$ + +$endif$ +$for(include-after)$ +$include-after$ + +$endfor$ +\end{document} + |
