The invention relates to a method (100) for context based encoding of a histogram map of an image, the histogram map representing location information of key points of the image, the method comprising: providing (101) compressed context representation information (A; B; C) associated to a given encoding size and to a given block size of a spatial grid applied to a matrix representation of the image to obtain the histogram map; computing (103), from the compressed context representation information (A; B; C), a context (201) for the given encoding size and the given block size by applying an approximation algorithm; and encoding (105) the histogram map using the context computed for the given encoding size and the given block size.