Detection of gaps in scanned images

Claim 3

A method as in claim 1 wherein the first pair of peripheral pixels is selected such that the center pixel is located along an axis between the first and second ones of the first pair of pixels.

Claim 4

A method as in claim 1 wherein the second pair of peripheral pixels is selected such that the center pixel is located along an axis between the first and second ones of the second pair of pixels.

Claim 5

A method as in claim 1 wherein the step of comparing the values of other adjacent pixels to other predetermined value patterns additionally comprises the step of: comparing the values of the other adjacent pixels to the other predetermined value patterns to identify the location of two apparent line features located on opposite sides of the potential gap.

Claim 6

A method as in claim 1 wherein the step of comparing the values of the other adjacent pixels to other predetermined value patterns additionally comprises the steps of: determining if the apparent line features have the topological characteristics of an erroneously scanned single line in the source image, by locating a perimeter pixel situated along the perimeter for each apparent line feature; and calculating the distance between the perimeter pixels for each apparent line feature.

Claim 7

A method as in claim 1 wherein the image data is bitmap-encoded, and the step of reading image data from the memory to determine the values of preselected pixels additionally comprises: determining the pixel values by reading the contents of array locations in the memory.

Claim 8

A method as in claim 1 wherein the image data is run-encoded, and the step of reading image data from the memory to determine the values of preselected pixels additionally comprises: determining the pixel values by reading the contents of locations in the memory corresponding to the start coordinates of runs of pixels in the source image.

Claim 11

A method as in claim 8 additionally comprising the steps of, after the step (iv) of producing an indication that a potential erroneous gap exists adjacent the center pixel: reading the image data to determine the location of a first feature edge pixel, the first feature edge pixel being a pixel having a value equal to the foreground line value, and located near the center pixel and the first pixel of the first pixel pair; reading the image data to determine the location of a second feature edge pixel, the second feature edge pixel being that pixel having a value equal to the foreground line value, and located near the center pixel and the second pixel of the first pixel pair; reading the image data to determine the location of a first feature terminus pixel, the first feature terminus pixel being a pixel having a value equal to the foreground line value, and located in a counterclockwise direction and a predetermined number of pixels away from the first feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; reading the image data to determine the location of a second feature terminus pixel, the second feature terminus pixel being a pixel having a value equal to the foreground line value, and located in a clockwise direction and a predetermined number of pixels away from the second feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; calculating a first distance between the first feature terminus pixel and the second feature terminus pixel; and if the first distance is less than a predetermined distance, producing an indication that an erroneous gap does not exist adjacent the center pixel.

Claim 12

A method as in claim 9 additionally comprising the steps of: reading the image data to determine the location of a third feature terminus pixel, the third feature terminus pixel being a pixel having a value equal to the foreground line value, and located in a clockwise direction and a predetermined number of pixels away from the first feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; reading the image data to determine the location of a fourth feature terminus pixel, the fourth feature terminus pixel being that pixel having a value equal to the foreground line value, and located in a counterclockwise direction and a predetermined number of pixels away from the second feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; calculating a second distance between the third feature terminus pixel and the fourth feature terminus pixel; and if the second distance is less than a predetermined distance, producing an indication that an erroneous gap does not exist adjacent the center pixel.

Claim 13

A method as in claim 10 additionally comprising the step of: if the distance between the first terminus pixel and the third terminus pixel is greater than a predetermined amount, producing an indication that an unintentional gap does not exist adjacent the center pixel; if the distance between the second terminus pixel and the fourth terminus pixel is greater than a predetermined amount, producing an indication that an erroneous gap does not exist adjacent the center pixel; and otherwise, producing an indication that erroneous gap does exist adjacent the center pixel.

Claim 16

A method as in claim 12 additionally comprising the step of: iteratively reading the image data to select center pixel runs and first and second run pairs, and calculating maximum possible start and minimum possible end coordinates; and producing a list of pixel runs for which erroneous gaps exist.

Claim 17

A detector for detecting erroneous gaps in image data output by a scanner, the image data being a representation of pixels of a source image input to the scanner, the detector comprising: means for storing the image data; means for comparing the values of preselected pixels corresponding to a portion of the source image to a predetermined value pattern, comprising: means for comparing the value of a center pixel in the image portion to a background gap value; means for comparing the values of a first pair of peripheral pixels to a foreground pixel value, the first pair of peripheral pixels being located on the periphery of the source image portion; and means for comparing the values of a second pair of peripheral pixels to a background pixel value, the second pair of peripheral pixels located on the periphery of the image portion; means for indicating, if the preselected pixel values match the predetermined value pattern, that a potential gap exists in the image data; means for comparing the values of other adjacent pixels in the source image portion to other predetermined patterns; and means for indicating, if the other predetermined value patterns match the other adjacent pixels, that the image data contains an erroneous gap.

Claim 18

A detector for detecting erroneous gaps in image data output by a scanner, the image data being a representation of pixels of a source image input to the scanner, the detector comprising: means for storing the image data; means for comparing the values of preselected pixels corresponding to a portion of the source image to a predetermined value pattern, comprising: means for comparing the value of a center pixel in the image portion to a background gap value; means for comparing the values of a first pair of peripheral pixels to a foreground pixel value, the first pair of peripheral pixels being located on the periphery of the source image portion; and means for comparing the values of a second pair of peripheral pixels to a background pixel value, the second pair of peripheral pixels located on the periphery of the image portion; means for indicating, if the preselected pixel values match the predetermined value pattern, that a potential gap exists in the image data; means for comparing the values of other adjacent pixels in the source image portion to other predetermined patterns; and means for indicating, if the other predetermined value patterns match the other adjacent pixels, that the image data contains an erroneous gap.

Claim 19

A detector as in claim 14 wherein the first pair of peripheral pixels is selected such that the center pixel is located along an axis between the first and second ones of the first pair of pixels.

Claim 20

A detector as in claim 14 wherein the second pair of peripheral pixels is selected such that the center pixel is located along an axis between the first and second ones of the second pair of pixels.

Claim 21

A detector as in claim 14 wherein the means for comparing the values of the other adjacent pixels to other predetermined value patterns additionally comprises: means for comparing the values of the other adjacent pixels to other predetermined value patterns to identify the location of two apparent line features located on opposite sides of the potential gap.

Claim 22

A detector as in claim 17 wherein the means for comparing the values of the other adjacent pixels to other predetermined value patterns additionally comprises: means for determining if the apparent line features have the topological characteristics of an erroneously scanned single line in the source image, and for locating a perimeter pixel situated along the perimeter for each apparent line feature; and means for calculating the distance between the perimeter pixels for each apparent line feature.

Claim 23

A detector as in claim 14 wherein the image data is bitmap-encoded, and means for comparing the values of preselected pixels to the predetermined pattern additionally comprises: means for reading the contents of locations in the memory.

Claim 24

A detector as in claim 14 wherein the image data is run-encoded, and the means for comparing the values of preselected pixels to the predetermined pattern additionally comprises: means for reading the contents of locations in the memory corresponding to the start coordinates of runs of pixels in the source image.

Claim 25

A detector for operating on image data output by a scanner in response to a source image, the image data being in the form of a bitmap representation containing a two-dimensional array of pixel values, the coordinates of the array at which a particular pixel value is located being determined by the spatial position of a corresponding pixel of the source image, each pixel value representing the intensity of the corresponding pixel in the source image, the detector identifying the location of erroneously detected pixel values corresponding to a line in the source image, the erroneous pixel values resulting in unintentional gaps in the image data representation of the line, the detector also distinguishing the gaps originating from such erroneous pixel value detection from other gaps formed intentionally as part of the source image, the detector comprising: means for storing the image data in a memory; means for reading a center pixel value from the memory; means for comparing the center pixel value to a background gap value; means for indicating, if the center pixel value is equal to the background value, that an erroneous gap does not exist adjacent the center pixel; means for reading a first pair of pixel values from the memory, the first pixel of the first pair located a predetermined number of pixels away from the center pixel, and the second pixel of the first pair located a predetermined number of pixels away from the center pixel in an opposite direction; means for reading a second pair of pixel values from the memory, the first pixel of the second pair located a predetermined number of pixels away from the center pixel, and the second pixel of the second pair located a predetermined number of pixels away from the center pixel in an opposite direction; means for comparing the values of the first and second pair of pixel values to the background value and a foreground line value; and means for indicating, if each one of the first pair of pixel values is equal to a foreground line value, and if each one of the second pair of pixel values is equal to a background gap value, that a potential erroneous gap exists adjacent the center pixel.

Claim 26

A detector for operating on image data output by a scanner in response to a source image, the image data being in the form of a bitmap representation containing a two-dimensional array of pixel values, the coordinates of the array at which a particular pixel value is located being determined by the spatial position of a corresponding pixel of the source image, each pixel value representing the intensity of the corresponding pixel in the source image, the detector identifying the location of erroneously detected pixel values corresponding to a line in the source image, the erroneous pixel values resulting in unintentional gaps in the image data representation of the line, the detector also distinguishing the gaps originating from such erroneous pixel value detection from other gaps formed intentionally as part of the source image, the detector comprising: means for storing the image data in a memory; means for reading a center pixel value from the memory; means for comparing the center pixel value to a background gap value; means for indicating, if the center pixel value is equal to the background value, that an erroneous gap does not exist adjacent the center pixel; means for reading a first pair of pixel values from the memory, the first pixel of the first pair located a predetermined number of pixels away from the center pixel, and the second pixel of the first pair located a predetermined number of pixels away from the center pixel in an opposite direction; means for reading a second pair of pixel values from the memory, the first pixel of the second pair located a predetermined number of pixels away from the center pixel, and the second pixel of the second pair located a predetermined number of pixels away from the center pixel in an opposite direction; means for comparing the values of the first and second pair of pixel values to the background value and a foreground line value; and means for indicating, if each one of the first pair of pixel values is equal to a foreground line value, and if each one of the second pair of pixel values is equal to a background gap value, that a potential erroneous gap exists adjacent the center pixel.

Claim 27

A detector as in claim 21 additionally comprising: means for reading the image data to determine the location of a first feature edge pixel, the first feature edge pixel being a pixel having a value equal to the foreground line value, and located near the center pixel and the first pixel of the first pixel pair; means for reading the image data to determine the location of a second feature edge pixel, the second feature edge pixel being that pixel having a value equal to the foreground line value, and located near the center pixel and the second pixel of the first pixel pair; means for reading the image data to determine the location of a first feature terminus pixel, the first feature terminus pixel being a pixel having a value equal to the foreground line value, and located in a counterclockwise direction and a predetermined number of pixels away from the first feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; means for reading the image data to determine the location of a second feature terminus pixel, the second feature terminus pixel being a pixel having a value equal to the foreground line value, and located in a clockwise direction and a predetermined number of pixels away from the second feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; means for calculating a first distance between the first feature terminus pixel and the second feature terminus pixel; and means for indicating, if the sum of the first and second distances is less than a predetermined distance, that an erroneous gap does not exist adjacent the center pixel.

Claim 28

A detector as in claim 22 additionally comprising: means for reading the image data to determine the location of a third feature terminus pixel, the third feature terminus pixel being a pixel having a value equal to the foreground line value, and located in a clockwise direction and a predetermined number of pixels away from the first feature edge pixel, and located adjacent at least one pixel having a value equal to the background gap value; means for reading the image data to determine the location of a fourth feature terminus pixel, the fourth feature terminus pixel being that pixel having a value equal to the foreground line value, and located in a counterclockwise direction and a predetermined number of pixels away from the second feature edge pixel, and located adjacent at least on pixel having a value equal to the background gap value; means for calculating a second distance between the third feature terminus pixel and the fourth feature terminus pixel; and means for indicating, if the second distance is less than a predetermined distance, that an erroneous gap does not exist adjacent the center pixel.

Claim 29

A detector as in claim 23 additionally comprising: means for indicating, if the distance between the first terminus pixel and the third terminus pixel is greater than a predetermined amount, that an unintentional gap does not exist adjacent the center pixel; means for indicating, if the distance between the second terminus pixel and the fourth terminus pixel is greater than a predetermined amount, that an erroneous gap does not exist adjacent the center pixel; and means for otherwise producing an indication that erroneous gap does exist adjacent the center pixel.

Claim 30

A detector for operating on image data output by a scanner in response to a source image, the image data encoded as a representation of the starting x-coordinates of runs of adjacent pixels from the same scan line having the same value, the detector identifying the location of erroneously detected pixel values corresponding to a line in the source image, the erroneous pixel values resulting in erroneous gaps in the image data, the detector also distinguishing the gaps originating from such erroneous pixel value detection from other gaps formed intentionally as part of the source image, the detector comprising: memory means, for storing the image data; means for reading the image data to select a center pixel run from the representation, the center pixel run having a pixel value equal to a background gap value; means for reading the image data to select a first pair of pixel runs from the representation, the first run of the first pair located a predetermined number of scan lines away from the center run, and the second run of the pair located a predetermined number of scan lines away from the center pixel in an opposite direction, both of the first pair of runs having pixel values equal to a predetermined foreground line value; means for reading the image data to select a second pair of pixel runs from the representation, the first run of the second pair located a predetermined number of scan lines away from the center run, and the second run of the pair located a predetermined number of scan lines away from the center pixel in an opposite direction, both of the second pair of runs having pixel values equal to a predetermined background gap value; means for calculating a maximum possible start coordinate by determining the maximum of the start coordinates of the center run, the first run of the first pair plus a predetermined offset, the second run of the first pair plus the offset, the first run of the second pair minus the offset, and the second run of the second pair minus the offset; means for calculating a minimum possible end coordinate by determining the minimum of the end coordinates of the center run, the first run of the first pair plus an offset, the second run of the first pair plus the offset, the first run of the second pair minus the offset, and the second run of the second pair minus the offset, the end coordinates of runs calculated by determining the start coordinate of a next adjacent run; and means for indicating, if the minimum possible end coordinate is greater than the maximum possible start coordinate, that an erroneous gap exists adjacent at least one pixel of the center run.

Claim 31

A detector for operating on image data output by a scanner in response to a source image, the image data encoded as a representation of the starting x-coordinates of runs of adjacent pixels from the same scan line having the same value, the detector identifying the location of erroneously detected pixel values corresponding to a line in the source image, the erroneous pixel values resulting in erroneous gaps in the image data, the detector also distinguishing the gaps originating from such erroneous pixel value detection from other gaps formed intentionally as part of the source image, the detector comprising: memory means, for storing the image data; means for reading the image data to select a center pixel run from the representation, the center pixel run having a pixel value equal to a background gap value; means for reading the image data to select a first pair of pixel runs from the representation, the first run of the first pair located a predetermined number of scan lines away from the center run, and the second run of the pair located a predetermined number of scan lines away from the center pixel in an opposite direction, both of the first pair of runs having pixel values equal to a predetermined foreground line value; means for reading the image data to select a second pair of pixel runs from the representation, the first run of the second pair located a predetermined number of scan lines away from the center run, and the second run of the pair located a predetermined number of scan lines away from the center pixel in an opposite direction, both of the second pair of runs having pixel values equal to a predetermined background gap value; means for calculating a maximum possible start coordinate by determining the maximum of the start coordinates of the center run, the first run of the first pair plus a predetermined offset, the second run of the first pair plus the offset, the first run of the second pair minus the offset, and the second run of the second pair minus the offset; means for calculating a minimum possible end coordinate by determining the minimum of the end coordinates of the center run, the first run of the first pair plus an offset, the second run of the first pair plus the offset, the first run of the second pair minus the offset, and the second run of the second pair minus the offset, the end coordinates of runs calculated by determining the start coordinate of a next adjacent run; and means for indicating, if the minimum possible end coordinate is greater than the maximum possible start coordinate, that an erroneous gap exists adjacent at least one pixel of the center run.

Claim 32

A detector as in claim 25 additionally comprising: means for iteratively reading the image data to select center pixel runs, and first and second run pairs, calculating maximum possible start and minimum possible end coordinates; and means for producing a list of pixel runs for which erroneous gaps exist.