Matrix slicing

• US 7,409,087 B2
• Filed: 05/20/2005
• Issued: 08/05/2008
• Est. Priority Date: 05/20/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hsu, Siu Chi
• Primary Examiner(s): Wu; Jingge
• Assistant Examiner(s): TSAI, TSUNG YIN
• Application Number:
  US11/133,546
• Publication Number:
  US 20060262135A1
• Time in Patent Office: 1,173 Days
• Field of Search: 382/254, 382/173
• US Class Current: 382/173
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/182 the unit being a pixel
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques

Abstract

A user identifies desired target elements in a two dimensional matrix. A set of interesting cuts is created. The maximum potential gain in isolated target elements for each cut in the set of interesting cuts is calculated. The cut with the greatest potential gain is applied to the matrix and removed from the set of interesting cuts. The maximum potential gain for each remaining cut in the set of interesting cuts is recalculated given the cuts applied so far. With each iteration, the cut providing the maximum potential gain is applied to the matrix, removed from the set of interesting cuts, and the maximum gain for each remaining cut is recalculated given the cuts applied to the matrix so far.

Claims

1. A method for isolating target elements in a matrix, comprising:

identifying target matrix elements in a matrix to isolate, wherein the matrix comprises target and non-target matrix elements;

calculating the potential gain of isolated target matrix elements for each cut from a set of matrix cuts by;

selecting a horizontal cut from the set of matrix cuts;

for each remaining cut from the set of matrix cuts between the selected cut and the nearest existing cut above the selected cut;

determining the number of isolated and isolatable target matrix elements above the selected cut and the nearest existing cut above the selected cut attributable to introducing the selected cut to the matrix;

determining the number of isolated and isolatable target matrix elements above the selected cut and the nearest existing cut above the selected cut attributable to introducing the remaining cut to the matrix;

assigning a score to each isolated and isolatable target matrix element attributable to introducing the selected cut to the matrix, wherein the score is proportional to the number of additional vertical cuts required to isolate each isolated or isolatable target matrix element; and

summing the inverse of each score assigned to each isolated and isolatable target matrix element;

setting the potential gain of isolated target matrix elements above the selected cut to the highest calculated sum;

calculating the potential gain of isolated target matrix elements below the selected cut;

selecting the highest calculated potential gain as the potential gain of isolated target elements for the selected cut; and

applying the matrix cut from the set of matrix cuts with the greatest calculated potential gain.

2. The method of claim 1, further comprising removing the applied matrix cut from the set of matrix cuts.

3. The method of claim 1, further comprising revaluating the final pair of matrix cuts applied to the matrix by calculating the actual gain of isolated target matrix elements for each pair of cuts in the set of matrix cuts, and applying the pair with the greatest calculated gain.

4. The method of claim 1, wherein applying the matrix cut from the set of matrix cuts with the greatest calculated potential gain comprises:

calculating a ratio between the potential gain of the matrix cut with the greatest calculated potential gain and the total number of isolated target matrix elements from previously applied matrix cuts, if any; and

applying the matrix cut only if the calculated ratio is greater than a threshold ratio.

5. The method of claim 1, wherein applying the matrix cut from the set of matrix cuts with the greatest calculated potential gain comprises:

calculating an average gain of isolated target pixels for previously applied matrix cuts, if any; and

applying the matrix cut with the greatest calculated potential gain only if the calculated potential gain is above the average calculated gain.

6. The method of claim 1, wherein the matrix comprises an image file, and the matrix elements comprise pixels.

7. The method of claim 1, wherein the set of cuts comprises all possible matrix cuts.

8. The method of claim 1, further comprising removing uninteresting cuts from the set of cuts, wherein a cut is uninteresting if the patterns of target matrix elements on adjacent sides of the cut are equivalent.

9. The method of claim 1, wherein the matrix elements comprise pixels, and further comprising replacing the isolated target pixels with HTML table cell.

10. A computer-readable medium with computer-executable instructions stored thereon for:

identifying target matrix elements in a matrix to isolate, wherein the matrix comprises target and non-target matrix elements;

calculating the potential gain of isolated target matrix elements for each cut from a set of matrix cuts by;

selecting a horizontal cut from the set of matrix cuts;

calculating the potential gain of isolated target matrix elements above the selected cut;

for each remaining cut from the set of matrix cuts between the selected cut and the nearest existing cut below the selected cut;

determining the number of isolated and isolatable target matrix elements below the selected cut and the nearest existing cut below the selected cut attributable to introducing the selected cut to the matrix;

determining the number of isolated and isolatable target matrix elements below the selected cut and the nearest existing cut below the selected cut attributable to introducing the remaining cut to the matrix;

assigning a score to each isolated and isolatable target matrix element attributable to introducing the selected cut to the matrix, wherein the score is proportional to the number of additional vertical cuts required to isolate each isolated or isolatable target matrix element; and

summing the inverse of each score assigned to each isolated and isolatable target matrix element;

setting the potential gain of isolated target matrix elements above the selected cut to the highest calculated sum;

selecting the highest calculated potential gain as the potential gain of isolated target elements for the selected cut; and

applying the matrix cut from the set of matrix cuts with the greatest calculated potential gain.

11. The computer-readable medium of claim 10, further comprising removing the applied matrix cut from the set of matrix cuts.

12. The computer-readable medium of claim 10, wherein applying the matrix cut from the set of matrix cuts with the greatest calculated potential gain comprises computer-executable instructions for:

calculating a ratio between the potential gain of the matrix cut with the greatest calculated potential gain and the total number of isolated target matrix elements from previously applied matrix cuts, if any; and

applying the matrix cut only if the calculated ratio is greater than a threshold ratio.

13. A system for isolating target matrix elements in a matrix, the system comprising:

identifying means for identifying target matrix elements in a matrix to isolate, wherein the matrix comprises target and non-target matrix elements;

maximum gain calculating means for calculating the potential gain of isolated target matrix elements for each cut from a set of matrix cuts by;

selecting a horizontal cut from the set of matrix cuts;

for each remaining cut from the set of matrix cuts between the selected cut and the nearest existing cut above the selected cut;

determining the number of isolated and isolatable target matrix elements above the selected cut and the nearest existing cut above the selected cut attributable to introducing the selected cut to the matrix;

determining the number of isolated and isolatable target matrix elements above the selected cut and the nearest existing cut above the selected cut attributable to introducing the remaining cut to the matrix;

assigning a score to each isolated and isolatable target matrix element attributable to introducing the selected cut to the matrix, wherein the score is proportional to the number of additional vertical cuts required to isolate each isolated or isolatable target matrix element; and

summing the inverse of each score assigned to each isolated and isolatable target matrix element;

setting the potential gain of isolated target matrix elements above the selected cut to the highest calculated sum;

calculating the potential gain of isolated target matrix elements below the selected cut;

selecting the highest calculated potential gain as the potential gain of isolated target elements for the selected cut; and

isolating means for applying the cut from the set of matrix cuts that results in the maximum potential gain in isolated target matrix elements, wherein applying the cut divides the matrix into homogeneous regions of target and non-target matrix elements.

14. The system of claim 13, wherein the matrix is an image and the matrix elements comprise pixels, further comprising:

replacing means for replacing the homogenous regions of target pixels with HTML table cells.