المقدمة
كما هو مطبق على الصور الثنائية ، يتم استخدام مورفولوجيا لوصف أي خصائص لهذه الصورة. وتستخدم عمليات علم التشكل الرياضي لتحويل المجموعات. في هذا الصدد ، يتم استخدامها بشكل ملائم لمعالجة الصور الثنائية مع التحليل اللاحق.
ستناقش المقالة العمليات الأساسية للتشكيلات الرياضية (الثنائية) في سياق F #. وأيضًا ، في نهاية المقال ، سأعطي مثالًا لتحليل النتيجة ، والذي يمكن استخدامه في خوارزميات رؤية الآلة.
ستستخدم هذه المقالة المواد التي تمت مناقشتها في مقالتي السابقة حول تحليل خوارزمية وضع العلامات للمكونات ذات الصلة. يمكنك التعرف على المقالة هنا: F # ، خوارزمية لتمييز المكونات المتصلة بالصورة .
العمليات الأساسية للمورفولوجيا الثنائية
من أجل إجراء عملية مورفولوجيا ثنائية ، نحتاج
- الصورة الثنائية الأصلية (B)
- العناصر الهيكلية)
عنصر الهيكلة هو وصف لمنطقة ما من الشكل. يمكن أن يكون لهذه المنطقة أي حجم وشكل ، والتي يمكن تمثيلها كصورة ثنائية
فيما يلي بعض الأمثلة على عناصر الهيكلة على شكل مستطيل وقرص وخاتم.
عناصر الهيكلة هي بعض القناع الذي يحدد منطقة الصورة التي سيتم تنفيذ عملية التشكل الثنائي عليها.
عناصر الهيكلة لها أيضًا نقطة أصل . عادة ما يكون موجودًا في وسط القناع ، ولكن يمكن أن يكون في أي مكان. يجب أن يتطابق أصل عنصر الهيكلة مع البكسل الحالي للصورة الثنائية من أجل إجراء تحويلات عليه.
ضع في اعتبارك العمليات الأساسية للمورفولوجيا الثنائية.
يُشار إلى تمديد الصورة الثنائية B بواسطة عنصر الهيكلة S بواسطة B ⊕ S ويتم تعريفه على النحو التالي
. S . , , .
.
Figure 1: B
Figure 2: S
Figure 3: B ⊕ S
F#, .
let (>.) value checkValue = if value > checkValue then checkValue else value
let (<.) value checkValue = if value < checkValue then checkValue else value
let subArrayOfMaks array2d mask (centerX, centerY) (maskCenterX, maskCenterY) =
let (rows, cols) = Matrix.sizes {values = array2d}
let (maskRows, maskCols) = Matrix.sizes {values = mask}
let x1 = centerX - maskCenterX
let y1 = centerY - maskCenterY
let x2 = x1 + maskCols - 1
let y2 = y1 + maskRows - 1
(x1 <. 0, x2 >. (cols - 1), y1 <. 0, y2 >. (rows - 1))
let upbuilding array2d mask (maskCenterX, maskCenterY) =
let sub source mask (x, y) (maskCenterX, maskCenterY) =
let (x1, x2, y1, y2) = subArrayOfMaks source mask (x, y) (maskCenterX, maskCenterY)
source.[y1..y2, x1..x2] <- mask
let copy = (Matrix.cloneO {values = array2d}).values
array2d |> Array2D.iteri (fun y x v -> if v = 1 then sub copy mask (x, y) (maskCenterX, maskCenterY))
copy
upbuilding
let upbuilding array2d mask (maskCenterX, maskCenterY) =
, .
>. <.
let (>.) value checkValue = if value > checkValue then checkValue else value
let (<.) value checkValue = if value < checkValue then checkValue else value
value —
checkValue — ( )
value ( ) checkValue, checkValue, — value. nil Swift (??), , ( ).
,
2 <. 3 // 3
3 <. 2 // 3
, .
subArrayOfMaks
let subArrayOfMaks array2d mask (centerX, centerY) (maskCenterX, maskCenterY) =
.
array2d — ( )
mask — ()
(centerX, centerY) — ,
(maskCenterX, maskCenterY) — . , . , .
upbuilding
array2d —
mask —
(maskCenterX, maskCenterY) —
let upbuilding array2d mask (maskCenterX, maskCenterY) =
// ,
let sub source mask (x, y) (maskCenterX, maskCenterY) =
//
let (x1, x2, y1, y2) = subArrayOfMaks source mask (x, y) (maskCenterX, maskCenterY)
//
source.[y1..y2, x1..x2] <- mask
// ,
let copy = (Matrix.cloneO {values = array2d}).values
//
array2d |> Array2D.iteri (fun y x v -> if v = 1 then sub copy mask (x, y) (maskCenterX, maskCenterY))
//
copy
, .
B S B ⊖ S
"" . , .
( , Figure 1).
Figure 4: B ⊖ S
F#. , F#
// , array2d mask?
let contains array2d mask =
if Matrix.isEquallySized (Matrix.ofArray2D array2d) (Matrix.ofArray2D mask) then
not (array2d
|> Array2D.mapi (fun x y v -> if mask.[x, y ] = 0 then 1
elif mask.[x, y] = v then 1
else 0)
|> Seq.cast<int>
|> Seq.contains 0)
else false
// ,
let erosion array2d mask (maskCenterX, maskCenterY) =
let sub source (dest: int [,]) mask (x, y) (maskCenterX, maskCenterY) =
let (x1, x2, y1, y2) = subArrayOfMaks source mask (x, y) (maskCenterX, maskCenterY)
let subArray2d = source.[y1..y2, x1..x2]
if contains subArray2d mask then
dest.[y, x] <- 1
let copy = (Matrix.cloneO {values = array2d}).values
array2d |> Array2D.iteri (fun y x v -> if v = 1 then sub array2d copy mask (x, y) (maskCenterX, maskCenterY))
copy
, . , , .
.
B S B • S
F#
let closure array2d mask (centerX, centerY) =
let step1 = upbuilding array2d mask (centerX, centerY)
let step2 = erosion step1 mask (centerX, centerY)
step2
Figure 5: B • S
B S B ◦ S
F#
let opening array2d mask (centerX, centerY) =
let step1 = erosion array2d mask (centerX, centerY)
let step2 = upbuilding step1 mask (centerX, centerY)
step2
Figure 6: B ◦ S
, , , . , . , .
. , . , .
Figure 7:
Figure 8:
, , ( , ). ,
Figure 9:
F#
//
let origin = array2D [[0;0;0;0;0;0;0;0;0;0]
[0;0;1;0;0;0;0;0;0;0]
[0;1;1;1;0;0;0;1;0;0]
[0;0;0;0;0;0;0;0;1;0]
[0;0;0;0;1;0;0;0;0;0]
[0;0;0;0;1;1;0;0;1;0]
[0;0;0;1;1;1;1;0;1;0]
[0;0;0;1;0;0;0;0;1;0]
[0;0;0;0;0;0;0;1;1;0]
[0;0;0;0;0;0;0;0;0;0]]
//
let mask = array2D [[1]
[1]
[1]]
//
let marked = Algorithms.markingOfConnectedComponents origin
//
let erosion = Algorithms.erosion origin mask (0, 1)
printfn "origin = \n %A" origin
printfn "marked = \n %A" marked
printfn "erosion =\n %A" erosion
// . ()
let set = erosion |> Seq.cast<int> |> Seq.filter ((<>)0) |> Set.ofSeq
// ,
let copy = (Matrix.cloneO {values = marked}).values
//
erosion
|> Array2D.iteri (fun row col v -> if v = 1 then
//
let label = marked.[row, col]
if not (set.Contains label) then
// ,
marked |> Array2D.iteri (fun row1 col1 v1 -> if v1 = label then copy.[row1, col1] <- 1)
)
printfn "copy =\n %A" copy
origin =
[[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[0; 0; 1; 0; 0; 0; 0; 0; 0; 0]
[0; 1; 1; 1; 0; 0; 0; 1; 0; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 1; 0]
[0; 0; 0; 0; 1; 0; 0; 0; 0; 0]
[0; 0; 0; 0; 1; 1; 0; 0; 1; 0]
[0; 0; 0; 1; 1; 1; 1; 0; 1; 0]
[0; 0; 0; 1; 0; 0; 0; 0; 1; 0]
[0; 0; 0; 0; 0; 0; 0; 1; 1; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]
marked =
[[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[0; 0; 1; 0; 0; 0; 0; 0; 0; 0]
[0; 1; 1; 1; 0; 0; 0; 3; 0; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 4; 0]
[0; 0; 0; 0; 5; 0; 0; 0; 0; 0]
[0; 0; 0; 0; 5; 5; 0; 0; 6; 0]
[0; 0; 0; 5; 5; 5; 5; 0; 6; 0]
[0; 0; 0; 5; 0; 0; 0; 0; 6; 0]
[0; 0; 0; 0; 0; 0; 0; 6; 6; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]
erosion =
[[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; 1; 0; 0; 0; 0; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 1; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 1; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]
copy =
[[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; 1; 0; 0; 0; 0; 0]
[0; 0; 0; 0; 1; 1; 0; 0; 1; 0]
[0; 0; 0; 1; 1; 1; 1; 0; 1; 0]
[0; 0; 0; 1; 0; 0; 0; 0; 1; 0]
[0; 0; 0; 0; 0; 0; 0; 1; 1; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]
, , ,
F#
Figure 10:
A B
Figure 11:
A B
Figure 12:
A
Figure 13:
A B
Figure 13:
F#
//
let union array2d1 array2d2 =
if Matrix.isEquallyArraySized array2d1 array2d2 then
array2d1 |> Array2D.mapi (fun x y v -> v ||| array2d2.[x, y])
else failwith "array2d1 is not equal to array2d2"
//
let intersection array2d1 array2d2 =
if Matrix.isEquallyArraySized array2d1 array2d2 then
array2d1 |> Array2D.mapi (fun x y v -> v &&& array2d2.[x, y])
else failwith "array2d1 is not equal to array2d2"
// ( )
let inverse array2d =
array2d |> Array2D.mapi (fun _ _ v -> v ^^^ 1)
let complement array2d =
inverse array2d
//
let difference array2d1 array2d2 =
if Matrix.isEquallyArraySized array2d1 array2d2 then
array2d1 |> Array2D.mapi (fun x y v -> if v <> array2d2.[x, y] then v else 0)
else failwith "array2d1 is not equal to array2d2"
, . , . .
Figure 14:
Figure 15:
F#
let borderAllocation array2d mask (maskCenterX, maskCenterY) =
let e = erosion array2d mask (maskCenterX, maskCenterY)
let border = difference array2d e
border
. , . , . , , . , . , , .
, , : ,
F#
//
let multyBinImage = array2D [[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;1;1;1;1;0;0]
[1;1;1;1;0;0;0;0;0;1;1;1;1;1;1;0]
[1;1;1;1;0;0;0;0;1;1;1;1;1;1;1;1]
[1;1;1;1;0;0;0;0;1;1;1;1;1;1;1;1]
[1;1;1;1;0;0;0;0;1;1;1;1;1;1;1;1]
[1;1;1;1;0;0;0;0;0;1;1;1;1;1;1;0]
[1;1;1;1;0;0;0;0;0;0;1;1;1;1;0;0]
[1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0]
[1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0]
[1;1;1;1;0;0;1;1;1;0;0;0;0;0;0;0]
[1;1;1;1;0;0;1;1;1;0;0;0;0;0;0;0]
[1;1;1;1;0;0;1;1;1;0;0;0;0;0;0;0]
[1;1;1;1;0;0;0;0;0;0;0;0;0;0;0;0]]
,
//
let markedMultyImages = Algorithms.markingOfConnectedComponents mulyBinImage
printfn "marked = \n %A" markedMultyImages
marked =
[[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; 1; 1; 1; 1; 0; 0]
[2; 2; 2; 2; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 0]
[2; 2; 2; 2; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1]
[2; 2; 2; 2; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1]
[2; 2; 2; 2; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1]
[2; 2; 2; 2; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 0]
[2; 2; 2; 2; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 0; 0]
[2; 2; 2; 2; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[2; 2; 2; 2; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[2; 2; 2; 2; 0; 0; 5; 5; 5; 0; 0; 0; 0; 0; 0; 0]
[2; 2; 2; 2; 0; 0; 5; 5; 5; 0; 0; 0; 0; 0; 0; 0]
[2; 2; 2; 2; 0; 0; 5; 5; 5; 0; 0; 0; 0; 0; 0; 0]
[2; 2; 2; 2; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]
(1, 2, 5)
, — , , .
//
// groups key - , value - ,
let groups = Dictionary<int, (int*int) list>()
markedMultyImages
|> Array2D.iteri (fun row col v -> if v <> 0 then
if not (groups.ContainsKey(v)) then
groups.Add(v, [row, col])
else
groups.[v] <- (row, col)::groups.[v])
printfn "groups = \n %A" groups
groups =
seq
[[1, [(9, 13); (9, 12); (9, 11); ... ]];
[2, [(15, 3); (15, 2); (15, 1); ... ]];
[5, [(14, 8); (14, 7); (14, 6); ... ]]]
- ( )
- ( )
- ( )
let mapAreas = groups
|> Seq.map (|KeyValue|)
|> Map.ofSeq
//
let areas = mapAreas
|> Map.map (fun k v -> v |> List.length)
printfn "areas =\n %A" areas
areas — , — , —
areas =
map [(1, 44); (2, 48); (5, 9)]
, , 1 44 , 2 — 48 , 5 — 9 .
, , , 1 , . , . , — ,
//
let subarrays = mapAreas
|> Map.map (fun k v ->
let minRow = v |> List.map (fst) |> List.min
let maxRow = v |> List.map (fst) |> List.max
let minCol = v |> List.map (snd) |> List.min
let maxCol = v |> List.map (snd) |> List.max
let dimRow = maxRow - minRow + 2 + 1 // add two zeros on left and right sides
let dimCol = maxCol - minCol + 2 + 1
let array2d = Array2D.create dimRow dimCol 0
v |> List.iter (fun elem -> (array2d.[(fst elem) - minRow + 1, (snd elem) - minCol + 1] <- multyBinImage.[fst elem, snd elem]))
array2d
)
printfn "subarrays =\n %A" subarrays
subarrays =
map
[(1, [[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[0; 0; 0; 1; 1; 1; 1; 0; 0; 0]
[0; 0; 1; 1; 1; 1; 1; 1; 0; 0]
[0; 1; 1; 1; 1; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 1; 1; 1; 1; 0]
[0; 0; 1; 1; 1; 1; 1; 1; 0; 0]
[0; 0; 0; 1; 1; 1; 1; 0; 0; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]);
(2, [[0; 0; 0; 0; 0; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 0; 0; 0; 0; 0]]);
(5, [[0; 0; 0; 0; 0]
[0; 1; 1; 1; 0]
[0; 1; 1; 1; 0]
[0; 1; 1; 1; 0]
[0; 0; 0; 0; 0]])]
. — .
//
let erosionMaks = array2D [[0;1;0]
[1;1;1]
[0;1;0]]
let borders = subarrays
|> Map.map (fun label array2d -> Algorithms.borderAllocation array2d erosionMaks (1, 1))
let bordersLength = borders |> Map.map (fun label elem -> elem |> Seq.cast<int> |> Seq.filter ((<>)0) |> Seq.length)
printfn "borders =\n %A" borders
printfn "borders length =\n %A" bordersLength
borders =
map
[(1, [[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
[0; 0; 0; 1; 1; 1; 1; 0; 0; 0]
[0; 0; 1; 0; 0; 0; 0; 1; 0; 0]
[0; 1; 0; 0; 0; 0; 0; 0; 1; 0]
[0; 1; 0; 0; 0; 0; 0; 0; 1; 0]
[0; 1; 0; 0; 0; 0; 0; 0; 1; 0]
[0; 0; 1; 0; 0; 0; 0; 1; 0; 0]
[0; 0; 0; 1; 1; 1; 1; 0; 0; 0]
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0]]);
(2, [[0; 0; 0; 0; 0; 0]
[0; 1; 1; 1; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 0; 0; 1; 0]
[0; 1; 1; 1; 1; 0]
[0; 0; 0; 0; 0; 0]]);
(5, [[0; 0; 0; 0; 0]
[0; 1; 1; 1; 0]
[0; 1; 0; 1; 0]
[0; 1; 1; 1; 0]
[0; 0; 0; 0; 0]])]
borders length =
map [(1, 18); (2, 28); (5, 8)]
1 18 , 2 — 28 5 — 8 .
.
//
let centers = borders
|> Map.map (fun k v ->
let centerRow = v |> Array2D.mapi (fun r _ _ -> float r) |> Seq.cast<float> |> Seq.average // list.average requires float
let centerCol = v |> Array2D.mapi (fun _ c _ -> float c) |> Seq.cast<float> |> Seq.average
(int centerCol, int centerRow)
)
printfn "centers =\n %A" centers
centers =
map [(1, (4, 4)); (2, (2, 6)); (5, (2, 2))]
.
C=μRσR
μR —
σR —
μR=1K∑k=1K−1||(rk,ck)−(r¯,c¯)||
(r_k, c_k) —
(r, c) —
//
let diff point1 point2 =
let square x = x * x
let s1 = square ((fst point1) - (fst point2))
let s2 = square ((snd point1) - (snd point2))
sqrt(double (s1 + s2))
μR .
// , key - , value - (double)
let mr = borders
|> Map.map (fun label v ->
let aver = v
|> Array2D.mapi (fun r c v -> diff (r, c) centers.[label])
|> Seq.cast<double>
|> Seq.sum
aver / (double v.Length)
)
σR
σR=(1K∑k=1K−1[||(rk,ck)−(r¯,c¯)||−μR]2)1/2
let qr = borders
|> Map.map (fun label v ->
let aver = v
|> Array2D.mapi (fun r c v ->
let t1 = diff (r, c) centers.[label]
let t2 = (t1 - mr.[label]) * (t1 - mr.[label])
t2
)
|> Seq.cast<double>
|> Seq.sum
|> sqrt
aver / (double v.Length)
)
// . ,
let roundness = mr |> Map.map (fun label v -> v / qr.[label])
printfn "roundness =\n %A" roundness
roundness =
map [(1, 25.06054796); (2, 20.37134197); (5, 13.43281947)]
, 1 . .
() () F#. . , . , F# , . , , F# . , . .
يمكن العثور على الخوارزميات نفسها التي تمت مناقشتها في المقالة هنا. هناك ، في مستودع الاختبارات ، هناك تنفيذ للجزء الأخير من المقالة ، حيث يتم البحث عن معظم الأشياء الدائرية داخل الصورة.
خوارزميات مورفولوجيا ثنائية