We made such a requirement in the front-end time. The designer designed the theme template through Photoshop software, and then we parsed the layer information in the psd file through the program, such as decorative pictures, text boxes, picture boxes, background pictures, etc. (this may be Some layer tags will be involved). For information on how to parse psd files, please refer to the article: /js-parse-psd.html. You can also find some common psds in the article /psd-js-common-cases.html. Solutions to pitfalls in the use of js.
Back to the topic, for picture boxes and text boxes, since the later content is user-defined, we only need to generate corresponding elements to carry these elements, but for backgrounds and stickers, we need to actually upload them to Our system will be used directly later. As a general practice, we will definitely upload the parsed background and sticker images directly. However, the same type of theme may use the same background and sticker multiple times. If we don’t do anything Processing, there will be many duplicate backgrounds and stickers in the later system that are actually the same as the pictures. Here we need to do the deduplication operation. To deduplicate, we need to calculate the similarity of the pictures. Many people may say that this is the work of the back end, and it is different from the front end. It doesn’t matter. In fact, it’s not the case. Let’s analyze the problems that will arise if the backend directly removes duplicates.
1. Every time you upload a sticker and material, you need to go to the library and compare them with the existing materials. This calculation is very large, and the impact on the entire upload is disastrous, and the experience is hugely poor.
2. The logic of uploading and deduplication is coupled together, which is not very reasonable for the backend.
3. Since the calculation amount of deduplication is very large, it has a considerable impact on the load of the server.
In the end, we chose to generate the similarity hash (actually it should be the feature value) on the front end. We did not choose to directly remove duplicates because each import was independent. We had no supervisor and could not compare it with the materials in the existing library. So how to generate the feature values of the image?
Go to Du Niang to search for image similarity algorithms. The most mentioned and relatively simple one is the perceptual hash algorithm. Its principle is to reduce the image, usually 8X8, and then obtain the fingerprint based on the average grayscale of 64 pixels. This This method is relatively simple and works well in most cases, but the probability of misjudgment is very high. There are a lot of transparent areas in PNG-like images. This algorithm has a greater probability of misjudgment, and the large image is reduced to a very small size. A lot of details will be lost. Later, we implemented another algorithm by referring to the basic principles of this algorithm. How to do it?
First we also need to reduce the image, but not to 8X8, it will be larger, such as 500X500, and we will maintain the aspect ratio of the image, so that more details will be retained, but if we directly use the 500X500 image to generate Fingerprint, then the direct length will reach 250000 + (of course it may be less than this number), which is definitely not possible. In the end, we chose to partition the image, such as into 5X5 areas.
Sampling the pixels in each partition and using the grayscale average as a feature point, we can finally obtain an approximate feature array consisting of 25 (may be greater than or less than 25 digits) digits. Feature array extraction method:
getImageHash(img, {<!-- --> width = 100, height = 100, pieces = 5 } = {<!-- -->}) {<!-- -->
// Shrink the image
const imgData = getResizedImgData(img, width, height);
const {<!-- --> width: imgWidth, height: imgHeight } = imgData;
const grayStyles = [];
const stepX = Math.floor(imgWidth / pieces );
const stepY = Math.floor(imgHeight / pieces );
const features = [];
for (let y = 0; y < imgHeight; y + = stepY) {<!-- -->
for (let x = 0; x < imgWidth; x + = stepX) {<!-- -->
const grayStyles = [];
for (let j = 0; j < stepY; j + + ) {<!-- -->
const yy = y + j;
for (let i = 0; i < stepX; i + + ) {<!-- -->
const xx = x + i;
const index = (yy * imgWidth + xx) * 4;
grayStyles.push(this.getGrayStyle(imgData, index));
}
}
const average = Math.round(grayStyles.reduce((a, b) => {<!-- -->
return a + b;
}, 0) / grayStyles.length);
features.push(average);
}
}
return features;
}
The getResizedImgData method used is defined:
getResizedImgData(img, width = 8, height = 8) {<!-- -->
let imgWidth = img.width, imgHeight = img.height;
const ratio = imgWidth / imgHeight;
if (imgWidth > imgHeight) {<!-- -->
imgWidth = width;
imgHeight = Math.floor(imgWidth / ratio);
} else {<!-- -->
imgHeight = height;
imgWidth = Math.floor(imgHeight * ratio);
}
const canvas = document.createElement('canvas');
canvas.width = imgWidth;
canvas.height = imgHeight;
const ctx = canvas.getContext('2d');
ctx.drawImage(img, 0, 0, img.width, img.height, 0, 0, imgWidth, imgHeight);
return ctx.getImageData(0, 0, imgWidth, imgHeight);
}
According to the above method, we can get the feature array of the image, and use Hamming distance or cosine similarity to compare the similarity of the image.
Although we have obtained the feature array of the image through the above steps, and we can also compare the similarity of the image through some algorithms, there is still a certain distance from the hash we are talking about. So how to get a consistent hash?
In fact, if we think about it carefully, the value direction of the gray value is 0 <= gray <= 255, a total of 256 digits. We only need to divide 256 into several small ranges. Each number in the small range corresponds to a hash character, right? Is that enough? The format of the value in each small range is used to control the tolerance of accuracy to a certain extent. To open the number of special characters in the greenway, let the minimum tolerance value be 4, which means that the minimum value of each small range is 4 digits. , of course, can also be adjusted according to the situation. Here is a simple implementation:
function getIdentifier(graystyle, devitation = 4) {<!-- -->
const devi = devitation <= 4 ? 4 : devitation;
const indentifiers = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ%=';
return indentifiers[Math.floor(graystyle / devitation)];
}
Some thoughts at the end of the article:
1. Through the above, we can extract the feature array of the image and further generate the image similarity hash. We can adjust the accuracy of the feature array and hash by adjusting the size of the reduced image and the number of partitions.
2. Some friends may say that when the amount of data is relatively large, the calculation amount of this comparison is still very large. Here we can optimize the comparison speed by optimizing the comparison algorithm. We can optimize from the following aspects (here mainly for direct comparison) Using feature array):
1. Compare the lengths of the feature arrays. If they are not equal, then the pictures are not similar and return them directly.
2. What does it mean to introduce the concept of mutation? For example, the following two sets of feature arrays
const a = [300, 200, 100]; const b = [310, 202, 102];
For normal comparison, we will compare each corresponding position of the array in turn, such as comparing 200 and 202, comparing 100 and 102, and comparing 300 and 310. Under normal circumstances, if the two values are less than a certain error such as 2, we will It is considered to be similar, but if calculated in this way, we need to traverse the array to know whether it is similar. If a mutation is introduced, if we set the critical value of the mutation to 5, if the eigenvalue of a certain family is greater than 5, then we directly determine it as If they are not similar, they will be returned directly. For example, in the above case, the interval between the first group of numbers of a and b is 10, which is greater than the icon critical value 5. We do not need to compare the content after the array and return it directly.
3. Although this algorithm is better than the perceptual hash algorithm, there will still be some errors, such as the following two sets of pictures.
The theme content is completely the same, the difference lies in the blank space in the corners, and the current algorithm is sensitive to this blank space, because it calculates the average gray value, there may be a sudden mutation in the corners, and it is determined that the two pictures are not similar. This is obviously not in line with expectations. Of course, this problem is ultimately a design problem, and specifications can be made from the designer. However, people always make mistakes. We still need to consider using programs to make up for this problem. In fact, the idea is also very Simple, before reducing the image, extract the subject area of the image, and then continue the above process. Here is a simple graphic subject cutting, based on transparency:
function getSolidImage(img) {<!-- -->
const oCanvas = new OffscreenCanvas(img.width, img.height);
const oCtx = oCanvas.getContext('2d');
const imageData = oCtx.getImageData(0, 0, img.width, img.height);
const {<!-- --> width, height } = imageData;
const left = getSolidLeft(imageData);
const top = getSolidTop(imageData);
const right = getSolidRight(imageData);
const bottom = getSolidBottom(imageData);
const [solidX, solidY, solidWidth, solidHeight ] = [left, top, width - left - right, height - top - bottom];
let canvas = document.createElement('canvas');
canvas.width = solidWidth;
canvas.height = solidHeight;
const ctx = canvas.getContext('2d');
ctx.drawImage(mycanvas, solidX, solidY, solidWidth, solidHeight, 0, 0, solidWidth, solidHeight);
return canvas;
}
function getSolidTop(imageData) {<!-- -->
const {<!-- --> width, height, data } = imageData;
for (let j=0; j<height; j + + ) {<!-- -->
for (let i=0; i<width; i + + ) {<!-- -->
const index = i * 4 + j * width * 4;
if (data[index + 3] > 120) {<!-- -->
return j;
}
}
}
}
function getSolidRight(imageData) {<!-- -->
const {<!-- --> width, height, data } = imageData;
for (let i=width-1; i>=0; i--) {<!-- -->
for (let j=0; j<height-1; j + + ) {<!-- -->
const index = j * width * 4 + i * 4;
if (data[index + 3] > 120) {<!-- -->
return width-i;
}
}
}
}
function getSolidBottom(imageData) {<!-- -->
const {<!-- --> width, height, data } = imageData;
for (let j=height-1; j>=0; j--) {<!-- -->
for (let i=0; i<width; i + + ) {<!-- -->
const index = j * width * 4 + i * 4;
if (data[index + 3] > 120) {<!-- -->
return height-j;
}
}
}
}
function getSolidLeft(imageData) {<!-- -->
const {<!-- --> width, height, data } = imageData;
for (let i=0; i<width; i + + ) {<!-- -->
for (let j=0; j<height; j + + ) {<!-- -->
const index = j * width * 4 + i * 4;
if (data[index + 3] > 120) {<!-- -->
return i;
}
}
}
}
Well, this article ends here. After writing so much, there must be some imperfections that have been considered. If you have any questions, please feel free to contact me.
Original address: https://www.deanhan.cn/image-similarity-feature-hash.html