notebooks/eda/image_hashes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import time\n",
    "import json\n",
    "import pickle\n",
    "import hashlib\n",
    "from collections import defaultdict\n",
    "from collections import Counter\n",
    "from concurrent.futures import ThreadPoolExecutor\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "from tqdm import tqdm_notebook\n",
    "from skimage.util import montage\n",
    "import cv2\n",
    "from cv2 import img_hash\n",
    "\n",
    "from sdcdup.utils import get_project_root\n",
    "from sdcdup.utils import overlap_tag_maps\n",
    "from sdcdup.utils import overlap_tag_pairs\n",
    "from sdcdup.utils import generate_pair_tag_lookup\n",
    "from sdcdup.utils import get_hamming_distance\n",
    "from sdcdup.utils import get_hamming_distance_array\n",
    "from sdcdup.features import SDCImageContainer\n",
    "from sdcdup.visualization import get_ticks\n",
    "from sdcdup.visualization import draw_overlap_bbox\n",
    "\n",
    "%load_ext dotenv\n",
    "%dotenv\n",
    "%matplotlib inline\n",
    "%reload_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "SMALL_SIZE = 10\n",
    "MEDIUM_SIZE = 12\n",
    "BIGGER_SIZE = 16\n",
    "BIGGEST_SIZE = 20\n",
    "plt.rc('font', size=BIGGEST_SIZE)         # controls default text sizes\n",
    "plt.rc('axes', titlesize=BIGGEST_SIZE)    # fontsize of the axes title\n",
    "plt.rc('axes', labelsize=BIGGEST_SIZE)    # fontsize of the x and y labels\n",
    "plt.rc('xtick', labelsize=BIGGER_SIZE)    # fontsize of the tick labels\n",
    "plt.rc('ytick', labelsize=BIGGER_SIZE)    # fontsize of the tick labels\n",
    "plt.rc('legend', fontsize=MEDIUM_SIZE)    # legend fontsize\n",
    "plt.rc('figure', titlesize=BIGGEST_SIZE)  # fontsize of the figure title\n",
    "\n",
    "montage_rgb = lambda x: np.stack([montage(x[:, :, :, i]) for i in range(x.shape[3])], -1)\n",
    "\n",
    "project_root = get_project_root()\n",
    "train_image_dir = os.path.join(project_root, os.getenv('RAW_DATA_DIR'), 'train_768')\n",
    "interim_data_dir = os.path.join(project_root, os.getenv('INTERIM_DATA_DIR'))\n",
    "pair_tag_lookup = generate_pair_tag_lookup()\n",
    "ticks = get_ticks()\n",
    "\n",
    "matches_white = {\n",
    "    'bmh32': tuple(np.ones(32, dtype='uint8') * 255),\n",
    "    'bmh96': tuple(np.ones(96, dtype='uint8') * 255)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matches_metric = 'bmh32'\n",
    "matches_threshold = 0.9\n",
    "\n",
    "sdcic = SDCImageContainer()\n",
    "sdcic.load_image_metrics(['md5', 'bmh32', 'bmh96', 'avg'])\n",
    "img_ids = os.listdir(train_image_dir)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## All have the same blockMeanHash, but they each have different md5 hashes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "black_tile = np.zeros((256, 256, 3), dtype=np.uint8)\n",
    "white_tile = black_tile + 255\n",
    "blue_tile = np.copy(black_tile)\n",
    "blue_tile[:, :, 0] = 255\n",
    "red_tile = np.copy(black_tile)\n",
    "red_tile[:, :, 2] = 255\n",
    "color_tiles = [black_tile, white_tile, blue_tile, red_tile]\n",
    "for color_tile in color_tiles:\n",
    "    print(hashlib.md5(color_tile.tobytes()).hexdigest())\n",
    "    print(img_hash.blockMeanHash(color_tile, mode=0)[0])\n",
    "    # ...for each color channel\n",
    "    hash0 = img_hash.blockMeanHash(color_tile[..., 0], mode=0)\n",
    "    hash1 = img_hash.blockMeanHash(color_tile[..., 1], mode=0)\n",
    "    hash2 = img_hash.blockMeanHash(color_tile[..., 2], mode=0)\n",
    "    print(np.hstack([hash0, hash1, hash2])[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find overlapping images with hashlib.md5\n",
    "Update: The values between two supposedly exact 256x256 crops are not always exact (See below)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "md5hash_dict = defaultdict(list)\n",
    "for img_id in tqdm_notebook(img_ids):\n",
    "    for h in sdcic.img_metrics['md5'][img_id]:\n",
    "        md5hash_dict[h].append(img_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dup_counts_dict = defaultdict(int)\n",
    "for key, dups in md5hash_dict.items():\n",
    "    dup_counts_dict[len(dups)] += 1\n",
    "\n",
    "sorted_bin_sizes = sorted(dup_counts_dict.items())\n",
    "print('n images with k duplicates')\n",
    "print('(k, n)')\n",
    "sorted_bin_sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "batch_size = 9\n",
    "skip = 365\n",
    "ii = 0\n",
    "jj = 0\n",
    "\n",
    "for hash_id, dups in md5hash_dict.items():\n",
    "    ii += 1\n",
    "    if len(dups) == batch_size:\n",
    "        dups0 = list(set(dups))\n",
    "        img_id = dups0[0]\n",
    "        idx = sdcic.img_metrics['md5'][img_id].tolist().index(hash_id)\n",
    "        print(hash_id, len(dups), ii)\n",
    "        if jj == min(dup_counts_dict[len(dups)], skip):\n",
    "            break\n",
    "        jj += 1\n",
    "\n",
    "batch_limit = 9\n",
    "samples_images = np.empty((batch_limit, 768, 768, 3), dtype=np.float32)\n",
    "for i, c_img_id in enumerate(dups0[:batch_limit]):\n",
    "    c_img = cv2.cvtColor(sdcic.get_img(c_img_id), cv2.COLOR_BGR2RGB)\n",
    "    samples_images[i] = c_img.astype(np.float32) / 255.0\n",
    "\n",
    "batch_rgb = montage_rgb(samples_images)\n",
    "\n",
    "fig, ax = plt.subplots(1, 1, figsize = (16, 16))\n",
    "ax.imshow(batch_rgb, vmin=0, vmax=1)\n",
    "plt.axis('off')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find overlapping images with cv2.blockMeanHash \n",
    "(Using only exact first matches)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO: Use filter for all overlaps here?\n",
    "# img_ids = filter_duplicates(img_ids)\n",
    "\n",
    "bm0hash_dict = defaultdict(set)\n",
    "for img_id in tqdm_notebook(img_ids):\n",
    "    for h in sdcic.img_metrics[matches_metric][img_id]:\n",
    "        bm0hash_dict[tuple(h)].add(img_id)  # hex\n",
    "\n",
    "bm0hash_dict.pop(matches_white[matches_metric])\n",
    "\n",
    "sorted_hash_dict = {}\n",
    "for key, dups in sorted(bm0hash_dict.items(), key=lambda x: len(x[1]), reverse=True):\n",
    "    if len(dups) > 1:\n",
    "        sorted_hash_dict[key] = sorted(dups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dup_counts_dict = defaultdict(int)\n",
    "for key, dups in bm0hash_dict.items():\n",
    "    dup_counts_dict[len(dups)] += 1\n",
    "\n",
    "sorted_bin_sizes = sorted(dup_counts_dict.items())\n",
    "print('n images with k duplicates')\n",
    "print('(k, n)')\n",
    "sorted_bin_sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_matches(sorted_hash_dict, sdcic, matches_metric, matches_threshold):\n",
    "\n",
    "    test_matches = set()\n",
    "    for hash_id, img_list in tqdm_notebook(sorted_hash_dict.items()):\n",
    "\n",
    "        hamming_lookup = {img_id: get_hamming_distance_array(sdcic.img_metrics[matches_metric][img_id], np.asarray(hash_id)[None, :], normalize=True, as_score=True) for img_id in img_list}\n",
    "        \n",
    "        temp_matches = set()\n",
    "        for img1_id in img_list:\n",
    "            tiles1 = [idx for idx, bmhd in enumerate(hamming_lookup[img1_id]) if bmhd >= matches_threshold]\n",
    "            for img2_id in img_list:\n",
    "                if img2_id <= img1_id:\n",
    "                    continue\n",
    "                tiles2 = [idx for idx, bmhd in enumerate(hamming_lookup[img2_id]) if bmhd >= matches_threshold]\n",
    "\n",
    "                # create a set of valid overlap_tags based on matching image tiles.\n",
    "                overlap_tags = set()\n",
    "                for t1 in tiles1:\n",
    "                    for t2 in tiles2:\n",
    "                        overlap_tags.add(pair_tag_lookup.get((t1, t2)))\n",
    "\n",
    "                for img1_overlap_tag in overlap_tags:\n",
    "                    temp_matches.add((img1_id, img2_id, img1_overlap_tag))\n",
    "\n",
    "        test_matches.update(temp_matches)\n",
    "        \n",
    "    return test_matches\n",
    "\n",
    "def generate_matches2(test_matches, sdcic, matches_metric, matches_threshold):\n",
    "    matches = set()\n",
    "    for match in tqdm_notebook(sorted(test_matches)):\n",
    "        bmh_scores = sdcic.overlap_scores_config[matches_metric]['func'](*match)\n",
    "        if min(bmh_scores) < matches_threshold:\n",
    "            continue\n",
    "        matches.add(tuple(match))\n",
    "    \n",
    "    return matches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_matches = generate_matches(sorted_hash_dict, sdcic, matches_metric, matches_threshold)\n",
    "print(len(test_matches))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matches = generate_matches2(test_matches, sdcic, matches_metric, matches_threshold)\n",
    "print(len(matches))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matches_file = f'matches_{matches_metric}_{matches_threshold}.csv'\n",
    "full_matches_file = os.path.join(interim_data_dir, matches_file)\n",
    "df = pd.DataFrame(sorted(matches))\n",
    "df.to_csv(full_matches_file, index=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "batch_size = 18\n",
    "skip = 5\n",
    "ii = 0\n",
    "jj = 0\n",
    "\n",
    "for hash_id, dups in bm0hash_dict.items():\n",
    "    ii += 1\n",
    "    if len(dups) == batch_size:\n",
    "        dups0 = list(set(dups))\n",
    "        img_id = dups0[0]\n",
    "        idx = np.where(np.all(sdcic.img_metrics[matches_metric][img_id] == np.asarray(hash_id), axis=1))[0]\n",
    "        print(hash_id, len(dups), ii)\n",
    "        if jj == min(dup_counts_dict[len(dups)], skip):\n",
    "            break\n",
    "        jj += 1\n",
    "\n",
    "batch_limit = 9\n",
    "samples_images = np.empty((batch_limit, 768, 768, 3), dtype=np.float32)\n",
    "for i, c_img_id in enumerate(dups0[:batch_limit]):\n",
    "    c_img = cv2.cvtColor(sdcic.get_img(c_img_id), cv2.COLOR_BGR2RGB)\n",
    "    samples_images[i] = c_img.astype(np.float32) / 255.0\n",
    "\n",
    "batch_rgb = montage_rgb(samples_images)\n",
    "\n",
    "fig, ax = plt.subplots(1, 1, figsize = (16, 16))\n",
    "ax.imshow(batch_rgb, vmin=0, vmax=1)\n",
    "plt.axis('off')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find overlapping images with cv2.blockMeanHash \n",
    "(Using first matches within some threshold.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "score_to_hashes_file = os.path.join(interim_data_dir, f'score_to_hashes_{matches_metric}.pkl')\n",
    "score_to_hashes_file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hash_dict = defaultdict(set)\n",
    "\n",
    "for img_id in tqdm_notebook(sorted(img_ids)):\n",
    "    for h in sdcic.img_metrics[matches_metric][img_id]:\n",
    "        hash_dict[tuple(h)].add(img_id)\n",
    "\n",
    "hash_dict.pop(matches_white[matches_metric])\n",
    "\n",
    "sorted_hash_dict = {}\n",
    "for key, dups in sorted(hash_dict.items(), key=lambda x: len(x[1]), reverse=True):\n",
    "    if len(dups) > 1:\n",
    "        sorted_hash_dict[key] = sorted(dups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bmh_groups = Counter()\n",
    "for key in sorted_hash_dict:\n",
    "    bmh_groups[np.sum(np.unpackbits(key))] += 1\n",
    "\n",
    "for key, val in sorted(bmh_groups.items()):\n",
    "    print(key, val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "score_to_hashes0 = defaultdict(set)\n",
    "\n",
    "for img_id in tqdm_notebook(sorted(img_ids)):\n",
    "    for h in sdcic.img_metrics[matches_metric][img_id]:\n",
    "        score = np.sum(np.unpackbits(h))\n",
    "        score_to_hashes0[int(score)].add(tuple(h))\n",
    "        \n",
    "score_to_hashes0.pop(sdcic.img_metrics_config[matches_metric]['len']*8)\n",
    "\n",
    "score_to_hashes1 = defaultdict(list)\n",
    "for score, h_tup_set in tqdm_notebook(sorted(score_to_hashes0.items())):\n",
    "    for h_tup in sorted(h_tup_set):\n",
    "        score_to_hashes1[score].append(tuple(map(int, h_tup)))\n",
    "print(len(score_to_hashes1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "with open(score_to_hashes_file, 'wb') as ofs:\n",
    "    pickle.dump(score_to_hashes1, ofs, pickle.HIGHEST_PROTOCOL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(score_to_hashes_file, 'rb') as ofs:\n",
    "    score_to_hashes1 = pickle.load(ofs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "score_to_hashes = defaultdict(list)\n",
    "for score, h_tup_list in tqdm_notebook(score_to_hashes1.items()):\n",
    "    for h_tup in sorted(h_tup_list):\n",
    "        score_to_hashes[score].append(np.array(h_tup, dtype=np.uint8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for score, hashes in sorted(score_to_hashes.items()):\n",
    "    print(score, len(hashes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bit_difference(b1, b2):\n",
    "    return np.sum(b1[:, None, :] ^ b2[None, :, :], dtype=np.int, axis=2)\n",
    "\n",
    "def get_array_splits(size, max_size):\n",
    "    n_splits = (size - 1) // max_size\n",
    "    pivot = size // (n_splits + 1)\n",
    "    pivots = [ii * pivot for ii in range(n_splits + 1)] + [size]\n",
    "    splits = [(p1, p2) for p1, p2 in zip(pivots[:-1], pivots[1:])]\n",
    "    return splits\n",
    "\n",
    "def parallel_process(b1, b2, max_size):\n",
    "\n",
    "    b1_splits = get_array_splits(b1.shape[0], max_size)\n",
    "    b2_splits = get_array_splits(b2.shape[0], max_size)\n",
    "    \n",
    "    splits = []\n",
    "    b1_chunks = []\n",
    "    b2_chunks = []\n",
    "    for b1_split in b1_splits:\n",
    "        for b2_split in b2_splits:\n",
    "            splits.append((b1_split, b2_split))\n",
    "            b1_chunks.append(b1[b1_split[0]:b1_split[1]])\n",
    "            b2_chunks.append(b2[b2_split[0]:b2_split[1]])\n",
    "\n",
    "    bit_diff = np.zeros((b1.shape[0], b2.shape[0]), dtype=np.int)\n",
    "    with ThreadPoolExecutor() as executor:\n",
    "        for split, bit_diff_chunk in zip(splits, executor.map(bit_difference, b1_chunks, b2_chunks)):\n",
    "            bit_diff[split[0][0]:split[0][1], split[1][0]:split[1][1]] = bit_diff_chunk\n",
    "            \n",
    "    return bit_diff\n",
    "\n",
    "def get_bit_difference(b1, b2, max_size):\n",
    "    \n",
    "    if b1.shape[0] > max_size or b2.shape[0] > max_size:\n",
    "        return parallel_process(b1, b2, max_size)\n",
    "    else:\n",
    "        return bit_difference(b1, b2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for bmh96\n",
    "bounds < 2000\n",
    "max_size = 500\n",
    "max_offset = 3\n",
    "       Workers              Time\n",
    "single       1  598.7040269374847\n",
    "thread       4  295.7433452606201\n",
    "thread      12  230.2517523765564\n",
    "thread      18  228.97077655792236\n",
    "thread     all  225.48815441131592\n",
    "process      4  626.4333462715149\n",
    "\n",
    "max_offset = 3\n",
    "workers: all\n",
    "      max_size              Time\n",
    "thread     500  225.48815441131592\n",
    "thread     400  199.03486013412476\n",
    "thread     200  110.82181811332703\n",
    "thread     100   98.9623429775238\n",
    "thread      50  113.35412073135376\n",
    "\n",
    "5000 < bounds < 6000\n",
    "max_offset = 1\n",
    "workers: all\n",
    "      max_size              Time\n",
    "process    500   63.29715895652771\n",
    "process    400   62.84799337387085\n",
    "process    200   61.1794650554657\n",
    "process    100   69.73269319534302\n",
    "thread     500   36.114161252975464\n",
    "thread     200   27.83505415916443\n",
    "thread     100   30.965204000473022\n",
    "\n",
    "15000 < bounds < 16000\n",
    "max_offset = 1\n",
    "workers: all\n",
    "      max_size              Time\n",
    "process    500   34.47118520736694\n",
    "process    200   33.95744609832764\n",
    "process    100   37.45988988876343\n",
    "thread     500   32.89252519607544\n",
    "thread     200   26.59809684753418\n",
    "thread     100   27.964319229125977\n",
    "\n",
    "24780 < bounds\n",
    "max_offset = 1\n",
    "workers: all\n",
    "      max_size              Time\n",
    "process   1000   88.20187282562256\n",
    "process    500   82.89880657196045\n",
    "process    400   82.8500907421112\n",
    "process    300   81.7402081489563\n",
    "process    200   79.99603962898254\n",
    "process    100   91.45985507965088\n",
    "thread     500   89.29903173446655\n",
    "thread     300   86.33439707756042\n",
    "thread     200   69.23344659805298, 67.5252251625061\n",
    "thread     100   76.26239681243896\n",
    "\n",
    "for bmh32\n",
    "40900 < bounds\n",
    "max_offset = 1\n",
    "workers: all\n",
    "      max_size              Time\n",
    "thread     400   75.88064217567444\n",
    "thread     350   73.0563383102417\n",
    "thread     300   75.30764889717102\n",
    "thread     200   77.82986497879028\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_offset = int(sdcic.img_metrics_config[matches_metric]['len']*8*(1.0-matches_threshold))+1\n",
    "# max_offset = 1\n",
    "max_size = 350\n",
    "print(max_offset, max_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "t00 = time.time()\n",
    "overlap_tile_candidates = {}\n",
    "ii = 0\n",
    "for s1, h1 in tqdm_notebook(sorted(score_to_hashes.items())):\n",
    "\n",
    "#     if len(h1) < 40900:\n",
    "#         continue\n",
    "#     if len(h1) > 400:\n",
    "#         continue\n",
    "\n",
    "    for offset in range(max_offset):\n",
    "        \n",
    "        t0 = time.time()\n",
    "        s2 = s1 + offset + 1\n",
    "        \n",
    "        if s2 not in score_to_hashes:\n",
    "            continue\n",
    "            \n",
    "        h2 = score_to_hashes[s2]\n",
    "    \n",
    "#         if len(h2) < 41000:\n",
    "#             continue\n",
    "#         if len(h2) > 400:\n",
    "#             continue\n",
    "\n",
    "        b1 = np.unpackbits(h1, axis=1)\n",
    "        b2 = np.unpackbits(h2, axis=1)\n",
    "        res = get_bit_difference(b1, b2, max_size)\n",
    "        overlap_tile_candidate = np.argwhere(res <= max_offset)\n",
    "        if len(overlap_tile_candidate) == 0:\n",
    "            continue\n",
    "            \n",
    "        overlap_tile_candidates[(s1, s2)] = overlap_tile_candidate\n",
    "        print(f'{ii}, {s1}, {s2}, {offset + 1}, {b1.shape[0]}, {b2.shape[0]}, {len(overlap_tile_candidate)}, {time.time() - t0}')\n",
    "        ii += 1\n",
    "\n",
    "print(time.time() - t00)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "overlap_tile_candidates_file = os.path.join(interim_data_dir, f'prematch_candidates_{matches_metric}_{matches_threshold}.csv')\n",
    "overlap_tile_candidates_file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(overlap_tile_candidates_file, 'w') as ofs:\n",
    "    for (idx1, idx2), arr in tqdm_notebook(overlap_tile_candidates.items()):\n",
    "        if len(arr) == 0:\n",
    "            continue\n",
    "        ofs.write(','.join(map(str, [idx1, idx2, *arr.flatten()])) + '\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "overlap_tile_candidates = {}\n",
    "with open(overlap_tile_candidates_file, 'r') as ifs:\n",
    "    for line in tqdm_notebook(ifs.readlines()):\n",
    "        idx1_str, idx2_str, *arr_str = line.strip().split(',')\n",
    "        arr = np.array(list(map(np.int64, arr_str)))\n",
    "        overlap_tile_candidates[(int(idx1_str), int(idx2_str))] = arr.reshape((-1, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "flip_count = 0\n",
    "match_count = 0\n",
    "total_count = 0\n",
    "test_matches = set()\n",
    "for (s1, s2), hash_index_pairs in tqdm_notebook(overlap_tile_candidates.items()):\n",
    "    for hidx1, hidx2 in hash_index_pairs:\n",
    "        h1 = score_to_hashes[s1][hidx1]\n",
    "        h2 = score_to_hashes[s2][hidx2]\n",
    "        for img1_id in list(hash_dict[tuple(h1)]):\n",
    "            t1 = np.where(np.all(sdcic.img_metrics[matches_metric][img1_id] == h1, axis=1))[0][0]\n",
    "            for img2_id in list(hash_dict[tuple(h2)]):\n",
    "                t2 = np.where(np.all(sdcic.img_metrics[matches_metric][img2_id] == h2, axis=1))[0][0]\n",
    "                total_count += 1\n",
    "                if img1_id == img2_id:\n",
    "                    continue\n",
    "                elif img2_id < img1_id:\n",
    "                    test_matches.add((img2_id, img1_id, pair_tag_lookup.get((t2, t1))))\n",
    "                    flip_count += 1\n",
    "                else:\n",
    "                    test_matches.add((img1_id, img2_id, pair_tag_lookup.get((t1, t2))))\n",
    "                match_count += 1\n",
    "                if match_count % 1_000_000 == 0:\n",
    "                    print(s1, s2, flip_count, len(test_matches), total_count)\n",
    "                \n",
    "print(s1, s2, flip_count, len(test_matches), total_count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Skip matches if any tile overlap is below the threshold.\n",
    "matches = set()\n",
    "for img1_id, img2_id, img1_overlap_tag in tqdm_notebook(test_matches):\n",
    "    bmh_scores = sdcic.overlap_scores_config[matches_metric]['func'](img1_id, img2_id, img1_overlap_tag)\n",
    "    if min(bmh_scores) < matches_threshold:\n",
    "        continue\n",
    "    matches.add((img1_id, img2_id, img1_overlap_tag))\n",
    "len(matches)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If available, calculate the 'avg' overlap score for each match.\n",
    "overlap_image_maps2 = {}\n",
    "for img1_id, img2_id, img1_overlap_tag in tqdm_notebook(matches):\n",
    "    if img1_id not in overlap_image_maps2:\n",
    "        overlap_image_maps2[img1_id] = {}\n",
    "    if img1_overlap_tag not in overlap_image_maps2[img1_id]:\n",
    "        overlap_image_maps2[img1_id][img1_overlap_tag] = {}\n",
    "    if img2_id not in overlap_image_maps2[img1_id][img1_overlap_tag]:\n",
    "        avg_scores = sdcic.overlap_scores_config['avg']['func'](img1_id, img2_id, img1_overlap_tag)\n",
    "        overlap_image_maps2[img1_id][img1_overlap_tag][img2_id] = avg_scores[:len(overlap_tag_maps[img1_overlap_tag])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check and verify.\n",
    "ctr = Counter()\n",
    "for img1_id, img1_matches in overlap_image_maps2.items():\n",
    "    for img1_overlap_tag, img2_ids in img1_matches.items():\n",
    "        if len(img2_ids) == 576:\n",
    "            print(img1_id)\n",
    "            for img2_id, score in sorted(img2_ids.items(), key=lambda x: np.max(x[1])):\n",
    "                print(img2_id, score)\n",
    "        ctr[len(img2_ids)] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(ctr.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Filter high scoring matches.\n",
    "new_matches = set()\n",
    "for img1_id, img1_matches in tqdm_notebook(overlap_image_maps2.items()):\n",
    "    for img1_overlap_tag, img2_ids in img1_matches.items():\n",
    "        ii = 0\n",
    "        for img2_id, score in sorted(img2_ids.items(), key=lambda x: np.max(x[1])):\n",
    "            if ii >= 3 and np.max(score) > 20000:\n",
    "                break\n",
    "            ii += 1\n",
    "            new_matches.add((img1_id, img2_id, img1_overlap_tag))\n",
    "len(new_matches)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matches_file = os.path.join(interim_data_dir, f'matches_{matches_metric}_{matches_threshold}_offset.csv')\n",
    "df = pd.DataFrame(sorted(new_matches))\n",
    "df.to_csv(matches_file, index=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Post processing extras (optional)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "overlap_tags_by_size = defaultdict(list)\n",
    "for overlap_tag_map, indexes in overlap_tag_maps.items():\n",
    "    overlap_tags_by_size[len(indexes)].append(overlap_tag_map)\n",
    "\n",
    "overlap_candidates_stats = Counter()\n",
    "for n_tiles, overlap_tags in sorted(overlap_tags_by_size.items(), reverse=True):\n",
    "    print(n_tiles, overlap_tags)\n",
    "    for (img1_id, img2_id, img1_overlap_tag) in matches:\n",
    "        if img1_overlap_tag not in overlap_tags:\n",
    "            continue\n",
    "        overlap_candidates_stats[(n_tiles, img1_overlap_tag)] += 1\n",
    "\n",
    "for key, cts in sorted(overlap_candidates_stats.items(), key=lambda x: x[1]):\n",
    "    print(key, f'{cts:>6}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# img1_id, img2_id, img1_overlap_tag = matches[1804]\n",
    "match_str = '0209f50e1.jpg c6b55566f.jpg 07'\n",
    "match_str = '0b8ce2b47.jpg ae1508781.jpg 18'\n",
    "match_str = '0d403a5dc.jpg fb91d24aa.jpg 38'\n",
    "match_str = '0d604c106.jpg 21d7ea9bf.jpg 38'\n",
    "match_str = '0dab350e9.jpg 8c7b3dbe6.jpg 08'\n",
    "match_str = '0e0e77e04.jpg ca09e27e2.jpg 18'\n",
    "match_str = '0e3c1baba.jpg 53331228d.jpg 08'\n",
    "match_str = '115ca0d9c.jpg 6cb57577b.jpg 08'\n",
    "match_str = '144b1d485.jpg 193b28b01.jpg 38'\n",
    "match_str = '1ae8df736.jpg 9a1c53871.jpg 08'\n",
    "match_str = '1ae8df736.jpg 9a1c53871.jpg 38'\n",
    "match_str = '1bdba4a27.jpg f90042ce7.jpg 08'\n",
    "# match_str = '1ec51371b.jpg ee94d427e.jpg 08'\n",
    "# match_str = '21d7ea9bf.jpg 89d46f4c4.jpg 08'\n",
    "img1_id, img2_id, img1_overlap_tag = match_str.split()\n",
    "img1_id, img2_id, img1_overlap_tag, max_hamm, avg_hamm = t_matches[25]\n",
    "# img1_overlap_tag = '28'\n",
    "img1 = cv2.cvtColor(sdcic.get_img(img1_id), cv2.COLOR_BGR2RGB)\n",
    "img2 = cv2.cvtColor(sdcic.get_img(img2_id), cv2.COLOR_BGR2RGB)\n",
    "GREEN = (76, 175, 80)\n",
    "bbox_thickness = 8\n",
    "bbox_color = GREEN\n",
    "draw_overlap_bbox(img1, img1_overlap_tag, bbox_thickness, bbox_color)\n",
    "draw_overlap_bbox(img2, overlap_tag_pairs[img1_overlap_tag], bbox_thickness, bbox_color)\n",
    "\n",
    "fig, ax = plt.subplots(1, 2, figsize = (16, 16))\n",
    "ax[0].imshow(img1)\n",
    "ax[0].set_title(f\"{img1_id}  max: {max_hamm}\")\n",
    "ax[0].set_xticks(ticks)\n",
    "ax[0].set_yticks(ticks)\n",
    "ax[1].imshow(img2)\n",
    "ax[1].set_title(f\"{img2_id}  avg: {avg_hamm}\")\n",
    "ax[1].set_xticks(ticks)\n",
    "ax[1].set_yticks(ticks)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matches_file8 = os.path.join(interim_data_dir, 'matches_bmh96_0.8.csv')\n",
    "df = pd.read_csv(matches_file8, dtype=str)\n",
    "matches8 = df.to_dict('split')['data']\n",
    "matches8_list = []\n",
    "for match in matches8:\n",
    "    matches8_list.append(tuple(match))\n",
    "len(matches8_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t_matches = []\n",
    "for img1_id, img2_id, img1_overlap_tag in sorted(matches8_list):\n",
    "    if img1_id == '115ca0d9c.jpg':\n",
    "        print(img1_id, img2_id, img1_overlap_tag, sdcic.get_bmh_scores(img1_id, img2_id, img1_overlap_tag))\n",
    "    if (img1_id, img2_id, img1_overlap_tag) not in matches:\n",
    "        scores = sdcic.get_bmh_scores(img1_id, img2_id, img1_overlap_tag)\n",
    "        if len(overlap_tag_maps[img1_overlap_tag]) <= 4:\n",
    "            continue\n",
    "        if np.max(scores) < 1:\n",
    "            img1_overlap_map = overlap_tag_maps[img1_overlap_tag]\n",
    "            img2_overlap_map = overlap_tag_maps[overlap_tag_pairs[img1_overlap_tag]]\n",
    "            print('')\n",
    "            hamm_total = 0\n",
    "            max_hamm = 0\n",
    "            for idx1, idx2 in zip(img1_overlap_map, img2_overlap_map):\n",
    "                h1 = sdcic.img_metrics['bmh96'][img1_id][idx1]\n",
    "                h2 = sdcic.img_metrics['bmh96'][img2_id][idx2]\n",
    "                b1 = np.unpackbits(h1)\n",
    "                b2 = np.unpackbits(h2)\n",
    "                hamm = np.sum(b1 ^ b2, dtype=np.int)\n",
    "                max_hamm = hamm if hamm > max_hamm else max_hamm\n",
    "                hamm_total += hamm\n",
    "                avg_hamm = hamm_total // len(img1_overlap_map)\n",
    "                print(img1_id, img2_id, img1_overlap_tag, idx1, idx2, f\"{hamm:>3} {avg_hamm:>3}\")\n",
    "            t_matches.append((img1_id, img2_id, img1_overlap_tag, max_hamm, avg_hamm))\n",
    "#             break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "matches_file9 = os.path.join(interim_data_dir, 'matches_bmh96_0.9.csv')\n",
    "df = pd.read_csv(matches_file9, dtype=str)\n",
    "matches9 = df.to_dict('split')['data']\n",
    "matches9_list = []\n",
    "for match in matches9:\n",
    "    matches9_list.append(tuple(match))\n",
    "len(matches9_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eqsum_cts = 0\n",
    "for img1_id, img2_id, img1_overlap_tag in sorted(matches9_list):\n",
    "    if (img1_id, img2_id, img1_overlap_tag) not in matches:\n",
    "        scores = sdcic.get_bmh_scores(img1_id, img2_id, img1_overlap_tag)\n",
    "        if len(overlap_tag_maps[img1_overlap_tag]) <= 4:\n",
    "            continue\n",
    "        if np.max(scores) < 1:\n",
    "            img1_overlap_map = overlap_tag_maps[img1_overlap_tag]\n",
    "            img2_overlap_map = overlap_tag_maps[overlap_tag_pairs[img1_overlap_tag]]\n",
    "            print('')\n",
    "            hamm_total = 0\n",
    "            for idx1, idx2 in zip(img1_overlap_map, img2_overlap_map):\n",
    "                h1 = sdcic.img_metrics['bmh96'][img1_id][idx1]\n",
    "                h2 = sdcic.img_metrics['bmh96'][img2_id][idx2]\n",
    "                b1 = np.unpackbits(h1)\n",
    "                b2 = np.unpackbits(h2)\n",
    "                m1 = sdcic.img_metrics['md5'][img1_id][idx1]\n",
    "                m2 = sdcic.img_metrics['md5'][img2_id][idx2]\n",
    "                hamm = np.sum(b1 ^ b2, dtype=np.int)\n",
    "                hamm_total += hamm\n",
    "                print(img1_id, img2_id, img1_overlap_tag, idx1, idx2, f\"{hamm:>3} {hamm_total//len(img1_overlap_map):>3}\", m1, m2)\n",
    "#             break"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}