Algoritma Tercepat untuk Transformasi Jarak

Saya mencari algoritma tercepat yang tersedia untuk transformasi jarak.

Menurut situs ini http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm , itu menggambarkan:

Transformasi jarak dapat dihitung jauh lebih efisien menggunakan algoritma pintar hanya dalam dua lintasan (misalnya Rosenfeld dan Pfaltz 1968).

Ketika mencari-cari di sekitar, saya menemukan: "Rosenfeld, A dan Pfaltz, J L. 1968. Fungsi Jarak pada Gambar Digital. Pengenalan Pola, 1, 33-61."

Tapi saya percaya kita harus memiliki algoritma yang lebih baik dan lebih cepat daripada yang ada di tahun 1968? Bahkan, saya tidak dapat menemukan sumbernya dari tahun 1968, jadi bantuan apa pun sangat dihargai.

Pedro F. Felzenszwalb dan Daniel P. Huttenlocher telah menerbitkan implementasi mereka untuk transformasi jarak . Anda tidak dapat menggunakannya untuk gambar volumetrik, tetapi mungkin Anda dapat memperluasnya untuk mendukung data 3d. Saya hanya menggunakannya sebagai kotak hitam.

Makalah ini membahas semua transformasi jarak tepat modern:

"Transformasi jarak Euclide 2D: survei komparatif", ACM Computing Survey, Vol 40, Edisi 1, Februari 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

Makalah ini mengutip teknik dari Meijster, et. Al. sebagai tujuan umum tercepat, transformasi yang tepat. Teknik ini dirinci di sini:

"Algoritma Umum untuk Menghitung Transformasi Jarak dalam Waktu Linear", A. Meijster, JBTM Roerdink dan WH Hesselink. http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Algoritma Meijster digunakan di pustaka efek open source saya: https://github.com/vinniefalco/LayerEffects

Saya harap ini membantu seseorang.

Berikut ini adalah kode C # untuk transformasi jarak euclidean kuadrat 1D menurut makalah Felzenszwald & Huttenlocher :

private static void DistanceTransform(double[] dataInput, ref double[] dataOutput)
{
    int n = dataInput.Length;

    int k = 0;
    int[] v = new int[n];
    double[] z = new double[n + 1];

    v[0] = 0;
    z[0] = Double.NegativeInfinity;
    z[1] = Double.PositiveInfinity;

    double s;

    for (int q = 1; q < n; q++)
    {
        while (true)
        {
            s = (((dataInput[q] + q * q) - (dataInput[v[k]] + v[k] * v[k])) / (2.0 * q - 2.0 * v[k]));

            if (s <= z[k])
            {
                k--;
            }
            else
            {
                break;
            }
        }

        k++;

        v[k] = q;
        z[k] = s;
        z[k + 1] = Double.PositiveInfinity;
    }

    k = 0;

    for (int q = 0; q < n; q++)
    {
        while (z[k + 1] < q)
        {
            k++;
        }

        dataOutput[q] = ((q - v[k]) * (q - v[k]) + dataInput[v[k]]);
    }
}

Ini dapat dengan mudah digunakan untuk gambar biner dan skala abu-abu dengan menerapkannya terlebih dahulu pada kolom gambar dan kemudian baris (atau sebaliknya, tentu saja).

Transformasinya memang sangat cepat.

Berikut adalah gambar sumber dan keluaran:

Piksel hitam memiliki nilai 0 dan putih memiliki beberapa nilai besar (harus lebih besar dari jarak kuadrat terbesar yang mungkin dalam gambar tetapi tidak terbatas) sehingga transformasi mengembalikan jarak dari piksel hitam dan yang putih dihilangkan.

Untuk mendapatkan transformasi jarak euclidean yang sebenarnya, cukup ambil akar kuadrat dari setiap piksel dari gambar output.