THE AUTOMATIC RECOGNITION OF INTERMODULATION, HUM AND SNOW NOISE IN CABLE TELEVISION SYSTEMS. By Reidar Gresseth B. Sc. (Combined Physics and Mathematics) University of British Columbia, 1988 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard UNIVERSITY OF BRITISH COLUMBIA November 1992 ©ReidarGsth,192 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. (Signature) Department of Electrical Engineering The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Al9 V 1 7^19.2 . ABSTRACT A system which automatically monitors the cable television signal is proposed. The monitoring devices, located at key areas in the television network, would alert the cable company to the presence of several important types of television impairments. In this thesis, the automatic detection of three kinds of impairments is discussed; intermodulation carrier beats, hum modulation and snow noise. The detection algorithms we develop are non-intrusive and do not require the use of test signals. A mathematical model which describes an intermodulation carrier beat is developed and the corresponding 2-dimensional Fourier transform is shown to exhibit properties which are advantageous for automatic recognition. In particular, it is shown that four peaks will appear in the Fourier transform of the image if a beat is present. These peaks possess distinguishing characteristics which allow the automatic detection of the beat. Another television impairment, hum modulation, causes either single or double bands on the television screen depending upon the impairment's frequency. By using the theory of orthogonal functions developed by Sturm and Liouville, a general algorithm is developed which recognizes hum modulation or any impairment of a fixed and known shape. The algorithm is applied to the case of a sinusoidal hum function. Finally, snow noise, which is a random white Gaussian noise, is addressed. An algorithm is developed which detects these random variations by comparing each pixel in the image with neighbouring points. Experimental verification done with several images is shown to produce good results even if the level of noise is small ( up to carrier to noise ratio of 35 dB ). ii TABLE OF CONTENTS ii ABSTRACT^ LIST OF FIGURES^ ACKNOWLEDGEMENT^ 1 vi viii INTRODUCTION 1 1.1 HISTORY OF TELEVISION STANDARDS ^ 1 1.2 SCANNING THE IMAGE AND THE CRT ^ 2 1.3 THE NTSC STANDARD AND INTERLACING ^ 3 1.4 PICTURE QUALITY OF THE SIGNAL ^ 4 1.5 AN AUTOMATIC DETECTION SYSTEM ^ 5 1.6 TELEVISION IMPAIRMENT CLASSIFICATIONS ^ 5 1.7 RATING AND DETECTING THE IMPAIRMENT ^ 7 1.8 AUTOMATIC IMPAIRMENT RECOGNITION ^ 8 2 INTERMODULATION 10 2.1 INTERMODULATION IN THE CABLE NETWORK ^ 11 2.2 TYPES OF INTERMODULATION ^ 13 2.3 FREQUENCY OF THE INTERMODULATION IMPAIRMENT 14 2.4 MATHEMATICAL DESCRIPTION OF INTERMODULATION ^ 16 2.5 FOURIER, TRANSFORM OF THE MODEL ^ 18 2.6 AUTOMATIC DETECTION USING THE 2-D TRANSFORM ^ 22 iii 3 4 5 2.7 AN ALTERNATE RECOGNITION ALGORITHM ^ 23 2.8 SOFTWARE ^ 25 2.9 EXPERIMENTAL VERIFICATION ^ 26 HUM 36 3.1 CHARACTERISTICS AND CAUSES OF HUM ^ 36 3.2 GENERAL APPROACH TO HUM RECOGNITION ^ 37 3.3 THE THEORY OF ORTHOGONAL FUNCTIONS ^ 38 3.4 STURM-LIOUVILLE THEORY ^ 40 3.5 HUM RECOGNITION USING ORTHOGONAL FUNCTIONS ^ 44 3.6 APPLICATIONS VIA FOURIER SERIES ^ 47 3.7 SOFTWARE ^ 48 3.8 EXPERIMENTAL VERIFICATION ^ 49 SNOW NOISE 57 4.1 CHARACTERISTICS AND CAUSES OF SNOW ^ 57 4.2 CARRIER-TO-NOISE RATIO ^ 58 4.3 FOURIER, TRANSFORM OF SNOW NOISE ^ 59 4.4 SUBJECTIVE RECOGNITION OF SNOW IMPAIRMENT ^ 59 4.5 AUTOMATIC RECOGNITION OF SNOW NOISE ^ 59 4.6 MODIFICATIONS TO THE DETECTION ALGORITHM ^ 62 4.7 OTHER POSSIBLE DETECTION ALGORITHMS ^ 63 4.8 SOFTWARE ^ 64 4.9 EXPERIMENTAL VERIFICATION ^ 64 CONCLUSION 5.1 74 INTERMODULATION BEAT PRODUCTS ^ iv 74 5.2 HUM ^ 75 5.3 SNOW NOISE ^ 76 BIBLIOGRAPHY^ 77 LIST OF FIGURES ^17 2.1 Television Screen Dimensions 2.2 Fourier Transform Showing Intermodulation Peaks ^ 22 2.3 Sample 1-D Detection Algorithm Graph ^ 24 2.4 Ritukoen Image Without Intermodulation Noise ^ 28 2.5 2-D Fourier Transform of Ritukoen Image Without Noise ^ 29 2.6 Ritukoen Image With Intermodulation Noise - 25 dB ^ 30 2.7 2-D Fourier Transform of Ritukoen Image With Noise - 25 dB ^ 31 2.8 2-D Fourier Transform of Ritukoen Image With Noise - 43 dB ^ 32 2.9 1-D Fourier Transform of Ritukoen Image Without Noise ^ 33 2.10 1-D Fourier Transform of Ritukoen Image With Noise - 25 dB ^ 34 2.11 1-D Fourier Transform of Ritukoen Image With Noise - 43 dB ^ 35 3.12 The Television Screen In Terms Of A 1-D Function ^ 45 3.13 Experimental Frames Used by Hum Detection Algorithm ^ 50 3.14 Aliens Image With Hum And With A Block Removed ^ 52 3.15 Aliens Image With Horizontal Motion - Cosine Inner Product ^ 53 3.16 Aliens Image With Horizontal Motion - Sine Inner Product ^ 54 3.17 Aliens Image With Vertical Motion - Cosine Inner Product ^ 55 3.18 Aliens Image With Vertical Motion - Sine Inner Product ^ 56 4.19 Pixel Neighbourhood For Snow Detection ^ 60 4.20 Data Image Without Snow Noise ^ 66 4.21 Gorby Image Without Snow Noise ^ 67 vi 4.22 Oldmill Image Without Snow Noise ^ 68 4.23 Fiji Image Without Snow Noise^ 69 4.24 Fiji Image With Snow Noise - 21dB ^70 4.25 Snow Noise Predictions ^71 4.26 Snow Noise Predictions - Enlargement Near The Origin ^ 72 4.27 Relation Between X_noise And Carrier To Noise Ratio ^ 73 vii ACKNOWLEDGEMENT Sincere thanks go to Dr Rabab Ward for her assistance as thesis advisor and to Rogers Cable, Inc who supplied computer equipment for the project. viii Chapter 1 INTRODUCTION In the last fifty years, the number of television sets being used worldwide has increased steadily. In more remote areas, the quality of the signal obtained directly from the television transmitter may be of an unsatisfactory quality. This may be caused by many factors, such as overhead power lines, high flying airplanes, nearby mountain ranges or simply the distance from the transmitter. Many homes have opted to use satellite dishes to improve their reception, this can be an expensive and somewhat impractical solution. In urban or densely populated areas a more economical solution is the use of a cable network for the transmission of the signal, cable also has the added benefit that many more channels can be made available to the viewer. Monitoring the quality of the transmitted picture through the cable network is the topic of this thesis. 1.1 HISTORY OF TELEVISION STANDARDS The first colour television system was designed and built by .John Logie Baird in 1928, see [10]. It was another twenty five years before a standard would be adopted in North America. This standard was developed by the National Television Systems Committee ( or NTSC ) which contained representatives from many of the largest corporations of the day. They defined a 525 line resolution system that was colour compatible. or more specifically, the signal was compatible on both black-and-white and colour television sets. The NTSC system is the oldest television system still in widespread use and has a poorer resolution than other popular standards such as SECANT or PAL. 1 Chapter 1. INTRODUCTION ^ 2 The television system used in France, SECAM, was developed by Henri de France. This system is quite similar to that proposed by the NTSC, however, SECAM merges the two colour difference signals into a single alternating signal. This produces a system that is less affected by small changes of phase in the transmission and propagation path but results in a poorer quality black-and-white picture. SECAM has undergone several small changes and improvements since its initial adoption, the system presently in use is known as SECAM IIIA, while a variant of the system used in Russia is called NIR. In 1962, Walter Bruch of the Telefunken Company developed the PAL system. PAL, which stands for phase alternation line, has been adopted in most of Europe and the rest of the world. It gives a 625 line resolution which provides a superior quality picture to the NTSC system. Also, by an ingenious method of phase alternation, the PAL system reduces the susceptibility of colour and phase changes in the transmitted signal. PAL is available in PAL deluxe, which produces more accurate colour reproduction through averaging, and in People's PAL, which does not include the colour averaging. 1.2 SCANNING THE IMAGE AND THE CRT Most TV sets draw the television image as a series of horizontal lines using a cathode ray tube, or CRT. There are exceptions, such as certain laboratory experiments, in which it is advantageous for the image to be drawn from the center outward. However, for this discussion and for most commercial applications, the CRT scans individual lines from left to right and draws each successive line from top to bottom. Lines are divided into a series of points, called pixels, which make up the basic picture unit. Since each line in the image is started from the left side, there is a small interval of time after the CRT has drawn the line during which the CRT must move back to the leftmost point of the screen. This period is called the horizontal retrace time. For several Chapter 1. INTRODUCTION^ 3 of the television impairments to be discussed this interval needs to be considered in the calculations to ensure that the results obtained are accurate. Once the cathode ray tube has drawn the last line at the bottom of the screen, it begins to draw the next image. As the image is always scanned from top to bottom it is necessary that the CRT returns to its initial point at the top of the screen. The interval in which the CRT moves to the initial point is called the vertical retrace time. Due to this retrace, the CRT does not draw the final lines in the image and, consequently, the 525 line resolution of the NTSC system is slightly reduced, only 480 lines will be visibly scanned by the CRT for each image. 1.3 THE NTSC STANDARD AND INTERLACING To produce a better quality picture, the NTSC and other standards require that the television image be drawn in an interlaced format, see [13]. This means that when the first line is drawn the CRT doesn't start drawing the second line but rather goes to the third line. Once the third line is drawn the cathode ray tube begins with the fifth line, and so on to the bottom of the screen. When the CRT returns to the top of the screen it draws the second line of the same image, followed by the fourth line and so on until the picture is completely drawn. It was found that by interlacing the image, the flicker that is inherent otherwise is significantly reduced. If the image were not interlaced each area of the screen would fade before the CRT returned to trace the next image, this effect would be quite visible to the human eye. Let us calculate the actual number of lines drawn in the NTSC standard each second. Thirty frames are drawn each second at a rate of 525 lines per image. This gives 525 x 30 = 15,750 lines/second.^ (1.1) The aspect ratio for most television sets is 4 : 3 and so, assuming television pixels are Chapter I. INTRODUCTION^ 4 square, there are 640 pixels per line. By multiplying this by the result in equation (1.1) we see that there are more than ten million pixels drawn on the screen each second. 1.4 PICTURE QUALITY OF THE SIGNAL As the television signal may be quite weak unless the viewer lives within the station transmitter's range, several cable companies operate which provide an amplified signal to homes for a monthly fee. These companies are able to provide additional important services, such as more channels, pay TV and information channels. The major cable company in the Vancouver area is Roger's Cable, Inc. Cable companies provide their service through an elaborate series of amplifiers connected by coaxial cables. This network distributes the signal from the headend where the signals are received to the cable subscribers. If any point in this network fails to work properly the image quality will degrade. In the 1990 annual questionnaire of Consumer Reports, the readers were asked how they would rate their satisfaction with the local cable company, see [1]. The results were the lowest they had found in sixteen years. Even though these complaints showed that customer dissatisfaction was also due to price increases and billing problems, it is apparent that the quality of the picture is a very important factor to the cable subscriber. Most cable companies are aware of the need for an impairment free picture and they expend a great deal of effort to provide a good signal. If a problem is found the servicemen are usually able to repair the fault quickly, but in this period, the affected subscriber, who is usually the person who has reported the problem, has had his or her viewing interrupted. Ideally, the problem should be detected and repaired before there has been any significant interruption to the subscriber's television signal. Chapter I. INTRODUCTION^ 5 1.5 AN AUTOMATIC DETECTION SYSTEM To improve the quality of the cable service, we propose that monitoring stations be developed and located throughout the cable network. These stations would be operated automatically and would test the signal for some of the more serious types of television impairments. If a particular problem is recognized a warning is sent by the device to the headend, a serviceman is then dispatched to fix the network. If all goes well, the problem will be located and repaired before there is any significant inconvenience on the part of the subscriber. The monitoring devices would provide a fast, reliable TV impairment warning system. 1.6 TELEVISION IMPAIRMENT CLASSIFICATIONS There are several major types of impairments that are common to the television signal, see [4]. Some impairments will only affect a single subscriber, such as those due to a faulty television receiver. Others will affect an entire region, for example, impairments due to extremely poor weather conditions or due to a faulty cable amplifier. Intermodulation, hum and snow noise will be discussed in chapters 2-4, while some of the other significant impairments will be briefly described below. An interesting impairment is ghosting, a phenomenon in which a delayed version of television image appears on the screen. The delayed image is visible either to the right or the left of the original image. If the image appears to the right then this is normal ghosting, the second image is generally not as strong as the main picture. If the image appears to the left then this is called leading ghosting, the reflected image is usually stronger than the normal signal. This impairment is caused by a strong reflected signal at the antenna site. Crossmodulation is very closely related to the phenomenon of intermodulation and Chapter 1. INTRODUCTION^ 6 the causes of both will be discussed in the next chapter. Crossmodulation is characterized by the presence of a faint image on the screen due to another channel. This impairment is produced by a converter overload or an overload of one of the headend or distribution amplifiers. The herringbone impairment is so named by the shape of the distortion that is produced. The screen is filled with horizontal herringbone bands which move across the picture. If only a few channels are affected the cause may be due to interference with lower adjacent sound frequencies, while if all channels are affected then the problem may be due to a mistuned television set or converter. Neighbouring subscribers may be affected depending upon the type of receiver they have. There are two types of electrical interference impairments, the broadband and the impulse type. The broadband is characterized by a moving interference pattern, with tearing of some lines and the presence of a peppery interference across the entire screen. It may be caused by fluorescent lighting fixtures or by power line interference. The second type of electrical interference, the impulse type, is characterized by random bursts of interference for only a brief duration. This usually only occurs for a small number of lines and does not cause very extensive line tearing. This impairment can be caused by electrical motors, faulty lighting fixtures, dimmer controls and by the ignition systems in internal combustion engines. Diathermy is characterized by intermittent, usually repetitive, patterns of herringbones shapes, reminiscent of an elongated S. This impairment tends to affect only channels two, six, seven, and thirteen and occasionally channel three. Typically, diathermy is caused by appliances such as microwave ovens or by certain devices used in hospitals. Additional disturbances can be caused by overhead airplanes or by poor weather conditions. However, cable companies are most concerned with those types of impairments that arise in the cable system and can be readily fixed, and accordingly, most of Chapter 1. INTRODUCTION^ 7 this discussion will deal with those impairments that were fundamental concerns to our local cable company, Roger's Cable. For example, of primary importance are picture carrier beats, which are a form of intermodulation. These beats may affect an entire neighborhood and can be very annoying to the subscriber. 1.7 RATING AND DETECTING THE IMPAIRMENT There have been a number of experiments done on television impairments in which the severity of each type of disturbance is rated. Typically, the approach has been to take a selection of viewers and ask them to rate the disturbance in terms of how annoying they feel it is. This subjective approach has been studied in a number of instances, see [3]. Although this thesis is more concerned with methods of detecting and rating these impairments without the aid of a human viewer, it is important that the predictions made by the monitoring devices coincide with the ratings found using the subjective approach. Several methods of monitoring and recognizing television impairments have been studied, for instance, a mechanical simulation of the human eye was used to rate the severity of television impairments in [16]. This approach, while reasonably successful, required a fairly restrictive testing environment. Another possible solution is to hire engineering firms to assist the cable company in rating the quality of the signal, see [15]. This latter approach could be inconvenient since it involves visits by the engineers to subscribers homes in order to test the quality of the signal. An approach for automatic detection that could be considered is the introduction to the cable system of a test signal. There are certain time intervals, in particular, the horizontal and vertical retrace times in which the cathode ray tube does not draw on the screen. During these periods, the cable company could arrange to send a predetermined signal to the detection devices. If the device finds any difference between the received Chapter 1. INTRODUCTION ^ 8 signal and the expected pattern then it knows that some type of distortion is present. Also, since the expected signal is known it is much easier to determine the manner of the impairment, in particular, taking the difference image will give the impairment without any underlying image to affect the prediction. A variation of the test signal approach involves digitizing the received signal, protecting it with a high order correction code and then sending it back through the same network if a return path exists or through a second network to the cable headquarters. The image, once reconstructed and displayed on the screen, could be studied by an employee who would have no difficulty in seeing whether impairments were present in the signal or not. This would be a very simple solution to the problem, the employee could instantly see the image that has been received at any point in the network without leaving his or her office. The cable company could locate any problem themselves or could verify reports of a problem from their customers. 1.8 AUTOMATIC IMPAIRMENT RECOGNITION Our aim is to develop impairment recognition algorithms which can be implemented in "black box" devices located throughout the cable network. The devices would monitor the signal and report the existence any type of television noise to the cable company. Primarily, it is important that the monitoring devices operate with the least possible alteration to the existing cable network. For example, there would have to be significant redesign of the broadcasting equipment to be able to send a test signal during the horizontal or vertical retrace periods. There are currently three lines in the vertical retrace time reserved for test signals but this is not enough information for impairment recognition, especially if more than one impairment is present in the signal at the same time. Chapter 1. INTRODUCTION^ 9 Therefore, the remainder of the discussion will assume that the detection devices are selfcontained and do not require test signals or any other modification to the existing cable system. The image that is received via the network is the only available information the device will have and the prediction must be based entirely upon means independent of human interaction. The goal is to devise detection algorithms that will effectively monitor the signal without lengthy calculations. Since the NTSC system transmits 30 frames per second and all but the simplest algorithms require more than 1/30th of a second to compute, it is apparent that the device will not be able to test each image, the device would test every second or third ( or more ) frame that is transmitted. The interval between the images that are tested should be as small as possible, since statistically, a greater degree of accuracy is obtained by using more data samples. We will, for example, discuss two algorithms for detecting intermodulation distortion, one uses the two dimensional Fourier transform and the other uses the one dimensional Fourier transform. The latter is preferred since fewer calculations need to be performed while the algorithm produces only slightly less accurate predictions. Chapter 2 INTERMODULATION Let us consider the properties of an intermodulation carrier beat and the various effects this impairment has on the television picture. As will be seen, intermodulation has several forms, from picture carrier beats to composite triple beats, in addition, there is a close relationship between intermodulation and crossmodulation. We will develop algorithms which automatically detect the picture carrier beat, which is the basic form of intermodulation and appears on the screen as a series of diagonally parallel lines, from the image itself. Television programs that are available through cable systems come from many diverse sources. Each program occupies a different range of frequencies, called a channel. These channels are combined at the headend of the cable system. The system forms a wide band multichannel signal of up to eighty channels. Cable companies transmit this signal to thousands of households through an elaborate network where amplifiers are cascaded every half mile ( or less ). These amplifiers, never perfectly ideal, may produce certain distortions due to their nonlinear transfer function. Intermodulation implies the mixing of the desired signal with one or more unwanted signals. This may happen through any of the nonlinear elements in the system; the television transmitter, the receiver or in one of the amplifiers. Due to the large number of amplifiers used in the network, the study of intermodulation becomes very meaningful for cable television signals. 10 Chapter 2. INTERMODULATION ^ 11 2.1 INTERMODULATION IN THE CABLE NETWORK Intermodulation is most significant if the nonlinear device has a characteristic of odd order, most prominently for third or fifth degree distortion. If one or more unwanted signals is present simultaneously in the television's input then intermodulation or crossmodulation may result. The former impairment will appear as a series of diagonal lines while the latter will produce a faint image from the unwanted channel. For example, let us assume that the television signal can be described by the superposition of the two functions ^(t)^ v i (t) cos [w i t + 0 1 (0]^ (2.2) ^x 2 (t)^v 2 (t) cos[w 2 t + 0 2 (0]^ (2.3) where x i (t) is the intended signal and x 2 (t) is the unintended signal. Both of these signals are combined and passed through a nonlinear device which has a characteristic of the third degree, producing the equation [x i ( t) + x2(t)] 3 =^vi (t) ( 3 co s[w i t + 0 1 (0] + cos [3w i t + 30 1 (t) ]) / 4 + 3q(t)v 2 (t) cos(2w i t + w 2 t + 20 1 (0 + 0 2 (0)/4 + 3t4(t) v 2 (t) cos ( 2w i t — w 2 t + 20 1 (0 — 0 2 (0)/4 + 3 q(t ) v 2 (t ) cos ( w 2 t + 0 2 ( 0) /2 + 3v i ( t)v(t) co s(2 w 2 t + w i t + 2 02( t ) + 0 1 (0) / 4 + 31) 1 (t) v ( t ) c o s(2 w 2 t — w i t + 202( 0 — 01 ( t) ) /4 + 3v i t ) v (t) co s ( w i t + ¢ i (t))/2 ( L'(t)( 3 cos[w 2 t + ¢2(t)] + cos[3w 2 t + 3¢ 2 (t)])/4. ^(2.4) The first two terms in equation (2.4), ^14(0( 3 cos(w i t^+ 01(0) + cos(3w 1 t + 30i(t)))/4 ^ (2.5) Chapter 2. INTERMODULATION^ are simply the value of the signal is, they are equal to 12 x 1 (t) when transformed by the nonlinear device, that xi(t). It should be apparent that the last two terms, equal to 4(0, like equation (2.5), are of little interest. The second line in equation (2.4), 14(t)v 2 (t ) co s (2w i t w 2t 201( 0 + 0 2 ( 0) /4^(2.6) will appear as intermodulation if 2w 1 W 2 is within the passband of the cable amplifier. Similarly, the third line of equation (2.4) 3v1(t)v 2 (t) cos(2w i t — w2t 201(0 — 02(t))/4 ^(2.7) appears as intermodulation if 2w 1 — w 2 is within the passband of the amplifier. The fifth term in equation (2.4) 34(t)v 2 (t) cos(w 2 t^0 2 (0)/2^ (2.8) is the crossmodulation term. Note that the crossmodulation term has a frequency equal to the frequency of the signal in equation (2.3) while its amplitude becomes a combination of both the signals. If the signal has crossmodulation impairment this simply implies that the unwanted signal is re-radiated. Since intermodulation occurs at an entirely new frequency this type of disturbance is considered to be more serious than crossmodulation. As stated, the combination of the signals x i (t) and x 2 (t) produce intermodulation components if the output device has a nonlinear characteristic of degree three. The frequencies 2w 1 f w 2 and 2w 2 f w 1 are the frequencies of the intermodulation disturbance. However, this is the simplest case in which intermodulation may result. Rather than a single unwanted signal there may be several signals causing the interference and intermodulation distortion may be added at any or all of the nodes in the cable network. We will consider the more general case in which there are three channels at frequencies w 1 , w 2 and w 3 . Once again, intermodulation will result from the cross terms that have a 13 Chapter 2. INTERMODULATION frequency which is within the passband of the cable amplifier. These will be (-02^w3 (2.9) w2 (2.10) where each of the indices can be permuted to form additional intermodulation frequencies. We can further generalize these results to include the case of the mixing of signals in an output device which has a characteristic of degree five. Although the fifth order terms will make a smaller contribution than the third order, they may still add significantly to the intermodulation component of the signal. Let us consider the merging of five channels with frequencies w 1 w 2 , w 3 , w 4 and w 5 . They will produce interference components with , frequencies col w2 w3^w5^ (2.11) 2w 1 w2 w3 w4^ (2.12) 3w 1 f co 2 f w3^(2.13) 3w 1 f 2w 2^(2.14) Once again, the indices can be permuted to provide other possible frequencies at which intermodulation may occur. 2.2 TYPES OF INTERMODULATION Intermodulation is classed under several different categories depending upon how the distortion affects the television picture. The first type is the picture carrier beat. This is characterized by horizontal or diagonal intensity bands across the screen. Depending upon how close the interference frequency is to the picture carrier, these beats can be either narrow or quite broad ( the nearer to the carrier the wider the band ). The carrier Chapter 2. INTERMODULATION^ 14 beats can be caused by an overdriven amplifier or they may be caused by interference from the radio frequencies used by taxicabs. In the latter instance, the problem will be intermittent as taxis approach the vicinity of the television receiver. A second kind of intermodulation distortion is called low frequency colour beats. This type of noise is characterized by broad bands of colour variation on the screen. Colour beats may cause noticeable changes in colour, where for example, greens become yellow or reds become orange. As with picture carrier beats, this intermodulation impairment can be due to an overdriven cable amplifier or can be caused by interference of the television signal with the radio frequencies of taxicabs. In the case of colour beats, the frequency of the interfering signal falls near that of the colour carrier of the victim channel. The final example of intermodulation is the composite triple beat. This type of intermodulation is due to the cumulative effect of hundreds of third and fifth order intermodulation beat products. This impairment is characterized by a graininess or a texture effect over the entire picture. Triple beats usually have the appearance of causing lines to tear in portions of the image. 2.3 FREQUENCY OF THE INTERMODULATION IMPAIRMENT In this thesis, we will consider the case in which intermodulation consists of a single beat product At cos(w t t O t )^ (2.15) with angular frequency W t . The superposition of this impairment and the victim signal fo (t) results in the sum ft (t ) = fo(t) + At cos(w t t + 4t).^ (2.16) 15 Chapter 2. INTERMODULATION^ and when painted on the TV screen becomes the function f (x, y). We will study the relationship between ft (t) and the function f (x, y) which describes the two dimensional television picture. To model the received signal in terms of the television picture it is necessary to understand how the cathode ray tube draws the image on the screen. The CRT traces the image in an interlaced format that is designed to reduce flicker. The beam draws lines horizontally across the screen, beginning with the top line and preceding to every other row. When the ray reaches the bottom of the screen the CRT moves up to the second line and traces the remaining parts of the image. By this method, the image is actually drawn in two complete segments called fields, each field consisting of the set of odd or the set of even lines in the image. The impaired image along each horizontal line is the superposition of the original television image f0 (t) and a sinusoid term corresponding to the intermodulation beat product A cos(co x t + 0). The last term when drawn on the screen will be assumed to have the angular frequency co x and an unknown phase, which, for simplicity, we will assume is zero when the CRT begins to scan the image. In other words, with y = y o held fixed each line on the screen is f (x, y o ) = fo(x, Yo) + A cos(wxx + Oyo ). (2.17) The phase of the harmonic Oyo will depend upon the width of the image and upon the vertical position of the line being drawn. The frequency of the intermodulation in the one dimensional signal, co t , will not be the same as the frequency cox . The latter frequency will depend upon the size of the screen being drawn and by the rate at which the images are drawn. For example, given a 30 Hertz interlaced frame cycle we have x= 30XYt ^ AxAy (2.18) Chapter 2. INTERMODULATION^ 16 where X and Y are the horizontal and vertical lengths, respectively, of the screen. This equation is only true for the interval in which the CRT is tracing the initial row of the image. However from this, we can use the expression w t t = wx x to give wt AxAtx wtt — ^ = w x x. 30XY (2.19) Thus the relationship between w t and w s is = AxAywt 30XY (2.20) As an example of the above formula, let us define X = 640 and Y = 525. If we set cos = 7r/2 this gives cot = (30)(640)(525)(7r)/2 = 1.58 x 10 7 Hz^(2.21) 2.4 MATHEMATICAL DESCRIPTION OF INTERMODULATION In order to mathematically construct a model of the intermodulation impairment we will first separately look at the noise contribution of each horizontal line. An equation which describes the noise can be easily obtained by combining each of the separate components. To facilitate our model, it will be useful to introduce a few definitions. Let X and Y be the horizontal and vertical lengths of the television image. Let X' be horizontal length that would be drawn if the CRT retrace period was zero. Likewise, let Y' be the length that would be drawn if vertical retrace period was zero. See figure 2.1 for details. Also, let us define the rectangle function to be rect a , b (x)^ 1, if x > a and x < b; ^ 0 otherwise. (2.22) , This function will be used as the final step in the derivation to set all values outside the screen image to zero. Chapter 2. INTERMODULATION^ 17 line 0 line 263 line 1 line 264 line 2 X' Y^ ^Y'^ Figure 2.1: Television Screen Dimensions We now describe f (x, y) when ft (t) = A t cos(wt t). If we consider the first row of the image, that is, we assume that the CRT is scanning the top line when t = 0 then this line can be expressed mathematically by f (x, 0) = A cos(w s x).^ (2.23) Once the CRT has drawn the first line, it bypasses the second line and begins tracing the third. We must now recognize that the phase at the point x = 0 will no longer be zero, it will be equal to the angle when the CRT is at the rightmost point of the first line, that is, when x = X'. Setting f(X', 0) = 2Ay) gives f (x 2Ay) = A cos(w x x cox X 1 )^ (2.24) It can be seen that until the CRT begins its vertical retrace the intermodulation for each line can be described by the general equation, with integer n, f (x. 2nLy) = A cos(w s x nws X')^ (2.25) After the CRT has completed the vertical retrace it begins to draw the remaining lines in the television image. Starting with the second line from the top of the screen the - 18 Chapter 2. INTERMODULATION^ beam will trace every even line until the image is completely drawn. The phase at the point f (0, Ay) will not be zero but will be equal to the value of the phase at the bottom corner of the image f (0, Ay) = f (X', Y' — 1), this gives f (x, Ay) = A cos(w x x wx(1/1 — 1)X' ^ ) (2.26) The intermodulation impairment can now be represented for each line, by summation over the entire screen. The first set of terms will represent the odd rows of the image while the second set will represent the even numbered rows. The intermodulation carrier beat can be modeled by the following two dimensional function A cos(wx x f(x,Y) 2 AY )rect o ,x(x)rect o ,y(Y) E 8(x — k Ax)6(y — 2j Ay) 3,1c + co x yX' co s X' (Y/ — 1) A cos(wrx^ )rEcto x(x)recto,x (y) 2Ay^20y^ ' > 8(x — kAx)8(y — 2jLy + Ay)^ (2.27) 3 ,k It should be noted that equation (2.27) is considerably more complex than it would be if interleaving did not occur. Another consequence of the interlaced signal is that if we consider the vertical frequency of the intermodulation component we find that this signal is quite sensitive to any changes in the value of wx . This will become more apparent once the Fourier transform of this function has been derived. 2.5 FOURIER TRANSFORM OF THE MODEL We will now study the Fourier transform of equation (2.27). The Fourier transform provides great insight into the relation between intermodulation and the frequency w x . To facilitate the calculation we can state some basic Fourier transform and convolution ^ 19 Chapter 2. INTERMODULATION^ relations : + by + c)) = 271-2 (S(u — a)S(v — b)e i c + 8(u + a)S(v b)e - ") (b — a) (a b) (rect„, b (x)) = (a + b) exp(iu )sinc( u) 2 E 6(u - 2n7r) 2 a(E 6(x ak b)) = ciub a (2.28) 8(x — a) 0 (5(x — b) = 8(x — a —^ where a denotes the Fourier transform and 0 the convolution operator. We take the Fourier transform of each of the products separately in our model, equation (2.27), to produce the expression ) 80.1 co x )(5(v t (f(x, y) ) = 27 2 (8(u — wx )6(v wsX' 2Ay • wxX1 ^)) 2Ay (XYCi ( * )-i(lx.) sinc( 11 -j--( )sinc( 12-9:1 )) 2^ 6. (u 2n7 )6(v m7r )\ Ax^Ay ) n,m wx _r ^ .A + 27r 2 (8(u — cox )6(v ^ )e^2, 2A y -i xiry c4., X'^ `' 4,s ) 6^2,^ ^ + 6(u + co,)6(v 2Ay^ (xyci(q-c+q:^UX s. ^vY )Sin^2 ) lnc( (E , ) (E6(u — n,m 2r7r )8(v — 72211-7 )e —zvAY Ay^Ay ) which gives the full transform of the intermodulation model as N,M = E 272xyci((.--wx-224 (v-4-1-1)*) n,m x sinc((u —^ icesX'(Y 1 —`1) 2nr X s X' mir Y ) )sinc((v w Ax 2 2Ay Ay 2 ) x (1 + e^20y^e N,M i(v--1-nr)AY) + E 271-2xy,---((u+-s+-2t-;)§+(o+*-En) ) n,m (2.29) Chapter 2. INTERMODULATION^ 20 2n7 X^wxX' mir Y sinc((u co z.^Ax ) 2 )sinc((t ^2Ay^y z y- )) , itex X / (1 4 -1) (2.30) X (1^e^2Ay^i(V+ The Fourier transform, as can be seen, is composed of the sum of a countable number of terms. Rather than examining each term in its entirety, we will look at select terms in the equation. By doing this, much insight into the properties of intermodulation distortion can be obtained. Let us consider the case in which n = 0 and m = 0. The first term of interest will be 27r 2 XYC i((14-wx)+(u-^))L.2 ) 3i17,C((li X .^wsX' Y — W s ) — )sznc((v 2 ^) 2,6,y 2 ).^(2.31) This term is made up of a product of very narrow sinc functions ( assuming X is large ) with a single peak at the point (u, v) = (w x , izE), the value of the point will be 2ir 2 XY. This peak depends only on the values of X and Y and so we see that the larger the dimensions of the television screen the larger the height of the peak. Also, since X and Y appear as variables within the sinc functions we see that the larger these values the sharper the peak will become ( the peak approaches an impulse function as X and Y near infinity ). As the frequency of the intermodulation changes, the amplitude of the peak does not change but its position does. In fact, by substituting u for w x we see that v = uX720y is the equation of a straight line. As the frequency changes the peak will move along this line, its slope leaning sharply toward the vertical. The next term of interest w^Y \ X^ X^wx-X' 27r 2 XY^2Ay ) 2 sinc((u — co z.)- )sinc((v ) 2 iw x .30(1"-1) x e^2Ay^c Y ) ) 2L‘y 2 itt c,,,T2L -1 k^20y^w (2.32) also has a single peak at the point (u, v) = (w x , ltl--(;), however, the value of the term at this point, i.e., 27 2 XY exp(iw s X'(Y' — 1)/2Ay), is not solely dependent upon X and Y. Chapter 2. INTERMODULATION^ 21 When both these terms are added the result will be a complex number with magnitude proportional to cos2( o),X'(V 4Ay — 1) ) (2.33) The value of the peak can be as much as 471- 2 XY or as little as zero. Considering that X' and Y' are generally quite large, any small change in the frequency can mean dramatic changes in the magnitude of the peak. The case in which m = 1 is only slightly different, here the magnitude of the two terms will be W x X I (1/1 - 1) sin2(^ 40y^) (2.34) and the origin of the peak will be shifted a distance 7/2Ay from the peaks formed in the = 0 case. As in equation (2.33), changes in frequency will cause the magnitude of the peak to alternate between its maximum, 47r 2 XY, and null. The Fourier transform, then, can be imagined as an series of peaks, where each peak has one of two heights. As the frequency changes each peak will move along parallel lines with periodic variations in its magnitude. All peaks will have a symmetric twin about the origin and the distance between vertically neighbouring peaks will be i-ry . As in figure 2.2, the intermodulation peaks in the Fourier transform appear as a single point in each quadrant. If we look at the area bounded by the rectangleox < u < ts- and —ty v we see that the Fourier transform will always have four peak points contained within this area. These points will form a rhombus with the center at the origin and the distance between two vertical points equal to half the height of the screen. These points do not necessarily have nonzero values, the frequency may be such that the magnitude of two of the peaks will be zero. However, we know that if the symmetric Chapter 2. INTERMODULATION^ 22 27r Ay co 2Ir Ax Figure 2.2: Fourier Transform Showing Intermodulation Peaks peaks have a null value then the other two will be at their maximum. If a peak is not found in one quadrant of the rectangle then one may be found in one of the adjacent quadrants, this neighbour will be at its maximum. 2.6 AUTOMATIC DETECTION USING THE 2 D TRANSFORM - From the above we see that the two dimensional Fourier transform can be used to automatically detect intermodulation impairment. In general, a real image will have a Fourier transform in which all nonzero points are clustered near the origin. An image with intermodulation impairment should have a transform that consists of points clustered about the origin and four strong peaks forming a rhombus somewhere outside this center region. A device may automatically detect the presence of intermodulation simply by looking for this parallelogram of points, for example, a transform similar to that depicted in figure 2.2. This can give a very reliable indication as to whether intermodulation noise is present in the image or not. Another benefit is that knowing the position of the peaks will allow the system to calculate the actual frequency of the intermodulation distortion. Chapter 2. INTERMODULATION^ 23 Of course, there are a few special cases for which the apparatus must be aware. As discussed, the peaks need not have nonzero values and the system must test at least two adjacent quadrants of the Fourier transform. If a peak is not found in the first quadrant then this does not mean that intermodulation is not present. Also, the intermodulation may be very near the origin so that the peaks appear within the cluster of points formed by the real image. In this latter case, the system may not be able to properly detect the impairment. Another problem with using the two dimensional Fourier transform is that the peaks may occur midway between two pixels. If the screen image is large, that is, if X' and Y' are large numbers, then we know that sine functions will be very narrow and each of the four peaks will be similar to an impulse function. A peak occurring midway between two pixels may have a large value but may also be small or even zero at the pixel points. 2.7 AN ALTERNATE RECOGNITION ALGORITHM An alternative method for detecting intermodulation noise involves using the one dimensional Fourier transform on lines of the image. This has several advantages, in particular, since the number of calculations that must be done to obtain the transform in one dimension is much less there will be a dramatic decrease in the amount of time required for the device to process the image. An algorithm that looks at small sections of the image and requires a fraction of the time to calculate has significant advantages. This second algorithm is based on the fact that if the intermodulation is present in the image then it will be present in each line of the image. By looking at the Fourier transform of each line we should have a good indication of whether the image contains intermodulation impairment or not. This may not be as good an indication of the impairment as the two dimensional algorithm but the benefit of faster calculation time should Chapter 2. INTERMODULATION ^ 24 F(u) 0 Figure 2.3: Sample 1-D Detection Algorithm Graph outweigh the slightly less accurate result. Let us define the set of functions which describe the horizontal lines of the image as fi (x) = y) where i = y/Ay. Then let us take the absolute value of the Fourier transform of line i, that is, Fi(u) = If fi(x)exp - 2 "x dxj (2.35) By taking the absolute value of the transform we ensure that the real values and the imaginary values are counted equally, this is especially important since the amplitude of the result is much more important than the separate components or the phase. One may be tempted now to simply say that we can look at the first line only, i.e., Fo (x), to test for intermodulation distortion. But we must remember that we are dealing with an unknown image with or without an impairment of unknown frequency and thus it is impossible to distinguish an intended frequency from an unintended one. If intermodulation is present in the image then the algorithm can detect this by summing the values of Fi (u). If we define F(u) =^Fi(u) (2.36) then F(u) should be a good indicator of the presence of intermodulation. If intermodulation exists then we should expect to see a graph similar to figure 2.3. If the image does not have an intermodulation component then, generally, the function F(u) will be zero or near zero at points outside the origin. This is similar to the case of the two dimensional Fourier transform where most of the nonzero points in the Chapter 2. INTERMODULATION^ 25 transform are concentrated near the origin for physical images. If the image does have an intermodulation component then, hopefully, the frequency is large enough so that the intermodulation peak appears outside the neighborhood of the origin, and away from all other nonzero points. Since points near the origin should be ignored, an appropriate threshold value should be selected such that if a peak is found with a frequency less than the threshold it is assumed to be part of the original image. 2.8 SOFTWARE The detection algorithms have been simulated on computer rather than constructing the monitoring devices, this is more practical until the algorithms have been thoroughly tested. Programs have been written which implement both the simulation of intermodulation impairment and the detection algorithms, as well, several grey scale images have been used. The images are discussed in the next section. To add intermodulation to an image the program add_intermod was written. This program utilizes the Utah raster toolkit, this package reads run length encoded image files and can be run in most UNIX environments. The frequency of the intermodulation impairment to be added is given, in radians, as a command line option. The program adds intermodulation distortion to the image using equation (2.27), being careful to ensure that the pixel values remain between zero and 255. Addintermod prints the signal-to-noise ratio to standard error. As many programs exists already which calculate the 2-I) Fourier transform of an image, no software has been written for this purpose. Since the 1-D Fourier transform algorithm requires more custom calculations, the program iiitermod_detect has been written. This program uses the Utah raster toolkit library and reads the same file format as add_intermod. The program assumes that the image is 512 by 512. and indeed, the fast Chapter 2. INTERMODULATION^ 26 Fourier transform algorithm, see [17}, requires that the image have dimensions which are both powers of two. 2.9 EXPERIMENTAL VERIFICATION Simulation has shown that our methods are effective in determining whether an image has been impaired by intermodulation or not. The peaks formed by intermodulation in the function F(u) or by the 2-D Fourier transform are apparent whether the noise is severe and but only slightly less so if the impairment is marginal. The height of the intermodulation peak will be dependent upon the severity of the impairment, in particular, a larger intermodulation component will produce a higher peak. The image used for experimentation is called Ritukoen. This image is shown in figure 2.4 and is a grey scale image of size 512 by 512. The corresponding two dimensional Fourier transform is shown in figure 2.5. The darker points correspond to values in which the transform is equal or near zero. The bright area about the origin implies that the image contains strong low frequency components, which is typical of most images. Intermodulation impairment with a carrier-to-noise ratio of 25 dB was added to the image, the carrier-to-noise ratio, a measure of noise, is defined in chapter 4. Note the diagonal lines, characteristic of carrier beats, that have appeared in the image shown in figure 2.6. The corresponding Fourier transform is shown in figure 2.7, this image is nearly identical to the transform of the image without noise, figure 2.5, we see the same cluster of points near the origin. The one discernible difference is that four peaks, forming a rhombus, appear in the image. This is as predicted, adding intermodulation produces these points and from their position the frequency of the impairment may be calculated. The Ritukoen image was tested by adding intermodulation of a carrier-to-noise ratio of 43 dB. The Fourier transform of this image, see figure 2.8. shows the same four peaks. Chapter 2. INTERMODULATION ^ 27 Note that the peaks are seen very dimly at the same positions as those in figure 2.7. The graph in figure 2.9 shows the result of applying the 1-D Fourier transform algorithm to the Ritukoen image. The nonzero points near the center, or origin, correspond to low frequency components in the image. Any intermodulation impairment will appear as a pair of peaks away from the center. This graph correctly shows that intermodulation is not present in figure 2.4. In figure 2.10 and figure 2.11 the 1-D Fourier transform algorithm has been applied to the Ritukoen image with varying degrees of intermodulation distortion added. The first graph, figure 2.10, was produced from the image with a carrier-to-noise ratio of 25 dB. Note that the intermodulation peaks appear symmetrically about the origin and are large indicating that the intermodulation impairment is very severe. The second graph, figure 2.11, was produced from an impaired Ritukoen image in which the carrier-to-noise ratio was 43 dB. The intermodulation peaks are much smaller in this latter case, showing that the impairment is not significant ( but may still be visible in the image ). Other example images have been tested with good results. The first algorithm produces a trapezoidal set of peaks surrounding the origin, the distance being dependent upon the intermodulation frequency. The second algorithm produces two solid peaks about the center which can also be easily detected. The latter should be the preferred method since fewer calculations are required, in particular, there will be log e N/N = log e 512512 fewer computations, see [17]. Chapter 2. INTERMODULATION ^ Figure 2.4: Ritukoen Image Without Intermodulation Noise 28 Chapter 2. INTERMODULATION ^ Figure 2.5: 2-D Fourier Transform of Ritukoen Image Without Noise 29 Chapter 2. INTERMODULATION ^ Figure 2.6: Ritukoen Image With Intermodulation Noise - 25 dB 30 Chapter 2. INTERMOD ULATION ^ Figure 2.7: 2-D Fourier Transform of Ritukoen Image With Noise - 25 dB 31 Chapter 2. INTERMODULATION ^ Figure 2.8: 2-D Fourier Transform of Ritukoen Image With Noise - 43 dB 32 3e+06 "no intermodulation" 2.5e+06 2e+06 1.5e+06 le+06 500000 100^200^300 ^ Figure 2.9: 1-1) Fourier Transform of Ritukoen Image Without Noise 400^500 3e+06 "25dB intermodulation" 2.5e+06 2e+06 1.5e+06 le+06 500000 0^1 00 ^ 200 ^ 300^400^500 Figure 2.10: 1-1) Fourier Transform of Ritukoen Image With Noise - 25 dB 3e+06 "43dB intermodulation" 2.5e+06 2e+06 1.5e+06 le+06 500000 I^ I^ I 100^200^300^400^500 Figure 2.11: 1-D Fourier Transform of Ritukoen Image With Noise - .13 dB Chapter 3 HUM An important type of impairment, according to many cable subscribers, is hum modulation. This is primarily due to the fact that hum produces a rather annoying, slowly moving band that can be very distracting to the viewer. For cable companies, this impairment is of interest as it usually results from within the cable network and affects a large number of homes. 3.1 CHARACTERISTICS AND CAUSES OF HUM Hum is characterized by faint hands moving up the screen. The bands will move slowly, at a rate of the height of the screen every half dozen seconds. The number of bands which appear on the screen at one time has a direct relation to the frequency of the impairment. There are two main types of hum, classified by the different frequencies in which they exist. The first kind, called 60 Hz hum modulation, is characterized by a single band on the screen, see figure 3.14. The band moves up the screen, another band will reappear at the bottom only when the previous band has disappeared at the top. The second type of hum, called 120 Hz hum modulation, consists of two bands moving up the screen. A new band will appear at the top only when the top band disappears, so that, two bands always appear somewhere on the screen. To determine some of the characteristics of hum we may visualize how the impairment is formed as an image on the television screen. The television scans an image by interleaving the signal, that is, it draws every other line of the image until it reaches 36 Chapter 3. HUM^ 37 the bottom. The remaining lines are drawn lines after the CRT has returned to the top of the screen. This means that, every second, the CRT will scan the entire television screen 60 times. We know that in the case of 60 Hz hum modulation, there will be 60 cycles completed every second, two cycles will appear in each image that is drawn on the screen. Consequently, if the hum produces a band at a particular point on the screen for one image then this band will appear at the identical point when the CRT next scans the field. The frequency of the hum is not precisely 60 Hz so this synchronization is not exact. This is particularly apparent by observing that since the hum produces a band that moves up the screen, its frequency must be slightly larger than 60 Hz. There are several causes of hum modulation. The first, which only operates at a frequency of 60 Hz, is due to a defective TV set power supply. In this case, the problem will affect the local subscriber and will not be present on neighbouring televisions. A defective TV power supply must be fixed by the subscriber himself, and so is of little interest to the cable company. Other possible causes of hum noise are an overloaded power supply or low AC power voltage in the cable distribution system, both of these problems may appear in the cable network. 3.2 GENERAL APPROACH TO HUM RECOGNITION The aim is to develop a system that will monitor the cable signal for the presence of hum. Once the system detects hum, it should inform the cable company. There are several difficulties in doing this automatically, in particular, since hum is a low frequency impairment, it is not easy to distinguish the hum from the actual image. The detection system cannot simply study a small section of the image, the pertinent information may be contained over the entire picture. The monitoring devices are, therefore, forced to consider the complete image in the 38 Chapter 3. HUM^ calculations. It is possible that even this will not be sufficient information, the original image may possess a significant component at the 60 Hz or 120 Hz frequency. In this case, further information may be obtained by comparing properties of the image with characteristics of preceding images. The approach that we will take will look for changes in the image due to the moving band. Since the eye can more readily distinguish hum by the upward movement, it seems reasonable that this is the best approach for an automatic detection system as well. The algorithm will first be developed from very general assumptions. Once the theory is formed we can look at more specific examples, in particular, the case in which the hum modulation is a sinusoidal wave. This approach should give a clearer understanding of the fundamental aspects of the theory. 3.3 THE THEORY OF ORTHOGONAL FUNCTIONS Let us introduce some results from the theory of orthogonal functions, a theory that is similar to matrix algebra, see [6]. An inner product is defined, in a general linear space, as a scalar function of two elements of the space satisfying certain axioms, in particular, to each pair f and g in the linear space there is a number (f,g), satisfying the following: (f, f) > 0^for every f (3.37) (f, f) = 0^if and only if f = 0 (3.38) ( f, g) =- (g, f)^for every Lg. (3.39) (af^3g,h) = a(f,h) + 3(g, h) (3.40) + 3(f. h) (3.41) (Lag + /3h) = ce(f, g) These properties of an inner product imply little in terms of the exact definition of the function, the inner product may be a sum, an integral or some other relation. For Chapter 3. HUM^ 39 the purposes of this thesis we will assume that the inner product will always be of the form I f(x)g*(x)r(x)dx^ (3.42) where r(x) is a weight function with a positive value for each point in the domain. Two functions, f and g are said to be orthogonal if and only if they are both nonzero and (f, g) =0 (3.43) The functions are orthonormal if the additional relations are true (f, f ) =1 (3.44) (g,g) =1 (3.45) and Note that if f and g are orthogonal then f /If 1 2 and g/ 1g1 2 are orthonormal. The number of linearly independent functions which can be orthonormal to each other is equal to the dimensions of the inner product space. For the function sets that we will be considering the dimensions are countable, that is, the space is spanned by a countably infinite set of functions. We state the following theorem. Theorem 1 If r 1, 2 ^ On form an orthonormal basis for an n-dimensional linear space V, then every f in V is of the form f=E k= 1 where a k = (f, ch k ). akok ^ (3.46) 40 Chapter 3. HUM^ 3.4 STURM-LIOUVILLE THEORY The Sturm-Liouville Theory introduced below provides a very powerful method in which an arbitrary periodic function can be detected in a television signal, see [6]. Any differential equation that can be written as dy c7;(P(x).-c6) q(x)y + r(x)y 0 (3.47) is called a Sturm-Liouville equation, see [6]. The functions p, q, and r must be real valued and continuous in the interval a < x < b, p must be continuously differentiable over the same interval, and both p(x) and r(x) must be positive for all values in the domain. These assumptions do restrict the equation somewhat, however, we can see that by differentiating the first term and dividing by p(x) y„ p'(x)y' q(x)y r(x)y = 0 p(x) p(x) p(x) ) (3.48) that the equation is still fairly general. Depending upon the differential equation, the parameter A may have a somewhat obscure significance or it may have a more physical interpretation, such as being proportional to either the frequency or angular velocity of the system. It should be noted that equation (3.47) is not really a single differential equation. when the parameters p, q and r have been chosen the equation will have a separate solution for every value of the unknown constant A. The Sturm-Louville boundary value problem is the study of nonzero solutions of equation (3.47) that satisfy particular boundary conditions, that is, the solutions must satisfy given relations at the endpoints x = a and x = b. The solutions to equation (3.47) are called eigenfunctions, and the corresponding values of A are called eigenvalues. In general, each boundary value problem will have a nontrivial solution for only a discrete values of A, the number of eigenvalues will form a countable set. ^Ly Chapter 3. HUM^ 41 Let us introduce the linear differential operator L, which will significantly simplify the statement of the Sturm-Liouville boundary value problem. If we define = y —(p(x)— ) q(x)y^ dx (3.49) then the differential equation, equation (3.47), can now be shortened to Ly Ary = 0.^ (3.50) Of the two requirements that the boundary conditions must satisfy, the first is that the class of functions satisfying the problem must be a member of the inner product space. The second requirement is that the boundary conditions must be chosen such that the operator L is self-adjoint in the space. An operator L is self-adjoint if g) = Cf, ^ (3.51) Consequently, the boundary conditions should satisfy the condition ^P(b)(i (b).9(b) — .9/ (b)f (b)) P(a)( (a)g (a)^.C 1 (Of (a)) = 0 ^ (3.52) Some very useful properties result if L is a self-adjoint operator. In particular, the following lemmas will be stated without proof. Lemma 1 Every eigenvalue of a self adjoint operator is real. - Lemma 2 Eigenfunctions corresponding to distinct eigenvalues of a self-adjoint operator are orthogonal with respect to the weighting factor r(x). The lemmas imply that if f and g are solutions to the Sturm- Liouville boundary value problem then their corresponding eigenvalues will be real and. assuming f and g are not equal, the inner product, defined above with weighting function r(x), gives (f,g) = 0. The following theorem, due to Sturm and Liouville. will also be stated without proof. Chapter 3. HUM^ 42 Theorem 2 (Sturm-Liouville) If the boundary conditions defining the space C 2 [a, b], where C 2 denotes the set of functions with continuous second derivatives, are such that L is self-adjoint in C 2 [a,b], that is, (L f, g) = (f, Lg) for all functions f and g in the set C 2 [a, b], then an infinite sequence of eigenfunctions exist 011 021 031 ••• (3.53) which are mutually orthogonal with weighting function r(x) f b r(x)o i (x)oz(x)dx 0, wheneverj k (3.54) Each bounded function f integrable over [a, b] can be expanded in a series f (x) = 01(x) + C2¢2(x) + C 303(x) + (3.55) which converges in the mean to f. If f is of class C 2 [a,b] then the series also converges pointwise, and additionally, the sequence converges uniformly and absolutely to the function f, throughout the interval [a, h]. The reason for insisting that r(x) be a positive function in the boundary value problem should now be clear, otherwise the integral f ab f(x)g*(x)r(x)dx would not satisfy the requirements of an inner product. It should also be apparent why the function p(x) must be positive, otherwise the Sturm-Liouville problem would not even be a differential equation. Finally, as the problem is given, the existence theorem of linear differential equations can be applied to ensure that the solution remains bounded throughout the interval a < x < b. There are several applications of Sturm-Liouville boundary value problems that are of interest. For example. the Fourier series comes from solving the set of differential equations y" + Ay = 0^ (3.56) 43 Chapter 3. HUM^ while the solution of the Bessel equation x 2 y" xy' x 2 y = Ay^ (3.57) gives the well known Bessel functions, which consequently, form an orthogonal set of functions. Likewise, the solutions to the Legendre equation, (1 — x 2 )y" — xy' + Ay = 0^ (3.58) called Legendre polynomials, form a orthogonal set of functions with respect to the weight function (1 — x 2 ). In fact, by putting any differential equation into the form of a Sturm-Liouville boundary value problem we know that the solutions form an orthogonal set of functions. This fact will be used to derive an algorithm which recognizes hum impairment. Although the Sturm-Liouville theorem states that the solutions of the diffential equation form mutually orthogonal functions, it is not clear from this, whether given an arbitrary function h(x), a function basis can be found in which h(x) is a basis element. The following original corollary partially answers this question. Corollary 1 If h(x) is a positive function in C 2 with period b— a then an orthogonal set of functions can be found in which h(x) is an element. Proof To prove this lemma we only need to show that there exists a Sturm-Liouville boundary value problem in which h(x) is a solution. By setting p^1^ h"(x) g^h(x)^ r = 1^ (3.59) (3.60) (3.61) with boundary conditions y(a) = y(b) and y'(a) = y'(b) we see by simple substitution that if A = 0 then h(x) is the solution. All other solutions to this Sturm-Liouville Chapter 3. HUM^ 44 boundary value problem are orthogonal to h(x). In addition, the proof of this corollary specifies the precise form of the Sturm-Liouville differential equation so that h(x) will be an eigenfunction. 3.5 HUM RECOGNITION USING ORTHOGONAL FUNCTIONS If it is assumed that the image resulting only from the hum is described by the function H(x, y) and the original unimpaired image by F(x, y) then the function representing the television image is defined as the sum of the two functions G(x, nAy) = F(x,nAy) H(x, nzy)^ (3.62) with 0 < x < X and 0 < nAy < Y. We shall map H(x, y) into a one dimensional function by taking the even lines of H(x, y) and arranging them progressively one next to the other h(x nAyX) = H(x, nAy)^ (3.63) as shown in figure 3.12. After mapping the even lines of H(x, y) to h(u), the set of odd lines are appended. The domain of the one dimensional function h(u) is NX = XY/Ay. We make similar definitions for Au) and g(u). Assume that an inner product space and a countable set of functions O i (x) have been defined where, for i j, we have f XY (c5i,^) =^4i(17)0;(X)r(X)d-X = 0 (3.64) and where r(x) is the positive weight function. If the functions f(x) and h(x) are bounded and integrable over the interval [0, NX] then this ensures that both functions, as well as g(x). will have a series expansion 45 Chapter 3. HUM^ F x,0) F x,2Ay Y^ Figure 3.12: The Television Screen In Terms Of A 1-D Function which converges in the mean. We can expand f (x) in terms of the orthogonal function .0o, 01,^•••1 f(x) = ^ n>0 fnsbn(x ^ ) (3.65) and similarly, h(x) and g(x) are expanded in terms of the respective h n 's and g n 's and by O n s, ^ h(x) = En>o hnOn(x) g(x) = En>o nOn(x). ^ (3.66) (3.67) A system is able to automatically predict whether an image contains hum or not if it can determine whether h(x) is present. Although the magnitude of h(x) is not known, it can be guessed by using Parseval's theorem, 1. xY Ih(x)1 2 r(x)ds = E ih r,12^ (3.68) n>0 which relates the magnitude of h(x) to nonzero values of h r . The monitoring devices' Chapter 3. HUM^ 46 prediction would be based on the fact that the larger the magnitudes of the h a 's the more severe the hum is. Since g(x) is known, the value of g n is calculated using the relation g„ = (g, cb,„). If the original image, f(x), were known then the hum could be found by the equation hn = gn — fn•^ (3.69) However, preferably, the system should work independently of any knowledge of the original image, and so it is assumed that the value of f„ is an unknown. Fortunately, we can assume that the value of fn is relatively constant in time. Only in cases where the background changes abruptly, for example, when the camera moves to a different vantage point, will there be any significant change in the original image. We will guess that, in most cases, each successive television picture is extremely similar to the previous picture, and scene changes which cause fn to change will occur only once every half dozen seconds or so. By taking the inner product of the consecutive frames g3 (x), where gj ( ) represents the jth frame, with the orthogonal functions O n (x) the variation of the inner product as a function of j can be plotted. This gives (g. h On) =^On) + NX ti NX 0^h j( )07,(x)r(x)dx ^ (3.70) k I^h i (x)0:(x)r(x)dx^ (3.71) where we assume that (fi , O n ) is approximately equal to the constant k. If the hum, h ; (x), is known then the curve (h i . O n ) versus j can be calculated. By calibrating the monitoring devices with the values that are expected, the system can make a reasonably accurate prediction as to whether hum is present in the image or not. If the values recorded for the function (gi, O n ) minus a constant are proportional to the calibrated results then the television picture contains hum impairment. If the values 47 Chapter 3. HUM^ minus a constant are not proportional and particularly if (g3 ,¢„) itself is a constant, then hum impairment is not present in the image. The most important functions (g3 , 6,), for different n. to be studied are those which are nonconstant when hum modulation is present in the image, and consequently, the orthogonal basis in which the g(x) is represented becomes very important. The fewer inner products that need to be studied the faster the algorithm can be calculated and the more accurate the results will be. In particular, it is preferable to use a basis in which the hum h(x) is proportional to only a single element rather than one in which the hum must be represented by an infinite series. As described above. the Sturm-Liouville theory of orthogonal functions is perfectly suited to finding othogonal functions. Although factors may indicate that the Fourier, Bessel or another well-known series may be optimal for hum recognition, it is advantageous to be able to use the more general theory to obtain the best possible basis for hum recognition. 3.6 APPLICATIONS VIA FOURIER SERIES Let the hum be defined as a sinusoidal function and, to account for the upward motion, let the hum be time dependent with frequency w xlr^. hj(x) = A cos(-wi)^ (3.72) The Fourier expansion of h j (x) is h • (x) =^ ,^ x7r al sin( — )^ X (3.73) where ci = A cos(u.)j)^ (3.74) and d i = —A sin(wj)^ (3.75) 48 Chapter 3. HUM^ In this case, the optimal othogonal basis to represent g( x) is the Fourier series. If the original television image can be expressed mathematically as a piecewise smooth function then the said function is guaranteed to have a Fourier expansion fj(X) = E(a n cosk „^nx7r „ + o r, sin(— )) 11X 7r X X (3.76) We will assume that f.7 is approximately constant so that the numbers a n and b n have no dependence on the integer j. The image that is received by the detection devices will be the superposition of these two function, that is, g 3 (x) = f 3 (x) + h 3 (x). As the algorithm suggests, the inner product of this sum should be taken with the relevant basis functions, (g(x), cos(5-)) = a n + A cos(c.uj ) (3.77) (g(x), sin( y)) = bn — A sin(u)j) (3.78) If hum is present in the image then a sinusoidal curve will be obtained when the inner product values are plotted. If the curve forms a horizontal line, or some other shape, then hum has not been added to the signal. 3.7 SOFTWARE To experimentally verify the algorithm described in section 3.5 several software programs have been written. As the facilities currently do not permit several images to be captured in succession, the motion of the hum has also been simulated via software. The hum function will be assumed to be a cosine wave, this will coincide with the example in the previous section, and so if hum modulation is present in the image we should expect to see sinusoidal curves. The first program, remove_block, utilizes the Utah raster toolkit to read run length encoded image files. Remove_block reads an image and sets all the pixels within a 128 Chapter 3. HUM^ 49 by 128 area to black, the new image is written to standard output. The position of the blackened square can be given on the command line by specifying the top rightmost coordinates. By creating a series of images, each using remove_block with a slightly different offset, a set of similar pictures is obtained. When these images are shown rapidly in succession, the viewer sees an image with a small black box moving about the screen. This should simulate the motion of a sequence of television images adequately for the experiment. To add hum impairment to an image, a program, called add_hum, was written. This program reads Utah raster toolkit images and adds hum with a carrier-to-noise ratio of 25dB. This program is almost identical to add_intermod, discussed in chapter 2, except that the frequency of the cosine that is added is fixed while its phase must be given on the command line. The program called hum_detect implements the hum detection algorithm discussed in the section 3.6. This program, which reads images files compatible with remove_block and add_hum, prints the resulting data to standard output. If the data, once graphed, shows a curve similar to a sinusoid then the algorithm has predicted the existence of hum in the sequence of images. 3.8 EXPERIMENTAL VERIFICATION To experimentally verify the hum recognition algorithm the image file Aliens, shown in figure 3.14, has been used. In this figure, it may be difficult to see but the image has been distorted with hum modulation with a carrier-to-noise ratio of 25 dB, this appears as a slight brightening near the top of the screen. The hum at this severity is much more visible when viewed as a moving series of images. A series of images has been created by setting a small area to black at different offset points in the Aliens picture. Showing these images in succession simulates a moving Chapter 3. HUM^ 50 Frame 1 Frame 5 Frame 9 Frame 13 Figure 3.13: Experimental Frames Used by Hum Detection Algorithm image. Figure 3.13 illustrates this, the block is moved vertically from the top of the screen in frame 1 to the bottom of the screen in the last frame, frame 13. Two separate experiments were performed on the image. In the first, the black square was moved in a horizontal direction, while in the second, the black was moved in a vertical direction. The two sequences of images were tested according to the algorithm, by taking the inner product of the frames with cosine and sine functions. The results obtained from moving the square in a horizontal direction are shown in figure 3.15 and figure 3.16. In the first, figure 3.15, the inner product of the image with the cosine function is graphed. The first line, called horizontal.cosine, shows the result when the sequence of images consists of the moving block where no hum has been added. As expected this forms a curve which is very unlike a sinusoid, in fact, the result is nearly Chapter 3. HUM^ 51 a straight line. The second curve, called hum.cosine, shows the result when the block is held fixed with the image impaired, a constant image with a moving band of hum. As predicted, this forms a curve which strongly resembles a cosine. Finally, the last line, called hum.horizontal.cosine, shows the result of the moving square where hum has been added. The curve also resembles a cosine, indicating that the algorithm has made a correct prediction. The second graph, figure 3.16, shows similar curves with the inner product taken with a sine function rather than a cosine function. The second experiment, in which the black square is moved vertically, is shown in figure 3.17 and 3.18. The graphs show the three curves produced by a moving image without hum, a constant image with hum and a moving image with hum. These results are obtained using the inner product of the images with the cosine function in figure 3.17 and a sine function in figure 3.18. It should be noted that although the data does indicate that the algorithm has successfully predicted the presence of hum modulation, the results are not as good as in the first experiment. This is due to how the image is mapped into a one dimensional function g(x), the algorithm is more sensitive to vertical changes in the image than to horizontal changes. Chapter 3. HUM ^ Figure 3.14: Aliens Image With Hum And With A Block Removed 52 "horizontal.cosine" "hum.cosine" "hum.horizontal.cosine" 30000 20000 10000 a) ty) -H 0 0 4J o o -10000 -20000 -30000 0 2 4 6^8^10 Frame number 12 14 Figure 3.15: Aliens Image With Horizontal Motion - Cosine Inner Product 16 18 "horizontal. sine" "hum.sine" "hum.horizontal.sine" 30000 CD ti C" 20000 10000 ro (41^ 0 0 4J o 0^-10000 1-1^ -20000 -30000 0 2 4 6^8^10 Frame number 12 14 Figure 3.16: Aliens Image With Horizontal Motion - Sine Inner Product 16 18 "vertical. cosine" "hum.cosine" "hum.vertical.cosine" 30000 20000 - (1 ro^10000 a) t3) ro (4-1 0 0 4J '0^-10000 • -20000 -30000 0 2 4 6 8^10 Frame number 12 Figure 3.17: Aliens Image With Vertical Motion - Cosine Inner Product 14 16 18 vertical. cosine" "hum.cosine" "hum.vertical.cosine" 30000 w co 0 0 20000 10000 t7) 'ti 0 0 -p E -10000 -20000 -30000 0 2 ^ 4 6^8^10 Frame number 12 14 Figure 3.17: Aliens Image With Vertical Motion - Cosine Inner Product 16 18 Chapter 4 SNOW NOISE Television impairments are classified as either coherent or non-coherent noise. A coherent impairment, such as intermodulation carrier beats or hum modulation, produces recognizable patterns which tend to be very annoying. Snow noise is an example of a non-coherent noise, this impairment arises from random variations in the television signal which become apparent when the signal is very weak. The quantum fluctuations in the cable signal which cause snow noise produce a uniform effect over the entire screen, adding a random Gaussian value each pixel. Although snow noise can occur due to poor weather and other external conditions, it is important that cable companies monitor their networks for bad connections or faulty wiring that may also produce this impairment. 4.1 CHARACTERISTICS AND CAUSES OF SNOW Snow noise is so named from the snowstorm effect that it creates on the screen. The statistical nature of this impairment will affect the image and may also affect the sound signal, the sound will become noisy and difficult to distinguish. Snow is a serious type of impairment to cable companies, their subscribers expect the signal they receive will produce a strong and clear picture, free from noise. If snow noise is caused by the television set itself, for example, by a faulty television set RF amplifier or a broken television matching transformer. then the impairment will only affect the single television. If snow noise is caused by problems in the cable network, Chapter 4. SNOW NOISE^ 58 such as due to a badly coupled "F" type connector or to faulty cable splices, then this will affect a large number of viewers and must be repaired by the cable company. There are conditions, such as poor weather, in which the addition of snow noise to the signal is beyond the control of the cable company. To guarantee that snow noise is not produced by a weak point in the cable network, the cable company should carefully check their connections and try to repair all problems as soon as possible. 4.2 CARRIER-TO-NOISE RATIO The most common measure in which the severity of noise is reported is the signal-tonoise ratio. This value is a measure which relates the strength of the original signal in comparison to the noise that has been added. This ratio is defined as x 2^/ 101og 10 ( ^ ) dB (4.79) X noise where x„,i„ is the amount of noise in the picture and x s i 9 „/ is the original signal strength. A more common method to measure the amount of impairment in the television signal is the carrier-to-noise ratio, see [8]. This measure is similar to the signal-to-noise ratio, being defined, in dB, as signal 10log1o(1.6 2^— X 2^) dB (4.80) Xnoise where x signai is always set equal to 256. The carrier-to-noise ratio, or C/N ratio, will be equal to the signal-to-noise ratio plus 20 x log 10 (1.6) 4.08 dB. The carrier-to-noise ratio should ideally be 45 dB or greater to ensure that the noise is not visible to the viewer. Snow may be barely visible when the C/N ratio is greater than 40 dB and the impairment will he especially objectional if the C/N ratio is below 40 dB. Chapter 4. SNOW NOISE^ 59 4.3 FOURIER TRANSFORM OF SNOW NOISE As described above, snow noise is characterized by a uniformly fine disturbance over the entire screen, produced by random fluctuations in the pixel values. These quantum variations can be considered as the result of several high frequency components which will appear as points interspersed throughout the Fourier transform. The number of calculations that must be performed to derive the transform indicates that a faster detection algorithm should be developed. 4.4 SUBJECTIVE RECOGNITION OF SNOW IMPAIRMENT Several experiments have been done which use a subjective approach to the problem of recognizing snow noise, see [3]. For example, a picture shown to a number of human subjects is rated as to the quality of the image. Typically, the subject is asked to rate the image under several classifications, such as, excellent, good, fair, poor and bad. The number of categories is best limited to a small amount since it was found that the subjects become confused if there are too many image classifications. Although the subjective approach is contrary to the concept of automatic recognition, it is important to remember that one of the best approaches for developing detection algorithms is to mimic the methods used by human subjects. Unfortunately, humans are better able to relate the image or parts of the image with their own knowledge of the world when determining whether snow exists. Since computer algorithms are unable to do this, an alternate approach has been adopted. 4.5 AUTOMATIC RECOGNITION OF SNOW NOISE The snow recognition algorithm that will be described below relies on the fact that if an image contains random noise then many individual pixels will assume values quite Chapter 4. SNOW NOISE^ h k (i - 1 ,i hk(i,i 60 hk(i+1,j- 1) h k (i — 1, j) hk(i,i) hA +Li) h k (i —1,j +1) hk(i,j +1) h k (i + 1, j + 1) Figure 4.19: Pixel Neighbourhood For Snow Detection different from their neighbours. An image which does not contain snow should be smooth, causing these variations in pixel values to be far less numerous. This will not be true at edges and regions with texture but the variations due to these effects should be much less than the contribution caused by snow as the latter affects the entire screen. Consider an image which is represented by the function f'(;, j), where i and j assume integer values. Let the noise be defined by the function random Gaussian distributed n(i, j). As the noise is added, this defines the function {0,^if f(i,j) + n(i, j) < 0; Rid = Pi, j) + n(i, j), if f(i,j)+ n(i,j) < 255;^(4.81) 255,^otherwise: which is the superposition of the original image and the snow noise and where a threshold has been used to ensure that the values of f (i, j) remain within predefined bounds. Chapter 4. SNOW NOISE^ 61 The image may contain areas which the algorithm could assume were caused by snow noise, although the human subject, using knowledge of physical objects, will not. For example, an image which contains water waves, a forest or any object with a great deal of texture, may easily be mistaken for an impaired picture by the computer algorithm. To circumvent this, we will subdivide the image into blocks of size 64 x 64. The algorithm will not consider the noisiest sections in its predictions, all decisions will be based upon the smoothest area. This should not affect the accuracy of the algorithm since if snow is present the impairment will be uniform over the entire image. Once the image is subdivided, this defines new functions h k (i, j) which represent a different block for each integer k. The algorithm considers each pixel, called hk(i,j), and compares it to the eight neighbouring points, see figure 4.19. The pixel is called isolated if its value is significantly different from each of the other points. Let us define a new function which is the smallest difference of all the comparisons abs[hk(i —1, j —1)— hk( 1 , j)] abs[hk(i, j — 1) — hk(i,j)] abs[h k (i +1, j —1) — hk( 1 , j)] = min abs[hk(i —1, j) — hk(i,j)] abs[hk(i +1, j) — hk(i,j)] ^ (4.82) abs[h k (i —1, j + 1) — h k (i, abs[hk(i, + 1) — hk(i,j)] abs[hk(i +1, j +1) — hk(i,j)] The value of hk(i, j) will be large if and only if the pixel assumes a value very different from any of its neighbours, that is, if the pixel is an isolated point. If a threshold is applied so that the smaller values of hk(i, j) are set to zero then a point at which hk(i, j)^0 represents an area that has probably been severely affected Chapter 4. SNOW NOISE ^ 62 by snow, the more nonzero points imply the stronger the snow impairment. We can represent this simply by summing each value in the block k h/k (i, j). if hVi, j) > 8 Pk =^ t o { 0,^otherwise (4.83) where 8 is an arbitrary threshold value. Finally, in order to base the prediction on the smoothest block in the image the minimum value of the numbers pk is taken, we call this value P P -= min{Pk}.^ (4.84) The device will predict whether snow is present in the image by comparing P with a previously calibrated threshold value. This algorithm will ignore areas in the image that are greatly detailed, such as forests and lakes, unless, as is not true in most physical images, these areas affect every part of the image. From experimentation a threshold value is selected, if P is greater than this value then snow is declared present in the image. 4.6 MODIFICATIONS TO THE DETECTION ALGORITHM Many of the devices which are used to capture an image from the television signal to the computer, apply a low pass filter in the horizontal direction when the image is captured. This means that the variations in the horizontal direction of the image are smoothed out and when the image is studied by the snow detection algorithm, the pixels which originally had large variations with its neighbours will no longer be isolated points. It is necessary to look at how this may affect the snow detection algorithm discussed above. The algorithm depends a great deal upon being able to isolate those pixels which are very much different in value from their neighbours, where the assumption is that this will be a good indication as to how much noise is inherent in the image. However, ^ Chapter 4. SNOW NOISE^ 63 this will no longer produce a satisfactory result if the image is low passed filtered in one direction. The points that were isolated will not remain so and consequently the detection algorithm will fail to produce an accurate prediction. This problem can be solved by a simple modification to the function P k . If the algorithm does not test the two horizontal neighbours, but only the remaining six points, then even if the image is low passed filtered the prediction should not be affected. This can be described mathematically by redefining the function Pk as abs(hk(i —1, j — 1) — h k (i,j)) abs(h k (i,j —1)— h k (i,j)) abs(h k (i +1, j — 1) — h k (i, j)) = min^ abs(h k (i —1, j +1) — h k (i,j)) (4.85) abs(hk(i,j + 1) — hk(i,j)) abs(h k (i +1, j +1)— h k (i,j)) 4.7 OTHER POSSIBLE DETECTION ALGORITHMS Other automatic detection algorithms have been studied. Of course, possibly the simplest to implement would be to study the quality of the signal (luring the horizontal and vertical retrace times using test signals. This, however, turns out to be impractical as the horizontal retrace time is too short to produce any useful information and the vertical retrace time, though longer, is used for other purposes. There are three lines during the vertical retrace in the NTSC standard which are devoted to a test signal. These could be used to detect snow noise, however, three lines are not sufficient to detect the snow that may be present. Chapter 4. SNOW NOISE^ 64 4.8 SOFTWARE Software has been written to experimentally test the snow detection algorithm discussed in Section 4.5. The first program, called add_snow, uses the Utah raster toolkit and correspondingly reads run length encode images files. Add snow will read the image, add a random Gaussian noise to each pixel and print the carrier-to-noise ratio to standard error. The second program, called snow_detect, is also compatible with the Utah raster file format. This program applies the snow detection algorithm described previously, that is, it subdivides the image into blocks, calculates the value of pk for each section and prints the minimum P. 4.9 EXPERIMENTAL VERIFICATION To verify the algorithm experimentally, several public domain images have been used. These images, listed respectively in figures 2.4 and 4.20-4.23. are called Ritukoen, Data, Gorby, Oldmill and Fiji. An example of snow noise, with a carrier-to-noise ratio of 25 dB, is shown in figure 4.24, this illustrates how a moderate amount of snow can severely limit the clarity of the image. To experimentally test the effectiveness of the detection algorithm, thirty different levels of snow impairment have been added to each image. Each level is defined by a different value of x„ i „, where x„ i „ is related to the carrier-to-noise ratio according to the graph in figure 4.27. As defined in section 4.5, P is the measure, generated by the algorithm, of the severity of the impairment. The relation between the value of P to the amount of snow in the image is shown in figure 4.25. each curve in the graph represents the results produced by a different image. The curves are shown in the same graph so that the results can be compared. For the algorithm to be effective the curves generated for different images Chapter 4. SNOW NOISE^ 65 should be similar, this way the value of P can produce an estimate of the carrier-to-noise ratio in the image. The data obtained has been enlarged near the origin and shown in figure 4.26, this graph is used to determine an effective threshold value. We see that if Snow is not present when P < 800 { Snow is present^when P > 800 (4.86) then the algorithm will detect snow noise if x„, „ is greater than 7 or equivalently if the carrier-to-noise ratio is less than 35 dB. From this, we deduce that the detection algorithm will produce accurate predictions for moderately to severely impaired images. Chapter 4. SNOW NOISE ^ Figure 4.20: Data Image Without Snow Noise 66 ti 00 <.C) ^ 35000 ^"data" ^ "fiji" "gorby" ^ "oldmill" ^ "ritu koen" 30000 - / 25000 20000 15000 • / • 1 000 0 • 5000 5 10 15 20 25 x noise 30^35^40^45^50 • Figure 4.25: Snow Noise Predictions b ti ^ 7000 "data" 6000 "gorby" ^ "oldmill" ^ p ritukoen"/--- 5000 4000 3000 2000 1000 0 0^2^4^6 8 x noise 10 Figure 4.26: Snow Noise Predictions - Enlargement Near The Origin 12 14 0 -H 4J ro cn -H 0 z 0 4J a) $-1 co Figure 4.27: Relation Between X_noise And Carrier To Noise Ratio Chapter 5 CONCLUSION Many cable companies strive to offer the best possible service to their customers, in particular, they take great pains to ensure that the signal they send through their network remains unaffected by the many common television impairments. Nevertheless, the quality of the television signal has been poorly rated by many viewers. Since errors in the network can be very difficult to detect most cable companies are unaware of the problem until an angry viewer complains. An automatic detection system which would continually monitor the signal at many points in the network is proposed. The device would determine whether an impairment is present, and if so, what type of noise it is. Furthermore, the device would preferably operate under conditions in which it does not know what the original image looks like, that is, a test signal would not be available for the device to calibrate its results. There are several types of noise, including snow noise, ghosting, crossmodulation, intermodulation, hum and diathermy. This thesis has discussed and developed detection algorithms for the three impairments that have been rated most significant by our local cable company, that is, intermodulation beats, hum modulation and snow noise. 5.1 INTERMODULATION BEAT PRODUCTS The first type of television impairment that was studied was the intermodulation beat product. It was shown that this noise is closely related to crossmodulation and how both impairments depend upon a superposition of signals with different frequencies. 74 Chapter 5. CONCLUSION^ 75 Intermodulation comes in several forms, picture carrier beats, low frequency colour beats and composite triple beat. In order to detect intermodulation distortion, two algorithms were proposed. The first uses the two dimensional Fourier transform of the image, it was shown that four peaks appear in the transform when intermodulation is added. By detecting these points it is possible to accurately deduce the presence of intermodulation. The second method that was discussed uses the one dimensional Fourier transform taken over each horizontal line in the image. The graphs that were produced from this method showed that if intermodulation is present then the spectrum contains two sharp impulses. These peaks can also be detected automatically. 5.2 HUM Hum modulation was also studied. This is a low frequency distortion, having a frequency of either 60 Hz or 120 Hz, that appears as light or dark bars moving slowly up the screen. This impairment is caused by a defective TV set power supply or an overloaded power supply in the cable network. To discuss hum modulation as generally as possible the theory of orthogonal functions was introduced. It was shown how selecting the proper function basis for the signal can significantly reduce both the accuracy of the prediction and the number of calculations that the device had to perform. We assumed that hum is in the form of a sine wave and added different phases of the impairment to a moving picture. By using this method, we found that the experimental results agreed with our theoretical predictions. Chapter 5. CONCLUSION^ 76 5.3 SNOW NOISE Finally, snow noise was studied. This is a random noise, characterized by a weak television signal, that produces a uniformly fine snowstorm effect on the screen. A technique is proposed to detect snow noise in which each pixel is compared to its local area. Since, typically, snow noise produces many isolated pixels whose values are quite different from their neighbours, we simply take a weighted count of the number of isolated pixels to estimate of the amount of snow in the image. Several pictures were tested with varying degrees of snow noise. By applying the detection algorithm to each image a graph was produced which related the predicted amount of noise to the actual carrier-to-noise ratio of the image. It was seen from this graph that the results will produce fairly accurate predictions for images that are moderately to severely impaired by snow noise. BIBLIOGRAPHY [1] Bachman, Scott. "Reliability in Cable Systems" Specs International June 1992 : 5-8. [2] Bartlett, Eugene R.^Cable Television Technology and Operations : HDTV and NTSC Systems New York : McGraw-Hill Publishing Company, 1990. [3] Bednarek, Robert A. "On Evaluating Impaired Television Pictures By Subjective Measurements." Transactions On Broadcasting Vol BC-25, No 2 (June 1979) : 41-46. [4] Cable Television Picture Impairment Guide. Chart. Ottawa : Cable Telecommunications Research Institute, n.d. [5] Ciciora, Walter S. "An Introduction to Cable Television in the United States." IEEE LCS Magazine February 1990 : 19-25. [6] Davis, Harry F. Fourier Series and Orthogonal Functions Boston : Allyn and Bacon, Inc, 1963. [7] Drewery, J. 0. "An Adaptive Noise Reducer For PAL And NTSC Signals." Internation Broadcasting Convention Conference Publication 166 London, (1978): 231-237. [8] Fink, Donald G., and Donald Christiansen. Electronics Engineers' Handbook 3rd Ed. New York : McGraw-Hill Book Company, 1989. [9] Gresseth, R., and R K Ward. Automatic Recognition Of The Hum Impairment In Cable Television Systems Proc. of the CSECE Conference, Toronto, September 1992 : TM5.13.1-TM5.13.4. [10] Hawker, J. P. Outline of Radio and Television London : George Newnes Limited, 1966. [11] Krauss, Herbert L., Charles W Bostian, and Frederick H Raab. Solid State Radio Engineering New York : John Wiley and Sons, Incorporated, 1980. [12] Mambo, P. L., and D C Coll. "Perceived Picture Quality In CATV Systems With Impairments." Cable Television Vol 4 (January 1979) : 10-16. 77 BIBLIOGRAPHY^ 78 [13] Martin, A. V. J. Technical Television Englewood Cliffs : Prentice-Hall, Incorporated, 1962. [14] Meyer, Robert G., Mark J Shensa, and Ralph Eschenbach "Cross Modulation and Intermodulation in Amplifiers at High Frequencies." IEEE Journal Of Solid-State Circuits Vol SC-7, No 1 (February 1972) : 16-23. [15] Osborne, B. W. "The Assessment Of Picture Quality On Cable Television Systems By Means Of Engineering Auits." Transactions On Cable Television Vol CATV-2, No 2 (April 1977) : 95-98. [16] Pomerleau, Andre, and Dany Sylvain. "Quality Measurement Of Television Picture By Eye Simulation." Transactions On Broadcasting Vol 28 (March 1982) : 27-36. [17] Press, William H., Brian P Flannery, Saul A Teukolsky, and William T Vetterling. Numerical Recipes in C Combridge : Cambridge University Press, 1989. [18] Sasaki, Tai, and Hiroshi Hataoka. "An Intermodulation Prediction And Measurement Technique For Multiple Carriers Through Weak Nonlinearities." Cable Television Vol 4 (October 1979) : 146-154. [19] Taylor, Ralph E. Radio Frequency Interference Handbook Goddard Space Flight Center, MD : NASA, 1971. [20] Thomas, Spencer W. Utah Raster Toolkit Version 3.0. Computer Software. University of Utah, 1986. UNIX. [21] Zhang, Q., and R K Ward. Automatic Identification Of Impairments Caused By Intermodulation Distortion In Cable Television Pictures IEEE Trans on Broadcasting Vol 38, No 1, March 1992 : 60-68. [22] Zhang, Q., R K Ward, and R Gresseth. An Automatic System Which Detects Intermodulation Impairments in Cable TV Pictures Proc. of the Cdn. Conf. on Electr. and Computer Eng., Sept 1991 : 28.2.1-28.2.4.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The automatic recognition of intermodulation, hum and...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The automatic recognition of intermodulation, hum and snow noise in cable television systems Gresseth, Reidar 1992
pdf
Page Metadata
Item Metadata
Title | The automatic recognition of intermodulation, hum and snow noise in cable television systems |
Creator |
Gresseth, Reidar |
Date Issued | 1992 |
Description | A system which automatically monitors the cable television signal is proposed. The monitoring devices, located at key areas in the television network, would alert the cable company to the presence of several important types of television impairments. In this thesis, the automatic detection of three kinds of impairments is discussed; intermodulation carrier beats, hum modulation and snow noise. The detection algorithms we develop are non-intrusive and do not require the use of test signals. A mathematical model which describes an intermodulation carrier beat is developed and the corresponding 2-dimensional Fourier transform is shown to exhibit properties which are advantageous for automatic recognition. In particular, it is shown that four peaks will appear in the Fourier transform of the image if a beat is present. These peaks possess distinguishing characteristics which allow the automatic detection of the beat. Another television impairment, hum modulation, causes either single or double bands on the television screen depending upon the impairment's frequency. By using the theory of orthogonal functions developed by Sturm and Liouville, a general algorithm is developed which recognizes hum modulation or any impairment of a fixed and known shape. The algorithm is applied to the case of a sinusoidal hum function. Finally, snow noise, which is a random white Gaussian noise, is addressed. An algorithm is developed which detects these random variations by comparing each pixel in the image with neighbouring points. Experimental verification done with several images is shown to produce good results even if the level of noise is small (up to carrier to noise ratio of 35 dB). |
Extent | 6187976 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-08-12 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065246 |
URI | http://hdl.handle.net/2429/1368 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1993_spring_gresseth_reidar.pdf [ 5.9MB ]
- Metadata
- JSON: 831-1.0065246.json
- JSON-LD: 831-1.0065246-ld.json
- RDF/XML (Pretty): 831-1.0065246-rdf.xml
- RDF/JSON: 831-1.0065246-rdf.json
- Turtle: 831-1.0065246-turtle.txt
- N-Triples: 831-1.0065246-rdf-ntriples.txt
- Original Record: 831-1.0065246-source.json
- Full Text
- 831-1.0065246-fulltext.txt
- Citation
- 831-1.0065246.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065246/manifest