Systems, methods, and computer-readable storage media for web-scale visual search capable of using a combination of visual input modalities are provided. An edgel index is created that includes shape-descriptors, including edgel-based representations, that correspond to each of a plurality of images. Each edgel-based representation includes pixels that depicts edges or boundary contours of an image and is created, at least in part, by segmenting the image into a plurality of image segments and performing a multi-phase contour detection on each segment. Upon receiving a search query having a visual query input, the visual query input is converted into shape-descriptors, including an edgel-based representation, and the shape-descriptors, including the edgel-based representation, of each of the plurality of images is compared with the shape-descriptors, including the edgel-based representation, of the visual query input to identify at least one image of the plurality of images that matches the visual query input.