System and method for signal processing using sorting based filtering

Abstract

Embodiments may include receiving an input block of data having one or more rows wherein each row includes one or more elements. Embodiments may further include adjusting the input block of data to generate a two-dimensional sorted block of data and identifying at least one position within the two-dimensional sorted block of data that cannot contain a median value or a desired Nth sorted value. Embodiments may also include sorting the two-dimensional block of data along one or more columns to obtain one or more candidate elements that contain the median value or the desired Nth sorted value. Embodiments may include discarding at least one non-candidate element to generate one or more remaining elements and rearranging the one or more remaining elements such that a number of diagonal elements form a column. Embodiments may also include iteratively repeating some of the above operations until a desired value is identified.

What is claimed is: 
     
       1. A computer-implemented method for use in signal processing comprising:
 receiving, using at least one processor, a one or two-dimensional input block of data having one or more sorted or unsorted rows wherein each row includes one or more elements; 
 adjusting the input block of data to generate a two-dimensional sorted block of data, wherein the two-dimensional sorted block of data is an orthogonal-direction sorting invariant structure; 
 identifying at least one position within the two-dimensional sorted block of data that cannot contain a median value or a desired Nth sorted value; 
 sorting the two-dimensional block of data along one or more columns to obtain one or more candidate elements that contain the median value or the desired Nth sorted value, wherein after sorting the two-dimensional block of data along one or more columns is performed, row sorting is preserved; 
 discarding at least one non-candidate element to generate one or more remaining elements; 
 rearranging the one or more remaining elements such that a number of diagonal elements form a column; and 
 iteratively repeating one or more of the adjusting, identifying, sorting, discarding, and rearranging operations until a desired value of the input block of data is identified. 
 
     
     
       2. The computer-implemented method of  claim 1 , wherein identifying includes identifying at least one element located at a corner of the two-dimensional input block of data. 
     
     
       3. The computer-implemented method of  claim 1 , wherein the two-dimensional input block of data is an M×N block of data, where M, N are greater than or equal 1. 
     
     
       4. The computer-implemented method of  claim 3 , wherein the desired value is a median value. 
     
     
       5. The computer-implemented method of  claim 3 , wherein the desired value is an Nth minimum value. 
     
     
       6. The computer-implemented method of  claim 3 , wherein the desired value is an Nth maximum value. 
     
     
       7. The computer-implemented method of  claim 3 , wherein the desired value is a plurality of values. 
     
     
       8. The computer-implemented method of  claim 1 , wherein two-dimensional input block of data is sorted along columns and iteratively repeating includes sorting along one or more rows. 
     
     
       9. The computer-implemented method of  claim 8 , wherein iteratively repeating the sorting along one or more rows is performed partially. 
     
     
       10. The computer-implemented method of  claim 9 , wherein iteratively repeating the sorting along one or more rows is performed partially to identify at least one value to be discarded. 
     
     
       11. A system for use in signal processing comprising:
 a computing device having at least one processor configured to receive, using at least one processor, a one or two-dimensional input block of data having one or more sorted or unsorted rows wherein each row includes one or more elements, the at least one processor configured to adjust the input block of data to generate a two-dimensional sorted block of data, wherein the two-dimensional sorted block of data is an orthogonal-direction sorting invariant structure, and to identify at least one position within the two-dimensional sorted block of data that cannot contain a median value or a desired Nth sorted value, the at least one processor further configured to sort the two-dimensional block of data along one or more columns to obtain one or more candidate elements that contain the median value or the desired Nth sorted value, wherein after sorting the two-dimensional block of data along one or more columns is performed, row sorting is preserved, the at least one processor configured to discard at least one non-candidate element to generate one or more remaining elements and to rearrange the one or more remaining elements such that a number of diagonal elements form a column, the at least one processor further configured to iteratively repeat one or more of the adjusting, identifying, sorting, discarding, and rearranging operations until a desired value of the input block of data is identified. 
 
     
     
       12. The system of  claim 11 , wherein identifying includes identifying at least one element located at a corner of the two-dimensional input block of data. 
     
     
       13. The system of  claim 11 , wherein the two-dimensional input block of data is an M×N block of data, where M, N are greater than or equal 1 and the structure may have gap or missing regions in it. 
     
     
       14. The system of  claim 13 , wherein the desired value is a median value. 
     
     
       15. The system of  claim 13 , wherein the desired value is an Nth minimum value. 
     
     
       16. The system of  claim 13 , wherein the desired value is an Nth maximum value. 
     
     
       17. The system of  claim 13 , wherein the desired value is a plurality of values. 
     
     
       18. The system of  claim 11 , wherein two-dimensional input block of data is sorted along columns and iteratively repeating includes sorting along one or more rows. 
     
     
       19. The system of  claim 18 , wherein iteratively repeating the sorting along one or more rows is performed partially. 
     
     
       20. The system of  claim 19 , wherein iteratively repeating the sorting along one or more rows is performed partially to identify at least one value to be discarded.