Shape-based object detection and localization system

[0001] The present application is a Continuation-in-Part application, claiming the benefit of priority of U.S. patent application Ser. No. 12/072,697, filed on Feb. 26, 2008, entitled, “System for anomaly detection using sub-space analysis.”

[0002] The present invention relates to an object detection and localization system and, more particularly, to a system that localizes and detects an object based on the shape of the object.

[0003] The security industry is in need of technological innovation for producing automated image analysis systems for detecting concealed objects underneath a person's clothing. As shown in FIG. 1, existing imaging modalities include a visible image 100, a millimeter wave image (mmW) 102, and backscatter X-ray image 104. The objective in such a system is to automate the process so that a human operator is not required to look at raw data. However, as shown, a visible image 100 does not identify concealed objects. Alternatively, raw scans (such as the mmW 102 and backscatter X-ray 104 images) reveal what is underneath the clothing, which is the naked appearance of subjects. In the current state of technology, human operators have to directly inspect the scans displaying human subjects essentially in a naked form. As such, these systems generate concerns in the public over privacy issues. Another example of such a raw scan is depicted in FIG. 2, which illustrates a frontal image 200 and a rear image 202 of a subject.

[0004] In almost all the existing mmW and backscatter X-ray scanning systems, the task of image inspection and analysis of the image content for the presence of concealed objects (e.g., weapons) is carried out manually by human operators. Although some attempts are being made at automating the process by device manufacturers such as Rapiscan Systems Inc. and Trex Enterprises Corporation, no fully automated system currently exists that can scan and reliably analyze two-dimensional (2D) image content for the presence of concealed objects. Rapiscan Systems Inc. is located at 2805 Columbia Street Torrance, Calif. 90503. Trex Enterprises Corporation is located at 10455 Pacific Center Court, San Diego, Calif. 92121.

[0005] Additionally, several recent patent applications have been filed that reveal a number of object detection related systems devised within the context of medical imaging. The focus of related prior art on anomaly detection in the context of medical imaging is often on feature based anomalous/cancerous cell detection. For example, U.S. patent application Ser. No. 10/633,815, by Wrigglesworth et al., describes a system for detecting anomalous targets, namely cancerous cells. In this particular paradigm, a predefined number of features are extracted from a particular set of cell imagery. The features are then used to generate a probabilistic belief function to determine a probability that at least some of the cells in an image set are anomalous.

[0006] As another example, U.S. Pat. No. 7,072,435, issued to Metz et al., describes a system that processes computer tomography scans for detecting anomalous cancerous cells associated with lung cancer. The novelty in this particular patent is the use of CT imaging modality, while the algorithms for determining anomalies are somewhat standard computer aided detection (classification) methods.

[0007] As yet another example, U.S. patent application Ser. No. 10/352,867, by Parker et al., describes a system in which segmentation and localization of biomarkers, such as liver metastases and brain lesions, are cast as an anomaly detection problem. Statistical segmentation methods are used to identify biomarkers in the first image and the process is carried over to several subsequent images that are time evolutions of the biological construct (liver or brain tissue) that is under observation. The method relies on processing temporal sequences of three-dimensional medical imagery (instead of two-dimensional views).

[0008] The prior art is limited for these particular types of imagery. The limitation is primarily due to availability and the need for use of such scanning modalities for security purposes in the public domain. Prior art largely remains in the medical imaging domain where the task of anomaly detection is posed as identification of cancerous lesions. In the mmW and backscatter X-ray image analysis domain, device manufacturers have made attempts at bringing together a combination of off-the-shelf algorithms to analyze images for weapon detection, yet a reliable system does not currently exist that is able to detect weapons in such scans. The existing methods are often not tailored to the specific nature of the data.

[0009] A literature and patent search on prior art has revealed related work, particularly in the area of medical imaging; however, as indicated herein, the methods used pose significant vulnerabilities to geometric deformations, image appearance variations and partial occlusions. Addressing these issues is important in creating a reliable automated detection system.

[0010] Thus, a continuing need exists for a system that uses an analysis and detection technique to automatically identify concealed objects without manual intervention

[0011] The present invention relates to a computer implemented method for identifying a concealed object of interest. The method comprises an act of causing a computer (having a processor and a memory module encoded with instruction means that are executable by the processor) to execute the instruction means and cause the processor to perform a plurality of acts (operations). Such acts include receiving an image in grayscale and processing the image to identify feature rich regions which are identified as a binary mask describing edge pixels and non-edge pixels. A set of edge pixels are then randomly sampled. Finally, an object detector function is used on the set of edge pixels to determine if an object of interest is present in the set of edge pixels.

[0012] In processing the image, all edges in the image are identified using an edge detector, which results in a binary image. The binary mask is constrained using a threshold to describe edge pixels and non-edge pixels as a binary, two-class classification.

[0013] In determining if an object of interest is present in the set of edge pixels, a region of interest window is cropped out that is centered around a selected edge pixel. An edge preserving non-linear diffusion is then performed on the region of interest window to increase saliency of edges of a potential object of interest. A background and a foreground are thereafter formed in the region of interest window. The background is segmented from the foreground, with pixel information extracted for the foreground (the pixel information having dimensional coordinates for each pixel in the foreground). Two best fit ellipsoids are fit to the pixel information (each ellipsoid having a major and minor axis). The two best fit ellipsoids are fit to the pixel information such that there exists an intersection between the major axis of the two ellipsoids. The two major axes are then extracted from the two ellipsoids. The two major axes can then be aligned with a known two-axis model representing an object of interest. A distance measurement is then determined between the two major axes and the known two-axis model. Additionally, the object is identified as an object of interest if the distance measurement is below a predetermined threshold.

[0014] Finally, the present invention also includes a computer program product and a system. The computer program product comprises computer-readable instruction means stored on a computer-readable medium that are executable by a computer for causing the computer to perform the operations described herein. Additionally, the system includes a processor and memory module that are configured to perform said operations.

[0027] The present invention relates to an object detection and localization system and, more particularly, to a system that localizes and detects an object based on the shape of the object. The following description is presented to enable one of ordinary skill in the art to make and use the invention and to incorporate it in the context of particular applications. Various modifications, as well as a variety of uses in different applications will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to a wide range of embodiments. Thus, the present invention is not intended to be limited to the embodiments presented, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

[0028] In the following detailed description, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without necessarily being limited to these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.

[0029] The reader's attention is directed to all papers and documents which are filed concurrently with this specification and which are open to public inspection with this specification, and the contents of all such papers and documents are incorporated herein by reference. All the features disclosed in this specification, (including any accompanying claims, abstract, and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features.

[0030] Furthermore, any element in a claim that does not explicitly state “means for” performing a specified function, or “step for” performing a specific function, is not to be interpreted as a “means” or “step” clause as specified in 35 U.S.C. Section 112, Paragraph 6. In particular, the use of “step of” or “act of” in the claims herein is not intended to invoke the provisions of 35 U.S.C. 112, Paragraph 6.

[0031] Before describing the invention in detail, a description of various principal aspects of the present invention is provided. Subsequently, an introduction provides the reader with a general understanding of the present invention. Next, details of the present invention are provided to give an understanding of the specific aspects. Finally, a brief synopsis of experimental results is provided.

[0032] (1) Principal Aspects

[0033] The present invention has three “principal” aspects. The first is an object detection and localization system. The object detection and localization system is typically in the form of a computer system operating software or in the form of a “hard-coded” instruction set. This system may be incorporated into a wide variety of devices that provide different functionalities. The second principal aspect is a method, typically in the form of software, operated using a data processing system (computer). The third principal aspect is a computer program product. The computer program product generally represents computer-readable instructions stored on a computer-readable medium such as an optical storage device, e.g., a compact disc (CD) or digital versatile disc (DVD), or a magnetic storage device such as a floppy disk or magnetic tape. Other, non-limiting examples of computer-readable media include hard disks, read-only memory (ROM), and flash-type memories. These aspects will be described in more detail below.

[0034] A block diagram depicting the components of an object detection and localization system of the present invention is provided in FIG. 3. The object detection and localization system 300 comprises an input 302 for receiving information from at least one sensor for use in detecting an object in an image. Note that the input 302 may include multiple “ports.” Typically, input is received from at least one sensor, non-limiting examples of which include a video image sensor, a millimeter wave (mmW) scanning device, an infra-red (IR) scanning device, or a backscatter X-ray scanning device. An output 304 is connected with the processor for providing information regarding image (or an anomaly in the image) to other systems in order that a network of computer systems may serve as an anomaly detection system. Output may also be provided to other devices or other programs; e.g., to other software modules, for use therein. The input 302 and the output 304 are both coupled with a processor 306, which may be a general-purpose computer processor or a specialized processor designed specifically for use with the present invention. The processor 306 is coupled with a memory 308 to permit storage of data and software that are to be manipulated by commands to the processor 306.

[0035] An illustrative diagram of a computer program product embodying the present invention is depicted in FIG. 4. The computer program product 400 is depicted as an optical disk such as a CD or DVD. However, as mentioned previously, the computer program product generally represents computer-readable instruction means stored on any compatible computer-readable medium. The term “instruction means” as used with respect to this invention generally indicates a set of operations to be performed on a computer, and may represent pieces of a whole program or individual, separable, software modules. Non-limiting examples of “instruction means” include computer program code (source or object code) and “hard-coded” electronics (i.e., computer operations coded into a computer chip). The “instruction means” may be stored in the memory of a computer or on a computer-readable medium such as a floppy disk, a CD-ROM, and a flash drive.

[0036] (2) Introduction

[0037] Imaging technology to detect objects hidden underneath layers of clothing is a recent and rapidly developing field. Backscatter X-ray scanning devices have been in use for some time in prisons for scanning inmates for the presence of concealed weapons. More recently, millimeter wave (mmW)-based imaging devices are being developed with the same intent by a number of companies. However, such devices are unmarketable for use in the public domain due to privacy issues involved in the nature of scans (scans reveal humans in naked form).

[0038] Addressing the need for privacy, the present invention can be used to analyze such scans automatically for the presence of objects (such as weapons), eliminating the need for inspection of scans by a human operator. Such systems can be deployed in airports and elsewhere where there is a need for inspection of subjects for the presence of concealed objects.

[0039] The present invention improves upon the prior art by providing a shape-based object detection and localization technique for computer aided analysis of images. The present invention is capable of automatic analysis of two-dimensional (2D) images of human scans produced using unconventional imaging modalities, such as millimeter wave (mmW), infra-red (IR) or backscatter X-ray scanning devices. A goal of the present invention is to detect and localize weapons or weapon-like conspicuous objects that may be concealed underneath layers of clothing. The present invention learns key appearance elements (models) for specific objects, such as guns or knives. After learning the models, the present invention can search and locate new instances of the object in novel images with an extended measure of robustness to background and geometric distortions (both local and global) that may be due to object's orientation, viewing angle or partial occlusions.

[0040] The present invention detects and localizes an object using four primary elements:

[0041] a. Model learning;

[0042] b. Image preprocessing;

[0043] c. Shape extraction; and

[0044] d. A normalized metric in the space of shapes of certain geometric topology.

[0045] Combined, the elements of the present invention can be used to analyze an image for the presence of particular objects. More specifically, the present invention can be applied to mmW or backscatter X-ray images to identify and localize the presence of a variety of concealed objects.

[0046] (3) Details of the Invention

[0047] As noted above, the present invention is a system for shape-based object detection. Generally speaking and as illustrated in FIG. 5A, the present invention operates by receiving an image in grayscale 501, processing the image to identify feature rich regions 503 (which are identified as a binary mask describing edge pixels and non-edge pixels), randomly sampling a set of edge pixels 505, and determining if an object of interest is present in the set of edge pixels 507.

[0048] In operation, the present invention relies on learning a model for a specific object. The model is used later to search in images for objects with similar appearance characteristics.

[0049] There are several components that comprise the core technique of the present invention. The components are:

[0050] a. Model learning;

[0051] b. Image preprocessing;

[0052] c. Shape extraction; and

[0053] d. A normalized metric in the space of shapes of certain geometric topology. For clarity, each of the components will be described in turn.

[0054] (3.1) Model Learning

[0055] Before detecting an object, the system must learn a model of the object's (e.g., weapon) appearance and then analyze image patches against the model. The system uses a local window that analyzes rectangular regions of the image for the presence of objects. Building models of objects that can be used to robustly and reliably perform classification and localization tasks is an active area of research in computer vision and pattern recognition. The present invention draws upon the latest findings in these areas.

[0056] The first stage of model learning includes a body shape registration mechanism. As show in FIG. 5A, the registration stage brings the body scan 500, using manually annotated landmarks points, normalized (e.g., using piecewise affine warping) to a reference frame 502 (e.g., a reference frame that is a 512 pixel by 256 pixel rectangular image grid). The registration in preliminary experiments were carried out manually; however, it is worth noting that automatic registration of the human body scan can be done using the geometric registration tools developed by the medical imaging community. Shape registration is an important area of focus in medical imaging community and powerful computational methods have been devised. For example, a non-limiting example of such a shape registration tool was described by Duta et al., in “Automatic Construction of 2D Shape Models,” IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 23, issue 5, pages 433-446, May 2001.

[0057] (3.2) Image Preprocessing

[0058] After receiving an image in grayscale, the second stage (as shown in FIG. 6) is preprocessing of the image where interesting, feature rich regions of the image are identified as a binary mask describing edge pixels and non-edge pixels. Typically, scans of the human body reveal a uniformly bright appearance with relatively low gradient features. The presence of objects is marked by high gradient texture rich regions. The term high gradient texture rich regions refers to regions in the image in which there are several instances of quick blending of colors from low to high color values (or vice versa) across the region. A low gradient region would be a region where there is a casual blend of color across the region. In contrast, a high gradient region is a region where there is a quick or dramatic blend of color across the region. If there are numerous instances of dramatic or quick color blends, this is indicative of a feature rich region. It is, therefore, reasonable to focus on feature rich regions that will form the search space for object detection analysis later.

[0059] In the present invention, feature rich regions are identified as a binary mask 600 describing edge pixels and non-edge pixels. The mask 600 is primarily used to reduce the search space for processing and search by the object detection operator. The object detection operator is essentially an image operator Φ(I_O) that operates on a rectangular patch I_O and returns an object score that is indicative of the patch containing a particular object. The object detection operator (function) works on the set of edge pixels to determine if an object of interest is present in the set of edge pixels.

[0060] The mask 600 is created by using a reference frame 502 and performing edge preserving nonlinear diffusion 601 on the reference frame 502. Edge preserving nonlinear diffusion is used to improve the accuracy of later segmentation by preserving changes in image intensity to generate an image with enhanced changes 602. Due to United States Patent and Trademark Office (U.S.P.T.O.) rules regarding grayscale drawings, the enhanced changes are depicted as an additional line surrounding the object. However, in operation, the enhanced changes can be sharp contrasting edges that depict the changes in image intensity from grayscale images. Non-limiting examples of techniques for edge preserving nonlinear diffusion include median filtering and gray-scale morphology.

[0061] Using an edge detector, edge detection 604 is then performed to identify points in the image at which the image brightness changes sharply or, more formally, has discontinuities. Thus, the edges are identified in the image which results in a binary image. A non-limiting example of a suitable technique for edge detection is Canny Edge Detection, described by Canny, J., in “A Computational Approach to Edge Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 8, pp. 679-714, 1986.

[0062] The binary mask 600 is then created to reduce the search space for processing and search by the object detection operator. A threshold is used to constrain the binary mask 600 to describe edge pixels and non-edge pixels as a binary, two-class classification.

[0063] The binary mask 600 is created to identify interesting feature regions using a Gaussian Kernel. Uniform sampling 604 is then performed in the interesting regions that were identified in the mask 600 for use by the object detection operator 700.

[0064] (3.3) Shape Extraction

[0065] As shown in FIG. 7, an object detection operator 700 is at the heart of the shape-based detection system. The object detection operator 700 itself has several stages. The first stage is the shape extraction. As shown in FIG. 7, a region of interest window Ω 702, centered around a selected edge pixel x_cεR² with dimensions m×n, is cropped out for further use. The window 702 is scanned for interesting points using an object detection operator 700, which can be calculated as follows:
φ(I_O(x))
φ:R^m×n→R
where R is a real number, φ is an image operator, I_O is a rectangular patch in the image, x is one of the pixels in the rectangular patch, while I_O(x) is the rectangular patch of pixels being examined. Additionally, R is the space of Real numbers, while R^m×n is the space of rectangular image pixels of size m×n. The equation provided above is an equation for the object detection operator where the object detection operator examines the m×n window of pixels (I₀(x)) and returns a real number. This number reflects how similar the pixels in the rectangular patch are to a known object model.

[0066] Thus, the object detection operator window is defined as:
I_O(x)=I(x)|xεΩ⊂₂
where ε means “is an element of” while ⊂ means “is a subset of.”

[0067] Initially, an edge preserving nonlinear diffusion process is used to aid the segmentation of the dark 704 (e.g., weapon) regions from the lighter 706 background (e.g., body) regions. A non-limiting example of a suitable edge preserving nonlinear diffusion process was described by Perona et al. in “Scale-Space and Edge Detection Using Anisotropic Diffusion,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 7, pp. 629-639, 1990.

[0068] As shown in FIGS. 8A and 8B, the goal is to carry out the segmentation while preserving the shape information contained in the darker (or the lighter depending on the imaging modality) region. A two part mixture of Gaussians (maximum likelihood) fit is applied to segment the patch into dark and bright regions. FIG. 8A depicts the object detection operator 800 and edge preserving nonlinear diffusion 802. Edge preserving nonlinear diffusion 802 is performed on the region of interest window 803 to increase saliency of edges of a potential object of interest. Saliency refers to the state of the edges of the potential object of interest to be able to stand out relative to any neighboring item or background scenery. For example, the edge preserving nonlinear diffusion 802 increases the contrast of the edges of the potential object of interest to stand out from surrounding material in the image.

[0069] Depicted is the region of interest window with increased saliency 805. Edge preserving nonlinear diffusion 802 can be performed according to the following:

[0070] $\frac{\partial }{\partial t}I\left(x,y,t\right)-c\left(x,y,t\right)\Delta I\left(x,y,t\right)+\nabla c\left(x,y,t\right)·\nabla I\left(x,y,t\right),$
where x, y are points in the image, t is time, c is the coefficient of diffusion that, in this formulation, is both space (i.e., image location) and time dependent. Further, ∇ denotes the gradient operator while Δ is the Laplacian operator. As can be appreciated by one skilled in the art, the Laplacian operator is a second order differential operator in the n-dimensional Euclidean space, defined as the divergence of the gradient ∇f.

[0071] Additionally, FIG. 8B depicts a luminance histogram 804 and the resulting binary shape image 806. As understood by one skilled in the art, the luminance histogram 804 is used to show the total tonal distribution in the image and represent the count of pixels of every tone of gray that occurs in the image. The luminance histogram 804 assists a user in determining the how to segment the image patch into dark and bright regions, resulting in the binary shape image 806, in which the test object is segmented from the background.

[0072] One procedure to segment the image patch into dark and bright regions is depicted in FIG. 8B. A two part mixture of Gaussians (maximum likelihood) fit is applied to luminance histogram. As shown in 804, the luminance histogram is modeled as the sum of two Gaussians:
LH(n)≅αN(n−m₁,ρ₁²)+(1−α)N(n−m₂,ρ₂²),
where LH(n) is the luminance histogram at pixel value n and N(m,ρ) is a Gaussian distribution with mean m and variance ρ². Through analysis of the Gaussian mixture model, the threshold β_ρ1 is chosen and used to create the binary shape image (806).

[0073] A normalized metric in the space of shapes of certain geometric topology is used to determine if an object of interest is present in the set of edge pixels, as follows.

[0074] FIG. 9 depicts a shape extraction stage, where a two-dimensional mixture of Gaussians fit is used to extract the principal skeletal structure (i.e., geometric form 900) of the foreground object 902. The foreground object 902 is assumed to contain the object of interest which is defined by pixel information. The geometric form 900 (referred to as shape 5) is defined by two-dimensional point data corresponding to the two major axes of ellipsoids 904 and 906. Thus, pixel information is extracted for the foreground. The pixel information includes dimensional coordinates for each pixel in the foreground. Each ellipsoid 904 and 906 includes a major axis 908 and a minor axis 910. The two best fit ellipsoids 904 and 906 are fit to the pixel information such that there exists an intersection 911 between the major axes 908 and 909 of the two ellipsoids 904 and 906. The two-dimensional, mixture of Gaussians fit is carried out on the foreground patch geometry. Such a procedure was described by Duda, R. O. and Hart, P. E., in “Pattern Classification and Scene Analysis,” Wiley (1973), which is incorporated by reference as though fully set forth herein. Thus, after the major axes 908 and 909 are identified, they are extracted for further comparison against the axes corresponding to known objects.

[0075] The geometric form 900 of the foreground is then used for comparison against known object shapes (e.g., a hand gun). The major axes 908 and 909 of resulting Gaussians are analyzed and shape registered against known geometric topology of a two-axis shape description of an object. Shape S is registered to known object shape S_object, according to the following equation:

[0076] $\underset{A}{\arg \min }S-{\mathrm{AS}}_{\mathrm{object}},$

• • [0077] subject to AA^T=I and Procrustes analysis,
    where A is a matrix used to shape register the axes of the known object (S_object) to the axes of the test shape (S) and/is the identity matrix. Arg min∥ ∥ is an operation that minimizes what is inside the brackets (which in this case is the difference between the shape S and the warped shape AS_object) by varying the matrix A. Matrix A is a rotation matrix found by least squares analysis. For example, the Procrustes analysis first removes scale and translation invariance prior to determining A and applying it.

[0078] Initial topological (line end-point correspondence) alignment is resolved through minimizing the Hausdorff distance between end points and intersection 911 of the two primary axes 908 and 909. Thus, the two major axes 908 and 909 are aligned with a known two-axis model representing an object of interest.

[0079] Given correct end point correspondences, shape registration is achieved through Procrustes alignment. This is a key step in removing geometric deformations from the shape, bringing it to a normalized shape reference frame. Such a procedure was described by G. H. Golub and C. F. in “Van Loan. Matrix Computations,” Johns Hopkins University Press, 1996, which is incorporated by reference as though fully set forth herein.

[0080] Once the extracted shape is registered and normalized, the Euclidean distance between registered sampling of a predetermined number of points (e.g., 100) on the reference and target shapes is computed. Thus, a distance measurement is determined between the two major axes and the known two-axis model. This distance is ultimately used as the basis for object detection. The object is identified as an object of interest if the distance measurement is below a predetermined threshold. An object detection score can be calculated according to the following equation:

[0081] $\Phi ={S-{\mathrm{AS}}_{\mathrm{object}}}_F=\sum _N{S_i-{\mathrm{AS}}_{\mathrm{i\_object}}}_2$
where Φ is the object detection score, N is the number of sampled points used in calculating the score, i and i_object are indices (that go from 1 to N) of corresponding sample points in the test shape (S) and known object (S_object), and F is the set of points that make up S and S_object.

[0082] Thus, in essence, the object detection operator includes two stages, the shape extraction stage and the shape distance stage, summarized as follows:

[0083] $I\in R^{\mathrm{mxn}}\stackrel{\mathrm{Shape}.\mathrm{Extraction}}{\to }S\in R^{2\mathrm{xN}}\stackrel{\mathrm{Shape}.\mathrm{Distance}}{\to }\Phi \in R.$