Image searching method based on feature extraction

Abstract

This invention provides an image searching method based on feature extraction to determine at least one sample image similar to the image to be searched, including the following steps: a. feature extraction on all sample images to obtain all corresponding feature information, while all sample images are I.sub.1, I.sub.2, . . . , I.sub.S and all said feature information corresponding to all sample images are V.sub.1, V.sub.2, . . . , V.sub.S; b. creating an index tree based on all of said feature information; c. obtaining the feature information corresponding to the image to be searched based on the feature extraction; d. determining said feature information corresponding to at least one sample image having a minimum distance from the image to be searched based on the index tree and the feature information of the image to be searched. The invention has powerful functions and simple operation, and is able to avoid interference of background, text annotation and image merging during processing and filtering of feature extraction, which has good search results and high commercial value.

Claims

1. An image searching method based on feature extraction, which is used to determine at least one sample image similar to the image to be searched, including the following steps: a. Performing feature extraction step on all sample images to obtain all corresponding feature information, wherein all sample images are I.sub.1, I.sub.2, . . . , I.sub.s, and the feature information corresponding to all sample images are V.sub.1, V.sub.2, . . . , V.sub.s; b. Creating an index tree based on all of said feature information; c. Acquiring said feature information corresponding to the image to be searched based on the feature extraction step; d. Determining said feature information corresponding to at least one sample image having a minimum distance based on the index tree and said feature information of the image to be searched, which is characterized in that, to perform the feature extraction step on said sample image or each pixel of images to be searched, said step including the following steps: i. Determining whether the pixel locates within the outer frame of the main image, if the pixel locates in the outer frame of the main image, then continue with step ii; if the pixel is beyond the outer frame of the main image, then end processing on this pixel, and continue processing the next pixel; ii. Calculating the background weight w.sub.b and foreground weight w.sub.f of the pixel; iii. Accumulating said w.sub.f and said w.sub.b to variable m.sub.f and m.sub.b; iv. Getting the screening result of the pixel in the screening information of said sample image or said image to be searched, if the screening result shows that the pixel is reserved, then continue with step v; if the screening result shows that the pixel is screened out, the pixel is not subjected to subsequent processing, and the next pixel will be processed from step i; v. Determining whether the red, green, and blue components values of said pixel are all 1, if so, the pixel is not subjected to subsequent processing, and the next pixel will be processed from step i; if any component of the red, green, or blue of the pixel is not 1, then it will continue with step vi; vi. Calculating the brightness value Val, the saturation value Sat, and the hue value Hue of said pixel respectively; vii. Adding up the brightness value Val, the saturation value Sat, the hue value Hue, background weight w.sub.b and foreground weight w.sub.f to the foreground\background luminance histogram, foreground\background saturation histogram, foreground\background hue histogram, and returning to step i to process the next pixel; viii. After performing the process from steps i to vii for all the pixels, next step is to normalize the foreground luminance real array variable and the background luminance real array variable respectively and perform subtraction operations to obtain a luminance feature array V.sub.val, normalize the foreground saturation real array variable and the background saturation real array variable respectively and perform subtraction operations to obtain a luminance feature array V.sub.sat, and normalize the foreground hue real array variable and the background hue real array variable are respectively and perform subtraction operations to obtain a hue feature array V.sub.hue, and define the real array variable in which V.sub.val, V.sub.sat, and V.sub.hue are combined into as the feature information.

2. The method of claim 1, which is characterized in that, when performing feature extraction on all sample images to obtain all corresponding feature information, performing screening step on the sample images to obtain screening information corresponding to the sample images, and performing feature extraction step on the screening information corresponding to the sample images.

3. The method of claim 2, which is characterized in that, step ii includes following steps: When the pixel locates within the inner frame range of the main image, calculating the background weight w.sub.b and foreground weight w.sub.f according to the following formulas “w.sub.b=(w.sub.b0).sup.2, w.sub.f=1−w.sub.b”, where $w_{b0}=\min \left(.Math.\frac{i}{\max \left(H-1,1\right)}-0.5.Math.,.Math.\frac{i-i_{1^{\prime }}}{\max \left(i_{2^{\prime }}-i_1^{\prime }-1,1\right)}-0.5.Math.\right)+\min (.Math.\frac{j}{\max \left(W-1,1\right)}-0.5.Math.,.Math.\frac{j-j_{1^{\prime }}}{\max \left(j_{2^{\prime }}-j_1^{\prime }-1,1\right)}-0.5.Math.),$ where i.sub.1′,i.sub.2′ represent the two endpoint in the Y-axis of the inner frame of said main image; j.sub.1′,j.sub.2′ represent the two endpoint in the X-axis of the inner frame of said main image; H represents the height of said image; W represents the width of said image; i, j represent the value of each Y-axis and X-axis coordinate of the pixel; if the pixel is beyond the inner frame range of said main image, then w.sub.b=1, w.sub.f=0.

4. The method of claim 3, which is characterized in that, step iii includes: to set m.sub.f and m.sub.b as two real variables with initial values of 0, and evaluate the pixel in accordance with m.sub.f:=m.sub.f+w.sub.f, m.sub.b:=m.sub.b+w.sub.b.

5. The method of claim 4, which is characterized in that, step vi includes: Calculating brightness value Val of the pixel according to the formula Val=1−(0.299*Red+0.587*Green+0.114*Blue), where Red, Green, Blue represent the red, green, and blue component values, and Red, Green, Blue are all real numbers between 0 and 1; Calculating saturation value Sat according to the formula:
Sat=√{square root over (Sat.sub.2)}, where Sat.sub.2=Sat.sub.1*min(Sat.sub.1*8,1), where Sat.sub.1=Sat.sub.0*min(MaxRGB*2,1), Sat.sub.0=MaxRGB−MinRGB, MaxRGB represents the maximum value among Red, Green, Blue, MinRGB represents minimum value of among Red, Green, Blue; The hue value of the pixel is calculated according to the following formula: $\mathrm{Hue}=\{\begin{array}{c}1-\frac{\mathrm{Blue}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Green};\\ 1+\frac{\mathrm{Green}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Blue};\\ 3-\frac{\mathrm{Red}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Green},\mathrm{Min}\mathrm{RGB}=\mathrm{Blue};\\ 3+\frac{\mathrm{Blue}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Green},\mathrm{Min}\mathrm{RGB}=\mathrm{Red};\\ 5-\frac{\mathrm{Green}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Blue},\mathrm{Min}\mathrm{RGB}=\mathrm{Red};\\ 5+\frac{\mathrm{Red}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Blue}>\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Green}.\end{array}$

6. The method of claim 5, which is characterized in that, step vii includes: To set h.sub.val,f and h.sub.val,b as foreground brightness real array variable and background brightness real array variable containing N.sub.val elements respectively; h.sub.sat,f and h.sub.sat,b as foreground saturation real array variable and background saturation real array variable containing N.sub.sat elements respectively; h.sub.hue,f and h.sub.hue,b as foreground hue real array variable and background hue real array variable containing N.sub.hue elements respectively; To set (N.sub.val−1)*Val=u+v, where u is an integer between 0 and N.sub.val−2, v is a real number between 0 and 1, then assigning values according to the formulas:
h.sub.val,f[u]:=h.sub.val,f[u]+(1−v)*w.sub.f,
h.sub.val,f[u+1]:=h.sub.val,f[u+1]v*w.sub.f;
h.sub.val,b[u]:=h.sub.val,b[u]+(1−v)*w.sub.b,
h.sub.val,b[u+1]:=h.sub.val,b[u+1]+v*w.sub.b; To set(N.sub.sat−1)*Sat=u+v, where u is an integer between 0 and N.sub.sal−2, v is a real number between 0 and 1, then assigning values according to the formulas:
h.sub.sat,f[u]:=h.sub.sat,f[u]+(1−v)*w.sub.f,h.sub.sat,f[u+1]:=h.sub.sat,f[u+1]+v*w.sub.f;
h.sub.sat,b[u]:=h.sub.sat,b[u]+(1−v)*w.sub.b,h.sub.sat,b[u+1]:=h.sub.sat,b[u+1]+v*w.sub.b; To set (N.sub.hue/6)*Hue=u+v, where u is an integer between 0 and N.sub.hue−1, v is a real number between 0 and 1, and u.sup.+=(u+l)mod N.sub.hue, then assigning values according to the formulas:
h.sub.hue,f[u]:=h.sub.hue,f[u]+(1−v)*Sat*w.sub.f,h.sub.hue,f[u.sup.+]:=h.sub.hue,f[u.sup.+]+v*Sat*w.sub.f;
h.sub.hue,b[u]:=h.sub.hue,b[u]+(1−v)*Sat*w.sub.b,h.sub.hue,b[u.sup.+]:=h.sub.hue,b[u.sup.+]+v*Sat*w.sub.b.

7. The method of claim 6, which is characterized in that, step viii includes:
V.sub.val[u]=max(h.sub.val,f[u]/m.sub.f−h.sub.val,b[u]/m.sub.b,0),u=0, . . . ,N.sub.val−1;
V.sub.sat[u]=max(h.sub.sat,f[u]/m.sub.f−h.sub.sat,b[u]/m.sub.b,0),u=0, . . . ,N.sub.sat−1;
V.sub.hue[u]=max(h.sub.hue,f[u]/m.sub.f−h.sub.hue,b[u]/m.sub.b,0),u=0, . . . ,N.sub.hue−1.

8. The method of claim 1, which is characterized in that, while obtaining the feature information corresponding to the image to be searched based on the feature extraction step, screening the images to be searched to obtain screening information corresponding to the images to be searched and performing feature extraction step on the screening information corresponding to the images to be searched.

9. The method of claim 1, which is characterized in that, step ii includes following steps: When the pixel locates within the inner frame range of the main image, calculating the background weight w.sub.b and foreground weight w.sub.f according to the following formulas “w.sub.b=(w.sub.b0).sup.2, w.sub.f=1−w.sub.b”, where $w_{b0}=\min \left(.Math.\frac{i}{\max \left(H-1,1\right)}-0.5.Math.,.Math.\frac{i-i_{1^{\prime }}}{\max \left(i_{2^{\prime }}-i_1^{\prime }-1,1\right)}-0.5.Math.\right)+\min (.Math.\frac{j}{\max \left(W-1,1\right)}-0.5.Math.,.Math.\frac{j-j_{1^{\prime }}}{\max \left(j_{2^{\prime }}-j_1^{\prime }-1,1\right)}-0.5.Math.),$ where i.sub.1′,i.sub.2′ represent the two endpoint in the Y-axis of the inner frame of said main image; j.sub.1′,j.sub.2′ represent the two endpoint in the X-axis of the inner frame of said main image; H represents the height of said image; W represents the width of said image; i,j represent the value of each Y-axis and X-axis coordinate of the pixel; if the pixel is beyond the inner frame range of said main image, then w.sub.b=1, w.sub.f=0.

10. The method of claim 9, which is characterized in that, step iii includes: to set m.sub.f and m.sub.b as two real variables with initial values of 0, and evaluate the pixel in accordance with m.sub.f:=m.sub.f+w.sub.f, m.sub.b:=m.sub.b+w.sub.b.

11. The method of claim 10, which is characterized in that, step vi includes: Calculating brightness value Val of the pixel according to the formula Val=1−(0.299*Red+0.587*Green+0.114*Blue), where Red, Green, Blue represent the red, green, and blue component values, and Red, Green, Blue are all real numbers between 0 and 1; Calculating saturation value Sat according to the formula:
Sat=√{square root over (Sat.sub.2)}″, where Sat.sub.2=Sat.sub.1*min(Sat.sub.1*8,1), where Sat.sub.1=Sat.sub.0*min(MaxRGB*2,1), Sat.sub.0=MaxRGB−MinRGB, MaxRGB represents the maximum value among Red, Green, Blue, MinRGB represents minimum value of among Red, Green, Blue; The hue value of the pixel is calculated according to the following formula: $\mathrm{Hue}=\{\begin{array}{c}1-\frac{\mathrm{Blue}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Green};\\ 1+\frac{\mathrm{Green}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Blue};\\ 3-\frac{\mathrm{Red}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Green},\mathrm{Min}\mathrm{RGB}=\mathrm{Blue};\\ 3+\frac{\mathrm{Blue}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Green},\mathrm{Min}\mathrm{RGB}=\mathrm{Red};\\ 5-\frac{\mathrm{Green}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Blue},\mathrm{Min}\mathrm{RGB}=\mathrm{Red};\\ 5+\frac{\mathrm{Red}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Blue}>\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Green}.\end{array}$

12. The method of claim 6, which is characterized in that, step vii includes: To set h.sub.val,f and h.sub.val,b as foreground brightness real array variable and background brightness real array variable containing N.sub.val elements respectively; h.sub.sat,f and h.sub.sat,b as foreground saturation real array variable and background saturation real array variable containing N.sub.sat elements respectively; h.sub.hue,f and h.sub.hue,b as foreground hue real array variable and background hue real array variable containing N.sub.hue elements respectively; To set (N.sub.val−1)*Val=u+v, where u is an integer between 0 and N.sub.val−2, v is a real number between 0 and 1, then assigning values according to the formulas:
h.sub.val,f[u]:=h.sub.val,f[u]+(1−v)*w.sub.f,
h.sub.val,f[u+1]:=h.sub.val,f[u+1]v*w.sub.f;
h.sub.val,b[u]:=h.sub.val,b[u]+(1−v)*w.sub.b,
h.sub.val,b[u+1]:=h.sub.val,b[u+1]+v*w.sub.b; To set(N.sub.sat−1)*Sat=u+v, where u is an integer between 0 and N.sub.sal−2, v is a real number between 0 and 1, then assigning values according to the formulas:
h.sub.sat,f[u]:=h.sub.sat,f[u]+(1−v)*w.sub.f,h.sub.sat,f[u+1]:=h.sub.sat,f[u+1]+v*w.sub.f;
h.sub.sat,b[u]:=h.sub.sat,b[u]+(1−v)*w.sub.b,h.sub.sat,b[u+1]:=h.sub.sat,b[u+1]+v*w.sub.b; To set (N.sub.hue/6)*Hue=u+v, where u is an integer between 0 and N.sub.hue−1, v is a real number between 0 and 1, and u.sup.+=(u+l)mod N.sub.hue, then assigning values according to the formulas:
h.sub.hue,f[u]:=h.sub.hue,f[u]+(1−v)*Sat*w.sub.f,h.sub.hue,f[u.sup.+]:=h.sub.hue,f[u.sup.+]+v*Sat*w.sub.f;
h.sub.hue,b[u]:=h.sub.hue,b[u]+(1−v)*Sat*w.sub.b,h.sub.hue,b[u.sup.+]:=h.sub.hue,b[u.sup.+]+v*Sat*w.sub.b.

13. The method of claim 12, which is characterized in that, step viii includes:
V.sub.val[u]=max(h.sub.val,f[u]/m.sub.f−h.sub.val,b[u]/m.sub.b,0),u=0, . . . ,N.sub.val−1;
V.sub.sat[u]=max(h.sub.sat,f[u]/m.sub.f−h.sub.sat,b[u]/m.sub.b,0),u=0, . . . ,N.sub.sat−1;
V.sub.hue[u]=max(h.sub.hue,f[u]/m.sub.f−h.sub.hue,b[u]/m.sub.b,0),u=0, . . . ,N.sub.hue−1.

14. The method of claim 1, which is characterized in that, before the feature extraction step, performing size compression step on said sample images and/or said images to be searched.

15. The method of claim 1, which characterized in that, said index tree is a k-d tree, and in said k-d tree containing said feature information V.sub.1, . . . , V.sub.S corresponding to all sample images, searching feature information of one or more sample image which has or have the least square Euclidean distance $\left(\mathrm{dist}\left(V_s,V_0\right)=\underset{k=0}{\overset{N_{\mathrm{feat}}-1}{.Math.}}{\left(V_s\left[k\right]-V_0\left[k\right]\right)}^2\right)$ from the feature information V.sub.0 corresponding to the image to be searched, among which, N.sub.feat=N.sub.val+N.sub.sat+N.sub.hue represents the total number of elements in the feature array for each image.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) By reading and referring to the detailed descriptions of the non-limiting embodiments described by the following figures, the other features, objectives and advantages of the invention will be more apparent.

(2) FIG. 1 is shown as a process schematic diagram of an image searching method based on feature extraction, showing the detailed implementation of the invention;

(3) FIG. 2 is shown as a process schematic diagram of feature extraction on all sample images to obtain all corresponding feature information via the image searching method based on feature extraction, according to the first embodiment of the invention.

(4) FIG. 3 is shown as a process schematic diagram of obtaining the corresponding feature information of images to be searched feature based on feature extraction via the image searching method based on feature extraction, according to the second embodiment of the invention; and

(5) FIG. 4 is shown as a process schematic diagram of performing feature extraction on pixels of the sample images or images to be searched via the image searching method based on feature extraction, according to the third embodiment of the invention.

DETAILED EMBODIMENT

(6) In order to make the purpose, technical scheme and advantages of the invention clearer, the technical scheme of the invention is described below in combination with the drawings. FIG. 1 is shown as a process schematic diagram of an image searching method based on feature extraction, showing the detailed implementation of the invention. Specifically, FIG. 1 is used for determining at least one sample image similar to the image to be searched, that is, by extracting feature information corresponding to each image from all sample images, and searching for all feature information of sample images corresponding to the image to be searched based on said feature information of said image to be searched, thereby obtaining the commodity images similar to the sample image. Specifically, as follows,

(7) Firstly, step S101, performing feature extraction on all sample images to obtain all corresponding feature information, wherein all sample images are I.sub.1, I.sub.2, . . . , I.sub.S, and the feature information corresponding to all sample images are V.sub.1; V.sub.2, . . . , V.sub.S; S represents the number of all sample images in these embodiments for there are a lot of sample images.

(8) The feature information of each image is small quantities of information generated based on the image content that can be used for similar image searching. Further, feature information is preferably an array contains N.sub.feat=21 (among which N.sub.val=5, N.sub.sat=4, N.sub.hue=12) real number. It is understood by those skilled in the art that the detailed steps of performing feature extraction on all the sample images to obtain all the corresponding feature information will be further described in the detailed embodiments later, and will not be described herein.

(9) Then, step S102, creating index tree based on all the feature information. Further, after step S101, all the feature information corresponding to all sample images are obtained as V.sub.1, V.sub.2, . . . , V.sub.S. Then create k-d tree containing all the feature information corresponding to all sample images(V.sub.1, V.sub.2, . . . , V.sub.S) and call it “index of sample feature”. K-d tree (short for k-dimensional tree) is a data structure that organizes points in the Euclidean space in the k dimension (if the feature information is an array containing 21 real Numbers as described above, then k=21). In computer science, k-d trees can be used in a variety of applications, such as multidimensional key-value search. K-d tree is a special case of the binary tree, that is, the k-d tree is a binary tree in which each node is a k-dimensional point. It is understood by those skilled in the art that the establishment of the k-d tree adopts an industry-accepted algorithm which belongs to the current available technical solutions, and will not be described herein.

(10) After finishing the above steps in one time, perform steps S103 and S104 for each image to be searched submitted by the user. In step S103, the feature information corresponding to the image to be searched is acquired based on the feature extraction. It is understood by those skilled in the art that the step of acquiring the feature information corresponding to the image to be searched is the same as the step of extracting the feature information of obtaining all the sample images in step S101, which will be described in the mode of implementation hereafter.

(11) In step S104, determining said feature information corresponding to at least one sample image having a minimum distance from the image to be searched based on the index tree and said feature information of said image to be searched. It is understood by those skilled in the art that step S104, which is to determine said feature information corresponding to at least one sample image closest to said image to be searched based on the index tree and the feature information of said image to be searched. It will define the square Euclidean distance between feature information V.sub.s corresponding to each sample image I.sub.s and feature information V.sub.o corresponding to the image to be searched based on the formula

(12) $“\mathrm{dist}\left(V_s,V_0\right)=\underset{k=0}{\overset{N_{\mathrm{feat}}-1}{.Math.}}{\left(V_s\left[k\right]-V_0\left[k\right]\right)}^2”,$
and use the search algorithm of k-d tree to query the subscript “s” of one or more sample image(s) that minimize the square Euclidean distance and return the corresponding image (with the associated item ID, name, purchase link, and other metadata information in a preferable embodiment) to the user as the search result. Calculating and searching square Euclidean distance according to formulas will adopt an industry-accepted algorithm which can be achieved by the technical engineer of such fields following description of this invention, and will not be described herein.

(13) FIG. 2 is shown as a process schematic diagram, in the first embodiment of the invention, of feature extraction on all sample images to obtain all corresponding feature information via the image searching method based on feature extraction. In step S101, screening on the sample image to obtain screening information corresponding to the sample image, and performing feature extraction step using said screening information corresponding to the sample image. The screening information of each image includes the coordinate range of two rectangular areas, which is referred to as the outer frame of main image and the inner frame of main image respectively, wherein the inner frame is a sub-area of the outer frame, and the screening result of each pixel point, wherein “1” indicates that the pixel is screened out, and “0” indicates that the pixel is retained. It is understood by those skilled in the art that there is a sample image in the sample image database corresponding to each s=1, . . . , S, and we shall screen each sample image. Further, for each sample image I (or image to be searched), defining its width as W, its height as H (W,H>=1), and the pixels of row j and column i as I[I,j] (i=0, . . . , H−1, j=0, . . . , W−1). Each pixel I[i,j] contains three components which are red, green and blue (expressed as real numbers between 0 and 1). It is understood by those skilled in the art that red, green, and blue components of each pixel in the actual image are usually represented as integers between 0 and 255 and in these embodiments can the original value of each component be divided by 255 to be a real number between 0 and 1.

(14) Accordingly, FIG. 3 is shown as a process schematic diagram, in the second embodiment of the invention, of obtaining the corresponding feature information of images to be searched feature based on feature extraction via the image searching method based on feature extraction.

(15) In step S103, performing a screening step on the images to be searched to obtain screening information corresponding to the sample images and performing the feature extraction step using the screening information of the images to be searched, which will be further described in the detailed embodiments below, and will not be described herein

(16) Further, before the feature extraction step, performing size compression step on the sample images and the images to be searched. In these embodiments, to speed up the subsequent processing, if the width or height of the sample image exceeds 220 pixels, it will be scaled down to the width or height whichever bigger becomes 220 pixels with the same ratio of width to height; if the width or height of the searched image exceeds 220 pixels, it will be scaled down to the width or height whichever bigger becomes 220 pixels with the same ratio of width to height; After scaling down, image and its width and height are still referred to as I, W, H.

(17) FIG. 4 is shown as a process schematic diagram, in the third embodiment of the invention, of performing feature extraction on pixels of the sample images or images to be searched via the image searching method based on feature extraction. The step is processing the pixel one by one to implement feature extraction for each image, specifically, contains the following steps:

(18) With respect to each pixel, we will keep selecting the next pixel in the image before step S201 is carried out, so there is a continuing cycle between steps S201 and S207 until no pixel can be selected in the image. In the process of steps S201 to S207, the steps may be terminated in advance and proceed to the next pixel point in accordance with the result of continuous judgment process, which will be further described in the detailed embodiments later.

(19) Firstly, step S201, which is a determination process, is to determine whether the pixel point is located within the outer frame of the main image. If the pixel is located in the outer frame of the main image, proceed to step S202; if the pixel is beyond the outer frame of the main image, no subsequent processing will be performed on this pixel, and the next pixel will be processed from step S201.

(20) After step S201, step S202 is processed to calculate the background weight w.sub.b and the foreground weight w.sub.f of the pixel point. It is understood by those skilled in the art that, in order to reduce the interference of the background, the invention calculates the histograms (including the histograms of brightness, saturation, hue) of the background and the foreground part respectively, use the result of subtraction as a feature in step S208.

(21) In particular, if the pixel locates within the inner frame range of the main image, calculating the background weight w.sub.b and foreground weight w.sub.f according to the formulas:
w.sub.b=(w.sub.b0).sup.2,w.sub.f=1−w.sub.b, where

(22) $w_{b0}=\min \left(.Math.\frac{i}{\max \left(H-1,1\right)}-0.5.Math.,.Math.\frac{i-i_{1^{\prime }}}{\max \left(i_{2^{\prime }}-i_1^{\prime }-1,1\right)}-0.5.Math.\right)+\min (.Math.\frac{j}{\max \left(W-1,1\right)}-0.5.Math.,.Math.\frac{j-j_{1^{\prime }}}{\max \left(j_{2^{\prime }}-j_1^{\prime }-1,1\right)}-0.5.Math.),$
where i.sub.1′,i.sub.2′ represent the two end point in the Y-axis of the main frame of the image; j.sub.1′,j.sub.2′ represent the two endpoint in the X-axis of the main frame of the image; H represents the height of the image; W represents the width of the image; i,j represent the value of each y-axis and x-axis coordinate of the pixel point.

(23) If the pixel is beyond the inner frame range of the main image, then w.sub.b=1, w.sub.f=0. w.sub.b is between 0 and 1, close to 0 means the pixel is in the foreground (commodity) part, and close to 1 means the pixel is in the background part. Intuitively, the above formula will treat the part close to the overall center of the image and the central part of the inner frame range of the main image as foreground.

(24) And then, in step S203, set m.sub.f and m.sub.b as two real variables with initial values of 0, and assign m.sub.f:=w.sub.f, m.sub.b:=m.sub.b+w.sub.b to this pixel.

(25) And further, step S204 is to find the screening result of the pixel in the screening information of the sample image/image to be searched, if the screening result shows that the pixel is reserved, proceeding to step S205; if the screening result shows that the pixel is screened out, the pixel is not subjected to subsequent processing, and the next pixel will be processed from S201. In the screening results, the text, added framework and other parts made by human on the image will be screened out as much as possible to avoid affecting the extracted feature information. And further, step S205 is to determine whether the red, green, and blue components of the pixel are all 1. If so, i.e., the pixel is pure white, the pixel is not subjected to subsequent processing, and the next pixel will be processed from S201; if any of the red, green, and blue components of the pixel is not 1, i.e. the pixel is not pure white, step S206 below is to be continued.

(26) Step S206 is to calculate the brightness value Val, the saturation value Sat, and the hue value Hue of the pixel respectively. In these embodiments, calculating the pixel brightness value Val according to the formula:
Val=1−(0.299*Red+0.587*Green+0.114*Blue), where Red, Green, Blue represent the red, green, and blue component values, which is expressed as real numbers between 0 and 1.

(27) For the background of most of images in the gallery is white, “Val=0” represents white, “Val=1” represents black.

(28) In said step S207, set h.sub.val,f and h.sub.val,b as foreground brightness real array variable and background brightness real array variable containing N.sub.val elements respectively; set h.sub.sat,f and h.sub.sat,b as foreground saturation real array variable and background saturation real array variable containing N.sub.sat elements respectively; set h.sub.hue,f and h.sub.hue,b as foreground hue real array variable and background hue real array variable containing N.sub.hue elements respectively; the initial value of all elements is 0; and, set (N.sub.val−1)*Val=u+v, where u is an integer between 0 and N.sub.val−2, and v is a real number between 0 and 1, then assigning values according to the formulas:
h.sub.val,f[u]:=h.sub.val,f[u]+(1−v)*w.sub.f,h.sub.val,f[u+1]:=h.sub.val,f[u+1]+v*w.sub.f;
h.sub.val,b[u]:=h.sub.val,b[u]+(1−v)*w.sub.b,h.sub.val,b[u+1]:=h.sub.val,b[u+1]+v*w.sub.b; and set(Nsat−1)*Sat=u+v, where u is an integer between 0 and N.sub.sal−2, and v is a real number between 0 and 1, then assigning values according to the formulas:
h.sub.sat,f[u]:=h.sub.sat,f[u]+(1−v)*w.sub.f,h.sub.sat,f[u+1]:=h.sub.sat,f[u+1]+v*w.sub.f;
h.sub.sat,b[u]:=h.sub.sat,b[u]+(1−v)*w.sub.b,h.sub.sat,b[u+1]:=h.sub.sat,b[u+1]+v*w.sub.b; and set(N.sub.hue/6)*Hue=u+v, where u is an integer between 0 and N.sub.hue−1, and v is a real number between 0 and 1, and set u.sup.+=(u+1)mod N.sub.hue, then assigning values according to the formulas:
h.sub.hue,f[u]:=h.sub.hue,f[u]+(1−v)*Sat*w.sub.f,h.sub.hue,f[u.sup.+]:=h.sub.hue,f[u.sup.+]+v*Sat*w.sub.f;
h.sub.hue,b[u]:=h.sub.hue,b[u]+(1−v)*Sat*w.sub.b,h.sub.hue,b[u.sup.+]:=h.sub.hue,b[u.sup.+]+v*Sat*w.sub.b.

(29) Calculating saturation value Sat according to the formula:
Sat=√{square root over (Sat.sub.2)}, where Sat.sub.2=Sat.sub.1*min(Sat.sub.1*8, 1), Sat.sub.1=Sat.sub.0*min(MaxRGB*2,1), Sat.sub.0=MaxRGB−MinRGB, where MaxRGB represents the maximum value of Red, Green, Blue, MinRGB represents minimum value of the Red, Green, Blue.

(30) Besides, Sat.sub.0 can be regarded as the original saturation of pixels and the modification of Sat.sub.1 reduces the saturation of dark colors to make them more intuitive, the modification of Sat.sub.2 reduces the interference of pixels with extremely low saturation, for it is usually just a phenomenon of incorrect white balance and does not mean that it is actually colored. The hue value of the pixel point is calculated according to the following formula:

(31) $\mathrm{Hue}=\{\begin{array}{c}1-\frac{\mathrm{Blue}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}R\mathrm{GB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Green};\\ 1+\frac{\mathrm{Green}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Blue};\\ 3-\frac{\mathrm{Red}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Green},\mathrm{Min}\mathrm{RGB}=\mathrm{Blue};\\ 3+\frac{\mathrm{Blue}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Green},\mathrm{Min}\mathrm{RGB}=\mathrm{Red};\\ 5-\frac{\mathrm{Green}-\mathrm{Min}\mathrm{RGB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Blue},\mathrm{Min}\mathrm{RGB}=\mathrm{Red};\\ 5+\frac{\mathrm{Red}-\mathrm{Min}R\mathrm{GB}}{\mathrm{Max}\mathrm{RGB}-\mathrm{Min}\mathrm{RGB}},\mathrm{if}\mathrm{Max}\mathrm{RGB}=\mathrm{Blue}>\mathrm{Red},\mathrm{Min}\mathrm{RGB}=\mathrm{Green}.\end{array}$

(32) It is understood by those skilled in the art that according to the above formula, even when Red, Green, and Blue are not completely different, a unique Hue value can be obtained and fall within the scope of 0<=Hue<6. In a particular embodiment, if MaxRGB=MinRGB, then Hue=0. In such an embodiment, since Sat=0 at this time, the value of Hue has no effect on step S207.

(33) Thus, until now the processing of the pixel points is completed. Further, determining whether there is still a pixel point unprocessed. If so, such pixel point should be processed from step S201; if not, the process proceeds to step S208.

(34) After performing steps S201-S207 for all the pixels, step S208 is to normalize the foreground luminance real array variable and the background luminance real array variable respectively and perform subtraction operations to obtain a luminance feature array V.sub.val, normalize the foreground saturation real array variable and the background saturation real array variable respectively and perform subtraction operations to obtain a luminance feature array V.sub.sat, and normalize the foreground hue real array variable and the background hue real array variable are respectively and perform subtraction operations to obtain a hue feature array V.sub.hue, and define the real array variable in which V.sub.val, V.sub.sat, and V.sub.hue, are combined into as the feature information.

(35) Preferably, in step S208, set V.sub.val[u]=max(h.sub.val,f[u]/m.sub.f−h.sub.val,b[u]/m.sub.b, 0), u=0, . . . , N.sub.val−1; V.sub.sat[u]=max(h.sub.sat,f[u]/m.sub.f−h.sub.sat,b[u]/m.sub.b, 0), u=0, . . . , N.sub.sat−1; V.sub.hue[u]=max(h.sub.hue,f[u]/m.sub.f−h.sub.hue,b[u]/m.sub.b, 0), u=0, . . . , N.sub.hue−1. To avoid the situation that 0 is as the divisor, when m.sub.f or m.sub.b is less than 1, set it as 1.

(36) Further, the index tree is a k-d tree, and step S104 includes follows:

(37) In the k-d tree which is the index tree containing said feature information V.sub.1, . . . , V.sub.S corresponding to all sample images, feature information of one or more sample image which has or have the least square Euclidean distance

(38) $\mathrm{dist}\left(V_s,V_0\right)=\underset{k=0}{\overset{N_{\mathrm{feat}}-1}{.Math.}}{\left(V_s\left[k\right]-V_0\left[k\right]\right)}^2$
from the feature information of the image to be searched (V.sub.0) corresponding to the image to be searched, among which, N.sub.feat=N.sub.val+N.sub.sat+N.sub.hue represents the total number of elements in the feature array for each image.

(39) It is understood by those skilled in the art that, preferably, said feature information is an array contains N.sub.feat=21 (among which N.sub.val=5, N.sub.sat=4, N.sub.hue=12) real number, and then defining the square Euclidean distance between feature information V.sub.s corresponding to each sample image I.sub.s and feature information V.sub.o corresponding to the image to be searched based on the formula

(40) $\mathrm{dist}\left(V_s,V_0\right)=\underset{k=0}{\overset{N_{\mathrm{feat}}-1}{.Math.}}{\left(V_s\left[k\right]-V_0\left[k\right]\right)}^2,$
and use the search algorithm of k-d tree to query the subscript s of one or more sample image(s) that minimize the square Euclidean distance. The V.sub.s corresponding to each subscript s is the feature information corresponding to a sample image in the k-d tree, and V.sub.0 is the feature information corresponding to the image to be searched. It is understood by those skilled in the art that the smaller the square Euclidean distance of the feature information, the closer the feature information of the corresponding sample image is to the feature information of the image to be searched, which means that the sample image is similar to the image to be searched.

(41) Further, the k-d tree contains the features of all sample images, but does not contain the features of the image to be searched. Its purpose is to speed up the searching process, and it is not necessary to calculate the squared Euclidean distance from all sample image features and only a small part of the distance may be processed. The more recent sample image feature may be calculated, preferably by using the k-d tree search algorithm in the prior technology, and the smaller the square Euclidean distance, the higher degree of matching between the corresponding sample image and the image to be searched.

(42) Furthermore, according to the subscript s of the closest image among all the sample images, referring the corresponding image content, metadata and other information and finally returning to the client.

(43) The above describes the embodiments of the invention. And it is to be understood that, the invention is not limited to the embodiments mentioned above, those skilled in the art can transform and modify the embodiments within the range of claims, which doesn't affect the essential content of the invention.