Patent Publication Number: US-9424466-B2

Title: Shoe image retrieval apparatus and method using matching pair

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority under 35 U.S.C. §119 to Korean Patent Application No. 10-2013-0140791, filed on Nov. 19, 2013, the disclosure of which is incorporated herein by reference in its entirety. 
     TECHNICAL FIELD 
     The present invention relates to a shoe image retrieval apparatus and method using a matching pair, and more particularly, to an apparatus and method for retrieving a shoe image using information on a matching pair. 
     BACKGROUND 
     The related art shoe retrieval systems provide a service with enhanced user convenience to a user. Specifically, as online shopping malls are showing a steady and high growth rate, the shoe retrieval systems may quickly retrieve a product desired by a user from a product database (hereinafter, referred to as DB) and provide the product to the user. 
     In addition, smart equipment such as a smart phone, a tablet, a smart TV, a PC, etc., which has been widely used in recent years, provides an enhanced service for assisting consumer purchase decision-making. 
     Flow, Fabulous, etc. of Amazon (a9.com) are representative shoe retrieval systems, which are currently being serviced. 
     The related art shoe retrieval systems provide a service for sufficiently accommodating various requirements of users to filter inquired products according to predetermined conditions such as color and type in addition to a service for providing basic information on the inquired products such as product comments, prices, related links, and so on. 
     In addition, the related art shoe retrieval systems also provide a service for accurately and quickly retrieving a product desired by a user by adding a image retrieval function. 
     That is, when a shoe are photographed with a built-in camera in smart equipment of a user and the image of the photographed shoe is inputted, the related art shoe retrieval systems retrieve a shoe image most similar to the inputted shoe image from the DB and provide a service for displaying the retrieved shoe image on a screen of the smart equipment of the user. 
     Accordingly, the user may check information on shoes desired to be purchased, in real time. 
     However, the related art shoe retrieval system with an added image retrieval function considers only geometric information when comparing the image stored in the DB with the image photographed by the user. Thus it is impossible to accommodate all variations of the object to provide an accurate retrieval result obtained by reflecting image variations such as brightness, size, and rotation, and it is possible to generate an error in a matching stage when a plurality of the same shoes are included in the photographed image or a pair of objects have different geometric variations. 
     SUMMARY 
     Accordingly, the present invention provides a shoe image retrieval apparatus and method using a matching pair, which can accurately retrieve image information corresponding to an input image from the database and provide the retrieved image information, by normalizing a correspondence relation in consideration of geometric image transformation corresponding to the matching pair and allowing a similar image to be retrieved by applying the normalized correspondence relation. 
     In one general aspect, a shoe image retrieval apparatus using a matching pair includes: a matching region search unit configured to extract features from a query image and search a matching region based on the extracted features; a matching information detection unit configured to detect geometric image transformation on a matching pair between the searched matching region and an image stored in a database; and a similar image retrieval unit configured to retrieve image information corresponding to the query image from the database based on the detected geometric image transformation. 
     In another general aspect, a shoe image retrieval method using a matching pair includes: extracting features from a query image and searching a matching region based on the extracted features; detecting geometric image transformation on a matching pair between the searched matching region and an image stored in a database; and retrieving image information corresponding to the query image from the database based on the geometric image transformation. 
     Other features and aspects will be apparent from the following detailed description, the drawings, and the claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a view illustrating a shoe image retrieval apparatus using a matching pair according to an embodiment of the present invention. 
         FIG. 2  is a view illustrating a method of searching a matching region. 
         FIG. 3  is a view illustrating a method of identifying a matching pair region. 
         FIG. 4  is a view illustrating a result of searching a matching region. 
         FIG. 5  is a view illustrating a matching information detection structure. 
         FIG. 6  is a view illustrating a method of extracting a matching pair between a comparison image and a matching region. 
         FIG. 7  is a view illustrating a self matching to a similar region in an image. 
         FIG. 8  is a view illustrating an image retrieval service using smart equipment. 
         FIG. 9  is a flowchart illustrating a shoe image retrieval method using a matching pair according to an embodiment of the present invention. 
         FIG. 10  is a view illustrating a configuration of a computer device in which a method for automatically generating a visual annotation based on a visual language according to an embodiment of the present invention is executed. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Advantages and features of the present invention, and implementation methods thereof will be clarified through following embodiments described with reference to the accompanying drawings. The present invention may, however, be embodied in different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the present invention to those skilled in the art. The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments. As used herein, the singular forms “a,” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. 
     Hereinafter, a shoe image retrieval apparatus using a matching pair according to an embodiment of the present invention will be described with reference to  FIGS. 1 to 8 .  FIG. 1  is a view illustrating a shoe image retrieval apparatus using a matching pair according to an embodiment of the present invention,  FIG. 2  is a view illustrating a method of searching a matching region,  FIG. 3  is a view illustrating a method of identifying a matching pair region,  FIG. 4  is a view illustrating a result of searching a matching region,  FIG. 5  is a view illustrating a matching information detection structure,  FIG. 6  is a view illustrating a method of extracting a matching pair between a comparison image and a matching region,  FIG. 7  is a view illustrating a self matching to a similar region in an image, and  FIG. 8  is a view illustrating an image retrieval service using smart equipment. 
     As shown in  FIG. 1 , a shoe image retrieval apparatus using a matching pair of the present invention includes a matching region search unit  100 ; a matching information detection unit  200 , and a similar image retrieval unit  300 , and when a shoe image is inputted, as a query image, by a user via a terminal, detects geometric image transformation about a matching pair between an inputted shoe image and an image stored in a database (DB)  400 , retrieves image information corresponding to the inputted shoe image from the DB  400  based on the detected geometric image transformation, and displaying the retrieved image information on a terminal of a user. 
     The matching region search unit  100 , as shown in  FIG. 2 , includes an image feature detection unit  110 , a matching region classification unit  120 , and a matching region identification unit  130 . 
     When a shoe image is inputted, as a query image, by a user via a terminal, the image feature detection unit  110  detects features invariant to image scaling and rotation, from the inputted shoe image using Scale-Invariant Feature Transform (SIFT) algorithm. 
     That is, the image feature detection unit  110  extracts Scale-space extrema to detect features, from the inputted shoe image using Scale-Invariant Feature Transform-Laplacian of Gaussian (SIFT-LoG) applied LoG (Laplacian of Gaussian) instead of DoG (Difference of Gaussian). 
     The matching region classification unit  120  decomposes the detected features by components in a threshold range predetermined according to the geometric property taken from points adjacent to the features, groups the features decomposed by components into a group having a similar component according to a predetermined condition to form a matching region, and classifies the inputted shoe image for each matching region. 
     The matching region identification unit  130  determines whether there is a similar matching region in the shoe image classified by matching regions and as a result of the determination, separates the shoe image into a self matching region and a single matching region in order to identify a case where a pair of or a plurality of shoes (specific matching region) are included in the shoe image classified by the matching regions. 
     That is, the matching region identification unit  130  identifies the shoe image classified by the matching regions as the self matching region when there is the similar matching region in the shoe image and as the single matching region when there is not the similar matching region in the shoe image. 
     For example, when the shoe image is delivered from the matching region classification unit  120 , as shown in  FIG. 3 , the matching region identification unit  130  labels and groups matching regions positioned within a predetermined range from the delivered shoe image in operation S 131 . 
     Subsequently, the matching region identification unit  130  performs matching between all groups to determine whether a group having the same region as a specific group is positioned at another position of the shoe image, and when the group having the same region as the specific group is positioned at another position as a result of the determination, recognizes the specific group and the group having the same matching region as the specific group as a similar matching region to identify the shoe image as the self matching region in operation S 132 . 
     More specifically, as shown in  FIG. 4 , the matching region identification unit  130  groups matching regions in the shoe image classified by the matching regions, performs matching between the groups, and determines whether there is a group having the same matching region as a specific group A. 
     As a result of the determination, when there is a group B having the same matching region as the specific group A, the matching region identification unit  130  recognizes the group B as a similar matching region of the specific group A, identifies the shoe image classified by the matching regions as the self matching region, and identifies positions of the group A and the group B based on an image coordinate system. 
     Accordingly, the matching region search unit  100  may recognize that the inputted shoe image includes a pair of shoes (matching regions). 
     The matching information detection unit  200  includes a correspondence relation generation unit  210 , a geometric image transformation modeling unit  220 , a candidate feature detection unit  230 , and a matching data classification unit  240 , and determines a matching pair between the shoe image identified as the self matching region or single matching region and the image stored in the DB  400  to generate a correspondence relation therebetween, models the generated correspondence relation with respect to geometric image transformation components, selects a candidate matching pair that meets a predetermined matching condition on the basis of the modeled correspondence relation, and calculates a correlation from the selected candidate matching pair to classify final-matching data. 
     To this end, as shown in  FIG. 6 , the correspondence relation generation unit  210  detects matching pairs between a specific matching region A of the shoe image identified as the self matching region and a comparison image stored in the DB  400  and forms correspondence information corresponding to geometric image transformation, using the detected matching pairs. 
     The detected matching pairs are also used to normalize the formed correspondence information. 
     When the matching pairs between the specific matching region A of the shoe image identified as the self matching region and the comparison image stored in the DB  400  are detected, as shown in  FIG. 7 , the correspondence relation generation unit  210  generates a symmetry axis C between the specific matching region A and a matching region B recognized as a similar matching region similar to the specific matching region A and additionally detects matching pairs orthogonal to the generated symmetry axis C. 
     In addition, when the initial symmetry axis C is generated between the specific matching region A of a shoe region identified as the self matching region and the matching region B recognized as similar to the specific matching region A, the correspondence relation generation unit  210  generates the symmetry axis C corresponding to a vertical axis direction of the shoe image and changes the symmetry axis C according to a correspondence structure such that an euclidean distance between feature pairs detected by the image feature detection unit  110  may be smallest. 
     The geometric image transformation model unit  220  models both phase related information such as size, rotation, and geometric transformation according to distribution of the matching pairs detected between the specific matching region A of a shoe region identified as the self matching region and image variation information about variation in an image due to brightness, lightning, shadow, etc. of the detected matching pair. 
     For example, the geometric image transformation modeling unit  220  calculates a mathematical model and a matching coefficient specialized in geometric image transformation from the detected matching pair, using an optimization algorithm such as RANdom SAmple Consensus (RANSAC). 
     The candidate feature detection unit  230  detects a candidate matching pair among the matching pairs detected based on correspondence information formed by the correspondence generation unit  210  according to a predetermined threshold range of the calculated mathematical model and matching coefficient. 
     The matching data classification unit  240  finds a one-to-one correspondence pair having a correlation higher than a predetermined value from each one-to-N correspondence pair among correspondence pairs according to a correspondence relation, that is, a correspondence correlation between the candidate matching pairs detected by the candidate feature detection unit  230 , normalizes the one-to-one correspondence pair, and determines final-matching data on the basis of a result of the normalization. 
     As shown in  FIG. 8 , the similar image retrieval unit  300  includes an image retrieval module  310 , and provides an image retrieval service. 
     For example, when matching pair variation information, that is, the determined final matching data is delivered from the matching information detection unit  200 , the image retrieval module  310  retrieves an image similar to the query image (the inputted shoe image) from the DB  400  on the basis of the delivered final-matching data to select a candidate ranking and displays the retrieved similar image on a user&#39;s terminal through an image retrieval interface according to the selected candidate ranking. 
     As described above, according to the present invention, it is possible to detect optimum geometric image transformation from a matching pair between an inputted shoe image and an image stored in the database and simultaneously retrieve a plurality of objects in the inputted shoe image based on the detected geometric image transformation, thereby providing an efficient shoe retrieval service. 
     The shoe image retrieval apparatus using a matching pair according to an embodiment of the present invention has been described with reference to  FIGS. 1 to 8 . Hereinafter, a shoe image retrieval method using a matching pair according to an embodiment of the present invention will be described with reference to  FIG. 9 .  FIG. 9  is a flowchart illustrating a shoe image retrieval method using a matching pair according to an embodiment of the present invention. 
     As shown in  FIG. 9 , the method includes determining whether a query image, that is, a shoe image is inputted by a user via a terminal in operation S 900 . 
     As a result of the determination, when the shoe image is inputted, features that is invariant to image scaling and rotation is detected from the inputted shoe image using Scale-Invariant Feature Transform (SIFT) algorithm. 
     That is, Scale-space extrema to detect features is extracted from the inputted shoe image using Scale-Invariant Feature Transform-Laplacian of Gaussian (SIFT-LoG) applied LoG (Laplacian of Gaussian) instead of DoG (Difference of Gaussian). 
     The detected features is decomposed by components in a threshold range that is predetermined according to the geometric property taken from points adjacent to the features, the features decomposed by components is grouped into a group having a similar component according to a predetermined condition to form a matching region, and the inputted shoe image is classified for each matching region. 
     In order to identify a case where a pair of or a plurality of shoes (specific matching region) are included in the shoe image classified by the matching regions, the shoe image classified by matching regions is separated into a self matching region and a single matching region according to whether there is a similar matching region in the shoe image classified by matching regions. 
     That is, the shoe image classified by the matching regions is identified as the self matching region when there is the similar matching region in the shoe image and as the single matching region when there is not the similar matching region in the shoe image. 
     For example, matching regions positioned within a predetermined range from the shoe image classified by the matching regions are labeled and grouped, all groups are matched to determine whether a group having the same region as a specific group is positioned at another position of the shoe image in operation S 901 , and when the group having the same region as the specific group is positioned at another position as a result of the determination, the specific group and the group having the same matching region as the specific group are recognized as the similar matching region to identify the shoe image as the self matching region. 
     The method includes detecting matching pairs between the specific matching region of a shoe image identified as the self matching region and a comparison image stored in the DB  400  in operation S 902 , and correspondence information corresponding to geometric image transformation is formed using the detected matching pair. 
     That is, the matching pairs are used to form and normalize the correspondence information corresponding to geometric image transformation. 
     When the matching pairs between the specific matching region of the shoe image identified as the self matching region and the comparison image stored in the DB  400  are detected, a symmetry axis is generated between the specific matching region and a matching region recognized as a similar matching region similar to the specific matching region and matching pairs orthogonal to the generated symmetry axis are additionally detected. 
     In addition, when the initial symmetry axis is generated between the specific matching region of the shoe region identified as the self matching region and the matching region recognized as the similar matching region, the symmetry axis corresponding to a vertical axis direction of the shoe image is generated and the symmetry axis is changed according to a correspondence structure such that an euclidean distance between the detected feature pairs may be smallest. 
     Both phase related information such as size, rotation, and geometric transformation according to distribution of the matching pairs detected between the specific matching region of a shoe region identified as the self matching region and image variation information about variation in an image due to brightness, lightning, shadow, etc. of the detected matching pairs are modeled. 
     For example, a mathematical model and a matching coefficient specialized in geometric image transformation are calculated from the detected matching pair, using an optimization algorithm such as RANdom SAmple Consensus (RANSAC). 
     A candidate matching pair is detected among the detected matching pairs, according to a predetermined threshold range of the calculated mathematical model and matching coefficient. 
     A one-to-one correspondence pair having a correlation higher than a predetermined value is found from each one-to-N correspondence pair among correspondence pairs according to a correspondence correlation between the detected candidate matching pairs, the one-to-one correspondence pair is normalized, and final-matching data is determined based on a result of the normalization. 
     The method includes retrieving an image similar to the query image (the inputted shoe image) from the DB  400  on the basis of the determined final-matching data to select a candidate ranking in operation S 903  and displaying the retrieved similar image on a user&#39;s terminal through an image retrieval interface according to the selected candidate ranking in operation S 904 . 
     According to the present invention, it is possible to detect optimum geometric image transformation from the matching pair between the inputted shoe image and the image stored in the database and simultaneously retrieve a plurality of objects in the inputted shoe image based on the detected geometric image transformation, thereby, as described above, providing an efficient shoe retrieval service. 
     A method for automatically generating a visual annotation based on a visual language according to an embodiment of the present invention may be implemented in a computer system, e.g., as a computer readable medium. As shown in  FIG. 10 , a computer system  1200 - 1  may include one or more of a processor  1210 , a memory  1230 , a user input device  1260 , a user output device  1270 , and a storage  1280 , each of which communicates through a bus  1220 . The computer system  1200 - 1  may also include a network interface  1290  that is coupled to a network  1300 . The processor  1210  may be a central processing unit (CPU) or a semiconductor device that executes processing instructions stored in the memory  1230  and/or the storage  1280 . The memory  1230  and the storage  1280  may include various forms of volatile or non-volatile storage media. For example, the memory may include a read-only memory (ROM)  1240  and a random access memory (RAM) 1250. 
     Accordingly, a method for automatically generating a visual annotation based on a visual language according to an embodiment of the present invention may be implemented as a computer implemented method or as a non-transitory computer readable medium with computer executable instructions stored thereon. In an embodiment, when executed by the processor, the computer readable instructions may perform a method according to at least one aspect of the invention. 
     It should be understood that although the present invention has been described above in detail with reference to the accompanying drawings and exemplary embodiments, this is illustrative only and various modifications may be made without departing from the spirit or scope of the invention. Thus, the scope of the present invention is to be determined by the following claims and their equivalents, and shall not be restricted or limited by the foregoing detailed description.