Method for illumination independent change detection in a pair of registered gray images

Abstract

A method for illumination-independent change detection in a pair of original registered gray images based on blob extraction. Blobs are extracted from the two original images and their negatives, using an enhanced blob extraction algorithm based on connectivity analysis along gray-levels. Blobs extracted from the first original and negative images are compared with blobs extracted from the second original and negative images to determine whether each blob has a corresponding blob, i.e. whether it is a matched or unmatched blob. All unmatched blobs are tested for significance as “blobs of change” using a fitness measure based on either a ratio of saliency gradients, or a product of this ratio and a gradient distribution measure. The disclosed method is exact, fast, robust, illumination-insensitive, and has low time-complexity

1. A method for illumination-independent change detection between a pair of registered images, comprising:
 a. providing a first original gray-level image, a second original gray-level images, a first negative image related to said first original image and a second negative image related to said second original image, 
 b. extracting by a computer respective pluralities of blobs from each of said first and second original images and each of said first and second negative images, 
 c. matching by a computer each extracted blob in said first original and negative images with each extracted blob in said second original and negative images to obtain matched and unmatched blobs, and 
 d. testing by a computer all said unmatched blobs to identify blobs of change. 
 
     
     
       2. The method of  claim 1 , wherein said step of extracting further includes:
 i. extracting a first plurality of blobs from said first original image, a second plurality of blobs from said second original image, a third plurality of blobs from said first negative image and a fourth plurality of blobs from said second negative image, 
 ii. forming a first unified blob list by unifying said first plurality with said third plurality of blobs, and 
 iii. forming a second unified blob list by unifying said second plurality with said fourth plurality of blobs. 
 
     
     
       3. The method of  claim 1 , wherein said step of extracting is accomplished using a modified connectivity analysis along gray-levels algorithm. 
     
     
       4. The method of  claim 2 , wherein said step of matching further includes determining if each blob in said first unified blob list has a corresponding blob in said second unified blob list, and if each blob in said second unified blob list has a corresponding blob in said first unified blob list. 
     
     
       5. The method of  claim 4 , wherein said determining includes checking overlaps of pixels. 
     
     
       6. The method of  claim 5 , wherein said overlap is about 90%. 
     
     
       7. The method of  claim 2 , wherein said step of testing includes calculating for each said unmatched blob a fitness measure, and comparing said fitness measure with a predetermined threshold to establish whether each said unmatched blob is a said blob of change. 
     
     
       8. The method of  claim 7 , wherein said substep of calculating said fitness measure includes: for each said unmatched blob:
 i. calculating a first and a second saliency in each of said first and second original images respectively, 
 ii. dividing said first saliency by said second saliency to obtain a saliency ratio, 
 iii. calculating a gradient distribution measure, and 
 iv. setting said fitness measure being to be equal to said saliency ratio if said saliency ratio is larger than or equal to said threshold, and setting said fitness measure to be equal to the product of said saliency ratio and said gradient distribution measure if said saliency ratio is smaller than said threshold. 
 
     
     
       9. The method of  claim 6 , wherein said threshold has a value of about 0.6. 
     
     
       10. The method of  claim 8 , wherein said substep of calculating said first and said second saliency includes using a contour-following algorithm. 
     
     
       11. A method for change detection in images, comprising:
 a. providing a pair of first and second registered gray level images, wherein said step of providing further includes providing respective negative first and second images; 
 b. extracting by a computer respective first and second pluralities of blobs from each of said images using a modified connectivity along gray levels (CAG) analysis, wherein said step of extracting further includes extracting a third plurality of blobs from said negative first image and a fourth plurality of blobs from said second negative image; 
 c. locating by a computer at least one unmatched blob in at least one of said images, wherein said step of locating at least one unmatched blob further includes:
 i. comparing each blob from said first and third pluralities of blobs with each blob from said second and fourth pluralities of blobs, 
 ii. locating corresponding blobs based on said comparison, and 
 iii. identifying said at least one unmatched blob based on a pixel overlap between each pair of said corresponding blobs; and 
 
 d. identifying by a computer at least one blob of change related to said images by applying a test on said at least one unmatched blob. 
 
     
     
       12. The method of  claim 11 , wherein said step of identifying said at least one blob of change by further includes checking a fitness measure to said at least one unmatched blob. 
     
     
       13. The method of  claim 12 , wherein said substep of checking said fitness measure includes: for each said at least one unmatched blob
 i. calculating a first and a second saliency in each of said first and second gray level images respectively, 
 ii. dividing said first saliency by said second saliency to obtain a saliency ratio, 
 iii. calculating a gradient distribution measure, and 
 iv. setting said fitness measure being to be equal to said saliency ratio if said saliency ratio is larger than or equal to a predetermined threshold, and setting said fitness measure to be equal to the product of said saliency ratio and said gradient distribution measure if said saliency ratio is smaller than said threshold. 
 
     
     
       14. The method of  claim 13 , wherein said threshold has a value of about 0.6. 
     
     
       15. The method of  claim 14 , wherein said substep of calculating said first and said second saliency includes using a contour-following algorithm. 
     
     
       16. A method for change detection between a pair of images, the method comprising:
 extracting by a computer respective pluralities of blobs from each of a first gray-level image, a second gray-level image, a first negative image related to the first gray-level image, and a second negative image related to the second gray-level image,   comparing by a computer extracted blobs in the first gray-level image and first negative image with extracted blobs in the second gray-level image and second negative image to obtain matched blobs and unmatched blobs, and   testing by a computer a plurality of the unmatched blobs to identify blobs of change.   
     
     
       17. The method of claim 16, further comprising generating each of the first and second negative images. 
     
     
       18. The method of claim 16, further comprising outputting a list of the blobs of change. 
     
     
       19. The method of claim 16, wherein said testing further comprises calculating a fitness function of a first unmatched blob of the first gray-level and first negative images in a unified list of the extracted blobs from the second gray-level and second negative images. 
     
     
       20. The method of claim 16, wherein the first grey-level image and the second grey-level image comprise different illumination. 
     
     
       21. A method for change detection between a pair of images, the method comprising:
 accessing by a computer a first gray-level image, a second gray-level image, a first negative image related to the first gray-level image and a second negative image related to the second gray-level image, and   extracting by a computer respective pluralities of blobs from each of the first and second gray-level images and each of the first and second negative images.   
     
     
       22. The method of claim 21, wherein said extracting respective pluralities of blobs further comprises:
 extracting a first plurality of blobs from the first gray-level image, a second plurality of blobs from the second gray-level image, a third plurality of blobs from the first negative image and a fourth plurality of blobs from the second negative image;   generating a first unified blob list by unifying the first plurality of blobs with the third plurality of blobs; and   generating a second unified blob list by unifying the second plurality of blobs with the fourth plurality of blobs.   
     
     
       23. The method of claim 22, further comprising identifying each blob in the first unified blob list that has a corresponding blob in the second unified blob list, and identifying each blob in the second unified blob list that has a corresponding blob in the first unified blob list. 
     
     
       24. The method of claim 21, wherein said extracting respective pluralities of blobs comprises using a modified connectivity along gray levels (CAG) analysis. 
     
     
       25. The method of claim 21, wherein said extracting respective pluralities of blobs comprises excluding from the first, second, third and fourth pluralities of blobs blobs having a pixel size less than a minimum pixel threshold or greater than a maximum pixel threshold. 
     
     
       26. A method for change detection between a pair of images, the method comprising:
 comparing by a computer first extracted blobs in a first image and a first negative image related to the first image with second extracted blobs in a second image and a second negative image related to the second image to obtain matched blobs and unmatched blobs, and   testing by a computer a plurality of the unmatched blobs to identify blobs of change.   
     
     
       27. The method of claim 26, wherein said comparing comprises determining if each of the first extracted blobs has a corresponding blob in the second extracted blobs and if each of the second extracted blobs has a corresponding blob in the first extracted blobs. 
     
     
       28. The method of claim 27, wherein said determining comprises determining if an overlap of pixels of each of the first extracted blobs with the corresponding blob exceeds a threshold amount. 
     
     
       29. The method of claim 28, wherein the threshold amount is approximately 75%. 
     
     
       30. The method of claim 28, wherein the threshold amount is approximately 90%. 
     
     
       31. The method of claim 28, wherein the plurality of unmatched blobs comprises certain first and second extracted blobs that do not have an overlap of pixels with any corresponding blob that exceeds the threshold amount. 
     
     
       32. The method of claim 31, wherein said testing the plurality of unmatched blobs comprises for each of the plurality of unmatched blobs:
 calculating a fitness measure; and   comparing the fitness measure with a second threshold amount.   
     
     
       33. The method of claim 32, wherein the fitness measure is based at least on a ratio of first and second saliency gradients associated with, respectively, the first and second images. 
     
     
       34. The method of claim 33, wherein the fitness measure is further based at least on a product of the ratio and a gradient distribution measure. 
     
     
       35. The method of claim 33, further comprising calculating the first and second saliency gradients using a contour-following algorithm. 
     
     
       36. The method of claim 35, further comprising assigning a weight to each pixel in the first and second images indicative of an edge saliency. 
     
     
       37. A system for detecting changes between a pair of images, the system comprising:
 a processor configured to
 extract a first plurality of blobs from a first gray-level image and a first negative image related to the first gray-level image, 
 extract a second plurality of blobs from the second gray-level image and a second negative image related to the second gray-level image, 
 compare each of the first plurality of blobs with each blob in the second plurality of blobs to identify matched blobs and unmatched blobs, and 
 test the unmatched blobs to identify blobs of change; and 
   an output configured to generate a list of the blobs of change.   
     
     
       38. The system of claim 37, wherein the matched blobs comprise:
 identified ones of the first plurality of blobs that have a corresponding blob in the second plurality of blobs; and   identified ones of the second plurality of blobs that have a corresponding blob in the first plurality of blobs.   
     
     
       39. The system of claim 38, wherein each of the matched blobs and its corresponding blob comprise a particular number of pixels that have the same coordinates. 
     
     
       40. The system of claim 38, wherein the processor is further configured to test the unmatched blobs by computing a fitness measure of each of:
 the unmatched blobs of the first plurality of blobs in the second graylevel image; and   the unmatched blobs of the second plurality of blobs in the first gray-level image.