6

私は現在、 OpenCVAsyncTaskを使用した手法を使用して画像を比較する単一のものを持っています。たとえば、画像を互いにbubble sort比較する必要があります。これは比較400を意味します。400*401/2=80,2001 回の比較に 1 秒かかるとします。それで、それ80,200 secは22.27 hours途方もなく長いです。そこで、このタイプのアルゴリズムを開発しました。

400画像を のグループに分割します5。したがって80、各グループに画像があります。

アルゴリズムの最初の部分は、グループ メンバー内で自分自身を比較する画像です。

したがって、image1は自身を と比較します。これは、比較image2-80があることを意味し79ます。比較などを行いますimage2。78これは3,160比較を行います。または3,160 sec。同様に、image81自分自身をなどと比較image82-160します。したがって、すべての「グループ比較」は3,160 sec、並行して実行されるため、終了します。

アルゴリズムの 2 番目の部分では、要素group 1をgroup 2要素group 2と比較します。これはが と比較されることを意味し、これは比較であるため、 と の間の合計比較は比較になります。グループ比較と並行して各画像比較を行うことは可能ですか? つまり、自分自身をthenと比較する場合は、他のグループが同じことをしている間、同じことを行う必要があります。したがって、この部分は のみを取る必要があります。group 3group 3group 4image1image81-16080group 1group 280*80=6400image1image81-160image26400 sec

今、と、と、とgroup1比較されます。->group3group2group4group3group56400 sec

その後、group1 will be compared with group4そして. ->group2group56400 sec

したがって、すべてのグループが比較されます。

合計時間 = 3160+6400+6400+6400=22,360sec。グループが多ければ多いほど、時間がかかることに気づきました。したがって、時間の増加を抑えるには、グループのサイズを大きくする必要があります。いずれにせよ、それは時間をほぼ1/4th実際の時間に短縮します。

このアルゴリズムは非現実的ですか? もしそうなら、なぜですか？その欠陥は何ですか？どうすれば修正できますか？画像のリストをより速く比較するためのより良いアルゴリズムはありますか? 明らかにそうquick sortではありません。画像を昇順または降順で並べることはできません。それともできますか？

このアルゴリズムが可能なら？それを実装する最良の方法は何ですか？ThreadまたはAsyncTask？

4

1 に答える 1

1

これは現実的なアルゴリズムですが、プログラム全体で同じ数のワーカー スレッドを使用できることが理想的です。このためには、偶数のスレッド (たとえば 8) を使用する必要があります。

パス 1 では、スレッド 1 がイメージ 1 ～ 50 を処理し、スレッド 2 がイメージ 51 ～ 100 を処理します。

Pass2 では、Thread1 と Thread2 の両方がイメージ 1 ～ 100 を処理します。スレッド 1 は画像 1 ～ 25 および 50 ～ 75 を処理し、スレッド 2 は画像 26 ～ 50 および画像 76 ～ 100 を処理します。次に、スレッド 1 がイメージ 1 ～ 25 および 76 ～ 100 を処理し、スレッド 2 がイメージ 26 ～ 75 を処理します。

パス 3 から 8 までは同じパターンに従います。処理中の 2 つのグループに割り当てられた 2 つのスレッドが、それらの間のグループを分割します。このようにして、すべてのスレッドをビジー状態に保ちます。ただし、グループのパーティショニングを簡素化するには、偶数のスレッドが必要です。

4 スレッドのサンプル コード

class ImageGroup {
    final int index1;
    final int index2;
}

class ImageComparer implements Runnable {
    final Image[] images;
    ImageGroup group1;
    ImageGroup group2;

    public ImageComparer(Image[] images, ImageGroup group1, ImageGroup group2) {
        ...
    }

    public void run() {
        if(group2 == null) { // Compare images within a single group
            for(int i = group1.index1; i < group1.index2; i++) {
                for(int j = i + 1; j < group1.inex2; j++) {
                    compare(images[i], images[j]);
                }
            }
        } else { // Compare images between two groups
            for(int i = group1.index1; i < group1.index2; i++) {
                for(int j = group2.index1; j < group2.index2; j++) {
                    compare(images[i], images[j]);
                }
            }
        }
    }
}

ExecutorService executor = new ThreadPoolExecutor(); // use a corePoolSize equal to the number of target threads
// for 4 threads we need 8 image groups
ImageGroup group1 = new ImageGroup(0, 50);
ImageGroup group2 = new ImageGroup(50, 100);
...
ImageGroup group8 = new ImageGroup(450, 500);

ImageComparer comparer1 = new ImageComparer(images, group1, null);
ImageComparer comparer2 = new ImageComparer(images, group3, null);
...
ImageComparer comparer4 = new ImageComparer(images, group7, null);

// submit comparers to executor service
Future future1 = executor.submit(comparer1);
Future future2 = executor.submit(comparer2);
Future future3 = executor.submit(comparer3);
Future future4 = executor.submit(comparer4);

// wait for threads to finish
future1.get();
future2.get();
future3.get();
future4.get();

comparer1 = new ImageComparer(images, group2, null);
...
comparer4 = new ImageComparer(images, group8, null);

// submit to executor, wait to finish

comparer1 = new ImageComparer(images, group1, group3);
...
comparer4 = new ImageComparer(images, group7, group6);

// submit to executor, wait to finish

comparer1 = new ImageComparer(images, group1, group4);
...
comparer4 = new ImageComparer(images, group7, group5);
于 2013-04-23T03:00:42.310 に答える