image matching algorithms

[Shane Geiger]

Daniel Fetchinson wrote:
>>> There are a number of free tools for image matching but it's not very
>>> easy to decipher the actual algorithm from the code that includes db
>>> management, GUI, etc, etc. I have my own image database and GUI so all
>>> I need is the actual algorithm preferably in pseudo code and not in
>>> the form of a research paper (from which I also found a lot but since
>>> I'm not that much interested in the actual science of image
>>> recognition this seems like an over kill).
>>>       
>> I'd recommend SIFT. There's quite a bit of information on SIFT. In most
>> cases, they don't cover the background science too much, but are still
>> heavy on the math. Pseudo code is hard to come by since it will take
>> many lines of pseudo code just to express one concise mathematical
>> equation. There are however many links to implementations in various
>> languages on the Wikipedia page.
>>
>> http://en.wikipedia.org/wiki/Scale-invariant_feature_transform
>>
>> I have had good experiences with SIFT for feature extraction from images
>> (I have used it for panorama stitching and robot mapping). It's
>> insensitive to scale and rotation. Note that it is a patented algorithm
>> and this may (or may not) pose a problem for you.
>>     
>
> Thanks for the info! SIFT really looks like a heavy weight solution,
> but do you think the whole  concept can be simplified if all I needed
> was: given a photo, find similar ones? I mean SIFT first detects
> objects on the image and find similarities, but I don't need the
> detection part at all, all I care about is similarity for the whole
> photo. I surely don't understand the big picture fully but just have
> the general feeling that SIFT and other expert tools are an overkill
> for me and a simplified version would be just as good with a much more
> easily comprehensible core algorithm.
>
> Or am I being too optimistic and there is no way out of going into the details?
>   


Using the histogram of the picture may be good enough for your
application.  Here's something I put together for comparing images (for
purposes of detecting motion) taken by the built-in web cam in my
Macbook Pro.  This might be good enough if you play with the threshold.


"""
I'm writing a simple little app for doing motion detection with data
output from wacaw, a package for MacOSX.  You could easily modify this
script to get data output from some other source.

cd /Applications ; for i in `jot 1024`; do /Applications/wacaw --png
picture-${i} && sleep 3 ; done; open *.png
cd /Applications; open picture-*

"""

# cd /Applications ; for i in `jot 1024`; do /Applications/wacaw --png
picture-${i} && sleep 3 ; done; open *.png


# SOURCE:
http://gumuz.looze.net/wordpress/index.php/archives/2005/06/06/python-webcam-fun-motion-detection/

import os
from time import sleep
import tempfile

import Image

# Sun Mar 18 16:40:51 CDT 2007
def diff_image(img1, img2, pix_threshold=50, img_threshold=4):
    """Compare 2 images to detect possible motion
    You might want to choose the img_threshold amount based on the
conditions.
    """
    img1 = Image.open(img1)
    img2 = Image.open(img2)
    if not img1 or not img2: return False
    img1 = img1.getdata()
    img2 = img2.getdata()
    pixel_count = len(img1)
    pixdiff = 0
    for i in range(pixel_count):
        #if abs(sum(img1[i]) - sum(img2[i])) > pix_threshold:
    diffval = abs(sum(img1[i]) - sum(img2[i]))
    #print "Pixel diffval:",diffval
        if diffval > pix_threshold:
            pixdiff += 1
    diffperc = pixdiff / (pixel_count/100.0)
    print "Photo diff percentage:",diffperc
    if diffperc > img_threshold:
        # motion detected
        return True
    else:
        return False

photos = []  # consider automatically serializing this data

import commands


"""
def analyze_thresholds(list_of_photos):
    last = list_of_photos[0]
    for photo in list_of_photos[1:]:
    diff_image(last, photo)
    last = photo
"""



def detect():
    number = 0
    while True:
        number += 1
        sleep(3)
        current = 'photo-'+str(number)
        #tmp = tempfile.mktemp()
        print commands.getoutput('/Applications/wacaw --png ' + current
)      # ' + tmp +'.png')

        # Here's the actual name of the file wacaw created:
        current = '/Applications/'+current+'.png'
        photos.append( current )
        if len(photos) < 2:  # pad the list for the first time
            photos.append( current )

        if diff_image(photos[-1],photos[-2], pix_threshold=50,
img_threshold=5):
            print "motion detected"
        else:
            print "motion NOT detected"



detect()

#import glob
#analyze_thresholds(glob.glob('/Applications/photo-*')

 




-- 
Shane Geiger
IT Director
National Council on Economic Education
sgeiger at ncee.net  |  402-438-8958  |  http://www.ncee.net

Leading the Campaign for Economic and Financial Literacy