ime_detect_IMEs.m

function varargout=ime_detect_IMEs(Chl,islands)


%% IME_DETECT_IMES: detects the Island Mass Effect (IME) associated with each island, from a map of satellite Chl concentration.
% Reference: Messié, M., A. Petrenko, A. Doglioli, E. Martinez, and S. Alvain (2022). 
%	Basin-scale biogeochemical and ecological impacts of islands in the tropical Pacific Ocean. Nature Geoscience, submitted.
%
% islands=ime_detect_IMEs(Chl,islands);
% [islands,Chl]=ime_detect_IMEs(Chl,islands);
% 
%% Inputs:
% 	Chl:		structure containing .lon (vector), .lat (vector), .chl (as a 2D matrix, dimension 1 = lat and dimension 2 = lon),
%						.mask_cont (mask containing continent pixels), 
%						.mask_30m (mask containing pixels shallower than 30 m, considered as land except to calculate area_IME),
%						.area (pixel area in km²)
% 	islands:	structure containing (everything as vector of length the number of pixels):
%						.lon, .lat, .Iname (island names, cell), .is_NunnDB (true if belonging to the Nunn et al. database).
%						.Iarea (island area, km²), .Rarea (area shallower than 30 m including land, km²),
% 				(Note - .Iarea, .Rarea, and .is_NunnDB are exclusively used to choose which island is kept within groups of Chl NaN pixels, 
%				see ime_combine_islands)
% 
%% Outputs: the same Chl and islands structures with additional fields.
%	islands:	.cChl			IME Chl contour
%				.Chl_max		nearby max Chl (within 1 pixel of island mask)
%				.Chl_min		nearby min Chl (within 1 pixel of island mask)
%				.Chl_REF		Chl averaged within REF mask
%				.Chl_IME		Chl averaged within IME mask
%				.area_IME		IME area (km²)
%				.has_IME		1 if IME, 0 if not, NaN if undetermined (too many gaps near the island, does not happen on a climatology)
%				.keep_IME		NaN if no IME or merged IME, 0 if too many gaps within IME region (does not happen on a climatology), 1 otherwise
%				.mask_IME		cell containing the IME mask for each island (same size as Chl.chl)
%				.mask_REF		idem for REF masks
%				.reason_stop	reason why the IME iteration stopped
%				.islandIME		name of the island where the IME originated (lead island - island with highest Chl_max within the IME region)
% 	Chl:	.mask_IME_all: all IME regions
%			.mask_REF_all: corresponding reference regions
%		Note that these masks are simplified by removing holes so that there might be pixels > cChl within mask_REF, 
%			and pixels < cChl within mask_IME.
%
% Monique Messié, 2021 for public version


% parameters
arg.dChl=0.01;						% step used to lower cChl in the first iteration (in mg/m3)
arg.rankratio=0.8;					% threshold for local maxima (Chl above 80% of Chl_mask)
arg.ranklim=0.02;					% minimum threshold for local maxima (local maxima within 0.02 mg/m3 of cChl are always considered to be OK)
arg.pixels_tolerance=32;			% local maxima within pixels_tolerance are considered to be generated by an IME, and merged (~ 150 km)
arg.pixels_tolerance_clouds=10;		% missing data within 10 pixels of the island are OK, beyond this IMEs are considered unknown (~ 46 km) (not an issue for climatological maps)

% check the image toolbox is available on the current license
if ~license('checkout','image_toolbox'), error('!!!! Image processing toolbox necessary'), end

% input & prepare outputs: Chl
[Chl.lon2D,Chl.lat2D]=meshgrid(Chl.lon,Chl.lat);
[Chl.nb_lat,Chl.nb_lon]=size(Chl.lon2D);
Chl.mask_IME_all=false(Chl.nb_lat,Chl.nb_lon);
Chl.mask_REF_all=false(Chl.nb_lat,Chl.nb_lon);

% input & prepare outputs: islands
% Note - using cells instead of matrix for mask_IME and mask_REF to save space (can be kept empty when no IME is detected)
islands.nb_pts=length(islands.lon);
for varname={'cChl','Chl_max','Chl_min','Chl_REF','Chl_IME','area_IME','keep_IME'}, varname=varname{:};
	islands.(varname)=nan(islands.nb_pts,1); 
end
islands.has_IME=zeros(islands.nb_pts,1);
for varname={'mask_IME','mask_REF'}, varname=varname{:}; islands.(varname)=cell(islands.nb_pts,1); end
islands.reason_stop=cell(islands.nb_pts,1); 
islands.islandIME=repmat({''},islands.nb_pts,1); 

% get pixel indices in the Chl grid for each island
ilon_islands=nan(size(islands.lon)); ilat_islands=nan(size(islands.lat));
for iisland=1:length(islands.lon)
	dist_lon=abs(Chl.lon-islands.lon(iisland));
	dist_lat=abs(Chl.lat-islands.lat(iisland));
	ilon_islands(iisland)=find(dist_lon==min(dist_lon),1);
	ilat_islands(iisland)=find(dist_lat==min(dist_lat),1);
end


%% Finding which islands to investigate (these steps are mostly unnecessary on climatological maps with few gaps when using the curated island database)
%   first combine islands within the current mask of NaNs (w/ gaps)
mask_combine=struct('lon',Chl.lon,'lat',Chl.lat,'mask',~isnan(Chl.chl));
[~,ikeep]=ime_combine_islands(islands,mask_combine); 
% 	then keep only islands within the Chl domain
is_inChlDomain = islands.lon>=min(Chl.lon2D(:)) & islands.lon<=max(Chl.lon2D(:)) & islands.lat>=min(Chl.lat2D(:)) & islands.lat<=max(Chl.lat2D(:));
% 	then remove islands within the extended continent mask (continent + adjacent NaNs)
[ilat_cont,ilon_cont]=find(Chl.mask_cont);
mask_extended_continents = bwselect(isnan(Chl.chl),ilon_cont,ilat_cont,8);
is_inExtendedContinent=false(islands.nb_pts,1);
for ii=1:islands.nb_pts, is_inExtendedContinent(ii)=mask_extended_continents(ilat_islands(ii),ilon_islands(ii)); end
% 	combine the 3 steps: keep islands not combined, within the Chl domain and not within extended continents
ikeep = ikeep & is_inChlDomain & ~is_inExtendedContinent;
islands.reason_stop(~is_inChlDomain)=repmat({'not in Chl domain'},1,sum(~is_inChlDomain));
islands.reason_stop(is_inExtendedContinent)=repmat({'in extended continent mask'},1,sum(is_inExtendedContinent));
icombined = ~ikeep & is_inChlDomain & ~is_inExtendedContinent;
islands.reason_stop(icombined)=repmat({'combined within NaN pixels'},1,sum(icombined));
ikeep = find(ikeep);

% masks
mask_all_islandscont=Chl.mask_cont | Chl.mask_30m;													% all islands and continents, ie regular mask
mask_all_NaNpatches_wIslands = bwselect(isnan(Chl.chl),ilon_islands(ikeep),ilat_islands(ikeep),8); 	% all NaN patches containing an island (regular mask + no data)
mask_all_islands = bwselect(Chl.mask_30m,ilon_islands(ikeep),ilat_islands(ikeep),8);				% islands mask (keeping only islands studied)
distance_all_islands = bwdist(mask_all_islands); 													% distance to an island NaN patch (in pixels)

% update mask_cont to include NaN pixels next to it (used for detection of mask_IME touching a continent)
[ilat,ilon]=ind2sub([Chl.nb_lat,Chl.nb_lon],find(Chl.mask_cont));
mask_cont=bwselect(isnan(Chl.chl),ilon,ilat,8);

% mask of "lead island" numbers, where each IME pixel is associated with one island responsible for the IME
no_islandIME_all=nan(Chl.nb_lat,Chl.nb_lon);		% gives the island number of the IME detected at a given pixel, used to fill islands.islandIME

% distance (in km) between 2 points [lon,lat] (in °) using the Spherical Law of Cosines (http://www.movable-type.co.uk/scripts/latlong.html)
Re = 6371008.8;		% mean earth radius, in m
lonlat2km = @(point1,point2) acos( sin(point1(2)/180*pi)*sin(point2(2)/180*pi) + cos(point1(2)/180*pi)*cos(point2(2)/180*pi) * cos(point2(1)/180*pi-point1(1)/180*pi) ) * Re/1E3;



%% --------------------------------------------------------------------------------------------------------------------------------------------------------- %%
%% 										loop first on all islands to get Chl_min, Chl_max and sort islands													 %%
%% --------------------------------------------------------------------------------------------------------------------------------------------------------- %%

disp(' '), disp('Sorting islands based on Chl_min: looping through islands...')

for iisland=ikeep'

	% mask_island for this specific island (subset of mask_all_NaNpatches_wIslands), connection via corners ok
	mask_island = bwselect(isnan(Chl.chl),ilon_islands(iisland),ilat_islands(iisland),8); 				% current NaN patch including clouds
	mask_island_mask = bwselect(mask_all_islandscont,ilon_islands(iisland),ilat_islands(iisland),8);	% theoretical NaN patch (no clouds)
	nb_ext=2*arg.pixels_tolerance_clouds+1;
	mask_island(~imdilate(mask_island_mask,ones(nb_ext,nb_ext)))=false;	% removing parts of mask_island that are more than 10 pixels away from mask_island_mask
	if max(mask_island(:))==0, disp(iisland)
		error('to check - island is not within a Chl NaN patch??? check that areas shallower than 30m were set to NaN for Chl')
	end
	mask_island_borderChl = imdilate(mask_island,ones(3,3)) & ~mask_island;
	mask_island_borderChl(isnan(Chl.chl))=false;	% can happen if mask_island had exceeded the cloud tolerance
	islands.Chl_min(iisland)=min(Chl.chl(mask_island_borderChl));
	islands.Chl_max(iisland)=max(Chl.chl(mask_island_borderChl));

end

% Sort island by lowest Chl_min, then largest reef area, then largest island area
[~,ikeepsort]=sortrows([islands.Chl_min(ikeep),-islands.Rarea(ikeep),-islands.Iarea(ikeep)]);
ikeep=ikeep(ikeepsort); 


%% --------------------------------------------------------------------------------------------------------------------------------------------------------- %%
%% 																loop on all islands																			 %%
%% --------------------------------------------------------------------------------------------------------------------------------------------------------- %%


disp(' '), disp('Detecting IME: looping through islands...')

for iisland=ikeep', disp(' '), disp(['island n°',num2str(iisland),' (',num2str(find(iisland==ikeep)),'th)'])

	reason_stop='';
	mask_island = bwselect(isnan(Chl.chl),ilon_islands(iisland),ilat_islands(iisland),8);

	% ----------- check if the IME has already been detected by another island, and get which island it is
	no_islandIME=no_islandIME_all(ilat_islands(iisland),ilon_islands(iisland));
	
if isnan(islands.Chl_min(iisland)), disp(['Skipping island ',num2str(iisland),' - too many gaps nearby']), reason_stop='too cloudy';
	islands.has_IME(iisland)=NaN; 

elseif ~isnan(no_islandIME), disp(['Skipping island ',num2str(iisland),' - already done']), reason_stop='already done';
	islands.islandIME(iisland)=islands.Iname(no_islandIME); islands.has_IME(iisland)=1; 

else


	%% -------------------------------------------------------------------------------------------- %%
	%% 		step 1: starting from Chl_max, decrease cChl until finding the correct Chl contour 		%%
	%% -------------------------------------------------------------------------------------------- %%


	% start with Chl_max, then decrease as much as possible
	tostop=false; iteration=1; dChl=arg.dChl;
	Chl_max = islands.Chl_max(iisland);
	Chl_min = islands.Chl_min(iisland);	
	cChl_current=floor(Chl_max/dChl)*dChl; 
	mask_IME_prev=mask_island;


%----------- decrease cChl
	while ~tostop

		disp(['cChl_current=',num2str(cChl_current,3)])

		% ---------- step 1a: find mask_IME

		if cChl_current<Chl_min		% rationale: IME supposed to be displaced by currents to one side of the island		
			tostop=true; disp('cChl < Chl_min'), reason_stop='cChl less than cChl min'; mask_IME=false(Chl.nb_lat,Chl.nb_lon);

		else

			% get mask_IME as patch higher than cChl including the island; has to include islands; not connecting by corners.
			mask_IME = bwselect(mask_all_NaNpatches_wIslands | Chl.chl>=cChl_current,ilon_islands(iisland),ilat_islands(iisland),4);

			% simplify the mask by removing potential holes inside
			mask_IME=imfill(mask_IME,'holes');

		end		% if ~cChl_current<Chl_min
		

		% ---------- step 1b: check if contour is too low (intersecting continent or exiting the region)

		if max(mask_IME(1,:)) || max(mask_IME(end,:)) || max(mask_IME(:,1)) || max(mask_IME(:,end))
			tostop=true; disp('contour exits grid domain'), reason_stop='too wide (exits grid domain)';
		elseif max(mask_cont(imdilate(mask_IME,ones(3,3))))		% (imdilate needed b/c of issues with Papua New Guinea otherwise)
			tostop=true; disp('touching a continent'), reason_stop='touching continent';
		end
		if tostop, mask_IME=false(Chl.nb_lat,Chl.nb_lon); end		% no need to look for patches


		% ---------- step 1c: find patches above (Chl_max-cChl_current)*arg.rankratio and check whether they get merged or we stop.

		% Note: if rankratio==1, we are looking for patches above Chl_max.
		rank_threshold=max(arg.ranklim,(Chl_max-cChl_current)*arg.rankratio);									% threshold for patches.
		objects_patchHighChl = bwconncomp(mask_IME & ~mask_IME_prev & Chl.chl>=cChl_current+rank_threshold,8);	% all separate high patches (connected by corners ok)
		nPatches=objects_patchHighChl.NumObjects; 
		objects_patchHighChl=objects_patchHighChl.PixelIdxList;
		if nPatches>0, disp(['found ',num2str(nPatches),' patches with rank >= ',num2str(arg.ranklim),' or rank ratio']), end
		ipatch=1;
		while ipatch<=nPatches && ~tostop		%  test if the local maximum is another island effect
			mask_HighChl_current=false(Chl.nb_lat,Chl.nb_lon); mask_HighChl_current(objects_patchHighChl{ipatch})=true; 	% mask current patch
			distance_max=min(distance_all_islands(mask_HighChl_current & Chl.chl==max(Chl.chl(mask_HighChl_current)))); 	% distance between the local max and any island mask, in pixels
			if distance_max<=arg.pixels_tolerance, disp('   local max close to island mask, combining'), ipatch=ipatch+1; 	% include new IME and recalculate Chl_max
				Chl_max_new=max(Chl.chl(mask_HighChl_current & distance_all_islands==1)); 
				if ~isempty(Chl_max_new), Chl_max=max(Chl_max,Chl_max_new); end
			else, tostop=true; disp('   local max too far from islands and hitting rank ratio'), reason_stop='hitting rank ratio'; 
			end
		end


		% ---------- step 1d: finalization

		if tostop		% the previous contour was the correct IME contour

			% get back to the previous contour and previous masks
			cChl_current=round((cChl_current+dChl)/dChl)*dChl;
			mask_IME=mask_IME_prev;

			% start 2nd iteration if needed, or stop
			if iteration==1
				tostop=false; iteration=2; disp('Iteration 2 with higher resolution dChl')
				dChl=dChl/10; 											% increase resolution
				cChl_current=round((cChl_current-dChl)/dChl)*dChl;		% since the previous contour was already done, starting with the next one at high resolution
			elseif cChl_current>Chl_max, disp('IME not detected at Chl_max-dChl'), reason_stop=[reason_stop,' at the 1st contour'];
			else, disp(['Keeping previous cChl = ',num2str(cChl_current,3)])
			end

		else

			cChl_current=round((cChl_current-dChl)/dChl)*dChl;	% take the next contour (round to deal with a precision issue)
			mask_IME_prev=mask_IME; 							% save previous mask_IME

		end


	end 	% cChl iteration
%----------- 


	%% -------------------------------------------------------------------------------------------- %%
	%% 		step 2: fill in the database information based on cChl_current (and check if IME kept) 	%%
	%% -------------------------------------------------------------------------------------------- %%


	if sum(mask_IME(:) & ~isnan(Chl.chl(:)))>1, disp('IME detected')		% considering that 1 pixel is not enough - we want at least 2

		% giving stats for current IME
		Chl_IME=mean(Chl.chl(mask_IME & ~isnan(Chl.chl)));
		disp(['   cChl max = ',num2str(Chl_max,3)])
		disp(['   cChl min = ',num2str(Chl_min,3)])
		disp(['   cChl contour = ',num2str(cChl_current,3)])
		disp(['   mean Chl IME = ',num2str(Chl_IME,3)])

		% save data into outputs
		islands.mask_IME{iisland}=mask_IME;
		islands.area_IME(iisland)=sum(Chl.area(mask_IME & ~mask_all_islandscont));
		islands.cChl(iisland)=cChl_current;
		islands.Chl_IME(iisland)=Chl_IME;
		islands.islandIME(iisland)=islands.Iname(iisland);
		islands.has_IME(iisland)=1; 

		% keep_IME: 0 if more than 60% gaps in chl (unlikely at the seasonal scale), otherwise 1
		islands.keep_IME(iisland)=1; 
		mask_IME_woisland=mask_IME & ~mask_all_islands;
		if sum(isnan(Chl.chl(mask_IME_woisland(:))))/sum(mask_IME_woisland(:))>=0.6
			islands.keep_IME(iisland)=0; disp('Too many gaps, not kept'), reason_stop=[reason_stop,' but not kept (too many gaps)']; % not happening at the seasonal scale
		end

		% Update mask_IME_all and no_islandIME_all (Note: if IME is not kept, mask_IME_all is not updated but no_islandIME_all always is to avoid duplicating IMEs)
		if islands.keep_IME(iisland), Chl.mask_IME_all(mask_IME)=true; end
		% Before updating no_islandIME_all, need to merge all IMEs potentially belonging to the new IME by updating the "lead island" name
		liste_iisland_toupdate=sort(no_islandIME_all(mask_IME));	% get the list of all "lead islands" that generated an IME previously detected within the current IME
		liste_iisland_toupdate=liste_iisland_toupdate(~isnan(liste_iisland_toupdate));
		iisland_update=ismember(islands.islandIME,islands.Iname(liste_iisland_toupdate)); 	% find all islands belonging to each "lead island" IME
		islands.islandIME(iisland_update)=repmat(islands.Iname(iisland),1,sum(iisland_update));	% update all islands associated with the current IME to the new lead island name
		no_islandIME_all(mask_IME)=iisland; 	% update the mask of lead island numbers

	else, disp('no IME')
	end

end		% stopped early if too many gaps or already done

islands.reason_stop{iisland}=reason_stop;

end		% loop on islands


% ------------------------------------------------------------------------------------------------------------------------- %
% 	step 2bis: update the database information by correcting the lead island, finding the highest IME within merged IMEs 	%
% ------------------------------------------------------------------------------------------------------------------------- %
% (this mostly impacts the mask_REF associated with each IME since it will be centered on the lead island)

liste_merged_IMEs=unique(islands.islandIME(islands.has_IME==1));
for imerged=1:length(liste_merged_IMEs)
	Iname_lead_previous=liste_merged_IMEs(imerged);											% name of the lead iland that will be updated
	iisland = ismember(islands.islandIME,Iname_lead_previous);								% all islands belonging to the merged IME
	iisland_lead_previous = find(ismember(islands.Iname,Iname_lead_previous));				% island where the IME originated from before merging
	iisland_lead_new = find(iisland & islands.Chl_max==max(islands.Chl_max(iisland)),1);	% island with highest Chl_max within merged islands, becoming the new "lead island"
	iisland=find(iisland);
	iisland_wo_new = iisland(iisland~=iisland_lead_new);									% all islands belonging to the merged IME except the new lead island
	islands.islandIME(iisland)=repmat(islands.Iname(iisland_lead_new),1,length(iisland));	% replace islandIME within the merged IME with the new lead island name
	for varname={'mask_IME','keep_IME','area_IME','cChl','Chl_IME'}; varname=varname{:};
		islands.(varname)(iisland_lead_new)=islands.(varname)(iisland_lead_previous);		% update all the IME characteristics by moving them to the new "lead island"
		if strcmp(varname,'mask_IME'), islands.(varname)(iisland_wo_new)={[]};				% only the lead island keeps the IME attributes
		else, islands.(varname)(iisland_wo_new)=NaN;
		end 
	end
end



%% --------------------------------------------------------------------------------------------------------------------------------------------------------- %%
%% 												step 3: once all IMEs detected, get reference region														 %%
%% --------------------------------------------------------------------------------------------------------------------------------------------------------- %%

disp(' ')
disp('---------------------------------')
disp('Getting reference masks')
for iisland=ikeep',  disp(['island n°',num2str(iisland),' (',num2str(find(iisland==ikeep)),'th)'])

	% get mask_island and mask_IME
	mask_island = bwselect(isnan(Chl.chl),ilon_islands(iisland),ilat_islands(iisland),8);
	if isnan(islands.keep_IME(iisland)) && islands.has_IME(iisland)==1		% merged IME
		iisland_IME = find(strcmp(islands.islandIME{iisland},islands.Iname));
	else, iisland_IME=iisland; 
	end
	mask_IME = islands.mask_IME{iisland_IME};
	if isempty(mask_IME), mask_IME=false(size(mask_island)); end

	% Get the reference pixels from a 2000km-radius circle around island and compute mask_distance = distance to center of island within that circle
	% This speeds up the code by restricting the region where pixels are sorted according to distance to the island mask (see below)
	mask_distance=ones(Chl.nb_lat,Chl.nb_lon); 
	radius=2000;		% circle radius, in km (used to limit the region over which the distance to the island center is computed)
	mask_distance(abs(Chl.lat2D-islands.lat(iisland))>radius/100 | abs(Chl.lon2D-islands.lon(iisland))>radius/100)=NaN;
	for icircle=find(mask_distance==1)'
		mask_distance(icircle)=lonlat2km([Chl.lon2D(icircle),Chl.lat2D(icircle)],[islands.lon(iisland),islands.lat(iisland)]);
	end
	mask_large_circle=mask_distance<=radius; 

	% sorting mask_large_circle pixels by distance to the island mask (in pixels).
	mask_distpixels=bwdist(mask_island);
	if islands.has_IME(iisland)==1

		% sorting mask_large_circle pixels by distance to mask_island
		% Note - mask_IME not necessarily included in mask_IME_all (not updated if too many gaps and keep_IME=0).
		mask_REF_possible=mask_large_circle & ~Chl.mask_IME_all & ~mask_IME & ~mask_all_islandscont;  
		indices_REF_all=double(mask_REF_possible); 
		indices_REF_all(mask_REF_possible)=1:sum(mask_REF_possible(:)); 
		liste_distpixels=[mask_distpixels(mask_REF_possible),indices_REF_all(mask_REF_possible)]; 
		liste_distpixels=sortrows(liste_distpixels); 

		% getting reference region defined as same number of pixels as IME (area ie no data counts), taking the first pixels closest to the island. 
		nb_pixels_IME=sum(mask_IME(:) & ~mask_all_islandscont(:));
		nb_pixels_REF=min(nb_pixels_IME,sum(mask_REF_possible(:)));		% unlikely to be needed but possible if island in rich region
		mask_REF=false(Chl.nb_lat,Chl.nb_lon); mask_REF(ismember(indices_REF_all,liste_distpixels(1:nb_pixels_REF,2)))=true;
		if sum(mask_REF(:))~=nb_pixels_REF || max(mask_REF(:) & mask_IME(:)), error('issue with mask_REF'), end
		mask_REF=imfill(mask_REF,'holes');	% this can cause the number of pixel to be different from IME - solved later by randomly taking the same number of pixels.
		islands.mask_REF{iisland}=mask_REF;
		islands.Chl_REF(iisland)=mean(Chl.chl(mask_REF & ~isnan(Chl.chl)));
		if islands.keep_IME(iisland)==1, Chl.mask_REF_all(mask_REF & ~Chl.mask_IME_all & ~mask_IME & ~mask_all_islandscont)=true; end

	end

end
disp('100%')

varargout={islands,Chl}; varargout=varargout(1:nargout);


end