A NEW FM SCREENING METHOD TO GENERATE CLUSTER-DOT BINARY IMAGES USING THE LOCAL EXHAUSTIVE SEARCH WITH FPGA ACCELERATION
Yasuaki Ito, Koji Nakano · International Journal of Foundations of Computer Science · 2008
Screening is an important task to convert a continuous-tone image into a binary image with pure black and white pixels. The main contribution of this paper is to show a new algorithm for cluster-dot screening using a local exhaustive search. Our new algorithm generates 2-cluster, 3-cluster, and 4-cluster binary images, in which all dots have at least 2, 3, and 4 pixels, respectively. The key idea of our new screening method is to repeat a local exhaustive search that finds the best binary pattern in small windows of size k × k in a binary image. The experimental results show that the local exhaustive search produces high quality and sharp cluster-dot binary images. We also present an hardware algorithm to accelerate the computation. Our hardware algorithm for a round of the local exhaustive search runs O(k2) clock cycles while the software implementation runs in O(2k2 w2) time, where (2w + 1) × (2w + 1) is the size of Gaussian filter. Thus, from theoretical point of view, our hardware algorithm achieves a speedup factor of O(w2). To show that our hardware algorithm is practically fast, we have implemented it on an FPGA. Our hardware algorithm achieved a speedup factor of up to 229 over the software implementation.