🕧 💆 ♋️ F #, algoritma penandaan untuk komponen gambar yang terhubung 👞 💪🏼 🎞️

Pencarian dan penandaan komponen yang terhubung dalam gambar biner adalah salah satu algoritma dasar untuk analisis dan pemrosesan gambar. Secara khusus, algoritma ini dapat digunakan dalam penglihatan mesin untuk mencari dan menghitung struktur umum dalam gambar, dengan analisis selanjutnya.

Dalam kerangka kerja artikel ini, dua algoritma untuk menandai komponen yang terhubung akan dipertimbangkan, implementasi mereka dalam bahasa pemrograman F # ditampilkan. Dan juga, analisis komparatif dari algoritma, mencari kelemahan. Bahan sumber untuk implementasi algoritma diambil dari buku " Computer Vision" (penulis L. Shapiro, J. Stockman. Terjemahan dari bahasa Inggris oleh A. A. Boguslavsky diedit oleh S. M. Sokolov) .

pengantar

Komponen yang terhubung dengan nilai v adalah himpunan C piksel yang memiliki nilai v dan masing-masing pasangan piksel ini terhubung dengan nilai v

Kedengarannya muskil, jadi mari kita lihat gambarnya saja. Kami berasumsi bahwa piksel foreground dari gambar biner ditandai sebagai 1 , dan piksel latar belakang ditandai sebagai 0 .

Setelah memproses gambar dengan algoritma penandaan komponen yang terhubung, kami mendapatkan gambar berikut. Di sini, alih-alih piksel, komponen yang terhubung dibentuk, yang berbeda satu sama lain dalam jumlah. Dalam contoh ini, 5 komponen ditemukan dan dimungkinkan untuk bekerja dengannya seperti dengan entitas yang terpisah.

Gambar 1: Komponen yang Terhubung Berlabel

\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 2 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 2 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 3 & 3 & 3 & 3 & 0 & 4 & 0 & 2 \\ 0 & 0 & 0 & 3 & 0 & 4 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 0 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 2 & 2 & 2 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 2 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 2 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 3 & 3 & 3 & 3 & 0 & 4 & 0 & 2 \\ 0 & 0 & 0 & 3 & 0 & 4 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 0 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 2 & 2 & 2 \end{matrix}$

Dua algoritma yang dapat digunakan untuk menyelesaikan masalah seperti itu akan dipertimbangkan di bawah ini.

Algoritma pelabelan rekursif

Kami akan mulai dengan melihat algoritma berbasis rekursi sebagai yang paling jelas. Prinsip operasi dari algoritma tersebut adalah sebagai berikut:

Tetapkan label, yang akan kita tandai komponen terkait, nilai awal.

Kami memilah-milah semua poin dalam tabel, mulai dengan koordinat 0x0 (sudut kiri atas). Setelah memproses poin berikutnya, tambah label satu per satu
Jika piksel pada koordinat saat ini adalah 1 , maka kami memindai keempat tetangga dari titik ini (atas, bawah, kanan, kiri)
1, , 0
, .

Dengan demikian, memilah-milah semua titik dalam array dan memohon algoritma rekursif untuk masing-masing, kemudian pada akhir pencarian kita mendapatkan tabel yang sepenuhnya ditandai. Karena ada pemeriksaan apakah suatu titik telah ditandai, setiap titik akan diproses hanya satu kali. Kedalaman rekursi hanya akan bergantung pada jumlah tetangga yang terhubung ke titik saat ini. Algoritma ini sangat cocok untuk gambar yang tidak memiliki isi gambar besar. Artinya, gambar di mana ada garis tipis dan pendek, dan yang lainnya adalah gambar latar belakang yang tidak diproses. Selain itu, kecepatan algoritma semacam itu mungkin lebih tinggi daripada algoritma baris demi baris (kita akan membahasnya nanti dalam artikel).

Karena gambar biner dua dimensi adalah matriks dua dimensi, ketika menulis algoritma, saya akan beroperasi dengan konsep matriks, tentang yang saya buat artikel terpisah, yang dapat Anda baca di sini.

Pemrograman fungsional menggunakan contoh bekerja dengan matriks dari teori aljabar linier.

Pertimbangkan dan analisis secara rinci fungsi F # yang mengimplementasikan algoritma pelabelan rekursif untuk komponen gambar biner yang terhubung

let recMarkingOfConnectedComponents matrix =

        let copy = Matrix.clone matrix

        let (|Value|Zero|Out|) (x, y) = 
            if x < 0 || y < 0
                || x > (copy.values.[0, *].Length - 1)
                || y > (copy.values.[*, 0].Length - 1) then
                Out
            else
                let row = copy.values.[y, *]
                match row.[x] with
                    | 0 -> Zero
                    | v -> Value(v)

        let rec markBits x y value =
            match (x, y) with
            | Value(v) ->
                if value > v then
                    copy.values.[y, x] <- value
                    markBits (x + 1) y value
                    markBits (x - 1) y value
                    markBits x (y + 1) value
                    markBits x (y - 1) value
            | Zero | Out -> ()

        let mutable value = 2
        copy.values
        |> Array2D.iteri (fun y x v -> if v = 1 then
                                            markBits x y value
                                            value <- value + 1)

        copy

Kami mendeklarasikan fungsi recMarkingOfConnectedComponents , yang mengambil array matriks dua dimensi, dikemas ke dalam catatan tipe Matrix. Fungsi tidak akan mengubah array asli, jadi pertama buat salinannya, yang akan diproses oleh algoritma dan dikembalikan.

let copy = Matrix.clone matrix

Untuk menyederhanakan pemeriksaan indeks poin yang diminta di luar array, buat templat aktif yang mengembalikan salah satu dari tiga nilai.

Keluar - indeks yang diminta melampaui array dua dimensi
Nol - titik berisi piksel latar belakang (sama dengan nol)
Nilai - indeks yang diminta berada di dalam array

Template ini akan menyederhanakan memeriksa koordinat titik gambar pada frame rekursi berikutnya:

let (|Value|Zero|Out|) (x, y) = 
    if x < 0 || y < 0
        || x > (copy.values.[0, *].Length - 1)
        || y > (copy.values.[*, 0].Length - 1) then
        Out
    else
        let row = copy.values.[y, *]
        match row.[x] with
            | 0 -> Zero
            | v -> Value(v)

Fungsi MarkBits dinyatakan rekursif dan berfungsi untuk memproses piksel saat ini dan semua tetangganya (atas, bawah, kiri, kanan):

let rec markBits x y value =
    match (x, y) with
    | Value(v) ->
        if value > v then
            copy.values.[y, x] <- value
            markBits (x + 1) y value
            markBits (x - 1) y value
            markBits x (y + 1) value
            markBits x (y - 1) value
    | Zero | Out -> ()

Fungsi menerima parameter berikut sebagai input: nomor

x - baris
y -
nilai nomor kolom - nilai label saat ini untuk menandai piksel.

Menggunakan kecocokan / dengan konstruksi dan template aktif (di atas), koordinat piksel diperiksa sehingga tidak melampaui dua dimensi. Himpunan. Jika titik berada di dalam array dua dimensi, maka kami melakukan pemeriksaan pendahuluan agar tidak memproses titik yang sudah diproses.

if value > v then

Jika tidak, rekursi tak terbatas akan terjadi dan algoritme tidak akan berfungsi.

Selanjutnya, tandai titik dengan nilai marker saat ini:

copy.values.[y, x] <- value

Dan kami memproses semua tetangganya, secara rekursif memanggil fungsi yang sama:

markBits (x + 1) y value
markBits (x - 1) y value
markBits x (y + 1) value
markBits x (y - 1) value

Setelah kami mengimplementasikan algoritma, itu harus digunakan. Pertimbangkan kodenya lebih detail.

let mutable value = 2
copy.values
|> Array2D.iteri (fun y x v -> if v = 1 then
                                    markBits x y value
                                    value <- value + 1)

Sebelum memproses gambar, atur nilai awal label, yang akan menandai grup piksel yang terhubung.

let mutable value = 2

Faktanya adalah bahwa piksel depan pada gambar biner sudah diatur ke 1 , oleh karena itu, jika nilai awal label juga 1 , maka algoritma tidak akan berfungsi. Oleh karena itu, nilai awal label harus lebih besar dari 1 . Ada cara lain untuk menyelesaikan masalah. Sebelum memulai algoritme, tandai semua piksel yang disetel ke 1 dengan nilai awal -1 . Kemudian kita dapat mengatur nilainya menjadi 1 . Anda dapat melakukannya sendiri jika Anda mau.

Konstruksi berikutnya, menggunakan fungsi Array2D.iteri , beralih ke semua titik dalam array, dan jika selama pencarian Anda menemukan titik yang ditetapkan ke 1, Maka ini berarti bahwa itu tidak diproses dan untuk itu Anda perlu untuk memanggil fungsi rekursif markBits dengan nilai label saat ini. Semua piksel yang diatur ke 0 diabaikan oleh algoritma.

Setelah memproses titik secara rekursif, kita dapat mengasumsikan bahwa seluruh grup yang terhubung dengan titik ini dijamin ditandai dan Anda dapat meningkatkan nilai label dengan 1 untuk menerapkannya ke titik terhubung berikutnya.

Pertimbangkan contoh penerapan algoritma semacam itu.

let a = array2D [[1;1;0;1;1;1;0;1]
                 [1;1;0;1;0;1;0;1]
                 [1;1;1;1;0;0;0;1]
                 [0;0;0;0;0;0;0;1]
                 [1;1;1;1;0;1;0;1]
                 [0;0;0;1;0;1;0;1]
                 [1;1;0;1;0;0;0;1]
                 [1;1;0;1;0;1;1;1]]
let A = Matrix.ofArray2D a

let t = System.Diagnostics.Stopwatch.StartNew()
let R = Algorithms.recMarkingOfConnectedComponents A
t.Stop()

printfn "origin =\n %A" A.values
printfn "rec markers =\n %A" R.values
printfn "elapsed recurcive = %O" t.Elapsed

origin =
 [[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]

rec markers =
 [[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]

elapsed recurcive = 00:00:00.0037342

Keuntungan dari algoritma rekursif termasuk kesederhanaannya dalam menulis dan memahami. Ini bagus untuk gambar biner yang mengandung latar belakang besar dan diselingi dengan kelompok kecil piksel (misalnya, garis, bintik-bintik kecil, dan sebagainya). Dalam hal ini, kecepatan pemrosesan gambar mungkin tinggi, karena algoritma memproses seluruh gambar dalam satu lintasan.

Kerugiannya juga jelas - ini adalah rekursi. Jika gambar terdiri dari bintik-bintik besar atau benar-benar banjir, maka kecepatan pemrosesan turun tajam (berdasarkan urutan besarnya) dan ada risiko bahwa program akan macet sama sekali karena kurangnya ruang kosong pada tumpukan.

Sayangnya, prinsip rekursi ekor tidak dapat diterapkan dalam algoritma ini, karena rekursi ekor memiliki dua persyaratan:

Setiap frame rekursi harus melakukan perhitungan dan menambahkan hasilnya ke akumulator, yang akan dikirim ke tumpukan.
Seharusnya tidak ada lebih dari satu panggilan fungsi rekursif dalam satu frame rekursi.

Dalam kasus kami, rekursi tidak melakukan perhitungan akhir apa pun, yang dapat diteruskan ke kerangka rekursi berikutnya, tetapi hanya memodifikasi array dua dimensi. Pada prinsipnya, ini dapat dielakkan dengan hanya mengembalikan satu nomor, yang dengan sendirinya tidak berarti apa-apa. Kami juga membuat 4 panggilan secara rekursif, karena kami perlu memproses keempat tetangga saat itu.

Algoritma klasik untuk menandai komponen yang terhubung berdasarkan pada struktur data untuk menggabungkan pencarian

Algoritma juga memiliki nama lain, "Algoritma penandaan progresif," dan di sini kita akan mencoba untuk menguraikannya.

Algoritme memproses gambar dalam dua lintasan. Pada lulus pertama, kelas ekivalensi ditentukan dan label sementara diberikan. Pada lintasan kedua, setiap tanda sementara digantikan oleh tanda kelas ekivalensi yang sesuai. Di antara lintasan pertama dan kedua, rekaman relasi ekivalensi yang disimpan yang disimpan dalam bentuk tabel biner diproses untuk menentukan kelas ekivalensi.

Definisi di atas bahkan lebih membingungkan, jadi kami akan mencoba menangani prinsip algoritma dengan cara yang berbeda dan mulai dari jauh.

Pertama, kita akan berurusan dengan definisi lingkungan yang terhubung empat dan delapan terhubung dari titik saat ini. Lihat gambar-gambar di bawah ini untuk memahami apa itu dan apa bedanya.

Gambar 2: Komponen empat terhubung

\begin{matrix} 1 \\ 2 & * & 3 \\ 4 \end{matrix}

$\begin{matrix} & 1 & \\ 2 & * & 3 \\ & 4 & \end{matrix}$

Gambar 2: Komponen yang terhubung delapan

\begin{matrix} 1 & 2 & 3 \\ 4 & * & 5 \\ 6 & 7 & 8 \end{matrix}

$\begin{matrix} 1 & 2 & 3 \\ 4 & * & 5 \\ 6 & 7 & 8 \end{matrix}$
Gambar pertama menunjukkan komponen yang terhubung empat titik, yaitu, ini berarti bahwa algoritma memproses 4 tetangga dari titik saat ini (kiri, kanan, atas dan bawah). Dengan demikian, komponen delapan titik yang terhubung berarti memiliki 8 tetangga. Pada artikel ini, kami akan bekerja dengan empat komponen yang terhubung.

Sekarang Anda perlu mencari tahu apa struktur data untuk menggabungkan pencarian , dibangun di atas beberapa set?

Sebagai contoh, misalkan kita memiliki dua set

(1, 2, 3, 4, 8) и (5, 6, 7)

$(1, 2, 3, 4, 8) (5, 6, 7)$

Set ini disusun dalam bentuk pohon-pohon berikut:

Perhatikan bahwa pada set pertama node 3 adalah root, dan yang kedua node 6.

Sekarang kami mempertimbangkan struktur data untuk pencarian-serikat, yang berisi kedua set ini, dan juga mengatur struktur pohon mereka. .

Gambar 4: Struktur data untuk pencarian-penyatuan

\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 0 & 3 & 7 & 7 & 0 & 3 \end{matrix}

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 0 & 3 & 7 & 7 & 0 & 3 \end{matrix}$

Perhatikan dengan cermat tabel di atas dan cobalah untuk menemukan hubungan dengan susunan pohon yang ditunjukkan di atas. Tabel tersebut harus dilihat dalam kolom vertikal. Dapat dilihat bahwa angka 3baris pertama sesuai dengan angka 0 pada baris kedua. Dan di pohon pertama, angka 3 adalah akar dari set pertama. Dengan analogi, Anda dapat menemukan bahwa angka 7 dari baris pertama sesuai dengan angka 0 dari baris kedua. Angka 7 juga merupakan akar dari pohon set kedua.

Jadi, kami menyimpulkan bahwa angka-angka dari baris atas adalah simpul anak dari set, dan angka-angka yang sesuai dari baris bawah adalah simpul induknya. Dipandu oleh aturan ini, Anda dapat dengan mudah mengembalikan kedua pohon dari tabel di atas.

Kami menganalisis detail tersebut sehingga nantinya akan lebih mudah bagi kami untuk memahami cara kerja algoritma penandaan progresif .. Untuk saat ini, mari kita memikirkan fakta bahwa serangkaian angka dari baris pertama selalu angka dari 1 hingga angka maksimum tertentu. Faktanya, jumlah maksimum baris pertama adalah nilai maksimum label yang ditandai dengan komponen yang terhubung . Dan set individual adalah transisi antara label yang terbentuk sebagai hasil dari pass pertama (kami akan membahas lebih rinci nanti).

Sebelum melanjutkan, pertimbangkan pseudo-code dari beberapa fungsi yang akan digunakan oleh algoritma.

Kami menunjukkan tabel yang mewakili struktur data untuk pencarian gabungan sebagai PARENT . Fungsi selanjutnya disebut find dan akan menggunakan label X saat ini sebagai parameterdan berbagai ORANGTUA . Orangtua jejak prosedur ini pointer sampai ke akar pohon dan menemukan label dari simpul akar pohon yang X milik .

 ̆   ̆  .
X —  
PARENT — , ̆    -

procedure find(X, PARENT);
{
j := X;
while PARENT[j] <> 0
    j := PARENT[j]; return(j);
}

Pertimbangkan bagaimana fungsi seperti itu dapat diimplementasikan pada F #

let rec find x =
    let index = Array.tryFindIndex ((=)x) parents.[0, *]
    match index with
    | Some(i) -> 
        match parents.[1, i] with
        | p when p <> 0 -> find p
        | _ -> x
    | None -> x

Di sini kita mendeklarasikan fungsi rekursif penemuan , yang mengambil label X saat ini . Array PARRENT tidak diteruskan di sini, karena kita sudah memilikinya di namespace global dan fungsinya sudah melihatnya dan dapat bekerja dengannya.

Pertama, fungsi mencoba menemukan indeks label di baris atas (karena Anda perlu menemukan induknya, yang terletak di baris bawah).

let index = Array.tryFindIndex ((=)x) parents.[0, *]

Jika pencarian berhasil, maka kami mendapatkan induknya dan membandingkannya dengan 0 . Jika induknya bukan 0 , maka simpul ini juga memiliki orangtua dan fungsinya secara rekursif memanggil dirinya sendiri sampai induknya adalah 0 . Ini berarti bahwa kami telah menemukan simpul root dari set.

match index with
    | Some(i) -> 
        match parents.[1, i] with
        | p when p <> 0 -> find p
        | _ -> x
    | None -> x

Fungsi selanjutnya yang kita butuhkan disebut persatuan . Dibutuhkan dua label X dan Y , serta array PARENT . Struktur ini memodifikasi (jika perlu) INDUK fusion bagian yang mengandung label X , dengan set yang terdiri dari label Y . Prosedur mencari node root dari kedua label dan jika mereka tidak cocok, maka simpul salah satu label ditetapkan sebagai simpul induk dari label kedua. Jadi ada penyatuan dua set.

   .
X — ,   .
Y — ,   .
PARENT — , ̆    -.

procedure union(X, Y, PARENT);
{
j := X;
k := Y;
while PARENT[j] <> 0
    j := PARENT[j];
while PARENT[k]] <> 0
    k := PARENT[k];

if j <> k then PARENT[k] := j;
}

Implementasi F # terlihat seperti ini

let union x y =
    let j = find x
    let k = find y
    if j <> k then parents.[1, k-1] <- j

Perhatikan bahwa fungsi find yang telah kami implementasikan sudah digunakan di sini .

Algoritma ini juga membutuhkan dua fungsi tambahan, yang disebut tetangga dan label . Fungsi tetangga mengembalikan himpunan titik tetangga ke kiri dan atas (karena dalam kasus kami algoritme bekerja pada komponen yang terhubung empat) dari piksel yang diberikan, dan fungsi label mengembalikan himpunan label yang telah ditetapkan ke sekumpulan piksel yang diberikan fungsi tetangga yang dikembalikan . Dalam kasus kami, kami tidak akan mengimplementasikan kedua fungsi ini, tetapi kami hanya akan membuat satu yang menggabungkan kedua fungsi dan mengembalikan label yang ditemukan.

let neighbors_labels x y =
    match (x, y) with
    | (0, 0) -> []
    | (0, _) -> [step1.[0, y-1]]
    | (_, 0) -> [step1.[x-1, 0]]
    | _ -> [step1.[x, y-1]; step1.[x-1, y]]
    |> List.filter ((<>)0)

Ke depan, saya akan mengatakan langsung bahwa array step1 yang menggunakan fungsi sudah ada di ruang global dan berisi hasil pemrosesan algoritma pada lintasan pertama. Saya ingin memberi perhatian khusus pada filter tambahan.

|> List.filter ((<>)0)

Itu memotong semua hasil yang 0 . Artinya, jika label berisi 0 , maka kita berurusan dengan titik di gambar latar belakang yang tidak perlu diproses. Ini adalah nuansa yang sangat penting yang tidak disebutkan dalam buku dari mana kita mengambil contoh, tetapi bagaimanapun, algoritma tidak akan bekerja tanpa pemeriksaan semacam itu.

Secara bertahap, langkah demi langkah, kita semakin mendekati esensi algoritma. Mari kita lihat kembali gambar yang perlu kita proses.

Gambar 5: Gambar biner asli

\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix}$

Sebelum memproses, buat sebuah array kosong step1 , di mana hasil dari pass pertama akan disimpan.

Gambar 6: Array step1 untuk menyimpan hasil pemrosesan utama

\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

$\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$

Pertimbangkan beberapa langkah pertama dari pemrosesan data primer (hanya tiga baris pertama dari gambar biner asli).

Sebelum kita melihat langkah demi langkah algoritma, mari kita lihat pseudo-code yang menjelaskan prinsip umum operasi.

     .
B —   .
LB —   .

procedure classical_with_union-find(B, LB);
{
“  .” initialize();
“  1 ̆  L     .”
for L := 0 to MaxRow
{
“     L  ”
for P := 0 to MaxCol
    LB[L,P] := 0;
“  L.”
for P := 0 to MaxCol
    if B[L,P] == 1 then
    {
        A := prior_neighbors(L,P);
        if isempty(A)
        then {M := label; label := label + 1;};
        else M := min(labels(A));
        LB[L,P] := M;
        for X in labels(A) and X <> M
           union(M, X, PARENT);
    }
}
“  2 ,    1,     .”
for L := 0 to MaxRow
    for P := 0 to MaxCol
        if B[L, P] == 1
        then LB[L,P] := find(LB[L,P], PARENT);
};
      LB ( step1)     ( ).

Gambar 7: Langkah 1. Poin (0,0), label = 1

\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$
Gambar 8: Langkah 2. Poin (1,0), label = 1

\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$
Gambar 9: Langkah 2. Poin (2.0), label = 1

\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$
Gambar 10: Langkah 4. Point (3.0), label = 2

\begin{matrix} 1 & 1 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$
Gambar 11: Langkah terakhir, hasil akhir dari operan pertama

\begin{matrix} 1 & 1 & 0 & 2 & 2 & 2 & 0 & 3 \\ 1 & 1 & 0 & 2 & 0 & 2 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 7 & 7 & 3 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 2 & 2 & 2 & 0 & 3 \\ 1 & 1 & 0 & 2 & 0 & 2 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 7 & 7 & 3 \end{matrix}$
Harap dicatat bahwa sebagai hasil dari pemrosesan awal gambar asli, kami mendapat dua set

(1, 2) - (3, 7)

$(1,2) - (3,7)$

Secara visual, ini dapat dilihat sebagai kontak dari tanda 1 dan 2 (koordinat titik (1,3) dan (2,3) ) dan tanda 3 dan 7 (koordinat titik (7,7) dan (7,6) ). Dari sudut pandang struktur data untuk pencarian-serikat, hasil ini diperoleh.

Gambar 12: Struktur data terkomputasi untuk agregasi pencarian

\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 3 \end{matrix}

$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 3 \end{matrix}$
Setelah akhirnya memproses gambar menggunakan struktur data yang diperoleh, kami mendapatkan hasil berikut.

Gambar 13: Hasil Akhir

\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 3 & 3 & 3 \end{matrix}

$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 3 & 3 & 3 \end{matrix}$
Sekarang semua komponen yang terhubung kami memiliki label unik dan dapat digunakan dalam algoritma selanjutnya untuk diproses.

Implementasi kode F # adalah sebagai berikut

let markingOfConnectedComponents matrix =

    // up to 10 markers
    let parents = Array2D.init 2 10 (fun x y -> if x = 0 then y+1 else 0)

    // create a zero initialized copy
    let step1 = (Matrix.cloneO matrix).values

    let rec find x =
        let index = Array.tryFindIndex ((=)x) parents.[0, *]
        match index with
        | Some(i) -> 
            match parents.[1, i] with
            | p when p <> 0 -> find p
            | _ -> x
        | None -> x

    let union x y =
        let j = find x
        let k = find y
        if j <> k then parents.[1, k-1] <- j

    // returns up and left neighbors of pixel
    let neighbors_labels x y =
        match (x, y) with
        | (0, 0) -> []
        | (0, _) -> [step1.[0, y-1]]
        | (_, 0) -> [step1.[x-1, 0]]
        | _ -> [step1.[x, y-1]; step1.[x-1, y]]
        |> List.filter ((<>)0)

    let mutable label = 0
    matrix.values
    |> Array2D.iteri (fun x y v ->
                        if v = 1 then
                            let n = neighbors_labels x y
                            let m = if n.IsEmpty then
                                        label <- label + 1
                                        label
                                    else
                                        n |> List.min
                            n |> List.iter (fun v -> if v <> m then union m v)
                            step1.[x, y] <- m)

    let step2 = matrix.values
                |> Array2D.mapi (fun x y v ->
                        if v = 1 then step1.[x, y] <- find step1.[x, y]
                        step1.[x, y])

    { values = step2 }

Penjelasan baris-demi-baris dari kode tidak lagi masuk akal, karena semuanya dijelaskan di atas. Di sini Anda cukup memetakan kode F # ke kode semu untuk memperjelas cara kerjanya.

Algoritma Pembandingan

Mari kita bandingkan kecepatan pemrosesan data dengan kedua algoritma (rekursif dan baris-bijaksana).

let a = array2D [[1;1;0;1;1;1;0;1]
                 [1;1;0;1;0;1;0;1]
                 [1;1;1;1;0;0;0;1]
                 [0;0;0;0;0;0;0;1]
                 [1;1;1;1;0;1;0;1]
                 [0;0;0;1;0;1;0;1]
                 [1;1;0;1;0;0;0;1]
                 [1;1;0;1;0;1;1;1]]
let A = Matrix.ofArray2D a

let t1 = System.Diagnostics.Stopwatch.StartNew()
let R1 = Algorithms.markingOfConnectedComponents A
t1.Stop()

let t2 = System.Diagnostics.Stopwatch.StartNew()
let R2 = Algorithms.recMarkingOfConnectedComponents A
t2.Stop()

printfn "origin =\n %A" A.values
printfn "markers =\n %A" R1.values
printfn "rec markers =\n %A" R2.values

printfn "elapsed lines = %O" t1.Elapsed
printfn "elapsed recurcive = %O" t2.Elapsed

origin =
 [[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]
markers =
 [[1; 1; 0; 1; 1; 1; 0; 3]
 [1; 1; 0; 1; 0; 1; 0; 3]
 [1; 1; 1; 1; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]
rec markers =
 [[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]
elapsed lines = 00:00:00.0081837
elapsed recurcive = 00:00:00.0038338

Seperti yang Anda lihat, dalam contoh ini, kecepatan algoritma rekursif secara signifikan melebihi kecepatan algoritma baris demi baris. Namun semuanya berubah segera setelah kami mulai memproses gambar yang diisi dengan warna solid dan untuk kejelasan, kami juga akan meningkatkan ukurannya menjadi 100x100 piksel.

let a = Array2D.create 100 100 1
let A = Matrix.ofArray2D a

let t1 = System.Diagnostics.Stopwatch.StartNew()
let R1 = Algorithms.markingOfConnectedComponents A
t1.Stop()
printfn "elapsed lines = %O" t1.Elapsed

let t2 = System.Diagnostics.Stopwatch.StartNew()
let R2 = Algorithms.recMarkingOfConnectedComponents A
t2.Stop()
printfn "elapsed recurcive = %O" t2.Elapsed

elapsed lines = 00:00:00.0131790
elapsed recurcive = 00:00:00.2632489

Seperti yang Anda lihat, algoritma rekursif sudah 25 kali lebih lambat daripada yang linier. Mari kita tambah ukuran gambar menjadi 200x200 piksel.

elapsed lines = 00:00:00.0269896
elapsed recurcive = 00:00:06.1033132

Perbedaannya sudah ratusan kali lipat. Saya perhatikan bahwa sudah pada ukuran 300x300 piksel, algoritma rekursif menyebabkan stack overflow dan program macet.

Ringkasan

Dalam kerangka kerja artikel ini, salah satu algoritma dasar untuk menandai komponen yang terhubung untuk memproses gambar biner diperiksa menggunakan bahasa fungsional F # sebagai contoh. Di sini diberikan contoh penerapan algoritma rekursif dan klasik, prinsip operasinya dijelaskan, analisis komparatif dilakukan dengan menggunakan contoh spesifik.

Kode sumber yang dibahas di sini juga dapat dilihat di MatrixAlgorithms
github,

semoga artikel ini menarik bagi mereka yang tertarik pada F # dan algoritma pemrosesan gambar pada khususnya.

F #, algoritma penandaan untuk komponen gambar yang terhubung

pengantar

Algoritma pelabelan rekursif

Algoritma klasik untuk menandai komponen yang terhubung berdasarkan pada struktur data untuk menggabungkan pencarian

Algoritma Pembandingan

Ringkasan

More articles: