Record Details

Fast algorithms for binary cross-correlation

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Fast algorithms for binary cross-correlation
 
Creator MUKHERJI, S
 
Description Cross-correlation is widely used to match images. Cross-correlation of windows where pixels have binary values is necessary when thresholded sign-of-laplacian images are matched. Nishihara proposed that the sign of the laplacian of an image be used as a characteristic (that is robust to illumination changes and noise) to match images. We have reduced the number of multiplications required in the computation of the laplacian by half by making use of the symmetry of the convolution masks. Thresholding the sign of the laplacian of an image results in a binary image and image matching can then be done by matching corresponding windows of the binary images using cross-correlation. Leberl proposed fast algorithms for computing binary cross-correlation. We propose a fast implementation of his best algorithm. We also propose, in this paper, a bit-based algorithm which makes use of the fact that the binary data in the windows can be represented by bits. The algorithm packs the bits into integer variables and then uses the logical operations to identify matching bits in the windows. This very packing of bits into integer variables (that enables us to use the logical operations, hence speeding up the process) renders the step of counting the number of matching pixels difficult. This step, then, is the bottleneck in the algorithm. We solve this problem of counting the number of matching pixels by an algebraic property. The bit-method is exceedingly simple and is most efficient when the number of bits is close to multiples of 32. Binary cross-correlation can also be computed and, hence, speeded up by the FFT. We conclude the paper by comparing the bit-based method, Leberl's algorithm and the FFT-based method for computing binary cross-correlation.
 
Publisher IEEE
 
Date 2011-10-26T16:49:02Z
2011-12-15T09:12:25Z
2011-10-26T16:49:02Z
2011-12-15T09:12:25Z
2005
 
Type Proceedings Paper
 
Identifier IGARSS 2005: IEEE International Geoscience and Remote Sensing Symposium, Vols 1-8, Proceedings,340-343
0-7803-9050-4
http://dspace.library.iitb.ac.in/xmlui/handle/10054/16066
http://hdl.handle.net/100/2657
 
Source 25th IEEE International Geoscience and Remote Sensing Symposium (IGARSS 2005),Seoul, SOUTH KOREA,JUL 25-29, 2005
 
Language English