Commits

Lars Yencken committed d1c2f91

Replaced old comparePng extension with a newer Pyrex version.

Comments (0)

Files changed (8)

 tmp/
 *.swp
 www/localSettings.py
+pixel/comparePng.c
     print 'Using optimised targets'
     env.Replace(DEBUG=False, CXXFLAGS='-O3 -DNDEBUG ')
 
+pyxbuild = Builder(action='pyrexc -o $TARGET $SOURCE')
+env.Append(BUILDERS={'Pyrex': pyxbuild})
+
 # Configure the environment.
 env = checkLibraries(env)
 
 #
 #----------------------------------------------------------------------------#
 
-""" Scons SConstruct file for the comparePng extension.
-"""
+"""Build instructions for the comparePng extension."""
 
 #----------------------------------------------------------------------------#
 
 
 #----------------------------------------------------------------------------#
 
-if env['DEBUG']:
-    env.SharedLibrary('comparePng.cpp', CXXFLAGS='-funroll-loops ')
-#    env.SharedLibrary('diffPng.cpp', CXXFLAGS='-funroll-loops ')
-else:
-    env.SharedLibrary('comparePng.cpp')
-#    env.SharedLibrary('diffPng.cpp')
+comparePng = env.Pyrex('comparePng.c', 'comparePng.pyx')
+env.SharedLibrary('comparePng', comparePng)
 
 #----------------------------------------------------------------------------#

pixel/comparePng.cpp

-//--------------------------------------------------------------------------//
-// comparePng.hpp
-// Lars Yencken <lars.yencken@gmail.com>
-// vim: ts=4 sw=4 sts=4 et tw=78:
-// $Id: comparePng.cpp 233 2007-02-01 04:47:04Z lars $
-//
-//--------------------------------------------------------------------------//
-
-#include "comparePng.hpp"
-
-#include <math.h>
-#include <iostream>
-#include <fstream>
-#include <assert.h>
-
-using namespace std;
-
-//--------------------------------------------------------------------------//
-
-const int g_minOverlap = 5;
-
-//--------------------------------------------------------------------------//
-
-bool fileExists(string filename)
-{
-    ifstream iStream;
-    iStream.open(filename.c_str(), ifstream::in);
-    iStream.close();
-
-    if (iStream.fail())
-    {
-        return false;
-    }
-
-    return true;
-}
-
-//--------------------------------------------------------------------------//
-
-PngImage::PngImage(string filename)
-{
-    FILE* iStream = NULL;
-
-    // Check that the file is ok.
-    if (!fileExists(filename))
-    {
-        throw "File does not exist";
-    }
-
-    // Load in the image.
-    iStream = fopen(filename.c_str(), "rb");
-    gdImagePtr image = gdImageCreateFromPng(iStream);
-    fclose(iStream);
-
-    // Cache the image.
-    cacheImage(image, m_cachedImage);
-    extendImage(image, m_extendedImage);
-
-    // Determine the dimensions.
-    m_width = gdImageSX(image);
-    m_height = gdImageSY(image);
-
-    // Delete the original.
-    gdImageDestroy(image);
-}
-
-//--------------------------------------------------------------------------//
-
-void PngImage::cacheImage(const gdImagePtr& image, CachedImage& cache) const
-{
-    const int width = gdImageSX(image);
-    const int height = gdImageSY(image);
-
-    cache.clear();
-
-    for (int y = 0; y < height; ++y)
-    {
-        cache.push_back(vector<double>());
-
-        vector<double>& rowCache = cache[y];
-        for (int x = 0; x < width; ++x)
-        {
-            rowCache.push_back(greyPixel(image, x, y));
-        }
-    }
-
-    return;
-}
-
-//--------------------------------------------------------------------------//
-
-void PngImage::extendImage(const gdImagePtr& image, CachedImage& cache) const
-{
-    const int width = gdImageSX(image);
-    const int height = gdImageSY(image);
-
-    // The extended image is buffered by whitespace by (width - g_minOverlap)
-    // pixels on each side.
-    const int totalWidth = width + 2*(width - g_minOverlap);
-    const int totalHeight = height + 2*(height - g_minOverlap);
-
-    // The coordinates on the original image, where (0, 0) is the top
-    // left-hand corner of the image. 
-    int yReal = 0, xReal = 0;
-
-    const double white = 1.0;
-
-    cache.clear();
-
-    cache.reserve(totalHeight);
-    for (int y = 0; y < totalHeight; ++y)
-    {
-        // Allocate a new row vector.
-        cache.push_back(vector<double>());
-        vector<double>& rowCache = cache[y];
-        rowCache.reserve(totalWidth);
-
-        // Fill the values for this row.
-        yReal = y - (height - g_minOverlap);
-
-        if (yReal >= 0 && yReal < height)
-        {
-            // Part of this row is within bounds, part is out of bounds.
-            for (int x = 0; x < totalWidth; ++x)
-            {
-                xReal = x - (width - g_minOverlap);
-
-                if (xReal >= 0 && xReal < height)
-                {
-                    // X and Y are both within the bounds of the original
-                    // image, so copy the pixel.
-                    rowCache.push_back(greyPixel(image, xReal, yReal));
-                }
-                else
-                {
-                    // Out of bounds, consider this pixel white.
-                    rowCache.push_back(white);
-                }
-            }
-        }
-        else
-        {
-            // This entire row is out of bounds, consider it white.
-            for (int x = 0; x < totalWidth; ++x)
-            {
-                rowCache.push_back(white);
-            }
-        }
-    }
-
-    return;
-}
-
-//--------------------------------------------------------------------------//
-
-double PngImage::differenceAtOffset(const PngImage& rhsImage,
-        int xOffset, int yOffset) const
-{
-    const CachedImage& lhsCache = m_cachedImage;
-    const CachedImage& rhsCache = rhsImage.m_extendedImage;
-
-    // Determine the difference at the current offset. The left hand image is
-    // conceptually placed on top of the extended right hand side image. They
-    // are only compared directly in this space; outside it a penalty is
-    // applied for any black pixels.
-    double diff = 0.0;
-    int xLhs = 0;
-    int yLhs = 0;
-
-    // Convert an offset in coordinates where (0,0) aligns normally to 
-    // coordinates where (alpha, alpha) aligns normally, where alpha > 0.
-    const int xOffsetReal = xOffset + (m_width - g_minOverlap);
-    const int yOffsetReal = yOffset + (m_height - g_minOverlap);
-
-    const int xSizeRhs = m_width + 2*(m_width - g_minOverlap);
-    const int ySizeRhs = m_height + 2*(m_height - g_minOverlap);
-
-    for (int yRhs = 0; yRhs < ySizeRhs; ++yRhs)
-    {
-        yLhs = yRhs - yOffsetReal;
-
-        for (int xRhs = 0; xRhs < xSizeRhs; ++xRhs)
-        {
-            xLhs = xRhs - xOffsetReal;
-            if (boundsCheck(xLhs, yLhs))
-            {
-                // Within bounds, so compare the actual pixels.
-                diff += fabs(lhsCache[yLhs][xLhs] - rhsCache[yRhs][xRhs]);
-            }
-            else
-            {
-                // Outside bounds, so add penalties for black pixels. Note
-                // that the left side is always counted entirely, so we don't
-                // need a black pixel penalty for it.
-                diff += fabs(rhsCache[yRhs][xRhs] - 1.0);
-            }
-        }
-    }
-
-    return diff / (float) (m_height * m_width);
-}
-
-//--------------------------------------------------------------------------//
-
-double PngImage::invariantDifference(const PngImage& rhsImage) const
-{
-    double bestDifference = 1.0; // The worst case distance.
-#ifndef NDEBUG
-    cout << "Debugging invariant distance..." << endl;
-    int bestX = 0;
-    int bestY = 0;
-#endif
-
-    // We consider x and y offsets within range [minOffset, maxOffset)
-    const int maxOffset = m_width - g_minOverlap;
-    const int minOffset = -maxOffset;
-
-    assert(maxOffset > minOffset);
-    // Conceptually, we place the smaller left image on top of the extended
-    // right image, and slide it across, comparing at each offset. 
-    double diff = 0.0;
-    for (int yOffset = minOffset; yOffset < maxOffset; ++yOffset)
-    {
-        for (int xOffset = minOffset; xOffset < maxOffset; ++xOffset)
-        {
-            // Calculate the difference at this offset.
-            diff = differenceAtOffset(rhsImage, xOffset, yOffset);
-
-            // Compare to the previous best. We are looking for the minimum
-            // possible difference.
-            if (diff < bestDifference)
-            {
-                bestDifference = diff;
-#ifndef NDEBUG
-                bestY = yOffset;
-                bestX = xOffset;
-#endif
-            }
-#ifndef NDEBUG
-            else if (diff == bestDifference && fabs(xOffset) < fabs(bestX) &&
-                fabs(yOffset) < fabs(bestY))
-            {
-                // This is used primarily for debugging.
-                bestY = yOffset;
-                bestX = xOffset;
-            }
-#endif
-        }
-    }
-
-    bestDifference = bestDifference / (double) (m_width*m_height);
-
-    return bestDifference;
-}
-
-//--------------------------------------------------------------------------//
-
-double PngImage::difference(const PngImage& rhs) const
-{
-    if (m_width != rhs.width() || m_height != rhs.height())
-    {
-        throw range_error("Images are not the same size!");
-    }
-
-    return differenceAtOffset(rhs, 0, 0);
-}
-
-//--------------------------------------------------------------------------//
-
-double PngImage::greyPixel(gdImagePtr image, int x, int y) const
-{
-    const int pixel = gdImageGetPixel(image, x, y);
-    return ((double) gdImageRed(image, pixel) + gdImageGreen(image, pixel) + 
-            gdImageBlue(image, pixel))/(3.0*255.0);
-}
-
-//--------------------------------------------------------------------------//
-
-int PngImage::width() const
-{
-    return m_width;
-}
-
-//--------------------------------------------------------------------------//
-
-int PngImage::height() const
-{
-    return m_height;
-}
-
-//--------------------------------------------------------------------------//
-
-PngImage::~PngImage()
-{
-}
-
-//--------------------------------------------------------------------------//
-
-double PngImage::getPixel(tuple loc) const
-{
-    if (extract<int>(loc.attr("__len__")()) != 2)
-    {
-        throw range_error("Tuple must must be of form (x, y)");
-    }
-
-    const int x = extract<int>(loc[0]);
-    const int y = extract<int>(loc[1]);
-
-    if (!boundsCheck(x, y))
-    {
-        throw range_error("Out of range pixel values");
-    }
-
-    return m_cachedImage[y][x];
-}
-
-//--------------------------------------------------------------------------//
-
-BOOST_PYTHON_MODULE(comparePng)
-{
-    class_<PngImage>("PngImage", init<string>())
-        .def("difference", &PngImage::difference)
-        .def("differenceAtOffset", &PngImage::differenceAtOffset)
-        .def("invariantDifference", &PngImage::invariantDifference)
-        .def("boundsCheck", &PngImage::boundsCheck)
-        .add_property("width", &PngImage::width)
-        .add_property("height", &PngImage::height)
-        .def("__getitem__", &PngImage::getPixel)
-        ;
-}
-
-//--------------------------------------------------------------------------//

pixel/comparePng.hpp

-//--------------------------------------------------------------------------//
-// comparePng.cpp
-// Lars Yencken <lars.yencken@gmail.com>
-// vim: ts=4 sw=4 sts=4 et tw=78:
-// $Id: comparePng.hpp 233 2007-02-01 04:47:04Z lars $
-//
-//--------------------------------------------------------------------------//
-
-#ifndef COMPAREPNG_CPP
-#define COMPAREPNG_CPP
-
-//--------------------------------------------------------------------------//
-
-#include <string>
-#include <gd.h>
-#include <boost/python.hpp>
-#include <vector>
-
-using namespace std;
-using namespace boost::python;
-
-/**
- * A simple 2d array of doubles, used to cache images. 
- */
-typedef vector< vector<double> >    CachedImage;
-
-//--------------------------------------------------------------------------//
-
-/**
- * A single PNG image, with methods which allow you to compare to other PNG
- * images and calculate distance. Distance can be calculated either quickly,
- * or using a translation invariant method.
- */
-class PngImage
-{
-    public:
-        // *** CONSTRUCTORS *** //
-
-        /**
-         * Given a filename, loads a PNG image from that filename. Raises an
-         * exception if no such image exists. Caches the image twice for
-         * comparison speed.
-         *
-         * @param filename: The location of the image.
-         */
-        PngImage( string filename );
-
-        // *** ACCESSORS *** //
-
-        /**
-         * Calculates and returns the mean pixel difference between this image
-         * and another image. Only the default alignment (i.e. a (0,0) offset)
-         * is considered, making this much faster than the invariant method.
-         *
-         * @param rhs The image to compare to.
-         * @return The return value.
-         */
-        double difference( const PngImage& rhs ) const;
-
-        /**
-         * Calculates the lowest possible pixel difference, considering all
-         * possible offsets that overlap by at least g_minOverlap pixels in
-         * both the x and y directions. The tuple which gets returned
-         * indicates the best x and y offset for debugging.
-         *
-         * @param rhs The other image to compare with.
-         * @return The tuple (diff, bestX, bestY).
-         */
-        double invariantDifference( const PngImage& rhsImage ) const;
-
-        /**
-         * Returns the width of the image in pixels.
-         *
-         * @return The width.
-         */
-        int width() const;
-
-        /**
-         * Returns the height of the image in pixels.
-         *
-         * @return The height.
-         */
-        int height() const;
-
-        /**
-         * Returns the RGB components of a pixel's value, given its (x, y)
-         * coordinates. 
-         *
-         * @param loc An (x, y) tuple location. 
-         * @return: An (r, g, b) tuple.
-         */
-        double getPixel( tuple loc ) const;
-
-        /**
-         * Calculates and returns the average pixel difference at this offset.
-         * The resulting distance will be between 0.0 and 1.0.
-         *
-         * @param rhsImage The right hand side image.
-         * @param xOffset The x offset to compare at.
-         * @param yOffset The y offset to compare at.
-         */
-        double differenceAtOffset(
-                const PngImage& rhsImage,
-                int xOffset, int yOffset
-            ) const;
-
-        /**
-         * A quick bounds-checking function, which returns true if the
-         * coordinates are within valid bounds for this image, and false
-         * otherwise.
-         *
-         * @param x: The x coordinate to check.
-         * @param y: The y coordinate to check.
-         */
-        bool boundsCheck(int x, int y) const;
-
-        // *** MANIPULATORS *** //
-
-        // *** DESTRUCTOR *** //
-
-        /**
-         * Destructor, frees the memory held by the PNG image.
-         */
-        ~PngImage();
-
-    private:
-        // *** ATTRIBUTES *** //
-
-        /**
-         * A cached copy of the image in greyscale, pixel for pixel.
-         */
-        CachedImage m_cachedImage;
-
-        /**
-         * A cached copy of the image in greyscale, padded on either side to
-         * allow swift comparison with fewer bounds checks.
-         */
-        CachedImage m_extendedImage;
-
-        /**
-         * The width of the image.
-         */
-        int m_width;
-
-        /**
-         * The height of the image.
-         */
-        int m_height;
-
-        /**
-         * Converts a single pixel from RGB space to grey space, and scales
-         * from [0, 255] to [0.0, 1.0].
-         *
-         * @param image The image whose pixel to fetch.
-         * @param x The pixel's x coordinate.
-         * @param y The pixel's y coordinate.
-         * @return The pixel's greyscale index.
-         */
-        double greyPixel( const gdImagePtr image, int x, int y ) const;
-
-        /**
-         * Populates an image cache with the given image.
-         *
-         * @param image The image to cache.
-         * @param cachedObj The cache object to populate.
-         */
-        void cacheImage( 
-                const gdImagePtr& image,
-                CachedImage& cachedObj 
-            ) const;
-
-        /**
-         * Populates an image cache with the given image, however the image
-         * cache is padded with whitespace on either side, so as to be able to
-         * efficiently compare two images across a range of offsets. Only the 
-         * right hand image should be extended in this way.
-         *
-         * @param image The image to cache.
-         * @param cachedObj The cache object to store the image in.
-         */
-        void extendImage(
-                const gdImagePtr& image,
-                CachedImage& cachedObj
-            ) const;
-};
-
-//--------------------------------------------------------------------------//
-
-inline bool PngImage::boundsCheck(int x, int y) const
-{
-    return (x >= 0 && x < m_width && y >= 0 && y < m_height);
-}
-
-//--------------------------------------------------------------------------//
-
-#endif
-

pixel/comparePng.pyx

+# -*- coding: utf-8 -*-
+#----------------------------------------------------------------------------#
+# comparePng.pyx
+# Lars Yencken <lljy@csse.unimelb.edu.au>
+# vim: ts=4 sw=4 sts=4 et tw=78:
+# Tue May 13 17:03:21 2008
+#
+#----------------------------------------------------------------------------#
+
+import os
+
+#----------------------------------------------------------------------------# 
+
+cdef extern from "math.h":
+    double fabs(double x)
+    double pow(double x, double exp)
+
+#----------------------------------------------------------------------------#
+
+cdef extern from "stdio.h":
+    ctypedef struct FILE:
+        pass
+
+    FILE* fopen(char* filename, char* mode)
+    void fclose(FILE*)
+
+#----------------------------------------------------------------------------# 
+
+cdef extern from "gd.h":
+    ctypedef struct gdImage:
+        pass
+
+    gdImage* gdImageCreateFromPng(FILE* fd)
+    void gdImageDestroy(gdImage* image)
+    int gdImageSX(gdImage* image)
+    int gdImageSY(gdImage* image)
+    int gdImageGetPixel(gdImage* image, int x, int y)
+    int gdImageRed(gdImage* image, int pixel)
+    int gdImageGreen(gdImage* image, int pixel)
+    int gdImageBlue(gdImage* image, int pixel)
+
+#----------------------------------------------------------------------------# 
+
+class ImageSizeMismatch(Exception): pass
+
+cdef class PngImage:
+    cdef gdImage* _image
+    cdef int _width
+    cdef int _height
+
+    def __cinit__(self, filename):
+        cdef FILE* f
+        if not os.path.exists(filename):
+            raise IOError, 'file does not exist: %s' % filename
+
+        f = fopen(filename, "rb")
+        if f == NULL:
+            raise IOError, 'error opening file: %s' % filename 
+        self._image = gdImageCreateFromPng(f)
+        fclose(f)
+
+        self._width = gdImageSX(self._image)
+        self._height = gdImageSY(self._image)
+
+    cdef double getLuminancePixel(self, int x, int y):
+        "Fetch the luminance of the pixel at (x, y)."
+        cdef int red, green, blue, pixel
+        pixel = gdImageGetPixel(self._image, x, y)
+        red = gdImageRed(self._image, pixel)
+        green = gdImageGreen(self._image, pixel)
+        blue = gdImageBlue(self._image, pixel)
+        return (0.2126*red + 0.7152*green + 0.0722*blue)/255.0;
+
+    def norm(self, PngImage rhs not None, double n):
+        cdef int i, j
+        cdef double sum, diff
+
+        if self._width != rhs._width or self._height != rhs._height:
+            raise ImageSizeMismatch
+
+        if n < 1:
+            raise ValueError, "n must be >= 1: %d" % n
+
+        sum = 0.0
+        for y from  0 <= y < self._height:
+            for x from 0 <= x < self._width:
+                sum = sum + pow(fabs(self.getLuminancePixel(x, y) - \
+                        rhs.getLuminancePixel(x, y)), n)
+
+        return pow(sum, 1.0/n) / (self._width * self._height)
+
+    def __dealloc__(self):
+        if self._image != NULL:
+            gdImageDestroy(self._image)
+
+#----------------------------------------------------------------------------# 

pixel/pixelSimilarity.py

     imageA = _lazyLoadImage(kanjiA, font)
     imageB = _lazyLoadImage(kanjiB, font)
 
-    return 1.0 - imageA.difference(imageB)
-
-#----------------------------------------------------------------------------#
-
-def pixelSimilarityInvariant(kanjiA, kanjiB, font=settings.PIXEL_DEFAULT_FONT):
-    """ Calculates the translation invariant similarity using the comparePng
-        extension.
-    """
-    imageA = _lazyLoadImage(kanjiA, font)
-    imageB = _lazyLoadImage(kanjiB, font)
-
-    retVal = imageA.invariantDifference(imageB)
-
-    return 1.0 - retVal
-
-#----------------------------------------------------------------------------#
-
-def pixelSimilarityInvariantLoc(kanjiA, kanjiB, font=settings.PIXEL_DEFAULT_FONT):
-    """ Like pixelSimilarityInvariant(), but also provides the successful
-        offset.
-    """
-    imageA = _lazyLoadImage(kanjiA, font)
-    imageB = _lazyLoadImage(kanjiB, font)
-
-    difference, bestX, bestY = imageA.invariantDifference(imageB)[0]
-
-    return (1.0 - difference, bestX, bestY)
+    return 1.0 - imageA.norm(imageB, 1.0)
 
 #----------------------------------------------------------------------------#
 

pixel/testComparePng.py

         blankPng = PngImage(self.blank)
         glyphPng = PngImage(self.glyph)
 
-        self.assertAlmostEqual(blankPng.difference(blankPng), 0.0)
-        self.assertAlmostEqual(glyphPng.difference(glyphPng), 0.0)
+        self.assertAlmostEqual(blankPng.norm(blankPng, 1.0), 0.0)
+        self.assertAlmostEqual(glyphPng.norm(glyphPng, 1.0), 0.0)
         return
     
     #------------------------------------------------------------------------#
         blankPng = PngImage(self.blank)
         glyphPng = PngImage(self.glyph)
 
-        diffVal = blankPng.difference(glyphPng)
+        diffVal = blankPng.norm(glyphPng, 1.0)
         assert 0 < diffVal <= 1, "Out of range difference %f" % diffVal
 
         return
 
     #------------------------------------------------------------------------#
 
-    def testInvariantIdentical(self):
-        """ Tests the invariant method on identical images.
-        """
-        blankPng = PngImage(self.blank)
-        glyphPng = PngImage(self.glyph)
-
-        self.assertAlmostEqual(blankPng.invariantDifference(blankPng), 0, 3)
-        self.assertAlmostEqual(glyphPng.differenceAtOffset(glyphPng, 0, 0), 0)
-        self.assertAlmostEqual(glyphPng.invariantDifference(glyphPng), 0, 3)
-
-        return
-
-    #------------------------------------------------------------------------#
-
-    def testInvariantDifference(self):
-        """ Tests where a generic difference occurs.
-        """
-        blankPng = PngImage(self.blank)
-        glyphPng = PngImage(self.glyph)
-
-        diffVal = blankPng.invariantDifference(glyphPng)
-        assert 0 < diffVal <= 1, "Out of range difference %f" % diffVal
-
-        return
-
-    #------------------------------------------------------------------------#
-
-    def testInvariantTranslation(self):
-        """ Tests invariance under translation.
-        """
-        glyphPng = PngImage(self.glyph)
-        translatedPng = PngImage(self.translated)
-        self.assertAlmostEqual(glyphPng.invariantDifference(translatedPng), 0)
-        return
-
-    #------------------------------------------------------------------------#
-
 #----------------------------------------------------------------------------#
 
 if __name__ == "__main__":
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.