how to find a cluster - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>CS - 计算机科学

how to find a cluster

how to find a cluster# CS - 计算机科学

e*f2009-02-23 08:02

1 楼

I have a question and hope someone smart here can help me out.
I have a binary 2-dimensional image, say 16 by 16 pixels. The pixel values
are either 0 or 1 and are randomly distributed. We define a cluster as: for
those non-zero pixels, if they share at least one side with each other, they
form a cluster of connectivity-1. What is the simple algorithm to search
for these clusters and find the largest one (larget number of pixels in one
cluster)?
Your help is highly appreciated!

e*f2009-02-23 08:02

2 楼

t*a2009-02-23 08:02

3 楼

Your problem is officially called "connected component labeling", just
google
it. the easiest algorithm is called the two-pass union-find algorithm.

for
they
one

【在 e****f 的大作中提到】

: I have a question and hope someone smart here can help me out.
: I have a binary 2-dimensional image, say 16 by 16 pixels. The pixel values
: are either 0 or 1 and are randomly distributed. We define a cluster as: for
: those non-zero pixels, if they share at least one side with each other, they
: form a cluster of connectivity-1. What is the simple algorithm to search
: for these clusters and find the largest one (larget number of pixels in one
: cluster)?
: Your help is highly appreciated!

e*f2009-02-23 08:02

4 楼

thanks, already found it.