# US 8,787,679 B1 · Shape-based search of a collection of content > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,787,679 B1 - Document ID: US8787679B1 - Status: Granted - Kind: B1 - Application number: 13/913,318 - Filed: 2013-06-07 - Granted: 2014-07-22 - Earliest claimed: 2010-09-30 - Assignees: A9.com, Inc. - Applicants: A9.com, Inc. - Inventors: Sunil Ramesh; Arnab Sanat Kumar Dhua; Gurumurthy D. Ramkumar; Gautam Bhargava; Sonja E. Hyde-Moyer - Web page: https://patentgrep.com/patent/US8787679B1 ## CPC - G06F 16/5854: {using shape and object relationship} - G06V 10/50: by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis - G06V 10/467: {Encoded features or binary features, e.g. local binary patterns [LBP]} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Shape-based search of a collection of content associated with one or more images of inventory items (“inventory images”) is enabled at least in part by associating the collection of content and/or its associated inventory images with representative refinement shapes. Inventory items may be grouped into categories and at least one refinement shape may be created for each of the categories. A refinement-shape hierarchy may be created by arranging the refinement shapes into parent and child refinement shapes. Inventory images may be associated to at least one of the refinement shapes of the refinement-shape hierarchy based at least in part on similarities between the refinement shapes and shapes of the inventory items reflected in the inventory images. ## Claims ### Claim 1 A computer-implemented method comprising: under the control of one or more computer systems configured with executable instructions, providing for display a plurality of refinement shapes configured to represent different types of shapes of a particular item available for selection by a user; causing a plurality of images of inventory items to be associated with at least one of the plurality of refinement shapes based at least in part on similarities between a first plurality of texture histogram descriptors associated with the refinement shapes and a second plurality of texture histogram descriptors associated with the inventory items; receiving information for a search request specifying at least one of the refinement shapes; and providing search results including at least a reference to at least one of the images of the inventory items associated with the at least one of the refinement shapes specified in the search request. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, further comprising: associating each of a plurality of training images of training items to at least one of the refinement shapes based at least in part on similarities between the refinement shapes and shapes of the training items. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, further comprising: determining texture histogram descriptors of the training images; and determining texture histogram descriptors of the images of the inventory items. ### Claim 4 (depends on 3) The computer-implemented method of claim 3, wherein the similarities between the refinement shapes and shapes of the inventory items are based at least in part on similarities between the descriptors of the images of the inventory items and the descriptors of the training images that are associated with the refinement shapes. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, further comprising: creating a refinement-shape hierarchy by arranging the refinement shapes in a plurality of levels. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein each of the texture histogram descriptors are combined with at least one of a contour descriptor, a global-shape descriptor, or a local-shape descriptor to generate a respective combined histogram descriptor. ### Claim 7 A non-transitory computer-readable storage medium storing instructions that, when executed by at least one processor, cause a computing device to: provide for display a plurality of refinement shapes configured to represent different types of shapes of a particular item available for selection by a user; cause a training image to be associated with at least one of the plurality of refinement shapes based at least in part on similarities between the refinement shape and a shape of an item in the training image; cause a first contour histogram descriptor of the training image to be determined; receive an image of an inventory item; cause a second contour histogram descriptor of the image of the inventory item to be determined; cause the image of the inventory item to be associated with the refinement shape based at least in part on similarities between the second contour histogram descriptor of the image and the first contour histogram descriptor of the training image; receive a search request including information associated with the at least one of the plurality of refinement shapes; and provide search results associated with the inventory item. ### Claim 8 (depends on 7) The non-transitory computer-readable storage medium of claim 7, wherein the instructions that, when executed by the at least one processor, cause a computing device to: cause the image of the inventory item to be associated with the at least one refinement shape based at least in part on a similarity between at least one texture histogram descriptor associated with the refinement shape and at least one second texture histogram descriptor associated with the inventory item. ### Claim 9 (depends on 7) The non-transitory computer-readable storage medium of claim 7, wherein the at least one refinement shape is arranged in a refinement-shape hierarchy. ### Claim 10 (depends on 9) The non-transitory computer-readable storage medium of claim 9, wherein the first contour histogram descriptor of the training image and the second contour histogram descriptor of the image of the inventory item are combined with at least one of a local-texture descriptor, a global-shape descriptor, or a local-shape descriptor to generate a respective combined histogram descriptor. ### Claim 11 (depends on 7) The non-transitory computer-readable storage medium of claim 7, wherein the refinement shapes correspond to common shapes of the inventory items. ### Claim 12 (depends on 7) The non-transitory computer-readable storage medium of claim 7, wherein the inventory items are shoes and the refinement shapes correspond to common shapes of shoes. ### Claim 13 (depends on 7) The non-transitory computer-readable storage medium of claim 7, wherein the refinement shapes are manually selected. ### Claim 14 A computing device, comprising: a processor; and memory including instructions that, when executed by the processor, cause the computing device to: provide for display a plurality of refinement shapes configured to represent different types of shapes of a particular item available for selection by a user; cause a plurality of images of inventory items to be associated with at least one of the plurality of refinement shapes based at least in part on similarities between a first plurality of contour histogram descriptors associated with the refinement shapes and a second plurality of contour histogram descriptors associated with the inventory items; receive information for a search request specifying at least one of the refinement shapes; and provide search results including at least a reference to at least one of the images of the inventory items associated with the at least one of the refinement shapes specified in the search request. ### Claim 15 (depends on 14) The computing device of claim 14, wherein the instructions, when executed by the processor, further enable the computing device to: associate each of a plurality of training images of training items to at least one of the refinement shapes based at least in part on similarities between the refinement shapes and shapes of the training items. ### Claim 16 (depends on 15) The computing device of claim 15, wherein the instructions, when executed by the processor, further enable the computing device to: determining texture histogram descriptors of the training images; and determining texture histogram descriptors of the images of the inventory items. ### Claim 17 (depends on 16) The computing device of claim 16, wherein the similarities between the refinement shapes and shapes of the inventory items are based at least in part on similarities between the descriptors of the images of the inventory items and the descriptors of the training images that are associated with the refinement shapes. ### Claim 18 (depends on 14) The computing device of claim 14, wherein the instructions, when executed by the processor, further enable the computing device to: creating a refinement-shape hierarchy by arranging the refinement shapes in a plurality of levels. ### Claim 19 (depends on 14) The computing device of claim 14, wherein each of the contour histogram descriptors are combined with at least one of a contour descriptor, a global-shape descriptor, or a local-shape descriptor to generate a respective combined histogram descriptor. ### Claim 20 (depends on 14) The computing device of claim 14, wherein the refinement shapes are manually selected.