Methods and apparatus to measure brand exposure in media streams are disclosed. Example apparatus disclosed herein are to determine a first histogram based on at least one of luminance components or chrominance components of a first frame of video, and determine a second histogram based on at least one of luminance components or chrominance components of a second frame of the video. Disclosed example apparatus are also to detect a transition in the video based on the first histogram and the second histogram, and responsive to the detection of the transition in the video. Disclosed example apparatus are further to process a region of interest within at least one of the first frame or the second frame to detect a logo in the region of interest.