In-place Algorithm for Erasing a Connected Component in a Binary Image
In-place Algorithm for Erasing a Connected Component in a Binary Image
复制标题
用于擦除二进制图像中连通分量的就地算法
DOI：
10.1007/s00224-011-9335-6
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
Tetsuo Asano
中科院分区：
文献类型：
--
作者：
Yuki Sakai;Akira Uchiyama;Hirozumi Yamaguchi and Teruo Higashino;Tetsuo Asano
去除给定二值图像中的噪声是一种常见的操作。该操作的另一个概括是通过反转组件中的像素值来擦除任意指定的组件。本文表明，这种操作可以不使用任何数据结构，如堆栈或队列，或者更准确地说，对于由m个像素组成的分量，只使用恒定的额外存储器(对于n个像素的图像，由恒定数量的字组成的0(Logn)位的字)Ino(Mlogm)时间。这是一种就地算法，但图像矩阵不能用作工作空间，因为它的每个像素只有一位。每当我们翻转目标组件中的像素值时，组件形状也会变形，这会带来一些困难。我们的恒定工作空间算法的主要思想是使组件变形，从而保持其连通性。
Removing noise in a given binary image is a common operation. A generalization of the operation is to erase an arbitrarily specified component by reversing pixel values in the component. This paper shows that this operation can be done without using any data structure like a stack or queue, or more exactly using only constant extra memory (consisting of a constant number of words ofO(logn) bits for an image ofnpixels) inO(mlogm) time for a component consisting ofmpixels. This is an in-place algorithm, but the image matrix cannot be used as work space since it has just one bit for each pixel. Whenever we flip a pixel value in a target component, the component shape is also deformed, which causes some difficulty. The main idea for our constant work space algorithm is to deform a component so that its connectivity is preserved.
登录
查看更多内容
寻找最近的较大邻居
DOI：
10.1007/978-3-642-03456-5_17
发表时间：
2009
期刊：
--
影响因子：
--
作者：
T. Asano;S. Bereg;D. Kirkpatrick
通讯作者：
D. Kirkpatrick
简单遍历细分，无需额外存储
DOI：
10.1145/237218.237408
发表时间：
1996
期刊：
Int. J. Geogr. Inf. Sci.
影响因子：
--
作者：
M. D. Berg;M. V. Kreveld;R. V. Oostrum;M. Overmars
通讯作者：
M. Overmars
一种无需额外存储的改进细分遍历算法
DOI：
10.1007/3-540-40996-3_38
发表时间：
2000
期刊：
--
影响因子：
--
作者：
P. Bose;Pat Morin
通讯作者：
Pat Morin
给定角度的恒定工作空间图像扫描
DOI：
--
发表时间：
2011
期刊：
Interdisciplinary Information Sciences
影响因子：
--
作者：
伊佐田百合子;井垣伸子;山川茂孝;仲川勇二;T.Asano
通讯作者：
T.Asano
用于连接组件标记的恒定工作空间算法
DOI：
--
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Asano Tetsuo;Tanaka Hiroshi
通讯作者：
Tanaka Hiroshi