C++ - Dizide lokal maksimum/minimum değerlerinin bulunması

Bu yazı kapsamında bir dizi içerisindeki değerlerin lokal maksimum/minimum noktalarını bulan algoritmayı açıklayıp, C++ ile implementasyonunu gerçekleştireceğiz. OpenCV ile hareket tespiti, takibi ve yapılan hareketin tanınmasına yönelik hobi amaçlı gerçekleştirdiğim bir proje dahilinde böyle bir ihtiyaç ortaya çıktı ve ben de projenin bu kısmını paylaşmak istedim. Örneğin şöyle bir dizimiz olduğunu farzedelim ve bu dizinin değerlerini grafik üzerinde gösterelim.

data = [3 8 15 5 6 10 10 3 1 20 7];

Bu dizideki lokal maksimum değerler: 15, 10 ve 20 değerleridir, diyebiliriz. Aslında lokal maksimum ya da lokal minimum noktalarını tepe noktası olarak da isimlendirebiliriz. Tepe noktasını tanımlayacak olursak, dizideki değerlerin artıştan azalışa veyahut da azalıştan artışa geçtiği noktalardır. 

 Yukarıdaki örnek veri için tepe noktaları 15,10 ve 20'dir dedim. Fakat burada aslında görece bir durum söz konusu. Yani sadece 15 veya 20 değerleri de bizim için tepe noktaları olabilirdi. Demek ki bu noktada algoritmamıza bir threshold değeri belirtmemiz faydalı olacaktır. threshold değeri ile bulmak istediğimiz tepelerin yüksekliklerini belirleyeceğiz. Tepe noktalarını bulacak algoritmamızı yazılı olarak özetledikten sonra ilgili işi yapan kod parçacığını/fonksiyonu aşağıda bulabilirsiniz. 

İlk olarak dizi üzerinde dolaşıp maksimum ve minimum değerleri bulacağız ve bunları sürekli güncelleyeceğiz. Yani iterasyon dahilinde yeni alınan değer maksimum değerden büyükse bu değer maksimum olarak atanacaktır (minimum için de hakeza tam tersi). Şunu da belirtelim ilk olarak bir lokal maksimum değer arıyoruz, yani ilk lokal maksimum noktamızı bulmadan lokal minimum değer bulmayacağız. Peki bir noktanın lokal maksimum olduğuna nasıl karar vereceğiz? Eğer iterasyon dahilinde üzerinde bulunulan değer, bulunan maksimum değerden en az threshold değeri kadar küçükse bu nokta bir lokal maksimumdur. Bu durumu aşağıda grafik üzerinden gösterirsek daha anlaşılır olacaktır.

Dolayısıyla bulunmuş bu maksimum nokta, lokal bir maksimumdur. Bu durumun tersi de yine lokal minimum değerler için geçerli olacaktır. Bu algoritmada son derece önemli bir nokta ise şu:  lokal minimum nokta bulduktan sonra, lokal minimum değeri bulduğumuz nokta (data[i]) ( yani bulunmuş minimum değere göre threshold değerinden daha büyük bir artışın olduğu nokta) daki değeri, yeni maksimum nokta ve değeri olarak güncelliyoruz. Bunu yapmamızın sebebi, büyük bir lokal maksimum nokta bulduktan sonra, daha küçük olan lokal maksimum noktaları kaçırmak istemememiz. Bu durumun da tam tersi yine lokal minimumlar için geçerli. Algoritmamızın bu kısa sözlü açıklamasının ışığında fonksiyonu inceleyebilirsiniz.

#include<map>
#include<vector>
#include<iostream>

using namespace std;


struct peak
{
 unsigned int index;
 int value;

 peak()
 {

 }

 peak(int ind,int val)
 {
  index = ind;
  value = val;
 }
};

map<int, peak> local_peaks(vector<int> vec, int thresh)
{
 size_t length = vec.size();
 int max = 0, min = 100000;
 int maxloc = -1, minloc = -1;
 bool lookformax = true;

 map<int,peak> max_peaks;
 map<int,peak> min_peaks;

 for (size_t i = 0; i < length; i++)
 {

  int current = vec[i];  

  if (current > max)
  {
   max = current;
   maxloc = i;
  }
  if (current < min)
  {
   min = current;
   minloc = i;
  }


  if (lookformax)
  {
   if (current < (max - thresh))
   {
    std::cout << "local max: " << max << std::endl;
    max_peaks[maxloc] = peak(maxloc, max);
    min = current;
    minloc = i;
    lookformax = false;
   }
  }
  else
  {
   if (current > (min + thresh))
   {
    std::cout << "local min: " << min << std::endl;
    min_peaks[minloc] = peak(minloc, min);
    max = current;
    maxloc = i;
    lookformax = true;
   }
  }

 }


 return max_peaks;
}

int main(int argc, const char * argv[]) {
 // insert code here...

 vector<int> vec = { 3,4,8,9,22,20,19,18,17,13,14,15,16,17,18,20,25,28,32,35,30,21,20,10,5,2,4,6,7,8,9,28,3,5,2,0 };

 //vec = { 3,8,15,5,6,10,10,3,1,20,7 };

 auto elem = local_peaks(vec,5);


 return 0;
}

 threshold = 5 için

 threshold = 10 için

Her türlü görüş, öneri ve sorularınızı iletebilirsiniz...