xla-lqn-tuan 9.pdf

8/10/2019 XLA-LQN-TUAN 9.pdf

1/31

X l nh s v video s nng caoTun9: Phn onnh

TS. L QucNgc


2/31

Ni dung

10.1. Pht biubi ton10.2. Region growing

10.3. K-means

10.4. HAC (Hierarchical Agglomerative Clustering)

2TS. L Quc Ngc


3/31

10.1. Pht biu bi ton

Giscnphn onnh thnh N vngCnxc nhlutphn on sao cho

3TS. L Quc Ngc

NRRR ,...,, 21I

)(RP

jiFalseRRPNiTrueRP

jiRR

RI

ji

i

ji

N

ii

,)(,...,2,1,)(

,

1


4/31

10.2. Region growing

Nguyn lGeometrical proximity + homogeneity -> connected

image regions.

4TS. L Quc Ngc


5/31


Phngphp- Khinguntmtsimmm, lan tankhi phton bnh.

-hinthcviclan tacnxc nh.immm

. Lutlan tavvtr

. Lutkimtra tnh thunnhtcavng sau mibclan ta.

5TS. L Quc Ngc


6/31


7/31


Phngphp. Lutlan tavvtr

Lan tatheo ln cn8.

7TS. L Quc Ngc


8/31


Phngphp. Lutkim tra tnh thunnhtcavng sau mibclan ta.

Tibcthk, vimivng

Kimtra cc pixels chacphn lptrong ln cn

8 camipixel thucbin cavng.

Nu th ktnp

pixel vo vng

8TS. L Quc Ngc

NiR ki ,...,2,1,)(

TrueyxbRP kiki )}),({( )()( ),()( yxb ki

)(kiR


9/31


10/31


Phngphp

. Lutkim tra tnh thunnhtcavng sau mibclan ta.

10TS. L Quc Ngc

2/1

)()()(

)(2)()()1(

)()()()1(

))(),())(1)(/()((

)()())[1)(/(1()(

)]()(),())[1)(/(1()(

ki

ki

ki

ki

ki

kik

i

ki

ki

ki

ki

RmyxfRNRN

RRNRNR

RmRNyxfRNRm


11/31


Phngphp

. Lutmerge vng.

11TS. L Quc Ngc

)(|)()(|

)(|)()(|

)1()1()1(

)1()1()1(

''

'

k

i

k

i

ki

ki

k

i

ki

RkRmRm

RkRmRm


12/31

10.3. K-means

Nguyn lhomogeneity -> image regions.

12TS. L Quc Ngc


13/31

Bahadir K. Gunturk EE 7730 - Image Analysis I 13

10.3. K-means

1. Partition the data points into K clusters randomly. Find thecentroids of each cluster.

2. For each data point:

Calculate the distance from the data point to each cluster.

Assign the data point to the closest cluster.

3. Recompute the centroid of each cluster.

4. Repeat steps 2 and 3 until there is no further change in the

assignment of data points (or in the centroids).


14/31

14

10.3. K-means


15/31

15

10.3. K-means


16/31

16

10.3. K-means


17/31

17

10.3. K-means


18/31

18

10.3. K-means


19/31


10.3. K-means


20/31


10.3. K-means


21/31

21

10.3. K-means


22/31

22

10.3. K-means

RGB vector

xj

i

2

jelements of i'th cluster

iclusters

K-means clustering minimizes


23/31

Bahadir

K.Gunturk

EE 7730 - Image Analysis I 23

10.3. K-means

Example

Original K=5 K=11


24/31

10.3. K-means

Phngphp

24TS. L Quc Ngc

changeslongerno

membershipclusterortlysignificanchangenotdoesUntil

||

:functionerrorheComputer t

|C|/thatso,Cincurrently

samplesallofcentroidthetoprototypethee Updat

dok},{1,...,jwhere,Cclustereach For

prototypenearestwithCclustertoAssign

do

n},{1,...,lwhere,orinput vecteach For

Repeat

prototypewithassociatedisCclusterEach

n}{1,...,lk},{1,...,j,thatsuch),...,(sprototype

()

1 C

2

jCj

j

**j

j

1

j

j

E

wiE

iw

w

wi

i

w

iwwwkInitialize

meansKFunction

k

j i

jl

i lj

j

jl

l

j

ljk

l

l


25/31

10.4. HAC

Nguyn l

homogeneity -> image regions.

25TS. L Quc Ngc


26/31

10.4. HAC

26TS. L Quc Ngc


27/31

10.4. HAC

27TS. L Quc Ngc


28/31

10.4. HAC

Phng

php

28TS. L Quc Ngc


29/31

10.4. HACPhngphp

29TS. L Quc Ngc


30/31

10.4. HACPhngphp

30TS. L Quc Ngc


31/31

10.4. HACPhngphp

31TS. L Quc Ngc

xla-lqn-tuan 9.pdf

Documents