79
aylanadan diagonal va gorizontal yo‗nalishdagi piksellargacha bo‗lgan masofani
kvadratlar farqini tekshiramiz:
= [(x
i
+ 1)
2
+ (y
y
)
2
- R
2
] – [(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
]
0
bo‗lganda aylanadan diognal pikselgacha bo‗lgan masofa (
m
D
) dan katta.
Teskarisi, agar
0
bo‗lganda gorizontalgacha bo‗lgan masofa (
m
H
) katta.
Shunday qilib,
0
bo‗lganda
m
H
ni
(x
i
+ 1, u
i
)
da tanlaymiz.
0
bo‗lganda
m
D
ni
(x
i
+ 1, u
i
- 1)
da tanlaymiz.
= 0
bo‗lganda aylanadan ikki pikselgacha
bo‗lgan masofa bir xil gorizontal qadamni tanlaymiz.
miqdorini baholash uchun
zarur bo‗lgan hisoblar sonini, agar birinchi holatni e‘tiborga olsak,
kamaytirish
mumkin.
(x
i
+ 1)
2
+ (y
i
)
2
- R
2
0
(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
0
Shunday qilib, diagonal piksel
(x
i
+ 1, u
i
- 1)
har doim aylana ichida yotadi,
gorizontal piksel
(x
i
+ 1, u
i
)
esa aylana tashqarisida. Shunday qilib,
ni
quyidagi
formula bo‗yicha hisoblash mumkin.
= (x
i
+ 1)
2
+ (y
i
)
2
- R
2
+ (x
i
+ 1)
2
+ (y
i
+ 1)
2
- R
2
2y
i
+ 1
qo‗shish
va ayirish yordamida
(y
i
)
2
qatnashchilarni to‗la kvadratgacha
to‗ldirish quyidagini beradi.
= 2 [(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
] + 2y
i
- 1
Kvadrat qavslar ichida aniqlanishi bo‗yicha
i
va uning qo‗yiluvchilari turadi.
= 2 (
i
+y
i
)- 1
Ifodani sezilarli darajada qisqartiradi.
Ikkinchi holatni ko‗rib chiqamiz va bu yerda
(x
i
+ 1, u
i
)
gorizontal piksel
tanlanishi zarurligini e‘tiborga olamiz. Shunday
qilib u monoton kamayuvchi
funksiya.
komponentini tekshirish ko‗rsatadiki
(x
i
+ 1)
2
+ (y
i
)
2
- R
2
0
(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
0
80
Ikkinchi holatda gorizontal
(x
i
+ 1, u
i
)
va diagonal
(x
i
+ 1, u
i
- 1)
piksellar
aylana ichida yotadi. Shunday qilib
0
va xuddi 1 holat kabi shu kriteriyadan
foydalanilganda
(x
i
+ 1, u
i
)
piksel tanlanadi.
Agar
i
0
bo‗lsa,
u holda
(x
i
+ 1, u
i
- 1)
diagonal nuqta aylana tashqarisida
joylashadi. Bu holatlardan ko‗rinadiki, yoki piksel
(x
i
+ 1, u
i
- 1) m
D
yoki
(x
i
,y
i
- 1) m
V
piksellar tanlanishi shart. Aylanadan diagonal
m
D
va vertikal
m
V
piksellargacha
masofani kvadratlari orasidagi farqni tekshirish orqali kriteriya tanlovini olish
mumkin.
1
= [(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
] – [(x
i
)
2
+ (y
i
- 1)
2
- R
2
]
1
0
bo‗lganda aylanadan vertikal pikselgacha
(x
i
,y
i
- 1)
bo‗lgan masofa katta
va
(x
i
+ 1, u
i
- 1) m
D
piksellarga diagonal qadamni tanlash kerak bo‗ladi.
Teskari
holatda
1
0
aylanadan diagonal pikselgacha bo‗lgan masofa katta va
(x
i
,y
i
- 1)
pikselga vertikal harakatni tanlash kerak. Shunday qilib,
1
0
bo‗lganda
(x
i
+ 1, u
i
- 1)
da
m
D
ni tanlaymiz.
1
0
bo‗lganda
(x
i
,y
i
- 1)
da
m
V
ni tanlaymiz.
1
= 0
bo‗lgan holatda masofalar teng va diagonal qadam tanlangan.
1
komponentlarini tekshirish ko‗rsatdiki
(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
0
(x
i
)
2
+ (y
i
- 1)
2
- R
2
0
Shunday qilib, 3 holatda diagonal piksel
(x
i
+ 1, u
i
- 1)
aylanadan tashqarida
joylashadi, vertikal piksel
(x
i
,y
i
- 1)
aylana ichida yotadi. Bu
1
ni quyidagi
ko‗rinishda yozish imkonini beradi.
1
= (x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
+ (x
i
)
2
+ (y
i
- 1)
2
- R
2
2x
i
+ 1
ni qo‗shish va ayirish yordamida
(x
i
)
2
qatnashchilarini to‗la
kvadratgacha to‗ldirish quyidagini
1
= 2 [(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
] + 2x
i
- 1
i
aniqlovchidan foydalanish ifodani quyidagi ko‗rinishga keltiradi.
1
= 2 (
i
- 1) - 1
81
4 holatga qarab
(x
i
,y
i
- 1)
vertikal pikselni tanlash lozim ekanligini e‘tiborga
olamiz, shunday ekan
x
funksiya o‗sganda
u
funksiya monoton kamayuvchi funksiya
hisoblanadi.
4 holat uchun
1
komponentlarini tekshirish quyidagini ko‗rsatadi
(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
0
(x
i
)
2
+ (y
i
- 1)
2
- R
2
0
kelib chiqadiki ikala piksel ham aylanadan tashqarida joylashgan.
Shunday qilib,
1
0
va 3 holat uchun qayta ishlangan kriteriyadan
foydalanilganda
m
V
va to‗g‗ri tanlov amalga oshiriladi.
Diagonal piksel
(x
i
+ 1, u
i
- 1)
aylanada yotganda uchraydigan 5 holatni
tekshirish qoldi.
komponentlarini tekshirish shuni ko‗rsatdiki
(x
i
+ 1)
2
+ (y
i
)
2
- R
2
0
(x
i
+ 1)
2
+ (i
i
- 1)
2
- R
2
= 0
Shunday qilib,
1
0
va
(x
i
+ 1, u
i
- 1)
diagonal piksel tanlanadi.
Logik usul
bilan
komponentini baholaymiz.
(x
i
+ 1)
2
+ (y
i
- 1)
2
- R
2
= 0
(x
i
)
2
+ (y
i
- 1)
2
- R
2
0
va
1
0
ga
(x
i
+ 1, u
i
- 1)
diagonal qadamni to‗g‗ri tanlash sharti hisoblanadi.
Shunday qilib
i
= 0
holat,
i
0
yoki
i
0
holatlar kabi bita kriteriyaga bo‗ysunadi.
Olingan natijalardan xulosa chiqaramiz:
i
0
1
0
bo‗lganda
(x
i
+ 1, u
i
)
m
N
pikselni tanlaymiz.
1
0
bo‗lganda
(x
i
+ 1, y
i
- 1)
m
D
pikselni tanlaymiz.
i
0
1
0
bo‗lganda
(x
i
+ 1, u
i
- 1)
m
D
pikselni tanlaymiz.
1
0
bo‗lganda
(x
i
, y
i
- 1)
m
V
pikselni tanlaymiz.
i
0
bo‗lganda
(x
i
+ 1, u
i
- 1)
m
o
pikselni tanlaymiz.
82
Birinchi navbatda
(x
i
+ 1, u
i
)
piksel uchun
m
N
gorizontal qadamni qarab
chiqamiz. Buni pikselni
(i + 1)
yangi holatni deb belgilaymiz.
Shunda yangi piksel
koordinatasi va
i
qiymati quyidagiga teng:
x
i + 1
= x
i+ 1
u
i + 1
= u
i
i + 1
= (x
i+ 1
+ 1)
2
+ (u
i+ 1
- 1)
2
- R
2
= (x
i+ 1
)
2
+ 2x
i+ 1
+ 1 + u
i
- 1)
2
- R
2
=
= (x
i
+ 1)
2
+ (u
i
- 1)
2
- R
2
+ 2x
i+ 1
- 1=
i
+ 2x
i+ 1
- 1.
(x
i
+ 1, u
i
- 1)
pikselga
m
D
qadam uchun
I
qiymati va yangi piksel koordinatasi
quyidagicha:
x
i + 1
= x
i
+ 1
u
i + 1
= u
i
- 1
i + 1
=
i
+ 2x
i + 1
- 2u
i+ 1
+ 2
Xuddi shunday
(x
i
, y
i
- 1)
ga
m
V
qadam uchun ham
x
i + 1
= x
i
u
i + 1
= u
i
- 1
i + 1
=
i
- 2u
i+ 1
+ 1.
Brezemxem algoritmini aylana uchun psevokodda qo‗llash pastda keltirilgan
Dostları ilə paylaş: