embeddings-sort

This program can sort images such that ones with similar content are close together. This is accomplished by using AI to extract the meaning of the image, and then approximating a travelling-salesperson-tour through all of them. As a bonus feature, this program can also sort the images by hue, brightness or color, though the results for this could be improved by using a less generalized algorithm.

The sorting can be accessed by letting the progam print the image paths in order, or by copying/symlinking the images into a new directory.

Detailed usage:

Usage: embeddings-sort [OPTIONS] [IMAGES]...

Arguments:
  [IMAGES]...

Options:
  -e, --embedder <EMBEDDER>        Characteristic to sort by [default: content-angular-distance] [possible values: brightness, hue, color, content-euclidean, content-angular-distance, content-manhatten]
  -s, --symlink-dir <SYMLINK_DIR>  Symlink the sorted images into this directory
  -o, --copy-dir <COPY_DIR>        Copy the sorted images into this directory. Uses COW when available
  -c, --stdout                     Write sorted paths into stdout, one per line
  -0, --stdout0                    Write sorted paths into stdout, null-separated. Overrides -c
  -b, --benchmark                  Output total tour length to stderr
      --tsp-approx <TSP_APPROX>    Algorithm for TSP approximation. Leave as default if unsure [default: christofides] [possible values: mst-dfs, christofides]
  -r <REFINE>                      Number of 2-Opt refinement steps. Has quickly diminishing returns [default: 5]
      --no-rotate                  Don't try to improve result by rotating the output path such that less emphasis is put on the similarity of the first and last image
  -i, --ignore-errors              Ignore failed embeddings
      --hash-seed <HASH_SEED>      Seed for hashing. Random by default
  -h, --help                       Print help

Insides

The christofides implementation uses an approximated min-weight matching algorithm, which may be non-ideal, though I haven't benchmarked how much of a difference it makes (mainly due to the implementation complexity of an exact algorithm, which would also increase the implementations complexity from O(n²) to O(n³) where n is the number of given images).

The 2-Opt refinement algorithm uses a doubly linked list with implicit iteration order to be able to do 2-Opt swaps in O(1), bringing a 2-Opt iteration to O(n²) complexity. Unless --no-rotate is given, the calculated path is rotated in-between 2-Opt iterations such that the longest edge is between the first and the last image - as this edge is of no importance for the output of the algorithm, this improves output quality, though it does not improve the output according to the TSP problem formulation.

Compatibility

embeddings-sort has, at some point, worked on both linux and windows.