← Back to branch summary

~ubuntu-branches/ubuntu/maverick/digikam/maverick

« back to all changes in this revision

Viewing changes to libs/database/haar/haariface.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Luka Renko
  • Date: 2009-03-17 23:07:56 UTC
  • mfrom: (1.2.20 upstream) (3.1.4 experimental)
  • Revision ID: james.westby@ubuntu.com-20090317230756-db5b8rqjwb2j35e5
Tags: 2:0.10.0-1ubuntu1
* Remaining changes to Debian (committed to Debian SVN):
  - Depends: kde-icons-oxygen dropped (included through kdelibs)
  - Recommends: kipi-plugins added (provides major functionality)
  - debian/digikamthemedesigner.manpage: add missing manpage
* Remaning change to Debian:
  - Section: devel for -dbg package (no debug in Jaunty)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libs/database/haar/haariface.cpp
7
7
 * Description : Haar Database interface
8
8
 *
9
9
 * Copyright (C) 2003 by Ricardo Niederberger Cabral <nieder at mail dot ru>
10
 
 * Copyright (C) 2008 by Gilles Caulier <caulier dot gilles at gmail dot com>
11
 
 * Copyright (C) 2008 by Marcel Wiesweg <marcel dot wiesweg at gmx dot de>
 
10
 * Copyright (C) 2009 by Gilles Caulier <caulier dot gilles at gmail dot com>
 
11
 * Copyright (C) 2009 by Marcel Wiesweg <marcel dot wiesweg at gmx dot de>
 
12
 * Copyright (C) 2009 by Andi Clemens <andi dot clemens at gmx dot net>
12
13
 *
13
14
 * This program is free software; you can redistribute it
14
15
 * and/or modify it under the terms of the GNU General
137
138
 
138
139
    HaarIfacePriv()
139
140
    {
140
 
        data = 0;
141
 
        bin  = 0;
 
141
        data          = 0;
 
142
        bin           = 0;
 
143
        sigMap        = 0;
 
144
        useCachedSigs = false;
142
145
    }
143
146
 
144
147
    ~HaarIfacePriv()
145
148
    {
146
149
        delete data;
147
150
        delete bin;
 
151
        delete sigMap;
148
152
    }
149
153
 
150
154
    void createLoadingBuffer()
159
163
            bin = new Haar::WeightBin;
160
164
    }
161
165
 
162
 
    Haar::ImageData *data;
163
 
    Haar::WeightBin *bin;
 
166
    void enableCachedSignatures(bool cached)
 
167
    {
 
168
        if (sigMap)
 
169
            delete sigMap;
 
170
 
 
171
        if (cached)
 
172
            sigMap = new QMap<qlonglong, Haar::SignatureData>();
 
173
 
 
174
        useCachedSigs = cached;
 
175
    }
 
176
 
 
177
    bool                                  useCachedSigs;
 
178
    Haar::ImageData                      *data;
 
179
    Haar::WeightBin                      *bin;
 
180
    QMap<qlonglong, Haar::SignatureData> *sigMap;
164
181
 
165
182
    QSet<int> albumRootsToSearch;
166
183
};
301
318
    return bestMatches(&sig, numberOfResults, type);
302
319
}
303
320
 
304
 
QList<qlonglong> HaarIface::bestMatchesForImageWithThreshold(qlonglong imageid, double requiredPercentage, SketchType type)
 
321
QList<qlonglong> HaarIface::bestMatchesForImageWithThreshold(qlonglong imageid, double requiredPercentage,
 
322
                                                             SketchType type)
305
323
{
306
324
    Haar::SignatureData sig;
307
325
    if (!retrieveSignatureFromDB(imageid, &sig))
422
440
QMap<qlonglong, double> HaarIface::searchDatabase(Haar::SignatureData *querySig, SketchType type)
423
441
{
424
442
    d->createWeightBin();
 
443
 
425
444
    // The table of constant weight factors applied to each channel and bin
426
445
    Haar::Weights weights((Haar::Weights::SketchType)type);
427
446
 
437
456
    QMap<qlonglong, double> scores;
438
457
 
439
458
    // Variables for data read from DB
440
 
    DatabaseBlob blob;
441
 
    qlonglong imageid;
 
459
    DatabaseAccess      access;
 
460
    QSqlQuery           query;
 
461
    DatabaseBlob        blob;
 
462
    qlonglong           imageid;
442
463
    Haar::SignatureData targetSig;
443
464
 
 
465
    // reference for easier access
 
466
    QMap<qlonglong, Haar::SignatureData> &sigMap = *d->sigMap;
 
467
 
444
468
    bool filterByAlbumRoots = !d->albumRootsToSearch.isEmpty();
445
469
 
446
 
    DatabaseAccess access;
447
 
    QSqlQuery query;
448
 
    if (filterByAlbumRoots)
449
 
        query = access.backend()->prepareQuery(QString("SELECT imageid, Albums.albumRoot, matrix FROM ImageHaarMatrix "
450
 
                                                       " LEFT JOIN Images ON Images.id=ImageHaarMatrix.imageid "
451
 
                                                       " LEFT JOIN Albums ON Albums.id=Images.album "
452
 
                                                       " WHERE Images.status=1; "));
453
 
    else
454
 
        query = access.backend()->prepareQuery(QString("SELECT imageid, 0, matrix FROM ImageHaarMatrix "
455
 
                                                       " LEFT JOIN Images ON Images.id=ImageHaarMatrix.imageid "
456
 
                                                       " WHERE Images.status=1; "));
457
 
    if (!access.backend()->exec(query))
458
 
        return scores;
459
 
 
460
 
    // We don't use DatabaseBackend's convenience calls, as the result set is large
461
 
    // and we try to avoid copying in a temporary QList<QVariant>
462
 
    while (query.next())
 
470
    // if no cache is used or the cache signature map is empty, query the database
 
471
    if ( !d->useCachedSigs || (sigMap.isEmpty() && d->useCachedSigs) )
463
472
    {
464
 
        imageid = query.value(0).toLongLong();
465
473
        if (filterByAlbumRoots)
466
 
        {
467
 
            int albumRootId = query.value(1).toInt();
468
 
            if (!d->albumRootsToSearch.contains(albumRootId))
469
 
                continue;
470
 
        }
471
 
        blob.read(query.value(2).toByteArray(), &targetSig);
472
 
 
473
 
        // this is a reference
474
 
        double &score = scores[imageid];
475
 
 
476
 
        // Step 1: Initialize scores with average intensity values of all three channels
477
 
        for (int channel=0; channel<3; channel++)
478
 
        {
479
 
            score += weights.weightForAverage(channel) * fabs( querySig->avg[channel] - targetSig.avg[channel] );
480
 
        }
481
 
 
482
 
        // Step 2: Decrease the score if query and target have significant coefficients in common
483
 
        for (int channel=0; channel<3; channel++)
484
 
        {
485
 
            Haar::Idx *sig = targetSig.sig[channel];
486
 
            Haar::SignatureMap *queryMap = queryMaps[channel];
487
 
            int x;
488
 
            for (int coef = 0; coef < Haar::NumberOfCoefficients; coef++)
489
 
            {
490
 
                // x is a pixel index, either positive or negative, 0..16384
491
 
                x = sig[coef];
492
 
                // If x is a significant coefficient with the same sign in the query signature as well,
493
 
                // descrease the score (lower is better)
494
 
                // Note: both method calls called with x accept positive or negative values
495
 
                if ((*queryMap)[x])
496
 
                    score -= weights.weight(d->bin->binAbs(x), channel);
497
 
            }
498
 
        }
499
 
    }
 
474
            query = access.backend()->prepareQuery(QString("SELECT M.imageid, Albums.albumRoot, M.matrix "
 
475
                                                           " FROM ImageHaarMatrix AS M, Albums, Images "
 
476
                                                           " WHERE Images.id=M.imageid "
 
477
                                                           " AND Albums.id=Images.album "
 
478
                                                           " AND Images.status=1; "));
 
479
        else
 
480
            query = access.backend()->prepareQuery(QString("SELECT M.imageid, 0, M.matrix "
 
481
                                                           " FROM ImageHaarMatrix AS M, Images "
 
482
                                                           " WHERE Images.id=M.imageid "
 
483
                                                           " AND Images.status=1; "));
 
484
        if (!access.backend()->exec(query))
 
485
            return scores;
 
486
 
 
487
        // We don't use DatabaseBackend's convenience calls, as the result set is large
 
488
        // and we try to avoid copying in a temporary QList<QVariant>
 
489
        while (query.next())
 
490
        {
 
491
            imageid = query.value(0).toLongLong();
 
492
 
 
493
            if (filterByAlbumRoots)
 
494
            {
 
495
                int albumRootId = query.value(1).toInt();
 
496
                if (!d->albumRootsToSearch.contains(albumRootId))
 
497
                    continue;
 
498
            }
 
499
 
 
500
            blob.read(query.value(2).toByteArray(), &targetSig);
 
501
 
 
502
            if (d->useCachedSigs)
 
503
            {
 
504
                sigMap[imageid] = targetSig;
 
505
            }
 
506
            else
 
507
            {
 
508
                double              &score = scores[imageid];
 
509
                Haar::SignatureData &qSig  = *querySig;
 
510
                Haar::SignatureData &tSig  = targetSig;
 
511
 
 
512
                calculateScore(score, qSig, tSig, weights, queryMaps);
 
513
            }
 
514
        }
 
515
    }
 
516
    // read cached signature map if possible
 
517
    else
 
518
    {
 
519
        foreach (const qlonglong &imageid, sigMap.keys())
 
520
        {
 
521
            double              &score = scores[imageid];
 
522
            Haar::SignatureData &qSig  = *querySig;
 
523
            Haar::SignatureData &tSig  = sigMap[imageid];
 
524
 
 
525
            calculateScore(score, qSig, tSig, weights, queryMaps);
 
526
        }
 
527
    }
 
528
 
500
529
 
501
530
    return scores;
502
531
}
628
657
QMap< qlonglong, QList<qlonglong> > HaarIface::findDuplicates(const QList<qlonglong>& images2Scan,
629
658
                                               double requiredPercentage, HaarProgressObserver *observer)
630
659
{
631
 
    QMap< qlonglong, QList<qlonglong> > resultsMap;
632
 
    QList<qlonglong>::const_iterator    it;
633
 
    QList<qlonglong>::const_iterator    it2;
634
 
    QList<qlonglong>                    list;
635
 
    QSet<qlonglong>                     alreadyChecked;
 
660
    QMap< qlonglong, QList<qlonglong> >  resultsMap;
 
661
    QList<qlonglong>::const_iterator     it;
 
662
    QList<qlonglong>::const_iterator     it2;
 
663
    QList<qlonglong>                     list;
 
664
    QSet<qlonglong>                      resultsCandidates;
636
665
 
637
 
    int                                 total = 0;
638
 
    int                                 progress = 0;
639
 
    int                                 progressStep = 20;
 
666
    int                                  total        = 0;
 
667
    int                                  progress     = 0;
 
668
    int                                  progressStep = 20;
640
669
 
641
670
    if (observer)
642
671
    {
645
674
        observer->totalNumberToScan(total);
646
675
    }
647
676
 
 
677
    // create signature cache map for fast lookup
 
678
    d->enableCachedSignatures(true);
 
679
 
648
680
    for (it = images2Scan.constBegin(); it != images2Scan.constEnd(); ++it)
649
681
    {
650
 
        if (!alreadyChecked.contains(*it))
 
682
        if (!resultsCandidates.contains(*it))
651
683
        {
652
684
            //list = bestMatchesForImage(*it, 20, ScannedSketch);
653
685
            // find images with at least 90% similarity
658
690
                if (!(list.count() == 1 && list.first() == *it))
659
691
                {
660
692
                    resultsMap.insert(*it, list);
 
693
                    resultsCandidates << *it;
661
694
 
662
 
                    // mark already checked ids
663
 
                    alreadyChecked << *it;
664
 
                    foreach (qlonglong id, list)
 
695
                    foreach (const qlonglong &id, list)
665
696
                    {
666
 
                        alreadyChecked << id;
 
697
                        resultsCandidates << id;
667
698
                    }
668
699
                }
669
700
            }
670
701
        }
 
702
        // if an imageid is not a results candidate, remove it from the cached signature map as well,
 
703
        // to greatly improve speed
 
704
        if (!resultsCandidates.contains(*it))
 
705
            d->sigMap->remove(*it);
671
706
 
672
707
        progress++;
673
708
 
677
712
        }
678
713
    }
679
714
 
680
 
    return resultsMap;
 
715
    d->enableCachedSignatures(false);
 
716
 
 
717
    return resultsMap;
 
718
}
 
719
 
 
720
QMap< qlonglong, QList<qlonglong> > HaarIface::findDuplicatesFast(HaarProgressObserver *observer)
 
721
{
 
722
    QMap<qlonglong, QList<qlonglong> > resultsMap;
 
723
    QList<QByteArray> matrixList;
 
724
    int _total        = 0;
 
725
    int total         = 0;
 
726
    int progress      = 0;
 
727
    int progressStep  = 20;
 
728
 
 
729
    DatabaseAccess access;
 
730
 
 
731
    /*
 
732
     * Step 1: get all fingerprints that are absolutely identical
 
733
     */
 
734
    QSqlQuery mainQuery = access.backend()->prepareQuery(QString(
 
735
                                                         "SELECT COUNT(*)AS x, ImageHaarMatrix.matrix "
 
736
                                                         "FROM ImageHaarMatrix, Images "
 
737
                                                         "WHERE Images.id=ImageHaarMatrix.imageid "
 
738
                                                         "AND Images.status=1 "
 
739
                                                         "GROUP BY ImageHaarMatrix.matrix HAVING x>1 ")
 
740
    );
 
741
 
 
742
    if (!access.backend()->exec(mainQuery))
 
743
        return resultsMap;
 
744
 
 
745
    // get all duplicate fingerprints and calculate total images
 
746
    while (mainQuery.next())
 
747
    {
 
748
        matrixList << mainQuery.value(1).toByteArray();
 
749
        _total += mainQuery.value(0).toInt();
 
750
    }
 
751
 
 
752
    // --------------------------------------------------------
 
753
 
 
754
    if (observer)
 
755
    {
 
756
        total        = _total;
 
757
        progressStep = qMax(progressStep, total / 100);
 
758
        observer->totalNumberToScan(total);
 
759
    }
 
760
 
 
761
    // --------------------------------------------------------
 
762
 
 
763
    /*
 
764
     * Step 2: get all image ids for each duplicate fingerprint
 
765
     */
 
766
    QList<qlonglong> ids;
 
767
    foreach(const QByteArray &matrix, matrixList)
 
768
    {
 
769
        QSqlQuery imageQuery = access.backend()->prepareQuery(QString(
 
770
                "SELECT Images.id "
 
771
                "FROM Images, ImageHaarMatrix "
 
772
                "WHERE Images.id=ImageHaarMatrix.imageid "
 
773
                "AND Images.status=1 "
 
774
                "AND ImageHaarMatrix.matrix=?; ")
 
775
        );
 
776
        imageQuery.bindValue(0, matrix);
 
777
        access.backend()->exec(imageQuery);
 
778
 
 
779
        ids.clear();
 
780
 
 
781
        while (imageQuery.next())
 
782
        {
 
783
            ids << imageQuery.value(0).toLongLong();
 
784
            ++progress;
 
785
        }
 
786
        resultsMap[ids.first()] = ids;
 
787
 
 
788
        if (observer && (progress % progressStep == 0))
 
789
            observer->processedNumber(progress);
 
790
    }
 
791
 
 
792
    // make sure that the progress bar is really set to maximum now, just in case
 
793
    // we have calculated a wrong amount of duplicate images
 
794
    if (observer)
 
795
        observer->processedNumber(total);
 
796
 
 
797
    return resultsMap;
 
798
}
 
799
 
 
800
void HaarIface::calculateScore(double &score, Haar::SignatureData &querySig, Haar::SignatureData &targetSig,
 
801
                           Haar::Weights &weights, Haar::SignatureMap** queryMaps)
 
802
{
 
803
    // this is a reference
 
804
//    double &score                  = scores[imageid];
 
805
//    Haar::SignatureData &targetSig = sigMap[imageid];
 
806
 
 
807
    // Step 1: Initialize scores with average intensity values of all three channels
 
808
    for (int channel=0; channel<3; channel++)
 
809
    {
 
810
        score += weights.weightForAverage(channel) * fabs( querySig.avg[channel] - targetSig.avg[channel] );
 
811
    }
 
812
 
 
813
    // Step 2: Decrease the score if query and target have significant coefficients in common
 
814
    for (int channel=0; channel<3; channel++)
 
815
    {
 
816
        Haar::Idx *sig               = targetSig.sig[channel];
 
817
        Haar::SignatureMap *queryMap = queryMaps[channel];
 
818
        int x;
 
819
        for (int coef = 0; coef < Haar::NumberOfCoefficients; coef++)
 
820
        {
 
821
            // x is a pixel index, either positive or negative, 0..16384
 
822
            x = sig[coef];
 
823
            // If x is a significant coefficient with the same sign in the query signature as well,
 
824
            // decrease the score (lower is better)
 
825
            // Note: both method calls called with x accept positive or negative values
 
826
            if ((*queryMap)[x])
 
827
                score -= weights.weight(d->bin->binAbs(x), channel);
 
828
        }
 
829
    }
681
830
}
682
831
 
683
832
}  // namespace Digikam