{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Google Landmark Recognition 2020","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"This notebook requires the dataset of `delg-saved-models` which contains the pretrained models of DELG. Please add this dataset to this notebook on Kaggle before running this notebook.","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"## 1. Import Modules","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"import time\nimport copy\nimport csv\nimport operator\nimport os\nimport pathlib\nimport shutil  # for file operation\n\nimport numpy as np\nimport PIL\nimport pydegensac  # RANSAC in Python\nfrom scipy import spatial\nimport tensorflow as tf\nimport warnings\n\n\n# warnings.simplefilter(\"ignore\")","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 2. Constant Definition","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"# Dataset parameters:\nINPUT_DIR = '../input/'\nDATASET_DIR = INPUT_DIR + 'landmark-recognition-2020/'\nTEST_DIR = DATASET_DIR + 'test/'\nTRAIN_DIR = DATASET_DIR + 'train/'\nTRAIN_LABELMAP_PATH = DATASET_DIR + 'train.csv'\n\n# DEBUGGING PARAMS\nDEBUG = False  # only use small portion (DEBUG_SIZE) of data to get result quickly\nDEBUG_SIZE = 500\nPUBLIC_TRAIN_SIZE = 1580470  # Used to detect if in session or re-run\nMAX_NUM_EMBEDDINGS = -1  # Set to > 1 to subsample dataset while debugging\n\n# Retrieval & re-ranking parameters\nNUM_TO_RERANK = 5\nTOP_K = 3  # Number of retrieved images used to make prediction for a test image\n\n# RANSAC parameters\nMAX_INLIER_SCORE = 30\nMAX_REPROJECTION_ERROR = 6.0\nMAX_RANSAC_ITERATIONS = 5_000  # 5_000_000\nHOMOGRAPHY_CONFIDENCE = 0.96  # 0.99\n\n# DELG model\nDELG_MODEL_DIR = '../input/delg-saved-models/local_and_global'\nDELG_IMAGE_SCALES = tf.convert_to_tensor([0.70710677, 1.0, 1.4142135])\nDELG_SCORE_THRESHOLD = tf.constant(175.)\nDELG_INPUT_TENSOR_NAMES = [\n    'input_image:0', 'input_scales:0', 'input_abs_thres:0'\n]\n\n# Global feature extraction\nNUM_EMBEDDING_DIMENSIONS = 2048\n\n# Local feature extraction\nLOCAL_FEATURE_NUM = tf.constant(1000)\n\n# log frequency\nLOG_FREQ = 500\n\n# quick submit\nQUICK_SUBMIT = True","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 3. Preparatory Work","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"The training set is available in the `train/` folder, with corresponding landmark labels in `train.csv`. The test set images are listed in the `test/` folder.\n\nEach image has a unique hex id. Since there are a large number of images, each image is placed within three subfolders according to the first three characters of the image id (i.e. image `abcdef.jpg` is placed in `a/b/c/abcdef.jpg`).","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"def image_path(subset, image_id):\n    \"\"\"Get image path by image id.\"\"\"\n    return os.path.join(DATASET_DIR, subset, image_id[0], image_id[1], image_id[2],\n                        '{}.jpg'.format(image_id))\n\n\ndef load_image(image_path):\n    \"\"\"Convert image to tensor.\"\"\"\n    return tf.convert_to_tensor(\n            np.array(PIL.Image.open(image_path).convert('RGB')))\n\n\n# load label map\nlabelmap = None\nwith open(TRAIN_LABELMAP_PATH, mode='r') as csv_file:\n    csv_reader = csv.DictReader(csv_file)\n    labelmap = {row['id']: row['landmark_id'] for row in csv_reader}","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 4. Feature Extraction\n-- Using DELG TensorFlow Pre-trained Model for global and local feature extraction.\n\nImage retrieval is the problem of searching an image database for items that are similar to a query image. To address this task, two main types of image representations have been studied: global and local image features[1].\n\n* A global feature, also commonly referred to as “global descriptor” or “embedding”, summarizes the contents of an image, often leading to a compact representation; information about spatial arrangement of visual elements is lost.\n\n* Local features, on the other hand, comprise descriptors and geometry information (keypoints) about specific image regions; they are especially useful to match images depicting rigid objects.\n\n* Generally speaking, global features are better at recall, while local features are better at precision.","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"delg_model = tf.saved_model.load(DELG_MODEL_DIR)\n\n# Global feature extraction function\nglobal_feature_fn = delg_model.prune(DELG_INPUT_TENSOR_NAMES,\n    ['global_descriptors:0'])\n\n# Local feature extraction function\nlocal_feature_fn = delg_model.prune(\n    DELG_INPUT_TENSOR_NAMES + ['input_max_feature_num:0'],\n    ['boxes:0', 'features:0'])","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"def global_features(image_root_dir):\n    \"\"\"Extracts embeddings for all the images in given `image_root_dir`.\"\"\"\n    image_paths = [x for x in pathlib.Path(image_root_dir).rglob('*.jpg')]\n    if DEBUG:\n        image_paths = image_paths[:DEBUG_SIZE]\n\n    num_embeddings = len(image_paths)\n    if MAX_NUM_EMBEDDINGS > 0:\n        num_embeddings = min(MAX_NUM_EMBEDDINGS, num_embeddings)\n\n    ids = num_embeddings * [None]\n    embeddings = np.empty((num_embeddings, NUM_EMBEDDING_DIMENSIONS))\n\n    start = time.time()\n    total = 0  # total time used\n    for i, image_path in enumerate(image_paths):\n        if i >= num_embeddings:\n            break\n\n        ids[i] = image_path.name.split('.')[0]\n        image_tensor = load_image(image_path)\n        features = global_feature_fn(image_tensor,\n            DELG_IMAGE_SCALES, DELG_SCORE_THRESHOLD)\n\n        embeddings[i, :] = tf.nn.l2_normalize(\n                tf.reduce_sum(features[0], axis=0, name='sum_pooling'),\n                axis=0, name='final_l2_normalization').numpy()\n\n        # logging\n        x = i + 1\n        if x % LOG_FREQ == 0 or x == num_embeddings:\n            end = time.time()\n            used = end - start\n            total += used\n            avg = total / x  # average time used per step\n            remain = avg * (num_embeddings-x) / 60.0\n            start = end\n            print('[{}/{}], [{:.2f}s/{:.2f}mins] used, {:.2f}mins remain'.format(x,\n                num_embeddings, used, total/60, remain))\n\n    print('Global features extracted, {:.2f}mins used'.format(total/60))\n    return ids, embeddings\n\n\ndef local_features(image_path):\n    \"\"\"Extracts local features for the given `image_path`.\"\"\"\n    image_tensor = load_image(image_path)\n\n    features = local_feature_fn(image_tensor, DELG_IMAGE_SCALES,\n                                DELG_SCORE_THRESHOLD, LOCAL_FEATURE_NUM)\n\n    # Shape: (N, 2)\n    keypoints = tf.divide(\n            tf.add(tf.gather(features[0], [0, 1], axis=1),\n                   tf.gather(features[0], [2, 3], axis=1)), 2.0).numpy()\n\n    # Shape: (N, 128)\n    descriptors = tf.nn.l2_normalize(\n        features[1], axis=1, name='l2_normalization').numpy()\n\n    return keypoints, descriptors","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 5. Keypoints Matching","execution_count":null},{"metadata":{},"cell_type":"markdown","source":"Using KDTree[2] to speed up the searching of nearst keypoint, cKDTree is the C implementation of KDTree. After that, we need to compute the number of RANSAC[3] (pydegensac is an Python wrapper of RANSAC for homography and fundamental matrix estimation from sparse correspondences.) inliers by the function `findHomography`[4].\n\nSince we only need to compute the number of inliers, the homography matrix `H` is unimportant, what we need is the `mask` array, a bool array, to compute the number of inliers.","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"def match_keypoints(test_keypoints, test_descriptors, train_keypoints,\n                    train_descriptors, max_distance=0.9):\n    \"\"\"Finds matches from `test_descriptors` to KD-tree of `train_descriptors`.\"\"\"\n    train_descriptor_tree = spatial.cKDTree(train_descriptors)\n    _, matches = train_descriptor_tree.query(\n            test_descriptors, distance_upper_bound=max_distance)\n\n    test_kp_count = test_keypoints.shape[0]\n    train_kp_count = train_keypoints.shape[0]\n\n    test_matching_keypoints = np.array([\n            test_keypoints[i,]\n            for i in range(test_kp_count)\n            if matches[i] != train_kp_count\n    ])\n\n    train_matching_keypoints = np.array([\n            train_keypoints[matches[i],]\n            for i in range(test_kp_count)\n            if matches[i] != train_kp_count\n    ])\n\n    return test_matching_keypoints, train_matching_keypoints\n\n\ndef inliers_num(test_keypoints, test_descriptors,\n                train_keypoints, train_descriptors):\n    \"\"\"Returns the number of RANSAC inliers.\"\"\"\n\n    test_match_kp, train_match_kp = match_keypoints(\n        test_keypoints, test_descriptors,\n        train_keypoints, train_descriptors)\n\n    if test_match_kp.shape[0] <= 4:\n        # Min keypoints supported by `pydegensac.findHomography()`\n        # RANSAC needs at least 5 keypoints\n        return 0\n\n    try:\n        # 计算多个点对之间的最优单映射变换矩阵H\n        H, mask = pydegensac.findHomography(test_match_kp, train_match_kp,\n                                            MAX_REPROJECTION_ERROR,\n                                            HOMOGRAPHY_CONFIDENCE,\n                                            MAX_RANSAC_ITERATIONS)\n    except np.linalg.LinAlgError:  # When det(H)=0, can't invert matrix.\n        return 0\n\n    return int(copy.deepcopy(mask).astype(np.float32).sum())\n\n\ndef score(num_inliers, global_score):\n    \"\"\"Compute total score.\"\"\"\n    local_score = min(num_inliers, MAX_INLIER_SCORE) / MAX_INLIER_SCORE\n    return local_score + global_score\n\n\ndef rescore(test_image_id, labels_scores):\n    \"\"\"Returns rescored and sorted training images by local feature extraction.\"\"\"\n\n    test_image_path = image_path('test', test_image_id)\n    test_keypoints, test_descriptors = local_features(test_image_path)\n\n    for i in range(len(labels_scores)):\n        train_image_id, label, global_score = labels_scores[i]\n\n        train_image_path = image_path('train', train_image_id)\n        train_keypoints, train_descriptors = local_features(\n            train_image_path)\n\n        num_inliers = inliers_num(test_keypoints, test_descriptors,\n                                  train_keypoints, train_descriptors)\n        s = score(num_inliers, global_score)\n        labels_scores[i] = (train_image_id, label, s)\n\n    labels_scores.sort(key=lambda x: x[2], reverse=True)\n\n    return labels_scores","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 6. Prediction\nFirst, ranks all training images by embedding similarity to each test image -- global features. Then, performs `geometric-verification` and re-ranking on the `NUM_TO_RERANK` most similar training images -- local features.\n\nFor a given test image, each class's score is the sum of the scores of re-ranked training images, and the predicted class is the one with the highest aggregate score.","execution_count":null},{"metadata":{"_cell_guid":"08a86f3f-f92c-44fa-ac01-3516c6713fda","_uuid":"71ef7fef-1c42-4c6e-9e03-5408ef6a7401","trusted":false},"cell_type":"code","source":"def predict_map(test_ids, labels_scores):\n    \"\"\"Makes dict from test ids and ranked training ids, labels, scores.\"\"\"\n    prediction_map = dict()\n\n    for test_index, test_id in enumerate(test_ids):\n        aggregate_scores = {}\n        for _, label, score in labels_scores[test_index][:TOP_K]:\n            if label not in aggregate_scores:\n                aggregate_scores[label] = 0\n            aggregate_scores[label] += score\n\n        label, score = max(aggregate_scores.items(), key=operator.itemgetter(1))\n\n        prediction_map[test_id] = {'score': score, 'class': label}\n\n    return prediction_map\n\n\ndef predict(test_ids, test_embeddings, train_ids, train_embeddings):\n    \"\"\"Gets predictions using embedding similarity and local feature reranking.\"\"\"\n    labels_scores = [None] * test_embeddings.shape[0]\n    \n    # using global features\n    for test_index in range(test_embeddings.shape[0]):\n        distances = spatial.distance.cdist(\n                test_embeddings[np.newaxis, test_index, :], train_embeddings,\n                'cosine')[0]\n        \n        # get NUM_TO_RERANK entries by distance to re-rank\n        partition = np.argpartition(distances, NUM_TO_RERANK)[:NUM_TO_RERANK]\n\n        # sort tuple (train_id, distance) by distance\n        nearest = sorted([(train_ids[p], distances[p]) for p in partition],\n                         key=lambda x: x[1])\n\n        labels_scores[test_index] = [\n                (train_id, labelmap[train_id], 1. - cosine_distance)\n                for train_id, cosine_distance in nearest\n        ]\n        \n    # using local features to rescore\n    pre_verify_preds = predict_map(test_ids, labels_scores)\n\n    for test_index, test_id in enumerate(test_ids):\n        labels_scores[test_index] = rescore(\n            test_id, labels_scores[test_index])\n\n    post_verify_preds = predict_map(\n            test_ids, labels_scores)\n\n    return post_verify_preds\n\n\ndef save(predictions):\n    \"\"\"Save prediction result to submission.csv.\"\"\"\n    with open('submission.csv', 'w') as f:\n        csv_writer = csv.DictWriter(f, fieldnames=['id', 'landmarks'])\n        csv_writer.writeheader()\n        for image_id, prediction in predictions.items():\n            label = prediction['class']\n            score = prediction['score']\n            csv_writer.writerow({'id': image_id, 'landmarks': '{} {:.8f}'.format(label, score)})","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 7. Run\nCall the functions above to generate `submission.csv`. When `QUICK_SUBMIT` is turn on and the number of training images indicates that the kernel is being run against the public dataset, simply copies `sample_submission.csv` to allow for quickly starting re-runs on the private dataset.\n\nWhen it re-run against the private dataset, makes predictions via retrieval.","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"def run():\n    start = time.time()\n    training_size = len(labelmap.keys())\n    print('Found {} training images.'.format(training_size))\n\n    if QUICK_SUBMIT and training_size == PUBLIC_TRAIN_SIZE:\n        # dummy submission\n        print('Copying sample submission...')\n        shutil.copyfile(DATASET_DIR + 'sample_submission.csv', 'submission.csv')\n        return\n    \n    print('Extracting global features on testing set...')\n    test_ids, test_embeddings = global_features(TEST_DIR)\n    \n    print('\\nExtracting global features on training set...')\n    train_ids, train_embeddings = global_features(TRAIN_DIR)\n    \n    print('\\nPredicting...')\n    preds = predict(test_ids, test_embeddings,\n                    train_ids, train_embeddings)\n    \n    print('Saving result to csv...')\n    save(preds)\n    \n    end = time.time()\n    print('All done!({:.2f}mins used)'.format((end-start)/60))","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"run()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 8. Reference\n[1] \"Unifying Deep Local and Global Features for Image Search\", B. Cao*, A. Araujo* and J. Sim, Proc. ECCV'20\n\n[2] https://blog.csdn.net/qq_38250162/article/details/89917671\n\n[3] http://huitaofuwu.com/2020/07/19/DELG%E8%AE%BA%E6%96%87%E7%B2%BE%E5%BA%A6%E7%AC%94%E8%AE%B0/\n\n[4] https://blog.csdn.net/fengyeer20120/article/details/87798638","execution_count":null},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}