Bug 207188

Summary: Fuzzy Search ignores colours
Product: [Applications] digikam Reporter: Simon <simon.eu>
Component: Searches-SimilarityAssignee: Digikam Developers <digikam-bugs-null>
Status: REPORTED ---    
Severity: normal CC: caulier.gilles, greenleaf123, marcel.wiesweg, metzpinguin, nadavkav, nicolas.brisset, niels.misc, simon
Priority: NOR    
Version: 1.0.0   
Target Milestone: ---   
Platform: unspecified   
OS: Linux   
Latest Commit: Version Fixed In:

Description Simon 2009-09-12 17:08:43 UTC
Version:           1.0.0-beta5 (rev.: 1022091) (using 4.3.1 (KDE 4.3.1), Debian packages)
Compiler:          cc
OS:                Linux (i686) release 2.6.31-rc8-sidux-686

When I fill the Fuzzy Search Sketch with green colour, I get about 50 pictures showing a blue sky with light clouds.

No green at all.

Hmmm ...

Or when taking a fully saturated orange, the first image is this one: http://de.wikipedia.org/wiki/Datei:Frost_on_birch.jpg

Imho that's not the expected behaviour.
Comment 1 Mikolaj Machowski 2009-09-13 11:01:21 UTC
Fuzzy search is looking for brightest points of R, G, B and their patterns. If you check carefully your images you will find that those images are similar in that terms.
Comment 2 Andi Clemens 2009-09-13 11:08:43 UTC
But still it is wrong :)
When I want to search red images, I want to find red images, not green, blue, yellow or black ones.
I'm not sure if current duplicates algorithm is capable of being that precise though.
Find similar works fine because all channels are involved, but fuzzy search is behaving wrong in this case.
Maybe we just need to adjust the fuzzy search instead of re-thinking the whole duplicates algorithm?
Comment 3 Simon 2009-09-13 11:20:49 UTC
http://granjow.net/uploads/bt/digikam-fuzzy-4.jpg
http://granjow.net/uploads/bt/digikam-fuzzy-3.jpg
http://granjow.net/uploads/bt/digikam-fuzzy-2.jpg
http://granjow.net/uploads/bt/digikam-fuzzy-1.jpg

@Mikolaj If I check carefully I see that I'm rarely finding what I'm actually searching for. 

What I remember is colour and shape, but only roughly. I don't care what the brightest point is, as my eye sees colours but not RGB values; I don't even know which they are.
Comment 4 Mikolaj Machowski 2009-09-13 12:03:06 UTC
On Sunday 13 September 2009 11:20:50 Simon wrote:
> @Mikolaj If I check carefully I see that I'm rarely finding what I'm
>  actually searching for.

Unfortunately in all your examples this is what algorithm finds, it is really 
confused by pure colors and grays (4), apart from 3rd image in first line 
everything is OK (3), similar in (2), (1) is more complicated but also fits 
algorithm mechanism.

I wonder if it could be helped not by total rethinking of fuzzy logic but 
"simply" by adding to fingerprint data about darkest point of image. It should 
reduce number of really strange hits.

Note that this is very similar approach practically it would require almost 
total rewrite of haar.cpp...
Comment 5 Marcel Wiesweg 2009-09-13 16:04:50 UTC
Literatur is available [1]. We have faithfully implemented the algorithm outlined there, only adapted to our storage situation.
Remember that for fingerprint generation, the image is transformed to YIQ colorspace and wavelet transformed. Then the coordinates of the 40 largest wavelet coefficients are taken.
So unless your mind is accustomed to thinking in frequency domain for images (mine is not) this is _not_ intuitive. For the question here, note that the YIQ color space conversion may be the main cause.

Suggestions for superior algorithms are welcome (literature, GPL reference implementation, no patent problems, comparable speed and storage impact)


[1]"Fast Multiresolution Image Querying"
   by Charles E. Jacobs, Adam Finkelstein and David H. Salesin.
   http://www.cs.washington.edu/homes/salesin/abstracts.html
Comment 6 Simon 2010-04-30 09:17:11 UTC
What about using the esame algorithm again, but with RGB, without color space conversion?
Comment 7 Andi Clemens 2010-09-25 22:52:01 UTC
*** Bug 175905 has been marked as a duplicate of this bug. ***
Comment 8 Niels 2013-06-03 16:28:06 UTC
My personal conclusion is that the results of sketch searches are not ever useful.

I really don't know much about the subject matter. A quick google returned this discussion:
http://stackoverflow.com/questions/843972/image-comparison-fast-algorithm
Comment 9 caulier.gilles 2014-08-31 10:16:03 UTC
*** Bug 187293 has been marked as a duplicate of this bug. ***
Comment 10 caulier.gilles 2020-08-03 05:08:00 UTC
digiKam 7.0.0 stable release is now published:

https://www.digikam.org/news/2020-07-19-7.0.0_release_announcement/

We need a fresh feedback on this file using this version.

Best Regards

Gilles Caulier
Comment 11 caulier.gilles 2023-05-01 03:22:09 UTC
Maik, 

about this entry, the fuzzy search gives the best results as it can. It's not perfect but not too bad at all. For me the colors shape searches give at least suitable items, even if few items do not correspond matches the query.

Gilles
Comment 12 caulier.gilles 2023-10-24 06:06:47 UTC
Maik,

Do you seen my previous comment ?

Gilles
Comment 13 Maik Qualmann 2023-10-24 11:12:34 UTC
I don't use this feature often, agree to your Comment 11. I find the results that found but often surprisingly good. There were relatively many comments here who would like a better result, we could make a note of it as a GSOC project.

Maik
Comment 14 caulier.gilles 2023-12-01 12:51:24 UTC
*** Bug 452878 has been marked as a duplicate of this bug. ***