Thresholding of Image Difference Maps

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
1Forward
Citation 
0
Petitions 
2
Assignments
First Claim
1. Computerreadable media embodying instructions executable by a computer to perform a method comprising:
 receiving a first twodimensional array;
generating a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number;
generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays;
generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector;
generating a third vector, comprising filtering the second vector; and
selecting, based on the third vector, at least one ofone of the threshold numbers; and
one of the second twodimensional arrays.
2 Assignments
0 Petitions
Accused Products
Abstract
Computerreadable media having corresponding apparatus embodies instructions executable by a computer to perform a method comprising: receiving a first array; generating a plurality of second arrays based on the first array, wherein each of the second arrays is generated using a different threshold number, and wherein each entry of the second arrays indicates whether a corresponding entry in the first array exceeds the respective threshold number; generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second arrays; generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; generating a third vector, comprising filtering the second vector; and selecting, based on the third vector, one of the threshold numbers, of the second arrays or both.
7 Citations
View as Search Results
FILTERS FOR SPECTRAL ANALYSIS DATA  
Patent #
US 20120323533A1
Filed 08/28/2012

Current Assignee
Battelle Memorial Institute

Sponsoring Entity
Battelle Memorial Institute

Multilevel screening mapping tone values to control signal values for greater color or shade fidelity and reduced print aberrations  
Patent #
US 7,969,617 B2
Filed 06/04/2008

Current Assignee
FFEI Limited

Sponsoring Entity
FFEI Limited

Stroke localization and binding to electronic document  
Patent #
US 7,580,576 B2
Filed 06/02/2005

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Apparatus and method for detecting defect on object  
Patent #
US 20060078191A1
Filed 09/06/2005

Current Assignee
SCREEN Holdings Co. Ltd.

Sponsoring Entity
SCREEN Holdings Co. Ltd.

Pattern recognizing apparatus  
Patent #
US 6,850,645 B2
Filed 12/04/2001

Current Assignee
Fujitsu Limited

Sponsoring Entity
Fujitsu Limited

Method and system for data analysis  
Patent #
US 20030030637A1
Filed 02/15/2002

Current Assignee
ANVIL INFORMATICS INC.

Sponsoring Entity
ANVIL INFORMATICS INC.

Number plate recognition system  
Patent #
US 5,315,664 A
Filed 05/26/1993

Current Assignee
YOZAN Inc.

Sponsoring Entity
Ezel Inc.

15 Claims
 1. Computerreadable media embodying instructions executable by a computer to perform a method comprising:
receiving a first twodimensional array; generating a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; generating a third vector, comprising filtering the second vector; and selecting, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.  View Dependent Claims (2, 3, 4, 5)
 6. An apparatus comprising:
an input module to receive a first twodimensional array; a threshold module to generate a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; a count module to generate a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; a variance module to generate a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; a filter module to generate a third vector, comprising filtering the second vector; and a select module to select, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.  View Dependent Claims (7, 8, 9, 10)
 11. An apparatus comprising:
input means for receiving a first twodimensional array; threshold means for generating a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; count means for generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; variance means for generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; filter means for generating a third vector, comprising means for filtering the second vector; and select means for selecting, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.  View Dependent Claims (12, 13, 14, 15)
1 Specification
The present disclosure relates generally to image processing, and more particularly to the thresholding of image difference maps. However, various embodiments can be used to process any sort of twodimensional array.
An image difference map is an array of entries, where each entry represents a difference between the values of corresponding pixels in two images. In a grayscale image, an entry can represent a difference in intensity. In a color image, an entry can represent the magnitude of a vector between the color space coordinates of the corresponding pixels. Difference maps are generally used to detect changes between two images such as video frames.
Image difference maps are generally thresholded to mitigate noise. That is, a pixel is considered to differ between two images only when the value of the pixel'"'"'s entry in the image difference map exceeds a threshold number. A challenge arises in selecting a proper threshold number that will mitigate noise while still properly indicating image changes.
In general, in one aspect, an embodiment features computerreadable media embodying instructions executable by a computer to perform a method comprising: receiving a first twodimensional array; generating a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; generating a third vector, comprising filtering the second vector; and selecting, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.
Embodiments of the computerreadable media can include one or more of the following features. In some embodiments, generating a first vector comprises: determining the respective number of connected components for each of the second twodimensional arrays. In some embodiments, determining the number of connected components for each of the second twodimensional arrays comprises: determining a respective Euler number for each of the second twodimensional arrays. In some embodiments, filtering the second vector comprises: applying a median absolute deviation filter to the second vector. In some embodiments, the first twodimensional array represents a difference map for a plurality of images.
In general, in one aspect, an embodiment features a method comprising: receiving a first twodimensional array; generating a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; generating a third vector, comprising filtering the second vector; and selecting, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.
Embodiments of the method can include one or more of the following features. In some embodiments, generating a first vector comprises: determining the respective number of connected components for each of the second twodimensional arrays. In some embodiments, determining the number of connected components for each of the second twodimensional arrays comprises: determining a respective Euler number for each of the second twodimensional arrays. In some embodiments, filtering the second vector comprises: applying a median absolute deviation filter to the second vector. In some embodiments, the first twodimensional array represents a difference map for a plurality of images.
In general, in one aspect, an embodiment features an apparatus comprising: an input module to receive a first twodimensional array; a threshold module to generate a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; a count module to generate a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; a variance module to generate a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; a filter module to generate a third vector, comprising filtering the second vector; and a select module to select, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.
Embodiments of the apparatus can include one or more of the following features. In some embodiments, the count module comprises: a connected component module to determine the respective number of connected components for each of the second twodimensional arrays. In some embodiments, the connected component module comprises: an Euler module to determine a respective Euler number for each of the second twodimensional arrays. In some embodiments, the filter module comprises: a median absolute deviation filter module to apply a median absolute deviation filter to the second vector. In some embodiments, the first twodimensional array represents a difference map for a plurality of images.
In general, in one aspect, an embodiment features an apparatus comprising: input means for receiving a first twodimensional array; threshold means for generating a plurality of second twodimensional arrays based on the first twodimensional array, wherein each of the second twodimensional arrays is generated using a different threshold number, and wherein each entry of the second twodimensional arrays indicates whether a corresponding entry in the first twodimensional array exceeds the respective threshold number; count means for generating a first vector, wherein each entry in the first vector represents a number of connected components for a respective one of the second twodimensional arrays; variance means for generating a second vector based on the first vector, wherein each entry of the second vector represents a variance of a plurality of entries, including a corresponding entry, of the first vector; filter means for generating a third vector, comprising means for filtering the second vector; and select means for selecting, based on the third vector, at least one of one of the threshold numbers; and one of the second twodimensional arrays.
Embodiments of the apparatus can include one or more of the following features. In some embodiments, the count means comprises: connected component means for determining the respective number of connected components for each of the second twodimensional arrays. In some embodiments, the connected component means comprises: Euler means for determining a respective Euler number for each of the second twodimensional arrays. In some embodiments, the filter means comprises: median absolute deviation filter means for applying a median absolute deviation filter to the second vector. In some embodiments, the first twodimensional array represents a difference map for a plurality of images.
The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features will be apparent from the description and drawings, and from the claims.
The leading digit(s) of each reference numeral used in this specification indicates the number of the drawing in which the reference numeral first appears.
According to one embodiment, an input array, which can be an image difference map, is thresholded using a plurality of different threshold numbers to generate a plurality of bit maps. Each entry in each bit map indicates whether the corresponding entry in the input array exceeds the respective threshold number.
A count value is determined for each of the bit maps. Each count value is based on the number of connected components in the respective bit map. For example, each count value can be the Euler number for the respective bit map. The count values form a count vector.
A variance vector is generated based on the count vector, for example using a sliding window, so that each entry in the variance vector represents a variance of a plurality of entries, including the corresponding entry, of the count vector.
The variance vector is then filtered, for example using a median absolute deviation filter. Based on the filtered vector, one of the threshold numbers, one of the bit maps, or both, is selected.
Referring to
Referring to
A difference map indicates how much each pixel has changed between two images. For example, if the original two images are 24bit RGB images, then each entry in the difference map will have a value ranging from 0255 with 0 indicating no change and 255 indicating total change.
Often the only concern is whether a change has occurred. Therefore, the difference map is thresholded using a value in the range to produce a bit map. Each entry in the bit map can have only one of two values, generally 0 or 1. For example, a value of 0 indicates the corresponding entry in the difference map fell below the threshold, while a value of 1 indicates the corresponding entry in the difference map equaled or exceeded the threshold. The only remaining question is the choice of the proper threshold number. However, this question is complicated by extraneous factors.
In a perfect world, if two images are taken of the same scene, the entries in a difference map for the two images would be all zeros. But due to subtle environmental variations, imperfect capture devices, and the like, the difference map entries generally are not zero. For example, slight lighting changes due to flickering fluorescent lamps can cause images of the same scene to differ. As another example, noise generated by a video camera during the video capture process can differ between otherwise identical frames. These subtle variations makes it difficult to differentiate actual changes from changes due to the capture process or inconsequential environmental changes.
To mitigate these extraneous factors, a plurality of such bit maps are produced, each using from a different threshold number. The bit maps are then analyzed to select a one of the bit maps, the corresponding threshold number, or both, as described in detail below.
Referring again to
Count module 106 generates a count vector 124 indexed by threshold number based on bit maps 122 (step 206). Each entry in count vector 124 represents a number of connected components for the respective bit map 122. Count module 106 can include a connected component module 114 to determine the number of connected components for each bit map 122.
Determining the number of connected components can be an expensive operation. An alternative approach is to determine the Euler number. The Euler number is the difference between the number of connected components and the number of holes in the components. The Euler number can be calculated efficiently using a scan line technique. Therefore, in some embodiments, connected component module 114 includes an Euler module 116 to determine a respective Euler number for each bit map 122.
Referring again to
In some cases, variance vector 126 can include unwanted spikes.
Referring again to
In some embodiments, filter module 110 includes a median absolute deviation (MAD) module 118. At each step of the window, the MAD module 118 computes the median absolute deviation of only the peak values. If there is a peak that is over 3 times the median absolute deviation, that peak is removed. Any peak removal technique can be used. For example, a peak can be removed by finding the lowest point on each side of the peak and performing a linear interpolation between each to the two minimum values for any values that are needed in the region of the removed spike.
Filter module 110 should preserve the falling edge following the initial large variance changes, which can be seen for example in
Next, select module 112 selects one of the threshold numbers 130 based on filtered vector 128 (step 212). In some embodiments, select module 112 selects the difference map corresponding to the threshold number in addition to, or instead of, selecting the threshold number. In some embodiments, threshold number 130 is selected based on the trough to the right of the initial large changes in variance. For example, this trough can be seen in the plot of
Once the trough is found, threshold number 130 is selected. But while one technique for selecting threshold number 130 based on the trough is described below, others can be used instead. Threshold number 130 can be selected by searching to the left of the trough to find a local maximum. The local maximum is the first peak to the left of the trough. A peak detector can be used so that very small local maximums are ignored. Similarly, the local minimum to the right of the trough is found. A line is computed between these two points. The value of filtered vector 128 between these two points that is farthest in distance from the computed line (at right angles) is selected as threshold number 130.
Various embodiments can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. Embodiments can be implemented in a computer program product tangibly embodied in a machinereadable storage device for execution by a programmable processor; and method steps can be performed by a programmable processor executing a program of instructions to perform functions by operating on input data and generating output. Embodiments can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Each computer program can be implemented in a highlevel procedural or objectoriented programming language or in assembly or machine language if desired; and in any case, the language can be a compiled or interpreted language. Suitable processors include, by way of example, both general and special purpose microprocessors. Generally, a processor will receive instructions and data from a readonly memory and/or a random access memory. Generally, a computer will include one or more mass storage devices for storing data files; such devices include magnetic disks, such as internal hard disks and removable disks; magnetooptical disks; and optical disks. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of nonvolatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magnetooptical disks; and CDROM disks. Any of the foregoing can be supplemented by, or incorporated in, ASICs (applicationspecific integrated circuits).
A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of this disclosure. Accordingly, other implementations are within the scope of the following claims.