[Digikam-devel] Reusing the "fuzzy search" algorithm

[Marcel Wiesweg]

> Note: this is only tangentially related to Digikam, but it was suggested
> that I send a mail here, so feel free to stop reading if you're not
> interested.
>
> Basically I'm working on a program which is mostly inspired by the blog
> post here: http://tinyurl.com/5rm8af which basically builds representations
> of an image using coloured polygons. But I wanted to make my own that used
> a real genetic algorithm.
>
> Anyways, I need a way to determine how close the images that are created by
> painting coloured polygons are to the original image, in order to be able
> to select and crossover the "best" patterns of polygons. Right now I
> basically convert the coordinates to Y-I-Q colour space and then use the
> Pythagorean theorem to find the distance and add up the total, but I want a
> better way, like how Digikam's fuzzy search works. So, I'm wondering if it
> would be possible to reuse Digikam's implementation of the search in my
> program (which would be Free software of course).

You are free to use the source, of course ;-)

>
> However I looked at the paper and though I don't fully understand a lot of
> the math (I am only in highschool right now, not at a university, so I hope
> it's forgivable), I noticed some things that might cause problems: e.g. the
> algorithm in the paper is optimised for matching an ill-defined query image
> to well-defined target images, whereas I have a well-defined query image
> [1] and I'm trying to rank a series of ill-defined targets (like [2]).
> Also, I don't really need to store a searchable index of the images since I
> am only using the computed value once.

The interesting thing about the algorithm is that the Math is very simple. 
It's just sometimes a bit confusing.
We did not do the initial implementation, but adopted it from the imgseek 
program. Comparing the old code with the matching part of the paper was the 
best way to get a good understanding of both.
The paper suggests and imgseek implemented an efficient method for in-memory 
storage of the index which we had to implement differently, because our 
signatures are stored in database we ruled out to keep it all in memory. We 
can now read signatures sequentially. But that's not of your interest. Other 
differences to Imgseek code is that we use good C++ features and syntax in my 
taste.

Have a look at our code:
libs/database/haar/haar.cpp is mostly low-level code which you can use as-is
libs/database/haar/haariface.cpp interfaces with our data storage, but the 
bestMatches() and searchDatabase() methods contain essential code.

>
> Would it be possible to adapt the Digikam implementation to my needs or
> would I be better off to attempt to reimplement a modified version of the
> algorithm in the paper (e.g. drop the condition in section 2.3 "we only
> consider terms in which the query has a non-zero wavelet coefficient
> ~Q[i,j]. A potential benefit (…) however it does not allow a detailed query
> to match a target that does not contain that same detail" ) ?

I dont know a good answer on that. Either you think it through or you try it 
out ;-)

>
> Henry de Valence
>
> [1] Source image: http://imagebin.ca/view/3JL760.html
> [2] After 229 generations: http://imagebin.ca/view/3fKx7IT.html
> _______________________________________________
> Digikam-devel mailing list
> Digikam-devel at kde.org
> https://mail.kde.org/mailman/listinfo/digikam-devel


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/digikam-devel/attachments/20090115/96439966/attachment.html>