LIRE Use Case “What Anime is this?”

screenshot-animeI do not often hear of application built with LIRE, however if I do I really appreciate it. The use case of What Anime is this? is exceptional in many ways. First of all LIRE was very well applied and can really solve a problem there, and second, Soruly Ho tuned it to search through over 360 million images on a single server with incredibly reasonable response time.

The web page built by Soruly Ho provides a search interface to (re-)find frames in Anime videos. Not being into Anime myself I still know it’s a hand drawn or computer animation and it’s hugely popular among fans … and there are a lot of them.

Soruly Ho was so nice to compile background information on his project:

Thanks to the LIRE Solr Integration Project, I was able to develop the first prototype just 12 hours after I met LIRE, without touching a line of the source code! After setting up the web server and Solr, I just have to write a few scripts to put all the pieces together. To analyze the video, I use ffmpeg to extract each frame as a jpg file with the timecode as the file name. Then, the ParallelSolrIndexer analyze all these images and generate an XML file. Before loading this XML into Solr, I use a Python script to put the video path and timecode to the title field. Finally, I write a few lines of Javascript to use Solr REST API to submit the image URL to the LireRequestHandler. After some magic, it would return a list of matching images sorted by similarity, with the original video path and timecode in the title field. The idea is pretty simple. Every developer can build this.

But scaling is challenging. There are over 15,000 hours of video indexed in my search engine. Assume they are all 24 fps, there would be 1.3 billion frames in total. This is too big to fit in my server (which is just a high-end PC). Video always play forward in time, so I use a running window to remove duplicate frames. Unlike real life video, most anime are actually drawn in 12 fps or less, this method significantly reduces number of frames by 70%. Out of many feature classes supported by LIRE, I only use the Color Layout Descriptor and drop others to save space, memory and computation time for analysis. Now, each analyzed frame in my Solr index only occupies 197 Bytes. Still, solely relying on one image descriptor already achieves very high accuracy. Even after such optimization, the remaining 366 million frames are still too much that the query would often timeout. So I studied and modified a little bit of the LireRequestHandler. (It is great that LIRE is free and open source!) Instead of using the performance-killing BooleanClause.Occur.SHOULD, I search the hashes with BooleanClause.Occur.MUST one by one until a good match is found. I am only interested to images with similarity > 90%, i.e. there is at least one common hash if I select 10 out of 100 hash values at random. The search would complete in at most 10 iterations, otherwise, I assume there is no match. But random is not good because results are inconsistent, thus, cannot be cached. So I ran an analysis on the hash distribution, and always start searching from the least populated hash. So, similarity calculation is performed on a smaller set of images. The Color Layout Descriptor does not produce an evenly distributed hash on anime. Least populated hash matches only a few frames while most populated hash matches over 277 million frames. The last performance issue is keeping a 67.5GB index with just 32GB RAM, which I think can be solved with just more RAM.

The actual source I have modified and my hash distribution table, can be found on Github.

You can try What Anime is this? yourself at https://whatanime.ga/. Thanks to Soruly Ho for sharing his thoughts and building this great search engine!

CBMI 2016 Deadline extended to March 7, 2016

The 14th International Workshop on Content-based Multimedia Indexing aims at bringing together the various communities involved in all aspects of content-based multimedia indexing for retrieval, browsing, visualization and analytics.

In addition to multimedia and social media search and retrieval, we wish to highlight related and equally important issues that build on content-based indexing, such as multimedia content management, user interaction and visualization, media analytics, etc.

Find the call and the new dates at http://cbmi2016.upb.ro/

14th CBMI Deadlines Approaching

CBMI aims at bringing together the various communities involved in all aspects of content-based multimedia indexing for retrieval, browsing, visualization and analytics.

In addition to multimedia and social media search and retrieval, we wish to highlight related and equally important issues that build on content-based indexing, such as multimedia content management, user interaction and visualization, media analytics, etc.

Additional special sessions are planned in areas such as deep learning, medical image retrieval, and eLearning.

Deadlines

  • February 1: Full/short paper submission deadline
  • February 1: Special session paper submission deadline
  • February 29: Demo paper submission deadline

LIRE 1.0b2 released

LireLogo_small

Today, the first official beta version of LIRE 1.0 has been released. After loads of internal tests we decided to pin it down to quasi-stable. There are loads of new features compared to 0.9.5 including metric spaces indexing, DocValues based searching, the SIMPLE approach for localizing global descriptors, new global ones, like CENTRIST, a lot of performance tweaks, and so on.

For those of you using the nightly build or the repository version not much changed, everyone else might check out the new APIs and possibilities staring from the SimpleApplication collection moving over to the LIRE documentation.

You will find the pre-compiled binaries on the download page, hosted by ITEC / Klagenfurt University.

 

 

A search runtime analysis of LIRE on 500k images

Run time for search in LIRE heavily depends on the method used for indexing and search. There are two main ways to store data and two search strategies for linear search and there is approximate indexing of course. The two storing strategies are to (i) store the actual feature vector in a Lucene text field and (ii) to use the Lucene DocValues data format. While the former allows for easy access, more flexibility and compression, the latter is much faster when accessing raw byte[] data. Linear search then needs to open each and every document and compare the query vector to the one stored in the document. For linear search in Lucene text fields, caching boosts performance, so the byte[] data of the feature vectors is read once from the index and stored in memory. For the DocValues data storage format access is fast enough to allow for linear search. With approximate indexing a query string is used on the inverted index and only the first k best matching candidates are used to fin the n << k actual results by linear search. So first a text search is done, then a linear search on much less images is performed [1]. In our tests we used k=500 and n=10.

Tests on 499,207 images have shown that with this order approximate search is already outperforming linear search. The following numbers are given in ms search time. Note at this point that the average value per search differs for a different number of test runs due to the context of the runs, ie. the state of the Java VM, OS processes, file systems, etc. But the trend can be seen.

ms per search avg. on 10 runs

ms per search avg. on 100 runs

Cached linear search on text fields (*)

969.8

867.5

Not cached linear search on text fields

5,090.7

n.a.

Linear search on DocValues

636.3

634.1

Approximate search by Metric Spaces (**)

523.9

370.4

(*) Start-up latency when filling the cache was 6.098 seconds

(**) Recall with 10 results on ten runs was 0.76, on 100 run recall was 0.72

As a conclusion with nearly 500,000 images the DocValues approach might be the best choice, as the approximate indexing is loosing around 25% of the results while not boosting runtime performance that much. Further optimization would be for instance query bundling or index splitting in combination with multithreading.

[1] Gennaro, Claudio, et al. “An approach to content-based image retrieval based on the Lucene search engine library.” Research and Advanced Technology for Digital Libraries. Springer Berlin Heidelberg, 2010. 55-66.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. (c) Mathias Lux, 2015

Caliph & Emir moved to Github

I just moved Caliph & Emir to Github. Due to necessary bug fixes, which now allow it to be run on Java 7 & 8 I took the chance to move it to the more sleek and focused Github portal. I also released the binary version as v0.9.27 tested with Java 7 and 8 on Windows 7. If you use Caliph & Emir for research, please don’t forget to cite

Lux, Mathias. “Caliph & Emir: MPEG-7 photo annotation and retrieval.” Proceedings of the 17th ACM international conference on Multimedia. ACM, 2009.

LIRE Help & Communication

Hi there! I’m writing this basically in my own interest, but it may save me and you time :) I currently get a lot of mails regarding LIRE on how to do that, how to use that, or how to fix that. While I totally appreciate the popularity, I still have a “day job”, by being an associate professor at Klagenfurt University in Austria and I cannot answer all the mails. However, there are skilled and motivated people there, subscribed to the mailing list, who can answer many of the questions, and there are others, who might have the same questions, but have to ask them over again because of those private conversations.

Therefore, I ask for all contact on LIRE support to be handled on the mailing list and not via private messages or mails to me. This helps all of us, as questions will less often be asked twice, and other people get a chance to help.

If the mailing list does not work for you because you need to keep a lid on a not-yet released project, or you want to have priority support, you can make use of the consulting services I offer in context of LIRE and content based retrieval.

Web page changes

Due to a security breach on the wiki, the developer documentation was spammed by a bot net, leading to a warning from my hosting company to get it under control. After getting it under control by basically taking the wiki online and replacing it with a static error page, we cam up with a new way of handling the developer documentation.

First it’s now based on markdown files, which are located in the LIRE source SVN. We are using MkDocs, an awesome python script, to generate the static html files and serve them from the former wiki location.

So how to contribute now? It’s rather easy: Either write a new markdown file for a topic, or checkout an existing one, edit it to your will and send us a patch on the mailing list.

LIRE 0.9.5 released

It’s been more than a year since we made a release, so there have been lots of changes, fixes and new features. Most important of all is the integration of the SIMPLE descriptor, a local feature that works extremely well for content based image retrieval. This has been done with a lot of help from Nektarios Anagnostopoulos and Savvas Chatzichristofis!

Besides that we switched to OpenCV for SURF and SIFT extraction, added numerous bug fixes, updated Lucene to 4.10.2 and much more. Best you give it a try.

>> Head over to the downloads

 

New LIRE Demo online

I just put up the new LIRE demo at http://demo-itec.uni-klu.ac.at/liredemo/. It’s based on the LIRE Solr plugin, which now supports arbitrary LIRE features and has been updated to fit the current Solr version 4.10.2.

Check out the new search options for searching for tags in combination with image similarity. Basically you can use the first parameter box to search for any string (ie. tags:dog) and the use the sort option below the images to re-rank the images according to the similarity of the selected picture.

Btw. thanks go to my department, the Department of Information Technology at the Faculty of Technical Sciences of the Alpen-Adria-Universität Klagenfurt for running the demo on their servers.