<p>I need an algorithm that can determine whether two images are 'similar' and recognizes similar patterns of color, brightness, shape etc.. I might need some pointers as to what parameters the human brain uses to 'categorize' images. .. </p>

<p>I have looked at hausdorff based matching but that seems mainly for matching transformed objects and patterns of shape.</p>

[{'answer_id': 75902, 'author': 'Dark Shikari', 'author_id': 11206, 'author_profile': 'https://Stackoverflow.com/users/11206', 'pm_score': 1, 'selected': False, 'text': '<p>You could perform some sort of block-matching motion estimation between the two images and measure the overall sum of residuals and motion vector costs (much like one would do in a video encoder).  This would compensate for motion; for bonus points, do affine-transformation motion estimation (compensates for zooms and stretching and similar).  You could also do overlapped blocks or optical flow.</p>\n'}, {'answer_id': 75929, 'author': 'Alejandro Bologna', 'author_id': 9263, 'author_profile': 'https://Stackoverflow.com/users/9263', 'pm_score': 3, 'selected': False, 'text': '<p>You could use <a href="http://pdiff.sourceforge.net/" rel="noreferrer">Perceptual Image Diff</a></p>\n\n<p>It\'s a command line utility that compares two images using a perceptual metric. That is, it uses a computational model of the human visual system to determine if two images are visually different, so minor changes in pixels are ignored. Plus, it drastically reduces the number of false positives caused by differences in random number generation, OS or machine architecture differences.</p>\n'}, {'answer_id': 75931, 'author': 'Dima', 'author_id': 13313, 'author_profile': 'https://Stackoverflow.com/users/13313', 'pm_score': 1, 'selected': False, 'text': '<p>As a first pass, you can try using color histograms.  However, you really need to narrow down your problem domain.  Generic image matching is a very hard problem.  </p>\n'}, {'answer_id': 75940, 'author': 'Ben', 'author_id': 11522, 'author_profile': 'https://Stackoverflow.com/users/11522', 'pm_score': 2, 'selected': False, 'text': "<p>It's a difficult problem! It depends on how accurate you need to be, and it depends on what kind of images you are working with. You can use histograms to compare colours, but that obviously doesn't take into account the spatial distribution of those colours within the images (i.e. the shapes). Edge detection followed by some kind of segmentation (i.e. picking out the shapes) can provide a pattern for matching against another image. You can use coocurence matrices to compare textures, by considering the images as matrices of pixel values, and comparing those matrices. There are some good books out there on image matching and machine vision -- A search on Amazon will find some.</p>\n\n<p>Hope this helps!</p>\n"}, {'answer_id': 75990, 'author': 'neuroguy123', 'author_id': 12529, 'author_profile': 'https://Stackoverflow.com/users/12529', 'pm_score': 0, 'selected': False, 'text': '<p>There are some good answers in the other thread on this, but I wonder if something involving a spectral analysis would work?  I.e., break the image down to it\'s phase and amplitude information and compare those.  This may avoid some of the issues with cropping, transformation and intensity differences.  Anyway, that\'s just me speculating since this seems like an interesting problem.  If you searched <a href="http://scholar.google.com" rel="nofollow noreferrer">http://scholar.google.com</a> I\'m sure you could come up with several papers on this.</p>\n'}, {'answer_id': 76036, 'author': 'willasaywhat', 'author_id': 12234, 'author_profile': 'https://Stackoverflow.com/users/12234', 'pm_score': 2, 'selected': False, 'text': "<p>This sounds like a vision problem. You might want to look into Adaptive Boosting as well as the Burns Line Extraction algorithm. The concepts in these two should help with approaching this problem. Edge detection is an even simpler place to start if you're new to vision algorithms, as it explains the basics. </p>\n\n<p>As far as parameters for categorization:</p>\n\n<ul>\n<li>Color Palette &amp; Location (Gradient calculation, histogram of colors)</li>\n<li>Contained Shapes (Ada. Boosting/Training to detect shapes)</li>\n</ul>\n"}, {'answer_id': 83406, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 2, 'selected': False, 'text': "<p>Depending on how much accurate results you need, you can simply break the images in n x n pixels blocks and analyze them. If you get different results in the first block you can't stop processing, resulting in some performance improvements.</p>\n\n<p>For analyzing the squares you can for example get the sum of the color values.</p>\n"}, {'answer_id': 83463, 'author': 'petr k.', 'author_id': 15497, 'author_profile': 'https://Stackoverflow.com/users/15497', 'pm_score': 2, 'selected': False, 'text': '<p>Some image recognition software solutions are actually not purely algorithm-based, but make use of the <strong>neural network</strong> concept instead. Check out <a href="http://en.wikipedia.org/wiki/Artificial_neural_network" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Artificial_neural_network</a> and namely NeuronDotNet which also includes interesting samples: <a href="http://neurondotnet.freehostia.com/index.html" rel="nofollow noreferrer">http://neurondotnet.freehostia.com/index.html</a></p>\n'}, {'answer_id': 83486, 'author': 'freespace', 'author_id': 8297, 'author_profile': 'https://Stackoverflow.com/users/8297', 'pm_score': 7, 'selected': True, 'text': '<p>I have done something similar, by decomposing images into signatures using <a href="http://en.wikipedia.org/wiki/Wavelet" rel="nofollow noreferrer">wavelet transform</a>.</p>\n<p>My approach was to pick the most significant <em>n</em> coefficients from each transformed channel, and recording their location. This was done by sorting the list of (power,location) tuples according to abs(power). Similar images will share similarities in that they will have significant coefficients in the same places.</p>\n<p>I found it was best to transform in the image into YUV format, which effectively allows you weight similarity in shape (Y channel) and colour (UV channels).</p>\n<p>You can in find my implementation of the above in <a href="https://github.com/freespace/mactorii" rel="nofollow noreferrer">mactorii</a>, which unfortunately I haven\'t been working on as much as I should have :-)</p>\n<p>Another method, which some friends of mine have used with surprisingly good results, is to simply resize your image down to say, a 4x4 pixel and store that as your signature. How similar 2 images are can be scored by say, computing the <a href="http://en.wikipedia.org/wiki/Manhattan_distance" rel="nofollow noreferrer">Manhattan distance</a> between the 2 images, using corresponding pixels. I don\'t have the details of how they performed the resizing, so you may have to play with the various algorithms available for that task to find one which is suitable.</p>\n'}, {'answer_id': 85842, 'author': 'EPa', 'author_id': 15281, 'author_profile': 'https://Stackoverflow.com/users/15281', 'pm_score': 2, 'selected': False, 'text': '<p>There is related research using Kohonen neural networks/self organizing maps  </p>\n\n<p>Both more academic systems (Google for PicSOM ) or less academic<br>\n( <a href="http://www.generation5.org/content/2004/aiSomPic.asp" rel="nofollow noreferrer">http://www.generation5.org/content/2004/aiSomPic.asp</a> , (possibly not suitable\nfor all work enviroments)) presentations exist.</p>\n'}, {'answer_id': 88429, 'author': 'jilles de wit', 'author_id': 7531, 'author_profile': 'https://Stackoverflow.com/users/7531', 'pm_score': 4, 'selected': False, 'text': '<p>I\'ve used <a href="http://en.wikipedia.org/wiki/Scale-invariant_feature_transform" rel="noreferrer">SIFT</a> to re-detect te same object in different images. It is really powerfull but rather complex, and might be overkill. If the images are supposed to be pretty similar some simple parameters based on the difference between the two images can tell you quite a bit. Some pointers:</p>\n\n<ul>\n<li>Normalize the images i.e. make the average brightness of both images the same by calculating the average brightness of both and scaling the brightest down according to the ration (to avoid clipping at the highest level)) especially if you\'re more interested in shape than in colour.</li>\n<li>Sum of colour difference over normalized image per channel.</li>\n<li>find edges in the images and measure the distance betwee edge pixels in both images. (for shape)</li>\n<li>Divide the images in a set of discrete regions and compare the average colour of each region.</li>\n<li>Threshold the images at one (or a set of) level(s) and count the number of pixels where the resulting black/white images differ. </li>\n</ul>\n'}, {'answer_id': 774916, 'author': 'Alvis', 'author_id': 37500, 'author_profile': 'https://Stackoverflow.com/users/37500', 'pm_score': 6, 'selected': False, 'text': '<p><a href="http://www.phash.org/" rel="noreferrer">pHash</a> might interest you.</p>\n\n<blockquote>\n  <p>perceptual hash n. a fingerprint of an audio, video or image file that is mathematically based on the audio or visual content contained within. Unlike cryptographic hash functions which rely on the avalanche effect of small changes in input leading to drastic changes in the output, perceptual hashes are "close" to one another if the inputs are visually or auditorily similar.</p>\n</blockquote>\n'}, {'answer_id': 6226040, 'author': 'andi', 'author_id': 2250, 'author_profile': 'https://Stackoverflow.com/users/2250', 'pm_score': 2, 'selected': False, 'text': '<p>I found this article very helpful explaining how it works:</p>\n\n<p><a href="http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html" rel="nofollow">http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html</a></p>\n'}, {'answer_id': 7770104, 'author': 'chris', 'author_id': 995701, 'author_profile': 'https://Stackoverflow.com/users/995701', 'pm_score': 2, 'selected': False, 'text': '<p>Calculating the sum of the squares of the differences of the pixel colour values of a drastically scaled-down version (eg: 6x6 pixels) works nicely.  Identical images yield 0, similar images yield small numbers, different images yield big ones.  </p>\n\n<p>The other guys above\'s idea to break into YUV first sounds intriguing - while my idea works great, I want my images to be calculated as "different" so that it yields a correct result - even from the perspective of a colourblind observer.</p>\n'}, {'answer_id': 40079158, 'author': 'Vivek Srinivasan', 'author_id': 2625282, 'author_profile': 'https://Stackoverflow.com/users/2625282', 'pm_score': 1, 'selected': False, 'text': '<p>Apologies for joining late in the discussion.</p>\n\n<p>We can even use ORB methodology to detect similar features points between two images.\nFollowing link gives direct implementation of ORB in python</p>\n\n<p><a href="http://scikit-image.org/docs/dev/auto_examples/plot_orb.html" rel="nofollow">http://scikit-image.org/docs/dev/auto_examples/plot_orb.html</a></p>\n\n<p>Even openCV has got direct implementation of ORB. If you more info follow the research article given below.</p>\n\n<p><a href="https://www.researchgate.net/publication/292157133_Image_Matching_Using_SIFT_SURF_BRIEF_and_ORB_Performance_Comparison_for_Distorted_Images" rel="nofollow">https://www.researchgate.net/publication/292157133_Image_Matching_Using_SIFT_SURF_BRIEF_and_ORB_Performance_Comparison_for_Distorted_Images</a></p>\n'}, {'answer_id': 49534462, 'author': 'duhaime', 'author_id': 1727392, 'author_profile': 'https://Stackoverflow.com/users/1727392', 'pm_score': 3, 'selected': False, 'text': '<p>My lab needed to solve this problem as well, and we used Tensorflow. Here\'s a <a href="https://github.com/YaleDHLab/pix-plot" rel="noreferrer">full app</a> implementation for visualizing image similarity.</p>\n\n<p>For a tutorial on vectorizing images for similarity computation, check out <a href="http://douglasduhaime.com/posts/identifying-similar-images-with-tensorflow.html" rel="noreferrer">this page</a>. Here\'s the Python (again, see the post for full workflow):</p>\n\n<pre><code>from __future__ import absolute_import, division, print_function\n\n"""\n\nThis is a modification of the classify_images.py\nscript in Tensorflow. The original script produces\nstring labels for input images (e.g. you input a picture\nof a cat and the script returns the string "cat"); this\nmodification reads in a directory of images and \ngenerates a vector representation of the image using\nthe penultimate layer of neural network weights.\n\nUsage: python classify_images.py "../image_dir/*.jpg"\n\n"""\n\n# Copyright 2015 The TensorFlow Authors. All Rights Reserved.\n#\n# Licensed under the Apache License, Version 2.0 (the "License");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#     http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an "AS IS" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n# ==============================================================================\n\n"""Simple image classification with Inception.\n\nRun image classification with Inception trained on ImageNet 2012 Challenge data\nset.\n\nThis program creates a graph from a saved GraphDef protocol buffer,\nand runs inference on an input JPEG image. It outputs human readable\nstrings of the top 5 predictions along with their probabilities.\n\nChange the --image_file argument to any jpg image to compute a\nclassification of that image.\n\nPlease see the tutorial and website for a detailed description of how\nto use this script to perform image recognition.\n\nhttps://tensorflow.org/tutorials/image_recognition/\n"""\n\nimport os.path\nimport re\nimport sys\nimport tarfile\nimport glob\nimport json\nimport psutil\nfrom collections import defaultdict\nimport numpy as np\nfrom six.moves import urllib\nimport tensorflow as tf\n\nFLAGS = tf.app.flags.FLAGS\n\n# classify_image_graph_def.pb:\n#   Binary representation of the GraphDef protocol buffer.\n# imagenet_synset_to_human_label_map.txt:\n#   Map from synset ID to a human readable string.\n# imagenet_2012_challenge_label_map_proto.pbtxt:\n#   Text representation of a protocol buffer mapping a label to synset ID.\ntf.app.flags.DEFINE_string(\n    \'model_dir\', \'/tmp/imagenet\',\n    """Path to classify_image_graph_def.pb, """\n    """imagenet_synset_to_human_label_map.txt, and """\n    """imagenet_2012_challenge_label_map_proto.pbtxt.""")\ntf.app.flags.DEFINE_string(\'image_file\', \'\',\n                           """Absolute path to image file.""")\ntf.app.flags.DEFINE_integer(\'num_top_predictions\', 5,\n                            """Display this many predictions.""")\n\n# pylint: disable=line-too-long\nDATA_URL = \'http://download.tensorflow.org/models/image/imagenet/inception-2015-12-05.tgz\'\n# pylint: enable=line-too-long\n\n\nclass NodeLookup(object):\n  """Converts integer node ID\'s to human readable labels."""\n\n  def __init__(self,\n               label_lookup_path=None,\n               uid_lookup_path=None):\n    if not label_lookup_path:\n      label_lookup_path = os.path.join(\n          FLAGS.model_dir, \'imagenet_2012_challenge_label_map_proto.pbtxt\')\n    if not uid_lookup_path:\n      uid_lookup_path = os.path.join(\n          FLAGS.model_dir, \'imagenet_synset_to_human_label_map.txt\')\n    self.node_lookup = self.load(label_lookup_path, uid_lookup_path)\n\n  def load(self, label_lookup_path, uid_lookup_path):\n    """Loads a human readable English name for each softmax node.\n\n    Args:\n      label_lookup_path: string UID to integer node ID.\n      uid_lookup_path: string UID to human-readable string.\n\n    Returns:\n      dict from integer node ID to human-readable string.\n    """\n    if not tf.gfile.Exists(uid_lookup_path):\n      tf.logging.fatal(\'File does not exist %s\', uid_lookup_path)\n    if not tf.gfile.Exists(label_lookup_path):\n      tf.logging.fatal(\'File does not exist %s\', label_lookup_path)\n\n    # Loads mapping from string UID to human-readable string\n    proto_as_ascii_lines = tf.gfile.GFile(uid_lookup_path).readlines()\n    uid_to_human = {}\n    p = re.compile(r\'[n\\d]*[ \\S,]*\')\n    for line in proto_as_ascii_lines:\n      parsed_items = p.findall(line)\n      uid = parsed_items[0]\n      human_string = parsed_items[2]\n      uid_to_human[uid] = human_string\n\n    # Loads mapping from string UID to integer node ID.\n    node_id_to_uid = {}\n    proto_as_ascii = tf.gfile.GFile(label_lookup_path).readlines()\n    for line in proto_as_ascii:\n      if line.startswith(\'  target_class:\'):\n        target_class = int(line.split(\': \')[1])\n      if line.startswith(\'  target_class_string:\'):\n        target_class_string = line.split(\': \')[1]\n        node_id_to_uid[target_class] = target_class_string[1:-2]\n\n    # Loads the final mapping of integer node ID to human-readable string\n    node_id_to_name = {}\n    for key, val in node_id_to_uid.items():\n      if val not in uid_to_human:\n        tf.logging.fatal(\'Failed to locate: %s\', val)\n      name = uid_to_human[val]\n      node_id_to_name[key] = name\n\n    return node_id_to_name\n\n  def id_to_string(self, node_id):\n    if node_id not in self.node_lookup:\n      return \'\'\n    return self.node_lookup[node_id]\n\n\ndef create_graph():\n  """Creates a graph from saved GraphDef file and returns a saver."""\n  # Creates graph from saved graph_def.pb.\n  with tf.gfile.FastGFile(os.path.join(\n      FLAGS.model_dir, \'classify_image_graph_def.pb\'), \'rb\') as f:\n    graph_def = tf.GraphDef()\n    graph_def.ParseFromString(f.read())\n    _ = tf.import_graph_def(graph_def, name=\'\')\n\n\ndef run_inference_on_images(image_list, output_dir):\n  """Runs inference on an image list.\n\n  Args:\n    image_list: a list of images.\n    output_dir: the directory in which image vectors will be saved\n\n  Returns:\n    image_to_labels: a dictionary with image file keys and predicted\n      text label values\n  """\n  image_to_labels = defaultdict(list)\n\n  create_graph()\n\n  with tf.Session() as sess:\n    # Some useful tensors:\n    # \'softmax:0\': A tensor containing the normalized prediction across\n    #   1000 labels.\n    # \'pool_3:0\': A tensor containing the next-to-last layer containing 2048\n    #   float description of the image.\n    # \'DecodeJpeg/contents:0\': A tensor containing a string providing JPEG\n    #   encoding of the image.\n    # Runs the softmax tensor by feeding the image_data as input to the graph.\n    softmax_tensor = sess.graph.get_tensor_by_name(\'softmax:0\')\n\n    for image_index, image in enumerate(image_list):\n      try:\n        print("parsing", image_index, image, "\\n")\n        if not tf.gfile.Exists(image):\n          tf.logging.fatal(\'File does not exist %s\', image)\n\n        with tf.gfile.FastGFile(image, \'rb\') as f:\n          image_data =  f.read()\n\n          predictions = sess.run(softmax_tensor,\n                          {\'DecodeJpeg/contents:0\': image_data})\n\n          predictions = np.squeeze(predictions)\n\n          ###\n          # Get penultimate layer weights\n          ###\n\n          feature_tensor = sess.graph.get_tensor_by_name(\'pool_3:0\')\n          feature_set = sess.run(feature_tensor,\n                          {\'DecodeJpeg/contents:0\': image_data})\n          feature_vector = np.squeeze(feature_set)        \n          outfile_name = os.path.basename(image) + ".npz"\n          out_path = os.path.join(output_dir, outfile_name)\n          np.savetxt(out_path, feature_vector, delimiter=\',\')\n\n          # Creates node ID --&gt; English string lookup.\n          node_lookup = NodeLookup()\n\n          top_k = predictions.argsort()[-FLAGS.num_top_predictions:][::-1]\n          for node_id in top_k:\n            human_string = node_lookup.id_to_string(node_id)\n            score = predictions[node_id]\n            print("results for", image)\n            print(\'%s (score = %.5f)\' % (human_string, score))\n            print("\\n")\n\n            image_to_labels[image].append(\n              {\n                "labels": human_string,\n                "score": str(score)\n              }\n            )\n\n        # close the open file handlers\n        proc = psutil.Process()\n        open_files = proc.open_files()\n\n        for open_file in open_files:\n          file_handler = getattr(open_file, "fd")\n          os.close(file_handler)\n      except:\n        print(\'could not process image index\',image_index,\'image\', image)\n\n  return image_to_labels\n\n\ndef maybe_download_and_extract():\n  """Download and extract model tar file."""\n  dest_directory = FLAGS.model_dir\n  if not os.path.exists(dest_directory):\n    os.makedirs(dest_directory)\n  filename = DATA_URL.split(\'/\')[-1]\n  filepath = os.path.join(dest_directory, filename)\n  if not os.path.exists(filepath):\n    def _progress(count, block_size, total_size):\n      sys.stdout.write(\'\\r&gt;&gt; Downloading %s %.1f%%\' % (\n          filename, float(count * block_size) / float(total_size) * 100.0))\n      sys.stdout.flush()\n    filepath, _ = urllib.request.urlretrieve(DATA_URL, filepath, _progress)\n    print()\n    statinfo = os.stat(filepath)\n    print(\'Succesfully downloaded\', filename, statinfo.st_size, \'bytes.\')\n  tarfile.open(filepath, \'r:gz\').extractall(dest_directory)\n\n\ndef main(_):\n  maybe_download_and_extract()\n  if len(sys.argv) &lt; 2:\n    print("please provide a glob path to one or more images, e.g.")\n    print("python classify_image_modified.py \'../cats/*.jpg\'")\n    sys.exit()\n\n  else:\n    output_dir = "image_vectors"\n    if not os.path.exists(output_dir):\n      os.makedirs(output_dir)\n\n    images = glob.glob(sys.argv[1])\n    image_to_labels = run_inference_on_images(images, output_dir)\n\n    with open("image_to_labels.json", "w") as img_to_labels_out:\n      json.dump(image_to_labels, img_to_labels_out)\n\n    print("all done")\nif __name__ == \'__main__\':\n  tf.app.run()\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/75891', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/13466/']