{"cells": [{"cell_type": "markdown", "outputs": [], "source": "# Finding Leaked Images\n\nThis kernel aims to find images \"leaked\" from the train set into test set (because sometimes md5sum isn't enough!).  \nWe will use RGB histogram as feature vectors then compute L2 distance between test vectors and train vectors to see if we get a match.   \n**Note:** An even better approach is to use an ImageNet trained CNN (VGG16, ResNet50, etc.) with FC layers removed to get bottleneck features rather than histogram.  \n**EDIT:** Rather than leaked images I should say leaked \"patients\" as the images are not identical but from the same patient.\n", "execution_count": null, "metadata": {"_execution_state": "idle", "collapsed": false, "_uuid": "fa17153b497ff2af0d2372ba8ce4889bf1a484a0"}}, {"cell_type": "code", "outputs": [], "source": "from __future__ import print_function\nimport os\nimport glob\nimport cv2\nfrom matplotlib import pyplot as plt\nimport numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n\nfrom subprocess import check_output\n# print some info about server\nprint(check_output([\"ls\", \"../input\"]).decode(\"utf8\"))\nprint(check_output([\"df\", \"-h\"]).decode(\"utf8\"))\n\ntest_root = '../input/test'\ntrain_root = '../input/train'\nadditional_train_root = '../input/additional'\n\ntest_paths = glob.glob(test_root + '/*.jpg')\n#train_paths = glob.glob(train_root + '/**/*.jpg') + glob.glob(additional_train_root + '/**/*.jpg')\ntrain_paths = glob.glob(additional_train_root + '/Type_2/*.jpg') # only use type 2 additional for this demo\n# list some files as sanity check\nprint (len(test_paths))\nprint (test_paths[:10])\nprint (len(train_paths))\nprint (train_paths[:10])", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "collapsed": false, "_uuid": "ec011f9f7f807e4a6ad967d510073a991759ddf2"}}, {"cell_type": "code", "outputs": [], "source": "def get_histogram_features(img):\n    \"\"\"\n    Get 1D feature vector of RGB histogram\n    \"\"\"\n    # here we get 12x12x12 histogram\n    hist = cv2.calcHist([img], [0, 1, 2], \n                        None, \n                        [12, 12, 12], \n                        [0, 256, 0, 256, 0, 256])\n    features = np.array(hist).astype(np.float32).flatten() # flatten to 1D\n    features /= 255. # normalize between 0.0 and 1.0\n    return features", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "_uuid": "d6d1ccb30cc6742042d366c3056c2cd4926c1c76"}}, {"cell_type": "code", "outputs": [], "source": "test_vectors = []\nprint('begin extracting histogram features from test images...')\nfor i, pth in enumerate(test_paths):\n    img = cv2.imread(pth)\n    features = get_histogram_features(img)\n    #print(features.shape)\n    test_vectors.append(features)\n    if i%50 == 0 or i == len(test_paths) - 1:\n        print ('{} of {} test vectors loaded'.format(i + 1, len(test_paths)))\ntest_vectors = np.array(test_vectors)\nprint ('done.')\nprint('test_vectors.shape={}'.format(test_vectors.shape))", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "collapsed": false, "_uuid": "f6194be5696aaff45c70adb95880f4b54493ec89"}}, {"cell_type": "code", "outputs": [], "source": "train_vectors = []\ntrim_to_amount = 1000 # only small chunk of images for brevity\ntrain_paths = train_paths[:trim_to_amount]\nprint('begin extracting histogram features from train images...')\nfor i, pth in enumerate(train_paths):\n    img = cv2.imread(pth)\n    if img is None or img.shape[0] == 0 or img.shape[1] == 0:\n        raise Exception('corrupt image {}'.format(pth)) # TODO: handle corrupt images\n    features = get_histogram_features(img)\n    #print(features.shape)\n    train_vectors.append(features)\n    if i%50 == 0 or i == len(train_paths) - 1:\n        print ('{} of {} train vectors loaded'.format(i + 1, len(train_paths)))\ntrain_vectors = np.array(train_vectors)\nprint ('done loading features.')\nprint('train_vectors.shape={}'.format(train_vectors.shape))", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "collapsed": false, "_uuid": "071c2059ae680134770fd7c39fec9282990437a3"}}, {"cell_type": "code", "outputs": [], "source": "from sklearn.neighbors import KDTree\ndef find_duplicates(min_match_dist=2200.0):\n    # load train vectors into KDTree\n    kd = KDTree(train_vectors, leaf_size=40, metric='euclidean')\n    # find K closest vectors to each test vector\n    k = 1\n    # compare test/train vectors to find duplicates\n    # Note: we could also find all distances and indices in one shot with kd.query(X=test_vectors)\n    print ('beginning KNN search...')\n    for i, test_vector in enumerate(test_vectors):\n        dists, indices = kd.query(X=test_vector.reshape(1, -1), \n                                  k=k, \n                                  return_distance=True)\n        dists = dists[0]\n        indices = indices[0]\n\n        skip = False\n        for j, ind in enumerate(indices):\n            distance = dists[j]\n            if distance > min_match_dist:\n                skip = True\n                continue\n            train_img_path = train_paths[ind]\n            train_img = cv2.imread(train_img_path)\n            train_img = cv2.resize(train_img, (256, 256))  # resize for display\n            train_filename = os.path.basename(train_img_path)\n            train_class_type = os.path.basename(os.path.dirname(train_img_path))\n            # write some useful text on each image (filename, distance, class type)\n            cv2.putText(train_img, train_filename, (0, 25), 1, 1.75, (0, 255, 0), 2)\n            cv2.putText(train_img, 'dist={}'.format(distance), (0, 50), 1, 1.75, (0, 255, 0), 2)\n            cv2.putText(train_img, train_class_type, (0, 75), 1, 1.75, (0, 255, 0), 2)\n            plt.subplot(1, k + 1, j + 2)  # plot result image\n            plt.title('{}'.format(j + 1))\n            plt.axis('off')\n            plt.imshow(cv2.cvtColor(train_img, cv2.COLOR_BGR2RGB))\n        if skip is not True:\n            test_img_path = test_paths[i]\n            test_img = cv2.imread(test_img_path)\n            test_img = cv2.resize(test_img, (256, 256))  # resize for display\n            plt.subplot(1, k + 1, 1)  # plot query image\n            plt.title('query image')\n            plt.axis('off')\n            test_filename = os.path.basename(test_img_path)\n            cv2.putText(test_img, test_filename, (0, 25), 1, 1.75, (0, 0, 255), 2)\n            plt.imshow(cv2.cvtColor(test_img, cv2.COLOR_BGR2RGB))\n            plt.show()\n    print('done.')", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "collapsed": false, "_uuid": "6adf8ea5154500eb4210a3fd3365c91671a5ff18"}}, {"cell_type": "code", "outputs": [], "source": "min_match_dist = 2200.0 # found experimentally, feel free to increase/decrease\nfind_duplicates(min_match_dist=min_match_dist)", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "collapsed": false, "_uuid": "209931346ed8eb4463f158c8b75ad739585f3489"}}, {"cell_type": "markdown", "outputs": [], "source": "#We have matches!\nWe can see by visual inspection that there are some (very) similar images in training set and test set.  \nRecall we only searched a subset of `additional/Type_2` folder.  \nYou will get many more matches if you search all images.  \n  \nThanks for reading, upvote if you like!  ", "execution_count": null, "metadata": {"_execution_state": "idle", "collapsed": false, "_uuid": "e66a106ddaef31425ed022101fc55ec3bf9cd7cb"}}, {"cell_type": "code", "outputs": [], "source": "", "execution_count": null, "metadata": {"_execution_state": "idle", "trusted": false, "collapsed": false, "_uuid": "237454069529a00d70325049ee7f80366b7b361c"}}], "nbformat_minor": 0, "metadata": {"language_info": {"mimetype": "text/x-python", "file_extension": ".py", "codemirror_mode": {"name": "ipython", "version": 3}, "name": "python", "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "version": "3.6.0"}, "kernelspec": {"language": "python", "name": "python3", "display_name": "Python 3"}}, "nbformat": 4}