kolayne/find_most_similar_image

A command-line tool for searching for images visually similar to given

Find most similar image

Sorts an array of images by color similarity to a given image.

Imagine you are given a directory with a HUGE amount of images inside and something like a screenshot of one of them.

This script allows you to find an image (in fact images) visually nearest to a given (target) image. It prints a table with absolute paths to original images sorted by similarity so that last entry is the most similar to the target

It also allows to quickly search for images, similar to different targets, if you are searching in the same set of images.

Basic usage

$ ./find_most_similar_image.py -h
usage: find_most_similar_image.py [--help]
                                  [--mode {precalculate,search,onflight}]
                                  [--storage STORAGE] [--dir DIR]
                                  [--target TARGET] [--suppress-extras]

PLASE, NOTE, by default only REQUIRED arguments are displayed in the help message. Use -h/--help argument TWICE to also see OPTIONAL arguments

Sorts an array of images by color similarity to a given image.
Imagine you are given a directory with a HUGE amount of images inside and something like a screenshot of one of them.
This script allows you to find an image (in fact images) visually nearest to a given (target) image. It prints a table with absolute paths to original images sorted by similarity so that last entry is the most similar to the target
It also allows to quickly search for images, similar to different targets, if you are searching in the same set of images.

Abstract usage:
    1. Precalculate data for an images set (multiprocessing is out of the box, see --fork at detailed help)
    2. Search for images an similar to the target
This two steps can be combined into one with the ONFLIGHT mode (default)

optional arguments:
  --help, -h            Show help message and exit. Use it once (-h) to only see most needed arguments, twice (-hh) for detailed help with all arguments described

GLOBAL args:
  --mode {precalculate,search,onflight}, -m {precalculate,search,onflight}
                        The mode in which you want to run ("precalculate" to create storage, "search" to search for images using storage, "onflight" (DEFAULT) is precalculate+search)
  --storage STORAGE, -p STORAGE
                        Path to a data storage (to be created or read)

PRECALCULATION (or ONFLIGHT) mode arguments:
  --dir DIR, -d DIR     Path to the directory with images to precalculate data for

SEARCH (or ONFLIGHT) mode arguments:
  --target TARGET, -t TARGET
                        Path to the target image to search similar to (note that split depth is detected automatically from the storage)
  --suppress-extras, -x
                        Just print absolute path to the most similar image, suppress any other output. Equivalent to "--best-only --no-notes --table-fmt plane --no-headers --no-index --no-error-rate"

Examples:
    With two separate commands:
        ./find_most_similar_image.py --mode precalculate --storage ./storage.json --dir ./source_dir
        ./find_most_similar_image.py --mode search --storage ./storage.json --target ./image.png
    Or with one command:
        ./find_most_similar_image.py --dir ./source_dir --target ./image.png
    Also possible (to save storage):
        ./find_most_similar_image.py --dir ./source_dir --target ./image.png --storage ./storage.json
    When you want to omit all extra messages and, for example, use the output as an argument to another command:
        ./find_most_similar_image.py --dir ./source_dir --target ./image.png --best-only --table-fmt=plain --no-headers --no-notes \
            --no-index --no-error-rate

Advanced usage

$ ./find_most_similar_image.py -hh
usage: find_most_similar_image.py [--help]
                                  [--mode {precalculate,search,onflight}]
                                  [--storage STORAGE] [--fork FORK]
                                  [--dir DIR] [--split-depth SPLIT_DEPTH]
                                  [--target TARGET] [--suppress-extras]
                                  [--best-only] [--no-notes]
                                  [--table-fmt TABLE_FMT] [--no-headers]
                                  [--no-index] [--no-error-rate]

PLASE, NOTE, by default only REQUIRED arguments are displayed in the help message. Use -h/--help argument TWICE to also see OPTIONAL arguments

Sorts an array of images by color similarity to a given image.
Imagine you are given a directory with a HUGE amount of images inside and something like a screenshot of one of them.
This script allows you to find an image (in fact images) visually nearest to a given (target) image. It prints a table with absolute paths to original images sorted by similarity so that last entry is the most similar to the target
It also allows to quickly search for images, similar to different targets, if you are searching in the same set of images.

Abstract usage:
    1. Precalculate data for an images set (multiprocessing is out of the box, see --fork at detailed help)
    2. Search for images an similar to the target
This two steps can be combined into one with the ONFLIGHT mode (default)

optional arguments:
  --help, -h            Show help message and exit. Use it once (-h) to only see most needed arguments, twice (-hh) for detailed help with all arguments described

GLOBAL args:
  --mode {precalculate,search,onflight}, -m {precalculate,search,onflight}
                        The mode in which you want to run ("precalculate" to create storage, "search" to search for images using storage, "onflight" (DEFAULT) is precalculate+search)
  --storage STORAGE, -p STORAGE
                        Path to a data storage (to be created or read)

PRECALCULATION (or ONFLIGHT) mode arguments:
  --fork FORK, -f FORK  Number of parallel processes for precalculation (DEFAULT 1)
  --dir DIR, -d DIR     Path to the directory with images to precalculate data for
  --split-depth SPLIT_DEPTH, -s SPLIT_DEPTH
                        When calculating average colors, all images are split into SPLIT_DEPTH^2 rectangles, average color is calculated for each of them. (DEFAULT 4)

SEARCH (or ONFLIGHT) mode arguments:
  --target TARGET, -t TARGET
                        Path to the target image to search similar to (note that split depth is detected automatically from the storage)
  --suppress-extras, -x
                        Just print absolute path to the most similar image, suppress any other output. Equivalent to "--best-only --no-notes --table-fmt plane --no-headers --no-index --no-error-rate"

OUTPUT STYLE of search (or onflight) mode:
  --best-only, -b       Only print one image filename which is the best match
  --no-notes            Don't show constant notes for user, only print the final table
  --table-fmt TABLE_FMT
                        Table format (explained in detail in the `tabulate` library's docs). Use "plain" to not use any pseudo-graphics (DEFAULT "github")
  --no-headers          Don't show headers of the final table being printed
  --no-index            Don't show first column with indexes in the final table being printed
  --no-error-rate       Don't show last column with error rate in the final table being printed

Examples:
    With two separate commands:
        ./find_most_similar_image.py --mode precalculate --storage ./storage.json --dir ./source_dir
        ./find_most_similar_image.py --mode search --storage ./storage.json --target ./image.png
    Or with one command:
        ./find_most_similar_image.py --dir ./source_dir --target ./image.png
    Also possible (to save storage):
        ./find_most_similar_image.py --dir ./source_dir --target ./image.png --storage ./storage.json
    When you want to omit all extra messages and, for example, use the output as an argument to another command:
        ./find_most_similar_image.py --dir ./source_dir --target ./image.png --best-only --table-fmt=plain --no-headers --no-notes \
            --no-index --no-error-rate

Algorithm overview

The algorithm of looking for similar images is pretty simple.

Firstly (in precalculate mode), the app creates a storage with cached data of images inside --dir and it's subdirectories. Each of these images is split into --split-depth * --split-depth (approximately) equal rectangles, and an average color value is calculated for each of the rectangles. These average colors (and some meta data) are stored in the --storage file.

After that (in search mode), the --storage file is read, the --target image is split into the same number of rectangles the candidates were split into, the average colors for the last rectangles are calculated. A distance between two images now is the sum of distances between corresponding average colors. All the images are sorted by a value called Error rate which is the distance between an image and the target image.

Known issues

• Tqdm bars may behave strange (for example, create empty lines or fake bars) when forking is used

find_most_similar_image's Issues

Split the tool into core and CLI

At the moment the tool only consists of one file, which handles everything: analyzing images, saving storages, etc, and communicating with a user via a CLI. I find the latter function completely separate from the rest, and I want the tool to be split into (at least) two files, one of which would handle the search, why the other one would be dealing with cmd-line arguments (and most likely also managing files, while the core will only work with the data it is supposed to process, converted to the format it is going to be processed in).

This will also make it possible to create a good API: even though at the moment users can import the tool as a python module and use it in their programs, we currently force them to use files, wait for json.loads/np.asarray/etc conventions, which can be a tangible performance drawback when trying to process a large amount of data. Separating the core from the rest code would solve this problem

Tqdm bars display when forking

It seems to be impossible to both keep using the multiprocessing module and fix the issue of tqdm bars displayed incorrectly when using forking (at least, at the moment). However, there is a PR fixing the issue for threading. I'd like to see the measurements of performance when using one thread, multiple threads, and multiple processes. Probably it's a good idea to switch to threads to fix the problem, but I'm not ready to sacrifice performance on a notable scale

Optimize `get_avg_pixels`

Can we delegate the following piece of code to numpy and thus speed it up?

find_most_similar_image/find_most_similar_image.py

Lines 69 to 84 in b136fa0

	def get_avg_pixels(img, split_depth=2):
	ans = np.zeros((split_depth, split_depth, 3))
	img = np.asarray(img)
	x_size, y_size, _ = img.shape
	for x_multiplier in range(split_depth):
	x_range_from = int(x_size / split_depth * x_multiplier)
	x_range_to = int(x_size / split_depth * (x_multiplier + 1))
	for y_multiplier in range(split_depth):
	y_range_from = int(y_size / split_depth * y_multiplier)
	y_range_to = int(y_size / split_depth * (y_multiplier + 1))
	ans[x_multiplier, y_multiplier] = avg(img[x_range_from:x_range_to, y_range_from:y_range_to].ravel())
	return ans

Add docstrings

Document functions in find_most_similar_image.py