Detailed analysis of the 2021 central China Cup Title A (color selection of mosaic tiles)

List of articles

One 、 Basic introduction

1.1 Title Description

1.2 Problems to be solved

Two 、 Problem analysis and solution

2.1 Problem 1 Analysis and solution

 2.2 Problem 2 Analysis and solution

 2.3 Problem 3 Analysis and solution

  3、 ... and 、 summary

---

One 、 Basic introduction

1.1 Title Description

Mosaic tile is a smaller size （ Common specifications are that the side length does not exceed 5cm） Square tiles , Easy to lay on uneven surfaces , And it is easy to splice and combine various words or patterns . But limited by the process and cost , The color of ceramic tile can only be limited . When the user stitches patterns , First, according to the color in the original picture , Choose tiles with similar colors , To do the stitching .

A mosaic tile factory can only produce 22 Color （ See the attachment 1） Mosaic tiles . The factory will develop a software , According to the color of the original picture , Automatically find the tile with the closest color , So as to reduce the workload of manual color selection . The factory hopes that your team will provide an algorithm to determine the corresponding relationship between the original color and the tile color . Suppose the original image is 24 Bit true color format , namely R、G、B All three color components are 8 position , share 28 × 28 × 28 = 16777216 Color , For any given color , The algorithm outputs the color number of the tile with the closest color .

1.2 Problems to be solved

（1） The attachment 2 It's an image 1 Medium 216 Color , The attachment 3 It's an image 2 Medium 200 Color , Please find the tile color closest to each color , Number the selected tile colors according to the attachment 4 Output to the result file .

（2） If the plant's technological innovation , Plan to develop new color tiles . that , Regardless of the difficulty of research and development , Only considering the expressiveness of the mosaic image , Which color tiles should be added first ？ When simultaneously increasing 1 Color 、 At the same time increase 2 Color 、……、 At the same time increase 10 When planting colors , Give the corresponding colors respectively RGB Encoding value .

（3） If the cost of developing a new color tile is the same , It has nothing to do with the color itself , that , Consider both cost and performance , What new colors do you suggest , Explain the reason and give the corresponding RGB Encoding value .

Existing tile colors

Two 、 Problem analysis and solution

2.1 Problem 1 Analysis and solution

For question one , We first introduced chromatic aberration This concept represents the similarity between different colors , And coordinate the color object , utilize Euclidean distance formula , Find the distance between two points , And assign this value to the color difference , The size of the color difference value obtained by calculation indicates the similarity between different colors . also , We first chose RGB Space 、HSV Space and Lab Space Three color spaces , The characteristics of three different color spaces are explained , And each of the three spaces has its own Color matching model . after , We evaluate and compare the three spaces and their models , Finally choose to use Lab Space model and color matching model based on the model , And simplify the calculation in the process of solving , Final solution and attachment 2、3 in 216 Color and 200 Color closest to , as well as RGB Encoding value .

#HSV  3D cone image code 
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
from math import sin, cos, pi
# Conduct 
# r,g,b [0,255]
# h 0 - 360
# s 0 - 100
# v 0 - 100
def rgb2hsv(r, g, b):
    r_, g_, b_ = r / 255, g / 255, b / 255
    c_max = max(r_, g_, b_)
    c_min = min(r_, g_, b_)
    dela = c_max - c_min
    if dela == 0:
        h = 0
    elif c_max == r_ and g_ >= b_:\
            h = 60 * ((g_ - b_) / dela + 0)
    elif c_max == r_ and g_ < b_:
        h = 60 * ((g_ - b_) / dela + 2)
    elif c_max == g_:
        h = 60 * ((b_ - r_) / dela + 2)
    else:
        h = 60 * ((r_ - g_) / dela + 4)
        s = 0 if c_max == 0 else dela / c_max
        v = c_max
        return h, s * 100, v * 100
# h 0,255 s,v 0,1
def hsv2rgb(h, s, v):
    c = v * s
    x = c * (1 - abs((h / 60) % 2-1))
    m = v - c
    if 0 <= h < 60:
        r_, g_, b_ = c, x, 0
    elif 60 <= h <= 120:
        r_, g_, b_ = x, c, 0
    elif 120 <= h <= 180:
        r_, g_, b_ = 0, c, x
    elif 180 <= h <= 240:
        r_, g_, b_ = 0, x, c
    elif 240 <= h <= 300:
        r_, g_, b_ = x, 0, c
    elif 300 <= h <= 360:
        r_, g_, b_ = c, 0, x
    return (r_ + m) * 255, (g_ + m) * 255, (b_ + m)
fig = plt.figure() #  Define a new 3D axis 
ax = Axes3D(fig)
size = 30
points = np.linspace(0, 255, size).astype(np.int32)
for h in np.linspace(0, 360, size):
    for s in np.linspace(0, 100, size):
        for v in np.linspace(0, 100, size):
            if v < s:
                continue
            x_ = s * cos(h * pi / 180)
            y_ = s * sin(h * pi / 180)
            # z_ = -(v ** 2 - s ** 2) ** 0.5
            z_ = v
            x, y, z = hsv2rgb(h, s / 100, v / 100)
            ax.plot([x_], [y_], [z_], "ro", color=(x / 255, y / 255, z / 255, 1))
plt.show()
print('---')

import sys
import math
# This code is for the topic , The attachment 2 It's an image 1 Medium 216 Color , The attachment 3 It's an image 2 Medium 200 Color . The attachment 2 The color selection results of are saved in result1.txt in . The attachment 3 The color selection results of are saved in result2.txt in .
filename1=sys.argv[1]# Used to receive attachments 2
filename2=sys.argv[2]# The attachment 3
filename3=sys.argv[3]# Data output result1.txt
filename4=sys.argv[4]# Data output result2.txt
f1=open(filename1,'r',encoding='utf8')# Read in 
f2=open(filename2,'r',encoding='utf8')# Read in 
f3=open(filename3,'w',encoding='utf8')# Output result1.txt
f4=open(filename4,'w',encoding='utf8')# Output result2.txt
s=" Serial number , Tile color number "+'\n'
f3.writelines(s)# First output the format 
f4.writelines(s)
b=[[0,0,0],[255,255,255],[255,0,0],[246,232,9],[72,176,64],[27,115,186],[53,118,84],[244,181,208],[255,145,0],[177,125,85],[92,59,144],[11,222,222],[228,0,130],[255,218,32],[118,238,0],[17,168,226],[255,110,0],[201,202,202],[255,249,177],[179,226,242],[249,225,214],[186,149,195]]
def distance(a,b):#a Is a single color to be matched ,b For the existing color list , Returns the most similar color subscript plus 1
    min=[442,0]# The first parameter is zero math.sqrt(3*(255)**2), The second parameter represents the label , Is the subscript plus 1
    for i in range(len(b)):
        min_i=math.sqrt((a[0]-b[i][0])**2+(a[1]-b[i][1])**2+(a[2]-b[i][2])**2)
        if min_i<min[0]:
            min[0]=min_i
            min[1]=i+1
    return min
def str_int(s):# Defines a string that can be “(a,b,c)” Convert to an integer list
    b = []
    for i in range(len(s)):
        if s[i] == '(':
            first=i
        if s[i] ==')':
            last=i
    s1=s[first+1:last]
    s2=s1.split(',')
    for i in range(3):
        b.append(int(s2[i]))
    return b
lines1=f1.readlines()
lines2=f2.readlines()
for i in range(1,len(lines1)):# Start traversing attachments 2, The first line is not 
    s=""# An empty string 
    for j in range(len(lines1[i])):
        if lines1[i][j] ==',':# hold ',' Characters and serial numbers before 
            s=lines1[i][:j]+','
            break
    a=str_int(lines1[i])
    bianhao=distance(a,b)
    s=s+str(bianhao[1])+'\n'
    f3.writelines(s)
for i in range(1,len(lines2)):# Start traversing attachments 2, The first line is not 
    s=""# An empty string 
    for j in range(len(lines2[i])):
        if lines2[i][j] ==',':# hold ',' Characters and serial numbers before 
            s=lines2[i][:j]+','
            break
    a=str_int(lines2[i])
    bianhao=distance(a,b)
    s=s+str(bianhao[1])+'\n'
    f4.writelines(s)
f1.close()
f2.close()

 

 2.2 Problem 2 Analysis and solution

For question two , Because only the expressive effect is considered , Let's start with the attachment 2、3 Medium 216 Color 200 Colors and existing 22 Species were carried out Statistics And Visualization processing , Get their color spatial distribution map , On this basis, the demand side and the supply side are selected , Determine the performance evaluation criteria ——“ After adding colors , The new color set is more evenly distributed in space ”. According to the above conditions , Give priority to increase, and the difference between multiple colors is small , No matter how many colors are added , But in essence, choose similar colors , Just add more colors at the same time, we should consider the distribution of new cluster centers ,FCM Thought is more suitable to solve the problem , The objective function can be expressed as FCM Come on  .

among i Represents the cluster center ,j Indicates other points ,c Is the total number of cluster centers ,N Is the total number of other points （ except FCM It can also be done with the help of the ideas of other clustering algorithms ）, The idea of the algorithm is to minimize the reciprocal sum of the distances from other points to the cluster center , But don't apply the algorithm directly , The distance formula needs to be changed . The second question is from the perspective of technological innovation , Then the points to be clustered in this question should be 256*256*256 A little bit , Not an attachment 2 And accessories 3 To do cluster analysis , Of course, after selecting the new cluster center color , You can calculate another attachment 2 And accessories 3 Of J Function value , For the expressiveness mentioned in the title , The more similar the color, the better the expressiveness , The expression function formula can be directly J The reciprocal of a function .

%MATLAB Part of the code 
% The following program is a simple version of particle swarm optimization algorithm , The population size and iteration times are set to be small , Adjust yourself , It can also be replaced by other optimization algorithms 
num=20;% The population size 
k=2;% newly added k Center 
c1 = 0.5; % Nonnegative constant , Acceleration factor 
Vmax=10; % Maximum particle update speed 
Vmin=-10; % Minimum particle update speed 
% Initial population 
xx=[];

for i=1:num
    xx(i,:)=round(255.*rand(1,3*k));%round rounding 
end

F=[];
for i=1:num
    YY=[];
    YY=[Y;reshape(xx(i,:)',3,k)'];% Add a new cluster center to the tile color library 
    D=[];
    D=Dis(X,YY,a1,a2);
    D=1./D;
    D(find(D==Inf))=0;
    D=sum(D,2);
    D=1./D;
    F(i,1)=sum(D);
end
[bestf,in]=min(F);
bestx=xx(in,:);
trace(1)=bestf;
det=20;% The number of iterations 
slexx=xx;
for ii=1:det
    V=rands(num,k*3);
    for j=1:num
        V(j,:)=V(j,:)+c1*rand.*(bestx-slexx(j,:));
    end
    V(find(V>Vmax))=Vmax;
    V(find(V<Vmin))=Vmin;
    slexx=slexx+V;
    slexx=round(slexx);
    slexx(find(slexx>255))=255;
    slexx(find(slexx<0))=0;
    FF=[];
    for i=1:num
        YY=[];
        YY=[Y;reshape(slexx(i,:)',3,k)'];% Add a new cluster center to the tile color library 
        D=[];
        D=Dis(X,YY,a1,a2);
        D=1./D;
        D(find(D==Inf))=0;
        D=sum(D,2);
        D=1./D;
        FF(i,1)=sum(D);
    end
    if min(FF)<bestf
        [bestf,in]=min(FF);
        bestx=slexx(in,:);
    end
    trace=[trace;bestf];
end

 2.3 Problem 3 Analysis and solution

Third questions , Consider the cost on the basis of the previous question , The cost function is calculated by how many colors are added , It is equivalent to the number of independent variables for the optimization of this question m It is changing. , You can add an objective function in the above steps M, That is, adding m One color . This question is a multi-objective optimization problem . For question three , In the subject , In addition to considering the performance of mosaic images , R & D cost has also become an important consideration in the optimization problem . For the problem of expressiveness , We consider the distribution of new cluster centers in space , And used FCM thought , Given the Expressive force function ; And the cost problem , Because the cost of developing any new color is the same , And it has nothing to do with the color itself , So we put The relationship between R & D cost and color quantity is linear , And establish its cost function . According to the above , We set up the decision variable with increasing number as the change , Taking the expressive force function and the cost function as the objective function Multi objective optimization model , And used Non dominated sorting algorithm And Simulated annealing algorithm , Solve the model .

%MATLAB Self built function 
function D=distance(X,Y,a1,a2) 
    s=std(X-Y); 
    d=sqrt(sum((X-Y).^2)); 
    D=s*a1+d*a2; 
end 

function [TT,chrom]=ns2(NN,F1,F2) 
    a = 0; 
    T1 = []; 
    T2 = []; 
    chrom=NN; 
    chrom1 = []; 
    chrom2 = []; 
    while a == 0 
        M = []; 
        for i = 1:length(F1) 
            M(i,1) = length(find(F1<F1(i,1)))+length(find(F2<F2(i,1))); 
        end 
        b1 = []; 
        b2 = []; 
        [b1,b2] = sort(M); 
        if length(chrom)>0 && b1(1) == 0 
            T1 = [T1;F1(b2(1)),F2(b2(1))]; 
            chrom1 = [chrom1;chrom(b2(1),:)]; 
            F1(b2(1)) = []; 
            F2(b2(1)) = []; 
            chrom(b2(1),:) = []; 
        else 
            a = 1; 
            T2 = [F1,F2]; 
            chrom2 = chrom;
        end 
    end 
    T2 = T2(b2,:); 
    chrom2 = chrom2(b2,:); 
    if size(T1,1) > 2 
        y = yongji(T1);% Crowding degree  
        for i = 2:size(T1,1) 
            if y(i-1) > y(i) 
                T1(i-1:1:i,:) = T1(i:-1:i-1,:); 
                chrom1(i-1:1:i,:) = chrom1(i:-1:i-1,:); 
            end
        end
    end
    if length(T2) > 0
        y = yongji(T2);% Crowding degree  
        for i = 2:size(T2,1) 
            if b1(i) == b1(i-1) 
                if y(i-1) > y(i) 
                    T2(i-1:1:i,:) = T2(i:-1:i-1,:); 
                    chrom2(i-1:1:i,:) = chrom2(i:-1:i-1,:); 
                end
            end
        end
    end
    TT = [T1;T2];
    chrom = [chrom1;chrom2]; 
end 
function y=yongji(H) 
    y1=H(:,1); 
    y2=H(:,2); 
    [yy1,a1]=sort(y1); 
    [yy2,a2]=sort(y2); 
    L=[]; 
    L=[1 1]; 
    for i=2:length(yy1)-1 
        L=[L;(yy1(i+1,1)-yy1(i-1,1))/(max(yy1)-min(yy1)),(yy2(i+1,1)-yy2(i-1,1))/(max(yy2) 
        32-min(yy2))]; 
    end 
    L=[L;1 1]; 
    L=[L(a1,1),L(a2,2)]; 
    y=sum(L,2); 
end 
function D=Dis(X,Y,a1,a2) 
    D=[]; 
    for i=1:size(X,1) 
        for j=1:size(Y,1) 
            D(i,j)=distance(X(i,:),Y(j,:),a1,a2); 
        end
    end
end

  3、 ... and 、 summary

The interesting thing about mathematical modeling is that there are almost no right answers , There are many solutions , There is no absolutely good way , As long as you are comfortable with it OK, These are some of my superficial views on this problem , There may be some overlooked factors , Welcome to give us some advice .

Succeed in learning 、 Progress in learning ！ We study together and don't give up ~

Remember Sanlian ~ Your support is my biggest motivation ！！ Welcome to read previous articles ~

Xiao Bian's contact information is as follows , Welcome to communicate with you , Code what add small edit private chat oh ~

int[] arr=new int[]{4,8,3,2,6,5,1};
int[] index= new int[]{6,4,5,0,3,0,2,6,3,1};
String QQ = "";
    for (int i : index){
        QQ +=arr[i];
}
System.out.println(" Small make up the QQ:" + QQ);