Mathematics desk | ||
---|---|---|
< July 1 | << Jun | July | Aug >> | Current desk > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
Given a 2-dimensional array of random values (think of a noisy image) how do you construct an autocorrelation filter that will converge on a given point in the array starting anywhere in the array (or almost anywhere) Philvoids ( talk) 15:41, 2 July 2024 (UTC)
A numerical test |
---|
The following discussion has been closed. Please do not modify it. |
Below is an 8x8 array of numbers. Start from any one of 64 locations ranging from (x0,y0) = (0,0) bottom left to (7,7) top right. Can you show a formula whose input (x0,y0) always yields as output (X,Y) = (3,3) ? Y ^ | | 7 247 51 132 34 223 6 121 243 6 81 196 176 224 77 159 211 171 5 119 245 56 244 141 247 33 115 4 254 49 175 170 95 19 208 108 3 118 204 145 117 25 242 162 229 2 35 200 250 115 45 62 229 135 1 212 219 232 186 196 59 68 74 0 192 207 14 129 102 13 28 65 0 1 2 3 4 5 6 7 -->X |
Philvoids ( talk) 09:08, 3 July 2024 (UTC)
The context for my question is my interest in efficient software to perform Image stitching, Document mosaicing or extraction of unlimited large-area maps from multiple map patches screen dumped from sites such as Google Maps. In each case we begin with a pair of images (which are 2D arrays of pixel values) that are known to overlap partly, but the exact offset between them has to be found before we can join them seamlessly. Stitching map patches together seems relatively easy because with correct offset there will be 100% correlation between the images in their overlap area; this is an autocorrelation because the pixels come from one master map. Consider my 8x8 array example as part of a map overlap area; we make a rough guess of the x-y offset of the overlapping map. Allow that the guess is likely inaccurate, which becomes apparent if we look for the pixel value at position (x,y)=(3,3) on the second map, and are disapointed to find it is not 117. We know all the array values and its size suggests there is one correct offset and 63 wrong offsets.
Pseudocode for a clumsy stitching |
---|
The following discussion has been closed. Please do not modify it. |
define maparray(8,8) x=0 y=0 v=maparray(0,0) while v != maparray(3,3) {x++ if x==8 then x=0, y++ if y==8 then print "No match found." v=maparray(x,y) } print "Update offset by x:",-x," y:",-y Deficiencies of this code are - Up to 63 comparisons can be be needed before the correct offset is found - Noise causing false positive(s) or failure is not considered in my question but it arises when stitching photographs. The clumsy routine lacks noise tolerance because a 1 or 2 unit deviation at (3,3) disables the search, or causes a false positive at (3,2), (0,3), (0,5) or (7,5). That is regarding the array byte values that could represent 256 grey levels; I think that the error probabilities in hardware are independent of bit weightings and I find that there are 13 locations whose values have 2 or less [[Hamming distance]] from the value in (3,3) that was used for searching. |
Ideas for an improved algorithm
- A larger array may be needed for a larger overlap area
- Sequential search costs time and computation effort but is only necessary where there is no gradient to follow towards the correct offset.
- False positives that arise from noise when searching for one pixel value may be reduced by searching for blocks of pixel values, such as the combination of (3,3), (4,3), (3,4) and (4,4). Philvoids ( talk) 20:05, 5 July 2024 (UTC)
I limit the scope of my question to solving the challenge of stitching together map patches under these conditions: 1. There is no differential distortion between patches, no rotation, no stretching or compression, no lighting or parallax difference as can occur between photographs. 2. There is some uncertainty in the offset of the X and Y coordinates of the 2nd patch from the coordinates of the 1st patch that shall be regarded as the true reference coordinates for the full map to be produced. 3. From our knowledge of manually collecting map patches we predict our maximum error in estimating the X and Y offsets of a new patch. To accomodate these errors we need a practical overlap area between patches. The example calls for an 8x8 pixel overlap area. 4. For stitching a given pair of map patches, the predicted overlap area will be chosen close to a corner of the first established patch, from which the array of pixel values is read. Condition no. 1 guarantees that exactly the same array of pixel values exists somewhere to be found on the 2nd patch. 5. To run the pseudocoded algorithm below we must identify a unique target pixel in the overlap array. This was done in the example presented. Here only the pixel located at (xt,yt) = (3,3) and no other has the value 117. The algorithm fails if any other pixel in the array has the same value as the target. Obviously it is difficult to find a unique target in, say, a featureless desert area on a map. In such cases it may be easiest with manual interaction to try another target within the given array, or to choose a different overlap area. Pinpointing a suitable target pixel is a simpler and quicker task than the feature detection described by Lambiam. 6. The pseudocode below obviously does find the target pixel at correct offset (3,3) when it sees as input data only the test array that already has correct reference XY coordinates. However it succeeds in finding the target pixel wherever it may be hidden within the overlap array by incorrect estimates of the 2nd patch coordinates; this solution I report as tested for all 63 possible misalignments of the patches. The algorithm proceeds by building two "guide" arrays XG() and YG() that are progressively filled with 511 (a pixel value that is outside the range of single-byte pixel values) at invalid locations. 7. The inference when the algorithm takes as input array the 2nd patch using the uncertain estimated coordinate system (Xestim, Yestim) and finds the target pixel at (xu,yu) is that the correct 2nd patch coordinates to be used for stitching are ( (Xestm - xu + 3), (Yestim - yu + 3) ).
Pseudocode for stitching map patches |
---|
The following discussion has been closed. Please do not modify it. |
rem INPUTS: dimension A(7,7) as example array A(x,y) tx=3 example target is (3,3) ty=3 rem VARIABLES: dimension B(7,7), XG(7,7), YG(7,7) rem ASSIGNATIONS: for y=0 to 7 { for x=0 to 7 { B(x,y)=A(x,y)-A(tx,ty) if y==ty { XG(x,ty)=B(x,y) } else { XG(x,ty)=511 } if x==tx { YG(tx,y)=B(x,y) } else { XG(tx,y)=511 } } rem SEARCH: for x=0 to 7 { for y=0 to 7 { if B(x,y)==YG(x,y) { xu=x goto XFOUND } }" print ERROR: X NOT FOUND XFOUND: for y=0 to 7 { for x=0 to xu { if B(x,y)==XG(x,y) { yu=y print OFFSET (X,Y) FOUND. end } } print ERROR: Y NOT FOUND |
Philvoids ( talk) 20:47, 16 July 2024 (UTC)
Mathematics desk | ||
---|---|---|
< July 1 | << Jun | July | Aug >> | Current desk > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
Given a 2-dimensional array of random values (think of a noisy image) how do you construct an autocorrelation filter that will converge on a given point in the array starting anywhere in the array (or almost anywhere) Philvoids ( talk) 15:41, 2 July 2024 (UTC)
A numerical test |
---|
The following discussion has been closed. Please do not modify it. |
Below is an 8x8 array of numbers. Start from any one of 64 locations ranging from (x0,y0) = (0,0) bottom left to (7,7) top right. Can you show a formula whose input (x0,y0) always yields as output (X,Y) = (3,3) ? Y ^ | | 7 247 51 132 34 223 6 121 243 6 81 196 176 224 77 159 211 171 5 119 245 56 244 141 247 33 115 4 254 49 175 170 95 19 208 108 3 118 204 145 117 25 242 162 229 2 35 200 250 115 45 62 229 135 1 212 219 232 186 196 59 68 74 0 192 207 14 129 102 13 28 65 0 1 2 3 4 5 6 7 -->X |
Philvoids ( talk) 09:08, 3 July 2024 (UTC)
The context for my question is my interest in efficient software to perform Image stitching, Document mosaicing or extraction of unlimited large-area maps from multiple map patches screen dumped from sites such as Google Maps. In each case we begin with a pair of images (which are 2D arrays of pixel values) that are known to overlap partly, but the exact offset between them has to be found before we can join them seamlessly. Stitching map patches together seems relatively easy because with correct offset there will be 100% correlation between the images in their overlap area; this is an autocorrelation because the pixels come from one master map. Consider my 8x8 array example as part of a map overlap area; we make a rough guess of the x-y offset of the overlapping map. Allow that the guess is likely inaccurate, which becomes apparent if we look for the pixel value at position (x,y)=(3,3) on the second map, and are disapointed to find it is not 117. We know all the array values and its size suggests there is one correct offset and 63 wrong offsets.
Pseudocode for a clumsy stitching |
---|
The following discussion has been closed. Please do not modify it. |
define maparray(8,8) x=0 y=0 v=maparray(0,0) while v != maparray(3,3) {x++ if x==8 then x=0, y++ if y==8 then print "No match found." v=maparray(x,y) } print "Update offset by x:",-x," y:",-y Deficiencies of this code are - Up to 63 comparisons can be be needed before the correct offset is found - Noise causing false positive(s) or failure is not considered in my question but it arises when stitching photographs. The clumsy routine lacks noise tolerance because a 1 or 2 unit deviation at (3,3) disables the search, or causes a false positive at (3,2), (0,3), (0,5) or (7,5). That is regarding the array byte values that could represent 256 grey levels; I think that the error probabilities in hardware are independent of bit weightings and I find that there are 13 locations whose values have 2 or less [[Hamming distance]] from the value in (3,3) that was used for searching. |
Ideas for an improved algorithm
- A larger array may be needed for a larger overlap area
- Sequential search costs time and computation effort but is only necessary where there is no gradient to follow towards the correct offset.
- False positives that arise from noise when searching for one pixel value may be reduced by searching for blocks of pixel values, such as the combination of (3,3), (4,3), (3,4) and (4,4). Philvoids ( talk) 20:05, 5 July 2024 (UTC)
I limit the scope of my question to solving the challenge of stitching together map patches under these conditions: 1. There is no differential distortion between patches, no rotation, no stretching or compression, no lighting or parallax difference as can occur between photographs. 2. There is some uncertainty in the offset of the X and Y coordinates of the 2nd patch from the coordinates of the 1st patch that shall be regarded as the true reference coordinates for the full map to be produced. 3. From our knowledge of manually collecting map patches we predict our maximum error in estimating the X and Y offsets of a new patch. To accomodate these errors we need a practical overlap area between patches. The example calls for an 8x8 pixel overlap area. 4. For stitching a given pair of map patches, the predicted overlap area will be chosen close to a corner of the first established patch, from which the array of pixel values is read. Condition no. 1 guarantees that exactly the same array of pixel values exists somewhere to be found on the 2nd patch. 5. To run the pseudocoded algorithm below we must identify a unique target pixel in the overlap array. This was done in the example presented. Here only the pixel located at (xt,yt) = (3,3) and no other has the value 117. The algorithm fails if any other pixel in the array has the same value as the target. Obviously it is difficult to find a unique target in, say, a featureless desert area on a map. In such cases it may be easiest with manual interaction to try another target within the given array, or to choose a different overlap area. Pinpointing a suitable target pixel is a simpler and quicker task than the feature detection described by Lambiam. 6. The pseudocode below obviously does find the target pixel at correct offset (3,3) when it sees as input data only the test array that already has correct reference XY coordinates. However it succeeds in finding the target pixel wherever it may be hidden within the overlap array by incorrect estimates of the 2nd patch coordinates; this solution I report as tested for all 63 possible misalignments of the patches. The algorithm proceeds by building two "guide" arrays XG() and YG() that are progressively filled with 511 (a pixel value that is outside the range of single-byte pixel values) at invalid locations. 7. The inference when the algorithm takes as input array the 2nd patch using the uncertain estimated coordinate system (Xestim, Yestim) and finds the target pixel at (xu,yu) is that the correct 2nd patch coordinates to be used for stitching are ( (Xestm - xu + 3), (Yestim - yu + 3) ).
Pseudocode for stitching map patches |
---|
The following discussion has been closed. Please do not modify it. |
rem INPUTS: dimension A(7,7) as example array A(x,y) tx=3 example target is (3,3) ty=3 rem VARIABLES: dimension B(7,7), XG(7,7), YG(7,7) rem ASSIGNATIONS: for y=0 to 7 { for x=0 to 7 { B(x,y)=A(x,y)-A(tx,ty) if y==ty { XG(x,ty)=B(x,y) } else { XG(x,ty)=511 } if x==tx { YG(tx,y)=B(x,y) } else { XG(tx,y)=511 } } rem SEARCH: for x=0 to 7 { for y=0 to 7 { if B(x,y)==YG(x,y) { xu=x goto XFOUND } }" print ERROR: X NOT FOUND XFOUND: for y=0 to 7 { for x=0 to xu { if B(x,y)==XG(x,y) { yu=y print OFFSET (X,Y) FOUND. end } } print ERROR: Y NOT FOUND |
Philvoids ( talk) 20:47, 16 July 2024 (UTC)