In a method of extracting a logo mask from a video stream having a logo, a video stream including a plurality of frames is received. A plurality of online-weighted-average frames is sequentially generated using the video stream. A logo-boundary-score map is generated using a current frame among the plurality of frames and a current online-weighted-average frame among the plurality of online-weighted-average frames. The logo-boundary-score map includes a plurality of logo-boundary-score entries, each of which corresponds to one of a plurality of pixels of the video stream and includes a probability that a corresponding one of the plurality of pixels is a logo-boundary pixel. The logo mask includes a plurality of entries, each of which corresponds to one of the plurality of pixels and represents whether a corresponding one of the plurality of pixels is a logo pixel or a non-logo pixel.