Method and/or apparatus for object detection utilizing cached and compressed classifier information

[0001] The present invention relates to image processing generally and, more particularly, to a method and/or apparatus for implementing object detection utilizing cached and compressed classifier information.

[0002] Detecting objects by locating the position and size of objects in digital images is an important technology used in numerous applications. In digital cameras, the ability to detect faces can offer improvement in automatic camera control functions such as exposure, focus, color balance, and flash control. Video cameras can also utilize object detection to control various recording modes and qualities. Object detection also serves as a prerequisite function needed to enable more advanced features, such as smile-triggered shutter control, eye-blink avoidance, and object recognition.

[0003] One conventional object detection method is implemented as a binary pattern-classification task. In a binary pattern-classification task, the content of a given part of an image is transformed into features. Afterwards, a classifier trained on example objects determines whether a particular region of the image is an object or a non-object. Objects can be faces or other features. Non-objects can be background patterns. A window-sliding technique is often employed. In a window-sliding technique, a classifier is used to classify portions of an image. The portions of the image are classified at all locations and scales as either objects or non-objects. The portions of the image classified are usually square or rectangular.

[0004] A commonly used conventional approach for object detection is based on the Viola-Jones method. The general structure of the Viola-Jones method is composed of a hierarchy of layers. At the lowest hierarchy layer, a window associated with an image area for examination is used to determine whether the image area contains an object or not an object. The resolution of the window is coarse enough to ignore detail that does not relevantly contribute to the decision, yet fine enough to resolve differences in broad object features. Broad object features may include eyes, nose or a mouth for face detection methods in digital images. Over this window, features or measures are computed, and classification is performed using these features as inputs. The classifier output is a binary decision value declaring “Object” or “Not-Object”.

[0005] The window is scanned spatially to cover all locations of the input image for performing object detection. To be able to perform object detection over a range of possible object sizes, the scanning process is repeated over a range of scale sizes. The scaling may be accomplished using two methods. For the first method, the window size and associated feature computations are scaled through the range of desired scales, using the same intact input image. For the second method, the window size is kept fixed and the original input image is scaled down, forming a series of downsampled images to cover the scale range. The choice to either scale the scanning window or to scale the input images is an implementation choice.

[0006] The classifier in the Viola-Jones method is composed of layers of sub-classifiers arranged in a hierarchical tree-like structure. At the lowest level, a weak classifier is formed using one or more Haar features computed in the operating window. Haar features are sums of pixels over rectangular regions.

[0007] A particular realization of the Viola-Jones classifier can be described by parameters that define structure and decision processing. The overall-defining parameter set is derived through training for the particular detection task at hand, and serves as the blueprint for executing the detection task. The parameters may include the number of rectangles that make up the Haar feature for each weak classifier, rectangle weights in the summation of the Haar feature, rectangle coordinates in the operating window, or weak classifier decision thresholds and decision output weights.

[0008] Classifiers can be described by a set of programmable instructions which are loaded from external memory. Loading classifier instructions from external memory allows classifiers to be tuned, changed, and upgraded.

[0009] The bandwidth involved in fetching classifier parameters from an external memory can limit the ability for object detection tasks to perform in a fast and efficient way necessary for certain applications, such as real-time video applications.

[0010] It would be desirable to implement a processor used for object detection that operates efficiently for use in real-time video applications.

[0011] The present invention concerns an apparatus comprising a classifier cache, a plurality of variable length decoder circuits and a core engine circuit. The classifier cache may be configured to store one or more compressed classifier streams. The plurality of variable length decoder circuits may each be configured to generate one or more uncompressed classifier streams in response to a respective one of the compressed classifier streams received from the classifier cache. The core engine circuit may be configured to detect one or more objects in a video signal by checking a portion of the video signal using the uncompressed classifier streams.

[0012] The objects, features and advantages of the present invention include providing an object detection classifier that may (i) detect objects in digital images using a processor architecture, (ii) employ internal memory cache for storing classifiers, (iii) employ a compressed representation of classifiers, (iv) partition classifier definitions into multiple parallel processing streams, (v) decompress classifiers by implementing one or more variable length decoders and/or (vi) provide a fast and efficient implementation.

[0018] The present invention provides a dedicated processor for implementing object detection in a video system. While the specific architectures described are specifically applicable to the Viola-Jones-based object detection, the present invention may be used for object detection in any system that involves lengthy programmable classifier definitions.

[0019] Referring to FIG. 1, a block diagram 100 of an object detection classifier is shown in accordance with a preferred embodiment of the present invention. The circuit 100 generally comprises a block (or circuit) 102, a plurality of blocks (or circuits) 104a-104c, a block (or circuit) 106, a block (or circuit) 108, a block (or circuit) 110, a block (or circuit) 112 and a block (or circuit) 120. In one example, the circuit 102 may be implemented as a compressed classifier cache circuit. The circuit 102 may be configured to store a plurality of compressed classifier streams. In one example, the circuits 104a-104c may be implemented as variable length decoder (VLD) circuits. In one example, the circuit 106 may be implemented as a buffer circuit. In one example, the circuit 108 may be implemented as a search region fetcher and downsampler circuit. In one example, the circuit 110 may be implemented as a core engine circuit. In one example, the circuit 112 may be implemented as a buffer circuit. In one example, the circuit 120 may be implemented as an external dynamic random access memory (DRAM) circuit.

[0020] The circuit 102 may have an input 156 that may receive a signal (e.g., UPDATE), an output 160a that may present a signal (e.g., BSTR_—1), an output 160b that may present a signal (e.g., BSTR_—2), an output 160c that may present a signal (e.g., BSTR_—3) and an output 162 that may present a signal (e.g., STREAM_—4). The circuit 104a may have an input 164a that may receive the signal BSTR_—1 and an output 166a that may present a signal (e.g., STREAM_—1). The circuit 104b may have an input 164b that may receive the signal BSTR_—2 and an output 166b that may present a signal (e.g., STREAM_—2). The circuit 104c may have an input 164c that may receive the signal BSTR_—3 and an output 166c that may present a signal (e.g., STREAM_—3). The signals BSTR_—1, BSTR_—2 and BSTR_—3 may be compressed signals that include parameters or a library stored in the classifier cache 102. A particular number of compressed signals may be varied (e.g., either increased or decreased) to meet the design criteria of a particular implementation. The signals STREAM_—1, STREAM_—2, STREAM_—3 and STREAM_—4 may be uncompressed signals. The particular number of uncompressed signals may be varied (e.g., either increased or decreased) to meet the design criteria of a particular implementation. The signal UPDATE may be used to provide updates to the information stored in the circuit 102.

[0021] The circuit 106 may have an input 140 that may receive a signal (e.g., IN) and an output 142 that may present a signal (e.g., INT1). The circuit 108 may have an input 144 that may receive the signal INT1 and an output 146 that may present a signal (e.g., INT2). The circuit 110 may have an input 148 that may receive the signal. INT2, an input 168a that may receive the signal STREAM_—1, an input 168b that may receive the signal STREAM_—2, an input 168c that may receive the signal STREAM_—3, an input 170 that may receive the signal STREAM_—4 and an output 150 that may present a signal (e.g., INT3). The circuit 112 may have an input 152 that may receive the signal INT3 and an output 154 that may present a signal (e.g., OUT). The signal IN may represent an input video signal comprising a series of images. The signal IN may also represent a single input image. The signal OUT may represent detection results. For example, the signal OUT may point to one or more portions of the signal IN that have particular features and/or objects detected by the circuit 110. The circuit 106 may be a buffer circuit configured to provide an input buffer for the signal IN. The circuit 112 may be a buffer circuit configured to provide an output buffer that presents the signal OUT.

[0022] The core engine circuit 110 may be configured to receive the signals STREAM_—1, STREAM_—2, STREAM_—3 and STREAM_—4. The circuit 110 may identify a search region of the signal INT1 to be searched. The search region may comprise a number of pixels of a frame of the signal INT1. The search region fetcher and downsampler circuit 108 may present the signal INT2 as a reduced resolution signal to the core engine circuit 110. The core engine circuit 110 may evaluate the definition parameters of the signals STREAM_—1, STREAM_—2, STREAM_—3 and STREAM_—4 compared with the search region. The core engine circuit 110 may then present the signal INT3 that identifies one or more found objects in the search region.

[0023] The classifier operation performed by the circuit 110 may contain nearly all of the descriptors at the weak classifier level. Therefore, the system 100 may be designed to optimize how the parameters or library of the weak classifiers are represented and loaded for evaluation.

[0024] An example of an implementation of a weak classifier parameter may be shown by the following structure (or syntax):

WEAK_CLASSIFIER {

[0025] NUM_RECTANGLES

[0026] ALPHA (Weak classifier output weights)

[0027] THRESHOLD_WC (Weak classifier decision threshold)

[0028] for r=1 to NUM_RECTANGLES {

• • [0029] RECTANGLE

[0030] }

}

RECTANGLE

[0031] LEFT (coordinate)

[0032] TOP (coordinate)

[0033] WIDTH (coordinate)

[0034] HEIGHT (coordinate)

[0035] WEIGHT

}

[0036] The on-board classifier cache memory 102 may store a number of classifier parameters (e.g., output weights, decision threshold, etc.). With such an implementation, the classifier parameters only need to be loaded into the classifier cache memory 102 from the external memory 120 once at the beginning of the search. In general, the classifier cache memory 102 is loaded when the hardware is initialized. The classifier cache memory 102 may be reloaded if additional classifiers are needed as a function of a particular operating mode and/or if there are more total classifiers than fit into the internal classifier cache memory 102. In one example, the external memory 120 may be implemented as a DRAM memory. However, other memories may be implemented to meet the design criteria of a particular implementation. Additionally, updates may be provided through a communication channel, such as a network, a wireless communication channel, etc.

[0037] During execution of a search, scanning from one search position to the next, all of the needed classifier parameters are resident and fetched from the local classifier cache circuit 102. Access to the external memory 120 is not needed to retrieve classifier parameters during the scanning process.

[0038] Some parameters may be compressed, while other parameters may not be compressed. Parameters from the weak classifier prototype structure that benefit from compression may be partitioned into separate streams apart from parameters which are not compressed. While four streams are shown, the particular number of streams may be varied to meet the design criteria of a particular implementation. In one example, the stream BSTR_—1 may be a stream of the rectangle parameters (e.g., left, width). In one example, the stream BSTR_—2 may be another stream of the rectangle parameters (e.g., top, height). In one example, the stream BSTR_—3 may be a stream of the weak classifier alpha parameters. In one example, the STREAM_—4 may be a stream of all the other uncompressed classifier parameters.

[0039] The classifier definition may be configured in the classifier cache memory 102 as four separate memory areas corresponding to the four separate streams. Stream pointers may be implemented to locate where each stream resides in the cache memory 102. The streams BSTR_—1, BSTR_—2, and BSTR_—3 may reside in the cache memory 102 in a compressed format. The stream STREAM_—4 may reside in the cache memory 102 in an uncompressed format. The particular parameters that are stored in compressed format and the particular parameters that are stored in uncompressed format may be varied to meet the design criteria of a particular implementation.

[0040] The classifier streams STREAM_—1, STREAM_—2, STREAM_—3, and/or STREAM_—4 may be presented from the classifier cache 102 in parallel. In one example, the classifier cache 102 may be implemented as a multi-port memory to enable a parallel readout. In another example, the classifier cache 102 may be implemented as a time multiplexed single port memory with arbitration. In another example, the classifier cache 102 may be implemented as a plurality of separate memory circuits. The VLD circuits 104a-104c may each correspond to one of the compressed streams BSTR_—1, BSTR_—2, and BSTR_—3. The circuits 104a-104c may decode the compressed parameters from the signals BSTR_—1-BSTR_—3 received from the classifier cache 102. The circuits 104a-104c may convey the actual uncompressed value of those parameters (i.e., STREAM_—1-STREAM_—3) to the core engine 110 for evaluation. The parallel readout and parallel VLD mechanisms increase the throughput when fetching classifier instructions compared to the conventional serial approaches.

[0041] A typical classifier may be made up of thousands of weak classifiers. Every bit used in representing the prototype structure of the weak classifier parameters has the potential to be magnified one thousand-fold. Therefore, compressing the weak classifier and rectangle parameters may save on cache space. The on-board cache memory 102 may be of sufficient size to save the parameters described, and also optimized to reduce overall processor area and cost. The statistics of various weak classifier and rectangle parameters typically show presence of statistical correlation (redundancy). The probability distributions of those parameters may be modeled by using compression techniques to reduce the entire classifier representation. In one example, compression of up to 40% (or more) may be implemented.

[0042] As part of such compression, the system 100 recognizes dependencies in the rectangle parameters. One such dependency is the left coordinate and the width of a rectangle. For example, for a 20×20 pixel search window, rectangles may have a left coordinate ranging from 0 to 19 and a width ranging from 1 to 20. However, not all values of the left coordinate and the width may need to be independently specified.

[0043] Referring to FIG. 2, an example of an allowable range space is shown. The width is shown as being dependent on the left coordinate. Over such a two-dimensional range space, the 2-D probability distribution may be modeled. Huffman variable length codewords may then be designed based on the particular probability model using standard Huffman VLC design techniques.

[0044] Referring to FIGS. 3a-c, a table comprising an example of Huffman VLC codewords designed for coding the rectangle coordinate pairs (e.g., left, width) is shown. The rectangle coordinate pairs (e.g., top, height) are similarly related. Therefore, the same Huffman VLC table may be used for compression.

[0045] Also, as part of the compression method, the present invention recognizes that the weak classifier alpha parameter tends to have a non-uniform probability distribution. Therefore, the weak classifier alpha parameters may also be Huffman VLC encoded to contribute to classifier cache space savings.

[0046] Referring to FIG. 4, a flowchart of a method (or process) 200 for formatting classifier parameters to store into classifier cache is shown. The method 200 generally comprises a step (or state) 202, a step (or state) 204, a step (or state) 206, a step (or state) 208, a step (or state) 210. The state 202 starts the method 200 by executing a Viola-Jones Classifier Trainer based upon a training set of examples. Face examples and non-face examples may be used to generate the trained classifier parameters. The trained classifier parameters most relevant at the weak classifier level are previously described in connection with the WEAK_CLASSIFIER data structure. Some of the parameters of the WEAK_CLASSIFIER data structure, such as ALPHA and THRESHOLD_WC, may be continuous valued and may need to be quantized to a limited number of precision bits to be represented efficiently. The parameter quantizer state 204 may quantize the classifier parameters to a limited number of precision bits. Other parameters may already be in integer format with a known and suitable range for representation, and need not undergo any quantization.

[0047] The histogram analyzer state 206 examines the quantized classifier parameters. For each particular parameter examined in state 206, a histogram may be generated to count the number of occurrences of the particular parameter for each quantized value of the particular parameter. The shape (or distribution) of the histogram may be examined to make a binary decision to determine if a particular parameter needs to be compressed. If the histogram shape is sufficiently skewed, then that parameter will undergo compression through the Huffman VLC encoder state 208. The state 208 receives the quantized classifier parameters which have been deemed to have a skewed distribution, along with the skewed histogram distribution. The state 208 then generates a variable-length encoded bitstream representing the classifier parameters in compressed form. If the histogram shape is relatively uniform, or deemed not to be sufficiently skewed, then the quantized parameter will not undergo compression.

[0048] The classifier parameter packer state 210 may be used to bundle together the compressed classifier parameters and the non-compressed classifier parameters into a format that may be directly loaded into the classifier cache 102. In some cases, one particular parameter may exhibit dependency with another parameter. For example, the left parameter and the width parameter (as shown in FIG. 2) are not entirely independent parameters. Only certain combinations of left values and width values may be valid. It is beneficial in such cases of two-variable dependency to jointly compress the two parameters in order to achieve even higher compression efficiency. In such case, the histogram analyzer in step 206 generates and examines two-dimensional histograms. The Huffman VLC encoder in step 208 then operates using the 2-D histogram to generate codewords for the joint (left, width) pair symbols (as shown in connection with FIG. 3).

[0049] While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention.