A reverse image search algorithm which performs 2D affine transformation-invariant partial image-mat...
Available items
No Items, yet!
The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:
For more information you can check out the discussion here on Hacker News
Transformation-Invariant Reverse Image Search
This repo demos a reverse image search algorithm which performs 2D affine transformation-invariant partial image-matching in sublinear time with respect to the number of images in our database.
An online demo with a description of how the algorithm works is available here: Demo
The /docs directory contains this front end javascript demo: https://pippy360.github.io/transformationInvariantImageSearch
The /fullEndToEndDemo directory contains two full end to end c++ demos of the algorithm.
The two end to end c++ demos use Redis as a database and do a direct hash lookup for the constant number of hashes produced for each query image. Each demo runs in O(1) time with respect to the number of images in the database. A nearest neighbor algorithm could also be used instead to find the closest hash within some threshold which would increase the accuracy but then the algorithm would run in amortized O(log n) time (depending on which NN algorithm was used).
Processing each fragment/triangle of the image only requires the 3 points of the triangle and a read-only copy of the image so the preprocessing for an image is embarrassingly parallel. If implemented correctly there should be a near linear speedup with respect to the number of cores used.
However these demos were created quickly as a proof of concept and as a result are very slow. The demos show the alogrithm works and that it can work in O(1) time.
Setup
This setup was tested on a newly deployed vm on Debian GNU/Linux 9 (stretch), YMMV on different setups.
Instead of running these commands manually you can run the ./setup.sh script while in the /fullEndToEndDemo directory.
Or if you want to run the commands manually...
# From the root of the repo go to ./fullEndToEndDemo cd ./fullEndToEndDemoGrab all the dependencies, this install is pretty huge
sudo apt-get update sudo apt-get install git cmake g++ redis-server libboost-all-dev libopencv-dev python-opencv python-numpy python-scipy -y
#Make it cmake . make
This step is optional. It removes a pointless annoying error opencv spits out
About: https://stackoverflow.com/questions/12689304/ctypes-error-libdc1394-error-failed-to-initialize-libdc1394
sudo ln /dev/null /dev/raw1394
Then run either ./runDemo1.sh or ./runDemo2.sh to run the demo
Python setup
All credit for the python code goes to rachmadaniHaryono and meowcoder.
This setup was tested on a newly deployed vm on Ubuntu 18.04 LTS, YMMV on different setups.
To use python package, do the following:
sudo apt-get update sudo apt-get install python3-pip python3-opencv redis-server -yOn some systems this path is missing
read more here: https://github.com/pypa/pip/issues/3813
PATH="$PATH:~/.local/bin"
#cd to project directory pip3 install .
You also need install redis.
Demo 1
To run this demo go to the /fullEndToEndDemo directory and run ./runDemo1.sh
This demo shows the original image below matching the 8 transformed images below. Each image has some combination of 2D affine transformations applied to it. The demo inserts each of the 8 images individually into the database and then queries the database with the original image.
Output
Here the 8 cats images are inserted first and then the database is queried with the orginal cat image. The original image matches all 8 images despite the transfomations.
The low number of partial image matches is because we are doing direct hash lookups and so even a small bit of change (for example from antialising) can cause the perceptual hash to be ever so slightly off. Finding a closest hash using nearest neighbor would solve this issue.
The demo takes 2 minutes (1 minute 38 seconds*) to run on a quad core VM but could run orders of magnitude faster with a better implementation.
*Thanks to meowcoder for the speed up!
[email protected]:~/transformationInvariantImageSearch/fullEndToEndDemo$ time ./runDemo1.sh Loading image: inputImages/cat1.png ... done Added 46725 image fragments to DB Loading image: inputImages/cat2.png ... done Added 65769 image fragments to DB Loading image: inputImages/cat3.png ... done Added 34179 image fragments to DB Loading image: inputImages/cat4.png ... done Added 44388 image fragments to DB Loading image: inputImages/cat5.png ... done Added 47799 image fragments to DB Loading image: inputImages/cat6.png ... done Added 44172 image fragments to DB Loading image: inputImages/cat7.png ... done Added 67131 image fragments to DB Loading image: inputImages/cat8.png ... done Added 18078 image fragments to DB Loading image: inputImages/cat_original.png ... done Added 30372 image fragments to DB Loading image: inputImages/cat_original.png ... done Matches: inputImages/cat1.png: 12 inputImages/cat2.png: 16 inputImages/cat3.png: 15 inputImages/cat4.png: 1 inputImages/cat5.png: 2 inputImages/cat6.png: 4 inputImages/cat7.png: 43 inputImages/cat8.png: 18 inputImages/cat_original.png: 30352 Number of matches: 30463real 1m38.352s user 2m6.140s sys 0m6.592s
python example
$ time transformation-invariant-image-search insert fullEndToEndDemo/inputImages/cat* && \ time transformation-invariant-image-search lookup fullEndToEndDemo/inputImages/cat_original.pngloading fullEndToEndDemo/inputImages/cat1.png 100%|██| 3/3 [00:07<00:00, 2.66s/it] 100%|██| 3/3 [00:08<00:00, 2.70s/it] 100%|█| 3/3 [00:00<00:00, 270.58it/s] 100%|| 1/1 [00:00<00:00, 2457.12it/s] added 58956 fragments for fullEndToEndDemo/inputImages/cat1.png loading fullEndToEndDemo/inputImages/cat2.png 100%|██| 3/3 [00:07<00:00, 2.64s/it] 100%|██| 3/3 [00:08<00:00, 2.76s/it] 100%|█| 3/3 [00:00<00:00, 149.91it/s] 100%|█| 1/1 [00:00<00:00, 902.00it/s] added 58486 fragments for fullEndToEndDemo/inputImages/cat2.png loading fullEndToEndDemo/inputImages/cat3.png 100%|█████████| 3/3 [00:04<00:00, 1.51s/it] 100%|█████████| 3/3 [00:04<00:00, 1.56s/it] 100%|█| 5025/5025 [00:01<00:00, 3570.22it/s] added 30141 fragments for fullEndToEndDemo/inputImages/cat3.png loading fullEndToEndDemo/inputImages/cat4.png 100%|███| 3/3 [00:07<00:00, 2.58s/it] 100%|███| 3/3 [00:07<00:00, 2.62s/it] 100%|██| 3/3 [00:00<00:00, 434.36it/s] 100%|█| 1/1 [00:00<00:00, 1709.87it/s] added 53013 fragments for fullEndToEndDemo/inputImages/cat4.png loading fullEndToEndDemo/inputImages/cat5.png 100%|█████████| 3/3 [00:08<00:00, 2.90s/it] 100%|█████████| 3/3 [00:09<00:00, 3.07s/it] 100%|█| 9420/9420 [00:02<00:00, 3238.60it/s] added 56493 fragments for fullEndToEndDemo/inputImages/cat5.png loading fullEndToEndDemo/inputImages/cat6.png 100%|█████████| 3/3 [00:07<00:00, 2.41s/it] 100%|█████████| 3/3 [00:07<00:00, 2.50s/it] 100%|█| 7347/7347 [00:02<00:00, 2953.52it/s] added 44030 fragments for fullEndToEndDemo/inputImages/cat6.png loading fullEndToEndDemo/inputImages/cat7.png 100%|███████████| 3/3 [00:11<00:00, 3.82s/it] 100%|███████████| 3/3 [00:11<00:00, 3.94s/it] 100%|█| 10544/10544 [00:04<00:00, 2393.00it/s] added 63089 fragments for fullEndToEndDemo/inputImages/cat7.png loading fullEndToEndDemo/inputImages/cat8.png 100%|█████████| 3/3 [00:03<00:00, 1.06s/it] 100%|█████████| 3/3 [00:03<00:00, 1.07s/it] 100%|█| 3160/3160 [00:01<00:00, 3138.56it/s] added 18899 fragments for fullEndToEndDemo/inputImages/cat8.png loading fullEndToEndDemo/inputImages/cat_original.png 100%|█████████| 3/3 [00:05<00:00, 1.93s/it] 100%|█████████| 3/3 [00:05<00:00, 1.94s/it] 100%|█| 5795/5795 [00:01<00:00, 3211.96it/s] added 34764 fragments for fullEndToEndDemo/inputImages/cat_original.png transformation-invariant-image-search insert fullEndToEndDemo/inputImages/cat 141,98s user 10,14s system 159% cpu 1:35,54 total loading fullEndToEndDemo/inputImages/cat_original.png 100%|█████████| 3/3 [00:05<00:00, 1.83s/it] 100%|█████████| 3/3 [00:05<00:00, 1.94s/it] 100%|█| 5795/5795 [00:01<00:00, 3221.91it/s] matches for fullEndToEndDemo/inputImages/cat_original.png: 34770 fullEndToEndDemo/inputImages/cat_original.png 237 fullEndToEndDemo/inputImages/cat7.png 36 fullEndToEndDemo/inputImages/cat2.png 19 fullEndToEndDemo/inputImages/cat4.png 14 fullEndToEndDemo/inputImages/cat8.png 7 fullEndToEndDemo/inputImages/cat1.png 4 fullEndToEndDemo/inputImages/cat3.png 2 fullEndToEndDemo/inputImages/cat5.png 1 fullEndToEndDemo/inputImages/cat6.png transformation-invariant-image-search lookup 12,71s user 1,62s system 151% cpu 9,472 total
Demo 2
To run this demo go to the /fullEndToEndDemo directory and run ./runDemo2.sh
This demo shows partial image matching. The query image below (c) is a composite of images (a) and (b). The demo inserts images (a) and (b) into the database and then queries with image (c). Image (d) and (e) show the matching fragments, each coloured triangle is a fragment of the image that matched the composite image (c).
Output
Here the two images mona.jpg and van_gogh.jpg are inserted into the database and then the database is queried with monaComposite.jpg. The demo takes 5 minutes 17 seconds (4 minutes 36 seconds*) to run on a quad core VM but could run orders of magnitude faster with a better implementation.
*Thanks to meowcoder for the speed up!
[email protected]:~/transformationInvariantImageSearch/fullEndToEndDemo$ time ./runDemo2.sh Loading image: ./inputImages/mona.jpg ... done Added 26991 image fragments to DB Loading image: ./inputImages/van_gogh.jpg ... done Added 1129896 image fragments to DB Loading image: ./inputImages/monaComposite.jpg ... done Matches: ./inputImages/mona.jpg: 5 ./inputImages/van_gogh.jpg: 1478 Number of matches: 1483real 4m36.635s user 6m50.988s sys 0m18.224s
python example
$ time transformation-invariant-image-search insert ./fullEndToEndDemo/inputImages/mona.jpg ./fullEndToEndDemo/inputImages/van_gogh.jpg && \ time transformation-invariant-image-search lookup ./fullEndToEndDemo/inputImages/monaComposite.jpgloading ./fullEndToEndDemo/inputImages/mona.jpg 100%|███| 3/3 [00:03<00:00, 1.24s/it] 100%|███| 3/3 [00:03<00:00, 1.20s/it] 100%|██| 3/3 [00:00<00:00, 302.48it/s] 100%|█| 1/1 [00:00<00:00, 2471.60it/s] added 24145 fragments for ./fullEndToEndDemo/inputImages/mona.jpg loading ./fullEndToEndDemo/inputImages/van_gogh.jpg 100%|█████████████| 3/3 [02:50<00:00, 56.01s/it] 100%|█████████████| 3/3 [02:50<00:00, 56.14s/it] 100%|█| 178267/178267 [00:56<00:00, 3170.20it/s] added 1058329 fragments for ./fullEndToEndDemo/inputImages/van_gogh.jpg transformation-invariant-image-search insert 384,51s user 12,84s system 168% cpu 3:56,42 total loading ./fullEndToEndDemo/inputImages/monaComposite.jpg 100%|███████████| 3/3 [01:01<00:00, 20.88s/it] 100%|███████████| 3/3 [01:01<00:00, 20.77s/it] 100%|█| 61563/61563 [00:19<00:00, 3129.92it/s] matches for ./fullEndToEndDemo/inputImages/monaComposite.jpg: 1332 ./fullEndToEndDemo/inputImages/van_gogh.jpg 11 ./fullEndToEndDemo/inputImages/mona.jpg transformation-invariant-image-search lookup 133,29s user 5,07s system 164% cpu 1:24,30 total