Cách tìm int phổ biến nhất trong mảng int 2?

Question

OK, vì vậy tôi chỉ mới bắt đầu nghĩ cách triển khai một plugin đồ họa mới cho Paint.NET và tôi sẽ cần phải biết cách tìm số nguyên phổ biến nhất trong mảng số nguyên 2d. Có một built-in để C# cách để làm điều này? Hoặc, có ai có một cách khéo léo để làm điều đó?

Mảng sẽ giống như thế này:

300 300 300 300 300 300 300 
    0 150 300 300 300 300 300 
    0 0 150 300 300 300 300 
    0 0 0 0 300 300 300 
    0 0 0 0 150 300 300 
    0 0 0 0 0 150 300 
    0 0 0 0 0 0 300 

tôi sẽ cần phải biết rằng 300 là số phổ biến nhất trong mảng. Nếu không có "phổ biến nhất" thì chỉ cần trả lại số trung tâm (các mảng mờ sẽ luôn là số lẻ lẻ) 0.

Tôi sẽ thực hiện điều này bằng thuật toán "brute force" trừ khi các chuyên gia có thể với một cái gì đó nhanh hơn.

Mọi trợ giúp sẽ được đánh giá rất nhiều.

Cảm ơn!

CHỈNH SỬA: Thêm thông tin ...

Giá trị hầu như luôn luôn rất đa dạng (đa dạng hơn mảng mẫu của tôi). Các giá trị sẽ nằm trong khoảng 0-360. Kích thước của mảng sẽ là 5x5 đến khoảng 17x17 tùy thuộc vào tốc độ của thuật toán. Kết quả sẽ được tính một lần cho mỗi pixel trong một hình ảnh lớn ... vì vậy nhanh hơn là tốt hơn. ;)

Answer 1

Hãy xem mã LocalHistogramEffect trong Paint.NET, đặc biệt là LocalHistorgramEffect.RenderRect.

Tôi đi hình ảnh đầu vào, duy trì biểu đồ cường độ cho mỗi pixel nguồn bằng pixel 'r' của pixel đích. Khi các pixel đầu ra được di chuyển ngang, nó sẽ thêm cạnh đầu vào vào biểu đồ và trừ cạnh sau. Nó xử lý tất cả các trường hợp cạnh tốt, và là khá nhanh. Đó là cơ sở cho các hiệu ứng Trung bình, Không tập trung, Phác thảo và Xóa tiếng ồn.

Việc điều chỉnh để hỗ trợ Huế thay vì cường độ RGB sẽ khá nhỏ.

Hiệu suất khá tốt và cho mục đích của bạn hoạt động trong O (r^2 + w r + n w), trong đó r là bán kính, w là chiều rộng của hình ảnh và n là số lượng các cấp trong biểu đồ.

-tjackson

Answer 2

Ít nhất là O (n * m) bất kỳ cách nào bạn cắt nó - bạn sẽ phải xem xét từng ô ít nhất một lần. Nơi để tiết kiệm là nơi bạn tích lũy số lượng của mỗi giá trị trước khi tìm kiếm phổ biến nhất; nếu các số nguyên của bạn thay đổi trên một phạm vi tương đối nhỏ (chúng là uint16, giả sử), thì bạn có thể chỉ đơn giản là sử dụng một mảng phẳng thay vì bản đồ.

Tôi đoán bạn cũng có thể giữ một số chạy x, y của đỉnh hiện tại và thứ hai gần nhất ứng cử viên cho "phổ biến nhất" và đầu ra càng sớm càng tốt đã ít hơn (n * m) - (xy) các tế bào còn lại để xem xét, vì tại thời điểm đó không có cách nào Á hậu có thể vượt qua các ứng cử viên hàng đầu.

Các trình tạo số nguyên như thế này khá nhanh; ngay cả đối với ảnh megapixel, thuật toán brute force chỉ mất vài phần nghìn giây.

Tôi nhận thấy bạn đã chỉnh sửa câu hỏi ban đầu của mình để nói rằng giá trị pixel từ 0,255 - trong trường hợp đó, chắc chắn đi kèm với một mảng phẳng đơn giản; đó là đủ nhỏ để dễ dàng phù hợp với dcache l1 và tra cứu trong một mảng phẳng là trez nhanh chóng.

[sửa]: Đối phó với trường hợp "số không phổ biến nhất" rất đơn giản khi bạn đã tạo mảng biểu đồ: tất cả những gì bạn phải làm là đi qua nó để tìm "nhất" và "giây hầu hết các "số phổ biến; nếu chúng thường xuyên như nhau, thì theo định nghĩa thì không có ai phổ biến nhất.

const int numLevels = 360; // you said each cell contains a number [0..360) 
int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i" 
int mostCommon = 0, runnerUp = 0; 
for (int i = 1 ; i < numLevels ; ++i) 
{ 
    if (levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon]) 
    { 
    runnnerUp = mostCommon; 
    mostCommon = i; 
    } 
} 

if (levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp]) 
{ 
    return mostCommon; 
} 
else 
{ 
    return CenterOfInputData; // (something like InputData[n/2][m/2]) 
} 

Answer 3

thế nào tôi sẽ làm điều gì đó như thế này trong C#?

Something như thế này:

Dictionary<int, int> d = new Dictionary<int, int>(); 
foreach (int value in matrix) 
{ 
if (!d.ContainsKey(value)) 
    d.Add(value, 1); 
else 
    d[value] = d[value] + 1; 
} 
KeyValuePair<int, int> biggest = null; 
foreach (KeyValuePair<int, int> found in d) 
{ 
    if ((biggest == null) || (biggest.Value < found.Value)) 
    biggest = found; 
} 

Answer 4

Một lựa chọn là LINQ - một chút không hiệu quả, nhưng OK cho mảng phi khổng lồ:

var max = (from cell in data.Cast<int>() 
       group cell by cell into grp 
       select new { Key = grp.Key, Count = grp.Count() } into agg 
       orderby agg.Count descending 
       select agg).First(); 
    Console.WriteLine(max.Key + ": " + max.Count); 

Hoặc với một mảng lởm chởm:

var max = (from row in data 
       from cell in row 
       group cell by cell into grp 
       select new {Key = grp.Key, Count = grp.Count()} into agg 
       orderby agg.Count descending 
       select agg).First(); 
    Console.WriteLine(max.Key + ": " + max.Count); 

Thực tế, tôi có thể sử dụng từ điển/số lượng. Ví dụ này không có LINQ, chỉ "vì":

Dictionary<int, int> counts = new Dictionary<int, int>(); 
    foreach (int value in data) 
    { 
     int count; 
     counts.TryGetValue(value, out count); 
     counts[value] = count + 1; 
    } 
    int maxCount = -1, maxValue = 0; 
    foreach (KeyValuePair<int, int> pair in counts) 
    { 
     if (pair.Value > maxCount) 
     { 
      maxCount = pair.Value; 
      maxValue = pair.Key; 
     } 
    } 
    Console.WriteLine(maxCount + ": " + maxValue); 

Answer 5

Nếu tốc độ là mối quan tâm chính của bạn, không sử dụng từ điển. Gắn bó với một mảng các byte. Hãy thử điều này:

// stores hit counts (0-360) 
short[] hitCounts = new short[361]; 

// iterate through 2d array and increment hit counts 
for (int i = 0; i < toEvaluate.Length; i++) 
{ 
    for (int j = 0; j < toEvaluate[i].Length; j++) 
     hitCounts[toEvaluate[i][j]]++; 
} 

int greatestHitCount = 0; // the hit count of the current greatest value 
int greatest = -1; // the current greatest valeu 

// iterate through values (0-360) and evalute hit counts 
for (int i = 0; i < hitCounts.Length; i++) 
{ 
    // the hit count of hitCounts[i] is higher than the current greatest hit count value 
    if (hitCounts[i] > greatestHitCount) 
    { 
     greatestHitCount = vals[i]; // store the new hit count 
     greatest = i; // store the greatest value 
    } 
    // there is already a value with the same hit count (which is the greatest) 
    else if (hitCounts[i] == greatestHitCount) 
     greatest = -1; // there are more than one value, we can't use this if it ends up being the greatest 
} 

if (greatest >= 0) // no greatest value found 
    return greatest; 

// figure out the middle x and y value 
int x = (toEvaluate.Length - 1)/2 + 1; 
int y = (toEvaluate[x].Length - 1)/2 + 1; 

// return the value at the center of the 2d array as the value 
return toEvaluate[x][y]; 

Khi tốc độ trở thành mối lo ngại về khả năng đọc, bạn kết thúc với mã nhất thiết phải xấu. Ở trên chắc chắn có thể hưởng lợi từ tái cấu trúc (do đó overdoing các ý kiến), nhưng nó sẽ chạy nhanh. Nếu nó không đủ nhanh, bạn có thể đạt được tối ưu hơn nữa bằng cách chuyển nó sang mã không được quản lý.

Answer 6

Michael đánh bại tôi đến bưu điện, nhưng anh sẽ làm tương tự như vậy, một cái gì đó như thế này:

 int MaxValueIn2dArray(int[,] matrix) 
    { 
     var d = new int[360]; 
     int MaxValue = 0; 
     for (int x = 0; x <= matrix.GetUpperBound(0); x++) 
     { 
      for (int y = 0; y <= matrix.GetUpperBound(1); y++) 
      { 
       d[matrix[x, y]]++; 
      } 
     } 
     foreach (int value in d) 
     { 
      if (value > MaxValue) MaxValue = value; 
     } 
     return MaxValue; 
    } 

Nó sẽ cần phải được tối ưu hóa cho các nhu cầu cụ thể của bạn.

Answer 7

Hình ảnh của bạn:

300+ 300+ 300+ 300 300 300 300 
    0+ 150+ 300+ 300 300 300 300 
    0+ 0+ 150+ 300 300 300 300 
    0 0 0 0 300 300 300 
    0 0 0 0 150 300 300 
    0 0 0 0 0 150 300 
    0 0 0 0 0 0 300 

đánh dấu (+) con số này là cửa sổ của bạn. w, h là kích thước cửa sổ của bạn. Áp dụng bucket sorting (như những người khác được đề xuất vì phạm vi giá trị của bạn khá hạn chế). Không cắt giảm đánh giá của bạn nửa chừng như Crashworks gợi ý. Đừng ném kết quả của bạn. Đây là bước đầu tiên.

300- 300- 300- 300 300 300 300 
    0. 150. 300. 300 300 300 300 
    0. 0. 150. 300 300 300 300 
    0+ 0+ 0+ 0 300 300 300 
    0 0 0 0 150 300 300 
    0 0 0 0 0 150 300 
    0 0 0 0 0 0 300 

Chuyển cửa sổ của bạn. Thay vì thêm, hãy trừ các nhóm ở hàng/cột cuối cùng bạn đã chuyển và thêm các nhóm mới. Bằng cách này, bạn kiểm tra từng pixel 2 (w + h) lần, tức là khi nó vượt qua ranh giới cửa sổ, thay vì w * h lần, tức là trong khi pixel đó nằm trong cửa sổ, trong một triển khai ngây thơ.

Nói cách khác, bạn cần phải di chuyển cửa sổ của bạn như thế này:

| ^->|^
| | | | 
| | | | 
V->| V->| 

tôi giả sử bạn đang cố gắng để thực hiện một bộ lọc chập phi tuyến.

Sửa chữa được hoan nghênh.

Answer 8

Tất cả tôi sẽ cung cấp cho bất kỳ thuật toán để kiểm tra tất cả các tế bào (đó là khá nhiều những gì bạn mong muốn để làm) làm hai việc thêm:

1.) Hãy chắc chắn rằng các lối ra thường xuyên khi đếm cho giá trị hiện tại phổ biến nhất> (M x N/2). Nếu một cái gì đó có> 50% bảo hiểm trên lưới của bạn thì đó là giá trị phổ biến nhất, không cần phải tiếp tục. Nếu thói quen của bạn chỉ cần phải là đúng NHẤT của thời gian thì bạn có thể giảm tỷ lệ phần trăm và coi nó như là một heuristic. Bạn thậm chí có thể chạy một số phân tích mà phun ra một cái gì đó giống như nếu bảo hiểm là> 37,6% sau đó 99,9% thời gian nó sẽ là giá trị phổ biến nhất và sau đó sử dụng tỷ lệ phần trăm đó.

2.) Nếu có bất kỳ cách nào bạn có thể xác định vị trí bên, góc hoặc vị trí chung (cạnh ngoài, giữa, v.v.), các giá trị phổ biến nhất có thể là, sau đó bạn có thể quét theo thứ tự đó với tối ưu hóa 1 ở trên có thể cạo rất nhiều việc quét của bạn. Ví dụ trong ví dụ của bạn trên cùng bên phải là nặng trên giá trị chung. Nếu điều này được xác định bởi một số heuristic bạn có thể quét từ phía trên bên phải để phía dưới bên trái trong một số thời trang. Nếu mẫu quét cần thiết là phức tạp, hãy tạo trước.