Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval

Izat Khamiyev; Magzhan Gabidolla; Alisher Iskakov; M. Fatih Demirci

doi:10.1007/978-3-030-64559-5_24

Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval

Izat Khamiyev
, Magzhan Gabidolla
, Alisher Iskakov
, M. Fatih Demirci

Nazarbayev University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a distance matrix with triangular inequality violations, the metric nearness problem requires to find the closest matrix that satisfies the triangle inequality. It has been experimentally shown that deep neural networks can be used to efficiently produce close matrices with a fewer number of triangular inequality violations. This paper further extends the deep learning approach to the metric nearness problem by applying it to the content-based image retrieval. Since vantage space representation of an image database requires distances to satisfy triangle inequalities, applying deep learning to the matrices in the vantage space with triangular inequality violations produces distance matrices with a fewer number of violations. Experiments performed on the Corel-1k dataset demonstrate that fully convolutional autoencoders considerably reduce triangular inequality violations on distance matrices. Overall, the image retrieval accuracy based on the distance matrices generated by the deep learning model is better than that based on the original matrices in 91.16% of the time.

Original language	English
Title of host publication	Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings
Editors	George Bebis, Zhaozheng Yin, Edward Kim, Jan Bender, Kartic Subr, Bum Chul Kwon, Jian Zhao, Denis Kalkofen, George Baciu
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	310-318
Number of pages	9
ISBN (Print)	9783030645588
DOIs	https://doi.org/10.1007/978-3-030-64559-5_24
Publication status	Published - 2020
Event	15th International Symposium on Visual Computing, ISVC 2020 - San Diego, United States Duration: Oct 5 2020 → Oct 7 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12510 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Symposium on Visual Computing, ISVC 2020
Country/Territory	United States
City	San Diego
Period	10/5/20 → 10/7/20

Keywords

Convolutional neural networks
Deep learning
Image retrieval
Metric nearness

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-64559-5_24

Cite this

Khamiyev, I., Gabidolla, M., Iskakov, A., & Demirci, M. F. (2020). Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval. In G. Bebis, Z. Yin, E. Kim, J. Bender, K. Subr, B. C. Kwon, J. Zhao, D. Kalkofen, & G. Baciu (Eds.), Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings (pp. 310-318). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12510 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-64559-5_24

Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval. / Khamiyev, Izat; Gabidolla, Magzhan; Iskakov, Alisher et al.
Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings. ed. / George Bebis; Zhaozheng Yin; Edward Kim; Jan Bender; Kartic Subr; Bum Chul Kwon; Jian Zhao; Denis Kalkofen; George Baciu. Springer Science and Business Media Deutschland GmbH, 2020. p. 310-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12510 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Khamiyev, I, Gabidolla, M, Iskakov, A & Demirci, MF 2020, Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval. in G Bebis, Z Yin, E Kim, J Bender, K Subr, BC Kwon, J Zhao, D Kalkofen & G Baciu (eds), Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12510 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 310-318, 15th International Symposium on Visual Computing, ISVC 2020, San Diego, United States, 10/5/20. https://doi.org/10.1007/978-3-030-64559-5_24

Khamiyev I, Gabidolla M, Iskakov A, Demirci MF. Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval. In Bebis G, Yin Z, Kim E, Bender J, Subr K, Kwon BC, Zhao J, Kalkofen D, Baciu G, editors, Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings. Springer Science and Business Media Deutschland GmbH. 2020. p. 310-318. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-64559-5_24

Khamiyev, Izat ; Gabidolla, Magzhan ; Iskakov, Alisher et al. / Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval. Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings. editor / George Bebis ; Zhaozheng Yin ; Edward Kim ; Jan Bender ; Kartic Subr ; Bum Chul Kwon ; Jian Zhao ; Denis Kalkofen ; George Baciu. Springer Science and Business Media Deutschland GmbH, 2020. pp. 310-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{65bdf351c41d46d5836f8910edf5e210,

title = "Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval",

abstract = "Given a distance matrix with triangular inequality violations, the metric nearness problem requires to find the closest matrix that satisfies the triangle inequality. It has been experimentally shown that deep neural networks can be used to efficiently produce close matrices with a fewer number of triangular inequality violations. This paper further extends the deep learning approach to the metric nearness problem by applying it to the content-based image retrieval. Since vantage space representation of an image database requires distances to satisfy triangle inequalities, applying deep learning to the matrices in the vantage space with triangular inequality violations produces distance matrices with a fewer number of violations. Experiments performed on the Corel-1k dataset demonstrate that fully convolutional autoencoders considerably reduce triangular inequality violations on distance matrices. Overall, the image retrieval accuracy based on the distance matrices generated by the deep learning model is better than that based on the original matrices in 91.16\% of the time.",

keywords = "Convolutional neural networks, Deep learning, Image retrieval, Metric nearness",

author = "Izat Khamiyev and Magzhan Gabidolla and Alisher Iskakov and Demirci, \{M. Fatih\}",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 15th International Symposium on Visual Computing, ISVC 2020 ; Conference date: 05-10-2020 Through 07-10-2020",

year = "2020",

doi = "10.1007/978-3-030-64559-5\_24",

language = "English",

isbn = "9783030645588",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "310--318",

editor = "George Bebis and Zhaozheng Yin and Edward Kim and Jan Bender and Kartic Subr and Kwon, \{Bum Chul\} and Jian Zhao and Denis Kalkofen and George Baciu",

booktitle = "Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval

AU - Khamiyev, Izat

AU - Gabidolla, Magzhan

AU - Iskakov, Alisher

AU - Demirci, M. Fatih

PY - 2020

Y1 - 2020

N2 - Given a distance matrix with triangular inequality violations, the metric nearness problem requires to find the closest matrix that satisfies the triangle inequality. It has been experimentally shown that deep neural networks can be used to efficiently produce close matrices with a fewer number of triangular inequality violations. This paper further extends the deep learning approach to the metric nearness problem by applying it to the content-based image retrieval. Since vantage space representation of an image database requires distances to satisfy triangle inequalities, applying deep learning to the matrices in the vantage space with triangular inequality violations produces distance matrices with a fewer number of violations. Experiments performed on the Corel-1k dataset demonstrate that fully convolutional autoencoders considerably reduce triangular inequality violations on distance matrices. Overall, the image retrieval accuracy based on the distance matrices generated by the deep learning model is better than that based on the original matrices in 91.16% of the time.

AB - Given a distance matrix with triangular inequality violations, the metric nearness problem requires to find the closest matrix that satisfies the triangle inequality. It has been experimentally shown that deep neural networks can be used to efficiently produce close matrices with a fewer number of triangular inequality violations. This paper further extends the deep learning approach to the metric nearness problem by applying it to the content-based image retrieval. Since vantage space representation of an image database requires distances to satisfy triangle inequalities, applying deep learning to the matrices in the vantage space with triangular inequality violations produces distance matrices with a fewer number of violations. Experiments performed on the Corel-1k dataset demonstrate that fully convolutional autoencoders considerably reduce triangular inequality violations on distance matrices. Overall, the image retrieval accuracy based on the distance matrices generated by the deep learning model is better than that based on the original matrices in 91.16% of the time.

KW - Convolutional neural networks

KW - Deep learning

KW - Image retrieval

KW - Metric nearness

UR - https://www.scopus.com/pages/publications/85098210590

UR - https://www.scopus.com/pages/publications/85098210590#tab=citedBy

U2 - 10.1007/978-3-030-64559-5_24

DO - 10.1007/978-3-030-64559-5_24

M3 - Conference contribution

AN - SCOPUS:85098210590

SN - 9783030645588

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 310

EP - 318

BT - Advances in Visual Computing - 15th International Symposium, ISVC 2020, Proceedings

A2 - Bebis, George

A2 - Yin, Zhaozheng

A2 - Kim, Edward

A2 - Bender, Jan

A2 - Subr, Kartic

A2 - Kwon, Bum Chul

A2 - Zhao, Jian

A2 - Kalkofen, Denis

A2 - Baciu, George

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Symposium on Visual Computing, ISVC 2020

Y2 - 5 October 2020 through 7 October 2020

ER -

Reducing Triangle Inequality Violations with Deep Learning and Its Application to Image Retrieval

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this