[Java] Extraction min/max locaux dans un histogramme

Voici un petit bout de code pour extraire les min/max locaux d'une série de valeur. C'est un problème récurent dans l'analyse des histogrammes.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Local Extrema extraction
 *
 * @author by X.Philippeau
 * @param values the array of values
 * @return an array of local heights
 */
public static int[] localHeight(int[] values) {
	int[] height = new int[values.length];
 
	// pass 1: left to right
	int up=0,down=0;
	for(int i=1;i<=values.length-2;i++) {
		int delta = values[i]-values[i-1];
		if (delta>0) {down=0;up+=delta;}
		if (delta<0) {up=0;down+=delta;}
		height[i]=(up>-down)?up:down;
	}
 
	// pass 2: right to left
	up=0;down=0;
	for(int i=values.length-2;i>=0;i--) {
		int delta = values[i]-values[i+1];
		if (delta>0) {down=0;up+=delta;}
		if (delta<0) {up=0;down+=delta;}
		if (up<height[i]) height[i]=up;
		if (down>height[i]) height[i]=down;
	}	
 
	return height;
}

Cette méthode prend en paramètre le tableau d'entier des valeurs à analyser. Elle retourne un tableau d'entier de la meme taille que celui passé en parametre. Ce nouveau tableau contient l'altitude locale du pic (min/max).

altitude>0 -> le pic est un maximum
altitude<0 -> le pic est un minimum
altitude=0 -> il n'y a pas de pic a cet emplacement

Exemple:

Code:

1
2
3
4
 
Valeurs: 128  129  127  125  127  131  129  125  123  124  126  133  137  138  137  132  124  119  116  117  120  127  138  144  148  149  145  140  131  120  112  106  103  103  107  112  121  133  141  148  154  159  161  160  158  151  142  127  115  104  
 
Retour:   0    01   0   -04   0    06   0    0   -08   0    0    0    0    15   0    0    0    0   -22   0    0    0    0    0    0    33   0    0    0    0    0    0   -46  -46   0    0    0    0    0    0    0    0    57   0    0    0    0    0    0    0

La 14éme valeur du tableau (=138) est un maxima local d'altitude 15.