FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
A METHOD AND SYSTEM FOR NEWS STORY SEGMENTATION OF
TELECAST NEWS VIDEOS
Applicant:
TATA Consultancy Services Limited A company Incorporated in India under The Companies Act, 1956
Having address:
Nirmal Building, 9th Floor,
Nariman Point, Mumbai 400021,
Maharashtra, India
The following specification particularly describes the invention and the manner in which it is to be performed.

FIELD OF THE INVENTION
This invention generally relates to a system and method for news story segregation, In particular the present invention describes separating a plurality of news stories present in a continuous video stream news program from commercials, headlines and from each other.
PRIOR-ART REFERENCES:
1. Colace, F., Foggia, P., Percannella, G. A Probabilistic Framework for TV- News Stories Detection and Classification, IEEE International Conference on Multimedia and Expo, pp 1350-1353, 2005.
2. Chua, T-S, et al. Story Boundary Detection in Large Broadcast News Video Archives- Techniques, Experience and Trends, ACM international conference on Multimedia, 2004.
3. Chaisorn, L., et al. A Hierarchical Approach to Story Segmentation of Large Broadcast News Video Corpus, IEEE International conference on Multimedia and Expo, 2004.
4. Hoashi, Keiichiro., Matsumoto, Kazunori., Sugaya, Fumiaki ., "Story segmentation method for video", US Patent No. 0092327, May 04, 2005.
5. Maybury, Mark T., Merlino Jr., Andrew E. , "Automated segmentation, information extraction, summarization, and presentation of broadcast news" US Patent No. 6961954 , Jan 11, 2005.
6. Lee, Shih-hung., Yeh, Chia-hung ., Shih, Hsuan-huei Kuo, Chung-chieh .. "Anchor person detection for television news segmentation based on audiovisual features" US Patent No. 7305128, Apr 12, 2007 .
BACKGROUND OF THE INVENTION
In broadcasted video signals e.g. news or sports videos, commercials are often intermixed with respective regular and premium contents of news or sporting events. For efficient analysis which includes retrieval and browsing of the premium video signals,

post broadcasting thereof, detection and removal of unwanted or irrelevant contents such as commercials are generally desirable. Moreover, stories relating to different news segments are also required to be separated from each other.
Most of the methods described by the present state of art for story segmentation in news video depend on speech analysis or Closed Captioned Text (CCT) to distinguish the topic being discussed at different time intervals during a news program and thereby identify distinct stories. Closed Captioned Text is not generally available with most of the Television channels. Further, Automatic Speech Recognition (ASR) technology is not available for many languages, and wherever it is available, generally it cannot cope up with regional variation of accents. Thus, the present state of art is not universally applicable on telecast news programs on a TV channel. Some of the other methods combine multiple cues from the videos that make the process computationally inefficient.
The method and system disclosed herein overcome the above mentioned problems. The method described herein uses repetition of ticker text in a news story to identify story boundaries, and is not dependent on language tools such as optical character recognition (OCR). A ticker text is the text available on news video screen in readable format that contains summary of the news. The system and method described herein ascertains similarity of ticker texts through image processing techniques. Thus the algorithm can be universally applied on any news channel. Use of the feature to identify story boundaries makes the method computationally efficient.
Other features and advantages of the present invention will be explained in the following description of the invention having reference to the appended drawings.
OBJECTS OF THE INVENTION
The primary objective of the present invention is to provide a method for news story segmentation that is independent of language processing tools, such as Automatic Speech Recognition, Optical Character Recognition, and the like. Further, it also does not require video annotations, such as Closed Caption Text.

Another objective of the present invention is to provide a method and system that can be applied universally on any TV news channel irrespective of country and language of transmission.
It is also an objective of the instant invention to provide a method and system for news stories segmentation that is helpful to the viewers who don't want to watch the complete news broadcast but only the news which are of their interest such as news analysis agencies.
Yet another objective of the present invention is to provide a system and method for automatic news segmentation and therefore requiring no manual segregation of the news stories.
SUMMARY OF THE INVENTION:
The video recording of a TV news program comprises a plurality of news segments interspersed with a plurality of commercial segments. The present invention at first processes the news video in order to identify and remove the plurality of commercial segments. Such a processing results in a plurality of news segments. Each news segment comprises one or more stories and headlines. Specifically, the headlines are confined towards the beginning or the end of the segment. Further, it has also been observed that a news story is generally confined to one news segment in a news program. In certain cases, a news story may span over multiple news segments. In such cases, different aspects of the story are addressed in different news segments and they may be considered as different news stories.
The method of the instant invention includes a novel feature that uses repetition of local ticker texts within a story for distinguishing the various news stories within a video stream. The different parts of a news segment containing disjoint sets of ticker texts constitute independent stories. The continuous video stream of news segments is then

processed in accordance with the novel method to separate the stories from each other and from the headlines on the basis of repetition of one or more ticker texts within a news segment.
In general, there are at least three types of ticker text bands (1) One or more Local ticker text bands that contain the highlights of the news currently being presented, (2) One Global ticker text band that contains the highlights of all important stories in the news program and (3) One Scrolling text band providing gist of relatively unimportant news. One or more local ticker texts keep on repeating during the complete duration of a news story. The present invention utilizes this feature of local ticker texts to separate stories from each other and other components.
In an aspect, the repetition of ticker texts may be ascertained by image comparison technique and without extracting the text from ticker-text images. Thus, the method may be applied universally on telecast news program in any language without requiring the support of optical character recognition tools.
BRIEF DESCRIPTION OF DRAWINGS
The foregoing summary, as well as the following detailed description of preferred embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there is shown in the present document example constructions of the invention; however, the invention is not limited to the specific methods and apparatus disclosed in the document and the drawing:
Fig.I illustrates a block representation of interspersed news and commercial segments in a news program.
Fig.2 illustrates a general embodiment of the method described by the instant invention.

Fig. 3 illustrates a block representation of Local Ticker text bands in News Segment frames.
Fig. 4 illustrates Ticker Text Blocks (TTB's), Stable Ticket Text Blocks (STTB's) and Representative Ticker Text Images (RTTI's) in a Local Ticker text band.
Fig. 5 shows Unique Ticker texts and news story boundaries.
Fig. 6 shows extending story boundaries.
DETAILED DESCRIPTION OF THE INVENTION
Some embodiments of this invention, illustrating its features, will now be discussed:
The words "comprising," "having," "containing," and "including," and other forms thereof, are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items.
The disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms.
Fig. 1 illustrates a video recording of a TV news program comprises of news segments interspersed with commercial segments. Such commercial segments may be of a variable time period. Further, within the news segments there may be a plurality of news stories. One or more ticker texts may be present that keep on repeating during the complete duration of a news story.

The present invention describes a method that utilizes these ticker texts for separating stories from each other and other components.
According to fig. 2 an embodiment of the present invention is described. The method (200) includes the following steps:
Extraction of news segments (201): The initial step for segregating the news stories from each other is to segregating the news segments from commercial segments. The commercial segments may be identified by using methods well known in the art or a method as described in patent application no. 1746/MUM/201. The identified commercial segments are removed from the news segments that results in a plurality of contiguous news segments.
Extracting Ticker Text Band Images (202): The plurality of contiguous news segments is now independently processed, A news segment contains local ticker texts that occur at some known fixed regions of a frame in the news segment video as shown in figure 3. Such region containing a local ticker text is known as a local ticker text band. The frames are extracted from a given news segment and each of the frame is cropped to retain the regions corresponding to the local ticker text bands resulting in an image. The images are then converted into binary format to produce black and white images. Such a processing results into a plurality of black of white images corresponding to the local ticker text bands for every frame in a news segment. Such images are known as Ticker text images, hereinafter known as TTBi wherein i represents the local ticker-text band and the corresponding frame number is represented by k. Fig. 4 illustrates a ticker text band in detail.
Identifying Ticker Text Blocks (203): The ticker text images obtained from the step above may or may not contain text. The next step is to identify the ticket text boxes containing text. Images containing text generally contain more sharp edges than those not containing text. An edge detection algorithm using a Sobel operator may be executed on each of the images TTBi and the number of pixels containing horizontal edges (ne) in

each of the images is counted. The images are clustered in two clusters CHi and CL0 based on ne using k-means algorithm. The images in cluster Cm have greater number of horizontal edges than the images in the cluster CLo and are considered to contain text. The images in CHI belonging to the same local ticker text band and having contiguous frame numbers and grouped into Ticker Text Blocks (TTB's). For every local ticker-text band a set of TTBi's containing text are obtained that may be separated by blocks of TTBi's that do not contain ticker. Such text blocks are designated as TTBy, wherein i represents the local ticker-text band andy represents the block number.
Identifying stable ticker-text blocks (204): A ticker text may appear in a ticker text band and may remain stable for an adequate time for a viewer to read and then may disappear. The appearance and disappearance of a ticker text is often marked with video editing effects, such as swipe-in and swipe-out. A Ticker Text Block (TTB), identified in the last step, contains one or more distinct ticker text instances. Each Ticker Text block TTBy contains a set of Ticker Text images designated as/ hjk, where k represents the frame number for the image, The successive images in a Ticker Text block are then compared wherein two images Ix and ly of equal size are compared pixel-by-pixei and the absolute differences are added up to compute the difference designated as dxy between the two images. All difference values so obtained are then clustered into two clusters designated as CHJ having higher difference value and CL0 having lower difference value by means of a clustering method such as K-means clustering method. Consecutive images in a TTB that have difference values falling in the cluster Q0 constitutes Stable Ticker Text Blocks designated as STTB. Thus, we get a set of Stable Ticker Text Blocks STTBy, where i represents the local ticker text band and/ represents the block number.
Extracting Representative Ticker Text Images (205): Each Stable Ticker Text Block contains exactly one stable ticker text. Since a few frames at the beginning and at the end of a Stable Ticker Text Block may have some video editing effect, the Ticker Text Image in the middle frame in a Stable Ticker Text Block is chosen as the Representative Ticker Text Image designated as RTTIy, where / represents the Ticker text Band andy represents the STTB number. Figure-4 shows TTB's, STTB's and RTTi's in a local ticker text band.

Identifying unique Ticker Text Images (206): The RTTI's in each local ticker text band are then pair-wise compared and the difference values are clustered into two clusters as done while identifying stable ticker-text blocks (40). The lower difference values in do indicate matching ticker-text images. The number j in RTTIy and corresponding STTBy are replaced with a tuple (p,q), wherein p indicates a unique ticker text number and q indicates the instance of occurrence of the unique ticker text. Thus, the RTTI's and STTB's are now renumbered as RTTIipq and STTBipq. Figure 5 shows 5 instances of 3 distinct ticker texts and corresponding STTB's.
Identifying story segments (207): Story segments are identified in following steps:
a. The start and end times of STTBipq are designated as SjPq and eipq. The start
time for the first occurrence of the unique ticker text/? is designated as sip
and the end time of last occurrence of the unique ticker text p is
represented by eip, in local ticker text band i. The interval (sip, eip) is
called the extent of unique ticker text p in local ticket text band /.
b. All the overlapping extents are merged to define the boundaries of a story.
Extents from all local ticker text bands may be considered for merger. The
condition for merger of two extents extentx and extenty can be formally
specified as
sipx < eip}, AND eipx > sipy.
If a news story is created by merging a set of extents extentj (/=l..n). the story start and end times are computed asmin/(sip) and max;(eip;). Headlines generally occur in the beginning and at the end of a news segment. A headline, which occurs at the beginning and also repeated at the end of a news segment contain identical local ticker texts. Therefore, the entire news segment may be incorrectly considered as one single news story. In order to prevent such mistake, the following points need to be taken into consideration (a) the headlines are restricted within first or the last quarter of a news segment and (b) the ticker-text on the headlines are distinct from those on the stories. Such a method may be

applied independently to first 75% and to the last 75% of a news-segment in order to avoid duplication of ticker-text across the first and the last quarters. Stories which are less than a pre-determined time-period in duration, appearing at the beginning with no long story preceding them or at the end with no long story following them are discarded as headlines.
Figure 5 depicts overlapping extents of ticker texts and story boundaries.
Extending story boundaries (208): This method step is used to extend the story boundaries to cover parts of a news segment that may not form part of any story as identified in the preceding steps.
a) News story boundaries may always be marked with a visual change in the scene. Successive frames in a news segment may be compared based on color histogram in HSV space and shot boundaries may be identified using the difference values as done while identifying stable ticker-text blocks (40). The stories as defined are extended to the nearest shot boundaries. In general, the shot boundaries do not coincide with the STTB boundaries.
b) There may be a plurality of shots between the news stories that may be without any ticker-text. Such shots may be part of either the preceding or the succeeding story and further resolution is not possible. In an embodiment such shots may be included in both the news stories, hence none of the important information is missed out.
Figure 6 shows extension of story boundary to shot boundaries and to cover
unclaimed shots. The preceding description has been presented with leference to various embodiments of the invention. Persons skilled in the art and technology to which this invention pertains will appreciate that alterations and changes in the described structures and methods of operation can be practiced without meaningfully departing from the principle, spirit and scope of this invention,

CLAIMS:
1. A method for language independent news story segmentation from a broadcasted video stream, comprising:
a) extracting a contiguous news segment from the video stream;
b) extracting a plurality of frames from said contiguous news segment;
c) cropping said frames to retain a local ticker text band;
d) binarizing said local ticker text into a plurality of Ticker Text Band Images;
e) identifying and clustering said Ticker Text Band Images containing ticker text belonging to same local ticker text band and to contiguous frames into a plurality of Ticker Text Blocks;
f) identifying and clustering a plurality of Stable Ticker Text Blocks from said Ticker Text Blocks;
g) identifying a Representative Ticker Text Image from the Stable Ticker Text Blocks;
h) identifying at least one unique ticker text image by pair wise comparing said Representative Ticker Text Images in each local ticker text band; and
i) identifying a unique news story based on the occurrence of a distinct unique ticker text image.
2. The method of claiml wherein, the Ticker Text Blocks are created by employing an edge detection algorithm on the Ticker Text Band Images.
3. The method of claiml wherein, the Stable Ticker Text Blocks are identified by comparing difference in the images of the ticker text blocks.
4. The method of claim 1, wherein the Ticker text images not included in the Ticker Text Blocks are employed for extending story boundaries.