Complex-object detection using a cascade of classifiers

Complex-object detection using a cascade of classifiers for identifying complex-objects parts in an image in which successive classifiers process pixel patches on condition that respective discriminatory features sets of previous classifiers have been identified and selecting additional pixel patches from a query image by applying known positional relationships between an identified complex-object part and another part to be identified.

BACKGROUND OF THE PRESENT INVENTION

Computer-based object detection systems and methods are used in many different applications requiring high accuracy achieved in near real-time. Examples of such applications include active vehicular safety systems, smart surveillance systems, and robotics.

In the area of vehicular safety, for example, accurate high-speed identification of pedestrians or objects in the path of travel enables an automated safety system to take necessary measures to avoid collision or enables the automated system to alert the driver allowing the driver to take necessary precautions to avoid collision.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale and reference numerals may be repeated in different figures to indicate same, corresponding or analogous elements.

DETAILED DESCRIPTION OF THE PRESENT INVENTION

In the following detailed description, numerous details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. Furthermore, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention.

It should be appreciated that the following terms will be used throughout this document.

“Complex-object” refers to an object which is present in an image and requires a plurality of templates to be described or identified because of various complexities associated with the object. These complexities may include object parts having a variant anthropometric relationship with each other, large size variations within a particular classification, partial obstruction, and multiple views. Typical examples include inter-alia people, animals, or vehicles. For the purposes of this document, and without derogating generality, a person will be highlighted as an example of a complex-object.

“Classifier” refers to a function (e.g. a computer executable function) configured to identify image object parts based on discriminative features characteristic of parts associated with complex-objects. The discriminative features may typically be processed to produce, for example, an output value which is compared to a threshold value derived analogously from a model image to determine a “match”. Such matching may be based, for example, on imaging parameters like pixel intensities, geometrical primitives, and/or other image parameters.

“Cascade of classifiers” refers to a plurality of successive classifiers.

“Pixel patch” refers to a region of pixels.

“Discriminative features” refers to parameters of such image pixels as, for example, intensities gradients, average intensities, pixel colors and are representative of a feature of the image content.

“Anthropometric relationship” refers to the relative size, placement and orientation of body parts in human beings as projected in the image.

“Collaborative search” refers to selecting pixel patches in a query image based on prior, successful identification or classification of at least one complex-object part.

According to embodiments of the present invention a method for complex-object detection using a cascade of classifiers may involve identifying a pixel patch in a query image and processing it using a cascade of classifiers in search of learned discriminatory features. As noted above, the cascade of classifiers may have a succession of classifiers in which each classifier may be configured to identify its respective discriminatory feature set. Each successive classifier in the cascade searches for a greater number of discriminatory features for the same object part and is configured to identify its respective discriminative feature set only after previously employed classifier have successfully identified their respective discriminatory features. If this has not been achieved, each successive stage-classifier does not process the pixel patch and that particular patch is rejected and designated as an area lacking the required discriminative features. Another pixel patch may be then selected from the query image on a random or semi-random basis. In other embodiments an adjacent patch or any other patch may be selected as the next patch to process when prior classifiers do identify their respective discriminatory feature sets, successive classifiers process the pixel set until an object part is identified. After found, the object part location together with learned spatial relationships between object parts of a model object image serves as the basis for propagating additional, pixel patches within the query image likely to contain additional object parts. Other embodiments employ a data map in which the maximum of an argument of a probability function is used to select an additional pixel set having the greatest probability of containing an object part.

The collective computational savings afforded by the reduced number of classification operations for each part and the reduced number of search locations, according to embodiments of the present invention, enable near real-time, highly accurate identification of complex objects. Accordingly, the method and system according to the present invention have application in a wide variety of real world applications requiring accurate and quick complex-object identification like active vehicular safety features, smart surveillance systems, and robotics.

Turning now to the figures,FIG. 1is a schematic diagram of a system for complex-object detection using a cascade of classifiers according to an embodiment of the present invention. Complex object detection system100may include one or more computer vision sensors10(e.g., cameras, video camera, digital camera, or other image collection devices). Computer vision sensor10may capture an image that may include one or more objects and/or features. Images may also be otherwise input into system100, for example, as downloads from other computers, databases or systems. Object detection system100may include one or more processors or controllers20, memory30, long term non-transitory storage40, input devices50, and output devices60. Non-limiting examples of input devices50may be, for example, a touch screen, a capacitive input device, a keyboard, microphone, pointer device, a button, a switch, or other device. Non-limiting examples of output devices include a display screen, audio device such as speaker or headphones. Input devices50and output devices60may be combined into a single device.

Processor or controller20may be, for example, a central processing unit (CPU), a chip or any suitable computing device. Processor or controller20may include multiple processors, and may include general purpose processors and/or dedicated processors such as graphics processing chips. Processor20may execute code or instructions, for example stored in memory30or long term storage40, to carry out embodiments of the present invention.

Long term, non-transitory storage40may be or may include, for example, a hard disk drive, a floppy disk drive, a Compact Disk (CD) drive, a CD-Recordable (CD-R) drive, a universal serial bus (USB) device or other suitable removable and/or fixed storage unit, and may include multiple or a combination of such units. It should be appreciated that image data, code and other relevant data structures are stored in the above noted memory and/or storage devices.

FIG. 2is a query image210containing a complex object220of a person to be classified by indentifying various parts; head240, back250, and foot260. It should be appreciated that for the purpose of this document a person will be used as a non-limiting example of a complex-object.

FIG. 3depicts an image of complex-object model330from which discriminative feature sets for each part and anthropometric relationships between the parts may be extracted. Model complex object330is divided into pixel patches or image areas containing object parts. In the non-limiting example ofFIG. 3the complex object is person330in which three independent parts have been identified; a head340, a back350, and a foot360. It should be appreciated that a wide variety of complex-objects are suitable models that can be used to learn stage-classifiers. Such models include living and inanimate objects, objects having a large number of parts, objects having parts whose geometrical relationship to each other is variant, objects partially obstructed, all objects viewed from various angles or distances as noted above.

FIG. 4depicts three graphical representations,405,410, and415, of features derived from a front view of image sample (not shown). These features are used in learning successive classifiers of a cascade according to embodiments of the present invention. A feature selection algorithm may be applied to image sample to obtain graphical representations405,410, and415that may be further processed to identify discriminative features most characteristic of features associated with a sample. For example, the feature selection algorithm may generate ideal discriminative features based on only two pixel areas406and407for use with a first classifier, ideal discriminative features based also on pixel areas411-413for use with a second classifier, and seven additional pixel areas collectively designated414for use with a third classifier. In this manner, each classifier of a three-classifier cascade is enabled to identify distinguishing features of an object part associated with the complex-object with increasing accuracy and clarity.

It should be noted that there are many pixel or image parameters that may be used for extracting most effective feature identifying discriminative features and a few examples include Histogram of Gradients (HoGs), integral channel features and Haar features. Furthermore, it should be appreciated that in the example ofFIG. 4frontal facial features are identified from a sample image; however, features may be extracted from side views of sample images in accordance with the particular view of the object part to be identified.

FIG. 5depicts a three-classifier cascade configured to use the learned discriminative features on a stage-by-stage basis to identify complex-object part240according to embodiments of the present invention.

As noted above, each successive classifier searches object part240to identify its respective set of discriminative features. In the present, non-limiting example, first stage-classifier505checks candidate object part240for discriminative features derived from graphic representation405. If they are not found, the identified pixel patch is rejected and system100either propagates additional search areas in query image210or applies first stage-classifier505to additional pixel patches of complex-object parts in queue. If first classifier505identifies this first set of discriminative features, second classifier510searches for a second set of discriminative features derived from graphic representation410. If classifier510does not identify them, this pixel patch object is also rejected as noted above. If a match is achieved, third classifier515is applied and attempts to identify the discriminative features derived form graphic representation415. If a match is not identified, the searched pixel patch part is rejected, whereas, if a match is identified the object part240is deemed to have been identified by the cascade of classifiers520. It should be noted that any cascade of classifiers including any number of classifiers employing any numbers of discriminative features may be considered in embodiments of the present invention.

It should be noted that upon rejection, the pixel patch found to be devoid of the discriminative features is designated as a non-viable area in regards to this particular object part to avoid unnecessary searches in the same area for the part for which it was rejected. It should be noted that the present invention includes embodiments in which pixel patches are rejected in reference to a particular part and may indeed be searched for additional object parts.

FIG. 6depicts an example of classifier processing of pixel patches at five different locations I-V in which five separate cascades of three classifiers1-3each are employed to identify three complex-object parts1-3according to embodiments of the present invention. As depicted, classifiers1adetermine that content from locations I and III lack the desired features and so there is no further processing of remaining classifiers1band1cof content from these locations. Classifiers2bcontinue processing content from remaining locations II, IV and V. Classifier2bdetermines that content from location V also lacks the desired features and so classifiers1ccontinue processing content from locations II and IV only. Classifier1cdetermines that content from location IV also lacks the desired features and classifier1processing content from location II identifies the desired features and so part1is deemed to have been located at location II.

The search for complex-object part2may be continued at several (e.g. five) different locations in which respective pixel patches from locations VI-X are processed by another cascade of three classifiers2a-2c. Content from locations VII and VIII is rejected by classifier2aand so processing continues by classifiers2bof content from remaining locations VI, VIII and X. Classifiers2breject content from location VIII and so processing continues by classifiers2cof content derived from locations VI and X. Classifier2crejects content derived from location VI while classifier2aidentifies the relevant features in the content derived from location X. Since all three classifiers2a-2cidentified the relevant features in the content derived form location X, part2is deemed to have been identified.

The search for part three continues with five cascades of three classifiers each3a-3cof content derived from locations VI-X. Classifier3arejects content derived from location XIIII so processing continues of pixel patches derived from remaining locations XI-XII and XV. Classifier3brejects content derived from location XIII and classifiers3ccontinue processing content derived from remaining locations XI-XII and XV and then reject content derived form locations XII and XV. Remaining classifier3cidentifies the relevant features in content derived from location XI. Again, since all three classifiers3a-3chave identified the relevant features in the content derived from this location, part3is deemed identified at location XI.

FIG. 7and is a flow charts depicting the method described above with the additional steps of propagating additional search areas or pixel patches for remaining object parts after classification of an object part.

Specifically, in step710according to an embodiment of the present invention, a first pixel patch may be selected from query image210, e.g. on a random basis according to embodiments of the invention.

In step715, successive classifiers may be applied to each part on condition that all previous classifiers of the cascade have identified their respective discriminatory feature sets. In step720, if all respective discriminatory feature sets of all the classifiers have been identified, an object part is deemed to have been classified or identified as noted above. If, however, not all respective discriminatory feature sets have been identified, that pixel patch is designated as “Rejected” in step721and a new pixel patch is selected from the query image210on a random or semi-random basis in step710. Again, successive classifiers process the newly selected pixel patch as shown in step715. When all classifiers have successfully identified their respective discriminatory features, then an object part has been classified as shown in step725and an additional pixel patch is selected from query image based on learned spatial relationships between the previously identified object part (if there is one) and the part to be indentified as depicted in step730. After a new pixel patch likely containing the additional object part is selected, the process is repeated by applying successive classifiers associated with the additional part as shown in step715.

The method depicted inFIG. 8is analogous to the method illustrated inFIG. 7with an alternative manner of selecting additional pixel patches likely containing additional object parts in which a probability map is employed as shown in step830.

Specifically, a probability value ranging between zero and one is assigned to every pixel in response to output values of each classifier processing a particular pixel patch. After an object part is identified, the probability map is updated accordingly and a pixel patch selected is by calculating the argument of the maximum (Argmax) of a probability function for the next object part, or equivalently:
ArgmaxPn+1Prob(Pn+1|P′n+1,P1, . . . ,Pn) wherein:

Pn+1is the previous probability map.

Regions having probability values less than a pre-defined value are rejected by setting the probability values to zero.

FIG. 9andFIG. 10are query images210ofFIG. 2with superimposed search windows indicating areas being searched for an object part. In various embodiments, system for complex-object detection using a cascade of classifiers, according to an embodiment of the present invention may be configured to propagate search windows enclosing an area substantially corresponding to the area of the learned object part. By way of a non-limiting example, search windows970and975enclose areas corresponding to areas containing a learned head340and a learned back350, respectively, ofFIG. 3. Furthermore, search windows970and975may be propagated in a plurality of locations in which a portion of the new search area overlaps a portion of the previous searched area as shown or in a method which is entirely random for either the first pixel patch selected or two replace patches rejected as lacking the relevant discriminative features.

When an object part is identified, it is used as a basis for propagating additional search areas most likely containing the requested object part as noted above. Some embodiments apply a learned anthropometric relationship to the identified part to direct the ensuing search area to pixel areas most likely containing the additional part as noted above. Other embodiments use the location of the identified part as a priori data when determining the “maxarg” of a probability function for all parts as noted above. Window980indicates that head240(FIG. 2) has been located and therefore search windows990and1090(FIG. 10) are propagated in areas most likely to contain back250because these areas represent the anthropometric relationship of these parts in model image330ofFIG. 3. Since both sides of the object220fulfill leaned anthropometric relationship, both search windows990and1090areas are identified as appropriate pixel patches to be searched.

In some embodiments of the present invention, when employing probability maps, both areas enclosed in windows990and1090may be determined to have a high probability of containing back.250in view of the updated probability data. It should be appreciated that any plurality of searches are included within the scope of the present invention.

FIG. 11illustrates an embodiment in which pixel patches are propagated on the basis of successful identification or classification of a plurality of object parts. For example, both head240and foot260(FIG. 3) have been identified in search windows1110and1120, respectively. Search window1190is propagated on the basis of learned anthropometric relationships between each of these parts from the model image330depicted inFIG. 3or updated probability data. It should be appreciated that embodiments in which additional search areas are propagated on the basis of any number of previously identified object parts are included within the scope of the present invention.

In some embodiments of the present invention computational is efficiency further optimized by reducing search redundancy. Window1100is a window designating a rejected pixel patch or area after any one of the classifiers of a cascade has determined that the patch is devoid of discriminative features.

FIG. 12andFIG. 13illustrate applications of the above described, cascade-classifier assisted search for complex-object partially obstructed or reduced-in-scale, respectively according to embodiments of the present invention. Specifically, head240is identified within window1210and window1220is propagated as a possible location for foot260based on either learned anthropometric relationship between the head340and feet360ofFIG. 3or based on probability data in view of identified head240, as noted above.

FIG. 14depicts a non-limiting, computer-readable media containing executable code for configuring a computer system to execute the above described, cascade-classifier assisted search for complex-objects within an image according to embodiments of the present invention.

Embodiments of the present invention identify a complete-object by combining object parts indentified in various pixel patches.

It should be appreciated that search areas may be propagated on the basis of any number of successfully identified object parts in accordance to the particular embodiment. It should be further appreciated that search like circular, triangular, and polygonal shaped search widows are within the scope of the present invention.