Synopsis:
This paper presents three implementations of image retrieval, all done in python, where the first two are based on histogram comparisons and the hashing method is based on pixel distribution.
The retrieval method is as follows: import the image library as the retrieval range in advance, give the images to be retrieved, compare them with the images in the library, derive all the similarities and then sort them so that the retrieval result is the images with the highest to the lowest similarity. Since the project also contains other parts such as Qt interface classes, trigger functions, etc., only the code of key functions is given in this document.
Development system: MacOS
Implementation: Qt + Python
Method 1: Customized Histogram Comparison Algorithm
a) Basic idea
Iterate over the image pixel points, extract the R\G\B values and perform the corresponding counts to obtain the original histogram, but because the range of 0-255 is too large, so the statistics of each pixel value are small, so respectively, the 256 pixel values of R\G\B are mapped to a total of 32 pixel values of 0-31 to narrow the range of pixel values from 256*3 to 32*3. The data structure used to record the pixel values are One dimensional array, the 1st to 32nd values are the pixel histogram of R, the 33rd to 64th values are the pixel statistics of G, and the 65th to 96th values are the pixel statistics of B. After obtaining the histogram, the similarity between the histogram of the image to be retrieved and the histogram of the image in the image library is calculated.
b) Specific realization
Functions used:
- split_Img()
- calc_Hist(img)
- calc_Similar(h1,h2)
- calc_Similar_Split(h1,h2)
Iterate over the pixel points of the image to calculate the histogram: calc_Hist(img)
Two ways were tried, the first was to call getpixel() one by one when traversing the image to get the values of R,G,B, but found that the speed of this way is too slow. The second one uses memory reading, using load() function to read the pixel values of the image at once and then traverse the pixel values, this method is faster than extracting them one by one.
#Statistical histogram, use load() to load the pixelpix of the image, then read the R\G\B value of each pixel point separately for statistics (0-255 respectively)
# Project the statistics of 256 color values to 32, return the array of statistics after R\G\B projection, a total of 32 * 3 = 96 elements
def calc_Hist(img):
'''
#120 images, 4.43s
w,h =
pix = () #Load the image, pix are stored in pixels.
calcR = [0 for i in range(0,32)]
calcG = [0 for i in range(0,32)]
calcB = [0 for i in range(0,32)]
for i in range(0,w):
for j in range(0,h):
(r,g,b) = pix[i,j]
#print (r,g,b)
calcR[r/8] += 1
calcG[g/8] += 1
calcB[b/8] += 1
(calcB)
(calcG)
return calcR
'''
#120 charts, 3.49s
w,h =
pix = () #Load the image, pix are stored in pixels.
calcR = [0 for i in range(0,256)]
calcG = [0 for i in range(0,256)]
calcB = [0 for i in range(0,256)]
for i in range(0,w):
for j in range(0,h):
(r,g,b) = pix[i,j]
#print (r,g,b)
calcR[r] += 1
calcG[g] += 1
calcB[b] += 1
(calcB)
(calcG) #256*3
#calc holds the final result, 32*3
calc = [0 for i in range(0,96)]
step = 0 Subscript of #calc, 0~95
start = 0 # Start position of each count
while step < 96:
for i in range(start,start+8): #8 values for 1 group, statistical values are added, eg: color values of 0 ~ 7 statistical values are all converted to color values of 0 statistical values
calc[step] += calcR[i]
start = start+8
step += 1
#print calc
return calc
Histogram comparison calc_Similar(h1,h2)
The formula used is:
Where N is the number of color levels, the closer Sim is to 1 the more similar the two images are.
c) Problems and improvements
After simply implementing the histogram comparison, the retrieved results are not good and the error is large compared to the expectation. To analyze the reason, the histogram comparison mainly relies on the color statistics of the whole image for comparison, and the position of the pixels is not well documented, thus causing misjudgment.
At the same time add calc_Similar_Split(h1,h2) function to join the part of the chunk comparison, the calculation method is: call calc_Similar(h1,h2) for each small chunk, accumulate the calculation results, and finally divide it by 16 to get the average value.
Tests found significant improvement in results, based on color similarity while retaining shape information.
function is as follows:
# The function is used to unify the image size of 256 * 256, and split into 16 blocks, the return value is an array of 16 local image handles
def split_Img(img, size = (64,64)):
img = ((256,256)).convert('RGB')
w,h =
sw,sh = size
return [((i,j,i+sw,j+sh)).copy() for i in xrange(0,w,sw) for j in xrange(0,h,sh)]
# Calculate the similarity between two histograms, h1 and h2 are histograms, zip denotes synchronized traversal
def calc_Similar(h1,h2):
return sum(1 - (0 if g==s else float(abs(g-s))/max(g,s)) for g,s in zip(h1,h2)) / len(h1)
Method 2: Histogram comparison algorithm implementation of openCV library
The openCV open source library has integrated histogram extraction, histogram equalization and histogram comparison functions, which are easy to call. In order to further understand the various types of implementation methods for histogram comparison, experiments were re-conducted using openCV.
a) Basic idea
Histograms are extracted and equalized for each image in the gallery, then the cv library function is called to compare the histograms and the results are sorted and displayed.
b) Specific realization
First call () to read the image, then call () to compute the histogram, () to equalize and then enter the comparison phase, call (), to compare the histogram difference between the image to be retrieved and the image of the photo gallery, and then call DisplayTotalPics() to display it.
The key code is as follows:
results = {} # Recorded results
reverse = True The #correlation/intersection method reverses to true, the other two to false.
imgCV = (('utf-8'))
# for images to be matched
testHist = ([imgCV],[0,1,2],None,[8,8,8],[0,256,0,256,0,256])
# Extract histogram
testHist = (testHist,testHist,0,255,cv2.NORM_MINMAX).flatten()
# Equalization
#Calculate the histogram difference with other images, the INTERSECTION method works better!
for (k, hist) in self.index_cv.items():
#self.index_cv holds the histogram information of the images in the gallery
d = (testHist,hist, .CV_COMP_INTERSECT)
results[k] = d
# Sort the results with v, the d above, as the keyword
results = sorted([(v, k) for (k, v) in ()], reverse = reverse)
end = ()
print 'OpenCV Time:'
print end-start
(results)
c) Problems and solutions
There are 4 comparison methods provided in the compareHist function in openCV:
1. Correlation coefficient criterion (method=CV_COMP_CORREL) The larger the value, the higher the correlation, maximum value 1, minimum value 0
2. Criteria for chi-square coefficient (method=CV_COMP_CHISQR) The smaller the value, the higher the correlation, no upper limit, minimum value 0
3. Intersection coefficient criterion (method=CV_COMP_INTERSECT) value is large, the higher the correlation, maximum 9.455319, minimum 0
4. Criteria for Bachmann's coefficient (method=CV_COMP_BHATTACHARYYA) Smaller the value, the higher the correlation, the maximum value of 1, the minimum value of 0
Tested and selected method = .CV_COMP_INTERSECT
In addition, the method is fast and based entirely on the color distribution of the image, but in some cases the accuracy is not very high.
Method 3: Average Hash Comparison Algorithm Implementation
Functions used: getKey(),getCode(),cmpCode()
a) Basic idea
The comparison algorithm for average hash value is based on pixel distribution and the comparison is done on image fingerprints of gray scale maps. The image fingerprints are calculated by comparing the pixel values and the average pixel value of each map, then the Hamming distance between the image fingerprints is calculated and sorted to get the similar images.
b) Specific realization
The specific method is: calculate the average value of all pixel points of the image after grayscale processing, and then traverse each pixel of the grayscale image, if it is greater than the average value recorded as 1, otherwise it is 0. This step is completed by defining the function getCode(img). Then calculate the Hamming distance between the codes, i.e., the number of steps required to change a set of binary data into another set of data, the smaller the Hamming distance, the higher the similarity of the image fingerprints. Calculating the Hamming distance can be done by simple traversal and counting, the function is compCode(code1,code2), where code1 and code2 are the image fingerprints obtained by getCode.
The key function code is as follows:
# Get key values (i.e., Hamming distance) when sorting
def getKey(x):
return int(x[1])
# 2-value "fingerprints" are obtained from the grayscale map to calculate the Hamming distance
def getCode(img):
w,h =
pixel = []
for i in range(0,w):
for j in range(0,h):
pixel_value = ((i,j))
(pixel_value) #Join the pixel array
avg = sum(pixel)/len(pixel) # Calculate the pixel average
cp = [] # Binary arrays
for px in pixel:
if px > avg:
(1)
else:
(0)
return cp
# Calculate the Hamming distance between two codes
def compCode(code1,code2):
num = 0
for index in range(0,len(code1)):
if code1[index] != code2[index]:
num+=1
#print num
#print '\n'
return num
c) Problems and optimization
We found that the retrieval speed of this method is slow when there is a large amount of data, so we store the image fingerprint as an attribute of the image as well, which is calculated when importFolder, to avoid redundant repetitive calculations in subsequent operations.
This is the entire content of this article.