Methods are provided for extracting color distortion data from multimedia data in a content-based multimedia search and for searching multimedia data based on the extracted color distortion data. A method is also provided for generating multimedia data to be used in the content-based multimedia search. The color distortion data includes hues of the distorted color identifying which color affected such a distortion and intensity data representing how much color distortion data affected such a distortion.