Image sorting via a reduction in travelling salesman problem

Access Full Text

Image sorting via a reduction in travelling salesman problem

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Image Processing — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Received 17/07/2018, Accepted 18/09/2019, Revised 23/11/2018, Published 08/10/2019

The authors define and approximately solve the problem of unsupervised image sorting that is considered as a kind of content-based image clustering. The content-based image sorting is the creation of a route that passes through all the images once, in such an order that the next one from the previous image has similar content. In the end, an image ordering (e.g. slideshow) is automatically produced, so that the images with similar content should be close to each other. This problem resembles the problem known in the literature as ‘travelling salesman problem’ (TSP). In this work, the authors have proposed two classes of methods (the nearest-neighbour and genetic methods) that have also been applied on the TSP problem. Their benefits on computational efficiency and accuracy are discussed over six datasets that have been created from the GHIM-10K dataset. The experimental results demonstrate that the proposed methods efficiently solve the image sorting problem, producing image sequences that almost agree with human intuition.

Inspec keywords: travelling salesman problems; image retrieval; image sequences; content-based retrieval; pattern clustering; genetic algorithms; sorting

Other keywords: content-based image clustering; unsupervised image sorting; content-based image sorting; similar content; travelling salesman problem; TSP problem; image sequences; GHIM-10K dataset

Subjects: Optical, image and video signal processing; Computer vision and image processing techniques; Optimisation techniques; Information retrieval techniques; Optimisation techniques; Data handling techniques; Combinatorial mathematics

References

    1. 1)
      • 13. Bay, H., Ess, A., Tuytelaars, T., et al: ‘Speeded-up robust features (surf)’, Comput. Vis. Image Underst., 2008, 110, (3), pp. 346–359.
    2. 2)
      • 1. Gygli, M., Grabner, H., Gool, L.V.: ‘Video summarization by learning submodular mixtures of objectives’. Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, Boston, USA, 2015, pp. 3090–3098.
    3. 3)
      • 5. Gutin, G., Punnen, A.P.: ‘The traveling salesman problem and its variations’, vol. 12, (Springer Science & Business Media, Berlin, 2006).
    4. 4)
      • 20. Georgilakis, P.S., Doulamis, N.D., Doulamis, A.D., et al: ‘A novel iron loss reduction technique for distribution transformers based on a combined genetic algorithm-neural network approach’, IEEE Trans. Syst. Man Cybern. C, Appl. Rev., 2001, 31, (1), pp. 16–34.
    5. 5)
      • 15. Krizhevsky, A., Sutskever, I., Hinton, G.E.: ‘Imagenet classification with deep convolutional neural networks’. Advances in Neural Information Processing Systems, Lake Tahoe, USA, 2012, pp. 1097–1105.
    6. 6)
      • 9. Kim, G., Faloutsos, C., Hebert, M.: ‘Unsupervised modeling of object categories using link analysis techniques’. 2008 IEEE Conf. Computer Vision and Pattern Recognition, Anchorage, AK, USA, 2008, p. 342.
    7. 7)
      • 28. Philbin, J., Chum, O., Isard, M., et al: ‘Object retrieval with large vocabularies and fast spatial matching’. IEEE Conf. on Computer Vision and Pattern Recognition, 2007, CVPR'07, Minneapolis, USA, 2007, pp. 1–8.
    8. 8)
      • 26. Manjunath, B.S., Ohm, J.-R., Vasudevan, V.V., et al: ‘Color and texture descriptors’, IEEE Trans. Circuits Syst. Video Technol., 2001, 11, (6), pp. 703–715.
    9. 9)
      • 11. Ventura Royo, C.: ‘Image-based query by example using MPEG-7 visual descriptors’, 2010.
    10. 10)
      • 14. Dalal, N., Triggs, B.: ‘Histograms of oriented gradients for human detection’. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, 2005, CVPR 2005, San Diego, USA, 2005, vol. 1, pp. 886–893.
    11. 11)
      • 7. Hong, S., Choi, J., Feyereisl, J., et al: ‘Joint image clustering and labeling by matrix factorization’, IEEE Trans. Pattern Anal. Mach. Intell., 2016, 38, (7), pp. 1411–1424.
    12. 12)
      • 22. Dorigo, M., Gambardella, L.M.: ‘Ant colonies for the travelling salesman problem’, Biosystems, 1997, 43, (2), pp. 73–81.
    13. 13)
      • 16. Razali, N.M., Geraghty, J.: ‘Genetic algorithm performance with different selection strategies in solving TSP’. Proc. of the World Congress on Engineering, London, UK, 2011, vol. 2, pp. 1134–1139.
    14. 14)
      • 21. El-Samak, A.F., Ashour, W.: ‘Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm’, J. Artif. Intell. Soft Comput. Res., 2015, 5, (4), pp. 239–245.
    15. 15)
      • 19. Gutin, G., Yeo, A., Zverovich, A.: ‘Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP’, Discrete Appl. Math., 2002, 117, (1–3), pp. 81–86.
    16. 16)
      • 29. Radenović, F., Tolias, G., Chum, O.: ‘CNN image retrieval learns from bow: unsupervised fine-tuning with hard examples’. European Conf. on Computer Vision, Amsterdam, Netherlands, 2016, pp. 3–20.
    17. 17)
      • 27. Liu, G.-H., Yang, J.-Y., Li, Z.: ‘Content-based image retrieval using computational visual attention model’, Pattern Recognit., 2015, 48, (8), pp. 2554–2566.
    18. 18)
      • 6. Weise, T., Chiong, R., Lassig, J., et al: ‘Benchmarking optimization algorithms: an open source framework for the traveling salesman problem’, IEEE Comput. Intell. Mag., 2014, 9, (3), pp. 40–52.
    19. 19)
      • 4. Boland, N., Hewitt, M., Vu, D.M., et al: ‘Solving the traveling salesman problem with time windows through dynamically generated time-expanded networks’. Int. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Thessaloniki, Greece, 2017, pp. 254–262.
    20. 20)
      • 10. Panagiotakis, C., Doulamis, A., Tziritas, G.: ‘Equivalent key frames selection based on ISO-content principles’, IEEE Trans. Circuits Syst. Video Technol., 2009, 19, (3), pp. 447–451.
    21. 21)
      • 24. Zagoruyko, S., Komodakis, N.: ‘Learning to compare image patches via convolutional neural networks’. Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, Boston, USA, 2015, pp. 4353–4361.
    22. 22)
      • 30. Blom, M., Krumke, S.O., de Paepe, W.E., et al: ‘The online TSP against fair adversaries’, INFORMS J. Comput., 2001, 13, (2), pp. 138–148.
    23. 23)
      • 25. Panagiotakis, C., Ovsepian, N., Michael, E.: ‘Video synopsis based on a sequential distortion minimization method’. Int. Conf. on Computer Analysis of Images and Patterns, York, UK, 2013, pp. 94–101.
    24. 24)
      • 12. De Sande, K.V., Gevers, T., Snoek, C.: ‘Evaluating color descriptors for object and scene recognition’, IEEE Trans. Pattern Anal. Mach. Intell., 2010, 32, (9), pp. 1582–1596.
    25. 25)
      • 2. Agrawal, A., Karnick, H.: ‘Unsupervised image clustering’. PhD thesis, Indian Institute of Technology, Kanpur, 2009.
    26. 26)
      • 8. Liu, D., Chen, T.: ‘Unsupervised image categorization and object localization using topic models and correspondences between images’. IEEE 11th Int. Conf. on Computer Vision, 2007, ICCV 2007, Rio de Janeiro, Brazil, 2007, pp. 1–7.
    27. 27)
      • 17. Deng, Y., Liu, Y., Zhou, D.: ‘An improved genetic algorithm with initial population strategy for symmetric TSP’, Math. Probl. Eng., 2015, 2015, pp. 1–6.
    28. 28)
      • 3. Ahmed, N.: ‘Recent review on image clustering’, IET Image Process., 2015, 9, (11), pp. 1020–1032.
    29. 29)
      • 23. Mahi, M., Baykan, Ö.K., Kodaz, H.: ‘A new hybrid method based on particle swarm optimization, ant colony optimization and 3-OPT algorithms for traveling salesman problem’, Appl. Soft Comput., 2015, 30, pp. 484–490.
    30. 30)
      • 18. Johnson, D.S., McGeoch, L.A.: ‘The traveling salesman problem: a case study in local optimization’, Local Search Comb. Optim., 1997, 1, pp. 215–310.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2018.5880
Loading

Related content

content/journals/10.1049/iet-ipr.2018.5880
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading