Apparatus and software for geometric coarsening and segmenting of still images

• US 20080292187A1
• Filed: 05/23/2007
• Published: 11/27/2008
• Est. Priority Date: 05/23/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: VideoSurf, Inc. (Microsoft Corporation)
• Inventors: Achi, Brandt, Eitan, Sharon, Asael, Moshe
• Granted Patent: US 7,920,748 B2
• Time in Patent Office: Days
• US Class Current: 382/180
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

An apparatus and software for processing an image reduces the number of pixels constituting the image by sequentially eliminating alternate rows and columns of pixels, the information represented by each pixel being eliminated (a “source” pixel) being redistributed into adjacent “destination” pixel locations. The redistribution is made in proportion to the similarity between the source and each destination pixel, e.g., similarity of color and/or luminance values.

Claims

1. An apparatus for performing geometric coarsening and segmenting of an image representable as a two-dimensional array of pixels comprising:

a) a first engine operable to select every other column of the array to accumulate information contained therein into adjacent columns;

b) a second engine operable to determine, for each pixel of each selected column, a similarity of said pixel with respect to a first set of nearest pixels of adjacent columns to form respective dependency values;

c) a third engine operable to distribute, for each pixel of each selected column, information for said pixel to the first set of pixels of adjacent columns wherein said information from said pixel is accumulated, together with any existing information of said pixel, and weighted by the respective dependency values;

d) a fourth engine operable to select every other row of the array for accumulating information contained therein into adjacent rows;

e) a fifth engine operable to determine, for each pixel of each selected row, a similarity of said pixel with respect to a second set of nearest six pixels of adjacent rows to form respective dependency values; and

f) a sixth engine operable to distribute, for each pixel of each selected row, information for said pixel to the second set of pixels of adjacent rows wherein said information from said pixel is accumulated, together with any existing information of said pixel, and weighted by the respective dependency values.

2. The apparatus according to claim 1 wherein said first set of pixels comprise the six nearest pixels in adjacent columns and said second set of pixels comprise the six nearest pixels in adjacent rows.

3. The apparatus according to claim 1 wherein said engines first, second and third engines operate to perform the corresponding actions prior to operation of fourth, fifth and sixth engines.

4. The apparatus according to claim 3 wherein, after said actions attributable to said first, second and third engines are performed, and prior to performance of action attributable to said fourth, fifth and sixth engines, said selected every other column is deleted and, after operation of said fourth, fifth and sixth engines, said selected every other row is deleted.

5. The apparatus according to claim 4 wherein said actions attributable to said first, second, third, fourth, fifth and sixth engines are repeated a plurality of times.

6. The apparatus according to claim 1 wherein said similarity of pixels is determined based on specific color information endowed for each pixel and a specific similarity function appropriate to a type of said color information.

7. The apparatus according to claim 5 wherein, for each repetition of operations performed by said engines a through f, each remaining pixel accumulates additional information from an ever increasing volume of the original image pixels wherein remaining pixels are those not previously deleted.

8. The apparatus according to claim 5 wherein, for each repetition of operations performed by engines a though f, each remaining pixel may be mapped back to portions of pixels in the original image by backtracking the dependencies contributing to its accumulation wherein remaining pixels are those not previously deleted.

9. The apparatus according to claim 5 further comprising an engine operable to map back to portions of pixels in the original image by backtracking the dependencies contributing to its accumulation wherein remaining pixels are those not previously deleted.

10. The apparatus according to claim 1 wherein each pixels in the original image is endowed with color information and at least one additional type of information.

11. An apparatus of reducing the size of an image stored as a two-dimensional array of pixels comprising one or more engines operable to perform the steps of:

selecting a plurality of columns for elimination, each including a plurality of column-aligned source pixels;

redistributing image information from each of said column-aligned source pixels to corresponding nearest destination pixels of columns adjacent each of said column-aligned source pixels;

eliminating said plurality of columns selected for elimination;

selecting a plurality of row for elimination, each including a plurality of row-aligned source pixels;

redistributing image information from each of said row-aligned source pixels to corresponding nearest destination pixels of rows adjacent each of said row-aligned source pixels; and

eliminating said plurality of rows selected for elimination.

12. The apparatus according to claim 11 wherein said steps of redistributing said image information include steps of determining, for each of said column-aligned and row-aligned source pixels, a similarity of said source pixel with respect corresponding ones of said nearest destination pixels to form respective dependency values

13. An apparatus for compressing data stored in a multidimensional array of data elements, the apparatus comprising engines operable to perform the steps of:

a) selecting a first plurality of subarrays from said multidimensional array, said first plurality of subarrays arranged along a selected one said dimensions, each of said first plurality of subarrays including a first plurality of source data elements;

b) determining, for each of said first plurality of source data elements, a similarity of said source data elements with respect to a corresponding set of nearest destination data elements to form respective dependency values;

c) distributing data corresponding to each of said first plurality of source data elements to the corresponding set of nearest destination data elements wherein said information from said source data elements is accumulated, together with any existing information of said nearest destination data elements and weighted by the respective dependency values;

d) selecting a next plurality of subarrays from said multidimensional array, said next plurality of subarrays arranged along another of said dimensions and each including another plurality of source data elements; and

e) repeating steps b-c with said next plurality of subarrays.

14. A computer program comprising:

a computer usable medium having computer readable program code embodied therein for geometric coarsening and segmenting of an image representable as a two-dimensional array of pixels, the computer readable program code including;

a) computer readable program code for causing the computer to select every other column of the array for accumulating information contained therein into adjacent columns;

b) computer readable program code for causing the computer to determine, for each pixel of each selected column, a similarity of said pixel with respect to a first set of nearest pixels of adjacent columns to form respective dependency values;

c) computer readable program code for causing the computer to distribute, for each pixel of each selected column, information for said pixel to the first set of pixels of adjacent columns wherein said information from said pixel is accumulated, together with any existing information of said pixel, and weighted by the respective dependency values;

d) computer readable program code for causing the computer to select every other row of the array for accumulating information contained therein into adjacent rows;

e) computer readable program code for causing the computer to determine, for each pixel of each selected row, a similarity of said pixel with respect to a second set of nearest six pixels of adjacent rows to form respective dependency values; and

f) computer readable program code for causing the computer to distribute, for each pixel of each selected row, information for said pixel to the second set of pixels of adjacent rows wherein said information from said pixel is accumulated, together with any existing information of said pixel, and weighted by the respective dependency values.

15. The computer program according to claim 14 wherein said first set of pixels comprise the six nearest pixels in adjacent columns and said second set of pixels comprise the six nearest pixels in adjacent rows.

16. The computer program according to claim 14 wherein said computer readable program code for causing the computer to perform actions a, b and c operates prior to the program code for causing the computer to perform the actions of d, e and f.

17. The computer program according to claim 16 wherein, after said computer readable program code causes the computer to perform actions a, b and c, and prior to operation of said computer readable program code causing the computer to perform actions d, e and f, computer readable program code for causes said selected every other column to be deleted and, after said actions d, e and f, computer readable program codes causes said selected every other row to be deleted.

18. The computer program according to claim 17 wherein said computer readable program code operates to repeatedly perform actions a through f a plurality of times.

19. The computer program according to claim 14 wherein said similarity of pixels is determined based on specific color information endowed for each pixel and a specific similarity function appropriate to a type of said color information.

20. The computer program according to claim 18 wherein, for each repetition of actions a through f, each remaining pixel accumulations additional information from an ever increasing volume of the original image pixels wherein remaining pixels are those not previously deleted.

21. The computer program according to claim 18 wherein, for each repetition of actions a though f, each remaining pixel may be mapped back to portions of pixels in the original image by backtracking the dependencies contributing to its accumulation wherein remaining pixels are those not previously deleted.

22. The computer program according to claim 16 further comprising computer readable program code for causing the computer to map back to portions of pixels in the original image by backtracking the dependencies contributing to its accumulation wherein remaining pixels are those not previously deleted.

23. The computer program according to claim 14 wherein each pixels in the original image is endowed with color information and at least one additional type of information.

24. A computer program comprising:

a computer usable medium having computer readable program code embodied therein for reducing the size of an image stored as a two-dimensional array of pixels, the computer readable program code including;

computer readable program code for causing the computer to select a plurality of columns for elimination, each including a plurality of column-aligned source pixels;

computer readable program code for causing the computer to redistribute image information from each of said column-aligned source pixels to corresponding nearest destination pixels of columns adjacent each of said column-aligned source pixels;

computer readable program code for causing the computer to eliminate said plurality of columns selected for elimination;

computer readable program code for causing the computer to select a plurality of row for elimination, each including a plurality of row-aligned source pixels;

computer readable program code for causing the computer to redistribute image information from each of said row-aligned source pixels to corresponding nearest destination pixels of rows adjacent each of said row-aligned source pixels; and

computer readable program code for causing the computer to eliminate said plurality of rows selected for elimination.

25. The computer program according to claim 24 further comprising computer readable program code for causing the computer to determine, for each of said column-aligned and row-aligned source pixels, a similarity of said source pixel with respect corresponding ones of said nearest destination pixels to form respective dependency values

26. A computer program comprising:

a computer usable medium having computer readable program code embodied therein for compressing data stored in a multidimensional array of data elements, the computer readable program code including;

a) computer readable program code for causing the computer to select a first plurality of subarrays from said multidimensional array, said first plurality of subarrays arranged along a selected one said dimensions, each of said first plurality of subarrays including a first plurality of source data elements;

b) computer readable program code for causing the computer to determine, for each of said first plurality of source data elements, a similarity of said source data elements with respect to a corresponding set of nearest destination data elements to form respective dependency values;

c) computer readable program code for causing the computer to distribute data corresponding to each of said first plurality of source data elements to the corresponding set of nearest destination data elements wherein said information from said source data elements is accumulated, together with any existing information of said nearest destination data elements and weighted by the respective dependency values;

d) computer readable program code for causing the computer to select a next plurality of subarrays from said multidimensional array, said next plurality of subarrays arranged along another of said dimensions and each including another plurality of source data elements; and

e) computer readable program code for causing the computer to repeating actions b-c with said next plurality of subarrays.