Determining Median Value of an Array on Vector SIMD Architectures

• US 20150067008A1
• Filed: 08/08/2014
• Published: 03/05/2015
• Est. Priority Date: 09/05/2013
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Kamath, Sanmati S., Pathayapurakkal, Anoop K.
• Granted Patent: US 9,665,542 B2
• Time in Patent Office: Days
• US Class Current: 708/202
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 5/70 Denoising; Smoothing

Abstract

A method for determining a median value of an array of pixels in a vision system may be performed in an efficient manner using the parallel computing capabilities of a SIMD processing engine. Each column of an array may be sorted in ascending (descending) order to form a first sorted array. Each row of the first sorted array may be sorted in ascending (descending) order to form a second sorted array. A pixel may be selected as the median value from a diagonal portion of the second sorted array, wherein the diagonal portion bisects a lower value region and a higher value region of the second sorted array.

Claims

1. A computer implemented method for determining a median value of an array of pixels, the method comprising:

sorting each column of an array in ascending or descending order to form a first sorted array, wherein all of the columns are sorted in a parallel manner by a single instruction, multiple data (SIMD) processor;

sorting each row of the first sorted array in a parallel manner by the SIMD processor in ascending or descending order to form a second sorted array; and

selecting a pixel as the median value from a diagonal portion of the second sorted array, wherein the diagonal portion bisects a lower value region and a higher value region of the second sorted array.

2. The method of claim 1, further comprising sorting the diagonal portion of the second sorted array before selecting the pixel as the median value.

3. The method of claim 1, further comprising transposing the first sorted array to form a transposed array prior to sorting each row of the first sorted array, such that sorting each row of the first sorted array is performed by sorting each column of the transformed array in a parallel manner by the SIMD processor.

4. The method of claim 1, wherein selecting a pixel as the median value selects a pixel in a central position of the second sorted array, whereby an approximate median value is selected.

5. The method of claim 2, wherein the diagonal portion of the second sorted array comprises a low value diagonal, a high value diagonal and a mid value diagonal, wherein sorting the diagonal portion comprises sorting all of the elements in the low value diagonal, the mid value diagonal, and the high value diagonal into a sorted sequence;

and

wherein selecting a pixel as the median value selects a pixel in a central position of the sorted sequence.

6. The method of claim 2, wherein the diagonal portion of the second sorted array comprises a low value diagonal, a high value diagonal, and a mid value diagonal, wherein sorting the diagonal portion comprises:

sorting the mid value diagonal to form a sorted mid value diagonal;

updating an element at a low value end of the sorted mid value diagonal with a maximal value of the low value diagonal and the low value end;

updating an element at a high value end of the sorted mid value diagonal with a minimal value of the high value diagonal and the high value end;

sorting the resulting mid value diagonal to form an updated sorted mid value diagonal; and

wherein selecting a pixel as the median value selects a pixel in a central position of the updated sorted mid value diagonal.

7. The method of claim 6, further comprising sorting the sorted mid value diagonal prior to replacing the element at the high value end of the mid value diagonal.

8. The method of claim 2, wherein the diagonal portion of the second sorted array comprises a low value diagonal, a high value diagonal, and a mid value diagonal, wherein sorting the diagonal portion comprises:

sorting the mid value diagonal to form a sorted mid value diagonal; and

wherein selecting a pixel as the median value selects a pixel in a central position of the updated sorted mid value diagonal, whereby an approximate median value is selected.

9. A non-transitory computer readable medium storing software instructions that, when executed by at least one single instruction, multiple data (SIMD) processor, cause the performance of a method for selecting a median value of an array of data, the method comprising:

sorting each column of an array in ascending or descending order to form a first sorted array, wherein all of the columns are sorted in a parallel manner by the SIMD processor;

sorting each row of the first sorted array in a parallel manner by the SIMD processor in ascending or descending order to form a second sorted array; and

selecting a pixel as the median value from a diagonal portion of the second sorted array, wherein the diagonal portion bisects a lower value region and a higher value region of the second sorted array.

10. The method of claim 9, further comprising sorting the diagonal portion of the second sorted array before selecting the pixel as the median value.

11. The method of claim 9, further comprising transposing the first sorted array to form a transposed array prior to sorting each row of the first sorted array, such that sorting each row of the first sorted array is performed by sorting each column of the transformed array in a parallel manner by the SIMD processor.

12. The method of claim 9, wherein selecting a pixel as the median value selects a pixel in a central position of the second sorted array, whereby an approximate median value is selected.

13. The method of claim 10, wherein the diagonal portion of the second sorted array comprises a low value diagonal, a high value diagonal and a mid value diagonal, wherein sorting the diagonal portion comprises sorting all of the elements in the low value diagonal, the mid value diagonal, and the high value diagonal into a sorted sequence;

and

wherein selecting a pixel as the median value selects a pixel in a central position of the sorted sequence.

14. The method of claim 10, wherein the diagonal portion of the second sorted array comprises a low value diagonal, a high value diagonal, and a mid value diagonal, wherein sorting the diagonal portion comprises:

sorting the mid value diagonal to form a sorted mid value diagonal;

updating an element at a low value end of the sorted mid value diagonal with a maximal value of the low value diagonal and the low value end;

updating an element at a high value end of the sorted mid value diagonal with a minimal value of the high value diagonal and the high value end;

sorting the resulting mid value diagonal to form an updated sorted mid value diagonal; and

wherein selecting a pixel as the median value selects a pixel in a central position of the updated sorted mid value diagonal.

15. The method of claim 14, further comprising sorting the sorted mid value diagonal prior to replacing the element at the high value end of the mid value diagonal.

16. The method of claim 10, wherein the diagonal portion of the second sorted array comprises a low value diagonal, a high value diagonal, and a mid value diagonal, wherein sorting the diagonal portion comprises:

sorting the mid value diagonal to form a sorted mid value diagonal; and

wherein selecting a pixel as the median value selects a pixel in a central position of the updated sorted mid value diagonal, whereby an approximate median value is selected.

17. A computer vision system comprising:

a camera coupled to provide an array of pixel data to a memory array;

a single instruction, multiple data (SIMD) processor coupled to the memory array and to an instruction memory, wherein the SIMD processor is operable to execute instructions stored in the instruction memory to cause the performance of a method for selecting a median value of the array of data, the method comprising;

sorting each column of the array of pixel data in ascending or descending order to form a first sorted array, wherein all of the columns are sorted in a parallel manner by the SIMD processor;

sorting each row of the first sorted array in a parallel manner by the SIMD processor in ascending or descending order to form a second sorted array; and

selecting a pixel as the median value from a diagonal portion of the second sorted array, wherein the diagonal portion bisects a lower value region and a higher value region of the second sorted array.

18. The method of claim 17, further comprising sorting the diagonal portion of the second sorted array before selecting the pixel as the median value.

19. The method of claim 17, further comprising transposing the first sorted array to form a transposed array prior to sorting each row of the first sorted array, such that sorting each row of the first sorted array is performed by sorting each column of the transformed array in a parallel manner by the SIMD processor.

20. The method of claim 17, wherein selecting a pixel as the median value selects a pixel in a central position of the second sorted array, whereby an approximate median value is selected.